Return of Coppersmith’s Attack: Vulnerable RSA Generation | Hacker News Reader

Return of Coppersmith’s Attack: Vulnerable RSA Generation

crocs.fi.muni.cz

142 points0x022 comments

This, it seems to me, is a much more important vulnerability than the key-reinstallation attack on WPA2. It will take a very long time for every cached Infineon-generated RSA-1024/2048 key to be found and removed.

Yep. Infineon is one of the largest (the largest?) producers. Most consumers wont be affected, a few security nerds with Yubikeys will be, and then there’s a giant bunch of places that do PIV.

Infineon is ...

Hopefully people will soon be able to say Infineon was ...

There are certain screwups that are egregious enough to deserve a death penalty. This is one of them. IMO nobody should ever trust a crypto chip like this from Infineon ever again.

The paranoid side of me wonders if this flaw was accidental or intentional (a la Dual EC DRBG).

In addition, this passage (from an Ars Technica article [0]) seems "interesting":

> The researchers went on to find 15 factorizable keys used for TLS. Strangely, almost all of them contain the string "SCADA" in the common name field. All 15 fingerprinted keys have a characteristic involving their prime numbers that is outside the range of what's produced by the faulty Infineon library, raising the possibility there was a modification of it that hasn't yet been documented.

[0]: https://arstechnica.com/information-technology/2017/10/crypt...

More likely the pathology of closed-source software and hardware screwing up because few people will see inside the code or RTL, and the limited/no penalties for delivering an insecure HSM/TPM, processor, baseband or almost anything else.

So this is the vulnerability that broke the Estonian ID card program (see the technical references and media section). I had a feeling that was related to the Infineon TPM vulnerability; it seemed unlikely that TPMs were the only product affected or that two incredibly similar but unrelated vulns would come along at the same time. (See also https://arstechnica.com/information-technology/2017/10/crypt...)

>> Q: There was a recent (10th of October) security advisory regarding Trusted Platform Modules (TPM) by Microsoft, Google and other vendors. Is this connected to the vulnerability announced in this disclosure? A: Yes, this is the direct result of the vulnerability found as the affected devices are using TPMs with the vulnerable library.

So does this mean people will be able to attack TPM modules? Will we be able to sign firmware or do other things device manufacturers don't want people doing?

What can be attacked is the keys generated by the TPM chips. So things like biometric authentication and full disk encryption which rely on the TPM are vulnerable. Stuff like TPM based signature verification isn't directly affected unless the signing keys also were weak.

You should only be worried about this if you generated keys on a vulnerable device, such as a smart card (e.g. Yubikey) or a TPM embedded in your computer. You can detect if your card is affected with a variety of tools, both online and offline: https://crocs.fi.muni.cz/public/papers/rsa_ccs17#detection_t...

Fair word of warning: the offline (as in, on-your-machine) tools use a cornucopia of crypto libraries, meaning that it's nontrivial to build. If you're on macOS and don't know what an LDFLAGS is, you probably want the online checker.

Yubikey has their own tool: https://www.yubico.com/keycheck/

How does the attack work? The paper isn't released yet, but here's an educated guess. The authors have already indicated that this is not another variant of [BCCC13], a paper by Bernstein et al that relied on bugs in the CSPRNG of smart cards to find weak, factorizable keys. It does appear to build on earlier research by the same authors [SNSK16]. The detection tool is released, but that only shows us what the "fingerprints" (symptoms of a weak key) are, not how to factor them.

My best guess is that this is a Coppersmith/Howgrave-Graham [HG] style attack. The crucial difference between this and previous attacks is that the problem results from poor prime selection algorithms, not limited entropy. Briefly: patterns in the low-order bits of N appear in the high-order bits of p (since N=p*q), Coppersmith allows factoring if you guess sufficient high-order bits of p correctly.

So far the results I'm seeing appear to be cryptographically catastrophic but not so much operationally catastrophic. (please don't interpret this as me speaking ill of the paper: the paper is awesome) The range of real keys I've seen is currently between $40k and $4T (yes, trillion). That's pretty bad if you're running a company CA off of a $40k key, but probably not so bad you can't afford to wait for a replacement in most cases. If the fingerprints are to be believed, some keys can be factored in a matter of hours -- but I have no idea yet what the distribution of those keys is (i.e. is it 1 in 10 or 1 in 10k?).

