NSA Infiltrated RSA Deeper Than Imagined

Rambo Tribble (1273454) writes "Reuters is reporting that the U.S. National Security Agency managed to have security firm RSA adopt not just one, but two security tools, further facilitating NSA eavesdropping on Internet communications. The newly discovered software is dubbed 'Extended Random', and is intended to facilitate the use of the already known 'Dual Elliptic Curve' encryption software's back door. Researchers from several U.S. universities discovered Extended Random and assert it could help crack Dual Elliptic Curve encrypted communications 'tens of thousands of times faster'."

Comments

Sales plummeted

[spacepimp]

I can only hope that this sort of bullshit maneuver by RSA reflects both globally and in the USA with respect to sales. Name one Government willing to buy this equipment any longer? 10 M compared to what they're going to lose now is nothing.

Re:Sales plummeted

[Anonymous Coward]

I can't imagine why anybody anywhere would ever invest in proprietary crypto software.
The risk is too great to just take your vendor's word.

Re:Sales plummeted

[NatasRevol]

So your solution is what? Build your own crypto software?

Should every company and person wanting to have encrypted communications do this too?

Do you trust your compiler? Or your hardware?

Re:Sales plummeted

[Anonymous Coward]

So your solution is what? Build your own crypto software?

Use open source implementations of the established standard algorithms, with many eyes on them.

Should every company and person wanting to have encrypted communications do this too?

Yes. Proprietary software should have zero market share in this area. It's too important.

Do you trust your compiler? Or your hardware?

Yes, I do, but you don't have to.
If you're very very paranoid, use the "countering trusting trust" techniques.

Re:Sales plummeted

[ron_ivi]

why anybody anywhere would ever invest in proprietary crypto software.

People forced by their customers to buy off of this list (i.e. people who sell to the federal government):

http://csrc.nist.gov/groups/ST...

Sure there are a couple F/OSS groups that paid the pretty significant cost to get a certificate. But not that many, especially when it comes to networking products.

Re:Surprise surprise, they lied and it's still the

[interkin3tic]

I'm guessing it's because they honestly believe what they are doing is necessary to keep America safe. To the point that they think lying to the people who are supposed to be overseeing them is necessary for the greater good.

Which is terrifying. Give me all the cynical, greedy, lying, corrupt asshole politicians you want. Just please, don't put zealots in power.

Desensitizing the masses

[wjcofkc]

I can't help but wonder...

When the acts of the NSA first came to light as we now know them, there was outrage not just from the tech sector, but from the general population as well. As these stories continue coming at a steady and regular pace, I still see outrage over the infringement of our rights - and the understanding of the general slippery slope creepiness of it - from those technically inclined. But less and less are the major outlets making a fuss, and even when the general population catches wind of each new story it is increasingly met with a sarcastic, "Gee, didn't see that coming." and a shrug of the shoulders. Is the possibility of a tipping point in favor of our rights being eliminated be the increasing apathy of the greater people toward these issues? I suspect we are on the losing side. I suspect that as the stories come out, and people in general not only become desensitized - but worse, it becomes the norm. In becoming the norm it will balloon to scales and scopes unimaginable. I feel we will reach a point where the majority of people will have forgotten that it was ever any other way. Even as it continues to get worse, they will continue to forget.

Re:Desensitizing the masses

[wiredlogic]

It is unfortunate that the popular media does what it does these days and ignores "boring" news in their chase to find the next hot story. Still, this is an election year and the Snowden revelations will likely come back to the foreground as candidates pander for votes, especially with the GOP fractured, having no real consensus on how to sell themselves.

Re:Desensitizing the masses

[neiras]

Government organizations like the NSA are playing a long game. If one generation is desensitized, the next will be uncaring as long as basic needs and a sense of freedom are preserved.

They are winning, and even if we form long-lived organizations to fight them on their terms they will undermine until those organizations are publicly ridiculed and useless. Individuals who speak up will be tarred as "activists", "protestors", and later "traitors". They have the upper hand and there's no way to get it back without an actual war, which no one wants.

They are winning.

This began a long time ago. In two generations they will have won.

Re:Desensitizing the masses

[Anonymous Coward]

You could write a series of books on why this occurs but in a nutshell it comes down to this:

What are you (we) going to do about it?

