Google Has Demonstrated a Successful Practical Attack Against SHA-1 (googleblog.com)

Re:Practical? by darkain · 2017-02-23 06:07 · Score: 5, Interesting

It is all about cost-benefit. CPU speeds continue to get faster, and renting CPU time on cloud providers become cheaper and cheaper.

Why is this significant? There are still major certificate authorities out there with intermediate certificates using SHA-1. Find a collision for these certificates, and you essentially become a new intermediate certificate authority with the ability to issue domain certs for basically anything you want and they'll validate in browsers.

Now thing of government agencies or crime syndicates that could afford the CPU/GPU time to do this. It is a highly practical attack vector now.

Re:Practical? by MiniMike · 2017-02-23 06:08 · Score: 1

They have an alternative use of the word practical.

What should happen and what will happen by JoshuaZ · 2017-02-23 06:15 · Score: 4, Interesting

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.

Re:What should happen and what will happen by swillden · 2017-02-23 09:00 · Score: 3, Informative

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 secure.
Actually, even with salting, no standard cryptographic hash function is appropriate for password databases. You can squeak by if you iterate the hash function enough times, but even that is pretty weak, since it means that an attacker with lots of GPUs -- or, even worse, special-purpose hardware -- can perform hashes so much faster than you can that the key stretching you obtain is minimal.
The state of the art in password hashing is algorithms like Argon2, with parameters that are tuned to require significant amounts of not just CPU time, but RAM and threads. Argon2, tuned to require, say, 10ms of time on four cores and 256 MiB of RAM, is going to significantly strengthen passwords. The RAM requirement means a GPU with 4 GiB of RAM can only test 16 passwords in parallel, making GPU-based cracking essentially useless, since what GPUs provide is huge parallelism. Custom ASICs would do better, but would still run into bottlenecks on the speed of the RAM. Making really fast cracking hardware would require either huge amounts of RAM, or large amounts of extremely fast RAM. Either way, big $$$.
Even better, if at all possible you should use a hash that is keyed as well as salted. Doing that requires having some place to store the key that won't be compromised by the same sorts of attacks that compromise your password database. In most cases that's hard to do. Argon2 will accept a key so you can get both sorts of protection, though if you can be really, really certain that no attacker can ever get the key, then you can use a standard cryptographic hash function in a keyed mode, e.g. HMAC-SHA256, though I'd still recommend using a purpose-designed password hash (e.g. Argon2) in case your key is compromised.

--
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Re: What should happen and what will happen by Miamicanes · 2017-02-23 09:05 · Score: 1

There's a straightforward reason why lots of web apps continued to use MD5 *long* after it was deprecated: MySQL had a function for md5() almost from the start, but didn't have an inline function for SHA() until 4.0.2... and 4.x didn't become the default version in long-term stable server-oriented distros until 2006 or later. Getting a new release to run on YOUR development computer? Easy. Convincing an enterprise sysadmin to let you have it on a production server before it has become the 'stable' default *and* the servers have been upgraded to the new distro release? Good luck. Most developers don't have the social capital & stamina to campaign for newer versions from stubborn admins, and will just say 'fuck it' and use MD5 if their boss isn't ready to fight that battle for them.
Re:What should happen and what will happen by JoshuaZ · 2017-02-23 09:59 · Score: 1

The problem with that is on the other practical end: if you massively increase the resources needed will also increase the server side resources; it won't be as bad as it will be on the cracking end, but server resources are expensive. There's a point beyond which you aren't going to get people to agree to do it and a certain point where that insistence really does become reasonable. This is similar to why we don't use much longer keys for public key encryption and use really large primes for DH key exchange.
Re: What should happen and what will happen by flink · 2017-02-23 11:04 · Score: 1

There's a straightforward reason why lots of web apps continued to use MD5 *long* after it was deprecated: MySQL had a function for md5() almost from the start, but didn't have an inline function for SHA() until 4.0.2...
What sane person does their hashing inside their RDBMS? You hash it in code before you store it.
Re:What should happen and what will happen by swillden · 2017-02-23 12:10 · Score: 1

The problem with that is on the other practical end: if you massively increase the resources needed will also increase the server side resources; it won't be as bad as it will be on the cracking end, but server resources are expensive.
It won't be as bad as on the cracking end, that's the whole point. The reason for doing password hashing is to exploit the asymmetric level of effort between hashing and brute force search. To make that work, though, you do need to invest as much as you can afford in the server, to move the bar for the attacker as high as possible -- hopefully out of reach of all but the most serious. If you can't afford very much, fine, but realize that you're also not setting the bar very high.
But this is exactly why good password hashing algorithms are moving to RAM consumption as the primary barrier. It's pretty trivial for a server with many GiB of RAM to allocate 256 MiB to hashing a password, for a few milliseconds, but it gets very costly, very fast, for the attacker. And if you can't afford 256 MiB, how about 64?
What you definitely do not want is a solution that takes microseconds and uses a few dozen bytes. That creates a trivial situation for the attacker given modern hardware, and your server absolutely can afford more than that.

This is similar to why we don't use much longer keys for public key encryption and use really large primes for DH key exchange.
Nope. The leverage factor in the password hashing case is linear, since the entropy of passwords is constant (on average). The leverage factor for cryptographic keys is exponential. The reason we don't use much longer keys for public key encryption, etc., is because there's no point in doing so, not because we can't afford it. The key sizes we use are already invulnerable to any practical attack in the near future. For data that must be secret for a long time, we do use larger key sizes, as a hedge against the unknown.

--
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Re:What should happen and what will happen by JoshuaZ · 2017-02-23 12:46 · Score: 1

