Reconstructing RSA Keys from SSH Connections to Faulty Servers

A research team from the University of California, San Diego has demonstrated the possibility of reconstructing private host RSA keys of an SSH server by passively analyzing SSH traffic. This attack can be carried out on servers that, due to certain circumstances or attacker actions, experience faults during the computation of digital signatures when establishing SSH connections. These faults can be either software-based (incorrect execution of mathematical operations, memory corruption) or hardware-based (errors in NVRAM and DRAM, or power interruptions).

One way to induce such faults is through RowHammer attacks, which, among other things, can remotely or via JavaScript code in a browser cause bit flips in memory by repeatedly reading data from adjacent memory cells. Another method is exploiting vulnerabilities that lead to buffer overflows and corruption of key data in memory.

The published study shows that when SSH uses digital signatures based on the RSA algorithm, the parameters of the digital signature are susceptible to Lattice (Fault Attack) methods for reconstructing private RSA keys if software or hardware faults occur during the signature computation process. The core idea is that by comparing a correct and a faulty RSA digital signature, it is possible to determine the greatest common divisor and extract one of the prime numbers used to generate the key.

RSA encryption is based on modular exponentiation with a large number. The public key contains the modulus and exponent. The modulus is generated from two random prime numbers known only to the private key owner. The attack can be applied to RSA implementations that use the Chinese Remainder Theorem and deterministic padding schemes such as PKCS#1 v1.5.

To carry out the attack, it is enough to passively monitor legitimate SSH connections to the server until a faulty digital signature is detected in the traffic, which can then be used as a source of information to reconstruct the private RSA key. Once the host RSA key is reconstructed, an attacker can perform a MITM (Man-in-the-Middle) attack, silently redirecting requests to a fake host impersonating the compromised SSH server and intercepting data sent to that server.

Research Findings

By analyzing a collection of intercepted network data containing about 5.2 billion records related to SSH protocol usage, the researchers identified approximately 3.2 billion public host keys and digital signatures used during SSH session negotiation. Of these, 1.2 billion (39.1%) were generated using the RSA algorithm. In 593,671 cases (0.048%), the RSA signature was corrupted and failed verification. For 4,962 faulty signatures, the Lattice factorization method was successfully applied to determine the private key from the known public key, ultimately allowing the reconstruction of 189 unique RSA key pairs (in many cases, the same keys and faulty devices were used to generate different corrupted signatures). Reconstructing the keys took about 26 hours of CPU time.

Vulnerable Devices and Mitigations

This issue affects only specific SSH protocol implementations, mainly used in embedded devices. Examples of devices with problematic SSH implementations include products from Zyxel, Cisco, Mocana, and Hillstone Networks. OpenSSH is not affected, as it uses the OpenSSL (or LibreSSL) library for key generation, which has included protection against fault analysis attacks since 2001. Furthermore, in OpenSSH, the ssh-rsa digital signature scheme (based on sha1) was declared obsolete in 2020 and disabled in version 8.8 (support for rsa-sha2-256 and rsa-sha2-512 remains).

Potentially, this attack could also be applicable to the IPsec protocol, but the researchers did not have sufficient experimental data to confirm such an attack in practice.