Merkle-Damgard construction

compression function $f:\{0,1\}^b\times\{0,1\}^b \rightarrow \{0,1\}^b$.

Now we have the following structure:

if $f$ is collision-resistant then $h$ is collision-resistant.

proof

• if $n\neq n'$ then the last block of $f$ has a collision
• if $n = n'$ then
  • the last blocks differ and there was a collision
  • if not we can iterate to the previous block and find the block with a collision

length-extension: this is why it’s different from random function. Knowing the hash of a prefix helps us construct the hash of the whole message.

Attacks on hash functions

A nice presentation on various attacks.

For even more info I recommend Martin Mareš's notes or boards.

• birthday
  • better with parameterized messages
  • memory saving with hare, tortoise, and turtle technique (constant memory)
• collision between good and bad messages
  • used when there is someone who signs only good messages
• multiple collisions in M.D.
  • when the compression function is not collision-resistant it is possible to find a collision for the first block, then given it find a collision for the second block, and so on. This yields $2^k$ messages where $k$ is the number of blocks.
  • Allows us to attack efficiently the following when one of the hashes is M.D. It is easy because we only need to bruteforce the second hash after we find multicollisions in the first. $$h(x) = h_1(x) || h_2(x)$$

Davies-Meyer construction from a block cipher

Use block cipher to create compression function as $$f(x,y) = E_y(x) \oplus y$$ XOR is needed otherwise we could get $$f(x,y) = E_y(x) = E_z(D_z(E_y(x))) = f(z, D_z(E_y(x)))$$

Also, note that using this construction with arbitrary cipher is dangerous. For example, DES’s complementarity property makes creating collisions easy.

MD5 (Rivest)

The result has $128$b, due to birthday paradox the security level is $64$b which is weak.

Since 2004 we are able to produce collisions easily but it is not yet invertible.

The structure is Merkle-Damgard.

SHA-1 (NSA)

The structure is Merkle-Damgard.

We can produce collisions but it is not that easy (Google was needed to do it).

SHA-2 (NSA)

family of functions. Similar to SHA-1 but stronger and slower. No serious weaknesses were found at the time of writing this.

SHA-$224$, $256$, $384$, $512$.

SHA-3 (NIST competition)

family of functions

Sponge construction

security level is $min(r/2, c/2)$ due to the inner collision attack.

inner collision attack

you feed in zeros and wait till the “lower” (capacity) part repeats ($2^{c/2}$ steps needed). This gives us messages when one is a prefix of the other. The last block of the longer message si then set so that the “upper” (rate) part is the same as the “upper” part for the prefix message.

based on Keccak $1600$ bit permutation.

SHA-3

• $256$ $1152$ (r) $512$ (c)
• $512$ $576$ (r) $1024$ (c)

SHAKE can be used as PRNG

• $128$ $1344$ (r) $256$ (c)
• $256$ $1088$ (r) $512$ (c)

Merkle trees

A convenient way to hash databases or anything where some part of the data changes often.

The structure of the tree must be hashed to output, otherwise, some extension or truncation attacks are possible.

Security

can be defined like this: the attacker possesses a signing oracle and wants to produce a correct signature on a message that was not presented to the oracle

HMAC

today pretty much THE way to do MACs.

Combining with encryption

Shanon-secure MACs

Given a known pair of x and sign(x) all signatures of x’ different from x are equally probable for a random key.

one-time key

requires keys $2$ times the size of the message, so unusable in practice.

2-independence

GCM and Poly1305