Misplaced Pages

#552447

65-492: 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: 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

130-457: A Sophie Germain prime q is sometimes used to calculate p = 2 q + 1 , called a safe prime , since the order of G is then only divisible by 2 and q . Sometimes g is chosen to generate the order q subgroup of G , rather than G , so that the Legendre symbol of g never reveals the low order bit of a . A protocol using such a choice is for example IKEv2 . The generator g is often

195-625: A and b respectively, with public keys A and B , as well as the ephemeral key pairs x, X and y, Y . Then protocol is: The long term public keys need to be transferred somehow. That can be done beforehand in a separate, trusted channel, or the public keys can be encrypted using some partial key agreement to preserve anonymity. For more of such details as well as other improvements like side channel protection or explicit key confirmation , as well as early messages and additional password authentication, see e.g. US patent "Advanced modular handshake for key agreement and optional authentication". X3DH

260-648: A certificate authority , are one of the primary mechanisms used for secure web traffic (including HTTPS , SSL or Transport Layer Security protocols). Other specific examples are MQV , YAK and the ISAKMP component of the IPsec protocol suite for securing Internet Protocol communications. However, these systems require care in endorsing the match between identity information and public keys by certificate authorities in order to work properly. Hybrid systems use public-key cryptography to exchange secret keys, which are then used in

325-720: A denial-of-service attack (DoS) against the protocol variants use ephemeral keys, called D(HE)at attack. The attack exploits that the Diffie–Hellman key exchange allows attackers to send arbitrary numbers that are actually not public keys, triggering expensive modular exponentiation calculations on the victim's side. Another CVEs released disclosed that the Diffie–Hellman key exchange implementations may use long private exponents ( CVE-2022-40735 ) that arguably make modular exponentiation calculations unnecessarily expensive or may unnecessary check peer's public key ( CVE-2024-41996 ) has similar resource requirement as key calculation using

390-443: A given only g , p and g mod p . Such a problem is called the discrete logarithm problem . The computation of g mod p is known as modular exponentiation and can be done efficiently even for large numbers. Note that g need not be large at all, and in practice is usually a small integer (like 2, 3, ...). The chart below depicts who knows what, again with non-secret values in blue , and secret values in red . Here Eve

455-475: A shared secret key over an insecure channel . This key can then be used to encrypt subsequent communications using a symmetric-key cipher . Diffie–Hellman is used to secure a variety of Internet services. However, research published in October 2015 suggests that the parameters in use for many DH Internet applications at that time are not strong enough to prevent compromise by very well-funded attackers, such as

520-553: A Diffie–Hellman agreement as follows, with all operations taken to be modulo p : An eavesdropper has been able to see g mod p , g mod p , g mod p , g mod p , g mod p , and g mod p , but cannot use any combination of these to efficiently reproduce g mod p . To extend this mechanism to larger groups, two basic principles must be followed: These principles leave open various options for choosing in which order participants contribute to keys. The simplest and most obvious solution

585-410: A handful of groups that are of order 1024 bits or less. By precomputing the first three steps of the number field sieve for the most common groups, an attacker need only carry out the last step, which is much less computationally expensive than the first three steps, to obtain a specific logarithm. The Logjam attack used this vulnerability to compromise a variety of Internet services that allowed

650-419: A key) in a manner that is both private and integrity-assured. These are designed to resist man-in-the-middle and other active attacks on the password and the established keys. For example, DH- EKE , SPEKE , and SRP are password-authenticated variations of Diffie–Hellman. If one has an integrity-assured way to verify a shared key over a public channel, one may engage in a Diffie–Hellman key exchange to derive

715-403: A long exponent. An attacker can exploit both vulnerabilities together. The number field sieve algorithm, which is generally the most effective in solving the discrete logarithm problem , consists of four computational steps. The first three steps only depend on the order of the group G, not on the specific number whose finite log is desired. It turns out that much Internet traffic uses one of

SECTION 10

#1733085938553

780-602: 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

845-507: 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.) 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. In this publication Jablon also suggested a variant where, in step 2 of

