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 = ASSERT_PTR(_in);
  76         const uint8_t *end = in + inlen;
  77         size_t left = state->inlen & 7;
  78         uint64_t m;
  79
  80         assert(state);
  81
  82         /* Update total length */
  83         state->inlen += inlen;
  84
  85         /* If padding exists, fill it out */
  86         if (left > 0) {
  87                 for ( ; in < end && left < 8; in ++, left ++)
  88                         state->padding |= ((uint64_t) *in) << (left * 8);
  89
  90                 if (in == end && left < 8)
  91                         /* We did not have enough input to fill out the padding completely */
  92                         return;
  93
  94 #if ENABLE_DEBUG_SIPHASH
  95                 printf("(%3zu) v0 %08x %08x\n", state->inlen, (uint32_t) (state->v0 >> 32), (uint32_t) state->v0);
  96                 printf("(%3zu) v1 %08x %08x\n", state->inlen, (uint32_t) (state->v1 >> 32), (uint32_t) state->v1);
  97                 printf("(%3zu) v2 %08x %08x\n", state->inlen, (uint32_t) (state->v2 >> 32), (uint32_t) state->v2);
  98                 printf("(%3zu) v3 %08x %08x\n", state->inlen, (uint32_t) (state->v3 >> 32), (uint32_t) state->v3);
  99                 printf("(%3zu) compress padding %08x %08x\n", state->inlen, (uint32_t) (state->padding >> 32), (uint32_t)state->padding);
 100 #endif
 101
 102                 state->v3 ^= state->padding;
 103                 sipround(state);
 104                 sipround(state);
 105                 state->v0 ^= state->padding;
 106
 107                 state->padding = 0;
 108         }
 109
 110         end -= (state->inlen % sizeof(uint64_t));
 111
 112         for ( ; in < end; in += 8) {
 113                 m = unaligned_read_le64(in);
 114 #if ENABLE_DEBUG_SIPHASH
 115                 printf("(%3zu) v0 %08x %08x\n", state->inlen, (uint32_t) (state->v0 >> 32), (uint32_t) state->v0);
 116                 printf("(%3zu) v1 %08x %08x\n", state->inlen, (uint32_t) (state->v1 >> 32), (uint32_t) state->v1);
 117                 printf("(%3zu) v2 %08x %08x\n", state->inlen, (uint32_t) (state->v2 >> 32), (uint32_t) state->v2);
 118                 printf("(%3zu) v3 %08x %08x\n", state->inlen, (uint32_t) (state->v3 >> 32), (uint32_t) state->v3);
 119                 printf("(%3zu) compress %08x %08x\n", state->inlen, (uint32_t) (m >> 32), (uint32_t) m);
 120 #endif
 121                 state->v3 ^= m;
 122                 sipround(state);
 123                 sipround(state);
 124                 state->v0 ^= m;
 125         }
 126
 127         left = state->inlen & 7;
 128         switch (left) {
 129                 case 7:
 130                         state->padding |= ((uint64_t) in[6]) << 48;
 131                         _fallthrough_;
 132                 case 6:
 133                         state->padding |= ((uint64_t) in[5]) << 40;
 134                         _fallthrough_;
 135                 case 5:
 136                         state->padding |= ((uint64_t) in[4]) << 32;
 137                         _fallthrough_;
 138                 case 4:
 139                         state->padding |= ((uint64_t) in[3]) << 24;
 140                         _fallthrough_;
 141                 case 3:
 142                         state->padding |= ((uint64_t) in[2]) << 16;
 143                         _fallthrough_;
 144                 case 2:
 145                         state->padding |= ((uint64_t) in[1]) <<  8;
 146                         _fallthrough_;
 147                 case 1:
 148                         state->padding |= ((uint64_t) in[0]);
 149                         _fallthrough_;
 150                 case 0:
 151                         break;
 152         }
 153 }
 154
 155 uint64_t siphash24_finalize(struct siphash *state) {
 156         uint64_t b;
 157
 158         assert(state);
 159
 160         b = state->padding | (((uint64_t) state->inlen) << 56);
 161
 162 #if ENABLE_DEBUG_SIPHASH
 163         printf("(%3zu) v0 %08x %08x\n", state->inlen, (uint32_t) (state->v0 >> 32), (uint32_t) state->v0);
 164         printf("(%3zu) v1 %08x %08x\n", state->inlen, (uint32_t) (state->v1 >> 32), (uint32_t) state->v1);
 165         printf("(%3zu) v2 %08x %08x\n", state->inlen, (uint32_t) (state->v2 >> 32), (uint32_t) state->v2);
 166         printf("(%3zu) v3 %08x %08x\n", state->inlen, (uint32_t) (state->v3 >> 32), (uint32_t) state->v3);
 167         printf("(%3zu) padding   %08x %08x\n", state->inlen, (uint32_t) (state->padding >> 32), (uint32_t) state->padding);
 168 #endif
 169
 170         state->v3 ^= b;
 171         sipround(state);
 172         sipround(state);
 173         state->v0 ^= b;
 174
 175 #if ENABLE_DEBUG_SIPHASH
 176         printf("(%3zu) v0 %08x %08x\n", state->inlen, (uint32_t) (state->v0 >> 32), (uint32_t) state->v0);
 177         printf("(%3zu) v1 %08x %08x\n", state->inlen, (uint32_t) (state->v1 >> 32), (uint32_t) state->v1);
 178         printf("(%3zu) v2 %08x %08x\n", state->inlen, (uint32_t) (state->v2 >> 32), (uint32_t) state->v2);
 179         printf("(%3zu) v3 %08x %08x\n", state->inlen, (uint32_t) (state->v3 >> 32), (uint32_t) state->v3);
 180 #endif
 181         state->v2 ^= 0xff;
 182
 183         sipround(state);
 184         sipround(state);
 185         sipround(state);
 186         sipround(state);
 187
 188         return state->v0 ^ state->v1 ^ state->v2  ^ state->v3;
 189 }
 190
 191 uint64_t siphash24(const void *in, size_t inlen, const uint8_t k[static 16]) {
 192         struct siphash state;
 193
 194         assert(in);
 195         assert(k);
 196
 197         siphash24_init(&state, k);
 198         siphash24_compress(in, inlen, &state);
 199
 200         return siphash24_finalize(&state);
 201 }