NSA cracks encryption algorithms

[cheguevara]

So much for Secure Web Communications and Banking

The National Security Agency, working with the British government, has secretly been unraveling encryption technology that billions of Internet users rely upon to keep their electronic messages and confidential data safe from prying eyes, according to published reports based on internal US government do ents.

The NSA has bypassed or altogether cracked much of the digital encryption used by businesses and everyday Web users, according to reports in The New York Times, Britain's Guardian newspaper and the nonprofit news website ProPublica. The reports describe how the NSA invested billions of dollars since 2000 to make nearly everyone's secrets available for government consumption.

In doing so, the NSA built powerful supercomputers to break encryption codes and partnered with unnamed technology companies to insert "back doors" into their software, the reports said. Such a practice would give the government access to users' digital information before it was encrypted and sent over the Internet.

[ElNono]

For people that work with crypto, this isn't really news. There's still plenty of algos that work well (like elliptic curve + AES, etc) but the problem is that your average internet user relies on crypto managed by service providers (ie: SSL). With most providers handing out the private keys to the NSA, the whole thing becomes useless.

That said, if you need to communicate securely, PGP/GPG is still secure provided you use a 2048 bit key or larger, you use a strong password for the private key hide, and make sure a keystroke logger isn't running on your box...

[cheguevara]

For people that work with crypto, this isn't really news. There's still plenty of algos that work well (like elliptic curve + AES, etc) but the problem is that your average internet user relies on crypto managed by service providers (ie: SSL). With most providers handing out the private keys to the NSA, the whole thing becomes useless.

That said, if you need to communicate securely, PGP/GPG is still secure provided you use a 2048 bit key or larger, you use a strong password for the private key hide, and make sure a keystroke logger isn't running on your box...

But if what the article says is true, it won't matter, apparently AES or other algorithms might have been cracked already.(not to mention vendors like MS, etc might be giving NSA backdoors to their algos) The reality is algorithms might still be good to prevent "eavesdropping"

but if NSA singles out your data, I am pretty confident they would be able to crack it fairly easily. Hopefully I'm wrong

[ElNono]

But if what the article says is true, it won't matter, apparently AES or other algorithms might have been cracked already.(not to mention vendors like MS, etc might be giving NSA backdoors to their algos) The reality is algorithms might still be good to prevent "eavesdropping"

but if NSA singles out your data, I am pretty confident they would be able to crack it fairly easily. Hopefully I'm wrong

Actually, the fact that a couple of secure email services decided to shut down instead of installing a backdoor for the NSA tells you that the algos are fine. The problem is that big companies like Google or Microsoft are not going to close shop in order to make a stand to stuff like that. They'll just hand over the private key for their certificates to LE and move on (and probably charge them for the goods too).

There's nothing magical about encryption, heck almost all the algorithms are actually standard, public and available for everyone to peruse and cryptoanalyze. Everybody that works in crypto knows what algos have weaknesses, and what they are. Obviously, new algorithms are invented all the time, and scrutinized all the time. Even an algorithm like RSA, invented in the 70's is still secure, but everyone knows that a quantum computer can crack it using Shor, so you're better off transitioning to elliptic curve. It's actually what the NSA uses themselves (along with AES).

The biggest problem isn't with the algorithms themselves, it's normally with lousy implementation of such algorithms. The PS3 is a perfect example of that. They implemented all this secure system and skimped on the random number generator, which brought the whole thing down. Just amateur stuff.

