Breaking Diffie-Hellman with Massive Precomputation (Again)

The Internet is abuzz with this blog post and paper, speculating that the NSA is breaking the Diffie-Hellman key-exchange protocol in the wild through massive precomputation.

I wrote about this at length in May when this paper was first made public. (The reason it’s news again is that the paper was just presented at the ACM Computer and Communications Security conference.)

What’s newly being talked about his how this works inside the NSA surveillance architecture. Nicholas Weaver explains:

To decrypt IPsec, a large number of wiretaps monitor for IKE (Internet Key Exchange) handshakes, the protocol that sets up a new IPsec encrypted connection. The handshakes are forwarded to a decryption oracle, a black box system that performs the magic. While this happens, the wiretaps also record all traffic in the associated IPsec connections.

After a period of time, this oracle either returns the private keys or says “i give up”. If the oracle provides the keys, the wiretap decrypts all the stored traffic and continues to decrypt the connection going forward.

[…]

This would also better match the security implications: just the fact that the NSA can decrypt a particular flow is a critical secret. Forwarding a small number of potentially-crackable flows to a central point better matches what is needed to maintain such secrecy.

Thus by performing the decryption in bulk at the wiretaps, complete with hardware acceleration to keep up with the number of encrypted streams, this architecture directly implies that the NSA can break a massive amount of IPsec traffic, a degree of success which implies a cryptanalysis breakthrough.

That last paragraph is Weaver explaining how this attack matches the NSA rhetoric about capabilities in some of their secret documents.

Now that this is out, I’m sure there are a lot of really upset people inside the NSA.

EDITED TO ADD (11/15): How to protect yourself.

Tags: , , , , , , , , , ,

Posted on October 16, 2015 at 6:19 AM • 80 Comments

Comments

Goonie • October 16, 2015 7:00 AM

Speculating a bit (well, a lot) but the NSA’s working assumption if they did choose to exploit this rather than warn is that nobody has their resources, so nobidyy else could pull off this attack. Therefore, they aren’t putting American companies at risk.

When it comes to access to cash and bulk quantities of mpdern commodity computing hardware, that assumption seems increasingly dubious. Furthermore, the Chinese government is by all reports highly motivated to attack corporate networks that this attack would be most effective against.

stine • October 16, 2015 7:19 AM

If this is true, then what’s the optimum lifetime and size for keys used in an IPSec tunnel? 1 hour and 4096bits?

Z.Lozinski • October 16, 2015 7:25 AM

Fort Meade, we all have a problem. Let’s assume for the moment that nation states will operate within their own laws and instead think of evil non-state actors. So consider what could be done by a organised group of hackers.

The two estimates of the attack cost (Table-2 of the paper) are: 120,000 core years for RSA-1024, and 35,000,000 core years for DH-1024.

Amazon has over 10 million cores (based on careful reading of James Hamilton’s presentation at re-Invent 2014). So an attack on RSA-1024 would use under 1% of Amazon’s infrastructure. According to the SANS Institute, bot-net sizes range from 120,000 to 30 million bots. Say 240,000 to 60 million cores. That brings both of the 1024 bit key attacks into range from someone who is prepared to do some advance planning. Yes, I know the other parts of the attack also require work, but the expensive part, the pre-computation is now feasible.

On-line banking, treasury, corporate email (to allow front-running of M&A) are now very attractive targets.

Actually, NSA and GCHQ need to need to start looking to see of there are signs anyone else is trying this in the wild.

Dirk Praet • October 16, 2015 8:51 AM

@ Grauhut, @ Nick P., @ Wael

(moving your previous exchange on the subject to this here thread because more on topic)

If you can do a rainbow table alike attack on a single prime number below 1024bit you can drive the same one against any prime number below 2048bit.

I guess we now know what they’re using their Cray XC30’s at Bluffdale for. Some of the comments in the Freedom to Tinker blog post @Bruce is referring to are talking about the math behind building such database/rainbow table to “break” a prime p.

@ Goonie

… if they did choose to exploit this rather than warn is that nobody has their resources, so nobody else could pull off this attack.

Which is however kinda consistent with a philosophy/approach @Skeptical has been advocating on several occasions on this blog.

So for now, the 64k$ question is: how to protect/mitigate against this?

Wael • October 16, 2015 12:17 PM

@Dirk Praet,

moving your previous exchange on the subject to this here thread because more on topic)

You might as well move this one too!

Daniel • October 16, 2015 12:58 PM

I’m puzzled about whether or not the NSA is really upset and whether this is really the big breakthrough people think it is. Why? Because the NSA allowed the paper to be published. There have been examples of researchers pulling papers because the NSA asked them too. So why not here? If the national security implications are as strong as people suggest, I can’t believe the NSA would sit quietly on the sidelines.

Nick P • October 16, 2015 1:03 PM

@ Dirk Praet

“So for now, the 64k$ question is: how to protect/mitigate against this?”

That’s easy and in the paper: move to ECC or use 2,048-bit minimum. Bernstein has made it super easy with the NaCl implementations with curves giving tons of security and efficiency at same time. Little excuse other than social factors.

@ jayson

No, the paper gets their estimate assuming they are using ASIC’s. They mention that there’s usually around an 80x increase in performance. That’s on the high-end, though, with some problems barely pulling a 2x increase. They played it safe by giving them the benefit of the doubt. So, this result assumes they have a supercomputer with hundreds of thousands of ASIC’s. If I read it right.

@ All

The room for error here is in the ASIC assessment. We need to figure out how much they can parallelize this, either in cores or custom circuits, in a given ASIC. Then, how many of those can do in one chip at 14-28nm. Then how many they can squeeze in a rack. Then how much factoring can be done with Amazon or Microsoft datacenters full of those. That would be the most paranoid assessment.

