Provably Secure Subsitution of Cryptographic Tools
Many cryptographic protocols secure against malicious players use specially designed cryptographic tools. Essentially, these special tools function much like less-expensive tools, but give extra `powers' to a reduction or simulation algorithm. Using these powers, cryptographers can construct a proof of security using standard techniques. However, these powers are not available to either the honest parties or the adversary. In a large class of protocols, by replacing the expensive, specially designed cryptographic tool with a corresponding less-expensive tool, we can improve the protocol's efficiency without changing the functionality available to either the adversary or the honest parties. The key motivating question we address in this paper is whether the new, `substituted' protocol is still secure. We introduce a framework for reasoning about this question. Our framework uses translators: special purpose oracles that map outputs of one cryptographic tool to corresponding outputs of a different tool. Translators are similar to, but generally weaker than, the ``angels'' of Prabhakaran and Sahai. We introduce the notion of substitution-friendly protocols and show that such protocols remain secure after substitution in our framework. We also leverage existing proofs of security; there is no need to re-prove security from scratch. We demonstrate our framework with a non-interactive non-malleable bit commitment protocol.
Tamper-Evident, History-Independent, Subliminal-Free Data Structures on PROM Storage -or- How to Store Ballots on a Voting Machine
We enumerate requirements and give constructions for the vote storage unit of an electronic voting machine. In this application, the record of votes must survive even an unexpected failure of the machine; hence the data structure should be durable. At the same time, the order in which votes are cast must be hidden to protect the privacy of voters, so the data structure should be history-independent. Adversaries may try to surreptitiously add or delete votes from the storage unit after the election has concluded, so the storage should be tamper-evident. Finally, we must guard against an adversarial voting machine's attempts to mark ballots through the representation of the data structure, so we desire a subliminal-free representation. We leverage the properties of Programmable Read Only Memory (PROM), a special kind of write-once storage medium, to meet these requirements. We give constructions for data structures on PROM storage that simultaneously satisfy all our desired properties. Our techniques can significantly reduce the need to verify code running on a voting machine.
From Weak to Strong Watermarking
The informal goal of a watermarking scheme is to ``mark'' a digital object, such as a picture or video, in such a way that it is difficult for an adversary to remove the mark without destroying the content of the object. Although there has been considerable work proposing and breaking watermarking schemes, there has been little attention given to the formal security goals of such a scheme. In this work, we provide a new complexity-theoretic definition of security for watermarking schemes. We describe some shortcomings of previous attempts at defining watermarking security, and show that security under our definition also implies security under previous definitions. We also propose two weaker security conditions that seem to capture the security goals of practice-oriented work on watermarking and show how schemes satisfying these weaker goals can be strengthened to satisfy our definition.
Security and Privacy Issues in E-passports
Within the next year, travelers from dozens of nations may be carrying a new form of passport in response to a mandate by the United States government. The e-passport, as it is sometimes called, represents a bold initiative in the deployment of two new technologies: Radio-Frequency Identification (RFID) and biometrics. Important in their own right, e-passports are also the harbinger of a wave of next-generation ID cards: several national governments plan to deploy identity cards integrating RFID and biometrics for domestic use. We explore the privacy and security implications of this impending worldwide experiment in next-generation authentication technology. We describe privacy and security issues that apply to e-passports, then analyze these issues in the context of the International Civil Aviation Organization (ICAO) standard for e-passports.
A Scalable, Delegatable Pseudonym Protocol Enabling Ownership Transfer of RFID Tags
The ability to link two different sightings of the same Radio Frequency Identification (RFID) tag enables invasions of privacy. The problem is aggravated when an item, and the tag attached to it, changes hands during the course of its lifetime. After such an ownership transfer, the new owner should be able to read the tag but the old owner should not. We address these issues through an RFID pseudonym protocol. Each time it is queried, the RFID tag emits a different pseudonym using a pseudo-random function. Without consent of a special Trusted Center that shares secrets with the tag, it is infeasible to map the pseudonym to the tag's real identity. We present a scheme for RFID pseudonyms that works with legacy, untrusted readers, requires only one message from tag to reader, and is scalable: decoding tag pseudonyms takes work logarithmic in the number of tags. Our scheme further allows for time-limited delegation, so that we can give an RFID reader the power to disambiguate a limited number of pseudonyms without further help from the Trusted Center. We show how RFID pseudonyms facilitate the transfer of ownership of RFID tags between mutually distrustful parties. Our scheme requires only limited cryptographic functionality from the tag: we need a pseudo-random function (PRF) and the ability to update tag state or to generate random numbers. Tag storage and communication requirements are modest: we give example parameters for a deployment of one million tags in which each tag stores only $128$ bits, makes $6$ PRF evaluations, and sends $158$ bits each time it is read.
The Program Counter Security Model: Automatic Detection and Removal of Control-Flow Side Channel Attacks
We introduce new methods for detecting control-flow side channel attacks, transforming C source code to eliminate such attacks, and checking that the transformed code is free of control-flow side channels. We model control-flow side channels with a program counter transcript, in which the value of the program counter at each step is leaked to an adversary. The program counter transcript model captures a class of side channel attacks that includes timing attacks and error disclosure attacks. We further show that the model formalizes previous ad hoc approaches to preventing side channel attacks. We then give a dynamic testing procedure for finding code fragments that may reveal sensitive information by key-dependent behavior, and we show our method finds side channel vulnerabilities in real implementations of IDEA and RC5, in binary modular exponentiation, and in the lsh implementation of the ssh protocol. Further, we propose a generic source-to-source transformation that produces programs provably secure against control-flow side channel attacks. We implemented this transform for C together with a static checker that conservatively checks x86 assembly for violations of program counter security; our checker allows us to compile with optimizations while retaining assurance the resulting code is secure. We then measured our technique's effect on the performance of binary modular exponentiation and real-world implementations in C of RC5 and IDEA: we found it has a performance overhead of at most 5X and a stack space overhead of at most 2X. Our approach to side channel security is practical, generally applicable, and provably secure against an interesting class of side channel attacks.
Generic On-Line/Off-Line Threshold Signatures
We propose on-line/off-line threshold signature schemes, in which the bulk of signature computation can take place ``off-line" during lulls in service requests. Such precomputation can help systems using threshold signatures quickly respond to requests. For example, tests of the Pond distributed file system showed that computation of a threshold RSA signature consumes roughly 86% of the time required to service writes to small files. Because a large number of writes in file systems are for small files, threshold signatures form a performance bottleneck in Pond and similar systems. We apply the ``hash-sign-switch" paradigm of Shamir and Tauman and the distributed key generation protocol of Gennaro et al. to convert any existing secure threshold digital signature scheme into a threshold on-line/off-line signature scheme. Our construction is fully distributed and requires no trusted dealers. We show that the straightforward attempt at proving security of the resulting construction runs into a subtlety that does not arise for Shamir and Tauman's construction. We resolve the subtlety and prove our signature scheme secure against a static adversary in the partially synchronous communication model under the one-more-discrete-logarithm assumption. The on-line phase of our scheme is efficient: computing a signature takes one round of communication and a few modular multiplications in the common case.
- Jacob Appelbaum (1)
- Chris Crutchfield (2)
- Craig Gentry (1)
- Nicholas J. Hopper (2)
- Ari Juels (1)
- Lea Kissner (1)
- Tadayoshi Kohno (1)
- Arjen K. Lenstra (1)
- Dag Arne Osvik (1)
- Matt Piotrowski (1)
- Zulfikar Ramzan (1)
- Naveen Sastry (1)
- David Schultz (1)
- Andrea Soppera (1)
- Alexander Sotirov (1)
- Marc Stevens (1)
- David Turner (2)
- David Wagner (8)
- Benne de Weger (1)