Generating random non-repeating numbers from a small group

Question

I read this Q&A which gave a clever solution: feed an incrementing index into a block key cipher as a way of producing non-repeating random numbers. The problem is the block size of all the good algorithms is often way too big. What if I just want to iterate through all 16-bit numbers, or all N-bit numbers where N is determined by the problem at hand? Nobody in their right mind would make a 16-bit block cipher, but that's what I would need.

One idea I had to iterate pseudo-randomly through all n-bit numbers was to use a binary field. Randomise the modulus polynomial, $Q$, ensuring it's irreducible. Then take a random starting point, $a$, and multiply repeatedly by a random primitive element, $r$, to generate the pseudorandom series.

$n_i = a r^i \pmod Q$

Something tells me this isn't good enough. Predicting the next elements can be interpreted as a discrete logarithm problem if $i$ is the plaintext which must be found from $n_i$. The discrete logarithm is difficult, but when $n_i$ are all given in order, can the problem of finding $r$ and $Q$ from the sequence still be interpreted as the discrete logarithm problem? Does the problem have a name? How hard is it?

If this method of iteration is no good, I had an idea to make it a lot harder: pad the index $i$ with some random bits before encryption, so if the index is a 16 bit number, encrypt it to 20 bits with four random bits. Would that be enough to ensure an unpredictable pattern? What method of iteration would ensure sufficient difficulty in finding a solution? One downside to this modification is that although the sequence generated is non-repeating, it doesn't cover the entire output domain. Is there a way to cover the entire output domain?

Answer 1

If you are going to generate ALL the numbers in the output domain, an attacker's job of guessing the next number becomes easier the more numbers you use, once you pass the halfway point. I would suggest with whatever method you choose, to never exceed $N/2$ values used, where $N$ is the total number of elements that can be generated using that method, $N=2^{16}$ in your example.

I actually see no problem with using a finite field, but you would need to make it difficult for the attacker to guess the values used to generate it, even if the method was known.

My solution would be to use the same finite field inversion method as was used to generate the AES S-box, but in $GF(2^{16})$ with the APA method. It is a highly nonlinear sequence, and there are simply too many combinations of generator values and reduction polynomials to brute force every option like there are in $GF(2^{8})$.

Essentially, you perform an affine transformation on the input, then find the inverse in the field, and then perform the affine transformation again, with an irreducible polynomial chosen at random from the list of possible polynomials. There are specific combinations of affine generators and vectors within each finite field that generate high quality results useful for S-boxes, but you would not be constrained by the same conditions, giving you more flexibility. The mathematical description of the algorithm would be very simple.

The format preserving option easily allows you to build a Feistel cipher of whatever block size you want since your domain size is an even power of 2, in your case 16-bit, by using another block cipher or PRF as the F-function. You can drop in AES, use the 8-bit block half plus a round counter as an input, and truncate the output to 8-bits. This would be very easy to code and very quick to generate numbers, at the expense of a complex description of the final algorithm. You can also generate 128-bit subkeys in CTR mode, then use these as independent AES keys for each round, at the expense of additional computation.

Answer 2

Check out Swap or Not (pdf). Unlike some Feistel-network based solutions, this will provide you with near-ideal security (the adversary would have to query close to the entire space to have non-negligible advantage).

Alternatively, enumerating and shuffling a list of 2^16 16-bit numbers would require only ~128KB of RAM. If you needed to reproduce the ordering, use a key as PRNG seed.

Answer 3

As SEJPM mentions, what you are doing is called "format preserving encryption" and there is a lot of information out there on that, in case you want to go deeper than the answers here give you.

The problem of creating a custom sized cipher is a difficult one, especially if you want to be sure it's crypto secure, but one nice way to approach the problem is to use Feistel Networks.

They work this way:

1. Break your data into a left and right half
2. put the right half of your data through some "round function"
3. Take that result and xor the left half by that value
4. The result of that xor is the right half of the output
5. The left half of the output is the unmodified right half from step 1

A feistel network does $N$ rounds of the above, where $N$ is tunable where in general higher values of $N$ means a slower more secure cipher, and smaller values of $N$ means a faster less secure cipher.

To decrypt something encrypted with a feistel network, it's a similar process but done in reverse, using the same number of rounds.

The other tunable portion of the feistel network is what you use for the round function.

The round function is just a function where you pass in data, and it does some operations, most likely based on the data passed in, to ideally output a cryptographically secure random number.

The round function is able to destructive operations even, which might be counter intuitive, since it's overall a reversible operation. Took me a while to think through how that is possible personally.

If you have lower quality and security needs, your round function could be something like a pseudo random number generator (like those you might find in games), where you use the input of the function as the seed for the PRNG.

If you have higher quality and security needs, you could use a hash function as the round function. Note there are both cryptographic and non cryptographic hash functions, so you'd have to make a call there, again based on your needs.

The only other challenge remaining is that if your input set is not a full power of 2, your are not going to be able to get a perfectly sized cipher.

The way to handle this is to round up to the next power of 2 (you might have to round up to the next power of 4 actually, if you want your left and right side of your data to be the same size), and iterate through that full possible range of values.

You will get some output values which are "out of range" (larger than your input set), and for these you just throw them out.

For some deeper details and some simple working C++ code without external dependencies, check out my blog post on the subject: Fast & Lightweight Random “Shuffle” Functionality – FIXED!