4 ms·
> EDIT: Should I have not said preimage? My understanding is bittorrent is broken (by DDoS, not infohash(?)) if you can make a bad block that matches the length
by tialaramex 7y ago
> EDIT: Should I have not said preimage? My understanding is bittorrent is broken (by DDoS, not infohash(?)) if you can make a bad block that matches the length and sha1 of a target block.
There are three different attacks
1. Collision, which is practical (expensive but practical) for SHA-1 today, lets somebody make two documents A and B which have the same hash. This is only useful if you can fool people somehow into accepting document B when they think it's document A because of the hash, for example with digital signatures.
2. Pre-image, which is not practical for any hashes you care about including MD5. This lets you find the document A given the hash(A) value. This is very niche, since obviously for large documents by the pigeon hole principle there will be many such pre-images and it's impossible to get the "right" one, for small inputs it can be relevant, sometimes.
3. Second Pre-image, likewise not practical. Given either document A or hash(A) which you could easily determine from document A, this lets you produce a new document A' that is different from A but hash(A') == hash(A). This would be extremely bad, and is what you'd need to attack real world Bittorrent from somebody else.
Often people say "pre-image" meaning strictly second pre-image, it's usually clear from context, and a true pre-image attack as I explained above is only rarely relevant.
Collision would only let bad guys corrupt their own purposefully constructed collision bittorrent, which like, why? So yes, Bittorrent would only really be in serious trouble if there was a second pre-image attack. But on the other hand, don't use broken cryptographic primitives. Attacks only get better, always.
- SAI_Peregrinus 7y ago1.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.
- wyoung2 7y agoIt'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_construction#Security_characteristics https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_co... https://www.reddit.com/r/crypto/comments/44p5jc/eli5_why_are_chosenprefix_collisions_specific_to/ 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.
- tialaramex 7y agoHa 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.
- SAI_Peregrinus 7y agoNo, 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).
- dfox 7y agoThe reason why people mostly meand second pre-image when saying unqualified "pre-image" is that probably any imaginable method of reversing a hash function (given sufficiently long input to the hash) will with overwhelming probability produce hash input that is different from the original.
- jakeogh 7y agoThanks. Is there a name for collision with the same preimage size?