<div dir="ltr"><div>Hi Christian, welcome to the mailing list! </div><div><br></div><div>Excellent work! I&#39;ve been meaning to re-visit my implementation since I</div><div>finished it last October but have been busy tending to other lnd related items.</div><div>Thanks for the cleanups and optimizations you&#39;ve added to my initial Sphinx</div><div>implementation. Once we&#39;ve finished fleshing out the initial specification, I&#39;d</div><div>be happy to get those changes merged!</div><div><br></div><div>I&#39;ve taken a look at the diff against the existing implementation, plus the</div><div>current spec draft. I&#39;d say the current spec draft is the *clearest*</div><div>description of Sphinx I&#39;ve encountered, especially the padding bits. IMO, the</div><div>notation within the paper describing how to construct+process the mix-header is</div><div>rather opaque.</div><div><br></div><div>I see you&#39;ve modified the encryption scheme of the end-to-end payload,</div><div>switching from the arbitrary block-size block cipher (LIONESS) to purely a</div><div>stream cipher (ChaCha20). Initially I was under the impression that this might</div><div>compromise one of the security arguments of the scheme, but on closer</div><div>inspection this is perfectly fine if one extends the header MAC to the entire</div><div>payload as you&#39;ve done. If one was staying true to the original construction,</div><div>then this would eliminate the possibility of Single-Use Reply Blocks (SURB&#39;s)</div><div>since the sender would be unable to construct the reply mix-header as she would</div><div>be unaware of they responder&#39;s message. It&#39;s clear to me now that a MAC covering</div><div>the end-to-end payload was omitted in the original version since the proof of</div><div>computational indistinguishability of replies vs responses depends on the</div><div>structure+processing being identical for both messages types. However I don&#39;t</div><div>see us having any use for SURB&#39;s so this is an excellent change. Additionally,</div><div>modifications to the end-to-end payload will instantly cause packet corruption,</div><div>stopping invalid packets from propagating through the network.</div><div><br></div><div>I really like the addition of the per-hop payload! It&#39;s a change to the</div><div>original construction that I&#39;ve seriously considered proposing. Such a payload</div><div>should prove to be very useful in the future for information such as: limits on</div><div>the per-hop absolute timeout, fee information, etc. </div><div><br></div><div>The addition of a version byte is also very welcome. This&#39;ll streamline future</div><div>modifications we may make to the mix-header format in the future, such as</div><div>increasing the size of the per-hop payload, or switching to an alternative</div><div>format to encoding the &quot;next hop&quot; address.</div><div><br></div><div>The current draft doesn&#39;t specify the processor&#39;s action in the scenario that</div><div>they&#39;re unable to locate the next hop node within their local routing table.</div><div>Just to be explicit, I think a final paragraph should be inserted under the</div><div>&quot;Packet Forwarding&quot; section detailing the abort procedure.</div><div><br></div><div><br></div><div>&gt; However, they could easily be made variable should we decide that sending</div><div>&gt; mostly empty messages is wasteful.</div><div><br></div><div>I strongly think we should maintain the size uniformity of the packet</div><div>throughout processing, changes in payload size between hop can give away</div><div>information w.r.t a node&#39;s position within the route. </div><div><br></div><div>We might want to consider dropping the end-to-end payload altogether though. I</div><div>can&#39;t really think of a clear use case for the e2e payload within our specific</div><div>application.  That would save us 1k bytes, reducing the size of the full</div><div>mix-header to 1234 bytes. Accounting for the additional fields within an HTLC</div><div>&quot;add&quot; message, plus some additional overhead, this should keep us below typical</div><div>MTU sizes, avoiding fragmentation of HTLC &quot;add&quot; messages.</div><div><br></div><div>&gt; This specification is limited to version 0 packets and the structure of</div><div>&gt; future version may change. The receiving node then splits the packet into its</div><div>&gt; fields.</div><div><br></div><div>Packets with a non-zero version byte should be immediately rejected, as well as</div><div>packets which aren&#39;t *exactly* 2258 bytes (or 1234 bytes if we drop the e2e</div><div>payload).</div><div><br></div><div>&gt; The resulting HMAC is compared with the HMAC from the packet. Should the</div><div>&gt; computed HMAC and the HMAC from the packet differ then the node MUST abort</div><div>&gt; processing and report a route failure.</div><div><br></div><div>Perhaps we should explicitly specify that the HMAC equality check MUST be</div><div>performed without leaking timing information (constant time comparison)? I</div><div>can&#39;t think of a precise potential vulnerability otherwise since the scheme</div><div>uses an encrypt-then-MAC construction with a semantically secure encryption</div><div>scheme. I don&#39;t see any clear downsides in specifying that the comparison be</div><div>made in constant.</div><div><br></div><div>&gt; The sender computes a route {n_1, ..., n_{r-1}, n_r}, where n_1 is a peer of</div><div>&gt; the sender and n_r is the recipient. </div><div><br></div><div>In order to eliminate ambiguity, I think this should be more explicit,</div><div>specifying that &quot;n_1&quot; is a *direct neighbor* of the sender</div><div><br></div><div>&gt; A special HMAC value of 20 0x00 bytes indicates that the currently</div><div>&gt; processing hop is the intended recipient and that the packet should not be</div><div>&gt; forwarded. At this point the end-to-end payload is fully decrypted and the</div><div>&gt; route has terminated.</div><div><br></div><div>It seems that with the current construction, then the &quot;next hop&quot; address will</div><div>also be zero bytes if a packet processor is the last hop in the route.</div><div>Alternatively, if the sender is aware that the receiver is actually a &quot;virtual</div><div>channel&quot;, then an additional address could be used instead of the zero-address</div><div>to facilitate de-multiplexing at the last hop to the destination virtual</div><div>channel.</div><div><br></div><div>&gt; In the pocessing phase the secret is the node&#39;s private key...</div><div><br></div><div>Typo here, it should read &quot;In the processing phase...&quot;</div><div><br></div><div>I think two key onion-routing related aspects are under specified within the</div><div>current draft: replay protection, and key rotation. Although we might want to</div><div>place details concerning key rotation in a separate document covering the</div><div>initial routing protocol as the two are closely related.</div><div><br></div><div>First, lets talk replay protection. The current draft specifies that: </div><div><br></div><div>&gt; The node MUST keep a log of previously used shared secrets. Should the shared</div><div>&gt; secret already be in the log it MUST abort processing the packet and report a</div><div>&gt; route failure, since this is likely a replay attack, otherwise the shared</div><div>&gt; secret is added to the log</div><div><br></div><div>This is definitely necessary, however as dictated this would require nodes to</div><div>allocate a potentially *unbounded* amount of storage to the shared secret</div><div>&quot;seen&quot; log. I think we can allow nodes to periodically truncate this log by</div><div>adding an additional session time stamp to the mix-header, either placed</div><div>directly after the version byte, or within the per-hop payload.</div><div><br></div><div>With this absolute timestamp, each entry within the &quot;seen&quot; log becomes a </div><div>two-tuple: the shared secret itself, and the corresponding timestamp specified</div><div>within the mix-header. Before the absolute timestamp has passed, the entry</div><div>within the log remains, and mix-headers received with duplicated shared secret</div><div>are rejected. If we enforce an upper bound on the &quot;session lifetime&quot;, then</div><div>nodes can periodically prune this log, discarding obsolete shared secrets.</div><div>Once an entry has been pruned, although a node may not know if a shared secret</div><div>is being duplicated, they can reject expired sessions according to the</div><div>timestamp achieving a similar affect.</div><div><br></div><div>Reasonable session times may be something around 30-minutes to an hour or two.</div><div><br></div><div>With this scheme, I think that we can achieve near perfect replay protection</div><div>without unbounded storage.</div><div><br></div><div>On to the second aspect: key rotation. Ignoring the possible time-stamped log</div><div>solution, the (possibly) only other way to allow nodes to prune their shared</div><div>secret log is to periodically rotate keys. Once a node rotates a key, it can</div><div>safely delete its *entire* previous shared secret log, as replay attacks will</div><div>fail on the HMAC check. Independent of replay attack prevention, key rotation</div><div>is useful in order to provide a degree of forward secrecy. Without key</div><div>rotation, when a node is compromised by the adversary (assuming the node keeps</div><div>*all* prior mix-headers), the adversary learns of the next-node within the</div><div>route, and also the per-hop payload for the compromised node. With key</div><div>rotation, assuming the prior keys are deleted, then the adversary is only able</div><div>to decrypt partially ciphertexts from the current epoch.</div><div><br></div><div>So then a question arises: how do we perform key rotation within the network</div><div>globally with loose synchronization? I say loose synchronization since if</div><div>rotations aren&#39;t synchronized to a degree, then the payments of source nodes</div><div>may fail as an intermediate hop is unable to process the packet since it used an</div><div>obsolete onion key. Therefore published onion keys should come in pairs (with</div><div>overlapping lifetimes), and also be authenticated by a node&#39;s identity key.</div><div><br></div><div>A key rotation scheme might look something like the following: </div><div>    * A node publishes two keys, along with a block hash of a block beyond a</div><div>      &quot;safe&quot; re-org distance, and a signature (under the identity pubkey)</div><div>      covering the advertisement.</div><div>    * The first key is intended for use until N blocks after the specified</div><div>      block hash, with nodes switching to the second key afterwards.</div><div>    * At the N/2 point, the original node publishes a new advertisement with</div><div>      the second key from the original advertisement listed as the &quot;first&quot; key,</div><div>      and a new fresh quasi-ephemeral onion key. The original node performs</div><div>      this rotation at intervals at the mid-point of expiration of the oldest</div><div>      key.</div><div>    * Nodes who receive this new advertisement (aware of the previous) record</div><div>      this as the node&#39;s next rotation key. Nodes who receive this</div><div>      advertisement, unaware of the previous treat this as the node&#39;s initial</div><div>      pair of quasi-ephemeral onion keys.</div><div><br></div><div>With this scheme, rotations are synchronized very loosely, perhaps in the</div><div>timespan of half-days, days, etc. There is a new cost however, when processing</div><div>packets, a node must attempt to derive the shared secret with both active onion</div><div>keys. Alternatively, instead of block hashes, we can use some other time based</div><div>beacon as a switch over point in order to accommodate peers on multiple</div><div>blockchains.</div><div><br></div><div>I&#39;ll take a few more passes through the current draft spec, as well are your</div><div>commits in your fork of my original implementation, following up with any other</div><div>questions/comments.</div><div><br></div><div>-- Laolu</div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr">On Mon, Jul 25, 2016 at 9:23 AM Christian Decker &lt;<a href="mailto:decker.christian@gmail.com">decker.christian@gmail.com</a>&gt; wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi all,<div><br></div><div>I took the liberty of taking apart Olaoluwa&#39;s Sphinx implementation and I came up with a spec draft that I&#39;d like to propose [1]. It should roughly be Sphinx, pinning down the various key-generation and stream generation algorithms, and adding a per-hop payload.</div><div><br></div><div>The per-hop payload is used to give instructions to individual hops, i.e., how many coins to forward to the next hop. This means that the end-to-end payload, i.e., the message in the Sphinx protocol, is currently unused and could be omitted.</div><div><br></div><div>The payloads are currently fixed size (20 bytes per-hop and 1024 bytes for end-to-end payload) to avoid making messages collatable by their size. However, they could<span style="line-height:1.5"> easily be made variable should we decide that sending mostly empty messages is wasteful.</span></div><div><br></div><div>The spec is implemented in Go [2] and in C [3]. The Go version is an adaptation of Olaoluwa&#39;s implementation, with some minor speedups, removing some duplicate information, stripping the header, and switching to ChaCha20 for stream generation and encryption. I also added a small commandline tool that allows you to write packets to stdout so that we can feed an onion generated by the C version to the Go implementation and vice-versa :-)</div><div><br></div><div>Feedback is very welcome. If people like the draft I&#39;ll create pull-requests for the spec and the implementations, but I&#39;d like to keep the discussion on the mailing list :-)</div><div><br></div><div>Cheers,</div><div>Christian</div><div><br></div><div>[1] <a href="https://github.com/cdecker/lightning-rfc/blob/master/bolts/onion-protocol.md" target="_blank">https://github.com/cdecker/lightning-rfc/blob/master/bolts/onion-protocol.md</a></div><div>[2] <a href="https://github.com/cdecker/lightning-onion/tree/chacha20" target="_blank">https://github.com/cdecker/lightning-onion/tree/chacha20</a></div><div>[3] <a href="https://github.com/cdecker/lightning/tree/chacha20" target="_blank">https://github.com/cdecker/lightning/tree/chacha20</a></div></div>
_______________________________________________<br>
Lightning-dev mailing list<br>
<a href="mailto:Lightning-dev@lists.linuxfoundation.org" target="_blank">Lightning-dev@lists.linuxfoundation.org</a><br>
<a href="https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev" rel="noreferrer" target="_blank">https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev</a><br>
</blockquote></div>