Seed RNG with precision timestamps on receipt of net messages. #17573

TheBlueMatt · 2019-11-23T16:51:40Z

See title. Exposes a generic dead-simple "SeedEvent" interface, but currently just used for net messages.

sipa · 2019-11-23T17:00:07Z

src/random.h

+ *
+ * Thread-safe.
+ */
+void SeedEvent(const unsigned char* event_type_buf, size_t buf_len);


Do we expect the argument to always be a string? The interface could be made a bit simpler and safer if that's the case (you could also avoid the size_t prefix, and instead just write the c_str() including null byte, which self-describes the length).

I presume not, both for upcoming p2p encryption where the message type may just be a char, and I currently have some radio stuff hooked up that dumps RSSI information into this.

I kind of prefer this general (ptr,size) interface to using C strings, whose use we're generally trying to avoid in bitcoin code. std::string_view would be a safer interface, if only C++11 had it.

Here is a more C++ish interface, that serializes (through the serialization framework) all arguments passed to SeedEvent (without any allocations): https://github.com/sipa/bitcoin/tree/bluematt_2019-11-rng-netmsg

Oof, that's....quite a bigger diff. Are you worried about the current interface introducing bugs? I don't think it's particularly likely (nor are we likely to add calls to this everywhere), and it matches the rest of the random. interface.

If you switch to SHA256 (which you did) it's much smaller.

It also enables efficiently adding extra information without first copying everything into a buffer (say, you could call SeedEvent(msg.command, peerid); just as easily)

I agree it's perhaps overkill - up to you.

src/random.cpp

TheBlueMatt · 2019-11-23T18:29:50Z

It was pointed out that this would make processing of small net messages particularly slower. Instead of only mixing in extra randomness for large net messages I switched it to SHA256 to use our existing ASM optimizations here. Also changed the fn name to be closer to the rest of random.h.

sipa · 2019-11-23T18:37:19Z

src/random.cpp

@@ -553,6 +577,16 @@ void GetRandBytes(unsigned char* buf, int num) noexcept { ProcRand(buf, num, RNG
 void GetStrongRandBytes(unsigned char* buf, int num) noexcept { ProcRand(buf, num, RNGLevel::SLOW); }
 void RandAddPeriodic() { ProcRand(nullptr, 0, RNGLevel::PERIODIC); }

+void RandAddEvent(const unsigned char* event_type_buf, size_t buf_len) {
+    LOCK(events_mutex);
+    events_hasher.Write((unsigned char *)&buf_len, sizeof(size_t));


You could also limit this to 4 bytes (or even 2...), if size is an issue.

Hmm, I'm not too worried about it? Its mostly up to the caller and right now net will only ever pass in 12+4+8 bytes per call, which means it will never be more than one extra hash per two messages, which seems reasonable.

src/random.cpp

sipa · 2019-11-23T18:44:22Z

A comment on including the timestamp: GetPerformanceCounter on ARM is not extremely cheap (it involves a system call), perhaps you'd want a way for the caller to provide their own timestamp (or timestamp-like variable), as I assume generally they already have one?

TheBlueMatt · 2019-11-23T18:48:04Z

Hmm, net does have one, but its also mostly intended for things exactly like net, where you are handling an "event" that is the result of a syscall already...Unless its particularly more expensive than poll() + read(), I'm not too worried :). Its not like we're gonna call it somewhere where performance in nanoseconds is absolutely critical, though may be calling it in places where DoS is a risk. So...don't think its worth breaking the abstraction for it.

sipa · 2019-11-23T18:52:24Z

I would indeed assume that it's not more expensive than poll+read, good point.

sipa · 2019-11-23T19:18:13Z

Here is another idea: use the serialization-based interface, but instead feeding it directly into events_hasher, feed it into a SipHasher instead. Then feed a few bits (8, 16, 32?) of the SipHash of all passed data to events_hasher. That should be both simpler (no need to expose internals as much), and faster (much less SHA256'ing, don't hold lock as long).

TheBlueMatt · 2019-11-23T19:21:35Z

Even simpler idea, just use the damn message hash instead of the command :). Its nice and small (4 bytes), plus has more entropy in it anyway. Since our (real) goal is to get the time when we receive a message, that's more than sufficient, but we also steal our peers' entropy in their ping nonces :).

sipa · 2019-11-23T20:27:07Z

Nice... if the caller has too much data they can always siphash or wahtever it thenselves. You could simplify the interface by just allowing a uint32_t to be passed or so.

TheBlueMatt · 2019-11-23T20:44:27Z

Done. Its now an explicit uint32_t.

src/net.cpp

src/random.h

sipa · 2019-11-23T21:50:34Z

src/random.cpp

+    events_hasher.Finalize(events_hash);
+    hasher.Write(events_hash, 32);
+
+    // Re-initialize the hasher with the finalized state to use later.


sipa · 2019-11-23T21:51:00Z

utACK 02d8c56

DrahtBot · 2019-11-23T22:22:20Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#17167 (Allow whitelisting outgoing connections by luke-jr)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

sipa · 2019-11-23T22:27:03Z

This effectively adds one SHA256 compression per 8 messages/connections. That seems acceptably low, compared to the work already done for message checksumming.

meshcollider

utACK 02d8c56

TheBlueMatt · 2019-11-24T17:30:52Z

The AppVeyor build fail occurs before build even starts, so is a false positive.

practicalswift · 2019-11-25T00:02:08Z

Concept ACK: nice idea and straightforward implementation

practicalswift · 2019-11-25T00:11:58Z

Clang Thread Safety Analysis annotations seem to be missing? :)

