International Association for Cryptologic Research

International Association
for Cryptologic Research


Anton Mityagin


Stronger Security of Authenticated Key Exchange
In this paper we study security definitions for authenticated key exchange (AKE) protocols. We observe that there are several families of attacks on AKE protocols that lie outside the boundary of the current class of security definitions. In an attempt to bring these attacks within the scope of analysis we extend the AKE security definition to provide greater powers to the adversary. We provide a general framework for defining AKE security, which we call strong AKE security, such that existing security definitions occur as instances of the framework. We then introduce NAXOS, a new two-pass AKE protocol, and prove that it is secure in this stronger definition. In addition, we formulate a notion of ephemeral secret key which captures all ephemeral information used in session establishment. We demonstrate the importance of this formulation by showing that a secure AKE protocol SIG-DH can become vulnerable when instantiated with signature schemes which are insecure against revelation of the secret random bits used in the signature generation.
Analysis of the SPV Secure Routing Protocol: Weaknesses and Lessons
We analyze a secure routing protocol, Secure Path Vector (SPV), proposed in SIGCOMM 2004. SPV aims to provide authenticity for route announcements in the Border Gateway Protocol (BGP) using an efficient alternative to ordinary digital signatures, called constant-time signatures. Today, SPV is often considered the best cryptographic defense for BGP. We find subtle flaws in the design of SPV which lead to attacks that can be mounted by 60% of Autonomous Systems in the Internet. In addition, we study several of SPV's design decisions and assumptions and highlight the requirements for security of routing protocols. In light of our analysis, we reexamine the need for constant-time signatures and find that certain standard digital signature schemes can provide the same level of efficiency for route authenticity.
Hard Instances of the Constrained Discrete Logarithm Problem
Ilya Mironov Anton Mityagin Kobbi Nissim
The discrete logarithm problem (DLP) generalizes to the constrained DLP, where the secret exponent $x$ belongs to a set known to the attacker. The complexity of generic algorithms for solving the constrained DLP depends on the choice of the set. Motivated by cryptographic applications, we study sets with succinct representation for which the constrained DLP is hard. We draw on earlier results due to Erd\"os et~al. and Schnorr, develop geometric tools such as generalized Menelaus' theorem for proving lower bounds on the complexity of the constrained DLP, and construct sets with succinct representation with provable non-trivial lower bounds.
Append-Only Signatures
We present a new primitive--Append-only Signatures (AOS)--with the property that any party given an AOS signature aossig[M_1] on message M_1 can compute aossig[M_1||M_2] for any message M_2, where M_1||M_2 is the concatenation of M_1 and M_2. We define the security of AOS, present concrete AOS schemes, and prove their security under standard assumptions. In addition, we find that despite its simple definition, AOS is equivalent to Hierarchical Identity-based Signatures (HIBS) through efficient and security-preserving reductions. Finally, we show direct applications of AOS to problems in network security. Our investigations indicate that AOS is both useful in practical applications and worthy of further study as a cryptographic primitive.
Security Analysis of KEA Authenticated Key Exchange Protocol
Kristin E. Lauter Anton Mityagin
KEA is a Diffie-Hellman based key-exchange protocol developed by NSA which provides mutual authentication for the parties. It became publicly available in 1998 and since then it was neither attacked nor proved to be secure. We analyze the security of KEA and find that the original protocol is susceptible to a class of attacks. On the positive side, we present a simple modification of the protocol which makes KEA secure. We prove that the modified protocol, called KEA+, satisfies the strongest security requirements for authenticated key-exchange and that it retains some security even if a secret key of a party is leaked. Our security proof is in the random oracle model and uses the Gap Diffie-Hellman assumption. Finally, we show how to add a key confirmation feature to KEA+ (we call the version with key confirmation KEA+C) and discuss the security properties of KEA+C.
The Power of Verification Queries in Message Authentication and Authenticated Encryption
Mihir Bellare Oded Goldreich Anton Mityagin
This paper points out that, contrary to popular belief, allowing a message authentication adversary multiple verification attempts towards forgery is NOT equivalent to allowing it a single one, so that the notion of security that most message authentication schemes are proven to meet does not guarantee their security in practice. We then show, however, that the equivalence does hold for STRONG unforgeability. Based on this we recover security of popular classes of message authentication schemes such as MACs (including HMAC and PRF-based MACs) and CW-schemes. Furthermore, in many cases we do so with a TIGHT security reduction, so that in the end the news we bring is surprisingly positive given the initial negative result. Finally, we show analogous results for authenticated encryption.