Slashdot Mirror
Google Has Demonstrated a Successful Practical Attack Against SHA-1 (googleblog.com)
Reader Artem Tashkinov writes: Ten years after of SHA-1 was first introduced, Google has announced the first practical technique for generating an SHA-1 collision. It required two years of research between the CWI Institute in Amsterdam and Google. As a proof of the attack, Google has released two PDF files that have identical SHA-1 hashes but different content. The amount of computations required to carry out the attack is staggering: nine quintillion (9,223,372,036,854,775,808) SHA1 computations in total which took 6,500 years of CPU computation to complete the attack first phase and 110 years of GPU computation to complete the second phase.
Google says that people should migrate to newer hashing algorithms like SHA-256 and SHA-3, however it's worth noting that there are currently no ways of finding a collision for both MD5 and SHA-1 hashes simultaneously which means that we still can use old proven hardware accelerated hash functions to be on the safe side.
Google says that people should migrate to newer hashing algorithms like SHA-256 and SHA-3, however it's worth noting that there are currently no ways of finding a collision for both MD5 and SHA-1 hashes simultaneously which means that we still can use old proven hardware accelerated hash functions to be on the safe side.
Uh, "took 6,500 years of CPU computation to complete the attack first phase and 110 years of GPU computation to complete the second phase"
Practical attack? Google's marketing department at work?
If one looks at the history of what happened the last time a major hash was broken, there was a large gap between when MD5 has its first collisions and when it became practical to detect collisions. There was about a little under a decade between when the first collisions were found and when it became easy to find collisions. The general expectation is that hash systems will fail gracefully in a similar way so we have a large amount of warning to switch over. Unfortunately, we've also seen that in practice people don't adopt new hash algorithms nearly as fast as they should. The second to last Yahoo security breach was so bad in part because the passwords were hashed with a completely unsalted MD5 https://nakedsecurity.sophos.com/2016/12/15/yahoo-breach-ive-closed-my-account-because-it-uses-md5-to-hash-my-password/. The lack of salting would have been by itself a problem even when MD5 was still considered insecure. That in 2015, a decade after MD5 was broken for almost all purposes, Yahoo was still using it, is appalling. Unfortunately, they likely aren't the only one. And I fully expect that if Slashdot is around in a decade we'll read about someone who has foolishly stored passwords using SHA-1.
The thing is that there is not actually a lot you can do with an SHA1 hash collision. Sure, you may be able to impersonate a site by use of a fake certificate. But these are around anyways because of CAs with shoddy security and governments that do not understand the value of security and just coerce CAs in giving them out. So an SHA1 collision is actually a bit of overkill for that and likely the most expensive option by a large margin. So what else is left? I do not see anything.
Sure, if this was something Jonny hacker could do in his basement in a week and it was a one-sided collision (i.e. one document is already given when the attack starts, two-sided collisions where you create both documents are much, much easier to do), this may be some not very serious threat, but even that is not the case here.
What remains is a stunt that at best helps to estimate the difficulty of a not very relevant attack. Not that this is actually bad, good researchers demonstrate what their theories mean and a stunt is one form to do it, but the implications of this one are pretty minor.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
Any crypto geeks want to weigh in on the truth of this statement? I've often wondered about this. Wouldn't using two hash algorithms be easier and more effective over the long term than getting the whole world to upgrade to the Latest And Greatest Hash every ~10 years?
The key sequence to access my Slashdot bookmark in Firefox is Alt-B-S. I don't believe this is a coincidence.
And yet, when was the last time you saw a downloadable PDF file with SHA-XXX or MD5 hashes available.
Of course, everyone with any sense checks the hashes when they download an ISO file.
But they download PDF without any reservation
How come?
Apollo program demonstrated practical transportation to the moon.
love is just extroverted narcissism
compare the most recent public timestamp: http://publictimestamp.org/ptb/PTB-25461
here you can donwload the most recent public timestamp with all hashes: http://publictimestamp.org/ptb/PTB-25461
I know this isn't the primary point of the announcement, but does anyone know where the authors get 10 years from, as included in this statement: "Today, 10 years after of SHA-1 was first introduced..."? Best I can tell, SHA-1 was formally defined in 1995 (FIPS PUB 180-1), and I'm pretty certain it was in common widespread use long before 2007. Are they referring to the first time it was introduced into one of their own products or something? or I'm I missing something obvious?
Not a lot you can do?
Anything that requires signatures is vulnerable to forgery if the signer's certificate specifies SHA1.
An attacker could forge:
1. Software signatures - to slip malware into a software vendor's distribution channels.
2. SSL certificates - to MITM web connections to phish, steal data, or distribute malware.
3. Personal digital signatures - to fabricate documents, including emails, transaction, orders, etc that are normally trusted implicitly due to the signature
4. Subordinate CA certificates - to create trusted certificates which permit all of the above
The problem lies with #4. The real risk is not a one-off duplicate of John Doe's smart card. The real danger is the CAs signed with SHA1 who are still trusted by browsers, applications, and OSes around the world. If an attacker counterfeits one of their certificates, he can issue arbitrary certificates for any web site, any software publishers, or any user.
The only solution is to discontinue the use of SHA1 internally and to revoke trust for all CAs that still use SHA1. Better crypto has existed for a long time---the standard for SHA2 was finalized in 2001, well over a decade ago.
---
According to the latest ruleset, this post should be modded as Vorpal Flamebait +5.
I occasionally use a signed .jar in the company intranet. Reading TFA, I wondered what hash is used to sign that? It seems that jarsigner is not willing to divulge, so I had to write a little piece of code aaand ... yup, it's SHA1!
How common is this? Is loads of software now susceptible to attack by replacing a original code by a malware with the same SHA1?
The data was crafted in order to simplify attaining their goal. It would be far more damning if they could put together a document that results in the same SHA-1 hash as that of an externally specified document.
The Internet Archive to the rescue:
http://web.archive.org/web/*/https://marc-stevens.nl/research/papers/C13-S.pdf
The paper describes the tech behind the code (linked below) capable of *detecting* the probability of a file + sha-1 hash being either the result of a forgery, or "easier to forge" (from what I understand of the attack against SHA1 done by Google, et all.):
https://github.com/cr-marcstevens/sha1collisiondetection
Now, to try that code against some files as well as the two PDFs google released... :-)
Indeed. Not a lot you can do even when you ignore the high effort needed and that it is a 2-sided collision. I do not dispute that you should not use SHA1 when you want security, but the actual attacks possible at this time are pretty much irrelevant. Your list just confirms that. It looks impressive (well, sort of), but when you take into account the effort of each attack and the possible gain, they become meaningless, because higher gains at lower effort are around plenty.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
You seem to miss the point entirely. This is the expected course of degradation for a hashing algorithm. First it becomes theoretically possible, then it becomes demonstrable at extreme cost (meaning only a few organizations could pull it off). Then it becomes expensive but possible, then your watch can do it. From the amount of time it takes to hit these waypoints you can determine when it will be useless. Because changing the course of large organizations is like trying to turn around an aircraft carrier, you need to start ahead of time.
When it becomes theoretically possible it's about time to start the migration so that it's mostly just stragglers by the time it gets to the point where it's within financial range of your attackers to use it against you.
With over 9 quintillion hashes being computed, this hardly seems practical.
The web site where it is published use SHA-256
Would it be possible to tamper a famous git repo (e.g. Linux) by writing a malicious commit with the same hash?
But these are around anyways because of CAs with shoddy security and governments that do not understand the value of security and just coerce CAs in giving them out.
There's a big difference between having a systemic flaw and working on social engineering, and the presence of one doesn't invalidate strengthening against the other.
Nope I guess.
Such attacks append random junk to your original data and since the Linux kernel is made of text files your additions will be immediately visible.
However ... there are blobs in the kernel (firmware) and then it all becomes murky.
Not a lot you can do?
Anything that requires signatures is vulnerable to forgery if the signer's certificate specifies SHA1.
An attacker could forge:
1. Software signatures - to slip malware into a software vendor's distribution channels.
That requires a second pre-image attack, not just a collision attack. (What gweihir called "two-sided" rather than "one-sided"... though that is not standard terminology).
2. SSL certificates - to MITM web connections to phish, steal data, or distribute malware.
Also requires a second pre-image attack.
3. Personal digital signatures - to fabricate documents, including emails, transaction, orders, etc that are normally trusted implicitly due to the signature
This one can be done with a collision attack. You generate two different documents which hash to the same value, but have different contents. The PDF format, unfortunately, make it pretty easy to generate documents which look sensible and have this property. It's not possible with more transparent formats (not without a second pre-image attack).
4. Subordinate CA certificates - to create trusted certificates which permit all of the above
The problem lies with #4.
This can only be done with a collision attack if the CA is really, really stupid. Proper CAs should include chain-length restrictions in their certificates. That way even if you can create two certificates which hash to the same value, one of which has the keyCertSign bit set to true (which the CA would refuse to sign) and one of which does not (which presumably you can get the CA to sign), it wouldn't matter because if you used the former to generate other certs, no one would accept them due to the fact that your chain is too long.
The only solution is to discontinue the use of SHA1 internally and to revoke trust for all CAs that still use SHA1.
I certainly agree that any CA still issuing certificates with SHA1 should not be trusted. Any existing certs based on SHA1 should be scrutinized, but most of them are still secure.
Better crypto has existed for a long time---the standard for SHA2 was finalized in 2001, well over a decade ago.
Absolutely. Of course, I say that as the maintainer (ish) of an open source crypto library that still uses SHA1. In systems that weren't originally designed for digest agility, it's often hard to retrofit. Today's news is a nice kick in the pants, though.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
A country is only as secure as its weakest link. More computing power means the game is constantly evolving. What was once the strongest link 20 years ago might now susceptible because the system was never upgraded. Case in point; MD5 is now laughable.
> The thing is that there is not actually a lot you can do with an SHA1 hash collision.
Do you realize that the zionist entity attacked and partially demolished Iran's nuclear industry with a mere MD5 collision, use to turn a slightly incorrectly configured Microsoft IIS certificate into a rogue code-signing stamp, which made it possible to inject undetectable malware into (pirated) Siemens Simatic S7 SCADA?
It took an unexpectedly slow, vintage Pentium Pro computer getting inexplainable BSOD (due to malware making it run slightly even slower), followed by months of research by best of best belorussian virus analysts, just to find out what happened. Strangely, the hardware export embargo against Iran saved the theocracy's posterior that time. Nonetheless, the novel math behind creating that MD5 collision was brilliant. Nothing less expected from the jews, they are most clever and cunning people.
Fancy numbers, but they're incomplete. What was the total cost for this 2 year exercise if a ordinary human with a soul sat down and paid for every watt - how much did this PDF experiment cost? The maths has been clear about this for a very long time, google is drinking cool-aid if they think this means anything more than what has already been discussed or discovered.
Let me put it another way, in recent history the A+B=C mathematical formula was proven by a reclusive Japanese mathematician. Have we stopped using RSA keys? Has the banking system been completely replaced with mathematics which does not fall victim to this proof? No. And they wont. 1100 GPU years means nothing unless you're the one paying the bills.
Google needs to start hiring humans with brains that can think - and better yet, some grey hairs from working in IT.
Actually, that _is_ my point. This is not any big news, it is a small step in an expected progression. But my second point is that the value of certificates (what this mostly applies to) is generally vastly overrated.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
That is just my point. There is a big difference between a high-effort attack that is hard to do and a simpler one that has been done mass-scale. The second is a real risk, the first one is pretty irrelevant. Incidentally, the defects of the CA system are systematic, and they cannot be fixed by merely moving to a non-broken hash function.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
You know which they are
Your 601 bit key of all "a"s will be brute forced in under 5 seconds. The theoretical maximum time to brute force all keys is meaningless. You only need to find one key and the keys are not evenly distributed throughout the keyspace.
You may notice they never do these stunts on ASCII text files.
The attack always requires to be able to store a large number of random data on the document.
There are 62 different bytes in the provided PDFs : part of these are the edited message, part of them are the 'attack'. That's 496 bits.
So it may be applied to any kind of document allowing to store about 496 bits of (invisible) data on it (and to be on the safe side, I'm assuming even half of that could be enough).
Not all successful attacks will require the size of the document to not change.
To look at it on a subject I dabble in (DNSSEC):
In DNS the chain of trust puts a hash of the zone key on the level above, along with a 16 bits checksum.
I'm assuming the checksum to only represent a 'minor' inconvenience.
This means that an RSA DNS key may be forged as it's basically stored as the exponent followed by any number of bytes (limited to 1KB : more than enough).
On another hand Elliptic curve seems out of the question as their size is small and constant.
All this to say, the vulnerability of SHA-1 is to be taken with a grain of salt.
Irrelevant news and morons using moderation to mod down what they disagree on. 2018 resolution: so long.
Since SHA-2 ciphers where introduced in TLS 1.2, that suggest we should remove TLS 1.0 and TLS 1.1. suppoort soon.
TFS says a total of ~6600 computer years.
Get a botnet of ~80k computers and you have it in around a month. That's hardly "meaningless" when we're talking something as globally damaging as a root CA certificate, especially when its coming at a time that we're seeing botnets hitting millions of nodes.
AI will ruin encryption. Microsoft and gov will see to it. Enjoy privacy while you can.
This can only be done with a collision attack if the CA is really, really stupid. Proper CAs should include chain-length restrictions in their certificates.
Please correct me if I'm wrong, but it appears that most CAs are really, really stupid. Here's a list of the CAs included in Firefox: https://mozillacaprogram.secur... . I split the PEMs into a pile of files, and checked them:
$ for pem in * ; do openssl x509 -text -in $pem | grep pathlen ; done
CA:TRUE, pathlen:4
CA:TRUE, pathlen:1
CA:TRUE, pathlen:1
CA:TRUE, pathlen:7
CA:TRUE, pathlen:7
CA:TRUE, pathlen:3
CA:TRUE, pathlen:5
CA:TRUE, pathlen:12
CA:TRUE, pathlen:12
CA:TRUE, pathlen:12
CA:TRUE, pathlen:12
CA:TRUE, pathlen:3
CA:TRUE, pathlen:10
CA:TRUE, pathlen:3
So out of 172 root CAs only 14 include any path length restrictions, and even the ones who do still allow some chaining. This is what allowed the beautiful Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate to succeed.
I don't think the SHApocalypse will be tomorrow. This was an identical-prefix attack instead of a chosen-prefix which constrains the attacker considerably, and the computation required is much higher even to generate simple collisions. However, (again, please correct me if I'm missing something) it does seem plausible that that further weaknesses will be found which provide just enough leverage to forge a signature with one of those 172 CAs, and we may eventually see a rogue sha1WithRSAEncryption CA issued.
So out of 172 root CAs only 14 include any path length restrictions, and even the ones who do still allow some chaining.
O_o
We're doomed.
I don't think the SHApocalypse will be tomorrow. This was an identical-prefix attack instead of a chosen-prefix which constrains the attacker considerably, and the computation required is much higher even to generate simple collisions. However, (again, please correct me if I'm missing something) it does seem plausible that that further weaknesses will be found which provide just enough leverage to forge a signature with one of those 172 CAs, and we may eventually see a rogue sha1WithRSAEncryption CA issued.
I concur, completely.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
No you're missing the point. Social engineering and a trust model is not a systemic failure in the sense that the attack is replicatable with any kind of certainty. A broken hash function however is.
You break a hash function, it's broken.
You trick a guy into giving you a certificate to break the chain of trust, doesn't mean you can do it again when that cert becomes revoked.
Different person, but just downmodded because I could and your spam annoys me.
I'm glad to help via via NEW APK Hosts File Engine 9.0++ SR-7 32/64-bit https://www.google.com/search?hl=en&source=hp&biw=&bih=&q=%22APK+Hosts+File+Engine%22+and+%22start64%22&btnG=Google+Search&gbv=1/
Ads & malware rob speed/security/privacy
Hosts add speed (via hardcodes/adblocks), security (vs. bad sites/malware/poisoned dns), reliability (vs. dns down), & anonymity (vs. dns requestlogs/trackers).
Less power/cpu/ram + IO use vs. DNS/routers/addons/antivirus + less security bugs/complexity & faster vs. addons/routers/remote dns!
Avoids DNSChangers in routers/IP settings & dns redirects (99.999% of ISP DNS != patched vs. it) + lightens DNS load & resolves faster from local system RAM!
* Via what u NATIVELY have built in IP stack in FASTER kernelmode!
APK
P.S. - Safe https://www.virustotal.com/en/file/e01211ca36aa02e923f20adee0a3c4f5d5187dc65bdf1c997b3da3c2b0745425/analysis/1433430542/
See my subject: You're the same unidentifiable weasel I always blow away on hosts files' efficacy & you're butthurt I do, lol!
* You're effete useless "downmodpoints" are all drained now & I just repost nullifying your PUNY 'weapon' as always https://tech.slashdot.org/comments.pl?sid=10285975&cid=53928565/
Hahahahahaha!
APK
P.S.=> As always, I get the LAST LAUGH on losers like you because you're EASY to outthink, outsmart & outdo (you have no skills to do a better piece of work than I do that gets users of it more speed, security, reliability & anonymity online than ANY other single "so-called 'solution'" that SLOWS YOU DOWN where hosts speed you up 2 ways & does more for FAR LESS natively w/ less moving parts complexity/room for exploit & breakdown & is slower (addons) or security issue riddled (DNS/antivirus))... apk
You really have no clue about IT Security Risk Management. A broken trust model most certainly is a systematic failure and it is far, far worse than a defect implementation detail like an insecure hash function.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
It's also not mentioned, anywhere in this articles discussion so far, that this was constructed using a birthday attack, which is approximately log N complexity of crafting a collision for a specific existing hash. For most attack vectors to be practical you need to be able to craft a valid document that hashes to a particular hash, rather than crafting two documents that hash to an arbitrary hash, as was demonstrated by this Google demo.
See my subject: Sure I do. I love crushing unidentifiable fatherless bastards like you (you act like a bitch raised by one is why).
* I've actually done good things that do right by others, e.g. & yes I'll check when little weasels like YOU try your bullshit on me trying to wreck MY GOOD NAME & good works that slime like YOU can never ever produce OR show any errors in work like mine!
(I know WHY you do it - You do because you know you're shit & can't do the same as I have - you're a waste).
That's all a piece of shit like you is capable of - trying to spread your own misery onto others (especially those doing well & you're not, nor will you ever & you KNOW it scumbag).
APK
P.S.=> It just must TRULY suck to be you - you can't produce anything of worth because you wasted your life 'trolling' like the gossiping bitch you are (you're not a real man is why per the above) & are a waste of life - & funniest part is, it's only YOUR OWN FAULT you're such reprehensible scum I can laugh at... apk
I didn't read your post. Hear that voice in your head, giving you good advice in the succinct form of three letters? You should listen to it.