You see, the unit prices of these things are really low vs initial development costs. That’s one of main drivers for hardware to shrink. The circuits might cost pro’s $10-30 million to develop with boards a tiny fraction of that. Then, the chips themselves are dirt-cheap with the boards being inexpensive. If algorithm doesn’t need much communication, then they can use standard I/O options to farm out the jobs which then just run until they complete. They could add more capacity year after year dirt cheap after spending a ton of money on chip design and real estate just once. They could get 50,000-100,000 chips with multiple accelerators on each every year.

So, I think the authors upper bound is lower than the real upper bound. Need to get specialists who have implemented algorithms like this in hardware to show how it will likely be implemented. Need at least one person whose done a 28nm design to estimate how much of the chip can be dedicated to that with the other functions considered. Then multiply that by whatever Amazon has to get a decent upper-bound.

Andrew • October 16, 2015 1:04 PM

@John Galt IV – 10^12 attempts/s = 10^19/year = (*10^6 botnets, supercomputers, clusters) = 10^25
A 15 characters password = (2^5)15 = 2^75 = 10^22
So it can be fully tested within days, by brute force. And we are not even in quantum age.

rgaff • October 16, 2015 1:35 PM

It may cost the NSA a billion dollars to do this (gee, I wonder what that is in Utah, maybe not just “storage space” after all??) but it will cost the NEXT one who can do it far far less, and happen sooner than you think!

Who? • October 16, 2015 1:35 PM

These are old news. As you said, you wrote about this in May when this research was made public. Nothing has changed since then, right?

What would make this entry in your blog really useful would be discussing what can be done to avoid precomputation risks, now that we know that attacks against Diffie-Hellman are more than an academic dream. Is the IKEv2 protocol (as defined in RFC 5996) vulnerable? How is IPsec affected? Is SSHv2 vulnerable? For protocol version 2 forward security is provided through a DH key agreement, but this protocol version supports the curve25519-sha256@libssl.org key exchange algorithm too. Current OpenSSH defaults seems sane to me. What about web servers? Should we move to a larger than 2048-bit Diffie-Hellman now? How larger then?

CallMeLateForSupper has given a good reference. Let me provide another one: https://bettercrypto.org/ has a good encryption guide (the “Applied Crypto Hardening”), that knowledgeable members of this forum should be able to improve.

me • October 16, 2015 1:45 PM

@ Nick P

ioerror has mentioned at least twice today he sees no evidence that LONGHAUL is using ASICs.

“All the docs I’ve seen suggest LONGHAUL is general purpose.”

Wael • October 16, 2015 1:47 PM

@Z.Lozinski,

Actually, NSA and GCHQ need to need to start looking to see of there are signs anyone else is trying this in the wild.

I put the little money I have that Tianhe-2 is used for that purpose. It also seems the US is aware[1] of who’s hiding this endeavor behind the Bamboo Curtain

[1] Yup, the US will challenge China by building a faster super computer. Guess where it will be manufactured, along with a zillion knockoffs? 🙂

Earl Killian • October 16, 2015 2:07 PM

First, it sounds like getting everyone to change the DH parameters every month or week would be able to make this attack economically infeasible. Good luck on getting the lazy internet to do that though.

What about encrypting the DH key exchange? For example, the client would encrypt a random number using the server’s public-key, and use AES to encrypt the DH key exchange protocol with that.

In general, I think it makes sense to think about using catenated crypto, so that if a weakness is found in one protocol, it still requires a break in the second to break the overall system. For example, XOR with ChaCha20 and then use AES128 ECB on the result. You have to break ChaCha20 and AES128 both. Encrypting DH key exchange with ChaCha20 is an example of catenated crypto.

Nick P • October 16, 2015 2:23 PM

@ me

That’s good news if true. I figure they’re more likely to use a Cray-architected version of this thing. A farm of FPGA’s, high-end CPU’s, and tons of RAM are just what they need. Within budget and benefiting the right parties, too. Also general-purpose, esp supporting signal processing.

Regardless, my analysis applies because someone will build the ASIC’s even if NSA doesn’t. China is the likely candidate as they have a bunch of fabs and the cheap labor is making hardware development (esp RTL) concentrate in that area. They could do this attack in dozens of different ways without spending anything extra (past HW prototyping) because the existing work already paid for the tools and labor.

Anura • October 16, 2015 3:23 PM

@Earl Killian

Well, you are limited by the existing protocols; updating protocols and then getting people to use them takes a very long time. Getting software vendors to update their priority list for TLS ciphersuites and disable export-grade encryption is probably the most effective route. Ideally, the 2048-bit Diffie-Hellman prime wouldn’t be a static configuration, but would be generated in the background using a very low priority process spawned by the TLS server – I doubt you will get a major TLS suite to do this without it having to be manually configured.

Grauhut • October 16, 2015 3:30 PM

@Dirk: https://weakdh.org/sysadmin.html

@Nick: “A farm of FPGA’s, high-end CPU’s, and tons of RAM are just what they need.”

Right, i am with you, think its too early for ASICs. That could be the answer to the “Wtf did Intel invest $16.7 billion in Alteras FPGA tech?” question.

“We see a path to accelerating machine learning, to accelerate storage encryption, to accelerate network functions. We know because we are very deep into those workloads and we now see the opportunity to do it. Now, FPGAs have traditionally been kind of difficult, limited to the far-out expertise, because you are writing RTL. We are a company that writes RTL all the time, so we can solve that problem.”
(Waxman)

Sounds a little like NSA needs cheaper APIs to FPGAs for lazy gov hackers. 🙂

Nick P • October 16, 2015 6:25 PM

@ Grauhut

“Right, i am with you, think its too early for ASICs.”

I agree: most likely multi-core CPU’s, GPU’s, and FPGA [likely with HLS].

“That could be the answer to the “Wtf did Intel invest $16.7 billion in Alteras FPGA tech?” question.”

