What Did 3rd Century Chinese Maths Teach Us About Cracking Encryption?

Around the 3rd Century, the Chinese mathematician Sun Tzu came up with a method - Chinese Remainder Theorem (CRT) - that has been used in many complex operations ever since, especially within implementations of RSA. Unfortunately, it has now been exposed as having a problem that can be used to crack the private key from an RSA signature. With Heartbleed we say a new bug being added to one of the versions, and which went unnoticed for over a year. With the latest RSA crack - RSA-CRT key leaks - the vulnerability has been added by a new feature within TLS tunnelling - known as the Forward Secrecy option.

Chinese Remainder Theorem (CRT)

CRT works by stating:

• If we have a number (x), and divide by a we get a result of w for the remainder.
• Next we have the same number (x) and divide by b, we get a result of y for the remainder.
• Finally we take the same number (x) and divide by c, we get a result of z for the remainder.

This gives us the following to solve:

x mod a = w
x mod b = y
x mod c = z

So we can use the Chinese Remainder Theory to solve for x. For example, if we take the following:

x mod 7 = 2
x mod 5 = 4
x mod 11 = 0

If we try different values of x, we find the x=44 will solve all of these.

Try this here: https://asecuritysite.com/encryption/chinese?val1=7,5,11&val2=2,4,0

So, can you solve this simple one:

x mod 3 = 2
x mod 4 = 3
x mod 5 = 1

Try 1, 2, 3, 4 .... [ans] ...

Remember mod is the MOD button on your calculator and is the remainder from a divide operation (eg 11 mod 4 is 3).

So what?

Werner Schindler [here] defined a timing attack on RSA which involves a factorization on the RSA-modulus if CRT has been used. The work goes back to 1996, when Arjen Lenstra defined an attack against an optimization (called the CRT). If a fault was generated in calculating a signature (using RSA-CRT optimization), the attacker can recover the associated private key from a signature. This is known as a “RSA-CRT key leak”.

Many systems have been immune from this attack as TLS did not use an RSA signature. Unfortunately the forward security option in TLS is now being recommended, and this has re-introduced the problem.

Researchers at Red Hat [here] have now found many Web sites which were not hardened against this type of attack, and found quite a few with RSA-CRT key leaks (none of which were code repositories). They found that the private key of a Web site can be leaked to the intruder, who can then decoded all of the encrypted communications with the site, and also impersonate it. 

Forward secrecy is used with a key-exchange method, and uses a session key which derives itself from a given set of long-term keys and which will not reveal the session key even in the long-term keys are breached.

Eve does her magic

Want to see a real crack for RSA using CRT? Follow this link:

Conclusions

Overall RSA has not been broken, but it is the implementation of it, using CRT, that has been broken. The attack does not leave a footprint of network activity as the cracking is done off-line (after a standard TLS handshake), although an IDS (Intrusion Detection System) could detect it by checking all of the mathematical operations.

Here's a Web page that computing CRT:

https://asecuritysite.com/encryption/chinese?val1=3,4,5&val2=2,3,1

One day, and I think it might be soon, we will wake up and RSA will be cracked. Either it will be super computers cracking the prime numbers, or it will be quantum computers, but when it happens there will be no proper identity on the Web and all the tunnels will be broken. RSA has faced up to the crackers, and still can hold its own, but often it is the implementation which has suffered. New features in TLS has also not helped its case.

The Internet needs to start thinking about the future, and Elliptic Curve Diffie-Hellman (ECDH) is perhaps one way to go, where public keys are exchanged, and both sides generate the same key. For just now, the key used by a tunnel is wrapped in the public key of the server, using RSA, so if this is cracked, we are in trouble!