September 21, 2013

The Anatomy of an NSA intervention -- NIST & RSA fingered as breached

It is now almost good enough to take to a jury -- the NSA perverted the public standards process, and convinced at least one major supplier of crypto tools to weaken customer's infrastructure by using that flawed standard.

We don't have an admission of guilt from the NSA, and never will have that! But at the least, we now know enough to understand the anatomy of the breach. Here goes:

Part one. The NSA participated in a public standards process run by NIST (USA's National Institute for Standards and Technology) to create a new federal standard for random number generation, called Special Publication 800-90.

This is really important to us in the security world because of two things: good random numbers are the bedrock of many cryptographic protocols. Secondly, where NIST goes, the USA federal government *must* go, most of the USA industry slots into line without question, and the rest of the world also tends to nod wisely and follow.

The power of NIST standards over the crypto world is something without parallel, which made it a prize worth fighting for. The goal then was to force into NIST standards a flawed cryptographic random number generator that the NSA could crack -- that is, render the numbers un-random and therefore the cryptographic protocols broken and weak -- but nobody else would see the difference.

Details are on Mathew Greene's site, if you like a little math.

This was achieved, under the unlikely name of Dual_EC_DRBG! On to part two: the next act in the drama is to pay/extort/pressure/trick various suppliers of software into using the flawed standard. This is actually a lot easier than it sounds. Firstly, it was a standard, and most companies will bow and scrape before such a thing without question. OpenSSL ships it, so the ruse was far spread.

Secondly, where necessary, pressure can be brought to bear, and explanations can be fluffed. Crucial in this case was the logic that the Dual_EC concept used elliptic curve mathematics which were impenetrable to many, and rather new to industry. Hence it was possible to 'snow' the discussion with a lot of bla bla, and normally critical people were seemingly lulled from skepticism to acquiescence.

Which, once done then leads to part three: profit! Or in this case, eavesdrop. If there are all these systems out there using the flawed random number generator, it is possible for the NSA (only) to attack them. Listen, change, pervert, whichever. Unfortunately, we have little information on this phase; we don't know how many companies have been tricked into using the flawed generator (so far, NIST records: RSA and Thales, Catbird, McAfee, Cummings, OpenSSL, ARX, Certicom, RIM/Blackberry, Mocana, Microsoft, Cisco, Juniper, Blackberry, OpenPeak, Samsung, Symantec, Riverbed, CoCo, Kony, Lancope, SafeNet, SafeLogic, Panzura, GE Healthcare), and we don't know what successful penetration occurred as a result.

Little matter, for the potential for damage is huge. We know now how the attack happened, and it is important to document it as a case study, for future defence efforts.

Having said all that, the attack did not happen without some drama. Firstly, Dual_EC had some suspicious absences: a lack of any security proof and some unclear foundations. In a rump session at Crypto 2007, a couple of smart cryptographers from Microsoft laid out a theory by which if the NSA had been malicious, it could have spiked the design, kept a hidden backdoor, and nobody would be the wiser.

Unfortunately there was no proof. And the custom to label people as 'conspiracy theorists' until they bring PROOF, real solid actual proof of malicious actions, was enough to quell the concerns. If we know one thing, it is this: there is never ever any proof, and thus the temptation to downgrade any such crazy criticisms as tinfoil conspiracy theory fruitcakes from Microsoft works very well for the NSA.

Secondly, the NSA did not count on one thing which they should have known: a secret that big would have eventually outed. While it turns out that more than one knew about the attack, it was Edward Snowden that set the cat amongst the pigeons. When he commented recently that a 2006 NIST standard had been perverted, it took about a day to figure which one, because of the already published criticisms.

Then, within the week, NIST declared itself extremely uncomfortable with the flawed standard, and recommended against it. A couple of days later, RSA announced it was pulling that product.

RSA? The venerable old company that provided the crypto behind SSL's PKI? Yes the same company that was once responsible for the majority of ecommerce had placed the flawed random number generator as its default. Worse, allegations have circulated that serious amounts of money changed hand in exchange for the favour to NSA, although we'll never likely see any serious evidence of that scandalous claim.

Update -- the approach was one of influence via an existing large contract for $10m with the NSA. Of course.

So there we have it -- the anatomy of a breach, from NSA to NIST to RSA. This was a serious effort. It should lay to rest claims that this would not happen elsewhere. If the NSA went to that sort of trouble, breaching individual companies and other governments should now be seen as entirely plausible.

Addendum: more evidence from NSA's $250m SIGINT Enabling project:

Posted by iang at September 21, 2013 02:26 PM | TrackBack

According to "Secure implementations of the standard curves are theoretically possible but very hard."

Seems like another tactic :) notice how all the NIST curves are generated from an unexplained large seed... the RNG compromise was just a little too obvious... nice diversionary tactic!?