It might help them haha. Nah, that move was smart. CPU and FPGA techniques, especially auto-partitioning, showed promise far back as the 90’s. The FPGA’s have serious been eating into Intel’s market share in HPC and soon (if not already) cloud. Cloud vendors are finally learning that heterogenous setups geared to types of applications are more efficient. They already use FPGA’s and “semi-custom” hardware internally with AMD forging that path. Intel was getting their ass kicked on every front when they said, “We’ll just buy the cheaper of the Big Two who has easiest-to-use tools. Then, integrate them right in our CPU’s.”

Well-played, Intel. Except maybe for the price: I’m not qualified to judge whether they’re worth that much.

“Sounds a little like NSA needs cheaper APIs to FPGAs for lazy gov hackers. :)”

Seems like it. The number with real skill in the leaks always seems relatively small for a group their size. It’s mostly duct-tape like software in general. What they really need are good hardware people (for FPGA’s) and HPC people working together on projects like this. Once they have a working solution, they can use ASIC conversion to make it faster and cheaper to bulk up on it.

Stuff like Altera’s HardCopy which a major NSA supplier now owns. 🙂

Anura • October 16, 2015 6:53 PM

@Unknown

“What about OpenVPN?”

OpenVPN generates a new DH keypair every single time you connect. Unless you are using a common prime used by a lot of other servers, you should be more secure than a server that just uses RSA of the same key size (which should be at least 2048 bits!), since the precomputation for the Logjam attack takes about 40x as long (yes, over 5 WHOLE bits worth of extra security) as it does to break an RSA certificate (according to the paper). It’s also a lot easier to change out the primes, because you don’t have to sign them with a CA root certificate, and you can write a script to do so on reboot, daily, weekly, monthly, etc.

Booster • October 17, 2015 3:59 AM

I’m a bit of a noob to security, but in summary, are we saying that most IPSEC based VPNs are now not to be considered secure?

booster • October 17, 2015 7:55 AM

Given the post Andy M put up, I don’t see how anyone can work on the basis that IPSEC is secure and hasn’t been for years.

How can anyone still be using it?

Clive Robinson • October 17, 2015 8:06 AM

@ Who?

These are old news. As you said, you wrote about this in May when this research was made public. Nothing has changed since then, right?

It’s even older than that.

Logjam consists of three parts.

1, The Fallback or equivalent of keeping backwards compatibility.

2, The knowledge required to realize the DH attack.

3, The hardware to make the attack worthwhile.

The Fallback issue I’ve been banging on about on this blog for a long long time.

The knowledge required to realize the DH attack has similarly been around for quite some time. I’ve also been warning people to think about the way the NSA do things, not on an individual targeted scale but an industrial scale. Most notably when some researchers over at the Cambridge Labs showed how due to weaknesses in the generation of primes in embedded hardware PK certs had common primes and how that could be trivially found. I gave an outline of exactly how the NSA could have gone about it.

Which included how a “lookup” system could be made and used, which would be very very similar to what would be needed here.

So the ideas required for all three parts were around just waiting for the dots to be joined quite a lot longer than May…

The big take away from this is people are still not listening and thinking on “Fallback” and “Industrialisation” when it comes to attacks. I can think of one or two other protocols that suffer from these issues as I’m sure can others, the problem however is not listing them but getting people to think on them themselves. As Bruce has noted in the past a necessary part of being a designer of crypto systems, is the ability to think up ways to attack not just others systems but your own designs as well. And we need to encourage the “Thinking Hinky” attitude in people not repress it, one way we know works is by engaging peoples curiosity, perhaps the most famous mathematical one being an enigmatic note about the lack of space in a margin…

Clive Robinson • October 17, 2015 8:18 AM

@ Earl Killian,

What about encrypting the DH key exchange? For example, the client would encrypt a random number using the server’s public-key, and use AES to encrypt the DH key exchange protocol with that.

Why would you want to use DH if you already had the servers Public Key?

DH is a protocol for negotiating a secret key between two parties that have had no previous contact or secure side channel available to securely exchange a key or secret. To encrypt DH you would have to have had contact or a secure channel to get the key to do the AES encryption, thus would not need DH.

nighthawk • October 17, 2015 9:00 AM

Bah, the NSA is simply a huge criminal organisation, that deliberately weakens the standards in there own favour to cover up the huge fraud of Lucent & Bell-Labs.

Genie – Blue Gene – Space Bunny & Plan 9 from outer space – otherwise known as Unix V9

It was Robert Morris cryptographer for both bell-labs & the NSA who inserted back-door’s into the TCP/IP stack in partnership with Microsoft & AT&T. It’s bell-labs and there secret protocol that spy on the entire world and subvert the entire computer standards instead of using ANSI-C to fix the already destroyed reputations of Microsoft, Apple, Linux & BSD which they have of course deliberately and maliciously inserted back-door’s into. So the reputation of all five of these systems is in the dirt and all thanks to one agencies desire to own it all.

Clive Robinson • October 17, 2015 9:02 AM

@ Nick P,

What they really need are good hardware people (for FPGA’s) and HPC people working together on projects like this.

As you know, back in the past the NSA had such people, and encouraged them to go out on their own on the promise of contracts to buy the product…

Well due to the usual “bureaucratic crapola” the contracts did not happen instead we got COTS… Which gave us “supply chain poisoning” and all sorts of other nasties that outsourcing to foreign climbs brings.

One of which was first done by Sony, many many years ago the manufacture of CRTs was difficult and was done by just a handful of companies world wide, a couple in Europe and a couple in the US. Sony came along and offered CRTs to UK and US television factories at better rates than their domestic manufacturers of CRTs. The result was the domestic manufacturers went out of business. Sony the put the CRT price up and also supplied in competition cheaper finished TVs. The result you don’t have domestically manufactured TVs any more…

Likewise we don’t have much in the way of domestic manufacturing of silicon chips or computers either…

But now the NSA et al need it but don’t have it, are people going to repeat history, and fall for the old NSA “we’ve got contracts” line? Just to get cut down again by bureaucratic “free market” crapola or just say to the NSA “Hey guy’s money gets time, bull541t gets the back of the line”.

