1
$\begingroup$

$n$ is a run-time variable chosen each time the user runs the implementation.

One way I can think is to use any block cipher, say AES, as a seeded CSPRNG to randomly shuffle list of numbers $0, 1, \ldots, 2^n-1$. This way I guarantee collision-freeness up to $2^n$ numbers. But this approach is too expensive as it will require me to swap $2^n$ numbers.

Another way I can think of is to use the block cipher to generate ciphertext $c = \mathrm{enc}(\mathrm{0x000}\ldots, \mathrm{key})$, where $\mathrm{len}(c) \ge n$. Then take the 1st $n$ many bits of $c$; let's call it $c_n$. Then do: $c_n \oplus 0, c_n \oplus 1, \ldots, c_n \oplus 2^n-1$. This is efficient, but the problem is that, i think, the sequence is not random. E.g. $c_n \oplus 0$ is generally going to be closer to $c_n \oplus 1$ than, say, $c_n \oplus 100$.

The question: Is any faster approach, where I can use any block cipher for about once only, to generate the next number, such that, as I repeat the process, I get $2^n$ many unique numbers without collisions?

In a sense, I guess I may call it: an online version of shuffling the numbers $0, 1, \ldots, 2^n-1$, without needing to maintain a list in memory that is $2^n$ long.

Ideally, if the perfect online shuffle is found, it must have this distribution (where $i$ is any number in $\{0, 1, \ldots, 2^n-1\}$ and $N_j$ is a random variable that will take the value of a number in that set in the $j^{th}$ call of the ideal on-line shuffler):

$$\begin{split} \Pr(N_0 = i) &= 1/2^n \\ \Pr(N_1 = i) &= 1/(2^n - 1) \\ \Pr(N_2 = i) &= 1/(2^n - 2) \\ \vdots & \\ \Pr(N_{2^n-1} = i) &= 1/(2^n - (2^n-1)) = 1\\ \end{split}$$

$\endgroup$
6
  • 3
    $\begingroup$ Is there some requirement not satisfied by the classical method: enciphering an $n$-bit counter with an $n$-bit block cipher? If so, please state it. $\endgroup$
    – fgrieu
    Sep 22, 2021 at 13:34
  • $\begingroup$ @fgrieu - Not sure (I guess it's just ignorance). $n$ in my case is variable (defined at run time by user). I didn't think of it. Is ChaCha20 one such algorithms, where I can specify arbitrary blocksize at run time and have the effect above? $\endgroup$
    – caveman
    Sep 22, 2021 at 13:48
  • 2
    $\begingroup$ Yeah, I think the key stream generated by counter mode would fit this problem perfectly. If you only have encrypt then it is defined by CTR-mode encryption of all-zero blocks. $\endgroup$
    – Maarten Bodewes
    Sep 22, 2021 at 14:22
  • $\begingroup$ @MaartenBodewes - Interesting. Since ChaCha20 internally has 512 byte blocks (at least how implemented usually, e.g. libsodium's), is it possible to optimise the implementation for $n < 512$? such that the sequence is identical but memory/cpu consumption is less than that of a $512$? $\endgroup$
    – caveman
    Sep 22, 2021 at 14:27
  • 3
    $\begingroup$ Ah, so the missing requirement is $n$ variable at run time, which forces to use techniques of Format reserving Encryption. Please add that in the question, a range for $n$ (overly large $n$ make little sense, since collisions among independent uniformly random values of $n\ge256$ bit are not observable anyway); and perhaps whatever limit there may be to the number of $n$-bit values an adversary may obtain for a given sequence/key. Note: ChaCha20 is not a block cipher, much less of variable block width as needed, but it might be used as a building block for one. $\endgroup$
    – fgrieu
    Sep 22, 2021 at 14:42

1 Answer 1

3
$\begingroup$

Are there on-line ways to use a block cipher to generate unique $n$ bits that guarantee collision-freeness for $2^n$ times?

The obvious way to do this is select a Format Preserving Encryption mode of your block cipher, say, FF1. That is a mode that takes an arbitrary length block (in your case, $n$ bits); you would insert the key and encrypt a counter. With a fixed key (and nonce), the encryption is invertable, and has an output exactly the same length as the input - that gives you precisely what you are asking for.

The only downside I can see is that FF1 may have security issues for truly tiny blocks (in your case, $n \le 6$). Of course, if the user asks for that small of an $n$, you could fall back on the 'permute the values from 0 to $2^n-1$ strategy...)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.