ext/tdb/siphash24.c

   1 #include "rbtdb.h"
   2 /*
   3    SipHash reference C implementation
   4    Trivially adapted by Eric Wong for ruby-tdb
   5
   6    Written in 2012 by
   7    Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
   8    Daniel J. Bernstein <djb@cr.yp.to>
   9
  10    To the extent possible under law, the author(s) have dedicated all copyright
  11    and related and neighboring rights to this software to the public domain
  12    worldwide. This software is distributed without any warranty.
  13
  14    You should have received a copy of the CC0 Public Domain Dedication along with
  15    this software. If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
  16 */
  17 #include <stdint.h>
  18 #include <stdio.h>
  19 #include <string.h>
  20 typedef uint64_t u64;
  21 typedef uint32_t u32;
  22 typedef uint8_t u8;
  23
  24 #define ROTL(x,b) (u64)( ((x) << (b)) | ( (x) >> (64 - (b))) )
  25
  26 #define U32TO8_LE(p, v)         \
  27     (p)[0] = (u8)((v)      ); (p)[1] = (u8)((v) >>  8); \
  28     (p)[2] = (u8)((v) >> 16); (p)[3] = (u8)((v) >> 24);
  29
  30 #define U64TO8_LE(p, v)         \
  31   U32TO8_LE((p),     (u32)((v)      ));   \
  32   U32TO8_LE((p) + 4, (u32)((v) >> 32));
  33
  34 #define U8TO64_LE(p) \
  35   (((u64)((p)[0])      ) | \
  36    ((u64)((p)[1]) <<  8) | \
  37    ((u64)((p)[2]) << 16) | \
  38    ((u64)((p)[3]) << 24) | \
  39    ((u64)((p)[4]) << 32) | \
  40    ((u64)((p)[5]) << 40) | \
  41    ((u64)((p)[6]) << 48) | \
  42    ((u64)((p)[7]) << 56))
  43
  44 #define SIPROUND            \
  45   do {              \
  46     v0 += v1; v1=ROTL(v1,13); v1 ^= v0; v0=ROTL(v0,32); \
  47     v2 += v3; v3=ROTL(v3,16); v3 ^= v2;     \
  48     v0 += v3; v3=ROTL(v3,21); v3 ^= v0;     \
  49     v2 += v1; v1=ROTL(v1,17); v1 ^= v2; v2=ROTL(v2,32); \
  50   } while(0)
  51
  52 /* SipHash-2-4 */
  53 static int
  54 crypto_auth(unsigned char *out, const unsigned char *in,
  55             size_t inlen, const unsigned char *k)
  56 {
  57         /* "somepseudorandomlygeneratedbytes" */
  58         u64 v0 = 0x736f6d6570736575ULL;
  59         u64 v1 = 0x646f72616e646f6dULL;
  60         u64 v2 = 0x6c7967656e657261ULL;
  61         u64 v3 = 0x7465646279746573ULL;
  62         u64 b;
  63         u64 k0 = U8TO64_LE(k);
  64         u64 k1 = U8TO64_LE(k + 8);
  65         u64 m;
  66         const u8 *end = in + inlen - (inlen % sizeof(u64));
  67         const int left = inlen & 7;
  68         b = ((u64) inlen) << 56;
  69         v3 ^= k1;
  70         v2 ^= k0;
  71         v1 ^= k1;
  72         v0 ^= k0;
  73
  74         for (; in != end; in += 8) {
  75                 m = U8TO64_LE(in);
  76 #ifdef DEBUG
  77                 printf("(%3d) v0 %08x %08x\n", (int)inlen, (u32) (v0 >> 32),
  78                        (u32) v0);
  79                 printf("(%3d) v1 %08x %08x\n", (int)inlen, (u32) (v1 >> 32),
  80                        (u32) v1);
  81                 printf("(%3d) v2 %08x %08x\n", (int)inlen, (u32) (v2 >> 32),
  82                        (u32) v2);
  83                 printf("(%3d) v3 %08x %08x\n", (int)inlen, (u32) (v3 >> 32),
  84                        (u32) v3);
  85                 printf("(%3d) compress %08x %08x\n", (int)inlen,
  86                        (u32) (m >> 32), (u32) m);
  87 #endif
  88                 v3 ^= m;
  89                 SIPROUND;
  90                 SIPROUND;
  91                 v0 ^= m;
  92         }
  93
  94         switch (left) {
  95         case 7:
  96                 b |= ((u64) in[6]) << 48;
  97
  98         case 6:
  99                 b |= ((u64) in[5]) << 40;
 100
 101         case 5:
 102                 b |= ((u64) in[4]) << 32;
 103
 104         case 4:
 105                 b |= ((u64) in[3]) << 24;
 106
 107         case 3:
 108                 b |= ((u64) in[2]) << 16;
 109
 110         case 2:
 111                 b |= ((u64) in[1]) << 8;
 112
 113         case 1:
 114                 b |= ((u64) in[0]);
 115                 break;
 116
 117         case 0:
 118                 break;
 119         }
 120
 121 #ifdef DEBUG
 122         printf("(%3d) v0 %08x %08x\n", (int)inlen, (u32) (v0 >> 32), (u32) v0);
 123         printf("(%3d) v1 %08x %08x\n", (int)inlen, (u32) (v1 >> 32), (u32) v1);
 124         printf("(%3d) v2 %08x %08x\n", (int)inlen, (u32) (v2 >> 32), (u32) v2);
 125         printf("(%3d) v3 %08x %08x\n", (int)inlen, (u32) (v3 >> 32), (u32) v3);
 126         printf("(%3d) padding   %08x %08x\n", (int)inlen, (u32) (b >> 32),
 127                (u32) b);
 128 #endif
 129         v3 ^= b;
 130         SIPROUND;
 131         SIPROUND;
 132         v0 ^= b;
 133 #ifdef DEBUG
 134         printf("(%3d) v0 %08x %08x\n", (int)inlen, (u32) (v0 >> 32), (u32) v0);
 135         printf("(%3d) v1 %08x %08x\n", (int)inlen, (u32) (v1 >> 32), (u32) v1);
 136         printf("(%3d) v2 %08x %08x\n", (int)inlen, (u32) (v2 >> 32), (u32) v2);
 137         printf("(%3d) v3 %08x %08x\n", (int)inlen, (u32) (v3 >> 32), (u32) v3);
 138 #endif
 139         v2 ^= 0xff;
 140         SIPROUND;
 141         SIPROUND;
 142         SIPROUND;
 143         SIPROUND;
 144         b = v0 ^ v1 ^ v2 ^ v3;
 145         U64TO8_LE(out, b);
 146         return 0;
 147 }
 148
 149 /*
 150    SipHash-2-4 output with
 151    k = 00 01 02 ...
 152    and
 153    in = (empty string)
 154    in = 00 (1 byte)
 155    in = 00 01 (2 bytes)
 156    in = 00 01 02 (3 bytes)
 157    ...
 158    in = 00 01 02 ... 3e (63 bytes)
 159 */
 160 u8 vectors[64][8] = {
 161         {0x31, 0x0e, 0x0e, 0xdd, 0x47, 0xdb, 0x6f, 0x72,}
 162         ,
 163         {0xfd, 0x67, 0xdc, 0x93, 0xc5, 0x39, 0xf8, 0x74,}
 164         ,
 165         {0x5a, 0x4f, 0xa9, 0xd9, 0x09, 0x80, 0x6c, 0x0d,}
 166         ,
 167         {0x2d, 0x7e, 0xfb, 0xd7, 0x96, 0x66, 0x67, 0x85,}
 168         ,
 169         {0xb7, 0x87, 0x71, 0x27, 0xe0, 0x94, 0x27, 0xcf,}
 170         ,
 171         {0x8d, 0xa6, 0x99, 0xcd, 0x64, 0x55, 0x76, 0x18,}
 172         ,
 173         {0xce, 0xe3, 0xfe, 0x58, 0x6e, 0x46, 0xc9, 0xcb,}
 174         ,
 175         {0x37, 0xd1, 0x01, 0x8b, 0xf5, 0x00, 0x02, 0xab,}
 176         ,
 177         {0x62, 0x24, 0x93, 0x9a, 0x79, 0xf5, 0xf5, 0x93,}
 178         ,
 179         {0xb0, 0xe4, 0xa9, 0x0b, 0xdf, 0x82, 0x00, 0x9e,}
 180         ,
 181         {0xf3, 0xb9, 0xdd, 0x94, 0xc5, 0xbb, 0x5d, 0x7a,}
 182         ,
 183         {0xa7, 0xad, 0x6b, 0x22, 0x46, 0x2f, 0xb3, 0xf4,}
 184         ,
 185         {0xfb, 0xe5, 0x0e, 0x86, 0xbc, 0x8f, 0x1e, 0x75,}
 186         ,
 187         {0x90, 0x3d, 0x84, 0xc0, 0x27, 0x56, 0xea, 0x14,}
 188         ,
 189         {0xee, 0xf2, 0x7a, 0x8e, 0x90, 0xca, 0x23, 0xf7,}
 190         ,
 191         {0xe5, 0x45, 0xbe, 0x49, 0x61, 0xca, 0x29, 0xa1,}
 192         ,
 193         {0xdb, 0x9b, 0xc2, 0x57, 0x7f, 0xcc, 0x2a, 0x3f,}
 194         ,
 195         {0x94, 0x47, 0xbe, 0x2c, 0xf5, 0xe9, 0x9a, 0x69,}
 196         ,
 197         {0x9c, 0xd3, 0x8d, 0x96, 0xf0, 0xb3, 0xc1, 0x4b,}
 198         ,
 199         {0xbd, 0x61, 0x79, 0xa7, 0x1d, 0xc9, 0x6d, 0xbb,}
 200         ,
 201         {0x98, 0xee, 0xa2, 0x1a, 0xf2, 0x5c, 0xd6, 0xbe,}
 202         ,
 203         {0xc7, 0x67, 0x3b, 0x2e, 0xb0, 0xcb, 0xf2, 0xd0,}
 204         ,
 205         {0x88, 0x3e, 0xa3, 0xe3, 0x95, 0x67, 0x53, 0x93,}
 206         ,
 207         {0xc8, 0xce, 0x5c, 0xcd, 0x8c, 0x03, 0x0c, 0xa8,}
 208         ,
 209         {0x94, 0xaf, 0x49, 0xf6, 0xc6, 0x50, 0xad, 0xb8,}
 210         ,
 211         {0xea, 0xb8, 0x85, 0x8a, 0xde, 0x92, 0xe1, 0xbc,}
 212         ,
 213         {0xf3, 0x15, 0xbb, 0x5b, 0xb8, 0x35, 0xd8, 0x17,}
 214         ,
 215         {0xad, 0xcf, 0x6b, 0x07, 0x63, 0x61, 0x2e, 0x2f,}
 216         ,
 217         {0xa5, 0xc9, 0x1d, 0xa7, 0xac, 0xaa, 0x4d, 0xde,}
 218         ,
 219         {0x71, 0x65, 0x95, 0x87, 0x66, 0x50, 0xa2, 0xa6,}
 220         ,
 221         {0x28, 0xef, 0x49, 0x5c, 0x53, 0xa3, 0x87, 0xad,}
 222         ,
 223         {0x42, 0xc3, 0x41, 0xd8, 0xfa, 0x92, 0xd8, 0x32,}
 224         ,
 225         {0xce, 0x7c, 0xf2, 0x72, 0x2f, 0x51, 0x27, 0x71,}
 226         ,
 227         {0xe3, 0x78, 0x59, 0xf9, 0x46, 0x23, 0xf3, 0xa7,}
 228         ,
 229         {0x38, 0x12, 0x05, 0xbb, 0x1a, 0xb0, 0xe0, 0x12,}
 230         ,
 231         {0xae, 0x97, 0xa1, 0x0f, 0xd4, 0x34, 0xe0, 0x15,}
 232         ,
 233         {0xb4, 0xa3, 0x15, 0x08, 0xbe, 0xff, 0x4d, 0x31,}
 234         ,
 235         {0x81, 0x39, 0x62, 0x29, 0xf0, 0x90, 0x79, 0x02,}
 236         ,
 237         {0x4d, 0x0c, 0xf4, 0x9e, 0xe5, 0xd4, 0xdc, 0xca,}
 238         ,
 239         {0x5c, 0x73, 0x33, 0x6a, 0x76, 0xd8, 0xbf, 0x9a,}
 240         ,
 241         {0xd0, 0xa7, 0x04, 0x53, 0x6b, 0xa9, 0x3e, 0x0e,}
 242         ,
 243         {0x92, 0x59, 0x58, 0xfc, 0xd6, 0x42, 0x0c, 0xad,}
 244         ,
 245         {0xa9, 0x15, 0xc2, 0x9b, 0xc8, 0x06, 0x73, 0x18,}
 246         ,
 247         {0x95, 0x2b, 0x79, 0xf3, 0xbc, 0x0a, 0xa6, 0xd4,}
 248         ,
 249         {0xf2, 0x1d, 0xf2, 0xe4, 0x1d, 0x45, 0x35, 0xf9,}
 250         ,
 251         {0x87, 0x57, 0x75, 0x19, 0x04, 0x8f, 0x53, 0xa9,}
 252         ,
 253         {0x10, 0xa5, 0x6c, 0xf5, 0xdf, 0xcd, 0x9a, 0xdb,}
 254         ,
 255         {0xeb, 0x75, 0x09, 0x5c, 0xcd, 0x98, 0x6c, 0xd0,}
 256         ,
 257         {0x51, 0xa9, 0xcb, 0x9e, 0xcb, 0xa3, 0x12, 0xe6,}
 258         ,
 259         {0x96, 0xaf, 0xad, 0xfc, 0x2c, 0xe6, 0x66, 0xc7,}
 260         ,
 261         {0x72, 0xfe, 0x52, 0x97, 0x5a, 0x43, 0x64, 0xee,}
 262         ,
 263         {0x5a, 0x16, 0x45, 0xb2, 0x76, 0xd5, 0x92, 0xa1,}
 264         ,
 265         {0xb2, 0x74, 0xcb, 0x8e, 0xbf, 0x87, 0x87, 0x0a,}
 266         ,
 267         {0x6f, 0x9b, 0xb4, 0x20, 0x3d, 0xe7, 0xb3, 0x81,}
 268         ,
 269         {0xea, 0xec, 0xb2, 0xa3, 0x0b, 0x22, 0xa8, 0x7f,}
 270         ,
 271         {0x99, 0x24, 0xa4, 0x3c, 0xc1, 0x31, 0x57, 0x24,}
 272         ,
 273         {0xbd, 0x83, 0x8d, 0x3a, 0xaf, 0xbf, 0x8d, 0xb7,}
 274         ,
 275         {0x0b, 0x1a, 0x2a, 0x32, 0x65, 0xd5, 0x1a, 0xea,}
 276         ,
 277         {0x13, 0x50, 0x79, 0xa3, 0x23, 0x1c, 0xe6, 0x60,}
 278         ,
 279         {0x93, 0x2b, 0x28, 0x46, 0xe4, 0xd7, 0x06, 0x66,}
 280         ,
 281         {0xe1, 0x91, 0x5f, 0x5c, 0xb1, 0xec, 0xa4, 0x6c,}
 282         ,
 283         {0xf3, 0x25, 0x96, 0x5c, 0xa1, 0x6d, 0x62, 0x9f,}
 284         ,
 285         {0x57, 0x5f, 0xf2, 0x8e, 0x60, 0x38, 0x1b, 0xe5,}
 286         ,
 287         {0x72, 0x45, 0x06, 0xeb, 0x4c, 0x32, 0x8a, 0x95,}
 288 };
 289
 290 int rbtdb_siphash_test_vectors(void)
 291 {
 292 #define MAXLEN 64
 293         u8 in[MAXLEN], out[8], k[16];
 294         int i;
 295         int ok = 1;
 296
 297         for (i = 0; i < 16; ++i)
 298                 k[i] = i;
 299
 300         for (i = 0; i < MAXLEN; ++i) {
 301                 in[i] = i;
 302                 crypto_auth(out, in, i, k);
 303
 304                 if (memcmp(out, vectors[i], 8)) {
 305                         printf("test vector failed for %d bytes\n", i);
 306                         ok = 0;
 307                 }
 308         }
 309
 310         return ok;
 311 }
 312
 313 unsigned int rbtdb_siphash24(TDB_DATA *data)
 314 {
 315         /* n.b.: tdb is for persistent storage, so the key must be constant */
 316         static uint8_t key[] = "trivial database";
 317         /* static const uint8_t check[(sizeof(key) >= 16)]; */
 318         union {
 319                 uint32_t x32[2];
 320                 uint64_t x64;
 321         } out;
 322         unsigned char *in = data->dptr;
 323         size_t len = data->dsize;
 324
 325         crypto_auth((unsigned char *)&out, in, len, key);
 326
 327         return (unsigned int)(out.x32[0] ^ out.x32[1]);
 328 }