All your certs are belong to us
Keyfactor analyzed half a million online certificates and found that about 18% had some sort of identifiable flaws.Some of these issues are just bothersome and indicate that the certificate issuer was careless. But that sloppiness may attract attackers, as these certificates are more likely to have other problems.Overly long lifespans. Certificates should be valid for a year or less to reduce their risk of eventual compromise. But Keyfactor’s research indicated that 1 in 13, or 7.7%, had lifespans longer than two years. A few certificates were set to “live” until 11:59:59 p.m. on Dec. 31, 9999, the latest possible expiration date. There’s no reason for that other than negligence.”The important thing is it should not be happening,” Hickman told us. “[That certificate] should not be a part of a corporate data set or a product company data set, and people have to be aware of it.”Overly large file sizes. Some certificates can be very long strings of text. But if they get to be more than 100 kilobytes, they’ll overflow the space allocated for the certificate number in certain cryptographic protocols, among them the widely used OpenSSL.Negative serial numbers. Another clear example of negligence. Keyfactor researchers found that about one in 27, or 3.7%, of certificates had these.”If you’re not paying attention, and you just put a random bit string in, you’ve got about a 50-50 chance that that arbitrary bit string is going to be a negative number,” explained Keyfactor PKI and Internet Systems Engineer JD Kilgallin.Chain validation failure: These defective certificates can’t be used due to incomplete or improper information — there’s no certificate issuer documented, or the time format is invalid. This is not severe because these bad certificates “fail closed” and simply don’t work.Other certificate flaws are more serious and could lend themselves to exploitation or even public-key-infrastructure (PKI) compromise:No specified key usage. Unless the certificate issuer specifies what the certificate is to be used for, then it can be repurposed by a bad actor and used for, well, anything. About one in 25 certificates, or 4%, had this issue.In such cases, you could borrow a certificate meant for a server and use it instead to sign software. This may also be how some malware ends up signed and able to get past Microsoft and Apple’s protections.”You can technically use that key to sign code, and it would look perfectly legitimate inside your organization,” said Hickman. “That would be a gross misuse of that key, but it would be an allowable use by virtue of not having the key usage in there.”Lack of basic constraints. The certificate wasn’t issued with an extension that enables validity only if the type of certificate is specified and all the parties on the cryptographic “chain of trust” conform to specifications set by the issuing certificate authority.Without this, the certificate is at greater risk of being misused or exploited. One in 32, or 3.1%, of certificated examined by Keyfactor had this issue.
Factor, factor, gimme the news
Then there’s an issue that once was a low-level mathematical risk, but which has been made more dangerous by the prevalence of Internet of Things gadgets and other devices with limited processing power.The RSA encryption algorithm that creates the security of internet connections and digital certificates uses mathematical calculations based on very large numbers that are themselves the products of two very large prime numbers. The prime numbers are kept secret; their products are public and visible in digital certificates.To create all these numbers, a device — it can be a computer, a smartphone, a server, or your “smart” toaster — randomly generates two very large random primes and then multiplies them to create a third number. It sends the third number to an authority that responds with a digital certificate containing the number and verifying the device’s identity.So far, so good. All the numbers involved are so large that, at least today, it would take a standard computer thousands of years to factor the multiplied number into its constituent prime numbers.To use an easier example, let’s take the random four-digit primes 5,107 and 4,363 and multiply them to get a product of 22,281,841. If you had 22,281,841 only by itself, it would take you a very long time to try to factor it into its common divisors, because it has only two and they’re not obvious.A computer could calculate this quickly by sheer brute force. But if you use primes that are thousands of digits long, and then you multiply those to create much longer third numbers, you’re beyond the range of what a regular computer can handle. (Quantum computers, which will likely exist soon, should be able to factor these numbers, but that’s another issue.)It’s the near-impossibility of factoring those very large “semiprime” numbers into their prime divisors that makes RSA encryption secure.
It’s Greek to me
But there’s a catch. Using a method devised more than 2,000 years ago by the ancient Greek mathematician Euclid, it’s possible to find the largest common denominator — or greatest common divisor — of two numbers simply by repeated subtraction.For example, let’s take 72 and 51. Subtract 51 from 72 and you get 21. Now subtract the smaller of the two numbers you have left, 21, from the larger one, 54, and you get 33.Then subtract 21 from 33 and you get 12. Twenty-one minus 12 is nine; 12 minus nine is three; nine minus three is six; and six minus three is three.When you can’t go any further, then you’ve found the greatest common denominator of 72 and 51: three.Using powerful computers and some mathematical shortcuts, you can try to do this with very large subprime numbers, such as those used in RSA cryptography.In most cases, you should almost never be able to find any common divisors among RSA keys because each one should be the product of two randomly generated, very large, prime numbers.Yet people have tried, and they’ve found more common divisors than should be statistically possible. In a perfect world, the number of shared prime factors among RSA-based digital certificates should be very small, about 1 in 20 million or 0.000005%.At least four separate research studies over the past dozen years have found incidents of shared prime factors among RSA keys ranging from about 0.20% to 0.58%. That may seem small, but the latter percentage, found by Kilgallin and fellow researcher Ross Vasko in 2019, means that about 1 in 172 RSA certificates analyzed shared a factor with another RSA certificate.So why is this bad? Because if you know the original two numbers being factored, which are always public, and then you discover that they share a secret common divisor, then it’s trivial to find the OTHER secret common divisor for each of the original numbers. Then you’ve broken the encryption of at least two RSA keys, and you didn’t even need a quantum computer.”If two RSA keys share one factor, then both factors are vulnerable,” explained Kilgallin during a presentation devoted to his research at the Tech Days conference. “This is why prime numbers must be generated randomly.”Put mathematically, you have public key numbers A and B, and you find, using Euclid’s algorithm, that they share a common divisor C. Now you want to find the secret numbers X and Y that are the other factors of A and B.X will be equal to A/C. Y will be equal to B/C. And while most digital certificates are still safe, there are millions of digital certificates out there that can be cracked this way.Kilgallin explained that this isn’t a flaw in the RSA encryption algorithm itself. Instead, it’s because the large primes being used are not as random as they should be, especially when they’re generated by devices that don’t have the processing power to create very large numbers.So you get more duplicate factors than you should, and the number only increases as the number of devices and certificates increases. In four research papers that spanned a seven-year period from 2012 to 2019, the rate of shared factors among RSA-based digital certificates nearly tripled, from 0.20% to 0.58%. It’s probably higher now.These poor practices aren’t limited to no-name cheap IoT devices. In their 2019 research paper, Kilgallin and Vasko wrote that “almost exactly 50% of compromised certificates contain the name of a large network equipment manufacturer” that has remained unidentified.
Finding and categorizing all these problems
Armed with this knowledge, Keyfactor’s Command Risk Intelligence module for its Command platform scans an organization’s digital certificates for such weaknesses. If it finds weak or problematic certificates, it recommends revoking them and issuing new ones.In addition to looking for negative serial numbers, insane expiration dates, and no specified key usage, Command Risk Intelligence uses the set of known compromised certificates discovered by Kilgallin’s research (many of which have since been revoked) and matches the input against them.It then goes one step further. It tries to see if any of the discovered certificates use keys that have a known shared factor, in effect picking up where the 2019 research left off.”We realize that this won’t necessarily find every single pair, because we’re not checking each customer certificate against literally every certificate that we know about,” Kilgallin told us. “This is an area that we expect will improve in each release that will iteratively update our list of known broken factors that do appear in real certificates in the wild.”Kilgallin and Vasko’s 2019 key factoring process cost about $3,000 to rent a Microsoft Azure cloud virtual machine and took about a day. That’s well within the capability of international cybercrime rings, then and now, and is a rounding error in the budget of nation-state signals-intelligence agencies. It would be very unlikely if other groups had not carried out similar experiments and reached the same conclusions.”With all of the modern AI and machine learning, we also think that this risk is something that an attacker could more easily discover as well,” Kilgallin said. “In every dimension, we think we’re going to find that in some ways, the problem has gotten worse.”But, said Hickman, users of Keyfactor’s Command Risk Intelligence will be one step ahead of the problem, and several steps ahead of their competitors.”Just by virtue of the fact that the number of certificates on the internet has increased exponentially says there’s going to be more certificates,” Hickman told us. “We’ve got larger data sets for our next sampling, and it’s part of what we would like to continue to refine and improve in the product, because it is a unique position that nobody else is offering today.”
