“Go” Get Ready for the Post-Quantum Age with a CIRCL and Supersingular Isogeny Diffie-Hellman…

One of the companies I respect most in their approach to Internet security is Cloudflare. They have continually push every increasing…

“Go” Get Ready for the Post-Quantum Age with a CIRCL and Supersingular Isogeny Diffie-Hellman (SIDH)

One of the companies I respect most in their approach to Internet security is Cloudflare. They have continually push every increasing security standards, and have proved their credentials by publishing a new Go library for post-quantum cryptography: Cloudflare Interoperable Reusable Cryptographic Library (CIRCL) [here]. You basically can’t hide from the effects of quantum computers in cryptography, as they are likely to break most of our public key and key exchange methods. In this article I will outline a post-quantum contender to key exchange: Supersingular Isogeny Diffie-Hellman (SIDH), and use Go to implement it.

Introduction

Okay. Strap yourself in, and, it might take a while to fully understand the basic procedure here, but, if you’re interested in a future quantum robust world, it may be worth it. Before we start, you might want to read up on RSA methods here, elliptic curve methods here, and for Diffie-Hellman methods here.

Our public key methods are typically used to sign data/provide identity and for shared key generation. The methods include the Diffie-Hellman method (for key exchange), Elliptic Curve Diffie-Hellman (for key exchange), Elliptic Curve DSA (for signing), and RSA (for signing). The RSA method generates a value of N from the multiplication of two prime numbers (P and Q). Unfortunately quantum computers will be able to factorize N into P and Q, within a reasonable cost. Elliptic Curve methods use elliptic curves where we take a point on an elliptic curve (P) and then generate another point (Q) by using a gradient value (n), and where Q=nP. Again quantum computers will crack this method for a reasonable cost. For Diffie-Hellman, we use discrete logarithms, where we calculate a value of G^x mod p, and where G is a generator value and p is a prime number. Again quantum computers can crack this method with a reasonable cost.

So what’s the alternative? Well Supersingular Isogeny Diffie-Hellman (SIDH) is one of the first to be actually integrated into TLS 1.3, and can provide a direct replacement for key exchange.

Supersingular Isogeny Diffie-Hellman

SIDH is a quantum robust key-exchange method. It has a similar methodology to the Diffie-Hellman method, but is quantum robust. It is based on [2], and an enhanced version was created by Craig Costello, Patrick Longa, and Michael Naehrig at Microsoft [paper][3]. The method has one of the smallest key sizes for quantum robust cryptography methods (where 2,688 bits is equivalent to 128-bit public key security levels). It also supports perfect forward secrecy (PFS) and which stops the long-term key from being compromised, on the cracking of a single key (neither NTRU [here] nor Ring-LWS [here] are setup for PFS). Optimised code has shown the key parameters can be generated with 200 milliseconds, and the code has even been ported to ARM processors.

In the following, Medium does not fully support maths notation , so click here if you want to see the correct notation.

The basics

If we have two elliptic curves (E1 and E2), we can create a function that maps point (P) on E1 to a point Q on E2. This function is known as an isogeny. If we can map this function, every point on E1 can then be mapped to E2. Our secret key is then the isogeny, and the public key is the elliptic curve that we are using. For key exchange, Bob and Alice mix their isogeny and the other side’s curve to generate a secret curve.

With isogeneous elliptic curves we thus do not deal with a single elliptic curve but a family of them [paper]. An isogeny is then a map ϕ : E1 -> E2 and where the points on the source curve E1map to the target curve E2. It turns out that for every isogeny ϕ: E1 -> E2, there’s a dual isogeny ϕ: E2-> E1, so we can say that two curves are isogenous if they’re linked by an isogeny.

So Bob meet Alice

Let’s take an example of Bob and Alice generating the same shared key (as we do with the Diffie-Hellman methods). First Alice has a starting curve of E0, and four points on that curve: PA, QA, PB, QB.

Alice then select two random values ma and na and keeps these secret. These will be scalar values.