Sure "we" could all get together an elect people to "fix" things. That will never happen. Your special interest isn't the most important thing to everyone and most people vote based on a few select issues. Making sure this issue is everyone's core issue is impossible. Gay rights, women rights, abortion, religion, gun rights, taxes, welfare, etc are generally more important to those affected. Candidates can't run on only one issue so they must decide their stance or non-stance on each issue. Each of these decisions will alienate voters. The system creates two parties that bicker and can only focus on a few problems at a time. These problems are highly influenced by what the media focuses on. Read into that what you want.

Re:Desensitizing the masses

[Aighearach]

The pendulum swings both directions. I recommend thinking bigger.

Re:Desensitizing the masses

[Jiro]

Reeasing things in dribs and drabs has benefits, though. It probably keeps the public's interest more than releasing the whole thing as a lump; even if public interest is down because of exhaustion, it's probably not as far down as it would be if nothing had been released in a year.

The other reason is that it makes it harder for the government to lie. If you release a document, the government can't lie and deny it because they don't know that maybe tomorrow you'll release a document that could expose the lie. If you release the whole thing in a lump, they could just carefully tailor the lie to match the existing releases.

Thank goodness for open-source alternatives

[mrflash818]

So those that know how, can test and verify open-source alternatives are cryptographically secure, not back-doored, and safe for people to use.

Re:Thank goodness for open-source alternatives

[cryptizard]

Open-source doesn't help for shit in this situation. Dual_EC_DRBG was an open standard, all the details were public. The problem is that, with cryptographic algorithms, only a handful of people in the entire world are qualified to say whether something might or might not be secure. And even if there is a problem, it might go for years without being found.

Re:Thank goodness for open-source alternatives

[jandrese]

For what it is worth, people who know the math thought Dual_EC_DRGB smelled funny from the first time it was announced, although it was impossible to prove if it was actually compromised or not. Combined with the fact that it's much slower than its competitors (and low speed is not a virtue in a RNG like it is in a crypto alg) and you have something that was only used by people who were explicitly told to use it.

Re:If you can't beat 'em, join 'em

[TheCarp]

How? Easy for me, I was alive and paying attention.

The problem wasn't so much that good tools from American sources were unavailable, they were just subject to onerous restrictions, that made it hard to distribute. So producers of software were stuck either producing an "international" version which was easy to distribute and download, but had restrictive key length limits and a seperate, harder to download version for the US.

So yes, European tools were generally better, because they were not under such restrictions, and worked just fine in or outside the US. A lot of people in the US even used pgp "international" version just because it was easier.

It really was little more than a lame attempt to stuff a genie back in a bottle; after the bottom was smashed off. The ONLY thing it served to do was make the US into a laughing stock.

Times have changed

[PvtVoid]

Remember when the NSA was secretly changing widely-used crypto algortithms to make them stronger? I'm thinking of the DES sbox and differential cryptanalysis.

One thing's for sure, RSA is toast. They can issue all the denials they want. Nobody's ever going to trust them again.

Re:Times have changed

[MisterBlue]

I think this is the basis of Snowden's disagreement with the NSA -- the NSA could have taken a defensive mode and worked to make the country and its people more secure but it instead took an offensive mode and made crypto-weaker and found software bugs and used them to break in rather than working to have them fixed. The long term effect if this choice is a less secure country and a country with a shit reputation.

Re:Surprise surprise, they lied and it's still the

[fuzzyfuzzyfungus]

Anyone who falls into that belief might as well be written off and put up against the wall, second in line to the people who believe that their own possession of arbitrary power is the only way to ensure the nation's safety. They can go first.

Mole in Mozilla / "Eric Rescorla" ?

[burni2]

I think Mozilla needs to be cleaned of moles and it seems "Eric Rescorla" is one of them, and look where he is active:

https://tools.ietf.org/html/dr...

-- snip from reuters story -- .. Information Assurance Directorate, and an outside expert named Eric Rescorla.

Rescorla, who has advocated greater encryption of all Web traffic, works for Mozilla, maker of the Firefox web browser. He and Mozilla declined to comment. Salter did not respond to requests for comment.
-- snip --

Re:we must end this jewish problem once and for al

[Ziest]

America today is NOT the country my ancestors fled Eastern Europe for nor is it the country my wife and I grew up in. America is now a country run for the benefit of the wealthy, the privileged and the corporations. The CIA, NSA, FBI, DEA, etc. now exist to keep the powerful in charge and to detect and eliminate any movement that will challenge the status quo. Google "Green is the new Red"

