Let's talk about that NSA Diffie-Hellman crack

Even before the leaks by former NSA sysadmin Edward Snowden, rumours had circulated for years that the agency could decrypt a significant fraction of encrypted internet traffic. Now security researchers, who published a paper on their theory in May, have come forward with a detailed and credible theory on the technical …

[Destroy All Monsters]

Three years ago, James Bamford published an article quoting anonymous former NSA officials stating that the agency had achieved a “computing breakthrough” that gave them “the ability to crack current public encryption.”

That was the article in WiRED, right? I thought he had gone off the deep end...

[streaky]

Well, if the observations are accurate - he has. It's not that they can just break any crypto they feel like (unreasonable) it's that implementations are screwy and that leads to an open door on a one-time investment (completely reasonable).

If

Course if they can do it Russia, China and who knows who else can do it so why the NSA/NIST et al don't do their job and alert people is a whole different question.

[Trollslayer]

Don't worry, power will not be abused

Said McCarthy.

[chivo243]

Re: Don't worry, power will not be abused

Charlie? Or that guy Joe?

[g e]

Re: Don't worry, power will not be abused

Jenny, surely :oP

[Anonymous Coward]

The good news is...

...that the NSA has been able to decrypt criminal conversations. That is a very good result for society.

[ZSn]

Re: The good news is...

Then why, pray tell, are you an anonymous coward? Anything to hide?

[asdf]

Re: The good news is...

>..that the NSA has been able to decrypt criminal conversations.

Criminal is always so black and white huh and would never change based on what party and administration is in power huh (you know like the definition of torture)?

[Anonymous Coward]

Re: The good news is...

That is a very good result for society

Not if that ability basically treats everyone as a criminal (which it does in the good old US of A). Once upon a time you had such a thing as the 4th amendment, but it appears you signed that away after a couple of people scared you.

Enjoy your panopticon. You built that all by yourself.

[Malcolm Weir]

Re: The good news is...

... but the bad news is that they can't use the decrypts in criminal prosecutions because they don't want you to know they can decrypt criminal conversations...

[g e]

Re: The good news is...

It's the NSA, not the LAPD...

[Michael Wojcik]

Re: The good news is...

the NSA has been able to decrypt criminal conversations

Some conversations among some criminals, yes. How many? What sort of "criminals"? Was due process followed?

That is a very good result for society.

How so? What good was achieved? What was its magnitude - how many crimes committed, of what sort? What potential wrong was prevented? How are we supposed to assess any of these things with any degree of confidence?

And the big one: How does this supposed good weigh against the great wrong of trampling on civil rights, which are the only thing that makes society worth having in the first place?

[Anonymous Coward]

I am still having a hard time believing there are that few prime numbers being reused, some of the numbers in the article imply a max of five or less. At best that is a know flaw, in any case would be totally inadequate for long term use.

[Michael Wojcik]

It's happening, regardless of whether you believe it. A great many DH implementations just used the SKIP DH parameters, because they were widely known to be "good" (of the proper form, verified, etc), and because generating your own parameters required 1) some extra work, 2) understanding why you'd want to do that, and 3) a degree of confidence that you weren't screwing things up.

The SKIP parameters have been the default for OpenSSL, for example, for many years. It's not hard to supply your own - you can use "openssl dhparam" to generate your own set and then just hard-code them in an OpenSSL DH parameter callback function, which avoids this "popular prime" attack - but those three points above discouraged most OpenSSL users from doing so.

Most people implementing something that uses DH are actually implementing SSL/TLS or SSH or something along those lines. They don't really understand the threat model for DH. Their concern is to Get It Working, and that's a hard enough problem with cryptographic protocols. Worrying about "tuning" their underlying crypto algorithms is going to be way down on the list. So generating DH parameters becomes a bit of technical debt and then forgotten.

[Palpy]

Yes, and the double-plus good news --

-- is that in order to determine who is engaging in crime-think, the NSA will decrypt all possible conversations. You have nothing to fear, citizen, unless you betray ideas disloyal to the regime.

[Anonymous Coward]

Re: Yes, and the double-plus good news --

"...the NSA will decrypt all possible conversations."

...the NSA is decrypting all possible conversations and hoarding them away in hollowed out mountains.

