Shufflix: Design Summary
In 1990 Alesia Software developed software for MS-DOS-based PCs for
bridge deals for use in serious bridge tournaments run by the Danish NCBO,
Bridgeforbund (DBF). This effort was triggered by a series of errors
in 1989, where a set of deals was inadvertently reused. This type
mishap and the measures taken to prevent
them are discussed further in the Shufflix FAQ.
resulting software package is KG, which has been in use for
all high-level tournaments run by DBF since September 1990.
In the late 1990s machines for duplicating bridge boards had become
affordable for individual districts under DBF or even for individual
This resulted in a demand for a version of the bridge dealing software
that could be distributed freely without jeopardizing the quality of the
boards dealt. This version of KG was released in 1998 as freeware.
At this time, a standard for interchanging information relating to
bridge, including deals, was evolving. This effort, driven by Tis Veugen,
resulted in the Portable
Notation, which was also supported in the 1998 version of KG.
During 1998 and 1999, prompted by problems similar to those experienced
in Denmark in 1989, Hans van
took the initiative to develop dealing software for the Dutch Bridge
and the WBF with the intention of achieving a quality that can be used
worldwide for serious as well as everyday tournaments. This effort has
resulted in Bigdeal, which
a state of the art dealing program that anyone may download and run on
their own computer. This initiative touched off several discussions
on the Internet about the requirements that such software must meet and
the possible designs that can meet these requirements.
As a spin-off of these discussions, Alesia Software has developed Shufflix,
which is a WWW-based state-of-the-art dealing program that provides deals
for a session of bridge in a matter of seconds using only a WWW browser.
The basic requirements set out for the 1990 version of KG were the
In the 1998 version of KG, the requirements were revised to include the
Statistics (strong). The deals generated must be statistically
from deals chosen at random. [This property is known as unbiased
in the cryptographic literature about random number generators]
Non-repeating (strong). A sequence of boards generated for one
must not be observably related to the boards generated for some other
[This property is another requirement from the cryptographic literature
concerning random number generators]
Clerically robust (medium). The software must support clerical
that help prevent inadvertent use of generated deals in an event that
were not intended for.
Unpredictable (medium). No one, not even the programmer, possibly
assisted by ample computer power, should be able to predict the deals of
a tournament before the event. [This property also
as a requirement from the cryptographic literature concerning random
No discernable pattern (weak). It must not be possible for an
but knowledgeable player to predict the rest of the deals to be played
during a session, given the deals already played.
Users (weak): Few and trusted. Only a small number of known users
will have versions of the software.
Auditable (medium). It must be possible to ascertain after the
that the deals were not intentionally modified after dealing.
In Shufflix (1999-2001), the requirements have been revised to include
No discernable pattern (medium). It must not be possible for
knowledgeable players with access to covert computer resources of large
but reasonably limited capacity to predict the rest of the deals to be
played during a session, given the deals already played.
Users (medium): Potentially Hostile vs. Protected. A large
of general users must be supported without threatening the integrity of
selected, specially protected users.
As can be seen, the major developments from KG to Shufflix are primarily
concerned with issues that are treated in the cryptographical literature.
Unpredictable (strong). It must be infeasible, even when backed
by immense, but realistic computing resources, to categorically rule out
that any given sequence of boards will be generated for a particular
No discernable pattern (strong). It must not be possible for
knowledgeable players, even when backed by immense, but realistic
resources, to predict the rest of the deals to be played during a
given the deals already played.
Users (strong): Potentially Hostile Mutually Protected. A large
community of potentially hostile users must be protected against each
use of the software.
Auditable (strong). It must be possible to ascertain after the
that the deals were not intentionally modified during and after dealing.
Oh, by the way, there is also Hackix. This is a 9-line Perl program
that shows what a programmer who is only worried about the statistics
might develop. The requirements analysis of Hackix
is another way of getting to grips with what these requirements are all
Overall Design of Shufflix
The input to Shufflix is the following:
Sequence of deals
Description of the Deals
A Tournament Description, which gives the name and date of the
for which the deals are intended and the number of boards to be
A file of unpredictable information, called the entropy, using a
term from information theory.
Getting together a suitable entropy file for the deals is worth a special
short discussion. Note that the impact of the entropy file is concentrated
on the requirement that the deals should be Unpredictable and have
discernable pattern. Shufflix is designed in such a way that the
for good Statistical behavior and Non-repeating performance
are fulfilled anyway.
For reasonably serious tournaments, it can be desirable to demonstrate
that dishonest participants backed with immense computer power cannot
the deals, but where the operator of the dealing software is trusted,
care is needed to acquire entropy file. Shufflix accomplishes this
by extracting 128 unpredictable bits from the device urandom
on the Linux operating system, which constitues Shufflix's platform.
The output of Shufflix is a sequence of deals accompanied by all the
information for unique identification of the deals and the event for which
they are to be used.
Step 1: Generate the Run Seed
Step 1 uses a cryptographically
one-way hash function to transform the entropy into a sequence
of bits, which is called the run seed. The Shufflix prototype uses MD5,
which creates a run seed of 128 bits.
Miscellanous user data
The computer entropy consists of these contributions:
128 bits read from the Linux device /dev/urandom on the web server
This contribution is unpredictable at a cryptographically strong level;
it is based on timings of interrupts within the kernel. The use of
was suggested by Alan
Jaffray. This contribution is enough on its own to ensure that the
run seed is cryptographically unpredictable. The contribution from the
user makes it more unpredictable, but only slightly so.
All user-specific information available to the server, including the
clock time, the user's IP address, and the process number of the server
process. This information does add a little to the overall entropy of
run seed, but a significant effect is to ensure that even if the entropy
is reused in another run (which would be an error), the runseed will be
based on different input to the hash function, and therefore be
Step 2: Generate a Sequence of Pseudo-Random Bytes
Step 2 uses a one-way hash function to create a sequence of random byte
values (0..255). The values are for each board to be dealt. Shufflix
for this step too.
Long sequence of pseudo-random bytes
The overall approach, which is recommended in Carl Ellison's paper on
Random Numbers is to concatenate the unpredictable runseed with a
counter and process that through the hash function. This yields 16 bytes
for each call.
Step 3: Generate Boards
Sequence of Random Bytes
Description of Deals
Step 3 shuffles the cards once for each board, using the random bytes
from step 2. The algorithm selects a card at random and moves it
to the top of a result pile, repeating until all 52 cards have been
To do this, a random byte is converted to random number of appropriate
size K by taking its remainder modulo K. To avoid bias, the entire
byte is discarded if it is larger than the largest multiple of K less than
or equal to 256.
The resulting deals are described using 52 characters for each. Here
is an example of such a file.
Each line after the Tournament Description describes a board. The number
0,1,2, and 3 signify North, East, West, and South, respectively. The first
character shows which hand is to get the A,
the next character shows who gets the K,
so on through the s,
the s, and the s,
ending with the 2. This
is named .tso in honor of Thomas
Andrews (thomaso), who uses this format in generating his Impossible
of Bridge Deals.
#T:2001-09-02 18:55:17 Z
Step 4: Generate Various Output Formats
Step 4 generates formats needed by the user. The prototype supports the
Description of Deals
Some useful output format.
Have a look at the earlier example in the Danish
language HTML format.
HTML in Danish and English
DUP for the Duplimate
with other bridge software
Generally, anyone can write post-processing software that formats the
deals as they see fit. The best candidate for further formatting is PBN
because it is in general use for interchanging bridge software. Otherwise,
the easiest format to decode is probably the .tso format. For a fairly
straightforward example, see the Perl program tso-dup.pl.
It is important to support the clerical processes surrounding the use
of the deals, so whenever possible, the Tournament Description should be
carried over to the new format. For this reason, formats like the .DUP
format, which discards the Tournament Description, should be used only
when absolutely necessary, e.g. when feeding the deals to a Duplimate
The Shufflix prototype uses the CGI interface on a Web server. It is written
in Perl 5. The source code can be read here.
It is an important property of Shufflix that public access to the source
code in no way invalidates the properties of the software. On the
openness to public scrutiny should support overall trust in the Shufflix
It is a general feature of cryptographic hash functions, including MD5,
that the output cannot be distinguished statistically from random output.
In other words, each 128-bit hash result is supposed to be equally probable.
This implies that all random bytes in step 2 will be equally probable.
In turn, this implies that all shuffles in step 3 wil be equally probable
|The deals generated must be statistically indistinguishable from
chosen at random.
Of course, the theory is useless unless the implementation actually
fulfills the statistical requirements. So validation is called for. In
KG, this was achieved by creating 4000 runs of 40 boards (that is 160 000
boards), counting various statistics, and performing a chi-square test
against the theoretical distribution of these statistics. The statistics
can be quite varied, and outsiders are invited to invent statistical
Typical examples are
Such statistical tests are being run on Shufflix, and the results
published continually here. Stay tuned!
which hand gets the 7?
how many boards with a void per run of 36 boards?
where is the K when
are in one hand?
The statistical tests still use 4000 sequences of 40 boards each (160
000 boards). The sequences are generated along the following lines:
Both the entropy and the Tournament Identification are selected without
The Tournament Identification is generated systematically.
The entropy was picked up from the www.random.org,
which makes entropy publicly available on the WWW.
Simply put, if the Tournament Identification is not the same for the two
events, the one-way hash function will ensure that the boards are not
in any way. So theoretically, this boils down to convincing the operators
that it is in their interest to use thorough descriptions of the events
they are generating boards for. As a safety net under the user, the wall
clock time of his run is part of the tournament description.
|A sequence of boards generated for one event must not be
related to the boards generated for some other event.
And if that should fail, the run seeds going to be different with extreme
high likelihood, and that also makes it absolutely unlikely that two
events get related boards.
[Statistical note: Since there are 2**128 different run seeds, the
that two specific runs of Shufflix use the same run seed is
More importantly, the Birthday Paradox implies that even when
has run 2**64 times, the probability that some run seed has been used more
than once is less than ½. 2**64 is a huge number; if every
person on Earth (less than 2*33 persons on Earth) runs Shufflix once a
second (less than 2**25 seconds in a year) it still takes more than 64
years (2**6 years) to reach 2**64 runs.]
A feature of step 2 in the algorithm is that even if the same 16 random
bytes are output by MD5 in two different runs, the previous and subsequent
bytes in the two runs will still be completely unrelated. Again, this is
due to the properties of the one-way hash function.
Clerically Robust (medium)
The operator is implored to identify the tournament (or section of
for which the deals are intended. That information is then carefully
whenever possible in all subsequent renderings of the deals. At the target
event, the Tournament Director or his staff should ascertain that the boards
played are the boards intended to be played at that event.
|The software must support clerical procedures that help prevent
use of generated deals in an event that they were not intended for.
This boils down to predicting the set of possible run seeds. When sufficient
entropy is provided this amounts to checking all feasible 2**128 run seeds
with a supposedly known tournament identification. Given computer techonolgy
as of 2001, this approach will not yield useful information.
|It must be infeasible, even when backed by immense, but realistic
resources, to categorically rule out that any given sequence of
will be generated for a particular event.
No Discernable Pattern (strong)
Provided the one-way hash function is cryptographically secure, this attack
amounts to a brute-force calculation of 2**128 sequences of boards, all
performed after the first boards in the session have been seen.
|It must not be possible for dishonest, knowledgeable players, even
when backed by immense, but realistic computing resources, to
rest of the deals to be played during a session, given the deals
Users (strong): Potentially Hostile Mutually Protected
A user who describes his tournament precisely in the Tournament
is ensured against someone else running the same sequence of boards by
|A large community of potentially hostile users must be protected
each others' use of the software.
Someone else might generate the same sequence of boards by dishonest
design. The entropy ensures against that: The dishonest user has to guess
a 128-bit number in order to generate the same boards. That is sufficient
protection in practice.
Auditing that nothing was changed after dealing is fairly easy. The
saved with the deals (see the .tso file) is enough to allow an auditor
to repeat the generation process starting with step 2 and check that the
same deals are generated.
|It must be possible to ascertain after the event that the deals
not intentionally modified during and after dealing.
Auditing that the run seed was not selected knowingly in order to create
deals with certain properties is more complicated. See the FAQ
for a discussion.
The innards of Shufflix itself are in principle available for public
Anyone is allowed to read the source code. The boards become unpredictable
because of the unpredictable nature of the entropy input, not because of
any secret tricks in the Shufflix code.
For a specific event, the entropy and all the output from steps 1 through
4 have to be kept secret until the boards have been played. Of course,
this is no different from any other mechanism for dealing for a bridge
tournament, including manual dealing and manual duplication.
The simplest precaution is to deal the boards just in time - that way
very few people have a chance to know anything about the boards before
it is too late.
HTTPS to ensure that alle information regarding the deals is encrypted
when transmitted over the internet.
Version 2017-09-26/ jbc