Hacker News Reader

Comment by jobigoud | Hacker News Reader

So, what is a freestart collision?

The two messages from OP have many bytes in common. I would expect a hashing function like SHA-1 to give wildly different outputs given similar inputs due to the avalanche effect.

View on HN

It's a collision if you can choose the IV. That's not much practical use, it's just an interesting demonstration that confirms research is slowly progressing towards a real collision.

SHA-1 uses a Merkle-Damgard construction, which means the input is split into fixed-size blocks and the output from one block becomes the IV for the next. This is because SHA-1 operates on a fixed-size, so if you have more than 1 block of data, it's chained together like this:

  char *SHA1(char *IV, char *block);

  Digest = SHA1(SHA1(SHA1(StartIV, block1), block2), block3);

A freestart collision is a collision if you can choose the IV. That's not much use, because we don't know how to find a block (or chain of blocks) that produce the IV we want.

To make sure I understand correctly:

Suppose I had the magical ability to find a special value that would equal the IV listed in the link (i.e. 506b0178ff6d1890....) when that special value was applied to SHA-1. I could then use the results from this research to compute a collision using input that is prefixed with that special value?

Yes. If you are able to construct P1 such that SHA1(P1) = IV1 and P2 s.t. SHA1(P2) = IV2, then

    SHA1(P1 + padding(P1) + M1) = SHA1(P2 + padding(P2) + M2) = f020486f071bf11053547a86f4a7153b3c950f4b

where padding(M) is the padding appended to message M as the first step of computing SHA1.

(edit: clarified padding)

Thanks for clarifying. That is a really concise explanation.

Reply on news.ycombinator.com