328383
2010-07-15 12:08:18 +0000
<dev-libs/libtommath-0.42.0: weakness in mp_prime_next_prime()
2011-10-08 21:41:42 +0000
1
1
1
Unclassified
Gentoo Security
Vulnerabilities
unspecified
All
Linux
RESOLVED
FIXED
B4 [noglsa]
High
normal
---
1
mark
security
jer
maintainer-needed
---
0
oldest_to_newest
3067281
0
mark
2010-07-15 12:08:18 +0000
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)
3067373
1
238887
mark
2010-07-15 13:49:15 +0000
Created attachment 238887
Fix for mp_prime_next_prime() bug when checking generated prime
3067409
2
mark
2010-07-15 14:25:02 +0000
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)
3067441
3
mark
2010-07-15 15:13:47 +0000
The dropbear issue has been moved to bug 328409
3075415
4
mark
2010-07-23 14:57:09 +0000
Upstream has released libtommath-0.42.0 which fixes this issue.
http://www.libtom.org/?page=download&newsitems=5&whatfile=ltm
Download from:
http://www.libtom.org/files/ltm-0.42.0.tar.bz2
http://www.libtom.org/files/ltm-0.42.0.tar.bz2.sig
Note that upstream site which was down since ~2008 is now back.
4042229
5
radhermit
2011-06-10 01:01:33 +0000
I added libtommath-0.42.0 to CVS which fixes the issue.
4044410
6
underling
2011-06-12 18:31:57 +0000
(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:
=dev-libs/libtommath-0.42.0
Target keywords : "amd64 arm hppa ppc ppc64 x86"
4044426
7
ago
2011-06-12 18:43:45 +0000
amd64 ok.
Anyway for be picky, in src_test, when a binary for test are generated, "-O?" is not respected.
e.g.
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 ;)
4044785
8
phajdan.jr
2011-06-13 10:03:12 +0000
x86 stable
4045495
9
idella4
2011-06-13 21:29:59 +0000
amd64:
ok
4045693
10
jer
2011-06-14 03:24:09 +0000
Stable for HPPA.
4046305
11
maekke
2011-06-14 19:52:49 +0000
arm stable
4048893
12
hwoarang
2011-06-18 07:49:51 +0000
amd64 done. Thanks Agostino and Ian
4049695
13
xarthisius
2011-06-19 12:03:43 +0000
ppc/ppc64 stable, last arch done
4050257
14
underling
2011-06-20 03:31:35 +0000
Thanks, everyone. GLSA Vote: no.
4134753
15
py
2011-10-08 21:41:42 +0000
no too, and closing.
238887
2010-07-15 13:49:15 +0000
2010-07-15 13:49:15 +0000
Fix for mp_prime_next_prime() bug when checking generated prime
libtommath-0.41-mp_prime_next_prime_fix.patch
text/plain
544
mark
ZGlmZiAtcmJCVTMgbGlidG9tbWF0aC0wLjQxLW9yaWcvYm5fbXBfcHJpbWVfbmV4dF9wcmltZS5j
IGxpYnRvbW1hdGgtMC40MS9ibl9tcF9wcmltZV9uZXh0X3ByaW1lLmMKLS0tIGxpYnRvbW1hdGgt
MC40MS1vcmlnL2JuX21wX3ByaW1lX25leHRfcHJpbWUuYwkyMDA3LTAzLTExIDA4OjQ1OjExLjAw
MDAwMDAwMCArMDkwMAorKysgbGlidG9tbWF0aC0wLjQxL2JuX21wX3ByaW1lX25leHRfcHJpbWUu
YwkyMDEwLTA3LTE1IDIyOjQ2OjU0LjAwMDAwMDAwMCArMDkwMApAQCAtMTQzLDcgKzE0Myw3IEBA
CiAKICAgICAgIC8qIGlzIHRoaXMgcHJpbWU/ICovCiAgICAgICBmb3IgKHggPSAwOyB4IDwgdDsg
eCsrKSB7Ci0gICAgICAgICAgbXBfc2V0KCZiLCBsdG1fcHJpbWVfdGFiW3RdKTsKKyAgICAgICAg
ICBtcF9zZXQoJmIsIGx0bV9wcmltZV90YWJbeF0pOwogICAgICAgICAgIGlmICgoZXJyID0gbXBf
cHJpbWVfbWlsbGVyX3JhYmluKGEsICZiLCAmcmVzKSkgIT0gTVBfT0tBWSkgewogICAgICAgICAg
ICAgIGdvdG8gTEJMX0VSUjsKICAgICAgICAgICB9Cg==