Bug 615088
| Summary: | libtommath: weakness in mp_prime_next_prime() | ||
|---|---|---|---|
| Product: | [Other] Security Response | Reporter: | Vincent Danen <vdanen> |
| Component: | vulnerability | Assignee: | Simone Caronni <negativo17> |
| Status: | CLOSED CURRENTRELEASE | QA Contact: | |
| Severity: | medium | Docs Contact: | |
| Priority: | medium | ||
| Version: | unspecified | CC: | buytenh, i, itamar, jeremy, matt, negativo17, security-response-team |
| Target Milestone: | --- | Keywords: | Security |
| Target Release: | --- | ||
| Hardware: | All | ||
| OS: | Linux | ||
| Whiteboard: | |||
| Fixed In Version: | Doc Type: | Bug Fix | |
| Doc Text: | Story Points: | --- | |
| Clone Of: | Environment: | ||
| Last Closed: | 2013-08-19 07:23:19 UTC | Type: | --- |
| Regression: | --- | Mount Type: | --- |
| Documentation: | --- | CRM: | |
| Verified Versions: | Category: | --- | |
| oVirt Team: | --- | RHEL 7.3 requirements from Atomic Host: | |
| Cloudforms Team: | --- | Target Upstream Version: | |
| Embargoed: | |||
| Bug Depends On: | 994505 | ||
| Bug Blocks: | |||
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. 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.) 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. 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. 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. Matt Dropbear developer (In reply to Matt Johnston from comment #5) Hi Matt, Can I use system libraries now? Thanks. 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? (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. Thanks. Working on it, give me some time. I'm still struggling with all the latex/texlive/java issues after the mass rebuild. 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. Update landed in stable for f18 and f19 (el6 pending); don't know why the ticket has not been closed by Bodhi: https://admin.fedoraproject.org/updates/FEDORA-2013-14482/libtommath-0.42.0-2.fc19,libtomcrypt-1.17-20.fc19 https://admin.fedoraproject.org/updates/FEDORA-EPEL-2013-11179/libtommath-0.42.0-2.el6,libtomcrypt-1.17-20.el6 https://admin.fedoraproject.org/updates/FEDORA-2013-14488/libtommath-0.42.0-2.fc18,libtomcrypt-1.17-20.fc18 |
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