Security Flaw in Infineon Smart Cards and TPMs

A security flaw in Infineon smart cards and TPMs allows an attacker to recover private keys from the public keys. Basically, the key generation algorithm sometimes creates public keys that are vulnerable to Coppersmith’s attack:

While all keys generated with the library are much weaker than they should be, it’s not currently practical to factorize all of them. For example, 3072-bit and 4096-bit keys aren’t practically factorable. But oddly enough, the theoretically stronger, longer 4096-bit key is much weaker than the 3072-bit key and may fall within the reach of a practical (although costly) factorization if the researchers’ method improves.

To spare time and cost, attackers can first test a public key to see if it’s vulnerable to the attack. The test is inexpensive, requires less than 1 millisecond, and its creators believe it produces practically zero false positives and zero false negatives. The fingerprinting allows attackers to expend effort only on keys that are practically factorizable.

This is the flaw in the Estonian national ID card we learned about last month.

The paper isn’t online yet. I’ll post it when it is.

Ouch. This is a bad vulnerability, and it’s in systems—like the Estonian national ID card—that are critical.

EDITED TO ADD (11/14): More information from the researchers.

Tags: , , , , , ,

Posted on October 17, 2017 at 9:24 AM • 22 Comments

Comments

uh, Mike • October 17, 2017 9:52 AM

One step closer to the security apocalypse that forces us to demand secure products. It will be a lot of work. It will take a lot to force it to happen.

Anders • October 17, 2017 12:27 PM

The only question here is – was this vulnerability an accident or was this deliberately implemented to provide a backdoor for someone…?

estonian • October 17, 2017 1:56 PM

all Estonian cards will be migrated to ECC. Upgrade will be done online-remotely, within two weeks in November this year. Similar process was done for SHA1 to SHA256 upgrade.

Same cards are in use as ID in Slovakia – heard any news from there? Estonian government has done very open communication to its citizens and has worked out a proper mitigation very fast. There should be no criticd to Estonian government and its ID infrastructure.

Anders • October 17, 2017 2:05 PM

@estonian

Criticism here is in order – Estonian Gvt pissed on the experts opinions and nevertheless went on with the e-elections using vulnerable ID cards.

For that reason one high ranking government information security officer did resign of one’s own free will – de didn’t want to be a puppet on the politician’s hand any more.

So yes, experts were on the level but the political pressure on them was huge and inappropriate.

estonian • October 17, 2017 3:05 PM

Anders: you have facts or you just shout and blame? Sounds like anti-ivoting politician.

The way how Estonian government made the issue public and has been working on solution — is a good example.

Steve Loughran • October 17, 2017 3:57 PM

I got warned about my 4096 but yubikey based key being vulnerable by Facebook: I have my key registered with them and they clearly scanned through all keys to find those vulnerable…a nice little feature

The announcement: https://flic.kr/p/CoCo5h

Having revoked this key, I now see that git log —show-signature is warning that the signings are all invalid, which isn’t quite true. This shows a problem with key revocation and git commit signing. In future I’ll be using keys set to expire every year, so the consequences of a revocation are less

neill • October 17, 2017 5:38 PM

since there will always be problems with the hard/software implementation of those keys i always found it to be irresponsible to issue keys with expiration dates more than 5 or 6 years in the future – that’s 2 or 3 generations of moore’s

but sadly even after discussing public keys for 20+ years there’s no good infrastructure in place for the end user … (that is simple to use)

handle_x • October 17, 2017 8:30 PM

“Anders: you have facts or you just shout and blame? Sounds like anti-ivoting politician.”

No one shouted friend. i-voting has technical hurdles if ID’s can be compromised.
That’s not an exclamation, that’s an obvious fact.

However you should note that they shut down their national ID database to prevent unauthorized access, because the compromise potential is very real. It’s not the fault of Estonia or any other government for adopting standards that turn out to be flawed.

What they replace it with is the determinant.

toomas hendrik ilves • October 18, 2017 1:24 AM

Please examine the Estonian election system before simply venting. It is structured so that for the 40,000 USD of computation time required to enter once into the system, you can potentially alter one vote. With hundreds of millions of bank transactions annually using the identical system, why would anyone spend that kind of money on a single vote? To what end? Each vote change would cost 40k USD. It would be much easier to pay drunks to vote for a party for 5 euros. For the same money you would be able to alter 8000 votes.

