Only 86 Million Ways to Shuffle: What Game RNG Certification Checks

In 1999 a group of engineers at Reliable Software Technologies took a close look at the shuffling code behind PlanetPoker. The software came from ASF Software, which had posted its shuffling algorithm on the site to convince players the deal was fair. A deck of 52 cards has 52! possible orders, roughly 2 to the power of 226. Reading the code, they found the number that could actually come up was far smaller.

The shuffle used the random number generator that shipped with Borland’s compilers, which takes a 32-bit seed, so at most about four billion decks. The seed came from the number of milliseconds since midnight, which leaves 86,400,000 possibilities a day. Once they had synchronised their clock with the server’s, that dropped to around 200,000. During a hand, knowing their own two hole cards and the three cards of the flop was enough for their program to find the one matching seed, after which every deck in every later game could be computed in under a second. After they contacted ASF, the company changed its algorithm.

The other example people often reach for is from 2008. A patch to the OpenSSL package in Debian and Ubuntu left the random number generator with the process ID as its only real source of entropy. The maximum PID on most systems at the time was 32,768, so for a given architecture and key type that was about how many keys could ever be generated. The bug sat in Debian unstable from September 2006, reached the stable release in April 2007, and was announced on 13 May 2008.

In both cases the damage came from the seed, the state, and the few lines that connect random numbers to the business logic, which is also where game RNG certification spends most of its attention. The sections below follow the relevant clauses of GLI-11 v3.0, the gaming device standard from the testing lab GLI. The examples were run on Python 3.13.15.

1. Seed space: five cards are enough

Here is a simplified version of the 1999 attack. The deck is shuffled with milliseconds since midnight as the seed, the attacker has seen the first five cards, and their clock is within two seconds of the server’s:

import random, time

def shuffle_with_seed(seed):
    deck = list(range(52))
    random.Random(seed).shuffle(deck)
    return deck

server_seed = 45_296_789          # 12:34:56.789
deck = shuffle_with_seed(server_seed)
seen = deck[:5]                   # two hole cards + the three-card flop
guess_clock = 45_296_000          # attacker's clock, within ±2 seconds

t0 = time.perf_counter()
hits = [s for s in range(guess_clock - 2000, guess_clock + 2001)
        if shuffle_with_seed(s)[:5] == seen]
dt = time.perf_counter() - t0
print("hits:", hits, f"time: {dt*1000:.0f} ms")
print("full deck recovered:", shuffle_with_seed(hits[0]) == deck)

hits: [45296789] time: 81 ms
full deck recovered: True

Out of 4,001 candidate seeds, the right one turns up in 81 milliseconds, and with it the other 47 cards. The shuffle itself is fine here, since Python’s shuffle is a correct Fisher-Yates. The problem is entirely the seed: it has too few possible values, and it is tied to something an outsider can guess, the time.

GLI-11 covers this in 3.3.2: the initial state of a software RNG must be determined by “an uncontrolled and unpredictable event”. Time, PIDs and incrementing counters all fail that test. In practice the answer is to ask the operating system, through getrandom on Linux, crypto/rand in Go or secrets in Python, which exist for exactly this purpose.

2. Passing statistical tests doesn’t make it unpredictable

GLI-11 3.2.2 requires a set of statistical tests, listing chi-square, overlaps, coupon collector, runs, interplay correlation, serial correlation and duplicates among others, evaluated collectively at a 99% confidence level.

These tests look at distribution, whether each value turns up as often as it should and whether outputs are correlated with each other. They don’t ask whether someone who has seen part of the output can predict the next value. Python’s random module, used above, is built on the Mersenne Twister, with a period of 2 to the power of 19937 minus 1 and good statistical properties, and Python’s own documentation says it should not be used for security purposes and points to secrets instead. Its internal state can be reconstructed from enough consecutive outputs (to be verified: the figure usually quoted is 624 32-bit outputs).

That is why the standard asks for unpredictability on top of the statistics. Clause 3.2.6 says that unless a “cryptographic RNG” is used, the RNG’s state must change between every game, for example through background cycling (continuously discarding values so that an outsider can’t line up with the sequence) or by injecting fresh entropy. Clause 3.6 requires a cryptographic RNG to resist three kinds of attack: direct cryptanalysis, known input attacks, and state compromise extension, meaning that if the internal state is exposed at some point, later output still can’t be calculated from it. That in turn needs periodic entropy from outside.

