If The NSA's Not Complaining About Encryption, It's Likely Because It Has Already Found A Way In

from the we-left-ourselves-a-key-to-the-back-door-under-the-mat dept

Thu, Oct 15th 2015 11:41am — Tim Cushing

The NSA hasn't said much (well... compared to the FBI) over the past several months about the default phone encryption offered by Google and Apple. This lack of public outcry has to do with the NSA's capabilities, rather than a sudden interest in ensuring people around the world have access to secure communications. If it truly felt the world would be a better place with safer computing, it wouldn't have invested so much in hardware implants, software exploits and -- its biggest black budget line -- defeating encryption.

Where there's no smoke, there's a great deal of fire which can neither be confirmed nor denied. The NSA has very likely punched holes in encryption in existing encryption. But how does it do it? A brute force attack on encryption would be largely futile, even with the computing power the agency possesses. Alex Halderman and Nadia Heninger at Freedom to Tinker have a theory, and it involves a "flaw" in a highly-recommended encryption algorithm.

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.

The belief that these common primes (or at least some of them) wouldn't be cracked relied on the assumption that no one entity would have the money to assemble the computing force needed to break the code. The problem is that the NSA likely has the time, money and power to tackle this enormous project. Here's why it first seemed unlikely:

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.

And here's the reality of the situation, as exposed by documents leaked by Snowden.

The 2013 “black budget” request, leaked as part of the Snowden cache, states that NSA has prioritized “investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.” It shows that the agency’s budget is on the order of $10 billion a year, with over $1 billion dedicated to computer network exploitation, and several subprograms in the hundreds of millions a year.

What was once considered to be beyond the capabilities of even the biggest intelligence agency is obviously well within its reach. As the authors point out, this would explain the other information seen in leaked documents, like the NSA's ability to decrypt some secured connections "on command" or eavesdrop on VPN traffic.

This is still just a theory, but it does seem to explain much of what's been uncovered in leaked documents. It also shows the NSA is still doing what the NSA does best: leaving lots of stuff poorly-secured, despite directives otherwise.

Our findings illuminate the tension between NSA’s two missions, gathering intelligence and defending U.S. computer security. If our hypothesis is correct, the agency has been vigorously exploiting weak Diffie-Hellman, while taking only small steps to help fix the problem.

As the authors point out, the NSA has recommended better encryption methods, but no one's in any hurry to adopt them because no one trusts the NSA to recommend a method it hasn't already weakened, if not completely compromised. If there's any truth to what's covered here, the NSA has sat quietly by and allowed researchers to recommend yet another encryption method that it's already made large strides towards defeating. And, once again, we can see that when the word "security" is combined with the word "national," it means something completely different than when it stands on its own.

Thank you for reading this Techdirt post. With so many things competing for everyone’s attention these days, we really appreciate you giving us your time. We work hard every day to put quality content out there for our community.

Techdirt is one of the few remaining truly independent media outlets. We do not have a giant corporation behind us, and we rely heavily on our community to support us, in an age when advertisers are increasingly uninterested in sponsoring small, independent sites — especially a site like ours that is unwilling to pull punches in its reporting and analysis.

While other websites have resorted to paywalls, registration requirements, and increasingly annoying/intrusive advertising, we have always kept Techdirt open and available to anyone. But in order to continue doing so, we need your support. We offer a variety of ways for our readers to support us, from direct donations to special subscriptions and cool merchandise — and every little bit helps. Thank you.

–The Techdirt Team

Filed Under: alex halderman, backdoors, diffie hellman, diffie hellman key exchange, encryption, hacking, https, nadia heninger, nsa, surveillance, vpns

45 Comments

If you liked this post, you may also be interested in...

Reader Comments

Subscribe: RSS

View by: Time | Thread

Uriel-238 (profile), 15 Oct 2015 @ 12:02pm

That's a lot of money.
One must ask why we're spending ten billion dollars on the NSA. Does the NSA do anything for anyone outside the NSA?
[ link to this | view in thread ]
Anonymous Coward, 15 Oct 2015 @ 12:08pm

It's time to strengthen the encryption used.
[ link to this | view in thread ]
Anonymous Coward, 15 Oct 2015 @ 12:19pm

Tim,

