[Cryptography] Dual_EC_DRBG backdoor: a proof of concept

[Thierry Moreau]

Jon Callas wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> 
> 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, ...
> 
> 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.
> 

This is the only thing that the alluded BBS "backdoor" allows. In other 
words, the backdoor allows one to write a custom-made statistical test 
that the generator will fail. The backdoor does not allow the recovery 
of the PRNG state from a fraction of the output sequence -- or at least 
I never saw the slightest hint, speculation, or academic author 
conjecture that this would be possible for any fraction less than 1.

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

Out of memory, the engineering issue is solved as follows:

(A) Generate a first BBS modulus and discard the prime factors P and Q.

(B) When provisioning a secure device, seed the first BBS with true 
entropy, then generate a device-specific BBS modulus and discard prime 
factors P' and Q'. Don't use the first BBS for any other purpose 
starting with the same seed.

(C) In operations, occasionally re-seed the device-specific BBS as you 
would do with any deterministic PRNG.

If you don't trust the software for the discard operation in (A) and 
(B), then you shouldn't trust the software for any other crypto algorithm.

For bootstrap your confidence, you recursively perform (A)-(B)-(C) with 
  (C) being used for the next (A) in the recursion, until the "security 
by management exhaustion" paradigm applies.

Have fun with crypto-grade PRNG selection and implementation design!

-- 
- Thierry Moreau