[Cryptography] Defending against weak/trapdoored keys

[Jerry Leichter]

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

This particular class of attacks can be eliminated by using a verifiably randomly generated prime.  You can generate one using some kind of ceremony where a number of parties jointly construct the random starting point, publish the result together with their attestation that they were present and the random value was derived using a pre-agreed public procedure based on values published by them and the other participants; and then feeding that random value into another pre-agreed public procedure for generating a prime.  Anyone can then check the results by starting from the attested, published random values and running the algorithms.

Alternatively, you could get a similar effect by pre-publishing an algorithm that will take as input a large number of values that will be published at a pre-agreed time in the future.  For example, you might take the highest temperature recorded on a particular day in the future for a long list of cities, as published by a pre-determined collection of newspaper editions.

I'm a bit leery of the idea of using "some number of digits of pi" because then you get the problem of what the starting point should be.  If I can choose any starting point, I can probably mount an attack.  And there are plenty of mathematical constants in place of pi.  If I allow combinations, the potential for "cooking" the result gets that much higher.  This idea worked fine the first couple of times - when the random values were very early in pi, for example - but you quickly run out of variations that way.  Give the chooser too much freedom "to avoid values that have been used in other algorithms" and you start to give him the freedom to force a very safe-looking but spiked value.

                                                        -- Jerry