Infineon RSA Key Generation Issue | Hacker News Reader

Infineon RSA Key Generation Issue

yubico.com

238 pointscimnine87 comments

Relevant: https://arstechnica.com/information-technology/2017/10/crypt...

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.

A tool was created to let the people update their ID cards to use elliptic curve cryptography, it will be made public in november. Some time after that all the older certs will be revoked.

If they just revoked all the affected certs right now then there would be an outrage.

Also cosider that it would currently take around $80k (and some non-negligibe time) to break one single pair of certificate (and thus a person's identity and signature) stored on one card.

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 $80k figure comes from the PR of the gov agency (RIA) responsible for the ID card infra. I'd take it with a grain of salt.

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.

The next obvious question is "whose signature is worth more than €5k a month (until the Smartcard is updated and the old sig is revoked)?"

Anybody who has assets worth more than €5k?

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.

Aren't these cards in Estonia used for a LOT of things, like banking access? EG: at 50k it's probably not profitable to do this per-user but at 5k it is probably VERY profitable if you could get enough public keys.

Even a single ID card can be valuable - factor a big company CEO's private key, log in to his company's bank, start making transfers to places where the money does not come back from.

> or any other of the vastly cheaper alternatives

On how many of these vastly cheaper alternatives is it possible to simply spin up a fleet of a thousand machines?

You are correct. I stated it as a fact whereas I was just assuming there are vastly cheaper alternatives to AWS to do such nefarious things such as renting machines in a botnet, using dedicated HW that you might have anyway around for coin mining etc.

Oh my. I recently met an Estonian couple and I felt like this national ID was a huge thing for the country.

It still is, they'll get new keys and be fine. Meanwhile in the US we're still stuck with social security numbers that aren't secure at all.

I guess it is indeed infinitely more secure than SSNs :) even with the current security issues.

Well, yes, it is. It's used for communicating with the government online, internet banking and signing all kinds of contracts. Wouldn't imagine life without it.

Not to mention voting online - yes, Estonia does this, and it's as insecure as you'd imagine [0].

[0]: [pdf] https://jhalderm.com/pub/papers/ivoting-ccs14.pdf

There's going to be little fallout for the users of this ID card. It's too expensive to break for all but the juiciest of targets - the people that need to worry are folks in enterprise and government.

Many people mentioned that the Estonian ID card is vulnerable. I have an e-residency card, so I tried it out on https://keychest.net/roca

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?

I wrote a tool to convert between all of the RSA key formats that I could find: http://github.com/jpf/lokey

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

(You can also replace "jwk" with any of the other supported RSA types. It might be easier to compare the "ssh" type)

I’m no expert, but a serialization format cannot change any inherent properties about the key in question. It’s just a matter of how it’s presented. The key is the same (vulnerable or not).

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?

I'm not sure where you're looking but around my parts, 1024, 2048, 4096 bit RSA is most common. Most of those are 2048 bit. I can't think of a 3072 bit RSA key I've run into in the wild. That's usually TLS, GPG, SSH keys.

Check www.keylength.com, 3072-bit RSA keys are useless.

I use this functionality on a near-daily basis, and received an email from GitHub this morning informing me that two of my older, backup SSH keys generated on Yubikey 4s had been revoked. I'm going to start the replacement process with Yubico this morning, and probably share my experience with it here.

FWIW, I went through Yubico's automated replacement process earlier for a couple of Yubikeys. It took just a moment, was pretty much fully automated, and worked perfectly.

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.

Unfortunately, since I had previously overwritten the factory OTP configuration, I had to take photos of my affected Yubikeys, including my email address in the photo. A bit longer, but still easy enough. Now to wait, and hope they don't deny my claim (despite having ordered them directly from Yubico in April of this year...)

Update to this: I submitted a photo earlier with both of my affected keys, and I just got an email back with a coupon code good for both keys, with free shipping.

As bad as this might have been, Yubico seems to be doing a top-notch job of covering their customers.

Same. Replaced around 6 Yubikeys, some of which were associated with GitHub. Fairly seamless replacement process (but have obviously yet to recieve the replacement keys yet..)

Shitty situation, but good response from both GitHub and Yubico.

If you bought your Yubikey on Amazon, you can't replace it directly, but have to contact the seller.

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.

