Has the NSA really broken “strong” encryption?

[DanTex]

http://www.pcpro.co.uk/blogs/2013/09/06/has-the-nsa-really-broken-strong-encryption/

It’s been reported that GCHQ and the US National Security Agency have managed to crack the encryption systems we use to protect emails, personal data and financial transactions. If this means HTTPS, SSL and so forth are no longer secure, it’s a huge deal. You may not be immediately alarmed about the idea of spy agencies accessing your supposedly private data, but if they’ve found a technique for getting around strong encryption, it could sooner or later find their way into less well-meaning hands.

Frustratingly, however, we don’t know the specifics of what’s really been broken. The original report in The Guardian – based on revelations from US whistleblower Edward Snowden – describes specific intelligence programmes; but the central allegation rests on a mysterious “breakthrough”, of which no details are provided.


Cracking the code?

In truth, it seems unlikely that the NSA has found a quick way to decrypt files protected by an industry standard algorithm such as AES and RSA. These systems are used precisely because, so far as any mathematician has been able to prove, the only way of finding a decryption key is by trial and error. If anyone were able to discover a quick way of doing it, it would be huge news, not just for the encryption industry, but for mathematics as a whole. It’s very unlikely that such a discovery might have been made in secret.

So that leaves the brute-force approach – and even for the NSA, with its comparatively vast computing resources, this simply isn’t practical. With a 256-bit key system, the number of possible combinations is approximately 115,792, 089,237,316,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000. I don’t care how many billions of dollars you throw at the problem, when you’re up against those odds for every single message or file you want to read, you’re not going to be able to keep up. Snowden himself has previously affirmed that “properly implemented strong crypto systems are one of the few things that you can rely on”.

...

[Manifestor_of_Light]

1. What about using a proxy server?

So they don't know where it comes from, allegedly???

Does that help?

[longship]

2. Well, the algorithms are pretty simple.

They depend on "trap door" equations, ones that have no analytical inverse solution. An example is the product of two large prime numbers. It is not possible to factor a very large number except for exhaustive search. Such facts are used to design these trap doors.

By increasing the length of keys one can make these algorithms arbitrarily secure, meaning that the ability to crack a shorter key doesn't mean one could crack a longer one in any reasonable length of time even with huge computer resources (like the NSA).

These are the principles that make strong encryption so secure. It is not reasonable to claim that they are not safe. And there are plenty of people whose jobs are to insure their continued security.

[Silent3]

3. I'm very skeptical about this too, but a possibility I can imagine...

...(if I were to put my tinfoil hat on) is that the NSA (or other government agency) has somehow influenced code commonly used to generate encryption keys such that the solution space one needs to search is significantly smaller than you'd get have to deal with if key generation used purely random factors.

[GoneFishin]

4. I think you are on the right track. In cases where they could not actually crack

the encryption they paid money or otherwise influenced the companies to leave vulnerabilities for them to exploit.

[Egalitarian Thug]

6. Agreed. I think that, if such cracks exists, they will be primarily implemented through

cooperative hardware, not a brute force break.

[Aerows]

19. Yep

Cooperative hardware.

[DanTex]

7. It would be something like that.

To have actually cracked the encryption the "hard way" they would have had to outsmart the entire world's mathematical community, which is highly doubtful. But I can easily see them influencing commercial encryption implementations in order to make them easier to crack, for example in the way you describe.

[Aerows]

21. Hardware cracks.

They are far easier.

[longship]

8. Well, maybe. But...

Many computers today have noise circuits in them for generating random numbers. OS like Linux can access these as part of their kernels. I am not sure how prevalent this is now. It's been a few years since I've been involved deeply. But the Linux kernel still has the random device.

When one generates a new key pair for public key crypto such a device is used along with another source, for instance typing on a keyboard, to generate the keys. There is no way with an open source software that the NSA can get in to influence such key generation since it can be done while disconnected from the Net and the source code can be checked (and IS checked).

As far as proprietary software, I don't think many companies would put their clients at risk by deliberately building insecure crypto software, even at the request of the NSA. If I were lead tech, I would tell NSA to get bent. The chance that it would get leaked out is too great and then clients using the software would be open to exploit. Imagine if the client was the US Federal Reserve Bank, for instance. Or, a large state bank somewhere.

I think strong crypto is secure.

Good post, though. Interesting to ponder these things.

[DanTex]

9. My basic thought (hope) is that with open source you're safe.

The problem with commercial vendors is that the government could go to them and force them to put in a backdoor and also force them not to tell anyone about it. If I were lead tech, I would also want to tell the NSA to get bent, but then I would probably find myself out of a job, and also with a gag order that would send me to prison if I told the press.

I think the real issue, though, is not breaking the crypto, but how easy it is to get trojan horses. Even with open source. I've installed who knows how many packages. Yes in theory, they're open source, and malicious code would have been found by "thousands of eyes", but in reality who's to say the NSA hasn't put in a few obfuscated lines of code somewhere in there.

[longship]

14. Yup, always a danger.

That's why a lot of eyes on the code are a good idea. The more, the better.

Also, install only from known secure sites so no Trojans can be snuck into the code.

