Skip to main content

Breaking a cryptographic protocol with pseudoprimes

01 January 2005

New Image

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.