src/basic/siphash24.c

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