1 /* Statistical tests for arc4random-related functions.
2 Copyright (C) 2022 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
9
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <https://www.gnu.org/licenses/>. */
18
19 #include <array_length.h>
20 #include <stdbool.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <stdint.h>
24 #include <string.h>
25 #include <support/check.h>
26
27 enum
28 {
29 arc4random_key_size = 32
30 };
31
32 struct key
33 {
34 unsigned char data[arc4random_key_size];
35 };
36
37 /* With 12,000 keys, the probability that a byte in a predetermined
38 position does not have a predetermined value in all generated keys
39 is about 4e-21. The probability that this happens with any of the
40 16 * 256 possible byte position/values is 1.6e-17. This results in
41 an acceptably low false-positive rate. */
42 enum { key_count = 12000 };
43
44 static struct key keys[key_count];
45
46 /* Used to perform the distribution check. */
47 static int byte_counts[arc4random_key_size][256];
48
49 /* Bail out after this many failures. */
50 enum { failure_limit = 100 };
51
52 static void
find_stuck_bytes(bool (* func)(unsigned char * key))53 find_stuck_bytes (bool (*func) (unsigned char *key))
54 {
55 memset (&keys, 0xcc, sizeof (keys));
56
57 int failures = 0;
58 for (int key = 0; key < key_count; ++key)
59 {
60 while (true)
61 {
62 if (func (keys[key].data))
63 break;
64 ++failures;
65 if (failures >= failure_limit)
66 {
67 printf ("warning: bailing out after %d failures\n", failures);
68 return;
69 }
70 }
71 }
72 printf ("info: key generation finished with %d failures\n", failures);
73
74 memset (&byte_counts, 0, sizeof (byte_counts));
75 for (int key = 0; key < key_count; ++key)
76 for (int pos = 0; pos < arc4random_key_size; ++pos)
77 ++byte_counts[pos][keys[key].data[pos]];
78
79 for (int pos = 0; pos < arc4random_key_size; ++pos)
80 for (int byte = 0; byte < 256; ++byte)
81 if (byte_counts[pos][byte] == 0)
82 {
83 support_record_failure ();
84 printf ("error: byte %d never appeared at position %d\n", byte, pos);
85 }
86 }
87
88 /* Test adapter for arc4random. */
89 static bool
generate_arc4random(unsigned char * key)90 generate_arc4random (unsigned char *key)
91 {
92 uint32_t words[arc4random_key_size / 4];
93 _Static_assert (sizeof (words) == arc4random_key_size, "sizeof (words)");
94
95 for (int i = 0; i < array_length (words); ++i)
96 words[i] = arc4random ();
97 memcpy (key, &words, arc4random_key_size);
98 return true;
99 }
100
101 /* Test adapter for arc4random_buf. */
102 static bool
generate_arc4random_buf(unsigned char * key)103 generate_arc4random_buf (unsigned char *key)
104 {
105 arc4random_buf (key, arc4random_key_size);
106 return true;
107 }
108
109 /* Test adapter for arc4random_uniform. */
110 static bool
generate_arc4random_uniform(unsigned char * key)111 generate_arc4random_uniform (unsigned char *key)
112 {
113 for (int i = 0; i < arc4random_key_size; ++i)
114 key[i] = arc4random_uniform (256);
115 return true;
116 }
117
118 /* Test adapter for arc4random_uniform with argument 257. This means
119 that byte 0 happens more often, but we do not perform such a
120 statistcal check, so the test will still pass */
121 static bool
generate_arc4random_uniform_257(unsigned char * key)122 generate_arc4random_uniform_257 (unsigned char *key)
123 {
124 for (int i = 0; i < arc4random_key_size; ++i)
125 key[i] = arc4random_uniform (257);
126 return true;
127 }
128
129 static int
do_test(void)130 do_test (void)
131 {
132 puts ("info: arc4random implementation test");
133 find_stuck_bytes (generate_arc4random);
134
135 puts ("info: arc4random_buf implementation test");
136 find_stuck_bytes (generate_arc4random_buf);
137
138 puts ("info: arc4random_uniform implementation test");
139 find_stuck_bytes (generate_arc4random_uniform);
140
141 puts ("info: arc4random_uniform implementation test (257 variant)");
142 find_stuck_bytes (generate_arc4random_uniform_257);
143
144 return 0;
145 }
146
147 #include <support/test-driver.c>
148