The Indifferentiability Property for the Perfect Message Hash

The Indifferentiability Property for the Perfect Message Hash

When we look at twins, we might say they are indistinguishable from each other. But would we say that they have indifferentiability property? Well, not quite, but they relate to each other, and where, as human, we have thrived as a species because we differ from each other — we have a differentiability property in our creation. In cryptography, we strive for perfect randomness, and where it is not possible for an adversary to gain an advantage on the way we have created ciphertext. We thus need to make our ciphertext look as much as random as possible. When we creating the perfect message hash, we need to make sure we have:

• Collision resistance. This is where it is extremely difficult to find two messages which have the same hash.
• Pre-image resistance. If we already have a hash value (h), it should be extremely difficult to find a message which will give the same hash.

The original hash methods were often based on the Merkle-Damgård (MD) construction. With this, we create a hash function using blocks of data. From this Ron Rivest created the MD5 hashing method. Overall we take a static initialisation vector (IV) and then feed this into a one-way function (f) along with a block of the message. We feed this output into the next stage, and so on until we get to a message pad at the end:

The one-way function (f) will generally compress the data and produce fewer bits out than are fed in. Unfortunately, the MD construct has many weaknesses, such as with the length extension attack, and where an adversary can take a hash for an unknown message, and then add additional data to produce a new hash. So Bob could take a hash of a secret (“qwerty123”) and append with a message (“hello”), and produce H(Password || Message). This is a message authentication code (MAC) and validates that Bob knows a shared secret and the message. Eve could basically take this hash, and add the text of “ and goodbye”, and generate a new hash of H(Password || Message || EveMessage). When Alice receives this, it looks like it is a valid MAC, as Eve’s message will be “hello goodbye”.

Keyed hashing

With hashing methods, we often use a salt value to change the output of the hashing method. This salt, though, is not secret, and guards against a brute force attack on the hash. In message authentication, we can authenticate a message from Bob to Alice by “signing” the message with a secret that only they know. For this we can use HMAC (Hash-based message authentication code), and which supports most of the commonly used hashing methods such as MD5, SHA1, and SHA-256. The secret and the message are then used to create a hash of a given length.

For keyed hashing, we can use BLAKE2 as it has an indifferentiability property. In this case, Bob and Alice will share a secret key, and then Bob will sign a message with this secret key to produce a MAC, and send the MAC with the message. Alice then checks the MAC for the message with her shared secret. If they match the MAC that Bob sent, Alice knows that Bob sent it.

In the following example, we will check the signature with a valid secret, and with an incorrect one. With indifferentiability, it is not possible for hashes to be distinguishable from each other. Any hash value is thus indistinguishable from a random value, and that no additional information is leaked from the hash.

The coding is here:

from hashlib import blake2b
import hmac, hashlib
from hmac import compare_digest

import sys

m="hello"
bits=64
key="fdf"

if (len(sys.argv)>1):
  bits=int(sys.argv[1])
if (len(sys.argv)>2):
  key=(sys.argv[2])
if (len(sys.argv)>3):
  m=(sys.argv[3])

def sign(msg):
  h = blake2b(digest_size=bits, key=key.encode())
  h.update(msg.encode())
  return h.hexdigest().encode('utf-8')

def verify(msg, sig):
  good_sig = sign(msg)
  return compare_digest(good_sig, sig)

print ("Message: ",m)
print ("Secret key: ",key)
print ("Size: ",bits )

sig = sign(m)

print (f"\nSignature: {sig}")

print (f"\nVerified {m}: ",verify(m, sig))

ver=verify(m+"-", sig)

print (f"Verified {m}-: {ver}")

print ("\n== We can also use Blake for HMAC ==")
hm = hmac.new(key.encode(), digestmod=hashlib.blake2s)
hm.update(m.encode())
print ("\nHMAC: ",hm.hexdigest())

A sample run is:

Message:  hello
Secret key:  fdf
Size:  64

Signature: b'7cb36c835e103f7f4b5a9091074abe1d036d68c62ced9c508e1d409dd2223b54d7b4d9524f2de02559d399301952ec5816362ba8f9fbe8b8d35b64273e51647d'

Verified hello:  True
Verified hello-: False
We can also use Blake for HMAC:

HMAC:  6a9848f2622181412452c2439dcd96dbd5a0231e209750f3ddf6b6a49b3e1dd1

And the code here:

https://repl.it/join/geewqpqi-billbuchanan

Notice that while we can use the BLAKE2 hash on its own for keyed hashing, we can also integrate it with HMAC.

If you are interested, here’s some background around BLAKE2 and BLAKE3