I started Linux with Slackware 2.x (can't remember, it was an early 2.x) in the mid 90's. I've used SuSE, Debian, Gentoo, and Ubuntu. So, I've had a lot of experience with Linux. Now I stick with Ubuntu, but my big box is an older Gentoo AMD 64 twin core. Runs like a dream.

[Aerows]

11. If computer generated random numbers

are an argument, we are doomed. Particularly with elliptical.

Constants are notoriously easy to penetrate, and random has never meant random in machine language due to the fact that it is possible to track the generation of a "random" constant.

[longship]

16. Well, you've got to generate the key somehow.

And I don't know how the NSA can sneak into my machine to force a key. I mean, they aren't magic.

Please expand what you're saying as I am unsure of what that is.

[Aerows]

18. Pseudo random

has always been a problem.

[longship]

22. Agreed.

How does one insure a large cycle size? Eventually all pseudo random number generators must repeat their cycles. I played with them per Knuth once and realized how bad the problem could be.

I would hope they've solved that problem by now.

Linux has /dev/random but I am no kernel expert. I presume it is meant to connect to hardware RNG, like a noise circuit, or a very fast clock. I haven't built a computer in a few years, so I don't know if it connects to anything on my current boxes.

But I have little need for strong encryption these days. When I was in the business, I used it all the time. I've not kept up on things for a couple of years, but I was pretty deep into things for some time.

Thanks for your response.

[Aerows]

24. Many do, though

that's why it is a hotly debated topic and harshly enjoined decision.

You are obviously more involved and informed. That's why I ask.

[Aerows]

25. You and Dan rock

I am eating the worst pizza in the history of pizza, but I'm starving.

EDIT: Aerows, ate the worst pizza ever made by mankind, ate it, survived, and lived to complain about it. Vomiting may occur.

[DanTex]

26. I was under the impression that /dev/random is pretty good.

I think it grabs some "truly random" bits (from somewhere) and expands them into more pseudorandom bits in a "good" way. So obviously I'm not an expert here but that was my impression.

[longship]

29. I thought it was hardware, if MoBo has it.

On the MoBo they put what is just a noise circuit -- a diode of some kind or something like that which spits out random noise. All one does is read bits off the noise somehow. Voila! You have your random element. (Or something like that.) One could also get a random seed from the least significant bytes of a very fast clock.

There's provisions for such a thing in the kernel when one compiles it, or as a kernel library on precompiled kernels. That's what gives you /dev/random AFAIK.

One would have to look at ones MoBo spec to see if it has one of these and I haven't done that in years. I am kind of out of things these days. My info may be out of date.

[hunter]

5. No, but most people's home and work computers have been broken.

Me, I don't give a shit. I always do my best to say what I mean.

[Aerows]

10. If you think they haven't "cracked" (read: back door) commercial encryption

I have bridges to sell you. Proprietary code is notorious for containing things that you would rather it didn't.

[DanTex]

12. How about open source?

Have they cracked the actual protocols, or just forced commercial vendors to put in back doors? An important question IMO.

[Aerows]

13. That's where I see our safety and salvation

Everyone can examine the source and can compile their own. If you have the source, and you control the compile, you control the code.

Maybe I'm naive, but that is my thought, anyway.

[DanTex]

15. I tend to agree. I run open source (mostly).

But here's the thing. I'm a computer/math type, and I certainly don't read close to 1% of the source that install. In fact, I've read 0% of the Linux kernel. Who's to know if the NSA has snuck in some obfuscated backdoor? Certainly not me.

[Aerows]

17. "I've read 0% of the Linux kernel"

Why not? It's kind of important to know what you are deploying on a system.

It's kind of like a doctor proudly declaring that he's not read any of the Merck resource on drugs because he'd know if they caused a reaction.

Don't get me wrong, I'm not kicking you for being so certain of such things, but I guess I'm not the same. I will plow deep into the things that I compile to use them to the best of my ability. Best of my ability.

[DanTex]

20. I agree with you. It's just one of those things, like going to the gym more...

Believe, me, understanding the Linux kernel better is on my list, but it just never reaches the top.

Regarding being "certain", I hope I didn't give the wrong impression. I actually feel fairly uncertain. I kinda sorta hope that some other people (like you) are looking at the open-source software I install and making sure it works and is safe, but my point is that I haven't personally made sure of that, and I'm someone who actually could if I really wanted to. Most open-source users wouldn't have the technical knowledge to read the source even if they wanted. And even if I read a few percent of the source, which would take a very long time, I still would be very far from being able to spot some malicious code.

My point is that even with open source, we are (or at least I am) still relying on the "thousand eyes" to make sure things are right, as opposed to my own eyes.

[lpbk2713]

23. No problem.

Not as long as I have my decoder ring.

[devils chaplain]

27. Absolutely NO, although they might want you to think that...

They can't decrypt strong encryption. What they've achieved is success in twisting the arms (or perhaps gently nudging) corporations into including back doors in their proprietary encryption software. Open source stuff such as OpenPGP and Truecrypt are still uncompromised.

[whttevrr]

28. Two questions...

First, how many pages would the average program print out if you printed out the source code?
For instance: How many pages of text would the Linux kernel be?

Second, what if the 1,000 eyes were only a few handfuls of something or other?
Because 1,000 eyes implies 500 people scouring every page of code tirelessly every day... when actuality probably gets us maybe a few dozen looking at some choice areas?

amiright?

[MineralMan]

30. You are right, yes.

[whttevrr]

31. but...

I don't want to be.

You were supposed to come back with a retort about 1000 nerds, locked in a mothers basement, reading every single line of code that ever gets compiled.

Thanks...

Now my weekend is ruined...

You suck...








LOL J/K just kidding.

kinda...

[MineralMan]

32. I know, but news is often bad.

Sorry. You have it right about open source code. It gets looked at, but mostly by people not competent to write it. So malicious, but well hidden stuff would get missed.