4 ms·

Can someone with more crypto experience than me explain what a "freestart collision" is?

tptacek 11y ago
Every SHA1 hash starts with an initalization vector, which is a kind of ur-hash: 67452301EFCDAB8998BADCFE10325476C3D2E1F0 The function of SHA1 is to transform this ur-hash into the hash of a specific stream of data. In a freestart collision, attackers start from something other than the initialization vector. Think of it as if they're starting from the hash of some piece of data and then hashing more data into it (that's essentially what they'd be doing).
- fla 11y ago
  But the standard IV is hardcoded in the sha libraries right ?
  - sdevlin 11y ago
    Yes. It's usually not even accessible through the hash function's exposed interface.
  - acveilleux 11y ago
    If you change it, other SHA1 implementations will not be able to interoperate.
  - vzcx 11y ago
    It is an exercise to modify your SHA1 implementation to start hashing from whatever IV you please. If you work through tptacek and friends' wonderful cryptopals puzzles you will have to do just this!
- pbsd 11y ago
  The important bit here is not that the IV is different, but that you can also inject arbitrary differences into the IV. This gives the attacker more freedom than in the usual case, where differences only go into the message.
  - tptacek 11y ago
    Right. The relationship between SHA1 outputs and the IV seemed important to the concept of this being a building block for multicollisions. Also: I think it's pretty surprising to generalists (it certainly was to me!) that the SHA1 hash is literally the transformation of the IV, and that you can pick up the results of a SHA1 hash and keep hashing with it. If you grok this, length extension attacks are obvious, as is the benefit of the truncated SHA-2 variants.
    - taviso 11y ago
      It's definitely a neat demonstration that he can produce a collision for these favourable "neutral-bit" IV's relatively cheaply. I suppose the next steps are to find two inputs that produce favourable IV's, then repeat this process for those, and that seems like it's getting really close. Stevens actually already has the best near-collision in non-reduced SHA-1 I know about from this paper: http://marc-stevens.nl/research/papers/EC13-S.pdf http://marc-stevens.nl/research/papers/EC13-S.pdf I made a quick visualization of it here, it looks pretty cool: https://lock.cmpxchg8b.com/shatter/visualize.html?stevens=1 https://lock.cmpxchg8b.com/shatter/visualize.html?stevens=1 I also added the Shappening vectors: https://lock.cmpxchg8b.com/shatter/visualize.html?shappening=1 https://lock.cmpxchg8b.com/shatter/visualize.html?shappening... It's funny that they actually collide around R74, then he has to diverge again so that when you add the IV (part of the process of creating the IV for the next block) they collide.
    - pbsd 11y ago
      On that note, I was surprised to learn that if all you do is apply some invertible transform to the IV (xor with a constant, swap words, whatever) before processing the last padded block in Merkle-Damgard, you get an indifferentiable hash. This was suggested by John Kelsey way back in 2001 for SHA-2, but never took off: http://www.cs.utsa.edu/~wagner/CS4363/SHS/dfips-180-2-comments1.pdf http://www.cs.utsa.edu/~wagner/CS4363/SHS/dfips-180-2-commen...
- deleted 11y ago
  [deleted]
brohee 11y ago
I guess you should follow that Crypto StackExchange question. http://crypto.stackexchange.com/questions/29695/what-is-a-freestart-collision http://crypto.stackexchange.com/questions/29695/what-is-a-fr...

Every SHA1 hash starts with an initalization vector, which is a kind of ur-hash: 67452301EFCDAB8998BADCFE10325476C3D2E1F0 The function of SHA1 is to transform this ur-hash into the hash of a specific stream of data. In a freestart collision, attackers start from something other than the initialization vector. Think of it as if they're starting from the hash of some piece of data and then hashing more data into it (that's essentially what they'd be doing).

fla 11y ago
But the standard IV is hardcoded in the sha libraries right ?
- sdevlin 11y ago
  Yes. It's usually not even accessible through the hash function's exposed interface.
- acveilleux 11y ago
  If you change it, other SHA1 implementations will not be able to interoperate.
- vzcx 11y ago
  It is an exercise to modify your SHA1 implementation to start hashing from whatever IV you please. If you work through tptacek and friends' wonderful cryptopals puzzles you will have to do just this!
pbsd 11y ago
The important bit here is not that the IV is different, but that you can also inject arbitrary differences into the IV. This gives the attacker more freedom than in the usual case, where differences only go into the message.
- tptacek 11y ago
  Right. The relationship between SHA1 outputs and the IV seemed important to the concept of this being a building block for multicollisions. Also: I think it's pretty surprising to generalists (it certainly was to me!) that the SHA1 hash is literally the transformation of the IV, and that you can pick up the results of a SHA1 hash and keep hashing with it. If you grok this, length extension attacks are obvious, as is the benefit of the truncated SHA-2 variants.
  - taviso 11y ago
    It's definitely a neat demonstration that he can produce a collision for these favourable "neutral-bit" IV's relatively cheaply. I suppose the next steps are to find two inputs that produce favourable IV's, then repeat this process for those, and that seems like it's getting really close. Stevens actually already has the best near-collision in non-reduced SHA-1 I know about from this paper: http://marc-stevens.nl/research/papers/EC13-S.pdf http://marc-stevens.nl/research/papers/EC13-S.pdf I made a quick visualization of it here, it looks pretty cool: https://lock.cmpxchg8b.com/shatter/visualize.html?stevens=1 https://lock.cmpxchg8b.com/shatter/visualize.html?stevens=1 I also added the Shappening vectors: https://lock.cmpxchg8b.com/shatter/visualize.html?shappening=1 https://lock.cmpxchg8b.com/shatter/visualize.html?shappening... It's funny that they actually collide around R74, then he has to diverge again so that when you add the IV (part of the process of creating the IV for the next block) they collide.
  - pbsd 11y ago
    On that note, I was surprised to learn that if all you do is apply some invertible transform to the IV (xor with a constant, swap words, whatever) before processing the last padded block in Merkle-Damgard, you get an indifferentiable hash. This was suggested by John Kelsey way back in 2001 for SHA-2, but never took off: http://www.cs.utsa.edu/~wagner/CS4363/SHS/dfips-180-2-comments1.pdf http://www.cs.utsa.edu/~wagner/CS4363/SHS/dfips-180-2-commen...
deleted 11y ago
[deleted]

brohee 11y ago

I guess you should follow that Crypto StackExchange question. http://crypto.stackexchange.com/questions/29695/what-is-a-freestart-collision http://crypto.stackexchange.com/questions/29695/what-is-a-fr...