Flaw crippling millions of crypto keys is worse than first disclosed | Hacker News Reader

Flaw crippling millions of crypto keys is worse than first disclosed

arstechnica.com

167 pointsTomte42 comments

The vulnerability is CVE-2017-15361 and is described in depth in https://crocs.fi.muni.cz/_media/public/papers/nemec_roca_ccs... . An implementation of RSA by Infineon Technologies AG did key-generation incorrectly; rather than select two random large primes, it selected two large primes with a particular structure, enabling the resulting public key to be factored. This weakness is not present in other implementations of RSA, such as OpenSSL. The vulnerable key-generation code is used in the Estonian eID system, TPMs, and by Yubikey 4.

Thanks for the paper. It only mentions testing 1024 - 2048 bit keys. Does this also impact anything using > 2048 bit keys?

Yes, but it takes longer to break them. Don't wait, revoke your keys and replace hardware or generate in software. It only affects RSA though so if you used ECC you're safe.

This is not especially good reporting from Dan Goodin. You're better off going to his primary sources, the most important of which is Dan Bernstein's blog:

http://blog.cr.yp.to/20171105-infineon.html

Really, all he's saying is:

* Estonia is expediting the replacement of their ID cards. They probably should have done that earlier.

* More Estonian ID cards are vulnerable than were previously known. But so many were known to be vulnerable in the first place that ROCA already represented a grave problem.

* Dan Bernstein and Tanja Lange were, unsurprisingly, able to outdo the exploit implementation that the original ROCA team came up with. Someone else will get a faster implementation. The vulnerability was only recently published; Bernstein and Lange got their competing attack by re-discovering it from clues from the partial "teaser" discovery. There's been no serious competition for exploits and probably won't be.

All the ROCA exploits we know of place broken Infineon keys in the category of "breakable by with a 5-figure budget". That was the case both before and after Bernstein's post. Obviously, you can't use RSA keys that are 5-figures away from being factorized. Someone may get the budget down to 4 figures, but if you're still using a vulnerable key by that point, you've got bigger problems.

The most irritating thing about this reporting is the angle Goodin chose: "flaw more serious than anticipated". No, even given just the teaser details, ROCA was known (and widely acknowledged) to be a game-over problem. And not just for Estonia: everyone using a Y4 key to protect a VPN or SSH connection also needs to have their keys recalled, so the security nerds were pretty alert to the problem.

The better angle for the story is "partial disclosure doesn't work". Disclose or don't disclose. Don't create an easter egg hunt by releasing a teaser disclosure. Nobody working in crypto or software security was too surprised that Bernstein and Lange were able to reproduce the attack from clues (there were a lot of clues). They're right when they say in their blog post that others have probably figured out this exploit before the ROCA team (especially since it was sort of teased from an earlier paper). Which leaves the question of why the ROCA authors bothered to withhold publication after announcing the flaw.

I found the blog post [1] by Dan Bernstein and Tanja Lange to be an interesting read, since it is written from the perspective of someone in the process of trying to reverse engineer the vulnerability, rather than the Nemec et al. [2] paper written from the perspective from someone who has already found the vulnerability. (Although the tone is a bit peculiar.)

1: http://blog.cr.yp.to/20171105-infineon.html

2: https://crocs.fi.muni.cz/_media/public/papers/nemec_roca_ccs...

You have to dig through to the original report article to find out what the flaw is.

"The flaw resides in the Infineon-developed RSA Library version v1.02.013, specifically within an algorithm it implements for RSA primes generation."

"The flaw affects only keys generated with the RSA algorithm, and then only when they were generated on a smartcard or other embedded device that uses the Infineon library."

"All told, the researchers estimate that Infineon's faulty library may have generated tens of millions of RSA keys in the five or so years it has been commercially available."

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

To be clear (as lots of stories talk about 'canceling' the Estonian ID cards), I was able to update my e-Resident card in minutes: https://twitter.com/jgrahamc/status/927581940483575813

To contrast your single positive account with a single negative account, my brother has been unable to update his Estonian e-Resident card because the system only works reliably on Windows. He has to wait to re-activate until the next time he goes to Estonia.

He has used the system from the outset and describes it as dated. It was built for a pre-mobile era and does not have a full-featured ecosystem for mobile devices.

Mine updated OK on OS X. While I have fellow e-residents here...

- Is there a trick to getting "Load picture" (my own photo) to work? All I've ever gotten is "invalid response," and this is on Windows, OS X, and Linux.

