Post-Quantum Noise with New Hope

The specification for the Noise Protocol makes mention of a feature called secondary symmetric keys, or SSK's, that are intended to help with migrating to post-quantum cryptography in the future. The idea is that a post-quantum handshake can be run in parallel with the regular Noise handshake, and then a shared key derived from the post-quantum state is mixed into the regular handshake's state when Split() is called. The specification doesn't say much more than that. The specifics of post-quantum handshakes are left up to the reader's imagination.

This page describes an experimental method for post-quantum handshakes using the New Hope key exchange algorithm. It is not part of the offical Noise specification (yet!).

New Hope

The New Hope algorithm is a lattice-based key exchange algorithm with properties similar to traditional Diffie-Hellman schemes. Key sizes are as follows:

• Alice's public key: 1824 bytes
• Bob's public key: 2048 bytes
• Shared secret: 32 bytes

There are some differences with schemes like Curve25519 and Curve448. New Hope only supports ephemeral key exchange. There is no support for long-term static keys. Thus, the only Noise pattern that we can use is NN as all other patterns mix an ephemeral key with a static key in some way.

The API is also different. Standard DH schemes are "balanced" in the sense that both sides can generate keypairs and combine them in separate steps:

a = GENERATE_KEYPAIR()              b = GENERATE_KEYPAIR()
                   a.public      ->
                                 <- b.public
shared = DH(a.private, b.public)    shared = DH(b.private, a.public)

This balanced approach allows the same private key to be combined with different public keys in the session, which is the basis of all Noise patterns other than NN.

The New Hope key exchange by contrast is "unbalanced". Bob's public key and shared secret are derived in part from parameters sent by Alice. Bob's private key never appears in the New Hope API:

a = GENERATE_ALICE()
                   a.public      ->
                                    (b.public, shared) = SHARED_BOB(a.public)
                                 <- b.public
shared = SHARED_ALICE(a.private, b.public)

In the New Hope paper, Alice is typically the server/responder rather than the client/initiator. This allows some optional sharing of public parameters from session to session on TLS servers. But there's no reason why the roles cannot be reversed (a footnote in the paper indicates that it is perfectly reasonable to do so).

Implementing Noise tokens with New Hope

As stated above, New Hope is only suitable for use with the "NN" handshake pattern:

Noise_NN():
  -> e
  <- e, dhee

Because of the "unbalanced" nature of New Hope, we need to modify how the e and dhee tokens operate. The initiator and responder both have e and re variables for the local and remote ephemeral keys respectively. For New Hope, both variables start as empty and marked as "Alice".

WriteMessage(e):

• If re is empty, then mark re as "Bob" and call GENERATE_ALICE() to generate a new keypair for e.
• If re is not empty, then mark e as "Bob" and call SHARED_BOB(re.public) to generate a public key for e plus the shared secret. The shared secret is saved until later.
• Write e.public to the handshake message and call MixHash(e.public). Note that e.public may be either 1824 or 2048 bytes in length depending upon whether e is marked as "Alice" or "Bob".

ReadMessage(e):

• Same as for regular DH. Read re.public from the handshake message and call MixHash(re.public). Note that re.public may be either 1824 or 2048 bytes in length depending upon whether re is marked as "Alice" or "Bob" at this point in the handshake.

WriteMessage(dhee) and ReadMessage(dhee):

• If e is marked as "Alice", then generate a shared secret with SHARED_ALICE(e.private, re.public) and call MixKey(shared) on it.
• If e is marked as "Bob", then call MixKey(shared) on the previously saved shared secret that is stored in e.

If the prefix is NoisePSK then WriteMessage(e) and ReadMessage(e) are modified in the usual way to call MixKey(e.public) after MixHash(e.public).

For our purposes we do not allow or define null public keys for New Hope. Null public keys that generate all-zero or similar static output completely destroy the security of ephemeral key exchange. Since "NN" is the only pattern we can use with New Hope, it is safer not to attempt to support null public keys.

