siphash.mx raw
1 // Package siphash implements SipHash-2-4, a fast short-input PRF designed
2 // by Jean-Philippe Aumasson and Daniel J. Bernstein.
3 //
4 // Reference: https://131002.net/siphash/siphash.pdf
5 //
6 // Sum64 produces a 64-bit MAC. Sum128 produces a 128-bit MAC suitable for
7 // use as a collision-resistant hash key where truncation would reduce safety
8 // margins. For hash table use where DoS resistance is not required, a fixed
9 // or zero key is acceptable.
10 package siphash
11
12 import "math/bits"
13
14 // Key is a 128-bit SipHash key.
15 type Key [2]uint64
16
17 // DefaultKey returns a non-secret fixed key for deterministic hash-table use.
18 // It uses the SipHash initialization constants so it is well-tested.
19 func DefaultKey() Key { return Key{0x736f6d6570736575, 0x646f72616e646f6d} }
20
21 // Sum64 computes SipHash-2-4 with 64-bit output.
22 func Sum64(key Key, p []byte) uint64 {
23 v0 := key[0] ^ 0x736f6d6570736575
24 v1 := key[1] ^ 0x646f72616e646f6d
25 v2 := key[0] ^ 0x6c7967656e657261
26 v3 := key[1] ^ 0x7465646279746573
27
28 length := len(p)
29 blocks := length / 8
30 for i := 0; i < blocks; i++ {
31 m := leUint64(p[i*8:])
32 v3 ^= m
33 v0, v1, v2, v3 = sipRound(v0, v1, v2, v3)
34 v0, v1, v2, v3 = sipRound(v0, v1, v2, v3)
35 v0 ^= m
36 }
37
38 // Last block: remaining bytes + length in top byte.
39 last := uint64(length) << 56
40 tail := p[blocks*8:]
41 for i := len(tail) - 1; i >= 0; i-- {
42 last |= uint64(tail[i]) << (uint(i) * 8)
43 }
44 v3 ^= last
45 v0, v1, v2, v3 = sipRound(v0, v1, v2, v3)
46 v0, v1, v2, v3 = sipRound(v0, v1, v2, v3)
47 v0 ^= last
48
49 v2 ^= 0xff
50 for i := 0; i < 4; i++ {
51 v0, v1, v2, v3 = sipRound(v0, v1, v2, v3)
52 }
53 return v0 ^ v1 ^ v2 ^ v3
54 }
55
56 // Sum128 computes SipHash-2-4 with 128-bit output.
57 // The 128-bit variant is identical to Sum64 except:
58 // - v1 is XORed with 0xee at initialization
59 // - Finalization runs twice: once for the low 64 bits, then with
60 // v1 XORed by 0xdd for the high 64 bits
61 func Sum128(key Key, p []byte) [2]uint64 {
62 v0 := key[0] ^ 0x736f6d6570736575
63 v1 := key[1] ^ 0x646f72616e646f6d
64 v2 := key[0] ^ 0x6c7967656e657261
65 v3 := key[1] ^ 0x7465646279746573
66
67 // 128-bit output mode marker.
68 v1 ^= 0xee
69
70 length := len(p)
71 blocks := length / 8
72 for i := 0; i < blocks; i++ {
73 m := leUint64(p[i*8:])
74 v3 ^= m
75 v0, v1, v2, v3 = sipRound(v0, v1, v2, v3)
76 v0, v1, v2, v3 = sipRound(v0, v1, v2, v3)
77 v0 ^= m
78 }
79
80 // Last block.
81 last := uint64(length) << 56
82 tail := p[blocks*8:]
83 for i := len(tail) - 1; i >= 0; i-- {
84 last |= uint64(tail[i]) << (uint(i) * 8)
85 }
86 v3 ^= last
87 v0, v1, v2, v3 = sipRound(v0, v1, v2, v3)
88 v0, v1, v2, v3 = sipRound(v0, v1, v2, v3)
89 v0 ^= last
90
91 // First finalization: low 64 bits.
92 v2 ^= 0xee
93 for i := 0; i < 4; i++ {
94 v0, v1, v2, v3 = sipRound(v0, v1, v2, v3)
95 }
96 lo := v0 ^ v1 ^ v2 ^ v3
97
98 // Second finalization: high 64 bits.
99 v1 ^= 0xdd
100 for i := 0; i < 4; i++ {
101 v0, v1, v2, v3 = sipRound(v0, v1, v2, v3)
102 }
103 hi := v0 ^ v1 ^ v2 ^ v3
104
105 return [2]uint64{lo, hi}
106 }
107
108 func sipRound(v0, v1, v2, v3 uint64) (uint64, uint64, uint64, uint64) {
109 v0 += v1
110 v1 = bits.RotateLeft64(v1, 13)
111 v1 ^= v0
112 v0 = bits.RotateLeft64(v0, 32)
113 v2 += v3
114 v3 = bits.RotateLeft64(v3, 16)
115 v3 ^= v2
116 v0 += v3
117 v3 = bits.RotateLeft64(v3, 21)
118 v3 ^= v0
119 v2 += v1
120 v1 = bits.RotateLeft64(v1, 17)
121 v1 ^= v2
122 v2 = bits.RotateLeft64(v2, 32)
123 return v0, v1, v2, v3
124 }
125
126 // leUint64 reads a little-endian uint64 from b (must be at least 8 bytes).
127 func leUint64(b []byte) uint64 {
128 return uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | uint64(b[3])<<24 |
129 uint64(b[4])<<32 | uint64(b[5])<<40 | uint64(b[6])<<48 | uint64(b[7])<<56
130 }
131