[Lightning-dev] Potential Minor Sphinx Privacy Leak and Patch

[Olaoluwa Osuntokun]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20191105/e776780f/attachment.html>