But this is exactly why good password hashing algorithms are moving to RAM consumption as the primary barrier. It's pretty trivial for a server with many GiB of RAM to allocate 256 MiB to hashing a password, for a few milliseconds, but it gets very costly, very fast, for the attacker. And if you can't afford 256 MiB, how about 64?
Using memory dependent hashes works better if one is a small server since one will rarely have a lot of people sending in their passwords at the same time, so the RAM space you need isn't that large. If you are a large organization then this doesn't work as well because you then need room to be able to do many such calculations functionally simultaneously.

Nope. The leverage factor in the password hashing case is linear, since the entropy of passwords is constant (on average). The leverage factor for cryptographic keys is exponential. The reason we don't use much longer keys for public key encryption, etc., is because there's no point in doing so, not because we can't afford it. The key sizes we use are already invulnerable to any practical attack in the near future. For data that must be secret for a long time, we do use larger key sizes, as a hedge against the unknown.
I agree that there's a linear v. exponential difference there(although for many of these it is more like linear and subexponential due to algorithms like the number field sieve), but the rest of your comment is essentially wrong. We keep keys just long enough that we consider it to be highly unlikely that they are going to be vulnerable, but not much more than that. That's why for example we've been steadily increasing the size of keys used in RSA, DH and other systems. Note by the way that part of the concern also is that many of these algorithms require a fair bit of computation not just on the server side but on the client side as well which may be a small device like a tablet or phone. In fact, it would be a lot safer if we increased key sizes more than we do, but there are infrastructural problems with that. See e.g. discussion at http://crypto.stackexchange.com/questions/19655/what-is-the-history-of-recommended-rsa-key-sizes The only way that the linear v. exponential(or almost exponential) comes into play is how much we need to increase the underlying key size or how long we need to make the next hash system if we want it to be secure. Keys only need to be increased a tiny bit, whereas hashes need to grow a lot more. But in both cases we're still not making them any longer than we can plausibly get away with for most applications.
Re: What should happen and what will happen by Altrag · 2017-02-23 18:26 · Score: 1

The sane person who isn't given several days to investigate and implement their own algorithms (not to mention months of testing if you want to be sure you didn't fuck it up) when there's a 3-character function call sitting there waiting to be used.
Especially if they're not crypto experts and don't even know that doing the hash in the rdbms is bad, never mind why its bad. Which, for better or worse, is a large portion of the programming professionals, especially when you're including outsourcing companies that don't have much long-term interest in your project and hire the cheapest labor they can find who can do the bare minimum to make an application "work."
Re: What should happen and what will happen by brantondaveperson · 2017-02-23 22:56 · Score: 1

Ok, I give up. Why is it bad to hash values inside an RDBMS?
Re:What should happen and what will happen by swillden · 2017-02-24 03:16 · Score: 1

Using memory dependent hashes works better if one is a small server since one will rarely have a lot of people sending in their passwords at the same time, so the RAM space you need isn't that large. If you are a large organization then this doesn't work as well because you then need room to be able to do many such calculations functionally simultaneously.
Meh. If you are a large organization, you can afford more.
Anyway, the point is that you should turn it up as much as you can afford.

I agree that there's a linear v. exponential difference there(although for many of these it is more like linear and subexponential due to algorithms like the number field sieve),
Yes, NFS is subexponential, but not very "sub". And anyway, RSA is old, broken crypto which should be migrated away from.

but the rest of your comment is essentially wrong. We keep keys just long enough that we consider it to be highly unlikely that they are going to be vulnerable, but not much more than that.
I hate to resort to appeal to authority, but the actual analysis required to prove it is way more effort than I have time for this morning. Take a look at keylength.com, it has a host of authoritative references.

In fact, it would be a lot safer if we increased key sizes more than we do, but there are infrastructural problems with that. See e.g. discussion at http://crypto.stackexchange.com/questions/19655/what-is-the-history-of-recommended-rsa-key-sizes

Heh. In my previous reply I actually typed a long section about why RSA is a weak counterexample to my argument, but deleted it because it's nitpicking. Since you chose to pick that nit...
It's a valid counterexample because RSA key generation, and, to a much lesser extent, RSA private key operations, are computationally expensive enough to stress low-end devices (an issue I often have to deal with... I'm responsible for some of the core crypto subsystems in Android). But it's a weak counterexample because RSA is not modern crypto. It's ancient, outmoded, we have some reasons to suspect that factoring may not be NP hard, using it correctly is fraught with pitfalls, and it's ridiculously expensive computationally. And even still, the common standard of 2048-bit keys is secure for quite some time to come. As that stackoverflow article you linked mentions, the tendency has been to choose much larger-than-required keys (not barely large enough) rather than tracking Moore's law.
So, yeah, if you use an outdated, ridiculously expensive algorithm, and you do it on very low-spec hardware, and you want it to be secure for a very long time then, yeah, you might end up having to use barely-large-enough key sizes.
Don't do that. For asymmetric crypto use ECC. Preferably with an Edwards curve, so you don't have to deal with niggling suspicions that the curve is weak in some obscure way known only to the NSA.

--
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Re:What should happen and what will happen by JoshuaZ · 2017-02-24 13:26 · Score: 1

If you are a large organization, you can afford more.
Yes, but the point is the way it scales; If you are tiny you can reasonably assume that the almost no occasions will occur when you need to do multiple hashes in a small amount of time. If you are larger then you end up with a lot of extra RAM that you aren't going to use regularly but will need to use during peak log-in times. I agree that you can probably afford more, but getting corporations to do so is difficult; at the end of the day, everyone cares about their bottom lines.

RSA is old, broken crypto which should be migrated away from.
This suggests that you have some very opinionated and somewhat unique views.

