<div dir="ltr"><div dir="ltr"><div>Hi Conner,</div><div><br></div><div>thanks for the pointers, looking forward to reading up on the</div><div>wrap resistance. I don&#39;t quite follow if you&#39;re against the</div><div>re-wrapping for spontaneous re-routing, or the entire rendez-vous</div><div>construction we came up with in Australia. If it&#39;s the latter, do</div><div>you have an alternative construction that we might look at?</div><div>Hornet requires the onion-in-onion initial sphinx setup IIRC</div><div>which is pretty much what we came up with here (with the</div><div>exception that we manage to have the second onion be hidden in</div><div>the first one&#39;s header instead of the payload).</div><div><br></div><div>Cheers,</div><div>Christian</div><div><br></div><div class="gmail_quote"><div dir="ltr">On Tue, Nov 13, 2018 at 9:21 PM Conner Fromknecht &lt;conner@lightning.engineering&gt; wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Good morning all,<br>
<br>
Taking a step back—even if key switching can be done mathematically, it seems<br>
dubious that we would want to introduce re-routing or rendezvous routing in this<br>
manner. If the example provided _could_ be done, it would directly violate the<br>
wrap-resistance property of the ideal onion routing scheme defined in [1]. This<br>
property is proven for Sphinx in section 4.3 of [2]. Schemes like HORNET [3]<br>
support rendezvous routing and are formally proven in this model. Seems this<br>
would be the obvious path forward, given that we&#39;ve already done a considerable<br>
amount of work towards implementing HORNET via Sphinx.<br>
<br>
Cheers,<br>
Conner<br>
<br>
[1] A Formal Treatment of Onion Routing:<br>
<a href="https://www.iacr.org/cryptodb/archive/2005/CRYPTO/1091/1091.pdf" rel="noreferrer" target="_blank">https://www.iacr.org/cryptodb/archive/2005/CRYPTO/1091/1091.pdf</a><br>
[2] Sphinx: <a href="https://cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf" rel="noreferrer" target="_blank">https://cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf</a><br>
[3] HORNET: <a href="https://arxiv.org/pdf/1507.05724.pdf" rel="noreferrer" target="_blank">https://arxiv.org/pdf/1507.05724.pdf</a><br>
On Mon, Nov 12, 2018 at 8:47 PM ZmnSCPxj via Lightning-dev<br>
&lt;<a href="mailto:lightning-dev@lists.linuxfoundation.org" target="_blank">lightning-dev@lists.linuxfoundation.org</a>&gt; wrote:<br>
&gt;<br>
&gt; Good morning Christian,<br>
&gt;<br>
&gt; I am nowhere near a mathematician, thus, cannot countercheck your expertise here (and cannot give a counterproposal thusly).<br>
&gt;<br>
&gt; But I want to point out the below scenarios:<br>
&gt;<br>
&gt; 1.  C is the payer.  He is in contact with an unknown payee (who in reality is E).  E provides the onion-wrapped route D-&gt;E with ephemeral key and other data necessary, as well as informing C that D is the rendez-vous point.  Then C creates a route from itself to D (via channel C-&gt;D or via C-&gt;A-&gt;D).<br>
&gt;<br>
&gt; 2.  B is the payer.  He knows the entire route B-&gt;C-&gt;D-&gt;E and knows that payee is C.  Unfortunately the C&lt;-&gt;D channel is low capacity or down or etc etc.  At C, B has provided the onion-wrapped route D-&gt;E with ephemeral key and other data necessary, as well as informing to C that D is the next node.  Then C either pays via C-&gt;D or via C-&gt;A-&gt;D.<br>
&gt;<br>
&gt; Even if there is an off-by-one error in our thinking about rendez-vous nodes, could it not be compensated also by an off-by-one in the link-level payment splitting via intermediary rendez-vous node?<br>
&gt; In short, D is the one that switches keys instead of A.<br>
&gt;<br>
&gt; The operation of processing a hop would be:<br>
&gt;<br>
&gt; 1.  Unwrap the onion with current ephemeral key.<br>
&gt; 2.  Dispatch based on realm byte.<br>
&gt; 2.1.  If realm byte 0:<br>
&gt; 2.1.1.  Normal routing behavior, extract HMAC, etc etc<br>
&gt; 2.2.  If realm byte 2 &quot;switch ephemeral keys&quot;:<br>
&gt; 2.2.1.  Set current ephemeral key to bytes 1 -&gt; 32 of packet.<br>
&gt; 2.2.2.  Shift onion by one hop packet.<br>
&gt; 2.2.3.  Goto 1.<br>
&gt;<br>
&gt; Would that not work?<br>
&gt; (I am being naive here, as I am not a mathist and I did not understand half what you wrote, sorry)<br>
&gt;<br>
&gt; Then at C, we have the onion from D-&gt;E, we also know the next ephemeral key to use (we can derive it since we would pass it to D anyway).<br>
&gt; It rightshifts the onion by one, storing the next ephemeral key to the new hop it just allocated.<br>
&gt; Then it encrypts the onion using a new ephemeral key that it will use to generate the D&lt;-A&lt;-C part of the onion.<br>
&gt;<br>
&gt; Regards,<br>
&gt; ZmnSCPxj<br>
&gt;<br>
&gt;<br>
&gt; Sent with ProtonMail Secure Email.<br>
&gt;<br>
&gt; ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐<br>
&gt; On Tuesday, November 13, 2018 11:45 AM, Christian Decker &lt;<a href="mailto:decker.christian@gmail.com" target="_blank">decker.christian@gmail.com</a>&gt; wrote:<br>
&gt;<br>
&gt; &gt; Great proposal ZmnSCPxj, but I think I need to raise a small issue with<br>
&gt; &gt; it. While writing up the proposal for rendez-vous I came across a<br>
&gt; &gt; problem with the mechanism I described during the spec meeting: the<br>
&gt; &gt; padding at the rendez-vous point would usually zero-padded and then<br>
&gt; &gt; encrypted in one go with the shared secret that was generated from the<br>
&gt; &gt; previous ephemeral key (i.e., the one before the switch). That ephemeral<br>
&gt; &gt; key is not known to the recipient (barring additional rounds of<br>
&gt; &gt; communication) so the recipient would be unable to compute the correct<br>
&gt; &gt; MACs. There are a number of solutions to this, basically setting the<br>
&gt; &gt; padding to something that the recipient could know when generating its<br>
&gt; &gt; half onion.<br>
&gt; &gt;<br>
&gt; &gt; My current favorite goes like this:<br>
&gt; &gt;<br>
&gt; &gt; 1.  Rendez-vous RV receives an onion, performs ECDH like normal to get<br>
&gt; &gt;     the shared secret, decrypts its payload, simultaneously encrypts<br>
&gt; &gt;     the padding.<br>
&gt; &gt;<br>
&gt; &gt; 2.  It extracts its per-hop payload and shifts the entire packet over<br>
&gt; &gt;     (shift its payload out and the newly generated padding in)<br>
&gt; &gt;<br>
&gt; &gt; 3.  It then notices that it should perform an ephemeral key switch, now<br>
&gt; &gt;     deviating from the normal protocol (which would just be to generate<br>
&gt; &gt;     the new ephemeral key, serialize and forward)<br>
&gt; &gt;     3.1. It zero-fills the padding that it just added (so we are in a<br>
&gt; &gt;     state that the recipient knew when generating its partial onion<br>
&gt; &gt;     3.2 It performs ECDH with the switched in ephemeral key to get a new<br>
&gt; &gt;     shared secret that which is then used to unwrap one additional<br>
&gt; &gt;     layer of encryption, and most importantly encrypt the padding so<br>
&gt; &gt;     the next hop doesn&#39;t see the zero-filled padding.<br>
&gt; &gt;     3.3 Only then will it generate the new ephemeral key for the next<br>
&gt; &gt;     hop, based on the switched in ephemeral key and the newly<br>
&gt; &gt;     generated shared secret, serialize the packet and forward it.<br>
&gt; &gt;<br>
&gt; &gt;     This has the advantage of reusing all the existing machinery but<br>
&gt; &gt;     assembling it a bit differently, by adding a little detour when<br>
&gt; &gt;     generating the next onion. It involves one additional ECDH at the<br>
&gt; &gt;     rendez-vous, one ChaCha20 encryption and one scalar multiplication to<br>
&gt; &gt;     generate the next ephemeral keys. It does not need more space than the<br>
&gt; &gt;     single ephemeral key in the per-hop payload.<br>
&gt; &gt;<br>
&gt; &gt;     And now for the reason that I write this as a reply to your post: with<br>
&gt; &gt;     this scheme it is not possible for C to find an ephemeral key that would<br>
&gt; &gt;     end up identical to the one that D would require to decrypt the onion<br>
&gt; &gt;     correctly. This would not be an issue if D is informed about this split<br>
&gt; &gt;     and would basically accept whatever it gets, but that kind of defeats<br>
&gt; &gt;     the transparency that you were going for with your proposal.<br>
&gt; &gt;<br>
&gt; &gt;     I&#39;m open for other proposals but I currently can&#39;t think of a way to<br>
&gt; &gt;     make sure that a) the recipient can deterministically generate the same<br>
&gt; &gt;     padding that RV will generate, and b) hide the fact that RV was indeed a<br>
&gt; &gt;     rendez-vous point (e.g., by leaving the padding be a well known<br>
&gt; &gt;     constant).<br>
&gt; &gt;<br>
&gt; &gt;     Sorry for this problem, I had a mental off-by-one at the meeting that I<br>
&gt; &gt;     hadn&#39;t considered, the solution should work, but it makes this kind of<br>
&gt; &gt;     things a bit harder.<br>
&gt; &gt;<br>
&gt; &gt;     Cheers,<br>
&gt; &gt;     Christian<br>
&gt; &gt;<br>
&gt; &gt;     ZmnSCPxj via Lightning-dev <a href="mailto:lightning-dev@lists.linuxfoundation.org" target="_blank">lightning-dev@lists.linuxfoundation.org</a><br>
&gt; &gt;<br>
&gt; &gt;<br>
&gt; &gt; writes:<br>
&gt; &gt;<br>
&gt; &gt; &gt; Good morning list,<br>
&gt; &gt; &gt; As was discussed directly in summit, we accept link-lvel payment splitting (scid is not binding), and provisionally accept rendez-vous routing.<br>
&gt; &gt; &gt; It strikes me, that even if your node has only a single channel to the next node (c-lightning), it is possible, to still perform link-level payment splitting/re-routing.<br>
&gt; &gt; &gt; For instance, consider this below graph:<br>
&gt; &gt; &gt;<br>
&gt; &gt; &gt;       E&lt;---D---&gt;C&lt;---B<br>
&gt; &gt; &gt;            ^  /<br>
&gt; &gt; &gt;            | /<br>
&gt; &gt; &gt;            |L<br>
&gt; &gt; &gt;            A<br>
&gt; &gt; &gt;<br>
&gt; &gt; &gt;<br>
&gt; &gt; &gt; In the above, B requests a route from B-&gt;C-&gt;D-&gt;E.<br>
&gt; &gt; &gt; However, C cannot send to D, since the channel direction is saturated in favor of D.<br>
&gt; &gt; &gt; Alternately, C can route to D via A instead. It holds the (encrypted) route from D to E. It can take that sub-route and treat it as a partial route-to-payee under rendez-vous routing, as long as node A supports rendez-vous routing.<br>
&gt; &gt; &gt; This can allow re-routing or payment splitting over multiple hops.<br>
&gt; &gt; &gt; Even though C does not know the number of remaining hops between D and the destination, its alternative is to earn nothing anyway as its only alternative is to fail the routing. At least with this, there is a chance it can succeed to send the payment to the final destination.<br>
&gt; &gt; &gt; Regards,<br>
&gt; &gt; &gt; ZmnSCPxj<br>
&gt; &gt; &gt;<br>
&gt; &gt; &gt; Lightning-dev mailing list<br>
&gt; &gt; &gt; <a href="mailto:Lightning-dev@lists.linuxfoundation.org" target="_blank">Lightning-dev@lists.linuxfoundation.org</a><br>
&gt; &gt; &gt; <a href="https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev" rel="noreferrer" target="_blank">https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev</a><br>
&gt;<br>
&gt;<br>
&gt; _______________________________________________<br>
&gt; Lightning-dev mailing list<br>
&gt; <a href="mailto:Lightning-dev@lists.linuxfoundation.org" target="_blank">Lightning-dev@lists.linuxfoundation.org</a><br>
&gt; <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></div></div>