From 16329224e70d0525208f6b0ba00c5e1531a4f5ea Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Wed, 15 Feb 2017 17:45:22 -0800 Subject: Switch FastRandomContext to ChaCha20 --- src/Makefile.test.include | 2 +- src/addrman.cpp | 8 +++--- src/addrman.h | 11 ++++++-- src/random.cpp | 33 ++++++++++++---------- src/random.h | 66 ++++++++++++++++++++++++++++++++++++++------ src/test/addrman_tests.cpp | 9 +++--- src/test/prevector_tests.cpp | 8 +++--- src/test/random_tests.cpp | 21 +++++++++++++- src/test/test_bitcoin.cpp | 3 +- src/test/test_random.h | 8 +++++- 10 files changed, 126 insertions(+), 43 deletions(-) (limited to 'src') diff --git a/src/Makefile.test.include b/src/Makefile.test.include index fe0ed59fe2..194fc0c249 100644 --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -57,8 +57,8 @@ BITCOIN_TESTS =\ test/policyestimator_tests.cpp \ test/pow_tests.cpp \ test/prevector_tests.cpp \ - test/random_tests.cpp \ test/raii_event_tests.cpp \ + test/random_tests.cpp \ test/reverselock_tests.cpp \ test/rpc_tests.cpp \ test/sanity_tests.cpp \ diff --git a/src/addrman.cpp b/src/addrman.cpp index b6ab4c6305..33a623c1f2 100644 --- a/src/addrman.cpp +++ b/src/addrman.cpp @@ -351,8 +351,8 @@ CAddrInfo CAddrMan::Select_(bool newOnly) int nKBucket = RandomInt(ADDRMAN_TRIED_BUCKET_COUNT); int nKBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE); while (vvTried[nKBucket][nKBucketPos] == -1) { - nKBucket = (nKBucket + insecure_rand.rand32()) % ADDRMAN_TRIED_BUCKET_COUNT; - nKBucketPos = (nKBucketPos + insecure_rand.rand32()) % ADDRMAN_BUCKET_SIZE; + nKBucket = (nKBucket + insecure_rand.randbits(ADDRMAN_TRIED_BUCKET_COUNT_LOG2)) % ADDRMAN_TRIED_BUCKET_COUNT; + nKBucketPos = (nKBucketPos + insecure_rand.randbits(ADDRMAN_BUCKET_SIZE_LOG2)) % ADDRMAN_BUCKET_SIZE; } int nId = vvTried[nKBucket][nKBucketPos]; assert(mapInfo.count(nId) == 1); @@ -368,8 +368,8 @@ CAddrInfo CAddrMan::Select_(bool newOnly) int nUBucket = RandomInt(ADDRMAN_NEW_BUCKET_COUNT); int nUBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE); while (vvNew[nUBucket][nUBucketPos] == -1) { - nUBucket = (nUBucket + insecure_rand.rand32()) % ADDRMAN_NEW_BUCKET_COUNT; - nUBucketPos = (nUBucketPos + insecure_rand.rand32()) % ADDRMAN_BUCKET_SIZE; + nUBucket = (nUBucket + insecure_rand.randbits(ADDRMAN_NEW_BUCKET_COUNT_LOG2)) % ADDRMAN_NEW_BUCKET_COUNT; + nUBucketPos = (nUBucketPos + insecure_rand.randbits(ADDRMAN_BUCKET_SIZE_LOG2)) % ADDRMAN_BUCKET_SIZE; } int nId = vvNew[nUBucket][nUBucketPos]; assert(mapInfo.count(nId) == 1); diff --git a/src/addrman.h b/src/addrman.h index 6e5f946bf2..bb45ac91ea 100644 --- a/src/addrman.h +++ b/src/addrman.h @@ -136,13 +136,13 @@ public: */ //! total number of buckets for tried addresses -#define ADDRMAN_TRIED_BUCKET_COUNT 256 +#define ADDRMAN_TRIED_BUCKET_COUNT_LOG2 8 //! total number of buckets for new addresses -#define ADDRMAN_NEW_BUCKET_COUNT 1024 +#define ADDRMAN_NEW_BUCKET_COUNT_LOG2 10 //! maximum allowed number of entries in buckets for new and tried addresses -#define ADDRMAN_BUCKET_SIZE 64 +#define ADDRMAN_BUCKET_SIZE_LOG2 6 //! over how many buckets entries with tried addresses from a single group (/16 for IPv4) are spread #define ADDRMAN_TRIED_BUCKETS_PER_GROUP 8 @@ -171,6 +171,11 @@ public: //! the maximum number of nodes to return in a getaddr call #define ADDRMAN_GETADDR_MAX 2500 +//! Convenience +#define ADDRMAN_TRIED_BUCKET_COUNT (1 << ADDRMAN_TRIED_BUCKET_COUNT_LOG2) +#define ADDRMAN_NEW_BUCKET_COUNT (1 << ADDRMAN_NEW_BUCKET_COUNT_LOG2) +#define ADDRMAN_BUCKET_SIZE (1 << ADDRMAN_BUCKET_SIZE_LOG2) + /** * Stochastical (IP) address manager */ diff --git a/src/random.cpp b/src/random.cpp index 8284f457c9..c1e313cbde 100644 --- a/src/random.cpp +++ b/src/random.cpp @@ -240,22 +240,16 @@ uint256 GetRandHash() return hash; } -FastRandomContext::FastRandomContext(bool fDeterministic) +void FastRandomContext::RandomSeed() { - // The seed values have some unlikely fixed points which we avoid. - if (fDeterministic) { - Rz = Rw = 11; - } else { - uint32_t tmp; - do { - GetRandBytes((unsigned char*)&tmp, 4); - } while (tmp == 0 || tmp == 0x9068ffffU); - Rz = tmp; - do { - GetRandBytes((unsigned char*)&tmp, 4); - } while (tmp == 0 || tmp == 0x464fffffU); - Rw = tmp; - } + uint256 seed = GetRandHash(); + rng.SetKey(seed.begin(), 32); + requires_seed = false; +} + +FastRandomContext::FastRandomContext(const uint256& seed) : requires_seed(false), bytebuf_size(0), bitbuf_size(0) +{ + rng.SetKey(seed.begin(), 32); } bool Random_SanityCheck() @@ -288,3 +282,12 @@ bool Random_SanityCheck() } while (num_overwritten < NUM_OS_RANDOM_BYTES && tries < MAX_TRIES); return (num_overwritten == NUM_OS_RANDOM_BYTES); /* If this failed, bailed out after too many tries */ } + +FastRandomContext::FastRandomContext(bool fDeterministic) : requires_seed(!fDeterministic), bytebuf_size(0), bitbuf_size(0) +{ + if (!fDeterministic) { + return; + } + uint256 seed; + rng.SetKey(seed.begin(), 32); +} diff --git a/src/random.h b/src/random.h index 82886bec59..077f58c4d9 100644 --- a/src/random.h +++ b/src/random.h @@ -6,6 +6,7 @@ #ifndef BITCOIN_RANDOM_H #define BITCOIN_RANDOM_H +#include "crypto/chacha20.h" #include "uint256.h" #include @@ -33,21 +34,68 @@ void GetStrongRandBytes(unsigned char* buf, int num); * This class is not thread-safe. */ class FastRandomContext { +private: + bool requires_seed; + ChaCha20 rng; + + unsigned char bytebuf[64]; + int bytebuf_size; + + uint64_t bitbuf; + int bitbuf_size; + + void RandomSeed(); + + void FillByteBuffer() + { + if (requires_seed) { + RandomSeed(); + } + rng.Output(bytebuf, sizeof(bytebuf)); + bytebuf_size = sizeof(bytebuf); + } + + void FillBitBuffer() + { + bitbuf = rand64(); + bitbuf_size = 64; + } + public: - explicit FastRandomContext(bool fDeterministic=false); + explicit FastRandomContext(bool fDeterministic = false); - uint32_t rand32() { - Rz = 36969 * (Rz & 65535) + (Rz >> 16); - Rw = 18000 * (Rw & 65535) + (Rw >> 16); - return (Rw << 16) + Rz; + /** Initialize with explicit seed (only for testing) */ + explicit FastRandomContext(const uint256& seed); + + /** Generate a random 64-bit integer. */ + uint64_t rand64() + { + if (bytebuf_size < 8) FillByteBuffer(); + uint64_t ret = ReadLE64(bytebuf + 64 - bytebuf_size); + bytebuf_size -= 8; + return ret; } - bool randbool() { - return rand32() & 1; + /** Generate a random (bits)-bit integer. */ + uint64_t randbits(int bits) { + if (bits == 0) { + return 0; + } else if (bits > 32) { + return rand64() >> (64 - bits); + } else { + if (bitbuf_size < bits) FillBitBuffer(); + uint64_t ret = bitbuf & (~(uint64_t)0 >> (64 - bits)); + bitbuf >>= bits; + bitbuf_size -= bits; + return ret; + } } - uint32_t Rz; - uint32_t Rw; + /** Generate a random 32-bit integer. */ + uint32_t rand32() { return randbits(32); } + + /** Generate a random boolean. */ + bool randbool() { return randbits(1); } }; /* Number of random bytes returned by GetOSRand. diff --git a/src/test/addrman_tests.cpp b/src/test/addrman_tests.cpp index 5d1c5b78d1..39fa381dd0 100644 --- a/src/test/addrman_tests.cpp +++ b/src/test/addrman_tests.cpp @@ -203,10 +203,11 @@ BOOST_AUTO_TEST_CASE(addrman_select) BOOST_CHECK(addrman.size() == 7); // Test 12: Select pulls from new and tried regardless of port number. - BOOST_CHECK(addrman.Select().ToString() == "250.4.6.6:8333"); - BOOST_CHECK(addrman.Select().ToString() == "250.3.2.2:9999"); - BOOST_CHECK(addrman.Select().ToString() == "250.3.3.3:9999"); - BOOST_CHECK(addrman.Select().ToString() == "250.4.4.4:8333"); + std::set ports; + for (int i = 0; i < 20; ++i) { + ports.insert(addrman.Select().GetPort()); + } + BOOST_CHECK_EQUAL(ports.size(), 3); } BOOST_AUTO_TEST_CASE(addrman_new_collisions) diff --git a/src/test/prevector_tests.cpp b/src/test/prevector_tests.cpp index bd8a7819a4..cfed5e347e 100644 --- a/src/test/prevector_tests.cpp +++ b/src/test/prevector_tests.cpp @@ -28,6 +28,7 @@ class prevector_tester { typedef typename pretype::size_type Size; bool passed = true; FastRandomContext rand_cache; + uint256 rand_seed; template @@ -183,13 +184,12 @@ public: } ~prevector_tester() { - BOOST_CHECK_MESSAGE(passed, "insecure_rand_Rz: " - << rand_cache.Rz - << ", insecure_rand_Rw: " - << rand_cache.Rw); + BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString()); } + prevector_tester() { seed_insecure_rand(); + rand_seed = insecure_rand_seed; rand_cache = insecure_rand_ctx; } }; diff --git a/src/test/random_tests.cpp b/src/test/random_tests.cpp index d2c46c0daa..31b993cd38 100644 --- a/src/test/random_tests.cpp +++ b/src/test/random_tests.cpp @@ -15,5 +15,24 @@ BOOST_AUTO_TEST_CASE(osrandom_tests) BOOST_CHECK(Random_SanityCheck()); } -BOOST_AUTO_TEST_SUITE_END() +BOOST_AUTO_TEST_CASE(fastrandom_tests) +{ + // Check that deterministic FastRandomContexts are deterministic + FastRandomContext ctx1(true); + FastRandomContext ctx2(true); + + BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32()); + BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32()); + BOOST_CHECK_EQUAL(ctx1.rand64(), ctx2.rand64()); + BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3)); + BOOST_CHECK_EQUAL(ctx1.randbits(7), ctx2.randbits(7)); + BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32()); + BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3)); + // Check that a nondeterministic ones are not + FastRandomContext ctx3; + FastRandomContext ctx4; + BOOST_CHECK(ctx3.rand64() != ctx4.rand64()); // extremely unlikely to be equal +} + +BOOST_AUTO_TEST_SUITE_END() diff --git a/src/test/test_bitcoin.cpp b/src/test/test_bitcoin.cpp index abaec45cd7..48593f62d5 100644 --- a/src/test/test_bitcoin.cpp +++ b/src/test/test_bitcoin.cpp @@ -27,7 +27,8 @@ #include #include -FastRandomContext insecure_rand_ctx(true); +uint256 insecure_rand_seed = GetRandHash(); +FastRandomContext insecure_rand_ctx(insecure_rand_seed); extern bool fPrintToConsole; extern void noui_connect(); diff --git a/src/test/test_random.h b/src/test/test_random.h index 4a1637ac72..318c44df4d 100644 --- a/src/test/test_random.h +++ b/src/test/test_random.h @@ -8,11 +8,17 @@ #include "random.h" +extern uint256 insecure_rand_seed; extern FastRandomContext insecure_rand_ctx; static inline void seed_insecure_rand(bool fDeterministic = false) { - insecure_rand_ctx = FastRandomContext(fDeterministic); + if (fDeterministic) { + insecure_rand_seed = uint256(); + } else { + insecure_rand_seed = GetRandHash(); + } + insecure_rand_ctx = FastRandomContext(insecure_rand_seed); } static inline uint32_t insecure_rand(void) -- cgit v1.2.3