I hate to resort to appeal to authority, but the actual analysis required to prove it is way more effort than I have time for this morning. Take a look at keylength.com, it has a host of authoritative references.
I'm familiar with many of the references there, so if there are specific ones you'd like to point to (given the large number there) it might be helpful. But I will note that what they say there agrees to a large extent with what I wrote earlier, in that they explicitly say that they are trying to provide key sizes for a desired level of protection.

It's a valid counterexample because RSA key generation, and, to a much lesser extent, RSA private key operations, are computationally expensive enough to stress low-end devices (an issue I often have to deal with... I'm responsible for some of the core crypto subsystems in Android). But it's a weak counterexample because RSA is not modern crypto. It's ancient, outmoded, we have some reasons to suspect that factoring may not be NP hard, using it correctly is fraught with pitfalls, and it's ridiculously expensive computationally. And even still, the common standard of 2048-bit keys is secure for quite some time to come. As that stackoverflow article you linked mentions, the tendency has been to choose much larger-than-required keys (not barely large enough) rather than tracking Moore's law.
As discussed in the same stackexchange link, the key choice is due to infrastructural reasons (and in fact I specifically mentioned that in the part of my above comment you apparently decided not to quote). What actually happens is that we use keys that are larger than required and then use them for a *long time* before jumping to larger key sizes when we really need too. Again, the failure to perfectly track Moore's law (or even improvements in algorithms) is infrastructural, and similar issues will apply to many other crypto systems.
Frankly, I'm concerned that you claim to be someone who has done serious crypto work when you say that "we have some reasons to suspect that factoring may not be NP hard, using it correctly is fraught with pitfalls" because this indicates some serious misconceptions; first it isn't that a suspicion that factoring may not be NP-hard. We're very certain of this. If factoring were NP hard then a whole host of current conjectures that are only slightly stronger than P != NP would have to be true. Since factoring is in NP intersect co-NP if factoring were NP-hard then we'd have NP=co-NP we'd have the polynomial hierarchy collapse. Moreover, since factoring is in BQP by Shor's algorithm we'd also have NP in BQP, which we're pretty confident doesn't happen.
But there's a more serious failure here; which is pretty much no major cryptographic system today relies on an NP-hard problem, and reliance on such is not by itself a guarantee of success. For example, Merkle–Hellman knapsack was based on a problem known to NP-hard and it was broken. Similarly, NTRUE has a closely related NP-hard problem but it isn't actually known to be equivalent.
There's also another serious failure here; being reliant on an NP-hard problem isn't nearly as important as being reliant on a problem that is hard *for a random instance*. I

Re:Practical? by Artem+S.+Tashkinov · 2017-02-23 06:16 · Score: 2

If Google can do that, NSA can surely do that - maybe not right now but quite soon.

Also don't underestimate various botnets - right now they are mostly used for spamming/DDOS'ing/crypto currency mining (which in itself is ... hashing) but they can be used for finding collisions in SHA-1 as well.

Also don't forget that "practical" in this case means that an attack can be carried out using currently existing availble computational resources, vs. something purely theoretical which requires billions of CPUs/GPUs or quantum computers.

Re:Practical? by Anonymous Coward · 2017-02-23 06:22 · Score: 1

Yeah, um...except for a 3 letter agency with a 10 or 11 figure budget or a Google no one has the money to devote this much CPU time to one attack. SHA-1 is still fine unless your worried about 3 letter agencies in which case you probably have bigger problems than just encryption -- problems like drones with missiles attached.

Are two hashes better than one? by Anon+E.+Muss · 2017-02-23 06:27 · Score: 4, Interesting

... however it's worth noting that there are currently no ways of finding a collision for both MD5 and SHA-1 hashes simultaneously

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.

Re:Are two hashes better than one? by Artem+S.+Tashkinov · 2017-02-23 06:52 · Score: 1

Perhaps I was completely wrong - skip to the Mysid's comment. My sincere apologies then. But this explanation just doesn't work/compute in my head - even today finding MD5 collisions is extremely computationally expensive, yet the person says SHA1 + MD5 is only slightly more computationally expensive.
Let's put it in layman's terms: let's say your cluster made of a thousand GPUs finds MD5 collisions for given data every second. Now finding an SHA1 collision in Google's case required 9,223,372,036,854,775,808 computations based either on purely random data or data which needed to be fed to the SHA1 algorithm in succession both of which you cannot get using your already found MD5 collisions, because they are not random. I cannot see how your non random MD5 data could be used as a basis for cracking SHA-1 simultaneously. Again, maybe I'm totally wrong about that.
I'd also love to hear someone with a good cryptography background rather than believe a random person on the net or my amateurish logic.
Re:Are two hashes better than one? by WhiteKnight07 · 2017-02-23 07:11 · Score: 2

Taking the MD5 and the SHA1 of something isn't significantly more secure than just taking the SHA1 of said something. This was demonstrated in 2004 here: http://link.springer.com/chapt... This was then further elaborated and improved upon here: http://eprint.iacr.org/2008/07... So, don't concatenate hashes kids. It doesn't do what you think it does. Using a proper hash from the start is the only safe way to do things. Even if nobody has figured out how to do it yet the math conclusively shows that breaking SHA1+MD5 is not significantly harder than just breaking SHA1. This is why TLS 1.1 and earlier need to go away.

--

We're going to make information free Mr. Anderson, whether you like it, or not.
Re:Are two hashes better than one? by namgge · 2017-02-23 07:39 · Score: 3, Informative

I think the idea was that one finds an MD5 collision for document A by adding a block of data B to the end of it creating a new documents C. The SHA hash of document C, SHA(C) will not, in general, match SHA(A).
FInding B such that both MD5(C)==MD5(A) and SHA(C) ==SAH(A) is still unfeasible.
Re:Are two hashes better than one? by skids · 2017-02-23 07:48 · Score: 1