A CSPRNG is designed to meet those goals. A common construction puts a stream cipher or a hash function at the core, and the Hash_DRBG, HMAC_DRBG and CTR_DRBG designs in NIST SP 800-90A all belong to that family. For certification, which one you pick matters less than being able to show that it is one of them, where the seed comes from, and how often it is reseeded.

3. Good random numbers, skewed on the way to the cards

An RNG produces bits. A game wants a number between 1 and 52, or the stop position of a reel, and the step in between is called scaling or mapping. GLI-11 3.2.3 is blunt about it: all scaling, mapping and shuffling algorithms must be entirely free of bias, as verified by source code review.

The most common bias comes from taking a remainder. Take a random byte, 0 to 255, modulo 52:

from collections import Counter
counts = Counter(b % 52 for b in range(256))
print(sorted(set(counts.values())), 5/256, 4/256)

[4, 5] 0.01953125 0.015625

256 isn’t a multiple of 52, so each of the values 0 to 47 is reached by five different bytes and each of 48 to 51 by only four. The last four cards come up about 20% less often than the rest. With a 32-bit random number the bias shrinks until statistical tests will struggle to see it, but it is still there, the standard asks for none at all, and anyone reviewing the source will spot it straight away.

The fix is rejection sampling: if the value falls in the leftover range that doesn’t divide evenly, throw it away and draw again. Most standard libraries already do this, for example crypto/rand.Int in Go and secrets.randbelow in Python. A hand-written rand() % n is where the trouble usually starts.

Shuffling has the same problem. In Fisher-Yates, card i is swapped only with a card from the part of the deck not yet processed. A common mistake is to swap every card with any card in the whole deck. With three cards every case can be listed:

import itertools
from collections import Counter

def naive(n):
    res = Counter()
    for choices in itertools.product(range(n), repeat=n):
        a = list(range(n))
        for i, j in enumerate(choices):
            a[i], a[j] = a[j], a[i]
        res[tuple(a)] += 1
    return res

print(dict(sorted(naive(3).items())))

{(0, 1, 2): 4, (0, 2, 1): 5, (1, 0, 2): 5, (1, 2, 0): 5, (2, 0, 1): 4, (2, 1, 0): 4}

There are 27 equally likely sequences of choices and 6 orderings, 27 doesn’t divide by 6, so three of the orderings are bound to come up more often. The PlanetPoker code had an off-by-one on top of that: the swap target was only ever picked from cards 1 to 51, so position 52 could never be chosen. Scaled down to four cards:

never-last n=4, distinct perms: 18 of 24; who ends last: {0: 27, 1: 27, 2: 27}

Only 18 of the 24 orderings ever appear, and the card that starts in last place never ends up there. With 52 cards that is exactly what the 1999 report described, the 52nd card never landing in the 52nd position.

4. State and entropy: Debian’s one line

The Debian problem started when the package maintainer wanted to silence Valgrind warnings about the use of uninitialised memory and commented out an MD_Update call in RAND_add in md_rand.c. Besides mixing in uninitialised data, that line was also what added the real entropy. With it gone, only the PID was left. The algorithm hadn’t changed at all, yet the keys could now be enumerated.

In a 2024 write-up, Ryan Finnie recalls seeing identical SSH host keys turning up across different virtual machines months before the official announcement, without realising why at the time. Game systems have the same failure mode: if machines are cloned from one image and the RNG state is cloned along with it, two machines will produce identical results.

The checks that follow from this are straightforward. Is the seed fetched from the operating system again on every start? Does a long-running RNG get fresh entropy at regular intervals, as GLI-11 3.6 requires? If one RNG instance is shared between threads, is there a race that could hand two requests the same stretch of output? And do logs, error messages or debug endpoints ever leak the internal state or the seed?

5. The RNG is fine, the published odds are wrong

Everything so far has been about the random numbers themselves. The probability dispute that drew the most attention in Taiwan in recent years went wrong somewhere else.

In the mobile game Lineage M, an item known to players as “purple cloth” (紫布) is obtained by crafting, and each attempt has a set chance of success. According to Taiwan’s Fair Trade Commission, the Korean version used 201 materials per attempt with a 10% success rate, while the Taiwanese version used 99 materials per attempt with a 5% rate. At a player meeting in December 2019, the local publisher Gamania said the Taiwanese odds were exactly the same as the Korean ones, without explaining the difference. In September 2021 the streamer Ding Te (丁特) crafted the item 471 times on stream and succeeded about 2.3% of the time, a long way from the 10% players had assumed, and the dispute grew from there. Reports differ on how much money he spent, so no figure is given here.

