HRSS: omit reconstruction of ciphertext. In [1], section 5.1, an optimised re-encryption process is given. In the code, this simplifies to not needing to rebuild the ciphertext at all. Thanks to John Schanck for pointing this out. [1] https://eprint.iacr.org/2018/1174.pdf Change-Id: I807bd509e936b7e82a43e8656444431546e9bbdf Reviewed-on: https://boringssl-review.googlesource.com/c/33705 Commit-Queue: David Benjamin <davidben@google.com> Reviewed-by: David Benjamin <davidben@google.com>
diff --git a/crypto/hrss/hrss.c b/crypto/hrss/hrss.c index ff68e9b..13bfa08 100644 --- a/crypto/hrss/hrss.c +++ b/crypto/hrss/hrss.c
@@ -51,6 +51,8 @@ // SXY: https://eprint.iacr.org/2017/1005.pdf // NTRUTN14: // https://assets.onboardsecurity.com/static/downloads/NTRU/resources/NTRUTech014.pdf +// NTRUCOMP: +// https://eprint.iacr.org/2018/1174 // Vector operations. @@ -1686,6 +1688,7 @@ #define POLY_BYTES 1138 +// poly_marshal serialises all but the final coefficient of |in| to |out|. static void poly_marshal(uint8_t out[POLY_BYTES], const struct poly *in) { const uint16_t *p = in->v; @@ -1718,6 +1721,10 @@ out[6] = 0xf & (p[3] >> 9); } +// poly_unmarshal parses the output of |poly_marshal| and sets |out| such that +// all but the final coefficients match, and the final coefficient is calculated +// such that evaluating |out| at one results in zero. It returns one on success +// or zero if |in| is an invalid encoding. static int poly_unmarshal(struct poly *out, const uint8_t in[POLY_BYTES]) { uint16_t *p = out->v; @@ -2080,17 +2087,6 @@ poly_clamp(&priv->ph_inverse); } -static void owf(uint8_t out[POLY_BYTES], const struct public_key *pub, - const struct poly *m_lifted, const struct poly *r) { - struct poly prh_plus_m; - poly_mul(&prh_plus_m, r, &pub->ph); - for (unsigned i = 0; i < N; i++) { - prh_plus_m.v[i] += m_lifted->v[i]; - } - - poly_marshal(out, &prh_plus_m); -} - static const char kSharedKey[] = "shared key"; void HRSS_encap(uint8_t out_ciphertext[POLY_BYTES], @@ -2103,7 +2099,14 @@ poly_short_sample(&m, in); poly_short_sample(&r, in + HRSS_SAMPLE_BYTES); poly_lift(&m_lifted, &m); - owf(out_ciphertext, pub, &m_lifted, &r); + + struct poly prh_plus_m; + poly_mul(&prh_plus_m, &r, &pub->ph); + for (unsigned i = 0; i < N; i++) { + prh_plus_m.v[i] += m_lifted.v[i]; + } + + poly_marshal(out_ciphertext, &prh_plus_m); uint8_t m_bytes[HRSS_POLY3_BYTES], r_bytes[HRSS_POLY3_BYTES]; poly_marshal_mod3(m_bytes, &m); @@ -2119,11 +2122,8 @@ } void HRSS_decap(uint8_t out_shared_key[HRSS_KEY_BYTES], - const struct HRSS_public_key *in_pub, const struct HRSS_private_key *in_priv, const uint8_t *ciphertext, size_t ciphertext_len) { - const struct public_key *pub = - public_key_from_external((struct HRSS_public_key *)in_pub); const struct private_key *priv = private_key_from_external((struct HRSS_private_key *)in_priv); @@ -2168,43 +2168,62 @@ return; } - struct poly f; + struct poly f, cf; + struct poly3 cf3, m3; poly_from_poly3(&f, &priv->f); - - struct poly cf; poly_mul(&cf, &c, &f); - - struct poly3 cf3; poly3_from_poly(&cf3, &cf); // Note that cf3 is not reduced mod Φ(N). That reduction is deferred. - - struct poly3 m3; HRSS_poly3_mul(&m3, &cf3, &priv->f_inverse); struct poly m, m_lifted; poly_from_poly3(&m, &m3); poly_lift(&m_lifted, &m); + struct poly r; for (unsigned i = 0; i < N; i++) { - c.v[i] -= m_lifted.v[i]; + r.v[i] = c.v[i] - m_lifted.v[i]; } - poly_mul(&c, &c, &priv->ph_inverse); - poly_mod_phiN(&c); - poly_clamp(&c); + poly_mul(&r, &r, &priv->ph_inverse); + poly_mod_phiN(&r); + poly_clamp(&r); struct poly3 r3; - crypto_word_t ok = poly3_from_poly_checked(&r3, &c); + crypto_word_t ok = poly3_from_poly_checked(&r3, &r); + + // [NTRUCOMP] section 5.1 includes ReEnc2 and a proof that it's valid. Rather + // than do an expensive |poly_mul|, it rebuilds |c'| from |c - lift(m)| + // (called |b|) with: + // t = (−b(1)/N) mod Q + // c' = b + tΦ(N) + lift(m) mod Q + // + // When polynomials are transmitted, the final coefficient is omitted and + // |poly_unmarshal| sets it such that f(1) == 0. Thus c(1) == 0. Also, + // |poly_lift| multiplies the result by (x-1) and therefore evaluating a + // lifted polynomial at 1 is also zero. Thus lift(m)(1) == 0 and so + // (c - lift(m))(1) == 0. + // + // Although we defer the reduction above, |b| is conceptually reduced mod + // Φ(N). In order to do that reduction one subtracts |c[N-1]| from every + // coefficient. Therefore b(1) = -c[N-1]×N. The value of |t|, above, then is + // just recovering |c[N-1]|, and adding tΦ(N) is simply undoing the reduction. + // Therefore b + tΦ(N) + lift(m) = c by construction and we don't need to + // recover |c| at all so long as we do the checks in + // |poly3_from_poly_checked|. + // + // The |poly_marshal| here then is just confirming that |poly_unmarshal| is + // strict and could be omitted. uint8_t expected_ciphertext[HRSS_CIPHERTEXT_BYTES]; OPENSSL_STATIC_ASSERT(HRSS_CIPHERTEXT_BYTES == POLY_BYTES, "ciphertext is the wrong size"); assert(ciphertext_len == sizeof(expected_ciphertext)); - owf(expected_ciphertext, pub, &m_lifted, &c); + poly_marshal(expected_ciphertext, &c); uint8_t m_bytes[HRSS_POLY3_BYTES]; uint8_t r_bytes[HRSS_POLY3_BYTES]; poly_marshal_mod3(m_bytes, &m); - poly_marshal_mod3(r_bytes, &c); + poly_marshal_mod3(r_bytes, &r); ok &= constant_time_is_zero_w(CRYPTO_memcmp(ciphertext, expected_ciphertext, sizeof(expected_ciphertext)));
diff --git a/crypto/hrss/hrss_test.cc b/crypto/hrss/hrss_test.cc index 714cc7a..ee0400e 100644 --- a/crypto/hrss/hrss_test.cc +++ b/crypto/hrss/hrss_test.cc
@@ -180,17 +180,17 @@ encap_entropy[i] = i; } - uint8_t ciphertext[HRSS_CIPHERTEXT_BYTES]; - uint8_t shared_key[HRSS_KEY_BYTES]; - HRSS_encap(ciphertext, shared_key, &pub, encap_entropy); - HRSS_public_key pub2; uint8_t pub_bytes[HRSS_PUBLIC_KEY_BYTES]; HRSS_marshal_public_key(pub_bytes, &pub); ASSERT_TRUE(HRSS_parse_public_key(&pub2, pub_bytes)); + uint8_t ciphertext[HRSS_CIPHERTEXT_BYTES]; + uint8_t shared_key[HRSS_KEY_BYTES]; + HRSS_encap(ciphertext, shared_key, &pub2, encap_entropy); + uint8_t shared_key2[HRSS_KEY_BYTES]; - HRSS_decap(shared_key2, &pub2, &priv, ciphertext, sizeof(ciphertext)); + HRSS_decap(shared_key2, &priv, ciphertext, sizeof(ciphertext)); EXPECT_EQ(Bytes(shared_key), Bytes(shared_key2)); } @@ -215,7 +215,7 @@ HRSS_encap(ciphertext, shared_key, &pub, encap_entropy); uint8_t shared_key2[HRSS_KEY_BYTES]; - HRSS_decap(shared_key2, &pub, &priv, ciphertext, sizeof(ciphertext)); + HRSS_decap(shared_key2, &priv, ciphertext, sizeof(ciphertext)); EXPECT_EQ(Bytes(shared_key), Bytes(shared_key2)); uint32_t offset; @@ -223,7 +223,7 @@ uint8_t bit; RAND_bytes(&bit, sizeof(bit)); ciphertext[offset % sizeof(ciphertext)] ^= (1 << (bit & 7)); - HRSS_decap(shared_key2, &pub, &priv, ciphertext, sizeof(ciphertext)); + HRSS_decap(shared_key2, &priv, ciphertext, sizeof(ciphertext)); EXPECT_NE(Bytes(shared_key), Bytes(shared_key2)); } } @@ -462,13 +462,13 @@ }; EXPECT_EQ(Bytes(shared_key), Bytes(kExpectedSharedKey)); - HRSS_decap(shared_key, &pub, &priv, ciphertext, sizeof(ciphertext)); + HRSS_decap(shared_key, &priv, ciphertext, sizeof(ciphertext)); EXPECT_EQ(Bytes(shared_key, sizeof(shared_key)), Bytes(kExpectedSharedKey, sizeof(kExpectedSharedKey))); // Corrupt the ciphertext and ensure that the failure key is constant. ciphertext[50] ^= 4; - HRSS_decap(shared_key, &pub, &priv, ciphertext, sizeof(ciphertext)); + HRSS_decap(shared_key, &priv, ciphertext, sizeof(ciphertext)); static const uint8_t kExpectedFailureKey[HRSS_KEY_BYTES] = { 0x8e, 0x19, 0xfe, 0x2b, 0x12, 0x67, 0xef, 0x9a, 0x63, 0x4d, 0x79,
diff --git a/include/openssl/hrss.h b/include/openssl/hrss.h index cc5edff..d4e16dc 100644 --- a/include/openssl/hrss.h +++ b/include/openssl/hrss.h
@@ -80,7 +80,6 @@ // leak which was done via side-channels. Otherwise it should perform either // action in constant-time. OPENSSL_EXPORT void HRSS_decap(uint8_t out_shared_key[HRSS_KEY_BYTES], - const struct HRSS_public_key *in_pub, const struct HRSS_private_key *in_priv, const uint8_t *ciphertext, size_t ciphertext_len);
diff --git a/ssl/ssl_key_share.cc b/ssl/ssl_key_share.cc index 108ea6a..8556c4f 100644 --- a/ssl/ssl_key_share.cc +++ b/ssl/ssl_key_share.cc
@@ -220,11 +220,12 @@ X25519_keypair(x25519_public_key, x25519_private_key_); uint8_t hrss_entropy[HRSS_GENERATE_KEY_BYTES]; + HRSS_public_key hrss_public_key; RAND_bytes(hrss_entropy, sizeof(hrss_entropy)); - HRSS_generate_key(&hrss_public_key_, &hrss_private_key_, hrss_entropy); + HRSS_generate_key(&hrss_public_key, &hrss_private_key_, hrss_entropy); uint8_t hrss_public_key_bytes[HRSS_PUBLIC_KEY_BYTES]; - HRSS_marshal_public_key(hrss_public_key_bytes, &hrss_public_key_); + HRSS_marshal_public_key(hrss_public_key_bytes, &hrss_public_key); if (!CBB_add_bytes(out, x25519_public_key, sizeof(x25519_public_key)) || !CBB_add_bytes(out, hrss_public_key_bytes, @@ -287,8 +288,8 @@ return false; } - HRSS_decap(secret.data() + 32, &hrss_public_key_, &hrss_private_key_, - peer_key.data() + 32, peer_key.size() - 32); + HRSS_decap(secret.data() + 32, &hrss_private_key_, peer_key.data() + 32, + peer_key.size() - 32); *out_secret = std::move(secret); return true; @@ -296,7 +297,6 @@ private: uint8_t x25519_private_key_[32]; - HRSS_public_key hrss_public_key_; HRSS_private_key hrss_private_key_; };
diff --git a/tool/speed.cc b/tool/speed.cc index 975fb53..41dbc50 100644 --- a/tool/speed.cc +++ b/tool/speed.cc
@@ -786,9 +786,9 @@ results.Print("HRSS encap"); - if (!TimeFunction(&results, [&pub, &priv, &ciphertext]() -> bool { + if (!TimeFunction(&results, [&priv, &ciphertext]() -> bool { uint8_t shared_key[HRSS_KEY_BYTES]; - HRSS_decap(shared_key, &pub, &priv, ciphertext, sizeof(ciphertext)); + HRSS_decap(shared_key, &priv, ciphertext, sizeof(ciphertext)); return true; })) { fprintf(stderr, "Failed to time HRSS_encap.\n");