4 ms·

Does the algorithm solve the problem of "find me any two pieces of data that produce a clash" (thereby taking advantage of the Birthday Paradox), or does it say

Does the algorithm solve the problem of "find me any two pieces of data that produce a clash" (thereby taking advantage of the Birthday Paradox), or does it say "given this piece of data, output data who's SHA-1 sum is the same"? I assume that the second problem would be harder to solve - but I'm not sure by what order of magnitude. If it's the former, what are the practical applications of the attack?

ddlatham 11y ago
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.

ddlatham 11y ago

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.