Branch data Line data Source code
1 : : // Copyright (c) 2020-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 : : #include <crypto/muhash.h>
6 : :
7 : : #include <arith_uint256.h>
8 : : #include <span.h>
9 : : #include <test/fuzz/FuzzedDataProvider.h>
10 : : #include <test/fuzz/fuzz.h>
11 : : #include <test/fuzz/util.h>
12 : : #include <uint256.h>
13 : : #include <util/check.h>
14 : :
15 : : #include <algorithm>
16 : : #include <array>
17 : : #include <vector>
18 : :
19 : : namespace {
20 : :
21 : : /** Class to represent 6144-bit numbers using arith_uint256 code.
22 : : *
23 : : * 6144 is sufficient to represent the product of two 3072-bit numbers. */
24 : : class arith_uint6144 : public base_uint<6144> {
25 : : public:
26 : : arith_uint6144(uint64_t x) : base_uint{x} {}
27 : :
28 : : /** Construct an arith_uint6144 from any multiple of 4 bytes in LE notation,
29 : : * up to 768 bytes. */
30 : 836 : arith_uint6144(std::span<const uint8_t> bytes) : base_uint{}
31 : : {
32 [ - + ]: 836 : assert(bytes.size() % 4 == 0);
33 [ + - ]: 836 : assert(bytes.size() <= 768);
34 [ + + ]: 103940 : for (unsigned i = 0; i * 4 < bytes.size(); ++i) {
35 : 103104 : pn[i] = ReadLE32(bytes.data() + 4 * i);
36 : : }
37 : 836 : }
38 : :
39 : : /** Serialize an arithm_uint6144 to any multiply of 4 bytes in LE notation,
40 : : * on the condition that the represented number fits. */
41 : 131 : void Serialize(std::span<uint8_t> bytes) {
42 [ - + ]: 131 : assert(bytes.size() % 4 == 0);
43 [ + - ]: 131 : assert(bytes.size() <= 768);
44 [ + + ]: 12707 : for (unsigned i = 0; i * 4 < bytes.size(); ++i) {
45 : 12576 : WriteLE32(bytes.data() + 4 * i, pn[i]);
46 : : }
47 [ + + ]: 12707 : for (unsigned i = bytes.size() / 4; i * 4 < 768; ++i) {
48 [ - + ]: 12576 : assert(pn[i] == 0);
49 : : }
50 : 131 : };
51 : : };
52 : :
53 : : /** The MuHash3072 modulus (2**3072 - 1103717) as 768 LE8 bytes. */
54 : : constexpr std::array<const uint8_t, 768> MODULUS_BYTES = {
55 : : 155, 40, 239, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
56 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
57 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
58 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
59 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
60 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
61 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
62 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
63 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
64 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
65 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
66 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
67 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
68 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
69 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
70 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
71 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
72 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
73 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
74 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
75 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
76 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
77 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
78 : : 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
79 : : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
80 : : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
81 : : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
82 : : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
83 : : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
84 : : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
85 : : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
86 : : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
87 : : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
88 : : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
89 : : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
90 : : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
91 : : };
92 : :
93 : : const arith_uint6144 ZERO{0};
94 : : const arith_uint6144 ONE{1};
95 : : const arith_uint6144 MODULUS{MODULUS_BYTES};
96 : :
97 : : /** Update value to be the modulus of the input modulo MODULUS. */
98 : 298 : void Reduce(arith_uint6144& value)
99 : : {
100 : 298 : arith_uint6144 tmp = value;
101 : 298 : tmp /= MODULUS;
102 : 298 : tmp *= MODULUS;
103 : 298 : value -= tmp;
104 : 298 : }
105 : :
106 : : } // namespace
107 : :
108 [ + - ]: 607 : FUZZ_TARGET(num3072_mul)
109 : : {
110 : : // Test multiplication
111 : 131 : FuzzedDataProvider provider{buffer.data(), buffer.size()};
112 : :
113 : : // Read two 3072-bit numbers from fuzz input, and construct arith_uint6144
114 : : // and Num3072 objects with the read values.
115 : 131 : uint16_t data_a_len = provider.ConsumeIntegralInRange(0, 384);
116 : 131 : uint8_t data_a[384] = {0};
117 : 131 : provider.ConsumeData(data_a, data_a_len);
118 : 131 : arith_uint6144 a_uint{data_a};
119 : 131 : Num3072 a_num{data_a};
120 : :
121 : 131 : uint8_t data_b[384] = {0};
122 : 131 : provider.ConsumeData(data_b, 384);
123 : 131 : arith_uint6144 b_uint{data_b};
124 : 131 : Num3072 b_num{data_b};
125 : :
126 : : // Multiply the first number with the second, in both representations.
127 : 131 : a_num.Multiply(b_num);
128 : 131 : a_uint *= b_uint;
129 : 131 : Reduce(a_uint);
130 : :
131 : : // Serialize both to bytes and compare.
132 : 131 : uint8_t buf_num[384], buf_uint[384];
133 : 131 : a_num.ToBytes(buf_num);
134 : 131 : a_uint.Serialize(buf_uint);
135 [ - + ]: 131 : assert(std::ranges::equal(buf_num, buf_uint));
136 : 131 : }
137 : :
138 [ + - ]: 645 : FUZZ_TARGET(num3072_inv)
139 : : {
140 : : // Test inversion
141 : :
142 : 169 : FuzzedDataProvider provider{buffer.data(), buffer.size()};
143 : :
144 : : // Read a 3072-bit number from fuzz input, and construct arith_uint6144
145 : : // and Num3072 objects with the read values.
146 : 169 : uint8_t data[384] = {0};
147 : 169 : provider.ConsumeData(data, 384);
148 : 169 : Num3072 num{data};
149 : 169 : arith_uint6144 uint{data};
150 : :
151 : : // Bail out if the number has no inverse.
152 [ + + + + ]: 169 : if ((uint == ZERO) || (uint == MODULUS)) return;
153 : :
154 : : // Compute the inverse of the Num3072 object.
155 : 167 : Num3072 inv;
156 : 167 : inv.SetToOne();
157 : 167 : inv.Divide(num);
158 : :
159 : : // Convert the computed inverse to arith_uint6144.
160 : 167 : uint8_t buf[384];
161 : 167 : inv.ToBytes(buf);
162 : 167 : arith_uint6144 uint_inv{buf};
163 : :
164 : : // Multiply the original and the inverse, and expect 1.
165 : 167 : uint *= uint_inv;
166 : 167 : Reduce(uint);
167 [ - + ]: 167 : assert(uint == ONE);
168 : : }
169 : :
170 [ + - ]: 1216 : FUZZ_TARGET(muhash)
171 : : {
172 : 740 : FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
173 : 740 : std::vector<uint8_t> data{ConsumeRandomLengthByteVector(fuzzed_data_provider)};
174 : 740 : std::vector<uint8_t> data2{ConsumeRandomLengthByteVector(fuzzed_data_provider)};
175 : :
176 : 740 : MuHash3072 muhash;
177 : :
178 [ - + ]: 740 : muhash.Insert(data);
179 [ - + ]: 740 : muhash.Insert(data2);
180 : :
181 : 740 : constexpr uint256 initial_state_hash{"dd5ad2a105c2d29495f577245c357409002329b9f4d6182c0af3dc2f462555c8"};
182 : 740 : uint256 out;
183 : 740 : uint256 out2;
184 : 740 : CallOneOf(
185 : : fuzzed_data_provider,
186 : 131 : [&] {
187 : : // Test that MuHash result is consistent independent of order of operations
188 : 131 : muhash.Finalize(out);
189 : :
190 : 131 : muhash = MuHash3072();
191 [ - + ]: 131 : muhash.Insert(data2);
192 [ - + ]: 131 : muhash.Insert(data);
193 : 131 : muhash.Finalize(out2);
194 : 131 : },
195 : 50 : [&] {
196 : : // Test that multiplication with the initial state never changes the finalized result
197 : 50 : muhash.Finalize(out);
198 : 50 : MuHash3072 muhash3;
199 : 50 : muhash3 *= muhash;
200 : 50 : muhash3.Finalize(out2);
201 : 50 : },
202 : 412 : [&] {
203 : : // Test that dividing a MuHash by itself brings it back to its initial state
204 : : // Insert only multiplies the numerator, so without the Remove the denominator
205 : : // is still 1 and the division is trivially correct
206 [ - + ]: 412 : muhash.Remove(data);
207 : 412 : muhash /= muhash;
208 : 412 : muhash.Finalize(out);
209 : 412 : out2 = initial_state_hash;
210 : 412 : },
211 : 147 : [&] {
212 : : // Test that removing all added elements brings the object back to its initial state
213 [ - + ]: 147 : muhash.Remove(data);
214 [ - + ]: 147 : muhash.Remove(data2);
215 : 147 : muhash.Finalize(out);
216 : 147 : out2 = initial_state_hash;
217 : 147 : });
218 [ + - ]: 740 : assert(out == out2);
219 : 740 : }
|