1/* $NetBSD: rngtest.c,v 1.3 2016/03/28 15:20:16 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/*
34This software is free for commercial and non-commercial use
35subject to the following conditions.
36
37Copyright remains vested in QUALCOMM Incorporated, and Copyright
38notices in the code are not to be removed. If this package is used in
39a product, QUALCOMM should be given attribution as the author this
40software. This can be in the form of a textual message at program
41startup or in documentation (online or textual) provided with the
42package.
43
44Redistribution and use in source and binary forms, with or without
45modification, are permitted provided that the following conditions are
46met:
47
481. Redistributions of source code must retain the copyright notice,
49 this list of conditions and the following disclaimer.
50
512. 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
563. 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
60THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
61WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
62MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
63IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
64INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
65(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
66SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
67HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
68STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
69IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
70POSSIBILITY OF SUCH DAMAGE.
71
72The license and distribution terms for any publically available version
73or derivative of this code cannot be changed, that is, this code cannot
74simply be copied and put under another distribution license including
75the 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.3 2016/03/28 15:20:16 riastradh Exp $");
146
147#ifndef _KERNEL
148static inline int
149printf(const char * __restrict format, ...)
150{
151 return 0; /* XXX no standard way to do output in libkern? */
152}
153#endif
154
155int bitnum = 0;
156
157const int minrun[7] = {0, 2315, 1114, 527, 240, 103, 103};
158const 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
166const int longrun = LONGRUN;
167const int minones = MINONES;
168const int maxones = MAXONES;
169const long long minpoke = (MINPOKE * PRECISION);
170const long long maxpoke = (MAXPOKE * PRECISION);
171
172/* Population count of 1's in a byte */
173const unsigned char Popcount[] = {
174 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
175 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
176 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
177 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
178 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
179 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
180 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
181 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
182 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
183 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
184 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
185 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
186 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
187 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
188 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
189 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
190};
191
192/* end of run */
193static void
194endrun(rngtest_t *const rc, const int last, int run)
195{
196 if (run >= longrun) {
197 printf("Kernel RNG \"%s\" long run test FAILURE: "
198 "Run of %d %ds found\n", rc->rt_name, run, last);
199 ++rc->rt_nerrs;
200 }
201 if (run > 6)
202 run = 6;
203 ++rc->rt_runs[last][run];
204}
205
206int
207rngtest(rngtest_t *const rc)
208{
209 int i;
210 uint8_t *p;
211 int c;
212 long long X;
213 int last;
214 int run;
215
216 /* Enforce sanity for most members of the context */
217 memset(rc->rt_poker, 0, sizeof(rc->rt_poker));
218 memset(rc->rt_runs, 0, sizeof(rc->rt_runs));
219 rc->rt_nerrs = 0;
220 rc->rt_name[sizeof(rc->rt_name) - 1] = '\0';
221
222 /* monobit test */
223 for (p = rc->rt_b, c = 0; p < &rc->rt_b[sizeof rc->rt_b]; ++p)
224 c += Popcount[*p];
225 if (c <= minones || maxones <= c) {
226 printf("Kernel RNG \"%s\" monobit test FAILURE: %d ones\n",
227 rc->rt_name, c);
228 ++rc->rt_nerrs;
229 }
230 /* poker test */
231 for (p = rc->rt_b; p < &rc->rt_b[sizeof rc->rt_b]; ++p) {
232 ++rc->rt_poker[*p & 0xF];
233 ++rc->rt_poker[(*p >> 4) & 0xF];
234 }
235 for (X = i = 0; i < 16; ++i) {
236 X += rc->rt_poker[i] * rc->rt_poker[i];
237 }
238 X *= PRECISION;
239 X = 16 * X / 5000 - 5000 * PRECISION;
240 if (X <= minpoke || maxpoke <= X) {
241 printf("Kernel RNG \"%s\" poker test failure: "
242 "parameter X = %lld.%lld\n", rc->rt_name,
243 (X / PRECISION), (X % PRECISION));
244 ++rc->rt_nerrs;
245 }
246 /* runs test */
247 last = (rc->rt_b[0] >> 7) & 1;
248 run = 0;
249 for (p = rc->rt_b; p < &rc->rt_b[sizeof rc->rt_b]; ++p) {
250 c = *p;
251 for (i = 7; i >= 0; --i) {
252 if (((c >> i) & 1) != last) {
253 endrun(rc, last, run);
254 run = 0;
255 last = (c >> i) & 1;
256 }
257 ++run;
258 }
259 }
260 endrun(rc, last, run);
261
262 for (run = 1; run <= 6; ++run) {
263 for (last = 0; last <= 1; ++last) {
264 if (rc->rt_runs[last][run] <= minrun[run]) {
265 printf("Kernel RNG \"%s\" runs test FAILURE: "
266 "too few runs of %d %ds (%d <= %d)\n",
267 rc->rt_name, run, last,
268 rc->rt_runs[last][run], minrun[run]);
269 ++rc->rt_nerrs;
270 } else if (rc->rt_runs[last][run] >= maxrun[run]) {
271 printf("Kernel RNG \"%s\" runs test FAILURE: "
272 "too many runs of %d %ds (%d >= %d)\n",
273 rc->rt_name, run, last,
274 rc->rt_runs[last][run], maxrun[run]);
275 ++rc->rt_nerrs;
276 }
277 }
278 }
279 memset(rc->rt_b, 0, sizeof(rc->rt_b));
280 return rc->rt_nerrs;
281}
282