This patch improves the built-in RNG using hash strengthening.
At startup, and once every minute, 32 bytes of entropy are produced from the RNG, repeatedly hashed using SHA512 for 10ms, and then fed back into the RNG, together with high-precision timestamps obtained every 1000 iterations.
Is there a rationale for values "10ms" and "1000 iterations"?
@hebasto Sort of.
10ms as it's a amount that shouldn't cause any measurable latency in the background thread (where generally things run that aren't very time critical anyway).
1000 seems a nice trade-off between time spent on getting the time, and getting entropy out. If we'd get the clock every iteration, we'd be spending more time in reading the clock than actually strenghtening anything. If we'd only get it every 1000000 iterations, we'd probably only read the clock once and not get much entropy from that.
Concept ACK.
@sipa What would be the appropriate way to test/measure the improvement this change brings?
430 | @@ -432,6 +431,7 @@ libbitcoin_util_a_SOURCES = \ 431 | logging.cpp \ 432 | random.cpp \ 433 | rpc/protocol.cpp \ 434 | + shutdown.cpp \
Moving shutdown.cpp to util might not be a good choice, architecturally: it's shared between all executables, by far most of which don't use bitcond's init/shutdown mechanism. It's meant for general-purpose utilities.
server would be the right place, it's really part of the server functionality (shared between bitcoind and bitcoin-qt and unit tests…).
I can wait 10ms
464 | @@ -436,7 +465,23 @@ static void SeedSlow(CSHA512& hasher) noexcept 465 | SeedTimestamp(hasher); 466 | } 467 | 468 | -static void SeedSleep(CSHA512& hasher) 469 | +/** Extract entropy from rng, strengthen it, and feed it into hasher. */ 470 | +static void SeedStrengthen(CSHA512& hasher, RNGState& rng) noexcept 471 | +{ 472 | + // Once per minute, strengthen the hash for 10ms. 473 | + static std::atomic<int64_t> last_strengthen;
Initialize?
Static variables are always auto-initialized to zero, but for clarity, I've added an explicit zero.
473 | + static std::atomic<int64_t> last_strengthen; 474 | + int64_t current_time = GetTimeMicros(); 475 | + if (current_time > last_strengthen + 60000) { 476 | + // Generate 32 bytes of entropy from the RNG. 477 | + unsigned char buf[32]; 478 | + rng.MixExtract(buf, 32, CSHA512(), false);
Nit: might be slightly more readable to rename buf to strengthener_seed, or expand the comment with ", to seed the strengthener."
Done.
142 | @@ -143,6 +143,34 @@ static bool GetHardwareRand(unsigned char* ent32) noexcept { 143 | return false; 144 | } 145 | 146 | +/** Use repeated SHA512 to strengthen the randomness in seed32, and feed into hasher. */ 147 | +static void Strengthen(const unsigned char* seed32, int microseconds, CSHA512& hasher) noexcept 148 | +{ 149 | + CSHA512 inner_hasher; 150 | + inner_hasher.Write(seed32, 32);
Unless I'm misunderstanding it, the data collected by SeedStartup doesn't get strengthened in the first run of the strenghtener. This seems pretty suboptimal since SeedStartup is the obvious place to go get most of the weak pseudo-entropy (like filesystem data, network interface data, etc.) which is the stuff that most benefits from strengthening.
Good point, fixed.
It now extracts using the hasher state combined with the RNG.
So overall what happens in SeedStartup is:
E. E = SeedStuff()R0), and split the result in a seed and the new RNG state, so [S,R1] = SHA512(E || R0)S gets strengthened, S' = SHA512(SHA512(...(S)))S' is added to E, and mixed into the RNG: [_,R2] = SHA512(E || S' || R1).It's a bit weird in that it uses E both in construction R1 and R2, but I don't see how that can hurt.
I'd still prefer to see this using 4x SHA256^2-64b since that function has a much better ratio of current performance to attacker performance, but I grok the startup time interactions with function auto-detection make that messy. I'm okay with using sha512 for now in light of that!
We should contemplate increasing the strenghtening time on the first run. Rationale: usually long term private keys will get generated within one minute of first startup when only the startup strengthening will have applied. Adding an extra 90ms on startup won't be significantly noticeable on top of the existing startup time, and would increase resistance to search by 10x. Alternative: Once we've started carrying randomness across restarts in a file, a prolonged startup strengthen would only be needed when there is no saved randomness.
472 | + static std::atomic<int64_t> last_strengthen{0}; 473 | + int64_t current_time = GetTimeMicros(); 474 | + if (current_time > last_strengthen + 60000) { 475 | + // Generate 32 bytes of entropy from the RNG, and a copy of the entropy already in hasher. 476 | + unsigned char strengthen_seed[32]; 477 | + rng.MixExtract(strengthen_seed, 32, CSHA512(hasher), false);
nit: sizeof(strengthen_seed) would avoid the duplication here.
Fixed.
142 | @@ -143,6 +143,34 @@ static bool GetHardwareRand(unsigned char* ent32) noexcept { 143 | return false; 144 | } 145 | 146 | +/** Use repeated SHA512 to strengthen the randomness in seed32, and feed into hasher. */ 147 | +static void Strengthen(const unsigned char* seed32, int microseconds, CSHA512& hasher) noexcept
nit: passing in seed32's length could be less error prone, in that the function would make fewer assumptions about the arguments / have fewer preconditions for them. Could be good to document the size precondition in the comment as an alternative.
Fixed by using the C++11 "pass a reference to array of fixed size" construction (which will cause a compilation failure of the array has the wrong length).
utACK
149 | + CSHA512 inner_hasher; 150 | + inner_hasher.Write(seed, sizeof(seed)); 151 | + 152 | + // Hash loop 153 | + unsigned char buffer[64]; 154 | + int64_t start = GetTimeMicros();
nit const int64_t stop = GetTimeMicros() + microseconds;
Nice, done.
164 | + } while (GetTimeMicros() < start + microseconds); 165 | + 166 | + // Produce output from inner state and feed it to outer hasher. 167 | + inner_hasher.Finalize(buffer); 168 | + hasher.Write(buffer, sizeof(buffer)); 169 | + // Try to clean up.
Can you explain why "try"?
The C++ language has no way of guaranteeing memory gets cleaned up (it may have copied it elsewhere in memory, for starters, or detect that the clearing has no observable effect and optimize it away).
Once every minute, this will feed the RNG state through repeated SHA512
for 10ms. The timings of that operation are used as entropy source as
well.
utACK 3cb9ce85d0c6d01217babf0df7efc2eabde1b12f
Just wanted to note that the unit tests run 10% slower due to this:
@MarcoFalke Interesting. Is that considered too much? We could disable the strengthening time, or make it configurable... though at the cost of some complexity (the RNG may be used before command line options are parsed...)
Not really. Just mentioned because it might be interesting to some.
Milestone
0.19.0