2 January 2014
Dual_EC_DRBG backdoor: a proof of concept
From: Jon Callas <jon[at]callas.org>
Date: Thu, 2 Jan 2014 13:30:11 0800
To: ianG <iang[at]iang.org>
Cc: Cryptography Mailing List <cryptography[at]metzdowd.com>,
Jon Callas
<jon[at]callas.org>
Subject: Re: [Cryptography] Dual_EC_DRBG backdoor: a proof of concept
BEGIN PGP SIGNED MESSAGE
Hash: SHA1
On Jan 2, 2014, at 9:04 AM, ianG <iang[at]iang.org> wrote:
Tantalising! I've no time to look (and wouldn't know an eliptic curve
if it slapped me in the face). Comments?
http://blog.0xbadc0de.be/archives/155
It's nice work on a technical level, but I think it fails at its goal, that
is to be a piece of polemic  even mischaracterizing the Ferguson/Shumow
CRYPTO Rump Session talk (their last slide explicitly said they were not
suggesting a back door).
Lest you think I'm saying something nice about DUAL_EC_DRBG, I'll repeat
what I've said before, "Only an idiot would use it." It's slow, has biases
in its output that hashes and ciphers don't, and cannot be proved secure.
Let me rewind to the first public key based DRBG/PRNG  BlumBlumShub.
(DRBG is the name NIST gave to what you and I would call a PRNG, it's
Deterministic Random Bit Generator. If you think of a complete design of
an RNG, you want at least three major sections  "entropy" collection, entropy
pool management, and conditioned output. A DRBG is the output stage.)
BlubBlumShub uses an iterated RSAlike operation to generate random bits.
It was developed in 1986 and is a brilliant piece of mathematics. It was
one of the very, very few bits of early crypto to have a sound theoretical
basis.
Many people who haven't thought it through have sung its praises over the
years, mostly because they got seduced by the sound theoretic basis.
BlumBlumShub has two of the three flaws that DUAL_EC_DRBG has: it's slow,
and you can't prove it secure.
I'm sure you thinking, 'What do you mean, "can't be proved secure? Didn't
you just say that it had a sound theoretical basis?"' Yup, and the sound
theoretical basis gives you the good mathematical pseudorandomness of the
output. The slow part is pretty obvious. The inobvious part is that it can't
be proven secure.
As an iterated, RSAlike operation, the core of it is two prime numbers,
p and q. The security resolves down to the secrecy of the two primes.
And this leaves you with the question of how you get the primes. Well, if
you generate them at run time, then you push the construction of your RNG
down to the turtle below you. Your random number generator requires random
p and q and you get those by using some other random number generator, one
presumes.
Alternatively, you could use a fixed p and q, and then you have the *exact*
flaw as DUAL_EC_DRBG  you have a fixed private key that can be used to
jimmy the thing open.
Matt Green wrote a great blog post last week at
http://blog.cryptographyengineering.com
which you should read. I'll summarize a bit and say that Micali and Shnorr
did their own publickey based PRNG which also has Step 1 being "generate
large primes p and q" and they helpfully gave test P and Q. I'm not merely
being ironic. As someone who implemented the AESCTR DRBG, having test vectors
is really, really nice. NIST's test vectors for that are really, really annoying
and I'll complain at length to anyone who cares.
Anyway, Matt Green identifies the MicaliShnorr generator as a precursor
to DUAL_EC_DRBG in both design and having a fixed key that you use for whatever
purporses, testing or compromise.
I have a couple points:
(Point 1) Any publickey based PRNG is going to have the issue that either
you have a fixed key, or you have to generate a key using some other secure
means. This is why I use terms as strong as "can't be proven to be secure"
despite having a mathematical "sound theoretical basis."
I think there's a huge security philosophy problem here  security proofs
that are mathematical can have underlying engineering assumptions that render
them insecure to the point of being silly.
I think that people get blinded by this as well, and if there's a mathematical
proof they're blinded by it, if not cowed by the math and stop prodding at
the engineering and operational security.
Going back to BlumBlumShub, look at the Wikipedia article on it at
http://en.wikipedia.org/wiki/Blum_Blum_Shub
There are some interesting statements there, like the first sentence of the
security section:
The generator is not appropriate for use in simulations, only for cryptography,
because it is very slow.
That makes me splutter. As an engineer, I'd argue that slow alone makes it
not suitable for cryptography. I'm tempted to argue that for simulations,
speed isn't an issue, but really, if you slow things down enough, it's not
suitable for anything. I also have a longstanding twitch at *any* security
discussion that brings in performance. Performance is not security, and many
security sins have their root cause in a performance worry, usually an artificial
one.
The remainder of the section reads:
However, there is a proof reducing its security to the computational difficulty
of the Quadratic residuosity problem. Since the only known
way to solve that problem requires factoring the modulus, the difficulty
of Integer factorization is generally regarded as providing security. When
the primes are chosen appropriately, and O(log log M) lowerorder bits of
each xn are output, then in the limit as M grows large, distinguishing the
output bits from random should be at least as difficult as factoring M.
If integer factorization is difficult (as is suspected) then B.B.S. with
large M should have an output free from any nonrandom patterns
that can be discovered with any reasonable amount of calculation. Thus it
appears to be as secure as other encryption technologies
tied to the factorization problem, such as RSA encryption.
This is interesting because nowhere do they address the central engineering
issue  that a fixed p,q is not secure yet a variable one requires another
RNG to seed the RNG.
Also look at the section in the Handbook of Applied Cryptography on
"Cryptographically secure pseudorandom bit generation":
http://books.google.com/books?id=nSzoG72E93MC&lpg=PA185&dq=
Cryptographically%20secure%20pseudorandom%20bit%20generation&pg=
PA185#v=onepage
We find an RSAbased generator there along with MicaliShnorr and BlumBlumShub
and *all* of these have a recipe that starts unironically with (essentially):
1. Setup. Generate two RSAlike secret primes, p and q.
This is a blind spot that's been there forever  two of the three flaws
of DUAL_EC_DRBG have been staring us all in the face since 1986. Despite
mathematical brilliance, the security of publickey based PRNGs have always
been flawed with something that could be used as a back door.
(Point 2) History looks different when you look backwards than when you look
forwards. Everyone has a tendency to act as if things were predetermined
when we analyze the decisions of the past. We also assign intent when we
have to explain a WTF. Yet the usual answer to "What were you thinking?"
is "They weren't." To quote the great philosopher David Byrne, "And you might
say to yourself, 'My God, what have I done?'"
The general flaws have been there forever, and in general we still don't
see them. In specific, the documents on MicaliShnorr and DUAL_EC_DRBG were
up front about the flaw all along.
Would the NSA exploit such a flaw? Hell, yes. We keep seeing this from leaked
documents, over and over. It's clear that they have taken the hacker philosophy
that nothing is out of scope or out of bounds to heart as an operating principle.
You can see it in the recent ANT toy catalog, as well as the BULLRUN statement
that sent us all into a tizzy.
We have *assumed* that the BULLRUN statement that they're after damaging
standards means that DUAL_EC_DRBG is backdoored. People have said it so loudly
and so often that it's part of conventional wisdom now. Yet until BULLRUN,
it was part of conventional wisdom that despite the speed problems, mathematics
made public key PRNGs more secure.
I know that one of my personal blind spots is that I'm a contrarian. I'm
also a cynic who believes that stupidity is one of the fundamental forces
of the universe. So I find myself in the ironic position of defending a thing
I never liked because yes, really, people *can* be that stupid. We all defer
to authorities, are cowed by proofs, and lose our critical thinking skills
when faced with a standard. I am reminded of Markoff Chaney from Illuminatus!
as well as Poe's Purloined Letter.
If we want to look at this as a rootcause exercise, we can go back to
BlumBlumShub and see the kernel of the flaws and blindness of them. You
can see that despite it being there from the start, we didn't *understand*
it. You can see the progression through MicaliShnorr through the ANSI X9
committee, and then on to NIST.
I'm left wondering if something can really be a backdoor if it was there
all along, we just didn't grok it. Was the purloined letter hidden?
I can't help but feel that calling it a back door is just too cheap and easy
and convenient. It wasn't that we were collectively stupid and snookered
ourselves, it was demons and those in league with them.
This leaves the question of what they *have* been doing with that $250M,
which is a good question. I lean towards private standards like those used
in telecom etc. In the public world, we're good at doing it to ourselves.
Jon
BEGIN PGP SIGNATURE
Version: PGP Universal 3.2.0 (Build 1672)
Charset: usascii
wj8DBQFSxeyasTedWZOD3gYRAjaxAKDds43hYMPlr6koZNE+W7jJIqs+/ACfeVmg
XJtdY8Av/Uhfq5QvcSiRXYE=
=ASjJ
END PGP SIGNATURE
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
ListArchive:
http://www.metzdowd.com/pipermail/cryptography
