[Cryptography] Dual_EC_DRBG backdoor: a proof of concept

Florian Weimer fw at deneb.enyo.de
Sun Jan 5 13:51:47 EST 2014


* Jon Callas:

> 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.

Conventional wisdom, yes, but the mathematics don't actually add up:

| According to inequality (2), the BBS generator is secure against an
| adversary whose time is bounded by −2¹⁹². (Yes, that's a negative
| sign!) In this case we get a "better" result from inequality (3),
| which bounds the adversary’s time by 2⁻²⁶⁴. (Yes, that's a negative
| exponent!)

Koblitz and Menezes, "Another look at provable security II",
<http://eprint.iacr.org/2006/229.pdf>


More information about the cryptography mailing list