Also re an earlier post on this blog, Estonia has the opposite of a “Central Data Base” but rather a distributed data exchange layer, where you can only access your own data and no one else’s. cf. https://www.ria.ee/en/x-road.html

r0b0 • October 18, 2017 2:25 AM

@estonian
Same cards are in use as ID in Slovakia – heard any news from there? Slovak ministry of interior is still in denial that any real problem exists.

handle_x • October 18, 2017 3:19 AM

The researchers seem to think there’s a good possibility of improving the attack.
The keygen itself puts out breakable keys but there’s no yet known issue with exchange.

From Steffen’s link:
Time complexity and cost for the selected key lengths (Intel E5-2650 v3@3GHz Q2/2014):
512 bit RSA keys – 2 CPU hours (the cost of $0.06);
1024 bit RSA keys – 97 CPU days (the cost of $40-$80);
2048 bit RSA keys – 140.8 CPU years, (the cost of $20,000 – $40,000).

But that’s assuming they’d need to pay for it and that the attack can’t be improved.
50,000 botnet cpus could crack a handful per day, perhaps many more. They’re not equally difficult, the computational time for each one is not uniform or predictable.
The article also says there are relatively quick tests to see if keys are affected even in large sets. They can sort and crunch only the affected keys. That’s a big cut.

Attackers don’t need #all_voters either to muck things up. But this isn’t just voting systems or limited to Estonia either. This is all over the place.

The only way to find out “for sure” if affected is to generate a bunch of keys and test every implementation. One can guarantee there will be neglected systems ongoing.

“The vulnerable chips are pervasive and not necessarily sold directly by Infineon Technologies AG, as the chips can be embedded inside devices of other manufacturers.”

I don’t see why Estonians should be feeling upset or defensive as if people are trying to insult their country. After all they acted responsibly and timely AFAIK.
They shut the DB down and they’re working on a fix. Seems better than average?

We know MANY of the voting and other critical systems used in the US are vulnerable in various ways, and just imagine how much more difficult a political endeavor it would be to force them to be fixed/replaced? They aren’t obscure crypto keyfails either.

Mike Gerwitz • October 18, 2017 8:25 AM

Steve Loughran:

Having revoked this key, I now see that git log —show-signature is warning that the signings are all invalid, which isn’t quite true

GPG (which Git uses) verifies signatures at the time of verification, not relative to the time of the signature.

Anders • October 18, 2017 10:13 AM

@toomas hendrik ilves

“Also re an earlier post on this blog, Estonia has the opposite of a “Central Data Base” but rather a distributed data exchange layer, where you can only access your own data and no one else’s. cf.”

We are not talking about your X-Road here, we are talking here about CA, central database of public keys, those are not distributed. Estonia has only one, yes, one CA, Sertifitseerimiskeskus, which is owned by banks and telecoms. Monopoly. Single point of failure for the whole ID card infrastructure. Experts have long time pointed out that Estonia needs also backup, public sector CA but hey, who listens them?

Estonian problem is that they consider their e-voting as a national proud. Tarvi Martens (Head of Internet Voting) once said : “those who doubts in e-voting security are not patriotic”.

So yes, who cares about security when you should be blindly patriotic, blindly trust what “ärmatajad” politicians tell you…

Ulrich • October 18, 2017 3:40 PM

It might be worth to point out that the link to Coppersmith’s attack is misleading. The corresponding Wikipedia article does not cover Coppersmith’s factorization of the RSA modulus when a portion of the bits of one of its prime factors is known. Though I don’t have access to the CCS paper, I expect that this is the attack mounted in practice (thanks to repeated bits during prime number generation).

Patrick • October 20, 2017 7:34 AM

The real reason Estonia has done such a stupid thing as implementing e-voting must be that then Putin won’t have to invade militarily when he wants to grab power. He just has to hack an election result. Much better for Estonia to avoid the whole war, bomb and casualty thing.

handle_x • October 22, 2017 1:08 AM

Putin doesn’t want to “grab” or “steal” Estonia, he wants Estonia to WANT to join HIM.

“In Soviet RUSSIA” right? Everything in the meme works backwards… Voters hack PUTIN!

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.