I suspect many know the senior governmental posts are staffed with neo-cons who espouse “freemarket” clap trap to the citizens, but really mean “untouchable cartel, on the tax payer dollar”.

The move by Intel, is but one of several, for instance Apple, getting it’s own US based fab etc. Thus I suspect some people –possibly in the know– are preparing for a sea state change in the US based electronics industry. And this might have something to do with the way China have been “squaring up for a fight” in the South China Seas amongst other things. That is some are preparing for it not be Cyber-war alone much longer…

nighthawk • October 17, 2015 9:22 AM

Here’s an idea NSA – take your space bunny along with your keyhole and insert it into your pie-hole!

nighthawk • October 17, 2015 9:57 AM

@Clive Robinson

Ok, you should educate yourself a bit, there has never been nor is there ever going to be any cyber-war.

Go read up a bit on the history of Bell-Labs and Plan9 from outer space.

Plan9 – does not stop packets, plan9 is impervious to people wanting to break in, in other-words say hello to Unix V9 more Unix than Unix.

So what you have with the GNU – is Governments Not Unix, this is how the NSA enjoy’s spying on Billions of people, OWL – Open Wall Linux, yeap Plan9 goes directly through it’s firewall. SSL wrappers are broken on Windows, Apple, Linux & BSD the reason, SocksFS stealing all the information as your SSL makes its connection.

General Alexander called it, his most top secret CNE – Computer Network Exploitation

It’s so top secret it’s exactly what the russian’s use to spy on all there own Linux users that are too dumb to realise there living in a dream world, where all the software was broken by DESIGN by one agency in particular!

nighthawk • October 17, 2015 10:17 AM

@Clive Robinson

Starting to wake up from the Dream?

Welcome to the Desert of the Real!

CA certificates are inserted into Linux with a heavily obfuscated Kernel that is millions of line’s of code that the average user will never fully decipher in there life-time.

Plan9 is 120’000 Lines of ANSI-C the standard is ANSI-17024 Full Unicode Support and a kernel thats easy to read understand and digest with no obfuscated code or CA’s!

8-bits is as good as it gets, everything else running X is highly suspect!

UUID-STTY (oh ah now we’re getting some light on what’s really going on!)

Nick P • October 17, 2015 10:24 AM

@ Clive Robinson

I think COTS has a lot to do with it. Remember, though, we’re talking about design not manufacturing. The NSA, DOD, and defense contractors all keep plenty of design staff on hand for all kinds of stuff. The manufacturing side is outsourced or contracted plenty. On ASIC side, there’s plenty of companies in the U.S. with the RTL, packaging, etc being pushed to Asia. We still dominate in EDA tools, too, with virtually everyone using the Big Three.

So, one must wonder what staff they have for FPGA/ASIC design and what solutions they’re capable of pulling off. I know they have contractors like 502 design that can help. They have COTS contractors with FPGA/ASIC design capabilities, cleared staff, certified fabs, etc. Still a small segment but one would think they’d leverage it more on brute-force stuff. Not sure what’s up with them.

purple shelf • October 17, 2015 12:15 PM

Judging by the trolling, the NSA must be really upset about this one.

I am surprised that, after disabling the offending DHE ciphers from my browser and keeping the elliptic curve versions (as recommended by the EFF guidelines linked above), nothing appears to have broken. Am I missing something obvious? Is it really a case that not that many sites use it?

nighthawk • October 17, 2015 12:39 PM

@ purple shelf

The EFF? Freedom Foundation – Define freedom?

Free to put back-door’s in your operating system at the TCP/IP layer?

Free to put back-door’s in your kernel?

Free to Spy on you with your mobile phone?

Why’d you suppose the called a Plan of anything? Why not Code 9 or Cool OS 9

Why Plan 9 from Outer Space… Well lets take a closer look at that “Monster Mind” that we’ve all heard so much about and lets take a look at the Google white board and get a feel and understanding for what Google actually stands for…

http://regmedia.co.uk/2006/03/08/google_whitboard_extracts.jpg

Government
Online
Observation
Global
Linux
Environment

–Google!

nighthawk • October 17, 2015 1:03 PM

@ purple shelf

Meet the illuminati and the freemasonry that’s really running the venture capital world of america.

Plan9 & the X11 window manager (9&11), oh yeah, be afraid of that black budget and that giant tax free triangle.

Bill Stewart • October 17, 2015 1:19 PM

A couple of issues people have brought up above
– Breaking RSA is much easier than breaking DH, for a given length – Yes, that’s true, which is why anybody who has a choice has switched away from RSA-1024 to RSA-2048 or more. But while it’s 100x harder to break DH-1024, breaking RSA-1024 would only get you one target’s private keys, but a small number of DH-1024 primes are shared by millions of users, so there’s a huge payoff.

  • “generates a new DH keypair every single time you connect.” Yes, but once they’ve pre-analyzed the prime, cracking each new keypair is relatively trivial. So, as the comment said, if you’re using a common DH prime, the NSA may have done that. Which is fine, as far as it goes… but the alternative to using a common prime (which you negotiate by saying “Is Group 1/2/5/14 ok with you?”) is to negotiate the prime itself,
  • which not only takes a lot longer to exchange,
  • and risks all the various implementation/padding/etc. bugs that are possible in that kind of negotiation,
  • including the risk of negotiation failing and falling back to a cracked DH group,
  • but also requires the party who offers the prime to generate it and test it well (which is either too slow for most uses, or needs to be done in advance, e.g. generate a new prime every day),
  • and requires the other party to either trust that the prime is good (probably safe, except for the risks in transferring the number), or to test that it’s prime (slow, though I suppose you could do one random step of Miller-Rabin and get a 3/4 chance of catching a composite, instead of doing a longer test, since you assume that other people will also test the same prime.)
  • And of course it requires you to get everybody to adopt new libraries with that negotiation protocol, so good luck with that; it’s probably easier to get everybody to accept a new DH-2048 group.

