Cryptographic hash

February 14, 2021

A cryptographic hash function is an algorithm that maps messages of arbitrary size to a fixed-size bit array.

For example, try the following two commands in Bob's engine:

sha256 bob
sha256 bab

Yeah, there seems to be a private joke among Alice's friends – they like to say Bab instead of Bob. The reason is unknown and the whole thing is not confirmed, but it seems very likely. How come? How does Bob know it? Well, Alice has mistakenly called him Bab a couple of times. She quickly corrected herself, but Bab noticed it.

Bob's engine

The two outputs provided by sha256 seem to be completely uncorrelated, although the input values (bob and bab) are similar. This is called the avalanche effect – a small change to a message changes the hash value extensively.

Other properties of the cryptographic hashes are:

  • The same message always results in the same hash.
  • It is fast to compute for any given message.
  • It is infeasible to generate a message that yields a given hash value.
  • It is infeasible to find two different messages with the same hash value.

Some of these properties bother Bob. How come you can't generate a message that yields a particular hash value? Isn't this simply finding the inverse of the hash function? Well, it turns out that finding an inverse for these types of functions is not simple at all.

However, after a few late nights, Bob has discovered a function that he plans to submit to one of the upcoming hash function competitions.

The function is defined as follows: let's say we have a message 458198, bob-256 then does:

bob-256(458198) = 4 + 5 + 8 + 1 + 9 + 8 = 35

Can you reconstruct an original message from the hash value 35? Not without a lot of luck! Smart, huh? The function is extremely fast too.

Ok, there are a few little things that need tweaking, but that probably won't be a problem for Bob. For example, you can get messages that are hashed into 35 (for example 9998 or 8999) pretty quickly, the length of the output is not constant, and there is no avalanche effect. But these issues will eventually be overcome and Bob has a pretty good chance of winning a cryptographic competition.

The Alice and Bob newsletter

Get highlights of Alice and Bob's adventures delivered to your email box.

Made by XLAB with ❤️
Follow us
Twitter Twitter