4 ms·

The first problem is called collision resistance. The second is called second pre-image resistance. https://en.wikipedia.org/wiki/Cryptographic_hash_function#

The first problem is called collision resistance. The second is called second pre-image resistance. https://en.wikipedia.org/wiki/Cryptographic_hash_function#Properties https://en.wikipedia.org/wiki/Cryptographic_hash_function#Pr...

jobigoud 11y ago
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.
- jebed091 11y ago
  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.
  - kkl 11y ago
    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?
    - dunkelheit 11y ago
      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)
      - kkl 11y ago
        Thanks for clarifying. That is a really concise explanation.

jobigoud 11y ago

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.

jebed091 11y ago
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.
- kkl 11y ago
  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?
  - dunkelheit 11y ago
    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)
    - kkl 11y ago
      Thanks for clarifying. That is a really concise explanation.