Comment by benkuykendall | Hacker News Reader

Comment by benkuykendall | Hacker News Reader

With the whitening requirement already depending on an algorithm with cryptographic guarantees (they use SHA3), this hardware only seems useful for generating keys.

They suggest the following algorithm to generate N bytes:

> The Inifite Noise driver uses the reference version of the SHA3 "sponge", called Keccak, with a 1600 bit state. To make the state of the sponge unpredictable, it is initialized with 20,000 bits of of Infinite Noise data before any data is output. After that, reading bytes from the SHA3 sponge blocks until twice as many bytes of entropy have been fed into the sponge from the Infinite Noise TRNG.

In code, that is

  repeat N / (block size) times:
    raw <- output of hardware
    output SHA3(raw)

They claim that the hardware outputs only log(1.82) bits of entropy per bit. Thus, they are relying on SHA3 to act as a cryptographic extractor.

Now, I don't think it's proven that the existence of an extractor implies the existence of psuedorandomness. However, I believe the usual construction would still assume that SHA3 was a psuedorandom generator. Under this assumption, then the following algorithm also outputs psuedorandom bits, but with only one use of the hardware.

  let seed <- output of hardware
  repeat N / (2 * block size) times:
    result <- SHA3(seed)
    seed <- first half of result
    output second half of result

(Assuming the PRG is length-doubling. If it is less than length-doubling, we can still construct a length-doubling PRG wlog)

Does anyone know why (I'd accept cryptographic, philosophical, or practical reasons) the first algorithm would be preferable to the second?

Relevant reading (both highly recommended books in their own right!):

  Arora & Barak "Computational Complexity" Ch 21 "Expanders and Extractors"
  
  Goldreich "Founds of Cryptography I" defines PRG and so forth

SHA3 should be assumed to be psuedorandom under its inputs. If this can be shown to not be the case, SHA3 would be considered broken.

There is no reason once you have collected a sufficient amount of entropy (~128 bits), to continue to collect it from the device. You would want to also mix in other entropy sources as well, to prevent an attack along the lines of the Dual EC DRBG kerfuffle.

That's not what was being asked; what was being asked is "why wouldn't you want to persist some bits from a previous emission to a current one?" and the answer is "you do; it helps you in threat models where the attacker is somehow able to blast some hardware for a tiny time such that they can control an N bit-chunk of seed material, but not what came before or after." If you don't persist some bits between the calls, then this lets them determine entirely a few outputs of your RNG -- albeit scrambled by SHA3, but for some security expectations that's sufficient. On the other hand if you persist a seeding block between hash invocations, you block these attacks rather easily.

They're using something very similar to your second algorithm, but the structure is in fact baked into SHA3, and in fact your second approach essentially takes their literal suggestion and modifies it by, every round, zeroing some of their PRNG state bits. I don't need to tell you why that's less preferable than what they're doing! (Your approach also has something in the range of 1-2 times more memory usage, but that only matters for embedded applications since neither one has high memory demands.) But yeah, this is definitely not your first algorithm.

Details: during a hash, SHA3 at all times is keeping a very large state block of 1600 bits. It defines a pseudorandom permutation (think of a block cipher with a block size of 1600 bits and a fixed key) of those 1600 bits as its round function. To run the hash, you pad your message and then break it into N blocks of size `rate`; starting from a zeroed state you XOR in a block to the first `rate` bits of the state, then permute the state with the round function, repeat until all blocks are consumed. Afterwards you read the first `rate` bits, and if that's not enough, you permute the state and repeat until all the output blocks you want are generated. (The magic number of 1600 was chosen in part so that you wouldn't generally need to do this; for SHA3-512 the rate is still 576 bits with 1024 bits of "capacity" in the sponge, so one read is enough to pull out the 512 bits of output.)

Now that you understand the hash, to use it as a PRNG, you just reseed it with the XOR-then-Permute operation and read it with the readout-then-Permute operation, interleaved. Each readout that you get is therefore formally equivalent to a SHA3 hash of

     initial_seed_bytes + 
         repeat(zeros, number_requests_before_first_reseed)  +
         first_reseed_bytes +
         repeat(zeros, number_requests_before_second_reseed) +
         (...)

which proves that getting the PRNG to return a specific random string X is no easier than a preimage-attack on SHA3 for that string X. (This is why the researchers involved invented the sponge construction as an alternative to Merkle-Damgard; it was easy to prove security properties about it.)

Since an N-bit hash generally needs a 2N-bit state anyway to avoid nasty meet-in-the-middle attacks and such, the SHA3 PRNG is better than generic constructions purely because it can avoid a pointless R+C => R bit state reduction, which (since SHA3 starts from a 0-state and XORs in the first R bits as your seed block) is exactly same thing as zeroing all of the reserved C bits that aren't normally attacker-writable.

Reply on news.ycombinator.com