--- title: 'Noise Extension: Hybrid Forward Secrecy' author: 'Rhys Weatherley (rhys.weatherley@gmail.com)' revision: '1draft-5' date: '2017-06-17' --- 1. Motivation ============= Once quantum computers become available it is possible that existing Noise DH algorithms such as `25519` and `448` will become vulnerable. This might allow a future adversary armed with a quantum computer to read archived communications. Using currently-known post-quantum cryptography we may be able to strengthen the secrecy of current communications against future adversaries. This document describes an extension to the Noise protocol to augment handshakes with additional forward secrecy. We describe the general method here. Separate extensions will describe specific post-quantum algorithms. For demonstration purposes, we assume that `448` is being used to strengthen a `25519` handshake. This allows us to describe the minimum changes necessary to Noise to add extra forward secrecy to a handshake using existing Noise primitives. In a practical implementation, `448` would of course be replaced by a post-quantum algorithm. 2. Protocol naming ================== The name of the DH function in the protocol name is modified to include a pair of identifiers separated by a plus sign; for example: Noise_XXhfs_25519+448_AESGCM_SHA256 The pattern name `XXhfs` indicates that that pattern `XX` has been transformed using the "hybrid forward secrecy" modifier, which is defined later. The function for the first name in the pair (`25519`) plays the same role as in regular Noise. The function for the second name in the pair (`448`) specifies the algorithm that will be used to add hybrid forward secrecy to an otherwise plain `Noise_XX_25519_AESGCM_SHA256` handshake. If a protocol name includes a hybrid forward secrecy function, then the pattern must include the `"f"` and `"ff"` tokens described later. Otherwise the protocol name is invalid. Conversely, a pattern that includes `"f"` and `"ff"` tokens can only be used with a protocol name that includes a hybrid forward secrecy function. 3. Crypto functions =================== The following functions and constant definitions are added to Noise: * **`GENERATE_KEYPAIR_F(rf)`**: Generates a new key pair for the hybrid forward secrecy algorithm relative to a remote public key `rf`. The `rf` value will be empty for the first `"f"` token in the handshake, and non-empty for the second `"f"` token. * **`FF(key_pair, public_key)`**: Performs a calculation for the hybrid forward secrecy algorithm that mixes a local key pair with a remote public key. * **`FLEN1`** = A constant specifying the size in bytes of the output from `GENERATE_KEYPAIR_F(rf)` when `rf` is empty. * **`FLEN2`** = A constant specifying the size in bytes of the output from `GENERATE_KEYPAIR_F(rf)` when `rf` is not empty. * **`FFLEN`** = A constant specifying the size in bytes of the output from `FF()`. This extension uses these functions to generate and operate with ephemeral keys only. When a traditional Noise DH function like `448` is used to provide hybrid forward secrecy, the above definitions are specified as follows: * `GENERATE_KEYPAIR_F(rf)` = `GENERATE_KEYPAIR()` * `FF(key_pair, public_key)` = `DH(key_pair, public_key)` * `FLEN1` = `FLEN2` = `FFLEN` = `DHLEN` The separate extension for the post-quantum New Hope algorithm specifies the above definitions as follows: * `GENERATE_KEYPAIR_F(rf)` = `newhope_keygen()` if `rf` is empty, or `newhope_sharedb(r)` if `rf` is not empty. * `FF(key_pair, public_key)` = `newhope_shareda(key_pair, public_key)` if the `key_pair` was generated by `newhope_keygen()`. * `FF(key_pair, public_key)` = `key_pair.shared` if the `key_pair` was generated by `newhope_sharedb()`. * `FLEN1` = 1824 * `FLEN2` = 2176 * `FFLEN` = 32 As can be seen, New Hope has different key sizes and behaviors for the two parties (Alice and Bob). This asymmetric algorithm shape motivated the addition of `rf` to the parameters for `GENERATE_KEYPAIR_F()` and the multiple length values `FLEN1`, `FLEN2`, and `FFLEN`. 4. Changes to HandshakeState ============================ 4.1. Variables -------------- Two extra variables are added to the state: * `f`: The local hybrid forward secrecy key pair. * `rf`: The remote party's hybrid forward secrecy public key. Both of these variables are instances of the second function from the protocol name. If the protocol name does not include a second function, then the `f` and `rf` variables are not used by the handshake. 4.2. Initialization ------------------- `Initialize()` is modified to include `f` and `rf` parameters. If either value is supplied as a pre-message then that value must be hashed during the fourth pre-message step of the handshake. Pre-messages are hashed in the order `e`, `f`, `s`, initiator values first. The set of valid pre-messages is: * `e` * `s` * `e, s` * `e, f` * `e, f, s` * empty 4.3. Tokens ----------- Two new tokens are added for use in defining message patterns: `"f"` and `"ff"`. All other tokens continue to operate as before. Token handling for `WriteMessage()` is modified as follows: * For `"f"`: Sets `f = GENERATE_KEYPAIR_F(rf)`, overwriting any previous value for `f`. Appends `EncryptAndHash(f.public_key)` to the buffer. * For `"ff"`: Calls `MixKey(FF(f, rf))`. Token handling for `ReadMessage()` is modified as follows: * For `"f"`: If `f` is empty, then sets `temp` to the next `FLEN1` + 16` bytes of the message if `HasKey() == True`, or to the next `FLEN1` bytes otherwise. If `f` is not empty, then sets `temp` to the next `FLEN2 + 16` bytes of the message if `HasKey() == True`, or to the next `FLEN2` bytes otherwise. Sets `rf` to `DecryptAndHash(temp)`. * For `"ff"`: Calls `MixKey(FF(f, rf))`. Note that the `"f"` token values will be encrypted if a `"xy"` token has already been seen in the pattern, or if pre-shared keys are involved. 5. Message patterns for hybrid forward secrecy ============================================== 5.1. The `hfs` pattern modifier ------------------------------- This extension defines a pattern modifier named `hfs` that transforms an existing interactive pattern into one involving hybrid forward secrecy. The transformation rules are: * All occurrences of the `"e"` token in the pre-message and message body are replaced with `"e, f"`. * All occurrences of the `"ee"` token in the message body are replaced with `"ee, ff"`. * If the pattern contains `"e"` in its parameters, then `"f"` is added to the parameters. * If the pattern contains `"re"` in its parameters, then `"rf"` is added to the parameters. The following examples demonstrate the modifier: Noise_NNhfs(): -> e, f <- e, f, ee, ff Noise_XXhfs(s, rs): -> e, f <- e, f, ee, ff, s, es -> s, se Noise_IKhfs(s, rs): <- s ... -> e, f, es, s, ss <- e, f, ee, ff, se Noise_XXfallback+hfs(e, f, s, rs): -> e, f ... <- e, f, ee, ff, s, es -> s, se 5.2. Pattern validity --------------------- The following validity rules apply: * If `f` or `rf` appears in the parameters of a pattern, then the corresponding `e` or `re` value must also appear in the parameters. * The `"f"` token for a party must always appear after the corresponding `"e"` token for that party. * Only a single `"f"` token can be sent by each party. Alternatively, a pre-message `f` value for a party can stand in for the token. * `"ff"` must occur only once in the pattern, after both `"f"` tokens or their pre-message counterparts. * `"ff"` must occur after `"ee"`. 5.3. Hybrid pattern list ------------------------ Standard interactive Noise patterns that are modified with `hfs` fall into two broad categories: fully hybrid and partially hybrid. Fully hybrid patterns are those where the first two mixing operations in the pattern are `"ee"` and `"ff"`. All values that would have been encrypted in the original pattern are now encrypted with a hybrid key combining outputs from both algorithms. Any message payloads and static public key values that were previously sent in the clear are still in the clear. The following patterns are fully hybrid: Noise_NNhfs(): -> e, f <- e, f, ee, ff Noise_NXhfs(rs): -> e, f <- e, f, ee, ff, s, es Noise_XNhfs(s): -> e, f <- e, f, ee, ff -> s, se Noise_XXhfs(s, rs): -> e, f <- e, f, ee, ff, s, es -> s, se Noise_KNhfs(s): -> s ... -> e, f <- e, f, ee, ff, se Noise_KXhfs(s, rs): -> s ... -> e, f <- e, f, ee, ff, se, s, es Noise_INhfs(s): -> e, f, s <- e, f, ee, ff, se Noise_IXhfs(s, rs): -> e, f, s <- e, f, ee, ff, se, s, es Noise_XXfallback+hfs(e, f, s, rs): -> e, f ... <- e, f, ee, ff, s, es -> s, se Partially hybrid patterns are those where a `"xy"` operation involving a static public key precedes the first `"ee"` operation. Static public key values and message payloads that precede the first `"ff"` operation will be encrypted only with the classical DH algorithm. If that algorithm falls to a future attack, then message payloads or static public keys that were previously encrypted may be revealed. The following patterns are partially hybrid: Noise_NKhfs(rs): <- s ... -> e, f, es <- e, f, ee, ff Noise_XKhfs(s, rs): <- s ... -> e, f, es <- e, f, ee, ff -> s, se Noise_KKhfs(s, rs): -> s <- s ... -> e, f, es, ss <- e, f, ee, ff, se Noise_IKhfs(s, rs): <- s ... -> e, f, es, s, ss <- e, f, ee, ff, se As can be seen, all of the standard interactive patterns that end in `"K"` become partially hybrid when modified with `hfs`. It is disappointing that `"IK+hfs"` is partially hybrid because it means that a post-quantum Noise Pipes is not a simple matter of modifying `"XX"`, `"IK"`, and `"XXfallback"` with `hfs`. 6. Future Directions ==================== 6.1. Other hybrid patterns -------------------------- Partially hybrid patterns can be improved by using another modifier to move static public key values to later in the handshake to hide identity information: Noise_IKhfs+xyz(s, rs): <- s ... -> e, f, es <- e, f, ee, ff -> s, ss, se The `"es"` token in the first message could also be moved to the third message. Although for Noise Pipes we would like the first message to trigger fallback if the initiator is not in possession of the responder's current static public key. The responder's static public key value is not as secret as the initator's - any party can connect to the responder with `"XX"` and retrieve the responder's static public key without needing to mount an attack against archived communications. Transforming patterns in this way tends to increase the number of turn-arounds. More experimentation is required before such a modifier can be standardized. This extension provides the basic tools that could be used to define such a modifier later. 6.2. Encryption of hybrid forward secrecy values ------------------------------------------------ Given that post-quantum cryptography is very new, it is possible that weaknesses may be found in whatever algorithm is chosen. Encryption of `"f"` tokens can help hide patterns in the post-quantum values that might allow cryptanalysis. Encryption of `"f"` tokens may also be useful for implementing an Elligator-like scheme that converts post-quantum values into something indistinguishable from random. 6.3. Post-quantum static keys ----------------------------- This extension is solely concerned with augmenting the forward secrecy of an existing handshake. It is possible to imagine a further extension whereby the hybrid function also operates on static keys. Some post-quantum algorithms like New Hope only support ephemeral keys, whereas others like SIDHp751 support both ephemeral and static keys. Static keys could be handled in one of two ways: * Use `25519` or `448` for hybrid forward secrecy, and the post-quantum algorithm for static keys; e.g. `Noise_XXhfs_SIDHp751+448`. * Extend the facilities here with new tokens to allow static keys for both algorithms; e.g. `Noise_XXhfs+hstatic_448+SIDHp751`. At the moment we do not make any comment as to the wisdom in doing so or the mechanisms that would be involved.