Paper 2018/749

Prime and Prejudice: Primality Testing Under Adversarial Conditions

Martin R. Albrecht, Jake Massimo, 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.

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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. CCS 2018
DOI
10.1145/3243734.3243787
Keywords
Primality testingMiller-Rabin testLucas testBaillie-PSW testDiffie-HellmanTLS
Contact author(s)
kenny paterson @ rhul ac uk
History
2018-10-30: last of 2 revisions
2018-08-17: received
See all versions
Short URL
https://ia.cr/2018/749
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/749,
      author = {Martin R.  Albrecht and Jake Massimo and Kenneth G.  Paterson and Juraj Somorovsky},
      title = {Prime and Prejudice: Primality Testing Under Adversarial Conditions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/749},
      year = {2018},
      doi = {10.1145/3243734.3243787},
      note = {\url{https://eprint.iacr.org/2018/749}},
      url = {https://eprint.iacr.org/2018/749}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.