Earl Killian • October 17, 2015 1:25 PM

@Anura

Yes, except that TLS 1.3 is supposedly in the works, so in theory such a thing could be added to it. If it is too late for TLS 1.3, I’m sure there will be a 1.4 someday.

Yes, ideally the 2048-bit DH parameters would be generated periodically (I have a cron script do it monthly for 3072-bit parameters), but that seems less likely to happen internet-wide than getting TLS 1.4 to change…

nighthawk • October 17, 2015 1:41 PM

@ purple shelf

Remember the TAO -ANT’s or Tailored Access Operation ANT – Catalog?

Meet the ANT’s created by a hacker called Mycroft.

http://9gridchan.org/

See how it all start’s to come together, not a nice image isn’t it!

Z.Lozinski • October 17, 2015 1:49 PM

@ Nick P
“So, one must wonder what staff they have for FPGA/ASIC design and what solutions they’re capable of pulling off. … Not sure what’s up with them.”

I know in the mid/late 1980s that the NSA had in-house silicon designers. This was after Carver Mead and Lynn Conway’s work for DARPA on VLSI. The NSA team published a book describing the library of re-usable modules they had created. II read through parts of the book in Foyle’s bookshop in London, but I couldn’t afford it as it was very expensive. (Over GBP 50, when technical books were GBP 20).

A recent (2011) NSA publication “The Next Wave: The National Security Agency’s Review of Emerging Technology. High Confidence Software and Systems” has a paper on Cryptol, a domain specific language developed by the NSA for cryptographic algorithms, and the associated toolchain to compile down to FPGAs. There is an example of using Cryptol for 128-bit AES on Xilinx Virtex 4 FPGAs. (I assume the choice of 128-bit AES is to avoid having to get approval to describe a production implementation).

You can find Next Wave online, but the .PDF seems to be malformed, and it breaks Safari Web-Kit.

Earl Killian • October 17, 2015 1:59 PM

@Clive Robinson

You wrote: “Why would you want to use DH if you already had the servers Public Key? DH is a protocol for negotiating a secret key between two parties that have had no previous contact or secure side channel available to securely exchange a key or secret.”

We already use DH when we have the server’s public key. Consider the TLS 1.2 cipher TLS_DHE_RSA_WITH_AES_128_GCM_SHA256 where DHE is used for symmetric key exchange and RSA is used for authentication.

You wrote: “To encrypt DH you would have to have had contact or a secure channel to get the key to do the AES encryption, thus would not need DH.”

Again, as I said in the original comment, the client would encrypt a random number to be used for symmetric encryption using the server’s public key. No secure channel is required.

Who? • October 17, 2015 2:13 PM

@Clive Robinson

As Bruce has noted in the past a necessary part of being a designer of crypto systems, is the ability to think up ways to attack not just others systems but your own designs as well. And we need to encourage the “Thinking Hinky” attitude in people not repress it, one way we know works is by engaging peoples curiosity, perhaps the most famous mathematical one being an enigmatic note about the lack of space in a margin…

Very true. It is the only way to let cryptography advance.

Nice reference to Fermat’s last theorem. An old theorem that was successfully proof two decades ago by Andrew Willes using… elliptic curves.

Czerno • October 17, 2015 2:14 PM

@Nick P wrote: “So, this result assumes they have a supercomputer with hundreds of thousands of ASIC’s. If I read it right.”

Question for you all : is that kind of computer in existence and viable ? And, I mean, having acceptable reliability (MTBF calculations, anyone ?)

Nick P • October 17, 2015 3:17 PM

@ Z. Lozinski

I’ve seen Next Wave before. That and other hardware crypto work are mainly done with Galois Inc and Rockwell-Collins, respectively. Galois open-sourced their CRYPTOL language and compiler. Rockwell-Collins has several EAL7-grade toolchains that they describe in detail but probably have no intension of open-sourcing. 😉 So, those docs in Next Wave only hint at a handful of hardware experts with the real work done by contractors.

We’re still left to wonder what their level of staffing is. However, TAO catalog reveals majority is custom boards or devices w/ COTS IC’s. If they have the ASIC capability, they use it sparingly.

@ Czerno

“Question for you all : is that kind of computer in existence and viable ? And, I mean, having acceptable reliability (MTBF calculations, anyone ?)”

Every HPC cluster is a bunch of ASIC’s working together. Reliable enough. 😉 The model for this would be general-purpose CPU’s and I/O with a ton of co-processors. These co-processors would connect to a memory or I/O bus. The standard RAS features in HPC or NUMA machines could be used here. The CPU’s and I/O would act as drivers to push data into ASIC’s, monitor their work, and pull data from them. The ASIC’s would also start out as FPGA’s solving smaller versions of the problem for proof of concept.

That’s how I see it playing out if they do it.

Note: They might also use high-end GPU’s if the algorithm works on them just because many existing HPC solutions are using them.

Clive Robinson • October 17, 2015 4:54 PM

@ Earl Killian,

as I said in the original comment, the client would encrypt a random number to be used for symmetric encryption using the server’s public key. No secure channel is required.

If you do that to make a secret symmetric key to encrypt the DH why do you need to use DH just to make another secret symmetric key?

In the case you are thinking up the use of the PK cert is the secure channel, and you would have no need to use DH for it’s original purpose which was to securely come up with a secret key on an open channel… Thus the idea is in the use case you describe a redundant step.

If you are thinking of another reason to use a secure channel (PK cert) to establish another secure channel with DH then you need to state why you think it’s not a redundant step. That is why you think the first secure channel (PK cert) should not be used for anything except for DH to make a key for a second secure channel to be used instead of the first secure channel…

Dirk Praet • October 18, 2015 12:08 PM

@ Nick P. , @ Grauhut, @ CallMeLateForSupper, @ All TAILS users

