Git 3.0 will make SHA-256 the new default content hashing algorithm and it will be an incomprehensibly expensive and ultimately valueless and avoidable global nightmare.
You are proposing a second preimage attack (generate a file (called “the preimage of the hash” in the jargon) with a predetermined hash), not a collision attack (generate two files with any hash so long as they hash the same).
A second preimage attack’s expected cost for a secure hash is the full size of the hash: 2^256 trial hashes for SHA-256 or 2^160 trials for SHA-1. (Or to be precise, 2^255 and 2^159 because you expect to find a match before testing every possibility.)
A collision attack benefits from the birthday paradox so its expected cost is the square root, or half the exponent, so 2^128 trials for SHA256 or 2^80 trials for SHA-1. The standard security level for cryptographic operations is 2^128 symmetric ops, which SHA256 passes but SHA-1 does not.
The weaknesses in SHA-1 reduce a collision attack from 2^80 to about 2^61 trials, which is feasible to carry out in a reasonable length of time.
SHA-1 is not vulnerable to second preimage attacks at least partly because squaring the number of trials makes the attack unfeasible even for a weak hash. Even MD5 is not vulnerable to second preimage attacks.
Is the nature of SHA-1, or any commonly used cryptographically secure hash function, that it is not any harder to just put the random bytes necessary to make some malicious file collide with a benign one anywhere you want than it would be to construct an meaningless string from scratch that collides? Like could I put them in some unused segment of an ELF binary, or something?
That’s not a rhetorical question, I’m just curious.
There are subclasses of collision attacks that depend on details of how the collision is constructed.
Merkle-Damgård hash functions (like MD5, SHA-1, SHA-2) are subject to length extension because the hash value exposes the entire state of the function, so once you know h(M) you can calculate h(M++X) for any suffix X of your choice, and if you have a collision h(M) == h(M’) you can also calculate h(M++X) and h(M’++X). Depending on the details of the file format this can make collisions more powerful, because the colliding prefix can select different parts of the suffix so a single collision calculation can be reused for lots of different versions of an attack. The shattered collision used this in PDF, where the suffix X contained both the benign and malicious payloads, and the colliding prefixes M and M’ chose which payload to display.
In a collision attack, M is typically split into a prefix P and some carefully-constructed blocks C that cause the collision. The C blocks are a random mess. There are roughly three classes of collision attacks depending on the structures of M==P++C and M’==P’++C’:
P==P’ == “” - classical collision attack which in practice does not allow enough control over the structure of the message to create interesting attacks.
P==P’ != “” - this is a “free start” collision attack, which allows the attacker to construct a prefix of a valid file in some format that can be used for length extension attacks, as in the shattered collision.
P != P’ - a chosen-prefix attack, which allows two different files to be extended in a way that causes them to collide, almost as powerful as a second-preimage collision.
You are proposing a second preimage attack (generate a file (called “the preimage of the hash” in the jargon) with a predetermined hash), not a collision attack (generate two files with any hash so long as they hash the same).
A second preimage attack’s expected cost for a secure hash is the full size of the hash: 2^256 trial hashes for SHA-256 or 2^160 trials for SHA-1. (Or to be precise, 2^255 and 2^159 because you expect to find a match before testing every possibility.)
A collision attack benefits from the birthday paradox so its expected cost is the square root, or half the exponent, so 2^128 trials for SHA256 or 2^80 trials for SHA-1. The standard security level for cryptographic operations is 2^128 symmetric ops, which SHA256 passes but SHA-1 does not.
The weaknesses in SHA-1 reduce a collision attack from 2^80 to about 2^61 trials, which is feasible to carry out in a reasonable length of time.
SHA-1 is not vulnerable to second preimage attacks at least partly because squaring the number of trials makes the attack unfeasible even for a weak hash. Even MD5 is not vulnerable to second preimage attacks.
score 3 · canonical
Is the nature of SHA-1, or any commonly used cryptographically secure hash function, that it is not any harder to just put the random bytes necessary to make some malicious file collide with a benign one anywhere you want than it would be to construct an meaningless string from scratch that collides? Like could I put them in some unused segment of an ELF binary, or something? That’s not a rhetorical question, I’m just curious.
score 1 · canonical
There are subclasses of collision attacks that depend on details of how the collision is constructed.
Merkle-Damgård hash functions (like MD5, SHA-1, SHA-2) are subject to length extension because the hash value exposes the entire state of the function, so once you know h(M) you can calculate h(M++X) for any suffix X of your choice, and if you have a collision h(M) == h(M’) you can also calculate h(M++X) and h(M’++X). Depending on the details of the file format this can make collisions more powerful, because the colliding prefix can select different parts of the suffix so a single collision calculation can be reused for lots of different versions of an attack. The shattered collision used this in PDF, where the suffix X contained both the benign and malicious payloads, and the colliding prefixes M and M’ chose which payload to display.
In a collision attack, M is typically split into a prefix P and some carefully-constructed blocks C that cause the collision. The C blocks are a random mess. There are roughly three classes of collision attacks depending on the structures of M==P++C and M’==P’++C’:
P==P’ == “” - classical collision attack which in practice does not allow enough control over the structure of the message to create interesting attacks.
P==P’ != “” - this is a “free start” collision attack, which allows the attacker to construct a prefix of a valid file in some format that can be used for length extension attacks, as in the shattered collision.
P != P’ - a chosen-prefix attack, which allows two different files to be extended in a way that causes them to collide, almost as powerful as a second-preimage collision.
score 1 · canonical
The fact that this is well-taxonomized is exactly what I was wondering about; good answer. Thanks.
score 1 · canonical
deleted by creator
deleted by creator