src/basic/siphash24.c

   1 /*
   2    SipHash reference C implementation
   3
   4    Written in 2012 by
   5    Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
   6    Daniel J. Bernstein <djb@cr.yp.to>
   7
   8    To the extent possible under law, the author(s) have dedicated all copyright
   9    and related and neighboring rights to this software to the public domain
  10    worldwide. This software is distributed without any warranty.
  11
  12    You should have received a copy of the CC0 Public Domain Dedication along with
  13    this software. If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
  14
  15    (Minimal changes made by Lennart Poettering, to make clean for inclusion in systemd)
  16    (Refactored by Tom Gundersen to split up in several functions and follow systemd
  17     coding style)
  18 */
  19
  20 #include <stdio.h>
  21
  22 #include "macro.h"
  23 #include "siphash24.h"
  24 #include "unaligned.h"
  25
  26 static uint64_t rotate_left(uint64_t x, uint8_t b) {
  27         assert(b < 64);
  28
  29         return (x << b) | (x >> (64 - b));
  30 }
  31
  32 static void sipround(struct siphash *state) {
  33         assert(state);
  34
  35         state->v0 += state->v1;
  36         state->v1 = rotate_left(state->v1, 13);
  37         state->v1 ^= state->v0;
  38         state->v0 = rotate_left(state->v0, 32);
  39         state->v2 += state->v3;
  40         state->v3 = rotate_left(state->v3, 16);
  41         state->v3 ^= state->v2;
  42         state->v0 += state->v3;
  43         state->v3 = rotate_left(state->v3, 21);
  44         state->v3 ^= state->v0;
  45         state->v2 += state->v1;
  46         state->v1 = rotate_left(state->v1, 17);
  47         state->v1 ^= state->v2;
  48         state->v2 = rotate_left(state->v2, 32);
  49 }
  50
  51 void siphash24_init(struct siphash *state, const uint8_t k[static 16]) {
  52         uint64_t k0, k1;
  53
  54         assert(state);
  55         assert(k);
  56
  57         k0 = unaligned_read_le64(k);
  58         k1 = unaligned_read_le64(k + 8);
  59
  60         *state = (struct siphash) {
  61                 /* "somepseudorandomlygeneratedbytes" */
  62                 .v0 = 0x736f6d6570736575ULL ^ k0,
  63                 .v1 = 0x646f72616e646f6dULL ^ k1,
  64                 .v2 = 0x6c7967656e657261ULL ^ k0,
  65                 .v3 = 0x7465646279746573ULL ^ k1,
  66                 .padding = 0,
  67                 .inlen = 0,
  68         };
  69 }
  70
  71 void siphash24_compress(const void *_in, size_t inlen, struct siphash *state) {
  72
  73         const uint8_t *in = _in;
  74         const uint8_t *end = in + inlen;
  75         size_t left = state->inlen & 7;
  76         uint64_t m;
  77
  78         assert(in);
  79         assert(state);
  80
  81         /* Update total length */
  82         state->inlen += inlen;
  83
  84         /* If padding exists, fill it out */
  85         if (left > 0) {
  86                 for ( ; in < end && left < 8; in ++, left ++)
  87                         state->padding |= ((uint64_t) *in) << (left * 8);
  88
  89                 if (in == end && left < 8)
  90                         /* We did not have enough input to fill out the padding completely */
  91                         return;
  92
  93 #if ENABLE_DEBUG_SIPHASH
  94                 printf("(%3zu) v0 %08x %08x\n", state->inlen, (uint32_t) (state->v0 >> 32), (uint32_t) state->v0);
  95                 printf("(%3zu) v1 %08x %08x\n", state->inlen, (uint32_t) (state->v1 >> 32), (uint32_t) state->v1);
  96                 printf("(%3zu) v2 %08x %08x\n", state->inlen, (uint32_t) (state->v2 >> 32), (uint32_t) state->v2);
  97                 printf("(%3zu) v3 %08x %08x\n", state->inlen, (uint32_t) (state->v3 >> 32), (uint32_t) state->v3);
  98                 printf("(%3zu) compress padding %08x %08x\n", state->inlen, (uint32_t) (state->padding >> 32), (uint32_t)state->padding);
  99 #endif
 100
 101                 state->v3 ^= state->padding;
 102                 sipround(state);
 103                 sipround(state);
 104                 state->v0 ^= state->padding;
 105
 106                 state->padding = 0;
 107         }
 108
 109         end -= (state->inlen % sizeof(uint64_t));
 110
 111         for ( ; in < end; in += 8) {
 112                 m = unaligned_read_le64(in);
 113 #if ENABLE_DEBUG_SIPHASH
 114                 printf("(%3zu) v0 %08x %08x\n", state->inlen, (uint32_t) (state->v0 >> 32), (uint32_t) state->v0);
 115                 printf("(%3zu) v1 %08x %08x\n", state->inlen, (uint32_t) (state->v1 >> 32), (uint32_t) state->v1);
 116                 printf("(%3zu) v2 %08x %08x\n", state->inlen, (uint32_t) (state->v2 >> 32), (uint32_t) state->v2);
 117                 printf("(%3zu) v3 %08x %08x\n", state->inlen, (uint32_t) (state->v3 >> 32), (uint32_t) state->v3);
 118                 printf("(%3zu) compress %08x %08x\n", state->inlen, (uint32_t) (m >> 32), (uint32_t) m);
 119 #endif
 120                 state->v3 ^= m;
 121                 sipround(state);
 122                 sipround(state);
 123                 state->v0 ^= m;
 124         }
 125
 126         left = state->inlen & 7;
 127         switch (left) {
 128                 case 7:
 129                         state->padding |= ((uint64_t) in[6]) << 48;
 130                         _fallthrough_;
 131                 case 6:
 132                         state->padding |= ((uint64_t) in[5]) << 40;
 133                         _fallthrough_;
 134                 case 5:
 135                         state->padding |= ((uint64_t) in[4]) << 32;
 136                         _fallthrough_;
 137                 case 4:
 138                         state->padding |= ((uint64_t) in[3]) << 24;
 139                         _fallthrough_;
 140                 case 3:
 141                         state->padding |= ((uint64_t) in[2]) << 16;
 142                         _fallthrough_;
 143                 case 2:
 144                         state->padding |= ((uint64_t) in[1]) <<  8;
 145                         _fallthrough_;
 146                 case 1:
 147                         state->padding |= ((uint64_t) in[0]);
 148                         _fallthrough_;
 149                 case 0:
 150                         break;
 151         }
 152 }
 153
 154 void siphash24_compress_boolean(bool in, struct siphash *state) {
 155         int i = in;
 156
 157         siphash24_compress(&i, sizeof i, state);
 158 }
 159
 160 uint64_t siphash24_finalize(struct siphash *state) {
 161         uint64_t b;
 162
 163         assert(state);
 164
 165         b = state->padding | (((uint64_t) state->inlen) << 56);
 166
 167 #if ENABLE_DEBUG_SIPHASH
 168         printf("(%3zu) v0 %08x %08x\n", state->inlen, (uint32_t) (state->v0 >> 32), (uint32_t) state->v0);
 169         printf("(%3zu) v1 %08x %08x\n", state->inlen, (uint32_t) (state->v1 >> 32), (uint32_t) state->v1);
 170         printf("(%3zu) v2 %08x %08x\n", state->inlen, (uint32_t) (state->v2 >> 32), (uint32_t) state->v2);
 171         printf("(%3zu) v3 %08x %08x\n", state->inlen, (uint32_t) (state->v3 >> 32), (uint32_t) state->v3);
 172         printf("(%3zu) padding   %08x %08x\n", state->inlen, (uint32_t) (state->padding >> 32), (uint32_t) state->padding);
 173 #endif
 174
 175         state->v3 ^= b;
 176         sipround(state);
 177         sipround(state);
 178         state->v0 ^= b;
 179
 180 #if ENABLE_DEBUG_SIPHASH
 181         printf("(%3zu) v0 %08x %08x\n", state->inlen, (uint32_t) (state->v0 >> 32), (uint32_t) state->v0);
 182         printf("(%3zu) v1 %08x %08x\n", state->inlen, (uint32_t) (state->v1 >> 32), (uint32_t) state->v1);
 183         printf("(%3zu) v2 %08x %08x\n", state->inlen, (uint32_t) (state->v2 >> 32), (uint32_t) state->v2);
 184         printf("(%3zu) v3 %08x %08x\n", state->inlen, (uint32_t) (state->v3 >> 32), (uint32_t) state->v3);
 185 #endif
 186         state->v2 ^= 0xff;
 187
 188         sipround(state);
 189         sipround(state);
 190         sipround(state);
 191         sipround(state);
 192
 193         return state->v0 ^ state->v1 ^ state->v2  ^ state->v3;
 194 }
 195
 196 uint64_t siphash24(const void *in, size_t inlen, const uint8_t k[static 16]) {
 197         struct siphash state;
 198
 199         assert(in);
 200         assert(k);
 201
 202         siphash24_init(&state, k);
 203         siphash24_compress(in, inlen, &state);
 204
 205         return siphash24_finalize(&state);
 206 }