aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--crypto/newhope/CMakeLists.txt9
-rw-r--r--crypto/newhope/internal.h9
-rw-r--r--crypto/newhope/newhope.c25
-rw-r--r--crypto/newhope/newhope_statistical_test.cc156
-rw-r--r--crypto/newhope/poly.c10
-rw-r--r--include/openssl/newhope.h13
-rw-r--r--util/all_tests.json1
7 files changed, 200 insertions, 23 deletions
diff --git a/crypto/newhope/CMakeLists.txt b/crypto/newhope/CMakeLists.txt
index 5d339ba..7787cce 100644
--- a/crypto/newhope/CMakeLists.txt
+++ b/crypto/newhope/CMakeLists.txt
@@ -19,6 +19,13 @@ add_executable(
)
add_executable(
+ newhope_statistical_test
+
+ newhope_statistical_test.cc
+ $<TARGET_OBJECTS:test_support>
+)
+
+add_executable(
newhope_vectors_test
newhope_vectors_test.cc
@@ -26,6 +33,8 @@ add_executable(
)
target_link_libraries(newhope_test crypto)
+target_link_libraries(newhope_statistical_test crypto)
target_link_libraries(newhope_vectors_test crypto)
add_dependencies(all_tests newhope_test)
+add_dependencies(all_tests newhope_statistical_test)
add_dependencies(all_tests newhope_vectors_test)
diff --git a/crypto/newhope/internal.h b/crypto/newhope/internal.h
index 5c82d68..efc5adf 100644
--- a/crypto/newhope/internal.h
+++ b/crypto/newhope/internal.h
@@ -43,12 +43,6 @@ struct newhope_poly_st {
* |seed|. (In the reference implementation this was done with SHAKE-128.) */
void newhope_poly_uniform(NEWHOPE_POLY* a, const uint8_t* seed);
-/* newhope_poly_getnoise sets |r| to a random polynomial where the coefficients
- * are
- * sampled from the noise distribution. (In the reference implementation, this
- * is given a random seed and a nonce.)*/
-void newhope_poly_getnoise(NEWHOPE_POLY* r);
-
void newhope_helprec(NEWHOPE_POLY* c, const NEWHOPE_POLY* v,
const uint8_t rbits[32]);
@@ -58,9 +52,6 @@ void newhope_helprec(NEWHOPE_POLY* c, const NEWHOPE_POLY* v,
void newhope_reconcile(uint8_t* key, const NEWHOPE_POLY* v,
const NEWHOPE_POLY* c);
-/* newhope_poly_ntt performs NTT(r) in-place. */
-void newhope_poly_ntt(NEWHOPE_POLY* r);
-
/* newhope_poly_invntt performs the inverse of NTT(r) in-place. */
void newhope_poly_invntt(NEWHOPE_POLY* r);
diff --git a/crypto/newhope/newhope.c b/crypto/newhope/newhope.c
index c590cfa..7edb7eb 100644
--- a/crypto/newhope/newhope.c
+++ b/crypto/newhope/newhope.c
@@ -47,8 +47,7 @@ static void decode_rec(const uint8_t *r, NEWHOPE_POLY *c) {
}
void NEWHOPE_offer(uint8_t *offermsg, NEWHOPE_POLY *s) {
- newhope_poly_getnoise(s);
- newhope_poly_ntt(s);
+ NEWHOPE_POLY_noise_ntt(s);
/* The first part of the offer message is the seed, which compactly encodes
* a. */
@@ -58,8 +57,7 @@ void NEWHOPE_offer(uint8_t *offermsg, NEWHOPE_POLY *s) {
newhope_poly_uniform(&a, seed);
NEWHOPE_POLY e;
- newhope_poly_getnoise(&e);
- newhope_poly_ntt(&e);
+ NEWHOPE_POLY_noise_ntt(&e);
/* The second part of the offer message is the polynomial pk = a*s+e */
NEWHOPE_POLY pk;
@@ -78,17 +76,13 @@ int NEWHOPE_accept(uint8_t key[SHA256_DIGEST_LENGTH],
/* Decode the |offermsg|, generating the same |a| as the peer, from the peer's
* seed. */
NEWHOPE_POLY pk, a;
- const uint8_t *seed = &offermsg[NEWHOPE_POLY_LENGTH];
- newhope_poly_uniform(&a, seed);
- NEWHOPE_POLY_frombytes(&pk, offermsg);
+ NEWHOPE_offer_frommsg(&pk, &a, offermsg);
/* Generate noise polynomials used to generate our key. */
NEWHOPE_POLY sp, ep, epp;
- newhope_poly_getnoise(&sp);
- newhope_poly_ntt(&sp);
- newhope_poly_getnoise(&ep);
- newhope_poly_ntt(&ep);
- newhope_poly_getnoise(&epp); /* intentionally not NTT */
+ NEWHOPE_POLY_noise_ntt(&sp);
+ NEWHOPE_POLY_noise_ntt(&ep);
+ NEWHOPE_POLY_noise(&epp); /* intentionally not NTT */
/* Generate random bytes used for reconciliation. (The reference
* implementation calls ChaCha20 here.) */
@@ -171,3 +165,10 @@ void NEWHOPE_finish_computation(uint8_t k[NEWHOPE_KEY_LENGTH],
newhope_poly_invntt(&v);
newhope_reconcile(k, &v, reconciliation);
}
+
+void NEWHOPE_offer_frommsg(NEWHOPE_POLY *out_pk, NEWHOPE_POLY *out_a,
+ const uint8_t offermsg[NEWHOPE_OFFERMSG_LENGTH]) {
+ NEWHOPE_POLY_frombytes(out_pk, offermsg);
+ const uint8_t *seed = offermsg + NEWHOPE_POLY_LENGTH;
+ newhope_poly_uniform(out_a, seed);
+}
diff --git a/crypto/newhope/newhope_statistical_test.cc b/crypto/newhope/newhope_statistical_test.cc
new file mode 100644
index 0000000..272d9c5
--- /dev/null
+++ b/crypto/newhope/newhope_statistical_test.cc
@@ -0,0 +1,156 @@
+/* Copyright (c) 2016, Google 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. */
+
+#include <string>
+
+#include <math.h>
+#include <stdio.h>
+#include <string.h>
+
+#include <openssl/crypto.h>
+#include <openssl/rand.h>
+
+#include "../test/scoped_types.h"
+#include "internal.h"
+
+
+static const unsigned kNumTests = 1000;
+
+static bool TestNoise(void) {
+ printf("noise distribution:\n");
+
+ size_t buckets[1 + 2 * PARAM_K];
+ memset(buckets, 0, sizeof(buckets));
+ for (size_t i = 0; i < kNumTests; i++) {
+ NEWHOPE_POLY s;
+ NEWHOPE_POLY_noise(&s);
+ for (int j = 0; j < PARAM_N; j++) {
+ uint16_t value = (s.coeffs[j] + PARAM_K) % PARAM_Q;
+ buckets[value]++;
+ }
+ }
+
+ int64_t sum = 0, square_sum = 0;
+ for (int64_t i = 0; i < 1 + 2 * PARAM_K; i++) {
+ sum += (i - PARAM_K) * (int64_t) buckets[i];
+ square_sum += (i - PARAM_K) * (i - PARAM_K) * (int64_t) buckets[i];
+ }
+ double mean = double(sum) / double(PARAM_N * kNumTests);
+
+ double expected_variance = 0.5 * 0.5 * double(PARAM_K * 2);
+ double variance = double(square_sum) / double(PARAM_N * kNumTests) - mean * mean;
+
+ for (size_t i = 0; i < 1 + 2 * PARAM_K; i++) {
+ std::string dots;
+ for (size_t j = 0; j < 79 * buckets[i] / buckets[PARAM_K]; j++) {
+ dots += "+";
+ }
+ printf("%+zd\t%zd\t%s\n", i - PARAM_K, buckets[i], dots.c_str());
+ }
+ printf("mean: got %f, want %f\n", mean, 0.0);
+ printf("variance: got %f, want %f\n", variance, expected_variance);
+ printf("\n");
+
+ if (mean < -0.5 || 0.5 < mean) {
+ fprintf(stderr, "mean out of range: %f\n", mean);
+ return false;
+ }
+
+ if (variance < expected_variance - 1.0 || expected_variance + 1.0 < variance) {
+ fprintf(stderr, "variance out of range: got %f, want %f\n", variance,
+ expected_variance);
+ return false;
+ }
+ return true;
+}
+
+static int hamming32(const uint8_t key[NEWHOPE_KEY_LENGTH]) {
+ static int kHamming[256] = {
+ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
+ };
+
+ int r = 0;
+ for(int i = 0; i < NEWHOPE_KEY_LENGTH; i++) {
+ r += kHamming[key[i]];
+ }
+ return r;
+}
+
+static bool TestKeys(void) {
+ printf("keys (prior to whitening):\n");
+
+ uint8_t key[NEWHOPE_KEY_LENGTH];
+ uint8_t offermsg[NEWHOPE_OFFERMSG_LENGTH];
+
+ ScopedNEWHOPE_POLY sk(NEWHOPE_POLY_new()), pk(NEWHOPE_POLY_new()),
+ sp(NEWHOPE_POLY_new()), ep(NEWHOPE_POLY_new()), epp(NEWHOPE_POLY_new()),
+ a(NEWHOPE_POLY_new()), bp(NEWHOPE_POLY_new()), rec(NEWHOPE_POLY_new());
+
+ uint64_t ones = 0;
+ for (size_t i = 0; i < kNumTests; i++) {
+ NEWHOPE_offer(offermsg, sk.get());
+ NEWHOPE_offer_frommsg(pk.get(), a.get(), offermsg);
+
+ NEWHOPE_POLY_noise_ntt(sp.get());
+ NEWHOPE_POLY_noise_ntt(ep.get());
+ NEWHOPE_POLY_noise(epp.get()); /* intentionally not NTT */
+
+ uint8_t rand[32];
+ RAND_bytes(rand, 32);
+
+ NEWHOPE_accept_computation(key, bp.get(), rec.get(),
+ sp.get(), ep.get(), epp.get(), rand,
+ pk.get(), a.get());
+ ones += hamming32(key);
+ }
+
+ uint64_t bits = NEWHOPE_KEY_LENGTH * 8 * kNumTests;
+ uint64_t diff = bits - 2 * ones;
+ double fraction = (double) abs(diff) / bits;
+ printf("ones: %ld\n", ones);
+ printf("zeroes: %ld\n", bits - ones);
+ printf("diff: got %ld (%f), want %ld\n", diff, fraction, 0L);
+ printf("\n");
+
+ if (fraction > 0.01) {
+ fprintf(stderr, "key bias is too high (%f)\n", fraction);
+ return false;
+ }
+
+ return true;
+}
+
+int main(void) {
+ if (!TestKeys() ||
+ !TestNoise()) {
+ return 1;
+ }
+ printf("PASS\n");
+ return 0;
+}
diff --git a/crypto/newhope/poly.c b/crypto/newhope/poly.c
index a84bdeb..44cd383 100644
--- a/crypto/newhope/poly.c
+++ b/crypto/newhope/poly.c
@@ -126,7 +126,7 @@ void newhope_poly_uniform(NEWHOPE_POLY* a, const uint8_t* seed) {
}
}
-void newhope_poly_getnoise(NEWHOPE_POLY* r) {
+void NEWHOPE_POLY_noise(NEWHOPE_POLY* r) {
#if PARAM_K != 16
#error "poly_getnoise in poly.c only supports k=16"
#endif
@@ -171,7 +171,13 @@ void newhope_poly_add(NEWHOPE_POLY* r, const NEWHOPE_POLY* a,
}
}
-void newhope_poly_ntt(NEWHOPE_POLY* r) {
+void NEWHOPE_POLY_noise_ntt(NEWHOPE_POLY* r) {
+ NEWHOPE_POLY_noise(r);
+ /* Forward NTT transformation. Because we're operating on a noise polynomial,
+ * we can regard the bits as already reversed and skip the bit-reversal
+ * step:
+ *
+ * newhope_bitrev_vector(r->coeffs); */
newhope_mul_coefficients(r->coeffs, newhope_psis_bitrev_montgomery);
newhope_ntt((uint16_t *) r->coeffs, newhope_omegas_montgomery);
}
diff --git a/include/openssl/newhope.h b/include/openssl/newhope.h
index 31d559f..74103c9 100644
--- a/include/openssl/newhope.h
+++ b/include/openssl/newhope.h
@@ -89,6 +89,14 @@ OPENSSL_EXPORT int NEWHOPE_finish(uint8_t out_key[SHA256_DIGEST_LENGTH],
/* Lower-level functions. */
+/* NEWHOPE_POLY_noise sets |r| to a random polynomial where the coefficients are
+ * sampled from the noise distribution. */
+void NEWHOPE_POLY_noise(NEWHOPE_POLY* r);
+
+/* NEWHOPE_POLY_noise sets |r| to an output of NEWHOPE_POLY_noise, and then
+ * applies NTT(r) in-place. */
+void NEWHOPE_POLY_noise_ntt(NEWHOPE_POLY* r);
+
/* NEWHOPE_offer_computation is the work of |NEWHOPE_offer|, less the encoding
* parts. The inputs are the noise polynomials |s| and |e|, and random
* polynomial |a|. The output is the polynomial |pk|. */
@@ -125,6 +133,11 @@ OPENSSL_EXPORT void NEWHOPE_POLY_frombytes(
OPENSSL_EXPORT void NEWHOPE_POLY_tobytes(uint8_t r[NEWHOPE_POLY_LENGTH],
const NEWHOPE_POLY* p);
+/* NEWHOPE_offer_frommsg decodes an offer message |msg| into its constituent
+ * polynomials |out_pk| and |a|. */
+OPENSSL_EXPORT void NEWHOPE_offer_frommsg(
+ NEWHOPE_POLY *out_pk, NEWHOPE_POLY *out_a,
+ const uint8_t msg[NEWHOPE_OFFERMSG_LENGTH]);
#if defined(__cplusplus)
} /* extern "C" */
diff --git a/util/all_tests.json b/util/all_tests.json
index 9e3445c..bfbeebf 100644
--- a/util/all_tests.json
+++ b/util/all_tests.json
@@ -51,6 +51,7 @@
["crypto/lhash/lhash_test"],
["crypto/modes/gcm_test"],
["crypto/newhope/newhope_test"],
+ ["crypto/newhope/newhope_statistical_test"],
["crypto/newhope/newhope_vectors_test", "crypto/newhope/newhope_test.txt"],
["crypto/obj/obj_test"],
["crypto/pkcs8/pkcs12_test"],
generated by cgit v1.1 at 2024-08-04 15:24:39 +0000