diff options
| -rw-r--r-- | src/test/util_tests.cpp | 62 | ||||
| -rw-r--r-- | src/util.cpp | 26 | ||||
| -rw-r--r-- | src/util.h | 26 | ||||
| -rw-r--r-- | src/wallet.cpp | 10 |
4 files changed, 111 insertions, 13 deletions
diff --git a/src/test/util_tests.cpp b/src/test/util_tests.cpp index f56969cba6..1b0ccad511 100644 --- a/src/test/util_tests.cpp +++ b/src/test/util_tests.cpp @@ -261,4 +261,66 @@ BOOST_AUTO_TEST_CASE(util_IsHex) BOOST_CHECK(!IsHex("0x0000")); } +BOOST_AUTO_TEST_CASE(util_seed_insecure_rand) +{ + // Expected results for the determinstic seed. + const uint32_t exp_vals[11] = { 91632771U,1889679809U,3842137544U,3256031132U, + 1761911779U, 489223532U,2692793790U,2737472863U, + 2796262275U,1309899767U,840571781U}; + // Expected 0s in rand()%(idx+2) for the determinstic seed. + const int exp_count[9] = {5013,3346,2415,1972,1644,1386,1176,1096,1009}; + int i; + int count=0; + + seed_insecure_rand(); + + //Does the non-determistic rand give us results that look too like the determinstic one? + for (i=0;i<10;i++) + { + int match = 0; + uint32_t rval = insecure_rand(); + for (int j=0;j<11;j++)match |= rval==exp_vals[j]; + count += match; + } + // sum(binomial(10,i)*(11/(2^32))^i*(1-(11/(2^32)))^(10-i),i,0,4) ~= 1-1/2^134.73 + // So _very_ unlikely to throw a false failure here. + BOOST_CHECK(count<=4); + + for (int mod=2;mod<11;mod++) + { + int mask = 1; + // Really rough binomal confidence approximation. + int err = 30*10000./mod*sqrt((1./mod*(1-1./mod))/10000.); + //mask is 2^ceil(log2(mod))-1 + while(mask<mod-1)mask=(mask<<1)+1; + + count = 0; + //How often does it get a zero from the uniform range [0,mod)? + for (i=0;i<10000;i++) + { + uint32_t rval; + do{ + rval=insecure_rand()&mask; + }while(rval>=(uint32_t)mod); + count += rval==0; + } + BOOST_CHECK(count<=10000/mod+err); + BOOST_CHECK(count>=10000/mod-err); + } + + seed_insecure_rand(true); + + for (i=0;i<11;i++) + { + BOOST_CHECK_EQUAL(insecure_rand(),exp_vals[i]); + } + + for (int mod=2;mod<11;mod++) + { + count = 0; + for (i=0;i<10000;i++) count += insecure_rand()%mod==0; + BOOST_CHECK_EQUAL(count,exp_count[mod-2]); + } +} + BOOST_AUTO_TEST_SUITE_END() diff --git a/src/util.cpp b/src/util.cpp index 1f66aff609..4eff6ce71b 100644 --- a/src/util.cpp +++ b/src/util.cpp @@ -1281,12 +1281,26 @@ void AddTimeData(const CNetAddr& ip, int64 nTime) } } - - - - - - +uint32_t insecure_rand_Rz = 11; +uint32_t insecure_rand_Rw = 11; +void seed_insecure_rand(bool fDeterministic) +{ + //The seed values have some unlikely fixed points which we avoid. + if(fDeterministic) + { + insecure_rand_Rz = insecure_rand_Rw = 11; + } else { + uint32_t tmp; + do{ + RAND_bytes((unsigned char*)&tmp,4); + }while(tmp==0 || tmp==0x9068ffffU); + insecure_rand_Rz=tmp; + do{ + RAND_bytes((unsigned char*)&tmp,4); + }while(tmp==0 || tmp==0x464fffffU); + insecure_rand_Rw=tmp; + } +} string FormatVersion(int nVersion) { diff --git a/src/util.h b/src/util.h index 2050604e54..a6b88206e9 100644 --- a/src/util.h +++ b/src/util.h @@ -404,13 +404,27 @@ bool SoftSetArg(const std::string& strArg, const std::string& strValue); */ bool SoftSetBoolArg(const std::string& strArg, bool fValue); +/** + * MWC RNG of George Marsaglia + * This is intended to be fast. It has a period of 2^59.3, though the + * least significant 16 bits only have a period of about 2^30.1. + * + * @return random value + */ +extern uint32_t insecure_rand_Rz; +extern uint32_t insecure_rand_Rw; +static inline uint32_t insecure_rand(void) +{ + insecure_rand_Rz=36969*(insecure_rand_Rz&65535)+(insecure_rand_Rz>>16); + insecure_rand_Rw=18000*(insecure_rand_Rw&65535)+(insecure_rand_Rw>>16); + return (insecure_rand_Rw<<16)+insecure_rand_Rz; +} - - - - - - +/** + * Seed insecure_rand using the random pool. + * @param Deterministic Use a determinstic seed + */ +void seed_insecure_rand(bool fDeterministic=false); /** Median filter over a stream of values. * Returns the median of the last N numbers diff --git a/src/wallet.cpp b/src/wallet.cpp index 3892e4b801..eecb7d2d22 100644 --- a/src/wallet.cpp +++ b/src/wallet.cpp @@ -984,6 +984,8 @@ static void ApproximateBestSubset(vector<pair<int64, pair<const CWalletTx*,unsig vfBest.assign(vValue.size(), true); nBest = nTotalLower; + seed_insecure_rand(); + for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++) { vfIncluded.assign(vValue.size(), false); @@ -993,7 +995,13 @@ static void ApproximateBestSubset(vector<pair<int64, pair<const CWalletTx*,unsig { for (unsigned int i = 0; i < vValue.size(); i++) { - if (nPass == 0 ? rand() % 2 : !vfIncluded[i]) + //The solver here uses a randomized algorithm, + //the randomness serves no real security purpose but is just + //needed to prevent degenerate behavior and it is important + //that the rng fast. We do not use a constant random sequence, + //because there may be some privacy improvement by making + //the selection random. + if (nPass == 0 ? insecure_rand()&1 : !vfIncluded[i]) { nTotal += vValue[i].first; vfIncluded[i] = true; |