Edit: Yubico has just responded again, and now also offers replacements for keys bought through resellers, with their sincerest apologies.

The issue should be solved now.

Update: managed to get a replacement for mine.

The Yubikey refund site just asks you to prove you own a Y4 by generating OTP inputs and then gives you a coupon code to buy directly from Yubico's site.

It doesn't if you bought via Amazon. I tried the page.

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.

To quote:

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

This is fucked up (and not the only part of Yubico's process I'm not OK with). They manufactured and sold security tokens that generate factorable RSA keys. They shouldn't be fucking around.

Here's the exact message, and my Yubikey: https://i.imgur.com/FVINcQB.jpg and the response from support: https://i.imgur.com/it8zxgp.png

Now I'm stuck with a Yubikey that's insecure, and replacement will take ages to get through.

I bought mine via Amazon.co.uk but fortunately my order was fulfilled by Yubico itself it seems [1].

So my key was eligible for the coupon and I got full $40 off and free shipping from Yubico store just a moment ago.

[1] https://www.amazon.co.uk/s?merchant=A2Z7AQ6XNQ4XXH&fallThrou...

Can someone explain why it should matter where you bought the product when there is only one manufacturer? Can't understand it at all.

That's weird. I bought two YubiKeys on amazon.co.uk about 1.5 years ago and was able to use the replacement form on Yubico's site (the one that asks for three OTPs) to order replacements directly from them.

I bought mine on Amazon.de on 2017-03-02, and it was apparently sold by MTRIX GmbH. The replacement form tells me "Please contact the team or individual within your organization that issued your current YubiKey."

Yubico told me:

OTOH, I bought at least one of my affected ones via Amazon and had zero problems with a replacement.

It seemed to accept my request (didn't error on entering the serial - but I uploaded a picture instead of giving OTPs) - perhaps because it was sold by Yubico; fulfilled by Amazon.

The problem with Fulfilled by Amazon is that while you think you buy directly from Yubico, you might end up with a device from a reseller. Who actually ships your device is entirely random.

That's what happened to me, and it's infuriating.

It says on the page and order form who you’re buying from. The problem is that reseller agreement not being public — normally the products are the same across sellers but in this case there’s a big difference in what you’re getting.

That information isn't always accurate, but that's not even that relevant here.

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.

Lesson being buy directly from yubicon.

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.

Or just be careful on Amazon. I avoid third-party retailers for this reason because you never know what they’ll do for returns.

Just to update on this: I did get a coupon through, and have now ordered a replacement (directly from yubico.com this time) for zero cost, not even shipping which I thought I might have to pay.

So this is only a problem if you generate a key directly on your card instead of uploading it? Nothing else?

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.

For many people, a core value of a hardware token is "no one ever even momentarily had the key outside of this device, and extracting the key would destroy the device, so the token is the key". If you need a backup you can have a second token with its own key and make both keys authoritative. Or you could have three tokens, again each with their own key, and make it so you need two of the three to get access to the data. If you generate the keys off of the token you can never be 100% sure "no one else has a copy of this key", which should be at least somewhat distressing.

> If you generate the keys off of the token you can never be 100% sure "no one else has a copy of this key", which should be at least somewhat distressing.

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've stared at your post, for at least five minutes. I've read it at least a dozen times.

I can't figure out if you're being facetious or serious.

Because he wipes (writes to) the read-only USB stick? (The one that's had the firmware replaced with BadUSB, and which he then sticks in some other piece of hardware where it takes control of the machine and uploads his private key?

Not sure what you mean. The USB stick gets mounted as read-only on boot, so while technically you could write to it, this does not happen. The key never gets written to the USB stick, and is only kept in memory, sent to the wired printer as an QR code, and of course the Yubikey. I then wipe the USB just because, but there is no real point in doing so.

The largest vulnerability here would be the printer having some kind of memory, since BadUSB is a myth.

The whole laptop, no memory, no network, etc... Just for this.

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 work with keys used to move hundreds of millions of dollars. The effort to have an air gapped network is definitely worth it.

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?

Ah! That makes more sense. The closest I've come is working on an isolated network in a secured environment.

I can't be specific, but I'm pretty sure the data I worked with had very little comparative value.

It's an old laptop. Instead of throwing it in the trash, I kept it around.

The point of an SSH key whose RSA key lives on a Y4 token is that you can't back it up; that key is tied permanently and irrevocably to a specific piece of hardware. Since you can obviously lose that token, you simply install a backup SSH key along with the Y4 key.

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.

I use my yubikey as GPG key for mail and for pass(). I really like having a backup.

You can use your yubikey to store your subkeys (still generated on the yubikey itself) while your master key is stored somewhere else. If you lose your yubikey you can revoke the subkeys and generate new ones signed by your existing master key.

With few exceptions: A) you won't be able to decrypt old messages B) you'll have to upload new public SSH keys to all servers

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.

My password manager, hunter2 (https://chiselapp.com/user/rkeene/repository/hunter2/ ), overcomes this by spring multiple keys per password. If you change the password then all keys that currently know the password will also be updates.

pass() can make passwords readable by multiple keys as well, but then I'd have to add the keys before loosing one. Possible, but, well, a usb stick in a safe location does the job for me currently.

> B) you'll have to upload new public SSH keys to all servers

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.

You could also have some sort of mechanism that updates the various servers (puppet, ...) or central authentication via LDAP. SSH logins are the least of my worries. Not being able to access my passwords would suck, though :)

