PKI Crumbles A Bit More

PKI Crumbles A Bit More

The RSA public key encryption method uses two prime numbers: p and q, and then calculates a modulus (N=p*q). If we can find one of the random prime numbers, we can easily find the other one, and then can determine the private key from the public key value. We thus need to make sure we have a completely random prime number, and one which is not easily guessable. But Keyfactor scanned over 75 million RSA certificates certficates on the Internet and found that 1 in 172 digital certificates share a common factor [here].

The work is not new in its methodology and uses a GCD (Greatest Common Denominator) method in order to determine if a modulus (N) shares a factor with others. With GCD, we take two numbers, such as 15 and 21, and then determine if they share a common factor. In this case the largest common factor is 3. With an RSA modulus we should always get a GCD of 1 for two modulus’ that we try, and especially where we have completely random prime numbers. Here is an outline of how RSA is cracked if we can factor the modulus:

The Keyfactor work follows the work of Lensta et al [1] and Heninger et al [2]:

Lenstra found that 4.3% of 6.3 million digital certificates had a shared RSA modulus. In fact a single factor was shared by thousands of modulus’. Heninger [2] then analysed 5.8 million TLS certificates and 6.2 million SSH key, and found that they could factor over 16,000 public keys:

The Keyfactor study focused on IoT related infrastructures and found around 1 in 172 weak certificates (435,000 were discovered to share a factor). Overall the likely source of the weaknesses is related to the poor entropy used in the generation of the random prime numbers, and that this may be more likely in IoT devices, and which can struggle to find good sources of randomness.

From 2015 to 2017, Keyfactor used their “Internet Certificate Inventory” (ICI) to scan the public IPv4 address space, and found around 45 million unique modulus values, of which they managed to crack 192,709 of them, and which related to 344,055 digital certificates (0.56%). For 2019, they scanned over 13 million ICI sites, and 100 million CT Logs, and found another 56,844 keys.

Several Prime number factors came up quite often, and with one having a count value of 8,197:

A surprising thing here is that eight of these common factors relate to 1024-bit keys (and which are seen to be fairly secure in the generation of keys). The greatest vulnerabilities were found within 512-bit and 1,024 bit keys:

We can see that the prime numbers which make up 512-, 1,024- and 2048-bit keys are around 256, 512 and 1,024 bits long, representively. This is because two n-bit numbers when multiplied give an 2n bit length.

Other findings include the discovery of hacked certificates (66,939 for a single vendor), and that 12 in 20 of the most common subjects of the certificate relate to IoT devices. A particular problem is that there were many examples of “copying and pasting” certificate details as many contained the details of:

• “CN=192.168.1.1” (25,075 certificates)
• “[email protected], CN=NOHOSTNAME.NODOMAINNAME, O=ANY COMPANY, L=ANY LOCALITY, ST=ANY STATE, C=US” (242 certificates).

Conclusions

This study shows that we still have significant problems in PKI for non-random RSA keys, and that IoT devices seem to be particularly at risk. As these devices can be difficult to update and patch, we could be opening ourselves to a whole host of major data breaches on the Internet.

References

[1] A. K. Lenstra, J. P. Hughes, M. Augier, J. W. Bos, T. Kleinjung,
and C. Wachter, “Ron was wrong, Whit is right,” 32nd International
Cryptology Conference, CRYPTO ’12, August 2012.

[2] N. Heninger, Z. Durumeric, E. Wustrow, and J. A. Halderman,
“Mining your Ps and Qs: detection of widespread weak keys
in network device,” Proceedings of the 21st USENIX Security
Symposium, August 2012.