In late 2017, Nemec, Svenda et al. published their research on the generation of RSA keys on several widespread hardware platforms. The research also noted a relevant vulnerability on the Infineon chip, used in the Estonian ID-cards.
Essence of the Vulnerability
Setting up an RSA key pair starts from generating two secret prime numbers_p_and q of roughly equal length and multiplying them to get the public modulus N = pq. E.g. if the modulus N is required to have 2048 bits, both p and q need to be approximately 1024 bits long. The problem stems from the fact that generating such primes is a non-trivial task, especially for a limited platform like a smart card chip.
To speed up the prime number generation, smart card manufacturers implement various optimisations. It is the optimisation mechanism chosen for the Infineon chip that was actually attacked by Nemec, Svenda et al..
By observing the distribution of remainders after division by small primes of the moduli generated by the chip, the researchers were able to determine that the primes produced during the RSA key generation follow the pattern
where M is the product of n first prime numbers for some_n_ that guarantees M to be of roughly the same length as the required p and q. So for example, in order to generate 1024-bit primes, M would be the product of 126 first primes from_2_ to 701 (so M itself is a 961-bit number).
A naive approach to factoring N would be going through possible values of a and using an algorithm due to Don Coppersmith to find k. However, this algorithm would need to go through ordM(65537) ≈ 2254 candidates of a.
However, the Coppersmith's algorithm allows quite a lot of flexibility. Namely, it only requires 1/4 of the bits of the modulus to be known to succeed. Hence for factoring, M can be replaced by its divisor M' that would have more than 
bits, but for which the search space of ordM’(65537) elements would be manageable. Note that for such an M', the primes p would still be expressible in the form
The explicit value for a suitable M' is not given in the article, but a method of searching for one is presented. We also note that to give a good time-success ratio, _M'_does not have to be optimal.
The authors claim that using their value for M', the search space for_a'in case of 2048-bit modulus would decrease to about 234.As a result, a 2048-bit modulus generated by Infineon chips can be factored in an expected time of about 140 CPU years (which would cost about USD1000 in electricity). Later, Dan Bernstein presented an optimised version of the attack which would be even 5..._25% more efficient.
The Estonian ID-card is used nation-wide for both governmental and private sector services. Several critical processes rely on the operability of the digital identity infrastructure, while some of the systems support the ID-card exclusively (in Estonia, mobile-ID is also available for authentication and digital signatures in many, but not all services). „Shutting down“ all ID-cards would have had a severe impact on the entire country, including the economic impact to the businesses, and probably resulted in the deployment of substitute measures with lesser security standards while making several services more costly and time-consuming.
Replacing all the cards physically would have taken a long time, given the necessary steps for creating an entirely new card: choosing the chip, programming and testing the application, acquiring the necessary certification and procuring the new cards equipped with the new chips. Only after these steps would the actual replacement procedure take place, limited by the low amount of available personnel in the Police and Border Guard service points. According to our estimates the process would have taken at least a year, if not more, to complete.
The alternative was to create a solution that would bypass the vulnerability by updating the existing cards. There is a requirement that keys must be generated on-card and never leave the card. This is required in order to be able to use the ID-card to give legally binding digital signatures. The vulnerability that we had to bypass was found in the on-chip RSA key generation procedure. We had to abandon using RSA altogether. Thankfully, the ID-card chip also supported elliptic curve cryptography which was not affected by the found vulnerability. The solution was to update the cards to use elliptic curve cryptography instead of RSA. We analysed the possibilities to continue with RSA by using alternative key lengths, but ruled them out for several considerations (e.g there was no capability of generating 3k keys within the chip). Moreover, the decisions had to be made before the article on the vulnerability was published. In that situation, migrating to ECC was the most viable decision.
What was done
NIST curve P-384 was chosen from the elliptic curves supported by the ID-card chip. Our main criterion for the choice was the level of support by operating systems and applications. The uptake of non-NIST elliptic curves with superior security properties by standardisation organisations, operating system and application developers has been slow and support is lacking. It must be noted that it is highly recommended to require the use of new cryptographic primitives by chip manufacturers. We might be facing an incident in the future that requires replacing the algorithms currently in use, and it is best to be prepared.
Since mobile-ID had migrated to elliptic curve cryptography some years ago, most of the ecosystem (including digital signature applications) was prepared for the change. The system for remote updates existed as well, as it had been in use before for replacing incorrectly coded certificates. The main weak point actually lay in the distribution – the system was not prepared to handle the updates for such a high volume of cards simultaneously.
Apart from the card application itself, ID-card drivers for different operating systems needed changing, web applications of the service providers needed updating and a new solution for the encryption and decryption of files had to be developed. During the process, several interesting RSA-specific ID-card use cases were noted that needed updating by service providers.
Operating systems and browsers generally supported the elliptic curves – there were a few issues noted with using elliptic curves on hardware crypto devices.
Devising the concept for the solution itself was done rather quickly, mainly due to the lack of alternatives. Most of the time was spent on the development and testing of the ID-card base software and card application, retuning the remote update system, updating the service provider systems to support the elliptic curves.
Practical Consequences
The two core functions of the Estonian ID-card are authentication and digital signatures. Legally binding digital signatures in Estonia have always been time-stamped, retaining the authenticity of digitally signed documents even throughout this situation, as it is possible to provide evidence that the signature was given before the information about the vulnerability became available. This is exemplary of how relevant the regulatory steps of devising a digital signature framework are,
The authentication function remained intact as well – if service providers follow the procedure of validating of the certificates, invalid and/or expired certificates affected by the vulnerability were prevented from accessing the services.
Future Recommendations
In the future, the infrastructure dependency on one digital identity platform must be decreased, the use of several alternatives must be encouraged and promoted. In addition, the update and replacement capacity, both remote and physical, should be increased. We also recommend the government to procure the readiness to act fast in _force majeure_situations from the eID providers.. While deciding on the new eID platforms, the need to replace cryptographic primitives must be taken into account– particularly the possibility of the need to replace algorithms with those that are not even in existence yet.