Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Passive SSH Key Compromise via Lattices [pdf]

eprint.iacr.org

Post reply on HN
Print view View original

41–50 of 57 posts

Re: Passive SSH Key Compromise via Lattices [pdf]

#41

Post by hannob »

supriyo-biswas wrote: post #21
hannob wrote: post #15

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/

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

Re: Passive SSH Key Compromise via Lattices [pdf]

#42

Post by oxxoxoxooo »

hannob wrote: post #15

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…

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

Re: Passive SSH Key Compromise via Lattices [pdf]

#43

Post by hannob »

oxxoxoxooo wrote: post #42
hannob wrote: post #15

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…

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

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.

Re: Passive SSH Key Compromise via Lattices [pdf]

#44

Post by oxxoxoxooo »

hannob wrote: post #43
oxxoxoxooo wrote: post #42

Earlier quoted context omitted.

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

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.

Thanks!

Re: Passive SSH Key Compromise via Lattices [pdf]

#45

Post by tptacek »

upofadown wrote: post #39
tptacek wrote: post #38

Earlier quoted context omitted.

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

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.

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.

Re: Passive SSH Key Compromise via Lattices [pdf]

#46

Post by fweimer »

tptacek wrote: post #37
rollcat wrote: post #36

Earlier quoted context omitted.

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

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

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

Re: Passive SSH Key Compromise via Lattices [pdf]

#47

Post by tptacek »

hannob wrote: post #41
supriyo-biswas wrote: post #21

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/

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 irrelev…

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

Re: Passive SSH Key Compromise via Lattices [pdf]

#48

Post by fweimer »

tptacek wrote: post #31
fguerraz wrote: post #7

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.

Some OpenSSL deployments use RSA plugins that do not contain the check—it's not in generic OpenSSL or OpenSSH code, so every engine plugin needs to implement its own check.

Re: Passive SSH Key Compromise via Lattices [pdf]

#49

Post by tptacek »

fweimer wrote: post #48
tptacek wrote: post #31

Earlier quoted context omitted.

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.

Some OpenSSL deployments use RSA plugins that do not contain the check—it's not in generic OpenSSL or OpenSSH code, so every engine plugin needs to implement its own check.

Which plugins are you aware of that are used for RSA signatures and don't check signature validity? Just curious, from your comment it seemed like there might be specific ones.

Re: Passive SSH Key Compromise via Lattices [pdf]

#50

Post by SAI_Peregrinus »

tptacek wrote: post #47
hannob wrote: post #41

Earlier quoted context omitted.

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 irrelev…

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 pr…

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.

Post reply on HN