What email program do you use with Yubikey? I'm wanting to integrate more GPG into my email.

Thunderbird does the job. Used apple Mail with GPG for Mac before switching to Linux. That had a few glitches but was workable.

Anything that can work with GPG and GPGAgent should work with a Yubikey

Mail.app and GPGTools gives a pretty good experience if you’re on macOS

mutt works wonderfully w/ GPG.

Seems so.

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.

> It means that you have no backup.

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.

But then you're trusting the key generation software/hardware of your PC and some people feel this is less secure unless you're able to take drastic measures to secure the PC doing the key generation. Some people prefer the risk of losing their keys should their card/dongle get damaged or stolen so that they can have the card/dongle generate the keys itself using a verified mechanism (although in this case, clearly that verified mechanism wasn't working correctly).

That is incorrect: you can extract the key _once_ when generated on the device (at least with the OpenPGP applet) and hand it to e.g. paperkey for safekeeping.

do you have a source that private PGP keys are exportable?

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.

https://www.yubico.com/2015/04/yubikey-neo-openpgp-security-...

I have done this myself several times. That comment is accurate, but it's referring to the general case, post key generation.

Can you explain how to do this? I've never seen this functionality before.

Remediations so far:

- Chromebook https://sites.google.com/a/chromium.org/dev/chromium-os/tpm_...

- Windows https://portal.msrc.microsoft.com/en-US/security-guidance/ad...

If anyone is wondering if they are affected: https://keychest.net/roca

Note that the tool does not seem to filter out revoked keys, or take expiration into account. You have to cross check against what (sub)keys you still have in use.

How are they able to test my key within seconds?

The full paper is not out yet, so there is limited information. But the official website[0] mentions:

> The specific structure of the primes in question allows for a fast detection of vulnerable keys, even in very large datasets.

[0] https://crocs.fi.muni.cz/public/papers/rsa_ccs17

The affected keys are made by Infineon's weird RSA key generator. This produces keys with weird properties, listed in their 2016 paper and more so in the accompanying Technical Report.

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.

I think there's some obfuscation in the tests:-

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.

66PE do have a history of strange things happening to their RNG output. I wonder, was the RNG intentionally tampered?

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

Infineon still haven't said how their hardware is vulnerable?

https://crocs.fi.muni.cz/public/papers/rsa_ccs17 covers that aspect of the issue. Discussion here: https://news.ycombinator.com/item?id=15482441

Discussion overlaps with https://news.ycombinator.com/item?id=15482441

It appears that the blog post was removed shortly after publication. Here's what the text has been:

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

> The post Infineon RSA Key Generation Issue [2] appeared first on Yubico [3].

> [1] https://www.yubico.com/keycheck/

> [2] https://www.yubico.com/2017/10/infineon-rsa-key-generation-i...

> [3] https://www.yubico.com/

The article has been re-posted! I don't know if the content is the same, though...

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!

Reply on news.ycombinator.com