7
$\begingroup$

I saw Martijn Grooten's talk on elliptic curves at BSides London this year, and it helped me understand how elliptic curve crypto works, especially in the case of Diffie-Hellman (ECDH). He also touched on the use of EC for random number generators (e.g. Dual_EC_DRBG) and why they can be flawed / backdoored.

This got me thinking: why do we even bother using EC for CSPRNGs? What drove us to even try? Surely block-cipher based CSPRNGs (e.g. AES-CTR) would be faster and more reliable, with no potential for "hidden number" backdoors? What is the key benefit that EC brings to the world of PRNGs, which outweighs their potential for weakness?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ AES as PRNG may fail. EC-CSPRNGs can't. They give you provably secure random numbers, assuming the ECDLP is intractable and your seed is unpredictable. The only way to attack those generators (like BBS) is to generate the key parameters yourself (like the reference points in DUAL_EC_DRBG) or to guess the seed or to break the reference problem. And this sense of provable security was what most people attracted (and that it was standard in bsafe...) $\endgroup$
    – SEJPM
    Commented Jun 5, 2015 at 12:39
  • $\begingroup$ @SOJPM AES-CTR was just an example - the point I was trying to make is that there other CSPRNG designs out there that don't have the "magic number" problem. That being said, your "provably secure" comment intrigues me - do you have a reference for a proof? I guess the proof relies upon the discrete log problem being known hard? $\endgroup$
    – Polynomial
    Commented Jun 5, 2015 at 12:57
  • 1
    $\begingroup$ In my comment AES-CTR also was only a "sample" for a non-provably secure CSPRNG. DUAL_EC_DRBG should have a similar prove to that BBS has but with EC-discrete logarithm problem (ECDLP) instead of FACTORING. $\endgroup$
    – SEJPM
    Commented Jun 5, 2015 at 16:47
  • $\begingroup$ Indeed DUAL_EC_DRBG seems to have such a proof, but because the instantiation was flawed (outputs too many bits / call) it's insecure with right informations. These links may interest you. $\endgroup$
    – SEJPM
    Commented Jun 5, 2015 at 16:49
  • 1
    $\begingroup$ As the person who gave the presentation that prompted the question, I can fully endorse Samuel Neves's comment. I should have mentioned that, apart from the backdoor, there are other good reasons not to use Dual_EC_DRBG (or ECC in general) in a PRNG. $\endgroup$
    – Martijn Grooten
    Commented Jun 6, 2015 at 17:46

1 Answer 1

Reset to default
6
$\begingroup$

We, for the most part, don't bother with elliptic curve-based pseudorandom generators. DUAL_EC_DRBG was shoehorned into a NIST standard that also included a block cipher generator, CTR_DRBG, and two hash-based ones—Hash_DRBG and HMAC_DRBG—that are actually used in the field.

Number-theoretic generators, which include Blum-Blum-Shub, DUAL_EC_DRBG, and several others, tend to advertise provable security. What this means is that predicting the next bit reduces to solving a presumably hard problem, like integer factorization or the discrete logarithm problem. While this is appealing to mathematicians and theorists, this kind of generator tends to be very slow and hard to implement correctly, i.e., without leaking state information via a side-channel or buggy arithmetic.

Practitioners highly favor generators based on symmetric primitives that are much faster and easy to implement and reason about and—as a bonus—also happen to resist quantum computers, if those ever get built.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Martijn Grooten dropped in to endorse this answer. I'm commenting for him so we can delete the non answer. He's also contemplating "other good reasons not to use ECC in a PRNG without specifying why. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jun 9, 2015 at 0:44

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.