Nico, thanks for the detailed answer. Tell me if I'm off my rocker here...
So the mapping of {key, counter} to {mask} is one-to-one. In that case,
yes, it's as good as it gets, with respect to limit cycles.
Secondarily, as you pointed out, it then falls back to the failure rate of
counter incrementation (not to mention other failures), but those sorts of
issues would threaten any algo.
So finally, it comes down to the probability of accidentally reusing the
same counter with a given key. As you said, this could occur as the result
of forgetting the counter. The highest frequency of such an event would
likely result from deliberate attack, as opposed to random failure. With a
128-bit counter, this would happen once in O(2^64), based on the birthday
attack math. (This assumes that we always choose a true random initial
counter value from a "hard" generator. If, instead, it's based on some
saved previous state, then the probability would seem to be much higher.)
2^64 is probably close to the number of transistors in the world at the
moment, so for now, such a random initial counter value is strong. (Side
note: the idea of saving and later retrieving an incrementing counter
sounds like security suicide, if you think of virtual machines and the
occasional timestamp retrogression that you mentioned. So we're forced into
a birthday attack regime with random starting counter values, I think. In
other words, IV size and randomness quality is paramount.)
But yes, zero reuse is fantastic! The only negative side effect of
one-to-one mapping is that the LMICBR test would actually fail, because it
would not show _enough_ repetition. (Search "reflexive density constant".)
The implication is that a CTR ciphertext of sufficient length (O(2^64)
blocks, at most) is distinct from noise (i.e. not deniable), assuming that
the plaintext has low entropy. But for now I don't think that's a
meaningful problem.
Which leaves the second question: does anybody know what entropy analysis
has been done on the respective masks of {key, counter} and the mask of
{key, counter+1} (or {key, counter xor 1} or other would-be-exploitable
mask pairs)? For instance, their xor (and their difference) would be
expected to exhibit a "coin flip" distribution of the number of bit flips,
0s, and 1s.
On Thu, Jun 13, 2013 at 3:42 AM, Nico Williams <[email protected]>
wrote:
>
> On Wed, Jun 12, 2013 at 9:31 PM, Russell Leidich <[email protected]> wrote:
> > But what's the probability of 2 xor masks colliding? Is this just
assumed to
> > [...]
>
> For any one AES-128 key the probability of mask reuse is exactly the
> same as the probability of counter reuse.
>
> The bits of the counter are there to "count" things: nominally, at
> least, to count the blocks of plaintext encrypted thus far.
>
> For a session key (used only for a given stream of octets or
> datagrams) we only need to count blocks of plaintext encrypted thus
> far. In this case 128 bits is overkill: one cannot possibly use them
> all. The key here is that a session implies *state*, specifically
> here: a counter (and atomic updates of it). If we lose track of the
> counter we lose the session.
>
> In the case of session keys, then, the probability of {key, counter}
> reuse is actually no more than the probability of a cosmic ray
> flipping a bit of a counter. Ignoring such faults the probability
> then is zero. Zero is excellent.
>
> For a long-lived non-session key it's trickier: there may be no robust
> and reliable way to keep a counter. Worse, we may need to distribute
> the use of the key (and counter). In this case it will suffice to
> make it hard enough for the attacker to notice {key, counter} reuse,
> but IMO it's safer to derive sub-keys as I described. But assuming
> one did not design the system that way the probability will depend on
> the probability of a fault that causes {key, counter} reuse, and here
> we include unsafe system shutdowns, clocks jumping backwards (e.g., by
> ntpd), and misconfigurations. To estimate this probability we'd need
> to know the probability of those faults, to start.
>
> I'm ecstatic with a {key, counter} reuse probability of zero. I get
> concerned if that probability depends on the probability of
> potentially (possibly triggered by an attacker trying to cause {key,
> counter} reuse) frequent faults (e.g., KDC crash).
>
> Nico
> --
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
