31–40 of 57 posts
So the vast majority of servers is not at risk because OpenSSH is not vulnerable to these attacks?
RSA digital signatures can reveal a signer’s secret key if a computational or hardware fault occurs during signing with an unprotected implementation using the Chinese Remainder Theorem and a deterministic padding scheme like PKCS#1 v1.5. [...] 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. T…
Crypto is hard, and part of the hardness is implementing it correctly.
To give some easier explanation: This is an attack against faulty RSA implementations. There is a common optimization in RSA signature implementations that splits up an expensive mathematical operation into two smaller operations. If one of these throws out a bad result then you can break the key. Why does this happen? Multiple reasons. Implementations of big number math can and does contain bugs. (I used to hunt for…
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/
My comments on "Seriously, stop using RSA":
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. * Ope…
But imagine if the problem is slightly changed to f(x) = (x + padding)^3 - a mod N, for some large but known padding. Now you can't simply compute an integer cube root, and the above doesn't work anymore. But you can look for a product of f(x) by some other polynomial g(x): f(x)g(x) necessarily contains the roots of f(x), but may have smaller coefficients such that evaluating f(x)g(x) at the root you're looking for does not wrap around N.
Now look into what this multiplication looks like: f(x)g(x) = c_0 f(x) + c_1 x f(x) + c_2 x^2 f(x) + ..., where c_i are the unknown coefficients of g(x). This is a sum of integer multiples of known coefficient vectors and, to find the set of coefficients c_i such that this sum is a small as possible is exactly the same as finding a short vector in the lattice (f(x), xf(x), x^2f(x), ...), where the vectors are the coefficients of each (shifted) polynomial. You also have to weight the coefficients according to their exponent, to account for the fact that the coefficient of, say, x^3 needs to be smaller than x to avoid wrap-around.
Once lattice reduction gives you back an f(x)g(x) with small enough coefficients you compute its integer roots, which is doable very quickly, and check which of them work for f(x). That's the gist of it. The full-fledged method also includes powers of f(x) modulo powers of N instead of simply multiplying it by g(x), and that was the trick Coppersmith introduced, but if you understand the simple version the full version is straightforward.
To give some easier explanation: This is an attack against faulty RSA implementations. There is a common optimization in RSA signature implementations that splits up an expensive mathematical operation into two smaller operations. If one of these throws out a bad result then you can break the key. Why does this happen? Multiple reasons. Implementations of big number math can and does contain bugs. (I used to hunt for…
Upstream OpenSSH uses LibreSSL, which they've forked from OpenSSL precisely because they were concerned with code quality and correctness.
I don't know whether this problem affects LibreSSL, but one of their main goals was to be less afraid of breaking the OpenSSL API to fix usability problems that lead to incorrect (insecure) code.
To give some easier explanation: This is an attack against faulty RSA implementations. There is a common optimization in RSA signature implementations that splits up an expensive mathematical operation into two smaller operations. If one of these throws out a bad result then you can break the key. Why does this happen? Multiple reasons. Implementations of big number math can and does contain bugs. (I used to hunt for…
> openssh uses openssl's RSA implementation Upstream OpenSSH uses LibreSSL, which they've forked from OpenSSL precisely because they were concerned with code quality and correctness. I don't know whether this problem affects LibreSSL, but one of their main goals was to be less afraid of breaking the OpenSSL API to fix usability problems that lead to incorrect (insecure) code.
Look for the comment:
/*
* 'I' and 'vrfy' aren't congruent mod n. Don't leak
* miscalculated CRT output, just do a raw (slower)
* mod_exp and return that instead.
*/Earlier quoted context omitted.
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/
Well, sure, but the alternatives are more complex and harder to get right. You can literally just pick two random numbers of the right magnitude, find the closest primes, and be good for RSA. My comments on "Seriously, stop using RSA": * https://articles.59.ca/doku.php?id=pgpfan:rsabad
Further: the article you linked to describes the attack we are talking about right now on this thread, a fully remote fault attack that harvested keys off random SSH servers on the Internet, as "a completely theoretical hardware attack". (Narrator: it was not; further, this is that "completely theoretical" attack in its most difficult setting.)
Earlier quoted context omitted.
Well, sure, but the alternatives are more complex and harder to get right. You can literally just pick two random numbers of the right magnitude, find the closest primes, and be good for RSA. My comments on "Seriously, stop using RSA": * https://articles.59.ca/doku.php?id=pgpfan:rsabad
No, the alternatives are less complex, and easier to get right. Further: the article you linked to describes the attack we are talking about right now on this thread, a fully remote fault attack that harvested keys off random SSH servers on the Internet, as "a completely theoretical hardware attack". (Narrator: it was not; further, this is that "completely theoretical" attack in its most difficult setting.)
In context it it obvious that I was addressing the contention that the paper I linked to had something to do with an implementation error.
So the vast majority of servers is not at risk because OpenSSH is not vulnerable to these attacks?
Correct. You are almost certainly not at risk. OpenSSL isn't vulnerable to this attack; your stack needs to be seriously archaic to have a vulnerable RSA implementation.