An Analysis of Primality Testing and Its Use in Cryptographic Applications

Due to their fundamental utility within cryptography, prime numbers must be easy to both recognise and generate. For this, we depend upon primality testing. Both used as a tool to validate prime parameters, or as part of the algorithm used to generate random prime numbers, primality tests are found near universally within a cryptographer's tool-kit. In this thesis, we study in depth primality tests and their use in cryptographic applications.

We first provide a systematic analysis of the implementation landscape of primality testing within cryptographic libraries and mathematical software. We then demonstrate how these tests perform under adversarial conditions, where the numbers being tested are not generated randomly, but instead by a possibly malicious party. We show that many of the libraries studied provide primality tests that are not prepared for testing on adversarial input, and therefore can declare composite numbers as being prime with a high probability. We also demonstrate that for a number of libraries, including Apple's CommonCrypto, we are able to construct composites that always pass the supplied primality tests.

We then explore the implications of these security failures in applications, focusing on the construction of malicious Diffie-Hellman parameters. These malicious parameter sets target the public key parameter validation functions found in these same cryptographic libraries – particularly within the ones that offer TLS implementations. Using the analysis performed on these library's primality tests, we are able to construct malicious parameter sets for both finite-field and elliptic curve Diffie-Hellman that pass validation testing with some probability, but are designed such that the Discrete Logarithm Problem (DLP) is relatively easy to solve. We give an application of these malicious parameter sets to OpenSSL and password authenticated key exchange (PAKE) protocols.

Finally, we address the shortcomings uncovered in primality testing under adversarial conditions by the introduction of a performant primality test that provides strong security guarantees across all use cases, while providing the simplest possible API. We examine different options for the core of our test, describing four different candidate primality tests and analysing them theoretically and experimentally. We then evaluate the performance of the chosen test in the use case of prime generation and discuss how our proposed test was fully adopted by the developers of OpenSSL through a new API and primality test scheduled for release in OpenSSL 3.0 (2020).