naumenkogs · 2019-12-03T20:09:51Z

Concept ACK

laanwj · 2019-12-04T12:12:23Z

ACK 02d8c56

…ssages. 02d8c56 Seed RNG with precision timestamps on receipt of net messages. (Matt Corallo) Pull request description: See title. Exposes a generic dead-simple "SeedEvent" interface, but currently just used for net messages. ACKs for top commit: sipa: utACK 02d8c56 laanwj: ACK 02d8c56 meshcollider: utACK 02d8c56 Tree-SHA512: 28eb39a201ee2b13393c5c64dbf7c1913f3482f095969ef5141bfe549ce77dd63bb5f14738f6eedb296c686ea36014aa157b9c5e8059710a318590f30e9caa14

practicalswift · 2019-12-04T13:22:09Z

@laanwj I was a bit surprised to see this merged without thread safety annotations, or more specifically before the thread safety questions were addressed. Was there a reason for that? :)

laanwj · 2019-12-04T13:39:00Z

It has three ACKs and passes travis.

If you want to add any annotations, go ahead, but we're not going to block merges on always new requirements.

… net messages. 02d8c56 Seed RNG with precision timestamps on receipt of net messages. (Matt Corallo) Pull request description: See title. Exposes a generic dead-simple "SeedEvent" interface, but currently just used for net messages. ACKs for top commit: sipa: utACK bitcoin@02d8c56 laanwj: ACK 02d8c56 meshcollider: utACK 02d8c56 Tree-SHA512: 28eb39a201ee2b13393c5c64dbf7c1913f3482f095969ef5141bfe549ce77dd63bb5f14738f6eedb296c686ea36014aa157b9c5e8059710a318590f30e9caa14

sipsorcery · 2019-12-04T20:37:04Z

This change is causing problems on Windows. No appveyor tests have passed since it was merged and I've also verified locally that bitcoind.exe, bitcoin-qt.exe, bench_bitcoin.exe and test_bitcoin.exe are failing. Failing in this case means exiting almost immediately with no error message.

Running the programs in the Visual Studio debugger gets an Access Violation exception reported on the LOCK(events_mutex) call. I'm always cautious with Access Violation exceptions as often the cause could have been an earlier call and the reported site is a side effect.

As a quick and dirty test I moved the declaration of static Mutex events_mutex to be a local static variable in the two methods using it. The programs were all able to run normally after that. I realise that's defeating the purpose of the mutex so isn't a fix.

