Branch data Line data Source code
1 : : // Copyright (c) 2020-2021 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 : 490 : 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 : 709 : arith_uint6144(Span<const uint8_t> bytes) : base_uint{}
29 : : {
30 [ - + ]: 709 : assert(bytes.size() % 4 == 0);
31 [ + - ]: 709 : assert(bytes.size() <= 768);
32 [ + + ]: 89509 : for (unsigned i = 0; i * 4 < bytes.size(); ++i) {
33 : 88800 : pn[i] = ReadLE32(bytes.data() + 4 * i);
34 : : }
35 : 709 : }
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 : 113 : void Serialize(Span<uint8_t> bytes) {
40 [ - + ]: 113 : assert(bytes.size() % 4 == 0);
41 [ + - ]: 113 : assert(bytes.size() <= 768);
42 [ + + ]: 10961 : for (unsigned i = 0; i * 4 < bytes.size(); ++i) {
43 : 10848 : WriteLE32(bytes.data() + 4 * i, pn[i]);
44 : : }
45 [ + + ]: 10961 : for (unsigned i = bytes.size() / 4; i * 4 < 768; ++i) {
46 [ - + ]: 10848 : assert(pn[i] == 0);
47 : : }
48 : 113 : };
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 : 245 : void Reduce(arith_uint6144& value)
97 : : {
98 : 245 : arith_uint6144 tmp = value;
99 : 245 : tmp /= MODULUS;
100 : 245 : tmp *= MODULUS;
101 : 245 : value -= tmp;
102 : 245 : }
103 : :
104 : : } // namespace
105 : :
106 [ + - ]: 545 : FUZZ_TARGET(num3072_mul)
107 : : {
108 : : // Test multiplication
109 : 113 : 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 : 113 : uint16_t data_a_len = provider.ConsumeIntegralInRange(0, 384);
114 : 113 : uint8_t data_a[384] = {0};
115 : 113 : provider.ConsumeData(data_a, data_a_len);
116 : 113 : arith_uint6144 a_uint{data_a};
117 : 113 : Num3072 a_num{data_a};
118 : :
119 : 113 : uint8_t data_b[384] = {0};
120 : 113 : provider.ConsumeData(data_b, 384);
121 : 113 : arith_uint6144 b_uint{data_b};
122 : 113 : Num3072 b_num{data_b};
123 : :
124 : : // Multiply the first number with the second, in both representations.
125 : 113 : a_num.Multiply(b_num);
126 : 113 : a_uint *= b_uint;
127 : 113 : Reduce(a_uint);
128 : :
129 : : // Serialize both to bytes and compare.
130 : 113 : uint8_t buf_num[384], buf_uint[384];
131 : 113 : a_num.ToBytes(buf_num);
132 : 113 : a_uint.Serialize(buf_uint);
133 [ - + ]: 113 : assert(std::ranges::equal(buf_num, buf_uint));
134 : 113 : }
135 : :
136 [ + - ]: 567 : FUZZ_TARGET(num3072_inv)
137 : : {
138 : : // Test inversion
139 : :
140 : 135 : 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 : 135 : uint8_t data[384] = {0};
145 : 135 : provider.ConsumeData(data, 384);
146 : 135 : Num3072 num{data};
147 : 135 : arith_uint6144 uint{data};
148 : :
149 : : // Bail out if the number has no inverse.
150 [ + + + + ]: 135 : if ((uint == ZERO) || (uint == MODULUS)) return;
151 : :
152 : : // Compute the inverse of the Num3072 object.
153 : 132 : Num3072 inv;
154 : 132 : inv.SetToOne();
155 : 132 : inv.Divide(num);
156 : :
157 : : // Convert the computed inverse to arith_uint6144.
158 : 132 : uint8_t buf[384];
159 : 132 : inv.ToBytes(buf);
160 : 132 : arith_uint6144 uint_inv{buf};
161 : :
162 : : // Multiply the original and the inverse, and expect 1.
163 : 132 : uint *= uint_inv;
164 : 132 : Reduce(uint);
165 [ - + ]: 132 : assert(uint == ONE);
166 : : }
167 : :
168 [ + - ]: 1504 : FUZZ_TARGET(muhash)
169 : : {
170 : 1072 : FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
171 : 1072 : std::vector<uint8_t> data{ConsumeRandomLengthByteVector(fuzzed_data_provider)};
172 : 1072 : std::vector<uint8_t> data2{ConsumeRandomLengthByteVector(fuzzed_data_provider)};
173 : :
174 : 1072 : MuHash3072 muhash;
175 : :
176 : 1072 : muhash.Insert(data);
177 : 1072 : muhash.Insert(data2);
178 : :
179 : 1072 : constexpr uint256 initial_state_hash{"dd5ad2a105c2d29495f577245c357409002329b9f4d6182c0af3dc2f462555c8"};
180 : 1072 : uint256 out;
181 : 1072 : uint256 out2;
182 : 1072 : CallOneOf(
183 : : fuzzed_data_provider,
184 : 179 : [&] {
185 : : // Test that MuHash result is consistent independent of order of operations
186 : 179 : muhash.Finalize(out);
187 : :
188 : 179 : muhash = MuHash3072();
189 : 179 : muhash.Insert(data2);
190 : 179 : muhash.Insert(data);
191 : 179 : muhash.Finalize(out2);
192 : 179 : },
193 : 78 : [&] {
194 : : // Test that multiplication with the initial state never changes the finalized result
195 : 78 : muhash.Finalize(out);
196 : 78 : MuHash3072 muhash3;
197 : 78 : muhash3 *= muhash;
198 : 78 : muhash3.Finalize(out2);
199 : 78 : },
200 : 596 : [&] {
201 : : // Test that dividing a MuHash by itself brings it back to it's initial state
202 : :
203 : : // See note about clang + self-assignment in test/uint256_tests.cpp
204 : : #if defined(__clang__)
205 : : # pragma clang diagnostic push
206 : : # pragma clang diagnostic ignored "-Wself-assign-overloaded"
207 : : #endif
208 : :
209 : 596 : muhash /= muhash;
210 : :
211 : : #if defined(__clang__)
212 : : # pragma clang diagnostic pop
213 : : #endif
214 : :
215 : 596 : muhash.Finalize(out);
216 : 596 : out2 = initial_state_hash;
217 : 596 : },
218 : 219 : [&] {
219 : : // Test that removing all added elements brings the object back to it's initial state
220 : 219 : muhash.Remove(data);
221 : 219 : muhash.Remove(data2);
222 : 219 : muhash.Finalize(out);
223 : 219 : out2 = initial_state_hash;
224 : 219 : });
225 [ - + ]: 1072 : assert(out == out2);
226 : 1072 : }
|
