[hannob]

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 those via fuzzing, which turned up an amazing number of them.) Hardware failures. Other bugs that corrupt numbers in memory.

The basic attack is well known. Florian Weimer has demonstrated this against TLS in the wild: https://www.redhat.com/en/blog/factoring-rsa-keys-tls-perfec...

The new thing this paper adds is applying this attack to SSH.

There is a countermeasure against this attack, and this is to verify the signature before revealing it. It works. As the paper says, openssh uses openssl's RSA implementation, and it has been doing that since forever (2001).

So in summary: Applying a well-known attack against RSA to its use in SSH. Only works if you have an RSA implementation that outputs results of flawed computations. Countermeasures exist, and RSA implementations should use them.

[supriyo-biswas]

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/

[hannob]

FWIW I wrote one of the papers re RSA padding oracle attacks, and I disagree with quite a few bits in this blogpost.

Yeah, there are pitfalls in RSA, but so are there in elliptic curve algorithms. I'm not sure if I'd say RSA has more pitfalls than ECDSA. Ed25519 is better, but so is RSA-OAEP/PSS over PKCS #1.5, where many of the common RSA pitfalls are. Most of the RSA pitfalls are in RSA encryption, which is irrelevant if you only use signatures.

You don't have to select primes very carefully. You can select random numbers, check if they are of the right size and prime, and you're good. What some people tend to do is to select primes in a "smart" way, which this post rightfully points out is problematic (see ROCA). But they also reference the batchgcd issue, which is not really an RSA issue. It is ultimately a bad RNG issue, and the very same issue also caused ECDSA implementations to break (with the same catastrophic "you reveal your private key" result).

[tptacek]

Ultimately, I think the big problem here is encryption. A footgun ECC constructions don't have is direct public key encryption; idiomatically, ECC "encryption" is a DH key establishment and then a block/bulk cipher doing the encryption, where RSA exposes a direct encryption transform that people idiomatically use.

It's just also the case that RSA in popular use is virtually never OAEP or PSS, and that this isn't a problem you have with ECC constructions, even if you're not using the most misuse-resistant of them.

It's also kind of a dead letter at this point. The ship has sailed: new designs all use curves, and have for something like a decade now.

(I didn't write a paper on this, but I do believe myself to be the proprietor of the Internet's single largest collection of Bleichenbacher padding oracle exploits, in every conceivable language, so there's my bona fides.)

[SAI_Peregrinus]

I'd say encryption and PKCS#1v1.5. The latter is just hard enough to implement safely that it's quite likely to be vulnerable, but not so obviously bad as to be considered definitively broken & set for removal. PKCS#1v1.5 support might not be a deliberate backdoor, but allowing it in a new protocol today would be suspicious.

We went to curves largely due to the flaws of PKCS#1v1.5, not so much due to RSA itself being bad (though the false sense of simplicity it has is certainly dangerous). RSASSA-PSS verification is fast, so while the keys & signatures are big there's still some reason to use it for constrained devices.

[tptacek]

This attack works regardless of how well you've selected your primes and relies on valid padding.

[upofadown]

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

[tptacek]

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

[upofadown]

The attack I linked to discussed completely theoretical attacks. No examples were provided. The attack we are commenting on does provide an example.

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.

[tptacek]

Yes, examples of the attack you dismissed. And you cited it as evidence on this thread about that attack. It's just very funny, is all.

[upofadown]

OK, thanks. I have updated the article to remove the term "theoretical" and have added an appropriate footnote that references the new work.

[rollcat]

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

[tptacek]

IIUC, the original 2001 countermeasure for this is embedded in the modexp routine, and both OpenSSL (in rsa_ossl.c) and LibreSSL libcrypto (in rsa_eay.c) have substantially the same logic.

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

[fweimer]

Note that in the OpenSSL case at least, this check is in the default engine/plugin, not in generic code. If you load a different plugin, you only get protection if the engine/plugin implements a similar check internally.

(I expect that LibreSSL removed the plugin framework, but I haven't checked.)

[oxxoxoxooo]

> Implementations of big number math can and does contain bugs. (I used to hunt for those via fuzzing, which turned up an amazing number of them.)

I'm curious, can you give some examples what kind of bugs did you discover?

[hannob]

CVE-2015-3193 in OpenSSL, CVE-2016-1938 in NSS. There were more, it's been a while.

Ultimately: things like a^b or a/b would return wrong results for certain inputs.

[oxxoxoxooo]

Thanks!

[viraptor]

> I used to hunt for those via fuzzing

That's such an obvious-in-hindsight idea. I love it.