FHMQV-C
*******

FHMQV (Fully Hashed Menezes-Qu-Vanstone) is an extended, implicitly
authenticated Diffie-Hellman key exchange which has been specified in
[SEB09], correcting issues found in the earlier MQV ([LMQ+98]) and
Hashed MQV ([Kra05]) algorithms. It should be noted that proof of
security provided by [SEB09] was recently found to be faulty in
[LSW+14]; nevertheless it is very unlikely that this has an impact on
the security of the algorithm in practise.

The modified algorithm FHMQV-C specified in the same document also
provides *Perfect Forward Secrecy* (PFS), which isn't the case for the
simple FHMQV algorithm.

Like all MQV protocols, Alice and Bob have two key pairs each in
FHMQV-C:

* A long term key pair (called a and \hat{A} for Alice, b and \hat{B}
  for Bob)

  Alice and Bob must know each other's long term public keys in
  advance, as they are used to authenticate themselves against each
  other.

* A handshake key pair (called x and X for Alice, y and Y for Bob)
  generated randomly for each handshake

The algorithm further makes use of some arbitrary cryptographic hash
and MAC functions:

* \bar{H}: A cryptographic hash function with an output half the
  length of the secret keys

* \textit{MAC}: A message authentication code (keyed hash) function

* \textit{KDF}_1: A key derivation function with an output that can be
  used as key for the \textit{MAC} function

* \textit{KDF}_2: A key derivation function with an output with the
  desired length of the shared session key

The following description of the protocol has been directly taken from
[SEB09] with only minor formal changes. Upper case letter denote group
elements here, lower case letter scalars; \mathcal{G}^* is the
subgroup generated by G and q is the cardinality of \mathcal{G}^*.


Protocol specification
======================

1. The initiator Alice does the following:

   1. Choose x \in [1,q-1] and compute X = x G.

   2. Send (\hat{A},\hat{B},X) to Bob.

2. At the receipt of (\hat{A},\hat{B},X) Bob does the following:

   1. Verify that X \in \mathcal{G}^*.

   2. Choose y \in [1,q-1], compute Y = y G.

   3. Compute d = \bar{H}(X,Y,\hat{A},\hat{B}) and e =
      \bar{H}(Y,X,\hat{A},\hat{B}).

   4. Compute s_B = y + e b \mod q, \sigma_B = s_B(X + d A).

   5. Compute K_1 = \textit{KDF}_1(\sigma_B,\hat{A},\hat{B},X,Y) and
      t_B = \textit{MAC}_{K_1}(\hat{B},Y).

   6. Send (\hat{B},\hat{A},Y,t_B) to Alice.

3. At the receipt of (\hat{B},\hat{A},Y,t_B) Alice does the following:

   1. Verify that Y \in \mathcal{G}^*.

   2. Compute d = \bar{H}(X,Y,\hat{A},\hat{B}) and e =
      \bar{H}(Y,X,\hat{A},\hat{B}).

   3. Compute s_A = x + d a \mod q, \sigma_A = s_A(Y + e B).

   4. Compute K_1 = \textit{KDF}_1(\sigma_A,\hat{A},\hat{B},X,Y).

   5. Verify that t_B = \textit{MAC}_{K_1}(\hat{B},Y).

   6. Compute t_A = \textit{MAC}_{K_1}(\hat{A},X).

   7. Send t_A to Bob.

   8. Compute K_2 = \textit{KDF}_2(\sigma_A,\hat{A},\hat{B},X,Y).

4. At the receipt of t_A, Bob does the following:

   1. Verify that t_A = \textit{MAC}_{K_1}(\hat{A},X).

   2. Compute K_2 = \textit{KDF}_2(\sigma_A,\hat{A},\hat{B},X,Y).

5. The shared session key is K_2.

The third message allows Bob to ensure that he is actually
communicating with Alice before the handshake is completed and thus
prevents the attack on PFS described in [Kra05] that affects all
2-message key exchange protocols.


Usage in fastd
==============

fastd performs the FHMQV-C key exchange on the group specified in
ec25519.

