Hi Laolu, Finally someone who understands! I very much enjoyed reading your reply.
> Re Kyber, what's the current state of production-ready implementations? > Language wise, the most popular LN implementations today are written in > either: C, Go, Rust, or Scala/Kotlin. I ask as most of the Bitcoin community > uses libsecp256k1 [2] for anything related to EC-crypto, it's pretty well > tested, and very well trusted. If this Sphinx modification is used with an ECDH and a PQ KEM then in that case I'm calling it PQ Sphinx or KEM Sphinx, if you don't mind. Similarly, there's a PQ Noise that uses KEMs as well. Cloudflare uses Kyber in production and they've written various blog posts about their PQ cryptographic protocols, like this one https://blog.cloudflare.com/securing-the-post-quantum-world/ which mentions their CIRCL golang library: https://github.com/cloudflare/circl which implements Kyber from NIST round 3 in pure golang: https://github.com/cloudflare/circl/blob/main/kem/kyber/kyber1024/kyber.go // Package kyber1024 implements the IND-CCA2 secure key encapsulation mechanism // Kyber1024.CCAKEM as submitted to round 3 of the NIST PQC competition and // described in // // https://pq-crystals.org/kyber/data/kyber-specification-round3.pdf Kyber is going to standardization so anyone using Kyber needs to keep on following up with Peter Schwabe (crypto jedi) because they may have received some feedback from NIST for some more minor tweaks. Peter suggested I implement KEM Sphinx when I was discussing with him how slow Sphinx was when using X25519 + CTIDH https://ctidh.isogeny.org/ Anyway, if we take Cloudflare's example, upgrading your stuff to use PQ cryptography gives you forever bragging rights on technical blog posts. I mean... "Securing the post-quantum world" sounds like "Securing the world" aka "saving the world". :-) funny. haha. > I think if we started to investigating switching to something PQ for the > mixnet NIKE, then we'd also want to examine updating BOLT-09 (spec for p2p > network link encryption in the network) which uses Noise_XK to use a PQ KEM > as well [4]. Yes, exactly! Once we change our protocols to use KEMs instead of NIKEs it's easy to also make them hybrid classical post quantum. Currently, Katzenpost is the only software project that uses PQ Noise. One of the paper authors, Yawning Angel, wrote a PQ Noise implementation called Nyquist, written in golang: https://gitlab.com/yawning/nyquist/-/tree/experimental/pqnoise?ref_type=heads For Katzenpost, we've forked Nyquist: https://github.com/katzenpost/nyquist in order to give the caller control over the construction and selection of KEMs for use with noise. For rust implementation, best we modify snow, I've opened a ticket for that but I'm not currently incentivized to work on it: https://github.com/mcginty/snow/issues/142 I suspect the security preserving KEM combiner is more important for Noise than it is for Sphinx since at least the 2nd hop and on, make use of a MAC which covers the next hop's KEM ciphertext (or NIKE public key). Noise, unlike TLS, has a separate hash object for ciphertext transcriptos and for public keys. So, Cloudflare uses an insecure KEM combiner with TLS but still achieves semantic security due to TLS using one hash object for public keys and ciphertext transcripts. And to wrap it all up with a nice post quantum bow, Katzenpost has a hybrid signature scheme which our decentralized PKI uses to sign the PKI document which has all the network connection information and public key materials. Currently we're using X25519 and Sphincs+; the signatures are around 49 kilobytes but we just don't care, it has no performance impact that is noticeable to users. Cheers, David On Mon, Sep 4, 2023 at 4:54 PM Olaoluwa Osuntokun <laol...@gmail.com> wrote: > > Hi David, > > Happy to see that you're still working to push the state-of-the-art when it > comes to mixnets! > > > 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. > > Ah interesting, so sounds like a classic time-space-tradeoff: we can > eliminate that extra DH operation just by including the self-contained > ("post" blinded) group element in the packet! An earlier version of the > onion packet format for LN put the group element directly into the packet, > but then we switched to Sphinx as it was more compact (and an existing > peer-reviewed scheme) > > FWIW, we do have a basic versioning scheme in the packet format > (unfortunately, the initial version doesn't include this data in the per-hop > HMAC, so we'd want to fix that in the next version). So if we chose to > adopt this CPU optimization, we can bump the version, then introduce a new > p2p feature bit so senders can know whether the receiver supports this new > format or not. In the past we updated the per-hop payload from a fixed > format, to a more flexible canonical protobuf style encoding (dubbed the > "TLV" format), though we haven't yet updated any of the crypto bits. > > In terms of tangible benefit, for the most part, forwarding payments on the > network is limited by I/O bandwidth, not CPU utilization. In order to > properly forward packets in a robust manner, nodes need to write some book > keeping information to disk for each batch before forwarding. So I'm not > sure we'd see much tangible benefit for the payment packet forwarding case. > > On the other hand, right now our packets are ~1300 bytes, which supports ~27 > hops if each hop only requires 37 or so bytes of forwarding information. 27 > hops is really much much more than we need, so if we instead target 14 hops > (or maybe less really), then we'd be able to adopt this trick without any > tangible increase in the packet size for each payment. > > It's worth mentioning that some of the network has deployed a slightly > repurposed Sphinx packet format for the purpose of payment related > notifications or requests. This protocol extension is called "onion > messaging" [1], and more closely resembles a traditional mixnet (can be used > for general messaging), but still targets a low-latency use case (need to > know if the payment can be attempted or not quickly). Unlike normal payment > forwarding, onion messages don't require nodes to write to disk (as > currently specified) as there's no sort of internal retransmission or > reliability logic required (tho they should still hang onto the shared > secrets to implement proper replay protection). That's all to say that > perhaps this optimization would be more useful for onion messaging than > normal payments. > > > 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. > > Re Kyber, what's the current state of production-ready implementations? > Language wise, the most popular LN implementations today are written in > either: C, Go, Rust, or Scala/Kotlin. I ask as most of the Bitcoin community > uses libsecp256k1 [2] for anything related to EC-crypto, it's pretty well > tested, and very well trusted. > > I think if we started to investigating switching to something PQ for the > mixnet NIKE, then we'd also want to examine updating BOLT-09 (spec for p2p > network link encryption in the network) which uses Noise_XK to use a PQ KEM > as well [4]. > > Worth mentioning that switching to Kyber derived schemes for key exchange > and encapsulation would protect us at the network level from future > post-quantum attackers, but Bitcoin itself as defined today would still be > vulnerable (to various degrees) to a quantum adversary. Updating Bitcoin to > be post-quantum secure is an active area of research [5][6]. > > [1]: https://github.com/lightning/bolts/pull/759 > [2]: https://github.com/bitcoin-core/secp256k1 > [3]: https://github.com/lightning/bolts/blob/master/08-transport.md > [4]: https://eprint.iacr.org/2022/539 [5]: https://arxiv.org/abs/1804.08118 > [6]: https://eprint.iacr.org/2022/1423 > > -- Laolu > > > On Fri, Sep 1, 2023 at 12:16 AM David Stainton <dstainton...@gmail.com> wrote: >> >> 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 >> _______________________________________________ >> Lightning-dev mailing list >> Lightning-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev _______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
