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/param.h> 45 #include <sys/systm.h> 46 #include <sys/endian.h> 47 48 #include <crypto/siphash/siphash.h> 49 50 static void SipRounds(SIPHASH_CTX *ctx, int final); 51 52 void 53 SipHash_InitX(SIPHASH_CTX *ctx, int rc, int rf) 54 { 55 56 ctx->v[0] = 0x736f6d6570736575ull; 57 ctx->v[1] = 0x646f72616e646f6dull; 58 ctx->v[2] = 0x6c7967656e657261ull; 59 ctx->v[3] = 0x7465646279746573ull; 60 ctx->buf.b64 = 0; 61 ctx->bytes = 0; 62 ctx->buflen = 0; 63 ctx->rounds_compr = rc; 64 ctx->rounds_final = rf; 65 ctx->initialized = 1; 66 } 67 68 void 69 SipHash_SetKey(SIPHASH_CTX *ctx, const uint8_t key[static SIPHASH_KEY_LENGTH]) 70 { 71 uint64_t k[2]; 72 73 KASSERT(ctx->v[0] == 0x736f6d6570736575ull && ctx->initialized == 1, 74 ("%s: context %p not properly initialized", __func__, ctx)); 75 76 k[0] = le64dec(&key[0]); 77 k[1] = le64dec(&key[8]); 78 79 ctx->v[0] ^= k[0]; 80 ctx->v[1] ^= k[1]; 81 ctx->v[2] ^= k[0]; 82 ctx->v[3] ^= k[1]; 83 84 ctx->initialized = 2; 85 } 86 87 static size_t 88 SipBuf(SIPHASH_CTX *ctx, const uint8_t **src, size_t len, int final) 89 { 90 size_t x = 0; 91 92 KASSERT((!final && len > 0) || (final && len == 0), 93 ("%s: invalid parameters", __func__)); 94 95 if (!final) { 96 x = MIN(len, sizeof(ctx->buf.b64) - ctx->buflen); 97 bcopy(*src, &ctx->buf.b8[ctx->buflen], x); 98 ctx->buflen += x; 99 *src += x; 100 } else 101 ctx->buf.b8[7] = (uint8_t)ctx->bytes; 102 103 if (ctx->buflen == 8 || final) { 104 ctx->v[3] ^= le64toh(ctx->buf.b64); 105 SipRounds(ctx, 0); 106 ctx->v[0] ^= le64toh(ctx->buf.b64); 107 ctx->buf.b64 = 0; 108 ctx->buflen = 0; 109 } 110 return (x); 111 } 112 113 void 114 SipHash_Update(SIPHASH_CTX *ctx, const void *src, size_t len) 115 { 116 uint64_t m; 117 const uint64_t *p; 118 const uint8_t *s; 119 size_t rem; 120 121 KASSERT(ctx->initialized == 2, 122 ("%s: context %p not properly initialized", __func__, ctx)); 123 124 s = src; 125 ctx->bytes += len; 126 127 /* 128 * Push length smaller than block size into buffer or 129 * fill up the buffer if there is already something 130 * in it. 131 */ 132 if (ctx->buflen > 0 || len < 8) 133 len -= SipBuf(ctx, &s, len, 0); 134 if (len == 0) 135 return; 136 137 rem = len & 0x7; 138 len >>= 3; 139 140 /* Optimze for 64bit aligned/unaligned access. */ 141 if (((uintptr_t)s & 0x7) == 0) { 142 for (p = (const uint64_t *)s; len > 0; len--, p++) { 143 m = le64toh(*p); 144 ctx->v[3] ^= m; 145 SipRounds(ctx, 0); 146 ctx->v[0] ^= m; 147 } 148 s = (const uint8_t *)p; 149 } else { 150 for (; len > 0; len--, s += 8) { 151 m = le64dec(s); 152 ctx->v[3] ^= m; 153 SipRounds(ctx, 0); 154 ctx->v[0] ^= m; 155 } 156 } 157 158 /* Push remainder into buffer. */ 159 if (rem > 0) 160 (void)SipBuf(ctx, &s, rem, 0); 161 } 162 163 void 164 SipHash_Final(uint8_t dst[static SIPHASH_DIGEST_LENGTH], SIPHASH_CTX *ctx) 165 { 166 uint64_t r; 167 168 KASSERT(ctx->initialized == 2, 169 ("%s: context %p not properly initialized", __func__, ctx)); 170 171 r = SipHash_End(ctx); 172 le64enc(dst, r); 173 } 174 175 uint64_t 176 SipHash_End(SIPHASH_CTX *ctx) 177 { 178 uint64_t r; 179 180 KASSERT(ctx->initialized == 2, 181 ("%s: context %p not properly initialized", __func__, ctx)); 182 183 SipBuf(ctx, NULL, 0, 1); 184 ctx->v[2] ^= 0xff; 185 SipRounds(ctx, 1); 186 r = (ctx->v[0] ^ ctx->v[1]) ^ (ctx->v[2] ^ ctx->v[3]); 187 188 bzero(ctx, sizeof(*ctx)); 189 return (r); 190 } 191 192 uint64_t 193 SipHashX(SIPHASH_CTX *ctx, int rc, int rf, 194 const uint8_t key[static SIPHASH_KEY_LENGTH], const void *src, size_t len) 195 { 196 197 SipHash_InitX(ctx, rc, rf); 198 SipHash_SetKey(ctx, key); 199 SipHash_Update(ctx, src, len); 200 201 return (SipHash_End(ctx)); 202 } 203 204 #define SIP_ROTL(x, b) (uint64_t)(((x) << (b)) | ( (x) >> (64 - (b)))) 205 206 static void 207 SipRounds(SIPHASH_CTX *ctx, int final) 208 { 209 int rounds; 210 211 if (!final) 212 rounds = ctx->rounds_compr; 213 else 214 rounds = ctx->rounds_final; 215 216 while (rounds--) { 217 ctx->v[0] += ctx->v[1]; 218 ctx->v[2] += ctx->v[3]; 219 ctx->v[1] = SIP_ROTL(ctx->v[1], 13); 220 ctx->v[3] = SIP_ROTL(ctx->v[3], 16); 221 222 ctx->v[1] ^= ctx->v[0]; 223 ctx->v[3] ^= ctx->v[2]; 224 ctx->v[0] = SIP_ROTL(ctx->v[0], 32); 225 226 ctx->v[2] += ctx->v[1]; 227 ctx->v[0] += ctx->v[3]; 228 ctx->v[1] = SIP_ROTL(ctx->v[1], 17); 229 ctx->v[3] = SIP_ROTL(ctx->v[3], 21); 230 231 ctx->v[1] ^= ctx->v[2]; 232 ctx->v[3] ^= ctx->v[0]; 233 ctx->v[2] = SIP_ROTL(ctx->v[2], 32); 234 } 235 } 236