She then determines a secret point Ra which is:

Ra=ma×Pa +na×Qa

This is her secret isogeny (ϕa).

She then transforms Pb and Pq. Pq with this isogeny, and where Alice evaluates ϕA at point Pb, and at Qb.

She then sends Ea (her public key), and two transformed points (ϕA(Pb) and ϕA(Qb)) to Bob.

Bob does the same, but swaps the a and b values Pa for Pb, Qa for Qb and vice versa. He will generate his own random values mb and nb. Bob calculates his secret: (ϕB).

The following defines the exchange [1]:

Next, Alice uses EB, ϕB(PA), ϕB(QA) to construct an isogeny ϕ′A using:

mA×ϕB(PA)+nA×ϕB(QA)

Bob uses EA, ϕA(PB), ϕA(QB) to construct an isogeny ϕ′B using:

mB×ϕA(PB)+nB×ϕA(QB)

Now ϕ′A maps to a curve EAB, and ϕ′B maps to EBA, and we can define them is isomorphic. After this, we can calculate a value from the j-invariant, and where j(EAB) is equal to j(EBA), and this will be the same shared secret between Bob and Alice. Here a look here for the calculation of the invariant.

At the end of this, Bob and Alice will have the same key, and they will know that a quantum computer will not be able to crack it, and that no previous keys can be cracked.

The demonstrator of this method is defined here, and the following is an outline (based on code [here]):

package main

