lib/siphash.c

   1 /* Copyright (C) 2016 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.
   2  *
   3  * This file is provided under a dual BSD/GPLv2 license.
   4  *
   5  * SipHash: a fast short-input PRF
   6  * https://131002.net/siphash/
   7  *
   8  * This implementation is specifically for SipHash2-4 for a secure PRF
   9  * and HalfSipHash1-3/SipHash1-3 for an insecure PRF only suitable for
  10  * hashtables.
  11  */
  12
  13 #include <linux/siphash.h>
  14 #include <asm/unaligned.h>
  15
  16 #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
  17 #include <linux/dcache.h>
  18 #include <asm/word-at-a-time.h>
  19 #endif
  20
  21 #define SIPROUND \
  22         do { \
  23         v0 += v1; v1 = rol64(v1, 13); v1 ^= v0; v0 = rol64(v0, 32); \
  24         v2 += v3; v3 = rol64(v3, 16); v3 ^= v2; \
  25         v0 += v3; v3 = rol64(v3, 21); v3 ^= v0; \
  26         v2 += v1; v1 = rol64(v1, 17); v1 ^= v2; v2 = rol64(v2, 32); \
  27         } while (0)
  28
  29 #define PREAMBLE(len) \
  30         u64 v0 = 0x736f6d6570736575ULL; \
  31         u64 v1 = 0x646f72616e646f6dULL; \
  32         u64 v2 = 0x6c7967656e657261ULL; \
  33         u64 v3 = 0x7465646279746573ULL; \
  34         u64 b = ((u64)(len)) << 56; \
  35         v3 ^= key->key[1]; \
  36         v2 ^= key->key[0]; \
  37         v1 ^= key->key[1]; \
  38         v0 ^= key->key[0];
  39
  40 #define POSTAMBLE \
  41         v3 ^= b; \
  42         SIPROUND; \
  43         SIPROUND; \
  44         v0 ^= b; \
  45         v2 ^= 0xff; \
  46         SIPROUND; \
  47         SIPROUND; \
  48         SIPROUND; \
  49         SIPROUND; \
  50         return (v0 ^ v1) ^ (v2 ^ v3);
  51
  52 #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
  53 u64 __siphash_aligned(const void *data, size_t len, const siphash_key_t *key)
  54 {
  55         const u8 *end = data + len - (len % sizeof(u64));
  56         const u8 left = len & (sizeof(u64) - 1);
  57         u64 m;
  58         PREAMBLE(len)
  59         for (; data != end; data += sizeof(u64)) {
  60                 m = le64_to_cpup(data);
  61                 v3 ^= m;
  62                 SIPROUND;
  63                 SIPROUND;
  64                 v0 ^= m;
  65         }
  66 #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
  67         if (left)
  68                 b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) &
  69                                                   bytemask_from_count(left)));
  70 #else
  71         switch (left) {
  72         case 7: b |= ((u64)end[6]) << 48; fallthrough;
  73         case 6: b |= ((u64)end[5]) << 40; fallthrough;
  74         case 5: b |= ((u64)end[4]) << 32; fallthrough;
  75         case 4: b |= le32_to_cpup(data); break;
  76         case 3: b |= ((u64)end[2]) << 16; fallthrough;
  77         case 2: b |= le16_to_cpup(data); break;
  78         case 1: b |= end[0];
  79         }
  80 #endif
  81         POSTAMBLE
  82 }
  83 EXPORT_SYMBOL(__siphash_aligned);
  84 #endif
  85
  86 u64 __siphash_unaligned(const void *data, size_t len, const siphash_key_t *key)
  87 {
  88         const u8 *end = data + len - (len % sizeof(u64));
  89         const u8 left = len & (sizeof(u64) - 1);
  90         u64 m;
  91         PREAMBLE(len)
  92         for (; data != end; data += sizeof(u64)) {
  93                 m = get_unaligned_le64(data);
  94                 v3 ^= m;
  95                 SIPROUND;
  96                 SIPROUND;
  97                 v0 ^= m;
  98         }
  99 #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
 100         if (left)
 101                 b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) &
 102                                                   bytemask_from_count(left)));
 103 #else
 104         switch (left) {
 105         case 7: b |= ((u64)end[6]) << 48; fallthrough;
 106         case 6: b |= ((u64)end[5]) << 40; fallthrough;
 107         case 5: b |= ((u64)end[4]) << 32; fallthrough;
 108         case 4: b |= get_unaligned_le32(end); break;
 109         case 3: b |= ((u64)end[2]) << 16; fallthrough;
 110         case 2: b |= get_unaligned_le16(end); break;
 111         case 1: b |= end[0];
 112         }
 113 #endif
 114         POSTAMBLE
 115 }
 116 EXPORT_SYMBOL(__siphash_unaligned);
 117
 118 /**
 119  * siphash_1u64 - compute 64-bit siphash PRF value of a u64
 120  * @first: first u64
 121  * @key: the siphash key
 122  */
 123 u64 siphash_1u64(const u64 first, const siphash_key_t *key)
 124 {
 125         PREAMBLE(8)
 126         v3 ^= first;
 127         SIPROUND;
 128         SIPROUND;
 129         v0 ^= first;
 130         POSTAMBLE
 131 }
 132 EXPORT_SYMBOL(siphash_1u64);
 133
 134 /**
 135  * siphash_2u64 - compute 64-bit siphash PRF value of 2 u64
 136  * @first: first u64
 137  * @second: second u64
 138  * @key: the siphash key
 139  */
 140 u64 siphash_2u64(const u64 first, const u64 second, const siphash_key_t *key)
 141 {
 142         PREAMBLE(16)
 143         v3 ^= first;
 144         SIPROUND;
 145         SIPROUND;
 146         v0 ^= first;
 147         v3 ^= second;
 148         SIPROUND;
 149         SIPROUND;
 150         v0 ^= second;
 151         POSTAMBLE
 152 }
 153 EXPORT_SYMBOL(siphash_2u64);
 154
 155 /**
 156  * siphash_3u64 - compute 64-bit siphash PRF value of 3 u64
 157  * @first: first u64
 158  * @second: second u64
 159  * @third: third u64
 160  * @key: the siphash key
 161  */
 162 u64 siphash_3u64(const u64 first, const u64 second, const u64 third,
 163                  const siphash_key_t *key)
 164 {
 165         PREAMBLE(24)
 166         v3 ^= first;
 167         SIPROUND;
 168         SIPROUND;
 169         v0 ^= first;
 170         v3 ^= second;
 171         SIPROUND;
 172         SIPROUND;
 173         v0 ^= second;
 174         v3 ^= third;
 175         SIPROUND;
 176         SIPROUND;
 177         v0 ^= third;
 178         POSTAMBLE
 179 }
 180 EXPORT_SYMBOL(siphash_3u64);
 181
 182 /**
 183  * siphash_4u64 - compute 64-bit siphash PRF value of 4 u64
 184  * @first: first u64
 185  * @second: second u64
 186  * @third: third u64
 187  * @forth: forth u64
 188  * @key: the siphash key
 189  */
 190 u64 siphash_4u64(const u64 first, const u64 second, const u64 third,
 191                  const u64 forth, const siphash_key_t *key)
 192 {
 193         PREAMBLE(32)
 194         v3 ^= first;
 195         SIPROUND;
 196         SIPROUND;
 197         v0 ^= first;
 198         v3 ^= second;
 199         SIPROUND;
 200         SIPROUND;
 201         v0 ^= second;
 202         v3 ^= third;
 203         SIPROUND;
 204         SIPROUND;
 205         v0 ^= third;
 206         v3 ^= forth;
 207         SIPROUND;
 208         SIPROUND;
 209         v0 ^= forth;
 210         POSTAMBLE
 211 }
 212 EXPORT_SYMBOL(siphash_4u64);
 213
 214 u64 siphash_1u32(const u32 first, const siphash_key_t *key)
 215 {
 216         PREAMBLE(4)
 217         b |= first;
 218         POSTAMBLE
 219 }
 220 EXPORT_SYMBOL(siphash_1u32);
 221
 222 u64 siphash_3u32(const u32 first, const u32 second, const u32 third,
 223                  const siphash_key_t *key)
 224 {
 225         u64 combined = (u64)second << 32 | first;
 226         PREAMBLE(12)
 227         v3 ^= combined;
 228         SIPROUND;
 229         SIPROUND;
 230         v0 ^= combined;
 231         b |= third;
 232         POSTAMBLE
 233 }
 234 EXPORT_SYMBOL(siphash_3u32);
 235
 236 #if BITS_PER_LONG == 64
 237 /* Note that on 64-bit, we make HalfSipHash1-3 actually be SipHash1-3, for
 238  * performance reasons. On 32-bit, below, we actually implement HalfSipHash1-3.
 239  */
 240
 241 #define HSIPROUND SIPROUND
 242 #define HPREAMBLE(len) PREAMBLE(len)
 243 #define HPOSTAMBLE \
 244         v3 ^= b; \
 245         HSIPROUND; \
 246         v0 ^= b; \
 247         v2 ^= 0xff; \
 248         HSIPROUND; \
 249         HSIPROUND; \
 250         HSIPROUND; \
 251         return (v0 ^ v1) ^ (v2 ^ v3);
 252
 253 #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
 254 u32 __hsiphash_aligned(const void *data, size_t len, const hsiphash_key_t *key)
 255 {
 256         const u8 *end = data + len - (len % sizeof(u64));
 257         const u8 left = len & (sizeof(u64) - 1);
 258         u64 m;
 259         HPREAMBLE(len)
 260         for (; data != end; data += sizeof(u64)) {
 261                 m = le64_to_cpup(data);
 262                 v3 ^= m;
 263                 HSIPROUND;
 264                 v0 ^= m;
 265         }
 266 #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
 267         if (left)
 268                 b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) &
 269                                                   bytemask_from_count(left)));
 270 #else
 271         switch (left) {
 272         case 7: b |= ((u64)end[6]) << 48; fallthrough;
 273         case 6: b |= ((u64)end[5]) << 40; fallthrough;
 274         case 5: b |= ((u64)end[4]) << 32; fallthrough;
 275         case 4: b |= le32_to_cpup(data); break;
 276         case 3: b |= ((u64)end[2]) << 16; fallthrough;
 277         case 2: b |= le16_to_cpup(data); break;
 278         case 1: b |= end[0];
 279         }
 280 #endif
 281         HPOSTAMBLE
 282 }
 283 EXPORT_SYMBOL(__hsiphash_aligned);
 284 #endif
 285
 286 u32 __hsiphash_unaligned(const void *data, size_t len,
 287                          const hsiphash_key_t *key)
 288 {
 289         const u8 *end = data + len - (len % sizeof(u64));
 290         const u8 left = len & (sizeof(u64) - 1);
 291         u64 m;
 292         HPREAMBLE(len)
 293         for (; data != end; data += sizeof(u64)) {
 294                 m = get_unaligned_le64(data);
 295                 v3 ^= m;
 296                 HSIPROUND;
 297                 v0 ^= m;
 298         }
 299 #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
 300         if (left)
 301                 b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) &
 302                                                   bytemask_from_count(left)));
 303 #else
 304         switch (left) {
 305         case 7: b |= ((u64)end[6]) << 48; fallthrough;
 306         case 6: b |= ((u64)end[5]) << 40; fallthrough;
 307         case 5: b |= ((u64)end[4]) << 32; fallthrough;
 308         case 4: b |= get_unaligned_le32(end); break;
 309         case 3: b |= ((u64)end[2]) << 16; fallthrough;
 310         case 2: b |= get_unaligned_le16(end); break;
 311         case 1: b |= end[0];
 312         }
 313 #endif
 314         HPOSTAMBLE
 315 }
 316 EXPORT_SYMBOL(__hsiphash_unaligned);
 317
 318 /**
 319  * hsiphash_1u32 - compute 64-bit hsiphash PRF value of a u32
 320  * @first: first u32
 321  * @key: the hsiphash key
 322  */
 323 u32 hsiphash_1u32(const u32 first, const hsiphash_key_t *key)
 324 {
 325         HPREAMBLE(4)
 326         b |= first;
 327         HPOSTAMBLE
 328 }
 329 EXPORT_SYMBOL(hsiphash_1u32);
 330
 331 /**
 332  * hsiphash_2u32 - compute 32-bit hsiphash PRF value of 2 u32
 333  * @first: first u32
 334  * @second: second u32
 335  * @key: the hsiphash key
 336  */
 337 u32 hsiphash_2u32(const u32 first, const u32 second, const hsiphash_key_t *key)
 338 {
 339         u64 combined = (u64)second << 32 | first;
 340         HPREAMBLE(8)
 341         v3 ^= combined;
 342         HSIPROUND;
 343         v0 ^= combined;
 344         HPOSTAMBLE
 345 }
 346 EXPORT_SYMBOL(hsiphash_2u32);
 347
 348 /**
 349  * hsiphash_3u32 - compute 32-bit hsiphash PRF value of 3 u32
 350  * @first: first u32
 351  * @second: second u32
 352  * @third: third u32
 353  * @key: the hsiphash key
 354  */
 355 u32 hsiphash_3u32(const u32 first, const u32 second, const u32 third,
 356                   const hsiphash_key_t *key)
 357 {
 358         u64 combined = (u64)second << 32 | first;
 359         HPREAMBLE(12)
 360         v3 ^= combined;
 361         HSIPROUND;
 362         v0 ^= combined;
 363         b |= third;
 364         HPOSTAMBLE
 365 }
 366 EXPORT_SYMBOL(hsiphash_3u32);
 367
 368 /**
 369  * hsiphash_4u32 - compute 32-bit hsiphash PRF value of 4 u32
 370  * @first: first u32
 371  * @second: second u32
 372  * @third: third u32
 373  * @forth: forth u32
 374  * @key: the hsiphash key
 375  */
 376 u32 hsiphash_4u32(const u32 first, const u32 second, const u32 third,
 377                   const u32 forth, const hsiphash_key_t *key)
 378 {
 379         u64 combined = (u64)second << 32 | first;
 380         HPREAMBLE(16)
 381         v3 ^= combined;
 382         HSIPROUND;
 383         v0 ^= combined;
 384         combined = (u64)forth << 32 | third;
 385         v3 ^= combined;
 386         HSIPROUND;
 387         v0 ^= combined;
 388         HPOSTAMBLE
 389 }
 390 EXPORT_SYMBOL(hsiphash_4u32);
 391 #else
 392 #define HSIPROUND \
 393         do { \
 394         v0 += v1; v1 = rol32(v1, 5); v1 ^= v0; v0 = rol32(v0, 16); \
 395         v2 += v3; v3 = rol32(v3, 8); v3 ^= v2; \
 396         v0 += v3; v3 = rol32(v3, 7); v3 ^= v0; \
 397         v2 += v1; v1 = rol32(v1, 13); v1 ^= v2; v2 = rol32(v2, 16); \
 398         } while (0)
 399
 400 #define HPREAMBLE(len) \
 401         u32 v0 = 0; \
 402         u32 v1 = 0; \
 403         u32 v2 = 0x6c796765U; \
 404         u32 v3 = 0x74656462U; \
 405         u32 b = ((u32)(len)) << 24; \
 406         v3 ^= key->key[1]; \
 407         v2 ^= key->key[0]; \
 408         v1 ^= key->key[1]; \
 409         v0 ^= key->key[0];
 410
 411 #define HPOSTAMBLE \
 412         v3 ^= b; \
 413         HSIPROUND; \
 414         v0 ^= b; \
 415         v2 ^= 0xff; \
 416         HSIPROUND; \
 417         HSIPROUND; \
 418         HSIPROUND; \
 419         return v1 ^ v3;
 420
 421 #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
 422 u32 __hsiphash_aligned(const void *data, size_t len, const hsiphash_key_t *key)
 423 {
 424         const u8 *end = data + len - (len % sizeof(u32));
 425         const u8 left = len & (sizeof(u32) - 1);
 426         u32 m;
 427         HPREAMBLE(len)
 428         for (; data != end; data += sizeof(u32)) {
 429                 m = le32_to_cpup(data);
 430                 v3 ^= m;
 431                 HSIPROUND;
 432                 v0 ^= m;
 433         }
 434         switch (left) {
 435         case 3: b |= ((u32)end[2]) << 16; fallthrough;
 436         case 2: b |= le16_to_cpup(data); break;
 437         case 1: b |= end[0];
 438         }
 439         HPOSTAMBLE
 440 }
 441 EXPORT_SYMBOL(__hsiphash_aligned);
 442 #endif
 443
 444 u32 __hsiphash_unaligned(const void *data, size_t len,
 445                          const hsiphash_key_t *key)
 446 {
 447         const u8 *end = data + len - (len % sizeof(u32));
 448         const u8 left = len & (sizeof(u32) - 1);
 449         u32 m;
 450         HPREAMBLE(len)
 451         for (; data != end; data += sizeof(u32)) {
 452                 m = get_unaligned_le32(data);
 453                 v3 ^= m;
 454                 HSIPROUND;
 455                 v0 ^= m;
 456         }
 457         switch (left) {
 458         case 3: b |= ((u32)end[2]) << 16; fallthrough;
 459         case 2: b |= get_unaligned_le16(end); break;
 460         case 1: b |= end[0];
 461         }
 462         HPOSTAMBLE
 463 }
 464 EXPORT_SYMBOL(__hsiphash_unaligned);
 465
 466 /**
 467  * hsiphash_1u32 - compute 32-bit hsiphash PRF value of a u32
 468  * @first: first u32
 469  * @key: the hsiphash key
 470  */
 471 u32 hsiphash_1u32(const u32 first, const hsiphash_key_t *key)
 472 {
 473         HPREAMBLE(4)
 474         v3 ^= first;
 475         HSIPROUND;
 476         v0 ^= first;
 477         HPOSTAMBLE
 478 }
 479 EXPORT_SYMBOL(hsiphash_1u32);
 480
 481 /**
 482  * hsiphash_2u32 - compute 32-bit hsiphash PRF value of 2 u32
 483  * @first: first u32
 484  * @second: second u32
 485  * @key: the hsiphash key
 486  */
 487 u32 hsiphash_2u32(const u32 first, const u32 second, const hsiphash_key_t *key)
 488 {
 489         HPREAMBLE(8)
 490         v3 ^= first;
 491         HSIPROUND;
 492         v0 ^= first;
 493         v3 ^= second;
 494         HSIPROUND;
 495         v0 ^= second;
 496         HPOSTAMBLE
 497 }
 498 EXPORT_SYMBOL(hsiphash_2u32);
 499
 500 /**
 501  * hsiphash_3u32 - compute 32-bit hsiphash PRF value of 3 u32
 502  * @first: first u32
 503  * @second: second u32
 504  * @third: third u32
 505  * @key: the hsiphash key
 506  */
 507 u32 hsiphash_3u32(const u32 first, const u32 second, const u32 third,
 508                   const hsiphash_key_t *key)
 509 {
 510         HPREAMBLE(12)
 511         v3 ^= first;
 512         HSIPROUND;
 513         v0 ^= first;
 514         v3 ^= second;
 515         HSIPROUND;
 516         v0 ^= second;
 517         v3 ^= third;
 518         HSIPROUND;
 519         v0 ^= third;
 520         HPOSTAMBLE
 521 }
 522 EXPORT_SYMBOL(hsiphash_3u32);
 523
 524 /**
 525  * hsiphash_4u32 - compute 32-bit hsiphash PRF value of 4 u32
 526  * @first: first u32
 527  * @second: second u32
 528  * @third: third u32
 529  * @forth: forth u32
 530  * @key: the hsiphash key
 531  */
 532 u32 hsiphash_4u32(const u32 first, const u32 second, const u32 third,
 533                   const u32 forth, const hsiphash_key_t *key)
 534 {
 535         HPREAMBLE(16)
 536         v3 ^= first;
 537         HSIPROUND;
 538         v0 ^= first;
 539         v3 ^= second;
 540         HSIPROUND;
 541         v0 ^= second;
 542         v3 ^= third;
 543         HSIPROUND;
 544         v0 ^= third;
 545         v3 ^= forth;
 546         HSIPROUND;
 547         v0 ^= forth;
 548         HPOSTAMBLE
 549 }
 550 EXPORT_SYMBOL(hsiphash_4u32);
 551 #endif