Hacking the World Cup Draw
3 December 2009
The New York Times has an article about rigging the World Cup draw (which takes place tomorrow in South Africa): In World Cup Draw, Conspiracy Theories Abound, 3 December 2009.
The article mentions the final exam from my 2005 Cryptography course:
It is anyone’s guess how the 32 teams in the 2010 World Cup will be grouped by the draw Friday in South Africa, but one thing is for sure: the event will elicit sightings of things as far-fetched as U.F.O.’s and the Virgin Mary’s image on a potato chip.
…
Yet conspiracy theories abound. In 2005, the issue was part of a final exam in a cryptology course at the University of Virginia.
Here’s the actual exam: http://www.cs.virginia.edu/cs588/final/final.html and an excerpt from my comments:
4W. Germany 1, USA 0
After the 1994 World Cup draw placed the host USA in a very difficult
group, the USA coach, Bora Milutinovic, is reputed to have complained
that the US organizing committee was so incompetent they couldn’t even
rig the draw properly. For purposes of this question, assume the DFB
(German soccer federation) which is hosting the 2006 World Cup does not
suffer from such incompetence.
The draw assigns each qualified team to a group (one of eight, A-H) and
position (1-4). For example, in the 2002 draw the USA was assigned D3.
The host country is placed into position A1.
The protocol for the draw for the 2006 World Cup finals has not been
announced yet, but assume it will follow a protocol similar to this one
which was used in 2002:
- Before the draw event:
- The name of each finalist (except the host country which is placed
in position A1) is printed on a slip of paper which is placed in a
white, spherical ball. The ball is made of two hemispheres that connect
to each other, and can be separated to insert or remove the paper. The
balls are placed into different bowls based on a partitioning determined
by FIFA. - The letter name to identify each group (A, B, C, D, E, F, G, H) is
printed on a slip of paper and placed in a red, spherical ball. All the
red balls are placed in a bowl. - The position number (1, 2, 3, 4) is printed on a slip of paper and
placed in a blue, spherical ball. There are eight bowls of the four
numbers, one corresponding to each group A-H. (In the bowl for A, only
three balls with numbers 2, 3 and 4 are used, since the host country was
preassigned to position A1).At the draw event:
- A well-known celebrity picks a white ball from one of the country
bowls and hands it to Sepp Blatter, the President of FIFA. - Blatter unscrews the ball, extracts the slip of paper, reads the
country name, and holds it up so everyone can see. After reading the
slip, it is placed in a trash bin that is not examined after the draw. - A different well-known celebrity picks a red ball from the
group bowl and hand it to Blatter. - Blatter unscrews the ball, extracts the slip of paper, reads the
group name, and holds it up so everyone can see. - A different well-known celebrity picks a blue ball from the
positions bowl corresponding to the selected group and hand it to Blatter. - Blatter unscrews the ball, extracts the slip of paper, reads the
position number, and holds it up so everyone can see.
Note that at the end of the draw, all balls have been opened. It is a
check on the protocol that all positions, groups and countries have been
seen by the end. The actual slips of paper are destroyed (without
examination) after the draw.
You should assume both the DFB who is hosting the draw, and Sepp
Blatter, are both highly motivated to rig the results to ensure an easy
path to the second round for the host country. Well-known celebrities
are used to pick the balls to ensure a low likelihood that a selector
can be corrupted. The pre-draw steps are done in secret by the DFB.
The draw event itself is witnessed by thousands of people live and in
person and approximately a billion people live on TV around the world
(it is the world’s most watched televised event that is not a soccer
game).
Analyze the security of the World Cup draw procedure as described
above. Either describe tactics the DFB could use to improve the
likelihood that Germany get a favorable draw, or argue that the
procedure is secure and there is no reasonable way of effecting the
result. If you identify security weaknesses in the draw protocol,
suggest modifications that would make it more secure.
For inspiration, you may want to read Bruce Schneier’s Hacking the Papal Election analysis of the Papal election procedure.
(Note: this question should in no way be interpreted as
questioning the integrity of FIFA or the DFB, especially if they are
using RFID tags to track my tickets’ whereabouts.)
Comments: There are lots of weaknesses in the described protocol
(which does not match the actual world cup draw protocol which may have even more vulnerabilities) that could be used to alter the draw outcome.
The least risky way of rigging the draw would be to adjust the weights of the balls to increase the likelihood that certain balls end up on the outside edge of the bowl and will be picked early. This can effect the probabilities of getting certain teams in Germany’s group, and involves little risk of getting caught (as long as the process of loading the balls is done in secret by trusted (but not trustworthy) people).
A riskier, but more certain, way of fixing the draw would be to put two slips in some of the balls. Blatter would need to be able to pick the right slip without anyone noticing him doing so. The easiest way would be to have two slips of different length that are attached with a very weak adhesive. Blatter knows that the shorter slip has the strong team and the longer slip has the weak team. There are two balls with two slips, so Blatter will need to remember for the next ball to pick the opposite one. This allows control of two teams, which is not enough to control the whole draw, but is enough to give Germany one easier team.
Blatter could also have a slip “up his sleeve” with a desirable team name on it, but it would be difficult to pull of any sleight of hand tricks without getting caught.
Some improvements that would make cheating more difficult would be to have an independent third party create the balls in public, to have a multiple-readers strategy like in the Pope election where several people examine each slip in public, to have the celebrities (considered uncorruptable) not only pick the ball but open it and examine the slip before it is read, and to have all the balls selected before any one it opened (to prevent any attacks that depend on knowing what was in the previous ball to pick a desirable ball).
From the NYT article, I may be mistaken about the rumors of Bora Milutinovic’s comments about the 1994 draw. Perhaps it was really Bruce Arena’s quote about the draw for the 1996 Olympics, quoted in the NYT article which is presumably a fairly reputable source.
As for tomorrow’s draw, so long as the US doesn’t end up in a group with Brazil, France, and Ivory Coast, I’m willing to assume its not rigged.