An Efficient and Leakage-Resilient RSA-Based Authenticated Key Exchange Protocol with Tight Security Reduction

SeongHan SHIN
Kazukuni KOBARA
Hideki IMAI

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A    No.2    pp.474-490
Publication Date: 2007/02/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.2.474
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Security
authenticated key exchange,  passwords,  on-line and off-line dictionary attacks,  RSA,  leakage of stored secrets,  efficiency,  perfect forward secrecy,  

Full Text: PDF(321.4KB)>>
Buy this Article

Both mutual authentication and generation of session keys can be accomplished by an authenticated key exchange (AKE) protocol. Let us consider the following situation: (1) a client, who communicates with many different servers, remembers only one password and has insecure devices (e.g., mobile phones or PDAs) with very-restricted computing power and built-in memory capacity; (2) the counterpart servers have enormous computing power, but they are not perfectly secure against various attacks (e.g., virus or hackers); (3) neither PKI (Public Key Infrastructures) nor TRM (Tamper-Resistant Modules) is available. The main goal of this paper is to provide security against the leakage of stored secrets as well as to attain high efficiency on client's side. For those, we propose an efficient and leakage-resilient RSA-based AKE (RSA-AKE) protocol suitable for the above situation whose authenticity is based on password and another secret. In the extended model where an adversary is given access to the stored secret of client, we prove that its security of the RSA-AKE protocol is reduced tightly to the RSA one-wayness in the random oracle model. We also show that the RSA-AKE protocol guarantees several security properties (e.g., security of password, multiple sever scenario with only one password, perfect forward secrecy and anonymity). To our best knowledge, the RSA-AKE protocol is the most efficient, in terms of both computation costs of client and communication costs, over the previous AKE protocols of their kind (using password and RSA).