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");