Can you explain what it means to 'crack' a prime?
[ link to this | view in thread ]
Anonymous Anonymous Coward, 15 Oct 2015 @ 12:25pm

Passing Keys?
If I understand this post correctly, the issue is either in the reuse of large keys, and/or how large keys are passed. Doesn't passing keys in the clear automatically invalidate them? Is there a way to pass them not in the clear without using Diffie-Hellman? Does PGP use Diffie-Hellman?

The next question is along the lines of why use prime numbers. It seems to me that there are more limited quantities of those verses any large number and that might make finding them easier. I am relatively certain there is some mathematical explanation for this that is beyond my ken.
[ link to this | view in thread ]
icarusthecow (profile), 15 Oct 2015 @ 12:30pm

Re:
The point being is that the prime is used with separate secrets to derive a key. prime + secretA + secretB.
Like using rainbow tables for md5, one could (with enough computer power) generate all the possible derivations.
Since its designed for insecure channels (ie, in order to share a secret over an untrusted/unencrypted connection), intercepting the intermediate keys (prime + secretA and prime + secretB), and checking them against the factored table gives you the secrets. do for both. then you can derive the "secret key" that allows you to decrypt subsequent chatter.

So to answer your question, its not so much as "crack" but rather "factor" all of the potential prime+randomPrime combinations ahead of time.
[ link to this | view in thread ]
icarusthecow (profile), 15 Oct 2015 @ 12:43pm

Re: Passing Keys?
PGP doesn't necessarily use DH. SSL does for key exchange. both use RSA for identity verification (signing) and a block cipher for the actual data encryption.

DH was designed for the very reason of passing that block cipher key over an unencrypted channel, it packs secrets in a hard to reverse format that can be combined on the other end so that both sides come to the same conclusion, without every transmitting their own secret. Otherwise you have to establish an encrypted channel to exchange the key...
You can do this with RSA, but in that case, the key for every key exchange session is the same. Break one session, break them all. DH allows a different key exchange each time, so if you crack one key, you crack only that session.

