[GNU Crypto] An attack against SRP based on a flaws in the primality test.

[Daniel Bleichenbacher]

I've analyzed the primality test in Gnu Crypto version 1.1.0 and found a number 
of flaws.
The flaws in the library are serious and can be used to attack SRP.

List of flaws:
--------------

(1.) The number 1 is usually not considered to be a prime, but isProbablePrime 
returns true.
(2.) isProbablePrime returns false for all primes in SMALL_PRIME.
(3.) The bases for the Euler test are fixed. But they should be chosen randomly.
(4.) DO_MILLER_RABIN is false by default. It should be true, and in fact I see 
no
     reason to let a user turn the Miller-Rabin test off at all.
(5.) The number of rounds for the Miller-Rabin test is incorrect. One should
     perform k rounds with randomly chosen bases to guarantee that a composite 
number
     passes the test with a probability smaller than 4^{-k}.


(6.) There is also a flaw in the SRP implementation: Here only the 
deterministic part
     of the primality test (i.e. passEulerCriterion) is used to check the group 
parameters.

Explanations:
-------------

Assume a user in a cryptographic application receives an integer from an 
untrusted source, and
therefore has to verify that this integer is prime. In such a situation the 
user has to assume that
the integer comes from an adversary that has specially crafted a counter 
example that passes the
test (rsp. passes the test with maximal probability). Chosing a fixed set of 
bases for the Miller-Rabin
test is then a really bad idea. In particular, Alford, Granville and Pomerance 
have shown that for
every fixed set of bases there exist infinitively many composite numbers that 
pass the test.

The result by Damgard, Landrock and Pomerance "Average case error estimates for 
the strong probable prime test"
is like the title says an average case result. It can only be used when the 
number that is tested has
been chosen randomly. However, when the integer comes from a potential 
adversary then no such assumption
can be made. In particular, an adversary could submit an integer, which is a 
strong pseudoprime to 1/4 of
all bases. Hence 50 MR tests are necessary to bound the probability for an 
incorrect result in a prime verification
to 2^{-100}.

Exploiting the flaws for an attack:
-----------------------------------

Finding counterexample for the primality test is too easy. E.g.: here are just 
some composite numbers from my
thesis:


 168790877523676911809192454171451,
 1088781536295680823159869241893780851,
 6737122462074619354527015408434000671,
 167362055430542431223639618151191172751,
 29097303612595780926342159603334420097591,
 1943507923865720818249653583964807114160978140504971,
 62615921936975862712921940128790712192273358769807620171,
 68528663395046912244223605902738356719751082784386681071,

Therefore I've constructed some parameters that would break SRP. To do so one 
has to find
a tuple g, p, q, such that
 (I)    p = 2q+1
 (II)   q passes the primality test
 (III)  p passes the primality test
 (IV)   g appears to be a generator of the multiplicative group modulo p.
 (V)    computing discrete logs of y=g^x (mod p) is easy.

The tuples I've actually constructed look like this: p is a probable prime
with a bit size between 1024 and 2000. q is the product of small (27-60 bit) 
primes, so that discrete logs
can be computed efficiently using the algorithm by Pohlig-Hellman. g can be 
chosen to either generate
the full multiplicative group or just the subgroup of size 2 times the smallest 
prime factor of q.
Since SRP assumes q is prime it will not check correctly whether g is a 
generator or not.

Computing discrete logs in subgroups of order ~2^27 can be done in basically no 
time, e.g., by precomputing
lookup tables first. On the other hand I've spend about 200 h of CPU time for 
finding the tuples (g,p,q).

Implementation:
---------------

I have a small test program, for verifying the flaws in the primality test. I'm 
not posting this program here,
because it contains the pseudoprimes that could be used against SRP. You'll 
have to request it by e-mail.

I haven't implemented the attack against SRP, since I assume that this will not 
be necessary in order to
have GNU crypto fixed.

Recommendation:
---------------

Make the test as simple as possible,
i.e., do a trial division first then 50 rounds of Miller-Rabin with random 
bases.
Everything else increases with high probability the probability that the test
returns an incorrect result.



Daniel Bleichenbacher
Bell Laboratories
600 Mountain Av.
Murray Hill, NJ 07974