xref: /freebsd/sys/crypto/siphash/siphash.c (revision f4b37ed0f8b307b1f3f0f630ca725d68f1dff30d)
1 /*-
2  * Copyright (c) 2013 Andre Oppermann <andre@FreeBSD.org>
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  * 3. The name of the author may not be used to endorse or promote
14  *    products derived from this software without specific prior written
15  *    permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  */
29 
30 /*
31  * SipHash is a family of PRFs SipHash-c-d where the integer parameters c and d
32  * are the number of compression rounds and the number of finalization rounds.
33  * A compression round is identical to a finalization round and this round
34  * function is called SipRound.  Given a 128-bit key k and a (possibly empty)
35  * byte string m, SipHash-c-d returns a 64-bit value SipHash-c-d(k; m).
36  *
37  * Implemented from the paper "SipHash: a fast short-input PRF", 2012.09.18,
38  * by Jean-Philippe Aumasson and Daniel J. Bernstein,
39  * Permanent Document ID b9a943a805fbfc6fde808af9fc0ecdfa
40  * https://131002.net/siphash/siphash.pdf
41  * https://131002.net/siphash/
42  */
43 
44 #include <sys/cdefs.h>
45 __FBSDID("$FreeBSD$");
46 
47 #include <sys/param.h>
48 #include <sys/types.h>
49 #include <sys/systm.h>
50 #include <sys/libkern.h>
51 #include <sys/endian.h>
52 
53 #include <crypto/siphash/siphash.h>
54 
55 static void	SipRounds(SIPHASH_CTX *ctx, int final);
56 
57 void
58 SipHash_InitX(SIPHASH_CTX *ctx, int rc, int rf)
59 {
60 
61 	ctx->v[0] = 0x736f6d6570736575ull;
62 	ctx->v[1] = 0x646f72616e646f6dull;
63 	ctx->v[2] = 0x6c7967656e657261ull;
64 	ctx->v[3] = 0x7465646279746573ull;
65 	ctx->buf.b64 = 0;
66 	ctx->bytes = 0;
67 	ctx->buflen = 0;
68 	ctx->rounds_compr = rc;
69 	ctx->rounds_final = rf;
70 	ctx->initialized = 1;
71 }
72 
73 void
74 SipHash_SetKey(SIPHASH_CTX *ctx, const uint8_t key[16])
75 {
76 	uint64_t k[2];
77 
78 	KASSERT(ctx->v[0] == 0x736f6d6570736575ull &&
79 	    ctx->initialized == 1,
80 	    ("%s: context %p not properly initialized", __func__, ctx));
81 
82 	k[0] = le64dec(&key[0]);
83 	k[1] = le64dec(&key[8]);
84 
85 	ctx->v[0] ^= k[0];
86 	ctx->v[1] ^= k[1];
87 	ctx->v[2] ^= k[0];
88 	ctx->v[3] ^= k[1];
89 
90 	ctx->initialized = 2;
91 }
92 
93 static size_t
94 SipBuf(SIPHASH_CTX *ctx, const uint8_t **src, size_t len, int final)
95 {
96 	size_t x = 0;
97 
98 	KASSERT((!final && len > 0) || (final && len == 0),
99 	    ("%s: invalid parameters", __func__));
100 
101 	if (!final) {
102 		x = MIN(len, sizeof(ctx->buf.b64) - ctx->buflen);
103 		bcopy(*src, &ctx->buf.b8[ctx->buflen], x);
104 		ctx->buflen += x;
105 		*src += x;
106 	} else
107 		ctx->buf.b8[7] = (uint8_t)ctx->bytes;
108 
109 	if (ctx->buflen == 8 || final) {
110 		ctx->v[3] ^= le64toh(ctx->buf.b64);
111 		SipRounds(ctx, 0);
112 		ctx->v[0] ^= le64toh(ctx->buf.b64);
113 		ctx->buf.b64 = 0;
114 		ctx->buflen = 0;
115 	}
116 	return (x);
117 }
118 
119 void
120 SipHash_Update(SIPHASH_CTX *ctx, const void *src, size_t len)
121 {
122 	uint64_t m;
123 	const uint64_t *p;
124 	const uint8_t *s;
125 	size_t rem;
126 
127 	KASSERT(ctx->initialized == 2,
128 	    ("%s: context %p not properly initialized", __func__, ctx));
129 
130 	s = src;
131 	ctx->bytes += len;
132 
133 	/*
134 	 * Push length smaller than block size into buffer or
135 	 * fill up the buffer if there is already something
136 	 * in it.
137 	 */
138 	if (ctx->buflen > 0 || len < 8)
139 		len -= SipBuf(ctx, &s, len, 0);
140 	if (len == 0)
141 		return;
142 
143 	rem = len & 0x7;
144 	len >>= 3;
145 
146 	/* Optimze for 64bit aligned/unaligned access. */
147 	if (((uintptr_t)s & 0x7) == 0) {
148 		for (p = (const uint64_t *)s; len > 0; len--, p++) {
149 			m = le64toh(*p);
150 			ctx->v[3] ^= m;
151 			SipRounds(ctx, 0);
152 			ctx->v[0] ^= m;
153 		}
154 		s = (const uint8_t *)p;
155 	} else {
156 		for (; len > 0; len--, s += 8) {
157 			m = le64dec(s);
158 			ctx->v[3] ^= m;
159 			SipRounds(ctx, 0);
160 			ctx->v[0] ^= m;
161 		}
162 	}
163 
164 	/* Push remainder into buffer. */
165 	if (rem > 0)
166 		(void)SipBuf(ctx, &s, rem, 0);
167 }
168 
169 void
170 SipHash_Final(void *dst, SIPHASH_CTX *ctx)
171 {
172 	uint64_t r;
173 
174 	KASSERT(ctx->initialized == 2,
175 	    ("%s: context %p not properly initialized", __func__, ctx));
176 
177 	r = SipHash_End(ctx);
178 	le64enc(dst, r);
179 }
180 
181 uint64_t
182 SipHash_End(SIPHASH_CTX *ctx)
183 {
184 	uint64_t r;
185 
186 	KASSERT(ctx->initialized == 2,
187 	    ("%s: context %p not properly initialized", __func__, ctx));
188 
189 	SipBuf(ctx, NULL, 0, 1);
190 	ctx->v[2] ^= 0xff;
191 	SipRounds(ctx, 1);
192 	r = (ctx->v[0] ^ ctx->v[1]) ^ (ctx->v[2] ^ ctx->v[3]);
193 
194 	bzero(ctx, sizeof(*ctx));
195 	return (r);
196 }
197 
198 uint64_t
199 SipHashX(SIPHASH_CTX *ctx, int rc, int rf, const uint8_t key[16],
200     const void *src, size_t len)
201 {
202 
203 	SipHash_InitX(ctx, rc, rf);
204 	SipHash_SetKey(ctx, key);
205 	SipHash_Update(ctx, src, len);
206 
207 	return (SipHash_End(ctx));
208 }
209 
210 #define SIP_ROTL(x, b)	(uint64_t)(((x) << (b)) | ( (x) >> (64 - (b))))
211 
212 static void
213 SipRounds(SIPHASH_CTX *ctx, int final)
214 {
215 	int rounds;
216 
217 	if (!final)
218 		rounds = ctx->rounds_compr;
219 	else
220 		rounds = ctx->rounds_final;
221 
222 	while (rounds--) {
223 		ctx->v[0] += ctx->v[1];
224 		ctx->v[2] += ctx->v[3];
225 		ctx->v[1] = SIP_ROTL(ctx->v[1], 13);
226 		ctx->v[3] = SIP_ROTL(ctx->v[3], 16);
227 
228 		ctx->v[1] ^= ctx->v[0];
229 		ctx->v[3] ^= ctx->v[2];
230 		ctx->v[0] = SIP_ROTL(ctx->v[0], 32);
231 
232 		ctx->v[2] += ctx->v[1];
233 		ctx->v[0] += ctx->v[3];
234 		ctx->v[1] = SIP_ROTL(ctx->v[1], 17);
235 		ctx->v[3] = SIP_ROTL(ctx->v[3], 21);
236 
237 		ctx->v[1] ^= ctx->v[2];
238 		ctx->v[3] ^= ctx->v[0];
239 		ctx->v[2] = SIP_ROTL(ctx->v[2], 32);
240 	}
241 }
242 
243