[Botan-announce] Security Notification: Botan 1.10.8 + 1.11.9 released

Jack Lloyd lloyd at randombit.net
Thu Apr 10 20:10:27 EDT 2014

I've released new versions of Botan (1.10.8 and 1.11.9) fixing a serious bug in
prime testing. A change in version 1.8.3 resulted in Miller-Rabin primality
tests being done with a single random base rather than a sequence of such
bases. Miller-Rabin is a probabilistic algorithm where the rate of failure
(classifying a non-prime as prime) decreases as iterations increase, so having
a single test is more or less the worst case scenario.

What are the actual effects of this bug? There are two major cases: generating
a new RSA key (or DSA or DH parameters), and testing an untrusted DH group
provided by a third party (for instance during TLS DHE key exchange, where the
server hands the client an arbitrary DH group). RSA generation should be safe;
a proof (in http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf) shows that
for *randomly* chosen n the probability of a false accept is quite low and and
decreases rapidly as the size of the number increases, for instance with
randomly chosen 600 bit numbers even a single test should fail no more often
than 2^-75. In addition newly generated RSA keys are automatically checked for
consistency (including checking the primes, meaning a second Miller-Rabin
test), so in the event that a key was created with a non-prime factor, the self
test would with high probability fail and the constructor would throw an

The case of DH parameter verification is rather bleaker, as obviously the value
is chosen by the attacker, so about the best we can hope for is the base 3-in-4
detection rate of Miller-Rabin: that is, 75% of the time we would detect this
invalid prime, and 25% of the time we would not, and accept a composite as

I would like to thank Jeff Marrison for finding and reporting this issue.

The only other change in 1.10.8 is a modification for HMAC, which now accepts
keys as large as 512 bytes. This is primarily so PBKDF2 can accept very long

1.11.9 has some changes to PKIX path validation; when validating we return a
set of all the errors with the most severe error being provided as the primary
result. This prevents a seemingly innocuous error (such as an expired
certificate) from hiding an obviously serious error (such as an invalid
signature). A bug that prevented OCSP from working with some common responders
was also fixed. And implementations of HMAC_DRBG and the RFC 6979 deterministic
nonce generator were added.

As always download links are at http://botan.randombit.net/download.html

My apologies on the mess. From the events of this week it appears I'm at least
in good company.


More information about the botan-announce mailing list