For The Building A More Trusted World: Countries With Vision Win Every Time

For The Building A More Trusted World: Countries With Vision Win Every Time

The world looks to Estonia as a model of how to build a more trusted digital world. As I fill in forms for my GP and print out my email address — which will never be used by the GP — with pen on paper, and tick boxes for illnesses that I can remember that me and my family have had, Estonia goes ahead and implements its health care system in a purely digital way. And, as I receive bits of paper through my letterbox which say “Dear Occupier, Please can you tell us who lives in your house?”, Estonia knows every citizen by their first name.

I live in an old world — based on old ways of doing things — and Estonia lives in a new world — and which is more trusted, dynamic and which can adopt faster to change. My government often sees digital services as putting a paper-based system into an online format, and fails to see the complete rebuilding that is required. I often shake my head in disbelief that at the insignificant amounts of funding aimed at “transform” our public services — and basically which just converts a paper-based system into an on-line form.

The conversion of something from paper, to a desktop application, and then to a Web form, is not actually transforming things, as it lacks a solid foundation for scaling across every digital service. Until we create an infrastructure which properly defines identity, roles, consent, governance and rights across multiple systems — and puts the control back to the citizen — we will not have a solid foundation to build on.

And so Estonia has managed to get switched on to a vision and which has brought together some of the finest digital architects and cryptography professionals to define a purely digital world, and one which transforms their public sector and also provides a foundation to build new services and take advantage of new opportunities. While other countries setup think tanks and select committees, and then publish white papers, the Estonian’s just rolled-up their sleeves and go on with it.

But this dream takes a sustained vision, and there are massive bumps along the way. Whenever these appear, the country will either give up, and admit defeat, or re-double its efforts, as the country knows that it is right.

And so it happened, in November 2017, that Estonia hit their greatest challenge in building a new digital world, and where some of the media around the world pointed fingers at them and said, “I told you so … it was never going to work … go back to form filling like us!”. Actually it was caused by something that was not of their doing — the RSALib bug — but they redoubled their efforts and came out much stronger at the end of it — and, in fact, they accelerated their move from a plastic card based ID to a mobile phone ID.

And Estonia again led the world. Their in-built route to migrate their cryptography has done them well in moving the infrastructure on, while computation power has increased.

If you are interested, the attack is based on the Coppersmith attack: here.

The RSALib bug

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ª (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²⁵⁶ to 2⁹⁹ — 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:

Conclusions

Over the weekend of the discovery, the Estonia Government went ahead and updated their key infrastructure. They knew that using electronic cards was just a stop-gap to a mobile solution, but now needed to fully migrate. Initially it was key government workers, such as in healthcare, who received the updates, but they pushed on with a complete roll-out of a new identity system.

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).

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

Every politician should learn from Estonia, and aim to transform their own country in the same way. It will have to happen sometime, so let’s do it soon, and let’s build a solid foundation for the future of our public services and our economy.

As long as I print my email address out for my GP (and which they will never use), and tick boxes on a piece of paper for my health background, we will be a million miles behind Estonia.

The world cried “Why don’t you just use paper!”, and Estonia said, “No! This is the 21st Century!” For my own beautiful country of Scotland, and in my home city of Edinburgh, I say, “Just get on with it!”.

If you are interested, the attack was based on the Coppersmith attack: here.