Primes are important for mathematical reasons. They have certain properties that make verifying results provable.
For example (4^3)^2) => 4^3*2 (4^6) but, so would 2^6^2 (2^6*2 => 2^2^6 => 4^6), so it breaks the "provableness" (not a mathematician pardon the bad language) because multiple inputs can yield the same result. (That's a problem when it comes to signature verification when you need to prove knowledge of a specific secret)
[ link to this | view in thread ]
Anonymous Coward, 15 Oct 2015 @ 12:45pm

Re: Passing Keys?
It's because the product of two primes has only those two primes as possible factors (ie 35 can only be factored into 5 and 7).

If one or both of the factors isn't prime, then you can't be sure if you are both using the same key. For example, when you factor 36 you can get 6x6 or 3x12 or 4x9 or 2x18.

The numbers used in cryptography are much, much bigger though and so the factoring problem is very difficult.
[ link to this | view in thread ]
jackn, 15 Oct 2015 @ 1:28pm

Re:
Prime numbers are the basis for encryption.

https://en.wikipedia.org/wiki/RSA_(cryptosystem)
[ link to this | view in thread ]
DannyB (profile), 15 Oct 2015 @ 1:30pm

Re:
I think they mean crack a composite made of two prime numbers.

(One of the prime numbers is very very large, the other one is 7.)
[ link to this | view in thread ]
DannyB (profile), 15 Oct 2015 @ 1:30pm

Re: Re:
And by crack, I mean factor.
[ link to this | view in thread ]
DannyB (profile), 15 Oct 2015 @ 1:37pm

Re: Re: Passing Keys?
The numbers used in cryptography are indeed big.

Bigger than the national debt.

So big they are getting up there near the amount of money that the RIAA is losing due to piracy.

US $ 10 ^ 500
[ link to this | view in thread ]
cornfuzed, 15 Oct 2015 @ 1:37pm

huh >>>>

The NSA has very likely punched holes in encryption in existing encryption.

rewrite? edit?
[ link to this | view in thread ]
icarusthecow (profile), 15 Oct 2015 @ 1:41pm

Re: Re: Re:
In this case its not factoring. Its solving the discrete logarithm problem.

Given C, find A and B where A^B = C. A is the "shared prime" so you have to solve log C / log A. Discrete logs are computationally expensive to calculate, even more so than factoring. (which is just brute force multiplication)
This is why DH keys can be much smaller than RSA and still be relatively secure.
[ link to this | view in thread ]
sam1am (profile), 15 Oct 2015 @ 2:17pm

There has been some discussion of the problem, but how can it be fixed? Should I not be relying on encryption?
[ link to this | view in thread ]
Anonymous Coward, 15 Oct 2015 @ 2:18pm

Re:
There's some information on the Wikipedia page for DH. Short version: DH works by two parties each choosing a secret number modulo the same large prime. In theory it's OK for the prime to be publically known, but...
The number field sieve algorithm, which is generally the most effective in solving the discrete logarithm problem, consists of four computational steps. The first three steps only depend on the order of the group G, not on the specific number whose finite log is desired. It turns out that much Internet traffic uses one of a handful of groups that are of order 1024-bits or less. By precomputing the first three steps of the number field sieve for the most common groups, an attacker need only carry out the last step, which is much less computationally expensive than the first three steps, to obtain a specific logarithm.
(So the prime number needs to be large enough to make those first 3 steps impractical. 1024 bits aren't enough. The NSA probably can't crack every 1024-bit key, but if enough people share a prime, the resource investment for precomputation can pay off.)
[ link to this | view in thread ]
Anonymous Coward, 15 Oct 2015 @ 2:24pm

Re: Re:
I think they mean crack a composite made of two prime numbers.
I thought the same thing, but they didn't mean that. They're doing some precomputation related to the commonly-used prime numbers. Then, when people use those numbers, they can solve the specific discrete logarithm problem more easily. (Not trivially, so they're probably not cracking *all* traffic. But if you do anything they deem "suspicious", or if you're a high-value target like a sysadmin, they'll feed your DH exchange to their supercomputer.)
[ link to this | view in thread ]
Anon, 15 Oct 2015 @ 2:39pm

Re: That's a lot of money.
The main purpose of NSA/CSS is to support the US imperial war machine. Apart from vacuuming infinite amounts of public money it also does things like providing intel on which hospitals and weddings to bomb, which citizens to abduct and torture etc...
[ link to this | view in thread ]
Anonymous Coward, 15 Oct 2015 @ 3:10pm

Already Found A Way In

win10
[ link to this | view in thread ]
Anonymous Coward, 15 Oct 2015 @ 5:23pm

So I guess we all assumed who the real hackers were, and we were correct. If you truly want your business to be your own, don't do your business on the internet.
[ link to this | view in thread ]
Anonymous Coward, 15 Oct 2015 @ 6:21pm

What's the point of encryption?
If they already have spyware on phones and devices? Its pointless to have a safe phone-line if they bug the room you know.
Your communication may be safe from prying eyes of citizens, but the government is already watching you take a leak.
[ link to this | view in thread ]
Anonymous Coward, 15 Oct 2015 @ 6:29pm

Too easy?
Are we at the point where ROT-13 is the most secure because it's the least expected?

Security through mediocrity?
[ link to this | view in thread ]
Uriel-238 (profile), 15 Oct 2015 @ 6:44pm

One advantage is that most of us ARE mediocre
So that even if you really do look like a terrorist, there are probably another two million Americans who also look like terrorists as much as you do, if not more so.

They can't round up every single dissident. It's only when you catch the attention of some official who wants what you got.

So yeah, having some prime real estate or a pretty spouse or a company that is doing well in a given market is more likely to get you in trouble than your bomb hobby or your radical politics and fanatical faith to Islam.

Those last things will just be the justification to disappear you so that said official can take your stuff.
[ link to this | view in thread ]
That One Guy (profile), 15 Oct 2015 @ 7:03pm

Tension? What tension?
Our findings illuminate the tension between NSA’s two missions, gathering intelligence and defending U.S. computer security.

At this point I'd say it's pretty clear there is no tension between the two goals, because they only care about one of them, and it's not the 'defending US computer security' one.

They could not care less if every non-NSA system was breached, so long as they were able to continue grabbing as much data as they can.
[ link to this | view in thread ]
WaitWot, 15 Oct 2015 @ 7:27pm

They could've just asked...
If they wanted to see my porn they could've just asked...
[ link to this | view in thread ]
Uriel-238 (profile), 15 Oct 2015 @ 7:29pm

We don't know what encryption the NSA can crack.
It's unlikely they can crack it all. It's still unlikely they can crack most public-key encoded data, but our paranoia about it helps keep us aware of places we're getting lazy (e.g. using the same keys for too long)

It could be that they're confident that true quantum computing devices are imminent and they'll soon be able to derive private keys from public ones thanks to fast large-number-factoring that such technology would allow. There have been some recent developments of quantum computing tech, though the news I heard was of a prototype logic gate. I don't know how fast that will turn into a mainframe at the Big Utah Intelligence Center.

Generally, it's a good idea to not depend on one layer of protection to obfuscate your communication from the NSA or from law enforcement (or from competitors). When you have active enemies, you probably want redundant layers of data security. That way, even if they can crack your communications, it may be too expensive to do so consistently.
[ link to this | view in thread ]
Anonymous Coward, 15 Oct 2015 @ 8:08pm

Re: What's the point of encryption?
Its pointless to have a safe phone-line if they bug the room you know.
If that were true, they wouldn't need to spend so much money to break crypto. (Or maybe that's what they want us to think.) Anyway, it's the duty of all those who disapprove of their spying to make it as difficult as possible.
[ link to this | view in thread ]
Anon, 15 Oct 2015 @ 9:10pm

Re: Passing Keys?
According to my version of gpg (The open source version):

gpg (GnuPG) 1.4.16
Copyright (C) 2013 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Home: ~/.gnupg
Supported algorithms:
Pubkey: RSA, RSA-E, RSA-S, ELG-E, DSA
Cipher: IDEA, 3DES, CAST5, BLOWFISH, AES, AES192, AES256, TWOFISH,
CAMELLIA128, CAMELLIA192, CAMELLIA256
Hash: MD5, SHA1, RIPEMD160, SHA256, SHA384, SHA512, SHA224
Compression: Uncompressed, ZIP, ZLIB, BZIP2
[ link to this | view in thread ]
Pixelation, 15 Oct 2015 @ 9:45pm

What's needed
...is a dedicated effort to uncover them and any other insidious enemy of privacy.
[ link to this | view in thread ]
Anonymous Coward, 16 Oct 2015 @ 4:28am

Why crack when you can hack?
If the NSA wants to crack your encryption they just wait for you to order a new computing device. While being shipped your package is diverted to the NSA where they install backdoors.

If your device already contains pre-hacked electronic components or software then their job is already done and all your communique belong to NSA.
[ link to this | view in thread ]
Bamboo Harvester (profile), 16 Oct 2015 @ 7:18am

pre-factored primes
What I got from the story was that the real problem is that many communications use the SAME primes.

If you've already cracked the first 142 digit prime, *any* encryption using that same prime is now tremendously easy to crack (if you've got the gear, and the NSA apparently does).

