Hacker News Reader

Comment by colinbartlett | Hacker News Reader

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

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).

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.

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.

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

I made a quick visualization of it here, it looks pretty cool:

https://lock.cmpxchg8b.com/shatter/visualize.html?stevens=1

I also added the Shappening vectors:

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.

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-commen...

But the standard IV is hardcoded in the sha libraries right ?

Yes. It's usually not even accessible through the hash function's exposed interface.

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!

If you change it, other SHA1 implementations will not be able to interoperate.

I guess you should follow that Crypto StackExchange question.

http://crypto.stackexchange.com/questions/29695/what-is-a-fr...

Reply on news.ycombinator.com