It really doesn't matter for the most important use case, because X.509 does not have a way to use more than one hash in a certificate.
And there's a patent for that (US7793097, US20080270788), so unless the owners decide to be benevolent, there's a roadblock to actually implementing it.

--
Someone had to do it.
Re:Are two hashes better than one? by tlhIngan · 2017-02-23 08:54 · Score: 1

Taking the MD5 and the SHA1 of something isn't significantly more secure than just taking the SHA1 of said something. This was demonstrated in 2004 here: http://link.springer.com/chapt... This was then further elaborated and improved upon here: http://eprint.iacr.org/2008/07... So, don't concatenate hashes kids. It doesn't do what you think it does. Using a proper hash from the start is the only safe way to do things. Even if nobody has figured out how to do it yet the math conclusively shows that breaking SHA1+MD5 is not significantly harder than just breaking SHA1. This is why TLS 1.1 and earlier need to go away.
That's for concatenated hashes. As in, you hash the two hashes to form one number, usually by XOR'ing the numbers together. Which can be shown to increase the solution space considerably.
What I've been curious about, is if you maintain two hashes separately.
You have blob X here, with SHA-1 of S(X) and MD5 M(X). Can you find a blob Y with both a SHA-1 of S(X) and MD5 of M(X)?
It's easy to see if you XOR S(X) and M(X) you make it much easier - but what if we kept them separate, so the SHA-1 AND MD5 has to match. (With concatenation, you don't have to match, the final result has to match, but individually inside you have to find a S(Y)+M(Y) that equals S(X)+M(X), and not S(Y)==S(X) AND M(Y)==M(X).
The only concatenation that wouldn't be easier is if you literally concatenated the bytes together - so 128 bits of MD5 followed by 160 bits of SHA-1 to form a 288 bit MD5/SHA-1 hash that enforces the property that the two hashes individually MUST match simultaneously.
Re:Are two hashes better than one? by kiwix · 2017-02-23 09:31 · Score: 1

Finding collisions in MD5 and SHA-1 simultaneously is only marginally harder. Using Joux's multicollisions, you can finding a collision in both by running the SHA-1 attack 64 times: this defines 2^64 messages colliding for SHA-1, and you can locate a collision by evaluating all those hashes (wich costs less than finding the SHA-1 collisions with the current attack).
Re:Are two hashes better than one? by swillden · 2017-02-23 11:45 · Score: 1

... however it's worth noting that there are currently no ways of finding a collision for both MD5 and SHA-1 hashes simultaneously
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?
MD5 + SHA1 is a "new hash algorithm". Think about what you have to do to shift to a new algorithm... all of the message formats that have to be updated, all of the stored values that have to be recomputed, all of the cross-system compatibility dances you have to do to ensure that you can upgrade both sides (or all sides; there are often more than two) in order to update without having to make some error-prone attempt to cut over simultaneously.
The challenge of changing hash algorithms has nothing to do with getting correctly-implemented source code for a new algorithm. That's super easy. The challenges are all about how to handle the changeover, which is exactly the same whether you're switching to an actual new algorithm that incorporates the latest ideas and is (currently) completely invulnerable to all known attacks, or to a combination of old, broken algorithms that may or may not be better than either one alone.
The right solution is to build systems with algorithm agility and algorithm negotiation, then to add new algorithms as soon as they're standardized and remove algorithms completely once all parties have updated.

--
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Re:Are two hashes better than one? by AHuxley · 2017-02-23 14:13 · Score: 1

Argentina tried a few ideas like that in the 1980's knowing the skills the UK's GCHQ had https://en.wikipedia.org/wiki/.... Argentina needed a lot of fast, real time communications using equipment that was in place.
The GCHQ has most of the worlds mil grade export crypto decryption computer ready thanks to most brands and firms been happy to help the UK gov. Real time decryption was easy and any efforts to link two layers of junk export grade crypto was detected and useless.
The only aspect that slowed the GCHQ down was that Argentina had some South Africa crypto devices that the GCHQ did not know a lot about. That took an unexpected 24h to break given early 1980s' UK computers facing a new mil crypto task.
All communications was then plaint text in real time.
Other nations then equip their mil with that junk and think they have the best the private sector has to offer :)
So that is not really what your asking about, but shows how governments attack crypto. Govs go to the origins of "export" "brands" that sell mil grade crypto and get the keys. Consumer crypto efforts get the same police or international telco requests for keys. Most govs just ask the designers within their nations to help.
That consumer grade, police friendly product is then a tested, trusted global crypto standard.
Almost all crypto for sale was junk.
South Africa during the 1980's was one of the few nations to have working crypto that was not shared with the US, UK, Soviet Union as designed.

--
Domestic spying is now "Benign Information Gathering"
Re:Are two hashes better than one? by manu0601 · 2017-02-23 14:44 · Score: 1

That's for concatenated hashes. As in, you hash the two hashes to form one number, usually by XOR'ing the numbers together. Which can be shown to increase the solution space considerably.
But that reduced the difficulty of breaking SHA1, since you now just need a collision for the length of a shorter MD5 hash.

Re:Practical? by Guspaz · 2017-02-23 06:44 · Score: 4, Insightful

Well, what exactly a time unit of CPU computation means isn't defined (it's like saying "This item cost me 500 monetary units", there's no context), but if we just take it to mean a literal amount of time on any random CPU...

6,500 years of CPU time potentially costs as little as ~$171k USD at Amazon, and compute costs are continuously falling.

Practical by avandesande · 2017-02-23 07:02 · Score: 1

Apollo program demonstrated practical transportation to the moon.

--
love is just extroverted narcissism

Re:Practical? by DickBreath · 2017-02-23 07:04 · Score: 1