My assumption is they've got a bank of unique-task machines chewing their way through 512, 1024, 2048, etc bit primes to build comparison tables.
[ link to this | view in thread ]
Sampson (profile), 16 Oct 2015 @ 7:23am

Re: 'crack' a prime
If 2 prime numbers are multiplied together, it is very hard to find these 2 prime numbers from their product. e.g. 41 AND 83 are prime numbers. Their product is 3403. Given this product it is hard for a human to find the 2 prime factors. (multipliers). Now, in this case because we are only using 2 digit prime numbers a computer could solve this almost immediately. But the problem gets exponentially more difficult as the prime factors get larger and some would take a computer years to solve. This is why many encryption systems use very large prime numbers as factors:
Here is a link that explains how these prime factors are used to in Public Key Encryption methods.
http://www.livinginternet.com/i/is_crypt_pkc_work.htm
[ link to this | view in thread ]
John Fenderson (profile), 16 Oct 2015 @ 7:50am

Re:
There is never any such thing as perfect security, so the answer to this, as with all security questions, is "it depends". Security is a tradeoff.

For example, the amount of effort required to take advantage of this weakness ensures that it won't be used for blanket surveillance. You'd have to be of special interest to the NSA. Whether or not you are comfortable relying on being sufficiently uninteresting is a personal call. Only you can answer that question.

If you aren't comfortable, then there are other encryption scheme you can use that don't have this weakness (although they may be a bit less convenient). This isn't a weakness of encryption as a whole, just this particular type of scheme.
[ link to this | view in thread ]
John Fenderson (profile), 16 Oct 2015 @ 7:52am

