[cryptography] Duplicate primes in lots of RSA moduli

Adam Back adam at cypherspace.org
Fri Feb 17 18:13:18 EST 2012


Further the fact that the entropy seeding is so bad that some
implementations are generating literally the same p value (but seemingly
different q values) I would think you could view the fact that this can be
detected and efficiently exploited via batch GCD as an indication of an even
bigger problem.

Namely if the seeding is that bad you could outright compute all possible
values of p even for cases where p was not shared, by running through the
evidently small by cryptographic standards number of possible PRNG states...

Then you might be looking at more than 1% or whatever the number is that
literally collide in specific p value.  Assuming p is more vulnerable than
q, you could then use the same batch GCD to test.

Adam


On 16 February 2012 21:47, Nico Williams <nico at cryptonector.com> wrote:
> On Thu, Feb 16, 2012 at 12:28 PM, Jeffrey Schiller <jis at qyv.net> wrote:
>>> Are you thinking this is because it causes the entropy estimate in the RNG to be higher than it really is? Last time I checked OpenSSL it didn't block requests for numbers in cases of low entropy estimates anyway, so line 3 wouldn't reduce security for that reason.
>>
>> I  am thinking this because in low entropy cases where multiple boxes generate the same first prime adding that additional entropy before the second prime is generated means they are likely to generate a different second prime leading to the GCD attack.
>
> I'd thought that you were going to say that so many devices sharing
> the same key instead of one prime would be better on account of the
> problem being more noticeable.  Otherwise I don't see the difference
> between one low-entropy case and another -- both are catastrophic
> failures.
>
> Nico
> --
> _______________________________________________
> cryptography mailing list
> cryptography at randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography



More information about the cryptography mailing list