SPEKE

Last updated

SPEKE (Simple Password Exponential Key Exchange) is a cryptographic method for password-authenticated key agreement.

Contents

Description

The protocol consists of little more than a Diffie–Hellman key exchange where the Diffie-Hellman generator g is created from a hash of the password.

Here is one simple form of SPEKE:

  1. Alice and Bob agree to use an appropriately large and randomly selected safe prime p, as well as a hash function H().
  2. Alice and Bob agree on a shared password π.
  3. Alice and Bob both construct g = H(π)2 mod p. (Squaring makes g a generator of the prime order subgroup of the multiplicative group of integers modulo p.)
  4. Alice chooses a secret random integer a, then sends Bob ga mod p.
  5. Bob chooses a secret random integer b, then sends Alice gb mod p.
  6. Alice and Bob each abort if their received values are not in the range [2,p-2], to prevent small subgroup confinement attack.
  7. Alice computes K = (gb mod p)a mod p.
  8. Bob computes K = (ga mod p)b mod p.

Both Alice and Bob will arrive at the same value for K if and only if they use the same value for π. Once Alice and Bob compute the shared secret K they can use it in a key confirmation protocol to prove to each other that they know the same password π, and to derive a shared secret encryption key for sending secure and authenticated messages to each other. The use of a key confirmation protocol is optional, as specified in the IEEE P1363.2 and ISO/IEC 11770-4 standards.

Unlike unauthenticated Diffie-Hellman, SPEKE prevents man-in-the-middle attack by the incorporation of the password. An attacker who is able to read and modify all messages between Alice and Bob cannot learn the shared key K and cannot make more than one guess for the password in each interaction with a party that knows it.

In general, SPEKE can use any prime order group that is suitable for public key cryptography, including elliptic-curve cryptography. However, when SPEKE is realized by using Elliptic-curve cryptography, the protocol is essentially changed by requiring an additional primitive that must securely map a password onto a random point on the designated elliptic curve. (This primitive is called the IOP or Integer-to-Point function in IEEE P1363.2 and ISO/IEC 11770-4.)

History

SPEKE is one of the older and well-known protocols in the relatively new field of password-authenticated key exchange. It was first described by David Jablon in 1996. [1] In this publication Jablon also suggested a variant where, in step 2 of the protocol, g is calculated as g = gqS with a constant gq. However, this construction turned out to be insecure against dictionary attacks and was therefore not recommended anymore in a revised version of the paper. In 1997 Jablon refined and enhanced SPEKE with additional variations, including an augmented password-authenticated key agreement method called B-SPEKE. [2] A paper published by MacKenzie in 2001 presents a proof in the random oracle model that SPEKE is a secure PAKE protocol (using a somewhat relaxed definition) based on a variation of the Decision Diffie-Hellman assumption. [3] However, the proof treats the key confirmation function in SPEKE as mandatory, which is not how SPEKE is specified in the IEEE P1363.2 and ISO/IEC 11770-4 standards.

Since 1999, the protocol has been used by several companies in a variety of products, typically supplementing other cryptographic techniques.

In 2014, two attacks are identified against the SPEKE protocol as specified in the original Jablon's 1996 paper and in the IEEE P1363.2 (D26) and ISO/IEC 11770-4 (2006) standards. [4] The first attack allows an active attacker to impersonate a user without knowing the password by launching two parallel sessions with the victim. The second attack allows a man-in-the-middle attacker to manipulate the session key between two honest users without being detected. The first attack indicates a practical weakness of the protocol while the second attack has theoretical implications on security proofs of SPEKE. During the ISO/IEC JTC 1/SC 27 meeting in Mexico City in October 2014, the two attacks were discussed by the technical committee in ISO/IEC SC 27/Work Group 2, and it had been agreed that the SPEKE specification in ISO/IEC 11770-4 (2006) should be revised to address the identified issues. The proposed patch involves explicitly defining session identities, and including those identities into the key derivation function in a way that does not change the symmetry of the protocol. The patched SPEKE has been published in ISO/IEC 11770-4 (2017). [5] However, the SPEKE specification in IEEE P1363.2 remains unpatched.

