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.
How can you use SHA-1 for deduplication in a way that’s not somewhat security-related? If you do file-level deduplication, and someone has a file A backed up, then downloads a file B which collides with A, then restores to a point where they had B on their system, won’t your back-up system have replaced B with A?
Or, to invert it: if I get someone to download file B, won’t I have poisoned their system so that if they ever download A, it gets replaced by my file B upon backup restore?
This seems like an avenue for security issues. Sure, people shouldn’t download files from sources they don’t trust… but also, people don’t expect that merely downloading a file will permanently poison their back-ups.
Well, according to the article, it’s not feasible to create a collision for a file someone already has. Only to create two files that collide with each other. So an attacker would have to make you download two files, which might swap each others contents (although I suppose it’s possible that this could break your backup system, as it’s unexpected). This doesn’t seem that scary to me. This turns the case where they’ve given you malware, into a case where they’ve given you malware that might activate only after a restore.
It’s not too hard to predict the content of some files. For example I could get my malware to hash the same as the GPL license text. Or I could email you some harmless content, which hash-collides with malware that’s already in your backup system. If github (which shares git refs across repos) didn’t have collision protection, I could fork you project, push my malware to my fork, then send you a clean-looking PR.
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.
How can you use SHA-1 for deduplication in a way that’s not somewhat security-related? If you do file-level deduplication, and someone has a file A backed up, then downloads a file B which collides with A, then restores to a point where they had B on their system, won’t your back-up system have replaced B with A?
Or, to invert it: if I get someone to download file B, won’t I have poisoned their system so that if they ever download A, it gets replaced by my file B upon backup restore?
This seems like an avenue for security issues. Sure, people shouldn’t download files from sources they don’t trust… but also, people don’t expect that merely downloading a file will permanently poison their back-ups.
score 1 · canonical
Well, according to the article, it’s not feasible to create a collision for a file someone already has. Only to create two files that collide with each other. So an attacker would have to make you download two files, which might swap each others contents (although I suppose it’s possible that this could break your backup system, as it’s unexpected). This doesn’t seem that scary to me. This turns the case where they’ve given you malware, into a case where they’ve given you malware that might activate only after a restore.
score 1 · canonical
It’s not too hard to predict the content of some files. For example I could get my malware to hash the same as the GPL license text. Or I could email you some harmless content, which hash-collides with malware that’s already in your backup system. If github (which shares git refs across repos) didn’t have collision protection, I could fork you project, push my malware to my fork, then send you a clean-looking PR.
score 1 · canonical
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