SHA-1 collisions don't have to be practical. Just possible. It may take a huge amount of compute power and electrical power. But in principle is simple.

Accelerate SHA-1 hashes to nearly the speed of light and then collide them. Capture all of the bits that come flying out to understand what is inside.

--

I'll see your senator, and I'll raise you two judges.

Re:PDF is a major malware vector by Artem+S.+Tashkinov · 2017-02-23 07:10 · Score: 1

True! As for me I usually run downloaded PDFs though virustotal.com and then all scripting features in my Acrobat Reader are completely disabled.

Speaking of ISO's: most Ubuntu mirrors (and their official servers as well) distribute Ubuntu ISO's via ... HTTP and FTP. That's so "lovely" considering that any ISP can easily replace your HTTP traffic. Yes, they have PGP signatures but 99% of people out there have no idea how to verify them. And those PGP signatures are distributed from the same ... insecure channels.

Re:Practical? by hawguy · 2017-02-23 07:12 · Score: 1

Well, what exactly a time unit of CPU computation means isn't defined (it's like saying "This item cost me 500 monetary units", there's no context), but if we just take it to mean a literal amount of time on any random CPU...

6,500 years of CPU time potentially costs as little as ~$171k USD at Amazon, and compute costs are continuously falling.

how did you come up with that price?

Spot pricing on a 36CPU c4.8xl is currently $0.46/hour.

6500 years in hours / 36 * $0.46/hour is $728K

Spot pricing may go lower from time to time, but on-demand pricing for the c4.8xl is $1.80hour, so $0.46 is already a significant discount. The upcoming c5 series should help with pricing.

SHA-1 has only been around for 10 years? by nitro322 · 2017-02-23 07:16 · Score: 1

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?

Re:SHA-1 has only been around for 10 years? by viperidaenz · 2017-02-23 07:54 · Score: 1

It's been about 10 years since theoretical attacks against SHA-1 have been presented

Re:For variable values of "practical" and "relevan by EndlessNameless · 2017-02-23 07:24 · Score: 3, Informative

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.

Re:Practical? by Bob+the+Super+Hamste · 2017-02-23 07:24 · Score: 1

Sounds very practical to me. The fact that this is in the realm of being done by a wealthy individual should indicate why. Lets say you are a wealthy criminal gang go out and get your self a bunch of beefy servers and fill them with GPUs. You now can defraud banks and others at a massive scale and probably make the money back in short order. 6500 CPUs and 110 GPUs isn't all that expensive. You could probably get that for $10,000,000-$20,000,000 and next year it will cost even less to get that computational power. The fact that we aren't talking about time or energy requirements that are on the order of lifetimes of stars or the mass energy of a star should tell you that it broken. Also attacks only get better with time. It only took 4 years to go from theoretical to actual.

--
Time to offend someone

Re:Practical? by Anubis+IV · 2017-02-23 07:27 · Score: 2

A 10 million strong botnet would need +/- 3 years per key under ideal circumstances here.

Aren't you off by a few orders of magnitude there? 6,500 years of computation time divided by 10,000,000 bots would be about 5 hours and 42 minutes, not 3 years.

Even your hypothetical 10,000-strong botnet could do it in about 8 months, which might be well worth it if it meant being able to hijack a cert that could be leveraged in interesting ways (e.g. using it to sign your malware as an official update for the company).

Re:Practical? by Anonymous Coward · 2017-02-23 07:30 · Score: 1

You vastly over-inflate how much it would cost to simply rent some hacker group's botnet.

Re:Practical? by WhiteKnight07 · 2017-02-23 07:33 · Score: 1

The fact that we aren't talking about time or energy requirements that are on the order of lifetimes of stars or the mass energy of a star should tell you that it broken.

This is probably the best layman explanation of cryptographic security I have ever seen. If the numbers involved in breaking something crypto related can be expressed in easily understandable terms without doing something like this: https://what-if.xkcd.com/96/

Then the crypto thing you are talking about is broken and shouldn't be used.

--

We're going to make information free Mr. Anderson, whether you like it, or not.

What about signed code? by rastos1 · 2017-02-23 07:33 · Score: 2

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?

Re:What about signed code? by viperidaenz · 2017-02-23 07:56 · Score: 3, Informative

Perhaps you could have just read the documentation?

Supported Algorithms
By default, the jarsigner command signs a JAR file using one of the following algorithms:
Digital Signature Algorithm (DSA) with the SHA1 digest algorithm
RSA algorithm with the SHA256 digest algorithm
Elliptic Curve (EC) cryptography algorithm with the SHA256 with Elliptic Curve Digital Signature Algorithm (ECDSA).
If the signer's public and private keys are DSA keys, then jarsigner signs the JAR file with the SHA1withDSA algorithm. If the signer's keys are RSA keys, then jarsigner attempts to sign the JAR file with the SHA256withRSA algorithm. If the signer's keys are EC keys, then jarsigner signs the JAR file with the SHA256withECDSA algorithm.
These default signature algorithms can be overridden using the -sigalg option
http://docs.oracle.com/javase/7/docs/technotes/tools/windows/jarsigner.html

Re:Practical? by viperidaenz · 2017-02-23 07:38 · Score: 1

How long is 6500 years CPU time in China's top supercomputer? 6 hours over 10 million cores.

Crafted data by OneHundredAndTen · 2017-02-23 07:39 · Score: 4, Informative

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.

Re:Crafted data by PvtVoid · 2017-02-23 08:04 · Score: 1

What they did is called a chosen plaintext attack, and is still damning.

Re:Practical? by ShanghaiBill · 2017-02-23 07:45 · Score: 1

