From: Ulrik Sverdrup Date: Sun, 13 Jan 2013 15:24:11 +0000 (+0100) Subject: siphash: A keyed hash designed by Aumasson and djb X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=480b3117c39b91fcb6d39c60222232b7608f5507 siphash: A keyed hash designed by Aumasson and djb --- diff --git a/Makefile-ccan b/Makefile-ccan index 70f7c936..157f5d73 100644 --- a/Makefile-ccan +++ b/Makefile-ccan @@ -65,6 +65,7 @@ MODS_NORMAL_WITH_SRC := antithread \ rbuf \ read_write_all \ rfc822 \ + siphash \ sparse_bsearch \ str \ stringmap \ diff --git a/ccan/siphash/LICENSE b/ccan/siphash/LICENSE new file mode 120000 index 00000000..9961ca9d --- /dev/null +++ b/ccan/siphash/LICENSE @@ -0,0 +1 @@ +../../licenses/GPL-2 \ No newline at end of file diff --git a/ccan/siphash/_info b/ccan/siphash/_info new file mode 100644 index 00000000..e6d518aa --- /dev/null +++ b/ccan/siphash/_info @@ -0,0 +1,55 @@ +#include +#include +#include "config.h" + +/** + * siphash - a keyed hash function + * + * SipHash-c-d, where `c` is the number of rounds per message chunk + * and `d` the number of finalization rounds, + * "is a family of pseudorandom functions optimized for speed on short + * messages" + * + * Implemented from the paper https://131002.net/siphash/ + * The designers recommend using SipHash-2-4 or SipHash-4-8 + * + * SipHash-c-d uses a 16-byte key. + * To defend against hash-flooding, the application needs to use + * a new random key regularly. + * + * The designers of SipHash claim it is cryptographically strong + * to use as MAC with secret key but _not_collision_resistant_. + * + * Returns one 64-bit word as the hash function result. + * + * Example: + * // Outputs "cf2794e0277187b7" + * #include + * #include + * + * int main(void) + * { + * unsigned char t_key[16] = + * {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; + * unsigned char data[4] = "\0\1\2\3"; + * uint64_t hash = siphash_2_4(data, sizeof(data), t_key); + * printf("%llx\n", (unsigned long long)hash); + * + * return 0; + * } + * + * + * License: GPL (v2 or any later version) + */ +int main(int argc, char *argv[]) +{ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/endian\n"); + return 0; + } + + return 1; +} diff --git a/ccan/siphash/siphash.c b/ccan/siphash/siphash.c new file mode 100644 index 00000000..93eac040 --- /dev/null +++ b/ccan/siphash/siphash.c @@ -0,0 +1,85 @@ +/* Licensed under GPL v2+ - see LICENSE file for details */ + +#include + +#include "siphash.h" + +typedef uint64_t u64; + +enum sip_index { A=0, B=2, C=1, D=3, E=4 }; + +#define rol(x,l) (((x) << (l)) | ((x) >> (64-(l)))) + +#define SIP_HALF_ROUND(a,b,c,d,L1,L2) \ + (a) += (b); \ + (c) += (d); \ + (b) = (a) ^ rol((b),L1); \ + (d) = (c) ^ rol((d),L2); \ + (a) = rol((a),32); + +#define SIP_ROUND(W) \ + do { \ + SIP_HALF_ROUND((W)[A], (W)[B], (W)[C], (W)[D], 13, 16); \ + SIP_HALF_ROUND((W)[C], (W)[B], (W)[A], (W)[D], 17, 21); \ + } while(0) + +/* Load a 64-bit word as little endian */ +#define W64(S,I) (le64_to_cpu(*((u64 *)(S) + (I)))) + +static void siphash_init(u64 v[5], const unsigned char key[16]) +{ + v[A] = W64(key, 0) ^ UINT64_C(0x736f6d6570736575); + v[B] = W64(key, 1) ^ UINT64_C(0x646f72616e646f6d); + v[C] = W64(key, 0) ^ UINT64_C(0x6c7967656e657261); + v[D] = W64(key, 1) ^ UINT64_C(0x7465646279746573); + v[E] = 0; /* message continuation */ +} + +/* Load the last 0-7 bytes of `in` and put in len & 255 */ +static void siphash_epilogue(u64 *m, const void *in, size_t len) +{ + in = (char *)in + (len & ~7); + *m = (u64)(len & 255) << 56; + switch (len & 7) { + case 7: *m |= (u64)*((unsigned char *)in+6) << 48; + case 6: *m |= (u64)*((unsigned char *)in+5) << 40; + case 5: *m |= (u64)*((unsigned char *)in+4) << 32; + case 4: *m |= (u64)*((unsigned char *)in+3) << 24; + case 3: *m |= (u64)*((unsigned char *)in+2) << 16; + case 2: *m |= (u64)*((unsigned char *)in+1) << 8; + case 1: *m |= (u64)*((unsigned char *)in+0); + case 0: ; + } +} + +u64 siphash_2_4(const void *in, size_t len, const unsigned char key[16]) +{ + u64 v[5]; + size_t j; + + siphash_init(v, key); + + for (j = 0; j < len/8; j++) { + v[E] = W64(in, j); + v[D] ^= v[E]; + SIP_ROUND(v); + SIP_ROUND(v); + v[A] ^= v[E]; + } + siphash_epilogue(&v[E], in, len); + + v[D] ^= v[E]; + SIP_ROUND(v); + SIP_ROUND(v); + v[A] ^= v[E]; + + /* Finalize */ + v[C] ^= 0xff; + SIP_ROUND(v); + SIP_ROUND(v); + SIP_ROUND(v); + SIP_ROUND(v); + + return v[A]^v[B]^v[C]^v[D]; +} + diff --git a/ccan/siphash/siphash.h b/ccan/siphash/siphash.h new file mode 100644 index 00000000..55a391d2 --- /dev/null +++ b/ccan/siphash/siphash.h @@ -0,0 +1,50 @@ +#ifndef CCAN_SIPHASH_H_ +#define CCAN_SIPHASH_H_ + +/* Licensed under GPL v2+ - see LICENSE file for details */ +/* Written in 2013 by Ulrik Sverdrup */ + +#include +#include + +/** + * siphash - a keyed hash function + * + * SipHash-c-d, where `c` is the number of rounds per message chunk + * and `d` the number of finalization rounds, + * "is a family of pseudorandom functions optimized for speed on short + * messages" + * + * Implemented from the paper https://131002.net/siphash/ + * The designers recommend using SipHash-2-4 or SipHash-4-8 + * + * SipHash-c-d uses a 16-byte key. + * To defend against hash-flooding, the application needs to use + * a new random key regularly. + * + * The designers of SipHash claim it is cryptographically strong + * to use as MAC with secret key but _not_collision_resistant_. + * + * Returns one 64-bit word as the hash function result. + * + * Example: + * // Outputs "cf2794e0277187b7" + * #include + * #include + * + * int main(void) + * { + * unsigned char t_key[16] = + * {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; + * unsigned char data[4] = "\0\1\2\3"; + * uint64_t hash = siphash_2_4(data, sizeof(data), t_key); + * printf("%llx\n", (unsigned long long)hash); + * + * return 0; + * } + * + */ +uint64_t siphash_2_4(const void *in, size_t len, const unsigned char key[16]); + +#endif /* CCAN_SIPHASH_H_ */ + diff --git a/ccan/siphash/test/api.c b/ccan/siphash/test/api.c new file mode 100644 index 00000000..81394c7d --- /dev/null +++ b/ccan/siphash/test/api.c @@ -0,0 +1,79 @@ +#include +#include + +#include +#include + +typedef uint64_t u64; + + /* Testvectors for SipHash-2-4 */ +static const unsigned char t_key[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; +static const u64 t_s24exp[64] = { + 0x726fdb47dd0e0e31, 0x74f839c593dc67fd, + 0x0d6c8009d9a94f5a, 0x85676696d7fb7e2d, + 0xcf2794e0277187b7, 0x18765564cd99a68d, + 0xcbc9466e58fee3ce, 0xab0200f58b01d137, + 0x93f5f5799a932462, 0x9e0082df0ba9e4b0, + 0x7a5dbbc594ddb9f3, 0xf4b32f46226bada7, + 0x751e8fbc860ee5fb, 0x14ea5627c0843d90, + 0xf723ca908e7af2ee, 0xa129ca6149be45e5, + 0x3f2acc7f57c29bdb, 0x699ae9f52cbe4794, + 0x4bc1b3f0968dd39c, 0xbb6dc91da77961bd, + 0xbed65cf21aa2ee98, 0xd0f2cbb02e3b67c7, + 0x93536795e3a33e88, 0xa80c038ccd5ccec8, + 0xb8ad50c6f649af94, 0xbce192de8a85b8ea, + 0x17d835b85bbb15f3, 0x2f2e6163076bcfad, + 0xde4daaaca71dc9a5, 0xa6a2506687956571, + 0xad87a3535c49ef28, 0x32d892fad841c342, + 0x7127512f72f27cce, 0xa7f32346f95978e3, + 0x12e0b01abb051238, 0x15e034d40fa197ae, + 0x314dffbe0815a3b4, 0x027990f029623981, + 0xcadcd4e59ef40c4d, 0x9abfd8766a33735c, + 0x0e3ea96b5304a7d0, 0xad0c42d6fc585992, + 0x187306c89bc215a9, 0xd4a60abcf3792b95, + 0xf935451de4f21df2, 0xa9538f0419755787, + 0xdb9acddff56ca510, 0xd06c98cd5c0975eb, + 0xe612a3cb9ecba951, 0xc766e62cfcadaf96, + 0xee64435a9752fe72, 0xa192d576b245165a, + 0x0a8787bf8ecb74b2, 0x81b3e73d20b49b6f, + 0x7fa8220ba3b2ecea, 0x245731c13ca42499, + 0xb78dbfaf3a8d83bd, 0xea1ad565322a1a0b, + 0x60e61c23a3795013, 0x6606d7e446282b93, + 0x6ca4ecb15c5f91e1, 0x9f626da15c9625f3, + 0xe51b38608ef25f57, 0x958a324ceb064572, +}; + +#define CHECK_RET(MSG,IDX,EXP,GOT) \ + if ((EXP) != (GOT)) { \ + printf(MSG " %3d FAIL: Expect=%016"PRIx64" Got=%016"PRIx64"\n", \ + (IDX), (EXP), (GOT)); \ + return 0;\ + } + +#ifdef SPEEDTEST +#define PRT(...) +#define N 10000 +#else +#define PRT(...) printf(__VA_ARGS__) +#define N 1 +#endif + +static int siphash_sip24_test(void) +{ + unsigned char buf[64] = {0}; + int j; + u64 hash; + for (j = 0; j < 64; j++) { + buf[j] = j; + hash = siphash_2_4(buf, j, t_key); + + CHECK_RET("siphash_2_4", j, t_s24exp[j], hash); + } + PRT("SipHash-2-4 passed all tests.\n"); + return 1; +} + +int main(void) +{ + return !siphash_sip24_test(); +}