Cryptology ePrint Archive: Report 2018/749

Prime and Prejudice: Primality Testing Under Adversarial Conditions

Martin R. Albrecht and Jake Massimo and Kenneth G. Paterson and Juraj Somorovsky

Abstract: This work provides a systematic analysis of primality testing under adversarial conditions, where the numbers being tested for primality are not generated randomly, but instead provided by a possibly malicious party. Such a situation can arise in secure messaging protocols where a server supplies Diffie-Hellman parameters to the peers, or in a secure communications protocol like TLS where a developer can insert such a number to be able to later passively spy on client-server data. We study a broad range of cryptographic libraries and assess their performance in this adversarial setting. As examples of our findings, we are able to construct 2048-bit composites that are declared prime with probability \(1/16\) by OpenSSL's primality testing in its default configuration; the advertised performance is \(2^{-80}\). We can also construct 1024-bit composites that always pass the primality testing routine in GNU GMP when configured with the recommended minimum number of rounds. And, for a number of libraries (Cryptlib, LibTomCrypt, JavaScript Big Number, WolfSSL), we can construct composites that always pass the supplied primality tests. We explore the implications of these security failures in applications, focusing on the construction of malicious Diffie-Hellman parameters. We show that, unless careful primality testing is performed, an adversary can supply parameters $(p,q,g)$ which on the surface look secure, but where the discrete logarithm problem in the subgroup of order $q$ generated by $g$ is easy. We close by making recommendations for users and developers. In particular, we promote the Baillie-PSW primality test which is both efficient and conjectured to be robust even in the adversarial setting for numbers up to a few thousand bits.

Category / Keywords: public-key cryptography / Primality testing, Miller-Rabin test, Lucas test, Baillie-PSW test, Diffie-Hellman, TLS

Original Publication (with major differences): CCS 2018

Date: received 14 Aug 2018, last revised 30 Oct 2018

Contact author: kenny paterson at rhul ac uk

Available format(s): PDF | BibTeX Citation

Note: Updated to include details on vulnerabilities in Apple crypto libraries.

Version: 20181030:191742 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]