1 /* Bob Jenkins's cryptographic random number generators, ISAAC and ISAAC64.
2
3 Copyright (C) 1999-2023 Free Software Foundation, Inc.
4 Copyright (C) 1997, 1998, 1999 Colin Plumb.
5
6 This program is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <https://www.gnu.org/licenses/>.
18
19 Written by Colin Plumb and Paul Eggert. */
20
21 /*
22 * --------------------------------------------------------------------
23 * We need a source of random numbers for some data.
24 * Cryptographically secure is desirable, but it's not life-or-death
25 * so I can be a little bit experimental in the choice of RNGs here.
26 *
27 * This generator is based somewhat on RC4, but has analysis
28 * <https://burtleburtle.net/bob/rand/isaacafa.html>
29 * pointing to it actually being better. I like it because it's nice
30 * and fast, and because the author did good work analyzing it.
31 * --------------------------------------------------------------------
32 */
33 #include <config.h>
34
35 #include "rand-isaac.h"
36
37 #include <limits.h>
38 #include <string.h>
39
40 /* If the platform supports unaligned access,
41 then don't have -fsanitize=undefined warn about it. */
42 #undef ATTRIBUTE_NO_WARN_SANITIZE_UNDEFINED
43 #if !(_STRING_ARCH_unaligned || _STRING_INLINE_unaligned) \
44 || __GNUC__ < 4 || (__GNUC__ == 4 && __GNUC_MINOR__ < 9)
45 # define ATTRIBUTE_NO_WARN_SANITIZE_UNDEFINED /* empty */
46 #else
47 # define ATTRIBUTE_NO_WARN_SANITIZE_UNDEFINED \
48 __attribute__ ((__no_sanitize_undefined__))
49 #endif
50
51 /* A if 32-bit ISAAC, B if 64-bit. This is a macro, not an inline
52 function, to prevent undefined behavior if the unused argument
53 shifts by more than a word width. */
54 #define IF32(a, b) (ISAAC_BITS == 32 ? (a) : (b))
55
56 /* Discard bits outside the desired range. On typical machines, any
57 decent compiler should optimize this function call away to nothing.
58 But machines with pad bits in integers may need to do more work. */
59 static inline isaac_word
60 just (isaac_word a)
61 {
62 isaac_word desired_bits = ((isaac_word) 1 << 1 << (ISAAC_BITS - 1)) - 1;
63 return a & desired_bits;
64 }
65
66 /* The index operation. */
67 static inline isaac_word
68 ind (isaac_word const *m, isaac_word x)
69 {
70 if (sizeof *m * CHAR_BIT == ISAAC_BITS)
71 {
72 /* The typical case, where words are exactly the right size.
73 Optimize this to a mask, an addition, and an indirect
74 load. */
75 void const *void_m = m;
76 char const *base_p = void_m;
77 void const *word_p = base_p + (x & ((ISAAC_WORDS - 1) * sizeof *m));
78 isaac_word const *p = word_p;
79 return *p;
80 }
81 else
82 {
83 /* Atypical machines need more work. */
84 return m[(x / (ISAAC_BITS / CHAR_BIT)) & (ISAAC_WORDS - 1)];
85 }
86 }
87
88 /* Use and update *S to generate random data to fill RESULT. */
89 void ATTRIBUTE_NO_WARN_SANITIZE_UNDEFINED
90 isaac_refill (struct isaac_state *s, isaac_word result[ISAAC_WORDS])
91 {
92 /* Caches of S->a and S->b. */
93 isaac_word a = s->a;
94 isaac_word b = s->b + (++s->c);
95
96 /* Pointers into state array and into result. */
97 isaac_word *m = s->m;
98 isaac_word *r = result;
99
100 enum { HALF = ISAAC_WORDS / 2 };
101
102 /* The central step. S->m is the whole state array, while M is a
103 pointer to the current word. OFF is the offset from M to the
104 word ISAAC_WORDS/2 words away in the SM array, i.e., +/-
105 ISAAC_WORDS/2. A and B are state variables, and R the result.
106 This updates A, B, M[I], and R[I]. */
107 #define ISAAC_STEP(i, off, mix) \
108 { \
109 isaac_word x, y; \
110 a = (IF32 (a, 0) ^ (mix)) + m[off + (i)]; \
111 x = m[i]; \
112 m[i] = y = ind (s->m, x) + a + b; \
113 r[i] = b = just (ind (s->m, y >> ISAAC_WORDS_LOG) + x); \
114 }
115
116 do
117 {
118 ISAAC_STEP (0, HALF, IF32 ( a << 13, ~ (a ^ (a << 21))));
119 ISAAC_STEP (1, HALF, IF32 (just (a) >> 6, a ^ (just (a) >> 5)));
120 ISAAC_STEP (2, HALF, IF32 ( a << 2, a ^ ( a << 12)));
121 ISAAC_STEP (3, HALF, IF32 (just (a) >> 16, a ^ (just (a) >> 33)));
122 r += 4;
123 }
124 while ((m += 4) < s->m + HALF);
125
126 do
127 {
128 ISAAC_STEP (0, -HALF, IF32 ( a << 13, ~ (a ^ (a << 21))));
129 ISAAC_STEP (1, -HALF, IF32 (just (a) >> 6, a ^ (just (a) >> 5)));
130 ISAAC_STEP (2, -HALF, IF32 ( a << 2, a ^ ( a << 12)));
131 ISAAC_STEP (3, -HALF, IF32 (just (a) >> 16, a ^ (just (a) >> 33)));
132 r += 4;
133 }
134 while ((m += 4) < s->m + ISAAC_WORDS);
135
136 s->a = a;
137 s->b = b;
138 }
139
140 /*
141 * The basic seed-scrambling step for initialization, based on Bob
142 * Jenkins' 256-bit hash.
143 */
144 #if ISAAC_BITS == 32
145 #define mix(a, b, c, d, e, f, g, h) \
146 { \
147 a ^= b << 11; d += a; \
148 b += c; b ^= just (c) >> 2; e += b; \
149 c += d; c ^= d << 8; f += c; \
150 d += e; d ^= just (e) >> 16; g += d; \
151 e += f; e ^= f << 10; h += e; \
152 f += g; f ^= just (g) >> 4; a += f; \
153 g += h; g ^= h << 8; b += g; \
154 h += a; h ^= just (a) >> 9; c += h; \
155 a += b; \
156 }
157 #else
158 #define mix(a, b, c, d, e, f, g, h) \
159 { \
160 a -= e; f ^= just (h) >> 9; h += a; \
161 b -= f; g ^= a << 9; a += b; \
162 c -= g; h ^= just (b) >> 23; b += c; \
163 d -= h; a ^= c << 15; c += d; \
164 e -= a; b ^= just (d) >> 14; d += e; \
165 f -= b; c ^= e << 20; e += f; \
166 g -= c; d ^= just (f) >> 17; f += g; \
167 h -= d; e ^= g << 14; g += h; \
168 }
169 #endif
170
171
172 /* The basic ISAAC initialization pass. */
173 #define ISAAC_MIX(s, a, b, c, d, e, f, g, h, seed) \
174 { \
175 int i; \
176 \
177 for (i = 0; i < ISAAC_WORDS; i += 8) \
178 { \
179 a += seed[i]; \
180 b += seed[i + 1]; \
181 c += seed[i + 2]; \
182 d += seed[i + 3]; \
183 e += seed[i + 4]; \
184 f += seed[i + 5]; \
185 g += seed[i + 6]; \
186 h += seed[i + 7]; \
187 mix (a, b, c, d, e, f, g, h); \
188 s->m[i] = a; \
189 s->m[i + 1] = b; \
190 s->m[i + 2] = c; \
191 s->m[i + 3] = d; \
192 s->m[i + 4] = e; \
193 s->m[i + 5] = f; \
194 s->m[i + 6] = g; \
195 s->m[i + 7] = h; \
196 } \
197 }
198
199 #if 0 /* Provided for reference only; not used in this code */
200 /*
201 * Initialize the ISAAC RNG with the given seed material.
202 * Its size MUST be a multiple of ISAAC_BYTES, and may be
203 * stored in the s->m array.
204 *
205 * This is a generalization of the original ISAAC initialization code
206 * to support larger seed sizes. For seed sizes of 0 and ISAAC_BYTES,
207 * it is identical.
208 */
209 static void
210 isaac_init (struct isaac_state *s, isaac_word const *seed, size_t seedsize)
211 {
212 isaac_word a, b, c, d, e, f, g, h;
213
214 a = b = c = d = e = f = g = h = /* the golden ratio */
215 IF32 (UINT32_C (0x9e3779b9), UINT64_C (0x9e3779b97f4a7c13));
216 for (int i = 0; i < 4; i++) /* scramble it */
217 mix (a, b, c, d, e, f, g, h);
218 s->a = s->b = s->c = 0;
219
220 if (seedsize)
221 {
222 /* First pass (as in reference ISAAC code) */
223 ISAAC_MIX (s, a, b, c, d, e, f, g, h, seed);
224 /* Second and subsequent passes (extension to ISAAC) */
225 while (seedsize -= ISAAC_BYTES)
226 {
227 seed += ISAAC_WORDS;
228 for (i = 0; i < ISAAC_WORDS; i++)
229 s->m[i] += seed[i];
230 ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);
231 }
232 }
233 else
234 {
235 /* The no seed case (as in reference ISAAC code) */
236 for (i = 0; i < ISAAC_WORDS; i++)
237 s->m[i] = 0;
238 }
239
240 /* Final pass */
241 ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);
242 }
243 #endif
244
245 /* Initialize *S to a somewhat-random value, derived from a seed
246 stored in S->m. */
247 void
248 isaac_seed (struct isaac_state *s)
249 {
250 isaac_word a = IF32 (UINT32_C (0x1367df5a), UINT64_C (0x647c4677a2884b7c));
251 isaac_word b = IF32 (UINT32_C (0x95d90059), UINT64_C (0xb9f8b322c73ac862));
252 isaac_word c = IF32 (UINT32_C (0xc3163e4b), UINT64_C (0x8c0ea5053d4712a0));
253 isaac_word d = IF32 (UINT32_C (0x0f421ad8), UINT64_C (0xb29b2e824a595524));
254 isaac_word e = IF32 (UINT32_C (0xd92a4a78), UINT64_C (0x82f053db8355e0ce));
255 isaac_word f = IF32 (UINT32_C (0xa51a3c49), UINT64_C (0x48fe4a0fa5a09315));
256 isaac_word g = IF32 (UINT32_C (0xc4efea1b), UINT64_C (0xae985bf2cbfc89ed));
257 isaac_word h = IF32 (UINT32_C (0x30609119), UINT64_C (0x98f5704f6c44c0ab));
258
259 #if 0
260 /* The initialization of a through h is a precomputed form of: */
261 a = b = c = d = e = f = g = h = /* the golden ratio */
262 IF32 (UINT32_C (0x9e3779b9), UINT64_C (0x9e3779b97f4a7c13));
263 for (int i = 0; i < 4; i++) /* scramble it */
264 mix (a, b, c, d, e, f, g, h);
265 #endif
266
267 /* Mix S->m so that every part of the seed affects every part of the
268 state. */
269 ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);
270 ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);
271
272 s->a = s->b = s->c = 0;
273 }