[Cryptography] Dual_EC_DRBG backdoor: a proof of concept

[Theodore Ts'o]

On Thu, Jan 02, 2014 at 10:16:25PM -0500, Thierry Moreau wrote:
> Jon Callas wrote:
> (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.

Um, where are you going to get the true entropy from?  If you are
willing to assume that you can seed the device with true entropy, then
you can just use an AES-based CRNG.  Sure, it's not "provably secure",
but (a) it's not like we've proven that factorization is hard, only
mathematicians can't crack it to date, and if it doesn't, we're kind
of toast anyway since we assymetric crypto algorthms based on this
assumption all over the place, and (b) the exact same argument holds
for AES.  We use AES all over the place for our symmetric crypto, and
if AES is broken, then sure, the RNG is broken, but so is everything
else.

The hard part is "seed the device with true entropy".  #1, where does
that come from, and #2, do you trust the entity who seeded the
entropy, either against maliciousness (did the Apple really cooperate
with the NSA, or not), or simple outright incompetence (consider how
many manufacturers can't even get unique ethernet MAC addresses
right).

I recognize that there are limits to software-based entropy collection
systems, such as that which is used in Linux's /dev/random.  But at
least the algorithm is one which can be openly analyzed and peer
reviewed.  How do you peer review whether or not Apple (or more
specifically, Foxconn) seeded your iphone with "true entropy".  And
even if you reviewed their processes at one point in time, who's to
say whether either the Chinese MSS or the US's NSA hasn't managed to
bribe an assembly line worker after your review of their manufacturing
procedure?

							- Ted