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

That was a later attack, not the original. Attacks get cheaper with time.

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

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

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.

? How are nonces even involved in this?

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.

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.

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

Crytographic nonce > hashing: https://en.wikipedia.org/wiki/Cryptographic_nonce#Hashing

> 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?

Practically, iff browsers still relied upon SHA-1 to fingerprint and pin and verify certificates instead of the actual chain, and there were no file size limits on x.509 certificates, some fields in a cert (e.g. CommonName and SAN) would be chosen and other fields would then potentially be nonce.

In context to finding a valid cert with a known good hash fingerprint, how many prime keypairs could there be to precompute and cache/memoize when brute forcing.

"SHA-1 > Cryptanalysis and validation " does list chosen prefix collision as one of many weaknesses now identified in SHA-1: https://en.wikipedia.org/wiki/SHA-1#Cryptanalysis_and_valida...

This from 2008 re: the 200 PS3s it took to generate a rogue CA cert with a considered-valid MD5 hash: https://hackaday.com/2008/12/30/25c3-hackers-completely-brea...

... Was just discussing e.g. frankencerts the other day: https://news.ycombinator.com/item?id=26605647