Archive for the 'Cryptography' Category

Secure Multi-Party Computation: Promises, Protocols, and Practicalities

Tuesday, June 27th, 2017

I gave a talk at ECRYPT NET: Workshop on Crypto for the Cloud & Implementation (which was combined with Paris Crypto Day) on our group’s work on secure multi-party computation, using Bargav Jayaraman and Hannah Li‘s recent work on decentralizing certificate authorities as a motivating application.

Spectra Articles: Privacy-Preserving Regression and Ombuds

Monday, March 21st, 2016

The latest edition of Spectra: The Virginia Engineering and Science Research Journal includes two articles about SRGers!

The first is an article about Sam Havron’s research on using MPC to perform linear regression for social science applications: [PDF]

alt : Ombuds.pdf

The second is by Alex Kuck and Nick Skelsey on their work on using a blockchain to provide censorship-resistant messaging: Ombuds: A Public Space with a Single Shared History: [PDF]

alt : Ombuds.pdf

The full issue is available at the Spectra site (thanks to Garrett Beeghly for granting permission to post these excerpts here).

Latest from Karsten Nohl: POS Security

Wednesday, December 30th, 2015

Karsten Nohl (PhD 2009) presented his work (with Fabian Bräunlein and Philipp Maier) on vulnerabilities in payment protocols (the ones studied are widely used in Germany but not in other countries) at the Chaos Communications Congress on December 27.

The work has been widely covered in the press recently. Here are a few sample articles:

- Watch infosec bods swipe PINs, magstripe data from card readers live on stage, The Register, 30 Dec 2015. (I trust the use of “bods” here is some kind of Britishism, not what it means in American.)

Now let’s look at Poseidon: a crook can buy a Poseidon payment terminal from the internet, and configure it to pretend to be a particular merchant’s systems. To do this, you need three bits of information, which are trivial to obtain…. Now you can perform arbitrary refunds, drawing money from the store’s funds. As there is no interruption to a merchant’s service, the seller will be none the wiser until he or she audits their finances. … German banks have shrugged off their research as merely “theoretical.”

- Payment system security is hilariously bad, BoingBoing (Cory Doctorow), 29 Dec 2015.

- Worries over German retail payments risks, Reuters, 23 December 2015.

A top cyber security researcher has warned German banks that their retail payment systems have security flaws that could allow fraudsters to steal payment card PIN codes, create fake cards or siphon funds from customer or merchant accounts.
Karsten Nohl, who is credited with revealing major security threats in mobile phones, automobiles, security cards and thumb-sized USB drives, told Reuters he has found critical weaknesses in software that runs retail point-of-sale terminals in Germany.

Trick or Treat?: Bitcoin for Non-Believers, Cryptocurrencies for Cypherpunks

Sunday, November 8th, 2015

I gave a talk at Johns Hopkins University for the DC-Area Crypto Day focused on cryptocurrencies: Trick or Treat?: Bitcoin for Non-Believers, Cryptocurrencies for Cypherpunks.

Video of the Entire Workshop

Great to include two recent alums, Alex Kuck and Nick Skelsey at the end of my talk. They talks about progress with Ombuds, a platform for free speech built on the blockchain.

Download slides: [PPTX (35 MB), PDF (4-up, 34MB)]


Friday, June 5th, 2015

I went to a very interesting meeting at Darmstadt: CROSSING – Where Quantum Physics, Cryptography, System Security and Software Engineering meet. Lots more diversity than my typical computer security meeting, including a lively debate on quantum physics and superfluid vacuum theory between Nicolas Grisin (founder of ID Quantique and Ross Anderson. Interesting to learn that China is building a huge quantum key distribution network.

I gave a talk on Multi-Party Computation for the Masses:

CROSSING is a 12-year project funded by the German Science Foundation (with reviews every 4 years). Gives some context to US funding agencies that talk about long-range visionary projects with 5-year timelines.

Two Halves Make a Whole!

Monday, September 29th, 2014

Surprisingly, it is possible to reduce the data needed for a garbled gate to only two ciphertexts per gate, while preserving free xors. The scheme for doing that is described in our paper, Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates by Samee Zahur and Mike Rosulek and David Evans (now available on eprint).

Abstract. The well-known classical constructions of garbled circuits use four ciphertexts per gate, although various methods have been proposed to reduce this cost. The best previously known methods for optimizing AND gates (two ciphertexts; Pinkas et al., ASIACRYPT 2009) and XOR gates (zero ciphertexts; Kolesnikov & Schneider, ICALP 2008) were incompatible, so most implementations used the best known method compatible with free-XOR gates (three ciphertexts; Kolesnikov & Schneider, ICALP 2008). In this work we show how to simultaneously garble AND gates using two ciphertexts and XOR gates using zero ciphertexts, resulting in smaller garbled circuits than any prior scheme. The main idea behind our construction is to break an AND gate into two half-gates — AND gates for which one party knows one input. Each half-gate can be garbled with a single ciphertext, so our construction uses two ciphertexts for each AND gate while being compatible with free-XOR gates. The price for the reduction in size is that the evaluator must perform two cryptographic operations per AND gate, rather than one as in previous schemes. We experimentally demonstrate that our garbling scheme leads to an overall decrease in time (up to 25%), bandwidth (up to 33%), and energy use (up to 20%) over several benchmark applications. We also initiate a study of lower bounds for garbled gate size, and show that our construction is optimal for a large class of garbling schemes encompassing all known practical garbling techniques.

Karsten Nohl visits UVa

Friday, November 1st, 2013

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.

Engineering Cryptosystems

Wednesday, October 30th, 2013

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:

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

Symmetric Cut-and-Choose

Friday, June 14th, 2013

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]

Stephen Colbert on Jefferson’s Wheel!

Wednesday, May 22nd, 2013

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