- Hello Defcon, thank you for tuning into my talk,
being broadcast in Raleigh, North Carolina.
My name is Austin Allshouse.
I'm a research scientist at BitSight.
And as part of my job,
I do a lot of surveys and studies of security
best practices across the internet.
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.
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.
And that's because that is the mechanism by which we are
going to do it.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
And it's less likely to be some sort of composite value
representing multiple shared factors in the batch.
So I understand this may be very difficult to visualize just
from a verbal description.
So I'm going to walk you through an actual explicit example.
In this example,
we're using the same prime products as before,
which contain two products with
a shared factor of seven.
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.
After that product tree has been formed,
the remainder of each parent node is calculated with respect
to the square of its child node.
When the bottom of the tree is reached,
the greatest common divisor is calculated between the
resulting remainder and the modulates.
And if this value is not one,
it means it shares a factor with some other modulus
in the batch.
In the same example, the two shared factors of seven
are output just the same as using the
pairwise Euclidean implementation described earlier.
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.
So say you don't have a machine with a terabyte of memory.
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.
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.
While is less efficient in practice,
it could actually be faster because all the arithmetic is
being done on much smaller numbers.
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.
So to walk you through another explicit example,
here we have two batches of prime products.
The first batch is the same one as we had before that shares
a prime factor of seven.
The second batch has a shared factor of 23,
and then across the two batches,
there is a shared factor of 17.
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.
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.
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.
The sizes of the trees and the number of the batches can
really be tailored to the compute
and memory resources available.
Here's an example architecture that I used to factor
86 million RSA keys using just commodity hardware
and no specialized software.
The factorization code was all written in Go.
And all that really is,
is implementing this product tree and remainder tree logic
that was covered earlier.
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.
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.
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.
No specialized software NVIG data frameworks needed.
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.
Less than 50,000 of those keys were able to be compromised
due to sharing a prime factor.
This is a much lower number than I was expecting,
and also a much lower number that had been reported
in prior years.
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.
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.
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.
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.
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.
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.
And it's still connected to the internet and the owners and
operators just don't even realize that it's there online.
Out of the roughly 150 million total keys analyzed,
only a single vulnerable key
was signed by a trusted third party certificate authority.
Every single other vulnerable key was either self signed or
signed by an internal CA that's not publicly trusted.
This suggests that the likely culprit of many of these keys
are devices that are automatically generating certificates.
And this is somewhat reinforced by the absurdly long
validity durations present in the second chart on the right.
And this was done likely as a convenience by vendors.
And of course,
this is not in line with best practices for certificates.
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.
Finally,
I saved this chart for last because I think it is really the
most important chart of the whole presentation.
This chart represents the relationships between vulnerable
prime values where an edge exists between two primes
if they appeared in the same RSA modulus.
The coloring represents the product families
that the primes appeared in.
For example, one color is Huawei switches,
one is D-Link routers, et cetera, et cetera.
It becomes very obvious that the relationships between these
primes are mostly disjoint between different products.
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.
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.
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.
Much of the analysis on these keys in the past has
focused on keys collected from the public facing internet.
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.
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.
However this seems to be primarily the result
of really old devices
and not necessarily from new vulnerable products.
The culprits here seem to be primarily automatically
generated certificates from networking equipment.
So, you know, maybe don't trust those certificates.
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.
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.
This implementation is really just
for illustrative purposes.
It was written in Python
in order to be very simple, clear, and concise,
but as a result, it's also very, very slow.
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.
And I will close things with that.
Thank you for tuning in,
and I hope you enjoy the rest of Defcon 29.