newhope: restore statistical tests. One of these tests the distribution of noise polynomials; the other tests that that agreed-upon keys (prior to whitening) have roughly equal numbers of 0s and 1s. Along the way, expose a few more API bits. Change-Id: I6b04708d41590de45d82ea95bae1033cfccd5d67 Reviewed-on: https://boringssl-review.googlesource.com/8130 Reviewed-by: Adam Langley <agl@google.com>
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( + newhope_statistical_test + + newhope_statistical_test.cc + $<TARGET_OBJECTS:test_support> +) + +add_executable( newhope_vectors_test newhope_vectors_test.cc @@ -26,6 +33,8 @@ ) 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 @@ * |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_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 @@ } 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 @@ 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 @@ /* 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 @@ 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_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_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 @@ /* 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_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"],