FHMQV-C makes use of several cryptographic hash and key derivation
functions that are not given in the specification. fastd uses the
following definitions for these functions:

   d|e &= \text{SHA256}(Y|X|\hat{B}|\hat{A}) \\ K_1 &=
   \textit{KDF}_1(\sigma,\hat{A},\hat{B},X,Y) = \text{HKDF-
   SHA256}(\texttt{0x00}^{32}, \sigma, \hat{A}|\hat{B}|X|Y, 32) \\ K_2
   &= \textit{KDF}_2(\sigma,\hat{A},\hat{B},X,Y) = \text{HKDF-
   SHA256}(K_1, \sigma, \hat{A}|\hat{B}|X|Y|\textit{method}, *)

where V|W designates the concatenation of the binary strings V and W
and

   \text{HKDF}(\textit{salt}, \textit{IKM}, \textit{info}, L) = \text
   {HKDF-Expand}(\text{HKDF-Extract}(\textit{salt}, \textit{IKM}),
   \textit{info}, L)

See [FIPS180] (SHA256), [RFC2104] (HMAC) and [RFC5869] (HKDF) for the
specifications of these algorithms.

As one can see, the calculation of d and e deviates from the FHMQV-C
specification, which uses a hash function \bar{H} with half-width (127
bit in the case of "ec25519-fhmqvc") output, defining d and e as

   d &= \bar{H}(X|Y|\hat{A}|\hat{B}) \\ e &=
   \bar{H}(Y|X|\hat{A}|\hat{B})

fastd uses a single 256 bit hash \text{SHA256}(Y|X|\hat{B}|\hat{A})
instead and cuts it into two 128 bit pieces which are used as d and e.
This optimization allows reusing the SHA256 implementation that is
already used for \textit{KDF}_1 and \textit{KDF}_2 and saves one hash
calculation.

Furthermore, starting with fastd v11 a *TLV authentication tag*
protecting the whole handshake packet is used instead of the values
t_A and t_B, which verify the public keys only. To generate this tag,
\text{HMAC-SHA256}(K_1, \cdot) is applied to a pseudo TLV record list,
which is the same as the TLV record list sent in the actual handshake
packet, with the exception of the *TLV authentication tag* value,
which is replaced by zeros. This ensures that no part of the handshake
after the initial packet has been manipulated, preventing downgrade
attacks.

For the exact sequence of handshake packets see Handshake protocol.


Bibliography
============

[FIPS180] National Institute of Standards and Technology, "Secure hash
          standards (SHS)", Federal Information Processing Standard
          180-4, 2012. [Online] http://csrc.nist.gov/publications/fip
          s/fips180-4/fips-180-4.pdf

[Kra05] H. Krawczyk, "HMQV: a high-performance secure Diffie-Hellman
        protocol", Cryptology ePrint Archive, Report 2005/176,
        http://eprint.iacr.org/, 2005.

[LMQ+98] L. Law, A. Menezes, M. Qu, J. Solinas and S. Vanstone, "An
         efficient protocol for authenticated key agreement", Designs,
         Codes and Cryptography, vol. 28, pp. 361–377, 1998.

[LSW+14] S. Liu, K. Sakurai, J. Weng, F. Zhang, and Y. Zhao, "Security
         Model and Analysis of FHMQV, Revisited", in Information
         Security and Cryptology, pp. 255–269, Springer, 2014.

[RFC2104] H. Krawczyk, M. Bellare and R. Canetti, "HMAC: Keyed-Hashing
          for Message Authentication", RFC 2104 (Informational),
          Updated by RFC 6151, Internet Engineering Task Force, 1997.
          [Online] http://www.ietf.org/rfc/rfc2104.txt

[RFC5869] H. Krawczyk and P. Eronen, "HMAC-based Extract-and-Expand
          Key Derivation Function (HKDF)", RFC5869 (Informational),
          Internet Engineering Task Force, 2010. [Online]
          http://www.ietf.org/rfc/rfc5869.txt

[SEB09] A. P. Sarr, P. Elbaz–Vincent and J. Bajard, "A secure and
        efficient authenticated Diffie–Hellman protocol", Cryptology
        ePrint Archive, Report 2009/408, http://eprint.iacr.org/,
        2009.
