YAK (cryptography)

Last updated June 17, 2023

The YAK is a public-key authenticated key-agreement protocol, proposed by Feng Hao in 2010. ^[1]^[2] It is claimed to be the simplest authenticated key exchange protocol among the related schemes, including MQV, HMQV, Station-to-Station protocol, SSL/TLS etc. The authentication is based on public key pairs. As with other protocols, YAK normally requires a Public Key Infrastructure to distribute authentic public keys to the communicating parties. The security of YAK is disputed (see below and the talk page).

Description

Two parties, Alice and Bob, agree on a group $G$ with generator $g$ of prime order $q$ in which the discrete log problem is hard. Typically a Schnorr group is used. In general, YAK can use any prime order group that is suitable for public key cryptography, including elliptic curve cryptography. Let $g^{a}$ be Alice's long-term public key and $g^{b}$ be Bob's. The protocol executes in one round:

Alice selects $x\in _{\text{R}}[0,q-1]$ and sends out $g^{x}$ together with a zero-knowledge proof (using for example Schnorr non-interactive zero-knowledge proof as described in RFC 8235) for the proof of the exponent $x$ . Similarly, Bob selects $y\in _{\text{R}}[0,q-1]$ and sends out $g^{y}$ together with a zero-knowledge proof for the proof of the exponent $y$ . Here, the notation $\in _{\text{R}}$ denotes an element selected randomly with uniform probability.

The above communication can be completed in one round as neither party depends on the other. When it finishes, Alice and Bob verify the received zero-knowledge proofs. Alice then computes $K=(g^{y}g^{b})^{x+a}=g^{(x+a)(y+b)}$ . Similarly, Bob computes $K=(g^{x}g^{a})^{y+b}=g^{(x+a)(y+b)}$ . With the same keying material $K$ , Alice and Bob can derive a session key using a cryptographic hash function: $\kappa =H(K)$ .

Security properties

The use of well-established zero-knowledge proof primitives such as Schnorr's scheme greatly simplifies the security proofs. Given that the underlying zero knowledge proof primitive is secure, the YAK protocol aims to satisfy the following properties. ^[2]

Private key security – An attacker cannot learn the user's static private key even if he is able to learn all session-specific secrets in any compromised session.
Forward secrecy – Session keys that were securely established in the past uncorrupted sessions will remain incomputable in the future even when both users' static private keys are disclosed.
Session key security – An attacker cannot compute the session key if he impersonates a user but has no access to the user's private key.

The security claims in the original YAK paper ^[2] are based on the Computational Diffie-Hellman assumption in a random oracle model.

Cryptanalysis

In 2015, Toorani mentioned that "the YAK protocol lacks joint key control and perfect forward secrecy attributes and is vulnerable to some attacks including unknown key-share and key-replication attacks" ^[3] to which Hao has a different opinion.^[4]

In 2020, Mohammad mentioned that YAK protocol cannot withstand the known key security attack which leads to a new key compromise impersonation attack where an adversary is allowed to reveal both the shared static secret key between two parties and the ephemeral private key of the initiator. The author also proposed an improved protocol to remedy these attacks and the previous attacks mentioned by Toorani on the YAK protocol, and the proposed protocol uses a verification mechanism that provides entity authentication and key confirmation. The author showed that the proposed protocol is secure in the proposed formal security model under the gap Diffie‐Hellman assumption and the random oracle assumption. Moreover, the security of the proposed protocol and attacks on the YAK protocol were verified by the Scyther tool. ^[5] Mohammad's paper is discussed in the talk page.

Related Research Articles

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.

Quantum key distribution (QKD) is a secure communication method that implements a cryptographic protocol involving components of quantum mechanics. It enables two parties to produce a shared random secret key known only to them, which then can be used to encrypt and decrypt messages. The process of quantum key distribution is not to be confused with quantum cryptography, as it is the best-known example of a quantum-cryptographic task.

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.

Burrows–Abadi–Needham logic is a set of rules for defining and analyzing information exchange protocols. Specifically, BAN logic helps its users determine whether exchanged information is trustworthy, secured against eavesdropping, or both. BAN logic starts with the assumption that all information exchanges happen on media vulnerable to tampering and public monitoring. This has evolved into the popular security mantra, "Don't trust the network."

Articles related to cryptography include:

A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding. Commitment schemes have important applications in a number of cryptographic protocols including secure coin flipping, zero-knowledge proofs, and secure computation.

In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic-curve cryptography.

In cryptography, a Schnorr signature is a digital signature produced by the Schnorr signature algorithm that was described by Claus Schnorr. It is a digital signature scheme known for its simplicity, among the first whose security is based on the intractability of certain discrete logarithm problems. It is efficient and generates short signatures. It was covered by U.S. Patent 4,995,082 which expired in February 2008.