Re:If you can't beat 'em, join 'em

[fustakrakich]

So yes, European tools were generally better, because they were not under such restrictions...

Yes, they are better than the crippled exportable versions, but you still don't know if they've been compromised. You are speculating. Unless you have some kind of security clearance, you don't know as a fact if all publicly available encryption doesn't have a built in backdoor, as future documents might indicate. The tin hatters are looking a little less crazy every day as their suspicions become vindicated.

RSA's name is dirt in the security industry

[bazmail]

RSA are little more than a government puppet. If you are serious about security, avoid their products.

"RSA, now owned by EMC Corp, did not dispute the research when contacted by Reuters for comment. The company said it had not intentionally weakened security on any product and noted that Extended Random did not prove popular and had been removed from RSA's protection software in the last six months ."

lol. Wonder what new broke ~6 months ago.

FIPS 140-2 4.9.2. The Other Back Door.

[TechyImmigrant]

I think people are being blinded a bit by the dual_EC_DRBG issue. It makes people think the other 3 DRBG algorithms in SP800-90A are OK.

However if your system implements FIPS140-2 compliance, there's another hole which affects all RNGs within the FIPS boundary. Please read section 4.9.2 of FIPS140-2. You will see this. I call it the FIPS entropy destroyer...

"1. If each call to a RNG produces blocks of n bits (where n > 15), the first n-bit block generated
after power-up, initialization, or reset shall not be used, but shall be saved for comparison with
the next n-bit block to be generated. Each subsequent generation of an n-bit block shall be
compared with the previously generated block. The test shall fail if any two compared n-bit
blocks are equal. "

This will eliminate all adjacent pairs, which would otherwise appear with a frequency dictated by the binomial distribution derived from the bit width of the output and for a 16 bit source, is trivially distinguishable from random with less that 1MByte of output data.

For the record, RdRand doesn't do this because I refused to put it in because it's a back door in the spec.

Re:FIPS 140-2 4.9.2. The Other Back Door.

[cryptizard]

The 16 is just a lower limit. Almost every cryptographic RNG has a block size much, much larger so it's no big deal. Many applications rely on the fact that you will not get two blocks from an RNG that are the same so it seems like a good test to me.

Re:FIPS 140-2 4.9.2. The Other Back Door.

[TechyImmigrant]

>But making a practical attack based on that seems unlikely to me.

Q: If you have a 128 bit 'full entropy' key K[127:0] , how much is the entropy reduce if K[(n*16)+15:(n*16)] K[((n+1)*16)+15:((n+1)*16)] for n in {0..7} ?
A: A lot.

I.E. It reduces the brute force search space by a lot.

Re:FIPS 140-2 4.9.2. The Other Back Door.

[TechyImmigrant]

>The 16 is just a lower limit. Almost every cryptographic RNG has a block size much, much larger so it's no big deal.

But it asks for the test to be made at the output. The block size might be 128 or 256 bits, but the output is often less. E.G. RdRand has a block size of 16, 32 or 64 bits. So if you built a FIPS140-2 compliant software stack and didn't want to fight with the certification house and so implemented 4.9.2, it would fail easily at 16 bits and fairly easily at 32 bits.

Re:FIPS 140-2 4.9.2. The Other Back Door.

[TechyImmigrant]

But it gives you a set of algebraic equations you can use to attack a key composed of multiple of these values.
key[31:16] != key[15:0]
key[47:32] != key[31:16]
key[63:48] != key[47:32] ...
key[127:112] != key[111:96]

Imagine all the ways you could use these equations to attack they key schedule in a block cipher.

Re:FIPS 140-2 4.9.2. The Other Back Door.

[TechyImmigrant]

It's more than that by a lot. The min entropy of a composed number isn't the sum of the shannon entropies of the constituent numbers.

I'd post the math here, but I'm a work and my half written book that addresses this is at home.

Re:FIPS 140-2 4.9.2. The Other Back Door.

[TechyImmigrant]

Here's the basic idea...

Given say a 128 bit key made from a FIPS compliant 16 bit output RNG:

