It's worth pointing out that GitHub apparently revoked affected certs (generated by Yubikey 4), while the 750k affected national ID cards in Estonia will stay in use and certs won't be revoked for now.
If they just revoked all the affected certs right now then there would be an outrage.
That's not to say that everyone's safe, but before the attack becomes properly feasable (and it will be), everyone will be upgraded or revoked.
The affected Estonian ID cards use 2048-bit RSA keys. If you look at the Ars Technica link then they are quoted:
the worst case for a 2048-bit one would require no more than 17 days and $40,300 using a 1,000-instance machine on Amazon Web Service ... On average, it would require half the cost and time to factorize the affected keys.
I assume this is calculated based on the standard EC2 prices ($40300/key with 17 days and 1k machines). If you'd use EC2 spot instances (or the relevant Google or Microsoft services - or any other of the vastly cheaper alternatives) then the cost comes down to about €5k (and 8 days with 1k low-tier EC2 machines) for a single key pair (on average, worst case is 2x that much).
I'm not the one to judge if that's cheap or expensive enough to not worry about anybody ever breaking a key. I just have to point out that this key is equivalent to a real signature and documents signed with it (also cast votes etc) are legally binding. In case of a breached private key, there's no (known) way to prove if it was you who signed some documents or an attacker.
And there's currently no publicly announced plan/date for revoking the affected certs. There's a tool coming out in November that you can use to generate new certs for your own ID card but as it's not compulsory, don't expect 100% of affected people to update in a matter of days, weeks or months.
On how many of these vastly cheaper alternatives is it possible to simply spin up a fleet of a thousand machines?
: [pdf] https://jhalderm.com/pub/papers/ivoting-ccs14.pdf
If I use "pkcs15-tool --read-ssh-key 1" to read out the public key, (in the "ssh-rsa AAAAB3Nza....." format), then I get a vulnerable key warning (2048bit SSH key).
On the other hand, if I use "pkcs15-tool --read-ssh-key 1 --rfc4716" to output in "---- BEGIN SSH2 PUBLIC KEY ----...." format, then it shows different key tests and tells me it's "safe key".
Is this a weakness of the test, or is there really some difference between the "regular" and the "RFC4716 formatted key (I wouldn't expect that)? What am I missing?
EDIT: using the standalone "roca-detect" (note, Python2 is required), then the first format reports potential vulnerability, while running it on the second format results in "Exception in processing PGP rec file estonia1.asc: Incorrect padding". So I guess it is indeed that the tool does not handle RFC4716 formatted SSH keys correctly?
If you're still curious if the key material is different (I'm very curious), try the following and compare the results:
pkcs15-tool --read-ssh-key 1 | lokey to jwk
pkcs15-tool --read-ssh-key 1 --rfc4716 | lokey to jwk
Can anyone tell me if using 3072 bit keys would have made a difference? Everywhere I look, 3072 bit RSA/256 bit ECDSA/256 bit hash functions/128 bit AES (=128 bits of security) seems to be the standard. Why choose 2048 bit keys for a national ID card?
They gave me a coupon code, I went to their online store, and ordered the replacements.
The whole thing took maybe five minutes from start to finish.
As bad as this might have been, Yubico seems to be doing a top-notch job of covering their customers.
Shitty situation, but good response from both GitHub and Yubico.
As Amazon tends to intermingle supply from different resellers for Fulfillment by Amazon products, you might have a Yubikey whose Serial No is registered to a different reseller than the one you paid - as result, replacement is going to be complicated.
EDIT: Here the message the Yubico website displays: https://i.imgur.com/FVINcQB.jpg, and the response from the support: https://i.imgur.com/it8zxgp.png
Now I'm left with a Yubikey that's produces broken RSA keys, and Yubico refuses to take responsibility.
The issue should be solved now.
Update: managed to get a replacement for mine.
It just shows an error and displays:
> Please contact the team or individual within your organization that issued your current YubiKey.
I contacted Yubico support, and they said this is expected, and I'll have to contact the reseller that sold the key on Amazon.
> Thank you for contacting Yubico Support. That was bought through MTRIX GmbH, one of our resellers. They are responsible for replacement of all devices bought through them as part of the reseller agreement. You will need to contact them for the replacement process.
Now I'm stuck with a Yubikey that's insecure, and replacement will take ages to get through.
So my key was eligible for the coupon and I got full $40 off and free shipping from Yubico store just a moment ago.
Yubico told me:
That's what happened to me, and it's infuriating.
It's not made clear at all how you have to handle RMA in such cases, and customers end up confused. I'd never have bought a Yubikey this way if I had known about the RMA and replacement procedure beforehand.
It kind of makes sense to have as few trust points involved as possible when buying a security device like this.
One could argue yubicon should only sell directly, but that would probably hurt business.
I don't really understand why you would do that since there's no way to extract the key from the token once generated. It means that you have no backup. For this reason I always generate my keys on a trusted, offline computer, make a few backups and then upload it on the token. I guess that's one more reason to do so, at least you don't have to trust the RGN of the device.
Eh. I use a laptop with no local storage nor network booted off a read-only USB stick, and for good measure I wipe the USB stick after I'm done.
I can't figure out if you're being facetious or serious.
The largest vulnerability here would be the printer having some kind of memory, since BadUSB is a myth.
I'm not sure if they are serious or if they really do so. If they do, that's quite some dedication to security.
I certainly don't do that for the keys I use to access my home computer though.
Security is economics: what's it worth to attack you?
I can't be specific, but I'm pretty sure the data I worked with had very little comparative value.
There are somewhat understandable reasons for wanting to back up TOTP secrets (it's a royal pain to re-enroll with a new device). But people who back up their Y4 RSA keys are sort of missing the point.
If you use 'pass' for storing passwords, then (A) will make your password store unavailable.
And (B) is a lot of places you have to update. In fact I aim to make it impossible to connect and update my servers key without having the existing key.
In short, since sub-key infrastructure really works for signatures, it seems easiest to just backup your subkeys.
openssh supports a CA model, so .. you can set it up so that the servers trust the CA and the CA blesses the new key. Obviously, it just shifts the "but what if we lose the .." question from the user key to the CA key, but in many cases it makes a difference.
Anything that can work with GPG and GPGAgent should work with a Yubikey
I used my Yubikeys the same way as you did (using an old laptop which was wiped), not only to have a backup copy but because with well known software it is less likely to be problematic than some embedded chip developed on a budget somewhere.
It was my impression at the time that this was best practice for setting up Yubikeys for personal use.
That's actually a feature as it means you have physical access to the device. Obviously you don't want a single card to be the only key that can access a system, but it's a good technique to authenticate users. Lose the widget and you have to go talk to IT.
A statement in a blog-post by YubiKey:
> Note that moving usage of an OpenPGP key to a new YubiKey NEO requires that you have saved a backup copy of the private key on the card as there is no way to retrieve the private key from any YubiKey, including the YubiKey NEO.
- Chromebook https://sites.google.com/a/chromium.org/dev/chromium-os/tpm_...
- Windows https://portal.msrc.microsoft.com/en-US/security-guidance/ad...
> The specific structure of the primes in question allows for a fast detection of vulnerable keys, even in very large datasets.
The test they released today just checks for the oddest of those properties, if you divide the modulus (the main part of the RSA public key) by some small primes (e.g. 11) and take the remainder then instead of a random answer other then zero (zero would be super bad) you always get specific answers. So the code checks about two dozen small primes in this way.
This probably had nothing directly to do with the attack, but it finds Infineon keys and only those are affected.
As you say, the first few test numbers correspond just to simple divisor checks:-
Prime 3 paired with check number 6 (binary 110). So 1 << (n % 3) will only ever be 'safe' if n % 3 == 0, which is 'super bad' as you put it.
(2^3)-2 = 6
(2^5)-2 = 30 so this is a similar division check
(2^7)-2 = 126 ditto
I think these are just here as distractions as it starts to sometimes do different things at p=11
11 is paired with check number 1026, which is (2^10)+2 not (2^11)-2). So under what conditions does:-
( 1 << (n % 11) ) & 1026 != 0
Given 1026 only has two bits set (1024 and 2) it's a rather specific test for (n%11) = 1 or 10. All other residues would be safe.
Don't have time to investigate further for the other primes and check numbers but I can only think of some kind of p-1 or p+1 smoothness they can detect this way.
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:
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.
> Infineon Technologies, one of Yubico’s secure element vendors, has informed us of a security issue in their cryptographic firmware library. The issue weakens the strength of on-chip RSA key generation, and affects some use cases for the PIV smart card and OpenPGP functionality of the YubiKey 4 platform.
> FIDO U2F, OTP, and OATH functions of the YubiKey 4 platform are not affected. The YubiKey NEO, FIDO U2F Security Key and YubiHSM are not impacted, nor are the deprecated products YubiKey standard and YubiKey Edge. Externally generated RSA keys are not affected.
> Yubico estimates that approximately 2% of YubiKey customers utilize the functionality affected by this issue. We have addressed this issue in all shipments of YubiKey 4, YubiKey 4 Nano, and YubiKey 4C, since June 6, 2017.
> At this time, we are not aware of any security breaches due to this issue. We are committed to always improving how we protect our customers and continuously invest in making our products even more secure.
> We offer customers who are affected mitigation recommendations and optional YubiKey replacement. For more information please refer to our dedicated customer portal .
> The post Infineon RSA Key Generation Issue  appeared first on Yubico .
>  https://www.yubico.com/keycheck/
>  https://www.yubico.com/2017/10/infineon-rsa-key-generation-i...
>  https://www.yubico.com/
mods: Would it be possible to get this article reset, so that it appears at the top of the new list? I was thinking of resubmitting, but I'd rather cimnine get the votes!