Passive SSH Key Compromise via Lattices [pdf]

FWIW, RSA is well known to be difficult to get right because you have to select the primes very carefully, and must take explicit steps to avoid padding oracle attacks[1], and perhaps it's better to avoid it entirely.

[1] https://blog.trailofbits.com/2019/07/08/fuck-rsa/

> 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.

Seems like over long periods, it can occur a spoopy amount of time.

It's akin to me having the secret number 17, giving you 221 (17*13) and then, during a solar flare, fucking it up once and giving you 187 (17*11). You know that the numbers are the product of a multiplication, and you know that a common factor is my private secret number. You figure out that the only way to get to 187 and 221 while keeping a common factor is if that factor is 17. That's just computing the GCD.

>An RSA public key consists of a public exponent 𝑒 and a modulus 𝑁 = 𝑝𝑞 that is the product of two primes. The private key consists of the private exponent 𝑑 = 𝑒 −1 mod 𝜙 (𝑁) and 𝑁 . A textbook RSA signature on a message 𝑚 is the value 𝑠 = 𝑚𝑑 mod 𝑁 . To verify the signature, a user checks if 𝑠𝑒 mod 𝑁 = 𝑚

> these attacks exploit the fact that if an error is made while computing modulo one prime, say 𝑞, then the resulting invalid signature ˆ𝑠 is equivalent to the correct signature modulo one prime factor 𝑝, but not 𝑞. 2.2.1 GCD attack on fully known messages. Boneh, DeMillo, and Lipton noted [11] that if an attacker had a correct signature 𝑠 and an incorrect signature ˆ𝑠 of this form then the attacker could compute gcd(𝑁, ˆ𝑠 − 𝑠) = 𝑝

I remember they fixed that one, but plundervolt is more finely targeted, like a traditional glitch attack. The fun thing with this attack is we just need a little bit of corruptions everywhere, and some broken signatures might make it through!

DVFS aside, there's plenty of ways to stress and CPU and cause random errors. I don't know whether their RSA implementation protects against this attack, though.

Headlines:

* In (rare) vulnerable targets, this allows you to recover the host's key, and thus impersonate a host. You can't compromise client credentials with this attack, since client credentials are exchanged after the (active) secure channel is established. If you can impersonate a host, as this attack would allow you to do, you could capture client password credentials, and you can drive a forwarded agent.

* OpenSSH --- really, SSH servers on any Unix host you've been using in the last 20 years --- isn't vulnerable to this attack. The vulnerability is publishing a signature that is validly signed under RSA p and not under RSA q. Solution: just never do that; when you generate the signature, check it yourself before publishing. This is one of the better-known attacks on RSA, so this is a standard implementation countermeasure.

* The things that are vulnerable are crappy middleboxes from Zyxel, Mocana, apparently a rare subset of Cisco devices, and whatever "SSH-2.0-SSHD" is (the authors don't know either).

* This is a Nadia Heninger paper, and Heninger is, like, the modern master of the Coppersmith RSA attack, which transforms an RSA problem into a series of polynomials and then transforms those into a linear algebra problem set in a lattice (roughly: a vector space with exclusively integer components; really, when we say "lattice" we mean "some generated basis for that lattice"). You then use the LLL algorithm to reduce the basis, which gives you small vectors that, when reframed back into polynomials or whatever, can tractably solved for their roots. Get the intuition? Yeah, I mean, me neither. Lattice attacks on PQ crypto have a simpler intuition! But the lattices bases here are just R^3 matrices, so, that's pretty simple.

* You can get the intuition for the underlying vulnerability much more simply. From the paper: Boneh, DeMillo, and Lipton noted that if an attacker had a correct signature s and an incorrect signature s_hat of this form then the attacker could compute gcd(N, s_hat − s) = p. The complicated math comes from the fact that while we have the incorrect signature we're hoping for, we don't have the correct signature over the same message, or a fully known message.

* This attack is made possible by our old friend PKCSv1.5, this time in a signing setting. It works because a P1v1.5 RSA signature has regular format: 00 01 FF ... FF 00 aa .. aa hh .. hh, where aa are the (known) bits of the ASN.1 identifier of the hash, and hh are the (unknown) bits of the hash. Everything but the bit values of hh is known to the attacker.

* Amusing detail: the attack relies on a condition of the unknown bits being less than 1/4 of the RSA message (modulus) size, so the attack actually gets harder for RSA-1024 with better hashes, and is impossible for RSA-1024 with SHA2-512, which blows that budget.

* Another thing that uses PKCSv1.5-RSA signatures is DNSSEC. You could scan the Internet collecting DNSSEC signatures hoping to find some that don't validate (I think it's RIPE that periodically does surveys looking for invalid DNSSEC records, and routinely finding them?), and because all RSA DNSSEC is in viable parameters for this attack I guess recover keys from it? Or you could just not use DNSSEC. I guess maybe this is particularly problematic for "online-signers"; most DNSSEC signatures are computed offline, so you can't just repeatedly ask for new signatures waiting for a fault, but you could with an online signer.