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.

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.

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’ve won an Outstanding Faculty Award from the State Council on Higher Education for Virginia.

UVa has a story: U.Va. Computer Scientist David Evans Wins Statewide Outstanding Faculty Award, 29 January 2009.

SCHEV Update Newsletter [PDF]

Richmond Times-Dispatch: 12 college teachers honored in Virginia, 27 January 2009.

[Added 3 February] The Cavalier Daily also has an article: Computer science professor receives award: State Council of Higher Education honors David Evans as recipient of this year’s Outstanding Faculty Award, Cavalier Daily, 3 February 2009.

[Added 9 March] Pictures from the Ceremony

Jonathan McCune successfully defended his PhD thesis at Carnegie Mellon University last week. Jon (sorry, that’s “Dr. McCune”) was an undergraduate researcher in our group from 2001-2003, when he worked on agent-based software (for our RoboCup team) and adaptable sensor network security, before joining CMU’s PhD program in 2003. Dr. McCune’s recent research has focused on leveraging trusted hardware to build secure systems.

Congratulations Dr. McCune!

UVa Today has an article about our (myself, abhi shelat, John Lach, and Ben Calhoun) recent NSF Cybertrust grant on RFID security and privacy: U.Va. Team Receives $1 Million Grant To Improve RFID Security, by Brevy Cannon, 9 January 2009.

Some excerpts:

To address the problematic use of custom cryptography, the U.Va. research team will develop an encryption scheme that is relatively strong — providing some measure of privacy and security — but that can be implemented at almost zero cost by repurposing the meager hardware resources already available on common RFID tags. Providing a solution that adds virtually no cost is crucial, because these RFIDs are made by the billions, at such low costs (5 cents or less apiece) that there is no margin for any added expense.

…

The team is breaking new ground by using a holistic design approach that considers how all the various levels of the design — the hardware, the encryption algorithm and how it is used — work together, mindful of how an attacker will target the single weakest link in the design.

…

The research team hopes their research will forestall that possibility, enabling RFIDs to be used in countless ingenious applications not yet dreamt of, without sacrificing privacy and security in a Faustian bargain.

The University of Virginia Press has published a book, What Should I Read Next?: 70 University of Virginia Professors Recommend Readings in History, Politics, Literature, Math, Science, Technology, the Arts, and More edited by Jessica Feldman and Robert Stilling, University of Virginia Press, 2008.

The premise of the book is to collect essays from UVa professors that introduce their field to a general audience by recommending five books to read about it. I contributed an essay on computer science, How Computing Changes Thinking [HTML, PDF, 4 pages]. Here’s the blurb for the book:

What Should I Read Next? taps seventy University of Virginia professors in an array of fields for suggestions on how to satisfy this nagging intellectual curiosity. Each contributor recommends five titles that speak to their area of inquiry, providing both a general introduction and commentary on each selection. The results read like a series of personal tutorials: Larry Sabato considers how political power is acquired, used, and held onto; climatologist Robert E. Davis provides a timely navigation of global-warming literature; and Michael Levenson offers five ways to approach James Joyce’s Ulysses. Other topics include how computing changes thinking, the life and afterlife of slavery, understanding cities, and ecstatic poetry. The entries convey the contributors’ expertise but also, more importantly, the enthusiasm, the original kernels of curiosity, that drew these scholars to their life’s work.

Designed for the lifelong learner who wants to branch out from his or her own profession or discipline, these explorations–of art, science, history, technology, politics, and much more–offer an inspiring place to start.

UVa Today has an article about the book: Faculty Reading Recommendations May Guide Book Lovers, Oct 14, 2008.

The Charlottesville Daily Progress has an article by John Henderson about the Bernard Harris Summer Science Camp at UVa: <a href=”http://www.dailyprogress.com/cdp/news/local/education/article/students_get_crash_course_in_sciences_at_uva_camp/25051/”><em>Students get crash course in science at UVa camp</em></a>, The Daily Progress, 18 July 2008.  It describes some lessons we did on cryptography.  The handouts we used for this are here: <a href=”http://www.cs.virginia.edu/~evans/cavaliercrypto/”><em>http://www.cs.virginia.edu/evans/cavaliercrypto/</em></a>.

My shameless self-searching google alert occasionally turns up interesting things, like this letter to the editor of the Huntington News (West Virginia) by Gary Hurd. It refutes an op-ed piece that made all sorts of crazy pseudo-scientific arguments for “intelligent design”. The letter refutes one of the specific claims in the argument about the complexity of DNA using some material found in a lecture for my CS201J course:

And is this notion that human DNA is more complex than “any program ever devised” actually factual? The book by Watson was published in 1965, and the book by Gates that Ashby is misquoting was published in 1995, before the human genome project when we did not even know how many genes humans had! At the time, Gates’ statement was entirely reasonable, even though there was no actual data to test it. But Ashby makes a further claim, “… it is a well known fact that human DNA contains more organized information than the largest set of encyclopedias ever in print.”

David Evans, Professor of Computer Science at the University of Virginia has made some interesting comparisons between DNA and today’s computer software as part of his Computer Science 201: Engineering Software course. Let’s begin with his observation that complexity of computer software has grown at an amazing rate in the last 40 years (about since Watson’s book on the gene was published). The Apollo mission guidance programs had about 36,000 instructions, but today’s Windows XP made by Bill Gates’ Microsoft has about fifty million instructions! Professor Evans then compares this to what we now know about genes. For example, the smallest known set of genes of an organism belong to a bacterial parasite called Nanoarchaeum equitans which has 522 genes representing about 40,000 bytes of information. In other terms, it is slightly larger than the Apollo guidance system. The human genome, or as Evans called it “The Make-Human Program,” has a total of about 3 billion base pairs, which entail about 35 thousand genes. The total information content counting all of the bases is 750 megabytes, or just larger than the 650 megabytes that fit on your CDs at home. But, we have learned that massive amounts of human DNA are genetic “left overs,” non-coding segments and duplications. In short, Human DNA has fewer working instructions than Windows software, and even its total 3 billion bases are tiny compared to Wal-Mart’s 280 terabyte database (the equivalent of 1,120,000 billion DNA bases).

Like most antiscience, Ashby’s “well known facts” are not facts.

The lecture he is referring to is here: Lecture 23: Everything Else You Should Know (but won’t see on Exam 2) [PPT] (slides 18-26). Although I am happy to have anything I’ve done used to debunk intelligent design, the point I meant to make here is a bit different from what Dr. Hurd’s letter is claiming — I am not intending to suggest that the genome is not a complex program (since one could still claim it results in executions that are still far more complex, resillient, and sophisticated than anything humans have created), just that its encoding is incredibly expressive in order for such complex outcomes to be encoded with so little information. Of course, a lot of the information is not in the genome itself, but in the very complex biochemical operating system in which it is interpreted.

The specific claim from the original op-ed piece, that “DNA contains more organized information than the largest set of encyclopedias ever in print”, of course, is blatantly false. A few image-laden pages of a World Book volume contain far more information that the entire human genome.

Congratulations to two of our students who received awards yesterday!

Adrienne Felt received the Outstanding Student Award for the School of Engineering and Applied Science from the Virginia Engineering Foundation. This is an annual school-wide award for the graduating fourth-year student who has “demonstrated outstanding academic performance, leadership and service”.

Karsten Nohl won the Department of Electrical and Computer Engineering’s Louis T. Rader Graduate Research Award recognizing his outstanding research as a Computer Engineering PhD student.

Even I won an award this week.

Congratulations to Karsten and Adrienne for their much-deserved awards.