YAK (cryptography)

The YAK is a public-key authenticated key-agreement protocol, proposed by Feng Hao in 2010. [1][2] It is considered one of the simplest authenticated key exchange protocols 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.

Description

Two parties, Alice and Bob, agree on a group ${\displaystyle G}$ with generator ${\displaystyle g}$ of prime order ${\displaystyle 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 ${\displaystyle g^{a}}$ be Alice's long-term public key and ${\displaystyle g^{b}}$ be Bob's. The protocol executes in one round:

Alice selects ${\displaystyle x\in _{\text{R}}[0,q-1]}$ and sends out ${\displaystyle 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 ${\displaystyle x}$. Similarly, Bob selects ${\displaystyle y\in _{\text{R}}[0,q-1]}$ and sends out ${\displaystyle g^{y}}$ together with a zero-knowledge proof for the proof of the exponent ${\displaystyle y}$. Here, the notation ${\displaystyle \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 ${\displaystyle K=(g^{y}g^{b})^{x+a}=g^{(x+a)(y+b)}}$. Similarly, Bob computes ${\displaystyle K=(g^{x}g^{a})^{y+b}=g^{(x+a)(y+b)}}$. With the same keying material ${\displaystyle K}$, Alice and Bob can derive a session key using a cryptographic hash function: ${\displaystyle \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 is proved to satisfy the following properties. [2]

1. 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.
2. 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.
3. 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 proofs in the original YAK paper [2] are based on the Computational Diffie-Hellman assumption in a random oracle model. However, they are not constructed in a formal model as done in some other key agreement protocols.

Cryptanalysis

In 2015, Toorani claimed 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] The claimed attacks were responded to by Hao. [4]

In 2020, Mohammad claimed that the YAK protocol cannot withstand a "new key compromise impersonation attack, where an adversary is allowed to reveal both the shared static secret key between two‐party participation and the ephemeral private key of the initiator party." [5] It is shown that such an attacker is able to trivially break the session key in YAK. The author further showed that the same attack trivially breaks many other authenticated key exchange protocols including MQV and HMQV. However, according to the "extreme adversary principle" stated in the original YAK paper [2], if a powerful attacker is allowed access to ephemeral secrets, he should be allowed to access all session-specific ephemeral secrets rather than any subset. A session key is part of the session-specific secrets. Therefore, if a powerful adversary has the capability to access an ephemeral secret in the user's computer memory, he has the capability to access the session key by definition (however, the private key remains secure even if the adversary is able to reveal all session-specific secrets in any arbitrary session, as stated in "private key security").

References

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.
2. 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.
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.
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. doi:10.1002/dac.4386. ISSN 1099-1131.