LR-AKE

(Leakage-Resilient Authenticated Key Exchange)

LR-AKE is a NEW authentication protocol where a user and a server authenticate each other and generate session keys in order to protect the subsequent communication channels between them. You can also see our papers.

LR-AKE Strong forward secrecy1 Replacement attack2 Server compromise impersonation attack2
DL-based [SKI03,05] Yes (with Secret-Values Update) Not possible Not considered
DL-based [?] Yes Not possible Not possible
RSA-based [SKI07] Yes Not considered Not considered
RSA-based [SKI10] Yes Not possible Not possible (with Section 6.4)
1: See below
2: An attacker obtains server's stored secrets and then tries to impersonate the user, not the server. For more details, see [SKI10]. Another attack related to server compromise is server compromise server impersonation (for short, SCSI) attack where an attacker obtains server's stored secrets and then tries to impersonate the server. It is impossible for any AKE protocol to prevent the SCSI attack. However, DL-based LR-AKE provides security against the SCSI attack if the honest user and the honest server runs the LR-AKE protocol before the attacker impersonates the user or the server.

Notice that recent LR-AKE protocols, secure in relative leakage model [ADW09], are different from ours.

Relative leakage model considers side-channel attacks or cold-boot attacks where an attacker can get partial information about secrets. The constraint of this model is that the remaining information (after the partial leakage) about secrets should be at least in the security parameter (e.g., 80-bits). Contrary to relative leakage model, LR-AKE considers a different situation where an attacker can get all information about stored secrets. In such situation, LR-AKE is secure because the only possible attacks is on-line dictioinary attacks (i.e., the remaining secret information is a short password, remembered by the user).

[ADW09] J. Alwen, Y. Dodis, and D. Wichs, "“Survey: Leakage Resilience and the Bounded Retrieval Model", 2009

Motivation

Most of applications and services provided through open networks (e.g., the Internet) require authentication and confidentiality for the fundamental security goals. These security goals can be achieved by using an authenticated key exchange (called, AKE) protocol that has been studied for several decades in cryptographic community. In the case of 2-party (user and server) setting, an AKE protocol allows a user to authenticate with a server as well as to generate cryptographically-secure (i.e., high-entropy) session keys, only if the authentication is successful, which will be used to protect the subsequent communications between the two parties. Some AKE protocols can be found in EAP, SSL/TLS, IKE and IEEE P1363/1363.2.

The security of typical AKE protocols is based on the assumption that the stored secrets/data (related to authentication) are completely secure. However, what happens if these secrets/data are compromised or leaked to an attacker? Compromises or leakages of stored secrets/data render the existing AKE protocols insecure even if two or more factor authentication is used (see below). More seriously, such compromises and leakages are common in the real world [Rob08]:

  • No perfect TRM/TPM
  • Leakage vis lost/stolen devices (e.g., PCs, mobile/smart phones, PDA, USB memory)
  • Social engineering attacks (e.g., Phishing) or keylogger
  • Server administrator's misconduct, virus etc.

How many passwords do you remember? Another realistic problem is that a user can NOT remember many distinct passwords for different servers. The compromises or leakages of stored secrets/data may result in a catastrophe if a user registers one (or similar) password to many different servers.

An obvious solution is as follows: keep your stored secrets/data completely secure and do not register the same (or similar) password to different servers at all.

Instead of the obvious (but impractical) solution, we take a cryptographic approach for the above realistic problems.

[Rob08] R. Robert, “CSI Computer Crime & Security Survey”, 2008

Concept of LR-AKE

A unique 2-factor AKE



LR-AKE provides a maximum level of security against active attacks as well as leakage of stored secrets/data. In addition, a user remembers only one short password for different servers.


Comparison


In table, "OK" means secure and "NO" insecure. Also, "leakage from client/server" indicates whether or not a user's password in each protocol is secure against an attacker, who gets the stored secrets from client/server.


Another advantages

  • Serial on-line dictionary attacks are not possible without any leakage of stored secrets from client: Though on-line dictionary attacks are possible with leaked secrets from client, they can NOT be continued if an honest user successfully authenticates with the server
  • Efficiency in terms of computation and communication costs
  • Strong forward secrecy: Even if computationally-hard (e.g., DL/RSA) problems are broken in future, previous communications remain hidden as long as no leakage of stored secrets from both sides happens
  • Automatic revocation of already-leaked secrets
  • Easy setup, and no management of public-key certificates

Extension to Data Security

Data encryption is NOT a fundamental solution to compromises or leakages: PW-derived encryption key is insecure against off-line dictionary attacks.

How to protect data key securely?

On-line data key recovery using LR-AKE: single mode and cluster mode



In particular, cluster mode provides availability of data key: Any pair can recover the key even in the case of one party's total break-down.

Applications

Any authentication and/or data storage service

  • Login to remote server/intranet/hotspot, …
  • SSH, VPN, authentication for thin client, …
  • Web mail/shopping, internet banking, …
  • Identity management, SSO on client side, …
  • Credential-retrieval system, …
  • NAS, cloud storage system, …
  • On-line distributed storage system, …