1 | // Copyright 2016 Google Inc. All Rights Reserved. |
2 | // |
3 | // Licensed under the Apache License, Version 2.0 (the "License"); |
4 | // you may not use this file except in compliance with the License. |
5 | // You may obtain a copy of the License at |
6 | // |
7 | // http://www.apache.org/licenses/LICENSE-2.0 |
8 | // |
9 | // Unless required by applicable law or agreed to in writing, software |
10 | // distributed under the License is distributed on an "AS IS" BASIS, |
11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
12 | // See the License for the specific language governing permissions and |
13 | // limitations under the License. |
14 | |
15 | #ifndef HIGHWAYHASH_SIP_HASH_H_ |
16 | #define HIGHWAYHASH_SIP_HASH_H_ |
17 | |
18 | // Portable but fast SipHash implementation. |
19 | |
20 | #include <cstddef> |
21 | #include <cstring> // memcpy |
22 | |
23 | #include "highwayhash/arch_specific.h" |
24 | #include "highwayhash/compiler_specific.h" |
25 | #include "highwayhash/endianess.h" |
26 | #include "highwayhash/state_helpers.h" |
27 | |
28 | namespace highwayhash { |
29 | |
30 | // Paper: https://www.131002.net/siphash/siphash.pdf |
31 | template <int kUpdateIters, int kFinalizeIters> |
32 | class SipHashStateT { |
33 | public: |
34 | using Key = HH_U64[2]; |
35 | static const size_t kPacketSize = sizeof(HH_U64); |
36 | |
37 | explicit HH_INLINE SipHashStateT(const Key& key) { |
38 | v0 = 0x736f6d6570736575ull ^ key[0]; |
39 | v1 = 0x646f72616e646f6dull ^ key[1]; |
40 | v2 = 0x6c7967656e657261ull ^ key[0]; |
41 | v3 = 0x7465646279746573ull ^ key[1]; |
42 | } |
43 | |
44 | HH_INLINE void Update(const char* bytes) { |
45 | HH_U64 packet; |
46 | memcpy(&packet, bytes, sizeof(packet)); |
47 | packet = host_from_le64(packet); |
48 | |
49 | v3 ^= packet; |
50 | |
51 | Compress<kUpdateIters>(); |
52 | |
53 | v0 ^= packet; |
54 | } |
55 | |
56 | HH_INLINE HH_U64 Finalize() { |
57 | // Mix in bits to avoid leaking the key if all packets were zero. |
58 | v2 ^= 0xFF; |
59 | |
60 | Compress<kFinalizeIters>(); |
61 | |
62 | return (v0 ^ v1) ^ (v2 ^ v3); |
63 | } |
64 | private: |
65 | // Rotate a 64-bit value "v" left by N bits. |
66 | template <HH_U64 bits> |
67 | static HH_INLINE HH_U64 RotateLeft(const HH_U64 v) { |
68 | const HH_U64 left = v << bits; |
69 | const HH_U64 right = v >> (64 - bits); |
70 | return left | right; |
71 | } |
72 | |
73 | template <size_t rounds> |
74 | HH_INLINE void Compress() { |
75 | for (size_t i = 0; i < rounds; ++i) { |
76 | // ARX network: add, rotate, exclusive-or. |
77 | v0 += v1; |
78 | v2 += v3; |
79 | v1 = RotateLeft<13>(v1); |
80 | v3 = RotateLeft<16>(v3); |
81 | v1 ^= v0; |
82 | v3 ^= v2; |
83 | |
84 | v0 = RotateLeft<32>(v0); |
85 | |
86 | v2 += v1; |
87 | v0 += v3; |
88 | v1 = RotateLeft<17>(v1); |
89 | v3 = RotateLeft<21>(v3); |
90 | v1 ^= v2; |
91 | v3 ^= v0; |
92 | |
93 | v2 = RotateLeft<32>(v2); |
94 | } |
95 | } |
96 | |
97 | HH_U64 v0; |
98 | HH_U64 v1; |
99 | HH_U64 v2; |
100 | HH_U64 v3; |
101 | }; |
102 | |
103 | using SipHashState = SipHashStateT<2, 4>; |
104 | using SipHash13State = SipHashStateT<1, 3>; |
105 | |
106 | // Override the HighwayTreeHash padding scheme with that of SipHash so that |
107 | // the hash output matches the known-good values in sip_hash_test. |
108 | template <> |
109 | HH_INLINE void PaddedUpdate<SipHashState>(const HH_U64 size, |
110 | const char* remaining_bytes, |
111 | const HH_U64 remaining_size, |
112 | SipHashState* state) { |
113 | // Copy to avoid overrunning the input buffer. |
114 | char final_packet[SipHashState::kPacketSize] = {0}; |
115 | memcpy(final_packet, remaining_bytes, remaining_size); |
116 | final_packet[SipHashState::kPacketSize - 1] = static_cast<char>(size & 0xFF); |
117 | state->Update(final_packet); |
118 | } |
119 | |
120 | template <> |
121 | HH_INLINE void PaddedUpdate<SipHash13State>(const HH_U64 size, |
122 | const char* remaining_bytes, |
123 | const HH_U64 remaining_size, |
124 | SipHash13State* state) { |
125 | // Copy to avoid overrunning the input buffer. |
126 | char final_packet[SipHash13State::kPacketSize] = {0}; |
127 | memcpy(final_packet, remaining_bytes, remaining_size); |
128 | final_packet[SipHash13State::kPacketSize - 1] = |
129 | static_cast<char>(size & 0xFF); |
130 | state->Update(final_packet); |
131 | } |
132 | |
133 | // Fast, cryptographically strong pseudo-random function, e.g. for |
134 | // deterministic/idempotent 'random' number generation. See also |
135 | // README.md for information on resisting hash flooding attacks. |
136 | // |
137 | // Robust versus timing attacks because memory accesses are sequential |
138 | // and the algorithm is branch-free. Compute time is proportional to the |
139 | // number of 8-byte packets and about twice as fast as an sse41 implementation. |
140 | // |
141 | // "key" is a secret 128-bit key unknown to attackers. |
142 | // "bytes" is the data to hash; ceil(size / 8) * 8 bytes are read. |
143 | // Returns a 64-bit hash of the given data bytes, which are swapped on |
144 | // big-endian CPUs so the return value is the same as on little-endian CPUs. |
145 | static HH_INLINE HH_U64 SipHash(const SipHashState::Key& key, const char* bytes, |
146 | const HH_U64 size) { |
147 | return ComputeHash<SipHashState>(key, bytes, size); |
148 | } |
149 | |
150 | // Round-reduced SipHash version (1 update and 3 finalization rounds). |
151 | static HH_INLINE HH_U64 SipHash13(const SipHash13State::Key& key, |
152 | const char* bytes, const HH_U64 size) { |
153 | return ComputeHash<SipHash13State>(key, bytes, size); |
154 | } |
155 | |
156 | template <int kNumLanes, int kUpdateIters, int kFinalizeIters> |
157 | static HH_INLINE HH_U64 ReduceSipTreeHash( |
158 | const typename SipHashStateT<kUpdateIters, kFinalizeIters>::Key& key, |
159 | const uint64_t (&hashes)[kNumLanes]) { |
160 | SipHashStateT<kUpdateIters, kFinalizeIters> state(key); |
161 | |
162 | for (int i = 0; i < kNumLanes; ++i) { |
163 | state.Update(reinterpret_cast<const char*>(&hashes[i])); |
164 | } |
165 | |
166 | return state.Finalize(); |
167 | } |
168 | |
169 | } // namespace highwayhash |
170 | |
171 | #endif // HIGHWAYHASH_SIP_HASH_H_ |
172 | |