Factoring RSA keys from certified smart cards:
Coppersmith in the wild

Analysis: What went wrong

MOICA has confirmed that the 184 keys now known to be weak were generated by Renesas HD65145C1 chips inside Chunghwa Telecom HICOS PKI Smart Cards. Standard security certifications did not prevent these keys from being factored. For example, these certifications did not prevent 46 keys from being divisible by the first prime number larger than 2^511+2^510.

Problem: Low-quality hardware RNG

It is clear that the random-number generator inside the chip hardware is frequently stuck in a short cycle, for example producing 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 etc.

There are several standard designs of hardware RNGs that avoid such problems, but the chip manufacturer is clearly using different designs (quite possibly along the lines indicated in U.S. patents 7424500 and 8260835). Possible motivations include the cost of high-quality hardware, the cost of licensing patents from other manufacturers, and the opportunity to obtain new patents.

There is no evidence that any of the certification procedures involved an assessment of the quality of the RNG design.

Problem: Inadequate sanity checks

A short cycle is not something difficult to spot. There are many standard automated sanity checks that will immediately and reliably flag short cycles.

The standard certification procedures do appear to have included sanity checks on a small number of copies of this chip within a limited range of environmental conditions. However, these procedures were obviously inadequate to catch the RNG failures.

It seems likely that a physical analysis of the RNG design would pinpoint the environmental conditions that could cause the RNG to fail, allowing robust low-cost tests. However, there is no evidence that any of the certification procedures included any such analysis.

Problem: No run-time sanity checks

The card operating system, HICOS, has two modes: a "FIPS mode" where the software watches for obvious failures in the chip RNG, and a "non-FIPS mode" that does not carry out such tests.

The ability of HICOS to skip these RNG tests was disclosed during the FIPS certification procedure. However, this did not result in HICOS failing certification; it merely resulted in extra words on the certificate saying that the certificate was valid only when the card was "operated in FIPS mode". The dangerous "non-FIPS" features were still present in HICOS, and certification of the card did not stop those features from being used. MOICA estimates that approximately 10000 cards were deployed in non-FIPS mode as a result of "human error".

It is also not clear how stringent the run-time tests were. Serious sanity checks require heavy computation, and carrying out that computation on the card rather than on a PC would be quite time-consuming. The "continuous random number generator test" required by FIPS 140-2 would have been satisfied with much less computation, simply testing each 16-bit RNG output for a match with the previous 16-bit RNG output, but this test by itself would not have caught all of the weak keys. The chip manufacturer provided RNG-testing software as part of the chip-certification process, but that software has not been published.

Problem: No postprocessing

In "FIPS mode" the HICOS card applies "postprocessing" to RNG output, using the output to seed a hash-based pseudo-random number generator. In "non-FIPS mode" the card uses raw RNG output to generate RSA secret keys.

Postprocessing does not stop attackers from finding complete RNG failures via GCD. However, it would have made the RNG failures somewhat more difficult to model, increasing the reverse-engineering cost for attackers. It would also have eliminated all applicability of Coppersmith's method.

As part of the chip-certification procedure, the chip manufacturer provided (unpublished) guidelines for postprocessing. The Common Criteria certification report stated that this software "shall be implemented by the embedded software developer". However, this statement had no enforcement mechanism: the chip was in fact certified, no matter what the software developer ended up doing.

Problem: Inadequate initial response

The research reported here started with a GCD calculation, testing millions of RSA moduli for common divisors. The results of this calculation were reported to MOICA in April 2012 and clearly demonstrated randomness-generation failures. MOICA's initial response was to revoke exactly the certificates sharing common factors and to issue new cards only to those users.

Finding repeated primes is much more than an indication that those particular RSA keys are vulnerable: it shows that the underlying randomness-generation system is malfunctioning. The correct response is not merely to eliminate those RSA keys but to revoke all keys generated with that generation of hardware and throw away the entire randomness-generation system, replacing it with a properly engineered system.

An absence of common divisors is also not an indication of security. There are many potential vulnerabilities resulting from bad randomness; it is important to thoroughly test every component of a random-number generator, not merely to look for certain types of extreme failures.

MOICA has now initiated the task of contacting 408 registration offices across Taiwan to manually trace and replace all of the vulnerable cards from the same batch.