On 9 June 2022 the Fair Trade Commission ruled that the statement at the player meeting was a false or misleading representation, and fined Gamania NT$2 million under Article 21 of the Fair Trade Act. It was the first time the commission had penalised a game company for misrepresenting probabilities. Gamania challenged the decision in court. The Taipei High Administrative Court dismissed the case in 2024, and the Supreme Administrative Court dismissed the appeal on 12 June 2025, making the ruling final. Around the same time Taiwan’s Ministry of Economic Affairs amended the mandatory terms for online game service contracts, so that from 1 January 2023 the odds for chance-based items have to be published on the official website, the login page and the purchase page.

From an engineering point of view, the RNG in this story may have had nothing wrong with it at all. It could pass every statistical test and every seed and mapping check above, because the error lay between the configured value and the number told to players, and in two regional versions keeping separate configurations. RNG certification checks how random numbers are produced and mapped to outcomes. It won’t confirm that the percentage on your announcement page is the same number your server actually loads.

The check an outsider can run is not hard. Assume about 11 successes in 471 attempts, which is what 2.3% works out to (an estimate, not a reported figure), and use the binomial distribution to see how likely so few successes would be under different true rates:

from math import comb

def cdf(k, n, p):
    return sum(comb(n, i) * p**i * (1 - p)**(n - i) for i in range(k + 1))

n, k = 471, 11
for p in (0.10, 0.05):
    print(f"p={p:.2f}  expected={n*p:5.1f}  P(X<={k})={cdf(k, n, p):.2e}")

p=0.10  expected= 47.1  P(X<=11)=6.38e-11
p=0.05  expected= 23.6  P(X<=11)=2.71e-03

At a true rate of 10% you would expect about 47 successes, and 11 or fewer has a probability on the order of one in ten billion, which all but rules it out. At 5% the probability is about 0.3%, which is low but not impossible. An outside estimate like this has limits worth keeping in mind. A stream is one person’s sample, and the sessions that get talked about tend to be the unlucky ones. When the player chose to stop also affects the result. And from outside you can’t see whether each attempt is independent or whether there are hidden conditions. It is good for raising a question, not for settling one on its own.

The operator holds the full records, can do far more, and is the one who ought to:

Generate the published odds straight from the configuration the server actually uses, and don’t maintain a separate copy by hand. As long as either side is edited manually, the two will drift apart sooner or later.
Keep configurations separate per region and version, log every change, and announce changes before they take effect.
Count actual successes for every chance-based item in production and use the same binomial distribution to set control limits. At 5% over 471 attempts, for instance, the expectation is 23.6 with a standard deviation of about 4.7. Alert when the observed count falls outside the limits, so you find out before your players do.
Where there are pity systems, staged odds or conditional triggers, the announcement should translate them into the probability players actually face. Publishing the figure for only one stage is about as useful as publishing nothing.

6. Questions to ask yourself before submission

Turned around, the sections above give a checklist to run through before sending anything to a lab:

Where does the seed come from, and can you show it is an uncontrolled and unpredictable event?
Is the generator a CSPRNG? If not, how does its state change between games, through background cycling or fresh entropy?
For every mapping, scaling and shuffling step between RNG output and game result, is there a remainder, a floating-point multiplication or a home-made shuffle, and can you explain line by line why it has no bias?
Under what circumstances could the internal state be seen or copied: images, snapshots, logs, debug endpoints?
Can you export enough raw output for the lab’s statistical tests, and does the export run through the same code as production?
Do the published odds come from the same source as the configuration the server loads, and has each regional version been checked separately?

Submission formats and required documents vary between labs and jurisdictions, so go by whatever version is current when you submit.

Notes

The seed, the state and the mapping fail more often than the algorithm itself, as both the 1999 poker case and the 2008 Debian bug show.
The seed space has to be large and tied to nothing an outsider can guess. Time, PIDs and counters won’t do, so take it from the operating system.
Statistical tests check distribution, not predictability. GLI-11 also requires the state to change between games, or a cryptographic RNG that withstands state compromise.
rand() % n is biased whenever n doesn’t divide the range evenly. Use rejection sampling or the ready-made functions in the standard library.
Shuffle with a correct Fisher-Yates, swapping only within the unprocessed part of the deck. Three cards are enough to enumerate the bias in the wrong version.
Cloned machines and snapshots copy the RNG state too, so fetch a new seed on start-up.
A certified RNG doesn’t mean the published odds are right. Generate the announcement from the real configuration, and monitor actual success rates in production with the binomial distribution.