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