If you were actually going to do this, you would NOT use a CPU. A data-lite computation-intensive task like this is ideal for FPGAs, where it could be massively parallelized. If you needed to run multiple MITM attacks, then you could fab some ASICs and cut the hash/joule cost much more. There is likely some NSA datacenter in Utah doing this right now.

Re:Practical? by Leroy+Brown · 2017-02-23 07:49 · Score: 1

How do you figure?

"This attack required over 9,223,372,036,854,775,808 SHA1 computations. This took the equivalent processing power as 6,500 years of single-CPU computations and 110 years of single-GPU computations."

That works out to about 45mil computations/sec for CPU or 2.65 bil computations/sec for GPU.

To get it done in 30 days would take a 79,000 machine CPU botnet, or a 1,342 machine GPU botnet.

Fudge the numbers a bit as they probably won't be running full-tilt for 30 days straight, and they won't all have CPU/GPU as spec'd in the attack (paper protoyped on Nvidia GTX 970 btw). Still, we're nowhere remotely close to 10mil machine botnet taking 3 years.

Cached copy of the counter-cryptanalysis paper by Anonymous Coward · 2017-02-23 07:53 · Score: 1

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... :-)

Re:Practical? by Bob+the+Super+Hamste · 2017-02-23 07:53 · Score: 5, Informative

Ever since I read this blurb from Applied Cryptography by Bruce Schneier years ago it has really put things into perspective when it comes to what is strong crypto and what isn't. I got the concept from him so it isn't my own idea even if I did simplify the explanation of it.:

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that k = 1.38×10^-16 erg/Kelvin, and that the ambient temperature of the universe is 3.2 Kelvin, an ideal computer running at 3.2K would consume 4.4×10^-16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

Now, the annual energy output of our sun is about 1.21×10^41 ergs. This is enough to power about 2.7×10^56 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2^192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

But that's just one star, and a measly one at that. A typical supernova releases something like 10^51 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

I want crypto that has a good chance of outlasting the heat death of the universe even with a quantum computer. For symmetric key crypto this means you would need somewhere around a 601 bit keyspace IIRC before you exceed the mass energy of the universe.

--
Time to offend someone

Re:For variable values of "practical" and "relevan by gweihir · 2017-02-23 07:53 · Score: 1

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.

Re:For variable values of "practical" and "relevan by Anonymous Coward · 2017-02-23 08:04 · Score: 1

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.

Re:Practical? by lgw · 2017-02-23 08:15 · Score: 1

Yeah, um...except for a 3 letter agency with a 10 or 11 figure budget or a Google no one has the money to devote this much CPU time to one attack. SHA-1 is still fine unless your worried about 3 letter agencies in which case you probably have bigger problems than just encryption -- problems like drones with missiles attached.

I can easily throw 1 million cores at a problem. That's 2.5 days to get an answer. My company would be pissed at me for wasting the resources, and would fire me, but I could do it. There are lots of people like me in the world.

Fun fact: a core-year on EC2 Spot generally costs less than $100. No clue how many cores you could get in parallel, but lots of organizations could throw $500k in IT spending at a problem, they just need to achieve something worth more than that by doing so.

I bet doing the same with an ASIC solution would be surprisingly cost effective if you had a lot of digital signatures to forge.

--
Socialism: a lie told by totalitarians and believed by fools.

At least they don't use it by fred6666 · 2017-02-23 08:37 · Score: 1

The web site where it is published use SHA-256

Re:Practical? by hawguy · 2017-02-23 08:40 · Score: 1

If you were actually going to do this, you would NOT use a CPU. A data-lite computation-intensive task like this is ideal for FPGAs, where it could be massively parallelized. If you needed to run multiple MITM attacks, then you could fab some ASICs and cut the hash/joule cost much more. There is likely some NSA datacenter in Utah doing this right now.

But Google actually did it and they say they used CPU's.

if you happen to have thousands of CPU's laying around that aren't always busy, using CPU's is apparently feasible.

Re:For variable values of "practical" and "relevan by BlackPignouf · 2017-02-23 08:47 · Score: 1

Would it be possible to tamper a famous git repo (e.g. Linux) by writing a malicious commit with the same hash?

Re:For variable values of "practical" and "relevan by thegarbz · 2017-02-23 08:54 · Score: 1

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.

Re: Practical? by jovius · 2017-02-23 08:59 · Score: 1

How? Perhaps the parent poster has government discount price in.. Busted!

Re:Practical? by Guspaz · 2017-02-23 09:10 · Score: 1

Assuming Amazon has sufficient capacity, it could be completed in an arbitrarily short amount of time by spinning up enough instances. Amazon bills by aggregate time, so the cost of one node for two days is the same as the cost of two nodes for one day.

My point was more to show that it's potentially achievable without Google or NSA sized budgets, and that the cost would only shrink from there over time.

Re:Practical? by Guspaz · 2017-02-23 09:20 · Score: 1

The cheapest EC2 node has one CPU at a reserve pricing as low as $0.003 for a t2.nano instance. The exact math I used is:

(6500 * 365 * 24) * 0.003 = $170,820

I realize that a nano instances don't really have much CPU power available (they're intended to be used for bursty tasks), but Google didn't define what a "CPU hour" was, so neither did I.

Re:Practical? by harperska · 2017-02-23 09:27 · Score: 2

I know you are trying to be funny, but you are inadvertently correct. Everyone here seems to be assuming they are using the definition which is the opposite of 'impractical', when they are actually using the definition meaning 'not just theoretical'.

Re:For variable values of "practical" and "relevan by swillden · 2017-02-23 09:30 · Score: 2

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.

Re:Practical? by Kjella · 2017-02-23 09:36 · Score: 1

I want crypto that has a good chance of outlasting the heat death of the universe

