Publications

J. Alex Halderman
 

Index


BibTeX file   Talks and panels

[PDF]
Joseph A. Calandrino, J. Alex Halderman, and Edward W. Felten
In submission.

Generation of random numbers is a critical component of existing post-election auditing techniques. Recent work has largely discouraged the use of all pseudorandom number generators, including cryptographically secure pseudorandom number generators (CSPRNGs), for this purpose, instead recommending the sole use of observable physical techniques. In particular, simple dice rolling has received a great deal of positive attention. The typical justification for this recommendation is that those less comfortable with mathematics prefer a simple, observable technique. This paper takes a contrary view. Simple, observable techniques like dice rolling are not necessarily robust against sleight of hand and other forms of fraud, and attempts to harden them against fraud can dramatically increase their complexity. With simple dice rolling, we know of no techniques that provide citizens with a reasonable means of verifying that fraud did not occur during the roll process. CSPRNGs, used properly, can be simple, robust, and verifiable, and they allow for the use of auditing techniques that might otherwise be impractical. While we understand initial skepticism towards this option, we argue that appropriate use of CSPRNGs would strengthen audit security.

[PDF | Web site ]
J. Alex Halderman, Seth D. Schoen, Nadia Heninger, William Clarkson, William Paul, Joseph A. Calandrino, Ariel J. Feldman, Jacob Appelbaum, and Edward W. Felten
To appear in Proc. 17th USENIX Security Symposium (Sec '08), San Jose, CA, August 2008

Contrary to popular assumption, DRAMs used in most modern computers retain their contents for seconds to minutes after power is lost, even at operating temperatures and even if removed from a motherboard. Although DRAMs become less reliable when they are not refreshed, they are not immediately erased, and their contents persist sufficiently for malicious (or forensic) acquisition of usable full-system memory images. We show that this phenomenon limits the ability of an operating system to protect cryptographic key material from an attacker with physical access. We use cold reboots to mount attacks on popular disk encryption systems — BitLocker, FileVault, dm-crypt, and TrueCrypt — using no special devices or materials. We experimentally characterize the extent and predictability of memory remanence and report that remanence times can be increased dramatically with simple techniques. We offer new algorithms for finding cryptographic keys in memory images and for correcting errors caused by bit decay. Though we discuss several strategies for partially mitigating these risks, we know of no simple remedy that would eliminate them.

[PDF]
J. Alex Halderman and Ariel J. Feldman
Princeton University Computer Science Technical Report TR-816-08, March 8, 2008

This report describes the hardware design of the AVC Advantage direct-recording electronic (DRE) voting machine. We developed these functional specifications by reverse engineering a government-surplus system.

[PDF]
J. Alex Halderman and Brent Waters
Proc. 14th ACM Conference on Computer and Communications Security (CCS '07), Washington, DC, October 2007

Several important security protocols require parties to perform computations based on random challenges. Traditionally, proving that the challenges were randomly chosen has required interactive communication among the parties or the existence of a trusted server. We offer an alternative solution where challenges are harvested from oblivious servers on the Internet. This paper describes a framework for deriving "harvested challenges" by mixing data from various pre-existing online sources. While individual sources may become predictable or fall under adversarial control, we provide a policy language that allows application developers to specify combinations of sources that meet their security needs. Participants can then convince each other that their challenges were formed freshly and in accordance with the policy. We present Combine, an open source implementation of our framework, and show how it can be applied to a variety of applications, including remote storage auditing and non-interactive client puzzles.

[PDF, Workshop PDF]
Joseph A. Calandrino, J. Alex Halderman, and Edward W. Felten
Proc. 2007 USENIX/ACCURATE Electronic Voting Technology Workshop (EVT '07), Boston, MA, August 2007

Election audit procedures usually rely on precinct based recounts, in which workers manually review all paper ballots from selected polling places, but these recounts can be expensive due to the labor required. This paper proposes an alternative audit strategy that allows machines to perform most of the work. Precincts are recounted using recounting machines, and their output is manually audited using efficient ballot sampling techniques. This strategy can achieve equal or greater confidence than precinct-based auditing at a significantly lower cost while protecting voter privacy better than previous ballot-based auditing methods. We show how to determine which ballots to audit against the recounting machines' records and compare this new approach to precinct-based audits in the context of Virginia's November 2006 election. Far fewer ballots need to be audited by hand using our approach. We also explore extensions to these techniques, such as varying individual ballots' audit probabilities based on the votes they contain, that promise further efficiency gains.

[Extended PDF, Workshop PDF, Videos]
Ariel J. Feldman, J. Alex Halderman, and Edward W. Felten
Proc. 2007 USENIX/ACCURATE Electronic Voting Technology Workshop (EVT '07), Boston, MA, August 2007

This paper presents a fully independent security study of a Diebold AccuVote-TS voting machine, including its hardware and software. We obtained the machine from a private party. Analysis of the machine, in light of real election procedures, shows that it is vulnerable to extremely serious attacks. For example, an attacker who gets physical access to a machine or its removable memory card for as little as one minute could install malicious code; malicious code on a machine could steal votes undetectably, modifying all records, logs, and counters to be consistent with the fraudulent vote count it creates. An attacker could also create malicious code that spreads automatically and silently from machine to machine during normal election activities — a voting-machine virus. We have constructed working demonstrations of these attacks in our lab. Mitigating these threats will require changes to the voting machine's hardware and software and the adoption of more rigorous election procedures.

[PDF]
Joseph A. Calandrino, Ariel J. Feldman, J. Alex Halderman, David Wagner, Harlan Yu, and William Zeller
California Secretary of State's Top-to-Bottom Voting System Review, July 2007


[Extended PDF, Conference PDF, Slides: PPT]
J. Alex Halderman and Edward W. Felten
Proc. 15th USENIX Security Symposium (Sec '06), Vancouver, BC, August 2006

In the fall of 2005, problems discovered in two Sony-BMG compact disc copy protection systems, XCP and MediaMax, triggered a public uproar that ultimately led to class-action litigation and the recall of millions of discs. We present an in-depth analysis of these technologies, including their design, implementation, and deployment. The systems are surprisingly complex and suffer from a diverse array of flaws that weaken their content protection and expose users to serious security and privacy risks. Their complexity, and their failure, makes them an interesting case study of digital rights management that carries valuable lessons for content companies, DRM vendors, policymakers, end users, and the security community.

[PDF]
Edward W. Felten and J. Alex Halderman
IEEE Security and Privacy, January/February 2006


[PDF, Slides: PPT]
J. Alex Halderman, Brent Waters, and Edward W. Felten
Proc. 14th International World Wide Web Conference (WWW '05), Chiba, Japan, May 2005

Computer users are asked to generate, keep secret, and recall an increasing number of passwords for uses including host accounts, email servers, e-commerce sites, and online financial services. Unfortunately, the password entropy that users can comfortably memorize seems insufficient to store unique, secure passwords for all these accounts, and it is likely to remain constant as the number of passwords (and the adversary's computational power) increases into the future. In this paper, we propose a technique that uses a strengthened cryptographic hash function to compute secure passwords for arbitrarily many accounts while requiring the user to memorize only a single short password. This mechanism functions entirely on the client; no server-side changes are needed. Unlike previous approaches, our design is both highly resistant to brute force attacks and nearly stateless, allowing users to retrieve their passwords from any location so long as they can execute our program and remember a short secret. This combination of security and convenience will, we believe, entice users to adopt our scheme. We discuss the construction of our algorithm in detail, compare its strengths and weaknesses to those of related approaches, and present Password Multiplier, an implementation in the form of an extension to the Mozilla Firefox web browser.

[PDF, Slides: PPT]
J. Alex Halderman, Brent Waters, and Edward W. Felten
Proc. 2004 ACM Workshop on Privacy in the Electronic Society (WPES '04), Washington, DC, October 2004

The growing popularity of inexpensive, portable recording devices, such as cellular phone cameras and compact digital audio recorders, presents a significant new threat to privacy. We propose a set of technologies that can be integrated into recording devices to provide stronger, more accurately targeted privacy protections than other legal and technical measures now under consideration. Our design is based on an informed consent principle, which it supports by the use of novel devices and protocols that automate negotiations over consent and ensure appropriate safeguards on recorded data. We define the protocols needed for this purpose and establish their security. We also describe a working prototype implementation that safeguards audio recorded by laptop PCs in a wireless network.

[PDF]
Brent Waters, Ari Juels, J. Alex Halderman, and Edward W. Felten
Proc. 11th ACM Conference on Computer and Communications Security (CCS '04), Washington, DC, October 2004

We explore new techniques for the use of cryptographic puzzles as a countermeasure to Denial-of-Service (DoS) attacks. We propose simple new techniques that permit the outsourcing of puzzles--their distribution via a robust external service that we call a bastion. Many servers can rely on puzzles distributed by a single bastion. We show how a bastion, somewhat surprisingly, need not know which servers rely on its services. Indeed, in one of our constructions, a bastion may consist merely of a publicly accessible random data source, rather than a special purpose server. Our outsourcing techniques help eliminate puzzle distribution as a point of compromise. Our design has three main advantages over prior approaches. First, it is more resistant to DoS attacks aimed at the puzzle mechanism itself, withstanding over 80% more attack traffic than previous methods in our experiments. Second, our scheme is cheap enough to apply at the IP level, though it also works at higher levels of the protocol stack. Third, our method allows clients to solve puzzles offline, reducing the need for users to wait while their computers solve puzzles. We present a prototype implementation of our approach, and we describe experiments that validate our performance claims.

[HTML, PDF]
J. Alex Halderman
Princeton University Computer Science Technical Report TR-679-03, October 2003

MediaMax CD3 is a new copy-prevention technique from SunnComm Technologies that is designed to prevent unauthorized copying of audio CDs using personal computers. SunnComm claims its product facilitates "a verifiable and commendable level of security," but in tests on a newly-released album, I find that the protections may have no effect on a large fraction of deployed PCs, and that most users who would be affected can bypass the system entirely by holding the shift key every time they insert the CD. I explain that MediaMax interferes with audio copying by installing a device driver the first time software from the CD is executed, but I show that this provides only minimal protection because the driver can easily be disabled. I also examine the digital rights management system used to control access to a set of encrypted, compressed audio files distributed on the CD. Although restrictions on these files are more relaxed than in prior copy protected discs, they still prohibit many uses permitted by the law. I conclude that MediaMax and similar copy-prevention systems are irreparably flawed but predict that record companies will find success with more customer-friendly alternatives for reducing infringement.

[PDF]
Patrick Min, J. Alex Halderman, Michael Kazhdan, and Thomas A. Funkhouser
Proc. 8th International Conference on 3D Web Technology (Web3D '03), March 2003 — Best paper award

New acquisition and modeling tools make it easier to create 3D models, and fordable and powerful graphics hardware makes it easier to use them. As a result, the number of 3D models available on the web is increasing rapidly. However, it is still not as easy to find 3D models as it is to find, for example, text documents and images. What is needed is a "3D model search engine," a specialized search engine that targets 3D models. We created a prototype 3D model search engine to investigate the design and implementation issues. Our search engine can be partitioned into three main components: (1) acquisition: 3D models have to be collected from the web, (2) analysis: they have to be analyzed for later matching, and (3) query processing and matching: an online system has to match user queries to the collected 3D models. Our site currently indexes over 36,000 models, of which about 31,000 are freely available. In addition to a text search interface, it offers several 3D and 2D shape-based query interfaces. Since it went online one year ago (in November 2001), it has processed over 148,000 searches from 37,800 hosts in 103 different countries. Currently 20-25% of the about 1,000 visitors per week are returning users. This paper reports on our initial experiences designing, building, and running the 3D model search engine.

[PDF]
Thomas Funkhouser, Patrick Min, Misha Kazhdan, Joyce Chen, J. Alex Halderman, David Dobkin, and David Jacobs
ACM Transactions on Graphics, 22(1), pp. 83-105, January 2003

As the number of 3D models available on the Web grows, there is an increasing need for a search engine to help people find them. Unfortunately, traditional text-based search techniques are not always effective for 3D data. In this paper, we investigate new shape-based search methods. The key challenges are to develop query methods simple enough for novice users and matching algorithms robust enough to work for arbitrary polygonal models. We present a web-based search engine system that supports queries based on 3D sketches, 2D sketches, 3D models, and/or text keywords. For the shape-based queries, we have developed a new matching algorithm that uses spherical harmonics to compute discriminating similarity measures without requiring repair of model degeneracies or alignment of orientations. It provides 46.245% better performance than related shape matching methods during precision-recall experiments, and it is fast enough to return query results from a repository of 20,000 models in under a second. The net result is a growing interactive index of 3D models available on the Web (i.e., a Google for 3D models).

[PDF, Slides: PPT]
J. Alex Halderman
Proc. 2002 ACM Workshop on Digital Rights Management (DRM '02), Washington, DC, November 2002

Several major record labels are adopting a new family of copy-prevention techniques intended to limit "casual" copying by compact disc owners using their personal computers. These employ deliberate data errors introduced into discs during manufacturing to cause incompatibility with PCs without affecting ordinary CD players. We examine three such recordings: A Tribute to Jim Reeves by Charley Pride, A New Day Has Come by Celine Dion, and More Music from The Fast and the Furious by various artists. In tests with different CD-ROM drives, operating systems, and playback software, we find these discs are unreadable in several widely-used applications as of July 2002. We analyze the specific technical differences between the modified recordings and standard audio CDs, and we consider repairs to hardware and software that would restore compatibility. We conclude that these schemes are harmful to legitimate CD owners and will not reduce illegal copying in the long term, so the music industry should reconsider their deployment.