DEF CON 29 - Austin Allshouse - The Mechanics of Compromising Low Entropy RSA Keys

00:06 - My name is Austin Allshouse. I’m a research scientist at BitSight.

00:11 - And as part of my job, I do a lot of surveys and studies of security best practices across the internet.

00:17 - And today I’m going to walk you through some of the low level details of how to do one study that I did recently involving compromising RSA keys through factorization.

00:31 - While this talk is nominally about how to compromise a specific subset of vulnerable RSA keys, what it’s really functionally about is a scalable method to calculate shared factors across large batches of integers.

00:45 - And that’s because that is the mechanism by which we are going to do it.

00:50 - There has been a lot of past research on this topic, and many of the researchers have sort of simply attested that they built a custom scalable, distributed batch GCD implementation to factor keys collected from the internet, but many of these studies have been fairly light on implementation details.

01:08 - So this talk is going to walk you through what distributed batch GCD means and how to implement it yourself in order to break some RSA keys.

01:19 - I’m not going to give a whole RSA recap, but there is one thing that you need to know in order to understand the content of this talk.

01:28 - The first step when producing an RSA key pair is to select two random prime numbers and the product of those two prime numbers is shared as the modulus of the public key.

01:40 - The security of RSA is dependent upon the fact that given a sufficiently large key size, it is not tractable to factor that public modulus back into those constituent primes and the secrecy of those primes is critical to the security of the private key, but while large integer factorization is a computationally difficult problem, fast and efficient methods do exist for calculating the greatest common divisor of two integers.

02:14 - This means that if any two RSA keys just happened to choose one of the same primes when generating keys, both of those keys can be easily compromised by calculating the greatest common divisor of the two keys.

02:30 - In theory, this should never happen as the number of potential primes to choose from is so mindbogglingly large, that it would never actually happen by chance.

02:41 - However back almost a decade ago, two research teams actually found out that many RSA certificates collected from the internet do in fact share primes with other certificates, this making them trivial to compromise, and they were able to attribute this phenomenon to flawed implementations in pseudo random number generators seeding the key generation process.

03:08 - Over the years, this phenomenon has been revisited with researchers collecting and evaluating larger and larger batches of keys, necessitating various big data approaches to this problem.

03:21 - This culminated somewhat in a really interesting talk back at Defcon 26, in which some folks from Kudelski Security really industrialized the key acquisition process and evaluated hundreds of millions of keys for a variety of weak implementations, but including this shared prime factor vulnerability that I’m discussing today.

03:43 - So the question really sort of boils down to if some RSA keys do share primes and they can be compromised by finding share factors across them, how do you calculate the greatest common divisor across hundreds of millions of keys? To answer that question, we need to go back over 2000 years to what is one of the oldest known algorithms, the Euclidean algorithm, which is used to calculate the greatest common divisor of two numbers.

04:15 - It works by recursively calculating remainders between two numbers until the greatest common divisor of those two numbers is reached, which it may just be one if the two numbers don’t actually share any common factors.

04:29 - In this trivially small example on this slide comprised of four products of prime numbers, by calculating the pairwise greatest common divisor of each combination of numbers, we can discover that one pair does in fact share a common factor of seven, because it has a greatest common divisor of greater than one.

04:49 - While this slide is using small integers, just for illustrative purposes, these integers could just as easily be real RSA moduli, and this is a perfectly valid way to compromise keys if there does happen to be a shared prime factor with any small batch of keys.

05:06 - The Euclidean algorithm is fast and efficient, but because you have to do these pairwise combinations attempting to calculate the greatest common divisor across hundreds of millions of keys could potentially require hundreds of quadrillions of iterations of this algorithm, which means that it’s really just not scalable to that problem.

05:28 - So skipping ahead over 2000 years again, a cryptographer named Bernstein published an efficient method for calculating the greatest common divisor across batches of numbers, like many problems in computer science, it uses an intermediate tree data structure to bypass the requirement of having to calculate every pairwise combination of numbers.

05:52 - In simplest terms, Bernstein’s method builds a product tree by calculating the products of pairs of numbers in the batch, and then repeating this process up successive levels of the tree until the root of the tree represents the cumulative product of all numbers in the batch.

06:12 - It then decomposes this product tree back into remainders by calculating the remainder of each parent node with respect to the square of its child node until the leaves of the trees represent the remainders of each integer in the batch with respect to the cumulative product of the whole batch.

06:34 - A final greatest common divisor step is computed on each leaf remainder, which will reveal if that particular manager shares a factor with any other integer in the batch.

