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 | /* |
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.3 2016/03/28 15:20:16 riastradh Exp $" ); |
146 | |
147 | #ifndef _KERNEL |
148 | static inline int |
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 | /* Population count of 1's in a byte */ |
173 | const 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 */ |
193 | static void |
194 | endrun(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 | |
206 | int |
207 | rngtest(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 | |