Skip to content

Commit 1632922

Browse files
sipasipa
committed
Switch FastRandomContext to ChaCha20
1 parent e04326f commit 1632922

File tree

10 files changed

+126
-43
lines changed

10 files changed

+126
-43
lines changed

‎src/Makefile.test.include‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -57,8 +57,8 @@ BITCOIN_TESTS =\
5757
test/policyestimator_tests.cpp \
5858
test/pow_tests.cpp \
5959
test/prevector_tests.cpp \
60-
test/random_tests.cpp \
6160
test/raii_event_tests.cpp \
61+
test/random_tests.cpp \
6262
test/reverselock_tests.cpp \
6363
test/rpc_tests.cpp \
6464
test/sanity_tests.cpp \

‎src/addrman.cpp‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -351,8 +351,8 @@ CAddrInfo CAddrMan::Select_(bool newOnly)
351351
int nKBucket = RandomInt(ADDRMAN_TRIED_BUCKET_COUNT);
352352
int nKBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE);
353353
while (vvTried[nKBucket][nKBucketPos] == -1) {
354-
nKBucket = (nKBucket + insecure_rand.rand32()) % ADDRMAN_TRIED_BUCKET_COUNT;
355-
nKBucketPos = (nKBucketPos + insecure_rand.rand32()) % ADDRMAN_BUCKET_SIZE;
354+
nKBucket = (nKBucket + insecure_rand.randbits(ADDRMAN_TRIED_BUCKET_COUNT_LOG2)) % ADDRMAN_TRIED_BUCKET_COUNT;
355+
nKBucketPos = (nKBucketPos + insecure_rand.randbits(ADDRMAN_BUCKET_SIZE_LOG2)) % ADDRMAN_BUCKET_SIZE;
356356
}
357357
int nId = vvTried[nKBucket][nKBucketPos];
358358
assert(mapInfo.count(nId) == 1);
@@ -368,8 +368,8 @@ CAddrInfo CAddrMan::Select_(bool newOnly)
368368
int nUBucket = RandomInt(ADDRMAN_NEW_BUCKET_COUNT);
369369
int nUBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE);
370370
while (vvNew[nUBucket][nUBucketPos] == -1) {
371-
nUBucket = (nUBucket + insecure_rand.rand32()) % ADDRMAN_NEW_BUCKET_COUNT;
372-
nUBucketPos = (nUBucketPos + insecure_rand.rand32()) % ADDRMAN_BUCKET_SIZE;
371+
nUBucket = (nUBucket + insecure_rand.randbits(ADDRMAN_NEW_BUCKET_COUNT_LOG2)) % ADDRMAN_NEW_BUCKET_COUNT;
372+
nUBucketPos = (nUBucketPos + insecure_rand.randbits(ADDRMAN_BUCKET_SIZE_LOG2)) % ADDRMAN_BUCKET_SIZE;
373373
}
374374
int nId = vvNew[nUBucket][nUBucketPos];
375375
assert(mapInfo.count(nId) == 1);

‎src/addrman.h‎

Lines changed: 8 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -136,13 +136,13 @@ class CAddrInfo : public CAddress
136136
*/
137137

138138
//! total number of buckets for tried addresses
139-
#define ADDRMAN_TRIED_BUCKET_COUNT 256
139+
#define ADDRMAN_TRIED_BUCKET_COUNT_LOG2 8
140140

141141
//! total number of buckets for new addresses
142-
#define ADDRMAN_NEW_BUCKET_COUNT 1024
142+
#define ADDRMAN_NEW_BUCKET_COUNT_LOG2 10
143143

144144
//! maximum allowed number of entries in buckets for new and tried addresses
145-
#define ADDRMAN_BUCKET_SIZE 64
145+
#define ADDRMAN_BUCKET_SIZE_LOG2 6
146146

147147
//! over how many buckets entries with tried addresses from a single group (/16 for IPv4) are spread
148148
#define ADDRMAN_TRIED_BUCKETS_PER_GROUP 8
@@ -171,6 +171,11 @@ class CAddrInfo : public CAddress
171171
//! the maximum number of nodes to return in a getaddr call
172172
#define ADDRMAN_GETADDR_MAX 2500
173173

174+
//! Convenience
175+
#define ADDRMAN_TRIED_BUCKET_COUNT (1 << ADDRMAN_TRIED_BUCKET_COUNT_LOG2)
176+
#define ADDRMAN_NEW_BUCKET_COUNT (1 << ADDRMAN_NEW_BUCKET_COUNT_LOG2)
177+
#define ADDRMAN_BUCKET_SIZE (1 << ADDRMAN_BUCKET_SIZE_LOG2)
178+
174179
/**
175180
* Stochastical (IP) address manager
176181
*/

