Jefferson's Wheel

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:
1. 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.
2. 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.
3. 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:

4. A well-known celebrity picks a white ball from one of the country
   bowls and hands it to Sepp Blatter, the President of FIFA.
5. 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.
6. A different well-known celebrity picks a red ball from the
   group bowl and hand it to Blatter.
7. Blatter unscrews the ball, extracts the slip of paper, reads the
   group name, and holds it up so everyone can see.
8. A different well-known celebrity picks a blue ball from the
   positions bowl corresponding to the selected group and hand it to Blatter.
9. 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.

Oakland 2010 submissions closed last week. We received 269 total submissions (of which 30 were Systematization of Knowledge papers). The program should be available by early February, for the conference that will be held May 16-19, 2010 at the Claremont Resort in Berkeley, CA.

IEEE Spectrum has an article on Karsten Nohl’s efforts to lead an open-source GSM hacking project: Open-Source Effort to Hack GSM, IEEE Spectrum, 30 November 2009.

If you’re still using a cellphone based on early digital standards, you better be careful what you say. The encryption technology used to prevent eavesdropping in GSM (Global System for Mobile communications), the world’s most widely used cellphone system, has more security holes than Swiss cheese, according to an expert who plans to poke a big hole of his own.

Karsten Nohl, chief research scientist with H4RDW4RE, a Sunnyvale, Calif.-based security research firm, is mounting what could be the most ambitious attempt yet to compromise the GSM phone system, which is used by over 3 billion people around the world. Others have cracked the A5/1 encryption technology used in GSM before, but their results have remained secret. However, Nohl, who earned a Ph.D. in computer science at the University of Virginia and is a member of Germany’s Chaos Computer Club (CCC), intends to go one big step further: By the end of the year, he plans to make the keys available to everyone on the Internet.

…

GSM cracking has a long history, which began in the late 1990s in academic circles and has since sprouted a handful of commercial businesses. Today, these companies legally sell GSM call-interception solutions–which are relatively expensive–mostly to government intelligence agencies. In general, supplying and using this software is illegal in the wider market, but no one can say for certain how many groups have illegally gained access to the technology.

That’s the point Nohl hopes to drive home: The A5/1 algorithm is a broken 64-bit encryption technology, a relic of the Cold War era, when laws prohibited the export of strong encryption technology from the United States. It needs to be replaced–ideally by the much stronger, 128-bit A5/3 system, which is already being used in newer-generation digital cellular systems, such as Universal Mobile Telecommunications System (UMTS). “If you go from the 64 bits of the A5/1 cipher to the 128 bits of A5/3,” says Nohl, cracking requires an amount of memory storage that is beyond what “is available on earth.”

A big problem with plugging the GSM encryption hole, according to the security expert, is that operators are unwilling to admit that a problem even exists. Many want to avoid spending additional money on upgrading aging and amortized GSM infrastructure, he says. The GSM Association, which represents the interests of GSM mobile operators around the world, says only that it is aware of various eavesdropping projects. In the same breath, it points to the complexities of identifying and recording calls from RF signals.

British Prime Minister Gordon Brown has issued a long overdue apology to Alan Turing on behalf of the British government. The full text is here.

Turing was a quite brilliant mathematician, most famous for his work on breaking the German Enigma codes. It is no exaggeration to say that, without his outstanding contribution, the history of World War Two could well have been very different. He truly was one of those individuals we can point to whose unique contribution helped to turn the tide of war. The debt of gratitude he is owed makes it all the more horrifying, therefore, that he was treated so inhumanely. In 1952, he was convicted of ‘gross indecency’ – in effect, tried for being gay. His sentence – and he was faced with the miserable choice of this or prison – was chemical castration by a series of injections of female hormones. He took his own life just two years later.

… But even more than that, Alan deserves recognition for his contribution to humankind. For those of us born after 1945, into a Europe which is united, democratic and at peace, it is hard to imagine that our continent was once the theatre of mankind’s darkest hour. It is difficult to believe that in living memory, people could become so consumed by hate – by anti-Semitism, by homophobia, by xenophobia and other murderous prejudices – that the gas chambers and crematoria became a piece of the European landscape as surely as the galleries and universities and concert halls which had marked out the European civilisation for hundreds of years. It is thanks to men and women who were totally committed to fighting fascism, people like Alan Turing, that the horrors of the Holocaust and of total war are part of Europe’s history and not Europe’s present.

So on behalf of the British government, and all those who live freely thanks to Alan’s work I am very proud to say: we’re sorry, you deserved so much better.

The apology grew out of an online petition initiated by John Graham-Cumming (also known for writing the Geek Atlas travel guide). Britain has a long tradition of citizens being able to petition the government, which is now supported by an e-petitions website. The petition asking for an apology to Alan Turing is currently the fourth-most signed petition with 31,349 signatures (all of whom must be British citizens).

Some news coverage:

• BBC: PM apology after Turing petition
• The Guardian: No 10 apologises for “appalling” treatment of Alan Turing
• John Graham-Cumming’s blog: “Hello John, It’s Gordon Brown”

