______________________________
Report: NSA Paid RSA to Make Flawed Crypto Algorithm the Default
December 23, 2013
By Peter Bright, Bruce Schneier
Ars Technica, Wired (December 20, 2013)
Reuters' report suggests that RSA wasn't merely following
the trends when it picked the algorithm and that contrary to its
previous claims, the company has inserted presumed backdoors at the
behest of the spy agency.
Report: NSA Paid RSA to Make Flawed Crypto Algorithm the Default
Did NSA Put a Secret Backdoor in New Encryption Standard?
Report: NSA Paid RSA to Make Flawed Crypto Algorithm the Default
by Peter Bright
Ars Technica
December 20, 2013
http://arstechnica.com/security/2013/12/report-nsa-paid-rsa-to-make-flawed-crypto-algorithm-the-default/
Security company RSA was paid $10 million to use the flawed
Dual_EC_DRBG pseudorandom number generating algorithm as the default
algorithm in its BSafe crypto library, according to sources speaking
to Reuters.
The Dual_EC_DRBG algorithm is included in the NIST-approved crypto
standard SP 800-90 and has been viewed with suspicion since shortly
after its inclusion in the 2006 specification. In 2007, researchers
from Microsoft showed that the algorithm could be backdoored: if
certain relationships between numbers included within the algorithm
were known to an attacker, then that attacker could predict all the
numbers generated by the algorithm. These suspicions of backdooring
seemed to be confirmed this September with the news that the National
Security Agency had worked to undermine crypto standards.
The impact of this backdooring seemed low. The 2007 research, combined
with Dual_EC_DRBG's poor performance, meant that the algorithm was
largely ignored. Most software didn't implement it, and the software
that did generally didn't use it.
One exception to this was RSA's BSafe library of cryptographic
functions. With so much suspicion about Dual_EC_DRBG, RSA quickly
recommended that BSafe users switch away from the use of Dual_EC_DRBG
in favor of other pseduorandom number generation algorithms that its
software supported. This raised the question of why RSA had taken the
unusual decision to use the algorithm in the first place given the
already widespread distrust surrounding it.
RSA said that it didn't enable backdoors in its software and that the
choice of Dual_EC_DRBG was essentially down to fashion: at the time
that the algorithm was picked in 2004 (predating the NIST
specification), RSA says that elliptic curves (the underlying
mathematics on which Dual_EC_DRBG is built) had become "the rage" and
were felt to "have advantages over other algorithms."
Reuters' report suggests that RSA wasn't merely following the trends
when it picked the algorithm and that contrary to its previous claims,
the company has inserted presumed backdoors at the behest of the spy
agency. The $10 million that the agency is said to have been paid was
more than a third of the annual revenue earned for the crypto library.
Other sources speaking to Reuters said that the government did not let
on that it had backdoored the algorithm, presenting it instead as a
technical advance.
Did NSA Put a Secret Backdoor in New Encryption Standard?
Bruce Schneier
Wired
November 15, 2007
http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115
Random numbers are critical for cryptography: for encryption keys,
random authentication challenges, initialization vectors, nonces,
key-agreement schemes, generating prime numbers and so on. Break the
random-number generator, and most of the time you break the entire
security system. Which is why you should worry about a new
random-number standard that includes an algorithm that is slow, badly
designed and just might contain a backdoor for the National Security
Agency.
Generating random numbers isn't easy, and researchers have discovered
lots of problems and attacks over the years. A recent paper found a
flaw in the Windows 2000 random-number generator. Another paper found
flaws in the Linux random-number generator. Back in 1996, an early
version of SSL was broken because of flaws in its random-number
generator. With John Kelsey and Niels Ferguson in 1999, I co-authored
Yarrow, a random-number generator based on our own cryptanalysis work.
I improved this design four years later -- and renamed it Fortuna --
in the book Practical Cryptography, which I co-authored with Ferguson.
The U.S. government released a new official standard for random-number
generators this year, and it will likely be followed by software and
hardware developers around the world. Called NIST Special Publication
800-90 (.pdf), the 130-page document contains four different approved
techniques, called DRBGs, or "Deterministic Random Bit Generators."
All four are based on existing cryptographic primitives. One is based
on hash functions, one on HMAC, one on block ciphers and one on
elliptic curves. It's smart cryptographic design to use only a few
well-trusted cryptographic primitives, so building a random-number
generator out of existing parts is a good thing.
But 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.
The NSA has always been intimately involved in U.S. cryptography
standards -- it is, after all, expert in making and breaking secret
codes. So the agency's participation in the NIST (the U.S. Commerce
Department's National Institute of Standards and Technology) standard
is not sinister in itself. It's only when you look under the hood at
the NSA's contribution that questions arise.
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 -- and Appendix E of the NIST standard
describes an optional work-around to avoid the issue -- but it's cause
for concern. Cryptographers are a conservative bunch: We don't like to
use algorithms that have even a whiff of a problem.
But today there's an even bigger stink brewing around Dual_EC_DRBG. In
an informal presentation (.pdf) 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.
This is how it works: There are a bunch of constants -- fixed numbers
-- in the standard used to define the algorithm's elliptic curve.
These constants are listed in Appendix A of the NIST publication, but
nowhere is it explained where they came from.
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.
Of course, we have no way of knowing whether the NSA knows the secret
numbers that break Dual_EC-DRBG. We have no way of knowing whether an
NSA employee working on his own came up with the constants -- and has
the secret numbers. We don't know if someone from NIST, or someone in
the ANSI working group, has them. Maybe nobody does.
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.
This is scary stuff indeed.
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. He could then use it for
whatever nefarious purpose he wanted. Or he could publish his result,
and render every implementation of the random-number generator
completely insecure.
It's possible to implement Dual_EC_DRBG in such a way as to protect it
against this backdoor, by generating new constants with another secure
random-number generator and then publishing the seed. This method is
even in the NIST document, in Appendix A. But the procedure is
optional, and my guess is that most implementations of the
Dual_EC_DRBG won't bother.
If this story leaves you confused, join the club. 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.
In the meantime, both NIST and the NSA have some explaining to do.
________________________
Best
A. Mani
A. Mani
[Last_Name. First_Name Format]
CU, ASL, AMS, ISRS, CLC, CMS
http://www.logicamani.in
_______________________________________________
network mailing list
[email protected]
http://lists.fosscom.in/listinfo.cgi/network-fosscom.in
