[Cryptography] Dual_EC_DRBG backdoor: a proof of concept

[Thierry Moreau]

Theodore Ts'o wrote:
> 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?

It's interesting that you ask this question in the specific context of 
device provisioning. Maybe it's not intentional, but I intend to answer 
the question in this specific context.

If you provision a secure device for a usage that deserves strong 
protection, you may temporarily attach a trusted secret random data 
source for the provisioning operation.

Obviously, entropy source assurance is a system-level assurance 
challenge. If you procure turnkey systems from a given vendor, you 
either trust the vendor, or add an entropy source solution as an 
accessory. This is independent of a PRNG algorithm selection.

   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.

But Linux itself is not a system-level solution. Even a Linux 
distribution is not a system-level solution. It is when installed on a 
given hardware that we get a system-level solution and we may make a 
final assurance assessment.

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

You define the problem as an impossible one. It's impossible for you and 
I to ensure John Doe can trust a manufacturing process.

Maybe we can first address the needs in usage contexts where security 
impediments are offset by the value of additional protections. At least 
this is how I see my mission (in which the BBS algorithm has its merits).

-- 
- Thierry Moreau