One of our products meets NSA Suite B (http://www.nsa.gov/ia/programs/suiteb_cryptography/) standards, so I'm fairly familiar with this stuff.

[Axegrinder]

You post this , then turn around and act like its a ridiculous idea that the US did indeed intercept phone convos indicating that Assad forces used gas? Soldiers intercept Taliban chatter on a daily basis and you would be an utter fool to believe that the US has NOT been balls deep in surveilling Syria long enough to catch such a thing. And after the drubbing Bush got after the WMP fiasco in Iraq, do you REALLY believe this admin would willingly make that very same mistake by making up a story about these phone calls?

[cheguevara]

Actually, the fact that a couple of secure email services decided to shut down instead of installing a backdoor for the NSA tells you that the algos are fine. The problem is that big companies like Google or Microsoft are not going to close shop in order to make a stand to stuff like that. They'll just hand over the private key for their certificates to LE and move on (and probably charge them for the goods too).

There's nothing magical about encryption, heck almost all the algorithms are actually standard, public and available for everyone to peruse and cryptoanalyze. Everybody that works in crypto knows what algos have weaknesses, and what they are. Obviously, new algorithms are invented all the time, and scrutinized all the time. Even an algorithm like RSA, invented in the 70's is still secure, but everyone knows that a quantum computer can crack it using Shor, so you're better off transitioning to elliptic curve. It's actually what the NSA uses themselves (along with AES).

The biggest problem isn't with the algorithms themselves, it's normally with lousy implementation of such algorithms. The PS3 is a perfect example of that. They implemented all this secure system and skimped on the random number generator, which brought the whole thing down. Just amateur stuff.

One of our products meets NSA Suite B (http://www.nsa.gov/ia/programs/suiteb_cryptography/) standards, so I'm fairly familiar with this stuff.

yeah, an NSA algorithm is probably the last algorithm I'd use

I agree the open standard algorithms are probably the safest, but like you said 90% of users will use an implementation from a 3rd party which is more likely compromised by the NSA.

and in the end, it's all math and computations, any algorithm can eventually be broken with the right amount of computing power. And the NSA has billions to get such power

[ElNono]

yeah, an NSA algorithm is probably the last algorithm I'd use

I agree the open standard algorithms are probably the safest, but like you said 90% of users will use an implementation from a 3rd party which is more likely compromised by the NSA.

Well, AES is well studied and actually an open standard algo (previously known as Rijndael). It's a permutation algorithm, so there's no actual intractable math involved there (like in elliptic curve or RSA).

As far as compromised providers, from what's been published, that PRISM program is very likely exactly that.

and in the end, it's all math and computations, any algorithm can eventually be broken with the right amount of computing power. And the NSA has billions to get such power

Brute forcing AES-256 takes 10 quadrillion years. Even if you had 1 billion orders of magnitude more computing power, you would still be in the trillion years range. In other words, if you don't have the key, you won't break it.

It's just cheaper for them to eavesdrop the message on either end, which is very likely what they do.

There's a plethora of ways to "break" encryption that doesn't involve breaking the algo. From trojans and keyloggers to thermal cameras, etc.

[TDMVPDPOY]

elnono all that u mention isnt useful for the avg user unless you got some to hide....

[ElNono]

elnono all that u mention isnt useful for the avg user unless you got some to hide....

Well, that's exactly what I was pointing out...

the problem is that your average internet user relies on crypto managed by service providers (ie: SSL). With most providers handing out the private keys to the NSA, the whole thing becomes useless.

There are ways to still communicate securely, but you need to know what you're doing.

This is no knock on cheguevara, because he didn't write the OP, but that sort of article is kinda fluffy, that's all.

[ElNono]

This is actually a quote from Snowden himself:

“Properly implemented strong crypto systems are one of the few things that you can rely on,” he said, though cautioning that the N.S.A. often bypasses the encryption altogether by targeting the computers at one end or the other and grabbing text before it is encrypted or after it is decrypted.

[TDMVPDPOY]

This is actually a quote from Snowden himself:

“Properly implemented strong crypto systems are one of the few things that you can rely on,” he said, though cautioning that the N.S.A. often bypasses the encryption altogether by targeting the computers at one end or the other and grabbing text before it is encrypted or after it is decrypted.

only way for the g ovt to crack it is on the user end with a key logger even b4 the message/text is sent/deleted....ISP/server side or through those international lines that links the web teh govt could always shut it down if it wanted....

[xrayzebra]

Want secure communications, use a one time code. Slow but reliably secure.

Problem I see with NSA's programs is that they are intercepting so much stuff that they can't possibly process it all. Japanese made the same mistake during WWII.

[boutons_deux]

"intercepting so much stuff that they can't possibly process it all."

"big data" experts are in HUGE demand right now, name your salary, by corps and govt, to figure out how/if to handle "big data".

anybody seen any tea bagger demonstrations against govt/corporate surveillance?

[cheguevara]

Well, AES is well studied and actually an open standard algo (previously known as Rijndael). It's a permutation algorithm, so there's no actual intractable math involved there (like in elliptic curve or RSA).

As far as compromised providers, from what's been published, that PRISM program is very likely exactly that.



Brute forcing AES-256 takes 10 quadrillion years. Even if you had 1 billion orders of magnitude more computing power, you would still be in the trillion years range. In other words, if you don't have the key, you won't break it.

It's just cheaper for them to eavesdrop the message on either end, which is very likely what they do.

There's a plethora of ways to "break" encryption that doesn't involve breaking the algo. From trojans and keyloggers to thermal cameras, etc.

so let's say someone is making an application with end-end encryption. Would you say using Microsoft algorithm (AES 2K) is pretty much unbreakable, even to NSA?

there are 3 possible vulnerabilities:
- NSA brute force attack
- NSA using a Microsoft backdoor?
- NSA using their "supercomputer" which broke the algorithm itself?

IMO the 1st one is real, the 2nd one is very likely and the 3rd? not sure...

[cheguevara]

Want secure communications, use a one time code. Slow but reliably secure.

yes, also use an autodestruct function. Don't save anything on servers.

Problem I see with NSA's programs is that they are intercepting so much stuff that they can't possibly process it all. Japanese made the same mistake during WWII.

good point. That is why I said encryption is very good at preventing eavesdropping. There is no way NSA can decrypt every single encrypted communications that goes on a daily basis

[ElNono]

Want secure communications, use a one time code. Slow but reliably secure.

Doesn't work for modern communications. Plus one time codes require the other party to know information beforehand, which is also subject to eavesdropping.

Problem I see with NSA's programs is that they are intercepting so much stuff that they can't possibly process it all. Japanese made the same mistake during WWII.

They don't have to. They just need to store it to query it for the specific data they want to mine. They don't effectively focus on all the data. They just dump it on a big bad distributed database, and when they look up John Doe, they can see what's he been up to, who he talked to, who those people talked to, etc. It's not much different than a people's Google search. Google doesn't look at all the data, it just takes it in, classifies it, and stores it. When you actually do a query, it starts associating stuff. Almost all big data works the same way.

so let's say someone is making an application with end-end encryption. Would you say using Microsoft algorithm (AES 2K) is pretty much unbreakable, even to NSA?

there are 3 possible vulnerabilities:
- NSA brute force attack
- NSA using a Microsoft backdoor?
- NSA using their "supercomputer" which broke the algorithm itself?

IMO the 1st one is real, the 2nd one is very likely and the 3rd? not sure...

Microsoft doesn't have an algorithm themselves, they implement and use standard algos. The good thing about standard algos (especially on block-ciphers, like AES) is that you can't install a backdoor on them or weaken them. If you try to do that, the output of the algo will change, and effectively make it no longer AES and something the recipient of the encrypted data cannot decrypt.

The last time the NSA tried to standardize a 'weak' algo, it got caught pretty much right away (https://www.schneier.com/blog/archiv...range_sto.html). This stuff is scrutinized a lot, and weaknesses are found and published pretty quickly.

As far as your list, 1 and 3 are the same. That's what you use "supercomputers" for, brute forcing your way to finding the encryption key. On well implemented strong crypto, not possible. Again, we're talking trillion of years to go through the key space.

As far as backdoors, sure. Not in the algo itself, but if you rely on routines by a vendor like Microsoft, what they could do is install a backdoor on the OS itself. When you think you're passing the encryption key and data to the algorithm, it could actually re-route it and store the key, then run the regular algorithm. That's called a man in the middle attack. Well known stuff. The way to properly secure your data is not to use vendor routines (again what I was pointing out, don't rely on service providers). The source code for AES is widely available (http://gladman.plushost.co.uk/oldsite/AES/index.php) and you can compile a version you know it's secure in no time.

The problem is that vendors are one of lazy, subservient or they're forced by law enforcement to install such backdoors. That's what happened to those secure email services and they decided to shut down the doors instead of proving a backdoor. But companies like Microsoft, Google, etc won't do that for obvious reasons.

[xrayzebra]

Quote Originally Posted by xrayzebra
Want secure communications, use a one time code. Slow but reliably secure.
Doesn't work for modern communications. Plus one time codes require the other party to know information beforehand, which is also subject to eavesdropping.

Not necessarily, many ways to use pen and paper. Especially using poly alphabetic subs ution. Many unbroken codes. About mining, yes you can have programs that scan all messages for key words, phrase, names and places, but those are easily defeated.

Famous Unsolved Codes and Ciphers

http://elonka.com/UnsolvedCodes.html

Besides, even if a code is breakable, so long as it defeats being deciphered for a period of time, until the deed is done or accomplished, it has accomplished what was was needed. Secrecy.

[ElNono]

Quote Originally Posted by xrayzebra
Want secure communications, use a one time code. Slow but reliably secure.
Doesn't work for modern communications. Plus one time codes require the other party to know information beforehand, which is also subject to eavesdropping.

Not necessarily, many ways to use pen and paper. Especially using poly alphabetic subs ution. Many unbroken codes. About mining, yes you can have programs that scan all messages for key words, phrase, names and places, but those are easily defeated.

Famous Unsolved Codes and Ciphers

http://elonka.com/UnsolvedCodes.html

Besides, even if a code is breakable, so long as it defeats being deciphered for a period of time, until the deed is done or accomplished, it has accomplished what was was needed. Secrecy.

Those are subs ution ciphers. Algorithms like AES are actually an improvement over those, since you don't need a full alphabet, only a shared key.

What's known in cryptography as "one time code" is:

One-time code

A one-time code is a prearranged word, phrase or symbol that is intended to be used only once to convey a simple message, often the signal to execute or abort some plan or confirm that it has succeeded or failed. One-time codes are often designed to be included in what would appear to be an innocent conversation. Done properly they are almost impossible to detect, though a trained analyst monitoring the communications of someone who has already aroused su ion might be able to recognize a comment like "Aunt Bertha has gone into labor" as having an ominous meaning. Famous example of one time codes include:

- "One if by land; two if by sea" in "Paul Revere's Ride" made famous in the poem by Henry Wadsworth Longfellow
- "Climb Mount Niitaka" - the signal to Japanese planes to begin the attack on Pearl Harbor
- During World War II the British Broadcasting Corporation's overseas service frequently included "personal messages" as part of its regular broadcast schedule. The seemingly nonsensical stream of messages read out by announcers were actually one time codes intended for Special Operations Executive (SOE) agents operating behind enemy lines. An example might be "The princess wears red shoes" or "Mimi's cat is asleep under the table". Each code message was read out twice. By such means, the French Resistance were instructed to start sabotaging rail and other transport links the night before D-day.
- "Over all of Spain, the sky is clear" was a signal (broadcast on radio) to start the nationalist military revolt in Spain on July 17, 1936.


Agree about time-sensitive encryption, but it's utility is also severely limited. Highly sensitive data will be scrutinized, even if expired, and the last thing you want is to rely on a weak, non cryptoanalyzed cipher.

[DMC]

If the NSA wants to find out who's troll belongs to whom here, more power to them. I cannot imagine most of you worthless s are of any interest to them otherwise, and pretending you are is really pushing the envelope on make believe.

[cheguevara]

As far as your list, 1 and 3 are the same. That's what you use "supercomputers" for, brute forcing your way to finding the encryption key. On well implemented strong crypto, not possible. Again, we're talking trillion of years to go through the key space.

disagree, 1 and 3 are not the same. Brute force is just a method of breaking a piece of encrypted data. What I'm referring to #3 is creating a supercomputer that will eat the algorithm itself and spit out a boiler plate that can somehow reverse engineer whatever that algorithm produces. Again. Its all math. With enough computing power, this is possible. It goes along the lines of making a computer as smart as a human, look at big blue project.

As far as backdoors, sure. Not in the algo itself, but if you rely on routines by a vendor like Microsoft, what they could do is install a backdoor on the OS itself. When you think you're passing the encryption key and data to the algorithm, it could actually re-route it and store the key, then run the regular algorithm. That's called a man in the middle attack. Well known stuff. The way to properly secure your data is not to use vendor routines (again what I was pointing out, don't rely on service providers). The source code for AES is widely available (http://gladman.plushost.co.uk/oldsite/AES/index.php) and you can compile a version you know it's secure in no time.
.

yes this might work with PC. But Windows 8(mobile) now has the Windows RT which you cannot compile your own code. You HAVE to use their libraries. I'm sure it's the same with Apple iOS. so that's not an option. Android might be possible but you probably would have to jailbreak the device. so nowadays that's not really an option.

[cheguevara]

“It should hardly be a surprise that our intelligence agencies seek ways to counteract our adversaries’ use of encryption,” read the statement issued Friday. “Throughout history, nations have used encryption to protect their secrets, and today, terrorists, cyber-criminals, human traffickers and others also use code to hide their activities.”



translation: if encryption were a gun, we'd have taken it away from US citizens a long time ago....

[cheguevara]

"and others"

that basically means anyone who uses encryption

the whole point of encryption is to hide and protect activities you crazy ing nazi

[TDMVPDPOY]

"and others"

that basically means anyone who uses encryption

the whole point of encryption is to hide and protect activities you crazy ing nazi

so why isnt the US govt using it? why are they always gettin hack and losing private information to the chinese hackers who steal ur ideas and technology to go produce it at a cheaper rate and on the market ready to be sold...

[ElNono]

disagree, 1 and 3 are not the same. Brute force is just a method of breaking a piece of encrypted data. What I'm referring to #3 is creating a supercomputer that will eat the algorithm itself and spit out a boiler plate that can somehow reverse engineer whatever that algorithm produces. Again. Its all math. With enough computing power, this is possible. It goes along the lines of making a computer as smart as a human, look at big blue project.

I guess it's difficult to explain to the average person, but you don't need a supercomputer for that. You have the source code to the algo, there's nothing to reverse-engineer. You can run it back and forth, examine the internal state, etc. That's how algorithms are analyzed for leaking key bits, vulnerabilities, etc. In the case of solid algorithms, it is math and the missing variable is the key.

The fact that they have to reach out to service providers to obtain the keys should really tell you all you need to know.

It's much easier and cheaper to simply try to find vulnerabilities on the applications themselves (which I'm sure they do)

yes this might work with PC. But Windows 8(mobile) now has the Windows RT which you cannot compile your own code. You HAVE to use their libraries. I'm sure it's the same with Apple iOS. so that's not an option. Android might be possible but you probably would have to jailbreak the device. so nowadays that's not really an option.

Well, I'm sorry to disappoint, but I develop for all 3, and that's really not the case at all. I'm not even sure where you heard you cannot compile your own code. If you want to use any built-in hardware accelerated encryption engines, you can. If you don't, you can too. If you don't want it in bytecode, you can compile in native code. I know for a fact since our product doesn't use the built-in crypto at all for that exact reason.

That's not to say that the NSA isn't aware of all the software out there. The way it works here in the US, if you want to sell a product like ours, you have to go through a lot of hoops. You first have to obtain an export license from the department of commerce, which lets you sell the product (and you have to comply with not selling it to certain countries on a list), and also fill out a form every year and send it to the NSA. So if the NSA has a "person of interest" using your product, they know where to send the NSL to. Obviously, I can say that because we haven't received one (yet).

[cheguevara]

I guess it's difficult to explain to the average person, but you don't need a supercomputer for that. You have the source code to the algo, there's nothing to reverse-engineer. You can run it back and forth, examine the internal state, etc. That's how algorithms are analyzed for leaking key bits, vulnerabilities, etc. In the case of solid algorithms, it is math and the missing variable is the key.

"average person" what does that make you, Einstein?

The concept is pretty simple, there is nothing rocket science about understanding the concepts of algorithms and "breaking" an alogrithm. Here I'll explain it to you in simpler fashion:
An algorithm that is "broken" here means that there is a published attack that is computationally faster than a brute force attack.

to say that the current State of the Art Encryption algorithms are "unbreakable" is pretty naive, given that algorithms get broken on a daily basis. Again all you need is the computing power and engineers developing set of methods to break it. Again breaking means being able to decipher codes in relative "fast" fashion. the point of the thread is it seems NSA has probably broken most if not all.

The fact that they have to reach out to service providers to obtain the keys should really tell you all you need to know.

well good luck believing that. The fact that they ask for keys has absolutely nothing to do with the fact that they could be working on ways to circunvent that. It's like saying "why is that cop asking for my license if he is going to identify me anyway?"

Well, I'm sorry to disappoint, but I develop for all 3, and that's really not the case at all. I'm not even sure where you heard you cannot compile your own code. If you want to use any built-in hardware accelerated encryption engines, you can. If you don't, you can too. If you don't want it in bytecode, you can compile in native code. I know for a fact since our product doesn't use the built-in crypto at all for that exact reason.

cool, I'll look into this