‎src/random.cpp‎

Lines changed: 18 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -240,22 +240,16 @@ uint256 GetRandHash()
240240
return hash;
241241
}
242242

243-
FastRandomContext::FastRandomContext(bool fDeterministic)
243+
void FastRandomContext::RandomSeed()
244244
{
245-
// The seed values have some unlikely fixed points which we avoid.
246-
if (fDeterministic) {
247-
Rz = Rw = 11;
248-
} else {
249-
uint32_t tmp;
250-
do {
251-
GetRandBytes((unsigned char*)&tmp, 4);
252-
} while (tmp == 0 || tmp == 0x9068ffffU);
253-
Rz = tmp;
254-
do {
255-
GetRandBytes((unsigned char*)&tmp, 4);
256-
} while (tmp == 0 || tmp == 0x464fffffU);
257-
Rw = tmp;
258-
}
245+
uint256 seed = GetRandHash();
246+
rng.SetKey(seed.begin(), 32);
247+
requires_seed = false;
248+
}
249+
250+
FastRandomContext::FastRandomContext(const uint256& seed) : requires_seed(false), bytebuf_size(0), bitbuf_size(0)
251+
{
252+
rng.SetKey(seed.begin(), 32);
259253
}
260254

261255
bool Random_SanityCheck()
@@ -288,3 +282,12 @@ bool Random_SanityCheck()
288282
} while (num_overwritten < NUM_OS_RANDOM_BYTES && tries < MAX_TRIES);
289283
return (num_overwritten == NUM_OS_RANDOM_BYTES); /* If this failed, bailed out after too many tries */
290284
}
285+
286+
FastRandomContext::FastRandomContext(bool fDeterministic) : requires_seed(!fDeterministic), bytebuf_size(0), bitbuf_size(0)
287+
{
288+
if (!fDeterministic) {
289+
return;
290+
}
291+
uint256 seed;
292+
rng.SetKey(seed.begin(), 32);
293+
}

‎src/random.h‎

Lines changed: 57 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@
66
#ifndef BITCOIN_RANDOM_H
77
#define BITCOIN_RANDOM_H
88

9+
#include "crypto/chacha20.h"
910
#include "uint256.h"
1011

