Integrate SIKE with TLS key exchange. Implements support for hybrid key exchange based on SIKEp503, a post quantum, isogeny based KEM. This is a hybrid construction mixed with X25519 key agreement. Code point is 0xFE32. Cloudflare's SIDH implementation is used for testing. Key exchange can be used with TLS1.3 only. Change-Id: I3a5f38d6f7d016274e5bcfb629249664e1d983eb Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/35264 Reviewed-by: Adam Langley <alangley@gmail.com>
diff --git a/crypto/obj/obj_dat.h b/crypto/obj/obj_dat.h index 0313a08..1a9bf15 100644 --- a/crypto/obj/obj_dat.h +++ b/crypto/obj/obj_dat.h
@@ -57,7 +57,7 @@ /* This file is generated by crypto/obj/objects.go. */ -#define NUM_NID 960 +#define NUM_NID 961 static const uint8_t kObjectData[] = { /* NID_rsadsi */ @@ -8756,6 +8756,7 @@ {"KxANY", "kx-any", NID_kx_any, 0, NULL, 0}, {"AuthANY", "auth-any", NID_auth_any, 0, NULL, 0}, {"CECPQ2", "CECPQ2", NID_CECPQ2, 0, NULL, 0}, + {"CECPQ2b", "CECPQ2b", NID_CECPQ2b, 0, NULL, 0}, }; static const unsigned kNIDsInShortNameOrder[] = { @@ -8818,6 +8819,7 @@ 109 /* CAST5-ECB */, 111 /* CAST5-OFB */, 959 /* CECPQ2 */, + 960 /* CECPQ2b */, 894 /* CMAC */, 13 /* CN */, 141 /* CRLReason */, @@ -9723,6 +9725,7 @@ 179 /* CA Issuers */, 785 /* CA Repository */, 959 /* CECPQ2 */, + 960 /* CECPQ2b */, 131 /* Code Signing */, 783 /* Diffie-Hellman based MAC */, 382 /* Directory */,
diff --git a/crypto/obj/obj_mac.num b/crypto/obj/obj_mac.num index 5fa839d..f2d4e8c 100644 --- a/crypto/obj/obj_mac.num +++ b/crypto/obj/obj_mac.num
@@ -948,3 +948,4 @@ kx_any 957 auth_any 958 CECPQ2 959 +CECPQ2b 960
diff --git a/crypto/obj/objects.txt b/crypto/obj/objects.txt index 6dbb7ad..6e7ecf0 100644 --- a/crypto/obj/objects.txt +++ b/crypto/obj/objects.txt
@@ -1337,6 +1337,9 @@ # NID for CECPQ2 (no corresponding OID). : CECPQ2 +# NID for CECPQ2 (no corresponding OID). + : CECPQ2b + # See RFC 8410. 1 3 101 112 : ED25519
diff --git a/include/openssl/nid.h b/include/openssl/nid.h index 270d443..cea975a 100644 --- a/include/openssl/nid.h +++ b/include/openssl/nid.h
@@ -4237,6 +4237,9 @@ #define SN_CECPQ2 "CECPQ2" #define NID_CECPQ2 959 +#define SN_CECPQ2b "CECPQ2b" +#define NID_CECPQ2b 960 + #if defined(__cplusplus) } /* extern C */
diff --git a/include/openssl/ssl.h b/include/openssl/ssl.h index e732e3a..4586bdb 100644 --- a/include/openssl/ssl.h +++ b/include/openssl/ssl.h
@@ -2206,6 +2206,7 @@ #define SSL_CURVE_SECP521R1 25 #define SSL_CURVE_X25519 29 #define SSL_CURVE_CECPQ2 16696 +#define SSL_CURVE_CECPQ2b 65074 // SSL_get_curve_id returns the ID of the curve used by |ssl|'s most recently // completed handshake or 0 if not applicable.
diff --git a/ssl/ssl_key_share.cc b/ssl/ssl_key_share.cc index 78d2aa1..2bf177b 100644 --- a/ssl/ssl_key_share.cc +++ b/ssl/ssl_key_share.cc
@@ -31,7 +31,7 @@ #include "internal.h" #include "../crypto/internal.h" - +#include "../third_party/sike/sike.h" BSSL_NAMESPACE_BEGIN @@ -300,6 +300,87 @@ HRSS_private_key hrss_private_key_; }; +class CECPQ2bKeyShare : public SSLKeyShare { + public: + uint16_t GroupID() const override { return SSL_CURVE_CECPQ2b; } + + bool Offer(CBB *out) override { + uint8_t public_x25519[32] = {0}; + X25519_keypair(public_x25519, private_x25519_); + if (!SIKE_keypair(private_sike_, public_sike_)) { + return false; + } + + return CBB_add_bytes(out, public_x25519, sizeof(public_x25519)) && + CBB_add_bytes(out, public_sike_, sizeof(public_sike_)); + } + + bool Accept(CBB *out_public_key, Array<uint8_t> *out_secret, + uint8_t *out_alert, Span<const uint8_t> peer_key) override { + uint8_t public_x25519[32]; + uint8_t private_x25519[32]; + uint8_t sike_ciphertext[SIKEp503_CT_BYTESZ] = {0}; + + *out_alert = SSL_AD_INTERNAL_ERROR; + + if (peer_key.size() != sizeof(public_x25519) + SIKEp503_PUB_BYTESZ) { + *out_alert = SSL_AD_DECODE_ERROR; + OPENSSL_PUT_ERROR(SSL, SSL_R_BAD_ECPOINT); + return false; + } + + Array<uint8_t> secret; + if (!secret.Init(sizeof(private_x25519_) + SIKEp503_SS_BYTESZ)) { + OPENSSL_PUT_ERROR(SSL, ERR_R_MALLOC_FAILURE); + return false; + } + + X25519_keypair(public_x25519, private_x25519); + if (!X25519(secret.data(), private_x25519, peer_key.data())) { + *out_alert = SSL_AD_DECODE_ERROR; + OPENSSL_PUT_ERROR(SSL, SSL_R_BAD_ECPOINT); + return false; + } + + SIKE_encaps(secret.data() + sizeof(private_x25519_), sike_ciphertext, + peer_key.data() + sizeof(public_x25519)); + *out_secret = std::move(secret); + + return CBB_add_bytes(out_public_key, public_x25519, + sizeof(public_x25519)) && + CBB_add_bytes(out_public_key, sike_ciphertext, + sizeof(sike_ciphertext)); + } + + bool Finish(Array<uint8_t> *out_secret, uint8_t *out_alert, + Span<const uint8_t> peer_key) override { + *out_alert = SSL_AD_INTERNAL_ERROR; + + Array<uint8_t> secret; + if (!secret.Init(sizeof(private_x25519_) + SIKEp503_SS_BYTESZ)) { + OPENSSL_PUT_ERROR(SSL, ERR_R_MALLOC_FAILURE); + return false; + } + + if (peer_key.size() != 32 + SIKEp503_CT_BYTESZ || + !X25519(secret.data(), private_x25519_, peer_key.data())) { + *out_alert = SSL_AD_DECODE_ERROR; + OPENSSL_PUT_ERROR(SSL, SSL_R_BAD_ECPOINT); + return false; + } + + SIKE_decaps(secret.data() + sizeof(private_x25519_), peer_key.data() + 32, + public_sike_, private_sike_); + *out_secret = std::move(secret); + return true; + } + + private: + uint8_t private_x25519_[32]; + uint8_t private_sike_[SIKEp503_PRV_BYTESZ]; + uint8_t public_sike_[SIKEp503_PUB_BYTESZ]; +}; + CONSTEXPR_ARRAY NamedGroup kNamedGroups[] = { {NID_secp224r1, SSL_CURVE_SECP224R1, "P-224", "secp224r1"}, {NID_X9_62_prime256v1, SSL_CURVE_SECP256R1, "P-256", "prime256v1"}, @@ -307,6 +388,7 @@ {NID_secp521r1, SSL_CURVE_SECP521R1, "P-521", "secp521r1"}, {NID_X25519, SSL_CURVE_X25519, "X25519", "x25519"}, {NID_CECPQ2, SSL_CURVE_CECPQ2, "CECPQ2", "CECPQ2"}, + {NID_CECPQ2b, SSL_CURVE_CECPQ2b, "CECPQ2b", "CECPQ2b"}, }; } // namespace @@ -333,6 +415,8 @@ return UniquePtr<SSLKeyShare>(New<X25519KeyShare>()); case SSL_CURVE_CECPQ2: return UniquePtr<SSLKeyShare>(New<CECPQ2KeyShare>()); + case SSL_CURVE_CECPQ2b: + return UniquePtr<SSLKeyShare>(New<CECPQ2bKeyShare>()); default: return nullptr; }
diff --git a/ssl/t1_lib.cc b/ssl/t1_lib.cc index f79ce9b..3388556 100644 --- a/ssl/t1_lib.cc +++ b/ssl/t1_lib.cc
@@ -199,6 +199,10 @@ return true; } +static bool is_post_quantum_group(uint16_t id) { + return id == SSL_CURVE_CECPQ2 || id == SSL_CURVE_CECPQ2b; +} + bool ssl_client_hello_init(const SSL *ssl, SSL_CLIENT_HELLO *out, const SSLMessage &msg) { OPENSSL_memset(out, 0, sizeof(*out)); @@ -325,10 +329,10 @@ for (uint16_t pref_group : pref) { for (uint16_t supp_group : supp) { if (pref_group == supp_group && - // CECPQ2 doesn't fit in the u8-length-prefixed ECPoint field in TLS - // 1.2 and below. + // CECPQ2(b) doesn't fit in the u8-length-prefixed ECPoint field in + // TLS 1.2 and below. (ssl_protocol_version(ssl) >= TLS1_3_VERSION || - pref_group != SSL_CURVE_CECPQ2)) { + !is_post_quantum_group(pref_group))) { *out_group_id = pref_group; return true; } @@ -390,9 +394,9 @@ } bool tls1_check_group_id(const SSL_HANDSHAKE *hs, uint16_t group_id) { - if (group_id == SSL_CURVE_CECPQ2 && + if (is_post_quantum_group(group_id) && ssl_protocol_version(hs->ssl) < TLS1_3_VERSION) { - // CECPQ2 requires TLS 1.3. + // CECPQ2(b) requires TLS 1.3. return false; } @@ -2228,8 +2232,8 @@ group_id = groups[0]; - if (group_id == SSL_CURVE_CECPQ2 && groups.size() >= 2) { - // CECPQ2 is not sent as the only initial key share. We'll include the + if (is_post_quantum_group(group_id) && groups.size() >= 2) { + // CECPQ2(b) is not sent as the only initial key share. We'll include the // 2nd preference group too to avoid round-trips. second_group_id = groups[1]; assert(second_group_id != group_id); @@ -2466,7 +2470,7 @@ } for (uint16_t group : tls1_get_grouplist(hs)) { - if (group == SSL_CURVE_CECPQ2 && + if (is_post_quantum_group(group) && hs->max_version < TLS1_3_VERSION) { continue; }
diff --git a/ssl/test/runner/common.go b/ssl/test/runner/common.go index bbcacf5..1729289 100644 --- a/ssl/test/runner/common.go +++ b/ssl/test/runner/common.go
@@ -144,12 +144,13 @@ type CurveID uint16 const ( - CurveP224 CurveID = 21 - CurveP256 CurveID = 23 - CurveP384 CurveID = 24 - CurveP521 CurveID = 25 - CurveX25519 CurveID = 29 - CurveCECPQ2 CurveID = 16696 + CurveP224 CurveID = 21 + CurveP256 CurveID = 23 + CurveP384 CurveID = 24 + CurveP521 CurveID = 25 + CurveX25519 CurveID = 29 + CurveCECPQ2 CurveID = 16696 + CurveCECPQ2b CurveID = 65074 ) // TLS Elliptic Curve Point Formats @@ -1728,7 +1729,7 @@ return ret } -var defaultCurvePreferences = []CurveID{CurveCECPQ2, CurveX25519, CurveP256, CurveP384, CurveP521} +var defaultCurvePreferences = []CurveID{CurveCECPQ2b, CurveCECPQ2, CurveX25519, CurveP256, CurveP384, CurveP521} func (c *Config) curvePreferences() []CurveID { if c == nil || len(c.CurvePreferences) == 0 {
diff --git a/ssl/test/runner/handshake_server.go b/ssl/test/runner/handshake_server.go index d2ef9b4..2dc7032 100644 --- a/ssl/test/runner/handshake_server.go +++ b/ssl/test/runner/handshake_server.go
@@ -210,8 +210,8 @@ if config.Bugs.FailIfCECPQ2Offered { for _, offeredCurve := range hs.clientHello.supportedCurves { - if offeredCurve == CurveCECPQ2 { - return errors.New("tls: CECPQ2 was offered") + if isPqGroup(offeredCurve) { + return errors.New("tls: CECPQ2 or CECPQ2b was offered") } } } @@ -1232,8 +1232,8 @@ preferredCurves := config.curvePreferences() Curves: for _, curve := range hs.clientHello.supportedCurves { - if curve == CurveCECPQ2 && c.vers < VersionTLS13 { - // CECPQ2 is TLS 1.3-only. + if isPqGroup(curve) && c.vers < VersionTLS13 { + // CECPQ2 and CECPQ2b is TLS 1.3-only. continue }
diff --git a/ssl/test/runner/key_agreement.go b/ssl/test/runner/key_agreement.go index 13e78bc..0d6405f 100644 --- a/ssl/test/runner/key_agreement.go +++ b/ssl/test/runner/key_agreement.go
@@ -19,6 +19,7 @@ "boringssl.googlesource.com/boringssl/ssl/test/runner/curve25519" "boringssl.googlesource.com/boringssl/ssl/test/runner/ed25519" "boringssl.googlesource.com/boringssl/ssl/test/runner/hrss" + "boringssl.googlesource.com/boringssl/ssl/test/runner/sike" ) type keyType int @@ -433,6 +434,98 @@ return preMasterSecret, nil } +// cecpq2BCurve implements CECPQ2b, which is SIKEp503 combined with X25519. +type cecpq2BCurve struct { + // Both public key and shared secret size + x25519PrivateKey [32]byte + sikePrivateKey *sike.PrivateKey +} + +func (e *cecpq2BCurve) offer(rand io.Reader) (publicKey []byte, err error) { + if _, err = io.ReadFull(rand, e.x25519PrivateKey[:]); err != nil { + return nil, err + } + + var x25519Public [32]byte + curve25519.ScalarBaseMult(&x25519Public, &e.x25519PrivateKey) + + e.sikePrivateKey = sike.NewPrivateKey(sike.KeyVariant_SIKE) + if err = e.sikePrivateKey.Generate(rand); err != nil { + return nil, err + } + + sikePublic := e.sikePrivateKey.GeneratePublicKey().Export() + var ret []byte + ret = append(ret, x25519Public[:]...) + ret = append(ret, sikePublic...) + return ret, nil +} + +func (e *cecpq2BCurve) accept(rand io.Reader, peerKey []byte) (publicKey []byte, preMasterSecret []byte, err error) { + if len(peerKey) != 32+sike.Params.PublicKeySize { + return nil, nil, errors.New("tls: bad length CECPQ2b offer") + } + + if _, err = io.ReadFull(rand, e.x25519PrivateKey[:]); err != nil { + return nil, nil, err + } + + var x25519Shared, x25519PeerKey, x25519Public [32]byte + copy(x25519PeerKey[:], peerKey) + curve25519.ScalarBaseMult(&x25519Public, &e.x25519PrivateKey) + curve25519.ScalarMult(&x25519Shared, &e.x25519PrivateKey, &x25519PeerKey) + + // Per RFC 7748, reject the all-zero value in constant time. + var zeros [32]byte + if subtle.ConstantTimeCompare(zeros[:], x25519Shared[:]) == 1 { + return nil, nil, errors.New("tls: X25519 value with wrong order") + } + + var sikePubKey = sike.NewPublicKey(sike.KeyVariant_SIKE) + if err = sikePubKey.Import(peerKey[32:]); err != nil { + // should never happen as size was already checked + return nil, nil, errors.New("tls: implementation error") + } + sikeCiphertext, sikeShared, err := sike.Encapsulate(rand, sikePubKey) + if err != nil { + return nil, nil, err + } + + publicKey = append(publicKey, x25519Public[:]...) + publicKey = append(publicKey, sikeCiphertext...) + preMasterSecret = append(preMasterSecret, x25519Shared[:]...) + preMasterSecret = append(preMasterSecret, sikeShared...) + + return publicKey, preMasterSecret, nil +} + +func (e *cecpq2BCurve) finish(peerKey []byte) (preMasterSecret []byte, err error) { + if len(peerKey) != 32+(sike.Params.PublicKeySize+sike.Params.MsgLen) { + return nil, errors.New("tls: bad length CECPQ2b reply") + } + + var x25519Shared, x25519PeerKey [32]byte + copy(x25519PeerKey[:], peerKey) + curve25519.ScalarMult(&x25519Shared, &e.x25519PrivateKey, &x25519PeerKey) + + // Per RFC 7748, reject the all-zero value in constant time. + var zeros [32]byte + if subtle.ConstantTimeCompare(zeros[:], x25519Shared[:]) == 1 { + return nil, errors.New("tls: X25519 value with wrong order") + } + + var sikePubKey = e.sikePrivateKey.GeneratePublicKey() + sikeShared, err := sike.Decapsulate(e.sikePrivateKey, sikePubKey, peerKey[32:]) + if err != nil { + return nil, errors.New("tls: invalid SIKE ciphertext") + } + + preMasterSecret = append(preMasterSecret, x25519Shared[:]...) + preMasterSecret = append(preMasterSecret, sikeShared...) + + return preMasterSecret, nil +} + func curveForCurveID(id CurveID, config *Config) (ecdhCurve, bool) { switch id { case CurveP224: @@ -447,6 +540,8 @@ return &x25519ECDHCurve{setHighBit: config.Bugs.SetX25519HighBit}, true case CurveCECPQ2: return &cecpq2Curve{}, true + case CurveCECPQ2b: + return &cecpq2BCurve{}, true default: return nil, false } @@ -594,8 +689,8 @@ NextCandidate: for _, candidate := range preferredCurves { - if candidate == CurveCECPQ2 && version < VersionTLS13 { - // CECPQ2 is TLS 1.3-only. + if isPqGroup(candidate) && version < VersionTLS13 { + // CECPQ2 and CECPQ2b is TLS 1.3-only. continue }
diff --git a/ssl/test/runner/runner.go b/ssl/test/runner/runner.go index b792e2d..7dd0def 100644 --- a/ssl/test/runner/runner.go +++ b/ssl/test/runner/runner.go
@@ -10588,14 +10588,19 @@ {"P-521", CurveP521}, {"X25519", CurveX25519}, {"CECPQ2", CurveCECPQ2}, + {"CECPQ2b", CurveCECPQ2b}, } const bogusCurve = 0x1234 +func isPqGroup(r CurveID) bool { + return r == CurveCECPQ2 || r == CurveCECPQ2b +} + func addCurveTests() { for _, curve := range testCurves { for _, ver := range tlsVersions { - if curve.id == CurveCECPQ2 && ver.version < VersionTLS13 { + if isPqGroup(curve.id) && ver.version < VersionTLS13 { continue } @@ -10637,7 +10642,7 @@ expectedCurveID: curve.id, }) - if curve.id != CurveX25519 && curve.id != CurveCECPQ2 { + if curve.id != CurveX25519 && !isPqGroup(curve.id) { testCases = append(testCases, testCase{ name: "CurveTest-Client-Compressed-" + suffix, config: Config{ @@ -11062,6 +11067,21 @@ }, }) + // CECPQ2b should not be offered by a TLS < 1.3 client. + testCases = append(testCases, testCase{ + name: "CECPQ2bNotInTLS12", + config: Config{ + Bugs: ProtocolBugs{ + FailIfCECPQ2Offered: true, + }, + }, + flags: []string{ + "-max-version", strconv.Itoa(VersionTLS12), + "-curves", strconv.Itoa(int(CurveCECPQ2b)), + "-curves", strconv.Itoa(int(CurveX25519)), + }, + }) + // CECPQ2 should not crash a TLS < 1.3 client if the server mistakenly // selects it. testCases = append(testCases, testCase{ @@ -11080,6 +11100,24 @@ expectedError: ":WRONG_CURVE:", }) + // CECPQ2b should not crash a TLS < 1.3 client if the server mistakenly + // selects it. + testCases = append(testCases, testCase{ + name: "CECPQ2bNotAcceptedByTLS12Client", + config: Config{ + Bugs: ProtocolBugs{ + SendCurve: CurveCECPQ2b, + }, + }, + flags: []string{ + "-max-version", strconv.Itoa(VersionTLS12), + "-curves", strconv.Itoa(int(CurveCECPQ2b)), + "-curves", strconv.Itoa(int(CurveX25519)), + }, + shouldFail: true, + expectedError: ":WRONG_CURVE:", + }) + // CECPQ2 should not be offered by default as a client. testCases = append(testCases, testCase{ name: "CECPQ2NotEnabledByDefaultInClients", @@ -11091,6 +11129,17 @@ }, }) + // CECPQ2b should not be offered by default as a client. + testCases = append(testCases, testCase{ + name: "CECPQ2bNotEnabledByDefaultInClients", + config: Config{ + MinVersion: VersionTLS13, + Bugs: ProtocolBugs{ + FailIfCECPQ2Offered: true, + }, + }, + }) + // If CECPQ2 is offered, both X25519 and CECPQ2 should have a key-share. testCases = append(testCases, testCase{ name: "NotJustCECPQ2KeyShare", @@ -11123,6 +11172,38 @@ }, }) + // If CECPQ2b is offered, both X25519 and CECPQ2b should have a key-share. + testCases = append(testCases, testCase{ + name: "NotJustCECPQ2bKeyShare", + config: Config{ + MinVersion: VersionTLS13, + Bugs: ProtocolBugs{ + ExpectedKeyShares: []CurveID{CurveCECPQ2b, CurveX25519}, + }, + }, + flags: []string{ + "-curves", strconv.Itoa(int(CurveCECPQ2b)), + "-curves", strconv.Itoa(int(CurveX25519)), + "-expect-curve-id", strconv.Itoa(int(CurveCECPQ2b)), + }, + }) + + // ... but only if CECPQ2b is listed first. + testCases = append(testCases, testCase{ + name: "CECPQ2bKeyShareNotIncludedSecond", + config: Config{ + MinVersion: VersionTLS13, + Bugs: ProtocolBugs{ + ExpectedKeyShares: []CurveID{CurveX25519}, + }, + }, + flags: []string{ + "-curves", strconv.Itoa(int(CurveX25519)), + "-curves", strconv.Itoa(int(CurveCECPQ2b)), + "-expect-curve-id", strconv.Itoa(int(CurveX25519)), + }, + }) + // If CECPQ2 is the only configured curve, the key share is sent. testCases = append(testCases, testCase{ name: "JustConfiguringCECPQ2Works", @@ -11138,6 +11219,21 @@ }, }) + // If CECPQ2b is the only configured curve, the key share is sent. + testCases = append(testCases, testCase{ + name: "JustConfiguringCECPQ2bWorks", + config: Config{ + MinVersion: VersionTLS13, + Bugs: ProtocolBugs{ + ExpectedKeyShares: []CurveID{CurveCECPQ2b}, + }, + }, + flags: []string{ + "-curves", strconv.Itoa(int(CurveCECPQ2b)), + "-expect-curve-id", strconv.Itoa(int(CurveCECPQ2b)), + }, + }) + // As a server, CECPQ2 is not yet supported by default. testCases = append(testCases, testCase{ testType: serverTest, @@ -11152,6 +11248,21 @@ "-expect-curve-id", strconv.Itoa(int(CurveX25519)), }, }) + + // As a server, CECPQ2b is not yet supported by default. + testCases = append(testCases, testCase{ + testType: serverTest, + name: "CECPQ2bNotEnabledByDefaultForAServer", + config: Config{ + MinVersion: VersionTLS13, + CurvePreferences: []CurveID{CurveCECPQ2b, CurveX25519}, + DefaultCurves: []CurveID{CurveCECPQ2b}, + }, + flags: []string{ + "-server-preference", + "-expect-curve-id", strconv.Itoa(int(CurveX25519)), + }, + }) } func addTLS13RecordTests() { @@ -14076,6 +14187,22 @@ "-curves", strconv.Itoa(int(CurveCECPQ2)), }, }) + + // CECPQ2b prefers 256-bit ciphers but will use AES-128 if there's nothing else. + testCases = append(testCases, testCase{ + testType: serverTest, + name: "TLS13-CipherPreference-CECPQ2b-AES128Only", + config: Config{ + MaxVersion: VersionTLS13, + CipherSuites: []uint16{ + TLS_AES_128_GCM_SHA256, + }, + }, + flags: []string{ + "-curves", strconv.Itoa(int(CurveCECPQ2b)), + }, + }) + // When a 256-bit cipher is offered, even if not in first place, it should be // picked. testCases = append(testCases, testCase{ @@ -14110,6 +14237,40 @@ expectedCipher: TLS_AES_128_GCM_SHA256, }) + // When a 256-bit cipher is offered, even if not in first place, it should be + // picked. + testCases = append(testCases, testCase{ + testType: serverTest, + name: "TLS13-CipherPreference-CECPQ2b-AES256Preferred", + config: Config{ + MaxVersion: VersionTLS13, + CipherSuites: []uint16{ + TLS_AES_128_GCM_SHA256, + TLS_AES_256_GCM_SHA384, + }, + }, + flags: []string{ + "-curves", strconv.Itoa(int(CurveCECPQ2b)), + }, + expectedCipher: TLS_AES_256_GCM_SHA384, + }) + // ... but when CECPQ2b isn't being used, the client's preference controls. + testCases = append(testCases, testCase{ + testType: serverTest, + name: "TLS13-CipherPreference-CECPQ2b-AES128PreferredOtherwise", + config: Config{ + MaxVersion: VersionTLS13, + CipherSuites: []uint16{ + TLS_AES_128_GCM_SHA256, + TLS_AES_256_GCM_SHA384, + }, + }, + flags: []string{ + "-curves", strconv.Itoa(int(CurveX25519)), + }, + expectedCipher: TLS_AES_128_GCM_SHA256, + }) + // Test that CECPQ2 continues to honor AES vs ChaCha20 logic. testCases = append(testCases, testCase{ testType: serverTest, @@ -14145,6 +14306,42 @@ "-expect-cipher-no-aes", strconv.Itoa(int(TLS_CHACHA20_POLY1305_SHA256)), }, }) + + // Test that CECPQ2b continues to honor AES vs ChaCha20 logic. + testCases = append(testCases, testCase{ + testType: serverTest, + name: "TLS13-CipherPreference-CECPQ2b-AES128-ChaCha20-AES256", + config: Config{ + MaxVersion: VersionTLS13, + CipherSuites: []uint16{ + TLS_AES_128_GCM_SHA256, + TLS_CHACHA20_POLY1305_SHA256, + TLS_AES_256_GCM_SHA384, + }, + }, + flags: []string{ + "-curves", strconv.Itoa(int(CurveCECPQ2b)), + "-expect-cipher-aes", strconv.Itoa(int(TLS_CHACHA20_POLY1305_SHA256)), + "-expect-cipher-no-aes", strconv.Itoa(int(TLS_CHACHA20_POLY1305_SHA256)), + }, + }) + testCases = append(testCases, testCase{ + testType: serverTest, + name: "TLS13-CipherPreference-CECPQ2b-AES128-AES256-ChaCha20", + config: Config{ + MaxVersion: VersionTLS13, + CipherSuites: []uint16{ + TLS_AES_128_GCM_SHA256, + TLS_AES_256_GCM_SHA384, + TLS_CHACHA20_POLY1305_SHA256, + }, + }, + flags: []string{ + "-curves", strconv.Itoa(int(CurveCECPQ2b)), + "-expect-cipher-aes", strconv.Itoa(int(TLS_AES_256_GCM_SHA384)), + "-expect-cipher-no-aes", strconv.Itoa(int(TLS_CHACHA20_POLY1305_SHA256)), + }, + }) } func addPeekTests() {
diff --git a/ssl/test/runner/sike/arith.go b/ssl/test/runner/sike/arith.go new file mode 100644 index 0000000..0b9b5c0 --- /dev/null +++ b/ssl/test/runner/sike/arith.go
@@ -0,0 +1,430 @@ +// Copyright (c) 2019, Cloudflare Inc. +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY +// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION +// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN +// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + +package sike + +// Helpers + +// uint128 representation +type uint128 struct { + H, L uint64 +} + +func addc64(cin, a, b uint64) (ret, cout uint64) { + ret = cin + ret = ret + a + if ret < a { + cout = 1 + } + ret = ret + b + if ret < b { + cout = 1 + } + + return +} + +func subc64(bIn, a, b uint64) (ret, bOut uint64) { + tmp := a - bIn + if tmp > a { + bOut = 1 + } + ret = tmp - b + if ret > tmp { + bOut = 1 + } + return +} + +func mul64(a, b uint64) (res uint128) { + var al, bl, ah, bh, albl, albh, ahbl, ahbh uint64 + var res1, res2, res3 uint64 + var carry, maskL, maskH, temp uint64 + + maskL = (^maskL) >> 32 + maskH = ^maskL + + al = a & maskL + ah = a >> 32 + bl = b & maskL + bh = b >> 32 + + albl = al * bl + albh = al * bh + ahbl = ah * bl + ahbh = ah * bh + res.L = albl & maskL + + res1 = albl >> 32 + res2 = ahbl & maskL + res3 = albh & maskL + temp = res1 + res2 + res3 + carry = temp >> 32 + res.L ^= temp << 32 + + res1 = ahbl >> 32 + res2 = albh >> 32 + res3 = ahbh & maskL + temp = res1 + res2 + res3 + carry + res.H = temp & maskL + carry = temp & maskH + res.H ^= (ahbh & maskH) + carry + return +} + +// Fp implementation + +// Compute z = x + y (mod 2*p). +func fpAddRdc(z, x, y *Fp) { + var carry uint64 + + // z=x+y % p503 + for i := 0; i < FP_WORDS; i++ { + z[i], carry = addc64(carry, x[i], y[i]) + } + + // z = z - p503x2 + carry = 0 + for i := 0; i < FP_WORDS; i++ { + z[i], carry = subc64(carry, z[i], p503x2[i]) + } + + // if z<0 add p503x2 back + mask := uint64(0 - carry) + carry = 0 + for i := 0; i < FP_WORDS; i++ { + z[i], carry = addc64(carry, z[i], p503x2[i]&mask) + } +} + +// Compute z = x - y (mod 2*p). +func fpSubRdc(z, x, y *Fp) { + var borrow uint64 + + // z = z - p503x2 + for i := 0; i < FP_WORDS; i++ { + z[i], borrow = subc64(borrow, x[i], y[i]) + } + + // if z<0 add p503x2 back + mask := uint64(0 - borrow) + borrow = 0 + for i := 0; i < FP_WORDS; i++ { + z[i], borrow = addc64(borrow, z[i], p503x2[i]&mask) + } +} + +// Reduce a field element in [0, 2*p) to one in [0,p). +func fpRdcP(x *Fp) { + var borrow, mask uint64 + for i := 0; i < FP_WORDS; i++ { + x[i], borrow = subc64(borrow, x[i], p503[i]) + } + + // Sets all bits if borrow = 1 + mask = 0 - borrow + borrow = 0 + for i := 0; i < FP_WORDS; i++ { + x[i], borrow = addc64(borrow, x[i], p503[i]&mask) + } +} + +// Implementation doesn't actually depend on a prime field. +func fpSwapCond(x, y *Fp, mask uint8) { + if mask != 0 { + var tmp Fp + copy(tmp[:], y[:]) + copy(y[:], x[:]) + copy(x[:], tmp[:]) + } +} + +// Compute z = x * y. +func fpMul(z *FpX2, x, y *Fp) { + var u, v, t uint64 + var carry uint64 + var uv uint128 + + for i := uint64(0); i < FP_WORDS; i++ { + for j := uint64(0); j <= i; j++ { + uv = mul64(x[j], y[i-j]) + v, carry = addc64(0, uv.L, v) + u, carry = addc64(carry, uv.H, u) + t += carry + } + z[i] = v + v = u + u = t + t = 0 + } + + for i := FP_WORDS; i < (2*FP_WORDS)-1; i++ { + for j := i - FP_WORDS + 1; j < FP_WORDS; j++ { + uv = mul64(x[j], y[i-j]) + v, carry = addc64(0, uv.L, v) + u, carry = addc64(carry, uv.H, u) + t += carry + } + z[i] = v + v = u + u = t + t = 0 + } + z[2*FP_WORDS-1] = v +} + +// Perform Montgomery reduction: set z = x R^{-1} (mod 2*p) +// with R=2^512. Destroys the input value. +func fpMontRdc(z *Fp, x *FpX2) { + var carry, t, u, v uint64 + var uv uint128 + var count int + + count = 3 // number of 0 digits in the least significat part of p503 + 1 + + for i := 0; i < FP_WORDS; i++ { + for j := 0; j < i; j++ { + if j < (i - count + 1) { + uv = mul64(z[j], p503p1[i-j]) + v, carry = addc64(0, uv.L, v) + u, carry = addc64(carry, uv.H, u) + t += carry + } + } + v, carry = addc64(0, v, x[i]) + u, carry = addc64(carry, u, 0) + t += carry + + z[i] = v + v = u + u = t + t = 0 + } + + for i := FP_WORDS; i < 2*FP_WORDS-1; i++ { + if count > 0 { + count-- + } + for j := i - FP_WORDS + 1; j < FP_WORDS; j++ { + if j < (FP_WORDS - count) { + uv = mul64(z[j], p503p1[i-j]) + v, carry = addc64(0, uv.L, v) + u, carry = addc64(carry, uv.H, u) + t += carry + } + } + v, carry = addc64(0, v, x[i]) + u, carry = addc64(carry, u, 0) + + t += carry + z[i-FP_WORDS] = v + v = u + u = t + t = 0 + } + v, carry = addc64(0, v, x[2*FP_WORDS-1]) + z[FP_WORDS-1] = v +} + +// Compute z = x + y, without reducing mod p. +func fp2Add(z, x, y *FpX2) { + var carry uint64 + for i := 0; i < 2*FP_WORDS; i++ { + z[i], carry = addc64(carry, x[i], y[i]) + } +} + +// Compute z = x - y, without reducing mod p. +func fp2Sub(z, x, y *FpX2) { + var borrow, mask uint64 + for i := 0; i < 2*FP_WORDS; i++ { + z[i], borrow = subc64(borrow, x[i], y[i]) + } + + // Sets all bits if borrow = 1 + mask = 0 - borrow + borrow = 0 + for i := FP_WORDS; i < 2*FP_WORDS; i++ { + z[i], borrow = addc64(borrow, z[i], p503[i-FP_WORDS]&mask) + } +} + +// Montgomery multiplication. Input values must be already +// in Montgomery domain. +func fpMulRdc(dest, lhs, rhs *Fp) { + a := lhs // = a*R + b := rhs // = b*R + + var ab FpX2 + fpMul(&ab, a, b) // = a*b*R*R + fpMontRdc(dest, &ab) // = a*b*R mod p +} + +// Set dest = x^((p-3)/4). If x is square, this is 1/sqrt(x). +// Uses variation of sliding-window algorithm from with window size +// of 5 and least to most significant bit sliding (left-to-right) +// See HAC 14.85 for general description. +// +// Allowed to overlap x with dest. +// All values in Montgomery domains +func p34(dest, x *Fp) { + + // Set dest = x^(2^k), for k >= 1, by repeated squarings. + pow2k := func(dest, x *Fp, k uint8) { + fpMulRdc(dest, x, x) + for i := uint8(1); i < k; i++ { + fpMulRdc(dest, dest, dest) + } + } + // Sliding-window strategy computed with etc/scripts/sliding_window_strat_calc.py + // + // This performs sum(powStrategy) + 1 squarings and len(lookup) + len(mulStrategy) + // multiplications. + powStrategy := []uint8{1, 12, 5, 5, 2, 7, 11, 3, 8, 4, 11, 4, 7, 5, 6, 3, 7, 5, 7, 2, 12, 5, 6, 4, 6, 8, 6, 4, 7, 5, 5, 8, 5, 8, 5, 5, 8, 9, 3, 6, 2, 10, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 3} + mulStrategy := []uint8{0, 12, 11, 10, 0, 1, 8, 3, 7, 1, 8, 3, 6, 7, 14, 2, 14, 14, 9, 0, 13, 9, 15, 5, 12, 7, 13, 7, 15, 6, 7, 9, 0, 5, 7, 6, 8, 8, 3, 7, 0, 10, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 3} + + // Precompute lookup table of odd multiples of x for window + // size k=5. + lookup := [16]Fp{} + var xx Fp + fpMulRdc(&xx, x, x) + lookup[0] = *x + for i := 1; i < 16; i++ { + fpMulRdc(&lookup[i], &lookup[i-1], &xx) + } + + // Now lookup = {x, x^3, x^5, ... } + // so that lookup[i] = x^{2*i + 1} + // so that lookup[k/2] = x^k, for odd k + *dest = lookup[mulStrategy[0]] + for i := uint8(1); i < uint8(len(powStrategy)); i++ { + pow2k(dest, dest, powStrategy[i]) + fpMulRdc(dest, dest, &lookup[mulStrategy[i]]) + } +} + +func add(dest, lhs, rhs *Fp2) { + fpAddRdc(&dest.A, &lhs.A, &rhs.A) + fpAddRdc(&dest.B, &lhs.B, &rhs.B) +} + +func sub(dest, lhs, rhs *Fp2) { + fpSubRdc(&dest.A, &lhs.A, &rhs.A) + fpSubRdc(&dest.B, &lhs.B, &rhs.B) +} + +func mul(dest, lhs, rhs *Fp2) { + // Let (a,b,c,d) = (lhs.a,lhs.b,rhs.a,rhs.b). + a := &lhs.A + b := &lhs.B + c := &rhs.A + d := &rhs.B + + // We want to compute + // + // (a + bi)*(c + di) = (a*c - b*d) + (a*d + b*c)i + // + // Use Karatsuba's trick: note that + // + // (b - a)*(c - d) = (b*c + a*d) - a*c - b*d + // + // so (a*d + b*c) = (b-a)*(c-d) + a*c + b*d. + + var ac, bd FpX2 + fpMul(&ac, a, c) // = a*c*R*R + fpMul(&bd, b, d) // = b*d*R*R + + var b_minus_a, c_minus_d Fp + fpSubRdc(&b_minus_a, b, a) // = (b-a)*R + fpSubRdc(&c_minus_d, c, d) // = (c-d)*R + + var ad_plus_bc FpX2 + fpMul(&ad_plus_bc, &b_minus_a, &c_minus_d) // = (b-a)*(c-d)*R*R + fp2Add(&ad_plus_bc, &ad_plus_bc, &ac) // = ((b-a)*(c-d) + a*c)*R*R + fp2Add(&ad_plus_bc, &ad_plus_bc, &bd) // = ((b-a)*(c-d) + a*c + b*d)*R*R + + fpMontRdc(&dest.B, &ad_plus_bc) // = (a*d + b*c)*R mod p + + var ac_minus_bd FpX2 + fp2Sub(&ac_minus_bd, &ac, &bd) // = (a*c - b*d)*R*R + fpMontRdc(&dest.A, &ac_minus_bd) // = (a*c - b*d)*R mod p +} + +func inv(dest, x *Fp2) { + var a2PlusB2 Fp + var asq, bsq FpX2 + var ac FpX2 + var minusB Fp + var minusBC FpX2 + + a := &x.A + b := &x.B + + // We want to compute + // + // 1 1 (a - bi) (a - bi) + // -------- = -------- -------- = ----------- + // (a + bi) (a + bi) (a - bi) (a^2 + b^2) + // + // Letting c = 1/(a^2 + b^2), this is + // + // 1/(a+bi) = a*c - b*ci. + + fpMul(&asq, a, a) // = a*a*R*R + fpMul(&bsq, b, b) // = b*b*R*R + fp2Add(&asq, &asq, &bsq) // = (a^2 + b^2)*R*R + fpMontRdc(&a2PlusB2, &asq) // = (a^2 + b^2)*R mod p + // Now a2PlusB2 = a^2 + b^2 + + inv := a2PlusB2 + fpMulRdc(&inv, &a2PlusB2, &a2PlusB2) + p34(&inv, &inv) + fpMulRdc(&inv, &inv, &inv) + fpMulRdc(&inv, &inv, &a2PlusB2) + + fpMul(&ac, a, &inv) + fpMontRdc(&dest.A, &ac) + + fpSubRdc(&minusB, &minusB, b) + fpMul(&minusBC, &minusB, &inv) + fpMontRdc(&dest.B, &minusBC) +} + +func sqr(dest, x *Fp2) { + var a2, aPlusB, aMinusB Fp + var a2MinB2, ab2 FpX2 + + a := &x.A + b := &x.B + + // (a + bi)*(a + bi) = (a^2 - b^2) + 2abi. + fpAddRdc(&a2, a, a) // = a*R + a*R = 2*a*R + fpAddRdc(&aPlusB, a, b) // = a*R + b*R = (a+b)*R + fpSubRdc(&aMinusB, a, b) // = a*R - b*R = (a-b)*R + fpMul(&a2MinB2, &aPlusB, &aMinusB) // = (a+b)*(a-b)*R*R = (a^2 - b^2)*R*R + fpMul(&ab2, &a2, b) // = 2*a*b*R*R + fpMontRdc(&dest.A, &a2MinB2) // = (a^2 - b^2)*R mod p + fpMontRdc(&dest.B, &ab2) // = 2*a*b*R mod p +} + +// In case choice == 1, performs following swap in constant time: +// xPx <-> xQx +// xPz <-> xQz +// Otherwise returns xPx, xPz, xQx, xQz unchanged +func condSwap(xPx, xPz, xQx, xQz *Fp2, choice uint8) { + fpSwapCond(&xPx.A, &xQx.A, choice) + fpSwapCond(&xPx.B, &xQx.B, choice) + fpSwapCond(&xPz.A, &xQz.A, choice) + fpSwapCond(&xPz.B, &xQz.B, choice) +}
diff --git a/ssl/test/runner/sike/consts.go b/ssl/test/runner/sike/consts.go new file mode 100644 index 0000000..251047a --- /dev/null +++ b/ssl/test/runner/sike/consts.go
@@ -0,0 +1,301 @@ +// Copyright (c) 2019, Cloudflare Inc. +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY +// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION +// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN +// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + +package sike + +// I keep it bool in order to be able to apply logical NOT +type KeyVariant uint + +// Representation of an element of the base field F_p. +// +// No particular meaning is assigned to the representation -- it could represent +// an element in Montgomery form, or not. Tracking the meaning of the field +// element is left to higher types. +type Fp [FP_WORDS]uint64 + +// Represents an intermediate product of two elements of the base field F_p. +type FpX2 [2 * FP_WORDS]uint64 + +// Represents an element of the extended field Fp^2 = Fp(x+i) +type Fp2 struct { + A Fp + B Fp +} + +type DomainParams struct { + // P, Q and R=P-Q base points + Affine_P, Affine_Q, Affine_R Fp2 + // Size of a compuatation strategy for x-torsion group + IsogenyStrategy []uint32 + // Max size of secret key for x-torsion group + SecretBitLen uint + // Max size of secret key for x-torsion group + SecretByteLen uint +} + +type SidhParams struct { + Id uint8 + // Bytelen of P + Bytelen int + // The public key size, in bytes. + PublicKeySize int + // The shared secret size, in bytes. + SharedSecretSize int + // 2- and 3-torsion group parameter definitions + A, B DomainParams + // Precomputed identity element in the Fp2 in Montgomery domain + OneFp2 Fp2 + // Precomputed 1/2 in the Fp2 in Montgomery domain + HalfFp2 Fp2 + // Length of SIKE secret message. Must be one of {24,32,40}, + // depending on size of prime field used (see [SIKE], 1.4 and 5.1) + MsgLen int + // Length of SIKE ephemeral KEM key (see [SIKE], 1.4 and 5.1) + KemSize int +} + +// Stores curve projective parameters equivalent to A/C. Meaning of the +// values depends on the context. When working with isogenies over +// subgroup that are powers of: +// * three then (A:C) ~ (A+2C:A-2C) +// * four then (A:C) ~ (A+2C: 4C) +// See Appendix A of SIKE for more details +type CurveCoefficientsEquiv struct { + A Fp2 + C Fp2 +} + +// A point on the projective line P^1(F_{p^2}). +// +// This represents a point on the Kummer line of a Montgomery curve. The +// curve is specified by a ProjectiveCurveParameters struct. +type ProjectivePoint struct { + X Fp2 + Z Fp2 +} + +// Base type for public and private key. Used mainly to carry domain +// parameters. +type key struct { + // Domain parameters of the algorithm to be used with a key + params *SidhParams + // Flag indicates wether corresponds to 2-, 3-torsion group or SIKE + keyVariant KeyVariant +} + +// Defines operations on private key +type PrivateKey struct { + key + // Secret key + Scalar []byte + // Used only by KEM + S []byte +} + +// Defines operations on public key +type PublicKey struct { + key + affine_xP Fp2 + affine_xQ Fp2 + affine_xQmP Fp2 +} + +// A point on the projective line P^1(F_{p^2}). +// +// This is used to work projectively with the curve coefficients. +type ProjectiveCurveParameters struct { + A Fp2 + C Fp2 +} + +const ( + // First 2 bits identify SIDH variant third bit indicates + // wether key is a SIKE variant (set) or SIDH (not set) + + // 001 - SIDH: corresponds to 2-torsion group + KeyVariant_SIDH_A KeyVariant = 1 << 0 + // 010 - SIDH: corresponds to 3-torsion group + KeyVariant_SIDH_B = 1 << 1 + // 110 - SIKE + KeyVariant_SIKE = 1<<2 | KeyVariant_SIDH_B + // Number of uint64 limbs used to store field element + FP_WORDS = 8 +) + +// Used internally by this package +// ------------------------------- + +var p503 = Fp{ + 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xABFFFFFFFFFFFFFF, + 0x13085BDA2211E7A0, 0x1B9BF6C87B7E7DAF, 0x6045C6BDDA77A4D0, 0x004066F541811E1E, +} + +// 2*503 +var p503x2 = Fp{ + 0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0x57FFFFFFFFFFFFFF, + 0x2610B7B44423CF41, 0x3737ED90F6FCFB5E, 0xC08B8D7BB4EF49A0, 0x0080CDEA83023C3C, +} + +// p503 + 1 +var p503p1 = Fp{ + 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, 0xAC00000000000000, + 0x13085BDA2211E7A0, 0x1B9BF6C87B7E7DAF, 0x6045C6BDDA77A4D0, 0x004066F541811E1E, +} + +// R^2=(2^512)^2 mod p +var p503R2 = Fp{ + 0x5289A0CF641D011F, 0x9B88257189FED2B9, 0xA3B365D58DC8F17A, 0x5BC57AB6EFF168EC, + 0x9E51998BD84D4423, 0xBF8999CBAC3B5695, 0x46E9127BCE14CDB6, 0x003F6CFCE8B81771, +} + +// p503 + 1 left-shifted by 8, assuming little endianness +var p503p1s8 = Fp{ + 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, + 0x085BDA2211E7A0AC, 0x9BF6C87B7E7DAF13, 0x45C6BDDA77A4D01B, 0x4066F541811E1E60, +} + +// 1*R mod p +var P503_OneFp2 = Fp2{ + A: Fp{ + 0x00000000000003F9, 0x0000000000000000, 0x0000000000000000, 0xB400000000000000, + 0x63CB1A6EA6DED2B4, 0x51689D8D667EB37D, 0x8ACD77C71AB24142, 0x0026FBAEC60F5953}, +} + +// 1/2 * R mod p +var P503_HalfFp2 = Fp2{ + A: Fp{ + 0x00000000000001FC, 0x0000000000000000, 0x0000000000000000, 0xB000000000000000, + 0x3B69BB2464785D2A, 0x36824A2AF0FE9896, 0xF5899F427A94F309, 0x0033B15203C83BB8}, +} + +var Params SidhParams + +func init() { + Params = SidhParams{ + // SIDH public key byte size. + PublicKeySize: 378, + // SIDH shared secret byte size. + SharedSecretSize: 126, + A: DomainParams{ + // The x-coordinate of PA + Affine_P: Fp2{ + A: Fp{ + 0xE7EF4AA786D855AF, 0xED5758F03EB34D3B, 0x09AE172535A86AA9, 0x237B9CC07D622723, + 0xE3A284CBA4E7932D, 0x27481D9176C5E63F, 0x6A323FF55C6E71BF, 0x002ECC31A6FB8773, + }, + B: Fp{ + 0x64D02E4E90A620B8, 0xDAB8128537D4B9F1, 0x4BADF77B8A228F98, 0x0F5DBDF9D1FB7D1B, + 0xBEC4DB288E1A0DCC, 0xE76A8665E80675DB, 0x6D6F252E12929463, 0x003188BD1463FACC, + }, + }, + // The x-coordinate of QA + Affine_Q: Fp2{ + A: Fp{ + 0xB79D41025DE85D56, 0x0B867DA9DF169686, 0x740E5368021C827D, 0x20615D72157BF25C, + 0xFF1590013C9B9F5B, 0xC884DCADE8C16CEA, 0xEBD05E53BF724E01, 0x0032FEF8FDA5748C, + }, + B: Fp{ + 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, + 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, + }, + }, + // The x-coordinate of RA = PA-QA + Affine_R: Fp2{ + A: Fp{ + 0x12E2E849AA0A8006, 0x41CF47008635A1E8, 0x9CD720A70798AED7, 0x42A820B42FCF04CF, + 0x7BF9BAD32AAE88B1, 0xF619127A54090BBE, 0x1CB10D8F56408EAA, 0x001D6B54C3C0EDEB, + }, + B: Fp{ + 0x34DB54931CBAAC36, 0x420A18CB8DD5F0C4, 0x32008C1A48C0F44D, 0x3B3BA772B1CFD44D, + 0xA74B058FDAF13515, 0x095FC9CA7EEC17B4, 0x448E829D28F120F8, 0x00261EC3ED16A489, + }, + }, + // Max size of secret key for 2-torsion group, corresponds to 2^e2 - 1 + SecretBitLen: 250, + // SecretBitLen in bytes. + SecretByteLen: uint((250 + 7) / 8), + // 2-torsion group computation strategy + IsogenyStrategy: []uint32{ + 0x3D, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, 0x04, 0x02, 0x01, + 0x01, 0x02, 0x01, 0x01, 0x08, 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, 0x04, 0x02, + 0x01, 0x01, 0x02, 0x01, 0x01, 0x10, 0x08, 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, + 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, 0x08, 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, + 0x01, 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, 0x1D, 0x10, 0x08, 0x04, 0x02, 0x01, + 0x01, 0x02, 0x01, 0x01, 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, 0x08, 0x04, 0x02, + 0x01, 0x01, 0x02, 0x01, 0x01, 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, 0x0D, 0x08, + 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, + 0x05, 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01}, + }, + B: DomainParams{ + // The x-coordinate of PB + Affine_P: Fp2{ + A: Fp{ + 0x7EDE37F4FA0BC727, 0xF7F8EC5C8598941C, 0xD15519B516B5F5C8, 0xF6D5AC9B87A36282, + 0x7B19F105B30E952E, 0x13BD8B2025B4EBEE, 0x7B96D27F4EC579A2, 0x00140850CAB7E5DE, + }, + B: Fp{ + 0x7764909DAE7B7B2D, 0x578ABB16284911AB, 0x76E2BFD146A6BF4D, 0x4824044B23AA02F0, + 0x1105048912A321F3, 0xB8A2E482CF0F10C1, 0x42FF7D0BE2152085, 0x0018E599C5223352, + }, + }, + // The x-coordinate of QB + Affine_Q: Fp2{ + A: Fp{ + 0x4256C520FB388820, 0x744FD7C3BAAF0A13, 0x4B6A2DDDB12CBCB8, 0xE46826E27F427DF8, + 0xFE4A663CD505A61B, 0xD6B3A1BAF025C695, 0x7C3BB62B8FCC00BD, 0x003AFDDE4A35746C, + }, + B: Fp{ + 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, + 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, + }, + }, + // The x-coordinate of RB = PB - QB + Affine_R: Fp2{ + A: Fp{ + 0x75601CD1E6C0DFCB, 0x1A9007239B58F93E, 0xC1F1BE80C62107AC, 0x7F513B898F29FF08, + 0xEA0BEDFF43E1F7B2, 0x2C6D94018CBAE6D0, 0x3A430D31BCD84672, 0x000D26892ECCFE83, + }, + B: Fp{ + 0x1119D62AEA3007A1, 0xE3702AA4E04BAE1B, 0x9AB96F7D59F990E7, 0xF58440E8B43319C0, + 0xAF8134BEE1489775, 0xE7F7774E905192AA, 0xF54AE09308E98039, 0x001EF7A041A86112, + }, + }, + // Size of secret key for 3-torsion group, corresponds to log_2(3^e3) - 1. + SecretBitLen: 252, + // SecretBitLen in bytes. + SecretByteLen: uint((252 + 7) / 8), + // 3-torsion group computation strategy + IsogenyStrategy: []uint32{ + 0x47, 0x26, 0x15, 0x0D, 0x08, 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, 0x04, 0x02, + 0x01, 0x01, 0x02, 0x01, 0x01, 0x05, 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, + 0x01, 0x01, 0x01, 0x09, 0x05, 0x03, 0x02, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, + 0x01, 0x04, 0x02, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x11, 0x09, 0x05, 0x03, 0x02, + 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x04, 0x02, 0x01, 0x01, 0x01, 0x02, + 0x01, 0x01, 0x08, 0x04, 0x02, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x04, 0x02, 0x01, + 0x01, 0x02, 0x01, 0x01, 0x21, 0x11, 0x09, 0x05, 0x03, 0x02, 0x01, 0x01, 0x01, 0x01, + 0x02, 0x01, 0x01, 0x01, 0x04, 0x02, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x08, 0x04, + 0x02, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, + 0x10, 0x08, 0x04, 0x02, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x04, 0x02, 0x01, 0x01, + 0x02, 0x01, 0x01, 0x08, 0x04, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, 0x04, 0x02, 0x01, + 0x01, 0x02, 0x01, 0x01}, + }, + OneFp2: P503_OneFp2, + HalfFp2: P503_HalfFp2, + MsgLen: 24, + // SIKEp503 provides 128 bit of classical security ([SIKE], 5.1) + KemSize: 16, + // ceil(503+7/8) + Bytelen: 63, + } +}
diff --git a/ssl/test/runner/sike/curve.go b/ssl/test/runner/sike/curve.go new file mode 100644 index 0000000..69febaf --- /dev/null +++ b/ssl/test/runner/sike/curve.go
@@ -0,0 +1,422 @@ +// Copyright (c) 2019, Cloudflare Inc. +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY +// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION +// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN +// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + +package sike + +// Interface for working with isogenies. +type isogeny interface { + // Given a torsion point on a curve computes isogenous curve. + // Returns curve coefficients (A:C), so that E_(A/C) = E_(A/C)/<P>, + // where P is a provided projective point. Sets also isogeny constants + // that are needed for isogeny evaluation. + GenerateCurve(*ProjectivePoint) CurveCoefficientsEquiv + // Evaluates isogeny at caller provided point. Requires isogeny curve constants + // to be earlier computed by GenerateCurve. + EvaluatePoint(*ProjectivePoint) ProjectivePoint +} + +// Stores isogeny 3 curve constants +type isogeny3 struct { + K1 Fp2 + K2 Fp2 +} + +// Stores isogeny 4 curve constants +type isogeny4 struct { + isogeny3 + K3 Fp2 +} + +// Constructs isogeny3 objects +func NewIsogeny3() isogeny { + return &isogeny3{} +} + +// Constructs isogeny4 objects +func NewIsogeny4() isogeny { + return &isogeny4{} +} + +// Helper function for RightToLeftLadder(). Returns A+2C / 4. +func calcAplus2Over4(cparams *ProjectiveCurveParameters) (ret Fp2) { + var tmp Fp2 + + // 2C + add(&tmp, &cparams.C, &cparams.C) + // A+2C + add(&ret, &cparams.A, &tmp) + // 1/4C + add(&tmp, &tmp, &tmp) + inv(&tmp, &tmp) + // A+2C/4C + mul(&ret, &ret, &tmp) + return +} + +// Converts values in x.A and x.B to Montgomery domain +// x.A = x.A * R mod p +// x.B = x.B * R mod p +// Performs v = v*R^2*R^(-1) mod p, for both x.A and x.B +func toMontDomain(x *Fp2) { + var aRR FpX2 + + // convert to montgomery domain + fpMul(&aRR, &x.A, &p503R2) // = a*R*R + fpMontRdc(&x.A, &aRR) // = a*R mod p + fpMul(&aRR, &x.B, &p503R2) + fpMontRdc(&x.B, &aRR) +} + +// Converts values in x.A and x.B from Montgomery domain +// a = x.A mod p +// b = x.B mod p +// +// After returning from the call x is not modified. +func fromMontDomain(x *Fp2, out *Fp2) { + var aR FpX2 + + // convert from montgomery domain + copy(aR[:], x.A[:]) + fpMontRdc(&out.A, &aR) // = a mod p in [0, 2p) + fpRdcP(&out.A) // = a mod p in [0, p) + for i := range aR { + aR[i] = 0 + } + copy(aR[:], x.B[:]) + fpMontRdc(&out.B, &aR) + fpRdcP(&out.B) +} + +// Computes j-invariant for a curve y2=x3+A/Cx+x with A,C in F_(p^2). Result +// is returned in 'j'. Implementation corresponds to Algorithm 9 from SIKE. +func Jinvariant(cparams *ProjectiveCurveParameters, j *Fp2) { + var t0, t1 Fp2 + + sqr(j, &cparams.A) // j = A^2 + sqr(&t1, &cparams.C) // t1 = C^2 + add(&t0, &t1, &t1) // t0 = t1 + t1 + sub(&t0, j, &t0) // t0 = j - t0 + sub(&t0, &t0, &t1) // t0 = t0 - t1 + sub(j, &t0, &t1) // t0 = t0 - t1 + sqr(&t1, &t1) // t1 = t1^2 + mul(j, j, &t1) // j = j * t1 + add(&t0, &t0, &t0) // t0 = t0 + t0 + add(&t0, &t0, &t0) // t0 = t0 + t0 + sqr(&t1, &t0) // t1 = t0^2 + mul(&t0, &t0, &t1) // t0 = t0 * t1 + add(&t0, &t0, &t0) // t0 = t0 + t0 + add(&t0, &t0, &t0) // t0 = t0 + t0 + inv(j, j) // j = 1/j + mul(j, &t0, j) // j = t0 * j +} + +// Given affine points x(P), x(Q) and x(Q-P) in a extension field F_{p^2}, function +// recorvers projective coordinate A of a curve. This is Algorithm 10 from SIKE. +func RecoverCoordinateA(curve *ProjectiveCurveParameters, xp, xq, xr *Fp2) { + var t0, t1 Fp2 + + add(&t1, xp, xq) // t1 = Xp + Xq + mul(&t0, xp, xq) // t0 = Xp * Xq + mul(&curve.A, xr, &t1) // A = X(q-p) * t1 + add(&curve.A, &curve.A, &t0) // A = A + t0 + mul(&t0, &t0, xr) // t0 = t0 * X(q-p) + sub(&curve.A, &curve.A, &Params.OneFp2) // A = A - 1 + add(&t0, &t0, &t0) // t0 = t0 + t0 + add(&t1, &t1, xr) // t1 = t1 + X(q-p) + add(&t0, &t0, &t0) // t0 = t0 + t0 + sqr(&curve.A, &curve.A) // A = A^2 + inv(&t0, &t0) // t0 = 1/t0 + mul(&curve.A, &curve.A, &t0) // A = A * t0 + sub(&curve.A, &curve.A, &t1) // A = A - t1 +} + +// Computes equivalence (A:C) ~ (A+2C : A-2C) +func CalcCurveParamsEquiv3(cparams *ProjectiveCurveParameters) CurveCoefficientsEquiv { + var coef CurveCoefficientsEquiv + var c2 Fp2 + + add(&c2, &cparams.C, &cparams.C) + // A24p = A+2*C + add(&coef.A, &cparams.A, &c2) + // A24m = A-2*C + sub(&coef.C, &cparams.A, &c2) + return coef +} + +// Computes equivalence (A:C) ~ (A+2C : 4C) +func CalcCurveParamsEquiv4(cparams *ProjectiveCurveParameters) CurveCoefficientsEquiv { + var coefEq CurveCoefficientsEquiv + + add(&coefEq.C, &cparams.C, &cparams.C) + // A24p = A+2C + add(&coefEq.A, &cparams.A, &coefEq.C) + // C24 = 4*C + add(&coefEq.C, &coefEq.C, &coefEq.C) + return coefEq +} + +// Recovers (A:C) curve parameters from projectively equivalent (A+2C:A-2C). +func RecoverCurveCoefficients3(cparams *ProjectiveCurveParameters, coefEq *CurveCoefficientsEquiv) { + add(&cparams.A, &coefEq.A, &coefEq.C) + // cparams.A = 2*(A+2C+A-2C) = 4A + add(&cparams.A, &cparams.A, &cparams.A) + // cparams.C = (A+2C-A+2C) = 4C + sub(&cparams.C, &coefEq.A, &coefEq.C) + return +} + +// Recovers (A:C) curve parameters from projectively equivalent (A+2C:4C). +func RecoverCurveCoefficients4(cparams *ProjectiveCurveParameters, coefEq *CurveCoefficientsEquiv) { + // cparams.C = (4C)*1/2=2C + mul(&cparams.C, &coefEq.C, &Params.HalfFp2) + // cparams.A = A+2C - 2C = A + sub(&cparams.A, &coefEq.A, &cparams.C) + // cparams.C = 2C * 1/2 = C + mul(&cparams.C, &cparams.C, &Params.HalfFp2) + return +} + +// Combined coordinate doubling and differential addition. Takes projective points +// P,Q,Q-P and (A+2C)/4C curve E coefficient. Returns 2*P and P+Q calculated on E. +// Function is used only by RightToLeftLadder. Corresponds to Algorithm 5 of SIKE +func xDbladd(P, Q, QmP *ProjectivePoint, a24 *Fp2) (dblP, PaQ ProjectivePoint) { + var t0, t1, t2 Fp2 + xQmP, zQmP := &QmP.X, &QmP.Z + xPaQ, zPaQ := &PaQ.X, &PaQ.Z + x2P, z2P := &dblP.X, &dblP.Z + xP, zP := &P.X, &P.Z + xQ, zQ := &Q.X, &Q.Z + + add(&t0, xP, zP) // t0 = Xp+Zp + sub(&t1, xP, zP) // t1 = Xp-Zp + sqr(x2P, &t0) // 2P.X = t0^2 + sub(&t2, xQ, zQ) // t2 = Xq-Zq + add(xPaQ, xQ, zQ) // Xp+q = Xq+Zq + mul(&t0, &t0, &t2) // t0 = t0 * t2 + mul(z2P, &t1, &t1) // 2P.Z = t1 * t1 + mul(&t1, &t1, xPaQ) // t1 = t1 * Xp+q + sub(&t2, x2P, z2P) // t2 = 2P.X - 2P.Z + mul(x2P, x2P, z2P) // 2P.X = 2P.X * 2P.Z + mul(xPaQ, a24, &t2) // Xp+q = A24 * t2 + sub(zPaQ, &t0, &t1) // Zp+q = t0 - t1 + add(z2P, xPaQ, z2P) // 2P.Z = Xp+q + 2P.Z + add(xPaQ, &t0, &t1) // Xp+q = t0 + t1 + mul(z2P, z2P, &t2) // 2P.Z = 2P.Z * t2 + sqr(zPaQ, zPaQ) // Zp+q = Zp+q ^ 2 + sqr(xPaQ, xPaQ) // Xp+q = Xp+q ^ 2 + mul(zPaQ, xQmP, zPaQ) // Zp+q = Xq-p * Zp+q + mul(xPaQ, zQmP, xPaQ) // Xp+q = Zq-p * Xp+q + return +} + +// Given the curve parameters, xP = x(P), computes xP = x([2^k]P) +// Safe to overlap xP, x2P. +func Pow2k(xP *ProjectivePoint, params *CurveCoefficientsEquiv, k uint32) { + var t0, t1 Fp2 + + x, z := &xP.X, &xP.Z + for i := uint32(0); i < k; i++ { + sub(&t0, x, z) // t0 = Xp - Zp + add(&t1, x, z) // t1 = Xp + Zp + sqr(&t0, &t0) // t0 = t0 ^ 2 + sqr(&t1, &t1) // t1 = t1 ^ 2 + mul(z, ¶ms.C, &t0) // Z2p = C24 * t0 + mul(x, z, &t1) // X2p = Z2p * t1 + sub(&t1, &t1, &t0) // t1 = t1 - t0 + mul(&t0, ¶ms.A, &t1) // t0 = A24+ * t1 + add(z, z, &t0) // Z2p = Z2p + t0 + mul(z, z, &t1) // Zp = Z2p * t1 + } +} + +// Given the curve parameters, xP = x(P), and k >= 0, compute xP = x([3^k]P). +// +// Safe to overlap xP, xR. +func Pow3k(xP *ProjectivePoint, params *CurveCoefficientsEquiv, k uint32) { + var t0, t1, t2, t3, t4, t5, t6 Fp2 + + x, z := &xP.X, &xP.Z + for i := uint32(0); i < k; i++ { + sub(&t0, x, z) // t0 = Xp - Zp + sqr(&t2, &t0) // t2 = t0^2 + add(&t1, x, z) // t1 = Xp + Zp + sqr(&t3, &t1) // t3 = t1^2 + add(&t4, &t1, &t0) // t4 = t1 + t0 + sub(&t0, &t1, &t0) // t0 = t1 - t0 + sqr(&t1, &t4) // t1 = t4^2 + sub(&t1, &t1, &t3) // t1 = t1 - t3 + sub(&t1, &t1, &t2) // t1 = t1 - t2 + mul(&t5, &t3, ¶ms.A) // t5 = t3 * A24+ + mul(&t3, &t3, &t5) // t3 = t5 * t3 + mul(&t6, &t2, ¶ms.C) // t6 = t2 * A24- + mul(&t2, &t2, &t6) // t2 = t2 * t6 + sub(&t3, &t2, &t3) // t3 = t2 - t3 + sub(&t2, &t5, &t6) // t2 = t5 - t6 + mul(&t1, &t2, &t1) // t1 = t2 * t1 + add(&t2, &t3, &t1) // t2 = t3 + t1 + sqr(&t2, &t2) // t2 = t2^2 + mul(x, &t2, &t4) // X3p = t2 * t4 + sub(&t1, &t3, &t1) // t1 = t3 - t1 + sqr(&t1, &t1) // t1 = t1^2 + mul(z, &t1, &t0) // Z3p = t1 * t0 + } +} + +// Set (y1, y2, y3) = (1/x1, 1/x2, 1/x3). +// +// All xi, yi must be distinct. +func Fp2Batch3Inv(x1, x2, x3, y1, y2, y3 *Fp2) { + var x1x2, t Fp2 + + mul(&x1x2, x1, x2) // x1*x2 + mul(&t, &x1x2, x3) // 1/(x1*x2*x3) + inv(&t, &t) + mul(y1, &t, x2) // 1/x1 + mul(y1, y1, x3) + mul(y2, &t, x1) // 1/x2 + mul(y2, y2, x3) + mul(y3, &t, &x1x2) // 1/x3 +} + +// ScalarMul3Pt is a right-to-left point multiplication that given the +// x-coordinate of P, Q and P-Q calculates the x-coordinate of R=Q+[scalar]P. +// nbits must be smaller or equal to len(scalar). +func ScalarMul3Pt(cparams *ProjectiveCurveParameters, P, Q, PmQ *ProjectivePoint, nbits uint, scalar []uint8) ProjectivePoint { + var R0, R2, R1 ProjectivePoint + aPlus2Over4 := calcAplus2Over4(cparams) + R1 = *P + R2 = *PmQ + R0 = *Q + + // Iterate over the bits of the scalar, bottom to top + prevBit := uint8(0) + for i := uint(0); i < nbits; i++ { + bit := (scalar[i>>3] >> (i & 7) & 1) + swap := prevBit ^ bit + prevBit = bit + condSwap(&R1.X, &R1.Z, &R2.X, &R2.Z, swap) + R0, R2 = xDbladd(&R0, &R2, &R1, &aPlus2Over4) + } + condSwap(&R1.X, &R1.Z, &R2.X, &R2.Z, prevBit) + return R1 +} + +// Given a three-torsion point p = x(PB) on the curve E_(A:C), construct the +// three-isogeny phi : E_(A:C) -> E_(A:C)/<P_3> = E_(A':C'). +// +// Input: (XP_3: ZP_3), where P_3 has exact order 3 on E_A/C +// Output: * Curve coordinates (A' + 2C', A' - 2C') corresponding to E_A'/C' = A_E/C/<P3> +// * isogeny phi with constants in F_p^2 +func (phi *isogeny3) GenerateCurve(p *ProjectivePoint) CurveCoefficientsEquiv { + var t0, t1, t2, t3, t4 Fp2 + var coefEq CurveCoefficientsEquiv + var K1, K2 = &phi.K1, &phi.K2 + + sub(K1, &p.X, &p.Z) // K1 = XP3 - ZP3 + sqr(&t0, K1) // t0 = K1^2 + add(K2, &p.X, &p.Z) // K2 = XP3 + ZP3 + sqr(&t1, K2) // t1 = K2^2 + add(&t2, &t0, &t1) // t2 = t0 + t1 + add(&t3, K1, K2) // t3 = K1 + K2 + sqr(&t3, &t3) // t3 = t3^2 + sub(&t3, &t3, &t2) // t3 = t3 - t2 + add(&t2, &t1, &t3) // t2 = t1 + t3 + add(&t3, &t3, &t0) // t3 = t3 + t0 + add(&t4, &t3, &t0) // t4 = t3 + t0 + add(&t4, &t4, &t4) // t4 = t4 + t4 + add(&t4, &t1, &t4) // t4 = t1 + t4 + mul(&coefEq.C, &t2, &t4) // A24m = t2 * t4 + add(&t4, &t1, &t2) // t4 = t1 + t2 + add(&t4, &t4, &t4) // t4 = t4 + t4 + add(&t4, &t0, &t4) // t4 = t0 + t4 + mul(&t4, &t3, &t4) // t4 = t3 * t4 + sub(&t0, &t4, &coefEq.C) // t0 = t4 - A24m + add(&coefEq.A, &coefEq.C, &t0) // A24p = A24m + t0 + return coefEq +} + +// Given a 3-isogeny phi and a point pB = x(PB), compute x(QB), the x-coordinate +// of the image QB = phi(PB) of PB under phi : E_(A:C) -> E_(A':C'). +// +// The output xQ = x(Q) is then a point on the curve E_(A':C'); the curve +// parameters are returned by the GenerateCurve function used to construct phi. +func (phi *isogeny3) EvaluatePoint(p *ProjectivePoint) ProjectivePoint { + var t0, t1, t2 Fp2 + var q ProjectivePoint + var K1, K2 = &phi.K1, &phi.K2 + var px, pz = &p.X, &p.Z + + add(&t0, px, pz) // t0 = XQ + ZQ + sub(&t1, px, pz) // t1 = XQ - ZQ + mul(&t0, K1, &t0) // t2 = K1 * t0 + mul(&t1, K2, &t1) // t1 = K2 * t1 + add(&t2, &t0, &t1) // t2 = t0 + t1 + sub(&t0, &t1, &t0) // t0 = t1 - t0 + sqr(&t2, &t2) // t2 = t2 ^ 2 + sqr(&t0, &t0) // t0 = t0 ^ 2 + mul(&q.X, px, &t2) // XQ'= XQ * t2 + mul(&q.Z, pz, &t0) // ZQ'= ZQ * t0 + return q +} + +// Given a four-torsion point p = x(PB) on the curve E_(A:C), construct the +// four-isogeny phi : E_(A:C) -> E_(A:C)/<P_4> = E_(A':C'). +// +// Input: (XP_4: ZP_4), where P_4 has exact order 4 on E_A/C +// Output: * Curve coordinates (A' + 2C', 4C') corresponding to E_A'/C' = A_E/C/<P4> +// * isogeny phi with constants in F_p^2 +func (phi *isogeny4) GenerateCurve(p *ProjectivePoint) CurveCoefficientsEquiv { + var coefEq CurveCoefficientsEquiv + var xp4, zp4 = &p.X, &p.Z + var K1, K2, K3 = &phi.K1, &phi.K2, &phi.K3 + + sub(K2, xp4, zp4) + add(K3, xp4, zp4) + sqr(K1, zp4) + add(K1, K1, K1) + sqr(&coefEq.C, K1) + add(K1, K1, K1) + sqr(&coefEq.A, xp4) + add(&coefEq.A, &coefEq.A, &coefEq.A) + sqr(&coefEq.A, &coefEq.A) + return coefEq +} + +// Given a 4-isogeny phi and a point xP = x(P), compute x(Q), the x-coordinate +// of the image Q = phi(P) of P under phi : E_(A:C) -> E_(A':C'). +// +// Input: isogeny returned by GenerateCurve and point q=(Qx,Qz) from E0_A/C +// Output: Corresponding point q from E1_A'/C', where E1 is 4-isogenous to E0 +func (phi *isogeny4) EvaluatePoint(p *ProjectivePoint) ProjectivePoint { + var t0, t1 Fp2 + var q = *p + var xq, zq = &q.X, &q.Z + var K1, K2, K3 = &phi.K1, &phi.K2, &phi.K3 + + add(&t0, xq, zq) + sub(&t1, xq, zq) + mul(xq, &t0, K2) + mul(zq, &t1, K3) + mul(&t0, &t0, &t1) + mul(&t0, &t0, K1) + add(&t1, xq, zq) + sub(zq, xq, zq) + sqr(&t1, &t1) + sqr(zq, zq) + add(xq, &t0, &t1) + sub(&t0, zq, &t0) + mul(xq, xq, &t1) + mul(zq, zq, &t0) + return q +}
diff --git a/ssl/test/runner/sike/sike.go b/ssl/test/runner/sike/sike.go new file mode 100644 index 0000000..129cece --- /dev/null +++ b/ssl/test/runner/sike/sike.go
@@ -0,0 +1,709 @@ +// Copyright (c) 2019, Cloudflare Inc. +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY +// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION +// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN +// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + +package sike + +import ( + "crypto/hmac" + "crypto/sha256" + "crypto/subtle" + "errors" + "io" +) + +// Constants used for cSHAKE customization +// Those values are different than in [SIKE] - they are encoded on 16bits. This is +// done in order for implementation to be compatible with [REF] and test vectors. +var G = []byte{0x00, 0x00} +var H = []byte{0x01, 0x00} +var F = []byte{0x02, 0x00} + +// Generates HMAC-SHA256 sum +func hashMac(out, in, S []byte) { + h := hmac.New(sha256.New, in) + h.Write(S) + copy(out, h.Sum(nil)) +} + +// Zeroize Fp2 +func zeroize(fp *Fp2) { + // Zeroizing in 2 seperated loops tells compiler to + // use fast runtime.memclr() + for i := range fp.A { + fp.A[i] = 0 + } + for i := range fp.B { + fp.B[i] = 0 + } +} + +// Convert the input to wire format. +// +// The output byte slice must be at least 2*bytelen(p) bytes long. +func convFp2ToBytes(output []byte, fp2 *Fp2) { + if len(output) < 2*Params.Bytelen { + panic("output byte slice too short") + } + var a Fp2 + fromMontDomain(fp2, &a) + + // convert to bytes in little endian form + for i := 0; i < Params.Bytelen; i++ { + // set i = j*8 + k + tmp := i / 8 + k := uint64(i % 8) + output[i] = byte(a.A[tmp] >> (8 * k)) + output[i+Params.Bytelen] = byte(a.B[tmp] >> (8 * k)) + } +} + +// Read 2*bytelen(p) bytes into the given ExtensionFieldElement. +// +// It is an error to call this function if the input byte slice is less than 2*bytelen(p) bytes long. +func convBytesToFp2(fp2 *Fp2, input []byte) { + if len(input) < 2*Params.Bytelen { + panic("input byte slice too short") + } + + for i := 0; i < Params.Bytelen; i++ { + j := i / 8 + k := uint64(i % 8) + fp2.A[j] |= uint64(input[i]) << (8 * k) + fp2.B[j] |= uint64(input[i+Params.Bytelen]) << (8 * k) + } + toMontDomain(fp2) +} + +// ----------------------------------------------------------------------------- +// Functions for traversing isogeny trees acoording to strategy. Key type 'A' is +// + +// Traverses isogeny tree in order to compute xR, xP, xQ and xQmP needed +// for public key generation. +func traverseTreePublicKeyA(curve *ProjectiveCurveParameters, xR, phiP, phiQ, phiR *ProjectivePoint, pub *PublicKey) { + var points = make([]ProjectivePoint, 0, 8) + var indices = make([]int, 0, 8) + var i, sidx int + + cparam := CalcCurveParamsEquiv4(curve) + phi := NewIsogeny4() + strat := pub.params.A.IsogenyStrategy + stratSz := len(strat) + + for j := 1; j <= stratSz; j++ { + for i <= stratSz-j { + points = append(points, *xR) + indices = append(indices, i) + + k := strat[sidx] + sidx++ + Pow2k(xR, &cparam, 2*k) + i += int(k) + } + + cparam = phi.GenerateCurve(xR) + for k := 0; k < len(points); k++ { + points[k] = phi.EvaluatePoint(&points[k]) + } + + *phiP = phi.EvaluatePoint(phiP) + *phiQ = phi.EvaluatePoint(phiQ) + *phiR = phi.EvaluatePoint(phiR) + + // pop xR from points + *xR, points = points[len(points)-1], points[:len(points)-1] + i, indices = int(indices[len(indices)-1]), indices[:len(indices)-1] + } +} + +// Traverses isogeny tree in order to compute xR needed +// for public key generation. +func traverseTreeSharedKeyA(curve *ProjectiveCurveParameters, xR *ProjectivePoint, pub *PublicKey) { + var points = make([]ProjectivePoint, 0, 8) + var indices = make([]int, 0, 8) + var i, sidx int + + cparam := CalcCurveParamsEquiv4(curve) + phi := NewIsogeny4() + strat := pub.params.A.IsogenyStrategy + stratSz := len(strat) + + for j := 1; j <= stratSz; j++ { + for i <= stratSz-j { + points = append(points, *xR) + indices = append(indices, i) + + k := strat[sidx] + sidx++ + Pow2k(xR, &cparam, 2*k) + i += int(k) + } + + cparam = phi.GenerateCurve(xR) + for k := 0; k < len(points); k++ { + points[k] = phi.EvaluatePoint(&points[k]) + } + + // pop xR from points + *xR, points = points[len(points)-1], points[:len(points)-1] + i, indices = int(indices[len(indices)-1]), indices[:len(indices)-1] + } +} + +// Traverses isogeny tree in order to compute xR, xP, xQ and xQmP needed +// for public key generation. +func traverseTreePublicKeyB(curve *ProjectiveCurveParameters, xR, phiP, phiQ, phiR *ProjectivePoint, pub *PublicKey) { + var points = make([]ProjectivePoint, 0, 8) + var indices = make([]int, 0, 8) + var i, sidx int + + cparam := CalcCurveParamsEquiv3(curve) + phi := NewIsogeny3() + strat := pub.params.B.IsogenyStrategy + stratSz := len(strat) + + for j := 1; j <= stratSz; j++ { + for i <= stratSz-j { + points = append(points, *xR) + indices = append(indices, i) + + k := strat[sidx] + sidx++ + Pow3k(xR, &cparam, k) + i += int(k) + } + + cparam = phi.GenerateCurve(xR) + for k := 0; k < len(points); k++ { + points[k] = phi.EvaluatePoint(&points[k]) + } + + *phiP = phi.EvaluatePoint(phiP) + *phiQ = phi.EvaluatePoint(phiQ) + *phiR = phi.EvaluatePoint(phiR) + + // pop xR from points + *xR, points = points[len(points)-1], points[:len(points)-1] + i, indices = int(indices[len(indices)-1]), indices[:len(indices)-1] + } +} + +// Traverses isogeny tree in order to compute xR, xP, xQ and xQmP needed +// for public key generation. +func traverseTreeSharedKeyB(curve *ProjectiveCurveParameters, xR *ProjectivePoint, pub *PublicKey) { + var points = make([]ProjectivePoint, 0, 8) + var indices = make([]int, 0, 8) + var i, sidx int + + cparam := CalcCurveParamsEquiv3(curve) + phi := NewIsogeny3() + strat := pub.params.B.IsogenyStrategy + stratSz := len(strat) + + for j := 1; j <= stratSz; j++ { + for i <= stratSz-j { + points = append(points, *xR) + indices = append(indices, i) + + k := strat[sidx] + sidx++ + Pow3k(xR, &cparam, k) + i += int(k) + } + + cparam = phi.GenerateCurve(xR) + for k := 0; k < len(points); k++ { + points[k] = phi.EvaluatePoint(&points[k]) + } + + // pop xR from points + *xR, points = points[len(points)-1], points[:len(points)-1] + i, indices = int(indices[len(indices)-1]), indices[:len(indices)-1] + } +} + +// Generate a public key in the 2-torsion group +func publicKeyGenA(prv *PrivateKey) (pub *PublicKey) { + var xPA, xQA, xRA ProjectivePoint + var xPB, xQB, xRB, xR ProjectivePoint + var invZP, invZQ, invZR Fp2 + var tmp ProjectiveCurveParameters + + pub = NewPublicKey(KeyVariant_SIDH_A) + var phi = NewIsogeny4() + + // Load points for A + xPA = ProjectivePoint{X: prv.params.A.Affine_P, Z: prv.params.OneFp2} + xQA = ProjectivePoint{X: prv.params.A.Affine_Q, Z: prv.params.OneFp2} + xRA = ProjectivePoint{X: prv.params.A.Affine_R, Z: prv.params.OneFp2} + + // Load points for B + xRB = ProjectivePoint{X: prv.params.B.Affine_R, Z: prv.params.OneFp2} + xQB = ProjectivePoint{X: prv.params.B.Affine_Q, Z: prv.params.OneFp2} + xPB = ProjectivePoint{X: prv.params.B.Affine_P, Z: prv.params.OneFp2} + + // Find isogeny kernel + tmp.C = pub.params.OneFp2 + xR = ScalarMul3Pt(&tmp, &xPA, &xQA, &xRA, prv.params.A.SecretBitLen, prv.Scalar) + + // Reset params object and travers isogeny tree + tmp.C = pub.params.OneFp2 + zeroize(&tmp.A) + traverseTreePublicKeyA(&tmp, &xR, &xPB, &xQB, &xRB, pub) + + // Secret isogeny + phi.GenerateCurve(&xR) + xPA = phi.EvaluatePoint(&xPB) + xQA = phi.EvaluatePoint(&xQB) + xRA = phi.EvaluatePoint(&xRB) + Fp2Batch3Inv(&xPA.Z, &xQA.Z, &xRA.Z, &invZP, &invZQ, &invZR) + + mul(&pub.affine_xP, &xPA.X, &invZP) + mul(&pub.affine_xQ, &xQA.X, &invZQ) + mul(&pub.affine_xQmP, &xRA.X, &invZR) + return +} + +// Generate a public key in the 3-torsion group +func publicKeyGenB(prv *PrivateKey) (pub *PublicKey) { + var xPB, xQB, xRB, xR ProjectivePoint + var xPA, xQA, xRA ProjectivePoint + var invZP, invZQ, invZR Fp2 + var tmp ProjectiveCurveParameters + + pub = NewPublicKey(prv.keyVariant) + var phi = NewIsogeny3() + + // Load points for B + xRB = ProjectivePoint{X: prv.params.B.Affine_R, Z: prv.params.OneFp2} + xQB = ProjectivePoint{X: prv.params.B.Affine_Q, Z: prv.params.OneFp2} + xPB = ProjectivePoint{X: prv.params.B.Affine_P, Z: prv.params.OneFp2} + + // Load points for A + xPA = ProjectivePoint{X: prv.params.A.Affine_P, Z: prv.params.OneFp2} + xQA = ProjectivePoint{X: prv.params.A.Affine_Q, Z: prv.params.OneFp2} + xRA = ProjectivePoint{X: prv.params.A.Affine_R, Z: prv.params.OneFp2} + + tmp.C = pub.params.OneFp2 + xR = ScalarMul3Pt(&tmp, &xPB, &xQB, &xRB, prv.params.B.SecretBitLen, prv.Scalar) + + tmp.C = pub.params.OneFp2 + zeroize(&tmp.A) + traverseTreePublicKeyB(&tmp, &xR, &xPA, &xQA, &xRA, pub) + + phi.GenerateCurve(&xR) + xPB = phi.EvaluatePoint(&xPA) + xQB = phi.EvaluatePoint(&xQA) + xRB = phi.EvaluatePoint(&xRA) + Fp2Batch3Inv(&xPB.Z, &xQB.Z, &xRB.Z, &invZP, &invZQ, &invZR) + + mul(&pub.affine_xP, &xPB.X, &invZP) + mul(&pub.affine_xQ, &xQB.X, &invZQ) + mul(&pub.affine_xQmP, &xRB.X, &invZR) + return +} + +// ----------------------------------------------------------------------------- +// Key agreement functions +// + +// Establishing shared keys in in 2-torsion group +func deriveSecretA(prv *PrivateKey, pub *PublicKey) []byte { + var sharedSecret = make([]byte, pub.params.SharedSecretSize) + var cparam ProjectiveCurveParameters + var xP, xQ, xQmP ProjectivePoint + var xR ProjectivePoint + var phi = NewIsogeny4() + var jInv Fp2 + + // Recover curve coefficients + cparam.C = pub.params.OneFp2 + RecoverCoordinateA(&cparam, &pub.affine_xP, &pub.affine_xQ, &pub.affine_xQmP) + + // Find kernel of the morphism + xP = ProjectivePoint{X: pub.affine_xP, Z: pub.params.OneFp2} + xQ = ProjectivePoint{X: pub.affine_xQ, Z: pub.params.OneFp2} + xQmP = ProjectivePoint{X: pub.affine_xQmP, Z: pub.params.OneFp2} + xR = ScalarMul3Pt(&cparam, &xP, &xQ, &xQmP, pub.params.A.SecretBitLen, prv.Scalar) + + // Traverse isogeny tree + traverseTreeSharedKeyA(&cparam, &xR, pub) + + // Calculate j-invariant on isogeneus curve + c := phi.GenerateCurve(&xR) + RecoverCurveCoefficients4(&cparam, &c) + Jinvariant(&cparam, &jInv) + convFp2ToBytes(sharedSecret, &jInv) + return sharedSecret +} + +// Establishing shared keys in in 3-torsion group +func deriveSecretB(prv *PrivateKey, pub *PublicKey) []byte { + var sharedSecret = make([]byte, pub.params.SharedSecretSize) + var xP, xQ, xQmP ProjectivePoint + var xR ProjectivePoint + var cparam ProjectiveCurveParameters + var phi = NewIsogeny3() + var jInv Fp2 + + // Recover curve coefficients + cparam.C = pub.params.OneFp2 + RecoverCoordinateA(&cparam, &pub.affine_xP, &pub.affine_xQ, &pub.affine_xQmP) + + // Find kernel of the morphism + xP = ProjectivePoint{X: pub.affine_xP, Z: pub.params.OneFp2} + xQ = ProjectivePoint{X: pub.affine_xQ, Z: pub.params.OneFp2} + xQmP = ProjectivePoint{X: pub.affine_xQmP, Z: pub.params.OneFp2} + xR = ScalarMul3Pt(&cparam, &xP, &xQ, &xQmP, pub.params.B.SecretBitLen, prv.Scalar) + + // Traverse isogeny tree + traverseTreeSharedKeyB(&cparam, &xR, pub) + + // Calculate j-invariant on isogeneus curve + c := phi.GenerateCurve(&xR) + RecoverCurveCoefficients3(&cparam, &c) + Jinvariant(&cparam, &jInv) + convFp2ToBytes(sharedSecret, &jInv) + return sharedSecret +} + +func encrypt(skA *PrivateKey, pkA, pkB *PublicKey, ptext []byte) ([]byte, error) { + var n [40]byte // n can is max 320-bit (see 1.4 of [SIKE]) + var ptextLen = len(ptext) + + if pkB.keyVariant != KeyVariant_SIKE { + return nil, errors.New("wrong key type") + } + + j, err := DeriveSecret(skA, pkB) + if err != nil { + return nil, err + } + + hashMac(n[:ptextLen], j, F) + for i, _ := range ptext { + n[i] ^= ptext[i] + } + + ret := make([]byte, pkA.Size()+ptextLen) + copy(ret, pkA.Export()) + copy(ret[pkA.Size():], n[:ptextLen]) + return ret, nil +} + +// NewPrivateKey initializes private key. +// Usage of this function guarantees that the object is correctly initialized. +func NewPrivateKey(v KeyVariant) *PrivateKey { + prv := &PrivateKey{key: key{params: &Params, keyVariant: v}} + if (v & KeyVariant_SIDH_A) == KeyVariant_SIDH_A { + prv.Scalar = make([]byte, prv.params.A.SecretByteLen) + } else { + prv.Scalar = make([]byte, prv.params.B.SecretByteLen) + } + if v == KeyVariant_SIKE { + prv.S = make([]byte, prv.params.MsgLen) + } + return prv +} + +// NewPublicKey initializes public key. +// Usage of this function guarantees that the object is correctly initialized. +func NewPublicKey(v KeyVariant) *PublicKey { + return &PublicKey{key: key{params: &Params, keyVariant: v}} +} + +// Import clears content of the public key currently stored in the structure +// and imports key stored in the byte string. Returns error in case byte string +// size is wrong. Doesn't perform any validation. +func (pub *PublicKey) Import(input []byte) error { + if len(input) != pub.Size() { + return errors.New("sidh: input to short") + } + ssSz := pub.params.SharedSecretSize + convBytesToFp2(&pub.affine_xP, input[0:ssSz]) + convBytesToFp2(&pub.affine_xQ, input[ssSz:2*ssSz]) + convBytesToFp2(&pub.affine_xQmP, input[2*ssSz:3*ssSz]) + return nil +} + +// Exports currently stored key. In case structure hasn't been filled with key data +// returned byte string is filled with zeros. +func (pub *PublicKey) Export() []byte { + output := make([]byte, pub.params.PublicKeySize) + ssSz := pub.params.SharedSecretSize + convFp2ToBytes(output[0:ssSz], &pub.affine_xP) + convFp2ToBytes(output[ssSz:2*ssSz], &pub.affine_xQ) + convFp2ToBytes(output[2*ssSz:3*ssSz], &pub.affine_xQmP) + return output +} + +// Size returns size of the public key in bytes +func (pub *PublicKey) Size() int { + return pub.params.PublicKeySize +} + +// Exports currently stored key. In case structure hasn't been filled with key data +// returned byte string is filled with zeros. +func (prv *PrivateKey) Export() []byte { + ret := make([]byte, len(prv.Scalar)+len(prv.S)) + copy(ret, prv.S) + copy(ret[len(prv.S):], prv.Scalar) + return ret +} + +// Size returns size of the private key in bytes +func (prv *PrivateKey) Size() int { + tmp := len(prv.Scalar) + if prv.keyVariant == KeyVariant_SIKE { + tmp += int(prv.params.MsgLen) + } + return tmp +} + +// Import clears content of the private key currently stored in the structure +// and imports key from octet string. In case of SIKE, the random value 'S' +// must be prepended to the value of actual private key (see SIKE spec for details). +// Function doesn't import public key value to PrivateKey object. +func (prv *PrivateKey) Import(input []byte) error { + if len(input) != prv.Size() { + return errors.New("sidh: input to short") + } + copy(prv.S, input[:len(prv.S)]) + copy(prv.Scalar, input[len(prv.S):]) + return nil +} + +// Generates random private key for SIDH or SIKE. Generated value is +// formed as little-endian integer from key-space <2^(e2-1)..2^e2 - 1> +// for KeyVariant_A or <2^(s-1)..2^s - 1>, where s = floor(log_2(3^e3)), +// for KeyVariant_B. +// +// Returns error in case user provided RNG fails. +func (prv *PrivateKey) Generate(rand io.Reader) error { + var err error + var dp *DomainParams + + if (prv.keyVariant & KeyVariant_SIDH_A) == KeyVariant_SIDH_A { + dp = &prv.params.A + } else { + dp = &prv.params.B + } + + if prv.keyVariant == KeyVariant_SIKE && err == nil { + _, err = io.ReadFull(rand, prv.S) + } + + // Private key generation takes advantage of the fact that keyspace for secret + // key is (0, 2^x - 1), for some possitivite value of 'x' (see SIKE, 1.3.8). + // It means that all bytes in the secret key, but the last one, can take any + // value between <0x00,0xFF>. Similarily for the last byte, but generation + // needs to chop off some bits, to make sure generated value is an element of + // a key-space. + _, err = io.ReadFull(rand, prv.Scalar) + if err != nil { + return err + } + prv.Scalar[len(prv.Scalar)-1] &= (1 << (dp.SecretBitLen % 8)) - 1 + // Make sure scalar is SecretBitLen long. SIKE spec says that key + // space starts from 0, but I'm not confortable with having low + // value scalars used for private keys. It is still secrure as per + // table 5.1 in [SIKE]. + prv.Scalar[len(prv.Scalar)-1] |= 1 << ((dp.SecretBitLen % 8) - 1) + return err +} + +// Generates public key. +// +// Constant time. +func (prv *PrivateKey) GeneratePublicKey() *PublicKey { + if (prv.keyVariant & KeyVariant_SIDH_A) == KeyVariant_SIDH_A { + return publicKeyGenA(prv) + } + return publicKeyGenB(prv) +} + +// Computes a shared secret which is a j-invariant. Function requires that pub has +// different KeyVariant than prv. Length of returned output is 2*ceil(log_2 P)/8), +// where P is a prime defining finite field. +// +// It's important to notice that each keypair must not be used more than once +// to calculate shared secret. +// +// Function may return error. This happens only in case provided input is invalid. +// Constant time for properly initialized private and public key. +func DeriveSecret(prv *PrivateKey, pub *PublicKey) ([]byte, error) { + + if (pub == nil) || (prv == nil) { + return nil, errors.New("sidh: invalid arguments") + } + + if (pub.keyVariant == prv.keyVariant) || (pub.params.Id != prv.params.Id) { + return nil, errors.New("sidh: public and private are incompatbile") + } + + if (prv.keyVariant & KeyVariant_SIDH_A) == KeyVariant_SIDH_A { + return deriveSecretA(prv, pub), nil + } else { + return deriveSecretB(prv, pub), nil + } +} + +// Uses SIKE public key to encrypt plaintext. Requires cryptographically secure PRNG +// Returns ciphertext in case encryption succeeds. Returns error in case PRNG fails +// or wrongly formated input was provided. +func Encrypt(rng io.Reader, pub *PublicKey, ptext []byte) ([]byte, error) { + var ptextLen = len(ptext) + // c1 must be security level + 64 bits (see [SIKE] 1.4 and 4.3.3) + if ptextLen != (pub.params.KemSize + 8) { + return nil, errors.New("Unsupported message length") + } + + skA := NewPrivateKey(KeyVariant_SIDH_A) + err := skA.Generate(rng) + if err != nil { + return nil, err + } + + pkA := skA.GeneratePublicKey() + return encrypt(skA, pkA, pub, ptext) +} + +// Uses SIKE private key to decrypt ciphertext. Returns plaintext in case +// decryption succeeds or error in case unexptected input was provided. +// Constant time +func Decrypt(prv *PrivateKey, ctext []byte) ([]byte, error) { + var n [40]byte // n can is max 320-bit (see 1.4 of [SIKE]) + var c1_len int + var pk_len = prv.params.PublicKeySize + + if prv.keyVariant != KeyVariant_SIKE { + return nil, errors.New("wrong key type") + } + + // ctext is a concatenation of (pubkey_A || c1=ciphertext) + // it must be security level + 64 bits (see [SIKE] 1.4 and 4.3.3) + c1_len = len(ctext) - pk_len + if c1_len != (int(prv.params.KemSize) + 8) { + return nil, errors.New("wrong size of cipher text") + } + + c0 := NewPublicKey(KeyVariant_SIDH_A) + err := c0.Import(ctext[:pk_len]) + if err != nil { + return nil, err + } + j, err := DeriveSecret(prv, c0) + if err != nil { + return nil, err + } + + hashMac(n[:c1_len], j, F) + for i, _ := range n[:c1_len] { + n[i] ^= ctext[pk_len+i] + } + return n[:c1_len], nil +} + +// Encapsulation receives the public key and generates SIKE ciphertext and shared secret. +// The generated ciphertext is used for authentication. +// The rng must be cryptographically secure PRNG. +// Error is returned in case PRNG fails or wrongly formated input was provided. +func Encapsulate(rng io.Reader, pub *PublicKey) (ctext []byte, secret []byte, err error) { + // Buffer for random, secret message + var ptext = make([]byte, pub.params.MsgLen) + // r = G(ptext||pub) + var r = make([]byte, pub.params.A.SecretByteLen) + // Resulting shared secret + secret = make([]byte, pub.params.KemSize) + + // Generate ephemeral value + _, err = io.ReadFull(rng, ptext) + if err != nil { + return nil, nil, err + } + + // must be big enough to store ptext+c0+c1 + var hmac_key = make([]byte, pub.Size()+2*Params.MsgLen) + copy(hmac_key, ptext) + copy(hmac_key[len(ptext):], pub.Export()) + hashMac(r, hmac_key[:len(ptext)+pub.Size()], G) + // Ensure bitlength is not bigger then to 2^e2-1 + r[len(r)-1] &= (1 << (pub.params.A.SecretBitLen % 8)) - 1 + + // (c0 || c1) = Enc(pkA, ptext; r) + skA := NewPrivateKey(KeyVariant_SIDH_A) + err = skA.Import(r) + if err != nil { + return nil, nil, err + } + + pkA := skA.GeneratePublicKey() + ctext, err = encrypt(skA, pkA, pub, ptext) + if err != nil { + return nil, nil, err + } + + // K = H(ptext||(c0||c1)) + copy(hmac_key, ptext) + copy(hmac_key[len(ptext):], ctext) + hashMac(secret, hmac_key[:len(ptext)+len(ctext)], H) + return ctext, secret, nil +} + +// Decapsulate given the keypair and ciphertext as inputs, Decapsulate outputs a shared +// secret if plaintext verifies correctly, otherwise function outputs random value. +// Decapsulation may fail in case input is wrongly formated. +// Constant time for properly initialized input. +func Decapsulate(prv *PrivateKey, pub *PublicKey, ctext []byte) ([]byte, error) { + var r = make([]byte, pub.params.A.SecretByteLen) + // Resulting shared secret + var secret = make([]byte, pub.params.KemSize) + var skA = NewPrivateKey(KeyVariant_SIDH_A) + + m, err := Decrypt(prv, ctext) + if err != nil { + return nil, err + } + + // r' = G(m'||pub) + var hmac_key = make([]byte, pub.Size()+2*Params.MsgLen) + copy(hmac_key, m) + copy(hmac_key[len(m):], pub.Export()) + hashMac(r, hmac_key[:len(m)+pub.Size()], G) + // Ensure bitlength is not bigger than 2^e2-1 + r[len(r)-1] &= (1 << (pub.params.A.SecretBitLen % 8)) - 1 + + // Never fails + skA.Import(r) + + // Never fails + pkA := skA.GeneratePublicKey() + c0 := pkA.Export() + + if subtle.ConstantTimeCompare(c0, ctext[:len(c0)]) == 1 { + copy(hmac_key, m) + } else { + // S is chosen at random when generating a key and unknown to other party. It + // may seem weird, but it's correct. It is important that S is unpredictable + // to other party. Without this check, it is possible to recover a secret, by + // providing series of invalid ciphertexts. It is also important that in case + // + // See more details in "On the security of supersingular isogeny cryptosystems" + // (S. Galbraith, et al., 2016, ePrint #859). + copy(hmac_key, prv.S) + } + copy(hmac_key[len(m):], ctext) + hashMac(secret, hmac_key[:len(m)+len(ctext)], H) + return secret, nil +}
diff --git a/ssl/test/runner/sike/sike_test.go b/ssl/test/runner/sike/sike_test.go new file mode 100644 index 0000000..76ef59e --- /dev/null +++ b/ssl/test/runner/sike/sike_test.go
@@ -0,0 +1,694 @@ +// Copyright (c) 2019, Cloudflare Inc. +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY +// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION +// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN +// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + +package sike + +import ( + "bufio" + "bytes" + "crypto/rand" + "encoding/hex" + "math/big" + "strings" + "testing" +) + +var tdata = struct { + name string + PrB_sidh string + PkB_sidh string + PkB_sike string + PrB_sike string + PrA_sike string + PkA_sike string +}{ + name: "P-503", + PkB_sike: "68460C22466E95864CFEA7B5D9077E768FF4F9ED69AE56D7CF3F236FB06B31020EEE34B5B572CEA5DDF20B531966AA8F5F3ACC0C6D1CE04EEDC30FD1F1233E2D96FE60C6D638FC646EAF2E2246F1AEC96859CE874A1F029A78F9C978CD6B22114A0D5AB20101191FD923E80C76908B1498B9D0200065CCA09159A0C65A1E346CC6470314FE78388DAA89DD08EC67DBE63C1F606674ACC49EBF9FDBB2B898B3CE733113AA6F942DB401A76D629CE6EE6C0FDAF4CFB1A5E366DB66C17B3923A1B7FB26A3FF25B9018869C674D3DEF4AF269901D686FE4647F9D2CDB2CEB3AFA305B27C885F037ED167F595066C21E7DD467D8332B934A5102DA5F13332DFA356B82156A0BB2E7E91C6B85B7D1E381BC9E3F0FC4DB9C36016D9ECEC415D7E977E9AC29910D934BA2FE4EE49D3B387607A4E1AFABF495FB86A77194626589E802FF5167C7A25C542C1EAD25A6E0AA931D94F2F9AFD3DBDF222E651F729A90E77B20974905F1E65E041CE6C95AAB3E1F22D332E0A5DE9C5DB3D9C7A38", + PrB_sike: "80FC55DA74DEFE3113487B80841E678AF9ED4E0599CF07353A4AB93971C090A0" + + "A9402C9DC98AC6DC8F5FDE5E970AE22BA48A400EFC72851C", + PrB_sidh: "A885A8B889520A6DBAD9FB33365E5B77FDED629440A16A533F259A510F63A822", + PrA_sike: "B0AD510708F4ABCF3E0D97DC2F2FF112D9D2AAE49D97FFD1E4267F21C6E71C03", + PkA_sike: "A6BADBA04518A924B20046B59AC197DCDF0EA48014C9E228C4994CCA432F360E" + + "2D527AFB06CA7C96EE5CEE19BAD53BF9218A3961CAD7EC092BD8D9EBB22A3D51" + + "33008895A3F1F6A023F91E0FE06A00A622FD6335DAC107F8EC4283DC2632F080" + + "4E64B390DAD8A2572F1947C67FDF4F8787D140CE2C6B24E752DA9A195040EDFA" + + "C27333FAE97DBDEB41DA9EEB2DB067AE7DA8C58C0EF57AEFC18A3D6BD0576FF2" + + "F1CFCAEC50C958331BF631F3D2E769790C7B6DF282B74BBC02998AD10F291D47" + + "C5A762FF84253D3B3278BDF20C8D4D4AA317BE401B884E26A1F02C7308AADB68" + + "20EBDB0D339F5A63346F3B40CACED72F544DAF51566C6E807D0E6E1E38514342" + + "432661DC9564DA07548570E256688CD9E8060D8775F95D501886D958588CACA0" + + "9F2D2AE1913F996E76AF63E31A179A7A7D2A46EDA03B2BCCF9020A5AA15F9A28" + + "9340B33F3AE7F97360D45F8AE1B9DD48779A57E8C45B50A02C00349CD1C58C55" + + "1D68BC2A75EAFED944E8C599C288037181E997471352E24C952B", + PkB_sidh: "244AF1F367C2C33912750A98497CC8214BC195BD52BD76513D32ACE4B75E31F0" + + "281755C265F5565C74E3C04182B9C244071859C8588CC7F09547CEFF8F7705D2" + + "60CE87D6BFF914EE7DBE4B9AF051CA420062EEBDF043AF58184495026949B068" + + "98A47046BFAE8DF3B447746184AF550553BB5D266D6E1967ACA33CAC5F399F90" + + "360D70867F2C71EF6F94FF915C7DA8BC9549FB7656E691DAEFC93CF56876E482" + + "CA2F8BE2D6CDCC374C31AD8833CABE997CC92305F38497BEC4DFD1821B004FEC" + + "E16448F9A24F965EFE409A8939EEA671633D9FFCF961283E59B8834BDF7EDDB3" + + "05D6275B61DA6692325432A0BAA074FC7C1F51E76208AB193A57520D40A76334" + + "EE5712BDC3E1EFB6103966F2329EDFF63082C4DFCDF6BE1C5A048630B81871B8" + + "83B735748A8FD4E2D9530C272163AB18105B10015CA7456202FE1C9B92CEB167" + + "5EAE1132E582C88E47ED87B363D45F05BEA714D5E9933D7AF4071CBB5D49008F" + + "3E3DAD7DFF935EE509D5DE561842B678CCEB133D62E270E9AC3E", +} + +/* ------------------------------------------------------------------------- + Helpers + -------------------------------------------------------------------------*/ +// Fail if err !=nil. Display msg as an error message +func checkErr(t testing.TB, err error, msg string) { + if err != nil { + t.Error(msg) + } +} + +// Utility used for running same test with all registered prime fields +type MultiIdTestingFunc func(testing.TB) + +// Converts string to private key +func convToPrv(s string, v KeyVariant) *PrivateKey { + key := NewPrivateKey(v) + hex, e := hex.DecodeString(s) + if e != nil { + panic("non-hex number provided") + } + e = key.Import(hex) + if e != nil { + panic("Can't import private key") + } + return key +} + +// Converts string to public key +func convToPub(s string, v KeyVariant) *PublicKey { + key := NewPublicKey(v) + hex, e := hex.DecodeString(s) + if e != nil { + panic("non-hex number provided") + } + e = key.Import(hex) + if e != nil { + panic("Can't import public key") + } + return key +} + +/* ------------------------------------------------------------------------- + Unit tests + -------------------------------------------------------------------------*/ +func TestKeygen(t *testing.T) { + alicePrivate := convToPrv(tdata.PrA_sike, KeyVariant_SIDH_A) + bobPrivate := convToPrv(tdata.PrB_sidh, KeyVariant_SIDH_B) + expPubA := convToPub(tdata.PkA_sike, KeyVariant_SIDH_A) + expPubB := convToPub(tdata.PkB_sidh, KeyVariant_SIDH_B) + + pubA := alicePrivate.GeneratePublicKey() + pubB := bobPrivate.GeneratePublicKey() + + if !bytes.Equal(pubA.Export(), expPubA.Export()) { + t.Fatalf("unexpected value of public key A") + } + if !bytes.Equal(pubB.Export(), expPubB.Export()) { + t.Fatalf("unexpected value of public key B") + } +} + +func TestImportExport(t *testing.T) { + var err error + a := NewPublicKey(KeyVariant_SIDH_A) + b := NewPublicKey(KeyVariant_SIDH_B) + + // Import keys + a_hex, err := hex.DecodeString(tdata.PkA_sike) + checkErr(t, err, "invalid hex-number provided") + + err = a.Import(a_hex) + checkErr(t, err, "import failed") + + b_hex, err := hex.DecodeString(tdata.PkB_sike) + checkErr(t, err, "invalid hex-number provided") + + err = b.Import(b_hex) + checkErr(t, err, "import failed") + + // Export and check if same + if !bytes.Equal(b.Export(), b_hex) || !bytes.Equal(a.Export(), a_hex) { + t.Fatalf("export/import failed") + } + + if (len(b.Export()) != b.Size()) || (len(a.Export()) != a.Size()) { + t.Fatalf("wrong size of exported keys") + } +} + +func testPrivateKeyBelowMax(t testing.TB) { + for variant, keySz := range map[KeyVariant]*DomainParams{ + KeyVariant_SIDH_A: &Params.A, + KeyVariant_SIDH_B: &Params.B} { + + func(v KeyVariant, dp *DomainParams) { + var blen = int(dp.SecretByteLen) + var prv = NewPrivateKey(v) + + // Calculate either (2^e2 - 1) or (2^s - 1); where s=ceil(log_2(3^e3))) + maxSecertVal := big.NewInt(int64(dp.SecretBitLen)) + maxSecertVal.Exp(big.NewInt(int64(2)), maxSecertVal, nil) + maxSecertVal.Sub(maxSecertVal, big.NewInt(1)) + + // Do same test 1000 times + for i := 0; i < 1000; i++ { + err := prv.Generate(rand.Reader) + checkErr(t, err, "Private key generation") + + // Convert to big-endian, as that's what expected by (*Int)SetBytes() + secretBytes := prv.Export() + for i := 0; i < int(blen/2); i++ { + tmp := secretBytes[i] ^ secretBytes[blen-i-1] + secretBytes[i] = tmp ^ secretBytes[i] + secretBytes[blen-i-1] = tmp ^ secretBytes[blen-i-1] + } + prvBig := new(big.Int).SetBytes(secretBytes) + // Check if generated key is bigger then acceptable + if prvBig.Cmp(maxSecertVal) == 1 { + t.Error("Generated private key is wrong") + } + } + }(variant, keySz) + } +} + +func testKeyAgreement(t *testing.T, pkA, prA, pkB, prB string) { + var e error + + // KeyPairs + alicePublic := convToPub(pkA, KeyVariant_SIDH_A) + bobPublic := convToPub(pkB, KeyVariant_SIDH_B) + alicePrivate := convToPrv(prA, KeyVariant_SIDH_A) + bobPrivate := convToPrv(prB, KeyVariant_SIDH_B) + + // Do actual test + s1, e := DeriveSecret(bobPrivate, alicePublic) + checkErr(t, e, "derivation s1") + s2, e := DeriveSecret(alicePrivate, bobPublic) + checkErr(t, e, "derivation s1") + + if !bytes.Equal(s1[:], s2[:]) { + t.Fatalf("two shared keys: %d, %d do not match", s1, s2) + } + + // Negative case + dec, e := hex.DecodeString(tdata.PkA_sike) + if e != nil { + t.FailNow() + } + dec[0] = ^dec[0] + e = alicePublic.Import(dec) + if e != nil { + t.FailNow() + } + + s1, e = DeriveSecret(bobPrivate, alicePublic) + checkErr(t, e, "derivation of s1 failed") + s2, e = DeriveSecret(alicePrivate, bobPublic) + checkErr(t, e, "derivation of s2 failed") + + if bytes.Equal(s1[:], s2[:]) { + t.Fatalf("The two shared keys: %d, %d match", s1, s2) + } +} + +func TestDerivationRoundTrip(t *testing.T) { + var err error + + prvA := NewPrivateKey(KeyVariant_SIDH_A) + prvB := NewPrivateKey(KeyVariant_SIDH_B) + + // Generate private keys + err = prvA.Generate(rand.Reader) + checkErr(t, err, "key generation failed") + err = prvB.Generate(rand.Reader) + checkErr(t, err, "key generation failed") + + // Generate public keys + pubA := prvA.GeneratePublicKey() + pubB := prvB.GeneratePublicKey() + + // Derive shared secret + s1, err := DeriveSecret(prvB, pubA) + checkErr(t, err, "") + + s2, err := DeriveSecret(prvA, pubB) + checkErr(t, err, "") + + if !bytes.Equal(s1[:], s2[:]) { + t.Fatalf("Two shared keys: \n%X, \n%X do not match", s1, s2) + } +} + +// Encrypt, Decrypt, check if input/output plaintext is the same +func testPKERoundTrip(t testing.TB, id uint8) { + // Message to be encrypted + var msg = make([]byte, Params.MsgLen) + for i, _ := range msg { + msg[i] = byte(i) + } + + // Import keys + pkB := NewPublicKey(KeyVariant_SIKE) + skB := NewPrivateKey(KeyVariant_SIKE) + pk_hex, err := hex.DecodeString(tdata.PkB_sike) + if err != nil { + t.Fatal(err) + } + sk_hex, err := hex.DecodeString(tdata.PrB_sike) + if err != nil { + t.Fatal(err) + } + if pkB.Import(pk_hex) != nil || skB.Import(sk_hex) != nil { + t.Error("Import") + } + + ct, err := Encrypt(rand.Reader, pkB, msg[:]) + if err != nil { + t.Fatal(err) + } + pt, err := Decrypt(skB, ct) + if err != nil { + t.Fatal(err) + } + if !bytes.Equal(pt[:], msg[:]) { + t.Errorf("Decryption failed \n got : %X\n exp : %X", pt, msg) + } +} + +// Generate key and check if can encrypt +func TestPKEKeyGeneration(t *testing.T) { + // Message to be encrypted + var msg = make([]byte, Params.MsgLen) + var err error + for i, _ := range msg { + msg[i] = byte(i) + } + + sk := NewPrivateKey(KeyVariant_SIKE) + err = sk.Generate(rand.Reader) + checkErr(t, err, "PEK key generation") + pk := sk.GeneratePublicKey() + + // Try to encrypt + ct, err := Encrypt(rand.Reader, pk, msg[:]) + checkErr(t, err, "PEK encryption") + pt, err := Decrypt(sk, ct) + checkErr(t, err, "PEK key decryption") + + if !bytes.Equal(pt[:], msg[:]) { + t.Fatalf("Decryption failed \n got : %X\n exp : %X", pt, msg) + } +} + +func TestNegativePKE(t *testing.T) { + var msg [40]byte + var err error + + // Generate key + sk := NewPrivateKey(KeyVariant_SIKE) + err = sk.Generate(rand.Reader) + checkErr(t, err, "key generation") + + pk := sk.GeneratePublicKey() + + // bytelen(msg) - 1 + ct, err := Encrypt(rand.Reader, pk, msg[:Params.KemSize+8-1]) + if err == nil { + t.Fatal("Error hasn't been returned") + } + if ct != nil { + t.Fatal("Ciphertext must be nil") + } + + // KemSize - 1 + pt, err := Decrypt(sk, msg[:Params.KemSize+8-1]) + if err == nil { + t.Fatal("Error hasn't been returned") + } + if pt != nil { + t.Fatal("Ciphertext must be nil") + } +} + +func testKEMRoundTrip(t *testing.T, pkB, skB []byte) { + // Import keys + pk := NewPublicKey(KeyVariant_SIKE) + sk := NewPrivateKey(KeyVariant_SIKE) + if pk.Import(pkB) != nil || sk.Import(skB) != nil { + t.Error("Import failed") + } + + ct, ss_e, err := Encapsulate(rand.Reader, pk) + if err != nil { + t.Error("Encapsulate failed") + } + + ss_d, err := Decapsulate(sk, pk, ct) + if err != nil { + t.Error("Decapsulate failed") + } + if !bytes.Equal(ss_e, ss_d) { + t.Error("Shared secrets from decapsulation and encapsulation differ") + } +} + +func TestKEMRoundTrip(t *testing.T) { + pk, err := hex.DecodeString(tdata.PkB_sike) + checkErr(t, err, "public key B not a number") + sk, err := hex.DecodeString(tdata.PrB_sike) + checkErr(t, err, "private key B not a number") + testKEMRoundTrip(t, pk, sk) +} + +func TestKEMKeyGeneration(t *testing.T) { + // Generate key + sk := NewPrivateKey(KeyVariant_SIKE) + checkErr(t, sk.Generate(rand.Reader), "error: key generation") + pk := sk.GeneratePublicKey() + + // calculated shared secret + ct, ss_e, err := Encapsulate(rand.Reader, pk) + checkErr(t, err, "encapsulation failed") + ss_d, err := Decapsulate(sk, pk, ct) + checkErr(t, err, "decapsulation failed") + + if !bytes.Equal(ss_e, ss_d) { + t.Fatalf("KEM failed \n encapsulated: %X\n decapsulated: %X", ss_d, ss_e) + } +} + +func TestNegativeKEM(t *testing.T) { + sk := NewPrivateKey(KeyVariant_SIKE) + checkErr(t, sk.Generate(rand.Reader), "error: key generation") + pk := sk.GeneratePublicKey() + + ct, ss_e, err := Encapsulate(rand.Reader, pk) + checkErr(t, err, "pre-requisite for a test failed") + + ct[0] = ct[0] - 1 + ss_d, err := Decapsulate(sk, pk, ct) + checkErr(t, err, "decapsulation returns error when invalid ciphertext provided") + + if bytes.Equal(ss_e, ss_d) { + // no idea how this could ever happen, but it would be very bad + t.Error("critical error") + } + + // Try encapsulating with SIDH key + pkSidh := NewPublicKey(KeyVariant_SIDH_B) + prSidh := NewPrivateKey(KeyVariant_SIDH_B) + _, _, err = Encapsulate(rand.Reader, pkSidh) + if err == nil { + t.Error("encapsulation accepts SIDH public key") + } + // Try decapsulating with SIDH key + _, err = Decapsulate(prSidh, pk, ct) + if err == nil { + t.Error("decapsulation accepts SIDH private key key") + } +} + +// In case invalid ciphertext is provided, SIKE's decapsulation must +// return same (but unpredictable) result for a given key. +func TestNegativeKEMSameWrongResult(t *testing.T) { + sk := NewPrivateKey(KeyVariant_SIKE) + checkErr(t, sk.Generate(rand.Reader), "error: key generation") + pk := sk.GeneratePublicKey() + + ct, encSs, err := Encapsulate(rand.Reader, pk) + checkErr(t, err, "pre-requisite for a test failed") + + // make ciphertext wrong + ct[0] = ct[0] - 1 + decSs1, err := Decapsulate(sk, pk, ct) + checkErr(t, err, "pre-requisite for a test failed") + + // second decapsulation must be done with same, but imported private key + expSk := sk.Export() + + // creat new private key + sk = NewPrivateKey(KeyVariant_SIKE) + err = sk.Import(expSk) + checkErr(t, err, "import failed") + + // try decapsulating again. ss2 must be same as ss1 and different than + // original plaintext + decSs2, err := Decapsulate(sk, pk, ct) + checkErr(t, err, "pre-requisite for a test failed") + + if !bytes.Equal(decSs1, decSs2) { + t.Error("decapsulation is insecure") + } + + if bytes.Equal(encSs, decSs1) || bytes.Equal(encSs, decSs2) { + // this test requires that decapsulation returns wrong result + t.Errorf("test implementation error") + } +} + +func readAndCheckLine(r *bufio.Reader) []byte { + // Read next line from buffer + line, isPrefix, err := r.ReadLine() + if err != nil || isPrefix { + panic("Wrong format of input file") + } + + // Function expects that line is in format "KEY = HEX_VALUE". Get + // value, which should be a hex string + hexst := strings.Split(string(line), "=")[1] + hexst = strings.TrimSpace(hexst) + // Convert value to byte string + ret, err := hex.DecodeString(hexst) + if err != nil { + panic("Wrong format of input file") + } + return ret +} + +func testKeygenSIKE(pk, sk []byte, id uint8) bool { + // Import provided private key + var prvKey = NewPrivateKey(KeyVariant_SIKE) + if prvKey.Import(sk) != nil { + panic("sike test: can't load KAT") + } + + // Generate public key + pubKey := prvKey.GeneratePublicKey() + return bytes.Equal(pubKey.Export(), pk) +} + +func testDecapsulation(pk, sk, ct, ssExpected []byte, id uint8) bool { + var pubKey = NewPublicKey(KeyVariant_SIKE) + var prvKey = NewPrivateKey(KeyVariant_SIKE) + if pubKey.Import(pk) != nil || prvKey.Import(sk) != nil { + panic("sike test: can't load KAT") + } + + ssGot, err := Decapsulate(prvKey, pubKey, ct) + if err != nil { + panic("sike test: can't perform degcapsulation KAT") + } + + if err != nil { + return false + } + return bytes.Equal(ssGot, ssExpected) +} + +func TestKeyAgreement(t *testing.T) { + testKeyAgreement(t, tdata.PkA_sike, tdata.PrA_sike, tdata.PkB_sidh, tdata.PrB_sidh) +} + +// Same values as in sike_test.cc +func TestDecapsulation(t *testing.T) { + + var sk = [56]byte{ + 0xDB, 0xAF, 0x2C, 0x89, 0xCA, 0x5A, 0xD4, 0x9D, 0x4F, 0x13, + 0x40, 0xDF, 0x2D, 0xB1, 0x5F, 0x4C, 0x91, 0xA7, 0x1F, 0x0B, + 0x29, 0x15, 0x01, 0x59, 0xBC, 0x5F, 0x0B, 0x4A, 0x03, 0x27, + 0x6F, 0x18} + + var pk = []byte{ + 0x07, 0xAA, 0x51, 0x45, 0x3E, 0x1F, 0x53, 0x2A, 0x0A, 0x05, + 0x46, 0xF6, 0x54, 0x7F, 0x5D, 0x56, 0xD6, 0x76, 0xD3, 0xEA, + 0x4B, 0x6B, 0x01, 0x9B, 0x11, 0x72, 0x6F, 0x75, 0xEA, 0x34, + 0x3C, 0x28, 0x2C, 0x36, 0xFD, 0x77, 0xDA, 0xBE, 0xB6, 0x20, + 0x18, 0xC1, 0x93, 0x98, 0x18, 0x86, 0x30, 0x2F, 0x2E, 0xD2, + 0x00, 0x61, 0xFF, 0xAE, 0x78, 0xAE, 0xFB, 0x6F, 0x32, 0xAC, + 0x06, 0xBF, 0x35, 0xF6, 0xF7, 0x5B, 0x98, 0x26, 0x95, 0xC2, + 0xD8, 0xD6, 0x1C, 0x0E, 0x47, 0xDA, 0x76, 0xCE, 0xB5, 0xF1, + 0x19, 0xCC, 0x01, 0xE1, 0x17, 0xA9, 0x62, 0xF7, 0x82, 0x6C, + 0x25, 0x51, 0x25, 0xAE, 0xFE, 0xE3, 0xE2, 0xE1, 0x35, 0xAE, + 0x2E, 0x8F, 0x38, 0xE0, 0x7C, 0x74, 0x3C, 0x1D, 0x39, 0x91, + 0x1B, 0xC7, 0x9F, 0x8E, 0x33, 0x4E, 0x84, 0x19, 0xB8, 0xD9, + 0xC2, 0x71, 0x35, 0x02, 0x47, 0x3E, 0x79, 0xEF, 0x47, 0xE1, + 0xD8, 0x21, 0x96, 0x1F, 0x11, 0x59, 0x39, 0x34, 0x76, 0xEF, + 0x3E, 0xB7, 0x4E, 0xFB, 0x7C, 0x55, 0xA1, 0x85, 0xAA, 0xAB, + 0xAD, 0xF0, 0x09, 0xCB, 0xD1, 0xE3, 0x7C, 0x4F, 0x5D, 0x2D, + 0xE1, 0x13, 0xF0, 0x71, 0xD9, 0xE5, 0xF6, 0xAF, 0x7F, 0xC1, + 0x27, 0x95, 0x8D, 0x52, 0xD5, 0x96, 0x42, 0x38, 0x41, 0xF7, + 0x24, 0x3F, 0x3A, 0xB5, 0x7E, 0x11, 0xE4, 0xF9, 0x33, 0xEE, + 0x4D, 0xBE, 0x74, 0x48, 0xF9, 0x98, 0x04, 0x01, 0x16, 0xEB, + 0xA9, 0x0D, 0x61, 0xC6, 0xFD, 0x4C, 0xCF, 0x98, 0x84, 0x4A, + 0x94, 0xAC, 0x69, 0x2C, 0x02, 0x8B, 0xE3, 0xD1, 0x41, 0x0D, + 0xF2, 0x2D, 0x46, 0x1F, 0x57, 0x1C, 0x77, 0x86, 0x18, 0xE3, + 0x63, 0xDE, 0xF3, 0xE3, 0x02, 0x30, 0x54, 0x73, 0xAE, 0xC2, + 0x32, 0xA2, 0xCE, 0xEB, 0xCF, 0x81, 0x46, 0x54, 0x5C, 0xF4, + 0x5D, 0x2A, 0x03, 0x5D, 0x9C, 0xAE, 0xE0, 0x60, 0x03, 0x80, + 0x11, 0x30, 0xA5, 0xAA, 0xD1, 0x75, 0x67, 0xE0, 0x1C, 0x2B, + 0x6B, 0x5D, 0x83, 0xDE, 0x92, 0x9B, 0x0E, 0xD7, 0x11, 0x0F, + 0x00, 0xC4, 0x59, 0xE4, 0x81, 0x04, 0x3B, 0xEE, 0x5C, 0x04, + 0xD1, 0x0E, 0xD0, 0x67, 0xF5, 0xCC, 0xAA, 0x72, 0x73, 0xEA, + 0xC4, 0x76, 0x99, 0x3B, 0x4C, 0x90, 0x2F, 0xCB, 0xD8, 0x0A, + 0x5B, 0xEC, 0x0E, 0x0E, 0x1F, 0x59, 0xEA, 0x14, 0x8D, 0x34, + 0x53, 0x65, 0x4C, 0x1A, 0x59, 0xA8, 0x95, 0x66, 0x60, 0xBB, + 0xC4, 0xCC, 0x32, 0xA9, 0x8D, 0x2A, 0xAA, 0x14, 0x6F, 0x0F, + 0x81, 0x4D, 0x32, 0x02, 0xFD, 0x33, 0x58, 0x42, 0xCF, 0xF3, + 0x67, 0xD0, 0x9F, 0x0B, 0xB1, 0xCC, 0x18, 0xA5, 0xC4, 0x19, + 0xB6, 0x00, 0xED, 0xFA, 0x32, 0x1A, 0x5F, 0x67, 0xC8, 0xC3, + 0xEB, 0x0D, 0xB5, 0x9A, 0x36, 0x47, 0x82, 0x00, + } + + var ct = []byte{ + 0xE6, 0xB7, 0xE5, 0x7B, 0xA9, 0x19, 0xD1, 0x2C, 0xB8, 0x5C, + 0x7B, 0x66, 0x74, 0xB0, 0x71, 0xA1, 0xFF, 0x71, 0x7F, 0x4B, + 0xB5, 0xA6, 0xAF, 0x48, 0x32, 0x52, 0xD5, 0x82, 0xEE, 0x8A, + 0xBB, 0x08, 0x1E, 0xF6, 0xAC, 0x91, 0xA2, 0xCB, 0x6B, 0x6A, + 0x09, 0x2B, 0xD9, 0xC6, 0x27, 0xD6, 0x3A, 0x6B, 0x8D, 0xFC, + 0xB8, 0x90, 0x8F, 0x72, 0xB3, 0xFA, 0x7D, 0x34, 0x7A, 0xC4, + 0x7E, 0xE3, 0x30, 0xC5, 0xA0, 0xFE, 0x3D, 0x43, 0x14, 0x4E, + 0x3A, 0x14, 0x76, 0x3E, 0xFB, 0xDF, 0xE3, 0xA8, 0xE3, 0x5E, + 0x38, 0xF2, 0xE0, 0x39, 0x67, 0x60, 0xFD, 0xFB, 0xB4, 0x19, + 0xCD, 0xE1, 0x93, 0xA2, 0x06, 0xCC, 0x65, 0xCD, 0x6E, 0xC8, + 0xB4, 0x5E, 0x41, 0x4B, 0x6C, 0xA5, 0xF4, 0xE4, 0x9D, 0x52, + 0x8C, 0x25, 0x60, 0xDD, 0x3D, 0xA9, 0x7F, 0xF2, 0x88, 0xC1, + 0x0C, 0xEE, 0x97, 0xE0, 0xE7, 0x3B, 0xB7, 0xD3, 0x6F, 0x28, + 0x79, 0x2F, 0x50, 0xB2, 0x4F, 0x74, 0x3A, 0x0C, 0x88, 0x27, + 0x98, 0x3A, 0x27, 0xD3, 0x26, 0x83, 0x59, 0x49, 0x81, 0x5B, + 0x0D, 0xA7, 0x0C, 0x4F, 0xEF, 0xFB, 0x1E, 0xAF, 0xE9, 0xD2, + 0x1C, 0x10, 0x25, 0xEC, 0x9E, 0xFA, 0x57, 0x36, 0xAA, 0x3F, + 0xC1, 0xA3, 0x2C, 0xE9, 0xB5, 0xC9, 0xED, 0x72, 0x51, 0x4C, + 0x02, 0xB4, 0x7B, 0xB3, 0xED, 0x9F, 0x45, 0x03, 0x34, 0xAC, + 0x9A, 0x9E, 0x62, 0x5F, 0x82, 0x7A, 0x77, 0x34, 0xF9, 0x21, + 0x94, 0xD2, 0x38, 0x3D, 0x05, 0xF0, 0x8A, 0x60, 0x1C, 0xB7, + 0x1D, 0xF5, 0xB7, 0x53, 0x77, 0xD3, 0x9D, 0x3D, 0x70, 0x6A, + 0xCB, 0x18, 0x20, 0x6B, 0x29, 0x17, 0x3A, 0x6D, 0xA1, 0xB2, + 0x64, 0xDB, 0x6C, 0xE6, 0x1A, 0x95, 0xA7, 0xF4, 0x1A, 0x78, + 0x1D, 0xA2, 0x40, 0x15, 0x41, 0x59, 0xDD, 0xEE, 0x23, 0x57, + 0xCE, 0x36, 0x0D, 0x55, 0xBD, 0xB8, 0xFD, 0x0F, 0x35, 0xBD, + 0x5B, 0x92, 0xD6, 0x1C, 0x84, 0x8C, 0x32, 0x64, 0xA6, 0x5C, + 0x45, 0x18, 0x07, 0x6B, 0xF9, 0xA9, 0x43, 0x9A, 0x83, 0xCD, + 0xB5, 0xB3, 0xD9, 0x17, 0x99, 0x2C, 0x2A, 0x8B, 0xE0, 0x8E, + 0xAF, 0xA6, 0x4C, 0x95, 0xBB, 0x70, 0x60, 0x1A, 0x3A, 0x97, + 0xAA, 0x2F, 0x3D, 0x22, 0x83, 0xB7, 0x4F, 0x59, 0xED, 0x3F, + 0x4E, 0xF4, 0x19, 0xC6, 0x25, 0x0B, 0x0A, 0x5E, 0x21, 0xB9, + 0x91, 0xB8, 0x19, 0x84, 0x48, 0x78, 0xCE, 0x27, 0xBF, 0x41, + 0x89, 0xF6, 0x30, 0xFD, 0x6B, 0xD9, 0xB8, 0x1D, 0x72, 0x8A, + 0x56, 0xCC, 0x2F, 0x82, 0xE4, 0x46, 0x4D, 0x75, 0xD8, 0x92, + 0xE6, 0x9C, 0xCC, 0xD2, 0xCD, 0x35, 0xE4, 0xFC, 0x2A, 0x85, + 0x6B, 0xA9, 0xB2, 0x27, 0xC9, 0xA1, 0xFF, 0xB3, 0x96, 0x3E, + 0x59, 0xF6, 0x4C, 0x66, 0x56, 0x2E, 0xF5, 0x1B, 0x97, 0x32, + 0xB0, 0x71, 0x5A, 0x9C, 0x50, 0x4B, 0x6F, 0xC4, 0xCA, 0x94, + 0x75, 0x37, 0x46, 0x10, 0x12, 0x2F, 0x4F, 0xA3, 0x82, 0xCD, + 0xBD, 0x7C, + } + var ss_exp = []byte{ + 0x74, 0x3D, 0x25, 0x36, 0x00, 0x24, 0x63, 0x1A, 0x39, 0x1A, + 0xB4, 0xAD, 0x01, 0x17, 0x78, 0xE9} + + var prvObj = NewPrivateKey(KeyVariant_SIKE) + var pubObj = NewPublicKey(KeyVariant_SIKE) + + if pubObj.Import(pk) != nil || prvObj.Import(sk[:]) != nil { + t.Error("Can't import one of the keys") + } + + res, _ := Decapsulate(prvObj, pubObj, ct) + if !bytes.Equal(ss_exp, res) { + t.Error("Wrong decapsulation result") + } +} + +/* ------------------------------------------------------------------------- + Benchmarking + -------------------------------------------------------------------------*/ + +func BenchmarkSidhKeyAgreementP503(b *testing.B) { + // KeyPairs + alicePublic := convToPub(tdata.PkA_sike, KeyVariant_SIDH_A) + alicePrivate := convToPrv(tdata.PrA_sike, KeyVariant_SIDH_A) + bobPublic := convToPub(tdata.PkB_sidh, KeyVariant_SIDH_B) + bobPrivate := convToPrv(tdata.PrB_sidh, KeyVariant_SIDH_B) + + for i := 0; i < b.N; i++ { + // Derive shared secret + DeriveSecret(bobPrivate, alicePublic) + DeriveSecret(alicePrivate, bobPublic) + } +} + +func BenchmarkAliceKeyGenPrvP503(b *testing.B) { + prv := NewPrivateKey(KeyVariant_SIDH_A) + for n := 0; n < b.N; n++ { + prv.Generate(rand.Reader) + } +} + +func BenchmarkBobKeyGenPrvP503(b *testing.B) { + prv := NewPrivateKey(KeyVariant_SIDH_B) + for n := 0; n < b.N; n++ { + prv.Generate(rand.Reader) + } +} + +func BenchmarkAliceKeyGenPubP503(b *testing.B) { + prv := NewPrivateKey(KeyVariant_SIDH_A) + prv.Generate(rand.Reader) + for n := 0; n < b.N; n++ { + prv.GeneratePublicKey() + } +} + +func BenchmarkBobKeyGenPubP503(b *testing.B) { + prv := NewPrivateKey(KeyVariant_SIDH_B) + prv.Generate(rand.Reader) + for n := 0; n < b.N; n++ { + prv.GeneratePublicKey() + } +} + +func BenchmarkSharedSecretAliceP503(b *testing.B) { + aPr := convToPrv(tdata.PrA_sike, KeyVariant_SIDH_A) + bPk := convToPub(tdata.PkB_sike, KeyVariant_SIDH_B) + for n := 0; n < b.N; n++ { + DeriveSecret(aPr, bPk) + } +} + +func BenchmarkSharedSecretBobP503(b *testing.B) { + // m_B = 3*randint(0,3^238) + aPk := convToPub(tdata.PkA_sike, KeyVariant_SIDH_A) + bPr := convToPrv(tdata.PrB_sidh, KeyVariant_SIDH_B) + for n := 0; n < b.N; n++ { + DeriveSecret(bPr, aPk) + } +}
diff --git a/ssl/test/test_config.cc b/ssl/test/test_config.cc index 7b4f2c4..4a25b1a 100644 --- a/ssl/test/test_config.cc +++ b/ssl/test/test_config.cc
@@ -1620,6 +1620,9 @@ case SSL_CURVE_CECPQ2: nids.push_back(NID_CECPQ2); break; + case SSL_CURVE_CECPQ2b: + nids.push_back(NID_CECPQ2b); + break; } if (!SSL_set1_curves(ssl.get(), &nids[0], nids.size())) { return nullptr; @@ -1628,8 +1631,8 @@ } if (enable_all_curves) { static const int kAllCurves[] = { - NID_secp224r1, NID_X9_62_prime256v1, NID_secp384r1, - NID_secp521r1, NID_X25519, NID_CECPQ2, + NID_secp224r1, NID_X9_62_prime256v1, NID_secp384r1, NID_secp521r1, + NID_X25519, NID_CECPQ2, NID_CECPQ2b, }; if (!SSL_set1_curves(ssl.get(), kAllCurves, OPENSSL_ARRAY_SIZE(kAllCurves))) {
diff --git a/ssl/tls13_server.cc b/ssl/tls13_server.cc index 8f31704..8fb0d5c 100644 --- a/ssl/tls13_server.cc +++ b/ssl/tls13_server.cc
@@ -109,7 +109,8 @@ public: CipherScorer(uint16_t group_id) : aes_is_fine_(EVP_has_aes_hardware()), - security_128_is_fine_(group_id != SSL_CURVE_CECPQ2) {} + security_128_is_fine_(group_id != SSL_CURVE_CECPQ2 && + group_id != SSL_CURVE_CECPQ2b) {} typedef std::tuple<bool, bool, bool> Score;