Hacker News Reader

Comment by SAI_Peregrinus | Hacker News Reader

1.5 Chosen-prefix collision: Given a prefix A, generate two values AB and AC, where B and C differ but are both prefixed with A. (AX is A concatenated with X). This exists for SHA1. It's more powerful than a basic collision wheri you can't pick the prefix, but weaker than either type of pre-image.

View on HN

It's worth noting that this attack is a property of the Merkle–Damgård hash construction, not of SHA-1 specifically, which means SHA-2 (Git's path forward) is also vulnerable:

https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_co...

https://www.reddit.com/r/crypto/comments/44p5jc/eli5_why_are...

Fossil uses SHA-3, which has an entirely different construction, which is not at this time known to have a similar weakness. SHA-3 is also much newer, with a much shorter list of known attacks.

Ha that ELI5 is adorable, I love both how the person trying to answer in the affirmative resorts to more and more frantic hand-waving as it becomes obvious none of what they've said is true and most of it doesn't even make sense, while the person being "flagged" for their supposedly "highly inaccurate" simple statement that er, no, chosen prefix isn't about MD at all remains calm and doesn't care as people insist they must be wrong because after all they were flagged, and why would some anonymous user flag something as wrong unless they were an expert...

Anyway, as hinted above, chosen prefix has nothing to do with the type of hash construction, except in the sense that so far there were lots of Merkle–Damgård hashes and some of them are no longer safe, whereas until recently there weren't many of the Keccak family hashes.

The Wikipedia article is talking about Length Extension, which is a different phenomenon from chosen prefix collision attacks, and if it was a problem in Git (or indeed Fossil) would have doomed them both immediately anyway.

For a generic crypto hash you should use SHA-512/256 (NB this is not offering a choice that slash is part of the name) to avert Length Extension but since the DVCSs already seemingly put the effort in to be safe against it SHA-256 is a perfectly reasonable choice.

No, it's not the same as length extension. SHA1 is vulnerable to Chosen Prefix collisions. SHA2 doesn't have any known collision attacks faster than the birthday bounded brute force attack, let alone any chosen prefix collisions, but both do have length extension attacks. Also length extension isn't specific to Merkle–Damgård, though all Merkle–Damgård hashes are vulnerable to it without mitigations (like truncation of the output).

Reply on news.ycombinator.com