- Supposedly new Estonian IDs use ECC rather than RSA, but some articles seem to be confusing whether the once-vulnerable-but-now-regenerated IDs use ECC as well. I don't think that's possible, as the smart-card hardware doesn't appear to support it. Does an ECC key require new hardware for pre-November 2017 cards?

- For those of you who have been following Estonian ID technology for a while, why didn't they use regular OpenPGP cards that would enable cardholders to use ordinary PGP/GPG clients? Did the Estonian standard predate the OpenPGP standard? Or were there technical reasons the Estonian government needed something else?

> Is there a trick to getting "Load picture" (my own photo) to work? All I've ever gotten is "invalid response," and this is on Windows, OS X, and Linux.

No idea. It doesn't work for me either.

Odd. I did mine on Mac with no issues. I agree that the whole system feels clunky.

"use fast graphics cards, which have the potential to shave the average cost of factorizing a vulnerable 2048-bit key to $2,000."

Anyone has estimated the impact of this on crypto currency or crypto wallet system?

It would be interesting to see how many if any of the public keys use n crypto currency systems are potentially impacted by this type of hack.

Bitcoin and most other cryptocurrencies use elliptic-curve cryptography (in particular, ECDSA) instead of RSA. So this flaw is not applicable to Bitcoin. (One reason for Bitcoin using ECDSA instead of RSA is that ECDSA keys are significantly smaller than RSA keys for the same security level.)

In addition, in Bitcoin, the ECDSA public key for unspent transaction outputs is not itself stored in the blockchain; only the SHA256 hash of the key is stored. If the same private key isn't reused (and reuse is discouraged for privacy reasons), an attacker wouldn't have access to the public key.

Recently many bitcoin transactions are P2SH (addresses starting with 3) and it that case the address is not directly linked to any public key at all (1-addresses are hashes of ECDSA public keys, 3-addresses are hashes of arbitrary bytecode which validates the signature and is supplied together with the signature)

Even if they had used RSA keys, the vulnerability here is in a particular hardware/firmware implementation of the algorithm, not in RSA itself.

That was my immediate question and sadly TFA doesn’t address it.

> they estimated it would cost an attacker renting time on a commercial cloud service an average of $38 and 25 minutes to break a vulnerable 1024-bit key and $20,000 and nine days for a 2048-bit key

Can someone explain why a 2048-bit key isn't 2^1024 times as costly to break?

I don't know the answer, but since the vulnerability is because there is some structure in the chosen primes, you don't need to check all possibilities between 2^1024 and 2^2048. Only a known subset (i.e. a subset which is likely related to the 20,000/38 ratio)

Question: Once they knew there was a problem, and assuming they realized attackers could have already developed faster attacks or could start developing faster attacks at anytime, why did the company and the authors agree to delay publishing the paper?

> Ars is also aware of unconfirmed reports of a Western European country that also issues affected ID cards.

Any educated guesses?

