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  }