T,FTFY

[Anonymous Coward]

Hard coded primes?

Can anyone that understands this better elaborate? That seems like a monumentally stupid thing to do that was just asking for trouble! Was including a list of a few thousand 1024 bit primes to choose from now (maybe refreshed occasionally off the internet or via the regular software patches) deemed too wasteful of memory in a world where we have gigabytes of RAM even on a smartphone?

I can't believe that we'd leave such an obvious vulnerability in place. If we have, what other colossally stupid fails are present in encryption software?

If this is true, whatever belief I had that people working in encryption are at least smart and overly cautious so I should trust them is gone. They are clearly morons of the first degree if something like this has been present for years and years and this is apparently the first myself and a lot of others are hearing about it!

[Warm Braw]

Re: Hard coded primes?

To quote Mr. Schneier:

Millions of HTTPS, SSH, and VPN servers all use the same prime numbers for Diffie-Hellman key exchange. Practitioners believed this was safe as long as new key exchange messages were generated for every connection. However, the first step in the number field sieve -- the most efficient algorithm for breaking a Diffie-Hellman connection -- is dependent only on this prime. After this first step, an attacker can quickly break individual connections.

The reason they felt it was safe was that they didn't believe it was computationally feasible to do what has been done. The reason that "canned" prime numbers are used is that it can take some considerable time to compute a "safe" prime for use with the algorithm and both sides of the connection have to agree on the same number.

However, now it's known the lengths to which the NSA is prepared to go, then simply changing the numbers periodically (and possibly increasing their size) would indeed defeat the NSA's considerable apparent investment. For now.

[DropBear]

Re: Hard coded primes?

"The reason they felt it was safe was that they didn't believe it was computationally feasible to do what has been done."

...or, to put it differently, they thought security with a single point of failure was worthy of being called security. Proper job, gents!

[Warm Braw]

Re: Hard coded primes?

> they thought security with a single point of failure was worthy of being called security

I'm afraid you're expectations are unachievable.

As far as I'm aware, all cryptographic systems presently deployed (with the exception of one-time pads) depend on certain mathematical operations being difficult to perform and assume some level of economic sanity on the part of the attacker in their willingness to invest in breaking the codes. There is no proof that there isn't a shortcut and there is no real defence against an attacker willing to pay unbounded sums of money to gain access to communications of comparatively little real value.

If you find that unacceptable, I suggest you come up with a better scheme.

[Frumious Bandersnatch]

Re: Hard coded primes?

I can't believe that we'd leave such an obvious vulnerability

The thing is, it wasn't obvious. Lots of talented people have looked at the algorithm since it was first published and it was believed that the choice of prime didn't adversely impact the security of the algorithm in a way that was practical enough to exploit. Kind of like how HMAC constructions are believed to be secure even with slightly dodgy/insecure hash functions as the building block.

This is a good result. It doesn't mean that the DH key exchange protocol is fundamentally broken, I think. It will definitely need some tweaks to eliminate this vulnerability completely, and in the meanwhile I expect that we'll see a flurry of papers with people proposing different approaches to mitigating the weakness in short order.

It's also great to know what the "bad guys" (the guys with the most CPU power and storage space) are up to, since up until this point we didn't really know how they might be approaching the problem.

You may still feel that it's wrong that the vulnerability was there in the first place, but maths and cryptography is an uncertain business. Things take time to crack, then we understand why, and only then can we try to fix those faults. Nothing can ever be guaranteed to be completely secure and future-proof (except maybe quantum crypto). We just have to use the best tools available to us at any given time and balance it against the risk of future (or unknown present) attacks.

[Anonymous Coward]

No, it WAS obvious

The idea that "lots of talented people ... believed that the choice of prime didn't advertise impact the security of the algorithm" is what makes me think they're not worthy of my trust.

They're just assuming "even though we know this is a potential weakness, we think it is safe to ignore because we can't foresee a practical attack to take advantage of it" which is mind numbingly STUPID of them! Security isn't about taking shortcuts where you think it won't be a problem.

