siphash source code

1 // Written in the D programming language.
2 
3 /**
4 
5 $(BOOKTABLE ,
6 $(TR $(TH Category) $(TH Functions))
7 $(TR $(TDNW Template API) $(TD $(MYREF SipHash)))
8 $(TR $(TDNW Helpers) $(TD $(MYREF siphash24Of)))
9 )
10 
11  * SipHash: a fast short-input PRF
12  *
13  * Example:
14  * -----
15  * // Create key
16  * ubyte[16] key = cast(ubyte[])"To be|not to be!";
17  * // Compute hash with key and arbitrary message
18  * ulong  hashed = siphash24Of(key, cast(ubyte[])"that is the question.");
19  * assert(hashed == 17352353082512417190);
20  * -----
21  *
22  * See_Also:
23  *  $(LINK2 https://www.131002.net/siphash/, SipHash: a fast short-input PRF)
24  *
25  * Copyright: Copyright Masahiro Nakagawa 2012-.
26  * License:   <a href="http://www.boost.org/LICENSE_1_0.txt">Boost License 1.0</a>.
27  * Authors:   Masahiro Nakagawa
28  */
29 module siphash;
30 
31 import std.bitmanip : littleEndianToNative, nativeToLittleEndian;
32 
33 /**
34  * siphash template, which takes SipRound C and D parameters
35  */
36 template siphash(size_t C, size_t D)
37 {
38     /**
39      * Computes SipHash hashes of arbitrary data.
40      *
41      * Params:
42      *  key     = 16 byte key to hash
43      *  message = an arbitrary message
44      *
45      * Returns:
46      *  a 8 byte hash value.
47      */
48     @safe pure nothrow
49     ulong siphashOf(in ubyte[16] key, in ubyte[] message)
50     {
51         return siphashOf(u8to64_le(key.ptr), u8to64_le(key.ptr, BlockSize), message);
52     }
53 
54     /// ditto
55     @safe pure nothrow
56     ulong siphashOf(in ulong k0, in ulong k1, in ubyte[] message)
57     {
58         ulong v0 = k0 ^ 0x736f6d6570736575UL;
59         ulong v1 = k1 ^ 0x646f72616e646f6dUL;
60         ulong v2 = k0 ^ 0x6c7967656e657261UL;
61         ulong v3 = k1 ^ 0x7465646279746573UL;
62 
63         size_t index;
64         for (size_t blocks = message.length & ~7; index < blocks; index += BlockSize) {
65             immutable mi = u8to64_le(message.ptr, index);
66             v3 ^= mi;
67             foreach (Unused; 0..C)
68                 mixin(SipRound);
69             v0 ^= mi;
70         }
71 
72         ulong tail = cast(ulong)(message.length & 0xff) << 56;
73         switch (message.length % BlockSize) {
74         case 7: tail |= cast(ulong)message[index + 6] << 48; goto case 6;
75         case 6: tail |= cast(ulong)message[index + 5] << 40; goto case 5;
76         case 5: tail |= cast(ulong)message[index + 4] << 32; goto case 4;
77         case 4: tail |= cast(ulong)message[index + 3] << 24; goto case 3;
78         case 3: tail |= cast(ulong)message[index + 2] << 16; goto case 2;
79         case 2: tail |= cast(ulong)message[index + 1] <<  8; goto case 1;
80         case 1: tail |= cast(ulong)message[index]; break;
81         default:
82             break;
83         }
84 
85         v3 ^= tail;
86         foreach (Unused; 0..C)
87             mixin(SipRound);
88         v0 ^= tail;
89 
90         v2 ^= 0xff;
91         foreach (Unused; 0..D)
92             mixin(SipRound);
93 
94         return v0 ^ v1 ^ v2 ^ v3;
95     }
96 }
97 
98 alias siphash!(2, 4).siphashOf siphash24Of;
99 
100 /**
101  * SipHash object implements std.digest like API for supporting streaming update.
102  *
103  * Example:
104  * -----
105  * ubyte[16] key = cast(ubyte[])"To be|not to be!";
106  * auto sh = SipHash!(2, 4)(key);
107  *
108  * sh.start();
109  * foreach (chunk; chunks(cast(ubyte[])"that is the question.", 2))
110  *     sh.put(chunk);
111  * auto hashed = sh.finish();
112  * -----
113  */
114 struct SipHash(size_t C, size_t D)
115 {
116   private:
117     immutable ulong k0, k1;
118     ulong v0, v1, v2, v3;
119 
120     size_t processedLength;
121     const(ubyte)[] message;
122 
123 
124   public:
125     @safe pure nothrow
126     {
127         /**
128          * Constructs SipHash with 16 byte key.
129          */
130         this(in ubyte[16] key)
131         {
132             this(u8to64_le(key.ptr), u8to64_le(key.ptr, BlockSize));
133         }
134 
135         /**
136          * Constructs SipHash with two 8 byte key numbers.
137          */
138         this(in ulong key0, in ulong key1)
139         {
140             k0 = key0;
141             k1 = key1;
142         }
143 
144         /**
145          * Used to initialize the SipHash.
146          */
147         void start()
148         {
149             v0 = k0 ^ 0x736f6d6570736575UL;
150             v1 = k1 ^ 0x646f72616e646f6dUL;
151             v2 = k0 ^ 0x6c7967656e657261UL;
152             v3 = k1 ^ 0x7465646279746573UL;
153             processedLength = 0;
154             message = message.init;
155         }
156 
157         /**
158          * Use this to feed the digest with data.
159          * Also implements the $(XREF range, OutputRange) interface for $(D ubyte) and $(D const(ubyte)[]).
160          */
161         void put(scope const(ubyte)[] data...)
162         {
163             message ~= data;
164 
165             size_t index;
166             for (size_t blocks = message.length & ~7; index < blocks;
167                  index += BlockSize, processedLength += BlockSize) {
168                 immutable mi = u8to64_le(message.ptr, index);
169                 v3 ^= mi;
170                 foreach (Unused; 0..C)
171                     mixin(SipRound);
172                 v0 ^= mi;
173             }
174 
175             if (index != 0)
176                 message = message[index..$];
177         }
178 
179         /**
180          * Returns the finished SipHash hash as ubyte[8], not ulong.
181          * This also calls $(LREF start) to reset the internal state.
182          */
183         ubyte[8] finish()
184         {
185             ulong tail = cast(ulong)((processedLength + message.length) & 0xff) << 56;
186             switch (message.length % BlockSize) {
187             case 7: tail |= cast(ulong)message[6] << 48; goto case 6;
188             case 6: tail |= cast(ulong)message[5] << 40; goto case 5;
189             case 5: tail |= cast(ulong)message[4] << 32; goto case 4;
190             case 4: tail |= cast(ulong)message[3] << 24; goto case 3;
191             case 3: tail |= cast(ulong)message[2] << 16; goto case 2;
192             case 2: tail |= cast(ulong)message[1] <<  8; goto case 1;
193             case 1: tail |= cast(ulong)message[0]; break;
194             default:
195                 break;
196             }
197 
198             v3 ^= tail;
199             foreach (Unused; 0..C)
200                 mixin(SipRound);
201             v0 ^= tail;
202 
203             v2 ^= 0xff;
204             foreach (Unused; 0..D)
205                 mixin(SipRound);
206 
207             ubyte[8] result = nativeToLittleEndian(v0 ^ v1 ^ v2 ^ v3);
208 
209             start();
210 
211             return result;
212         }
213     }
214 }
215 
216 private:
217 
218 enum BlockSize = ulong.sizeof;
219 
220 enum SipRound = "
221     v0 += v1;
222     v1  = rotl(v1, 13);
223     v1 ^= v0;
224     v0  = rotl(v0, 32);
225 
226     v2 += v3;
227     v3  = rotl(v3, 16);
228     v3 ^= v2;
229 
230     v2 += v1;
231     v1  = rotl(v1, 17);
232     v1 ^= v2;
233     v2  = rotl(v2, 32);
234 
235     v0 += v3;
236     v3  = rotl(v3, 21);
237     v3 ^= v0;
238 ";
239 
240 @safe pure nothrow
241 ulong rotl(in ulong u, in uint s)
242 {
243     return (u << s) | (u >> (64 - s));
244 }
245 
246 @trusted pure nothrow
247 ulong u8to64_le(in ubyte* ptr, in size_t i = 0)
248 {
249     return *cast(ulong*)(ptr + i);
250 }
251 
252 unittest
253 {
254     import std.conv;
255     import std.range : chunks;
256 
257     /*
258       SipHash-2-4 output with
259       key = 00 01 02 ...
260       and
261       message = (empty string)
262       message = 00 (1 byte)
263       message = 00 01 (2 bytes)
264       message = 00 01 02 (3 bytes)
265       ...
266       message = 00 01 02 ... 3e (63 bytes)
267     */
268     ulong[64] testVectors = [
269         0x726fdb47dd0e0e31UL, 0x74f839c593dc67fdUL, 0x0d6c8009d9a94f5aUL, 0x85676696d7fb7e2dUL,
270         0xcf2794e0277187b7UL, 0x18765564cd99a68dUL, 0xcbc9466e58fee3ceUL, 0xab0200f58b01d137UL,
271         0x93f5f5799a932462UL, 0x9e0082df0ba9e4b0UL, 0x7a5dbbc594ddb9f3UL, 0xf4b32f46226bada7UL,
272         0x751e8fbc860ee5fbUL, 0x14ea5627c0843d90UL, 0xf723ca908e7af2eeUL, 0xa129ca6149be45e5UL,
273         0x3f2acc7f57c29bdbUL, 0x699ae9f52cbe4794UL, 0x4bc1b3f0968dd39cUL, 0xbb6dc91da77961bdUL,
274         0xbed65cf21aa2ee98UL, 0xd0f2cbb02e3b67c7UL, 0x93536795e3a33e88UL, 0xa80c038ccd5ccec8UL,
275         0xb8ad50c6f649af94UL, 0xbce192de8a85b8eaUL, 0x17d835b85bbb15f3UL, 0x2f2e6163076bcfadUL,
276         0xde4daaaca71dc9a5UL, 0xa6a2506687956571UL, 0xad87a3535c49ef28UL, 0x32d892fad841c342UL,
277         0x7127512f72f27cceUL, 0xa7f32346f95978e3UL, 0x12e0b01abb051238UL, 0x15e034d40fa197aeUL,
278         0x314dffbe0815a3b4UL, 0x027990f029623981UL, 0xcadcd4e59ef40c4dUL, 0x9abfd8766a33735cUL,
279         0x0e3ea96b5304a7d0UL, 0xad0c42d6fc585992UL, 0x187306c89bc215a9UL, 0xd4a60abcf3792b95UL,
280         0xf935451de4f21df2UL, 0xa9538f0419755787UL, 0xdb9acddff56ca510UL, 0xd06c98cd5c0975ebUL,
281         0xe612a3cb9ecba951UL, 0xc766e62cfcadaf96UL, 0xee64435a9752fe72UL, 0xa192d576b245165aUL,
282         0x0a8787bf8ecb74b2UL, 0x81b3e73d20b49b6fUL, 0x7fa8220ba3b2eceaUL, 0x245731c13ca42499UL,
283         0xb78dbfaf3a8d83bdUL, 0xea1ad565322a1a0bUL, 0x60e61c23a3795013UL, 0x6606d7e446282b93UL,
284         0x6ca4ecb15c5f91e1UL, 0x9f626da15c9625f3UL, 0xe51b38608ef25f57UL, 0x958a324ceb064572UL
285     ];
286 
287     ubyte[16] key;
288     foreach (ubyte i; 0..16)
289         key[i] = i;
290 
291     auto sh = SipHash!(2, 4)(key);
292     ulong calcViaStreaming(ubyte[] message)
293     {
294         sh.start();
295         foreach (chunk; chunks(message, 3))
296             sh.put(chunk);
297         return littleEndianToNative!ulong(sh.finish());
298     }
299 
300     ubyte[] message;
301     foreach (ubyte i; 0..64) {
302         auto result = siphash24Of(key, message);
303         assert(result == testVectors[i], "test vector failed for " ~ to!string(i));
304         assert(calcViaStreaming(message) == testVectors[i],
305                "test vector failed for " ~ to!string(i) ~ " in streaming");
306 
307         message ~= i;
308     }
309 }