>>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]
