Jefferson's Wheel

Samee Zahur and I have written a paper on Circuit Structures for Improving Efficiency of Security and Privacy Tools. The paper explores ways to design static circuits (as used in garbled circuit protocols and symbolic execution, among other things) to provide reasonable efficiency for algorithms that use common data structures like arrays. By taking advantage of somewhat predictable access patterns, as well as batching, our circuit structures are able to provide operations with amortized cost that is polylogarithmic in the size of the data structure (in contrast to naive approaches that would require effectively copying the entire data structure for each operation). Samee will present the paper at the IEEE Symposium on Security and Privacy (“Oakland”) in San Francisco in May.

Full paper (15 pages): [PDF]
Project: MightBeEvil.com/netlist

Code: http://github.com/samee/netlist

Our paper on strengthening secure computation protocols to resist stronger adversaries is now available:

Yan Huang, Jonathan Katz, and David Evans. Quid Pro Quo-tocols: Strengthening Semi-Honest Protocols with Dual Execution. In 33rd IEEE Symposium on Security and Privacy (“Oakland” 2012), San Francisco, CA. 20-23 May 2012. [PDF, 13 pages]

Yan Huang will present the paper at the Oakland conference (which will be held in San Francisco for the first time, after being in Berkeley/Oakland for the first 32 years!) in May.

Abstract: Known protocols for secure two-party computation that are designed to provide full security against malicious behavior are significantly less efficient than protocols intended only to thwart semi-honest adversaries. We present a concrete design and implementation of protocols achieving security guarantees that are much stronger than are possible with semi-honest protocols, at minimal extra cost. Specifically, we consider protocols in which a malicious adversary may learn a single (arbitrary) bit of additional information about the honest party’s input. Correctness of the honest party’s output is still guaranteed. Adapting prior work of Mohassel and Franklin, the basic idea in our protocols is to conduct two separate runs of a (specific) semi-honest, garbled-circuit protocol, with the parties swapping roles, followed by an inexpensive secure equality test. We provide a rigorous definition and prove that this protocol leaks no more than one additional bit against a malicious adversary. In addition, we propose some enhancements to reduce the overall information a cheating adversary learns. Our experiments show that protocols meeting this security level can be implemented at cost very close to that of protocols that only achieve semi-honest security. Our results indicate that this model enables the large-scale, practical applications possible within the semi-honest security model, while providing dramatically stronger security guarantees.

Full paper (13 pages): [PDF]
Project site: MightBeEvil.com

Forbes has an excellent interview with Karsten Nohl: Codebreaker Karsten Nohl: Why Your Phone Is Insecure By Design, Andy Greenberg, Forbes, 12 August 2011.

Nohl’s findings aren’t only meant to demonstrate that Nohl is an uber-skilled codebreaker. He argues that his work shows, more importantly, that phone encryption is made to be broken. Whether intentionally or unintentionally, he says, GPRS included flaws that its designers must have known about.

[Added 21 August] The Economist’s Babbage Blog also has an interesting article summarizing Karsten’s work on mobile phone security over the past few years: Living on the EDGE, 18 August 2011.

Dr Nohl stresses that the 11 minutes was just a first pass at writing the cracking software, and that his group used only modest equipment with no financial motive. Criminals, by contrast, could benefit mightily from accelerating the crack, he says, one reason his group has refrained from expounding the technique in detail. It has, however, pointed to some specific holes which ought to be plugged. The group found some networks disabled all security features, relying on the highly misguided notion that traffic could not be easily intercepted except by mobile operators. Having no security from the phone to a base station on a mast makes it easier to filter and monitor traffic.

In 2009 Dr Nohl and colleagues pointed out significant weaknesses to the base GSM standard. Their new attack focuses on General Packet Radio Service, better known as GPRS—a modest improvement to GSM—introduced commercially in 2000. GPRS allows rates of tens of kilobits per second (Kbps), while a subsequent tweak known as EDGE allows downstream rates of 200 to 400 Kbps. GPRS and EDGE are commonly referred to as 2.5G, sitting in between 2G and 3G network speeds.

The New York Times is covering Karsten Nohl’s work on vulnerabilities in cellular data networks: Hacker to Demonstrate ‘Weak’ Mobile Internet Security, New York Times, 9 August 2011.

Karsten Nohl, who published the algorithms used by mobile operators to encrypt voice conversations on digital phone networks in 2009, said during an interview he planned to demonstrate how he had intercepted and read the data during a presentation Wednesday.