Re:
"don't do your business on the internet"

If you're of that mindset, then you also need to avoid using the telephone (cell or landline) and third party service providers such as payment processors, etc.
[ link to this | view in thread ]
John Fenderson (profile), 16 Oct 2015 @ 7:54am

Re: We don't know what encryption the NSA can crack.
"Generally, it's a good idea to not depend on one layer of protection to obfuscate your communication from the NSA or from law enforcement (or from competitors). When you have active enemies, you probably want redundant layers of data security."

YES.

This is security 101. If you only have one line of defense, no matter what that defense mechanism is, then your security is woefully inadequate. Even if the attacker you're worried about isn't a government agency.
[ link to this | view in thread ]
John Fenderson (profile), 16 Oct 2015 @ 7:56am

Re: They could've just asked...
That doesn't let them plant kiddie porn on your system, though.
[ link to this | view in thread ]
Monday (profile), 16 Oct 2015 @ 8:05am

What the fu..
I got about five posts into this thread and realized it was about to get sticky, and above my pay grade. I'm studying up on this DF, and I'm thinking irrational numbers, and prime numbers, and other stuff. It all sorta flooded me at the same time, and I need to learn this stuff in more detail.

Thanks for all the posts TD readers!
[ link to this | view in thread ]
Anonymous Coward, 16 Oct 2015 @ 10:03am

Re: Re: 'crack' a prime
Sure, I get all that. So 83 is a prime number, what does it mean to crack it?
[ link to this | view in thread ]
Uriel-238 (profile), 16 Oct 2015 @ 10:38am

Re: Re: Re: 'crack' a prime
I think it means (I'm guessing here) to build a huge database of multiples with other primes so that it's a giant lookup table.

Since doing a search within that table will be significantly fast than computing factors, it serves as a shortcut if someone used 83 as one of their key primes.

That way, determining a private key from a public key that used 83 (or any of their cracked primes) would take hours or days instead of months or years.

Again, I'm guessing. IANAM
[ link to this | view in thread ]
Anonymous Coward, 16 Oct 2015 @ 12:21pm

Re: Re: Re: Re: 'crack' a prime
You're describing a rainbow table. I think if that's what they meant, they would have said that.
[ link to this | view in thread ]
Anonymous Coward, 16 Oct 2015 @ 12:36pm

This article is nothing but speculation. You have to realize that people who don't understand the issue are reading thing and go on to spread misinformation about encryption being cracked.

There has never been a recorded instance of anyone "breaking" encryption standards. Nothing in this article has sources or even credible evidence. Please stop.
[ link to this | view in thread ]
Uriel-238 (profile), 16 Oct 2015 @ 2:02pm

Rainbow table
I've never heard the term (but thank you for giving it to me!). It's possible that other less-math-savvy people may not know it either.

But also, even if they have rainbow tables doesn't mean that's their only inroad to cryptanalysis of public keys. Or of other standard cryptography algos.

It's probably better for us to assume The NSA is one step ahead until the its benefactors are actively complaining about how useless it is.
[ link to this | view in thread ]
Uriel-238 (profile), 16 Oct 2015 @ 10:42pm

They can only bug so many rooms
I suspect that if Microsoft were to indeed store everyone's keylogs that they'd have a massive storage problem similar to those that the NSA is trying to solve with their big Utah facility.

My guess is they'll probably have to triage data retention to the more interesting candidates. So like any other camouflage you just need to blend into the background noise.

And that is what you have when you're sucking in all the communications in the US: noise.
[ link to this | view in thread ]
Anonymous Coward, 17 Oct 2015 @ 4:09am

Re: They can only bug so many rooms
"I suspect that if Microsoft were to indeed store everyone's keylogs that they'd have a massive storage problem similar to those that the NSA is trying to solve with their big Utah facility."

For all we know, Microsoft may have an arraignment with the NSA for "storage" (wink wink).
[ link to this | view in thread ]
Anonymous Coward, 17 Oct 2015 @ 4:10am

Re: Too easy?
"Are we at the point where ROT-13 is the most secure because it's the least expected?"

I use double ROT-13.
[ link to this | view in thread ]
Anonymous Coward, 19 Oct 2015 @ 2:27pm

Re:
Nice try, NSA.
[ link to this | view in thread ]