So What Was The Problem With The Estonian ID System and TPMs? Weak Prime Number Generators (and RSA!)

The march of time in cryptography often means that something which is secure now may not be secure in a few years time. As long as humans introduce flaws into the implementation of the methods too, we will have weaknesses. But we should always have ways to revoke public keys and update our system. And so Estonia received a jolt in the usage of their ID system, and at the core of the problem was the availability of the public key and in the weak generation of prime numbers.

Let's start with the method that RSA uses to generate our keys [calc]:

We can see that the core element of the method is the generation of N, which is the multiplication of two prime numbers (p and q). If the value of N can be factorized, we can find the private key.

The flaw in the implementation of the Estonian ID system comes from the usage of a certain library - RSALib - and where a research team found that the variation of the values used to generate the prime numbers did not look quite right. Without the source code, they reasoned that the system which generating prime numbers using:

p=k?M+(65537^a mod M)

where k and a are unknown integers when cracking and M is the multiplication of the first n prime numbers. If we take a simple Python program we generate:

import sys

k=16

primes = [1,2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 
53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 
131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 
199]

a=12
M=1
for x in range(0, 30):
    M=M*primes[x]


p=k?M+(65537**a %M)
print 'M=',M
print 'p=',p

So for a=12, and k=3, and for the first 39 prime numbers used to generate M, we get [calculator]:

k= 3
a= 12
Number of prime numbers used= 39
======
M= 962947420735983927056946215901134429196419130606213075415963491270

Prime= 28888422684862029846771832244101148077859019965161804576999836
27091

The library uses the value of 39 (1...167) for the number of primes used to generate M for key sizes of 512 to 960-bits, then 71, 126 and 225 values are used for the key intervals 992-1952 bits; 1984-3936 bits; and 3968-4096 bits, respectively. M must be large and is around the same size of they generated. The weakness is the k and a are relatively small values, and the entropy of the keys falls significantly. For 512-bit keys, for example, the entropy drops to just 99 bits. The number of available prime numbers available for 512-bit keys then moves from 2^256 to 2^99 - a significantly weakening the method.

The attack focuses on Coppersmith method, and where the research team - through responsible disclosure - were able to factorize the prime numbers, and without gaining access to RSALib. Overall the research team verified the cracking of 512-bit RSA keys within less than two hours, and keys within 97 days (and at a cost of around $76 per crack on the Amazon AWS Cloud). These were achieved on a standard processor, and could be considerably reduced on multi-process systems:

As we see 2,048-bit keys (the current recommended size) takes over 140 years on a single and will cost over $40,000 for a single crack. At the core of the crack is the availability of the public key, as some of the bits of the key make it easier for the system to find the factors. For TLS and PGP it is relatively easy as the keys must be known, but for payment cards and electronic IDs, it is less easy:

In the research, the team assessed a wide range of datasets and found that the Estonian ID system and some TPM chips were highly vulnerable:

What can be done?

The Estonia Government have just defined that they are now in the process of updating their key infrastructure, but it will take a while to fully complete. They know that using electronic cards is just a stop-gap to a mobile solution, but need to fully migrate.

For just now, key government workers, such as in healthcare, are the first to get their key pairs updated. It will be a costly process, but, if it works, Estonia will show they have an infrastructure which can adapt to change. With 2,048 bit keys we see that it still takes years to crack a single key, and where 4,096-bit keys would take:

418,000,000 years

and at a cost of:

$366,000,000,000

For the library - RSALib - it needs to be changed so that it does not construct from a candidate of primes, but from random numbers, and then determine if the value is a prime number or not. If it is not prime we add one onto and keep going until we find a prime number. use the safe prime number defined in NIST FIPS 186-4).

A worry is that TPM chips on laptops will not be as easy to fix and that these would require a major update on the device.

Most new implementation for signing methods within IoT avoid RSA for its weaknesses and its complexity and thus concentrate on Elliptic Curve methods (Tor, Bitcoin and many RFID devices use EC). For ID, if you have to use RSA, it's got to be 2,048 bits or 4,096 bits!