Mr. Nohl said he and a colleague, Luca Melette, intercepted and decrypted wireless data using an inexpensive, modified, 7-year-old Motorola cellphone and several free software applications. The two intercepted and decrypted data traffic in a five-kilometer, or 3.1-mile, radius, Mr. Nohl said.

The interceptor phone was used to test networks in Germany, Italy and other European countries that Mr. Nohl declined to identify. In Germany, Mr. Nohl said he was able to decrypt and read data transmissions on all four mobile networks — T-Mobile, O2 Germany, Vodafone and E-Plus. He described the level of encryption provided by operators as “weak.”

In Italy, Mr. Nohl said his interceptions revealed that two operators, TIM, the mobile unit of the market leader, Telecom Italia, and Wind did not encrypt their mobile data transmissions at all. A third, Vodafone Italia, provided weak encryption, he said.

Technology Review also has an article: Researchers Hack Mobile Data Communications, Technology Review, 10 August 2011.

Phones might be the most familiar devices affected by the research, says Karsten Nohl, founder of Security Research Labs, a Berlin-based research consultancy that conducted the work. But the standard is also used in some cars, automated industrial systems, and electronic tollbooths. “It carries a lot of sensitive data,” Nohl says.

Security researchers haven’t looked at the GPRS standard much in the past, Nohl says, but since more and more devices are using GPRS, he believes the risk posed by poor security is growing.

Nohl’s group found a number of problems with GPRS. First, he says, lax authentication rules could allow an attacker to set up a fake cellular base station and eavesdrop on information transmitted by users passing by. In some countries, they found that GPRS communications weren’t encrypted at all. When they were encrypted, Nohl adds, the ciphers were often weak and could be either broken or decoded with relatively short keys that were easy to guess.

The group generated an optimized set of codes that an attacker could quickly use to find the key protecting a given communication. The attack the researchers designed against GPRS costs about 10 euros for radio equipment, Nohl says.

The Register also has this story: Hackers crack crypto for GPRS mobile networks, The Register, 10 August 2011.

The details will be presented at Chaos Communications Camp today (August 10).

Peter Chapman presented our paper on Privacy-Preserving Applications on Smartphones at the 6th USENIX Workshop on Hot Topics in Security today. Here are the talk slides [PDF].

The CommonContacts demonstration app is now available in the Android Market.

Project Website

Steve Bellovin has uncovered a Telegraph Codebook by Frank Miller from 1882 that describes a one-time pad cipher. This predates the invention by Vernam and Mauborgne during World War I, that was previously thought to be the first use of a one-time pad. The New York Times has an article, and Steve’s full report is available.

Karsten Nohl is in the news again, this time for demonstrating how bad the proprietary crypto used for car immobilizers is. Here are a few articles:

• NewScientist, Criminals find the key to car immobilisers, 6 December 2010. (Note that the criminals in the title refers to evidence that actual car theft is increasing, after many years of steady decline, not to Karsten!)
• Schneier on Security, Proprietary Encryption in Car Immobilizers Cracked, 23 December 2010.
• The Register, Car immobilisers easily circumvented by crafty carjackers: Crap crypto to blame, 20 December 2010. (British publications as so much better at titling than American ones!)

Karsten presented the technical aspects in a talk at the 8th Embedded Security in Cars conference in Berlin.

Even if car manufacturers get the crypto right, relay attacks pose a serious threat, especially for modern cars that do away with the mechanical key completely. See the upcoming NDSS paper by Aurelien Francillon, Boris Danev, and Srdjan Capkun: Relay Attacks on Passive Keyless Entry and Start Systems in Modern Cars.

Nate Paul, who finished a PhD in our group a few years ago and is now a research scientist at Oak Ridge National Labs, is the focus of this CNN story: Scientists work to keep hackers out of implanted medical devices, CNN, 16 April 2010.

Nathanael Paul likes the convenience of the insulin pump that regulates his diabetes. It communicates with other gadgets wirelessly and adjusts his blood sugar levels automatically.

But, a few years ago, the computer scientist started to worry about the security of this setup.

What if someone hacked into that system and sent his blood sugar levels plummeting? Or skyrocketing? Those scenarios could be fatal.

“If your computer fails, no one dies,” he said in a phone interview. “If your insulin pump fails, you have problems.”

As sci-fi as it sounds, Paul’s fears are founded in reality.
…

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.

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.