sipa · 2019-12-04T20:39:59Z

@sipsorcery I should have known that would happen; I suspect it is invoking the RNG before global initialization is complete, and thus potentially before events_mutex is initialized. Working on a fix.

EDIT: see #17670.

8bda096 Move events_hasher into RNGState() (Pieter Wuille) Pull request description: This moves `events_hasher` and `events_mutex` into `RNGState()` in random.cpp. This guarantees (through the existing `GetRNGState()` function) that the mutex is always created before any events are added, even when that happens inside global initializers. Fixes the issue reported here: #17573 (comment), and includes the annotation from #17666). ACKs for top commit: MarcoFalke: re-ACK 8bda096 🥈 sipsorcery: re-ACK 8bda096. Tree-SHA512: 78702d668764df19e9d61d87d82eca71cceca87d5351b740e13e732a1c18a3d53d7fbaaf63245266da597370bfebec9fa6a4749c15ec5a78dcfe6122c33553ed

1f9d5af tests: Add initialization order fiasco detection in Travis (practicalswift) Pull request description: Add initialization order fiasco detection in Travis :) Context: #17670 (comment) This would have caught the `events_hasher` initialization order issue introduced in #17573 and fixed in #17670. Output in case of an initialization order fiasco: ``` ==7934==ERROR: AddressSanitizer: initialization-order-fiasco on address 0x557098d79200 at pc 0x55709796b9a3 bp 0x7ffde524dc30 sp 0x7ffde524dc28 READ of size 8 at 0x557098d79200 thread T0 #0 0x55709796b9a2 in CSHA256::Finalize(unsigned char*) src/crypto/sha256.cpp:667:25 #1 0x5570978150e9 in SeedEvents(CSHA512&) src/random.cpp:462:19 #2 0x5570978145e1 in SeedSlow(CSHA512&) src/random.cpp:482:5 #3 0x5570978149a3 in SeedStartup(CSHA512&, (anonymous namespace)::RNGState&) src/random.cpp:527:5 #4 0x55709781102d in ProcRand(unsigned char*, int, RNGLevel) src/random.cpp:571:9 #5 0x557097810d19 in GetRandBytes(unsigned char*, int) src/random.cpp:576:59 #6 0x557096c2f9d5 in (anonymous namespace)::CSignatureCache::CSignatureCache() src/script/sigcache.cpp:34:9 #7 0x557096511977 in __cxx_global_var_init.7 src/script/sigcache.cpp:67:24 #8 0x5570965119f8 in _GLOBAL__sub_I_sigcache.cpp src/script/sigcache.cpp #9 0x557097bba4ac in __libc_csu_init (src/bitcoind+0x18554ac) #10 0x7f214b1c2b27 in __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:266 #11 0x5570965347d9 in _start (src/bitcoind+0x1cf7d9) 0x557098d79200 is located 96 bytes inside of global variable 'events_hasher' defined in 'random.cpp:456:16' (0x557098d791a0) of size 104 registered at: #0 0x557096545dfd in __asan_register_globals compiler-rt/lib/asan/asan_globals.cpp:360:3 #1 0x557097817f8b in asan.module_ctor (src/bitcoind+0x14b2f8b) SUMMARY: AddressSanitizer: initialization-order-fiasco src/crypto/sha256.cpp:667:25 in CSHA256::Finalize(unsigned char*) ``` ACKs for top commit: promag: Tested ACK 1f9d5af, got MarcoFalke: ACK 1f9d5af 👔 Tree-SHA512: f24ac0a313df7549193bd7f4fcfdf9b72bdfc6a6ee31d0b08e6d0752e5108fbd532106b6c86377ae0641258c9adb4921872e5d9a0154c0284e03315e0777102c