Patents

U.S. Patent 6,226,383 describes several variations of the method. This patent expired in March 2017.

Standards

Standards that describe SPEKE include IEEE P1363.2 and ISO/IEC 11770-4. In the latest ISO/IEC 11770-4 (2017) standard, the SPEKE specification is revised from the previous one in ISO/IEC 11770-4 (2006) to address the two attacks reported by Hao and Shahandashti in 2014. [4]

Related Research Articles

<span class="mw-page-title-main">Diffie–Hellman key exchange</span> Method of exchanging cryptographic keys

Diffie–Hellman key exchange is a mathematical method of securely exchanging cryptographic keys over a public channel and was one of the first public-key protocols as conceived by Ralph Merkle and named after Whitfield Diffie and Martin Hellman. DH is one of the earliest practical examples of public key exchange implemented within the field of cryptography. Published in 1976 by Diffie and Hellman, this is the earliest publicly known work that proposed the idea of a private key and a corresponding public key.

A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key can be different sizes and varieties, but in all cases, the strength of the encryption relies on the security of the key being maintained. A key's security strength is dependent on its algorithm, the size of the key, the generation of the key, and the process of key exchange.

In cryptography, a key-agreement protocol is a protocol whereby two or more parties can agree on a cryptographic key in such a way that both influence the outcome. If properly done, this precludes undesired third parties from forcing a key choice on the agreeing parties. Protocols that are useful in practice also do not reveal to any eavesdropping party what key has been agreed upon.

Articles related to cryptography include:

<span class="mw-page-title-main">Key exchange</span> Cryptographic protocol enabling the sharing of a secret key over an insecure channel

Key exchange is a method in cryptography by which cryptographic keys are exchanged between two parties, allowing use of a cryptographic algorithm.

The Secure Remote Password protocol (SRP) is an augmented password-authenticated key exchange (PAKE) protocol, specifically designed to work around existing patents.

<span class="mw-page-title-main">Encrypted key exchange</span>

Encrypted Key Exchange is a family of password-authenticated key agreement methods described by Steven M. Bellovin and Michael Merritt. Although several of the forms of EKE in this paper were later found to be flawed, the surviving, refined, and enhanced forms of EKE effectively make this the first method to amplify a shared password into a shared key, where the shared key may subsequently be used to provide a zero-knowledge password proof or other functions.

MQV (Menezes–Qu–Vanstone) is an authenticated protocol for key agreement based on the Diffie–Hellman scheme. Like other authenticated Diffie–Hellman schemes, MQV provides protection against an active attacker. The protocol can be modified to work in an arbitrary finite group, and, in particular, elliptic curve groups, where it is known as elliptic curve MQV (ECMQV).

IEEE P1363 is an Institute of Electrical and Electronics Engineers (IEEE) standardization project for public-key cryptography. It includes specifications for:

In cryptography, a zero-knowledge password proof (ZKPP) is a type of zero-knowledge proof that allows one party to prove to another party that it knows a value of a password, without revealing anything other than the fact that it knows the password to the verifier. The term is defined in IEEE P1363.2, in reference to one of the benefits of using a password-authenticated key exchange (PAKE) protocol that is secure against off-line dictionary attacks. A ZKPP prevents any party from verifying guesses for the password without interacting with a party that knows it and, in the optimal case, provides exactly one guess in each interaction.

In cryptography, a password-authenticated key agreement method is an interactive method for two or more parties to establish cryptographic keys based on one or more party's knowledge of a password.

In cryptography, the interlock protocol, as described by Ron Rivest and Adi Shamir, is a protocol designed to frustrate eavesdropper attack against two parties that use an anonymous key exchange protocol to secure their conversation. A further paper proposed using it as an authentication protocol, which was subsequently broken.

In cryptography, forward secrecy (FS), also known as perfect forward secrecy (PFS), is a feature of specific key-agreement protocols that gives assurances that session keys will not be compromised even if long-term secrets used in the session key exchange are compromised. For HTTPS, the long-term secret is typically the private key of the server. Forward secrecy protects past sessions against future compromises of keys or passwords. By generating a unique session key for every session a user initiates, the compromise of a single session key will not affect any data other than that exchanged in the specific session protected by that particular key. This by itself is not sufficient for forward secrecy which additionally requires that a long-term secret compromise does not affect the security of past session keys.