910-702: A point on an elliptic curve instead of as an integer modulo n. Variants using hyperelliptic curves have also been proposed. The supersingular isogeny key exchange is a Diffie–Hellman variant that was designed to be secure against quantum computers , but it was broken in July 2022. The used keys can either be ephemeral or static (long term) key, but could even be mixed, so called semi-static DH. These variants have different properties and hence different use cases. An overview over many variants and some also discussions can for example be found in NIST SP 800-56A. A basic list: It

975-471: A pre-shared key), it is impossible to create an authenticated session key. The session key may be generated via: key transport, key agreement and hybrid. If there is no trusted third party, then the cases of key transport and hybrid session key generation are indistinguishable. SKA is concerned with protocols in which the session key is established using only symmetric primitives. Anonymous key exchange, like Diffie–Hellman, does not provide authentication of

1040-518: 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. 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

1105-471: A protocol is the Secure Remote Password protocol . Key-agreement protocol In cryptography, a key-agreement protocol is a protocol whereby two (or more) parties generate a cryptographic key as a function of information provided by each honest party so that no party can predetermine the resulting value. In particular, all honest participants influence the outcome. A key-agreement protocol

1170-465: A server, which Alice downloads and verifies the signature on. Alice then initiates the exchange to Bob. The OPK is optional. Diffie–Hellman key agreement is not limited to negotiating a key shared by only two participants. Any number of users can take part in an agreement by performing iterations of the agreement protocol and exchanging intermediate data (which does not itself need to be kept secret). For example, Alice, Bob, and Carol could participate in

1235-464: A shared key is. Exponential key exchange in and of itself does not specify any prior agreement or subsequent authentication between the participants. It has thus been described as an anonymous key agreement protocol. Symmetric Key Agreement (SKA) is a method of key-agreement that uses solely symmetric cryptography and cryptographic hash functions as cryptographic primitives . It is related to Symmetric Authenticated Key Exchange. SKA may assume

1300-490: A shared key must be done in a manner that is private and integrity-assured. Historically, this was achieved by physical means, such as by using a trusted courier . An example of a SKA protocol is the Needham-Schroeder Symmetric Key Protocol . It establishes a  session key  between two parties on the same network , using a server as a trusted third party. The original Needham-Schroeder protocol

1365-472: A short-term shared key, and then subsequently authenticate that the keys match. One way is to use a voice-authenticated read-out of the key, as in PGPfone . Voice authentication, however, presumes that it is infeasible for a man-in-the-middle to spoof one participant's voice to the other in real-time, which may be an undesirable assumption. Such protocols may be designed to work with even a small public value, such as

SECTION 20

#1733085938553

1430-444: A small integer such as 2. Because of the random self-reducibility of the discrete logarithm problem a small g is equally secure as any other generator of the same group. If Alice and Bob use random number generators whose outputs are not completely random and can be predicted to some extent, then it is much easier to eavesdrop. In the original description, the Diffie–Hellman exchange by itself does not provide authentication of