The Call for Papers for the 2010 IEEE Symposium on Security and Privacy is now available: oakland10.cs.virginia.edu/cfp.html.

The first three deadlines are:

Workshop proposals due: Friday, 21 August 2009
Research papers due: Wednesday, 18 November 2009
Systematization of Knowledge papers due: Tuesday, 24 November

The Examiner has an article on Facebook privacy issues: To Facebook or not to Facebook, 29 June 2009.

The second approach is even scarier, a feature of Facebook which allows outside developers to create small programs called “applications” for members to do things like playing poker, getting daily horoscopes, and sending each other virtual fantasies. With the younger set, the latter must cause parents a lot of consternation over their kids. Word is there are about 24,000 applications that have been built by 400,000 developers.

And here’s the kicker. Once these developers have your personal data, there is nothing Facebook can do. Adrienne Felt of the University of Virginia investigated the procedure in her thesis and found out that 90 out of 150 of Facebook’s most popular applications (that’s 60 percent) have unnecessary access to your private information.

Jake Widman has written an interesting article about the impact of “oversharing” on Facebook: How Facebook mucks up office life: Managing a workforce is already a challenging job; now Facebook and other social networks raise a host of sticky new situations., ComputerWorld, 30 April 2009.

The key observation is the way social networks mix different social circles that would rarely intersect in real life, along with people’s willingness to accept friend requests from unknown or unvalidated individuals.

Separate from the social challenge is the issue of people, particularly younger Facebook users, becoming friends with people they don’t know well, or even at all. “Facebook doesn’t have our normal social mechanisms for validating someone,” Argast points out — and many users, especially people who use Facebook to network, are reluctant to turn down a friend request.

The article mentions studies that indicate both that a significant fraction (23%) of hiring managers check social networking sites on potential hires, and that the majority of Facebook users do not understand how visible their “private” information is.

The article also highlights the additional risks of applications.

A further issue is the fact Facebook applications gain access to — as the warning screen tells you — “your profile information, photos, your friends’ info, and other content that it requires to work,” whether they need it or not.

In 2007, Adrienne Porter Felt, then a computer science student at the University of Virginia and now a student at U.C. Berkeley, and David Evans, an Associate Professor of Computer Science at the University of Virginia, did a survey of the top 150 Facebook applications and found that “90.7% of applications are being given more privileges than they need” to perform their intended functions.

The researchers haven’t updated those earlier findings, but Evans says he suspects the results would be pretty similar. “If anything, the applications are getting more complex,” he says. “And there is also an emerging model for third-party advertising networks embedded in applications, which has further privacy risks.”

In summary,

Bottom line? Facebook doesn’t call for new principles, Selvas says, just smart application of the old ones. And the constant reminder that you and your employees are in public when you’re on Facebook. As Selvas sums up, “Don’t do anything on Facebook you wouldn’t do in an airport.”

Congratulations to Adrienne Felt (BSCS 2008, now a PhD student at Berkeley) who won an NSF Graduate Research Fellowship! The award provides 3 years of funding along with lots of prestige and glory.

Four other UVa students one NSF Graduate fellowships in Computer Science this year (two of whom are BACS students):

• Sara Alspaugh, BACS 2009
• Erika Chin, BSCS 2007 (now at Berkeley)
• Linda Yang Liu, BS Biology 2008 (now at Stanford doing bioinformatics)
• Rachel Miller, BACS 2009

No other school had 5 of its graduates win CS NSF Graduate fellowships — Princeton was second with 4, followed by MIT and UC Berkeley with 3 each.

I found two of our former undergraduate researchers at a seminar at Dagstuhl (Germany) on Web Application Security.

Photo by Anh Nguyen-Tuong

Salvatore Guarnieri (UVa BS 2006, left in the picture) is now a PhD student at the University of Washington. He presented his work on (mostly) statically analyzing JavaScript that he did as an intern at MSR.

William G. J. Halfond (UVa BS 2002, right in the picture) is finishing a PhD at Georgia Tech this year. He presented his work on automatically generating inputs for web application penetration testing.

John Wilander has been blogging the workshop: Dagstuhl Seminar Final (or, if you can’t read Swedish try Google’s translation).

On his recent visit to England, President Obama presented the Queen with an iPod loaded with showtunes. Although one might question the diplomatic and musical judgment behind such a gift, it also raises some interesting questions about copyright law and computer security.

The EFF has an interesting article about the copyright issues: iPods, First Sale, President Obama, and the Queen of England, Fred von Lohmann, 2 April 2009. It starts,

President Obama reportedly gave an iPod, loaded with 40 show tunes, to England’s Queen Elizabeth II as a gift. Did he violate the law when he did so?

You know your copyright laws are broken when there is no easy answer to this question.

The other question this raises is how effective of a malware vector this is when the Queen attaches the iPod to her PC (okay, the Queen probably runs ubuntu). I don’t know if there are any known vulnerabilities in the iPod/iTunes interface, but its a wide enough interface that it would be very unsurprising if there are ways to get malware from an iPod to a host machine. Perhaps, this is all part of a clever strategy to make heads of less friendly states than the Queen expect to receive electronic gadgets from our President and connect them to their systems.