A cryptographic protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods, often as sequences of cryptographic primitives. A protocol describes how the algorithms should be used and includes details about data structures and representations, at which point it can be used to implement multiple, interoperable versions of a program.

The Cramer–Shoup system is an asymmetric key encryption algorithm, and was the first efficient scheme proven to be secure against adaptive chosen ciphertext attack using standard cryptographic assumptions. Its security is based on the computational intractability of the decisional Diffie–Hellman assumption. Developed by Ronald Cramer and Victor Shoup in 1998, it is an extension of the ElGamal cryptosystem. In contrast to ElGamal, which is extremely malleable, Cramer–Shoup adds other elements to ensure non-malleability even against a resourceful attacker. This non-malleability is achieved through the use of a universal one-way hash function and additional computations, resulting in a ciphertext which is twice as large as in ElGamal.

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).

SPEKE is a cryptographic method for password-authenticated key agreement.

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, a proof of knowledge is an interactive proof in which the prover succeeds in 'convincing' a verifier that the prover knows something. What it means for a machine to 'know something' is defined in terms of computation. A machine 'knows something', if this something can be computed, given the machine as an input. As the program of the prover does not necessarily spit out the knowledge itself a machine with a different program, called the knowledge extractor is introduced to capture this idea. We are mostly interested in what can be proven by polynomial time bounded machines. In this case the set of knowledge elements is limited to a set of witnesses of some language in NP.

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.

In cryptography, the anonymous veto network is a multi-party secure computation protocol to compute the boolean-OR function. It was first proposed by Feng Hao and Piotr Zieliński in 2006. This protocol presents an efficient solution to the Dining cryptographers problem.

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.

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.

In cryptography, the open vote network is a secure multi-party computation protocol to compute the boolean-count function: namely, given a set of binary values 0/1 in the input, compute the total count of ones without revealing each individual value. This protocol was proposed by Feng Hao, Peter Ryan, and Piotr Zieliński in 2010. It extends Hao and Zieliński's anonymous veto network protocol by allowing each participant to count the number of veto votes while preserving the anonymity of those who have voted. The protocol can be generalized to support a wider range of inputs beyond just the binary values 0 and 1.

References

↑ Hao, Feng (2010). "On Robust Key Agreement Based on Public Key Authentication" (PDF). Financial Cryptography and Data Security, LNCS 6052. 14th Conference on Financial Cryptography and Data Security. Tenerife, Spain. pp. 383–390.
1 2 3 Hao, Feng (18 April 2012). "On robust key agreement based on public key authentication" (PDF). Security and Communication Networks. 7 (1): 77–87. doi: 10.1002/sec.550 . ISSN 1939-0122.
↑ Toorani, Mohsen (30 October 2015). "Cryptanalysis of a robust key agreement based on public key authentication". Security and Communication Networks. 9: 19–26. doi: 10.1002/sec.1373 . ISSN 1939-0122.
↑ Hao, Feng (2019). "Comments on "Cryptanalysis of a robust key agreement based on public key authentication"" (PDF). Retrieved 22 September 2019.
↑ Mohammad, Zeyad (11 March 2020). "Cryptanalysis and improvement of the YAK protocol with formal security proof and security verification via Scyther". International Journal of Communication Systems. 33 (9): e4386. doi:10.1002/dac.4386. ISSN 1099-1131. S2CID 215836240.

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.

[YAK-short-1] Hao, Feng (2010). "On Robust Key Agreement Based on Public Key Authentication" (PDF). Financial Cryptography and Data Security, LNCS 6052. 14th Conference on Financial Cryptography and Data Security. Tenerife, Spain. pp. 383–390.

[YAK-full-2] 1 2 3 Hao, Feng (18 April 2012). "On robust key agreement based on public key authentication" (PDF). Security and Communication Networks. 7 (1): 77–87. doi: 10.1002/sec.550 . ISSN 1939-0122.

[cryptanalysis1-3] Toorani, Mohsen (30 October 2015). "Cryptanalysis of a robust key agreement based on public key authentication". Security and Communication Networks. 9: 19–26. doi: 10.1002/sec.1373 . ISSN 1939-0122.

[4] Hao, Feng (2019). "Comments on "Cryptanalysis of a robust key agreement based on public key authentication"" (PDF). Retrieved 22 September 2019.

[cryptanalysis2-5] Mohammad, Zeyad (11 March 2020). "Cryptanalysis and improvement of the YAK protocol with formal security proof and security verification via Scyther". International Journal of Communication Systems. 33 (9): e4386. doi:10.1002/dac.4386. ISSN 1099-1131. S2CID 215836240.

[1]

[2]

[3]

[4]

[5]