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.
Showing posts with label history hash. Show all posts
Showing posts with label history hash. Show all posts
Sunday, May 24, 2015
Antiperiodic Countermeasures: Sequence Hashes and Populations Thereof
Home / Previous Lesson / Next Lesson
Plausible periodic timedelta sequences must not be allowed to enable an attacker to predict any part of the output entropy. For safety's sake, we should endeavor to ignore them entirely. Let me say up front that, while Enranda cannot reject every periodic signal, it does so successfully up to period 255 (with caveats as explained below). Period 255 is utterly implausible in the most quiescent systems, let alone those interesting enough to warrant attack, unless they have been rooted in order to construct such a protracted period via malicious virtualization (a blue pill attack), in which case, the TRNG output is irrelevant anyway. So in practice, Enranda does indeed ignore all periodic signals. But without performing a computationally expensive operation such as treewise string compression, how can we accomplish this?
Enter the "sequence hash". Here's how it works. Suppose we have a period-5 timedelta stream:
{8, 9, 8, 3, 3, 8, 9, 8, 3, 3, 8, 9, 8, 3, 3, 8, 9, 8, 3, 3...}
We then identify, one at a time, each unique sequence in the order of discovery. In the periodic example above, this process would produce the following unique sequences separated by semicolons:
{8; 9; 8, 3; 3; 8, 9; 8, 3, 3; 8, 9, 8; 3, 3; 8, 9, 8, 3; 3...}
We don't actually search backwards, which would be computationally expensive. Instead Enranda implements the sequence hash ("sequence_hash" in the code) as a 16-bit "corkscrew hash" of successive 16-bit timedeltas until said hash is found to be "unique" (meaning that it has not occurred in the past (2^16) such hashes, as ensured by a ring buffer of sequence_hashes at sequence_hash_list_base, and their populations at sequence_hash_count_list_base). Just like its metal counterpart, a corkscrew hash rotates on each iteration in order to make it as sensitive as possible to the order of particular timedeltas, yet symmetric with respect to each iteration in that all bits of all timedeltas influence the corkscrew hash, regardless of order. The simplest corkscrew hashes meeting these criteria are rotate-and-add and rotate-and-xor; we use the former for the sake of maximum collision avoidance. (See enranda_entropy_accrue() for an example.) The reason for the rotation (which is coprime to 16 (bits)), is to achieve maximum dispersion despite most timedeltas being of similar small magnitude.
As soon as a unique sequence_hash is discovered, it's stored to sequence_hash_list_base and its population at sequence_hash_count_list_base is set to one, whereupon sequence_hash itself is reset to zero. But if a previously encountered hash is seen again (as evidenced by its population being nonzero), its population is incremented (such that wrapping back to zero is prohibited). The only way in which population can be decremented is by virtue of a sequence_hash expiring from sequence_hash_list_base, which contains (2^16) items.
Critically, the populations of all (2^16) possible (sequence_hash)es at sequence_hash_count_list_base are initially set to one by enranda_rewind(). This almost gaurantees that the first (2^16) timedelta observations will be ignored. A few such observations pass through this filter, but it doesn't matter because of the way that protoentropy is hashed into entropy, as explained later. And of course, there are hash collisions from time to time, meaning that we fail to detect a small fraction of unique sequences. This is a minor tax on efficiency, which is well worth the speed advantages of keeping the ring buffer and population list small enough to fit in most CPU caches.
So how many hashes, in the worst case, would be required to detect a sequence with period 255? In the worst case, if all the timedeltas were unique, then we would have 255 sequences of period one. We would also have 255 sequences of periods 2, 3... 255. If every such sequence had a unique hash, then we would need (255*(1+2+... 255)), or 32,640 (because sum(n)=(n(n+1)/2)), items in the ring buffer, which is slightly less than half of the (2^16) items actually present. The reason for the factor of (1/2) will become clear in the next lesson, but essentially, we need to ensure that at least half of the unique (sequence_hash)es were generated in a truly unpredictable manner. So in other words, we are making the conservative assumption that the first 32,640 hashes are all different but actually predictable due to a period-255 timedelta sequence. In reality, tiny periods seldom exceeding 4, which are much harder to forget (or to regard as unique in the first place) on account of requiring quadratically fewer unique (sequence_hash)es to circumscribe, will dominate.
So conservatively, a unique sequence_hash is worth at least 16 bits, on average, because by definition it occurs less than once in (2^16) such hashes. But we cannot directly use them as protoentropy, let alone entropy! The reason is that, while unique (sequence_hash)es are mostly unpredictable, we can at least say with confidence that popular (sequence_hash)es will not be among them. This constitutes a weak but potentially exploitable bias. What to do? See the next lesson.
Plausible periodic timedelta sequences must not be allowed to enable an attacker to predict any part of the output entropy. For safety's sake, we should endeavor to ignore them entirely. Let me say up front that, while Enranda cannot reject every periodic signal, it does so successfully up to period 255 (with caveats as explained below). Period 255 is utterly implausible in the most quiescent systems, let alone those interesting enough to warrant attack, unless they have been rooted in order to construct such a protracted period via malicious virtualization (a blue pill attack), in which case, the TRNG output is irrelevant anyway. So in practice, Enranda does indeed ignore all periodic signals. But without performing a computationally expensive operation such as treewise string compression, how can we accomplish this?
Enter the "sequence hash". Here's how it works. Suppose we have a period-5 timedelta stream:
{8, 9, 8, 3, 3, 8, 9, 8, 3, 3, 8, 9, 8, 3, 3, 8, 9, 8, 3, 3...}
We then identify, one at a time, each unique sequence in the order of discovery. In the periodic example above, this process would produce the following unique sequences separated by semicolons:
{8; 9; 8, 3; 3; 8, 9; 8, 3, 3; 8, 9, 8; 3, 3; 8, 9, 8, 3; 3...}
We don't actually search backwards, which would be computationally expensive. Instead Enranda implements the sequence hash ("sequence_hash" in the code) as a 16-bit "corkscrew hash" of successive 16-bit timedeltas until said hash is found to be "unique" (meaning that it has not occurred in the past (2^16) such hashes, as ensured by a ring buffer of sequence_hashes at sequence_hash_list_base, and their populations at sequence_hash_count_list_base). Just like its metal counterpart, a corkscrew hash rotates on each iteration in order to make it as sensitive as possible to the order of particular timedeltas, yet symmetric with respect to each iteration in that all bits of all timedeltas influence the corkscrew hash, regardless of order. The simplest corkscrew hashes meeting these criteria are rotate-and-add and rotate-and-xor; we use the former for the sake of maximum collision avoidance. (See enranda_entropy_accrue() for an example.) The reason for the rotation (which is coprime to 16 (bits)), is to achieve maximum dispersion despite most timedeltas being of similar small magnitude.
As soon as a unique sequence_hash is discovered, it's stored to sequence_hash_list_base and its population at sequence_hash_count_list_base is set to one, whereupon sequence_hash itself is reset to zero. But if a previously encountered hash is seen again (as evidenced by its population being nonzero), its population is incremented (such that wrapping back to zero is prohibited). The only way in which population can be decremented is by virtue of a sequence_hash expiring from sequence_hash_list_base, which contains (2^16) items.
Critically, the populations of all (2^16) possible (sequence_hash)es at sequence_hash_count_list_base are initially set to one by enranda_rewind(). This almost gaurantees that the first (2^16) timedelta observations will be ignored. A few such observations pass through this filter, but it doesn't matter because of the way that protoentropy is hashed into entropy, as explained later. And of course, there are hash collisions from time to time, meaning that we fail to detect a small fraction of unique sequences. This is a minor tax on efficiency, which is well worth the speed advantages of keeping the ring buffer and population list small enough to fit in most CPU caches.
So how many hashes, in the worst case, would be required to detect a sequence with period 255? In the worst case, if all the timedeltas were unique, then we would have 255 sequences of period one. We would also have 255 sequences of periods 2, 3... 255. If every such sequence had a unique hash, then we would need (255*(1+2+... 255)), or 32,640 (because sum(n)=(n(n+1)/2)), items in the ring buffer, which is slightly less than half of the (2^16) items actually present. The reason for the factor of (1/2) will become clear in the next lesson, but essentially, we need to ensure that at least half of the unique (sequence_hash)es were generated in a truly unpredictable manner. So in other words, we are making the conservative assumption that the first 32,640 hashes are all different but actually predictable due to a period-255 timedelta sequence. In reality, tiny periods seldom exceeding 4, which are much harder to forget (or to regard as unique in the first place) on account of requiring quadratically fewer unique (sequence_hash)es to circumscribe, will dominate.
So conservatively, a unique sequence_hash is worth at least 16 bits, on average, because by definition it occurs less than once in (2^16) such hashes. But we cannot directly use them as protoentropy, let alone entropy! The reason is that, while unique (sequence_hash)es are mostly unpredictable, we can at least say with confidence that popular (sequence_hash)es will not be among them. This constitutes a weak but potentially exploitable bias. What to do? See the next lesson.
Subscribe to:
Posts (Atom)