New Hope in Noise-C

Noise-C has been modified to include a new DH algorithm called NewHope that can be used with the NN handshake pattern. If the application attempts to use NewHope with any other handshake pattern, an error will be reported.

Most of the modifications were to implement the new DH backend for NewHope. The details of marking keys as either "Alice" or "Bob" were mostly hidden inside the backend with minimal modifications to common code. Some logic was added to the common code to reject patterns other than NN and to make the e and re objects mutually aware of each other.

The echo example in Noise-C has also been modified to support the NewHope algorithm to allow for testing.

Combining Protocols

The specification for the Noise Protocol proposes running a post-quantum handshake in parallel with the regular handshake, and then mixing the post-quantum chaining key into the regular handshake as a secondary symmetric key (SSK). The two handshakes could run like this:

Noise_XX_25519(s, rs):          Noise_NN_NewHope():
  -> e                            -> e
  <- e, dhee, s, dhse             <- e, dhee
  -> s, dhse
                                  Q_SSK = DerivePSK()
  Split(Q_SSK)

The DerivePSK() function derives a resumption pre-shared key from the cipher state. The value is fed into the regular handshake as the SSK when it is split.

In a practical implementation, we can run the post-quantum handshake inside the payloads of the regular handshake messages. In pseudo-code, the initiator would perform the following steps:

regular.Initialize("Noise_XX_25519...")
quantum.Initialize("Noise_NN_NewHope...")

quantum.WriteMessage(payload1, buffer1)
regular.WriteMessage(buffer1, message1)

// transmit message1, receive message2

regular.ReadMessage(message2, buffer2)
quantum.ReadMessage(buffer2, payload2)
(qc1,qc2) = quantum.Split()

buffer3 = qc1.EncryptWithAd(ad, payload3)
regular.WriteMessage(buffer3, message3)

// transmit message3

(c1,c2) = regular.Split(qc1.DerivePSK())

We note that the handshake message payloads for the second and third messages are encrypted with the post-quantum key. Any certificates or other metadata in those payloads would be double-encrypted by both handshakes, protecting them from attacks on both the regular and quantum handshakes.

Another approach

The previous sections describe how to use New Hope as a drop-in replacement for the Diffie-Hellman algorithm in a traditional Noise handshake. In the process we are limited to just the NN handshake pattern. Another approach is to specify two DH algorithms, one regular and one post-quantum, in the protocol name; e.g. Noise_XXq_25519_ChaChaPoly_BLAKE2s_NewHope. The variables in the HandshakeState are extended with two new variables:

• q for the local post-quantum key.
• rq for the remote post-quantum key.

We then add two new tokens q and dhqq which are defined as above for New Hope. The existing e and re variables are used with the regular DH algorithm (e.g. 25519 or 448).

The new tokens can be used to transform existing Noise handshake patterns to include post-quantum operations directly:

Noise_XXq(s, rs):
  -> q, e
  <- q, dhqq, e, dhee, s, dhse
  -> s, dhse

In the above example, Alice is the initiator. The payloads for the second and third handshake messages are encrypted with a key derived from the results of both the regular and post-quantum DH operations.

The technique also works with Alice as the responder, although this time only the third message's payload is protected by the post-quantum key:

Noise_XXrq(s, rs):
  -> e
  <- q, e, dhee, s, dhse
  -> q, dhqq, s, dhse

Final words

We note that if a post-quantum key exchange algorithm is balanced and supports long-term static keys, then none of the above is necessary. The post-quantum algorithm would be a true drop-in replacement, suitable for use in all handshake patterns. However, given that post-quantum algorithms are usually slower than regular DH algorithms and involve more data on the wire, there may still be some value in combining the methods as described above.

The companion page Post-Quantum Noise with SIDHp751 discusses how SIDHp751 can be used as a true drop-in replacement suitable for use in all handshake patterns.