If the code to shuffle an array is known, is it possible for the randomized shuffle to stay secure?

Question

I recently was looking at Poker shuffles that were hacked and made to be guessable within a reasonable degree and this was because of the weakness of the shuffles. Is it possible to make a shuffle that is cryopgraphically secure, even if the code for the client and server is available?

Answer 1

Yes. In fact, most of these broken shuffling mechanisms are actually broken because they're using "secret" shuffling algorithms.

Generally speaking, a shuffling mechanism has two components:

1. Shuffling algorithm.
2. Pseudo-random number generator (PRNG).

While the shuffling algorithm can have a certain bias of its own, the whole shuffling mechanism cannot have any less bias than the PRNG itself has. In other words, a shuffling algorithm cannot be any more random than its PRNG. Let's look at one of most efficient shuffling algorithms out there, the Fisher–Yates shuffle.

The source code (or, rather, the pseudocode) of the modern Fisher-Yates shuffle has been publicly available since 1964, with implementations in tens of languages.

To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

However, it still remains one of the most widely used algorithms for this purpose.

If you look closely, the algorithm depends on random integer. This is where the PRNG comes into play. If your PRNG is unbiased and your implementation is correct, then your shuffles should be unbiased as well.

Plenty of good PRNGs which are well-vetted, time-tested, and proven to be unbiased are available. Since a PRNG is deterministic (for the same initial state, it always returns the same value) the security/randomness of the whole shuffling mechanism relies on the randomness of the PRNG's initial state, its seed. This reliance on the quality of the seed is an extension of Kerckhoffs' Principle, since without knowing the seed knowledge of the algorithm tells you nothing. Luckily, most good PRNGs utilize good "randomness sources" provided by the operating system, such as /dev/urandom.

Answer 2

To complete @Adnan's answer: there is code, and there is data. "Shuffling" is applying a permutation on a given space, which is very akin to encryption. So your question can be reformulated as: is it possible to encrypt data securely, when the attacker knows the code ? And the answer is: yes, as long as the attacker does not know the key. The key concentrates the secret. We separated the key from the code precisely so that the code needs not be secret, and we do that because it is very hard to keep code secret.

The Fisher-Yates algorithm (also known, improperly, as the "Knuth shuffle") can be viewed as an encryption algorithm, whose key is the sequence of random values obtained from the random source. The code is well known, but the attacker is assumed not to know these values. As long as the returned random integers are obtained from a cryptographically strong source and unbiased, this is "perfect" (every permutation among the 52! possible permutations of a space of size 52 can be selected with uniform probability). Generating unbiased integers in a given range, from a source which produces bytes, is subject to some subtleties, which can be overcome (see what I wrote on page 3 of this article).

The general case (securely permuting a space of some arbitrary size, not necessarily a power of 2) is covered by Format Preserving Encryption. When you want the complete codebook, i.e. you want the full permutation (that's the case of a shuffle, where you need to know where each card went), the Fisher-Yates shuffle is about as good as you can get. Other solutions for FPE allow partial evaluation (i.e. without having an array containing the full shuffle) but may induce biases (in particular, Feistel schemes are always even permutations). There is little point in trying to do anything else than Fisher-Yates for cards.

Answer 3

A cryptographically secure pseudo-random number generator, with suitable sources of entropy, should meet your requirements quite nicely. A CSPRNG must behave in the same fashion, because being able to predict future values or determine previous values would cause many encryption systems to become vulnerable. Being able to predict random numbers was at the heart of the infamous Netscape bug.

Here is a list: http://en.wikipedia.org/wiki/Category:Cryptographically_secure_pseudorandom_number_generators