International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Tadayoshi Kohno

Publications

Year
Venue
Title
2015
EPRINT
2008
JOFC
2006
EUROCRYPT
2006
EPRINT
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.
2006
EPRINT
Stateful Public-Key Cryptosystems: How to Encrypt with One 160-bit Exponentiation
Mihir Bellare Tadayoshi Kohno Victor Shoup
We show how to significantly speed-up the encryption portion of some public-key cryptosystems by the simple expedient of allowing a sender to maintain state that is re-used across different encryptions. In particular we present stateful versions of the DHIES and Kurosawa-Desmedt schemes that each use only one exponentiation to encrypt, as opposed to two and three respectively in the original schemes, yielding the fastest discrete-log based public-key encryption schemes known in the random-oracle and standard models respectively. The schemes are proven to meet an appropriate extension of the standard definition of IND-CCA security that takes into account novel types of attacks possible in the stateful setting.
2005
CRYPTO
2005
EPRINT
Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions
We identify and fill some gaps with regard to consistency (the extent to which false positives are produced) for public-key encryption with keyword search (PEKS). We define computational and statistical relaxations of the existing notion of perfect consistency, show that the scheme of Boneh et al. in Eurocrypt 2004 is computationally consistent, and provide a new scheme that is statistically consistent. We also provide a transform of an anonymous IBE scheme to a secure PEKS scheme that, unlike the previous one, guarantees consistency. Finally, we suggest three extensions of the basic notions considered here, namely anonymous HIBE, public-key encryption with temporary keyword search, and identity-based encryption with keyword search.
2005
EPRINT
Herding Hash Functions and the Nostradamus Attack
John Kelsey Tadayoshi Kohno
In this paper, we develop a new attack on Damg{\aa}rd-Merkle hash functions, called the \emph{herding attack}, in which an attacker who can find many collisions on the hash function by brute force can first provide the hash of a message, and later ``herd'' any given starting part of a message to that hash value by the choice of an appropriate suffix. We introduce a new property which hash functions should have--Chosen Target Forced Prefix (CTFP) preimage resistance--and show the distinction between Damg{\aa}rd-Merkle construction hashes and random oracles with respect to this property. We describe a number of ways that violation of this property can be used in arguably practical attacks on real-world applications of hash functions. An important lesson from these results is that hash functions susceptible to collision-finding attacks, especially brute-force collision-finding attacks, cannot in general be used to prove knowledge of a secret value
2005
EPRINT
Key Regression: Enabling Efficient Key Distribution for Secure Distributed Storage
Kevin Fu Seny Kamara Tadayoshi Kohno
The Plutus file system introduced the notion of key rotation as a means to derive a sequence of temporally-related keys from the most recent key. In this paper we show that, despite natural intuition to the contrary, key rotation schemes cannot generically be used to key other cryptographic objects; in fact, keying an encryption scheme with the output of a key rotation scheme can yield a composite system that is insecure. To address these shortcomings, we introduce a new cryptographic object called a key regression scheme, and we propose three constructions that are provably secure under standard cryptographic assumptions. We implement key regression in a secure file system and empirically show that key regression can significantly reduce the bandwidth requirements of a content publisher under realistic workloads using lazy revocation. Our experiments also serve as the first empirical evaluation of either a key rotation or key regression scheme.
2004
EUROCRYPT
2004
FSE
2004
FSE
2004
EPRINT
New Security Proofs for the 3GPP Confidentiality and Integrity Algorithms
Tetsu Iwata Tadayoshi Kohno
This paper analyses the 3GPP confidentiality and integrity schemes adopted by Universal Mobile Telecommunication System, an emerging standard for third generation wireless communications. The schemes, known as $f8$ and $f9$, are based on the block cipher KASUMI. Although previous works claim security proofs for $f8$ and $f9'$, where $f9'$ is a generalized versions of $f9$, it was recently shown that these proofs are incorrect. Moreover, Iwata and Kurosawa (2003) showed that it is \emph{impossible} to prove $f8$ and $f9'$ secure under the standard PRP assumption on the underlying block cipher. We address this issue here, showing that it is possible to prove $f8'$ and $f9'$ secure if we make the assumption that the underlying block cipher is a secure PRP-RKA against a certain class of related-key attacks; here $f8'$ is a generalized version of $f8$. Our results clarify the assumptions necessary in order for $f8$ and $f9$ to be secure and, since no related-key attacks are known against the full eight rounds of KASUMI, lead us to believe that the confidentiality and integrity mechanisms used in real 3GPP applications are secure.
2004
EPRINT
Analysis of the WinZip encryption method
Tadayoshi Kohno
WinZip is a popular compression utility for Microsoft Windows computers, the latest version of which is advertised as having "easy-to-use AES encryption to protect your sensitive data." We exhibit several attacks against WinZip's new encryption method, dubbed "AE-2" or "Advanced Encryption, version two." We then discuss secure alternatives. Since at a high level the underlying WinZip encryption method appears secure (the core is exactly Encrypt-then-Authenticate using AES-CTR and HMAC-SHA1), and since one of our attacks was made possible because of the way that WinZip Computing, Inc.~decided to fix a different security problem with its previous encryption method AE-1, our attacks further underscore the subtlety of designing cryptographically secure software.
2003
EUROCRYPT
2003
FSE
2003
FSE
2003
EPRINT
Hash Function Balance and its Impact on Birthday Attacks
Mihir Bellare Tadayoshi Kohno
Textbooks tell us that a birthday attack on a hash function $h$ with range size $r$ requires $r^{1/2}$ trials (hash computations) to find a collision. But this is misleading, being true only if $h$ is regular, meaning all points in the range have the same number of pre-images under $h$; if $h$ is not regular, \textit{fewer} trials may be required. But how much fewer? This paper addresses this question by introducing a measure of the ``amount of regularity'' of a hash function that we call its balance, and then providing estimates of the success-rate of the birthday attack as a function of the balance of the hash function being attacked. In particular, we will see that the number of trials to find a collision can be significantly less than $r^{1/2}$ for hash functions of low balance. This leads us to examine popular design principles, such as the MD (Merkle-Damg{\aa}rd) transform, from the point of view of balance preservation, and to mount experiments to determine the balance of popular hash functions.
2003
EPRINT
CWC: A high-performance conventional authenticated encryption mode
Tadayoshi Kohno John Viega Doug Whiting
We introduce CWC, a new block cipher mode of operation for protecting both the privacy and the authenticity of encapsulated data. CWC is currently the only such mode having all five of the following properties: provable security, parallelizability, high performance in hardware, high performance in software, and no intellectual property concerns. We believe that having all five of these properties makes CWC a powerful tool for use in many performance-critical cryptographic applications. CWC is also the only appropriate solution for some applications; e.g., standardization bodies like the IETF and NIST prefer patent-free modes, and CWC is the only such mode capable of processing data at 10Gbps in hardware, which will be important for future IPsec (and other) network devices. As part of our design, we also introduce a new parallelizable universal hash function optimized for performance in both hardware and software.
2003
EPRINT
Building Secure Cryptographic Transforms, or How to Encrypt and MAC
Tadayoshi Kohno Adriana Palacio John Black
We describe several notions of ``cryptographic transforms,'' symmetric schemes designed to meet a variety of privacy and authenticity goals. We consider goals, such as replay-avoidance and in-order packet delivery, that have not been fully addressed in previous works in this area. We then provide an analysis of possible ways to combine standard encryption and message authentication schemes in order to provably meet these goals. Our results further narrow the gap between the provable-security results from the theoretical community and the needs of developers who implement real systems.
2002
EPRINT
Related-Key and Key-Collision Attacks Against RMAC
Tadayoshi Kohno
In [JJV02] Jaulmes, Joux, and Valette propose a new randomized message authentication scheme, called RMAC, which NIST is currently in the process of standardizing [NIS02]. In this work we present several attacks against RMAC. The attacks are based on a new protocol-level related-key attack against RMAC and can be considered variants of Biham's key-collision attack [Bih02]. These attacks provide insights into the RMAC design. We believe that the protocol-level related-key attack is of independent interest.
2000
FSE

Program Committees

Eurocrypt 2008