RSA 2048-bit keys in Estonian ID cards issued after October 2014 are factorizable

On September 5, 2017, Estonian Information System Authority (RIA) informed about a security risk in ID cards:

On 30 August, an international team of researchers informed the Information System Authority (RIA) of a security risk affecting ID-cards issued in Estonia since October 2014 (including cards issued to e-residents), i.e. about 750,000 cards altogether. ID-cards issued before 16 October 2014 have a different chip and are not affected by this risk.

Now we have more details:

The flaw resides in the Infineon-developed RSA Library version v1.02.013, specifically within an algorithm it implements for RSA primes generation. [..] To boost performance, the Infineon library constructs the keys’ underlying prime numbers in a way that makes the keys prone to a process known as factorization. When generated properly, an RSA key with 2048 bits should require several quadrillion years—or hundreds of thousands of times the age of the universe—to be factorized with a general-purpose computer. Factorizing a 2048-bit RSA key generated with the faulty Infineon library, by contrast, takes [..] 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. All that’s required is passing the public key through an extension of what’s known as Coppersmith’s Attack.

The researchers examined keys used in electronic identity cards issued by four countries and quickly found two—Estonia and Slovakia—were issuing documents with fingerprinted keys, both of which were 2048 bits in length, making them practically factorizable.[..] While it has closed its public key database, Estonian government officials have also announced plans to rotate all keys to a format that’s not vulnerable, starting in November.

Details from Infineon:

Due to application-specific requirements, it is common practice to employ acceleration algorithms in order to generate key pairs, especially if time resources are sparse. Infineon also utilizes such an acceleration algorithm in time-restricted cases, called “Fast Prime”. [..] The foundations of “Fast Prime” date back to the year 2000. Its use started around ten years later after thorough reviews. [..] this software function was certified by the BSI (Federal Office for Information Security) in Germany. No mathematical weaknesses were known, nor have been discovered during the certification processes. Recently, a research team from the of the Masaryk University, Czech Republic, developed advanced mathematical methods to analyze and exploit weaknesses in acceleration algorithms for prime number selection.

In a way these findings are a blessing for the practical security of Estonian eID. Up to now, at least publicly the chip of Estonian ID card was presumed infallible, and if someone approached these issues in the risk analysis, it was considered a heresy.

There are several lessons to be learned on different levels of management. The current practice of the plain hope that the vendor of the unauditable chip will get it right, may not be a sustainable approach for the state which so heavily relies on the secrecy of the private keys held therein.


Leave a Reply

Your email address will not be published. Required fields are marked *