I'm terming this "compromise-in-depth"

Posted by: Slim at October 14, 2013 11:32 AM

The NSA back door to NIST

Thomas C. Hales (University of Pittsburgh)

(This article will be published in the Notices of the American Mathematical Society.)

Use once. Die once. — activist saying about insecure communication

This article gives a brief mathematical description of the NIST standard for cryptographically secure pseudo-random number generation by elliptic curves, the back door to the algorithm discovered by Ferguson and Shumow, and finally the design of the back door based on the Diffie-Hellman key exchange algorithm.

NIST (the National Institute for Standards and Technology) of the U.S. Department of Commerce derives its mandate from the U.S. Constitution, through the congressional power to “fix the standard of weights and measures.” In brief, NIST establishes the basic standards of science and commerce. Whatever NIST says about cryptography becomes implemented in cryptographic applications throughout U.S. government agencies. Its influence leads to the widespread use of its standards in industry and the broad adoption of its standards internationally.

Through the Snowden disclosures, the NIST standard for pseudo-random number generation has fallen into disrepute. Here I describe the back door to the NIST standard for pseudo-random number generation in elementary and mathematically precise terms. The NIST standard offers three methods for pseudo-random number generation [NIST]. My remarks are limited to the third of the three methods, which is based on elliptic curves.


Posted by: (rtf) The NSA back door to NIST at November 12, 2013 03:52 AM

(Reuters) - As a key part of a campaign to embed encryption software that it could crack into widely used computer products, the U.S. National Security Agency arranged a secret $10 million contract with RSA, one of the most influential firms in the computer security industry, Reuters has learned.
Undisclosed until now was that RSA received $10 million in a deal that set the NSA formula as the preferred, or default, method for number generation in the BSafe software, according to two sources familiar with the contract. Although that sum might seem paltry, it represented more than a third of the revenue that the relevant division at RSA had taken in during the entire previous year, securities filings show.
Most of the dozen current and former RSA employees interviewed said that the company erred in agreeing to such a contract, and many cited RSA's corporate evolution away from pure cryptography products as one of the reasons it occurred.

But several said that RSA also was misled by government officials, who portrayed the formula as a secure technological advance.

"They did not show their true hand," one person briefed on the deal said of the NSA, asserting that government officials did not let on that they knew how to break the encryption.
Bidzos stepped down as CEO in 1999 to concentrate on VeriSign, a security certificate company that had been spun out of RSA. The elite lab Bidzos had founded in Silicon Valley moved east to Massachusetts, and many top engineers left the company, several former employees said.

And the BSafe toolkit was becoming a much smaller part of the company. By 2005, BSafe and other tools for developers brought in just $27.5 million of RSA's revenue, less than 9% of the $310 million total.

"When I joined there were 10 people in the labs, and we were fighting the NSA," said Victor Chan, who rose to lead engineering and the Australian operation before he left in 2005. "It became a very different company later on."

By the first half of 2006, RSA was among the many technology companies seeing the U.S. government as a partner against overseas hackers.

New RSA Chief Executive Art Coviello and his team still wanted to be seen as part of the technological vanguard, former employees say, and the NSA had just the right pitch. Coviello declined an interview request.
RSA's contract made Dual Elliptic Curve the default option for producing random numbers in the RSA toolkit. No alarms were raised, former employees said, because the deal was handled by business leaders rather than pure technologists.

"The labs group had played a very intricate role at BSafe, and they were basically gone," said labs veteran Michael Wenocur, who left in 1999.

Posted by: Reuters at December 27, 2013 12:35 AM
Post a comment

Remember personal info?

Hit preview to see your comment as it would be displayed.