1 | /* Statistical tests for arc4random-related functions. |
2 | Copyright (C) 2022-2024 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 |
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 (format: "warning: bailing out after %d failures\n" , failures); |
68 | return; |
69 | } |
70 | } |
71 | } |
72 | printf (format: "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 (format: "error: byte %d never appeared at position %d\n" , byte, pos); |
85 | } |
86 | } |
87 | |
88 | /* Test adapter for arc4random. */ |
89 | static bool |
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 |
103 | generate_arc4random_buf (unsigned char *key) |
104 | { |
105 | arc4random_buf (buf: key, size: arc4random_key_size); |
106 | return true; |
107 | } |
108 | |
109 | /* Test adapter for arc4random_uniform. */ |
110 | static bool |
111 | generate_arc4random_uniform (unsigned char *key) |
112 | { |
113 | for (int i = 0; i < arc4random_key_size; ++i) |
114 | key[i] = arc4random_uniform (upper_bound: 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 | statistical check, so the test will still pass */ |
121 | static bool |
122 | generate_arc4random_uniform_257 (unsigned char *key) |
123 | { |
124 | for (int i = 0; i < arc4random_key_size; ++i) |
125 | key[i] = arc4random_uniform (upper_bound: 257); |
126 | return true; |
127 | } |
128 | |
129 | static int |
130 | do_test (void) |
131 | { |
132 | puts (s: "info: arc4random implementation test" ); |
133 | find_stuck_bytes (func: generate_arc4random); |
134 | |
135 | puts (s: "info: arc4random_buf implementation test" ); |
136 | find_stuck_bytes (func: generate_arc4random_buf); |
137 | |
138 | puts (s: "info: arc4random_uniform implementation test" ); |
139 | find_stuck_bytes (func: generate_arc4random_uniform); |
140 | |
141 | puts (s: "info: arc4random_uniform implementation test (257 variant)" ); |
142 | find_stuck_bytes (func: generate_arc4random_uniform_257); |
143 | |
144 | return 0; |
145 | } |
146 | |
147 | #include <support/test-driver.c> |
148 | |