7 ms·

> it'd be quite easy for them to generate two different versions of the same file Citation needed. When SHA1 was cracked, it cost $110k worth of cloud computin

> it'd be quite easy for them to generate two different versions of the same file Citation needed. When SHA1 was cracked, it cost $110k worth of cloud computing. And there was some restriction on the two files which matched checksums. IIRC it was like the Birthday Paradox — you don’t pick one and find another sharing the same match, but you generate billions of mutations of similar binaries and statistically two would have the same checksum. Not exactly easy, fast, cheap, or work with all use cases.

cratermoon 6y ago
It was $11K https://www.usenix.org/conference/usenixsecurity20/presentation/leurent https://www.usenix.org/conference/usenixsecurity20/presentat...
- bawolff 6y ago
  That was a later attack, not the original. Attacks get cheaper with time.
westurner 6y ago
That nonce value could be ±\0 or 5,621,964,321e100; though for well-designed cryptographic hash functions it's far less likely that - at maximum difficulty - a low nonce value will result in a hash collision.
- bawolff 6y ago
  ? How are nonces even involved in this?
  - westurner 6y ago
    Searching for the value to prepend or append that causes a hash collision is exactly the same as finding a nonce value at maximum difficulty (not less than the difficulty value, exactly equal to the target hash). Mutate and check.
    - bawolff 6y ago
      The term nonce has a broader meaning than how it is used in bitcoin. (Edit: i reworded this sentence from what i originally had) That said, no, finding a collision and finding a preimage are very different things, and well the collision attacks on sha1 will involve a lot of guessing and checking, they are not generic birthday or bruteforce attacks but rely on weaknesses in sha-1 to be practical. They also do not make preimage attacks practical.
      - westurner 6y ago
        Brute forcing to find `hash(data_1+nonce) == hash(data_0)` differs very little from ``hash(data_1+nonce) < difficulty_level`. Write each and compare the cost/fitness/survival functions. If the hash function is reversible - as may be discovered through e.g. mutation and selection - that would help find hashes that are equal and maybe also less than. Practically, there are "rainbow tables" for very many combinations of primes and stacked transforms: it's not necessary to search the whole space for simple collisions and may not be necessary for preimages; we don't know and it's just a matter of time. "Collision attack" https://en.wikipedia.org/wiki/Collision_attack https://en.wikipedia.org/wiki/Collision_attack Crytographic nonce > hashing: https://en.wikipedia.org/wiki/Cryptographic_nonce#Hashing https://en.wikipedia.org/wiki/Cryptographic_nonce#Hashing
        bawolff 6y ago
        > Brute forcing The attack being discussed is not a brute force attack (or not purely). If the best attack on sha1 was bruteforce than we would still be using it. > to find `hash(data_1+nonce) == hash(data_0)` differs very little from ``hash(data_1+nonce) < difficulty_level`. Neither of those are collision attacks (assuming you dont control the data variable). The first is a second pre-image and the second (with equality) would be a normal preimage. The attack for sha1 under discussion (chosen prefix collision) is finding hash(a+b) == hash(c+d) where you control b and d (but not neccesarily a and c) > Practically, there are "rainbow tables" for very many combinations of primes and stacked transforms: What do primes or rainbow tables have to do with any of this? Primes especially. Rainbow tables are at least related to reversing hashes, if totally irrelavent to the subject at hand, but how did you get to primes?
bawolff 6y ago
Later versions of the attack were much cheaper and also chosen prefix collisions which are much less restrictive in the requirements on the file.
petertodd 6y ago
> And there was some restriction on the two files which matched checksums. I know. That's why I mentioned the difference in difficulty between getting a collision in binary files and git commit objects themselves, and textual sourcecode.

cratermoon 6y ago

It was $11K https://www.usenix.org/conference/usenixsecurity20/presentation/leurent https://www.usenix.org/conference/usenixsecurity20/presentat...

bawolff 6y ago
That was a later attack, not the original. Attacks get cheaper with time.

westurner 6y ago

That nonce value could be ±\0 or 5,621,964,321e100; though for well-designed cryptographic hash functions it's far less likely that - at maximum difficulty - a low nonce value will result in a hash collision.

bawolff 6y ago
? How are nonces even involved in this?
- westurner 6y ago
  Searching for the value to prepend or append that causes a hash collision is exactly the same as finding a nonce value at maximum difficulty (not less than the difficulty value, exactly equal to the target hash). Mutate and check.
  - bawolff 6y ago
    The term nonce has a broader meaning than how it is used in bitcoin. (Edit: i reworded this sentence from what i originally had) That said, no, finding a collision and finding a preimage are very different things, and well the collision attacks on sha1 will involve a lot of guessing and checking, they are not generic birthday or bruteforce attacks but rely on weaknesses in sha-1 to be practical. They also do not make preimage attacks practical.
    - westurner 6y ago
      Brute forcing to find `hash(data_1+nonce) == hash(data_0)` differs very little from ``hash(data_1+nonce) < difficulty_level`. Write each and compare the cost/fitness/survival functions. If the hash function is reversible - as may be discovered through e.g. mutation and selection - that would help find hashes that are equal and maybe also less than. Practically, there are "rainbow tables" for very many combinations of primes and stacked transforms: it's not necessary to search the whole space for simple collisions and may not be necessary for preimages; we don't know and it's just a matter of time. "Collision attack" https://en.wikipedia.org/wiki/Collision_attack https://en.wikipedia.org/wiki/Collision_attack Crytographic nonce > hashing: https://en.wikipedia.org/wiki/Cryptographic_nonce#Hashing https://en.wikipedia.org/wiki/Cryptographic_nonce#Hashing
      - bawolff 6y ago
        > Brute forcing The attack being discussed is not a brute force attack (or not purely). If the best attack on sha1 was bruteforce than we would still be using it. > to find `hash(data_1+nonce) == hash(data_0)` differs very little from ``hash(data_1+nonce) < difficulty_level`. Neither of those are collision attacks (assuming you dont control the data variable). The first is a second pre-image and the second (with equality) would be a normal preimage. The attack for sha1 under discussion (chosen prefix collision) is finding hash(a+b) == hash(c+d) where you control b and d (but not neccesarily a and c) > Practically, there are "rainbow tables" for very many combinations of primes and stacked transforms: What do primes or rainbow tables have to do with any of this? Primes especially. Rainbow tables are at least related to reversing hashes, if totally irrelavent to the subject at hand, but how did you get to primes?

bawolff 6y ago

Later versions of the attack were much cheaper and also chosen prefix collisions which are much less restrictive in the requirements on the file.

petertodd 6y ago

> And there was some restriction on the two files which matched checksums. I know. That's why I mentioned the difference in difficulty between getting a collision in binary files and git commit objects themselves, and textual sourcecode.