August 11, 2016

2016 Internet Defense Prize Winner Brings New Hope for Post-Quantum Key Exchange

By: Nektarios Leontiadis

Security research is in a race against time to innovate faster than adversaries. The last year has seen multiple high-visibility vulnerability disclosures for every major platform. The industry has a history of over-rotating toward offensive work that has little direct impact on most people’s lives. Much of the attention still goes to research that celebrates “owning” rather than finding practical solutions for protecting people in the real world. At Facebook, we believe these incentives need to change.

This is why we created the Internet Defense Prize in 2014 through a partnership with USENIX. The Internet Defense Prize is designed to reward researchers who combine a working prototype with significant contributions to the security of the Internet—particularly in the areas of protection and defense.

In the first year, we awarded $50,000 to a pair of German researchers for their work using static analysis to detect “second-order vulnerabilities” that are used to inflict harm after being stored on the web server ahead of time. Last year, we doubled the award amount to $100,000 and presented it to a team from Georgia Tech who identified an important emerging class of security issues for C++ programs. They proposed a novel technique for detecting bad type casts by combining both static and dynamic analysis.

2016 Internet Defense Prize Winner

After careful consideration by our Award Committee, we decided to award the 2016 Internet Defense Prize and $100,000 to the authors of Post-Quantum Key Exchange – A New Hope. The winning authors include: Erdem Alkim (Department of Mathemathics, Ege University, Turkey), Léo Ducas (Centrum Wiskunde & Informatica, Amsterdam, The Netherlands), Thomas Pöppelmann (Infineon Technologies AG, Munich, Germany), and Peter Schwabe (Digital Security Group, Radboud University, The Netherlands).

post00015_image0002
Thomas Pöppelmann & Peter Schwabe, two co-authors of the 2016 Internet Defense Prize winning paper accept their award from Facebook at the 25th USENIX Security Symposium. Co-authors not pictured: Erdem Alkim and Léo Ducas.

The authors proposed new parameters for providing post-quantum security for TLS. Building on a previously proposed instantiation presented by researchers at IEEE Security & Privacy 2015, this new research identified a better suited error distribution and reconciliation mechanism, analyzed the scheme’s hardness against attacks by quantum computers, and identified a possible defense against backdoors and all-for-the-price-of-one attacks. Using these measures — and for the same lattice dimension — they were able to increase the security parameter by more than 100 percent, reduce the communication overhead by more than half, and significantly increase computation speed in portable C implementation and current Intel CPUs, all while protecting against timing attacks. This work has already led to concrete use in Chrome and planned usage in TOR.
We awarded this year’s prize at the 25th USENIX Security Symposium in Austin, Texas.

Finalists

Due to the high volume of quality papers we received this year, we also named two additional teams as finalists. We believe the strength and potential impact of their research deserves recognition.

The two finalists are:

DROWN: Breaking TLS using SSLv2, submitted by researchers from Tel Aviv University, Münster University of Applied Sciences, Horst Görtz Institute for IT Security, Ruhr University Bochum, University of Pennsylvania, Hashcat Project, University of Michigan, Two Sigma/OpenSSL, and Google/OpenSSL.

The authors developed DROWN, a dangerous attack against TLS that uses a server supporting SSLv2 as an oracle to decrypt modern TLS connections. SSLv2, an ancestor of TLS, has been obsolete for 20 years, but about a third of all TLS servers still support it for backwards compatibility. DROWN demonstrates, through several attacks scenarios, that SSLv2 is not only weak, but actively harmful to the TLS ecosystem. The protocol flaws that DROWN exploits are an unanticipated side-effect of U.S. government regulations from the 1990s, which limited the strength of cryptography that could be exported in order to ensure that intelligence agencies could circumvent it. Decades after these export restrictions were relaxed, they nonetheless contributed to widespread security problems. The authors argue that the attack provides an important historical perspective on how deliberately weakened cryptography can create risks for global Internet security, with implications for current law enforcement demands for backdoor access to encrypted devices and data.

Off-Path TCP Exploits: Global Rate Limit Considered Dangerous, submitted by researchers from the University of California, Riverside and US Army Research Laboratory. The authors of this paper reported a subtle, yet serious side channel vulnerability (CVE-2016-5696) introduced in a recent TCP specification. You can watch the proof of concept video here. The vulnerability allows a blind off-path attacker to infer if any two arbitrary hosts on the Internet are communicating using a TCP connection, and ultimately terminate that connection and perform data injection attacks. This can be used to disrupt or degrade the privacy guarantees of an anonymity network such as Tor, and perform web connection hijacking. The authors also proposed changes to both the TCP specification and implementation to eliminate the root cause of the problem.

We’d like to once again thank USENIX for their partnership and enthusiastic support of the Internet Defense Prize. According to Casey Henderson, Executive Director of the USENIX Association, “USENIX is gratified that Facebook’s Internet Defense Prize recognizes the achievements of the systems community in safeguarding the Internet. By winning this year’s prize at the 25th USENIX Security Symposium, the authors of ‘Post-Quantum Key Exchange Offers New Hope’ will be able to continue their significant research. We are proud to provide a forum for the work done by security researchers, which positively impacts the daily lives of all people.”

If you’d like to learn more about the prize, please visit InternetDefensePrize.org.

Nektarios Leontiadis is a threat research scientist on the Facebook Security team. He served on the Award Committee for the 2016 Internet Defense Prize.