Bug 615088 - libtommath: weakness in mp_prime_next_prime()
Summary: libtommath: weakness in mp_prime_next_prime()
Alias: None
Product: Security Response
Classification: Other
Component: vulnerability
Version: unspecified
Hardware: All
OS: Linux
Target Milestone: ---
Assignee: Simone Caronni
QA Contact:
Depends On: 994505
TreeView+ depends on / blocked
Reported: 2010-07-15 21:45 UTC by Vincent Danen
Modified: 2019-09-29 12:37 UTC (History)
7 users (show)

Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Clone Of:
Last Closed: 2013-08-19 07:23:19 UTC

Attachments (Terms of Use)

Description Vincent Danen 2010-07-15 21:45:53 UTC
A bug in libtommath was reported to Gentoo [1] where the mp_prime_next_prime() is supposed to find the next prime number based on a given prime number.  The prime testing code has a bug and will test t times the same prime from ltm_prime_tab, resulting in potentially weaker prime testing.

The offset in ltm_prime_tab is supposed to be x (the incrementing value in the for loop), rather than t, which does not change.

144       /* is this prime? */
145       for (x = 0; x < t; x++) {
146           mp_set(&b, ltm_prime_tab[t]);
147           if ((err = mp_prime_miller_rabin(a, &b, &res)) != MP_OKAY) {
148              goto LBL_ERR;
149           }
150           if (res == MP_NO) {
151              break;
152           }
153       }

libtommath is also embedded in dropbear, which is an ssh server/client, and as a result may affect the integrity of generated keys (I don't know this for sure, but a comment in the Gentoo bz [2] implies this may be a problem, as upstream is considering the possibility).

Similar code exists in silc-toolkit's lib/silcmath/tma.c, but it properly uses x (silc-toolkit-1.0.2/lib/silcmath/tma.c):

5602       for (x = PRIME_SIZE - 2; x >= 0; x--) {
5603           if (mp_cmp_d(a, ltm_prime_tab[x]) != MP_LT) {

Clamav has similar code as well in libclamav/bignum.c but is similar to that in silc-toolkit (looks identical).

The fix is to change "ltm_prime_tab[t]" to "ltm_prime_tab[x]".

I also believe that having libtommath embedded in dropbear would be against our policies, so we should try to make dropbear use the system libtommath.  dropbear is not compiled static, so we should be able to make it use the system libtommath rather than its own internal copy.

[1] http://bugs.gentoo.org/show_bug.cgi?id=328383
[2] http://bugs.gentoo.org/show_bug.cgi?id=328409#c2

Comment 1 Vincent Danen 2010-07-15 21:51:02 UTC
The CVSSv2 score is likely nonsense because I'm not sure what the full impact of this issue is.

Can someone investigate whether it is possible to make dropbear link against the system libtommath?  That would be the ideal solution to fix dropbear, and then libtommath can be patched to correct this.

I'm also going to ask upstream about this as well, and for clarification on the key issue as noted in the Gentoo report.

Comment 2 Lennert Buytenhek 2010-07-16 08:31:52 UTC
If either p or q is inadvertently composite, the computation of phi(n) as (p-1)(q-1) will likely be incorrect, and the computed decryption exponent as e^-1 mod (p-1)(q-1) will likely not satisfy d * e = 1 mod phi(n).

I.e. there's a good chance that if p or q do happen to be composite numbers, the produced public and private keys will not be a valid key pair, and things encrypted with the public key will fail to decrypt with the private key.

(If d = e^-1 mod (p-1)(q-1) does happen to also satisfy d * e = 1 mod phi(n), then you would have a valid key pair, but one that is weaker (i.e. one where n is not the product of two large primes that are similar in magnitude, which would make n easier to factor). I'll have to think a bit more about how likely this would be.)

Comment 3 Vincent Danen 2010-07-16 18:30:09 UTC
Ok, talking with upstream, the reasoning behind embedding libtommath in dropbear was because a lot of distros, at the time, did not ship libtommath.  He is going to be adding a compile argument to allow for it, and says that it should be fine to use system libtommath.

He also indicates that, while he is still investigating, he doesn't feel that key collisions are feasible since it is still generating random values, although it may be possible to determine the private key from the public key (although this is just theoretical speculation).

At any rate, updating libtommath with this fix and making dropbear use the system libtommath seems to be the way to proceed with this.

Comment 4 Lennert Buytenhek 2010-07-28 19:28:05 UTC
Although I can't formally prove it, it seems unlikely that if p or q or both are composite you would end up with an actual valid public/private key pair.

In other words, I don't think one needs to worry about there being "bad" keys out there.

Comment 5 Matt Johnston 2010-07-29 12:18:00 UTC
As a different measure I've generated 3.9 million Dropbear DSA keys over the past week and no bad primes were seen. I tested after each mp_prime_next_prime() call with mp_prime_is_prime(), the latter doesn't suffer from this bug.

I would expect calculating the q parameter for DSA to be a lot more susceptible to prime generation failure since it is only a 160 bit value - it needs 18 rounds of Miller-Rabin versus 8 for RSA (512 bit minimum size).

Of course that many key-generation iterations doesn't prove it isn't a problem, but it does suggest that it won't be a widespread issue to worry about.

Using the system libtommath/libtomcrypt for Dropbear won't work straight away due to symbol conflicts with "rsa_key" - it's straightforward to fix, hopefully will get a release out not too long.

Dropbear developer

Comment 6 Christopher Meng 2013-08-05 05:18:12 UTC
(In reply to Matt Johnston from comment #5)
Hi Matt,

Can I use system libraries now?


Comment 7 Matt Johnston 2013-08-07 00:54:29 UTC
Dropbear 0.53 (Feb 2011) builds against system libtomcrypt/libtommath if available and also fixes the bundled libtommath. That is problematic on Fedora - it doesn't look like system libtommath ever got the fix for this bug?

Comment 8 Christopher Meng 2013-08-08 02:52:19 UTC
(In reply to Matt Johnston from comment #7)
> Dropbear 0.53 (Feb 2011) builds against system libtomcrypt/libtommath if
> available and also fixes the bundled libtommath. That is problematic on
> Fedora - it doesn't look like system libtommath ever got the fix for this
> bug?

I have notified the maintainer of tommath, hope he will update it soon.


Comment 9 Simone Caronni 2013-08-08 13:33:59 UTC
Working on it, give me some time. I'm still struggling with all the latex/texlive/java issues after the mass rebuild.

Comment 10 Simone Caronni 2013-08-08 15:18:16 UTC
libtommath is built, waiting on another component to release updates in updates-testing.

I never noticed this bug, a bug on libtommath has never been opened. I will reference this in the update.

Note You need to log in before you can comment on or make changes to this bug.