A Recommended Handshake and Encryption Scheme

  1. Handshake
    1. Parameters
      1. Handshake Definition
      2. Transport Encryption
        1. References

          The specification of private interest overlap detection mandates using a handshake and subsequent encryption with certain properties. In this document, we provide specific constructions for achieving the required properties.

          Handshake

          The handshake we describe here is essentially the XX handshake of the noise protocol framework11Specifically, revision 34., with a few modifications:

          • Noise only supports a limited set of cryptographic primitives, whereas we — analogous to all the other Willow specs — allow for arbitrary parameters.
          • We use tweaked protocol names (which determine the initialisation of the Noise h variable): the names start with Nose intead of Noise.
          • The h variables of the peers are always initialised to the hash of the protocol name, instead of zero-padding sufficiently short names.
          • The algorithm names may also be non-standard, due to our greater flexibility in parameter selection.
          • Our handshake has no notion of payloads. Unmodified Noise would force us to encrypt and authenticate the empty string as part of each message, adding an overhead of 16 bytes per message. We completely remove the notion instead.

          We give a self-contained specification next, defining precisely the possible parameters and omitting all details of the noise framework but those relevant for the XX handshake pattern.

          Parameters

          Noise allows for Curve25519 and Curve448 here.The parameters for the Diffie-Hellman part of the handshake are types PublicKey and SecretKey, a function corresponding from SecretKey to PublicKey, and a function dh(SecretKey, PublicKey) -> PublicKey such that for any two SecretKeys sk1 and sk2, we have that dh(sk1, corresponding(sk2)) == dh(sk2, corresponding(sk1)). We further require an encoding function encode_pk for PublicKey, and we denote the inverse as decode_pk.

          Noise allows for ChaChaPoly and AES256 with GCM here.The parameters for the AEAD part are a type AEADKey, a natural number nonce_length — we write Nonce for the type of natural numbers between and (both inclusive), and a two functions

          • encrypt(pk: AEADKey, nonce: Nonce, ad: &[U8], plaintext: &[U8]) -> &[U8], and
          • We do not reflect this on the type level to keep things simple, but decrypt also needs a way of signalling decryption failures. Any decryption failure immediately aborts the connection.decrypt(pk: AEADKey, nonce: Nonce, ad: &[U8], cyphertext: &[U8]) -> &[U8],

          such that using the output of encrypt as the final argument for decrypt yields the original plaintext (for arbitrary but equal other arguments).

          Noise allows for SHA256, SHA512, Blake2s and Blake2b here.The parameters for hashing during the handshake are a natural number hashlen (must be 32 or greater), a hash function hash(&[U8]) -> [U8; hashlen], and a natural number blocklen to serve as the B parameter of HMAC (i.e., it should be the block length of hash in bytes). We further require a function22In Noise, this corresponds to truncating a hash and using the result as an encryption key. digest_to_aeadkey from [U8; hashlen] to AEADKey.

          The parameters for state initialisation are an arbitrary bytestring prologue33The prologue data is hashed into the initial states of the peers, handshakes between two peers with non-equal prologues will fail. We recommend using 16 zero-bytes as the prologue if you want to interact with as many peers as possible, and to otherwise use a (pseudo-) random 16 byte number for creating a fully independent universe of syncing., and an ASCII protocol_name of the form Nose_XX_{dh}_{aead}_{hash} (note the deliberate lack of an i in the first part), where {dh} is an algorithm name for the Diffie Hellman parameters, {aead} is an algorithm name for the AEAD parameters, and {hash} is an algorithm name for the hashing parameters. When using parameters supported by Noise, you should use the same names as Noise does. An example name would be Nose_XX_ED25519_ChaChaPoly_WILLIAM3.

          Handshake Definition

          We now describe the data that the two peers exchange, and the local state they need to track in order to perform the necessary computations. We call the peer that sends the first message the initiator, and the other peer the responder.

          A helpful resource that can serve as a middle ground between our presentation and the Noise spec is Noise Explorer, which essentially projects the Noise spec down to a single handshake.The presentation is in a deliberately different style than the Noise spec: minimal abstractions, sequential reading, a birds-eye view of both peers. The variable names are derived from those of the Noise spec, with ini or res prefixes to indicate variables maintained by the initiator or the responder respectively, and with pk and sk suffixes to indicate public keys and secret keys respectively.

          We denote by hkdf(chaining_key: [U8; hashlen], input_key_material: &[U8]): ([U8; hashlen], [U8; hashlen]) the function that produces two OKMs with the HKDF (RFC 5869) function, using hash as the HMAC-Hash. This corresponds directly to the HKDF function of the Noise spec, with num_outputs set to two.

          Setup
          init keys

          Initialise ini_esk (type SecretKey) to a random SecretKey.

          Initialise res_esk (type SecretKey) to a random SecretKey.

          Initialise ini_epk (type PublicKey) to corresponding(ini_esk).

          Initialise res_epk (type PublicKey) to corresponding(res_esk).

          Initialise ini_ssk (type SecretKey) to an arbitrary SecretKey.

          Initialise res_ssk (type SecretKey) to an arbitrary SecretKey.

          Initialise ini_spk (type PublicKey) to corresponding(ini_ssk).

          Initialise res_spk (type PublicKey) to corresponding(res_ssk).

          init state

          Initialise ini_h (type [U8; hashlen]) to to hash(protocol_name).

          Initialise res_h (type [U8; hashlen]) to to hash(protocol_name).

          Initialise ini_ck (type [U8; hashlen]) to ini_h.

          Initialise res_ck (type [U8; hashlen]) to res_h.

          Set ini_h to hash(concat(ini_h, prologue)).

          Set res_h to hash(concat(res_h, prologue)).

          e →
          e

          Send encode_pk(ini_epk).

          Set ini_h to hash(concat(ini_h, encode_pk(ini_epk))).

          e

          Receive the encoded ini_epk, call the encoding e.

          Initialise res_repk (type PublicKey) to decode_pk(e).

          Set res_h to hash(concat(res_h, e)).

          ← e, ee, s, es
          e

          Send encode_pk(res_epk).

          Set res_h to hash(concat(res_h, encode_pk(res_epk))).

          ee

          Let (tmp_ck, tmp_k) = hkdf(res_ck, dh(res_esk, res_repk)).

          Set res_ck to tmp_ck.

          Initialise res_k (type AEADKey) to digest_to_aeadkey(tmp_k).

          s

          Let cyphertext1 be encrypt(res_k, 0, res_h, encode_pk(res_spk)).

          Send cyphertext1.

          Set res_h to hash(concat(res_h, cyphertext1)).

          es

          Let (tmp_ck, tmp_k) = hkdf(res_ck, dh(res_ssk, res_repk)).

          Set res_ck to tmp_ck.

          Set res_k to digest_to_aeadkey(tmp_k).

          e

          Receive the encoded res_epk, call the encoding e.

          Initialise ini_repk (type PublicKey) to decode_pk(e).

          Set ini_h to hash(concat(ini_h, e)).

          ee

          Let (tmp_ck, tmp_k) = hkdf(ini_ck, dh(ini_esk, ini_repk)).

          Set ini_ck to tmp_ck.

          Initialise ini_k (type AEADKey) to digest_to_aeadkey(tmp_k).

          s

          Receive cyphertext1.

          Initialise ini_rspk (type PublicKey) to decode_pk(decrypt(ini_k, 0, ini_h, cyphertext1)).

          Set ini_h to hash(concat(ini_h, cyphertext1)).

          es

          Let (tmp_ck, tmp_k) = hkdf(ini_ck, dh(ini_esk, ini_rspk)).

          Set ini_ck to tmp_ck.

          Set ini_k to digest_to_aeadkey(tmp_k).

          s, se →
          s

          Let cyphertext2 be encrypt(ini_k, 0, ini_h, encode_pk(ini_spk)).

          Send cyphertext2.

          Set ini_h to hash(concat(ini_h, cyphertext2)).

          se

          Let (tmp_ck, tmp_k) = hkdf(ini_ck, dh(ini_ssk, ini_repk)).

          Set ini_ck to tmp_ck.

          Set ini_k to digest_to_aeadkey(tmp_k).

          s

          Receive cyphertext2.

          Initialise res_rspk (type PublicKey) to decode_pk(decrypt(res_k, 0, res_h, cyphertext2)).

          Set res_h to hash(concat(res_h, cyphertext2)).

          se

          Let (tmp_ck, tmp_k) = hkdf(res_ck, dh(res_esk, res_rspk)).

          Set res_ck to tmp_ck.

          Set res_k to digest_to_aeadkey(tmp_k).

          Secret Derivation

          Let zerolen denote the byte string of length zero.

          Let zerolen denote the byte string of length zero.

          Let (ini_tmp_k1, ini_tmp_k2) = hkdf(ini_ck, zerolen).

          Let (res_tmp_k1, res_tmp_k2) = hkdf(res_ck, zerolen).

          Initialise ini_aeadk1 (type AEADKey) to digest_to_aeadkey(ini_tmp_k1).

          Initialise res_aeadk1 (type AEADKey) to digest_to_aeadkey(res_tmp_k1).

          Initialise ini_aeadk2 (type AEADKey) to digest_to_aeadkey(ini_tmp_k2).

          Initialise res_aeadk2 (type AEADKey) to digest_to_aeadkey(res_tmp_k2).

          By the end of this handshake, it holds that ini_aeadk1 == res_aeadk1, ini_aeadk2 == res_aeadk2, and ini_h == res_h.

          In the context of private interest overlap detection, ini_h and res_h serve as the shared, random bytestring rnd. The public keys for which the initiator proves ownership (ini_pk in the PIO spec) is ini_spk. The public keys for which the responder proves ownership (res_pk in the PIO spec) is res_spk.

          Subsequent encryption is performed as described in the next section, with ini_aeadk1 and ini_aeadk2 (which are equal to res_aeadk1 and res_aeadk2 respectively) serving as the shared secrets for symmetric encryption.

          Transport Encryption

          When sending data after the handshake, the data is encrypted with encrypt. To this end, each peer needs a sending_key: for the initiator, it is ini_aeadk1, and for the responder, it is ini_aeadk2. Each peer also maintains a 64-bit integer sending_nonce, initialised to zero.

          For decryption (which we do not specify explicitly), the peers also require a receiving_nonce (initialised to zero) and a receiving_key (ini_aeadk2 for the initiator, and ini_aeadk1 for the responder).

          This aproach to encryption is a generalisation of Dominic Tarr’s Box Stream, and it is compatible with how Noise specifies transport message transmission.After the handshake, data can be sent in chunks of length at least one and at most (both inclusive). To send a chunk hs_chunk of length len, a peer first transmits encrypt(sending_key, sending_nonce, zerolen, be_chunklen), where be_chunklen is len encoded as a big-endian two-byte integer. Then, the peer increments sending_nonce. Then, the peer transmits encrypt(sending_key, sending_nonce, zerolen, hs_chunk), and finally increments sending_nonce again.

          If incrementing the sending_nonce would result in an overflow, an error must be emitted instead and no further bytes may be sent.

          Instead of sending a chunk, a peer can also signal the end of all transmissions, by transmitting encrypt(sending_key, sending_nonce, zerolen, 0x0000).

          This approach to encrypting and sending data authenticates the end of the stream, and it makes chunk boundaries less obvious than when sending them in plaintext. Note that chunk boundaries are still not fully obscured either: for one, physically sending off a chunk leaks where it ends; and also, active attackers can induce bitflips and then observe where exactly decoding fails44For a detailed discussion of the theoretical security notions at play here, see the InterMAC paper (Boldyreva et al., 2012).. Paranoid peers that wish to achieve better theoretical security guarantees can do so by only using a single chunk length, padding shorter chunks if necessary. When using LCMUX, you can pad with with SendGlobalFrames of empty content, for example.

          References