… move to ECC or use 2,048-bit minimum. Bernstein has made it super easy with the NaCl implementations with curves giving tons of security and efficiency at same time. Little excuse other than social factors.

https://weakdh.org/sysadmin.html

Thanks for the pointers, guys. A few comments:

1) For securing OpenSSH, I recommend using https://stribika.github.io/2015/01/04/secure-secure-shell.html , referenced in @CallMeLateForSupper’s EFF-link, instead of https://weakdh.org/sysadmin.html . It contains detailed instructions for setting Ciphers, KexAlgorithms, MACs, HostKeyAlgorithms etc.

2) When recreating the /etc/ssh/moduli file with “ssh-keygen -G /etc/ssh/moduli.all -b 4096” and “ssh-keygen -T /etc/ssh/moduli.safe -f /etc/ssh/moduli.all“, make sure to execute those commands on a somewhat recent and powerful machine. On one of my old laptops it ran for several days.

3) Attention TAILS users: current version 1.6 ships with a really old version of openssh-client that doesn’t yet support most of the recommendations made in above stribika.github.io page. Which means that after every boot you need to upgrade that package with “sudo apt-get install openssh-client=1:6.6p1-4~bpo70+1” (or higher) if you plan on doing any (NSA-proof) SSH-sessions.

Nick P • October 18, 2015 1:23 PM

@ Dirk

“When recreating the /etc/ssh/moduli file with “ssh-keygen -G /etc/ssh/moduli.all -b 4096” and “ssh-keygen -T /etc/ssh/moduli.safe -f /etc/ssh/moduli.all”, make sure to execute those commands on a somewhat recent and powerful machine. On one of my old laptops it ran for several days.”

I wonder if that’s the algorithm, RNG, or implementation problem. If you can, see if it’s using /dev/random. If it is, force it to use /dev/urandom to see if you get better results. If you do get better results, then we know the solution is to use a fast CRNG seeded with /dev/random for default case. A keygen taking hours to days is too much delay to get any uptake.

Clive Robinson • October 18, 2015 8:50 PM

@ Earl Killian

The reason to use DH after creating a temporary encryption key is to get an ephemeral key for forward secrecy:

And the reason for creating the ephemeral key is?

To deal with the possibility that the server private key was compromised by heartbleed or blackbag job etc etc.

So your proposal to solve the issue of a potentially broken ephemeral key protocol is to try and fix it with more of what it was designed to protect against in the first place.

Thus if the server private key ever gets compromised, your fix gets striped off and the broken ephemeral key protocol designed to protect against the possibility gets exposed.

So your idea gains you no protection just added complication, thus at best it’s a redundant step.

But it could be worse, that random number you encrypt with the server public key gets exposed to the attacker. Due to the way people have written crypto systems in the past, there is a high likelihood that knowing that random number and the system the client uses the attacker can use it to predict the next random number you are going to use as the client secret in the DH protocol…

So back to you to explain where you think the advantages are in your idea.

Ex ASIOworkman • October 19, 2015 8:33 AM

Curtisy of http://www.guru3d.com/news-story/how-is-nsa-breaking-so-much-crypto.html

There have been rumors for years that the NSA can decrypt a significant fraction of encrypted Internet traffic. In 2012, 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.’

The Snowden documents also hint at some extraordinary capabilities: they show that NSA has built extensive infrastructure to intercept and decrypt VPN traffic and suggest that the agency can decrypt at least some HTTPS and SSH connections on demand. However, the documents do not explain how these breakthroughs work.

The key is, somewhat ironically, Diffie-Hellman key exchange, an algorithm that we and many others have advocated as a defense against mass surveillance. Diffie-Hellman is a cornerstone of modern cryptography used for VPNs, HTTPS websites, email, and many other protocols. Our paper shows that, through a confluence of number theory and bad implementation choices, many real-world users of Diffie-Hellman are likely vulnerable to state-level attackers. 

For the nerds in the audience, here's what's wrong: If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number with a particular form. There seemed to be no reason why everyone couldn't just use the same prime, and, in fact, many applications tend to use standardized or hard-coded primes. But there was a very important detail that got lost in translation between the mathematicians and the practitioners: an adversary can perform a single enormous computation to “crack” a particular prime, then easily break any individual connection that uses that prime.

How enormous a computation, you ask? Possibly a technical feat on a scale (relative to the state of computing at the time) not seen since the Enigma cryptanalysis during World War II. Even estimating the difficulty is tricky, due to the complexity of the algorithm involved, but our paper gives some conservative estimates. For the most common strength of Diffie-Hellman (1024 bits), it would cost a few hundred million dollars to build a machine, based on special purpose hardware, that would be able to crack one Diffie-Hellman prime every year. 

Would this be worth it for an intelligence agency? Since a handful of primes are so widely reused, the payoff, in terms of connections they could decrypt, would be enormous. Breaking a single, common 1024-bit prime would allow NSA to passively decrypt connections to two-thirds of VPNs and a quarter of all SSH servers globally. Breaking a second 1024-bit prime would allow passive eavesdropping on connections to nearly 20% of the top million HTTPS websites. In other words, a one-time investment in massive computation would make it possible to eavesdrop on trillions of encrypted connections.

NOTE : The real capabilities of monitoring are far more powerful, at least in Australia.

rgaff • October 19, 2015 10:46 AM

@Nick P, Dirk

In my experience, the first command seems to generate lots of random prime “candidates”… right? That runs relatively fast. It’s the second command that sifts through those candidates to find the ones that are real primes that takes so long. Thus, it’s probably not the RNG that’s the bottleneck.

But if you have really slow and old machines, you can always generate it on another faster one and copy it over (just do so on a private network so there’s less likelihood of your connection being snooped).

But keep in mind that simply generating 2048-bit primes on a Raspberry Pi 2 isn’t bad. You can put multiple sizes in that moduli file (just like it had originally).

Dirk Praet • October 19, 2015 4:36 PM

@ rgaff, @ Nick P.

