While it doesnt hurt as a partial sanity check, but with a huge false negative rate (ie it wont complain many many times even though the entropy is too small because it cant measure entropy, just the occasional side effect that two computers generated the same value), it doesnt robustly fix the problem which is the entropy of the device RNG is woefully small.
eg say the entropy is 20-bits and there are enough clients participating that mostly you get a collision for any of the 2^20 (1million) keys. So then you tell it to try again, and it repeatedly does until there is no collision. All you've done is add a new entry to your previously seen public key table on the server. No entropy was added. You cant really (securely) send entropy over the network to a device with no entropy because an eavesdropper can read whatever you send it. There is another RNG problem also where if you add entropy in too small chunks the attacker can also brute force in stages. The yarrow design was supposed to defend against that. eg consider you break in and copy rng state, then the user adds 32-bits, draws one externally published or verifiable output - eg a nonce or encryption using a random key etc, then adds another 32-bits and repeat. Well that remains insecure indefinitely because the attacker can brute force each 32-bits independently. As a last resort defense its probably better to send the client some randomness in the clear, or encrypted with a key exchange depending on what randomness it has - at least then in the off chance that the attacker missed those messages, you retain some security rather than going forward with an insecure public key... But really the device itself should be tracking what entropy it has as it is the only device in a position to know that and refraining from generating cryptographic keys with under 128-bits of entropy... Adam On 18 February 2012 00:23, Stephen Farrell <[email protected]> wrote: > > Hiya, > > > On 02/17/2012 11:11 PM, Adam Back wrote: >> >> 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. > > > Sure. But wouldn't this protocol still help then? Assuming that > protocol clients don't ignore the known-bad answers, they'd > hopefully iterate until they get a not-known-bad key one way or > another. > > I think so, but maybe you're seeing something I'm not. > > Something not that clear in the -00 is that the responder here > can supply random bits as a side effect of answering the > query. (The -01 will make this clearer when its ready.) > > > S. > >> >> 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 >> > _______________________________________________ therightkey mailing list [email protected] https://www.ietf.org/mailman/listinfo/therightkey
