Jefferson's Wheel

Yuchen Zhou won the Rader Graduate Research Award for Computer Engineering! This award from the Department of Electrical and Computer Engineering recognizes outstanding research by a Computer Engineering PhD student.

I gave a keynote talk at the Applied Multi-Party Computation workshop at Microsoft Research Redmond on Multi-Party Computation in 2029: Boom, Bust, or Bonanza?. Despite the risk of being proved horribly wrong in 15 years, my slides are here (also available as [PPTX] and as a video):

There are well-written summaries of the talk by Mahnush Movahedi and Mahdi Zamani and the Aarhus Crypto Group.

My children’s book on combinatorics and computability is now available!

“If only I had this book when I was a young student, I might have done something useful with my life like discover a new complexity class instead of dropping out and wasting my life on flipping pancakes, playing with basic blocks, and eradicating polo.”
Gill Bates, Founder of Mic-Soft Corporation

The book is available for free download from dori-mic.org and nicely printed color copies from amazon.com.

Here’s a picture from our research group lunch to congratulate Ivan Alagenchev on his MCS graduation and wish him well at Amazon.

Karsten Nohl, who complete a PhD in our group in 2009, is visiting UVa this week. UVa Today has an article: Renowned ‘White Hat Hacker’ to Speak on Real-World Security Holes:

University of Virginia graduate Karsten Nohl, one of the world’s most famous “white hat computer hackers,” will speak Friday at 3:30 p.m. in Rice Hall, room 130, about lessons learned from the security holes that he and fellow researchers have uncovered in mobile phones, wireless car keys and other technology used by billions of people everyday.

Nohl first made international headlines in 2008, while still a computer engineering doctoral student at U.Va., for research that exposed vulnerabilities in the world’s most popular smartcard, used by millions of people to pay fares on several major mass-transit systems around the world, including the London Underground and the Boston subway.

Such cards utilize miniscule wireless computer chips, about the size of a grain of rice, called RFIDs, short for “radio-frequency identification.” They send and receive information over short distances (generally 10 feet or less) via very low-power radio waves.

As an ethical security researcher, often called a “white hat hacker,” Nohl exposes vulnerabilities to spur improvements in the systems that he researches. He now does such work around the world as the founder and director of research at Security Research Labs in Berlin.

To prevent those with nefarious purposes from exploiting security holes he uncovers, Nohl typically withholds key details of the exploit and discloses his findings only months after sharing his research with the relevant manufacturers or trade organizations to allow them to roll out upgrades or countermeasures to mitigate the security risk.

Since graduating from U.Va. in August 2008, Nohl has gone on to discover and demonstrate two key security vulnerabilities in mobile phones – encryption flaws in both the GSM protocol that most cell phones use to communicate with cell towers, and in SIM cards, the tiny “subscriber identity module” chip in every phone that identifies and authenticates the phone.

Both discoveries generated worldwide media coverage.

As just one example of possible ramifications, the latter security hole could allow a malicious hacker to send a virus through a text message, which could then allow the hacker to eavesdrop on calls or make purchases through mobile payment systems.

“Karsten has had an outstanding impact in analyzing how cryptography gets used in the real world and demonstrating what goes wrong when important engineering principles are not followed carefully,” said computer science professor David Evans, Nohl’s former doctoral adviser and a co-organizer of Friday’s talk. “The vulnerabilities he has identified in RFID algorithms, GSM encryption and SIM cards impact billions of devices most of us use every day, and it’s really important that people understand the security weaknesses in these systems and that vendors work to improve them. Karsten’s work is a fundamental step toward those goals.”

Nohl’s talk will discuss how security exploits with real-world implications are usually enabled by not just one design flaw, but by deviations from best practices on multiple design layers. Protection designs that focus on a single security function and neglect complementary layers are more prone to compromise, Nohl will argue, with examples from his own research on three widely deployed technologies – cell phones, car keys and smartcards.

“Real-world cryptographic systems rarely meet academic expectations, with most systems being shown ‘insecure’ at some point,” Nohl said in an email description of his talk. “At the same time, our IT-driven world has not yet fallen apart, suggesting that many protection mechanisms are ‘secure enough’ for how they are employed.”

The talk will be followed by a reception in the fourth-floor atrium of Rice Hall.

The event is co-sponsored by the departments of Computer Science and Electrical and Computer Engineering, which jointly administer U.Va.’s computer engineering Program in the School of Engineering and Applied Science.

I gave a four-session “mini-course” for Microstrategy on Engineering Cryptosystems. It ended up attracting enough interest to be moved from their offices to a nearby movie theater!

The course was targeted to engineers at Microstrategy with no prior experience with cryptography, and designed to give them some ideas of the power of modern cryptography, and to provide enough stories about cryptosystems going bad to convince them not do try to develop their own cryptosystems, and to know enough to ask the right questions of people who do.

The four main topics were:

• Symmetric Cryptosystems
• Using (and Misusing) Symmetric Cryptosystems
• Public-Key Protocols
• The Future of Cryptography

Since it was in a movie theater, it also provided an opportunity to officially screen this trailer in a real movie theater:

Security exploits nearly always stem from attackers finding ways to violate assumptions system implementers relied upon. As a simple example, consider a classic buffer overflow attack which is possible because the implementers assumed (perhaps implicitly) that the size of some data could not exceed the buffer size, but an attacker found a way to create an input that violates that assumption.

In this work, joint with colleagues at Microsoft Research, we consider the implicit assumptions upon which secure use of single sign-on SDKs depends. Our study of three important authentication and authorization SDKs (including Facebook’s) supports the need for systematically explicating SDKs to uncover these assumptions. We found assumptions that were critical to secure use of the SDKs, but that were not clearly documented and were subtle enough to be missed by the majority of tested apps.

We advocate that a systematic explication process for uncovering these assumptions should be part of the engineering process for developing security-critical SDKs.

For details, see our paper:

Our paper on symmetric cut-and-choose is now available. The paper will be presented at CRYPTO 2013 in August.

Abstract. Beginning with the work of Lindell and Pinkas, researchers have proposed several protocols for secure two-party computation based on the cut-and-choose paradigm. In existing instantiations of this paradigm, one party generates k garbled circuits; some fraction of those are “checked” by the other party, and the remaining fraction are evaluated. We introduce here the idea of symmetric cut-and-choose protocols, in which both parties generate k circuits to be checked by the other party. The main advantage of our technique is that k can be reduced by a factor of 3 while attaining the same statistical security level as in prior work. Since the number of garbled circuits dominates the costs of the protocol, especially as larger circuits are evaluated, our protocol is expected to run up to 3 times faster than existing schemes. Preliminary experiments validate this claim.

Full paper (16 pages): [PDF]

Congratulations to the 2013 SRG Graduates!

Tianhao Tong (MCS), Dr. Yan Huang (PhD)

Jonathan Burket (BACS with Highest Distinction), William Melicher (BSCS, not pictured)

Stephen Colbert spoke about Jefferson’s wheel cipher at his valediction speech: