Skip to content

Instantly share code, notes, and snippets.

@0xabad1dea
Last active May 4, 2022 21:59
Show Gist options
  • Save 0xabad1dea/8101758 to your computer and use it in GitHub Desktop.
Save 0xabad1dea/8101758 to your computer and use it in GitHub Desktop.
Sorry, RSA, I'm just not buying it

Sorry, RSA, I'm just not buying it

I want to be extremely clear about three things. First, this is my personal opinion – insert full standard disclaimer. Second, this is not a condemnation of everyone at RSA, present and past. I assume most of them are pretty okay, and that the problem is confined to a few specific points in the company. However, “unknown problem people making major decisions at RSA” is a bit unwieldy, so I will just say RSA. Third, I'm not calling for a total boycott on RSA. I work almost literally across the street from them and I don’t want to get beat up by roving gangs of cryptographers at the local Chipotle.

RSA's denial published last night is utter codswallop that denies pretty much everything in the world except the actual allegations put forth by Reuters and hinted at for months by other sources. It makes pathetically weak excuses which make them look like Grade-A idiots if we take them at their word. The non-denial denial contains PR weasel words written in blinking neon lights that can be seen from the Asteroid Belt. Someone spent their weekend agonizing over every word of this to maximize its meaninglessness and they certainly succeeded.

There are three basic possibilities of what happened, and only one is “categorically denied.” They categorically deny being cartoon supervillains, and I suppose that's better than not denying that. The supervillain scheming to dishonestly subvert the world's security is reserved for the NSA itself. The other two possibilities are that: a) RSA understood at some point that something smelly was going on, but repeatedly chose to pretend they didn't notice to avoid angering the NSA b) the people in charge of these decisions are the same sort of people who, placed at the helm of the Titanic, would see an iceberg on the horizon and steer straight towards it. (I am now informed by the twittering public that maybe it would not have sank if it had collided at such an angle. OH WELL.)

Let's review what, exactly, happened:

  • A long time ago: NSA issues changes to DES without much explanation. It is eventually shown by others that they improved it, not backdoored it.

  • September 2001: the start of a fundamental change in what the NSA feels its mission and scope are, and everyone outside can see it happening over the next several years.

  • June 2004: ANS X9.82, Part 3 draft published with Dual EC DRBG. (This is the earliest reference I can find to starting the standardization process. More documentation here.)

  • ? 2004: NSA allegedly approaches RSA with an offer for ten million dollars to make Dual EC its default random number generator in the BSAFE library despite it being relatively new, a bit strange, and very slow. We do not know what reasons they gave or what terms may have been agreed to.

  • January 2005: first interior-to-standards-group concerns Dual EC could be backdoored, according to Matthew Green.

  • March 2006: Acknowledgements published that an adversary with special knowledge could subvert the proof of Dual EC’s security.

  • June 2006: first edition of NIST SP 800-90A, containing Dual EC. It is now claimed by a Reuters source (perhaps someone can give me a cite of at-the-time discussion) that RSA already having deployed it was used as a reason to put it in this standard.

  • August 2007: Claims published by Microsoft that Dual EC could contain a backdoor. Everyone eyes it warily and nobody, it seems, deliberately chooses to use it after this point. After all, it is broken in OpenSSL for years and nobody notices. It quietly remains the default in BSAFE.

  • September 2013: Revelations derived from the Snowden leak show* that Dual EC is definitely deliberately backdoored by the NSA. RSA acts really surprised. RSA offers some weak excuse that elliptic curves were totally hip (literally in vogue) at the time. RSA does not mention anything about taking anyone’s money. Allegations are posted that an unspecified company accepted ten million dollars to make it their default. Everyone paying attention is pretty sure it's RSA. (* Full disclosure: smart people disagree with the smoking-gunness of Dual EC being called out specifically by the leak. It's complicated.)

  • December 2013: Reuters points to RSA specifically regarding the ten million dollars. RSA issues a non-denial of such magnitude that I'm driven to rage blog.

