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.

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 :math:`a` and :math:`\hat{A}` for Alice, :math:`b` and :math:`\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 :math:`x` and :math:`X` for Alice, :math:`y` and :math:`Y` for Bob) generated randomly for each handshake

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

* :math:`\bar{H}`: A cryptographic hash function with an output half the length of the secret keys
* :math:`\textit{MAC}`: A message authentication code (keyed hash) function
* :math:`\textit{KDF}_1`: A key derivation function with an output that can be used as key for the :math:`\textit{MAC}` function
* :math:`\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; :math:`\mathcal{G}^*` is
the subgroup generated by :math:`G` and :math:`q` is the cardinality of :math:`\mathcal{G}^*`.

Protocol specification
~~~~~~~~~~~~~~~~~~~~~~

I. The initiator Alice does the following:

   a) Choose :math:`x \in [1,q-1]` and compute :math:`X = x G`.
   b) Send :math:`(\hat{A},\hat{B},X)` to Bob.

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

    a) Verify that :math:`X \in \mathcal{G}^*`.
    b) Choose :math:`y \in [1,q-1]`, compute :math:`Y = y G`.
    c) Compute :math:`d = \bar{H}(X,Y,\hat{A},\hat{B})` and :math:`e = \bar{H}(Y,X,\hat{A},\hat{B})`.
    d) Compute :math:`s_B = y + e b \mod q`, :math:`\sigma_B = s_B(X + d A)`.
    e) Compute :math:`K_1 = \textit{KDF}_1(\sigma_B,\hat{A},\hat{B},X,Y)` and :math:`t_B = \textit{MAC}_{K_1}(\hat{B},Y)`.
    f) Send :math:`(\hat{B},\hat{A},Y,t_B)` to Alice.

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

    a) Verify that :math:`Y \in \mathcal{G}^*`.
    b) Compute :math:`d = \bar{H}(X,Y,\hat{A},\hat{B})` and :math:`e = \bar{H}(Y,X,\hat{A},\hat{B})`.
    c) Compute :math:`s_A = x + d a \mod q`, :math:`\sigma_A = s_A(Y + e B)`.
    d) Compute :math:`K_1 = \textit{KDF}_1(\sigma_A,\hat{A},\hat{B},X,Y)`.
    e) Verify that :math:`t_B = \textit{MAC}_{K_1}(\hat{B},Y)`.
    f) Compute :math:`t_A = \textit{MAC}_{K_1}(\hat{A},X)`.
    g) Send :math:`t_A` to Bob.
    h) Compute :math:`K_2 = \textit{KDF}_2(\sigma_A,\hat{A},\hat{B},X,Y)`.

IV. At the receipt of :math:`t_A`, Bob does the following:

    a) Verify that :math:`t_A = \textit{MAC}_{K_1}(\hat{A},X)`.
    b) Compute :math:`K_2 = \textit{KDF}_2(\sigma_A,\hat{A},\hat{B},X,Y)`.

V. The shared session key is :math:`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 :doc:`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:

.. math::

   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 :math:`V|W` designates the concatenation of the binary strings :math:`V` and :math:`W` and

.. math::

   \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 :math:`d` and :math:`e` deviates from the FHMQV-C specification, which uses a hash
function :math:`\bar{H}` with half-width (127 bit in the case of ``ec25519-fhmqvc``) output, defining :math:`d` and :math:`e`
as

.. math::

   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 :math:`\text{SHA256}(Y|X|\hat{B}|\hat{A})` instead and cuts it into two 128 bit pieces
which are used as :math:`d` and :math:`e`. This optimization allows reusing the SHA256 implementation that is already used for
:math:`\textit{KDF}_1` and :math:`\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 :math:`t_A` and :math:`t_B`, which verify the public keys only. To generate this tag, :math:`\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 :ref:`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/fips/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.

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