[cryptography] Duplicate primes in lots of RSA moduli

Marsh Ray marsh at extendedsubset.com
Thu Feb 16 22:18:44 EST 2012

On 02/16/2012 08:42 PM, Jeffrey I. Schiller wrote:
> I've read the code, I know how it works... That's my point. By adding
> additional entropy (in this case the time) between the generation of P
> and Q you setup a situation where it is more likely that two hosts
> will share a P but not a Q.

It is entirely possible to engineer a CSPRNG such that (from the 
perspective of the attacker) all valid values of P are equally likely.

Yes, this is a bit more difficult to do in the first two seconds after 
cold boot on platforms that wasn't designed for it. But still, this is a 
basic test of competence for any crypto system.

If P is generated so badly that two identical Ps are ever likely to be 
produced in the history of the Earth, then the discussion stops there.

> Without that additional entropy P and Q
> would likely be the same.

There is no point in trying to reason about the security of Q. In my 
experience, it is likely to be counterproductive.

If there was some mechanism available by which Q could be generated 
securely after P was not, then you should have used that method for P.

The idea that mixing in the current Unix time between P and Q is going 
to significantly improve matters is particularly absurd. The date of 
generation is in the freaking certificate or PGP key!

> I was probably less precise in my wording then I should have
> been. What I mean is that once P and Q are generated, the state of the
> pseudo random number generator should be destroyed and never used
> again.

Your entropy pool has hopefully been accumulating entropy since system 
boot (or even longer if some was persisted to disk). By throwing away 
what you have, all you are doing is *guaranteeing* worst-case operation.

>  Although in theory it shouldn't be possible to determine
> previous state from current state (i.e., run it backwards to determine
> P and Q based on the state when it was done doing so) it is probably
> safer to assume that the previous state can be derived.

No, one-way functions do exist! If they do not, the system has far 
bigger problems.

If your CSPRNG is not using them, then it is broken and should be thrown 

It's good to be conservative and not rely on more properties than are 
actually needed. But don't compromise simplicity and real robustness in 
the design in order to eliminate dependence on a fundamental and 
well-tested primitive like a OWF.

- Marsh

More information about the cryptography mailing list