RSA (Rivest Shamir Adleman), invented in the year 1977, is used for encryption and to create digital signatures. For using RSA, cryptographic keys are needed. These keys are always set up in pairs, consisting of a secret key and a public key – therefore RSA is called an asymmetric cryptosystem. Such a key pair is based on two very large prime numbers, which have to be generated first. But still, even in the 21^st century, finding prime numbers of appropriate length, and checking if these are really prime, is a challenging task even for today’s systems. 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”. This algorithm is software-based and not related to hardware.

The foundations of “Fast Prime” date back to the year 2000. Its use started around ten years later after thorough reviews. As a sub-part of one cryptographic software library which is supplied to customers as a basis for their own development, 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. The renowned experts Matúš Nemec, Marek Sýs, Petr Švenda, Dusan Klinec and Vashek Matyas thereby identified weaknesses in specific algorithms, which in turn could be exploited in order to simplify the calculation of an RSA secret key. For this mathematical procedure, knowledge of the respective public key is needed. Furthermore, the team developed means to identify conspicuous characteristics of different manufacturers’ algorithms, thereby identifying the origin of groups of keys.

In the context of a responsible disclosure process, the team informed Infineon upfront that also “Fast Prime” could be exposed to an exploit using one of the newly developed analysis methods under a specific combination of preconditions: First, the application software must utilize the “Fast Prime” algorithm instead of the non-accelerated version, both of which are selectable. Second, the RSA key pairs have to be generated on a card or token which uses this algorithm. If these preconditions are met, then RSA key lengths of up to 2048 bits are considered to be significantly weakened in cryptographic strength:

Using the new method, the researchers estimated that RSA-1024 (not recommended anymore since 2013) keys could be retrieved using commercial equipment in less than 45 CPU-days on average. According to their latest results, an RSA-2048 key can be retrieved using efforts of about 50 CPU-years on average. This would mean 50 years on one commercial PC, but appropriately less on parallel systems (e.g. one year on 50 CPUs, one month on 600 CPUs).

Software functions for RSA encryption and decryption, as well as for RSA signature generation and verification, are not affected.

The TPM (Trusted Platform Module) is a security microcontroller mainly utilized in PCs for authentication of hardware and software. For the Infineon TPM, certified according to Common Criteria EAL4 (moderate), the “Fast Prime” algorithm was used by the TPM firmware. The basic “Endorsement Key” of the TPM is not affected, as it is generated during production using a non-accelerated algorithm. Nevertheless, RSA keys which are generated by the TPM itself, for example for the purpose of disk drive encryption, can be exposed. This can be the case if the public key gets known; for example if an adversary would get physical access to a device or if remote exploits are utilized first.

Infineon immediately took action by informing its related customers and offering mitigation paths. In parallel, an updated software function was developed in close co-operation with the research team, customers and the German certification body. The updated version of the software function is currently in the process of being certified and rolled out. The firmware for the TPM has been updated for production and for field updates.