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.
I had this same experience working on a proprietary backup system that used hashes heavily in 2016 or so.
“FIPS says we can only use SHA-256.”
“But we use hashes for deduplication, not security.”
“Doesn’t matter, FIPS says it.”
“But we have thousands of users. Many are on older CPUs where that hash is expensive.”
“Doesn’t matter.”
“Can we just throw truncated SHA-256 in the same field as SHA-1 and call it a day?”
“No.”
Anyway we upgraded all our users to SHA-256.
I’ve found a lot of the time that FIPS builds just straight-up don’t include “unapproved” hashing algorithms in libraries. Even if you could argue an exception for SHA-1 in some non-security case, the software build may simply not include the functions to do it at all.
I’ve hit this problem with the Linux kernel before, where a FIPS=1 kernel will not load many crypto modules and if you were relying on the kernel implementations for MD5 or SHA-1 then you’re out of luck.
My understanding for SHA-1 in FIPS is that it gets a harsher treatment than MD5 did.
MD5 got a transition and accepted usecases. SHA-1 on the other hand basically disappears. You could say that if it doesn’t exist for FIPS then you can use it for what isn’t regulated by FIPS but you should probably get ready to pay lawyers and have a lot of uncertainty around your product (good luck selling it in contracts that need years or decades of support). I think your example is an example of that: you were able to do the technical change while noone got through the justification approach.
I think that part of that is the past experience with MD5 and the difficulty with assessing usage of given codes. It’s quite easy to detect non-obfuscated/adversarial cryptography code and terribly difficult to asses how and when it’s used. The more realistic option is to remove SHA-1 code completely. I think that’s the approach in FIPS.
I don’t understand the companies (including gitbutler) that try to avoid the change because they’re going to aleniate a lot of customers. They don’t even have to kill SHA-1 support in their current stuff: they need to have the compatibility for SHA-256 and the ability to skip SHA-1. These are very common developments when you have a mix of US-government and non-US-government customers.
I meant that NIST makes a pretty strong move with the disappearance of SHA-1 in the future FIPS 180-5 (in constrast to 180-4). Of course, it never specified MD5 but the fact is that SHA-1 will not be deprecated: it will be un-standardized and that’s pretty uncommon.
It lists the transition and accepted usecases more clearly than the links in my previous comment.
As far as I can tell, SHA-1 was treated much more leniently than MD5: its deprecation process was far slower and gentler. That’s partly because MD5 is so broken that attacks became cheap and practical in 2005 so there was an undeniable urgency to doing the re-engineering work that was necessary to get rid of it; SHA-1 is not yet cheap to attack.
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.
I think that reasoning led to a svn repository being catastrophically corrupted by the shattered sha-1 collision.
It’s a common fallacy that deduplication doesn’t depend on the security properties of cryptographic hash functions: if the system doesn’t have any extra machinery to handle a collision then a broken hash function will cause loss of data integrity and probably availability, two of the three legs of the CIA triad.
I had this same experience working on a proprietary backup system that used hashes heavily in 2016 or so. “FIPS says we can only use SHA-256.” “But we use hashes for deduplication, not security.” “Doesn’t matter, FIPS says it.” “But we have thousands of users. Many are on older CPUs where that hash is expensive.” “Doesn’t matter.” “Can we just throw truncated SHA-256 in the same field as SHA-1 and call it a day?” “No.” Anyway we upgraded all our users to SHA-256.
score 1 · canonical
I’ve found a lot of the time that FIPS builds just straight-up don’t include “unapproved” hashing algorithms in libraries. Even if you could argue an exception for SHA-1 in some non-security case, the software build may simply not include the functions to do it at all.
I’ve hit this problem with the Linux kernel before, where a
FIPS=1kernel will not load many crypto modules and if you were relying on the kernel implementations for MD5 or SHA-1 then you’re out of luck.score 1 · canonical
My understanding for SHA-1 in FIPS is that it gets a harsher treatment than MD5 did.
MD5 got a transition and accepted usecases. SHA-1 on the other hand basically disappears. You could say that if it doesn’t exist for FIPS then you can use it for what isn’t regulated by FIPS but you should probably get ready to pay lawyers and have a lot of uncertainty around your product (good luck selling it in contracts that need years or decades of support). I think your example is an example of that: you were able to do the technical change while noone got through the justification approach.
I think that part of that is the past experience with MD5 and the difficulty with assessing usage of given codes. It’s quite easy to detect non-obfuscated/adversarial cryptography code and terribly difficult to asses how and when it’s used. The more realistic option is to remove SHA-1 code completely. I think that’s the approach in FIPS.
I don’t understand the companies (including gitbutler) that try to avoid the change because they’re going to aleniate a lot of customers. They don’t even have to kill SHA-1 support in their current stuff: they need to have the compatibility for SHA-256 and the ability to skip SHA-1. These are very common developments when you have a mix of US-government and non-US-government customers.
score 1 · canonical
SHA-1 started the deprecation process 20 years ago. In 2011, SHA-1 was deprecated for digital signatures and was supposed to be unused for them after 2013, but it was still acceptable in HMAC https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-131a.pdf
score 1 · canonical
I meant that NIST makes a pretty strong move with the disappearance of SHA-1 in the future FIPS 180-5 (in constrast to 180-4). Of course, it never specified MD5 but the fact is that SHA-1 will not be deprecated: it will be un-standardized and that’s pretty uncommon.
score 1 · canonical
Here’s a better summary of NIST’s SHA-1 deprecation timeline: https://csrc.nist.gov/Projects/Hash-Functions/NIST-Policy-on-Hash-Functions
It lists the transition and accepted usecases more clearly than the links in my previous comment.
As far as I can tell, SHA-1 was treated much more leniently than MD5: its deprecation process was far slower and gentler. That’s partly because MD5 is so broken that attacks became cheap and practical in 2005 so there was an undeniable urgency to doing the re-engineering work that was necessary to get rid of it; SHA-1 is not yet cheap to attack.
score 1 · canonical
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
I think that reasoning led to a svn repository being catastrophically corrupted by the shattered sha-1 collision.
It’s a common fallacy that deduplication doesn’t depend on the security properties of cryptographic hash functions: if the system doesn’t have any extra machinery to handle a collision then a broken hash function will cause loss of data integrity and probably availability, two of the three legs of the CIA triad.
score 1 · canonical
This made me double-take and I had to look it up.
“The CIA triad represents the three pillars of information security: confidentiality, integrity, and availability” (https://www.nccoe.nist.gov/publication/1800-26/VolA/index.html)
TIL.
score 1 · canonical
Heh, thanks for posting that explanation. It is definitely one of the more amusing acronym collisions :-)
score 1 · canonical