A bad randomness may cause catastrophic results in security; thus, it is of importance to make cryptographic systems secure against bad randomness. In this paper, we focus on a practical situation where an adversary is able to force participants in an authenticated key exchange (AKE) system to reuse the random values and the functions of these values, called related randomness attack (RRA). Following the existing randomness resetting security model of AKE and the RRA security model of public-key encryption, we present a model of RRA security for authenticated key exchange, as well as the necessary restrictions on the related randomness functions used to obtain the security definition. Then we show how a related randomness attack adversary breaks the security of some existing AKE protocols, and propose some constructions of RRA-secure authenticated key exchange in the random oracle model and standard model, respectively.
A bad randomness may cause catastrophic results in security; thus, it is of importance to make cryptographic systems secure against bad randomness. In this paper, we focus on a practical situation where an adversary is able to force participants in an authenticated key exchange (AKE) system to reuse the random values and the functions of these values, called related randomness attack (RRA). Following the existing randomness resetting security model of AKE and the RRA security model of public-key encryption, we present a model of RRA security for authenticated key exchange, as well as the necessary restrictions on the related randomness functions used to obtain the security definition. Then we show how a related randomness attack adversary breaks the security of some existing AKE protocols, and propose some constructions of RRA-secure authenticated key exchange in the random oracle model and standard model, respectively.
Abstract. We initiate the formal study on authenticated key exchange (AKE) under bad randomness. This could happen when (1) an adversary compromises the randomness source and hence directly controls the randomness of each AKE session; and (2) the randomness repeats in different AKE sessions due to reset attacks. We construct two formal security models, Reset-1 and Reset-2, to capture these two bad randomness situations respectively, and investigate the security of some widely used AKE protocols in these models by showing that they become insecure when the adversary is able to manipulate the randomness. On the positive side, we propose simple but generic methods to make AKE protocols secure in Reset-1 and Reset-2 models. The methods work in a modular way: first, we strengthen a widely used AKE protocol to achieve Reset-2 security, then we show how to transform any Reset-2 secure AKE protocol to a new one which also satisfies Reset-1 security.
Leakage attacks, including various kinds of side-channel attacks, allow an attacker to learn partial information about the internal secrets such as the secret key and the randomness of a cryptographic system. Designing a strong, meaningful, yet achievable security notion to capture practical leakage attacks is one of the primary goals of leakage-resilient cryptography. In this work, we revisit the modelling and design of authenticated key exchange (AKE) protocols with leakage resilience. We show that the prior works on this topic are inadequate in capturing realistic leakage attacks. To close this research gap, we propose a new security notion named leakage-resilient eCK model w.r.t. auxiliary inputs (AI-LR-eCK) for AKE protocols, which addresses the limitations of the previous models. Our model allows computationally hard-to-invert leakage of both the long-term secret key and the randomness, and also addresses a limitation existing in most of the previous models where the adversary is disallowed to make leakage queries during the challenge session. As another major contribution of this work, we present a generic framework for the construction of AKE protocols that are secure under the proposed AI-LR-eCK model. An instantiation based on the decision Diffie–Hellman (DDH) assumption in the standard model is also given to demonstrate the feasibility of our proposed framework.
Abstract. In this paper, we prove the security of the RSA-AKE protocol [9] in the random oracle model. The proof states that the RSA-AKE protocol is secure against an adversary who gets the client’s stored secret or the server’s RSA private key. 1 To our best knowledge, the RSA-AKE protocol is the most efficient among their kinds (i.e., RSA and password based AKE protocols). The other security properties and efficiency measurements of the RSA-AKE protocol remain the same as in [9]. 1 The protocol is the same as [9], but we corrected the security proof partially. The attacks appeared in [10] are no longer available in the proof since the adversary has access to either the client’s stored secret or the server’s private key, not both of them. 2 1 The Model and Security Definitions In this section we introduce an extended model building on [1, 5] and security definitions for the LR-AKE security and perfect forward secrecy. We denote by C and S two parties that participate in a key exchange protocol P. Each of them may have several instances called oracles involved in distinct, possibly concurrent, executions of P where we
Authenticated Key Exchange (AKE) is a cryptographic protocol to share a common session key among multiple parties. Usually, PKI-based AKE schemes are designed to guarantee secrecy of the session key and mutual authentication. However, in practice, there are many cases where mutual authentication is undesirable such as in anonymous networks like Tor and Riffle, or difficult to achieve due to the certificate management at the user level such as the Internet. Goldberg et al. formulated a model of anonymous one-sided AKE which guarantees the anonymity of the client by allowing only the client to authenticate the server, and proposed a concrete scheme. However, existing anonymous one-sided AKE schemes are only known to be secure in the random oracle model. In this paper, we propose generic constructions of anonymous one-sided AKE in the random oracle model and in the standard model, respectively. Our constructions allow us to construct the first post-quantum anonymous one-sided AKE scheme from isogenies in the standard model.
Secure channels can be realized by an authenticated key exchange (AKE) protocol that generates authenticated session keys between the involving parties. In [32], Shin et al., proposed a new kind of AKE (RSA-AKE) protocol whose goal is to provide high efficiency and security against leakage of stored secrets as much as possible. Let us consider more powerful attacks where an adversary completely controls the communications and the stored secrets (the latter is denoted by “replacement” attacks). In this paper, we first show that the RSA-AKE protocol [32] is no longer secure against such an adversary. The main contributions of this paper are as follows: (1) we propose an RSA-based leakage-resilient AKE (RSA-AKE2) protocol that is secure against active attacks as well as replacement attacks; (2) we prove that the RSA-AKE2 protocol is secure against replacement attacks based on the number theory results; (3) we show that it is provably secure in the random oracle model, by showing the reduction to the RSA one-wayness, under an extended model that covers active attacks and replacement attacks; (4) in terms of efficiency, the RSA-AKE2 protocol is comparable to [32] in the sense that the client needs to compute only one modular multiplication with pre-computation; and (5) we also discuss about extensions of the RSA-AKE2 protocol for several security properties (i.e., synchronization of stored secrets, privacy of client and solution to server compromise-impersonation attacks).
Abstract. An unresolved problem in research on authenticated key exchange (AKE) is to construct a secure protocol against advanced attacks such as key compromise impersonation and maximal exposure attacks without relying on random oracles. HMQV, a state of the art AKE protocol, achieves both efficiency and the strong security proposed by Krawczyk (we call it the CK + model), which includes resistance to advanced attacks. However, the security proof is given under the random oracle model. We propose a generic construction of AKE from a key encapsulation mechanism (KEM). The construction is based on a chosen-ciphertext secure KEM, and the resultant AKE protocol is CK + secure in the standard model. The construction gives the first CK + secure AKE protocols based on the hardness of integer factorization problem, code-based problems, or learning problems with errors. In addition, instantiations under the Diffie-Hellman assumption or its variant can be proved to have strong security without non-standard assumptions such as πPRF and KEA1. Furthermore, we extend the CK + model to identity-based (called the id-CK + model), and propose a generic construction of identity-based AKE (ID-AKE) based on identity-based KEM, which satisfies id-CK + security. The construction leads first strongly secure ID-AKE protocols under the hardness of integer factorization problem, or learning problems with errors.