I dont think this is going to be very robust because 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 14:12, Stephen Farrell <[email protected]> wrote: > > Dunno if anyone else thinks this might be interesting > but I do:-) > > So I sketched out an initial idea for how it might fit > in here. [1] > > Comments welcome. > > S. > > [1] http://www.ietf.org/id/draft-farrell-kc-00.txt > > > On 02/15/2012 07:17 PM, Stephen Farrell wrote: >> >> >> Hiya, >> >> I guess the recent publications about common factors [1,2] >> are something else that this group might want to consider. >> >> I wonder if an rsa modulus checker protocol might help or >> something. Not sure if that's something that could be run >> quickly enough though, other than for the straight >> duplicates or dumbass things with small factors you should >> spot yourself. Anyone know? >> >> Or maybe you could register your public key and get a >> nonce, then come back periodically to see if any problems >> have been detected for your key. >> >> And yes, better prngs are needed, but there'll probably >> always be bad ones out there. >> >> S. >> >> [1] http://eprint.iacr.org/2012/064 >> [2] >> >> http://it.slashdot.org/story/12/02/15/1540212/factorable-keys-twice-as-many-but-half-as-bad >> >> _______________________________________________ >> therightkey mailing list >> [email protected] >> https://www.ietf.org/mailman/listinfo/therightkey >> > _______________________________________________ > therightkey mailing list > [email protected] > https://www.ietf.org/mailman/listinfo/therightkey _______________________________________________ therightkey mailing list [email protected] https://www.ietf.org/mailman/listinfo/therightkey
