In a recent Q&A with Bruce Schneier and James Ball (a journalist)[1],

Ball said, "Because the NSA and GCHQ have been influencing standards,

and working to covertly modify code, almost anything could potentially

have been compromised. Something as simple as – hypothetically –

modifying a basic random-number-generator could weaken numerous

implementations of open-source code."

In 2007, there was a fair amount of discussion about some elliptic

curve algorithms -- and specifically random-number generators

introduced by NIST in special publication 800-90 (now split off in to

800-90A)[2]. Here's a list of highlights from Bruce's article back

then[3]:

"... one of those generators -- the one based on elliptic curves -- is

not like the others. Called Dual_EC_DRBG, not only is it a mouthful to

say, it's also three orders of magnitude slower than its peers. It's

in the standard only because it's been championed by the NSA, which

first proposed it years ago in a related standardization project at

the American National Standards Institute. ... Problems with

Dual_EC_DRBG were first described in early 2006. The math is

complicated, but the general point is that the random numbers it

produces have a small bias. The problem isn't large enough to make the

algorithm unusable ... [but] at the CRYPTO 2007 conference in August,

Dan Shumow and Niels Ferguson showed that the algorithm contains a

weakness that can only be described a backdoor. ...

What Shumow and Ferguson showed is that these numbers have a

relationship with a second, secret set of numbers that can act as a

kind of skeleton key. If you know the secret numbers, you can predict

the output of the random-number generator after collecting just 32

bytes of its output. To put that in real terms, you only need to

monitor one TLS internet encryption connection in order to crack the

security of that protocol. If you know the secret numbers, you can

completely break any instantiation of Dual_EC_DRBG.

The researchers don't know what the secret numbers are. But because of

the way the algorithm works, the person who produced the constants

might know; he had the mathematical opportunity to produce the

constants and the secret numbers in tandem. ... We don't know where

the constants came from in the first place. We only know that whoever

came up with them could have the key to this backdoor. And we know

there's no way for NIST -- or anyone else -- to prove otherwise. ...

Even if no one knows the secret numbers, the fact that the backdoor is

present makes Dual_EC_DRBG very fragile. If someone were to solve just

one instance of the algorithm's elliptic-curve problem, he would

effectively have the keys to the kingdom. ...

I don't understand why the NSA was so insistent about including

Dual_EC_DRBG in the standard. It makes no sense as a trap door: It's

public, and rather obvious. It makes no sense from an engineering

perspective: It's too slow for anyone to willingly use it. And it

makes no sense from a backwards-compatibility perspective: Swapping

one random-number generator for another is easy.

My recommendation, if you're in need of a random-number generator, is

not to use Dual_EC_DRBG under any circumstances. If you have to use

something in SP 800-90, use CTR_DRBG or Hash_DRBG."

So from Ball's recent comments one might suppose that software to keep

an eye on are those that use or could potentially be using

Dual_EC_DRBG from NIST special publication 800-90A. It so happens that

there is a list of implementations using the DRBG validation suite[4].

Some of them could be repeats but I count about 65 hits on

Dual_EC_DRBG -- including the OpenSSL FIPS module. What I find

interesting is that Bruce has been helping the Guardian vet all the

documents they're publishing and aside from talking about his own

methods for remaining secure[5], he's not gone on record about his

speculation as to what technical methods the NSA have used to

compromise so much at once. However, I have seen much call for

industry insiders to come forward if they've taken part in any known

compromise of products. This is the closest I've come to tracking down

anything useful -- and my hand was heavily tipped by a friend that did

some sleuthing of his own to suggest Dual_EC_DRBG in the first place.

But I am surprised to find just how many have implemented Dual_EC_DRBG

despite all the warnings against it in light of how crucial random

number generation is to the integrity of PKI.

-Gary

1.

http://www.theguardian.com/commentisfree/2013/sep/06/nsa-surveillance-revelations-encryption-expert-chat2.

http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf3.

http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_11154.

http://csrc.nist.gov/groups/STM/cavp/documents/drbg/drbgval.html5.

http://www.theguardian.com/world/2013/sep/05/nsa-how-to-remain-secure-surveillance______________________________________________________________________

OpenSSL Project

http://www.openssl.orgUser Support Mailing List

[hidden email]
Automated List Manager

[hidden email]