Jefferson's Wheel

Karsten Nohl’s research on USB security is covered in The Good News and Bad News About USB Security — Only half have an unpatchable flaw, but we don’t know which half, Wired and Slate Magazine, 12 Nov 2014:

Nohl’s BadUSB attack, which he revealed at the Black Hat security conference in August, takes advantage of the fact that a USB controller chip’s firmware can be reprogrammed. That means a thumb drive’s controller chip itself, rather than the Flash storage on that memory stick, can be infected with malware that invisibly spreads to computers, corrupts files stored on the drive, or quietly begins impersonating a USB keyboard to type commands on the victim’s machine.

…

Nohl says that means combatting BadUSB will require device-makers to clearly label the chips their products use. “You’d never get away with this in a laptop. People would go crazy if they bought a computer and it wasn’t the chip they saw in the review they read,” he says. “It’s just these USB devices that come as black boxes.”

For the technical details, see https://opensource.srlabs.de/projects/badusb.

I had a chance earlier this week to visit and speak at Hacker School in New York. Hacker School is an amazing place, billed as a “retreat for programmers”, where a remarkable group of curious and self-motivated people from a wide range of backgrounds put their lives on hold for 12 weeks to gather with like-minded people to learn about programming and spend their evenings (and 21st birthday parties) hearing talks about computability!

Slides and notes from my talk are here: What Every Hacker Should Know about Theory of Computation.

By Hannah Li

Single Sign-On (SSO) services are widely used in modern web applications for authentication and social networking. While implementing a SSO service for a website is moderately straightforward, building it correctly could be tough and mistakes can lead to serious security consequences. Previous research on Facebook SSO revealed several major vulnerabilities which could easily allow an attacker to obtain sensitive user information or to take full control of a user’s account. These security weaknesses can often lead to token credentials misuse.

Because of these findings, I was motivated to discover whether SSO services implemented with other versions of OAuth would exhibit the same security vulnerabilities. I analyzed Twitter SSO, which is implemented using OAuth 1.0A instead of OAuth 2 which is used by Facebook, for similar security weaknesses. I searched for vulnerabilities by building a web application implementing Twitter SSO and by examining the traffic between the client and the server for patterns and token leakages.

Twitter SSO Protocol: Tokens

The four “tokens” which could be used by an attacker are the Consumer Key, Request Token, Verifier, and Access Token, which will be the focus of this analysis. For the rest of this post, Alice is the user and Mallory is the attacker.

Consumer Key. The Consumer Key and Secret are given to the application when it registers with Twitter. App developers are instructors to keep this key/secret pair secret and if exposed, to generate another key/secret pair.

Request Token. This token also comes in a key/secret pair. This temporary key is issued by Twitter to the application when Alice first requests to sign in with twitter. While the key is shown publicly in the URL, the secret should be kept private.

Verifier. The Verifier is a publicly shown key (in the URL) that Twitter issues to confirm that Alice has approved the application.

Access Token. This key/secret pair is a more permanent token that allows applications to access protected resources on behalf of Alice.

Twitter SSO Protocol: Overview

The diagram below provides a high-level description for Twitter SSO procedure, breaking up the protocol into three steps, each processing an authentication token.

Twitter SSO Protocol: More Details

The diagram below expands each of the three steps. Note that the items written on the arrows do not show a comprehensive list of parameters sent, but rather a few important ones (see Implementing Sign in with Twitter Overview and OAuth Core 1.0a for detailed documentation).

Security Implications

To evaluate the security of Twitter’s SSO implementation, I tried swapping all three tokens for other tokens in different combinations. I did not find any way to use these methods to gain illicit access to private, user information. There are several countermeasures associated with each token that Twitter SSO uses to prevent this type of attack.

Request Token. The Request Token must be connected to the Consumer Key and Secret and expires after the first time it is used to request an Access Token. Due to its temporary nature and correspondence with the Consumer Key and Secret, Mallory cannot exploit the system by stealing this Request Token without also knowing the Consumer Key and Secret, which should be kept secret.

Verifier. Twitter issues a different Verifier each time, thus preventing a malicious party from reusing the Verifier through an impersonation attack. Even through the Verifier is passed through the URL, like the Request Token, Mallory cannot attack the web application without also knowing the Consumer Key and Secret.

