From dstainton415 at gmail.com  Thu Aug 31 17:22:26 2023
From: dstainton415 at gmail.com (David Stainton)
Date: Thu, 31 Aug 2023 10:22:26 -0700
Subject: [Lightning-dev] faster NIKE Sphinx or more secure KEM Sphinx
Message-ID: <CAFN1edrb1X4CKh5cfXfvUNU+hh9dn9VYFe2nz9E5Ca82TcgaPQ@mail.gmail.com>

Greetings,

The Sphinx cryptographic packet format as it was originally published
in the 2009 paper
( https://www.freehaven.net/anonbib/cache/DBLP:conf/sp/DanezisG09.pdf )
has a very compact packet format but in exchange, performance is sacrificed.
Certainly when mixminion was around in 2002 this was the right choice
because networks were
a lot slower back then. And it may have also been the right choice
back in 2009, It's now 2023 and I am highly skeptical of this current
choice.

The NIKE group operations take orders of magnitude longer to perform
than all the other cryptographic primitives in the Sphinx packet
combined.
Sphinx performs two public key (ecdh group) operations per hop. One is
a DH and the other is the "blinding trick" (see paper for details).
Sphinx is essentially twice as fast if we eliminate the "blinding
trick" and only have one group operation per hop, the DH.
In order to make that work you'd also have to store the group element
for each hop within the Sphinx header's routing information section
which is properly padded and encrypted for each hop.
And also we want to preserve IND-CCA2 so then we can use a NIKE to KEM
adapter that combines both public keys with the DH output:

```
func ENCAPSULATE(their_pubkey publickey) ([]byte, []byte) {
        my_privkey, my_pubkey = GEN_KEYPAIR(RNG)
        ss = DH(my_privkey, their_pubkey)
        ss2 = H(ss || their_pubkey || my_pubkey)
        return my_pubkey, ss2
}

func DECAPSULATE(my_privkey, their_pubkey) []byte {
        s = DH(my_privkey, their_pubkey)
        shared_key = H(ss || my_pubkey || their_pubkey)
        return shared_key
}
```

With these modifications your Sphinx will be about twice as fast.
Or you may choose to combine the KEM with a Post Quantum KEM
such as the crypto jedi's Kyber1024 or other PQ KEMs. Let me remind
you that Kyber is
much faster than even X25519 (and I guess it must also be faster than
secp256k1). So combining your NIKE adapted KEM with a PQ KEM like
Kyber
will probably be the same speed as your current NIKE Sphinx implementation.

I made a table of Sphinx benchmarks using the Katzenpost
implementation of Sphinx using various NIKEs and KEMs:

https://github.com/katzenpost/napkin-math#sphinx-latency

The KEM Sphinx using Kyber768 X25519 Hybrid is about the same speed as
X25519 NIKE Sphinx.
If you are interested in this hybrid PQ construction then you'll want
to continue reading below how we do it properly in Katzenpost with a
security preserving KEM combiner.
However note that the bandwidth overhead is significant when using a
Kyber KEM Sphinx because each hop's KEM ciphertext must be stored
within the routing info section of the Sphinx header; and those KEM
ciphertexts can get pretty big, like 2 kilobytes.
And so here we have another table indicating the bandwidth overhead of
the Katzenpost Sphinx implementation using various KEMs:

https://github.com/katzenpost/napkin-math#bandwidth-overhead


There's this KEM Combiners paper, https://eprint.iacr.org/2018/024.pdf
which discusses the design of
a security preserving KEM combiner. The KEM Combiners paper makes the
observation that if a KEM combiner
is not security preserving then the resulting hybrid KEM will not have
IND-CCA2 security if one of the composing KEMs does not have IND-CCA2
security. Likewise the paper points out that when using a security
preserving KEM combiner, if only one of the composing KEMs has
IND-CCA2 security then the resulting hybrid KEM will have IND-CCA2
security.

Our KEM combiner uses the split PRF design from the paper when combining
two KEM shared secrets together we use a hash function to also mix
in the values of both KEM ciphertexts. In this pseudo code
example we are hashing together the two shared secrets
from the two underlying KEMs, ss1 and ss2. Additionally
the two ciphertexts from the underlying KEMs, cct1 and cct2,
are also hashed together:

```
// H is a hash function

func splitPRF(ss1, ss2, cct1, cct2 []byte) []byte {
        return H(ss1 || ss2 || cct1 || cct2)
}
```

Sincerely,
David Stainton