As usual, the issue here is different with signing keys and encryption keys. If you're not using forward-secure ciphersuites and merely signing with a smartcard key (as you typically would be with smartcard-powered SSH or TLS) and instead are really encrypting with the key itself (GPG), you've lost confidentiality on all messages once that key is compromised. A compromised signing key merely allows for forged signatures, and by then you've hopefully revoked trust in that key.

Right now I have to go deal with immigration administrivia, but I'll get back to this.

[BCCC13]: https://smartfacts.cr.yp.to/smartfacts-20130916.pdf

[SNSK16]: https://www.usenix.org/system/files/conference/usenixsecurit...

[HG]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144...

btw, are yubikeys considered smart cards?

I'd say it's fair to consider them smart cards even if there's no real physical removable SIM-sized card. The non-U2F-only ones pretend to be smart cards, offering both PIV (traditional smart card) and OpenPGP applet modes. They're certainly functionally equivalent to smartcards for purposes of this attack.

I was curious so...

  $ roca-detect /usr/share/ca-certificates/mozilla/
  2017-10-16 13:37:50 [30012] INFO ### SUMMARY ####################
  2017-10-16 13:37:50 [30012] INFO Records tested: 132
  2017-10-16 13:37:50 [30012] INFO .. PEM certs: . . . 148
  2017-10-16 13:37:50 [30012] INFO .. DER certs: . . . 0
  2017-10-16 13:37:50 [30012] INFO .. RSA key files: . 0
  2017-10-16 13:37:50 [30012] INFO .. PGP master keys: 0
  2017-10-16 13:37:50 [30012] INFO .. PGP total keys:  0
  2017-10-16 13:37:50 [30012] INFO .. SSH keys:  . . . 0
  2017-10-16 13:37:50 [30012] INFO .. APK keys:  . . . 0
  2017-10-16 13:37:50 [30012] INFO .. JSON keys: . . . 0
  2017-10-16 13:37:50 [30012] INFO .. LDIFF certs: . . 0
  2017-10-16 13:37:50 [30012] INFO .. JKS certs: . . . 0
  2017-10-16 13:37:50 [30012] INFO No fingerprinted keys found (OK)
  2017-10-16 13:37:50 [30012] INFO ################################

Quite expected, as root certs are not generated by a smartcard chip. The paper itself says not much of typical browser TLS is affected.

Oops, I meant to post the results of running the tool across the US DoD's Root CA certificates (same result, FWIW) -- I have NFI how they are generated -- but thanks for the response.

I would hope that most root CA certificates are generated by and stored in HSMs but I really wouldn't be surprised to find that some little-known root CA went the cheap/easy route.

The requirements for being a public CA are self-regulated by the industry (via a consortium called CABforum including CAs and browser vendors). The requirements are far more stringent than that, but yes, you need an appropriate HSM.

There are some biases that are far more likely in some root CAs because they’re unusually long-lived. For example, I would expect Blum primes to be more prevalent among CAs than a randomly selected leaf certificate. This is because of pre-NFS/QFS folklore that they’re safer. While this is a detectable pattern, it’s not known to produce weaker keys, though it does effectively halve your set of primes.

> The requirements for being a public CA are self-regulated by the industry (via a consortium called CABforum including CAs and browser vendors). The requirements are far more stringent than that, but yes, you need an appropriate HSM.

Yeah, and no root CA would ever do anything to violate the BRs, right? /s

It’s true that BRs exist for a reason (and CAs occasionally fail to follow them), but roots not being on an appropriate HSM would be an extraordinary claim. The failures we’ve seen are not in the same ballpark.

We also checked all intermediate CA certs - all are ok. (sources: Certificate Transparency, Censys)

I guess I'll go and generate new (4096-bit) S,E,A GPG subkeys now, just in case...

The paper providers a bunch of public detection tools, both offline (just in case you don't trust them) and online:

tools: https://crocs.fi.muni.cz/public/papers/rsa_ccs17#detection_t...

online: https://keytester.cryptosense.com/

Yeah, I'm looking at those now, too.

> Note that 4096-bit RSA key is not practically factorizable now, but may become so, if the attack is improved.

I have to assume that the attack will improve and -- even if they aren't factorizable now -- will become factorizable at some future time (i.e. "just in case").

online:

https://keychest.net/roca

https://github.com/crocs-muni/roca

offline info: https://crocs-muni.github.io/roca/

Reply on news.ycombinator.com