Permutative Trapdoors and History Hashes

Home / Previous Lesson / Next Lesson

A practical answer is to introduce a second corkscrew hash, with a rotation coprime to both 16 and (the rotation of sequence_hash). In the code, this is known as "history_hash". history_hash is simply a hash of every unique sequence_hash in the order in which it was observed. It is for all practical purposes utterly unpredictable, but we can tolerate the first (2^15) history hashes being predictable. (In reality, the first one is virtually indeterminate to begin with, let alone the (2^15)th.)

There is the obvious temptation to use the history hash as entropy directly. I don't like this idea because it slightly facilitates differential prediction, whereby an attacker might be able to predict something about the next 16 bits of entropy from the previous 16. Instead, we invoke the titanic entropy power of the permutation. It works like this:

enranda_rewind() (which need never be called directly, as it launches from enranda_init() automatically) sets up a permutation consisting of every whole number on [0, (2^16)-1] at unique_list_base (where "unique" reflects the fact that each whole is thus unique). After every update to history_hash, it becomes a swap index into unique_list_base. So after the first update, we swap the whole number at index zero with the whole number at index history_hash. After the next update, we swap the whole number at index one with the whole number at index history_hash, etc. The result, after (2^16) updates of history_hash, is a random permutation of all possible 16-bit values. This permutation constitutes Enranda's protoentropy. It can assume any of about (2^954,036) possible states (2^(log2((2^16)!))). Eventually, the low half of the protoentropy will be added (more or less, as explained below) to the high half in order to create entropy for output.

Now perhaps you can understand why we can "only" tolerate roughly (2^15) predictable (history_hash)es: the output entropy is half as large as the protoentropy. Granted, half of the protoentropy doesn't quite equate to the entropy of (2^15) 16-bit values because they are all unique; but for all practical purposes, this rule of thumb is valid.

It's important to point out that while the permutation is created during entropy accrual, the trapdoor addition which "folds" the protoentropy in half occurs at the moment when entropy is requested, via the enranda_entropy_u16/u32/u64/u8_list_get() family of functions. For its part, the addition occurs with carry propagation across at least 16 successive bits, even if the output buffer is byte-granular. The reason for this is that (1) we don't want to propagate the carry continuously, because that would serialize the output process, which would be bad because the whole idea is that entropy needs to be delivered immediately and (2) 16-bit propagation is sufficient, because although it induces a bias in the output, such bias is statistically invisible to even theoretically acquirable quantum computing resources. This is due to the very slightly constrained number of possible outputs which one can obtain by adding the low half of a permutation to its high half. For example, it's not possible to generate (2^15) 16-bit zeroes in a row, but ((2^15)-1) is indeed possible. I conjecture that the bias reduces the number of possible outputs from (2^19) to (R(2^19)), where R is the reflexive density constant. Either way, such a bias is negligible.