Take the upper 32 bits. There are 2^16 values where the upper half==the lower half. For each of those 2^16 values, there are 2^96 values removed from the 2^128 bit number space (I.E. all the combinations of the lower 96 bits with the upper 32 where the halves match). So that's 2^(16+96). So the size of the output space is reduced to 2^128 - 2^112.

Then slide right 16 bits and repeat. Subtract another 2^112, but eliminate the overlap with the first elimination - that's where the math gets tricky. I have it written down at home.

Repeat until you have considered all adjacent 16 bit pairs in the key.

What you end up with is a 2^128 number space with a large number of holes. All present values are equally likely and the probability of all other values is 0. In terms of reducing the brute force search, it's significant, especially if you have a huge data center in Utah.

What may be worse (I don't know) is the simultaneous equations that it creates that are invariant for keys from such a source. Maybe they could be used in a cryptographic attack to help solve the sorts of attack that try to build big systems of simultaneous equations to attack the key schedule.

Re:FIPS 140-2 4.9.2. The Other Back Door.

[TechyImmigrant]

>And how do you know the NSA's influence didn't simply steamroll over all your professional objections and put the flawed standard in the chips anyway? The NSA has social as well as technological backdoors.

There are publicly published and peer reviewed mathematical proofs that the extraction algorithm (AES-CBC-MAC) and the PRNG algorithm (AES-CTR-DRBG) are secure outside of the NIST specs.

I have also done things to work around all the questionable aspects of the SP800-90 spec. E.G. Massive over reseeding. Not throwing away data marked as unhealthy by the online heath test - mix it in instead, just don't count its entropy. Not implementing FIPS 4.9.2 because it's evil. Not implementing the Dual_EC_DRBG because it was shown to be broke in 2006 and it's stupid anyway being slow and hard to understand. Preventing the personalization strings and 'additional entropy' inputs that could be used as an attack vector or side channel stimulus. Etc.

I've done my best to ensure that if there is some trick up their sleeves in the spec, I've done what's necessary to work around it.

Could EMC sue?

[real gumby]

EMC paid $2.6B for RSA. Could they sue the NSA for destroying the value of their property? What would be just compensation?

Re:Could EMC sue?

[whoever57]

EMC paid $2.6B for RSA. Could they sue the NSA for destroying the value of their property?

No, because the PHBs at EMC/RSA already accepted payment from the NSA. Someone should be fired over the fact that a $2.6B investment was hugely devalued for a payment of only $10M.

Re:we must end this jewish problem once and for al

[Dishevel]

It was. Then they lost that war.

Re:Surprise surprise, they lied and it's still the

[erikkemperman]

The only question is WHY DO THEY GO ON RECORD with the bullshit denials?

It is a calculated risk, and maybe out of habit.

Somewhere along the chain of command, though, the denials do become true. A good underling knows when to grant his masters the ultimate in plausible deniability by simply not filling them in on certain matters.

Re:Surprise surprise, they lied and it's still the

[Wootery]

A good underling

Good for whom, exactly?

Re:Surprise surprise, they lied and it's still the

[ObsessiveMathsFreak]

I'm guessing it's because they honestly believe what they are doing is necessary to keep America safe.

This is like the banks and sub-prime lenders "honestly believing" that house prices would go up forever and money would always be cheap.

Read my lips: Everyone involved knew exactly what was going on.

Everyone inside the NSA with so much as a high school Diploma, when encountering even a low level program, knew that it was fundamentally wrong, probably illegal, and corrosive to the civic society. You don't even need to know what civic society is to know that tapping and permanently recording all calls in the US is both dangerous and wrong.

The on the record denials are effectively the NSA aping of the likes of John Corzine's claims of "We have no idea where the money is", despite being the man who took it right out of customers accounts. I dwell on the financial crisis because the breakdown in the rule of law, propriety, common sense, and all morality there is a mirror image and ultimately a fore-runner of the excesses and lies we now see in the NSA.

All that Keeping America Safe is BS. This is all about budgets, contracts, staffing levels, prestige and power seeking on the part of an entire city block of executives, officers, and IT workers throughout the NSA. The purpose of the NSA is to procure BMWs and range rovers for its management, and for favored private contractors and sub-contractors. That is why the price of a incorporated city is being spent on all these ludicrously overblown surveillance programs.

Forget the lies. Follow the money. Men will do anything, say anything, to anyone to keep such a gravy train flowing.