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
(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)
Steps to Reproduce:
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
Package dev-libs/libtomcrypt uses libtommath but doesn't seem to be calling mp_prime_next_prime() anymore (grep returns nothing)
Created attachment 238887 [details, diff]
Fix for mp_prime_next_prime() bug when checking generated prime
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:
The dropbear issue has been moved to bug 328409
Upstream has released libtommath-0.42.0 which fixes this issue.
Note that upstream site which was down since ~2008 is now back.
I added libtommath-0.42.0 to CVS which fixes the issue.
(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"
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 ;)
Stable for HPPA.
amd64 done. Thanks Agostino and Ian
ppc/ppc64 stable, last arch done
Thanks, everyone. GLSA Vote: no.
no too, and closing.