Why cryptography is much harder than software engineers think

The recent ROCA vulnerability (CVE-2017-15361) raises some important issues about the design of secure cryptographic software. The vulnerability is not in this case an obvious coding error such as a buffer overflow, or the use of a poor quality random number generator.

In this case, it arose from what probably seemed like a reasonable software engineering decision. To understand this in detail requires some pretty complex mathematics. For that, I refer you to the paper that details the flaw along with the exploit, which you can download here.

In summary, the researchers studied the statistical properties of a large sample of public keys. These are not normally easy to obtain, but the Estonian government had set up a public directory, associated with their national ID card. Since, by definition, these are public keys that’s a perfectly reasonable thing to do. Recall that there is a corresponding private key which is of course not disclosed. In theory, it’s almost impossible to derive the private key from the public key unless enormous amounts of computer time are expended.

Researchers analyzed the statistical properties of these public keys. They found that the keys were not truly random, as they should be. This meant that it was possible to derive the private key from the public key in days, rather than the expected thousands of years.

Prime suspects

How did these weak keys come to be generated? The issue lies with the RSA algorithm which lies at the heart of public key cryptography. Recall that the public and private keys are generated from very large prime numbers. Five is a prime number (it can be divided only by itself and 1). Six is not (it can be divided by 1,2,3 and 6).

The RSA algorithm best practice implementation requires that these primes (which can contain thousands of digits) have certain additional properties, which means that not just ANY large prime number will do.

The tests required to establish the suitability of the primes can be computationally expensive. Consequently some shortcuts can be taken to speed the process up. In the case of the Infineon library associated with the vulnerability, these ‘optimized’ tests favored the selection of certain prime numbers, whose digits contained patterns that the researchers could pick up through their statistical analysis.

Therefore the primes chosen to create the public/private key pairs were chosen from a much smaller set of primes where the efficient test could quickly determine that they were suitable. They were still huge primes, of course, but not truly random primes.

The major key

The researchers could exploit this lack of true randomness. Because they had inferred the patterns within the primes, they could use this knowledge, along with attack known as ‘Coppersmith’s algorithm’ to efficiently derive the private key from the public key.

Infineon are highly unlikely to be alone in exploiting this technique for efficiency. The researchers examined some other publicly available databases of public keys. This is what the researchers said about keys generated by Trusted Platform Modules (TPMs). A TPM is a hardware device used to generate and manage keys securely.

We analyzed a sample of 41 different laptop models equipped with TPM chips…. All chips [from]… 2013 or later were vulnerable, including both TPM 1.2 and TPM 2.0.

TPM devices have very limited computational resources. Consequently, the code they use to generate and test random primes must be heavily optimized. This matters because the keys generated by TPMs are often used to support full disk encryption systems such as Microsoft’s BitLocker. If the keys are weak, an attacker can potentially recover the encrypted data.

The researchers point out that obtaining large-scale databases of public keys is not easy. Consequently there could be a lot of weak keys out there that have not yet been identified. Recall that Infineon used a particular ‘shortcut’ to optimize the tests for candidate primes. Other vendors may have used different shortcuts that expose their generated keys to a similar weakness.

Without a database of public keys all generated by the same algorithm, it’s hard to tell whether a specific key is weak. The researchers have a test for Infineon-generated keys, but for other vendors, presumably with different algorithmic shortcuts, the test would differ. This may therefore be a more widespread problem.

Most software engineers are not well-versed on cryptographic design, which requires strengths in both math and statistics. In writing the code that introduced the flaw, the engineers probably took some existing implementation and adapted it, based on reasonable considerations of efficiency – they were constrained for resource and made what seemed like a sound decision. Unfortunately, in doing so they introduced a subtle but critical flaw.

The challenge of implementation

It would have been possible to detect this through automated tests against a large set of generated keys. There are established algorithms for testing how truly random a set of supposedly random numbers actually is. Keys produced by this flawed algorithm should have failed this test.

But this vulnerability highlights how hard cryptography is to implement securely. There is no simple test to say that an implementation is intrinsically secure. Instead, security must be implemented by design. Open source implementations such as OpenSSL have the huge advantage that the code base can be publicly audited by security professionals. Indeed, as far as we know, keys generated by OpenSSL are cryptographically secure. However, closed platform implementations such as the Infineon TPM code are not auditable.

Note that the researchers did NOT reverse-engineer the Infineon devices. They merely examined the generated public keys for statistical anomalies and from these were able to infer the cryptographic weakness. Had the code been in the public domain this weakness may well have been discovered through code auditing. So – if your security depends on vendor-supplied ‘black boxes’ – be very careful. As this incident shows, security through obscurity is no security at all.