1 /* $NetBSD: rngtest.c,v 1.4 2018/09/03 18:52:33 riastradh Exp $ */
2
3 /*-
4 * Copyright (c) 2011 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Thor Lancelot Simon.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 /* fips140.c 1.5 (Qualcomm) 02/09/02 */
33 /*
34 This software is free for commercial and non-commercial use
35 subject to the following conditions.
36
37 Copyright remains vested in QUALCOMM Incorporated, and Copyright
38 notices in the code are not to be removed. If this package is used in
39 a product, QUALCOMM should be given attribution as the author this
40 software. This can be in the form of a textual message at program
41 startup or in documentation (online or textual) provided with the
42 package.
43
44 Redistribution and use in source and binary forms, with or without
45 modification, are permitted provided that the following conditions are
46 met:
47
48 1. Redistributions of source code must retain the copyright notice,
49 this list of conditions and the following disclaimer.
50
51 2. Redistributions in binary form must reproduce the above copyright
52 notice, this list of conditions and the following disclaimer in the
53 documentation and/or other materials provided with the
54 distribution.
55
56 3. All advertising materials mentioning features or use of this
57 software must display the following acknowledgement: This product
58 includes software developed by QUALCOMM Incorporated.
59
60 THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
61 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
62 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
63 IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
64 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
65 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
66 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
67 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
68 STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
69 IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
70 POSSIBILITY OF SUCH DAMAGE.
71
72 The license and distribution terms for any publically available version
73 or derivative of this code cannot be changed, that is, this code cannot
74 simply be copied and put under another distribution license including
75 the GNU Public License.
76 */
77
78 /* Run FIPS 140 statistical tests on a file */
79
80 /* written by Greg Rose, Copyright C 2000 QUALCOMM Incorporated */
81
82 /*
83 * Modified for in-kernel use (API adjustments, conversion from
84 * floating to fixed-point chi-sq computation) by Thor Lancelot
85 * Simon.
86 *
87 * A comment on appropriate use of this test and the infamous FIPS 140
88 * "continuous output test" (COT): Both tests are very appropriate for
89 * software interfaces to hardware implementations, and will quickly tell
90 * you if any number of very bad things have happened to your RNG: perhaps
91 * it has come disconnected from the rest of the system, somehow, and you
92 * are getting only unconditioned bus noise (read: clock edges from the
93 * loudest thing in your system). Perhaps it has ceased to latch a shift
94 * register and is feeding you the same data over and over again. Perhaps
95 * it is not really random at all but was sold to you as such. Perhaps it
96 * is not actually *there* (Intel chipset RNG anyone?) but claims to be,
97 * and is feeding you 01010101 on every register read.
98 *
99 * However, when applied to software RNGs, the situation is quite different.
100 * Most software RNGs use a modern hash function or cipher as an output
101 * stage. The resulting bitstream assuredly *should* pass both the
102 * "continuous output" (no two consecutive samples identical) and
103 * statistical tests: if it does not, the cryptographic primitive or its
104 * implementation is terribly broken.
105 *
106 * There is still value to this test: it will tell you if you inadvertently
107 * terribly break your implementation of the software RNG. Which is a thing
108 * that has in fact happened from time to time, even to the careful (or
109 * paranoid). But it will not tell you if there is a problem with the
110 * _input_ to that final cryptographic primitive -- the bits that are hashed
111 * or the key to the cipher -- and if an adversary can find one, you're
112 * still toast.
113 *
114 * The situation is -- sadly -- similar with hardware RNGs that are
115 * certified to one of the standards such as X9.31 or SP800-90. In these
116 * cases the hardware vendor has hidden the actual random bitstream behind
117 * a hardware cipher/hash implementation that should, indeed, produce good
118 * quality random numbers that pass will pass this test -- whether the
119 * underlying bitstream is trustworthy or not.
120 *
121 * However, this test (and the COT) will still probably tell you if the
122 * thing fell off the bus, etc. Which is a thing that has in fact
123 * happened from time to time, even to the fully certified...
124 *
125 * This module does not (yet?) implement the Continuous Output Test. When
126 * I call that test "infamous", it's because it obviously reduces the
127 * backtracking resistance of any implementation that includes it -- the
128 * implementation has to store the entire previous RNG output in order to
129 * perform the required comparison; not just periodically but all the time
130 * when operating at all. Nonetheless, it has obvious value for
131 * hardware implementations where it will quickly and surely detect a
132 * severe failure; but as of this writing several of the latest comments
133 * on SP800-90 recommend removing any requirement for the COT and my
134 * personal tendency is to agree. It's easy to add if you really need it.
135 *
136 */
137
138 #include <sys/types.h>
139 #include <sys/systm.h>
140 #include <sys/rngtest.h>
141
142 #include <lib/libkern/libkern.h>
143
144 #include <sys/cdefs.h>
145 __KERNEL_RCSID(0, "$NetBSD: rngtest.c,v 1.4 2018/09/03 18:52:33 riastradh Exp $");
146
147 #ifndef _KERNEL
148 static inline int
printf(const char * __restrict format,...)149 printf(const char * __restrict format, ...)
150 {
151 return 0; /* XXX no standard way to do output in libkern? */
152 }
153 #endif
154
155 int bitnum = 0;
156
157 const int minrun[7] = {0, 2315, 1114, 527, 240, 103, 103};
158 const int maxrun[7] = {0, 2685, 1386, 723, 384, 209, 209};
159 #define LONGRUN 26
160 #define MINONES 9725
161 #define MAXONES 10275
162 #define MINPOKE 2.16
163 #define MAXPOKE 46.17
164 #define PRECISION 100000
165
166 const int longrun = LONGRUN;
167 const int minones = MINONES;
168 const int maxones = MAXONES;
169 const long long minpoke = (MINPOKE * PRECISION);
170 const long long maxpoke = (MAXPOKE * PRECISION);
171
172 /* end of run */
173 static void
endrun(rngtest_t * const rc,const int last,int run)174 endrun(rngtest_t *const rc, const int last, int run)
175 {
176 if (run >= longrun) {
177 printf("Kernel RNG \"%s\" long run test FAILURE: "
178 "Run of %d %ds found\n", rc->rt_name, run, last);
179 ++rc->rt_nerrs;
180 }
181 if (run > 6)
182 run = 6;
183 ++rc->rt_runs[last][run];
184 }
185
186 int
rngtest(rngtest_t * const rc)187 rngtest(rngtest_t *const rc)
188 {
189 int i;
190 uint8_t *p;
191 int c;
192 long long X;
193 int last;
194 int run;
195
196 /* Enforce sanity for most members of the context */
197 memset(rc->rt_poker, 0, sizeof(rc->rt_poker));
198 memset(rc->rt_runs, 0, sizeof(rc->rt_runs));
199 rc->rt_nerrs = 0;
200 rc->rt_name[sizeof(rc->rt_name) - 1] = '\0';
201
202 /* monobit test */
203 for (p = rc->rt_b, c = 0; p < &rc->rt_b[sizeof rc->rt_b]; ++p)
204 c += popcount(*p);
205 if (c <= minones || maxones <= c) {
206 printf("Kernel RNG \"%s\" monobit test FAILURE: %d ones\n",
207 rc->rt_name, c);
208 ++rc->rt_nerrs;
209 }
210 /* poker test */
211 for (p = rc->rt_b; p < &rc->rt_b[sizeof rc->rt_b]; ++p) {
212 ++rc->rt_poker[*p & 0xF];
213 ++rc->rt_poker[(*p >> 4) & 0xF];
214 }
215 for (X = i = 0; i < 16; ++i) {
216 X += rc->rt_poker[i] * rc->rt_poker[i];
217 }
218 X *= PRECISION;
219 X = 16 * X / 5000 - 5000 * PRECISION;
220 if (X <= minpoke || maxpoke <= X) {
221 printf("Kernel RNG \"%s\" poker test failure: "
222 "parameter X = %lld.%lld\n", rc->rt_name,
223 (X / PRECISION), (X % PRECISION));
224 ++rc->rt_nerrs;
225 }
226 /* runs test */
227 last = (rc->rt_b[0] >> 7) & 1;
228 run = 0;
229 for (p = rc->rt_b; p < &rc->rt_b[sizeof rc->rt_b]; ++p) {
230 c = *p;
231 for (i = 7; i >= 0; --i) {
232 if (((c >> i) & 1) != last) {
233 endrun(rc, last, run);
234 run = 0;
235 last = (c >> i) & 1;
236 }
237 ++run;
238 }
239 }
240 endrun(rc, last, run);
241
242 for (run = 1; run <= 6; ++run) {
243 for (last = 0; last <= 1; ++last) {
244 if (rc->rt_runs[last][run] <= minrun[run]) {
245 printf("Kernel RNG \"%s\" runs test FAILURE: "
246 "too few runs of %d %ds (%d <= %d)\n",
247 rc->rt_name, run, last,
248 rc->rt_runs[last][run], minrun[run]);
249 ++rc->rt_nerrs;
250 } else if (rc->rt_runs[last][run] >= maxrun[run]) {
251 printf("Kernel RNG \"%s\" runs test FAILURE: "
252 "too many runs of %d %ds (%d >= %d)\n",
253 rc->rt_name, run, last,
254 rc->rt_runs[last][run], maxrun[run]);
255 ++rc->rt_nerrs;
256 }
257 }
258 }
259 memset(rc->rt_b, 0, sizeof(rc->rt_b));
260 return rc->rt_nerrs;
261 }
262