Use a better PRNG unless OpenSSL starts using a better one on their own.

#17694 (moved) hashes important PRNG output with some system randomness before use, so that observed PRNG outputs are resistant to PRNG state analysis.

But almost all of Tor's use of PRNG outputs is observable from one or more locations outside Tor, whether in salts or nonces sent to other machines on the wire, or in the random choices made in guard, directory, and path selection.

We could hash all of the bytes coming from the PRNG to avoid this state exposure. (Although we might not need to use the system randomness source each time.)

changed milestone to %Tor: unspecified

added actualpoints::5 component::core tor/tor crypto milestone::Tor: unspecified owner::nickm points::5 priority::medium prng resolution::worksforme review-group-34 reviewer::asn severity::normal status::closed tor-client tor-relay type::defect version::tor unspecified labels

Here is the design I would suggest for such a thing.

Replace crypto_rand() with a construction that fills an internal buffer by taking bytes from RAND_byes() and then passing them through SHAKE128 to expand them. Then yield bytes from that buffer as required. As yielding them, clear the buffer. When the buffer is exhausted, refill it.

If we want, we can seed the initial buffer with crypto_strongest_rand(), and seed subsequent buffers with a mixture of the tail-end of the previous buffer and RAND_bytes().

This should meet the design criteria described above, and provide better performance and security than the current openssl nonsense.

I can take care of this once the SHA3 branch (#17783 (moved)) is merged.

I accidentally another prng.

Branch is shake_prng based on Yawning's branch for #17783 (moved).

Ready for quick looks, but not for serious review. It needs more documentation, real testing, free-on-exit, windows testing, etc.

Trac:
Status: new to needs_revision

I don't mind this in principle.

But if we're that scared of OpenSSL's RAND_bytes(), we may as well wrap our newfangled PRNG construct in the appropriate OpenSSL struct and set it as the engine so that TLS and all the OpenSSL internal entropy requests use our thing as well.

We're essentially replacing a SHA based DRBG with a SHAKE based one, which still feels rather silly to me. (The strongest_random call gets a pass because we don't go through OpenSSL there).

See the second patch on my branch. :)

Replying to nickm:

See the second patch on my branch. :)

Spiffy. Minor quibble with the code, don't use KECCAK_MAX_RATE like that (Yeah, I should have renamed it/hid it). Since you're instantiating SHAKE128, KECCAK_TARGET_TO_RATE(128) is what you want (Or 168, which is the SHAKE128 rate in bytes).

It'll still work, but you're lowering your security level. My improved version of the branch will be more opaque to avoid this confusion/pitfall and provide shake128_init/absorb/squeeze/free functions.

I added a whole bunch of fixes and changes in shake_prng, quite likely breaking something.

Benchmark says it's 6.6x faster than openssl's PRNG for short-ish outputs. IMO this means there's no need to jump into the wacky world of libottery's additional hacks.

The main change still needed would be getting #17783 (moved) merged, and then rebasing this and cleanup up the branch.

The Keccak authors have a paper regarding how to construct a sponge based PRNG. http://sponge.noekeon.org/SpongePRNG.pdf

The Keccak sponge function is an invertible permutation, right? If so, unless I'm crazy or missing something, I don't think their design would provide backtracking resistance except when new entropy is added. Looks a teeny bit faster though, but probably not a huge amount.

Replying to nickm:

The Keccak sponge function is an invertible permutation, right? If so, unless I'm crazy or missing something, I don't think their design would provide backtracking resistance except when new entropy is added. Looks a teeny bit faster though, but probably not a huge amount.

Indeed, though see 4.3. Compared to the construct you use, the main difference seemed performance related, I linked the paper mainly for reference. Rebasing against my take2 branch should be easy, let me know if it's not and I can fix it further.

I think their performance is likely to be worse, but their space usage is likely to be better. If I'm doing the math right, and we're using SHAKE-128 or equivalent, and we assume that we want to have 2^256^ security against backtracking attacks, I get 166.7 bytes per Keccak-f call with 4K memory usage, and they get 152 bytes,with somewhere between 200 and 400 bytes of memory usage.

(I'm also assuming that reseed events are comparatively uncommon. If that's wrong, oops!)

Shake_prng_v2 is rebased and mostly squashed.

(I just did a force-update on it to clean up a couple of things; please don't hate me.)

I made a couple more changes to shake_prng_v2. Notably the pointer arithmetic is much simpler.

Trac:
Status: needs_revision to needs_review

Rebased and squashed as shake_prng_v3.

I wrote the code here, so setting myself as owner.

Trac:
Owner: N/A to nickm
Status: needs_review to assigned

... but they still need_review

Trac:
Status: assigned to needs_review

Trac:
Milestone: Tor: 0.2.8.x-final to Tor: 0.2.9.x-final

Trac:
Points: N/A to small/medium-remaining
Reviewer: N/A to N/A