docs: FHMQV-C

2 files changed, 142 insertions, 0 deletions

diff --git a/doc/source/crypto/fhmqvc.rst b/doc/source/crypto/fhmqvc.rst
index b82c817..aa6f0cc 100644
--- a/doc/source/crypto/fhmqvc.rst
+++ b/doc/source/crypto/fhmqvc.rst
@@ -1,4 +1,144 @@
 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::
+
+   \begin{align}
+     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}, *)
+   \end{align}
+
+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-Expand}(\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::
+
+   \begin{align}
+     d = \bar{H}(X|Y|\hat{A}|\hat{B}) \\
+     e = \bar{H}(Y|X|\hat{A}|\hat{B})
+   \end{align}
+
+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.
 
diff --git a/doc/source/devel/protocol.rst b/doc/source/devel/protocol.rst
index b3b40f3..a8c3c71 100644
--- a/doc/source/devel/protocol.rst
+++ b/doc/source/devel/protocol.rst
@@ -50,6 +50,8 @@ Record ID  Value description             Format                     Values
 ``0x000f`` TLV authentication tag        32-byte opaque value
 ========== ============================= ========================== ===================================================================
 
+.. _handshake_protocol:
+
 Handshake protocol
 ------------------
 The following specification describes the current handshake as it is performed by fastd versions