Werner Koch <[EMAIL PROTECTED]> writes: > On Mon, 29 Aug 2005 17:32:47 +0200, Simon Josefsson said: > >> which are Fermat pseudoprime in every base. Some applications, >> e.g. Libgcrypt used by GnuPG, use Fermat tests, so if you have control >> of the random number generator, I believe you could make GnuPG believe >> it has found a prime when it only found a Carmichael number. > > 5 Rabin-Miller tests using random bases are run after a passed Fermat > test.
If you control the random number generator, you control which Miller-Rabin bases that are used too. Of course, it must be realized that the threat scenario here is slightly obscure. The scenario I have been thinking about is when an attacker has gained control of the hardware or kernel. The attacker might then be able to see when a crypto library requests randomness, and return carefully constructed data to fool the user. The constructed data should be so the RSA/DH parameters become weak [for the attacker]. The attacker may not be in a position to send the generated prime back home over the network, and doing that may also be detected by firewalls. The target system might not even be networked. Designing this fake random number generator is not trivial, and must likely be done separately for each crypto library that is used. If software only used prime numbers that came with a prime certificate, you combat this attack. Too bad you can't mathematically certify that "real" randomness was used in choosing the prime too. Although perhaps you get pretty close with algorithms that both generate a prime and a prime certificate in one go. Regards, Simon --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]