The Impact of Flawed Pseudorandom Number Generators in Network Devices

Summary

To gauge the impact of flawed pseudorandom number generators in network devices, Bitsight scanned the public Internet for RSA public keys and was able to factor the public modulus and recover the private keys for 41,225 network devices. Bitsight has also found that the prevalence of such vulnerable devices on the Internet has been declining in recent years; however, many still pose a risk to organizations that lack security controls to prevent the inadvertent exposure of unmanaged network assets to the public Internet.

Background

A mathematical principle that underpins the RSA public-key cryptosystem is that no known efficient method exists for factoring large integers. It is trivial to multiply two large prime numbers together, but factoring the product into its constituent primes remains computationally infeasible when the product is large enough. Embedded into a public key infrastructure (PKI) scheme, this asymmetry is the basis from which the majority of web clients authenticate Internet services across the globe.

To enable a variety of secure communications protocols such as HTTPS and SSH, a server requires a public and private key pair which can be used to authenticate the server to clients. The first step when generating such a key with RSA, is to randomly choose two prime numbers p and q. These primes must be kept secret for the security of the private key, but their product p * q = n, is shared as the modulus of the public key. The infeasibility of factoring the public modulus (n) back into the random primes selected by the server (p,q) is foundational to the security of RSA.

While integer factorization is computationally hard, efficient methods do exist for calculating the Greatest Common Divisor (GCD) for two large integers. When generating an RSA key, if two devices select the same value for p or q, it is trivial to recover the other prime values by calculating the GCD of the two public moduli. Given the very large space from which random prime values of p and q are selected, the odds of two separate key generations choosing the same prime values of p or q is extremely small; but as prior research has found; in practice, this can occur when flaws exists in the processes by which devices derive “random” prime numbers. These flaws create a proliferation of RSA public keys from which their associated private keys can be recovered, nullifying any security benefit they provide.

To assess the current and historical impact of this class of vulnerability, Bitsight scanned the public Internet for RSA public keys and computed the GCD across all collected keys based on a distributed batch implementation described in Hastings et al.

Declining Impact

Over a three month period, RSA keys were extracted from TLS certificates and SSH banners. In total, roughly 86 million unique RSA moduli were extracted from 157 million endpoints. Only 13,652 public key moduli were found to share a factor with another modulus in the collection, and these moduli were present across 41,225 different endpoints. This 13.7k vulnerable moduli number is substantially lower than prior studies have reported on factorable RSA keys

To validate this observed decrease, separate random samples of 10 million RSA keys were selected from each year since 2015, and a dramatic decrease in the fraction of RSA keys sharing a prime factor within each sample was observed each subsequent year, dropping from over 20,000 in 2015 to just over 1,200 in 2021.

The majority of devices with factorable keys online today are devices that have been reported as vulnerable in prior studies; suggesting that many vendors have largely addressed flaws in device entropy pools, yet legacy, unmanaged network devices remain a risk to organizations.

Industries most likely to be hosting vulnerable RSA keys were those that tend to have poor cyber security performance on average. Organizations in the traditionally poor performing industry sector of Utilities were 10 times as likely to host a service with a factorable RSA key than organizations in traditionally high performing sectors such as Finance and Insurance.

Vulnerable Devices

The vast majority of devices serving vulnerable TLS certificates represent networking devices and various forms of embedded devices which is likely explained by the potentially limited available entropy pools in such devices. Prime factors were generally not shared across different products, suggesting that the random number generator failures causing the vulnerabilities are unique to the various device implementations.

The exception to this was a single embedded web server framework incorporated into multiple different appliances which occasionally shared prime factors across products.

The majority of factorable RSA keys were obtained from a small handful of network appliance vendors. The presence of a vendor or device on the following list does not imply that a current vulnerability exists in the product, only that Bitsight was able to recently recover the private key for a certificate served by an instance of the device on the Internet because it shared a prime factor with another device.

Device Lifecycle

Analysis of the “not valid before” dates on vulnerable TLS certificates provides some insight into the time period over which the certificates are being generated, as generally a device should not generate a certificate that is not valid at the time of generation.

Less than 4% of vulnerable endpoints presented a certificate that was not valid before January 2020, suggesting that recently generated vulnerable certificates are likely to be rare. This value underrepresents the true population of currently vulnerable devices because vendors often generate certificates with arbitrarily long or nonsensical validity timeframes. The distribution of “not valid before” dates from vulnerable devices, when compared to a random sample of Internet certificates, suggests that these vulnerable certificates are generally old and likely associated with endpoints that are not patched or maintained.

The distribution of the expiry dates for the vulnerable certificates further reinforces this hypothesis as many vulnerable certificates have already expired. It also shows that these devices generally have a much broader duration of certificate validity than most Internet certificates. This is likely the result of device vendors desiring minimal support and maintenance requirements for automatically generated device certificates. Recently the CA/Browser Forum moved to allow a maximum duration of 13 months for public CA signed certificates to be in line with security best practices.

Addressing Risks

This survey reveals several risks that organizations should consider when deploying network assets with PKI. In particular, organizations should ensure that they:

Do not rely on default or automatically generated certificates for Internet-facing systems

Vendors will often pre-package or automatically generate certificates on devices for ease of integration; however, the processes by which these certificates are generated may not be robust from a security perspective. This survey has shown that automatically generated, vulnerable certificates often have long lifetimes which is also against generally accepted best practices for TLS. When exposing a TLS service to the Internet, ensure the service has a certificate signed by a publicly trusted third-party Certificate Authority (CA). CAs enforce certificate best practices in their signing policies and it will ensure that the built-in trust anchors in modern browsers can authenticate the service.

Maintain visibility into the attack surface of your network and ensure that unmanaged devices are not exposed to the Internet

The distribution of certificate validity dates suggests that the vast majority of devices with factorable RSA certificates have been on the Internet for an extremely long period. With long expired certificates, it is likely that most of these devices do not serve a functional purpose and are exposed to the Internet unintentionally. The presence of unmanaged devices on a network can pose a significant risk for organizations in that they will likely elude patching and auditing processes. Where possible, maintain an up-to-date inventory of network assets and audit the attack surface of your network to ensure it is aligned with your inventory.