1 | /* ========================================================================== |
2 | * siphash.h - SipHash-2-4 in a single header file |
3 | * -------------------------------------------------------------------------- |
4 | * Derived by William Ahern from the reference implementation[1] published[2] |
5 | * by Jean-Philippe Aumasson and Daniel J. Berstein. |
6 | * Minimal changes by Sebastian Pipping and Victor Stinner on top, see below. |
7 | * Licensed under the CC0 Public Domain Dedication license. |
8 | * |
9 | * 1. https://www.131002.net/siphash/siphash24.c |
10 | * 2. https://www.131002.net/siphash/ |
11 | * -------------------------------------------------------------------------- |
12 | * HISTORY: |
13 | * |
14 | * 2020-10-03 (Sebastian Pipping) |
15 | * - Drop support for Visual Studio 9.0/2008 and earlier |
16 | * |
17 | * 2019-08-03 (Sebastian Pipping) |
18 | * - Mark part of sip24_valid as to be excluded from clang-format |
19 | * - Re-format code using clang-format 9 |
20 | * |
21 | * 2018-07-08 (Anton Maklakov) |
22 | * - Add "fall through" markers for GCC's -Wimplicit-fallthrough |
23 | * |
24 | * 2017-11-03 (Sebastian Pipping) |
25 | * - Hide sip_tobin and sip_binof unless SIPHASH_TOBIN macro is defined |
26 | * |
27 | * 2017-07-25 (Vadim Zeitlin) |
28 | * - Fix use of SIPHASH_MAIN macro |
29 | * |
30 | * 2017-07-05 (Sebastian Pipping) |
31 | * - Use _SIP_ULL macro to not require a C++11 compiler if compiled as C++ |
32 | * - Add const qualifiers at two places |
33 | * - Ensure <=80 characters line length (assuming tab width 4) |
34 | * |
35 | * 2017-06-23 (Victor Stinner) |
36 | * - Address Win64 compile warnings |
37 | * |
38 | * 2017-06-18 (Sebastian Pipping) |
39 | * - Clarify license note in the header |
40 | * - Address C89 issues: |
41 | * - Stop using inline keyword (and let compiler decide) |
42 | * - Replace _Bool by int |
43 | * - Turn macro siphash24 into a function |
44 | * - Address invalid conversion (void pointer) by explicit cast |
45 | * - Address lack of stdint.h for Visual Studio 2003 to 2008 |
46 | * - Always expose sip24_valid (for self-tests) |
47 | * |
48 | * 2012-11-04 - Born. (William Ahern) |
49 | * -------------------------------------------------------------------------- |
50 | * USAGE: |
51 | * |
52 | * SipHash-2-4 takes as input two 64-bit words as the key, some number of |
53 | * message bytes, and outputs a 64-bit word as the message digest. This |
54 | * implementation employs two data structures: a struct sipkey for |
55 | * representing the key, and a struct siphash for representing the hash |
56 | * state. |
57 | * |
58 | * For converting a 16-byte unsigned char array to a key, use either the |
59 | * macro sip_keyof or the routine sip_tokey. The former instantiates a |
60 | * compound literal key, while the latter requires a key object as a |
61 | * parameter. |
62 | * |
63 | * unsigned char secret[16]; |
64 | * arc4random_buf(secret, sizeof secret); |
65 | * struct sipkey *key = sip_keyof(secret); |
66 | * |
67 | * For hashing a message, use either the convenience macro siphash24 or the |
68 | * routines sip24_init, sip24_update, and sip24_final. |
69 | * |
70 | * struct siphash state; |
71 | * void *msg; |
72 | * size_t len; |
73 | * uint64_t hash; |
74 | * |
75 | * sip24_init(&state, key); |
76 | * sip24_update(&state, msg, len); |
77 | * hash = sip24_final(&state); |
78 | * |
79 | * or |
80 | * |
81 | * hash = siphash24(msg, len, key); |
82 | * |
83 | * To convert the 64-bit hash value to a canonical 8-byte little-endian |
84 | * binary representation, use either the macro sip_binof or the routine |
85 | * sip_tobin. The former instantiates and returns a compound literal array, |
86 | * while the latter requires an array object as a parameter. |
87 | * -------------------------------------------------------------------------- |
88 | * NOTES: |
89 | * |
90 | * o Neither sip_keyof, sip_binof, nor siphash24 will work with compilers |
91 | * lacking compound literal support. Instead, you must use the lower-level |
92 | * interfaces which take as parameters the temporary state objects. |
93 | * |
94 | * o Uppercase macros may evaluate parameters more than once. Lowercase |
95 | * macros should not exhibit any such side effects. |
96 | * ========================================================================== |
97 | */ |
98 | #ifndef SIPHASH_H |
99 | #define SIPHASH_H |
100 | |
101 | #include <stddef.h> /* size_t */ |
102 | #include <stdint.h> /* uint64_t uint32_t uint8_t */ |
103 | |
104 | /* |
105 | * Workaround to not require a C++11 compiler for using ULL suffix |
106 | * if this code is included and compiled as C++; related GCC warning is: |
107 | * warning: use of C++11 long long integer constant [-Wlong-long] |
108 | */ |
109 | #define _SIP_ULL(high, low) (((uint64_t)high << 32) | low) |
110 | |
111 | #define SIP_ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b)))) |
112 | |
113 | #define SIP_U32TO8_LE(p, v) \ |
114 | (p)[0] = (uint8_t)((v) >> 0); \ |
115 | (p)[1] = (uint8_t)((v) >> 8); \ |
116 | (p)[2] = (uint8_t)((v) >> 16); \ |
117 | (p)[3] = (uint8_t)((v) >> 24); |
118 | |
119 | #define SIP_U64TO8_LE(p, v) \ |
120 | SIP_U32TO8_LE((p) + 0, (uint32_t)((v) >> 0)); \ |
121 | SIP_U32TO8_LE((p) + 4, (uint32_t)((v) >> 32)); |
122 | |
123 | #define SIP_U8TO64_LE(p) \ |
124 | (((uint64_t)((p)[0]) << 0) | ((uint64_t)((p)[1]) << 8) \ |
125 | | ((uint64_t)((p)[2]) << 16) | ((uint64_t)((p)[3]) << 24) \ |
126 | | ((uint64_t)((p)[4]) << 32) | ((uint64_t)((p)[5]) << 40) \ |
127 | | ((uint64_t)((p)[6]) << 48) | ((uint64_t)((p)[7]) << 56)) |
128 | |
129 | #define SIPHASH_INITIALIZER \ |
130 | { 0, 0, 0, 0, {0}, 0, 0 } |
131 | |
132 | struct siphash { |
133 | uint64_t v0, v1, v2, v3; |
134 | |
135 | unsigned char buf[8], *p; |
136 | uint64_t c; |
137 | }; /* struct siphash */ |
138 | |
139 | #define SIP_KEYLEN 16 |
140 | |
141 | struct sipkey { |
142 | uint64_t k[2]; |
143 | }; /* struct sipkey */ |
144 | |
145 | #define sip_keyof(k) sip_tokey(&(struct sipkey){{0}}, (k)) |
146 | |
147 | static struct sipkey * |
148 | sip_tokey(struct sipkey *key, const void *src) { |
149 | key->k[0] = SIP_U8TO64_LE((const unsigned char *)src); |
150 | key->k[1] = SIP_U8TO64_LE((const unsigned char *)src + 8); |
151 | return key; |
152 | } /* sip_tokey() */ |
153 | |
154 | #ifdef SIPHASH_TOBIN |
155 | |
156 | # define sip_binof(v) sip_tobin((unsigned char[8]){0}, (v)) |
157 | |
158 | static void * |
159 | sip_tobin(void *dst, uint64_t u64) { |
160 | SIP_U64TO8_LE((unsigned char *)dst, u64); |
161 | return dst; |
162 | } /* sip_tobin() */ |
163 | |
164 | #endif /* SIPHASH_TOBIN */ |
165 | |
166 | static void |
167 | sip_round(struct siphash *H, const int rounds) { |
168 | int i; |
169 | |
170 | for (i = 0; i < rounds; i++) { |
171 | H->v0 += H->v1; |
172 | H->v1 = SIP_ROTL(H->v1, 13); |
173 | H->v1 ^= H->v0; |
174 | H->v0 = SIP_ROTL(H->v0, 32); |
175 | |
176 | H->v2 += H->v3; |
177 | H->v3 = SIP_ROTL(H->v3, 16); |
178 | H->v3 ^= H->v2; |
179 | |
180 | H->v0 += H->v3; |
181 | H->v3 = SIP_ROTL(H->v3, 21); |
182 | H->v3 ^= H->v0; |
183 | |
184 | H->v2 += H->v1; |
185 | H->v1 = SIP_ROTL(H->v1, 17); |
186 | H->v1 ^= H->v2; |
187 | H->v2 = SIP_ROTL(H->v2, 32); |
188 | } |
189 | } /* sip_round() */ |
190 | |
191 | static struct siphash * |
192 | sip24_init(struct siphash *H, const struct sipkey *key) { |
193 | H->v0 = _SIP_ULL(0x736f6d65U, 0x70736575U) ^ key->k[0]; |
194 | H->v1 = _SIP_ULL(0x646f7261U, 0x6e646f6dU) ^ key->k[1]; |
195 | H->v2 = _SIP_ULL(0x6c796765U, 0x6e657261U) ^ key->k[0]; |
196 | H->v3 = _SIP_ULL(0x74656462U, 0x79746573U) ^ key->k[1]; |
197 | |
198 | H->p = H->buf; |
199 | H->c = 0; |
200 | |
201 | return H; |
202 | } /* sip24_init() */ |
203 | |
204 | #define sip_endof(a) (&(a)[sizeof(a) / sizeof *(a)]) |
205 | |
206 | static struct siphash * |
207 | sip24_update(struct siphash *H, const void *src, size_t len) { |
208 | const unsigned char *p = (const unsigned char *)src, *pe = p + len; |
209 | uint64_t m; |
210 | |
211 | do { |
212 | while (p < pe && H->p < sip_endof(H->buf)) |
213 | *H->p++ = *p++; |
214 | |
215 | if (H->p < sip_endof(H->buf)) |
216 | break; |
217 | |
218 | m = SIP_U8TO64_LE(H->buf); |
219 | H->v3 ^= m; |
220 | sip_round(H, 2); |
221 | H->v0 ^= m; |
222 | |
223 | H->p = H->buf; |
224 | H->c += 8; |
225 | } while (p < pe); |
226 | |
227 | return H; |
228 | } /* sip24_update() */ |
229 | |
230 | static uint64_t |
231 | sip24_final(struct siphash *H) { |
232 | const char left = (char)(H->p - H->buf); |
233 | uint64_t b = (H->c + left) << 56; |
234 | |
235 | switch (left) { |
236 | case 7: |
237 | b |= (uint64_t)H->buf[6] << 48; |
238 | /* fall through */ |
239 | case 6: |
240 | b |= (uint64_t)H->buf[5] << 40; |
241 | /* fall through */ |
242 | case 5: |
243 | b |= (uint64_t)H->buf[4] << 32; |
244 | /* fall through */ |
245 | case 4: |
246 | b |= (uint64_t)H->buf[3] << 24; |
247 | /* fall through */ |
248 | case 3: |
249 | b |= (uint64_t)H->buf[2] << 16; |
250 | /* fall through */ |
251 | case 2: |
252 | b |= (uint64_t)H->buf[1] << 8; |
253 | /* fall through */ |
254 | case 1: |
255 | b |= (uint64_t)H->buf[0] << 0; |
256 | /* fall through */ |
257 | case 0: |
258 | break; |
259 | } |
260 | |
261 | H->v3 ^= b; |
262 | sip_round(H, 2); |
263 | H->v0 ^= b; |
264 | H->v2 ^= 0xff; |
265 | sip_round(H, 4); |
266 | |
267 | return H->v0 ^ H->v1 ^ H->v2 ^ H->v3; |
268 | } /* sip24_final() */ |
269 | |
270 | static uint64_t |
271 | siphash24(const void *src, size_t len, const struct sipkey *key) { |
272 | struct siphash state = SIPHASH_INITIALIZER; |
273 | return sip24_final(sip24_update(sip24_init(&state, key), src, len)); |
274 | } /* siphash24() */ |
275 | |
276 | /* |
277 | * SipHash-2-4 output with |
278 | * k = 00 01 02 ... |
279 | * and |
280 | * in = (empty string) |
281 | * in = 00 (1 byte) |
282 | * in = 00 01 (2 bytes) |
283 | * in = 00 01 02 (3 bytes) |
284 | * ... |
285 | * in = 00 01 02 ... 3e (63 bytes) |
286 | */ |
287 | static int |
288 | sip24_valid(void) { |
289 | /* clang-format off */ |
290 | static const unsigned char vectors[64][8] = { |
291 | { 0x31, 0x0e, 0x0e, 0xdd, 0x47, 0xdb, 0x6f, 0x72, }, |
292 | { 0xfd, 0x67, 0xdc, 0x93, 0xc5, 0x39, 0xf8, 0x74, }, |
293 | { 0x5a, 0x4f, 0xa9, 0xd9, 0x09, 0x80, 0x6c, 0x0d, }, |
294 | { 0x2d, 0x7e, 0xfb, 0xd7, 0x96, 0x66, 0x67, 0x85, }, |
295 | { 0xb7, 0x87, 0x71, 0x27, 0xe0, 0x94, 0x27, 0xcf, }, |
296 | { 0x8d, 0xa6, 0x99, 0xcd, 0x64, 0x55, 0x76, 0x18, }, |
297 | { 0xce, 0xe3, 0xfe, 0x58, 0x6e, 0x46, 0xc9, 0xcb, }, |
298 | { 0x37, 0xd1, 0x01, 0x8b, 0xf5, 0x00, 0x02, 0xab, }, |
299 | { 0x62, 0x24, 0x93, 0x9a, 0x79, 0xf5, 0xf5, 0x93, }, |
300 | { 0xb0, 0xe4, 0xa9, 0x0b, 0xdf, 0x82, 0x00, 0x9e, }, |
301 | { 0xf3, 0xb9, 0xdd, 0x94, 0xc5, 0xbb, 0x5d, 0x7a, }, |
302 | { 0xa7, 0xad, 0x6b, 0x22, 0x46, 0x2f, 0xb3, 0xf4, }, |
303 | { 0xfb, 0xe5, 0x0e, 0x86, 0xbc, 0x8f, 0x1e, 0x75, }, |
304 | { 0x90, 0x3d, 0x84, 0xc0, 0x27, 0x56, 0xea, 0x14, }, |
305 | { 0xee, 0xf2, 0x7a, 0x8e, 0x90, 0xca, 0x23, 0xf7, }, |
306 | { 0xe5, 0x45, 0xbe, 0x49, 0x61, 0xca, 0x29, 0xa1, }, |
307 | { 0xdb, 0x9b, 0xc2, 0x57, 0x7f, 0xcc, 0x2a, 0x3f, }, |
308 | { 0x94, 0x47, 0xbe, 0x2c, 0xf5, 0xe9, 0x9a, 0x69, }, |
309 | { 0x9c, 0xd3, 0x8d, 0x96, 0xf0, 0xb3, 0xc1, 0x4b, }, |
310 | { 0xbd, 0x61, 0x79, 0xa7, 0x1d, 0xc9, 0x6d, 0xbb, }, |
311 | { 0x98, 0xee, 0xa2, 0x1a, 0xf2, 0x5c, 0xd6, 0xbe, }, |
312 | { 0xc7, 0x67, 0x3b, 0x2e, 0xb0, 0xcb, 0xf2, 0xd0, }, |
313 | { 0x88, 0x3e, 0xa3, 0xe3, 0x95, 0x67, 0x53, 0x93, }, |
314 | { 0xc8, 0xce, 0x5c, 0xcd, 0x8c, 0x03, 0x0c, 0xa8, }, |
315 | { 0x94, 0xaf, 0x49, 0xf6, 0xc6, 0x50, 0xad, 0xb8, }, |
316 | { 0xea, 0xb8, 0x85, 0x8a, 0xde, 0x92, 0xe1, 0xbc, }, |
317 | { 0xf3, 0x15, 0xbb, 0x5b, 0xb8, 0x35, 0xd8, 0x17, }, |
318 | { 0xad, 0xcf, 0x6b, 0x07, 0x63, 0x61, 0x2e, 0x2f, }, |
319 | { 0xa5, 0xc9, 0x1d, 0xa7, 0xac, 0xaa, 0x4d, 0xde, }, |
320 | { 0x71, 0x65, 0x95, 0x87, 0x66, 0x50, 0xa2, 0xa6, }, |
321 | { 0x28, 0xef, 0x49, 0x5c, 0x53, 0xa3, 0x87, 0xad, }, |
322 | { 0x42, 0xc3, 0x41, 0xd8, 0xfa, 0x92, 0xd8, 0x32, }, |
323 | { 0xce, 0x7c, 0xf2, 0x72, 0x2f, 0x51, 0x27, 0x71, }, |
324 | { 0xe3, 0x78, 0x59, 0xf9, 0x46, 0x23, 0xf3, 0xa7, }, |
325 | { 0x38, 0x12, 0x05, 0xbb, 0x1a, 0xb0, 0xe0, 0x12, }, |
326 | { 0xae, 0x97, 0xa1, 0x0f, 0xd4, 0x34, 0xe0, 0x15, }, |
327 | { 0xb4, 0xa3, 0x15, 0x08, 0xbe, 0xff, 0x4d, 0x31, }, |
328 | { 0x81, 0x39, 0x62, 0x29, 0xf0, 0x90, 0x79, 0x02, }, |
329 | { 0x4d, 0x0c, 0xf4, 0x9e, 0xe5, 0xd4, 0xdc, 0xca, }, |
330 | { 0x5c, 0x73, 0x33, 0x6a, 0x76, 0xd8, 0xbf, 0x9a, }, |
331 | { 0xd0, 0xa7, 0x04, 0x53, 0x6b, 0xa9, 0x3e, 0x0e, }, |
332 | { 0x92, 0x59, 0x58, 0xfc, 0xd6, 0x42, 0x0c, 0xad, }, |
333 | { 0xa9, 0x15, 0xc2, 0x9b, 0xc8, 0x06, 0x73, 0x18, }, |
334 | { 0x95, 0x2b, 0x79, 0xf3, 0xbc, 0x0a, 0xa6, 0xd4, }, |
335 | { 0xf2, 0x1d, 0xf2, 0xe4, 0x1d, 0x45, 0x35, 0xf9, }, |
336 | { 0x87, 0x57, 0x75, 0x19, 0x04, 0x8f, 0x53, 0xa9, }, |
337 | { 0x10, 0xa5, 0x6c, 0xf5, 0xdf, 0xcd, 0x9a, 0xdb, }, |
338 | { 0xeb, 0x75, 0x09, 0x5c, 0xcd, 0x98, 0x6c, 0xd0, }, |
339 | { 0x51, 0xa9, 0xcb, 0x9e, 0xcb, 0xa3, 0x12, 0xe6, }, |
340 | { 0x96, 0xaf, 0xad, 0xfc, 0x2c, 0xe6, 0x66, 0xc7, }, |
341 | { 0x72, 0xfe, 0x52, 0x97, 0x5a, 0x43, 0x64, 0xee, }, |
342 | { 0x5a, 0x16, 0x45, 0xb2, 0x76, 0xd5, 0x92, 0xa1, }, |
343 | { 0xb2, 0x74, 0xcb, 0x8e, 0xbf, 0x87, 0x87, 0x0a, }, |
344 | { 0x6f, 0x9b, 0xb4, 0x20, 0x3d, 0xe7, 0xb3, 0x81, }, |
345 | { 0xea, 0xec, 0xb2, 0xa3, 0x0b, 0x22, 0xa8, 0x7f, }, |
346 | { 0x99, 0x24, 0xa4, 0x3c, 0xc1, 0x31, 0x57, 0x24, }, |
347 | { 0xbd, 0x83, 0x8d, 0x3a, 0xaf, 0xbf, 0x8d, 0xb7, }, |
348 | { 0x0b, 0x1a, 0x2a, 0x32, 0x65, 0xd5, 0x1a, 0xea, }, |
349 | { 0x13, 0x50, 0x79, 0xa3, 0x23, 0x1c, 0xe6, 0x60, }, |
350 | { 0x93, 0x2b, 0x28, 0x46, 0xe4, 0xd7, 0x06, 0x66, }, |
351 | { 0xe1, 0x91, 0x5f, 0x5c, 0xb1, 0xec, 0xa4, 0x6c, }, |
352 | { 0xf3, 0x25, 0x96, 0x5c, 0xa1, 0x6d, 0x62, 0x9f, }, |
353 | { 0x57, 0x5f, 0xf2, 0x8e, 0x60, 0x38, 0x1b, 0xe5, }, |
354 | { 0x72, 0x45, 0x06, 0xeb, 0x4c, 0x32, 0x8a, 0x95, } |
355 | }; |
356 | /* clang-format on */ |
357 | |
358 | unsigned char in[64]; |
359 | struct sipkey k; |
360 | size_t i; |
361 | |
362 | sip_tokey(&k, "\000\001\002\003\004\005\006\007\010\011" |
363 | "\012\013\014\015\016\017" ); |
364 | |
365 | for (i = 0; i < sizeof in; ++i) { |
366 | in[i] = (unsigned char)i; |
367 | |
368 | if (siphash24(in, i, &k) != SIP_U8TO64_LE(vectors[i])) |
369 | return 0; |
370 | } |
371 | |
372 | return 1; |
373 | } /* sip24_valid() */ |
374 | |
375 | #ifdef SIPHASH_MAIN |
376 | |
377 | # include <stdio.h> |
378 | |
379 | int |
380 | main(void) { |
381 | const int ok = sip24_valid(); |
382 | |
383 | if (ok) |
384 | puts("OK" ); |
385 | else |
386 | puts("FAIL" ); |
387 | |
388 | return ! ok; |
389 | } /* main() */ |
390 | |
391 | #endif /* SIPHASH_MAIN */ |
392 | |
393 | #endif /* SIPHASH_H */ |
394 | |