Hybrid X25519 and Streamlined NTRU Prime sntrup761 with SHA3-256: Chempat-X

Abstract

This memo define Chempat-X, a post-quantum/traditional hybrid key exchange method (PQ/T KEM) based on X25519 and Streamlined NTRU Prime sntrup761 with SHA3-256.¶

1. Introduction

Streamlined NTRU Prime [NTRUPrime] [NTRUPrimePQCS] provides post-quantum small lattice-based key-encapsulation mechanisms. The variant sntrup761 instance has been implemented widely.¶

The pre-quantum elliptic-curve Diffie-Hellman X25519 function [RFC7748] has been widely implemented.¶

To hedge against attacks on either of sntrup761 or X25519 a hybrid construction may be used, with the intention that the hybrid would be secure if either of the involved algorithms are flawed.¶

This document describes how to implement key exchange based on a hybrid between Streamlined NTRU Prime sntrup761 and X25519 with SHA3-256 [NIST_FIPS_202].¶

This design is based on the Secure Shell protocol "sntrup761x25519-sha512", but we use a stronger combiner of the resulting shared secret. We offer this document for other protocols that desire to use a hybrid key exchange method based on established mechanisms.¶

2. Chempat-X Key Exchange Method

The key-agreement is done by the X25519 Diffie-Hellman protocol as described in section 6.1 (Curve25519) of [RFC7748], and the key encapsulation method described in [NTRUPrimePQCS].¶

Alice sends a concatenation of the 1158 byte public key output from the key generator of sntrup761 with the 32 byte K_A = X25519(a, 9) as described in [NTRUPrimePQCS] and [RFC7748]. The output value is thus 1190 bytes.¶

Bob sends a concatenation of the 1039 byte ciphertext output from the key encapsulation mechanism of sntrup761 with the 32 byte K_B = X25519(b, 9) as described in [NTRUPrimePQCS] and [RFC7748]. The output value is thus 1071 bytes.¶

Alice derive the 32 byte shared K1 based on the X25519 values as described in [RFC7748] and performs the sntrup761 key decapsulation operation as described in [NTRUPrimePQCS] to yield the 32 byte shared secret K2. Alice derives the final hybrid shared secret key K as described below.. The output is 32 bytes.¶

Bob derive the 32 byte shared K1 based on the X25519 values as described in [RFC7748] and takes the 32 byte shared secret key K2 from the earlier key encapsulation method of sntrup761. Bob derives the final hybrid shared secret secret key K as described below. The output is 32 bytes.¶

Alice and Bob has now established a shared key.¶

3. Key Combiner

The final hybrid shared secret key "hybridss" is derived using SHA3-256 as follows:¶

   H = SHA3-256,
   hybridpk = (receiverpkECDH,receiverpkKEM),
   hybridct = (senderpkECDH,senderctKEM),
   hybridss = H(ssECDH,ssKEM,H(hybridct),H(hybridpk),context)

4. Acknowledgements

This work is a simple generalization of the sntrup761x25519-sha512 mechanism due to [OpenSSH] and TinySSH [TinySSH] documented in draft-josefsson-ntruprime-ssh-00, but modified to use a stronger combiner function suggested by Daniel J. Bernstein.¶

5. Security Considerations

The security considerations of [RFC7748], [NTRUPrimePQCS] and [NIST_FIPS_202] are inherited.¶

While the construct should remain secure if either X25519 or sntrup761 is found to be insecure, the security of the combined hybrid construction also depends on the security of the combiner algorithm.¶

6. IANA Considerations

This document has no IANA actions.¶

7. References