Access Token. Each Access Token is connected to a Consumer Key and Secret, which are known only to the application developer. So even if Mallory were to successfully obtain a leaked token over the traffic, she would not be able to use it to log into Alice’s account. This is verified with HuffingtonPost.com, which leaks its Access Token pair through its last message to Alice’s browser. Without this defense, Mallory could have used the leaked Access Token to issue requests to Twitter on behalf of HuffingtonPost.com and Alice.

The last precaution also proved to be useful in another serious mistake in the SSO service. Many tests found that when an application uses the Access Token to request Alice’s information or post on her behalf, Twitter does not check the Access Token Secret, as only providing the Access Token is enough to give the client permission.

This may not pose a realistic security threat because the entire Access Token key pair is typically kept secret, so in order to take advantage of this mistake, Mallory would need to find the Consumer Key and Secret as well. To make the entire system more secure, it is recommended that Twitter verify the Access Token Secret, as many keys and secrets are accidentally leaked through GitHub and even mobile applications when the developers are not careful. When Mallory has both the Access Token and Consumer Key token/secret pairs, it would be much easier to attack a web application.

Though checking the Access Token against the Consumer Key makes SSO safer to use, it has its weaknesses as well. Mobile Applications are easy to reverse engineer since the client code must be made available. If an application needs the Consumer Key to implement SSO, then there is no possible way to build a client-only secure application with SSO since the Consumer Key must be in the code. The secure approach re-routes requests through an application server, which can securely store the key and add it to the requests sent to Twitter. This adds an extra step to app building and many developers may not realize the importance in not including the Consumer Key in the application code.

A recent study from Columbia (Nicolas Viennot, Edward Garcia, and Jason Nieh. A Measurement Study of Google Play. ACM SIGMETRICS, June 2014) scanned thousands of applications in the Google Play Store for token and secret leakages, supports the conclusion that requiring a Consumer Key from the client often leads to faulty implementations. They discovered 1,477 Facebook credentials and 28,235 Twitter credentials among all the free applications when the Facebook SDK is used twice as much as the Twitter4J Library. While their explanation of the significant difference in credentials found makes sense, a more reasonable explanation is that without using a server, it is impossible to implement a Twitter SSO without including the Consumer Key in the code.

Conclusion

While Twitter’s implementation of SSO has security advantages for web applications, it is dangerous for mobile applications. There are two clear options an API developer could use to make an authentication protocol: either you require the server to verify the Consumer Key and Secret during each step of the procedure, or you don’t, hoping that Mallory does not gain access to key information. The latter option, however, leads to many vulnerabilities as clearly seen with Facebook SSO. The first, seemingly more secure, choice causes mobile applications to sacrifice the security of an OAuth protocol.

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.

Yan Huang, who completed his PhD in 2012 and then was a post-doc at the University of Maryland, is now an Assistant Professor at Indiana University. See his IU faculty page and personal blog. IU is the home of several well-known security researchers including
Jean Camp, Steven Myers and XioFeng Wang, as well as one of my favorite authors, Douglas Hofstadter.

Our paper on automated testing of web applications has been accepted to the 2014 USENIX Security Symposium. [Update: the final version of the paper is available here.]

It describes a black-box technique for automatically scanning web sites for vulnerabilties in how they implement Facebook Single Sign-On, and results from our experiments running it on thousands of websites.

You can try the scanner at SSOScan.org.

Yuchen Zhou will present the paper at USENIX Security in San Diego, 20-22 August 2014.

Samee Zahur passed in PhD Proposal on Abstractions for Data Oblivious Programs. The abstract is:

While many recent papers have demonstrated the feasibility of secure computation for various interesting applications, such techniques have not yet been widely adopted outside of the research community. In the thesis proposed here, we try to reduce one aspect of this entry barrier: software abstractions. We motivate the problem by showing how secure computation necessarily requires redesigning of even simple software abstractions such as language control structures and data structures. First, we propose a new language that can be easily extended by other researchers for purposes of their investigations. Then, we propose new constructions for common data structures that are efficient in this execution model. Finally, we propose to develop new optimizations for ORAM structures to enable faster computations in the RAM model. Our preliminary investigations are already showing promising results. We have implemented a prototype compiler for our new language that provides significantly higher flexibility compared to existing systems. We demonstrate this flexibility by showing that our language allows implementation of various library-based features that have, in the past, always used compiler modifications in other languages. We have also shown constructions of data structures that can provide over 10x speed improvement even on small data sizes.

Congratulations to Samee on successfully presenting his PhD Proposal. Samee will be spending the summer at Microsoft Research (Redmond).

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.