Why, are you Doctor Who and got the key to unraveling space and time or something? And even if someone should bother, do you really care if crypto-archaeologists find your tin foil hat conspiracies or pr0n collection (I was considering saying love letters and gf sex video, but it's /.) many thousand years from now when you and everyone who ever knew you is countless generations dead? I do care about 20 or 50 years from now but unless we make significant progress towards immortality in that time, I hardly care what happens after I become worm food.

--
Live today, because you never know what tomorrow brings

Re:Practical? by JoshuaZ · 2017-02-23 10:06 · Score: 1

There's one context in which their concern isn't unreasonable: the default assumption is that if any crypto system (key exchange, public key encryption, hashing system, etc.) becomes common then people are going to think about it pretty hard. That's going to lead to a lot of insight in how to do better than brute force. The classic example of this is RSA where RSA-129 was estimated by Rivest that it would take on the order of quadrillions of years to factor even assuming the same improvement rate in computational power. But now RSA-129 is factorable in a few hours with a standard implementation of the number field sieve. This isn't as much about improvement in hardware as it is in improvement in algorithms (modern sieves were inspired in a large part due to RSA). So if you aim for your key to be large enough that any brute force method will be physically impossible, you can be more confident that even with algorithmic improvements, cracking will still take very long.

The real problem with their idea is that given current hardware, demanding long keys is computationally intensive for all involved (and as you pointed out for the vast majority of these what they want to hide just isn't worth that).

Economic cost was? by evil9000 · 2017-02-23 11:07 · Score: 1

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.

Re:For variable values of "practical" and "relevan by gweihir · 2017-02-23 11:31 · Score: 1

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.

Re:For variable values of "practical" and "relevan by gweihir · 2017-02-23 11:34 · Score: 1

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.

Random data storage required. by Thanatiel · 2017-02-23 12:47 · Score: 1

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.

Re:Practical? by Anonymous Coward · 2017-02-23 13:06 · Score: 1

Sunway TaihuLight

The Sunway TaihuLight uses a total of 40,960 Chinese-designed SW26010 manycore 64-bit RISC processors based on the Sunway architecture.[5] Each processor chip contains 256 processing cores, and an additional four auxiliary cores for system management (also RISC cores, just more fully featured) for a total of 10,649,600 CPU cores across the entire system.[5]

Re:Practical? by hawguy · 2017-02-23 13:11 · Score: 1

The cheapest EC2 node has one CPU at a reserve pricing as low as $0.003 for a t2.nano instance. The exact math I used is:

(6500 * 365 * 24) * 0.003 = $170,820

I realize that a nano instances don't really have much CPU power available (they're intended to be used for bursty tasks), but Google didn't define what a "CPU hour" was, so neither did I.

Like you said, t2's aren't meant for sustained CPU use. You only get 30 minutes of full CPU use after launch, and they further limit how many t2's you can launch with the full initial CPU credit (100 per day) - so you can't just keep launching new hosts to reset the CPU balance and run out the balance for 30 minutes then relaunch. After you use up the initial credit balance, they throttle the CPU to 5% and each hour they give you another 3 credits (which will let you run at 100% cpu for 3 minutes). They've been very careful with pricing and launch limits to prevent them from being used as a cheap CPU compute farm.

Maybe Google didn't define what a "CPU hour" was, but they surely didn't mean "5% of a typical server CPU".

To get the $.003 pricing, you need to purchase a 3-year reserved instance for $69, so assuming you want to get the job done in a year, you need to purchase 6500 instances for $448,500, if you could use the full CPU. But you can't, so you'd really need almost 20 times that number.

t2's are great if you have a low CPU use case, but once your application exceeds the CPU credit balance, performance gets terrible very quickly (even getting an SSH session open can take 30 seconds on a throttled t2.nano instance), so you need good monitoring and the ability to re-launch instances if you're going to use them for anything significant.

Re:Practical? by AHuxley · 2017-02-23 13:38 · Score: 1

Thats why so many nations allow things like VPN. The home router been used for all networking that can hide everything? No calls for VPN bans or to stop CC payments for all consumer VPN services?
Governments might have found another easy way in and all a VPN service cert will do is make a gov tracking easy.
Use a VPN, the users must be interesting, crypto funding and gov computer time was not an issue.

--
Domestic spying is now "Benign Information Gathering"

TLS 1.1 by manu0601 · 2017-02-23 14:50 · Score: 1

Since SHA-2 ciphers where introduced in TLS 1.2, that suggest we should remove TLS 1.0 and TLS 1.1. suppoort soon.

Re:For variable values of "practical" and "relevan by Altrag · 2017-02-23 18:32 · Score: 1

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.

Re:For variable values of "practical" and "relevan by subreality · 2017-02-23 19:59 · Score: 2

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.

Re:Practical? by rastos1 · 2017-02-23 22:16 · Score: 1

Nice explanation. However you are describing a scenario where you have 256- bit key and you have to loop through all possible keys and try to decrypt the ciphertext with it - brute force attack. Yes, in such scenario 256-bits is plenty good enough.

There are other attacks that you do not cover. Such as the key was not selected in random or there is non-brute force attack. Or symmetric cryptography is not sufficient in the given scenario and you need to use public key cryptography where the key has different properties ...

Re:Practical? by brantondaveperson · 2017-02-23 22:53 · Score: 1

Very true, and there's a potentially very serious downside here too. Encryption that's physically impossible to break is equivalent to a safe that physically impregnable against all attacks. Given the regularity with which I lose my keys, I'm not sure that we should put anything important in there, because losing the keys is game over.

Re:Practical? by TeknoHog · 2017-02-24 00:48 · Score: 1

The bit change is not necessary for computation at all from information theory perspective. Theoretically, no energy needed at all for any computation. Whatever, you can do with active circuit, can be done using passive circuit (e.g. your camera lens can be used for FFT). The energy is only needed for reading information. So no matter, how complex the cryptography is, the theoretical energy required to decrypt is zero.

Yes and no. In my understanding as a physicist, bit flipping per se is free, but you need a minimum of 1/2 kT of energy to destroy information (create entropy). To avoid destroying information during computation, you basically need to store every step you do, so the operation becomes reversible (google "reversible computing" for more). This is not usually practical, so most of computing does suffer from the 1/2 kT limit per bit operation.

The lens example is valid IMHO, as Fourier transform is reversible (and there are similar integer transforms to stay bit-exact, if you're worried about floats.) But to make that practical, you need to store all that information somewhere.

--
Escher was the first MC and Giger invented the HR department.

Re:Practical? by Bob+the+Super+Hamste · 2017-02-24 02:48 · Score: 1

The reason I want crypto that has a chance of surviving the heat death of the universe is simple. Unless you are using a One Time Pad the encryption you haven't isn't provably secure for all time. It will be attacked and the strength of it will decrease. Is my data so important that it personally needs to be kept secure until the heat death of the universe? Simple answer is no, but at the same time it is something that I would like to see stay secure for the next 50-60 years until I'm taking a dirt nap.

So now lets look at AES-256. Here we are dealing with a cipher that is in that mass energy of a star to brute force on an ideal classical computer. Now that may seem pretty damn strong, but there is a related key attack against it that brings that complexity down to 2^99.5 from 2^256. At this point we are no longer talking about star sized energy requirements but instead a sizeable portion of the total annual energy output of a a nation on an ideal classical computer. While currently infeasible further advances in cryptanalysis and quantum computing will decrease this further. So using something like Grover's algorithm we could possibly get the work down to about 2^50. At that level we have already rejected crypto standards because they are easy to defeat.

--
Time to offend someone

Re:Practical? by Bob+the+Super+Hamste · 2017-02-24 02:56 · Score: 1

If losing encryption keys is going to be a problem for with crypto that strong then it is already a problem for you as you neither have an ideal classical computer operating near the limit of Landauer's Principal nor do you have the ability to consume a large fraction of the US's total annual energy consumption. The problem is with encryption is that if it is feasable for a state actor to crack it, then it is also possiable for a large criminal gang to do so in a few years, and a few years later you can do so with a device that runs on a battery that you carry in your pocket, see the image in the original article where they point out that generating MD5 hash collisions can be done on your smart phone in about 30 seconds.

--
Time to offend someone

Re:Practical? by Bob+the+Super+Hamste · 2017-02-24 03:06 · Score: 1

I fully understand that but using the brute force attack does provide a good metric by how to judge things and yes I know that in my previous statement I didn't cover more detailed attacks as no one would like to read that wall of text. In response to another user above I look a little more closely at AES-256 taking into account using a quantum computer and the best attack against it. In that case we move from stellar mass energy requirements down to something that would become fairly trivial with a complexity of about 2^50.

--
Time to offend someone

Re:For variable values of "practical" and "relevan by swillden · 2017-02-24 07:50 · Score: 1

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.

Re:For variable values of "practical" and "relevan by thegarbz · 2017-02-24 08:07 · Score: 1

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.

Re:Practical? by lewis2 · 2017-02-24 10:14 · Score: 2

You can do it cheaper by using botnets rather than legitimate resources.

Re:For variable values of "practical" and "relevan by gweihir · 2017-02-25 02:07 · Score: 1

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.

Re:Practical? by Baloroth · 2017-02-25 12:09 · Score: 1

CPU time is perfectly well defined, though only really meaningful in terms of absolute value if you also give the relevant CPU you're talking about (obviously, 1 hour on a 386 and 1 hour on a modern Xeon are orders of magnitude difference levels of computation). Incidentally, they don't give the CPU used for the attack, as due to the fact they used cloud infrastructure the CPU time was spread over many different kinds of CPUs, but their "average CPU" unit reference is a 2.3Ghz Xeon E5-2650v3 (and for GPUs, they again used a spread of kinds, but they give the number of 114 years of device time for a cluster of K20s).

--
"None can love freedom heartily, but good men; the rest love not freedom, but license." --John Milton

Re:Practical? by syntotic · 2017-02-26 11:24 · Score: 1

Like a lot of gmail users in IExplorer browsers asking themselves why without connection and minimized browser their CPU is still working at 46%, mainly by the browser pulling it?

Re:Practical? by Bob+the+Super+Hamste · 2017-02-27 03:38 · Score: 1

They don't halve the time they halve the number of bits for symmetric key encryption, to put it another way the do it in square root time. So 128 bit encryption on classical computers is equivalent to 256 bit encryption on quantum computers. For asymmetric encryption take makes uses of elliptical curves or prime factorization it completely breaks them. The 2^50 is because the best break for AES-256 is a related key attack that has 2^99.5 complexity on classical computers. Assuming that this decreased key space can processed using Grover's Algorithm that give a complexity of about 2^50 on a quantum computer.

--
Time to offend someone

Re:Practical? by Bob+the+Super+Hamste · 2017-02-27 03:56 · Score: 1

The simple act of counting that high on an ideal classical CPU would probably kill all surface life on Earth.

Nope. The energy requirement while substantial is not insurmountable. I believe that the amount of energy to cycle a 128 bit counter through all states on an ideal classical computer is around 10% of the total annual US energy consumption. This assumes an ideal machine which happens to be many orders of magnitude more efficient than even our best computers so using conventional technology it would be ocean boiling energy consumption.

--
Time to offend someone

Slashdot Mirror

Google Has Demonstrated a Successful Practical Attack Against SHA-1 (googleblog.com)

84 of 143 comments (clear)