[cryptography] Duplicate primes in lots of RSA moduli
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
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
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.
More information about the cryptography