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