From earlier today, the general bug: https://news.ycombinator.com/item?id=15482441

Cribbing from my comment there...

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 difference between this and previous attacks is that the problem results from poor prime selection algorithms, not limited entropy. Briefly:

1. patterns in the small-prime residues of N tell you who made the key with some accuracy (based on 2016 research; I think they're probably not detecting the weakness directly but rather just detecting _other_ artifacts of a device that would otherwise, incidentally, generate poor primes)
2. a weak prime generator results in a largely predictable prime
3. 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?). Cost estimates given in the checker additionally bolster my belief that it's a Coppersmith/Howgrave-Graham attack.

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 smart card key (as you typically would be with smart card-backed 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.

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