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
28namespace highwayhash {
29
30// Paper: https://www.131002.net/siphash/siphash.pdf
31template <int kUpdateIters, int kFinalizeIters>
32class 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
103using SipHashState = SipHashStateT<2, 4>;
104using 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.
108template <>
109HH_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
120template <>
121HH_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.
145static 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).
151static 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
156template <int kNumLanes, int kUpdateIters, int kFinalizeIters>
157static 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