AWS Goes SIKE and Thinks BIKE …

AWS Goes SIKE and Thinks BIKE …

We are on a warning … quantum computers will rip up most of the trust on the Internet. Once created at scale, they will be able to crack RSA, ECC (Elliptic Curve Cryptography) and discrete log methods, and which provide most of the signing on the Internet at the current time. Also, they are likely to reveal symmetric keys which are often secured with public-key methods.

So, who knows how quickly they will come to the market, but we need to, at least, investigate new methods. The ability for a quantum computer to break all of the secure connections that have ever been recorded, secure databases, and all of the blockchain records ever created, could cause large scale damage to the security of the Internet.

Amazon recently announced that their AWS KMS (Key Management System) will now support the integration of post-quantum cryptography within TLS handshake. This involves the porting Bit Flipping Key Exchange (BIKE) and Supersingular Isogeny Key Exchange (SIKE)for key exchange into their s2n library [here]:

It is defined as a hybrid scheme in that is uses the traditional ECDH (Elliptic Curve Diffie Hellman) method, and adds post-quantum methods (BIKE and SIKE). AWS KMS now uses two key exchange methods FFDHE (Finite Field DH Ephemeral) and ECDHE, and which are both ephemeral, so that the key are always unique, and cannot be derived from the leakage of the long-term private key.

SIKE

Supersingular Isogeny Key Encapsulation (SIKE) is a post-quantum cryptography key encapsulation method for key exchange and is based on Supersingular Isogeny Diffie-Hellman (SIDH). It has a similar methodology to the Diffie-Hellman method but is quantum robust. It was created by Luca de Feo, David Jao and Jerome Plut [2][paper] and enhanced by Craig Costello, Patrick Longa, and Michael Naehrig at Microsoft [3][paper], and has one of the smallest key sizes for quantum robust crypto methods (where the public key is 751 bytes).

In elliptic curve methods, the public key is only 32 bytes. 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] 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. The method is still relatively slow compared with elliptic curve methods (and requires around 50 million cycles of a processor).

Creating an isogeny

If we have two elliptic curves (E1 and E2), we can create a function that maps a 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 be mapped to E2. Our secret key is then the isogeny, and the public key is the elliptic curve. 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 points on the source curve E1 map 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.

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 selects 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 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 Ea, ϕa(Pa), ϕb(Qa) to construct an isogeny ϕ′a using ma×ϕa(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. For a curve of y2=x3+px+q , the j-invariant is:

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.

Coding

The following is an outline (based on code [here])[demo]:

A sample run is [demo]:

Alice private: {{c000049c00 6} 53a6702212c581353efe328ab5cd2d69a6e3d0ad9ee046c15c05e34844353608 3312d40ebe210cb860a9717564470e797dff2cce6cc6dc31}
Alice public: {{c00004a300 6} [{[8cc865ea84d9aae5 71055570106ac84c 145fbde1f9fbf698 a88a8529dbb98651 91845915201a2dbd f2b4e77f2ae89a86 fe7918aa5bc6c63a 103b67e35290d3 0 0 0 0] [8b1a857ec7175352 112c362cde004a9 af0801fd57087895 f2a1749cdf5707e8 907d94076858ca2 ebac5de8aec5b586 fa72a50840bc676d 3a1b89a78702dd 0 0 0 0]} {[2e081904fc66cfd6 ee7e1943ddce7e15 96165b18fecb9e50 fae10b4b30f70981 b950a0b0c71a407d 672c48808dca0e61 ee5e4500eb00b206 1e15b86e098a14 0 0 0 0] [f849a4f3696041a3 f5d97d00c81b5f 53423d22f3f4e45d c97bd0aedbefc36f 28b2ed5e3dd4724 9ade8b4324bd0972 9b57f9ab5d4dba1b 801ee7d3f1085 0 0 0 0]} {[13eb4c512c169ac5 1ab19e06e806a51d 6ad6511ef7af9458 1e394919ad3c3c72 3ff374113ec1dc04 4f5cfc428217b63f 2a72b13b1c1a0dfa 6a635e07bd1893 0 0 0 0] [244889c2a5e41e87 b30aab90b84d71b9 9fb6b34e28682e9f a7c23517bee9651e f19e8b6c36b00d9c 926fe66306178910 b935b6ced0104651 3300b8e197c1e 0 0 0 0]}]}
Bob private: {{c00004aa00 6} 57e9bcf2afd5445eaeb5323e59d8756ba3fc27fa0906251405a9c9ffaea9950b 504b3fddfc7ab738f1b4319677c8ac4912c9ef58d36f7cf8}
Bob public: {{c00004b100 6} [{[1646c05125c0bf33 3f7db4efd65acfad 5f0debd38e3cdd63 ef0ff19a67928b1 a57773a5b0f0ec20 b6d110e87aae33a1 adcd04ea0278036 1789c8654a7099 0 0 0 0] [1f804ba79cc60ed2 e22a6a7b52c92317 511c50900dc1ef3 799472151889fa71 abe6967355136a5f fe2193d9d38582a7 4364b58c210b991e 12526ca2448b44 0 0 0 0]} {[9f8746301f179650 6c8e7f3eaef7f7a6 b9de44992695c0a6 a1af8780d47523fe 524ceb08b727c390 df4bed0f3429cd95 4f4290bdd5ff3c72 2fdf1abde72c3d 0 0 0 0] [4b7e93cd1442494f d04c5bd5f2bed1e0 f7988432f99339da a41d276f9e534d4 1fc9df17cb1629ad adc44bbc0dd74c4b 74dae0751d24fd2e c8028280c0aed 0 0 0 0]} {[ea7a90aff4e08e78 67a734ac35911575 4f90399f14bf18a2 8b97d438c0c7ff66 5140d04e6a0cb24d b3207394be08d536 4036a85a0df12f52 20aa19e6e5a561 0 0 0 0] [c9ab47ae5f97364 a6f998aaa5d8d4ad 21a6d43917fbdaf d456de25197138c5 15ba4f89afbd68f2 3c909566afe62ebd 3ffa57e0effa5c55 4e7295359d49 0 0 0 0]}]}
true

Alice shared: 0fc2623d6135990b25da16f8b0e8c520
Bob shared: 0fc2623d6135990b25da16f8b0e8c520 
Equal: true

Conclusions

Well done to Amazon! NIST will not complete its standardization until 2024, so it’s great to see companies taking it seriously now, and making plans for the eventual phase-out of the existing methods. The downside, though, is the performance hit:

With a traditional ECDHE taking 1.2 ms, while BIKE increases this to over 25 ms, and SIKE up to over 155 ms. This overhead can be considerable, but hopefully, the research community can focus their efforts on reducing this overhead. RSA has done us so well, but its time is coming to an end. For ECC, it is still King of the Hill, but it is on a warning that its method will not be a hard problem in a quantum computing era. We must thank ECC for helping us through this period of securing the Internet, but its core method also exposes many new dangers, so we must start to migrate away from it.