Bug 615088

Summary: libtommath: weakness in mp_prime_next_prime()
Product: [Other] Security Response Reporter: Vincent Danen <vdanen>
Component: vulnerabilityAssignee: Simone Caronni <negativo17>
Severity: medium Docs Contact:
Priority: medium    
Version: unspecifiedCC: buytenh, i, itamar, jeremy, matt, negativo17, security-response-team
Target Milestone: ---Keywords: Security
Target Release: ---   
Hardware: All   
OS: Linux   
Whiteboard: public=20100715,reported=20100715,source=gentoo,impact=moderate,cvss2=3.6/AV:N/AC:H/Au:S/C:P/I:P/A:N,fedora-all/libtommath=affected,fedora-all/dropbear=affected
Fixed In Version: Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of: Environment:
Last Closed: 2013-08-19 03:23:19 EDT Type: ---
Regression: --- Mount Type: ---
Documentation: --- CRM:
Verified Versions: Category: ---
oVirt Team: --- RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: ---
Bug Depends On: 994505    
Bug Blocks:    

Description Vincent Danen 2010-07-15 17:45:53 EDT
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 17:51:02 EDT
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 04:31:52 EDT
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 14:30:09 EDT
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 15:28:05 EDT
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 08:18:00 EDT
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 01:18:12 EDT
(In reply to Matt Johnston from comment #5)
Hi Matt,

Can I use system libraries now?

Comment 7 Matt Johnston 2013-08-06 20:54:29 EDT
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-07 22:52:19 EDT
(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 09:33:59 EDT
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 11:18:16 EDT
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.