[Cryptography] Defending against weak/trapdoored keys

[Henry Baker]

At 11:18 AM 10/13/2016, Jerry Leichter wrote:
>> I'm not at all convinced that random "secure" primes/ECCgroups can be quickly & efficiently generated in real time.
>>
>> However, by using multiple DH's, we might be able to force Eve to have to break them all.
>
>"Might", huh.
>
>The history of attempts to make cryptographic primitives stronger by simply combining them and claiming that the attacker will have to break all is littered with failures.
>
>For example, 2-DES (or similar) falls to a meet-in-the-middle attack; using two cryptographically secure MAC's and checking both isn't much stronger than just using one; and so on.
>
>I would be *very* leery of going this route without a proof.

OK.  Here's a proof outline.

Recall that we're doing *two* *complete* standard DH's (DH1 & DH2); one in either direction.  This means that each DHi uses its *own* (non-correlated) random numbers.  (If we use the same random numbers for both DH1 & DH2, then breaking *either* breaks the other, as well; so we won't do that.)

Assume that DH1 is completely compromised; assume Eve can trivially do discrete logs using DH1's prime and/or ECC group.

So WOLG we know secret1 = DH1.

We need to use this information to deduce (secret1 XOR secret2).

If Alice & Bob stupidly use exactly the same prime and/or ECC group, we are done, because secret1 = secret2, so (secret1 XOR secret2) == 0.  But Alice & Bob aren't that stupid.

Next problem: secret2 (= DH2) is essentially random.  I say "essentially" because it can't be identically 0, but all other choices are uniformly distributed.  So long as p (or the ECC group) is sufficiently large, secret2 is random, and *uncorrelated with secret1*.

(If you're still concerned about information possibly leaking from a few high order bits of secret2 (= DH2), then simply chop them off.)

So secret2 is a uniformly distributed random number.

So (secret1 XOR secret2) is a uniformly distributed random number, so it functions safely for the symmetric session key, so long as DH2 can't be broken.

So the difficulty of this scheme should be max(difficulty DH1,difficulty DH2).