The first chosen-prefix collision for SHA-1
sha-mbles.github.io
sha-mbles.github.io
A similar attack (which requires only a few hours on modest hardware nowadays) has been known for a long time for MD5, but this is the first time it’s been demonstrated for SHA-1.
The previous attack, called Shattered (https://shattered.io) was a regular collision, that is, they chose a single prefix P and found different C1, C2 such that SHA1(P+C1) = SHA1(P+C2). This can also be length extended, so that SHA1(P+C1+X) = SHA1(P+C2+X). However, this attack is more limited because there is little to no control over the pseudorandom C1 and C2 (the only differing parts of the messages).
With a chosen prefix collision, though, things are way worse. Now you can create two documents that are arbitrarily different, pad them to the same length, and tack on some extra blocks to make them collide.
Luckily, the first collision should have already warned people to get off of SHA1. It’s no longer safe to use for many applications. (Note, generally for basic integrity operations it might be OK since there’s no preimage attack, but I’d still be a bit wary myself).
https://crypto.stackexchange.com/questions/60640/does-shatte...
> What is a chosen-prefix collision?
> A classical collision (or identical-prefix collision) for a hash function H is simply two messages M and M’ that lead to the same hash output: H(M) = H(M’). Even though this security notion is fundamental in cryptography, exploiting a classical collision for attacks in practice is difficult.
> A chosen-prefix collision is a more constrained (and much more difficult to obtain) type of collision, where two message prefixes P and P’ are first given as challenge to the adversary, and his goal is then to compute two messages M and M’ such that H(P || M) = H(P’ || M’), where || denotes concatenation.
> With such an ability, the attacker can obtain a collision even though prefixes can be chosen arbitrarily (and thus potentially contain some meaningful information). This is particularly impactful when the hash function is used in a digital signature scheme, one of the most common usage of a hash function.
The SHAttered attack (classical collision) can be used in practice - for example, my project https://github.com/nneonneo/sha1collider exploits their collision to turn any two PDFs into documents with identical SHA-1 hashes.
I just don't understand what danger being able to pad two documents to make them collide poses?
edit: My guess is that it can be abused to make something that I believe to be library X actually be library Y when I download it from the internet. Lets say I want to download something, and I check the signature provided. Assuming the attacker is able to send me the wrong library via a MITM attack, how can this prefix collision work? It seems that the original library AND the original signature on the library's website have not been altered, so their efforts to use this and make them match are impossible. And it seems like if they can alter the signature on the website and stuff, then all bets are off--why not just send the malicious library at that point?
https://www.google.com/amp/s/techcrunch.com/2008/12/30/md5-c...
https://techcrunch.com/2008/12/30/md5-collision-creates-rogu...
That said, maybe AMP is more like a virus. A non-living organism that spreads by infecting living organisms and repurposing them to replicate itself instead of sustaining the organism they were a part of.
The more sites adopt AMP, the more everyone else says "well I guess we have to now." Seems pretty viral.
This might sound far-fetched; after all, you'd need to convince a signing authority to sign the code. But this is pretty much exactly how Apple's Gatekeeper verification works: your software is submitted to them, and they do some security checks and notarize your bundle (https://developer.apple.com/developer-id/), and I'm sure there's many more such examples out there.
im not much of a math guy, I'm getting hung up on this part:
SHA1(P1+C1+X) = SHA1(P2+C2+X) for any X.
The example above seems like SHA1(GOOD_DRIVER) == SHA1(BAD_DRIVER+C2+X) somehow.
How does the C1 and X get appended to the signature of the good driver.
GOOD_DRIVER = P1 (good code and some data) + C1 (data) + X (more data)
BAD_DRIVER = P2 (bad code and some data) + C2 (data) + X (more data)
You'd disguise the random-looking block of C1 data in the middle of the good driver as e.g. a cryptographic key to avoid suspicion. The "more data" part couldn't be modified in the bad driver, but since you can arbitrarily modify P2 this wouldn't be a severe restriction.
The good driver is actually padded so that it can be later replaced with the bad driver. I.E This doesn't allow the attacker to replace any driver, but only one they prepared in advance to look innocent but have the right structure.
Not necessarily. You can also self-sign or just announce the hash, let the public inspect and test your good driver for a year, and then ship the bad driver to people who only check the hash
Or someone could say that you have your legally binding signature attached to a contract with hash ABC, but then present a different contract with hash ABC but very different terms.
Those are the end state. This is a major step closer to that end state. Neither of those scenarios are the case today, but they're now close enough that it's a matter of time. And likely not a lot of time.
Time to abandon SHA1.
AFAIK there's still no practical preimage attack for MD5, for which you can generate collisions in seconds on hardware that's a decade old, so it seems making a hash function collision resistant is in general quite a bit harder than making it resistant to preimage attacks.
Attacks generally improve on brute force by factors; for example, MD5 collision finding is some 2^40 times more efficient than 2^64 brute force, but being 2^40 times more efficient than 2^128 brute force for preimage finding is still well outside of anyone’s capabilities.
MD5 also appears to be unusually preimage-resistant; the best attack requires something like 2^123 operations which is really infeasible.
Nice to see this bit of intellectual honesty. Would be even nicer if they had explained what that means in terms of PGP keys.
For example, if an attacker gains access to a victim email account, they could send to their contacts a "trusted" key (as explained above) and then use it to send signed documents to the victim's contacts.
This would defeat an adversary "paranoid" enough to check a key signature, but not paranoid enough to obtain a clear explaination/confirmation of why the key changed...
No...
> For example, if an attacker gains access to a victim email account, they could send to their contacts a "trusted" key (as explained above) and then use it to send signed documents to the victim's contacts.
Ok... But in this scenario the attacker has the victim’s new private key, so they don’t need to create a collision (using OP). They can just use the new private key to sign the documents. Right?
Why ?
> in this scenario the attacker has the victim’s new private key
You don't want to keep your private key in cleartext on your email provider servers, do you ?
Thereby turning the signal intelligence problem into a human intelligence problem.
I'm not really knowledgeable about the implementation details of GPG. Mind explaining how this follows?
I mean I truly admire these folks skills, the math involved is obviously remarkable.
But I think the feeling is related to not being able to rely on anything in our field. Hard to justify going to the trouble of encrypting your backup. 10 years from now, it might be as good as plain text.
It's not security only, nothing seems to work in the long term. Imagine an engineer receiving a call at midnight about his bridge because gravity changed during daylight saving in a leap year. That's our field.
Huh? If you're "encrypting" using SHA, I've got some bad news about those backups of yours.
Most people in the room will still have unique birthdays even if one pair share theirs.
From my numerical experiments (I hope I didn't mess up...) using the random oracle model, the probability that a given key is collision-free is 99.6% if the input is one byte shorter than hash, 1/e if input is same size as hash and 6.6e-112 if the input is one byte longer than hash.
And this holds basically irrespective of key size.
Salsa20 & ChaCha20 cores are hash functions (though not collision-resistant compression functions since it's not needed for their design goal and would be slower) run in CTR mode.[1]
This is the best, most delicious, type of pedantry friend!
(Just some more pedantry, friend.)
/s
And if you want really, provably unbreakable encryption, there is still OTP. But then you'd need a key, that is as long as the data you want to encrypt.
An issue so far for computer security is less that decay and entropy happen, but that they happen so fast that the timescales are decades or even years rather than lifetimes.
It also underscores that, when dealing with things like passwords, it's helpful to be able to seamlessly upgrade to more robust methods down the line, e.g. "if this password hash was generated using the old method, check the login using that method but rehash and update the database using the new method after authentication."
This was particularly a problem for castles vs. the progress of artillery, because those were supposed to have a rather long lifetime.
I'm confused what you mean by this? Why does the info theory suggest hashing wouldn't be possible? Also, you can easily derive a secure hash function from a secure symmetric cipher and vice-versa, so why would one seem to be possible but not the other?
The hash is this tiny bit of information, and somehow is expected to be sufficient to uniquely describe some arbitrarily large amount of information? That just flies in the face of the naive expectation. The only argument that it is even sort of reasonable to expect would be the idea that while there are an insane number of files very similar but not quite your file, very few of them are "interesting" to a human in any way, and so the set of "interesting" files might be super small... but it isn't like we designed the hash functions to know that.
The reality that it seemingly can be done well enough that no one notices most of the time is fascinating and surprising--the kind of thing that inspires awe and wonder at the universe if true or calls into question our hubris if it isn't--not something obvious in the way the existence of symmetric ciphers nor something reasonable to expect in the way asymmetric ciphers are: to the extent to which reality lets us pull this one off we should be thankful.
2) If one can truly "easily" derive a "secure" hash function from a secure symmetric cipher, then why don't we ever have secure hash functions, despite seemingly having secure symmetric ciphers? If this is so easy, I suggest you do it and then wait 30 years and see if someone figures out how to break it (and we can see it AES is still holding strong).
2) I mean, I'm not sure how correct your premise that symmetric ciphers are more secure than hash functions is, but it literally is something that is done. You can read more about it in [1], including the possible pitfalls. The transformation should provide more than enough intuition to see why both are equally plausible, which was the point of my reply. Whether or not it's best to actually implement them that way in practice is a separate question which I'm not trying to answer here.
The block cipher behaves how we expect, I'm confident that many of the ciphers used inside real hashes like SHA-256 are good block ciphers and either would not be broken if we used them as block ciphers or could be repaired by competent cryptographers to be robust enough so that they didn't get broken over their lifetime after the repairs were done.
But the transformation to get a hash introduces the effect that your parent sees (I think correctly) as unintuitive. Normally if I put a megabyte of plaintext into a cipher I get back a megabytes (or slightly more depending on my mode of operation and rounding up due to block size) of ciphertext, but this transformation ensures we always get one block back, the hash of a Wikipedia dump and of my address book are the same length for a particular hash function. The "block" is bigger than we're used to from popular block ciphers but that's what it is, one block.
And that's where the concern appears. Why is that safe? Surely that shouldn't be safe at all? And yet, it seems, it is successful, more or less, until it isn't.
It doesn't really describe the information it just indexes each piece. For that it is a very large key space. A 128 bit key could index 10^38 objects. That's a lot of slots. Provided your hash has sufficient mixing you will need a lot of shots to hit anything.
>If one can truly "easily" derive a "secure" hash function
Semantic security has a precise definition. We just have to make empirical assumptions about whether an input cipher is semantically secure. The hash is only secure if the cipher was but the derivation is easy.
That is an absurd statement. Every backup you encrypted 10 years ago with then up-to-date security is still well encrypted. The SHA1-thing came coming over a timespan of 15 years. It still doesn't threaten past usage, only active attacks are really relevant.
As with any other security issue, the question is "what is your threat model?" You can still justify encrypting your backup today if your threat model includes today's actors, however much you worry about "the future".
> 10 years from now, it might be as good as plain text.
Or 10 years from now it might be the next Linear A tablets to confuse cryptoarcheologists, unreadable and untranslatable and entirely foreign. If "the future" is in your threat model, don't forget the other fun forms of entropy beyond encryption being cracked such as encodings changing, file formats falling out of service/compatibility, "common knowledge" about slang or memes lost to the ages leaving things indecipherable, and so on and so forth. Most of those things are probably unlikely on only a 10 year time horizon, but you never can tell with "the future".
Didn't expect to see Front on HN today, what a pleasant surprise.
There's it's somewhat shortened form "cryptarch", generally more used as a title ("cryptoarcheologist"), which was used in places in the Quantum Thief trilogy of books and is most probably already burned into your brain if you have played any of the Destiny series of videogames (and I presume was heavily influenced by Quantum Thief).
(I don't think Destiny does much with the playful dual meaning, though. Certainly the cryptarchs in Destiny have never yet been meaningful leaders.)
At some point in the future, after the universe has expanded to the extent that other galaxies are moving away from ours faster than the speed of light, someone might read our astronomy papers and wonder whether they can believe something that cannot be verified.
https://phys.org/news/2020-01-evidence-key-assumption-discov...
With the usual disclaimer about one-time pads.
> other fun forms of entropy beyond encryption being cracked such as encodings changing, file formats falling out of service/compatibility, "common knowledge" about slang or memes lost to the ages leaving things indecipherable
I wonder what the digital archaeologists of the future will make of today's programming languages.
(I was going to point out how far we've come since the languages of yesteryear, but we still have such horror-shows as Perl and Bash.)
P.S. My father (still alive) was one of thousands of common liquidators of Chernobyl disaster from May to July 1986. Many of his coworkers, that lived with him in same tent, already dead.
Not great, but not terrible?
When has that happened? Public key cryptography and symmetric key cryptography are still doing fine as far as I'm aware, and the latter doesn't even seem to be vulnerable to quantum computing.
Moreover, SHA-1 has been considered insecure for, what, at least 10 years? The fact that a cryptographic hash function has been widely considered insecure and widely recommended for deprecation a decade before a proof of concept even emerges is, to me, something to feel very good about.
They might BnE your key though, if you aren't careful enough.
Now, there are various kinds of hot attacks, such as side channel leaks, that always present a serious challenge in many threat scenarios. And it's certainly possible to have bad implementations of a solid algorithm. But for AES implementations are very mature, and side channel attacks do not apply to data at rest. So in the context of "will my encrypted ciphertext with all my deepest secrets [sitting on a drive/in the cloud/wherever] be crackable in 40 years" no, symmetric-key crypto with 256-bit keys is dependable at this point.
A false sense of defeatism is itself plenty dangerous to security.
To be clear, 2^56 is trivially brute-force-able today, but that can be mitigated with constructs like 3DES, which are still (barely) secure despite being based on a 45-year-old cipher.
(So no one mistakes my intent, there are many reasons to prefer AES over DES. I just wanted to provide it as an example, especially since it happened to line up with the 40-year timeframe.)
Youch, this broke my intuition.
"we’ve built a system with 48 Virtex-6 LX240Ts which can exhaust the keyspace in around 26 hours"
Having to rent thousands of dollars in GPU-hours or using specialized hardware doesn't sound "trivial" to me. Practical, yes. Accessible even to a layman with money to spare, yes. Trivial? Hell no.
If I had some DES-encrypted files that I'd lost the key to, and they were important enough that I needed their contents, I would probably be happy that I could crack the key today and recover them if I spent enough, but doing so would still not be "trivial".
Apparently there's even a SaaS offering to do it for you in some cases (for staggeringly cheap, like $300), but I had no idea that existed when I wrote my comment.
> We have tried to contact the authors of affected software before announcing this attack, but due to limited resources, we could not notify everyone.
Many in the 'security industrial complex' make as if they are doing god's work by their 'research' but from a common sense, man/woman on the street, and layman point of view that is not what appears to be going on at all.
What they do is self serving and a detriment. Then they try to justify it in some way as being good when it's not good. It's like going around and compiling a list of doors in a neighborhood that are open, attempting to contact everyone but not getting some people and then saying 'hey look at what we did for you'. Meanwhile if a list were not compiled at all almost all people would do just fine.
> But I think the feeling is related to not being able to rely on anything in our field. Hard to justify going to the trouble of encrypting your backup. 10 years from now, it might be as good as plain text.
Figure out the amount of issues there would be if there was not such open disclosure and an entire industry surrounding breaking things vs. same not being done. That is the issue.
> Imagine an engineer receiving a call at midnight about his bridge because gravity changed during daylight saving in a leap year. That's our field.
No because nobody is able to or actively trying to change gravity (or is able to).
The government (in the US) does not have the resources to go after everyone who commits a crime and that would assume they are actually scooping up info and know of the crimes (they aren't and they don't). They don't even have the resources to audit tax returns (other than a very small percentage). This idea that you are being watched all the time is fantasy. In the US. Other countries? Unfortunate when that's the case but that does not mean as a US citizen I can't view it as detrimental to me that this type of security disclosure makes it so easy for hackers to do a better job (and it does nobody is going to dispute that fact, right?).
In point of fact, since Snowden's revelations we know not only that the USA state actually does have the resources to monitor everyone, but also that it does so. Furthermore, the state is not a monolith. While it may not be in the interest of the state as a whole to capriciously victimize individual humans, it is often in the interest of particular officers and organizations that comprise the state to do so. Cf. "parallel construction".
> all almost all people would do just fine
Here's an ongoing ransom attack in the UK, started on New Year's Eve: https://www.bbc.com/news/business-51017852 The ransom is in the millions of dollars range, Travelex websites in 30 countries down for a week, Sainsbury's money exchange websites down for the same time, and "Dates of birth, credit card information and social security numbers [of customers] are all in their possession, they say."
Not looking at problems doesn't stop problems from existing.
You are not recognizing the nuance which is typically the case with people who supports practically any and all disclosure and thinks it's good plain and simple. With almost no downside at all (not the case).
In particular this: "then bad people won't find out about them"
My point is that disclosure makes it simpler for more bad people to find and learn and inflict damage damage. Unclear to me how you could think that isn't what has and is happening. If someone say publishing how to create a card skimmer at a gas station then more people (who are bad actors) will then have what they need to give it a try. If not there will be people who have figured it out and people who will put the effort into figuring it out but you must realize vastly less will do that, right? The disclosure removes a great deal of friction.
The amount of effort and friction and the amount of 'bad people' that can be actors is many magnitudes larger (I would argue) as a result of disclosure.
It would be a nice world if we could tell companies about flaws and they fixed them, and nothing went public, but instead we tell companies with "responsible disclosure" and they ignore it, don't spend any effort on it, act incompetently leaving it with first line support people who don't understand it and have no path to escalate it, have no security contacts available for reports, cover it up or deny it or try to silence it with NDA style agreements, prioritise shareholder profit or public image over it, and generally behave irresponsibly in all possible ways that avoid them having to deal with it, with very few companies excepted.
In light of that, public disclosure with all its risks, actually does kick companies into taking action, and closing risk vectors for good. Like companies who say "we put customers first!" but it takes a complaining public Twitter thread for them to even respond at all. Telling people to not take it to Twitter ignores the fact that there's no other way which seems to actually work.
Give an alternative which also gets problems fixed, and I'll be much more in favour of it.
But the vast majority of people do literally have front doors which cannot guard them from 1% of the possible attacks in the world, if they were targeted. Never mind the best ones in the world.
[1] is a fun YouTube video about physical pen testing; one example at 13:45 in the video, the presenter is walking home from a bar, walks up to a locked high street bank, spits a mouthful of beer through the gap in the doors, triggers the presence sensor on the inside which lets people out, and the door opens and lets him in.
"Local people", huh. My front door is visible to everyone on the internet, and I have no practical way to prevent that. Some obscure company went by with their mapping vehicle and...
Now, some people do live in big buildings where less is exposed to the outside, but millions don't.
and... what? Unless telekinesis has been invented, a photo of your door doesn't increase the amount of people who are able to try opening your door. If you're about to say "someone might choose to come a long way just for my door" then that seems like an argument in favour of what I'm saying - in that case, wouldn't you like to know about any vulnerabilities your door has which you could address, before they arrived, instead of relying on silence and hoping they won't know about them?
I'm saying the ideas I read about how the world is don't seem to be connected to my view of reality. I don't have to argue with your conclusions to find fault with your premises, and I'm feeling too lazy to do it right now.
Realistically, any archive is going to have to re-record data to stay ahead of age and equipment becoming obsolete. I've heard the lifetime for the physical media of tape backups is in the 10-30 year range.
Updating the encryption isn't a big deal once you're already rewriting everything.
Now we know. It's better to know.
I created an account just to chime in on this.
In short: horseshit.
Look, cryptology is a tricky field, but when it comes to standards development (especially OPEN standards development, without government intervention), it's mostly been hits, not misses. While there are occasional breaks and busts, the fact is, most of the trusted algorithms have remained trustworthy-- lasting through their designated lifespans, and often a lot longer. Many of the algorithms that you hear are "insecure" aren't really insecure due to any math advances; they have simply fallen victim to their already-known limitations, or are "insecure" when used in specific ways.
For instance, look at the Blowfish block cipher. Blowfish was designed and released almost thirty years ago. Its current biggest security issue is not some tricky biclique attack that allows key recovery on a desktop computer or something. The problem is that the block size is 64 bits, and in modern contexts, that's just too small-- networks shuffle enough bits around these days that a 32-gigabyte encrypted transfer is suddenly a realistic use case, and there are known attacks related to that. 64 bits was fine at the time, and the block size was a known limitation of the algorithm (birthday attacks are well-understood). The algorithm didn't fall; we outgrew the use case.
Going back even further: DES was released nearly FORTY-FIVE years ago. It was released with a 56-bit key, which was known at the time to likely be in brute-force range for certain Nation State Adversaries. It has the same block-size issue as Blowfish. But it's actually stood up to cryptanalysis pretty well, given the power of the attacks that have been developed since then. Triple-DES, properly used, is plenty secure for lots of applications-- it's still even promulgated as a standard algorithm for a lot of financial industry systems.
More germane to modern encryption practice, AES was standardized nearly 20 years ago, and has been studied for even longer. It's still a solid algorithm today. There are a few implementation caveats if you want to avoid things like cache timing issues, but the algorithm itself is holding up very nicely to mathematical advances-- the best known mathematical attacks drop the security levels by 1 to 4 bits, depending on key size, which is... well, it's worse than 0 bits, but it's certainly nothing to worry about. AES has been integrated into processor designs, it's used to protect US government information classified up to TOP SECRET, and it's supported by nearly every cryptographic suite out there-- because of all of that, the algorithm has remained a significant subject of ongoing research, and it has stood up to the scrutiny beautifully.
Cryptography is always advancing, and sometimes algorithms do fall to mathematical breakthroughs (RC4 has been battered pretty badly, for instance, and SHA-1 is clearly dead now). But for the most part, cryptologists try their damnedest to know the limitations of their algorithms, and they're pretty up front about them.
I'll also point out: cryptologists are aware that there's risk associated with mathematical advances, and they hedge their bets. Note that there is now a SHA-3 standard. That's not because the SHA-2 algorithms are dead. It's because, while we're pretty sure they're secure, the SHA-2 algorithms are cut from the same mathematical cloth as SHA-1 (they use the Merkle-Damgard construction). SHA-3 was standardized with the explicit purpose of adding diversity to the pool of standardized algorithms. NIST is currently running a post-quantum public-key standardization effort, and has made it very clear from the start that they'd like to select multiple "winners" from multiple categories. Part of this is to allow flexibility for different use cases (key size / message size / performance trade-offs vary wildly for different classes of algorithms). But another part is preventing a complete disaster if one class of algorithms is broken (either classically or with a quantum computer).
All ciphers older than 100 years have been broken, except for one.
However, it seems to me that designs improved exponentially, while attacks only improved quadratically. The old days of WWII where Enigma was broken before the end of the war will never happen again.
Conceptually, it makes sense: Science improves quadratically because breakthroughs improve tooling that accelerate breakthroughs. I am simplifying here, but if you have N tools at T1 that make you progress at rate R1=N×K, and that progress yields another tool: at T2 you have N+1 tools, making you progress at rate R2=R1+K. Your progress is P2=P1+R1, which generalizes to Pn+1 = Pn+n×K = P0+K×N×(N-1)÷2, a quadratic progression.
On the other hand, cryptographic security is exponentially better with every bit. If an old cipher uses its bits badly, it will still be good enough if it is long enough. Let's say it reaches a given difficulty level after 10 rounds; a cipher that uses its bits twice as well will reach the same level after 5 rounds, but would have something like 2^K times that level after 6, 2^2K times after 7, … 2^5K times after 10, reaching a level that quadratic improvements won't reach for an increasingly long time.
For instance, it took 5 years for MD4 (1990) to have a practical collision, 12 for MD5 (1992), 22 for SHA1 (1995), therefore roughly doubling every three years. If we extrapolate, SHA2 will have a practical collision in 2080.
Engima (like most systems in use in the 1930s) is thinking about cryptography as being some sort of art in which the idea is to sort of stir letter symbols. Everything else often can't even be encrypted or must be elaborately transformed into letter symbols first. Bletchley has replica "Bombes" which would be used to attack this mechanically, replicating the function of the Enigma machine to defeat it.
Lorenz, which was also attacked at Bletchley using the Colossus, is a modern stream cipher. It XORs a pseudo-random stream against your plaintext bits (albeit in the 1940s these were in 5-bit ITA telegraph code) and so it isn't different in core principles from say RC4 or at a greater distance in time indeed Salsa20 - Lorenz just has about 56-bit keys where these modern ciphers have more and are better designed. Attacking this mechanically was impractical, and that's why a computer like Colossus was needed.
As a result it really isn't fair to compare 100 years ago. If we look back 50 years instead the difference is stark.
(edit: these are indeed general questions, not just about SHA1)
Has anyone else been worried about data deduplication done by storage and/or backup systems, considering that they usually use hashes to detect data blocks that are "the same" (without additional metadata) and avoid storing those "duplicate data blocks" again? Doesn't this seem far worse when you also consider that systems like Dropbox deduplicate data across all their users (expanding the footprint for collisions)? Are there any research papers/articles/investigations about this?
ZFS, for example, has a dedup setting option that forces the file system to do a byte-for-byte verification for any deduped data: https://docs.oracle.com/cd/E19120-01/open.solaris/817-2271/g...
The dedupe engine written where I work chunks a file and hashes those chunks meaning it's somewhat harder to craft collisions (I forget where the chunking boundaries are, but it's within a range iirc). The hashing algorithm was SHA-1 last I checkee but I've never heard even company folklore of corrupted backups caused by hash collisions. I get the feeling that it's near impossible in practical terms given the size of the string being hashed. Having said that, hubris is the downfall of programmers everywhere, so I wouldn't bet all my money on it.
https://en.wikipedia.org/wiki/Preimage_attack
This means if a storage system just uses SHA1 to detect duplication, you can abuse the ability to create a collision to possibly do bad things to the storage system.
And your data can't be stolen by a hash-to-data oracle either, unless the evil attacker constructed your secret data for you.
So it depends on your threat model. Yes there are practical concerns, but not the ones listed.
E.g. I make two things that hash to the same thing. One is a contract where I'm obligated to pay back a loan. Another is some meaningless document. I give them to a counterparty who puts them in their filesystem, which later scrubs and deduplicates data. Since they hash the same, the filesystem removes the contract and leaves my meaningless document (or never bothers to store the contract because it already exists, if deduping online, etc).
Note that this is a chosen prefix collision, which is much more demanding (and more useful!) than finding a collision in general. And this leaves aside that SHA1 is looking increasingly vulnerable to preimage attacks which further broaden the attack scenarios.
It may be repeatable to always remove the first or the last. If it's online dedup, it'll always be the last.
Or the attacker can provide many copies of the document you want to still have a copy of, and one copy in the middle of the one that should be vanished.
From your linked article:
>All currently known practical or almost-practical attacks on MD5 and SHA-1 are collision attacks. In general, a collision attack is easier to mount than a preimage attack, as it is not restricted by any set value (any two values can be used to collide).
This breaks anything that dedups on just the SHA-1 hashes of raw files
I see that Git doesn't actually use SHA-1 any more, it uses "hardened SHA-1": https://stackoverflow.com/questions/10434326/hash-collision-...
$ mkdir sha1
$ cd sha1
$ curl -O https://sha-mbles.github.io/messageA
...
$ curl -O https://sha-mbles.github.io/messageB
...
$ echo foo > bar
$ echo foo > baz
$ openssl sha1 *
SHA1(bar)= f1d2d2f924e986ac86fdf7b36c94bcdf32beec15
SHA1(baz)= f1d2d2f924e986ac86fdf7b36c94bcdf32beec15
SHA1(messageA)= 8ac60ba76f1999a1ab70223f225aefdc78d4ddc0
SHA1(messageB)= 8ac60ba76f1999a1ab70223f225aefdc78d4ddc0
$ git init
Initialized empty Git repository in ...
$ git add *
$ git commit
[master (root-commit) b274c88] sha1 collision test
...
4 files changed, 2 insertions(+)
create mode 100644 bar
create mode 100644 baz
create mode 100644 messageA
create mode 100644 messageB
$ git ls-files -s *
100644 257cc5642cb1a054f08cc83f2d943e56fd3ebe99 0 bar
100644 257cc5642cb1a054f08cc83f2d943e56fd3ebe99 0 baz
100644 5a7c30e97646c66422abe0a9793a5fcb9f1cf8d6 0 messageA
100644 fe39178400a7ebeedca8ccfd0f3a64ceecdb9cda 0 messageB
$> git doesn't really use SHA-1 anymore, it uses Hardened-SHA-1 (they just so happen to produce the same outputs 99.99999999999...% of the time).[1]
https://stackoverflow.com/questions/10434326/hash-collision-...
There's essentially no chance that the string "foo\n" fell into that tiny probability of difference. The reason there's a difference is because before git hashes something, git will do various processing to it (maybe appending and prepending various things) and those things broke the carefully created collision. But a chosen-prefix attack might mean those various things can be accounted for, and a collision could still be found.
So we need to directly run hardened SHA1 on the data, which I believe is located at https://github.com/cr-marcstevens/sha1collisiondetection
As seen in https://github.com/git/git/blob/master/sha1dc_git.c
So I tested that one:
$ sha1collisiondetection-master/bin/sha1dcsum bar baz messageA messageB shattered-1.pdf shattered-2.pdf
f1d2d2f924e986ac86fdf7b36c94bcdf32beec15 bar
f1d2d2f924e986ac86fdf7b36c94bcdf32beec15 baz
4f3d9be4a472c4dae83c6314aa6c36a064c1fd14 *coll* messageA
9ed5d77a4f48be1dbf3e9e15650733eb850897f2 *coll* messageB
16e96b70000dd1e7c85b8368ee197754400e58ec *coll* shattered-1.pdf
e1761773e6a35916d99f891b77663e6405313587 *coll* shattered-2.pdf
The idea in Marc Stevens' anti-collision work is that some inputs are "disturbance vectors" which do unusual things to the SHA-1 internals, and we want to detect those and handle that case specially since there is almost no chance of that happening by accident. It has a list of such vectors found during his research.
This paper doesn't talk about "disturbance vectors" but it does discuss ideas like "Boomerangs" which I think ends up being similar - I just don't understand the mathematics enough to know whether that means "the same" or not.
Key is part of a collision! It's a trap!yE'NsbK#ދW]{1gKmCx's/vr| -pJO_,1$)uB1qXv#U)9ESU;p~0G:Y ݕbBIjFra눰3&t'lB_!h5M([,˴QMK#|o5pv|i,+yYpݍD7_Rf\'GUZ,ϵdvAYAugV=Lk8_E 2 +nolBtxXoQt&+?Y3LP:'Qt(,ۛuԪWJm:A"M6<|B4kVv̨ޠA=M+m%殺j5N|EMA\Ed- s&@u@:a?pq^Xf0U?R}
and
Practical SHA-1 chosen-prefix collision!'lka}vbI3,·W]Ǟ+gK}Cxs/v&r| }-hRJO_ rO̳;bzC ,1&uRP-MXrU3aO;pr0:sY'2 l&r7#(A{oNyCJ_W,8 əbحBYީpFr2a8#&t+n_15q(_,ˤQMW#hzYMgVV=L,kO0E*N +oc@BpXoᯖd&?+?[{3LвP&'U t ( WJÏm\:A"6>>|SB(k;Vv̨ޠ^A=Y ;om%j-|cUAAۜEТ&@o@:La3psH^eXf0QJm ݶd
they have the same sha1sum, but in all practicality its nonsense since both messages are pure trash. you couldn't have malicious C code that would have the same hash as non malicious C code in this example
Dump your garbage string behind a // or inside an #if 0, restrict the garbage string character set to characters which will not disturb that, and your compiler will whistle while it works.
If there's a followup CL to "delete a garbage string that accidentally made it into the repo", which doesn't actually fix whatever else was added, would that get you anywhere?
Or what if it's a really obscure library for parsing like... pyramidal jpeg2000s, are the library consumers going to be checking the source? Heck, most people already don't check download checksums unless their downloader does it automatically.
In theory you might get people building software packages for distros to build your malicious version, you may also just temporarily shut down the ability for anyone to check out the version (basically denial of service for making?) but the time window would be weird.
Why are cryptographers always exaggerating things and so out of touch with reality? The first actual collision was like 3 years ago. It's not like the world has been on fire in the meantime, and it's not like SHA-1 is broken for every single possible usage even now. And why the nonsense with "no good reason"? Obviously performance is one significant consideration for the unbroken use cases. Do they think painting a different reality than the one we live in somehow makes their case more compelling?
So yeah, if you are building/improving software that has a clear focus on security, you should use a secure hash. Seems only natural to me.
So if this attack is developed today, then you should assume that NSA has been able to execute this attack for at least ten years already whenever it suited them, including mass surveilance of random not-that-important people. The same applies for the collisions - the first published collision was 3 years ago, but we should assume that that's definitely not the first; I mean, only a minority of the world's cryptography researchers participate in the public, open, academic community; the majority of them are employed with a condition that they won't get to publish anything important. And since we know for the last ten years that such attacks were possible, there's no reasonable reason why SHA-1 would have been considered as safe.
That said, historically speaking, back in the early 70s DES was being designed. The NSA made some unjustified changes to its S-boxes. At the time, there were allegations that they had made them intentionally weaker. (Or so I've read; I wasn't born yet.) In the early 90s, differential cryptanalysis was discovered for the first time, and it turns out that DES was already resistant to it (unlike other block ciphers at the time): in fact, the NSA already knew about differential cryptanalysis, 20 years ahead of the general public, and intentionally strengthened DES. (Also, IBM discovered it, too, but kept it quiet at the NSA's request.)
We know that British intelligence (who don't have as much resources as NSA) had developed the RSA equivalent something like 5 years before Rivest/Shamir/Adleman got to it; and we still have no idea how far NSA was with that math at the time - all we have is circumstancial evidence such as travel reports of NSA representatives going to cryptography conferences and being satisfied that absolutely no math that's new (to them) or even potentially leading to something new was being revealed there.
We also have NSA suddenly changing recommendations to use/stop using certain cryptosystems that still doesn't make sufficient sense - e.g. the 2015 turning away from 'suite B' ECC may have been due to some quantum discovery as is claimed, or some other weakness being found, but it's been five years and we (as far as I understand) still don't know as much as they did back in 2015, so they're more than 5 years ahead. But to know whether the current advantage is ten years or more or less, we'll have to wait a generation or so, it takes a long time for truth to leak.
It's hard to give good numbers, we'd have to look at Snowden leaks and others, but I haven't done much about that. Here's an earlier HN comment https://news.ycombinator.com/item?id=6338094 that estimates 600 proper mathemathic researchers working on crypto, and it seems quite plausible to me that it would be more research power than the entire public academia - especially because in many countries who do take this field seriously (e.g. China, Russia, Iran) there's no real public research in crypto happening because that's classified by default. I mean, prety much all academic research happens through targeted grants by governments, and who other than deparment of defence (or similar organizations in other countries) would be funding cryptographic research?
Also, I'll quote Bruce Shneier (2013, https://www.schneier.com/essays/archives/2013/09/how_advance...) regarding their budget - "According to the black budget summary, 35,000 people and $11 billion annually are part of the Department of Defense-wide Consolidated Cryptologic Program. Of that, 4 percent—or $440 million—goes to 'Research and Technology.' That's an enormous amount of money; probably more than everyone else on the planet spends on cryptography research put together."
I am aware of the 2015 plan to "transition soon(tm)", but that's because I was alive 5 years ago. Other earlier events would be super cool to read up on.
They might be 10 years ahead on the algorithms side, but they aren't 10 years ahead on the hardware side. Also, spending 45k today gets you a single collision. That is hardly going to be useful for mass surveillance.
They have access to better and more hardware than most threat actors.
[1]: https://www.nitrd.gov/pubs/nsa/sta.pdf [2]: https://it.slashdot.org/comments.pl?sid=485458&cid=22736288
It's good enough for you and me, but research isn't meant to be practical, imo
The point with assuming conservative threat models for key primitives like hash functions is that the threat model can change rapidly even within the same application, and attackers only get stronger. So you err on the side of caution, and don't rely on luck to keep safe.
These statements serve to shift the Overton window of perception, and therefore help improve the odds that people are't thinking "good enough" when they are broken.
It's a striking contrast with the stark mathematical language deployed by cryptographers, on whose work we rely.
If we differentiate between the two fields of software engineering and cryptography, it's easier to be generous in our appreciation for the different goals and mental models.
In particular, a primitive makes a number of useful promises. Any achievement that describes a way in which a promise is not kept makes that primitive broken, regardless of whether that achievement is theoretical or practical.
(They often talk about “theoretically broken” or “practically broken” to distinguish whether it was actually done.)
> it's not like SHA-1 is broken for every single possible usage
True, but it is extremely easy to believe your usage is unbroken and be wrong. Besides, often, primitives that are broken for one usage eventually break for others.
> why the nonsense with "no good reason"? Obviously performance is one significant consideration for the unbroken use cases
There are many much more robust primitives with better performance nowadays, such as BLAKE2, SHA-512/256, or Kangaroo12.
Regardless, no competent designer is going to use SHA1.
Deprecating things does take a long time, and the only practical thing to do about that is to get ahead of the game as you say.
This is chosen prefix collision. This means you can select a beginning of a document which in many cases is enough.
a) There's hardly an application where hash-performance matters. These things are fast.
b) For precisely that reason that people may still complain about performance cryptographers invented a hash function that is faster than all the old choices like md5/sha1 and still secure (it's called blake2).
This wasn't for some throw-away project. Big, old company. This may be the closest I've come by far to writing software that will still be used after I'm dead (gets a little easier every year, though). If I gave them SHA-1 they'd still be using it for sure.
I refused, and the fact that people were calling MD5 very broken and SHA-1 broken helped.
(A completely different faction was trying to get me to jump straight to SHA-512. I said that was probably overkill, and yes I will implement it but we're using SHA-256 as a default. Then a couple years later it turns out SHA-256 is more resilient than 512 anyway. But what a schizophrenic place.)
Since SHA-1 was always possible to break, and since NSA probably gets access to big computers and sophisticated techniques before researchers, why doesn't this invalidate every SHA-1 signature ever made and not just ones from last year?
Rather than keys, Alice will typically sign a document (e.g. an X.509 to-be-signed certificate)
Mallory creates two documents, the legitimate seeming document A (a to-be-signed certificate Alice willingly signs) and document B (the content of which is controlled by Mallory to an extent depending on the details of the collision). In document A I'm sure Alice will insist on the date being roughly correct so you'd detect that. But Alice never sees document B, she isn't aware it exists, so it can specify any date, including one chosen not to set off alarms.
For the Web PKI we were triply safe because:
1. We told Alice (the public CAs) never to sign anything at all with the dangerous algorithm after a set date. So long as Mallory wasn't able to develop and use a collision before that date and Alice did as she was told‡ this would be safe in perpetuity.
2. We already had a countermeasure in the documents, very early in each Web PKI X.509 certificate is the Serial Number, if you look at yours you'll notice it's a crazy huge number and seemingly not "serial" in any sense. It's random. Can't do a chosen prefix collision attack if you can't choose the prefix.
3. Since no more new documents were being signed clients in the Web PKI were able to stop recognising these signatures thus permanently ensuring the attack was impossible within about 18 months.
‡ A very small number of exceptions were explicitly granted, and a similarly small number of exceptional cases occurred for which no permission was asked. All investigated to everybody's satisfaction. As you may see if you poke around in the demo documents from this article, a collision document may not jump out as problematic from a crowd but it certainly isn't so innocuous as to survive careful scrutiny, and with such a small number of exceptions to look at this scrutiny was possible in a way it never would be for the wider Web PKI.
We know how to make pairs of new files that collide with each other, but there's no known way of creating a file that collides with something specific that existed before.
People tend to be conservative in making changes for stuff like this, and don't do so until forced.
On 64-bit capable processors SHA-512 has a slight performance gain over SHA-256, but only on larger inputs. However, the digest of SHA-512 is twice the size, so what you gain in processing time, you loose in storage.
The strength of hashes like SHA-256 doesn't just come from the number of output bits.
The 256 bits there is relevant for brute force attacks, but not more sophisticated attacks that take into account the internal structure of the hash algorithm, and in some cases "weak" values.
SHA-512 performs more "rounds" of computation than SHA-256.
Although it's impossible to compare two different hashes on rounds alone, in general a large number of rounds of the same type of hash decreases the likelihood of non-brute-force attacks finding a collision.
If you look at the literature for attacks on hashes, they will often say they could do it for a certain number of rounds, and that number increases over time as new methods are discovered.
The number of rounds in the hash design is chosen with this in mind, trying to balance being more than sufficient for future attacks yet not too slow.
Pity it didn't come across that way.
Latacora says to use SHA-2. If you can get away with it, SHA-512/256 instead of SHA-256. But they're all SHA-2 family hash functions.
https://latacora.micro.blog/2018/04/03/cryptographic-right-a...
No need to bikeshed this. But if you must: SHA-512/256 > SHA-384 > SHA-512 = SHA-256
If you're wondering, "Why is SHA-384 better than SHA-512 and SHA-256?" the answer is the same reason why SHA-512/256 is the most preferred option: https://blog.skullsecurity.org/2012/everything-you-need-to-k...
Additionally, the Intel SHA extensions target SHA1 and SHA-256 (but not SHA-512), which makes SHA-256 faster than SHA-512 on newer processors.
Isn't crypto fun?
SHA-384 is SHA-512 with a different IV (which doesn't affect LEAs) truncated to 384 bits (which gives you 128 bits of resistance against LEAs).
SHA-224 is the same story but with SHA-256 instead (and only 32 bits of LEA resistance).
If not, I completely do not understand the inequation you wrote, which seemingly lists SHA-256 (and -512) multiple times.
Length-extension attacks are relevant when you design a MAC by passing a secret and then a message to a hash function, where only the message is known.
Truncating the hash (which is what SHA-512/256 and SHA-384 do to SHA-512) removes the ability to grab an existing hash H(k || m) (where k is unknown and m might be known) and append junk because a truncated hash does not contain sufficient information to recover the full state of the hash function in order to append new blocks.
So rather than push off getting people to make things actually safe by providing a footgun NIST just didn't do that.
Considered by whom?
There are a lot of standards organizations all over the world with various recommendations. https://www.keylength.com collates quite a few of them. Pick the one most closely relevant for your jurisdiction.
Most of them recommend 2048-bit RSA as their minimum for asymmetric security, and AES-128 / SHA-256 as their minimum for symmetric security. This is a [112, 128]-bit security lower bound.
Truncating a hash to 160 bits yields 80-bit security, which is insufficient. 128 bits (64-bit security) is out of the question.
Depending on what you're doing, "SHA-512/128" could have a 128-bit security level. But I guess it's safer to assume n/2 when making a general recommendation.
There are six SHA-2 family hash functions:
* SHA-224
* SHA-256
* SHA-384
* SHA-512
* SHA-512/224
* SHA-512/256
SHA-512 is faster than SHA-256 in software on 64-bit machines. That's a more important difference than the security level. However, there are two major caveats to consider: 1) Hash function performance is more likely to matter on cheap (non-64-bit) hardware where everything is slow, than on fancy hardware where everything is fast. 2) Some x86 and ARM chips have hardware accelerated implementations of SHA-256, but not of SHA-512.
This attack is almost 2^64, and SHA-1 is 160 bits. All else being equal (big big if) that means sha256 is 102 bits, meaning 362703572709.30493 times more expensive. Or about $16321 trillion USD.
SHA-3 (originally named Keccak) is built on an entirely different foundation (called a sponge function), so it is unlikely that any attack against SHA-1 will be relevant to SHA-3. However, sponge functions are a relatively new idea, and weaknesses in the basic principles could conceivably be found in the future, as could weaknesses in the Keccak algorithm specifically.
SHA-1 has been broken for 15 years, so there is no good reason to use this hash function in modern security software. Attacks only get better over time, and the goal of the cryptanalysis effort is to warn users so that they can deprecate algorithms before the attacks get practical. We actually expect our attack to cost just a couple thousand USD in a few years.
>no good reason to use this hash function in modern security software
This argument conveniently ignores the cost to switching existing software (i.e. it's completely detached from reality).
I’m gonna say many developers will not care but and many compilers will not care either.
So yeah, Linus’ main deterrent reason (code won’t compile) doesn’t apply anymore.
HOWEVER!
1. A chosen-prefix attack still needs to compute TWO suffixes m1 and m2 so that h(a1+m1) = h(a2+m2). This does NOT mean that given a1 and a2 you can find a single m2 so that h(a1) = h(a2+m2). So that ONLY THE ORIGINAL AUTHOR OF THE COMMIT could spoof their own commit, by preparing in advance and attaching a long and weird comment in the end. And you could build tools to watch out for such commits in the first place
2. If git had used HMAC based on SHA1 then it would have been fine, even after this attack has become feasible.
3. Furthermore, it is likely still kinda fine because Merkle Trees have nodes referencing previous nodes. You’d have to spoof every historical node as well, to push malicious code. BitTorrent also requires computers to supply an entire merkle branch when serving file chunks.
Maybe someone can elaborate on this.
From the email...
"I haven't seen the attack yet, but git doesn't actually just hash the data, it does prepend a type/length field to it. That usually tends to make collision attacks much harder, because you either have to make the resulting size the same too, or you have to be able to also edit the size field in the header."
[...]
"I haven't seen the attack details, but I bet
(a) the fact that we have a separate size encoding makes it much harder to do on git objects in the first place
(b) we can probably easily add some extra sanity checks to the opaque data we do have, to make it much harder to do the hiding of random data that these attacks pretty much always depend on."
But it sounds as if the cost of changing the hash algorithm is high. What are the impacts of this change? How many things would break if git just changed the algorithm with each new release? Does git assume that the hash algorithm is statically given to be SHA-1 or are there qualifiers on which algorithm is enabled/permitted/configured?
Git is moving to a flexible hash though. [1]
[1] https://stackoverflow.com/questions/28159071/why-doesnt-git-...
The Python community would freak out, lol.
Unless Linus really believes that git will be fine using SHA-1 for decades to come I don't think it's very responsible to keep kicking the ball down the road waiting for the inevitable day when a viable proof of concept attack on git will be published and people will have to emergency-patch everything.
$ curl https://shattered.io/static/shattered-1.pdf | wc -c
422435
$ curl -s https://shattered.io/static/shattered-2.pdf | wc -c
422435
Second, the length is already being hashed into the content during computation of a SHA-1 hash. Look up Merkle-Damgard construction: https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_co...
There is benefit in storing the length at the prefix as well, as you can avoid length extension attacks, but that's not making attacks "much harder".
The only thing that prefixing the length makes difficult is using the same prefix multiple times: you basically have to make up your mind about the type and length before mounting the shattered attack. Also, the prefix means you have to do your own shattered attack and can't use the PDFs that google provided as proof of their project's success. Price tag for that seems to be 11k.
[1]: https://github.com/cr-marcstevens/sha1collisiondetection
As I tried to point out, the length is already part of what the SHA-1 function hashes:
https://tools.ietf.org/html/rfc3174#section-4
As a summary, a "1" followed by m "0"s followed by a 64-
bit integer are appended to the end of the message to produce a
padded message of length 512 * n. The 64-bit integer is the length
of the original message. The padded message is then processed by the
SHA-1 as n 512-bit blocks.
From what I understood the core of Linus' argument[1] is that it's very hard to make a "bad" variant of the code which has the same length _and_ the same hash while still looking like sane code. For random data files, sure those are more at risk.
That is very hard, but not what was quoted above. The length has no part in it. The core part needed for the shattered collision attacks involves basically binary data.
$ curl -s https://shattered.io/static/shattered-1.pdf | hexdump -C > s1
$ curl -s https://shattered.io/static/shattered-2.pdf | hexdump -C > s2
$ diff s1 s2
13,20c13,20
< 000000c0 73 46 dc 91 66 b6 7e 11 8f 02 9a b6 21 b2 56 0f |sF..f.~.....!.V.|
< 000000d0 f9 ca 67 cc a8 c7 f8 5b a8 4c 79 03 0c 2b 3d e2 |..g....[.Ly..+=.|
< 000000e0 18 f8 6d b3 a9 09 01 d5 df 45 c1 4f 26 fe df b3 |..m......E.O&...|
< 000000f0 dc 38 e9 6a c2 2f e7 bd 72 8f 0e 45 bc e0 46 d2 |.8.j./..r..E..F.|
< 00000100 3c 57 0f eb 14 13 98 bb 55 2e f5 a0 a8 2b e3 31 |<W......U....+.1|
< 00000110 fe a4 80 37 b8 b5 d7 1f 0e 33 2e df 93 ac 35 00 |...7.....3....5.|
< 00000120 eb 4d dc 0d ec c1 a8 64 79 0c 78 2c 76 21 56 60 |.M.....dy.x,v!V`|
< 00000130 dd 30 97 91 d0 6b d0 af 3f 98 cd a4 bc 46 29 b1 |.0...k..?....F).|
---
> 000000c0 7f 46 dc 93 a6 b6 7e 01 3b 02 9a aa 1d b2 56 0b |.F....~.;.....V.|
> 000000d0 45 ca 67 d6 88 c7 f8 4b 8c 4c 79 1f e0 2b 3d f6 |E.g....K.Ly..+=.|
> 000000e0 14 f8 6d b1 69 09 01 c5 6b 45 c1 53 0a fe df b7 |..m.i...kE.S....|
> 000000f0 60 38 e9 72 72 2f e7 ad 72 8f 0e 49 04 e0 46 c2 |`8.rr/..r..I..F.|
> 00000100 30 57 0f e9 d4 13 98 ab e1 2e f5 bc 94 2b e3 35 |0W...........+.5|
> 00000110 42 a4 80 2d 98 b5 d7 0f 2a 33 2e c3 7f ac 35 14 |B..-....*3....5.|
> 00000120 e7 4d dc 0f 2c c1 a8 74 cd 0c 78 30 5a 21 56 64 |.M..,..t..x0Z!Vd|
> 00000130 61 30 97 89 60 6b d0 bf 3f 98 cd a8 04 46 29 a1 |a0..`k..?....F).|
Also now git has collision detection code from sha1collisiondetection [1], making attacks even harder.
[1]: https://github.com/cr-marcstevens/sha1collisiondetection
The more restrictive the serialization format of the hashed data, the harder it is to find a collision that’s valid in the given application context.
$ curl -s https://shattered.io/static/shattered-1.pdf | hexdump -n 512 -C
00000000 25 50 44 46 2d 31 2e 33 0a 25 e2 e3 cf d3 0a 0a |%PDF-1.3.%......|
00000010 0a 31 20 30 20 6f 62 6a 0a 3c 3c 2f 57 69 64 74 |.1 0 obj.<</Widt|
00000020 68 20 32 20 30 20 52 2f 48 65 69 67 68 74 20 33 |h 2 0 R/Height 3|
00000030 20 30 20 52 2f 54 79 70 65 20 34 20 30 20 52 2f | 0 R/Type 4 0 R/|
00000040 53 75 62 74 79 70 65 20 35 20 30 20 52 2f 46 69 |Subtype 5 0 R/Fi|
00000050 6c 74 65 72 20 36 20 30 20 52 2f 43 6f 6c 6f 72 |lter 6 0 R/Color|
00000060 53 70 61 63 65 20 37 20 30 20 52 2f 4c 65 6e 67 |Space 7 0 R/Leng|
00000070 74 68 20 38 20 30 20 52 2f 42 69 74 73 50 65 72 |th 8 0 R/BitsPer|
00000080 43 6f 6d 70 6f 6e 65 6e 74 20 38 3e 3e 0a 73 74 |Component 8>>.st|
00000090 72 65 61 6d 0a ff d8 ff fe 00 24 53 48 41 2d 31 |ream......$SHA-1|
000000a0 20 69 73 20 64 65 61 64 21 21 21 21 21 85 2f ec | is dead!!!!!./.|
In the double-digit thousands of dollars, an attack that gets 10x or 100x harder is still cheap for state actors.
Assuming the NSA is at least a year or two ahead of the field, git should now accelerate its migration process.
I still feel like they really should've taken this problem more seriously and earlier. The more we wait the more painful the migration will be when the day comes to move to a different hash function, because everybody knows that'll happen sooner or later. Two years ago we had a collision, now we have chosen prefix, how much longer until somebody actually manages to make a git object collision?
And keep in mind that public research is probably several years behind top secret state agency capabilities. Let's stop looking for excuses every time SHA-1 takes a hit and rip the bandaid already. It's going to be messy and painful but it has to be done.
As I read the OP [1] a chosen-prefix collision attack such as this allows you to “edit the size field in the header”. Or am I missing something?
1. “A chosen-prefix collision is a more constrained (and much more difficult to obtain) type of collision, where two message prefixes P and P’ are first given as challenge to the adversary, and his goal is then to compute two messages M and M’ such that H(P || M) = H(P’ || M’), where || denotes concatenation.”
EDIT: On second thought I was missing something: the adversary is further constrained in the git case because it must find M and M’ of correct length (specified in P and P’). Linus is right (as usual), this probably makes it much harder.
This argument sounds sound to me.
People store things in git that aren't text. Therefore it's not safe.
With this chosen-prefix attack, they chose two prefixes and generated collisions by appending some data. So your two prefixes just need to be "tree {GOOD,BAD}\nauthor foo\n\nmerge me\0"
The only thing preventing injecting a backdoor into a pull request now seems to be git's use of hardened sha1.
See a previous discussion here, regarding Linus's position on this in 2017: https://news.ycombinator.com/item?id=13719368
-> https://stackoverflow.com/questions/9392365/how-would-git-ha...
(This does not answer your question, but is still interesting.)
FWIW this doesn't apply to Fedora currently, because it has a patch that re-enables SHA-1 in security level 2 in non-FIPS mode: https://src.fedoraproject.org/rpms/openssl/blob/master/f/ope...
That was with NO crypto/signature spoofing involved... if the CFO has now been trained to not act on large dollar amount requests from the CEO without at least checking a digital signature... perhaps the CFO would be more likely to fall for it now since he has been "trained" that cryptographic signatures are a sign of authenticity?
So if I understand today’s news correctly, you could use this to break blockchain integrity and offer-up alternative “valid” historical blocks (but not cheat at proof-of-work). You would still need to convince a quorum of network nodes to use your fake historical blocks - I imagine this might be doable on lesser-used coins that still have some trades - you could probably combine this with a few pump-and-dump trades too (without costing you anything as the coins you pump would be stolen).
How do I convince my IT department to update our CA to sha256?
Many public trusted CA certain are self-signed with SHA-1. These keys sign using SHA-256
We have tried to contact the authors of affected software before announcing this attack, but due to limited resources, we could not notify everyone.
Is there a list of affected software out there?
https://github.blog/2017-03-20-sha-1-collision-detection-on-...
Another reason is that for any given hash its theoretical maximum strength against any attack will be less than or equal to its bit length, but the practical strength always trends lower over time as attacks are found, and having two algorithms to attack increases the chances of finding flaws.
https://link.springer.com/chapter/10.1007/978-3-540-28628-8_...
"SHA-1 is a slaughterhouse"
"SHA-1 is a shambles"
Beyond that prefixing your comment by "downvoted" is frankly silly and only serves to derail the conversation IMO.
You are of course right that "a shambles" is perfectly fine British English, but that's beside the point.
Not sure how it would be measured, but I think a /r/dataisbeautiful map would be interesting to see.
I'd think "in practice" would mean evidence of contemporary usage.
-Shakespeare (Henry VI, Part 3)
Today "shambles" remains in the common vocabulary, but only in a sense of things being messy or disorganised, most English readers today probably wouldn't think of literal violence and I suppose that the people who named this website, likewise, were thinking of modern usage.
(nowadays devoid of mead products but a nice picturesque place to visit if you can stand crowds. Try the bookshop)
Sigh. Again with this idiocy. All instances where the adversary is capable of launching this attack financially mean they also have the capability to write the exploit themselves.
Targets worth attacking at a high financial cost will most likely be the first to take measures against this attack.
The kind of target that takes a longer time to switch most likely isn't worth attacking unless it's a very cheap and fast operation.
And the longer you spend developing an exploit, the less viable the attack will become.
Iran will eventually create a nuclear bomb, why don't we gave them one now, it's the same thing isn't it ?
So they just decided to try their attack and spend two years worth of salary on it?? That's crazy.
Not in the way you explain. Multi-million dollar grants are usually awarded over multiple years, and pay for multiple researchers’ salaries, as well as other resources, some of which are expected to outlast the project (e.g. microscopes, or hardware for databases). Burning 75k on a single experiment (which is effectively what was done here) is rare.
Note that this is true even for current hot topics such as biomedical (e.g. cancer) research, for which vast chunks of the federal budget have been allocated in multiple countries. Obtaining similar sums in less sexy fields is much harder. And even in biomedical research, multi-million dollar grants are considered large. Most grants are much smaller, they just don’t get talked about as much.
Since you mention human RNA samples I assume you know this. You mention the per-milligram cost but this is pretty misleading if you mean to imply that “milligram” is somehow little, because it isn’t: yes, the samples are tiny (≤1 µg of RNA is more typical than milligrams!), but so what? It’s not like we need more.
Like... chaotic good. Really really good.
Breaking MD5 for the Flame malware probably set the NSA back millions when you sum the person-hours and CPU time together.