In my experience, the first command seems to generate lots of random prime “candidates”… right?

Yep. The first command generated 850k+ candidates and took less than an hour. The second one took almost 60 hours to complete on a 10 year-old laptop stuffed with RAM. It generated a moduli file with just 40 records. ssh-keygen seems to use /dev/random indeed.

Nick P • October 19, 2015 5:19 PM

@ Dirk, rgaff

The source is mostly in modulo.c, etc. I looked at it. That particular procedure is heavy enough in domain knowledge that an amateur isn’t speeding it up any aside from an optimized, assembler implementation for their own hardware. More likely to “optimize” away some of its security or performance in corner cases. Well, at least I looked…

re copy it over

I’m trying to avoid that as the modern machines are less trustworthy. Best options are an old gaming desktop, hand-me-down server (esp Itanium), Linux on older gaming device (eg PS2), embedded board with DSP, lower subversion FPGA (esp cost/energy-optimized), and GPGPU on recent (probably safe) or older GPU. I mean, anything might work if it’s truly airgapped. Just gotta remember that what’s generating your keys and configurations is basically the root of trust. You don’t want anything getting in or out without lots of effort.

Clive Robinson • October 19, 2015 6:01 PM

@ Nick P, et al,

I’m trying to avoid that as the modern machines are less trustworthy. Best options are an old gaming desktop, hand-me-down server…

You might want to look at some of the PC104 and similar cage mount PCs for industrial control, most don’t have UFEI etc and are designed to take old fashioned ROM chips for the BIOS etc and you can pick and chose what IO cards you add. A friend has a system running Linux with eight serial ports and old fashioned 10BaseT networking, it runs a fairly sophisticated CANbus control system.

Nick P • October 19, 2015 6:26 PM

@ Clive Robinson

Appreciate the tip. Got any good sources for stuff like that past the few links that pop up in Google?

Clive Robinson • October 20, 2015 12:47 AM

@ Nick P,

Most of the details I have apply to the UK side of the puddle.

However the PC/104 Consortium has a products page,

http://www.pc104.org/products

From which you can work your way to the distributors of the various manufacturers in your region. Often the distributors will carry product not just from consortium members but other manufacturers as well.

What you are looking for is the older PC104 boards with the PC AT interface if you want to build your own interface cards. I’ve never been that fond of PCie as you have to get in interface chips that are QFP or worse which makes old school prototyping a pain in the 455.

Taz • October 20, 2015 1:33 PM

Please!!!

What else can be done to hit the NSA and its personnel?

“Rest of us” need a plan. Hit them where it hurts – their wallet.

Getting even must evolve into a recurring pattern. Not a one off event.

Wael • October 20, 2015 1:51 PM

@Taz,

Hit them where it hurts – their wallet.

Their wallet is your wallet!

This joint is getting so quiet, one can almost read a needle drop! Need some controversial subjects to discuss! I have a few, but they are “too” controversial and career-limiting for me to start! My sockpuppet is turning in its grave!

Anura • October 20, 2015 3:12 PM

@Wael

We could always go off topic in the squid post and start discussing the merits of market socialism, i.e. eliminating private property ownership (as in land, buildings, homes, etc), as well as eliminating corporations, replacing them with cooperatives, NPOs, and publicly owned companies.

rgaff • October 20, 2015 4:37 PM

@Nick P

Regarding avoiding copying it over, due to modern machines being less trustworthy…

You do have a very good point, of course…

It really comes down to “how secure” one wants to get, and not everyone has the same needs (“threat model”). At the same time, even those of us who (“think” we) don’t need “perfect” security (as if there ever was such a thing) we still shouldn’t get complacent and not keep learning and improving our security over time… cause the “bad guys” are always getting better and better at what they do, we gotta keep up the pace too to keep from getting totally squashed like little bugs. Security is a road, not a destination.

In this particular case, the way I understand it, the bigger the prime, the less important that it be unique or non-common, because it would take too much resources to crack. So, for example, when I regenerated all my /etc/ssh/moduli files on all my machines, I generated 2048, 3072, and 4096 on every machine itself… whereas I generated the 6144 one on only the faster machines and copied to slower ones, and the 8192 I only bothered to generate once and copy the exact same values to all machines. Yep, it takes a few days, but I think it’ll work for a few years until the next vulnerability is discovered…

As far as being secret or truly random… surely they can’t be needing to be totally secret and random… otherwise they wouldn’t have included the same values in a common file for all users, right? It’s just that the shorter ones have a more feasible precomputation attack that becomes even more valuable to expend the resources on when they’re all common…

And for those of you who are talking about air gapped… you don’t need SSH installed at all on those machines, right? 🙂

Nick P • October 20, 2015 7:47 PM

@ rgaff

“Yep, it takes a few days, but I think it’ll work for a few years until the next vulnerability is discovered…”

Haha. Realistic perspective.

“And for those of you who are talking about air gapped… you don’t need SSH installed at all on those machines, right? :)”

Idk about them but I’m only talking about source machine. That is, the machine that generates the entropy, secrets, or binaries the rest depend on. Optionally that stores their configurations or backups. Needs to be extremely isolated from the computers actually running SSH and connecting to untrusted networks. A basic design principle of mine.

Dirk Praet • October 20, 2015 8:49 PM

@ Nick P., @rgaff

“Yep, it takes a few days, but I think it’ll work for a few years until the next vulnerability is discovered…”

Still I believe it’s quite worth doing these little things. Like everyone else, I know there’s many more known and unknown attack surfaces (hardware, 0days etc.), but every effort – however small – that messes with 5Eyes and other criminal decryption capabilities of internet traffic is a step in the right direction.

I’m actually feeling quite pleased with the TAILS customisations I’ve been doing over the last couple of weeks – including this one – and I hope to be able to dump some of that stuff on Github at some point. Improved the PyBitmessage installation and configuration script and added a couple of extra lines to persistently disable RC4 and the two security.ssl3.dhe_* values in my TAILS start-up script today. Apparently, Firefox still has RC4 enabled by default and won’t be getting rid of it before January next year (FF44).

