TLS 1.3 starts a new road-map
TLS 1.3 starts a new road-map
This time it’s on a Quantum Path
While some organisations are on a path to insert backdoors into TLS 1.3 [backdoor], others are looking much further into the future, and making sure that our existing security infrastructure doesn’t open-up all of our existing data. And with GDPR on the horizon, things will be serious in terms of protecting data, with a large-scale breach of data bringing both fines and a reduction in levels of trust. In the future we must thus encrypt by default, and check of our connections for their identity and trustworthiness. But what happens if the Internet is cracked by a powerful computer?
Our existing methods
The race to defeat the cracking of public key methods with quantum computers has already started, and, to some extent, we must starting planning now to see the end of RSA and Elliptic Curve. The two main protections that we have are the difficulty in factorizing a number and in finding a discrete logarithms. For example if:
N = 167,393,905,215,827,498,969,023,638,554,233,713,209
then a computer must find the two prime numbers which created this factor, which are:
p=9,243,514,199,999,342,993 and q=18,109,336,080,842,435,113 [here]
If you want to see how this factorization cracks the keys, try [here].
For a discrete logarithm we have:
Y = G^x mod P
and where even if we know Y, G and P, it is not possible for us to find x within a reasonable time limit (as x can be many values). For example if we try a few values:
>>> G=3
>>> P=18109336080842435113
>>> x=5423
>>> Y=G**x % P
>>> print Y
1121168076396821668
In this case we use a prime number (P), and which is fairly small. In real-life we would use a much larger prime number, such as for a 1,048 bit one [try your own here]:
10,449,463,981,838,765,195,578,445,667,262,982,487,966,365,826,891,680,540,766,511,666,844,723,110,629,248,135,078,650,645,001,765,938,212,490,193,469,381,824,723,515,979,484,443,095,844,468,739,507,095,455,662,227,336,048,800,815,142,133,870,672,702,561,928,054,301,256,321,531,732,835,765,654,572,651,836,178,097,613,641,511,206,306,157,229,003,141,304,028,178,424,681,456,743,312,378,664,804,947,810,247,601,712,158,413,095,910,906,799,866,281,995,991,904,447,221,674,768,809,935,359,319,684,806,767,199,061,531
Now if we try:
>>> G=3
>>> P=10449463981838765195578445667262982487966365826891680540766511666844723110629248135078650645001765938212490193469381824723515979484443095844468739507095455662227336048800815142133870672702561928054301256321531732835765654572651836178097613641511206306157229003141304028178424681456743312378664804947810247601712158413095910906799866281995991904447221674768809935359319684806767199061531
>>> x=5423
>>> Y=G**x % P
>>> print Y
5944975377523390665533553615100450823464183757062333711866834887764379373853872891221744682715512606950313674716878833790423781343753247158152701149803483632156843524374039146167635987330135703437342576812184879731231964253325743467325815845621015759729819443294123098055177282263741477855385900461921632997239892579525521654360122623175390107679117250387270072374367553653492841008669
For this it would be extremely difficult to find the value of x which caused the Y value, even though we known P and G. As we increase the size of the prime number, the task becomes ever more difficult.
Quantum methods step in
These methods would be cracked, though, with a large-scale quantum computer. In the following table we see an exponential rise in classical time (using traditional public key methods), but where quantum computing methods only see a more linear increase in cracking time:
At the current time 512-bit RSA keys can be cracked, and the difference between 512-bit and 1,024-bit keys increases the difficulty by 100,000,000 times, and to 2,048-bit keys, it becomes 100,000,000,000,000,000 more difficult, but between 512-bit and 1,024-bit RSA, we only increase the difficult by eight times for quantum cracking methods.
We must now look to quantum-resistant cryptography, and are now looking at its methods being integrated in TLS 1.3. The core of TLS is to negotiate a key for the session, and to authentication the server to the client (and where you get the green symbol on an authenticated link). The negotiated key is then used with a symmetric key encryption method, such as AES (which is quantum robust). For quantum robustness the problem comes in with the key negotiation, and where we currently use Elliptic Curve or RSA to generate or protect the key as it is generated or passed.
Many, including Google, propose Lattice-based systems for quantum robustness [here], but these propose large keys and which can lead to delays in transmitting the keys. A new methods, proposed by Microsoft, are based on supersingular isogeny systems, and especially focused on supersingular isogeny Diffie-Hellman (SIDH). These have a lower overhead than Lattice-based methods, and also fit in well with the new standard for TLS 1.3. Microsoft have now added it as an add-on to Openssl, and companies such as Cloudflare are using it in their own network.
Diffie-Hellman
If you want to understand how the Diffie-Hellman (DH) method works, here’s a quick demo:
Within SSL/TLS we send a ClientHello with the parameters we want from the DH key exchange, and the server picks the one it wants, and sends back a ServerHello:
At the end of this they will have the same secret key, and have defined the symmetric key encryption they want to use. A method that is used in Tor, Signal, and many other applications is Elliptic Curve Diffie-Hellman (ECDH), and which merges Elliptic Curve methods with the Diffie-Hellman method:
Supersingular-isogeny Diffie-Hellman (SIDH)
The SIDH was proposed in 2011 by Luca De Feo and David Jao, and uses elliptic curves to build a quantum-resistant Diffie-Hellman scheme. If you want to understand Elliptic Curves, then here is a brief introduction:
A bit of maths …
Demo of SIDH here.
I may lose you here, but it’s worth sticking with in and to get your head round this. With isogeneous elliptic curves we do not deal with a single elliptic curve but a family of them. An isogeny is a map phi : E_1 -> E_2 of elliptic curves which sends the identity element of the source curve E_1 to the identity of the target curve E_2. It turns out that for every isogeny phi: E_1 -> E_2, there’s a dual isogeny psi: E_2 -> E_1, so we can say that two curves are isogenous if they’re linked by an isogeny.
If we have two curves (E1 and E2), we can create a rational morphism that allows us to map a point O on E1 to a point O on E2.
First we have a starting curve of E1, and defines points of P_A, Q_A, P_B, Q_B. Alice then select two scalar values — basically random numbers — m_A and n_A, and keeps these secret. She then determines a secret point which is:
m_A*P_A + n_A*Q_A
This is her secret isogeny (phi_A, and Bob calculates his secret: phi_B).
She then evaluates phi_A at point P_B, Q_B and sends E_A, phi_A(P_B) and phi_A(Q_B) to Bob. He does the same but swaps A and B.
Next, Alice uses E_B, phi_B(P_A), phi_B(Q_A) to construct an isogeny phi’_A using <m_A*phi_B(P_A) + n_A*phi_B(Q_A)>,
Bob uses E_A, phi_A(P_B), phi_A(Q_B) to construct an isogeny phi’_B using l <[m_B]phi_A(P_B) + [n_B]phi_A(Q_B)>.
Now phi’A maps to a curve E_AB, and phi’_B maps to E_BA, and we can define them is isomorphic. After this, we can calculate a value from the j-invariant, and where j(E_AB) is equal to j_(E_BA), and this will be the same shared secret between Bob and Alice.
You can read more [here]:
Conclusions
Presently SIDH is mainly untested, so the TLS 1.3 create a hybrid key exchange method, with both SIDH and the more traditional Curve-25519 elliptic curve method. So even if SIDH is broken, we will still have security of our existing Elliptic Curve (ECC) methods.
For symmetric key encryption (such as AES and Salsa20), quantum computers will half the security level, so that a 256-bit key will only have a 128-bit security levels. This is worrying as 128-bit symmetric key encryption would move to 64-bit levels, which are crackable on GPU-level systems. So, for your encryption keys, make sure you are using 256-bit keys for AES and similar methods, otherwise all of your keys could be crackable in the future.
If you are interested in some of the proposed methods, you can investigate them here:
- McEliece cryptosystem. mce. Outlines McEliece cryptosystem.
- Lattice Encryption. Lattice. This outlines Lattice encryption.
- Unbalanced Oil and Vinegar (UOV). UOV. Outlines Unbalanced Oil and Vinegar (UOV) cryptosystem.
- Generalised Merkle Signature Scheme. GMSS. Outlines Generalised Merkle Signature Scheme.
- Simple LWE. LWE. Outlines Learning With Errors.
- Lattice Encryption: NTRU (Python). NTRU. Outlines how NTRU operates for key generation.
- Lattice Encryption: Mod P polynominal operations. Poly. Outlines Mod P polynomial operations.