… net messages. 02d8c56 Seed RNG with precision timestamps on receipt of net messages. (Matt Corallo) Pull request description: See title. Exposes a generic dead-simple "SeedEvent" interface, but currently just used for net messages. ACKs for top commit: sipa: utACK bitcoin@02d8c56 laanwj: ACK 02d8c56 meshcollider: utACK 02d8c56 Tree-SHA512: 28eb39a201ee2b13393c5c64dbf7c1913f3482f095969ef5141bfe549ce77dd63bb5f14738f6eedb296c686ea36014aa157b9c5e8059710a318590f30e9caa14

Summary: [[bitcoin/bitcoin#17573 | PR17573]]: > Exposes a generic dead-simple "SeedEvent" interface, but currently just used for net messages. This PR caused CI failures on Windows, and was patched the day after its merge with the following: [[bitcoin/bitcoin#17670 | PR17670]] > This moves events_hasher and events_mutex into RNGState() in random.cpp. This guarantees (through the existing GetRNGState() function) that the mutex is always created before any events are added, even when that happens inside global initializers. > > Fixes the issue reported here: [[bitcoin/bitcoin#17573 (comment) | #17573 (comment)]], and includes the annotation from #17666). This is a backport of Core [[bitcoin/bitcoin#17573 | PR17573]] and [[bitcoin/bitcoin#17670 | PR17670]] Test Plan: ``` cmake .. -GNinja -DCMAKE_C_COMPILER=clang -DCMAKE_CXX_COMPILER=clang++ -DCMAKE_BUILD_TYPE=Debug ninja all check-all ``` Reviewers: O1 Bitcoin ABC, #bitcoin_abc, Fabien Reviewed By: O1 Bitcoin ABC, #bitcoin_abc, Fabien Differential Revision: https://reviews.bitcoinabc.org/D8287

… net messages. 02d8c56 Seed RNG with precision timestamps on receipt of net messages. (Matt Corallo) Pull request description: See title. Exposes a generic dead-simple "SeedEvent" interface, but currently just used for net messages. ACKs for top commit: sipa: utACK bitcoin@02d8c56 laanwj: ACK 02d8c56 meshcollider: utACK 02d8c56 Tree-SHA512: 28eb39a201ee2b13393c5c64dbf7c1913f3482f095969ef5141bfe549ce77dd63bb5f14738f6eedb296c686ea36014aa157b9c5e8059710a318590f30e9caa14

cecbf6c Use secure.h header for secure allocators (Fuzzbawls) d9f67da net: add ifaddrs.h include (fanquake) e906436 build: check if -lsocket is required with *ifaddrs (fanquake) 414f405 rand: only try and use freeifaddrs if available (fanquake) 3a039d6 build: avoid getifaddrs when unavailable (Cory Fields) 77bddd7 Use GetStrongRandBytes in gmp bignum initialization (Fuzzbawls) b70b26f Fix typo in comment in randomenv.cpp (Fuzzbawls) fec460c Put bounds on the number of CPUID leaves explored (Pieter Wuille) 41ab1ff Fix CPUID subleaf iteration (Pieter Wuille) 8a9bbb1 Move events_hasher into RNGState() (Pieter Wuille) 88c2ae5 random: mark RandAddPeriodic and SeedPeriodic as noexcept (fanquake) 81d382f doc: correct random.h docs after bitcoin#17270 (fanquake) f363ea9 Seed RNG with precision timestamps on receipt of net messages. (Matt Corallo) 7d6ddcb Run background seeding periodically instead of unpredictably (Pieter Wuille) 4679181 Add information gathered through getauxval() (Pieter Wuille) 88d97d0 Feed CPUID data into RNG (Pieter Wuille) 8f5b9c9 Use sysctl for seeding on MacOS/BSD (Pieter Wuille) 67de246 Gather additional entropy from the environment (Pieter Wuille) 6142e1f Seed randomness with process id / thread id / various clocks (Pieter Wuille) 7bde8b7 [MOVEONLY] Move cpuid code from random to compat/cpuid (Fuzzbawls) 52b5336 [MOVEONLY] Move perfmon data gathering to new randomenv module (Pieter Wuille) 27cf995 doc: minor corrections in random.cpp (fanquake) fccd2b8 doc: correct function name in ReportHardwareRand() (fanquake) 909473e Fix FreeBSD build by including utilstrencodings.h (Fuzzbawls) 630931f break circular dependency: random/sync -> util -> random/sync (Fuzzbawls) 5eed08c random: remove call to RAND_screen() (Windows only) (fanquake) ada9868 gui: remove OpenSSL PRNG seeding (Windows, Qt only) (fanquake) 22a7121 Fix non-deterministic coverage of test DoS_mapOrphans (Fuzzbawls) 79e7fd3 Add ChaCha20 bench (Jonas Schnelli) 6966aa9 Add ChaCha20 encryption option (XOR) (Jonas Schnelli) 28c9cdb tests: Add script checking for deterministic line coverage (practicalswift) c82e359 test: Make bloom tests deterministic (MarcoFalke) 7b33223 Document strenghtening (Pieter Wuille) 0190dec Add hash strengthening to the RNG (Pieter Wuille) 67e336d Use RdSeed when available, and reduce RdRand load (Pieter Wuille) 4ffda1f Document RNG design in random.h (Pieter Wuille) 2b6381e Use secure allocator for RNG state (Pieter Wuille) 080deb3 Encapsulate RNGState better (Pieter Wuille) 787d72f DRY: Implement GetRand using FastRandomContext::randrange (Pieter Wuille) 5bc2583 Sprinkle some sweet noexcepts over the RNG code (Pieter Wuille) 774899f Remove hwrand_initialized. (Pieter Wuille) 698d133 Switch all RNG code to the built-in PRNG. (Pieter Wuille) 038a45a Integrate util/system's CInit into RNGState (Fuzzbawls) 5f20e62 Abstract out seeding/extracting entropy into RNGState::MixExtract (Pieter Wuille) 298f97c Add thread safety annotations to RNG state (Pieter Wuille) 2326535 Rename some hardware RNG related functions (Pieter Wuille) d76ee83 Automatically initialize RNG on first use. (Pieter Wuille) 1a5dbc5 Don't log RandAddSeedPerfmon details (Pieter Wuille) 32e6c42 Simplify testing RNG code (Fuzzbawls) 972effa Make unit tests use the insecure_rand_ctx exclusively (Fuzzbawls) af52bf5 Use a FastRandomContext in LimitOrphanTxSize (Fuzzbawls) 746d466 Introduce a Shuffle for FastRandomContext and use it in wallet (Fuzzbawls) 1cdf124 Use a local FastRandomContext in a few more places in net (Fuzzbawls) e862564 Make addrman use its local RNG exclusively (Fuzzbawls) 94b2ead Make FastRandomContext support standard C++11 RNG interface (Pieter Wuille) Pull request description: This is a collection of upstream PRs that have been backported to bring our RNG (`src/random`) code more up-to-date. The following upstream PRs have been included here: - bitcoin#12742 - bitcoin#14624 - some of this had already been merged previously - bitcoin#14955 - bitcoin#15250 - bitcoin#15224 - bitcoin#15324 - bitcoin#15296 - bitcoin#15512 - bitcoin#16878 - bitcoin#17151 - bitcoin#17191 - bitcoin#13236 - bitcoin#13314 - bitcoin#17169 - bitcoin#17270 - omitted last commit as our testing framework doesn't support it currently - omitted bitcoin@64e1e02, to be pulled in after our time utility is updated in a separate PR - bitcoin#17573 - bitcoin#17507 - bitcoin#17670 - bitcoin#17527 - bitcoin#14127 - bitcoin#21486 ACKs for top commit: furszy: ACK cecbf6c with a minor nit that can be easily tackled later. random-zebra: rebase utACK cecbf6c and merging... Tree-SHA512: 3463b693cc9bddc1ec15228d264a794f5c2f159073fafa2ccf6e2563abfeb4369e49505f97ca84f2478ca792bd07b66d2cd83c58044d6a0cae6af42d22f5784b

fanquake added P2P Utils/log/libs labels Nov 23, 2019