Breaking a cryptographic protocol with pseudoprimes
01 January 2005
The Miller-Rabin pseudo primality test is widely used in cryptographic libraries, because of its apparent simplicity. But the test is not always correctly implemented. For example the pseudo primality test in GNU Crypto 1.1.0 uses a fixed set of bases. This paper shows how this flaw can be exploted to break the SRP implementation in GNU Crypto. The attack is demonstrated by explicitly constuctiong pseudoprimes that satisfie the parameter checks in SRP.