06:47 - This is a very similar approach to the Euclidean algorithm with the key distinction being that these shared factors are being discovered with respect to the cumulative product of the whole batch instead of the various pairwise combinations of all integers in the batch.

07:04 - This is a very effective approach specifically for the RSA key factorization problem, because in general, shared factors are relatively rare and therefore it’s very likely that any factor output by this method will be one of the actual primes used in key generation.

07:21 - And it’s less likely to be some sort of composite value representing multiple shared factors in the batch.

07:29 - So I understand this may be very difficult to visualize just from a verbal description.

07:34 - So I’m going to walk you through an actual explicit example.

07:39 - In this example, we’re using the same prime products as before, which contain two products with a shared factor of seven.

07:48 - Building the product tree is merely a process of pairing off the integers and calculating their products at each level, until we get the cumulative product of the batch, represented in green.

08:04 - After that product tree has been formed, the remainder of each parent node is calculated with respect to the square of its child node.

08:13 - When the bottom of the tree is reached, the greatest common divisor is calculated between the resulting remainder and the modulates.

08:21 - And if this value is not one, it means it shares a factor with some other modulus in the batch.

08:28 - In the same example, the two shared factors of seven are output just the same as using the pairwise Euclidean implementation described earlier.

08:39 - While this implementation is very fast, it does raise a new challenge in that these product trees can potentially get very, very large, such a tree of 150 million, 2048 bit RSA moduli would be over a terabyte in size, which can be very difficult to manage, especially on a single machine.

09:02 - So say you don’t have a machine with a terabyte of memory.

09:06 - There’s actually a pretty straightforward way to make this calculation much more manageable, instead of making the one that very large product tree, you can make a few smaller ones, breaking that 150 million batch into five smaller batches will produce product trees that are roughly 180 gigabytes in size, which can be quite a bit more manageable and potentially processable on just a single machine.

09:32 - There is a major downside to breaking the tree up into smaller batches, however, and that is in order to get coverage of the shared factors across these different batches, the remainder trees must be calculated with respect to each other tree, which requires this permutation step of all the trees.

09:52 - While is less efficient in practice, it could actually be faster because all the arithmetic is being done on much smaller numbers.

10:00 - And there’s no bottleneck where we’re trying to calculate arithmetic on really huge integers at the root of a massive monolithic product tree.

10:13 - So to walk you through another explicit example, here we have two batches of prime products.

10:19 - The first batch is the same one as we had before that shares a prime factor of seven.

10:25 - The second batch has a shared factor of 23, and then across the two batches, there is a shared factor of 17.

10:35 - When calculating the remainders for each tree against the cumulative product of both trees, all of these shared factors end up falling out at the bottom.

10:46 - And the permutation of these trees is really important because otherwise that 17 factor, which is shared across both batches would not have been discovered if we were only evaluating the trees within each batch.

11:01 - By calculating the product trees and then permuting the remainder trees in this way, the calculation of shared factors across a huge number of integers can be broken down into batches and pair-analyzed across any number of machines without any necessary outrageous memory requirements.

11:19 - The sizes of the trees and the number of the batches can really be tailored to the compute and memory resources available.

11:31 - Here’s an example architecture that I used to factor 86 million RSA keys using just commodity hardware and no specialized software.

11:41 - The factorization code was all written in Go.

11:43 - And all that really is, is implementing this product tree and remainder tree logic that was covered earlier.

11:51 - The arithmetic was calculated using the native C-GNU multi-position library since allegedly it is quite a bit more performant than its Go counterpart.

12:00 - RSA moduli were read from S3 and the product tree levels were restored to EBS, and they were just serialized using Go’s native built-in Gob library.

12:12 - Concurrency and calculating the various values at each tree level was done just using Go routines and orchestration of all the tree permutations was just a simple shell script.

12:23 - No specialized software NVIG data frameworks needed.

12:29 - So I used that architecture to factor about 86 million keys from certificates collected from the internet over about a three month period and found some interesting results.

12:41 - Less than 50,000 of those keys were able to be compromised due to sharing a prime factor.

12:50 - This is a much lower number than I was expecting, and also a much lower number that had been reported in prior years.

12:57 - As a sanity check, I went back and collected samples of keys dating back six years and discovered that sure enough, the prevalence of this type of vulnerable key has decreased dramatically over the years.

13:11 - The chart in the slide represents the number of keys that can be factored from a random sample of a hundred million keys collected in a given year based on sharing a prime factor with some other key in that same 10 million key sample.

