Hi Jon,
Thanks for forwarding your interesting email here.
You raise the provability issue about BBS (which is different from the two
issues about BBS that I previously raised, which were some attacks), and also
extend it to Dual_EC, and perhaps any "public-key" DRBG.
Specifically, you say that no public-key DRBG/PRNG can be proved secure. By
contrast, BBS claim a security proof (but I have not reviewed the BBS proof at
all). Gjosteen and I claim a security proof CRYPTO 2007 for Dual_EC.
Therefore, it would be interesting if we could find some common ground. To
that end, I've taken some time to write a reactionary missive that I think
addresses your concerns.
Firstly, the Dual_EC proof is only about its quality as a DRBG, PRNG, or PRG.
Specifically, any PRG, including HMAC_DRBG, CTR_DRBG, starts with an initially
random fixed length secret seed, maintains a state, and outputs a long stream,
with the aim to provide some measure of indistinguishability for the existing
outputs even permitting the adversary to access the latest current state. Our
claims ignored the threat of state compromise recovery (aka prediction
resistance). As usual, a security proof, like any proof, has some hypotheses,
and its conclusions are only as a strong as its hypotheses. Also, it is
implied by our CRYPTO 2007 paper, that what's required to be initially short
secret seed is not only the conventional running state s, but also
trapdoor-component of the state log_P(Q). To force log_P(Q) to be random, one
can just choose P and Q to be random. To do that, choose them yourself,
derived from the same entropy source you needed for the running state, or else
choose them as nothing up my sleeve numbers ideally perhaps via NIST SP 800-90A
alternative formulation. These techniques help to make log_P(Q) known to
nobody at all. If log_P(Q) has been chosen by (or for) you, by some authority,
then the Dual_EC, according to the proof, seems secure against everybody but
those who know both the running secret state and the value of log_P(Q).
Secondly, you also critique of Dual_EC and BBS that the p's and q's themselves
need a DRBG to be generated. But then so does any DRBG, once one insists on
uniform keys (like conventional security assmuptions for HMAC and AES-CTR
usually do). That's what entropy conditioners can help resolve, transitioning
from biased raw entropy, to something more like the keys that conventional
crypto algorithms usually expect. Also, a variable output-length DRBG is not
needed either, because the input states to DRBG are fixed length (with the
exceptional of continuously reseeding DRBG). Maybe it's a greater nuisance to
generate the public-key DRBG seeds, but I don't see it as some essential
obstacle.
That all said, I disagree {with /and perhaps even if} the conventional wisdom
{that / is} the public-key PRNGs are more secure, by some kind of default.
Security should be measured by firstly (a) what attacks are known, and by
secondly (b) what the valid proofs claim and assume. It's still on my to-do
list to review the security proof for HMAC_DRBG, and see what assumptions it
hypothesizes. It is also my hope that the somebody will prove the security of
CTR_DRBG, even if in the ideal cipher model (which may be necessary because its
backtracking resistance depends on related keys, and most standard assumptions
about AES don't involve related keys). As far as I know, there's no
fundamental difference in being able to prove security of schemes built from
symmetric and asymmetric primitives. The fixed version of Dual_EC (i.e.
truncated to 50% of bits per point and "verifiably random" P & Q), the
HMAC_DRBG and CTR_DRBG are free from any known attacks. It is also good to have
security proofs to complement the lack of attacks.
I also sympathize with your general point that security proofs have the danger
of dazzling and, thereby, lulling some people into passive acceptance. That's a
psychological issue, and I don't have any kind of workaround for it. I think
many other people have written lots on the general topic (see Another Look
...). I wonder how much other factors can induce similar effects:
implementations, advertising, publication, ...
You rightly point out a commonality between some public-key DRBGs, namely
Dual_EC and BBS, and their potential for a private key to be abused as a
backdoor. That said, some differences between BBS and Dual_EC (only the
insufficiently truncated version and backdoored version) include a different in
impact upon adversarial knowledge of the private-key-like "trapdoor" (portion
of the effective secret state):
1. Given also one output, Dual_EC allows computation of future states
(i.e. same consequence as state reveal for any DRBG), and distinguishing of
previous past output from random.
2. Given also one running secret state, BBS allows computation of future
and past states (and thus outputs).
So arguably, the weak version Dual_EC improves on BBS slightly on the narrow
aspect of the backtracking resistance: only distinguishing is possible, not
computation. (To be fair, though, BBS is better on the aspect of semming to
require invasive access to the internal secret state before backtracking.) The
significance of this is that (computational) backtracking resistance is
helpful, perhaps needed, for forward secrecy. Notice that there seems some
growing demand for forward secrecy. This brings me back to my second issue
about BBS in my original email on this thread.
Again the fully corrected version of Dual_EC does not have any known
backtracking vulnerability at all, and like, HMAC_DRBG, even has a security
proof (under various reasonable assumptions). Its main disadvantages are
being relatively slow, and hard-to-explain differences between the
possibly-backdoored version.
Best regards,
Dan
From: dsfjdssdfsd [mailto:[email protected]] On Behalf Of Jon Callas
Sent: Monday, March 17, 2014 12:53 PM
To: [email protected]
Cc: Jon Callas
Subject: Re: [dsfjdssdfsd] Blum-Blum-Shub ambiguity in 4086 ...
I found my missive in question, and upon re-reading it, I think it bears
repeating here.
The thread starts with
<http://www.metzdowd.com/pipermail/cryptography/2014-January/019423.html>
and the message I quote from below is
<http://www.metzdowd.com/pipermail/cryptography/2014-January/019426.html>.
The discussion started with the blog post
<http://blog.0xbadc0de.be/archives/155> which purports to show how DUAL_EC_DRBG
*must* have been backdoored from the start. That blog post is the antecedent of
"it" in the paragraph first paragraph.
----
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 -- Blum-Blum-Shub. (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.)
Blub-Blum-Shub uses an iterated RSA-like 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.
Blum-Blum-Shub 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 pseudo-randomness of the
output. The slow part is pretty obvious. The inobvious part is that it can't be
proven secure.
As an iterated, RSA-like 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 public-key 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 AES-CTR 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 Micali-Shnorr 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 public-key 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 Blum-Blum-Shub, 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 long-standing 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) lower-order 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 RSA-based generator there along with Micali-Shnorr and
Blum-Blum-Shub and *all* of these have a recipe that starts unironically with
(essentially):
1. Setup. Generate two RSA-like 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 public-key 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 Micali-Shnorr 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 root-cause exercise, we can go back to
Blum-Blum-Shub 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 Micali-Shnorr 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
_______________________________________________
dsfjdssdfsd mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/dsfjdssdfsd
