Primality Testing Under Adversarial Conditions


Cryptology ePrint Archive: Report 2018/749

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 16 Aug 2018
Contact author: Jake Massimo 2015 at rhul ac uk
Available format(s): PDF | BibTeX Citation

Version: 20180817:113746 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]

Read More

This site uses Akismet to reduce spam. Learn how your comment data is processed.