RSA-Based Password-Authenticated Key Exchange, Revisited

SeongHan SHIN  Kazukuni KOBARA  Hideki IMAI  

IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.5   pp.1424-1438
Publication Date: 2008/05/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e91-d.5.1424
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Information and Communication System Security)
Category: Key Management
password authentication,  key exchange,  RSA,  on-line/off-line attacks,  e-residue attacks,  provable security,  

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

The RSA-based Password-Authenticated Key Exchange (PAKE) protocols have been proposed to realize both mutual authentication and generation of secure session keys where a client is sharing his/her password only with a server and the latter should generate its RSA public/private key pair (e,n),(d,n) every time due to the lack of PKI (Public-Key Infrastructures). One of the ways to avoid a special kind of off-line (so called e-residue) attacks in the RSA-based PAKE protocols is to deploy a challenge/response method by which a client verifies the relative primality of e and φ(n) interactively with a server. However, this kind of RSA-based PAKE protocols did not give any proof of the underlying challenge/response method and therefore could not specify the exact complexity of their protocols since there exists another security parameter, needed in the challenge/response method. In this paper, we first present an RSA-based PAKE (RSA-PAKE) protocol that can deploy two different challenge/response methods (denoted by Challenge/Response Method1 and Challenge/Response Method2). The main contributions of this work include: (1) Based on the number theory, we prove that the Challenge/Response Method1 and the Challenge/Response Method2 are secure against e-residue attacks for any odd prime e; (2) With the security parameter for the on-line attacks, we show that the RSA-PAKE protocol is provably secure in the random oracle model where all of the off-line attacks are not more efficient than on-line dictionary attacks; and (3) By considering the Hamming weight of e and its complexity in the RSA-PAKE protocol, we search for primes to be recommended for a practical use. We also compare the RSA-PAKE protocol with the previous ones mainly in terms of computation and communication complexities.