jiminy jones • October 21, 2015 10:23 AM

Absolutely the min RSA-2048 (ASD publicly released advice) is not likely secure, more likey RSA-4096 minimum would be our safest bet they’d be hoping on.

saklater quests • October 21, 2015 10:34 AM

Turing broke the Enigma machines possible codings using his mind and a simple mechanised system. Once you discover a repeating or predictable series of patterns or protocols ( with any ability to detect information denoting order or intelligence, you have an angle)

Earl Killian • October 21, 2015 12:25 PM

@Clive Robinson

I was aware of that point when I proposed encrypting the DH key exchange but I still thought it was worthwhile because it requires Eve to accomplish two tasks rather than just one. Eve must both obtain the private key and break all the DH exchanges. It is a two-layer defense.

ianf • October 21, 2015 1:20 PM

@ saklater quests

Alan Turing was without a doubt a Copernicus-class genius (whom his fellow Brits treated extraordinarily harshly and inhumanely, but that’s another topic). You are however misinformed as to who broke the Enigma coding principles – it was a group of Polish mathematically-minded cryptographers who first done it in 1932, when an Enigma box that the Wehrmacht never knew was lost “fell into” their lap. They were also the ones to first construct mechanical emulators/ validators for the Enigma, that later stood model for Turing’s improved and enlarged “bombe” version. It only took the British 75 years to half-officially acknowledge it, well after the last of sole-British-Bletchley-credit heralds have died. Now that you know the score (described previously in many a code breaking history book—I’ve known it for 25+ years), you should not perpetuate the untruth.

Justin • October 22, 2015 10:02 PM

@ ianf

Alan Turing … whom his fellow Brits treated extraordinarily harshly and inhumanely, …

Nothing’s changed. They don’t treat people any better than that today.

ianf • October 23, 2015 1:50 AM

OT. I read it, so you won’t have to. Reports The Guardian (2 items):

An extremely rare and fully operational Nazi Enigma machine has sold for $365,000 in New York, setting a new record at auction.

The M4 machine, which was built between 1943 and 1945, is one of around 150 to have survived from an estimated 1,500 that were built as Nazi Germany fought to fend off the Allies. […]

The M4, with four rotors, is the scarcest of all Enigma encryption machines and was used on naval submarines.

Its manufacture was ordered by German Admiral Karl Donitz due to concerns that the three-rotor Enigma machine had been compromised following the capture of a U-boat in August 1941. […]

Bonhams sold a fully operational M3 Enigma machine for $269,000 at auction in New York last April. http://gu.com/p/4dhe6

    Damn, my 1953 Original Odhner 127 (in Grey) mechanical calculator #127-684916, pretty much an enigma for me, is only worth £39.79 on eBay, but so far nobody has made me an offer I couldn’t refuse!

Disastrous cold war operation provoked row over MI6 responsibility.

A disastrous MI6 operation that resulted in the headless body of a navy frogman being washed up in Chichester harbour provoked a furious row over who should be responsible for Britain’s secret intelligence service, hitherto classified files show.

Commander Lionel “Buster” Crabb was asked by MI6 to inspect the propeller and hull of a new Soviet cruiser, the Ordzhonikidze, which was moored at Portsmouth during Nikita Khrushchev and Marshal Nikolai Bulganin’s official visit to Britain in 1956. But Crabb vanished, and a coroner later ruled that a headless body found in June 1957 was his. […]

An official inquiry attacked MI6 for “errors in tradecraft”, describing as “criminal folly” the decision by Bernard Smith, the officer in charge of the operation, to sign his real name and address in the register of the Sally Port hotel, where he stayed the night with Crabb before the operation. It also noted that the 47-year-old Crabb had not done any diving for six months. An inquest jury on Crabb recorded an open verdict. […] http://gu.com/p/4dh6y

MarkH • October 24, 2015 6:57 PM

Probably I’m getting too old to follow some of these discussions …

It looked to me, like some comments expressed concern about the security of transferring DH prime candidates from one locus to another. Probably, I misunderstood.

The mathematical group used for DH key agreement does not need to secret. In most practical applications, it cannot be kept secret!

The same goes for candidate numbers to be tested for suitability as the basis of a DH discrete log group. You can publish them all in the newspaper, it will make no difference!

As distinct from typical crypto applications, it doesn’t even matter if your attacker knows the internal state of your PRBG. You can post the seed on a highway billboard.

Even using a PRBG is overkill. You could just as well hash strings of ASCII from your favorite news site. Precomputation is estimated to be ultra expensive. It can’t be done for more than a small list of primes. All you need to be safe from this attack, is not to be on the list! Protection is about the prime being distinct, not impossible to predict.

For a prime to form the basis of a DH multiplication group secure against the precomputation attack, it is necessary and sufficient to be:

• safe: based on a Sophie Germain prime
• large: even 1024 bits is estimated to be massively costly to break using today’s techniques; of course, bigger is safer
• fresh: distinct from the commonly used DH primes

That’s it! You don’t need anything else.

Apart from replacing all of your crypto software with malware, there is only one useful attack an opponent could possibly make against the machine used to compute your DH prime, and that is to tamper with the pseudo-random generation in such a way that with high probability, you will choose a prime that has already been precomputed, or a prime that so many other people will also derive as to render precomputation cost-effective.

That’s it. No other attack means anything at all.

Even if the Bad Guys (TM) DID infect your generating machine with malware, it is easy to validate your prime. You can do it as many times as you want on any computer anywhere.

1) Test it for primality, and then subtract one and test half of that for primality.

2) Check against the widely used primes already out there, to make sure it’s not on the list.

gryzor • October 30, 2015 6:44 AM

“Now that this is out, I’m sure there are a lot of really upset people inside the NSA.”

I guess I am more upset knowing what they do, than they can ever be knowing that we know.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.