Merge bitcoin/bitcoin#36286: crypto: Fix MuHash3072 division by itself
What the developer wrote
Authored by merge-script
Merge bitcoin/bitcoin#36286: crypto: Fix MuHash3072 division by itself
b388f9bd0d2bcc259d488638d479ba09a30ba040 crypto: Fix MuHash3072 division by itself (Fabian Jahr)
Pull request description:
`MuHash3072::operator/=` multiplies the numerator by the divisor's denominator and then the denominator by the divisor's numerator. But as it is currently implemented the divisor could be the MuHash object itself. When that is the case, the second step reads the numerator that the first step already updated, so `x /= x` actually leaves `1/D` instead of the empty set. This only goes unnoticed when the denominator is 1, which is the case in our existing fuzz target and benchmark. No code in the node/index divides MuHash objects by themselves, so runnings nodes are not affected.
Fixes the code by not using the potentially changed nominator, adds a test that reproduces the issue and updates the fuzz test to not always use denominator 1.
ACKs for top commit:
furszy:
utACK b388f9bd0d2bcc259d488638d479ba09a30ba040
sedited:
ACK b388f9bd0d2bcc259d488638d479ba09a30ba040
sipa:
utACK b388f9bd0d2bcc259d488638d479ba09a30ba040
Tree-SHA512: ae2eb845db07fb140e7946dfc7d084766e5f6d06060b91da6acc3434fdf6b59ad1eb050b4be79bc4644dea032d1ca0d01dd9e9b366bd04a545cf5224e57526df
What changed, and why it matters
This commit fixes a bug in Bitcoin Core's MuHash3072 cryptographic code where dividing a MuHash object by itself (x /= x) produced the wrong mathematical result. The fix is straightforward: the code now saves the divisor's numerator before modifying it, so the second multiplication step uses the original value rather than the already-changed one. The bug only affects self-division, and the project maintainers state that no live node or index code actually performs this operation, so running Bitcoin nodes are not affected. Tests and fuzzing targets were updated to catch this case in the future.
No urgent action for node operators; the bug is not reachable in production. Developers should ensure the patch is included in the next release and that the new regression test and fuzz target changes are present.
Security signals we found
Cryptographic correctness bug in MuHash3072 division operator
Self-aliasing in operator/= produces incorrect 1/D result instead of empty set
No production code path identified that triggers self-division
Fix includes regression test and improved fuzz coverage
Evidence from the diff
In src/crypto/muhash.cpp, MuHash3072::operator/= was aliasing-sensitive. When *this and div refer to the same object, the first line (m_numerator.Multiply(div.m_denominator)) mutates m_numerator, so the second line (m_denominator.Multiply(div.m_numerator)) reads the modified numerator instead of the original divisor numerator. The patch copies div.m_numerator into a local Num3072 before any mutation, then uses that copy for the denominator multiplication. The test in src/test/crypto_tests.cpp adds a self-division check, and the fuzz target in src/test/fuzz/muhash.cpp ensures the denominator is not always 1 so the bug would be exposed.
Changed components
src/crypto/muhash.cppsrc/test/crypto_tests.cppsrc/test/fuzz/muhash.cppInspect captured patch +11 / −1
### src/crypto/muhash.cpp
@@ -569,8 +569,9 @@ MuHash3072& MuHash3072::operator*=(const MuHash3072& mul) noexcept
MuHash3072& MuHash3072::operator/=(const MuHash3072& div) noexcept
{
+ const Num3072 div_numerator{div.m_numerator}; // div may alias *this
m_numerator.Multiply(div.m_denominator);
- m_denominator.Multiply(div.m_numerator);
+ m_denominator.Multiply(div_numerator);
return *this;
}
### src/test/crypto_tests.cpp
@@ -1240,6 +1240,12 @@ BOOST_AUTO_TEST_CASE(muhash_tests)
a.Finalize(out2);
BOOST_CHECK_EQUAL(out, out2);
+
+ // Self-division must yield the empty set
+ y /= x; // x=X, y=Y*X/X
+ y /= y; // x=X, y=1
+ y.Finalize(out);
+ BOOST_CHECK_EQUAL(out, out2);
}
MuHash3072 acc = FromInt(0);
### src/test/fuzz/muhash.cpp
@@ -199,6 +199,9 @@ FUZZ_TARGET(muhash)
},
[&] {
// Test that dividing a MuHash by itself brings it back to its initial state
+ // Insert only multiplies the numerator, so without the Remove the denominator
+ // is still 1 and the division is trivially correct
+ muhash.Remove(data);
muhash /= muhash;
muhash.Finalize(out);
out2 = initial_state_hash;Why this scored 24/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.