import (
    "bytes"
    "crypto/rand"
    "fmt"
    "github.com/cloudflare/circl/dh/sidh"

func main() {

    prvA := sidh.NewPrivateKey(sidh.Fp503, sidh.KeyVariantSidhA)
    pubA := sidh.NewPublicKey(sidh.Fp503, sidh.KeyVariantSidhA)

    prvB := sidh.NewPrivateKey(sidh.Fp503, sidh.KeyVariantSidhB)
    pubB := sidh.NewPublicKey(sidh.Fp503, sidh.KeyVariantSidhB)

    prvA.Generate(rand.Reader)
    prvA.GeneratePublicKey(pubA)

    prvB.Generate(rand.Reader)
    prvB.GeneratePublicKey(pubB)

    fmt.Printf("Alice private: %x\nAlice public: %x\n", *prvA, *pubA)
    fmt.Printf("Bob private: %x\nBob public: %x\n", *prvB, *pubB)

    ssA := make([]byte, prvA.SharedSecretSize())
    ssB := make([]byte, prvA.SharedSecretSize())

    prvA.DeriveSecret(ssA[:], pubB)

    prvB.DeriveSecret(ssB[:], pubA)

    fmt.Printf("\nAlice shared: %x\nBob shared: %x %t\n", ssA,ssB,bytes.Equal(ssA, ssB))

A sample run is:

Alice private: 0

Alice private: {{c000043c00 1} 263cd19c7ba407ff524f1fdca95fc727f6f60997e29a2284ec71ea66cfe84e03 }
Alice public: {{c000044300 1} [{[ccf0d548ddf07cbd 41199ff6cb06cd1c 26edf09167369570 583653a5dfc8bf79 a6b60a3e51ccef10 17d09493788c062e ca28c8e362c0577c 23e670204b7c2e 0 0 0 0] [1bebcdfe9a68e613 480868650344ae50 a51d0c94c4c35c0f 54980dbbf9d3ba74 768be9dc86eabf2d 65e47814164d67e1 7aac13c267169ee2 17a7cb569c0222 0 0 0 0]} {[653a2eeb739adaef b1b3de9baffda8a9 202a5c21c7655fe8 8850ea3e6831eb71 29dda4197c2c8d11 5f1779c50c36189c 1cec4572be725d94 4930889adf411 0 0 0 0] [37923a29ede16f4f bc9e52fb88852e3a f527ace725bc46df 1531958d06ccbe80 ef6319126721093c 1ee175ee2e559c43 8c3e8021db814e9f 3b0367ba4f8c12 0 0 0 0]} {[d8048555f96155b9 6aa4f05706d9b136 ea7eb22094c79deb 2e0fd664eb5831c3 be1ae15f1852ce37 85c6a5e5ff1da308 8c9a2af5b4b4ffb2 2c1711f1a6e0ee 0 0 0 0] [a7f3bb6eb1540728 4f86a78ca0a8c2c1 91f9d1bb5fa83045 6b9b1db7059a6270 744d633664da3983 dcec49662fd57327 4dedf20e70b77e6e 3d870d02d854b7 0 0 0 0]}]}
Bob private: {{c000044a00 2} 658bbaaca7c5d39687c172cd89e49ad259cccf3cf193dbb4e4f20329f17df90e }
Bob public: {{c000045100 2} [{[779fee56c8ae5a6d 1df5384bf4e875b3 e66a92e0674a6ac1 f4b812e744881eb9 87ddb7b75e0b881a 29c082d639ad247e 48a8b98261502531 35183c3418bd05 0 0 0 0] [48d60db3d3e8712a 9077e0efb3e742a1 78beaf48b2f93b1b 659d965bfdb3c7ac 804f1aa60ea1f3ae 1088ffa2a895f753 4be4ae41ff327b65 1bbfc3a56f6530 0 0 0 0]} {[53a5828dfed30fe9 ea1d9d39e51e107b 8204909ecd6e91d5 12327b817eb67166 4fd743c1400448be 23f778a231181804 1f7a764eaa240b21 382c3b4b33f1e2 0 0 0 0] [b4b227800846b6b4 589b3c40a510bc57 d6433037c4ce52e5 17edcd6e7b4d3d85 3971a2b34b2e22ea 360e9744f9c3fb74 1e96c717031e7dfc 243bcdfdf1e32c 0 0 0 0]} {[a75c045e62dcf5a5 7be21cee7a50b78f a2208f93932edbdf bd8fbf4cec758ac9 3532672b58939839 3f93bb3a8080d007 b60db88f3e237ace 48dc08eaa29106 0 0 0 0] [847f1a0bf673891f 6d00f16ccc02c2f4 88f9428aec35d449 d29085baef95abb4 8adf6402ca39965b 3722f594787565d4 c174301f2e2ca47e 31ac701f6f997e 0 0 0 0]}]}

Alice shared: 951774bd3663d61328044b79f0503813ad051691ef985b96529cab3d14c3c0ff0987f2b2e01863328df3240f0b84af97dc9df970b89e1fc5e2e8abaa7fa93c801538cec72bba6045cbf85056375294a0bd956b6fbeba6045f0e24961c7fcf689e7ee3036eb62976b41dc1794254c3418b2904a03b49f8758a78294e71223
Bob shared: 951774bd3663d61328044b79f0503813ad051691ef985b96529cab3d14c3c0ff0987f2b2e01863328df3240f0b84af97dc9df970b89e1fc5e2e8abaa7fa93c801538cec72bba6045cbf85056375294a0bd956b6fbeba6045f0e24961c7fcf689e7ee3036eb62976b41dc1794254c3418b2904a03b49f8758a78294e71223

Conclusion

Cryptography is fixing many of the problems caused within security, but it can help build a more trusted world. With quantum computers, many of the methods we use for trust will be cracked, and we must migrate to newer, and more robust methods, soon.

We are building a new world in GitHub, and Go is one of the best languages to support it, so “Go” and build a more secure world.

References

[1] https://www.academia.edu/32263564/Introduction_to_Supersingular_Isogeny_Diffie-Hellman

[2] De Feo, Luca, David Jao, and Jérôme Plût. “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies.” Journal of Mathematical Cryptology 8.3 (2014): 209–247.

[3] Costello, C., Longa, P., & Naehrig, M. (2016, August). Efficient algorithms for supersingular isogeny Diffie-Hellman. In Annual Cryptology Conference (pp. 572–601). Springer, Berlin, Heidelberg.