In a first, cryptographic keys protecting SSH connections stolen in new attack

For the first time, researchers have demonstrated that a large portion of cryptographic keys used to protect data in computer-to-server SSH traffic are vulnerable to complete compromise when naturally occurring computational errors occur while the connection is being established.

Underscoring the importance of their discovery, the researchers used their findings to calculate the private portion of almost 200 unique SSH keys they observed in public Internet scans taken over the past seven years. The researchers suspect keys used in IPsec connections could suffer the same fate. SSH is the cryptographic protocol used in secure shell connections that allows computers to remotely access servers, usually in security-sensitive enterprise environments. IPsec is a protocol used by virtual private networks that route traffic through an encrypted tunnel.

The vulnerability occurs when there are errors during the signature generation that takes place when a client and server are establishing a connection. It affects only keys using the RSA cryptographic algorithm, which the researchers found in roughly a third of the SSH signatures they examined. That translates to roughly 1 billion signatures out of the 3.2 billion signatures examined. Of the roughly 1 billion RSA signatures, about one in a million exposed the private key of the host.

While the percentage is infinitesimally small, the finding is nonetheless surprising for several reasons—most notably because most SSH software in use has deployed a countermeasure for decades that checks for signature faults before sending a signature over the Internet. Another reason for the surprise is that until now, researchers believed that signature faults exposed only RSA keys used in the TLS—or Transport Layer Security—protocol encrypting Web and email connections. They believed SSH traffic was immune from such attacks because passive attackers—meaning adversaries simply observing traffic as it goes by—couldn’t see some of the necessary information when the errors happened.

The researchers noted that since the 2018 release of TLS version 1.3, the protocol has encrypted handshake messages occurring while a web or email session is being negotiated. That has acted as an additional countermeasure protecting key compromise in the event of a computational error. Keegan Ryan, a researcher at the University of California San Diego and one of the authors of the research, suggested it may be time for other protocols to include the same additional protection.

In an email, Ryan wrote:

Even though the SSH protocol has been around for almost 18 years and is extremely widely deployed, we’re still finding new ways to exploit errors in cryptographic protocols and identifying vulnerable implementations. In our data, about one in a million SSH signatures exposed the private key of the SSH host. While this is rare, the massive amount of traffic on the Internet implies that these RSA faults in SSH happen regularly. Even though the vast majority of SSH connections are not affected, it’s still important that these failures are defended against. It only takes one bad signature in an unprotected implementation to reveal the key.

 

It’s fortunate that the most popular SSH implementations include countermeasures to prevent RSA signature faults from leading to catastrophic key leakage, but implementations that did not were still common enough to appear in our data.

The new findings are laid out in a paper published earlier this month titled "Passive SSH Key Compromise via Lattices." It builds on a series of discoveries spanning more than two decades. In 1996 and 1997, researchers published findings that, taken together, concluded that when naturally occurring computational errors resulted in a single faulty RSA signature, an adversary could use it to compute the private portion of the underlying key pair.

The reason: By comparing the malformed signature with a valid signature, the adversary could perform a GCD—or greatest common denominator—mathematical operation that, in turn, derived one of the prime numbers underpinning the security of the key. This led to a series of attacks that relied on actively triggering glitches during session negotiation, capturing the resulting faulty signature and eventually compromising the key. Triggering the errors relied on techniques such as tampering with a computer’s power supply or shining a laser on a smart card.

Then, in 2015, a researcher showed for the first time that attacks on keys used during TLS sessions were possible even when an adversary didn’t have physical access to the computing device. Instead, the attacker could simply connect to the device and opportunistically wait for a signature error to occur on its own. Last year, researchers found that even with countermeasures added to most TLS implementations as long as two decades earlier, they were still able to passively observe faulty signatures that allowed them to compromise the RSA keys of a small population of VPNs, network devices, and websites, most notably Baidu.com, a top-10 Alexa property.

As noted earlier, researchers had no evidence that passive attacks exploiting signature errors were feasible when traffic was transmitted through non-TLS protocols such as SSH or IPsec. The reason is that the cryptographic hash of the signature from the latter protocols includes a shared secret generated by the Diffie-Hellman key exchange. The security provided by the exchange meant that passively observing the faulty signature didn’t expose enough key material to recover the private key using a GCD attack.

The attack described in the paper published this month clears the hurdle of missing key material exposed in faulty SSH signatures by harnessing an advanced cryptanalytic technique involving the same mathematics found in lattice-based cryptography. The technique was first described in 2009, but the paper demonstrated only that it was theoretically possible to recover a key using incomplete information in a faulty signature. This month’s paper implements the technique in a real-world attack that uses a naturally occurring corrupted SSH signature to recover the underlying RSA key that generated it.

The researchers wrote:

In this paper, we show that passive RSA key recovery from a single PKCS#1 v1.5-padded faulty signature is possible in the SSH and IPsec protocols using a lattice attack described by Coron et al. In this context, a passive adversary can quietly monitor legitimate connections without risking detection until they observe a faulty signature that exposes the private key. The attacker can then actively and undetectably impersonate the compromised host to intercept sensitive data. We cast the key recovery problem as a variant of the partial approximate common divisor problem, and we show that this problem is efficient to solve for the key sizes and hash functions used for SSH and IPsec. For parameter settings that are near the asymptotic limits of these algorithms, we show how to balance the lattice attack parameters with an optimal amount of brute forcing to produce feasible running times.

 

We then carry out Internet-wide scans for SSH and IPsec to measure the prevalence of vulnerable signatures in the wild. We find multiple vulnerable implementations that appear to be due to different classes of hardware flaws. We also carry out a retrospective analysis of historical SSH scan data collected over the course of seven years and find that these invalid signatures and vulnerable devices are surprisingly common over time. Our combined dataset of around 5.2 billion SSH records contained more than 590,000 invalid RSA signatures. We used our lattice attack to find that more than 4,900 revealed the factorization of the corresponding RSA public key, giving us the private keys to 189 unique RSA public keys. We also analyze passively collected SSH network data. In addition to the signature vulnerabilities we were searching for, our analysis gives us a window into the state of the SSH, IKEv1, and IKEv2 deployment landscape. We observed a number of vulnerable and non-conformant behaviors among IPsec hosts in particular.

The researchers traced the keys they compromised to devices that used custom, closed-source SSH implementations that didn’t implement the countermeasures found in OpenSSH and other widely used open source code libraries. The devices came from four manufacturers: Cisco, Zyxel, Hillstone Networks, and Mocana. Both Cisco and Zyxel responded to the researchers’ notification of the test results before the completion of the study. Hillstone responded afterward. The paper reports:

Our analysis of active scan data revealed five unique SSH version strings that produced signatures resulting in factored keys, detailed in Table 3. The most prevalent software version is the “Zyxel SSH server” with 4873 vulnerable signatures followed by “SSHD” with 87. “Mocana SSH 5.3.1” and “Cisco-1.25” both generated a single vulnerable signature. We examined the behavior of hosts using these version strings over time. In particular, once a private key is exposed by a faulty signature, how long does the host continue to use that key? We also want to classify the nature of the errors; that is whether the error is permanent (all future signatures are faulty) or transient (the host generates valid signatures after the fault).

Once attackers have possession of the secret key through passive observation of traffic, they can mount an active Mallory-in-the-middle attack against the SSH server, in which they use the key to impersonate the server and respond to incoming SSH traffic from clients. From there, the attackers can do things such as recover the client's login credentials. Similar post-exploit attacks are also possible against IPsec servers if faults expose their private keys.

The root cause of the faults is not well understood. Some researchers have linked it to flaws in cryptographic accelerators in one study from Zyxel and Hillstone, two of the manufacturers identified in this month’s study.

Paper co-author Ryan wrote:

We think there are multiple different underlying causes for the faults we observed in different vendor implementations, because of how some devices were able to recover by generating correct signatures after generating a faulty signature, but other devices did not.

 

These are challenging issues to debug as well. Without having the exact software version and physical devices that created the faulty signatures, there’s not many leads to investigate, and vendors are limited to ensuring proper mitigations against fault attacks are in place in the latest firmware versions.

 

So we don’t have information specific to what caused the faults we observed, but we can speculate about a number of different possible causes: software bugs resulting in incorrect math operations in rare conditions, software bugs resulting in memory corruption, failing NVRAM or other hard disk storage, or bit errors in DRAM or other memory.

 

Whether or not an attacker can induce such faults depends on the root cause. For example, Rowhammer is an example of an attack where the attacker may be able to remotely trigger bit flips in DRAM. For an implementation with a memory safety vulnerability, an attacker could hypothetically remotely trigger a heap overflow that corrupts key data stored in memory.

The important thing is that a single flip of a bit—in which a 0 residing in a memory chip register turns to 1 or vice versa—is all that’s required to trigger an error that exposes a secret RSA key. Consequently, it’s crucial that the countermeasures that detect and suppress such errors work with near-100 percent accuracy. Ryan also said that secret keys in post-quantum algorithms may be similarly vulnerable to exposure caused by computational errors.

“Our research reiterates the importance of defense in depth in cryptographic implementations and illustrates the need for protocol designs that are more robust against computational errors, like is exhibited by TLS 1.3 or certain configurations of IPSec,” Ryan wrote. It “illustrates the importance of protecting against computational faults for any cryptographic implementation going forward, even in usage scenarios where an attacker is unlikely to have physical access.”