cryptographic ergodic sequence generators?

[John S. Denker]

Perry E. Metzger wrote:

 >>I've noted to others on this before that for an application like
 >>the IP fragmentation id, it might be even better if no repeats
 >>occurred in any block of 2^31 (n being 32) but the sequence did not
 >>repeat itself (or at least could be harmlessly reseeded at very very
 >>long intervals).

I assume the point of the reseeding is to make
the ID-values more unpredictable.

On 09/07/2003 11:18 AM, David Wagner wrote:
 >
 > Let E_k(.) be a secure block cipher on 31 bits with key k.
 > Pick an unending sequence of keys k0, k1, k2, ... for E.
 >
 > Then your desired sequence can be constructed by
 >   E_k0(0), E_k0(1), E_k0(2), ..., E_k0(2^31 - 1),
 >   2^31 + E_k1(0), 2^31 + E_k1(1), ..., 2^31 + E_k1(2^31 - 1),
 >   E_k2(0), E_k2(1), E_k2(2), ..., E_k2(2^31 - 1),
 >   2^31 + E_k3(0), 2^31 + E_k3(1), ..., 2^31 + E_k3(2^31 - 1),

Again if we assume the point is to make the values
unpredictable (not just ergodic), then there is
room for improvement.

To see what I mean, divide the values into generations
G=0,1,2,3... where each row in the tableau above is
one generation.

The problem is that at the end of each generation,
the values become highly predictable, à la Blackjack.

David's proposal can be improved by the method used
by Blackjack dealers:  shuffle early.  In each
generation, let the argument of E_kG(.) max out at
some fraction (f) of 2^(n-1).  A limit of f=1/2 is
the obvious choice, although other f values e.g. f=2/3
work nicely too.  The domain and range of E_kG(.) are
still unrestricted (n-1)-bit numbers.

This gives us the following properties
  -- Guaranteed no repeats within the last f*2^(n-1) IDs.
  -- Probably no repeats in an even longer time.
  -- Even if the opponent is a hard-working Blackjack
     player, he has only one chance in (1-f)*2^(n-1)
     of guessing the next value.  To put this number in
     context, note that the opposition has one chance
     in 2^(n-1) of guessing the next value without any
     work at all, just by random guessing.

Setting f too near zero degrades the no-repeat guarantee.
Setting f too near unity leads to the Blackjack problem.
Setting f somewhere in the middle should be just fine.

=================

Discussion of conceivable refinements:

A proposal that keeps coming up is to take the values
generated above and run them through an additional
encryption stage, with a key that is randomly chosen
at start-up time (then held fixed for all generations).
The domain and range of this post-processing stage
are n-bit numbers.

This makes the output seem more elegant, in that we
have unpredictability spread over the whole n-bit word,
rather than having n-1 hard-to-predict bits plus one
almost-constant bit.

Define the phase to be P := (G mod 2).

The opponent will have to collect roughly 2^n data
points before being able to figure out which values
belong to which phase, so initially his guess rate
will be closer to one in 2^n, which is a twofold
improvement ... temporarily.

This temporary improvement is not permanent, if we
allow the opponent to have on the order of 2^n
memory.  He will in the long run learn which values
belong to which phase.  I see no way to prevent this.

So as far as I can tell, the proposed post-processing
is more in the nature of a temporary annoyance to the
opposition, and should not be considered industrial-strength
cryptography.

Perhaps more to the point, if we are going to allow
the opposition to have 2^n memory, it would be only
fair to allow the good guys to have 2^n memory.  In
that case, all the schemes discussed above pale in
comparison to something I suggested previously, namely
generating an ID absolutely randomly, but using a
look-up table to check if it has been used recently,
in which case we veto it and generate another.  If
you can afford the look-up table, these randomly
generated IDs have the maximum possible unpredictability.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com