Branch data Line data Source code
1 : : // Copyright (c) 2016-present The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #ifndef BITCOIN_CRYPTO_SIPHASH_H
6 : : #define BITCOIN_CRYPTO_SIPHASH_H
7 : :
8 : : #include <attributes.h>
9 : : #include <uint256.h>
10 : :
11 : : #include <bit>
12 : : #include <cstdint>
13 : : #include <span>
14 : :
15 : : /** Shared SipHash state (v0..v3) with its round, compression, and finalization primitives.
16 : : * Internal building block, only meant to be composed by the hasher classes below. */
17 : : class SipHashState
18 : : {
19 : : /** SipHash initialization constants. */
20 : : static constexpr uint64_t C0{0x736f6d6570736575}, C1{0x646f72616e646f6d}, C2{0x6c7967656e657261}, C3{0x7465646279746573};
21 : : /** SipHash v2 finalizer constant. */
22 : : static constexpr uint64_t FINALIZER{0xFF};
23 : : /** SipHash custom unpadded finalizer constant. */
24 : : static constexpr uint64_t FINALIZER_UNPADDED{0x6465646461706e75};
25 : : static_assert(FINALIZER_UNPADDED != FINALIZER);
26 : :
27 : : /** Construct a SipHashState with the specified values as state. */
28 : 100703207 : ALWAYS_INLINE SipHashState(uint64_t v0, uint64_t v1, uint64_t v2, uint64_t v3) noexcept : m_v0{v0}, m_v1{v1}, m_v2{v2}, m_v3{v3} {}
29 : :
30 : : /** State variables. */
31 : : uint64_t m_v0, m_v1, m_v2, m_v3;
32 : :
33 : : /** Mutably perform one SipRound on this state. */
34 : 111439815 : ALWAYS_INLINE void SipRound() noexcept
35 : : {
36 : 111439815 : m_v0 += m_v1; m_v1 = std::rotl(m_v1, 13); m_v1 ^= m_v0;
37 : 111439815 : m_v0 = std::rotl(m_v0, 32);
38 : 111439815 : m_v2 += m_v3; m_v3 = std::rotl(m_v3, 16); m_v3 ^= m_v2;
39 : 111439815 : m_v0 += m_v3; m_v3 = std::rotl(m_v3, 21); m_v3 ^= m_v0;
40 : 111439815 : m_v2 += m_v1; m_v1 = std::rotl(m_v1, 17); m_v1 ^= m_v2;
41 : 111439815 : m_v2 = std::rotl(m_v2, 32);
42 : : }
43 : :
44 : : public:
45 : : /** Construct a SipHashState initialized with the specified key. */
46 : 4380171 : explicit ALWAYS_INLINE SipHashState(uint64_t k0, uint64_t k1) noexcept : SipHashState{C0 ^ k0, C1 ^ k1, C2 ^ k0, C3 ^ k1} {}
47 : : /** Construct a copy of this state. */
48 : 91327025 : ALWAYS_INLINE SipHashState Copy() const noexcept { return {m_v0, m_v1, m_v2, m_v3}; }
49 : : /** Mutably compress one block into this state, with 1 SipRound. */
50 : 87170228 : ALWAYS_INLINE SipHashState& Compress1(uint64_t data) noexcept
51 : : {
52 : 87170228 : m_v3 ^= data;
53 : 87170228 : SipRound();
54 : 87170228 : m_v0 ^= data;
55 : 87170228 : return *this;
56 : : }
57 : : /** Mutably compress one jumbo block into this state, with 1 SipRound. */
58 : 87179787 : ALWAYS_INLINE SipHashState& Compress1Jumbo(const uint256& data) noexcept
59 : : {
60 : 87179787 : const uint64_t d0{data.GetUint64(0)}, d1{data.GetUint64(1)}, d2{data.GetUint64(2)}, d3{data.GetUint64(3)};
61 : 87179787 : m_v3 ^= d0; m_v0 ^= d1; m_v1 ^= d2; m_v2 ^= d3;
62 [ + - + - ]: 87179787 : SipRound();
63 : 87179787 : m_v0 ^= d0; m_v1 ^= d1; m_v2 ^= d2; m_v3 ^= d3;
64 : 87179787 : return *this;
65 : : }
66 : : /** Mutably compress one block into this state, with 2 SipRounds. */
67 : 24259685 : ALWAYS_INLINE SipHashState& Compress2(uint64_t data) noexcept
68 : : {
69 : 24259685 : m_v3 ^= data;
70 : 15437408 : SipRound();
71 : 24259685 : SipRound();
72 : 24259685 : m_v0 ^= data;
73 : 15437408 : return *this;
74 : : }
75 : : /** Mutably finalize this state with 4 SipRounds, and return the resulting hash. */
76 : 4157381 : ALWAYS_INLINE uint64_t Finalize4() noexcept
77 : : {
78 : 4995755 : m_v2 ^= FINALIZER;
79 : 4995755 : SipRound();
80 : 4995755 : SipRound();
81 : 4995755 : SipRound();
82 : 4995755 : SipRound();
83 : 4995755 : return m_v0 ^ m_v1 ^ m_v2 ^ m_v3;
84 : : }
85 : : /** Mutably finalize this state with 3 SipRounds using the unpadded finalizer, and return the
86 : : * resulting hash. */
87 : 87179838 : ALWAYS_INLINE uint64_t Finalize3U() noexcept
88 : : {
89 : 87179838 : m_v2 ^= FINALIZER_UNPADDED;
90 : 87179838 : SipRound();
91 : 87179838 : SipRound();
92 : 87179838 : SipRound();
93 : 87179838 : return m_v0 ^ m_v1 ^ m_v2 ^ m_v3;
94 : : }
95 : : };
96 : :
97 : : /** General SipHash-2-4 implementation. */
98 : : class CSipHasher
99 : : {
100 : : SipHashState m_state;
101 : : uint64_t m_tmp{0};
102 : : uint8_t m_count{0}; //!< Only the low 8 bits of the input size matter.
103 : :
104 : : public:
105 : : /** Construct a SipHash calculator initialized with 128-bit key (k0, k1). */
106 : : CSipHasher(uint64_t k0, uint64_t k1);
107 : : /** Hash a 64-bit integer worth of data.
108 : : * It is treated as if this was the little-endian interpretation of 8 bytes.
109 : : * This function can only be used when a multiple of 8 bytes have been written so far.
110 : : */
111 : : CSipHasher& Write(uint64_t data);
112 : : /** Hash arbitrary bytes. */
113 : : CSipHasher& Write(std::span<const unsigned char> data);
114 : : /** Compute the 64-bit SipHash-2-4 of the data written so far. The object remains untouched. */
115 : : uint64_t Finalize() const;
116 : : };
117 : :
118 : : /** A custom weaker variant of SipHash-1-3 without padding, and supporting "jumbo" inputs.
119 : : *
120 : : * Compared to the traditional SipHash-2-4, this incorporates 3 changes:
121 : : *
122 : : * - Use SipHash-1-3: This common variant reduces the number of rounds between input blocks from 2
123 : : * to 1, and the number of finalization rounds at the end from 4 to 3.
124 : : * It is a standard faster choice with weaker security guarantees. It is
125 : : * considered strong enough for use in hash tables and other applications with
126 : : * only weak security requirements, in particular when attackers cannot directly
127 : : * observe the hash function output, and cannot control k0 and k1.
128 : : *
129 : : * - Remove padding: Standard SipHash operates on byte-oriented inputs, which are converted into
130 : : * 8-byte blocks internally by adding a padding of 1-8 bytes to obtain a multiple
131 : : * of 8 bytes. In this variant, the input is a sequence of blocks instead, which
132 : : * are used without padding. This saves 1 round for inputs that are a multiple of
133 : : * 8 bytes already. The padding normally adds a commitment to the input's byte
134 : : * length, but since our input is block oriented, and there is one round per
135 : : * input, the function of that commitment is directly fulfilled by the number of
136 : : * rounds. The empty input is permitted; it yields the result of finalizing the
137 : : * initialization directly. Out of an abundance of caution the finalizing
138 : : * v2 ^= 0xff is changed to v2 ^= 0x6465646461706e75 ("unpadded" in LE64), to
139 : : * avoid collisions between standard SipHash-1-3 and this variant.
140 : : *
141 : : * - Jumbo blocks: We generalize the input to consist of a sequence of blocks which are each either
142 : : * exactly 8 bytes (normal blocks) or 32 bytes (jumbo blocks), and may be
143 : : * arbitrarily mixed. For hash-table use, cryptographic hash outputs must make up
144 : : * all but a small bounded number of retained jumbo blocks. Note that the block
145 : : * structure matters: hashing one jumbo block is not the same as hashing the same
146 : : * data split up into four normal blocks. Jumbo blocks are interpreted as 4 LE64 integers
147 : : * (d0,d1,d2,d3), and XOR'ed into the state before a round as
148 : : * (v0,v1,v2,v3) ^= (d1,d2,d3,d0), and XOR'ed into the state after a round as
149 : : * (v0,v1,v2,v3) ^= (d0,d1,d2,d3). This is a strict generalization of normal block
150 : : * processing, in the sense that if d1..d3=0, it is identical to processing a normal
151 : : * block d0 (a single LE64 integer). Of course, making d1..d3=0 should be impossible
152 : : * in the output of a cryptographic hash function. These jumbo blocks are acceptable
153 : : * because even though they may give the attacker more control within a single
154 : : * round, that control is limited by the cryptographic hash in between.
155 : : *
156 : : * Other components are unchanged: initialization constants, SipRound, and 64-bit output.
157 : : * This interface serves as an executable specification for fixed-width implementations.
158 : : * The Hash overloads optimize fixed-width inputs without modifying the accumulated state.
159 : : */
160 : : class SipHasher13UJ
161 : : {
162 : : SipHashState m_state;
163 : :
164 : : public:
165 : : /** Construct a SipHash-1-3-UJ calculator initialized with 128-bit key (k0, k1). */
166 [ + + ]: 169084 : SipHasher13UJ(uint64_t k0, uint64_t k1) noexcept : m_state{k0, k1} {}
167 : : /** Hash a normal 64-bit value. */
168 : : SipHasher13UJ& Write(uint64_t data) noexcept;
169 : : /** Hash a 256-bit value as a jumbo block. For hash-table use, non-hash inputs must remain few and bounded. */
170 : : SipHasher13UJ& WriteJumbo(const uint256& hash) noexcept;
171 : : /** Compute the 64-bit SipHash-1-3-UJ of the data written so far. The object remains untouched. */
172 : : uint64_t Finalize() const noexcept;
173 : :
174 : : /** Hash a jumbo block after the data written so far and finalize without modifying the object. */
175 : 9441 : ALWAYS_INLINE uint64_t Hash(const uint256& hash) const noexcept
176 : : {
177 [ + - ]: 9441 : return m_state.Copy()
178 : 9441 : .Compress1Jumbo(hash)
179 [ + - ]: 9441 : .Finalize3U();
180 : : }
181 : :
182 : : /**
183 : : * Hash a jumbo block followed by a normal block after the data written so far,
184 : : * and finalize without modifying the object.
185 : : */
186 : 87170141 : ALWAYS_INLINE uint64_t Hash(const uint256& hash, uint64_t extra) const noexcept
187 : : {
188 [ + - ]: 87170141 : return m_state.Copy()
189 : 87170141 : .Compress1Jumbo(hash)
190 : 87170141 : .Compress1(extra)
191 [ + - ]: 87170141 : .Finalize3U();
192 : : }
193 : : };
194 : :
195 : : /**
196 : : * Optimized SipHash-2-4 implementation for uint256.
197 : : *
198 : : * This class caches the initial SipHash state (v0..v3) derived from (k0, k1)
199 : : * and implements a specialized hashing path for uint256 values, with or
200 : : * without an extra 32-bit word. The internal state is immutable, so
201 : : * PresaltedSipHasher instances can be reused for multiple hashes with the
202 : : * same key.
203 : : */
204 : : class PresaltedSipHasher
205 : : {
206 : : const SipHashState m_state;
207 : :
208 : : public:
209 [ + - + - : 63815 : explicit PresaltedSipHasher(uint64_t k0, uint64_t k1) noexcept : m_state{k0, k1} {}
+ - ]
210 : :
211 : : /** Equivalent to CSipHasher(k0, k1).Write(val).Finalize(). */
212 : : uint64_t operator()(const uint256& val) const noexcept;
213 : :
214 : : /**
215 : : * Equivalent to CSipHasher(k0, k1).Write(val).Write(extra).Finalize(),
216 : : * with `extra` encoded as 4 little-endian bytes.
217 : : */
218 : : uint64_t operator()(const uint256& val, uint32_t extra) const noexcept;
219 : : };
220 : :
221 : : #endif // BITCOIN_CRYPTO_SIPHASH_H
|
