From d8a73a26112fd7bd2c0bdab4fc6daf105d7eae3e Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Mon, 27 Oct 2014 02:49:01 +0100 Subject: docs: FHMQV-C --- doc/source/crypto/fhmqvc.rst | 140 ++++++++++++++++++++++++++++++++++++++++++ doc/source/devel/protocol.rst | 2 + 2 files changed, 142 insertions(+) (limited to 'doc/source') 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, ``_, 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, ``_, 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 -- cgit v1.2.3