3 ms·

The shuffle question ties in with the overlap question. Let's stick with the AES in counter mode example. AES is a block cipher, or in other words a keyed permu

by pbsd 11y ago

The shuffle question ties in with the overlap question. Let's stick with the AES in counter mode example. AES is a block cipher, or in other words a keyed permutation. What this means is that each key (resp. seed) determines a distinct permutation that we use to generate the blocks AES_K(0), AES_K(1), etc. In effect, each seed will result in an entirely distinct and independent 2^128-block sequence, instead of simply the same sequence starting at a different place, which is usually the case for non-cryptographic generators. So 2^128 possible keys (or 2^256, if you go AES-256) times 2^128 output blocks per key is probably enough to cover all possible card shuffles. I do believe that. RC4 is a good example, actually; the unexpected properties that make RC4 be considered completely broken for cryptography are considered irrelevant for simulations (I won't swear by this, but I'll bet that RC4 passes all of TestU01's tests). The standards are just so much higher for cryptographic primitives. I'm sure unsexy generators can be suitable to this or that application. But due to the ad hoc nature of the statistical tests used, you can't be sure that your generator is not oddly correlated with a concrete application. I've written a comment a few days ago---on a thread very similar to this one---about a real-world case of this happening [1]. [1] https://news.ycombinator.com/item?id=10549024 https://news.ycombinator.com/item?id=10549024

mmalone 11y ago
Ok, I get the seed/state space vs. cycle length bit. So it can theoretically generate all of the permutations of a shuffle if you re-key/re-seed periodically. But you can't guarantee that it actually will, right? It is possible that, for all 2^128 keys, and in all 2^128 cycles there are some shuffles that AES will never generate (in other words, some sequences of 52 numbers that will never be generated) so you effectively have a 0% chance of hitting them. From a cryptanalysis standpoint I think that's consistent -- the probability of generating any particular single shuffle is astronomically low, so the difference between the actual probability and 0% is probably outside the realm of what's computationally feasible. But with something like MT19937 I can show that its at least possible for every outcome to have a non-zero probability. Perhaps this is just interesting academically, but maybe not if you're actually playing a card game for instance?
- nialo 11y ago
  I think you have to hit every permutation, at least for AES, because AES is reversible. In particular, if there were some 0 <= y < 2^128 such that AES_k(x) != y for all 0 <= x < 2^128, then there must also be some z such that two different values x1 and x2 encrypt to the same value, which can't happen if AES is reversible.
  - mmalone 11y ago
    Sure but I don't immediately see how that equates to a proof of its ability to produce every combination of, say, 52 consecutive numbers... Just that it will produce every possible individual number. In PRNG-parlance it shows 1-dimensional equidistribution but not 52-dimensional (or generally (k, w)-dimensional) equidistribution. Or is there another pigeonhole step I'm missing?
- pbsd 11y ago
  No, that cannot be guaranteed. Equidistribution in 52 dimensions requires necessarily a minimum state size of 52 log_2(52) bits, which we don't even have. Even if we did, it could not be guaranteed anyway. You have already covered the distinction between guaranteed equidistribution and not, so I don't think there is much to add there. I do think the concern is mostly academic, since the difference between a subsequence that doesn't exist and one that will never be reached before the universe collapses is irrelevant to the user. I will note that Richard Brent, someone who is much better qualified than I to discuss this, has argued against the usefulness of equidistribution: http://maths-people.anu.edu.au/~brent/pub/pub240.html http://maths-people.anu.edu.au/~brent/pub/pub240.html

by pbsd 11y ago

mmalone 11y ago

Ok, I get the seed/state space vs. cycle length bit. So it can theoretically generate all of the permutations of a shuffle if you re-key/re-seed periodically. But you can't guarantee that it actually will, right? It is possible that, for all 2^128 keys, and in all 2^128 cycles there are some shuffles that AES will never generate (in other words, some sequences of 52 numbers that will never be generated) so you effectively have a 0% chance of hitting them. From a cryptanalysis standpoint I think that's consistent -- the probability of generating any particular single shuffle is astronomically low, so the difference between the actual probability and 0% is probably outside the realm of what's computationally feasible. But with something like MT19937 I can show that its at least possible for every outcome to have a non-zero probability. Perhaps this is just interesting academically, but maybe not if you're actually playing a card game for instance?

nialo 11y ago
I think you have to hit every permutation, at least for AES, because AES is reversible. In particular, if there were some 0 <= y < 2^128 such that AES_k(x) != y for all 0 <= x < 2^128, then there must also be some z such that two different values x1 and x2 encrypt to the same value, which can't happen if AES is reversible.
- mmalone 11y ago
  Sure but I don't immediately see how that equates to a proof of its ability to produce every combination of, say, 52 consecutive numbers... Just that it will produce every possible individual number. In PRNG-parlance it shows 1-dimensional equidistribution but not 52-dimensional (or generally (k, w)-dimensional) equidistribution. Or is there another pigeonhole step I'm missing?
pbsd 11y ago
No, that cannot be guaranteed. Equidistribution in 52 dimensions requires necessarily a minimum state size of 52 log_2(52) bits, which we don't even have. Even if we did, it could not be guaranteed anyway. You have already covered the distinction between guaranteed equidistribution and not, so I don't think there is much to add there. I do think the concern is mostly academic, since the difference between a subsequence that doesn't exist and one that will never be reached before the universe collapses is irrelevant to the user. I will note that Richard Brent, someone who is much better qualified than I to discuss this, has argued against the usefulness of equidistribution: http://maths-people.anu.edu.au/~brent/pub/pub240.html http://maths-people.anu.edu.au/~brent/pub/pub240.html