Debian Codegraph @

external/boringssl/crypto/newhope/newhope_statistical_test.cc

raw
1 /* Copyright (c) 2016, Google Inc.
2 *
3 * Permission to use, copy, modify, and/or distribute this software for any
4 * purpose with or without fee is hereby granted, provided that the above
5 * copyright notice and this permission notice appear in all copies.
6 *
7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
10 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
14
15 #include <string>
16
17 #include <math.h>
18 #include <stdio.h>
19 #include <string.h>
20
21 #include <openssl/crypto.h>
22 #include <openssl/rand.h>
23
24 #include "../test/scoped_types.h"
25 #include "internal.h"
26
27
28 static const unsigned kNumTests = 1000;
29
30 static bool TestNoise(void) {
31 printf("noise distribution:\n");
32
33 size_t buckets[1 + 2 * PARAM_K];
34 memset(buckets, 0, sizeof(buckets));
35 for (size_t i = 0; i < kNumTests; i++) {
36 NEWHOPE_POLY s;
37 NEWHOPE_POLY_noise(&s);
38 for (int j = 0; j < PARAM_N; j++) {
39 uint16_t value = (s.coeffs[j] + PARAM_K) % PARAM_Q;
40 buckets[value]++;
41 }
42 }
43
44 int64_t sum = 0, square_sum = 0;
45 for (int64_t i = 0; i < 1 + 2 * PARAM_K; i++) {
46 sum += (i - PARAM_K) * (int64_t) buckets[i];
47 square_sum += (i - PARAM_K) * (i - PARAM_K) * (int64_t) buckets[i];
48 }
49 double mean = double(sum) / double(PARAM_N * kNumTests);
50
51 double expected_variance = 0.5 * 0.5 * double(PARAM_K * 2);
52 double variance = double(square_sum) / double(PARAM_N * kNumTests) - mean * mean;
53
54 for (size_t i = 0; i < 1 + 2 * PARAM_K; i++) {
55 std::string dots;
56 for (size_t j = 0; j < 79 * buckets[i] / buckets[PARAM_K]; j++) {
57 dots += "+";
58 }
59 printf("%+zd\t%zd\t%s\n", i - PARAM_K, buckets[i], dots.c_str());
60 }
61 printf("mean: got %f, want %f\n", mean, 0.0);
62 printf("variance: got %f, want %f\n", variance, expected_variance);
63 printf("\n");
64
65 if (mean < -0.5 || 0.5 < mean) {
66 fprintf(stderr, "mean out of range: %f\n", mean);
67 return false;
68 }
69
70 if (variance < expected_variance - 1.0 || expected_variance + 1.0 < variance) {
71 fprintf(stderr, "variance out of range: got %f, want %f\n", variance,
72 expected_variance);
73 return false;
74 }
75 return true;
76 }
77
78 static int Hamming32(const uint8_t key[NEWHOPE_KEY_LENGTH]) {
79 static int kHamming[256] = {
80 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
81 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
82 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
83 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
84 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
85 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
86 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
87 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
88 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
89 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
90 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
91 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
92 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
93 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
94 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
95 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
96 };
97
98 int r = 0;
99 for(int i = 0; i < NEWHOPE_KEY_LENGTH; i++) {
100 r += kHamming[key[i]];
101 }
102 return r;
103 }
104
105 static bool TestKeys(void) {
106 printf("keys (prior to whitening):\n");
107
108 uint8_t key[NEWHOPE_KEY_LENGTH];
109 uint8_t offermsg[NEWHOPE_OFFERMSG_LENGTH];
110
111 ScopedNEWHOPE_POLY sk(NEWHOPE_POLY_new()), pk(NEWHOPE_POLY_new()),
112 sp(NEWHOPE_POLY_new()), ep(NEWHOPE_POLY_new()), epp(NEWHOPE_POLY_new()),
113 a(NEWHOPE_POLY_new()), bp(NEWHOPE_POLY_new()), rec(NEWHOPE_POLY_new());
114
115 int ones = 0;
116 for (size_t i = 0; i < kNumTests; i++) {
117 NEWHOPE_offer(offermsg, sk.get());
118 NEWHOPE_offer_frommsg(pk.get(), a.get(), offermsg);
119
120 NEWHOPE_POLY_noise_ntt(sp.get());
121 NEWHOPE_POLY_noise_ntt(ep.get());
122 NEWHOPE_POLY_noise(epp.get()); /* intentionally not NTT */
123
124 uint8_t rand[32];
125 RAND_bytes(rand, 32);
126
127 NEWHOPE_accept_computation(key, bp.get(), rec.get(),
128 sp.get(), ep.get(), epp.get(), rand,
129 pk.get(), a.get());
130 ones += Hamming32(key);
131 }
132
133 int bits = NEWHOPE_KEY_LENGTH * 8 * kNumTests;
134 int diff = bits - 2 * ones;
135 double fraction = (double) abs(diff) / bits;
136 printf("ones: %d\n", ones);
137 printf("zeroes: %d\n", (bits - ones));
138 printf("diff: got %d (%f), want 0\n", diff, fraction);
139 printf("\n");
140
141 if (fraction > 0.01) {
142 fprintf(stderr, "key bias is too high (%f)\n", fraction);
143 return false;
144 }
145
146 return true;
147 }
148
149 int main(void) {
150 if (!TestKeys() ||
151 !TestNoise()) {
152 return 1;
153 }
154 printf("PASS\n");
155 return 0;
156 }