📅 Original date posted:2018-11-13
📝 Original message:
Good morning all,
Taking a step back—even if key switching can be done mathematically, it seems
dubious that we would want to introduce re-routing or rendezvous routing in this
manner. If the example provided _could_ be done, it would directly violate the
wrap-resistance property of the ideal onion routing scheme defined in [1]. This
property is proven for Sphinx in section 4.3 of [2]. Schemes like HORNET [3]
support rendezvous routing and are formally proven in this model. Seems this
would be the obvious path forward, given that we've already done a considerable
amount of work towards implementing HORNET via Sphinx.
Cheers,
Conner
[1] A Formal Treatment of Onion Routing:
https://www.iacr.org/cryptodb/archive/2005/CRYPTO/1091/1091.pdf
[2] Sphinx: https://cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf
[3] HORNET: https://arxiv.org/pdf/1507.05724.pdf
On Mon, Nov 12, 2018 at 8:47 PM ZmnSCPxj via Lightning-dev
<lightning-dev at lists.linuxfoundation.org> wrote:
>
> Good morning Christian,
>
> I am nowhere near a mathematician, thus, cannot countercheck your expertise here (and cannot give a counterproposal thusly).
>
> But I want to point out the below scenarios:
>
> 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->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->D or via C->A->D).
>
> 2. B is the payer. He knows the entire route B->C->D->E and knows that payee is C. Unfortunately the C<->D channel is low capacity or down or etc etc. At C, B has provided the onion-wrapped route D->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->D or via C->A->D.
>
> 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?
> In short, D is the one that switches keys instead of A.
>
> The operation of processing a hop would be:
>
> 1. Unwrap the onion with current ephemeral key.
> 2. Dispatch based on realm byte.
> 2.1. If realm byte 0:
> 2.1.1. Normal routing behavior, extract HMAC, etc etc
> 2.2. If realm byte 2 "switch ephemeral keys":
> 2.2.1. Set current ephemeral key to bytes 1 -> 32 of packet.
> 2.2.2. Shift onion by one hop packet.
> 2.2.3. Goto 1.
>
> Would that not work?
> (I am being naive here, as I am not a mathist and I did not understand half what you wrote, sorry)
>
> Then at C, we have the onion from D->E, we also know the next ephemeral key to use (we can derive it since we would pass it to D anyway).
> It rightshifts the onion by one, storing the next ephemeral key to the new hop it just allocated.
> Then it encrypts the onion using a new ephemeral key that it will use to generate the D<-A<-C part of the onion.
>
> Regards,
> ZmnSCPxj
>
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> On Tuesday, November 13, 2018 11:45 AM, Christian Decker <decker.christian at gmail.com> wrote:
>
> > Great proposal ZmnSCPxj, but I think I need to raise a small issue with
> > it. While writing up the proposal for rendez-vous I came across a
> > problem with the mechanism I described during the spec meeting: the
> > padding at the rendez-vous point would usually zero-padded and then
> > encrypted in one go with the shared secret that was generated from the
> > previous ephemeral key (i.e., the one before the switch). That ephemeral
> > key is not known to the recipient (barring additional rounds of
> > communication) so the recipient would be unable to compute the correct
> > MACs. There are a number of solutions to this, basically setting the
> > padding to something that the recipient could know when generating its
> > half onion.
> >
> > My current favorite goes like this:
> >
> > 1. Rendez-vous RV receives an onion, performs ECDH like normal to get
> > the shared secret, decrypts its payload, simultaneously encrypts
> > the padding.
> >
> > 2. It extracts its per-hop payload and shifts the entire packet over
> > (shift its payload out and the newly generated padding in)
> >
> > 3. It then notices that it should perform an ephemeral key switch, now
> > deviating from the normal protocol (which would just be to generate
> > the new ephemeral key, serialize and forward)
> > 3.1. It zero-fills the padding that it just added (so we are in a
> > state that the recipient knew when generating its partial onion
> > 3.2 It performs ECDH with the switched in ephemeral key to get a new
> > shared secret that which is then used to unwrap one additional
> > layer of encryption, and most importantly encrypt the padding so
> > the next hop doesn't see the zero-filled padding.
> > 3.3 Only then will it generate the new ephemeral key for the next
> > hop, based on the switched in ephemeral key and the newly
> > generated shared secret, serialize the packet and forward it.
> >
> > This has the advantage of reusing all the existing machinery but
> > assembling it a bit differently, by adding a little detour when
> > generating the next onion. It involves one additional ECDH at the
> > rendez-vous, one ChaCha20 encryption and one scalar multiplication to
> > generate the next ephemeral keys. It does not need more space than the
> > single ephemeral key in the per-hop payload.
> >
> > And now for the reason that I write this as a reply to your post: with
> > this scheme it is not possible for C to find an ephemeral key that would
> > end up identical to the one that D would require to decrypt the onion
> > correctly. This would not be an issue if D is informed about this split
> > and would basically accept whatever it gets, but that kind of defeats
> > the transparency that you were going for with your proposal.
> >
> > I'm open for other proposals but I currently can't think of a way to
> > make sure that a) the recipient can deterministically generate the same
> > padding that RV will generate, and b) hide the fact that RV was indeed a
> > rendez-vous point (e.g., by leaving the padding be a well known
> > constant).
> >
> > Sorry for this problem, I had a mental off-by-one at the meeting that I
> > hadn't considered, the solution should work, but it makes this kind of
> > things a bit harder.
> >
> > Cheers,
> > Christian
> >
> > ZmnSCPxj via Lightning-dev lightning-dev at lists.linuxfoundation.org
> >
> >
> > writes:
> >
> > > Good morning list,
> > > As was discussed directly in summit, we accept link-lvel payment splitting (scid is not binding), and provisionally accept rendez-vous routing.
> > > 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.
> > > For instance, consider this below graph:
> > >
> > > E<---D--->C<---B
> > > ^ /
> > > | /
> > > |L
> > > A
> > >
> > >
> > > In the above, B requests a route from B->C->D->E.
> > > However, C cannot send to D, since the channel direction is saturated in favor of D.
> > > 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.
> > > This can allow re-routing or payment splitting over multiple hops.
> > > 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.
> > > Regards,
> > > ZmnSCPxj
> > >
> > > Lightning-dev mailing list
> > > Lightning-dev at lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Conner Fromknecht [ARCHIVE] /
npub1za…uua2a
2023-06-09 12:52:25
in reply to nevent1q…salv
Author Public Key
npub1za0a9afyj7um5feva0d5xmhfsah3zxm252hna2duq0numa952frqvuua2aPublished at
2023-06-09 12:52:25Event JSON
{
"id": "c5cac222b9f7e477a6df572d8bb71c8ff1ab9b3c1eaeb10d70d14a2793efbd77",
"pubkey": "175fd2f52497b9ba272cebdb436ee9876f111b6aa2af3ea9bc03e7cdf4b45246",
"created_at": 1686315145,
"kind": 1,
"tags": [
[
"e",
"f4b5ffab7a9c96d8928a76b4653d399422785cf29dac19cdb8e24eff6d895c9a",
"",
"root"
],
[
"e",
"89a8728aba8f0a4e38c14b116b5d4964d1bee088bde630cc6edc47faf072e0e3",
"",
"reply"
],
[
"p",
"4505072744a9d3e490af9262bfe38e6ee5338a77177b565b6b37730b63a7b861"
]
],
"content": "📅 Original date posted:2018-11-13\n📝 Original message:\nGood morning all,\n\nTaking a step back—even if key switching can be done mathematically, it seems\ndubious that we would want to introduce re-routing or rendezvous routing in this\nmanner. If the example provided _could_ be done, it would directly violate the\nwrap-resistance property of the ideal onion routing scheme defined in [1]. This\nproperty is proven for Sphinx in section 4.3 of [2]. Schemes like HORNET [3]\nsupport rendezvous routing and are formally proven in this model. Seems this\nwould be the obvious path forward, given that we've already done a considerable\namount of work towards implementing HORNET via Sphinx.\n\nCheers,\nConner\n\n[1] A Formal Treatment of Onion Routing:\nhttps://www.iacr.org/cryptodb/archive/2005/CRYPTO/1091/1091.pdf\n[2] Sphinx: https://cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf\n[3] HORNET: https://arxiv.org/pdf/1507.05724.pdf\nOn Mon, Nov 12, 2018 at 8:47 PM ZmnSCPxj via Lightning-dev\n\u003clightning-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\n\u003e Good morning Christian,\n\u003e\n\u003e I am nowhere near a mathematician, thus, cannot countercheck your expertise here (and cannot give a counterproposal thusly).\n\u003e\n\u003e But I want to point out the below scenarios:\n\u003e\n\u003e 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-\u003eE 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-\u003eD or via C-\u003eA-\u003eD).\n\u003e\n\u003e 2. B is the payer. He knows the entire route B-\u003eC-\u003eD-\u003eE and knows that payee is C. Unfortunately the C\u003c-\u003eD channel is low capacity or down or etc etc. At C, B has provided the onion-wrapped route D-\u003eE 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-\u003eD or via C-\u003eA-\u003eD.\n\u003e\n\u003e 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?\n\u003e In short, D is the one that switches keys instead of A.\n\u003e\n\u003e The operation of processing a hop would be:\n\u003e\n\u003e 1. Unwrap the onion with current ephemeral key.\n\u003e 2. Dispatch based on realm byte.\n\u003e 2.1. If realm byte 0:\n\u003e 2.1.1. Normal routing behavior, extract HMAC, etc etc\n\u003e 2.2. If realm byte 2 \"switch ephemeral keys\":\n\u003e 2.2.1. Set current ephemeral key to bytes 1 -\u003e 32 of packet.\n\u003e 2.2.2. Shift onion by one hop packet.\n\u003e 2.2.3. Goto 1.\n\u003e\n\u003e Would that not work?\n\u003e (I am being naive here, as I am not a mathist and I did not understand half what you wrote, sorry)\n\u003e\n\u003e Then at C, we have the onion from D-\u003eE, we also know the next ephemeral key to use (we can derive it since we would pass it to D anyway).\n\u003e It rightshifts the onion by one, storing the next ephemeral key to the new hop it just allocated.\n\u003e Then it encrypts the onion using a new ephemeral key that it will use to generate the D\u003c-A\u003c-C part of the onion.\n\u003e\n\u003e Regards,\n\u003e ZmnSCPxj\n\u003e\n\u003e\n\u003e Sent with ProtonMail Secure Email.\n\u003e\n\u003e ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐\n\u003e On Tuesday, November 13, 2018 11:45 AM, Christian Decker \u003cdecker.christian at gmail.com\u003e wrote:\n\u003e\n\u003e \u003e Great proposal ZmnSCPxj, but I think I need to raise a small issue with\n\u003e \u003e it. While writing up the proposal for rendez-vous I came across a\n\u003e \u003e problem with the mechanism I described during the spec meeting: the\n\u003e \u003e padding at the rendez-vous point would usually zero-padded and then\n\u003e \u003e encrypted in one go with the shared secret that was generated from the\n\u003e \u003e previous ephemeral key (i.e., the one before the switch). That ephemeral\n\u003e \u003e key is not known to the recipient (barring additional rounds of\n\u003e \u003e communication) so the recipient would be unable to compute the correct\n\u003e \u003e MACs. There are a number of solutions to this, basically setting the\n\u003e \u003e padding to something that the recipient could know when generating its\n\u003e \u003e half onion.\n\u003e \u003e\n\u003e \u003e My current favorite goes like this:\n\u003e \u003e\n\u003e \u003e 1. Rendez-vous RV receives an onion, performs ECDH like normal to get\n\u003e \u003e the shared secret, decrypts its payload, simultaneously encrypts\n\u003e \u003e the padding.\n\u003e \u003e\n\u003e \u003e 2. It extracts its per-hop payload and shifts the entire packet over\n\u003e \u003e (shift its payload out and the newly generated padding in)\n\u003e \u003e\n\u003e \u003e 3. It then notices that it should perform an ephemeral key switch, now\n\u003e \u003e deviating from the normal protocol (which would just be to generate\n\u003e \u003e the new ephemeral key, serialize and forward)\n\u003e \u003e 3.1. It zero-fills the padding that it just added (so we are in a\n\u003e \u003e state that the recipient knew when generating its partial onion\n\u003e \u003e 3.2 It performs ECDH with the switched in ephemeral key to get a new\n\u003e \u003e shared secret that which is then used to unwrap one additional\n\u003e \u003e layer of encryption, and most importantly encrypt the padding so\n\u003e \u003e the next hop doesn't see the zero-filled padding.\n\u003e \u003e 3.3 Only then will it generate the new ephemeral key for the next\n\u003e \u003e hop, based on the switched in ephemeral key and the newly\n\u003e \u003e generated shared secret, serialize the packet and forward it.\n\u003e \u003e\n\u003e \u003e This has the advantage of reusing all the existing machinery but\n\u003e \u003e assembling it a bit differently, by adding a little detour when\n\u003e \u003e generating the next onion. It involves one additional ECDH at the\n\u003e \u003e rendez-vous, one ChaCha20 encryption and one scalar multiplication to\n\u003e \u003e generate the next ephemeral keys. It does not need more space than the\n\u003e \u003e single ephemeral key in the per-hop payload.\n\u003e \u003e\n\u003e \u003e And now for the reason that I write this as a reply to your post: with\n\u003e \u003e this scheme it is not possible for C to find an ephemeral key that would\n\u003e \u003e end up identical to the one that D would require to decrypt the onion\n\u003e \u003e correctly. This would not be an issue if D is informed about this split\n\u003e \u003e and would basically accept whatever it gets, but that kind of defeats\n\u003e \u003e the transparency that you were going for with your proposal.\n\u003e \u003e\n\u003e \u003e I'm open for other proposals but I currently can't think of a way to\n\u003e \u003e make sure that a) the recipient can deterministically generate the same\n\u003e \u003e padding that RV will generate, and b) hide the fact that RV was indeed a\n\u003e \u003e rendez-vous point (e.g., by leaving the padding be a well known\n\u003e \u003e constant).\n\u003e \u003e\n\u003e \u003e Sorry for this problem, I had a mental off-by-one at the meeting that I\n\u003e \u003e hadn't considered, the solution should work, but it makes this kind of\n\u003e \u003e things a bit harder.\n\u003e \u003e\n\u003e \u003e Cheers,\n\u003e \u003e Christian\n\u003e \u003e\n\u003e \u003e ZmnSCPxj via Lightning-dev lightning-dev at lists.linuxfoundation.org\n\u003e \u003e\n\u003e \u003e\n\u003e \u003e writes:\n\u003e \u003e\n\u003e \u003e \u003e Good morning list,\n\u003e \u003e \u003e As was discussed directly in summit, we accept link-lvel payment splitting (scid is not binding), and provisionally accept rendez-vous routing.\n\u003e \u003e \u003e 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.\n\u003e \u003e \u003e For instance, consider this below graph:\n\u003e \u003e \u003e\n\u003e \u003e \u003e E\u003c---D---\u003eC\u003c---B\n\u003e \u003e \u003e ^ /\n\u003e \u003e \u003e | /\n\u003e \u003e \u003e |L\n\u003e \u003e \u003e A\n\u003e \u003e \u003e\n\u003e \u003e \u003e\n\u003e \u003e \u003e In the above, B requests a route from B-\u003eC-\u003eD-\u003eE.\n\u003e \u003e \u003e However, C cannot send to D, since the channel direction is saturated in favor of D.\n\u003e \u003e \u003e 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.\n\u003e \u003e \u003e This can allow re-routing or payment splitting over multiple hops.\n\u003e \u003e \u003e 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.\n\u003e \u003e \u003e Regards,\n\u003e \u003e \u003e ZmnSCPxj\n\u003e \u003e \u003e\n\u003e \u003e \u003e Lightning-dev mailing list\n\u003e \u003e \u003e Lightning-dev at lists.linuxfoundation.org\n\u003e \u003e \u003e https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev\n\u003e\n\u003e\n\u003e _______________________________________________\n\u003e Lightning-dev mailing list\n\u003e Lightning-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev",
"sig": "cd8d7f6ce881931946d77d4c5b846310692be8066c0ddee7229d8c040b2a6dd9841e5b6a55165b4518205659291f1436b7b0c5d2d8a2b9f177895c83c9736299"
}