Researchers extract RSA keys from SSH server signing errors

A team of academic researchers from universities in California and Massachusetts demonstrated that it’s possible under certain conditions for passive network attackers to retrieve secret RSA keys from naturally occurring errors leading to failed SSH (secure shell) connection attempts.

SSH is a cryptographic network protocol for secure communication, widely employed in remote system access, file transfers, and system administration tasks.

RSA is a public-key cryptosystem used in SSH for user authentication. It uses a private, secret key to decrypt communication that is encrypted with a public, shareable key.

Exposing hardware errors

A paper published by university researchers Keegan Ryan, Kaiwen He, Nadia Heninger, and George Arnold Sullivan, shows that it’s possible for a passive network attacker to obtain a private RSA key from SSH servers experiencing faults during signature computation.

“If a signing implementation using CRT-RSA has a fault during signature computation, an attacker who observes this signature may be able to compute the signer’s private key,” the researchers say in the technical paper.

The Chinese Remainder Theorem (CRT) is used with the RSA algorithm to lower the bit size for the public key and speed up the decryption time.

“These attacks exploit the fact that if an error is made while computing modulo one prime, say q, then the resulting invalid signature “s” is equivalent to the correct signature modulo one prime factor p, but not q,” the researchers further explain.

Although errors of this kind are rare, they are unavoidable due to hardware flaws. Given a large enough pool of data, an attacker can find and leverage many opportunities for exploitation.

This is a known problem that impacts older of TLS versions. It was addressed in TLS 1.3 by encrypting the handshake that establishes the connection, thus preventing passive eavesdroppers from reading the signatures.

SSH was previously assumed to be safe from this attack but the researchers proved that it is possible to retrieve RSA secrets using lattice-based attacks that recover the private key from partially known nonces.

The researchers note that their tests do not include results "for RSA-1024,SHA512 because the number of unknown bits in the hash is well beyond what we can brute force or solve with  lattices."

However, they add that "the lattice attack is quite efficient" and that their tests had a 100% success rate.

Using their lattice attack, the researchers managed to find 4,962 invalid signatures that revealed the factorization of the corresponding RSA public key, thus allowing the retrieval of private keys corresponding to 189 unique RSA public keys.

Many of the retrieved secrets came from devices with vulnerable implementations, the largest number of signatures coming from Zyxel devices.

The researchers disclosed the issue to Cisco and Zyxel earlier this year and the vendors investigated for the cause.

Cisco determined that a suitable mitigation was introduced last year in Cisco ASA and FTD Software. The company told the researchers that it was looking into mitigations in Cisco IOS and IOS XE Software. 

Zyxel found that the ZLD firmware version the researchers used in the experiment had switched to using OpenSSL, which eliminates the risk.

The researchers warn that if signing implementations using the Chinese Remainder Theorem (CRT) algorithm with RSA have a fault when computing the signature, an attacker observing the signature may be able to computer the signer's private key.

To counter an attacker's ability to retrieve the secret key, the researchers recommend implementations that validate signatures before sending them, such as the OpenSSH suite that relies on OpenSSL to generate signatures.

Source