13:28 - I think the dramatic decline observed here is really a testament to the impact of prior research, as it appears to have made vendors address this problem as it is far less prevalent today than it was just a couple of years earlier.

13:45 - Out of the keys that were still vulnerable, almost exclusively appeared in networking devices and embedded systems, but I think the question still remains, if this issue has largely been remediated, and if it is trending downward pretty dramatically, why are there still so many vulnerable keys on the internet? Well reviewing the certificate validity lifetimes of the vulnerable keys provides some insight into that.

14:14 - The charts here show a histogram of validity dates of vulnerable certificates compared to a random sample of certificates from the internet, the long tail of the not valid before dates hint that perhaps the certificates are just really old devices and the not valid after dates on the right show that over 10% had expired over a decade ago.

14:39 - And that helps really reinforce this fact. Many of the vulnerable certificates likely just represent really old networking equipment that is probably lost in a closet somewhere.

14:51 - And it’s still connected to the internet and the owners and operators just don’t even realize that it’s there online.

14:58 - Out of the roughly 150 million total keys analyzed, only a single vulnerable key was signed by a trusted third party certificate authority.

15:08 - Every single other vulnerable key was either self signed or signed by an internal CA that’s not publicly trusted.

15:17 - This suggests that the likely culprit of many of these keys are devices that are automatically generating certificates.

15:24 - And this is somewhat reinforced by the absurdly long validity durations present in the second chart on the right.

15:32 - And this was done likely as a convenience by vendors.

15:35 - And of course, this is not in line with best practices for certificates.

15:42 - When reviewing the organizations that were actually hosting these vulnerable devices, the trends are generally what you would expect, organizations and industries that typically have very mature security programs that invest a lot in security industry, such as financial services, were the least likely to be hosting vulnerable devices and industries that are more notorious for perhaps lax practices, such as utilities were more than 10 times as likely to be hosting a vulnerable device than their low risk industry counterparts such as financial services, insurance and legal.

16:24 - Finally, I saved this chart for last because I think it is really the most important chart of the whole presentation.

16:31 - This chart represents the relationships between vulnerable prime values where an edge exists between two primes if they appeared in the same RSA modulus.

16:43 - The coloring represents the product families that the primes appeared in.

16:48 - For example, one color is Huawei switches, one is D-Link routers, et cetera, et cetera.

16:55 - It becomes very obvious that the relationships between these primes are mostly disjoint between different products.

17:03 - This is really important because if they are disjoint, attempting to find shared factors across product families is somewhat of a fruitless exercise as the vendor specific random number generation flaws appear to only create prime collisions within their given product family.

17:22 - The implication of this is that you don’t necessarily need a big data approach of collecting some huge corpus of keys to compromise keys via this method.

17:33 - Small collections, the keys specific to a given networking device or embedded systems product is likely to be vulnerable as a massive collection of random keys that have been harvested from the internet.

17:48 - Much of the analysis on these keys in the past has focused on keys collected from the public facing internet.

17:54 - But I think this chart really shows that there may be opportunities to find additional vulnerable products in devices that are not typically exposed directly from the internet for anyone who is able to make product targeted key collections behind an external firewall at a large organization, or perhaps across many smaller organizations.

18:19 - So to wrap things up, almost a decade after the discovery of this phenomenon of the prevalence of shared primes in certificates on the internet, there’s still a fairly large number of devices that are factorable due to these shared primes.

18:35 - However this seems to be primarily the result of really old devices and not necessarily from new vulnerable products.

18:45 - The culprits here seem to be primarily automatically generated certificates from networking equipment.

18:51 - So, you know, maybe don’t trust those certificates.

18:55 - And finally, you don’t really need specialized software or a massive corpus of keys in order to compromise keys in this way, if you can get small targeted collections of keys from specific networking equipment or embedded systems products, that can potentially yield results.

19:14 - And to end things up, I published a reference implementation of the distributable batch GCD method described in this talk at the link on this slide, it’ll demonstrate the successful factorization of a small batch of actual RSA moduli.

19:32 - This implementation is really just for illustrative purposes.

19:36 - It was written in Python in order to be very simple, clear, and concise, but as a result, it’s also very, very slow.

19:43 - It will not scale. If you want to do this on larger batches of moduli, I highly recommend that you translate the code into your favorite compiled language of choice.

19:54 - And I will close things with that. Thank you for tuning in, and I hope you enjoy the rest of Defcon 29. .