Add Post Quantum Noise patterns from the paper

[david415]

Here's the link to the paper: https://eprint.iacr.org/2022/539
And here's the bibtext:

@misc{ ADH+22,
  author        = {Yawning Angel and Benjamin Dowling and Andreas Hülsing and Peter Schwabe and Florian Weber},
  title         = {Post Quantum Noise},
  booktitle     = {Proceedings of the 2022 {ACM SIGSAC} Conference on Computer and Communications Security, {CCS'22}},
  publisher     = {ACM},
  pages         = {97--109},
  year          = {2022},
  note          = {\url{http://cryptojedi.org/papers/\#pqnoise}},
}

I think it would be cool if test vectors were shared with snow, a rust implementation of the Noise spec, which also has not yet implemented this feature: mcginty/snow#142

Here's the abstract of Post Quantum Noise:

We introduce PQNoise, a post-quantum variant of the Noise framework. We demonstrate that it is possible to replace the Diffie-Hellman key-exchanges in Noise with KEMs in a secure way. A challenge is the inability to combine key pairs of KEMs, which can be resolved by certain forms of randomness-hardening for which we introduce a formal abstraction. We provide a generic recipe to turn classical Noise patterns into PQNoise patterns. We prove that the resulting PQNoise patterns achieve confidentiality and authenticity in the fACCE-model. Moreover we show that for those classical Noise-patterns that have been conjectured or proven secure in the fACCE-model our matching PQNoise-patterns eventually achieve the same security. Our security proof is generic and applies to any valid PQNoise pattern. This is made possible by another abstraction, called a hash-object, which hides the exact workings of how keying material is processed in an abstract stateful object that outputs pseudorandom keys under different corruption patterns. We also show that the hash chains used in Noise are a secure hash-object. Finally, we demonstrate the practicality of PQNoise delivering benchmarks for several base patterns.

[centromere]

Hi David. Thank you for bringing this paper to my attention. I think this would make a great addition to cacophony, though my bandwidth is limited at this time.

[david415]

Hi @centromere indeed there are no expectations here, only interesting information and suggestions. If I had more time I'd learn haskell and add this feature myself ;-)

By the way, this ticket is in fact more "fun" than it seems if we actually want a hybrid KEM to use with noise; let me explain:

Noise uses two different hash objects, one for ciphertext transcripts and the other for public keys. We therefore do not achieve IND-CCA2 merely by feeding Noise protocols any KEM, we must give it a IND-CCA2 KEM.

Any NIKE (non-interactive key exchange) can be adapted into a KEM (key encapsulation mechanism)... but for noise one must do so in a way that the NIKE-KEM adapter has semantic security, by hashing the shared secret with both public keys, like this:

Encapsulate(public key):
    ephemeral = random_scalar()
    ciphertext = scalar_mult(ephemeral, generator)
    s = scalar_mult(ephemeral, public key)
    shared key = H(s || public key || ciphertext)

Decapsulate(secret key, ciphertext):
    s = scalar_mult(secret key, ciphertext)
    shared key = H(s || public key || ciphertext)

And then likewise if we want to compose hybrid KEMs, involving a NIKE to KEM adapter KEM and a KEM such as Kyber1024 then in that case the KEM combiner should be security preserving. The KEM Combiners paper discusses this very same issue:
https://eprint.iacr.org/2018/024.pdf

My conclusion is that we must use the Split PRF KEM Combiner which means hashing together the shared secrets and KEM ciphertexts from both KEMs (that we are combining because we are a KEM combiner), like this:

 shared_secret = H(ss1 | ss2 | cct1 | cct2)

And obviously this all can and should be generalized over any NIKE or KEM.