Gentoo Websites Logo
Go to: Gentoo Home Documentation Forums Lists Bugs Planet Store Wiki Get Gentoo!
Bug 328383 - <dev-libs/libtommath-0.42.0: weakness in mp_prime_next_prime()
Summary: <dev-libs/libtommath-0.42.0: weakness in mp_prime_next_prime()
Alias: None
Product: Gentoo Security
Classification: Unclassified
Component: Vulnerabilities (show other bugs)
Hardware: All Linux
: High normal (vote)
Assignee: Gentoo Security
Whiteboard: B4 [noglsa]
Depends on:
Reported: 2010-07-15 12:08 UTC by Mark Karpeles
Modified: 2011-10-08 21:41 UTC (History)
2 users (show)

See Also:
Package list:
Runtime testing required: ---

Fix for mp_prime_next_prime() bug when checking generated prime (libtommath-0.41-mp_prime_next_prime_fix.patch,544 bytes, patch)
2010-07-15 13:49 UTC, Mark Karpeles
no flags Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Mark Karpeles 2010-07-15 12:08:18 UTC
Function mp_prime_next_prime() (bn_mp_prime_next_prime.c) will find the next prime number based on a given prime number.

It will increment by a given step and test each returned number to see if those are prime. The "t" parameter defines the number of Miller-Rabin trials done which each prime contained in table ltm_prime_tab, starting at 0.

However 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.

bn_mp_prime_next_prime.c line 146

mp_set(&b, ltm_prime_tab[t]);
should be:
mp_set(&b, ltm_prime_tab[x]);

(the offset in ltm_prime_tab is supposed to be x, the incrementing value from the for loop, as in bn_mp_prime_is_prime.c line 63, testing the same prime again and again has no effect)

Reproducible: Always

Steps to Reproduce:

Actual Results:  
Potentially weaker prime (in worst case with t=1 - which is the effective case here - mp_prime_miller_rabin has 25% chances of being wrong as explained in bn_mp_prime_miller_rabin.c on line 22).
Also CPU is wasted doing the same operation again and again for nothing

Expected Results:  
Strong primes

Package dev-libs/libtomcrypt uses libtommath but doesn't seem to be calling mp_prime_next_prime() anymore (grep returns nothing)
Comment 1 Mark Karpeles 2010-07-15 13:49:15 UTC
Created attachment 238887 [details, diff]
Fix for mp_prime_next_prime() bug when checking generated prime
Comment 2 Mark Karpeles 2010-07-15 14:25:02 UTC
Update: mp_prime_next_prime() is used in net-misc/dropbear-0.52-r1

File dropbear-0.52/libtommath/bn_mp_prime_next_prime.c has been confirmed with the same bug.

I will contact upstream for dropbear to notify about this bug and let them fix their bundled libtommath version.

mp_prime_next_prime() called at:
./dropbear-0.52/gendss.c:83 (t=18)
./dropbear-0.52/genrsa.c:110 (t=8)
Comment 3 Mark Karpeles 2010-07-15 15:13:47 UTC
The dropbear issue has been moved to bug 328409
Comment 4 Mark Karpeles 2010-07-23 14:57:09 UTC
Upstream has released libtommath-0.42.0 which fixes this issue.

Download from:

Note that upstream site which was down since ~2008 is now back.
Comment 5 Tim Harder gentoo-dev 2011-06-10 01:01:33 UTC
I added libtommath-0.42.0 to CVS which fixes the issue.
Comment 6 Tim Sammut (RETIRED) gentoo-dev 2011-06-12 18:31:57 UTC
(In reply to comment #5)
> I added libtommath-0.42.0 to CVS which fixes the issue.

Great, thank you, Tim.

Arches, please test and mark stable:
Target keywords : "amd64 arm hppa ppc ppc64 x86"
Comment 7 Agostino Sarubbo gentoo-dev 2011-06-12 18:43:45 UTC
amd64 ok.

Anyway for be picky, in src_test, when a binary for test are generated, "-O?" is not respected.

cc -march=native -O2 -g0 -I./ -Wall -W -Wshadow -Wsign-compare -O3 -funroll-loops -fomit-frame-pointer demo/demo.o libtommath.a -o test

But it does not block obviously ;)
Comment 8 Paweł Hajdan, Jr. (RETIRED) gentoo-dev 2011-06-13 10:03:12 UTC
x86 stable
Comment 9 Ian Delaney (RETIRED) gentoo-dev 2011-06-13 21:29:59 UTC

Comment 10 Jeroen Roovers (RETIRED) gentoo-dev 2011-06-14 03:24:09 UTC
Stable for HPPA.
Comment 11 Markus Meier gentoo-dev 2011-06-14 19:52:49 UTC
arm stable
Comment 12 Markos Chandras (RETIRED) gentoo-dev 2011-06-18 07:49:51 UTC
amd64 done. Thanks Agostino and Ian
Comment 13 Kacper Kowalik (Xarthisius) (RETIRED) gentoo-dev 2011-06-19 12:03:43 UTC
ppc/ppc64 stable, last arch done
Comment 14 Tim Sammut (RETIRED) gentoo-dev 2011-06-20 03:31:35 UTC
Thanks, everyone. GLSA Vote: no.
Comment 15 Pierre-Yves Rofes (RETIRED) gentoo-dev 2011-10-08 21:41:42 UTC
no too, and closing.