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

[Casey Marshall]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

>>>>> "Daniel" == Daniel Bleichenbacher <address@hidden> writes:

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

Daniel> List of flaws: --------------

Daniel> (1.) The number 1 is usually not considered to be a prime, but
Daniel> isProbablePrime returns true.
Daniel> (2.) isProbablePrime returns false for all primes in
Daniel> SMALL_PRIME.

I've changed this behavior in the CVS sources.

Daniel> (3.) The bases for the Euler test are fixed. But they should
Daniel> be chosen randomly.

I'm not familiar with the algorithm, but will investigate this.

Daniel> (4.) DO_MILLER_RABIN is false by default. It should be true,
Daniel> and in fact I see no reason to let a user turn the
Daniel> Miller-Rabin test off at all.

I don't know why this is (I'm guessing performance). The doMillerRabin
property in the Properties class is now true by default.

Daniel> (5.) The number of rounds for the Miller-Rabin test is
Daniel> incorrect. One should perform k rounds with randomly chosen
Daniel> bases to guarantee that a composite number passes the test
Daniel> with a probability smaller than 4^{-k}.

Will investigate.

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

I don't see any reason why these tests can't be changed to
isProbablePrime.

I'll try to get these issues resolved, and get 2.0.0 released within
the next week or two.

Thanks for the info.

- -- 
Casey Marshall || address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)
Comment: Processed by Mailcrypt 3.5.7 <http://mailcrypt.sourceforge.net/>

iD8DBQFABL5xgAuWMgRGsWsRAnYGAKCA9AA1NEeC3h21HLAXhzEa18Th6ACfbT1U
YFeDfX/uV1CU+pvcBFOIkXM=
=brI5
-----END PGP SIGNATURE-----