It is abundantly clear that, yes, RSA crowned Dual EC the default before the first published concerns it could be a backdoor. (They also did it well before it became officially NIST standard, so if you see anyone use that as an excuse, don't let them get away with it.) So, yes, it is possible that, in 2004, nobody at RSA had any articulable suspicions about Dual EC. They may have taken it on faith that this was another DES situation where the NSA knew it was better but couldn't disclose why. Okay. Is that fair? I think that's fair.

If that were the end of the story, I would be standing here saying “poor RSA! How cruelly the NSA mistreated them!” But, guess what, it isn't. In 2007 the possibility of a backdoor was made very public, and after that “everyone knew” not to use it. None of us knew for sure it was backdoored (even if some people retroactively pretend they did) but that was kind of a crazy risk to take when there were other RNGs to pick from with no known risks and were faster to boot. The OpenSSL bug conveniently testifies to the idea that either no-one was using it or a few people tried, got a weird crash, shrugged and used a different RNG. This is where my problem with RSA is. They heard, just like the rest of us (I was a kid in college in 2007, and I certainly heard) that respectable researchers believed Dual EC could be backdoored. They knew, unlike the rest of us, that it had been worth cold cash money to the NSA to make Dual EC the default in BSAFE.

At this point, an alarm bell should have gone off within the company. DING A FREAKING LING. It could be backdoored and they knew the NSA had paid for it to be there and it was believed by everyone in the industry that the NSA was most likely expanding its digital spying capabilities in recent years.

Why, after the year 2007, did RSA leave Dual EC in place as the default generator despite all signs pointing to trouble?

Well, of course, there could be many reasons. The NSA could have painted them into a corner with legal obligations to keep it as the default and keep their mouths shut. I’m rather inclined to this theory as it fits neatly with their current PR efforts. It could be that the few people who knew about the arrangement had already left the company and there was a failure (unintentional or deliberate) to clearly propagate this knowledge, making it harder to put two and two together. In this case, I would still blame them for being dumb about leaving it as the default, however, as there was no sensible reason to do so.

A random number generator has the nice property that for almost all applications, you can silently swap one out for another and it makes no functional difference to the application. It only matters which algorithm you’re using (in functionality terms) if you need the ability to store seeds and later reuse them to generate the exact same stream again. This is the sort of thing one does in simulations, and not very often in cryptography. Therefore, switching the default algorithm from Dual EC to any of the other equally standard and approved algorithms would not have a functional impact on the vast majority of customers; the few caught out would simply change from the new default back to Dual EC. As a bonus, all the other algorithms are apparently faster and that’s generally a desirable property.

RSA claims they did not do any of this because NIST did not drop the algorithm. However, NIST was not the reason the algorithm was adopted in the first place (see timeline) and this isn’t about removing the algorithm: they could have kept it on board as an option and I wouldn’t now have an issue with that. The issue is they left it as default. They had insider knowledge that the algorithm was of special interest to the NSA, which they did not disclose in the light of the backdoor hypothesis. They probably couldn’t disclose that, legally, I get that. I assume it was publicly documented at the time that BSAFE defaulted to Dual EC but this doesn’t really seem to have collectively “clicked” with those of us on the outside. Would we have cared more, in 2007, that Dual EC was the BSAFE default, had we known that RSA had accepted money from the NSA to make it so? I believe so. That would have made it a lot more obviously suspicious.

When the news about Dual EC broke a few months ago, a lot of people in the community said that, well, nobody used it anyway because everybody knew something was wrong with it. This both shows that nobody really realized it was the default in BSAFE and, critically, that RSA cannot really claim they never even suspected a thing at any point.

Therefore, I believe that from 2007 to 2013, RSA was in a state of negligence regarding their use of Dual EC as the default. I believe they had all the information necessary to deduce something was wrong and, for whatever reason, did not act. This has endangered all of RSA’s customers and their customers’ customers.

The reasons they did nothing are probably contractual and political. What do I know about politics? I’m just some firebrand kid. However, their current PR efforts are not doing any favors for their integrity. At all.

I’m willing to believe you were tricked in 2004, RSA. I’m not willing to believe that you were the only people on the planet too dumb to avoid Dual EC after 2007. At some point, you figured it out.

If there are any other skeletons in the closet, it’s probably a good time to air them out before we find out there’s other things you repeatedly did not disclose. Look on the bright side: can it really be any worse than that time you had to replace every single freakin’ token in the world?

@CodesInChaos
Copy link

As evidence of how easy it was to notice (after 2007) that DUAL_EC contains a potential backdoor, it was even mentioned in its wikipedia article.

In its very first version from November 2007:

In November 2007, researchers discovered what is believed to be an NSA-designed "back door" to the encryption standard that would allow the United States government to decrypt anything encrypted using the DUAL_EC_DRBG standard without needing access to the encryption keys

While the wording changed a bit over the years, every version of the article mentioned the possibility of a backdoor.

@stevens37
Copy link

The 'bug' in the OpenSSL wasn't caught even by the FIPS validation test.
Clever:))

@Thue
Copy link

Thue commented Dec 28, 2013

A long time ago: NSA issues changes to DES without much explanation. It is eventually shown by others that they improved it, not backdoored it.

I think you should moderate this a bit. NSA was also arguing for 48 bits instead of 64 bits, as your own link says, so NSA could brute force DES. NSA has never been completely trustworthy.

@Thue
Copy link

Thue commented Dec 28, 2013

You should also include http://blog.cryptographyengineering.com/2013/09/the-many-flaws-of-dualecdrbg.html in your timeline. The two 2006 papers linked which shows that DUAL_EC was insecure are surely relevant - fx the first of the papers has the following text in the second paragraph: "Our experimental results and also empirical arguments show that [DUAL_EC] is insecure". Note that this is a separate security vulnerability from the back door, but a vulnerability NSA had to insert to leak enough bits from the X coordinate to make the back door work.

The papers are linked in this paragraph:

So when NIST put forward its first draft of SP800-90 in 2005, academic cryptographers were left to analyze it from scratch. Which, to their great credit, they were quite successful at.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment