39
$\begingroup$

I have an audience of senior (non-technical) executives and senior technical people who are taking the backdoor in Dual_EC_DRBG and considering it as a weakness of Elliptic curves in general. I can take a max of about 10 mins in my presentation to address this issue - no more.

  1. How can I explain the weakness in the EC_DUAL_DRBG to such an audience via Mathematical intuition (rather than hardcore math proofs)?

  2. How do I establish the distinction between weakness in Dual EC DRBG from any weaknesses in EC in general (especially the NSA's Suite B EC curves - ironic, eh?). To me the weakness in Dual EC DRBG is clear (well, after the fact) with selection of the constant curve point. But the NIST EC curves also have constants although of a much different nature (the large prime modulo). Controlling paranoia is ... not easy.

Please note that the non-technical folks are very intelligent - just not security experts. So I'd like to respect that without dumbing it down too much.

$\endgroup$
4
  • 1
    $\begingroup$ Here's a presentation Shumow and Ferguson did about it. $\endgroup$
    – pg1989
    Commented Sep 18, 2013 at 18:25
  • 2
    $\begingroup$ Matt Green wrote a blog article about this: The Many Flaws of Dual_EC_DRBG $\endgroup$ Commented Sep 19, 2013 at 7:43
  • $\begingroup$ @CodesInChaos: That beautifully written, especially the little graphic (Shumow-Ferguson) - that's a key educational visual. Gotta love Matt's writing style even if it's opinionated at times. $\endgroup$ Commented Sep 20, 2013 at 0:56
  • 3
    $\begingroup$ IMO, this is pretty good evidence that EC is strong in general. NSA's ideal back door is one that only they can use. Therefore they must consider discrete log over the Dual_EC_DRBG curves to be "hard". $\endgroup$
    – Nemo
    Commented Sep 20, 2013 at 20:56

1 Answer 1

52
$\begingroup$

I wouldn't try to explain the mathematics of the backdoor. Just explain that the NSA hid a secret backdoor in there.

Instead, I would suggest focusing on the history and the context. For instance, you could explain about Crypto.AG, how they spiked their RNG to help the NSA spy on their customers. You could explain how random number generators are a classic weak point in cryptography, because of the RNG has been backdoored, whoever knows the backdoor can recover all your keys. You could also explain how this is very hard to detect: since RNGs are supposed to output random-looking bits, if it's actually pseudorandom bits that the NSA can predict but no one else can (if the bits are actually coming from a PRNG that the NSA knows the seed to, but no one else does), this is very difficult to detect through black-box testing or through inspection of the supposedly random bits.

If you wanted, you could explain that back in 2006, cryptographers discovered the mathematical structure that would allow a backdoor but shied away from making any accusations, because, hey, surely the NSA wouldn't do that -- that would be so egregious a breach, that it seemed hard to imagine it actually contained a backdoor. And now things are changed: it appears that what seemed unimaginable, is in fact reality. So, you could explain how this is an eye-opener for the cryptographic community and how it will change the way we think about government standards and system design for the future.

You could then explain the impact. You could explain how the impact is believed to be relatively minor, because most people heeded Bruce Schneier's warning from 2007 and didn't use Dual_EC_DRBG. However, you could explain that at least one major crypto library (RSA's BSAFE) does use it, for reasons that are unclear, so this might have an unknown impact on an unknown number of deployed products. You could explain how this backdoor is likely to only allow the NSA to decrypt traffic, not anyone else. And finally, you could explain what the biggest impact is: the potential for loss of trust in cryptographic standards and in American companies. I'm not sure that we've seen the general public lose trust yet -- I think people still trust Google and Apple and Amazon to have their back -- but if that ever happened, that might be hard to recover from.


I see that you want to explain the mathematics. OK, here is an explanation. I'm going to attack a simplified version of Dual_EC_DRBG, but the simplification doesn't change any of the essence of the attack.

The algorithm specification specifies an elliptic curve, which is basically just a finite cyclic (and thus Abelian) group $G$. The algorithm also specifies two group elements $P,Q$. It doesn't say how they were chosen; all we know is that they were chosen by an employee of the NSA. In the simplified algorithm, the state of the PRNG at time $t$ is some integer $s$. To run the PRNG forward one step, we do the following:

  • We compute $sP$ (recall we use additive group notation; this is the same as $P^s$, if you prefer multiplicative notation), convert this to an integer, and call it $r$.

  • We compute $rP$, convert it to an integer, and call it $s'$ (this will become the new state in the next step).

  • We compute $rQ$ and output it as this step's output from the PRNG. (OK, technically, we convert it to a bitstring in a particular way, but you can ignore that.)

Now here's the observation: we're pretty much guaranteed that $P=eQ$ for some integer $e$. We don't know what $e$ is, and it's hard for us to find it (that requires solving the discrete log problem on an elliptic curve, so this is presumably hard). However, since the NSA chose the values $P,Q$, it could have chosen them by picking $Q$ randomly, picking $e$ randomly, and setting $P=eQ$. In particular, the NSA could have chosen them so that they know $e$.

And here the number $e$ is a backdoor that lets you break the PRNG. Suppose the NSA can observe one output from the PRNG, namely, $rQ$. They can multiply this by $e$, to get $erQ$. Now notice that $erQ = r(eQ) = rP = s'$. So, they can infer what the next state of the PRNG will be. This means they learn the state of your PRNG! That's really bad -- after observing just one output from the PRNG, they can predict all future outputs from the PRNG with almost no work. This is just about as bad a break of the PRNG as could possibly happen.

Of course, only people who know $e$ can break the PRNG. So this is a special kind of backdoor: the NSA presumably knows how to break Dual_EC_DRBG, but it's very unlikely that anyone else knows how to break it. Even though we know now the backdoor exists, it's very hard to recover the secret backdoor $e$, because that requires solving a discrete log problem.


Hmm. Maybe that's still too complicated, because it requires understanding additive groups and a little bit about elliptic curves and... ugh. OK. So, let me share with you an analogous: a PRNG that is just like Dual_EC_PRNG, except that it uses integers, instead of elliptic curves. In particular, everything will be conceptually basically the same -- the backdoor will be the same, the PRNG will be the same -- this will just be easier to understand without any background in elliptic curve cryptography. Hopefully this will give the intuition better.

  • The PRNG. The algorithm specifies a prime number $p$, and two integers $g,h$ that are both less than $p$. The algorithm tells you that the state of the PRNG at each point in time is some number $s$ that satisfies $1\le s < p$. To step the PRNG forward by one iteration, you set $r = g^s \bmod p$, $s' = g^r \bmod p$, update the state to $s'$, and output $t = h^r \bmod p$.

  • The backdoor. The backdoor is a secret number $e$ such that $g=h^e \bmod p$. The NSA, who created the algorithm specification, chose $g,h$ by picking $h$ randomly, picking $e$ randomly, setting $g=h^e \bmod p$, and then publishing $g,h,p$ (but keeping $e$ secret, since $e$ is the backdoor).

  • Breaking the PRNG. Here's how the NSA can break this PRNG. Suppose they observe one output $t$ from the PRNG. They compute $t^e \bmod p$. Notice that

    $$t^e = (h^r)^e = h^{re} = (h^e)^r = g^r = s' \pmod p.$$

    This means they were able to compute $s'$, the next state of the PRNG. So, after observing just one output from the PRNG, they can infer the next state of the PRNG and thereby predict what all future outputs from the PRNG will be.

    For instance, suppose you generate a random IV using this generator (and send it in the clear), then generate a session key using this generator, then encrypt stuff under that session key. The NSA (who is eavesdropping on your communication and thus can see the IV) knows that the IV was output from this PRNG and can use their backdoor to infer the state of the PRNG and predict its future outputs -- and thus they can predict your session key and decrypt all your subsequent traffic. You've been owned!

I hope this gives the intuition. The problem with Dual_EC_DRBG is exactly the same as the problem with this hypothetical PRNG that I just described. Hopefully this is simple enough to follow: if you understand how Diffie-Hellman works, you can understand why this is broken.

$\endgroup$
5
  • $\begingroup$ I've got the non-technical bases covered well, similar in vein to yours above. I just know they'd be delighted if I could tease the intuition behind the math (than the core math itself). Getting the middle balance has been tricky ... $\endgroup$ Commented Sep 18, 2013 at 23:23
  • 1
    $\begingroup$ @Sid, OK, I edited my answer to explain the mathematics as well. I apologize that my answer got so long. You can decide whether this will be of interest to them or whether it's just too darn much. If you're giving a presentation, pictures might help. :-) $\endgroup$
    – D.W.
    Commented Sep 19, 2013 at 0:33
  • $\begingroup$ The fact that solving $P = eQ$ requires solving "the discrete log problem" is why I prefer the multiplicative notation $P = Q^e$. Am I out of the mainstream on this? $\endgroup$
    – Nemo
    Commented Sep 19, 2013 at 22:42
  • 2
    $\begingroup$ @Nemo, well... in some sense, yeah, you're out of the mainstream. The reason for this notation is that mathematicians have been studying elliptic curves for far longer than cryptographers have been using them in crypto, and mathematicians have used the additive notation ($eQ$ rather than $Q^e$), for reasons that make sense in the mathematical context. That said, many folks studying crypto have the same reaction you do, because they were initially trained on the integer discrete log problem rather than elliptic curve discrete log problem, and their intuition follows what they learned first. $\endgroup$
    – D.W.
    Commented Sep 19, 2013 at 22:55
  • 3
    $\begingroup$ "... you could explain that at least one major crypto library (RSA's BSAFE) does use it, for reasons that are unclear..." - there's actually $10,000,000 reasons. See Secret contract tied NSA and security industry pioneer. $\endgroup$
    – user10496
    Commented Dec 26, 2013 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.