Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

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.

share|improve this answer
    
Thank you - I was wondering why these were broken... yet we use secure numbers in lots of important parts of encryption and deem them safe. –  Vaughan Hilts Oct 25 '13 at 4:07
    
You may wish to mention Kerckhoffs' Principle explicitly in relation to your final paragraph. –  Jonathan Garber Oct 25 '13 at 13:54
    
Sorry, @JonathanGarber . I rejected your edit by mistake. Could you please re-suggest it again? I've already made some of the changes but I'd like to accept your edit. If possible, you may include the part about Kerckhoffs' Principle as you see fit. –  Adnan Oct 25 '13 at 14:10
    
Done. The reference to Kerckhoff isn't important in itself, but more to influence drive-by visitors. Given how vitally important the principle is in modern security, it can't hurt to have it prominently linked to everywhere. –  Jonathan Garber Oct 25 '13 at 14:18
    
/dev/urandom isn't the best choice if you want guaranteed randomness since if there's not sufficient entropy in the pool, urandom will return less cryptographically secure random numbers. /dev/random is safer, though it means that your process might block while awaiting more entropy. –  Johnny Oct 26 '13 at 7:01

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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