1112
#include <stdint.h>
@@ -33,21 +34,68 @@ void GetStrongRandBytes(unsigned char* buf, int num);
3334
* This class is not thread-safe.
3435
*/
3536
class FastRandomContext {
37+
private:
38+
bool requires_seed;
39+
ChaCha20 rng;
40+
41+
unsigned char bytebuf[64];
42+
int bytebuf_size;
43+
44+
uint64_t bitbuf;
45+
int bitbuf_size;
46+
47+
void RandomSeed();
48+
49+
void FillByteBuffer()
50+
{
51+
if (requires_seed) {
52+
RandomSeed();
53+
}
54+
rng.Output(bytebuf, sizeof(bytebuf));
55+
bytebuf_size = sizeof(bytebuf);
56+
}
57+
58+
void FillBitBuffer()
59+
{
60+
bitbuf = rand64();
61+
bitbuf_size = 64;
62+
}
63+
3664
public:
37-
explicit FastRandomContext(bool fDeterministic=false);
65+
explicit FastRandomContext(bool fDeterministic = false);
3866

39-
uint32_t rand32() {
40-
Rz = 36969 * (Rz & 65535) + (Rz >> 16);
41-
Rw = 18000 * (Rw & 65535) + (Rw >> 16);
42-
return (Rw << 16) + Rz;
67+
/** Initialize with explicit seed (only for testing) */
68+
explicit FastRandomContext(const uint256& seed);
69+
70+
/** Generate a random 64-bit integer. */
71+
uint64_t rand64()
72+
{
73+
if (bytebuf_size < 8) FillByteBuffer();
74+
uint64_t ret = ReadLE64(bytebuf + 64 - bytebuf_size);
75+
bytebuf_size -= 8;
76+
return ret;
4377
}
4478

45-
bool randbool() {
46-
return rand32() & 1;
79+
/** Generate a random (bits)-bit integer. */
80+
uint64_t randbits(int bits) {
81+
if (bits == 0) {
82+
return 0;
83+
} else if (bits > 32) {
84+
return rand64() >> (64 - bits);
85+
} else {
86+
if (bitbuf_size < bits) FillBitBuffer();
87+
uint64_t ret = bitbuf & (~(uint64_t)0 >> (64 - bits));
88+
bitbuf >>= bits;
89+
bitbuf_size -= bits;
90+
return ret;
91+
}
4792
}
4893

49-
uint32_t Rz;
50-
uint32_t Rw;
94+
/** Generate a random 32-bit integer. */
95+
uint32_t rand32() { return randbits(32); }
96+
97+
/** Generate a random boolean. */
98+
bool randbool() { return randbits(1); }
5199
};
52100

53101
/* Number of random bytes returned by GetOSRand.

‎src/test/addrman_tests.cpp‎

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -203,10 +203,11 @@ BOOST_AUTO_TEST_CASE(addrman_select)
203203
BOOST_CHECK(addrman.size() == 7);
204204

205205
// Test 12: Select pulls from new and tried regardless of port number.
206-
BOOST_CHECK(addrman.Select().ToString() == "250.4.6.6:8333");
207-
BOOST_CHECK(addrman.Select().ToString() == "250.3.2.2:9999");
208-
BOOST_CHECK(addrman.Select().ToString() == "250.3.3.3:9999");
209-
BOOST_CHECK(addrman.Select().ToString() == "250.4.4.4:8333");
206+
std::set<uint16_t> ports;
207+
for (int i = 0; i < 20; ++i) {
208+
ports.insert(addrman.Select().GetPort());
209+
}
210+
BOOST_CHECK_EQUAL(ports.size(), 3);
210211
}
211212

212213
BOOST_AUTO_TEST_CASE(addrman_new_collisions)

‎src/test/prevector_tests.cpp‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,7 @@ class prevector_tester {
2828
typedef typename pretype::size_type Size;
2929
bool passed = true;
3030
FastRandomContext rand_cache;
31+
uint256 rand_seed;
3132

3233

3334
template <typename A, typename B>
@@ -183,13 +184,12 @@ class prevector_tester {
183184
}
184185

185186
~prevector_tester() {
186-
BOOST_CHECK_MESSAGE(passed, "insecure_rand_Rz: "
187-
<< rand_cache.Rz
188-
<< ", insecure_rand_Rw: "
189-
<< rand_cache.Rw);
187+
BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString());
190188
}
189+
191190
prevector_tester() {
192191
seed_insecure_rand();
192+
rand_seed = insecure_rand_seed;
193193
rand_cache = insecure_rand_ctx;
194194
}
195195
};

‎src/test/random_tests.cpp‎

Lines changed: 20 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,5 +15,24 @@ BOOST_AUTO_TEST_CASE(osrandom_tests)
1515
BOOST_CHECK(Random_SanityCheck());
1616
}
1717

18-
BOOST_AUTO_TEST_SUITE_END()
18+
BOOST_AUTO_TEST_CASE(fastrandom_tests)
19+
{
20+
// Check that deterministic FastRandomContexts are deterministic
21+
FastRandomContext ctx1(true);
22+
FastRandomContext ctx2(true);
23+
24+
BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
25+
BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
26+
BOOST_CHECK_EQUAL(ctx1.rand64(), ctx2.rand64());
27+
BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
28+
BOOST_CHECK_EQUAL(ctx1.randbits(7), ctx2.randbits(7));
29+
BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
30+
BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
1931

32+
// Check that a nondeterministic ones are not
33+
FastRandomContext ctx3;
34+
FastRandomContext ctx4;
35+
BOOST_CHECK(ctx3.rand64() != ctx4.rand64()); // extremely unlikely to be equal
36+
}
37+
38+
BOOST_AUTO_TEST_SUITE_END()

‎src/test/test_bitcoin.cpp‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,8 @@
2727
#include <boost/filesystem.hpp>
2828
#include <boost/thread.hpp>
2929

30-
FastRandomContext insecure_rand_ctx(true);
30+
uint256 insecure_rand_seed = GetRandHash();
31+
FastRandomContext insecure_rand_ctx(insecure_rand_seed);
3132

3233
extern bool fPrintToConsole;
3334
extern void noui_connect();

‎src/test/test_random.h‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,11 +8,17 @@
88

99
#include "random.h"
1010

11+
extern uint256 insecure_rand_seed;
1112
extern FastRandomContext insecure_rand_ctx;
1213

1314
static inline void seed_insecure_rand(bool fDeterministic = false)
1415
{
15-
insecure_rand_ctx = FastRandomContext(fDeterministic);
16+
if (fDeterministic) {
17+
insecure_rand_seed = uint256();
18+
} else {
19+
insecure_rand_seed = GetRandHash();
20+
}
21+
insecure_rand_ctx = FastRandomContext(insecure_rand_seed);
1622
}
1723

1824
static inline uint32_t insecure_rand(void)

0 commit comments

Comments
 (0)