the cryptopals crypto challenges

• Challenges
• Set 7
• Challenge 53

Kelsey and Schneier's Expandable Messages

One of the basic yardsticks we use to judge a cryptographic hash function is its resistance to second preimage attacks. That means that if I give you x and y such that H(x) = y, you should have a tough time finding x' such that H(x') = H(x) = y.

How tough? Brute-force tough. For a 2^b hash function, we want second preimage attacks to cost 2^b operations.

This turns out not to be the case for very long messages.

Consider the problem we're trying to solve: we want to find a message that will collide with H(x) in the very last block. But there are a ton of intermediate blocks, each with its own intermediate hash state.

What if we could collide into one of those? We could then append all the following blocks from the original message to produce the original H(x). Almost.

We can't do this exactly because the padding will mess things up.

What we need are expandable messages.

In the last problem we used multicollisions to produce 2^n colliding messages for n*2^(b/2) effort. We can use the same principles to produce a set of messages of length (k, k + 2^k - 1) for a given k.

Here's how:

• Starting from the hash function's initial state, find a collision between a single-block message and a message of 2^(k-1)+1 blocks. DO NOT hash the entire long message each time. Choose 2^(k-1) dummy blocks, hash those, then focus on the last block.
• Take the output state from the first step. Use this as your new initial state and find another collision between a single-block message and a message of 2^(k-2)+1 blocks.
• Repeat this process k total times. Your last collision should be between a single-block message and a message of 2^0+1 = 2 blocks.

Now you can make a message of any length in (k, k + 2^k - 1) blocks by choosing the appropriate message (short or long) from each pair.

Now we're ready to attack a long message M of 2^k blocks.

1. Generate an expandable message of length (k, k + 2^k - 1) using the strategy outlined above.
2. Hash M and generate a map of intermediate hash states to the block indices that they correspond to.
3. From your expandable message's final state, find a single-block "bridge" to intermediate state in your map. Note the index i it maps to.
4. Use your expandable message to generate a prefix of the right length such that len(prefix || bridge || M[i..]) = len(M).

The padding in the final block should now be correct, and your forgery should hash to the same value as M.