The fact that they feel the fix to this is rather trivial means they totally dropped the ball by not doing this trivial fix from day one. How many other avenues of exploit could they fix today but have chosen not to because they believe an attack that takes advantage of it is impractical? They should fix all of them! The "wasted" effort is small if they were right and an attack never was practical but the potential cost is huge when they're wrong.

[Francis Vaughan]

Re: No, it WAS obvious

No, what was obvious is that eventually enough compute power would break it. That was explicitly understood. Everyone knew that.

What the problem is, is that it isn't a trivial fix. You can be sure that a lot of the "fixes" will be more likely to introduce new vulnerabilities, ones that may even weaken the system to be easier to break than now. Unless you understand the protocol in detail, don't assume you know how to fix this issue.

Don't assume the flaw is laziness. It is more likely to be a clear decision to favour simplicity over complexity, complexity that in itself leads to hard to understand and difficult to control new weaknesses. Better the devil you know.

[Michael Wojcik]

Re: Hard coded primes?

It doesn't mean that the DH key exchange protocol is fundamentally broken, I think.

Correct. It means:

- If you use a well-known set of parameters, there's a good chance that well-funded adversaries are already set up to break your key exchanges. Will they? Depends on just how great their resources are, and how much they care about your traffic.

- If you use your own parameters, and you use short primes (where "short" is relative to the attacker's resources and the perceived value of your traffic), well-funded adversaries might spend the time to crack your key exchanges. But this is almost always much less valuable to an attacker than cracking a popular set of parameters, for obvious reasons.

- If you use your own parameters and decently-long primes, DH is as good as ever - that is, there are no known good attacks against it.

[Tomato42]

Re: Hard coded primes?

most cryptographers say that DH and RSA key sizes are equivalent. So if 1024 bit RSA is breakable, 1024 bit DH is breakable.

You can't get 1024 bit RSA keys signed for a reason.

[cantankerous swineherd]

Re: Hard coded primes?

me too

anyone for internet banking?

[Overcharged Aussie]

Re: Hard coded primes?

Every system developed can have implementation flaws. I used to work for a commercial company in this space and often we would be brought it when the local team found crypto too hard or as part of a review of a design. In most cases you could see where they had really tried to be secure but had failed on some point that they had thought was not worth pursuing as they had limited resources (time or staff) to do everything.

The other problem is that most systems in production don't get touched unless there is a reported problem. Advances in security happen often as researchers uncover new exploits but rarely are old systems updated unless there is a reported problem. Some researcher somewhere who has made an advance that blows a hole in some other company's security coding may go unnoticed if it is not documented in a way that the team now responsible for maintaining the legacy product understand that they now have a vulnerability that needs to be patched now.

[JeffyPoooh]

V qb zl bja rapelcgvba...

V qb zl bja rapelcgvba. Gung jnl V'z gbgnyyl frpher.

[elDog]

Re: V qb zl bja rapelcgvba...

Well, that put an end to all the other blather.

Cellmates, let's move on.

[Dadmin]

Re: V qb zl bja rapelcgvba...

V nccebir bs lbhe ebg guvegrra! Uryyb, Jbeyq!

[Kingston Black]

Ohttre...

Zl frpergf nera'g vg frrzf. Onpx gb gur qenjvat obneq sbe zr.

[Feargal Reilly]

Re: V qb zl bja rapelcgvba...

Furrfu, ynfg gvzr gung wbxr jnf shaal argfpncr anivtngbe jnf phggvat rqtr.

[ZSn]

Re: V qb zl bja rapelcgvba...

Gur checbfr bs pelcgbtencul vf gb sbepr gur HF tbireazrag gb fraq lbh gb Thnagnanzb onl!

[ZSn]

Re: V qb zl bja rapelcgvba...

Gjb unfurf jnyx vagb n one, bar jnf n fnygrq.

Naq abj vg'f gvzr gb dhvg V guvax!

[Speltier]

This is news?

10 years ago, this might be a bit interesting. Now, really?

People just don't get the scaling power of a major government both financially and for personnel. First, the personnel. No mind wasting worry about being punted off because some Bozo in the c-suite needs to grease up the markets this quarter. No working on drivel that really has nothing to do with your training and skills. You can actually focus for months on end on a single problem. Sure, 80% of the workers are dead wood, but the other 20% run rings around pretty much everyone in private sector who are forced to produce a product for the unwashed masses (and that includes having to teach hordes of drooling undergrads). Then there is the financial aspect. Once the design exists, 200-500 million buys a huge configuration of custom silicon scaling out from the FPGA proof of concept. It is really cheap per unit using state-of-the-art -1 fabs (one gen old).

People seriously overestimate what one person can do, and underestimate what a group of people can do. NSA and GCHQ can hire amongst the best, and group them on one problem.... lone guy out in the wild is left in the dust unless he or she is a mule (and subject to being hired away in that case! The black budget pays very well for certain contractors if government service isn't enough.).

[Michael Wojcik]

Re: This is news?

Sigh.

As Bellovin says, this is still an excellent piece of work, even if it's not surprising. If you don't understand why, then you don't understand the paper and you don't understand the situation.

[Old Handle]

"Graham calculates that cracking 1024-bit DH it the computational equivalent of 2.5 hours' worth of global Bitcoin mining power."

Interesting, that means it should cost under $100,000. (2.5 hours * 6 blocks per hour * 25 BTC per block * $260 per BTC.) Admittedly that probably isn't really true, because people are stupid, but if that number is even half right, it makes the other figure of a few hundred million for one per year sound very conservative.

[Dick Palmer]

<i>"Graham calculates that cracking 1024-bit DH it the computational equivalent of 2.5 hours' worth of <b>**global**</b> Bitcoin mining power."</i>

[Old Handle]

Of course. That's how Bitcoin works. Less than $100,000 worth of Bitcoins are mined globally in that time. Therefore all bitcoin mining power is being expended for a share of that reward. The assumption, which I acknowledged isn't completely true (because people are stupid), is that the the total amount of work done should not exceed the value of the reward they're competing for, otherwise miners would realize that on average they're losing money and stop doing it.

But given that people are stupid, I can easily believe a substantial amount of money is being wasted. Suppose we allow a "stupid factor" of 90%. That would still only bring the global cost of 2.5 hours of mining up to $1,000,000. I'm just having a hard time reconciling that with a $X00,000,000 price tag for a machine that takes ~3500 times as long to do the same work.

[Anonymous Coward]

Wouldn't it be hilarious/scary if bitcoin hardware was a NSA scam?

Nobody knows what that hardware is really doing, this isn't like an open source mining program you compile yourself where you (in theory) know exactly what it is doing.

For the small price of a few bitcoins, the NSA gets people all over the world to buy custom ASICs in a box that are connected to the internet. They might be cracking encryption or something, but certainly aren't mining new bitcoins. The NSA pays for that service in bitcoins (is there any way to tell if a bitcoin is 'new' or has been around for a while?) Best of all, they can pay less and less over time, since bitcoins are designed to be harder and harder to mine :)

[dajames]

Re: Wouldn't it be hilarious/scary if bitcoin hardware was a NSA scam?

Nobody knows what that hardware is really doing, this isn't like an open source mining program you compile yourself where you (in theory) know exactly what it is doing.

I've said something very like this before ... bitcoin mining basically involves computing SHA-256 hashes very quickly, and I've suggested that one could use a bitcoin farm to brute-force digital signatures that use a SHA-256 hash. That could be more profitable than mining a few measly bitcoins.

You're taking this one step further by suggesting that those boxes of ASICs might not be doing hashing at all, but might be working on the polynomial expansions to attack a DH prime. You're quite right that it would be hard to tell -- and that most people wouldn't look.

[Anonymous Coward]

Mathematics fraud

The trend with each new revelation of a crypto failure is that something that looks good up on a blackboard ends up being crap when it gets implemented in reality. We have all been hoodwinked by this 'Trust the Math' ivory tower BS.

More light needs to be shed on all the fundamental assumptions behind this Potemkin security village we are all living in.

[cantankerous swineherd]

Re: Mathematics fraud

the maths is fine. the problem is when people start doing the hand wavy "no economic attack is feasible" and all that sort of thing. eventually an attack is developed. the schneir article (or one he links to, CBA to look it up) states that they don't properly test the "prime" they're using, that's in the too difficult box and there are some probabilistic methods used. it ain't prime, it's probably prime.

I have concede that real world implementation is way harder than maths: but the short story is, if you want to keep a secret, don't fuck about with computers.

[Destroy All Monsters]

Re: Mathematics fraud

We have all been hoodwinked by this 'Trust the Math' ivory tower BS.

I think there is a song for you that goes like "Don't know much about the math I took".

EDUCATE YOURSELF, EEJIT!

[chasil]

howto

There are a few simple steps to protect yourself by generating your own Diffie-Hellman primes.

To protect ssh, edit the file /etc/ssh/moduli and comment lines where the 5th field is less than 2047:

---

# $OpenBSD: moduli,v 1.8 2012/08/29 05:06:54 dtucker Exp $

# Time Type Tests Tries Size Generator Modulus

#20120821044040 2 6 100 1023 5 D927...

…

#20120821044502 2 6 100 1535 5 D139...

…

20120821045639 2 6 100 2047 2 DD20...

---

To protect TLS for HTTPS, compute your own Diffie-Hellman primes like so:

---

[root@limsprd ~]# openssl dhparam -out foo 2048

Generating DH parameters, 2048 bit long safe prime, generator 2

This is going to take a long time

...+..+..***...

[root@limsprd ~]# cat foo

-----BEGIN DH PARAMETERS-----

MIIBCAKCAQEAnRcLNdZeit18uYSAtEeumAOKIlAvkH5XLVw3V+jbltAjH09RJa8i

n+8bZlLGO7Rg01Exlf3FqMyK5uJTE3FkkCD2Xmv/UR+YS2c4XjzBfxELVC1C8V0J

fvgge4plUX04gG1AN3uwsLp6DgC4Ee06hEuKG6Nh6YX5tHawmPwsRqPM7GRjD4Rc

GYUJCWxh6lKuf63rHUwBH8i44FrQtJHL4lbbqxqQM1K3c2R/g+EcPoTd2VLxlT8y

gbN2rKsSi6/VggOSZ9f8DHNJB5lpuZgd6k7VymCAvc+mtFWVpBvSOWxaT7Wo5wLe

ID3exEDZl/DTDuijs/Tc0zPtoyC7vOPxawIBAg==

-----END DH PARAMETERS-----

Then add the BEGIN/END block above immediately after the “END CERTIFICATE” statement for your public key.

For more discussion on hardening your encryption settings, see these resources:

https://hynek.me/articles/hardening-your-web-servers-ssl-ciphers/

https://stribika.github.io/2015/01/04/secure-secure-shell.html

[pompurin]

Re: howto

Yes thankfully I use dh2048.pem as well, and it is not kidding when it says this will take a long time. I've waited a good five minutes plus on some machines. Not long in the grand scheme of things.

[Michael Wojcik]

Re: howto

I've waited a good five minutes plus on some machines

Really just means you need a bigger entropy pool. On a modern system with adequate entropy for the CPRNG, it shouldn't take very long to find a 2048-bit prime of the desired form.

[Anonymous Coward]

question for you folks

Does this mean that using a single wildcard certificate is a bad idea? Should I really pay for 1 cert per site?

[Destroy All Monsters]

Re: question for you folks

Where does that come in now?

[Sir Runcible Spoon]

Re: question for you folks

How would you know if the new certs were created with a different prime?

This goes a bit deeper than implementation changes at the consumer level, it requires the source of the key to be updated to use more than one prime.

Even if 10 primes were pre-generated and the key pair was generated using one of those ten, the only 1/10th of your comms could be intercepted if one prime were compromised. It's a tail chasing exercise, but it costs a lot more to compromise a prime than it does to calculate one in the first place, so it should be easy to stay ahead of this particular vulnerability once the implementation software for key creation is updated accordingly.

Doesn't do shit for stuff already out there of course.

[dajames]

Re: question for you folks

How would you know if the new certs were created with a different prime?

The public parameters of the Diffie-Hellman key are present in clear in the certificate, so you can just look at the certificate and see ... if you know how to read a key certificate.

[Mark 65]

Elliptical Curves

On the defensive side, NSA has recommended that implementers should transition to elliptic curve cryptography, which isn’t known to suffer from this loophole, but such recommendations tend to go unheeded without explicit justifications or demonstrations.

Isn't that because the NSA stuck a fault in the PRNG so that it repeats numbers hence making it a touch useless?

[Michael Wojcik]

Re: Elliptical Curves

Isn't that because the NSA stuck a fault in the PRNG so that it repeats numbers hence making it a touch useless?

No. Dual_E_DRBG, the backdoored CPRNG endorsed by NIST, has nothing to do with ECC in general. (And the problem isn't that "it repeats numbers", but there's no reason to go into technical details here.)

[Anonymous Coward]

Re. Primed

This has been around for longer than people think.

A few years back, there were rumblings on certain IRC channels that WPA was totally insecure and crackable in seconds with custom hardware (ie a rainbow table) but at the time it was prohibitively expensive due to the cost of solid state drives in the hundreds of GB needed.

In fact, to do the same with WPA, and WPA2 is trivial now and thanks to 512GB drives being virtually consumer components a setup could literally be installed in a mains charger for a phone, storing cracked keys as it went and sending them over the (now open) WiFi when available with its own onetime pad stored on the chips.

Cost would be a bit high but how would someone detect such a device? Even with an RF sniffer passive cracking is very low power and if it only "woke up" once a day at a random time it would be virtually undetectable.

[Dazed and Confused]

Re: Re. Primed

As sometime above signs off their posting "...for now"

This is always the guiding principle when it comes to encryption.

The military only needed encryption to be good enough that the information was no longer of strategic value by the time it was decrypted. A signal that tells an artillery battery to open fire in 5 minutes is fine to send out on a code system which can be broken in 6 minutes time.

But these things need to constantly reviewed, once the enemy can crack the code in sub 5mins you need to be prepared to upgrade your system.

This seems to be where so many crypto systems break down. People expect their encryption tech to last, well they won't. WPA2 is now over 10 years old, how many "Moores cycles" does that give us?

Any encryption system based on mathematical tricks should come with a maximum life time and mandatory reviews. Moores law talked about 18 months, so don't expect to go any longer than that before seriously reviewing things.

[Anonymous Coward]

Re: Re. Primed

Part of the problem is that far too many security articles online do not have dates on them. I went looking for details on wpa2 after reading this and the first article I came across was from over 1500 days ago (based on comment age, which is all I had to go on) but the most recent comment indicated that someone took it seriously in September.

[Vic]

Re: Re. Primed

A signal that tells an artillery battery to open fire in 5 minutes is fine to send out on a code system which can be broken in 6 minutes time.

At the risk of being pedantic, that's not actually true...

If an attacker can see your historic messages, he can build a picture of you. This will likely give him a good guess at certain phrases that you will usually use in communications. Bletchley Park dubbed these "tells", and they are an important method of breaking future communications. It's essentially how they broke Enigma...

Vic.

[Dazed and Confused]

Re: Re. Primed

> At the risk of being pedantic, that's not actually true...

You are of course correct Vic, and not just for "tells" traffic analysis also makes massive use of signals that you can't read. These were lessons that Bletchley taught the military and the powers that be got all snotty with Gordon Welchman when he told the world.

[Anonymous Coward]

Re: Re. Primed

Traffic analysis wasn't a Bletchley invention, military commanders have been using it ever since Ug first noted that the tribe over the hill were using smoke-signals to coordinate their attacks. Bletchley just applied it on a centralised and industrialised scale,

[Francis Vaughan]

"Graham calculates that cracking 1024-bit DH it the computational equivalent of 2.5 hours' worth of global Bitcoin mining power."

The article also stated that the NSA system took a year to crack a prime, and cost $100m

Thus the equivalent value of the global bitcoin mining equipment is $350 billion.

Hmmm. Obviously there is a lag in technology between the NSA system and now, but there remains something of a gap here.

[Anonymous Coward]

Re. Bitcoin

Am I right in saying that the ASICs used for Bitcoin mining essentially run a massively parallel search for a key to a mathematical lock which varies every few seconds?

The same approach (ie a custom chip) could be handy for cracking codes, in this case several million chips all running in parallel with 8nm feature size could do it.

It could also be that the NSA read my post a while back or discovered the effect independently (likely) about using semi-classical effects to increase complexity in a memory chip?