Infineon seems to be popular supplier for smartcard ID cards over whole EU, with Estonia and Slovakia being special in that most of the issued ID cards actually have the chip (it's optional and not especially useful in most of EU). I would hazard to guess that said country is Luxembourg, Belgium or Germany (in this order of probability) as these countries also have somewhat large penetration of state-issued smart cards.

In Belgium all ID cards issued over the past 14 years have a chip, this should cover all people with a Belgian ID card as a Belgian ID card needs to be replaced in less than 14 years.

edit: As it is also required to have an ID card this should cover 100% of the population of Belgium.

Some batches of German ID cards use Infineon chips (I don't know which version as only some seem to be affected). A chip is built into all IDs issues since 2010 but it's disabled or at least unused on almost all cards. Not sure they actually do key generation on the card which seems to be the affected thing.

What I meant by penetration is the percentage of people who actually have the chip activated and use it for something useful.

In Czech Republic chip ID is optional and you have to pay (~20EUR) for the chip itself. As it does not have any meaningful purpose that is legal (loading your own certificate onto the card is technically possible but explicitly outlawed) even the local authorities issuing IDs will advise you that you don't want chip ID.

In contrast to that in the above mentioned countries I've seen state issued smartcards (regardless of whether they are EU-wide ID or just additional smartcard) used for useful purposes (eg. to submit VAT returns online, which is something that in .cz you can do with any PKCS#11 token of you choosing or by using state-run OAuth-ish ID provider)

I cannot provide any citation for that, but I believe that the EU regulations related to digital signatures require that the private key to not be available to the state, which implies either on-card generation or same process as is used by commercial CAs (which is the case in .cz, where you can choose from three or so CAs which are at least notionally commercial entities)

Basically nobody in Germany uses the chip for identification. I once opened a bank account with it just for the novelty but even the one use should put me into a very small group of active users. Even most government agencies don't offer to use your card.

Actually signing is performed differently and since this summer they switched to a cloud signing process where you don't have access to your key. You cannot get a certificate for a key on the card anymore. Not that anyone actually used that feature.

I mentioned Germany because I've seen Luxembourg-style smartcard authentication as one of posdibilities for submitting german VAT returns online when I cared about such things few years ago and the application involved in that looked mostly the same as Luxembourgh and Belgian one (Oracle Forms, similar UI...)

Edit: otherwise you confirm my suspicion that essentially nobody uses the chip on ID cards outside of Estonia (Slovakia is mentioned due to their recent massive rollout of chip IDs inspired by Estonia, but I assume that actual usefullnes is nil)

https://www.dnielectronico.es/PortalDNIe/PRF1_Cons02.action?...

Googling suggests that they might be another user of the ~~infected~~ infineon SLE78 platform.

wow... no comments? I'm not a crypto guy, but I am very curious why is it that this vulnerability does not apply to other services used here in the US. could anyone explain this?

Infineon RSA Key Generation Issue | https://news.ycombinator.com/item?id=15481334 (2017Oct:238points,87comments)

Return of Coppersmith’s Attack [ROCA]: Vulnerable RSA Generation | https://news.ycombinator.com/item?id=15482441 (2017Oct:142points,22comments)

It does, probably the Estonian ID cards are just used as an example as the most widespread/high profile deployment.

https://www.yubico.com/support/security-advisories/ysa-2017-...

Because in the U.S. it's only used in private solutions. No public facing systems in the U.S. are even secure enough for this vulnerability to affect it.

Do we know if this is intentional or not? Because this is probably the kind of thing NSA would love to implement.

No, it's the opposite of the kind of thing NSA "loves to implement". The only reason this bug took so long to find is that it's a hardware/firmware bug, and you have to take the time to survey hardware RSA key generation to find it. Despite that fact, a bunch of grad students found it. Once you know the broken shortcut Infineon uses to generate primes, working out the exploit is itself academic. See, for instance, the name of the attack (ROCA) and what it stands for.

The NSA wants cryptographic vulnerabilities that are cryptographically "NOBUS". Dual_EC was a useful backdoor (if surprisingly clunky) because even if you understand the weakness, you can't take advantage of it without having custody of a private key.

>> The NSA wants cryptographic vulnerabilities that are cryptographically "NOBUS".

That depends on who is going to use the vulnerable system and for what purpose.

How? In what situation does NSA ever benefit from a vulnerability that its adversaries can exploit?

Oh, that must be why they disclosed all those vulnerabilities they found instead of exploiting them...

The NSA finds and exploits vulnerabilities for their own uses, suggesting that they might create some is hardly a stretch.

plausible deniability. Or honey pots - first compromise a 3rd party target, then wait for your adversary to think they broke in. Either trace them back or plant false data.

How does a NOBUS vulnerability cost them plausible deniability? To prove it's their vulnerability, you have to know the private key that matches a public key.

If you're setting up a honeypot, why would you use an extremely complex cryptographic vulnerability? There's tens of thousands of straightforward software vulnerabilities that allow you to set up honeypots.

These don't sound like plausible reasons for NSA to effectively allow its own assets to be compromised needlessly.

> How does a NOBUS vulnerability cost them plausible deniability? To prove it's their vulnerability, you have to know the private key that matches a public key.

Of course not. If the public key came from the intelligence community and is a possible vector for attack, then a successful attack implicates them as the likely holders of the private key. BTW, "plausibility" doesn't imply "proof".

> If you're setting up a honeypot, why would you use an extremely complex cryptographic vulnerability?

Because of it's complexity, the honey pot is less suspicious to your adversary. If you compromise a 3rd party, then install a straightforward vulnerability, that raises flags. But letting your adversary compromise the system using the same vulnerability as you is perfectly natural.

This article focuses on Estonian ID cards, but presumably this affects the symmetric encryption of Bitcoin wallets as well, correct?

If the crypto can be broken for ~1000$, as mentioned, that seems like a serious problem...

No, it doesn't. This is a vulnerability in a particular implementation of RSA. Bitcoin doesn't use RSA at all, let alone that particular implementation of it.

When that happens, you won't hear about it in the news like this. You'll hear about it when the price of BTC plummets as all wallets are emptied.

Reply on news.ycombinator.com