Hi y'all, A new paper analyzing the security of the Sphinx mix-net packet format [1] (and also HORNET) has recently caught my attention. The paper is rather long and very theory heavy, but the TL;DR is this:
* The OG Sphinx paper proved various aspects of its security using a model for onion routing originally put forth by Camenisch and Lysyanskaya [2]. * This new paper discovered that certain security notions put forth in [2] weren't actually practically achievable by real-world onion routing implementations (in this case Onion-Correctnes), or weren't entirely correct or additive. New stronger security notions are put forth in response, along with extensions to the original Sphinx mix-net packet format that achieve these notions. * A flaw they discovered in the original Sphinx paper [3], can allow an exit node to deduce a lower bound of the length of the path used to reach it. The issue is that the original paper constructs the _starting packet_ (what the exit hop will receive) by adding extra padding zeroes after the destination and identifier (we've more or less revamped this with our new onion format, but it still stands). An adversarial exit node can then locate the first set bit after the identifier (our payload in this case), then use that to compute the lower bound. * One of the (?) reference Sphinx implementations recognizes that this was/is an issue in the paper and implements the mitigation [4]. * The fix on our end is easy: we need to replace those zero bytes with random bytes when constructing the starting packet. I've created a PR to lnd's lightning-onion PR implementing this mitigation [5]. As this changes the starting packet format, we also need to either update the test vectors or we can keep them as is, and note that we use zeroes so the test vectors are fully deterministic. My PR to the spec patching the privacy leak leaves the test vectors untouched as is [6]. With all that said, IMO we have larger existing privacy leaks just due to our unique application of the packet format. As an example, a receiver can use the CLTV of the final HTLC to deduce bounds on the path length as we have a restricted topology and CLTV values for public channels are all known. Another leak is our usage of the variable length onion payloads which a node can use to ascertain path length since they space they consume counts towards the max hop count of 20-something. In any case, we can patch this with just a few lines of code (fill out with random bytes) at _senders_, and don't need any intermediate nodes to update. The new and old packet construction algos are compatible as packet _processing_ isn't changing, instead just the starting set of bytes are. As always, please double-check by interpretation of the paper, as it's possible I'm missing something. If my interpretation stands, then it's a relatively minor privacy leak, and an easy low-hanging fruit that can be patched without wide-spread network coordination. -- Laolu [1]: https://arxiv.org/abs/1910.13772 [2]: https://www.iacr.org/cryptodb/archive/2005/CRYPTO/1091/1091.pdf [3]: https://cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf [4]: https://github.com/UCL-InfoSec/sphinx/blob/c05b7034eaffd8f98454e0619b0b1548a9fa0f42/SphinxClient.py#L67 [5]: https://github.com/lightningnetwork/lightning-onion/pull/40 [6]: https://github.com/lightningnetwork/lightning-rfc/pull/697
_______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev