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 [EMAIL PROTECTED]
