Fwd: Tor security advisory: DH handshake flaw

Simon Josefsson jas at extundo.com
Thu Sep 1 09:04:43 EDT 2005

Werner Koch <wk at gnupg.org> 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.


The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

More information about the cryptography mailing list