5 ms·

Is there an archive of crypto related future predictions? How long until a specified length preimage attack can break bittorrent blocks? I remember a paper pu

Is there an archive of crypto related future predictions? How long until a specified length preimage attack can break bittorrent blocks? I remember a paper published a ~decade ago estimating very short (well funded) ASIC sha1 collisons. Anyone have that ref? 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.

glandium 7y ago
> How long until a specified length preimage attack can break bittorrent blocks? Even MD5 still doesn't have a known preimage attack, so... many many years?
- tialaramex 7y ago
  To be fair for MD5 there is a known attack, it's just impractical. It's a real attack though because the whole point of a crypto hash is that you'd have to brute force it to win, and the paper shows a slightly quicker way because MD5 is broken. It's just not quick enough that you could actually do it. Oh wait, perhaps you actually meant preimage as you said rather than I assumed second preimage. OK yes, that isn't ever going to be possible for non-trivial inputs.
  - GoblinSlayer 7y ago
    Cheap talk is hardly an attack though.
  - rocqua 7y ago
    I think OP meant 'viable' pre-image attack. Not just an attack that is better than brute force.
pabs3 7y ago
There is one for hashes: http://valerieaurora.org/hash.html http://valerieaurora.org/hash.html
- strenholme 7y ago
  Not to mention this one, which covers more hash algorithms: https://electriccoin.co/blog/lessons-from-the-history-of-attacks-on-secure-hash-functions/ https://electriccoin.co/blog/lessons-from-the-history-of-att...
hannob 7y ago
Preimage is really a whole different beast than collission. It's also not particularly surprising. Just by its length SHA-1 has in its best case 80 bits of collission security and 160 bits of preimage security. Now its important to understand that attacks usually don't cause full devastation, but they usually make attacks a bit better than optimal. Attacks in the 60 bit range is what's possible, attacks in the 70 bit range is what's dangerous. It's easy to imagine that relatively small deviation from optimal security gets SHA-1 from 80 into the dangerous territorry (the attacks are in the low 60s range). However getting from 160 bit down to the 60/70 bit range would require massive improvements in attacks. It's safe to say that SHA-1 is still very far from preimage attacks. Still to be clear I'd still recommend to get rid of it whereever you can. The far bigger risk is that you think you only need preimage security, while you actually need collission security for scenarios you haven't thought about.
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 ago
  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.
  - wyoung2 7y ago
    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_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.

glandium 7y ago

> How long until a specified length preimage attack can break bittorrent blocks? Even MD5 still doesn't have a known preimage attack, so... many many years?

tialaramex 7y ago
To be fair for MD5 there is a known attack, it's just impractical. It's a real attack though because the whole point of a crypto hash is that you'd have to brute force it to win, and the paper shows a slightly quicker way because MD5 is broken. It's just not quick enough that you could actually do it. Oh wait, perhaps you actually meant preimage as you said rather than I assumed second preimage. OK yes, that isn't ever going to be possible for non-trivial inputs.
- GoblinSlayer 7y ago
  Cheap talk is hardly an attack though.
- rocqua 7y ago
  I think OP meant 'viable' pre-image attack. Not just an attack that is better than brute force.

pabs3 7y ago

There is one for hashes: http://valerieaurora.org/hash.html http://valerieaurora.org/hash.html

strenholme 7y ago
Not to mention this one, which covers more hash algorithms: https://electriccoin.co/blog/lessons-from-the-history-of-attacks-on-secure-hash-functions/ https://electriccoin.co/blog/lessons-from-the-history-of-att...

hannob 7y ago

Preimage is really a whole different beast than collission. It's also not particularly surprising. Just by its length SHA-1 has in its best case 80 bits of collission security and 160 bits of preimage security. Now its important to understand that attacks usually don't cause full devastation, but they usually make attacks a bit better than optimal. Attacks in the 60 bit range is what's possible, attacks in the 70 bit range is what's dangerous. It's easy to imagine that relatively small deviation from optimal security gets SHA-1 from 80 into the dangerous territorry (the attacks are in the low 60s range). However getting from 160 bit down to the 60/70 bit range would require massive improvements in attacks. It's safe to say that SHA-1 is still very far from preimage attacks. Still to be clear I'd still recommend to get rid of it whereever you can. The far bigger risk is that you think you only need preimage security, while you actually need collission security for scenarios you haven't thought about.

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 ago
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.
- wyoung2 7y ago
  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_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.