1495-427: A symmetric-key cryptography systems. Most practical applications of cryptography use a combination of cryptographic functions to implement an overall system that provides all of the four desirable features of secure communications (confidentiality, integrity, authentication, and non-repudiation). Password-authenticated key agreement protocols require the separate establishment of a password (which may be smaller than

1560-431: 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. 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

1625-409: Is prime , and g is a primitive root modulo p . These two values are chosen in this way to ensure that the resulting shared secret can take on any value from 1 to p –1. Here is an example of the protocol, with non-secret values in blue , and secret values in red . Both Alice and Bob have arrived at the same values because under mod p, More specifically, Only a and b are kept secret. All

1690-451: Is a mathematical method of securely generating a symmetric cryptographic key 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

1755-440: Is a more general description of the protocol: Both Alice and Bob are now in possession of the group element g = g , which can serve as the shared secret key. The group G satisfies the requisite condition for secure communication as long as there is no efficient algorithm for determining g given g , g , and g . For example, the elliptic curve Diffie–Hellman protocol is a variant that represents an element of G as

1820-417: Is a specialisation of a key-exchange protocol. At the end of the agreement, all parties share the same key. A key-agreement protocol precludes undesired third parties from forcing a key choice on the agreeing parties. A secure key agreement can ensure confidentiality and data integrity in communications systems, ranging from simple messaging applications to complex banking transactions. Secure agreement

1885-434: Is an eavesdropper – she watches what is sent between Alice and Bob, but she does not alter the contents of their communications. Now s is the shared secret key and it is known to both Alice and Bob, but not to Eve. Note that it is not helpful for Eve to compute AB , which equals g mod p . Note: It should be difficult for Alice to solve for Bob's private key or for Bob to solve for Alice's private key. If it

1950-572: Is defined relative to a security model, for example the Universal Model. More generally, when evaluating protocols, it is important to state security goals and the security model. For example, it may be required for the session key to be authenticated . A protocol can be evaluated for success only in the context of its goals and attack model. An example of an adversarial model is the Dolev-Yao model . In many key exchange systems, one party generates

2015-472: Is large enough. An efficient algorithm to solve the discrete logarithm problem would make it easy to compute a or b and solve the Diffie–Hellman problem, making this and many other public key cryptosystems insecure. Fields of small characteristic may be less secure. The order of G should have a large prime factor to prevent use of the Pohlig–Hellman algorithm to obtain a or b . For this reason,

SPEKE - Misplaced Pages Continue

2080-447: Is not difficult for Alice to solve for Bob's private key (or vice versa), then an eavesdropper, Eve , may simply substitute her own private / public key pair, plug Bob's public key into her private key, produce a fake shared secret key, and solve for Bob's private key (and use that to solve for the shared secret key). Eve may attempt to choose a public / private key pair that will make it easy for her to solve for Bob's private key. Here

2145-487: Is possible to use ephemeral and static keys in one key agreement to provide more security as for example shown in NIST SP 800-56A, but it is also possible to combine those in a single DH key exchange, which is then called triple DH (3-DH). In 1997 a kind of triple DH was proposed by Simon Blake-Wilson, Don Johnson, Alfred Menezes in 1997, which was improved by C. Kudla and K. G. Paterson in 2005 and shown to be secure. The long term secret keys of Alice and Bob are denoted by

2210-623: Is the ElGamal encryption . A more modern variant is the Integrated Encryption Scheme . Protocols that achieve forward secrecy generate new key pairs for each session and discard them at the end of the session. The Diffie–Hellman key exchange is a frequent choice for such protocols, because of its fast key generation. When Alice and Bob share a password, they may use a password-authenticated key agreement (PK) form of Diffie–Hellman to prevent man-in-the-middle attacks. One simple scheme

2275-427: Is the earliest publicly known work that proposed the idea of a private key and a corresponding public key. Traditionally, secure encrypted communication between two parties required that they first exchange keys by some secure physical means, such as paper key lists transported by a trusted courier . The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish

2340-443: Is the use of digitally signed keys that must be integrity-assured: if Bob's key is signed by a trusted third party vouching for his identity, Alice can have considerable confidence that a signed key she receives is not an attempt to intercept by Eve. When Alice and Bob have a public-key infrastructure, they may digitally sign an agreed Diffie–Hellman key, or exchanged Diffie–Hellman public keys. Such signed keys, sometimes signed by

2405-399: Is to arrange the N participants in a circle and have N keys rotate around the circle, until eventually every key has been contributed to by all N participants (ending with its owner) and each participant has contributed to N keys (ending with their own). However, this requires that every participant perform N modular exponentiations. By choosing a more desirable order, and relying on

2470-508: Is to compare the hash of s concatenated with the password calculated independently on both ends of channel. A feature of these schemes is that an attacker can only test one specific password on each iteration with the other party, and so the system provides good security with relatively weak passwords. This approach is described in ITU-T Recommendation X.1035 , which is used by the G.hn home networking standard. An example of such

2535-461: Is vulnerable to a replay attack. Timestamps and nonces are included to fix this attack. It forms the basis for the Kerberos protocol . Boyd et al. classify two-party key agreement protocols according to two criteria as follows: The pre-shared key may be shared between the two parties, or each party may share a key with a trusted third party. If there is no secure channel (as may be established via

2600-505: The Logjam authors recommend use of elliptic curve cryptography , for which no similar attack is known. Failing that, they recommend that the order, p , of the Diffie–Hellman group should be at least 2048 bits. They estimate that the pre-computation required for a 2048-bit prime is 10 times more difficult than for 1024-bit primes. Public key encryption schemes based on the Diffie–Hellman key exchange have been proposed. The first such scheme

2665-538: 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). However, the SPEKE specification in IEEE P1363.2 remains unpatched. U.S. patent 6,226,383 describes several variations of

SPEKE - Misplaced Pages Continue

2730-588: The algorithm be called Diffie–Hellman–Merkle key exchange in recognition of Ralph Merkle 's contribution to the invention of public-key cryptography (Hellman, 2006), writing: The system...has since become known as Diffie–Hellman key exchange. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called 'Diffie–Hellman–Merkle key exchange' if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle's equal contribution to

2795-464: The analogy back to a real-life exchange using large numbers rather than colors, this determination is computationally expensive. It is impossible to compute in a practical amount of time even for modern supercomputers . The simplest and the original implementation, later formalized as Finite Field Diffie–Hellman in RFC 7919 , of the protocol uses the multiplicative group of integers modulo p , where p

2860-566: The basis for a variety of authenticated protocols, and is used to provide forward secrecy in Transport Layer Security 's ephemeral modes (referred to as EDH or DHE depending on the cipher suite ). The method was followed shortly afterwards by RSA , an implementation of public-key cryptography using asymmetric algorithms. Expired US patent 4,200,770 from 1977 describes the now public-domain algorithm. It credits Hellman, Diffie, and Merkle as inventors. In 2006, Hellman suggested

2925-454: The beginning and continuing to be so, actively decrypting and re-encrypting messages every time Alice and Bob communicate. If she arrives after the keys have been generated and the encrypted conversation between Alice and Bob has already begun, the attack cannot succeed. If she is ever absent, her previous presence is then revealed to Alice and Bob. They will know that all of their private conversations had been intercepted and decoded by someone in

2990-407: The channel. In most cases it will not help them get Mallory's private key, even if she used the same key for both exchanges. A method to authenticate the communicating parties to each other is generally needed to prevent this type of attack. Variants of Diffie–Hellman, such as STS protocol , may be used instead to avoid these types of attacks. A CVE released in 2021 ( CVE-2002-20001 ) disclosed

3055-416: The color is yellow. Each person also selects a secret color that they keep to themselves – in this case, red and cyan. The crucial part of the process is that Alice and Bob each mix their own secret color together with their mutually shared color, resulting in orange-tan and light-blue mixtures respectively, and then publicly exchange the two mixed colors. Finally, each of them mixes the color they received from

3120-408: The communicating parties and can be vulnerable to a man-in-the-middle attack . Mallory (an active attacker executing the man-in-the-middle attack) may establish two distinct key exchanges, one with Alice and the other with Bob, effectively masquerading as Alice to Bob, and vice versa, allowing her to decrypt, then re-encrypt, the messages passed between them. Note that Mallory must be in the middle from

3185-426: The discrete log problem for a 1024-bit prime would cost on the order of $ 100 million, well within the budget of a large national intelligence agency such as the U.S. National Security Agency (NSA). The Logjam authors speculate that precomputation against widely reused 1024-bit DH primes is behind claims in leaked NSA documents that NSA is able to break much of current cryptography. To avoid these vulnerabilities,

3250-462: The eight implied by a simple circular arrangement. The protocol is considered secure against eavesdroppers if G and g are chosen properly. In particular, the order of the group G must be large, particularly if the same group is used for large amounts of traffic. The eavesdropper has to solve the Diffie–Hellman problem to obtain g . This is currently considered difficult for groups whose order

3315-412: The fact that keys can be duplicated, it is possible to reduce the number of modular exponentiations performed by each participant to log 2 ( N ) + 1 using a divide-and-conquer-style approach, given here for eight participants: Once this operation has been completed all participants will possess the secret g , but each participant will have performed only four modular exponentiations, rather than

SECTION 50

#1733085938553

3380-475: The invention of public key cryptography. Diffie–Hellman key exchange establishes a shared secret between two parties that can be used for secret communication for exchanging data over a public network. An analogy illustrates the concept of public key exchange by using colors instead of very large numbers: The process begins by having the two parties, Alice and Bob , publicly agree on an arbitrary starting color that does not need to be kept secret. In this example,

3445-399: The key, and sends that key to the other party; the other party has no influence on the key. The first publicly known public-key agreement protocol that meets the above criteria was the Diffie–Hellman key exchange , in which two parties jointly exponentiate a generator with random numbers, in such a way that an eavesdropper cannot feasibly determine what the resultant value used to produce

3510-455: The method. This patent expired in March 2017. 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. Diffie%E2%80%93Hellman key exchange Diffie–Hellman ( DH ) key exchange

3575-411: The other values – p , g , g mod p , and g mod p – are sent in the clear. The strength of the scheme comes from the fact that g mod p = g mod p take extremely long times to compute by any known algorithm just from the knowledge of p , g , g mod p , and g mod p . Such a function that is easy to compute but hard to invert is called a one-way function . Once Alice and Bob compute

3640-409: The parties, and is thus vulnerable to man-in-the-middle attacks . A wide variety of cryptographic authentication schemes and protocols have been developed to provide authenticated key agreement to prevent man-in-the-middle and related attacks. These methods generally mathematically bind the agreed key to other agreed-upon data, such as the following: A widely used mechanism for defeating such attacks

3705-406: The partner with their own private color. The result is a final color mixture (yellow-brown in this case) that is identical to their partner's final color mixture. If a third party listened to the exchange, they would only know the common color (yellow) and the first mixed colors (orange-tan and light-blue), but it would be very hard for them to find out the final secret color (yellow-brown). Bringing

3770-433: The protocol, g is calculated as g = g q with a constant g q . 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. A paper published by MacKenzie in 2001 presents

3835-454: 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

3900-502: The security services of some countries. The scheme was published by Whitfield Diffie and Martin Hellman in 1976, but in 1997 it was revealed that James H. Ellis , Clifford Cocks , and Malcolm J. Williamson of GCHQ , the British signals intelligence agency, had previously shown in 1969 how public-key cryptography could be achieved. Although Diffie–Hellman key exchange itself is a non-authenticated key-agreement protocol , it provides

3965-422: 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

SECTION 60

#1733085938553

4030-431: The shared secret they can use it as an encryption key, known only to them, for sending messages across the same open communications channel. Of course, much larger values of a , b , and p would be needed to make this example secure, since there are only 23 possible results of n mod 23. However, if p is a prime of at least 600 digits, then even the fastest modern computers using the fastest known algorithm cannot find

4095-410: The use of groups whose order was a 512-bit prime number, so called export grade . The authors needed several thousand CPU cores for a week to precompute data for a single 512-bit prime. Once that was done, individual logarithms could be solved in about a minute using two 18-core Intel Xeon CPUs. As estimated by the authors behind the Logjam attack, the much more difficult precomputation needed to solve

4160-451: The use of initial shared secrets or a trusted third party with whom the agreeing parties share a secret is assumed. If no third party is present, then achieving SKA can be trivial: we assume that two parties share an initial secret and have tautologically achieved SKA. SKA contrasts with key-agreement protocols that include techniques from asymmetric cryptography . For example, key encapsulation mechanisms . The initial exchange of

4225-552: Was initially proposed as part of the Double Ratchet Algorithm used in the Signal Protocol . The protocol offers forward secrecy and cryptographic deniability. It operates on an elliptic curve. The protocol uses five public keys. Alice has an identity key IK A and an ephemeral key EK A . Bob has an identity key IK B , a signed prekey SPK B , and a one-time prekey OPK B . Bob first publishes his three keys to

#552447