Join GitHub today
GitHub is home to over 28 million developers working together to host and review code, manage projects, and build software together.Sign up
Post Quantum Noise with New Hope
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!).
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
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
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
dhee tokens operate. The initiator and responder
re variables for the local and remote
ephemeral keys respectively. For New Hope, both variables start as empty
and marked as "Alice".
reis empty, then mark
reas "Bob" and call
GENERATE_ALICE()to generate a new keypair for
reis not empty, then mark
eas "Bob" and call
SHARED_BOB(re.public)to generate a public key for
eplus the shared secret. The shared secret is saved until later.
e.publicto the handshake message and call
MixHash(e.public). Note that
e.publicmay be either 1824 or 2048 bytes in length depending upon whether
eis marked as "Alice" or "Bob".
- Same as for regular DH. Read
re.publicfrom the handshake message and call
MixHash(re.public). Note that
re.publicmay be either 1824 or 2048 bytes in length depending upon whether
reis marked as "Alice" or "Bob" at this point in the handshake.
eis marked as "Alice", then generate a shared secret with
SHARED_ALICE(e.private, re.public)and call
eis marked as "Bob", then call
MixKey(shared)on the previously saved shared secret that is stored in
If the prefix is
are modified in the usual way to call
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
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
NN and to make the
re objects mutually aware of
The echo example in Noise-C has also been modified to support the
algorithm to allow for testing.
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)
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.
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:
qfor the local post-quantum key.
rqfor the remote post-quantum key.
We then add two new tokens
dhqq which are defined as above for
New Hope. The existing
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
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.