In public-key cryptography, the Station-to-Station (STS) protocol is a cryptographic key agreement scheme. The protocol is based on classic Diffie–Hellman, and provides mutual key and entity authentication. Unlike the classic Diffie–Hellman, which is not secure against a man-in-the-middle attack, this protocol assumes that the parties have signature keys, which are used to sign messages, thereby providing security against man-in-the-middle attacks.

Elliptic-curve Diffie–Hellman (ECDH) is a key agreement protocol that allows two parties, each having an elliptic-curve public–private key pair, to establish a shared secret over an insecure channel. This shared secret may be directly used as a key, or to derive another key. The key, or the derived key, can then be used to encrypt subsequent communications using a symmetric-key cipher. It is a variant of the Diffie–Hellman protocol using elliptic-curve cryptography.

In cryptography, the socialist millionaire problem is one in which two millionaires want to determine if their wealth is equal without disclosing any information about their riches to each other. It is a variant of the Millionaire's Problem whereby two millionaires wish to compare their riches to determine who has the most wealth without disclosing any information about their riches to each other.

The Password Authenticated Key Exchange by Juggling is a password-authenticated key agreement protocol, proposed by Feng Hao and Peter Ryan. This protocol allows two parties to establish private and authenticated communication solely based on their shared (low-entropy) password without requiring a Public Key Infrastructure. It provides mutual authentication to the key exchange, a feature that is lacking in the Diffie–Hellman key exchange protocol.

The following outline is provided as an overview of and topical guide to cryptography:

In cryptography, a public key exchange algorithm is a cryptographic algorithm which allows two parties to create and share a secret key, which they can use to encrypt messages between themselves. The ring learning with errors key exchange (RLWE-KEX) is one of a new class of public key exchange algorithms that are designed to be secure against an adversary that possesses a quantum computer. This is important because some public key algorithms in use today will be easily broken by a quantum computer if such computers are implemented. RLWE-KEX is one of a set of post-quantum cryptographic algorithms which are based on the difficulty of solving certain mathematical problems involving lattices. Unlike older lattice based cryptographic algorithms, the RLWE-KEX is provably reducible to a known hard problem in lattices.

Algebraic Eraser (AE) is an anonymous key agreement protocol that allows two parties, each having an AE public–private key pair, to establish a shared secret over an insecure channel. This shared secret may be directly used as a key, or to derive another key that can then be used to encrypt subsequent communications using a symmetric key cipher. Algebraic Eraser was developed by Iris Anshel, Michael Anshel, Dorian Goldfeld and Stephane Lemieux. SecureRF owns patents covering the protocol and unsuccessfully attempted to standardize the protocol as part of ISO/IEC 29167-20, a standard for securing radio-frequency identification devices and wireless sensor networks.

References

  1. ↑ Jablon, David (October 1996). "Strong Password-Only Authenticated Key Exchange". ACM SIGCOMM Computer Communication Review. 26 (5): 5–26. CiteSeerX   10.1.1.57.4798 . doi:10.1145/242896.242897. S2CID   2870433.
  2. ↑ Jablon, David (20 June 1997). "Extended password key exchange protocols immune to dictionary attack". Proceedings of IEEE 6th Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises. Cambridge, MA, USA: IEEE Computer Society. pp. 248–255. CiteSeerX   10.1.1.30.8102 . doi:10.1109/ENABL.1997.630822. ISBN   978-0-8186-7967-4. S2CID   10568917.
  3. ↑ MacKenzie, Philip (2001-07-19). "On the Security of the SPEKE Password-Authenticated Key Exchange Protocol" . Retrieved 2008-03-22.
  4. 1 2 F. Hao, S.F. Shahandashti. The SPEKE Protocol Revisited. Proceedings of the 1st International Conference on Security Standardisation Research, 2014.
  5. ↑ "Online Browsing Platform (OBP)". Archived from the original on 2012-08-21.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.