1/*	$OpenBSD$	*/
2
3/*
4 * OCF/Linux port done by David McCullough <david_mccullough@mcafee.com>
5 * Copyright (C) 2006-2010 David McCullough
6 * Copyright (C) 2004-2005 Intel Corporation.
7 * The license and original author are listed below.
8 *
9 * Copyright (c) 2002 Jason L. Wright (jason@thought.net)
10 * All rights reserved.
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
14 * are met:
15 * 1. Redistributions of source code must retain the above copyright
16 *    notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 *    notice, this list of conditions and the following disclaimer in the
19 *    documentation and/or other materials provided with the distribution.
20 * 3. All advertising materials mentioning features or use of this software
21 *    must display the following acknowledgement:
22 *	This product includes software developed by Jason L. Wright
23 * 4. The name of the author may not be used to endorse or promote products
24 *    derived from this software without specific prior written permission.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
27 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
28 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
29 * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
30 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
31 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
32 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
34 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
35 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36 * POSSIBILITY OF SUCH DAMAGE.
37 */
38
39#include <linux/version.h>
40#if LINUX_VERSION_CODE < KERNEL_VERSION(2,6,38) && !defined(AUTOCONF_INCLUDED)
41#include <linux/config.h>
42#endif
43#include <linux/module.h>
44#include <linux/list.h>
45#include <linux/wait.h>
46#include <linux/time.h>
47#include <linux/unistd.h>
48#include <linux/kernel.h>
49#include <linux/string.h>
50#include <linux/time.h>
51#include <cryptodev.h>
52#include "rndtest.h"
53
54static struct rndtest_stats rndstats;
55
56static	void rndtest_test(struct rndtest_state *);
57
58/* The tests themselves */
59static	int rndtest_monobit(struct rndtest_state *);
60static	int rndtest_runs(struct rndtest_state *);
61static	int rndtest_longruns(struct rndtest_state *);
62static	int rndtest_chi_4(struct rndtest_state *);
63
64static	int rndtest_runs_check(struct rndtest_state *, int, int *);
65static	void rndtest_runs_record(struct rndtest_state *, int, int *);
66
67static const struct rndtest_testfunc {
68	int (*test)(struct rndtest_state *);
69} rndtest_funcs[] = {
70	{ rndtest_monobit },
71	{ rndtest_runs },
72	{ rndtest_chi_4 },
73	{ rndtest_longruns },
74};
75
76#define	RNDTEST_NTESTS	(sizeof(rndtest_funcs)/sizeof(rndtest_funcs[0]))
77
78static void
79rndtest_test(struct rndtest_state *rsp)
80{
81	int i, rv = 0;
82
83	rndstats.rst_tests++;
84	for (i = 0; i < RNDTEST_NTESTS; i++)
85		rv |= (*rndtest_funcs[i].test)(rsp);
86	rsp->rs_discard = (rv != 0);
87}
88
89
90extern int crypto_debug;
91#define rndtest_verbose 2
92#define rndtest_report(rsp, failure, fmt, a...) \
93	{ if (failure || crypto_debug) { printk("rng_test: " fmt "\n", a); } else; }
94
95#define	RNDTEST_MONOBIT_MINONES	9725
96#define	RNDTEST_MONOBIT_MAXONES	10275
97
98static int
99rndtest_monobit(struct rndtest_state *rsp)
100{
101	int i, ones = 0, j;
102	u_int8_t r;
103
104	for (i = 0; i < RNDTEST_NBYTES; i++) {
105		r = rsp->rs_buf[i];
106		for (j = 0; j < 8; j++, r <<= 1)
107			if (r & 0x80)
108				ones++;
109	}
110	if (ones > RNDTEST_MONOBIT_MINONES &&
111	    ones < RNDTEST_MONOBIT_MAXONES) {
112		if (rndtest_verbose > 1)
113			rndtest_report(rsp, 0, "monobit pass (%d < %d < %d)",
114			    RNDTEST_MONOBIT_MINONES, ones,
115			    RNDTEST_MONOBIT_MAXONES);
116		return (0);
117	} else {
118		if (rndtest_verbose)
119			rndtest_report(rsp, 1,
120			    "monobit failed (%d ones)", ones);
121		rndstats.rst_monobit++;
122		return (-1);
123	}
124}
125
126#define	RNDTEST_RUNS_NINTERVAL	6
127
128static const struct rndtest_runs_tabs {
129	u_int16_t min, max;
130} rndtest_runs_tab[] = {
131	{ 2343, 2657 },
132	{ 1135, 1365 },
133	{ 542, 708 },
134	{ 251, 373 },
135	{ 111, 201 },
136	{ 111, 201 },
137};
138
139static int
140rndtest_runs(struct rndtest_state *rsp)
141{
142	int i, j, ones, zeros, rv = 0;
143	int onei[RNDTEST_RUNS_NINTERVAL], zeroi[RNDTEST_RUNS_NINTERVAL];
144	u_int8_t c;
145
146	bzero(onei, sizeof(onei));
147	bzero(zeroi, sizeof(zeroi));
148	ones = zeros = 0;
149	for (i = 0; i < RNDTEST_NBYTES; i++) {
150		c = rsp->rs_buf[i];
151		for (j = 0; j < 8; j++, c <<= 1) {
152			if (c & 0x80) {
153				ones++;
154				rndtest_runs_record(rsp, zeros, zeroi);
155				zeros = 0;
156			} else {
157				zeros++;
158				rndtest_runs_record(rsp, ones, onei);
159				ones = 0;
160			}
161		}
162	}
163	rndtest_runs_record(rsp, ones, onei);
164	rndtest_runs_record(rsp, zeros, zeroi);
165
166	rv |= rndtest_runs_check(rsp, 0, zeroi);
167	rv |= rndtest_runs_check(rsp, 1, onei);
168
169	if (rv)
170		rndstats.rst_runs++;
171
172	return (rv);
173}
174
175static void
176rndtest_runs_record(struct rndtest_state *rsp, int len, int *intrv)
177{
178	if (len == 0)
179		return;
180	if (len > RNDTEST_RUNS_NINTERVAL)
181		len = RNDTEST_RUNS_NINTERVAL;
182	len -= 1;
183	intrv[len]++;
184}
185
186static int
187rndtest_runs_check(struct rndtest_state *rsp, int val, int *src)
188{
189	int i, rv = 0;
190
191	for (i = 0; i < RNDTEST_RUNS_NINTERVAL; i++) {
192		if (src[i] < rndtest_runs_tab[i].min ||
193		    src[i] > rndtest_runs_tab[i].max) {
194			rndtest_report(rsp, 1,
195			    "%s interval %d failed (%d, %d-%d)",
196			    val ? "ones" : "zeros",
197			    i + 1, src[i], rndtest_runs_tab[i].min,
198			    rndtest_runs_tab[i].max);
199			rv = -1;
200		} else {
201			rndtest_report(rsp, 0,
202			    "runs pass %s interval %d (%d < %d < %d)",
203			    val ? "ones" : "zeros",
204			    i + 1, rndtest_runs_tab[i].min, src[i],
205			    rndtest_runs_tab[i].max);
206		}
207	}
208	return (rv);
209}
210
211static int
212rndtest_longruns(struct rndtest_state *rsp)
213{
214	int i, j, ones = 0, zeros = 0, maxones = 0, maxzeros = 0;
215	u_int8_t c;
216
217	for (i = 0; i < RNDTEST_NBYTES; i++) {
218		c = rsp->rs_buf[i];
219		for (j = 0; j < 8; j++, c <<= 1) {
220			if (c & 0x80) {
221				zeros = 0;
222				ones++;
223				if (ones > maxones)
224					maxones = ones;
225			} else {
226				ones = 0;
227				zeros++;
228				if (zeros > maxzeros)
229					maxzeros = zeros;
230			}
231		}
232	}
233
234	if (maxones < 26 && maxzeros < 26) {
235		rndtest_report(rsp, 0, "longruns pass (%d ones, %d zeros)",
236			maxones, maxzeros);
237		return (0);
238	} else {
239		rndtest_report(rsp, 1, "longruns fail (%d ones, %d zeros)",
240			maxones, maxzeros);
241		rndstats.rst_longruns++;
242		return (-1);
243	}
244}
245
246/*
247 * chi^2 test over 4 bits: (this is called the poker test in FIPS 140-2,
248 * but it is really the chi^2 test over 4 bits (the poker test as described
249 * by Knuth vol 2 is something different, and I take him as authoritative
250 * on nomenclature over NIST).
251 */
252#define	RNDTEST_CHI4_K	16
253#define	RNDTEST_CHI4_K_MASK	(RNDTEST_CHI4_K - 1)
254
255/*
256 * The unnormalized values are used so that we don't have to worry about
257 * fractional precision.  The "real" value is found by:
258 *	(V - 1562500) * (16 / 5000) = Vn   (where V is the unnormalized value)
259 */
260#define	RNDTEST_CHI4_VMIN	1563181		/* 2.1792 */
261#define	RNDTEST_CHI4_VMAX	1576929		/* 46.1728 */
262
263static int
264rndtest_chi_4(struct rndtest_state *rsp)
265{
266	unsigned int freq[RNDTEST_CHI4_K], i, sum;
267
268	for (i = 0; i < RNDTEST_CHI4_K; i++)
269		freq[i] = 0;
270
271	/* Get number of occurances of each 4 bit pattern */
272	for (i = 0; i < RNDTEST_NBYTES; i++) {
273		freq[(rsp->rs_buf[i] >> 4) & RNDTEST_CHI4_K_MASK]++;
274		freq[(rsp->rs_buf[i] >> 0) & RNDTEST_CHI4_K_MASK]++;
275	}
276
277	for (i = 0, sum = 0; i < RNDTEST_CHI4_K; i++)
278		sum += freq[i] * freq[i];
279
280	if (sum >= 1563181 && sum <= 1576929) {
281		rndtest_report(rsp, 0, "chi^2(4): pass (sum %u)", sum);
282		return (0);
283	} else {
284		rndtest_report(rsp, 1, "chi^2(4): failed (sum %u)", sum);
285		rndstats.rst_chi++;
286		return (-1);
287	}
288}
289
290int
291rndtest_buf(unsigned char *buf)
292{
293	struct rndtest_state rsp;
294
295	memset(&rsp, 0, sizeof(rsp));
296	rsp.rs_buf = buf;
297	rndtest_test(&rsp);
298	return(rsp.rs_discard);
299}
300
301