On my normal morning commute I popped on Paul’s Security Weekly Podcast #535 just before hopping on the underground and I have to say it was an interesting journey; I was truly taken aback by their coverage of the ROCA vulnerability.
In a nutshell, with ROCA the attackers can find the private key using only the public key of devices hardcoded with RSA encryption… I know, RSA encryption is not secure?? No, RSA is and remains to be one of the most secure public key cryptosystems in existence. The vulnerability lies with the generation of random key pairs within Infineon’s Trusted Platform Module.
Firstly, let’s go back to basics and understand RSA key generation in it’s simplest form:
- Choose two distinct prime numbers p and q. < These must be truly randomly generated.
- Multiply p and q to get n. < n is the key length.
- Choose an integer e which has a special form. < greater detail can be found here
- Functions are then performed on n and e to generate a decryption key d.
- (n, e) is published as the public key.
- (n, d) is kept secret as the private key.
As you can see, the ultimate goal is that we want to keep a message secret, meaning d (the decryption key) must stay secret. From the steps above we can see that if p and q are known then we can calculate n and therefore d, so these must also be kept secret.
If you are unfamiliar with RSA key generation then you might be wondering why choosing two random primes, p and q, make this algorithm so secure; it is down to what is easy and hard for a computer to compute. A normal computer (i.e. not quantum) can compute p x q very easily and quickly. However, given a number n it takes a lot longer for the computer to work out which two primes were multiplied together to make n. This is called a one-way function, as it the core of our modern-day public cryptosystems.
Timings, length and randomness
Lets have a look at timings and why it’s so important for RSA keys to be certain length and also generated from randomness.
On your personal Intel Dual-Core i7 computer, using programs freely available on the internet, you can factorise an RSA 256-bit n in 103 seconds according to this blogger. However, as the keys get larger by every bit it gets exponentially harder to break. As it stands an RSA 1024-bit n has not been cracked by any computer, therefore to be truly secure in the current climate it’s recommend to use keys between 1024 to 4096 bits long.
True randomness is where a machine cannot use any method apart from guessing and exhaustive search in order to find your number, this makes random numbers very important when generating keys. If there is any pattern to the number generation then you have a better chance of working it out than just guessing – meaning your cryptosystem is weakened.
True randomness does not come from computer algorithms, it can be generated by rolling a dice, atmospheric noise, radio active decay or even lava lamps, which are videoed and then run through a hash function to generate randomness at CloudFlare.
When using RSA so many random numbers have to be generated that it’s not practical to use the above generators to give us randomness, which is why computer generators have been created to provide us with pseudo-randomness (as random as we can possibly get with a computer).
How is this relevant when talking about the ROCA vulnerability?
We finally get to the actual story at hand, why is all this relevant to ROCA? Well, the vulnerability is that the pseudo-random number generator in Infineon Technologies AG Trusted Platform Module (TPM) is flawed and an attacker can work out p and q a lot quicker than normal.
The National Cyber Security Centre gives a great detailed analysis stating that any vendor who has utilised Infineon TPM to generate their RSA key pairs is now vulnerable to attacks with the following estimated timing and price:
Key length: 1024 bits | Time to crack: 15 minutes | Cost of attack: $40
Key length: 2048 bits | Time to crack: 15-16 days | Cost of attack: $20,000
To give an idea of the scale of this vulnerability, the following vendors have made statements and provided updates to their products: Microsoft, Google (Chrome OS), Yubico and Gemalto. Smart cards have also been widely affected and 750,000 of Estonia’s citizen ID cards will have to be reissued due to the flaw.
An interesting aspect is that there is a website which allows you to input your public key to see if you are affected, meaning you can tell straight away (before cracking the private key) if the public key is vulnerable. In real life terms it is like putting a flag outside every house which has left it’s door unlocked; waiting for opportunistic robbers to walk past. It has also been said that this attack is a dry run for what it’s going to be like when we have Quantum computers – our cryptography will be left redundant as the computers can work out the prime factors instantly.
In my opinion this flaw is heartbreaking for the cryptographic community; the embedded hardware (smart cards and yubi keys) that were affected are thought to be the most secure way of using cryptography. So in effect this flaw has hit the people in the field who were implementing crypto the right way.
Zoe Mackenzie 