Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-13 Thread Bastien TEINTURIER
Damn you're good.

Le jeu. 13 févr. 2020 à 11:44, ZmnSCPxj  a écrit :

> Good morning t-bast,
>
> > > Propose we take the `z` to use as bolt11 letter, because even the
> French
> > > don't pronounce it in "rendez-vous"!)
> >
> > As long as Z-man didn't want to claim this bolt11 letter for himself or
> his
> > puppet army, that sounds good :).
>
> That would be too obvious.
> What I *am* claiming is `8` for my own use and for my non-existent army of
> city-marching robots, because it does not appear in my public alias at all,
> thus actively misleading surveillors.
>
> Regards,
> ZmnSCPxj
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-13 Thread ZmnSCPxj via Lightning-dev
Good morning t-bast,

> > Propose we take the `z` to use as bolt11 letter, because even the French
> > don't pronounce it in "rendez-vous"!)
>
> As long as Z-man didn't want to claim this bolt11 letter for himself or his
> puppet army, that sounds good :).

That would be too obvious.
What I *am* claiming is `8` for my own use and for my non-existent army of 
city-marching robots, because it does not appear in my public alias at all, 
thus actively misleading surveillors.

Regards,
ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-13 Thread Bastien TEINTURIER
Hey Rusty and list,

I was starting to think this whole thing was of marginal benefit: note
> that solving "private channels need a temp scid" is far simpler[1].


That's true, the simpler solution does break the on-chain / off-chain link
but
I think we can take this opportunity to also improve payee privacy to make
sure
two invoices can't leak that they are from the same payee.

Even better, this would be a replacement for current route hints


Definitely, this is clearly a good opportunity to re-work route hints to
something that can fix all the short-comings of current route hints, thanks
for
your suggestions on that. And if anyone on this list has other fields that
may
be useful in these new route hints, please do say it.

Propose we take the `z` to use as bolt11 letter, because even the French
> don't pronounce it in "rendez-vous"!)


As long as Z-man didn't want to claim this bolt11 letter for himself or his
puppet army, that sounds good :).

I'll get started on an implementation, and will start working on a spec PR
as
well. I'm hoping to get more reviews from anyone experienced with both
lightning and cryptography to verify that the scheme isn't broken. I'm still
offering beers and cocktails to anyone who cracks it [1]!

Thanks!
Bastien

[1] https://twitter.com/realtbast/status/1227233654503505925

Le jeu. 13 févr. 2020 à 05:49, Rusty Russell  a
écrit :
>
> Bastien TEINTURIER  writes:
> > Hi Rusty,
> >
> > Thanks for the answer, and good luck with c-lightning 0.8.1-rc1 ;)
>
> ... Now -rc2.  I actually had a RL use for lightning (OMG!), and sure
> enough found a bug.
>
> > I've been thinking more about improving my scheme to not require any
sender
> > change, but I don't think that's possible at the moment. As with all
> > Lightning
> > tricks though, once we have Schnorr then it's really easy to do.
> > Alice simply needs to use `s * d_a` as her "preimage" (and the payment
point
> > becomes the P_I Bob needs). That may depend on the exact multi-hop locks
> > construction we end up using though, so I'm not 100% sure about that
yet.
>
> I was starting to think this whole thing was of marginal benefit: note
> that solving "private channels need a temp scid" is far simpler[1].
>
> But since your scheme extends to rendevous, it's much more tempting!
>
> We would use this for normal private channels as well as private routes
> aka new rendezvous.  Even better, this would be a replacement for
> current route hints (which lack ability to specify feature bits, which
> we would add here, and is also grossly inefficient if you just want to
> use it for Routeboost[2]).
>
> Propose we take the `z` to use as bolt11 letter, because even the French
> don't pronounce it in "rendez-vous"!)
>
> Then use TLV inside:[3]
>
> * `z` (2): `data_length` variable. One or more entries containing extra
>   routing information; there may be more than one `z` field.  Each entry
>   looks like:
>* `tlv_len` (8 bits)
>* `rendezvous_tlv` (tlv_len bytes)
>
> 1. tlvs: `rendezvous_tlv`
> 2. types:
>1. type: 1 (`pubkey`)
>2. data:
>   * [`point`:`nodeid`]
>1. type: 2 (`short_channel_id`)
>2. data:
>   * [`short_channel_id`:`short_channel_id`]
>1. type: 3 (`fee_base_msat`)
>2. data:
>   * [`tu32`:`fee_base_msat`]
>1. type: 4 (`fee_proportional_millionths`)
>2. data:
>   * [`tu32`:`fee_proportional_millionths`]
>1. type: 5 (`cltv_expiry_delta`)
>2. data:
>   * [`tu16`:`cltv_expiry_delta`]
>1. type: 6 (`features`)
>2. data:
>   * [`...*byte`:`features`]
>
> That probably adds 6 bytes entry, but worth it I think.
>
> Cheers,
> Rusty.
>
> [1] Add a new field to 'funding_locked': "private_scid".  If both sides
> support 'option_private_scid' (?) then the "real" scid is no longer
> valid for routing, and we use the private scid.
>
> [2] It's enough to give the scid(s) in this case indicating where you
> have incoming capacity.
>
> [3] I'm really starting to dislike my bolt11 format.  We should probably
> start afresh with a TLV-based one, where signature covers the hash
> of each entry (so they can be easily externalized!), but that's a
> big, unrelated task.
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-12 Thread Rusty Russell
Bastien TEINTURIER  writes:
> Hi Rusty,
>
> Thanks for the answer, and good luck with c-lightning 0.8.1-rc1 ;)

... Now -rc2.  I actually had a RL use for lightning (OMG!), and sure
enough found a bug.

> I've been thinking more about improving my scheme to not require any sender
> change, but I don't think that's possible at the moment. As with all
> Lightning
> tricks though, once we have Schnorr then it's really easy to do.
> Alice simply needs to use `s * d_a` as her "preimage" (and the payment point
> becomes the P_I Bob needs). That may depend on the exact multi-hop locks
> construction we end up using though, so I'm not 100% sure about that yet.

I was starting to think this whole thing was of marginal benefit: note
that solving "private channels need a temp scid" is far simpler[1].

But since your scheme extends to rendevous, it's much more tempting!

We would use this for normal private channels as well as private routes
aka new rendezvous.  Even better, this would be a replacement for
current route hints (which lack ability to specify feature bits, which
we would add here, and is also grossly inefficient if you just want to
use it for Routeboost[2]).

Propose we take the `z` to use as bolt11 letter, because even the French
don't pronounce it in "rendez-vous"!)

Then use TLV inside:[3]

* `z` (2): `data_length` variable. One or more entries containing extra
  routing information; there may be more than one `z` field.  Each entry
  looks like:
   * `tlv_len` (8 bits)
   * `rendezvous_tlv` (tlv_len bytes)

1. tlvs: `rendezvous_tlv`
2. types:
   1. type: 1 (`pubkey`)
   2. data:
  * [`point`:`nodeid`]
   1. type: 2 (`short_channel_id`)
   2. data:
  * [`short_channel_id`:`short_channel_id`]
   1. type: 3 (`fee_base_msat`)
   2. data:
  * [`tu32`:`fee_base_msat`]
   1. type: 4 (`fee_proportional_millionths`)
   2. data:
  * [`tu32`:`fee_proportional_millionths`]
   1. type: 5 (`cltv_expiry_delta`)
   2. data:
  * [`tu16`:`cltv_expiry_delta`]
   1. type: 6 (`features`)
   2. data:
  * [`...*byte`:`features`]

That probably adds 6 bytes entry, but worth it I think.

Cheers,
Rusty.

[1] Add a new field to 'funding_locked': "private_scid".  If both sides
support 'option_private_scid' (?) then the "real" scid is no longer
valid for routing, and we use the private scid.

[2] It's enough to give the scid(s) in this case indicating where you
have incoming capacity.

[3] I'm really starting to dislike my bolt11 format.  We should probably
start afresh with a TLV-based one, where signature covers the hash
of each entry (so they can be easily externalized!), but that's a
big, unrelated task.
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-11 Thread Bastien TEINTURIER
Hi Rusty,

Thanks for the answer, and good luck with c-lightning 0.8.1-rc1 ;)

(I think we should probably ban forwarding to private channels,
> too, for similar reasons).


Can you detail why? I believe that forwarding through private channels can
actually be pretty useful in the future for payee privacy (more on that
later).

Note that with any self-assigned SCID schemes, Alice has to respond to
> unknown scids in update_add_htlc with some BADONION code (which makes
> *Bob* give Carol an error response, since Alice can't without revealing
> her identity).


I believe the difference is that in your scheme, Bob would answer with
`unknown_next_peer`. When instead Alice responds with a `BADONION`, the only
thing it reveals is that Alice does use the decoy feature (which Mallory
already knows because she has seen an invoice from Alice). As long as this
behavior is consistent throughout the network, I think both options offer
the
same privacy (unless I'm missing something).

I expect such payments to become
> significant, and as long as paying to a temporary id and paying to a
> private channel looks identical, it's too draconian to ban.


True, that must become the default flow for receiving payments on mobile
wallets.
Granted, my solution would take longer to deploy because it needs to be
added to
sender wallets before receivers can require it.

I've been thinking more about improving my scheme to not require any sender
change, but I don't think that's possible at the moment. As with all
Lightning
tricks though, once we have Schnorr then it's really easy to do.
Alice simply needs to use `s * d_a` as her "preimage" (and the payment point
becomes the P_I Bob needs). That may depend on the exact multi-hop locks
construction we end up using though, so I'm not 100% sure about that yet.

But I did come up with what could be an interesting development.
Nothing prevents the decoy scheme to be used for public channels too, and
for
multiple hops: that enables a cheap form of rendezvous that only costs a few
hundred bytes in the invoice.

Alice would select multiple hops to a rendezvous node, and would apply some
blinding to those hops' `node_id` and `scid`. Alice would include these
decoy
hops in the invoice `routing_hints` (only costs 51 bytes per hop instead of
a
full onion). Mallory would only learn an upper bound on the distance between
Alice and the rendezvous.

I have a detailed version of the scheme in a gist [1] if people want to
take a
deeper look and break it (beer on me to the first one who breaks the
scheme).

[1] https://gist.github.com/t-bast/9972bfe9523bb18395bdedb8dc691faf

Cheers,
Bastien

Le lun. 10 févr. 2020 à 04:40, Rusty Russell  a
écrit :
>
> Bastien TEINTURIER  writes:
> >> But Mallory can do the same attack, I think.  Just include the P_I from
> >> the wrong invoice for Bob.
> >
> > Good catch, that's true, thanks for keeping me honest there! In that
case
> > my proposal
> > would need the same mitigation as yours, Bob will need to include the
> > `scid` he received
> > in `update_add_htlc` (this is in fact not that hard once we allow TLV
> > extensions on every
> > message).
>
> Yes, I've added this to the PR.  Which gives a new validation path, I
> think:
>
> ## Figuring out what nodeid to use to decode onion
>
> 1. Look up scid from HTLC; if it didn't include one, use default.
> 2. Look up payment_hash; if no invoice is found, use default.
> 3. If invoice specified this scid, get nodeid and use that.
> 4. ... and refuse to forward the HTLC (it must terminate here).
>
> My plan is to add an argument to `invoice` which is an array of one or
> more scids: we get a temporary scids for each peer and use them in the
> routehints.  We also assign a random temporary nodeid to that invoice.
>
> The above algo is designed to ensure we behave like any other node which
> has no idea about this nodeid if Mallory:
>
> 1. tries to use a temporary node id on a normal channel to us.
> 2. tries to pay another invoice using this temporary node id.
> 3. tries to probe our outgoing channels using this routing hint
>(I think we should probably ban forwarding to private channels,
>too, for similar reasons).
>
> ---
>
> Note that with any self-assigned SCID schemes, Alice has to respond to
> unknown scids in update_add_htlc with some BADONION code (which makes
> *Bob* give Carol an error response, since Alice can't without revealing
> her identity).
>
> With Bob-assigned SCIDs, Alice simply needs to make him unallocate
> it before forgetting the invoice, so she will simply never see old
> invoices.
>
> (All these schemes give limited privacy, of course: Bob knows who Alice
> is, and fingerprinting and liveness attacks are always possible).
>
> > I'm extremely nervous about custodial lightning services restricting
> >> what they will pay to.  This is not theoretical: they will come under
> >> immense KYC pressure in the near future, which means they cannot pay
> >> arbitrary invoices.
> 1>>
> >
> > That's 

Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-09 Thread Rusty Russell
Bastien TEINTURIER  writes:
>> But Mallory can do the same attack, I think.  Just include the P_I from
>> the wrong invoice for Bob.
>
> Good catch, that's true, thanks for keeping me honest there! In that case
> my proposal
> would need the same mitigation as yours, Bob will need to include the
> `scid` he received
> in `update_add_htlc` (this is in fact not that hard once we allow TLV
> extensions on every
> message).

Yes, I've added this to the PR.  Which gives a new validation path, I
think:

## Figuring out what nodeid to use to decode onion

1. Look up scid from HTLC; if it didn't include one, use default.
2. Look up payment_hash; if no invoice is found, use default.
3. If invoice specified this scid, get nodeid and use that.
4. ... and refuse to forward the HTLC (it must terminate here).

My plan is to add an argument to `invoice` which is an array of one or
more scids: we get a temporary scids for each peer and use them in the
routehints.  We also assign a random temporary nodeid to that invoice.

The above algo is designed to ensure we behave like any other node which
has no idea about this nodeid if Mallory:

1. tries to use a temporary node id on a normal channel to us.
2. tries to pay another invoice using this temporary node id.
3. tries to probe our outgoing channels using this routing hint
   (I think we should probably ban forwarding to private channels,
   too, for similar reasons).

---

Note that with any self-assigned SCID schemes, Alice has to respond to
unknown scids in update_add_htlc with some BADONION code (which makes
*Bob* give Carol an error response, since Alice can't without revealing
her identity).

With Bob-assigned SCIDs, Alice simply needs to make him unallocate
it before forgetting the invoice, so she will simply never see old
invoices.

(All these schemes give limited privacy, of course: Bob knows who Alice
is, and fingerprinting and liveness attacks are always possible).

> I'm extremely nervous about custodial lightning services restricting
>> what they will pay to.  This is not theoretical: they will come under
>> immense KYC pressure in the near future, which means they cannot pay
>> arbitrary invoices.
1>>
>
> That's a very good point, thanks for raising this. However I believe that
> there are (and will be) enough
> non-custodial wallets to let motivated users pay whatever they want. Users
> can even run their own
> node to pay such invoices if needed.

Not if ln_strike (no, the other one!) is the future.

> If you are using a custodial wallet and KYC pressure kicks in, then
> regardless of that feature law may
> require users to completely reveal who they are paying, so even normal
> payments wouldn't protect
> them, don't you think? Regulation could for example disallow paying via
> unannounced channels entirely
> (or require you to show the funding tx associated to your unannounced
> channel).

Actually, as long as the same method is required for both normal private
channels (which will all use non-tx-based short_channel_ids in the near
future I hope!), I don't really mind.  I expect such payments to become
significant, and as long as paying to a temporary id and paying to a
private channel looks identical, it's too draconian to ban.  A business
would probably meet any KYC requirements by simply asking the user
(perhaps over a certain amount, etc).

(I've put my implementation on hold for a moment while I'm supposed to
be releasing 0.8.1-rc1 RSN!)

Cheers,
Rusty.
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-05 Thread ZmnSCPxj via Lightning-dev
Good morning Rusty,


> No, Bob can include the scid he used in the update_add_htlc message, so
> Alice can check.
>
> I'm extremely nervous about custodial lightning services restricting
> what they will pay to. This is not theoretical: they will come under
> immense KYC pressure in the near future, which means they cannot pay
> arbitrary invoices.
>
> Thus my preference for a system which doesn't add any requirements on
> the payer.

This adds requirements on Bob, so the KYC pressure could transfer to them 
instead.
This might be acceptable though, if the payer and Bob are on separate 
jurisdictions (i.e. Risk-Sharing), but then if the payer is on a custodial 
service as well, the custodial service can be pressured to inspect the routing 
hints of any invoice it is told to pay.

Which I suppose is the entire point of t-bast email.

Regards,
ZmnSCPxj

___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-05 Thread Bastien TEINTURIER
>
> But Mallory can do the same attack, I think.  Just include the P_I from
> the wrong invoice for Bob.
>

Good catch, that's true, thanks for keeping me honest there! In that case
my proposal
would need the same mitigation as yours, Bob will need to include the
`scid` he received
in `update_add_htlc` (this is in fact not that hard once we allow TLV
extensions on every
message).

I'm extremely nervous about custodial lightning services restricting
> what they will pay to.  This is not theoretical: they will come under
> immense KYC pressure in the near future, which means they cannot pay
> arbitrary invoices.
>

That's a very good point, thanks for raising this. However I believe that
there are (and will be) enough
non-custodial wallets to let motivated users pay whatever they want. Users
can even run their own
node to pay such invoices if needed.

If you are using a custodial wallet and KYC pressure kicks in, then
regardless of that feature law may
require users to completely reveal who they are paying, so even normal
payments wouldn't protect
them, don't you think? Regulation could for example disallow paying via
unannounced channels entirely
(or require you to show the funding tx associated to your unannounced
channel).

If we're taking into account such KYC pressure, then I believe none of the
solutions we can provide will
be useful. It will be up to the recipient to decide whether he thus wants
to use a normal invoice and
reveal his identity or pass on that payment.

What do you think? Do you believe `option_scid_assign` can do a better job
in such situations?

Cheers,
Bastien

Le mer. 5 févr. 2020 à 02:44, Rusty Russell  a
écrit :

> Bastien TEINTURIER  writes:
> > Hey again,
> >
> > Otherwise Mallory gets two invoices, and wants to know if they're
> >> actually the same node.  Inv1 has nodeid N1, routehint Bob->C1, Inv2 has
> >> nodeid N2, routehint Bob->C2.
> >
> > I think this attack is interesting. AFAICT my proposal defends against
> this
> > because of the way
> > `payment_secret` and `decoy_key` are both used to derive the `decoy_scid`
> > (but don't trust me, do
> > verify that I'm not missing something).
> >
> > If Mallory doesn't use both the right `decoy_node_id` and
> `payment_secret`
> > to compute `P_I`, Bob
> > will not decode that to a valid real `scid` and will return an
> > `unknown_next_peer` which is good
> > for privacy.
>
> But Mallory can do the same attack, I think.  Just include the P_I from
> the wrong invoice for Bob.
>
> > It seems to me that
> > https://github.com/lightningnetwork/lightning-rfc/pull/681 cannot defend
> > against this attack. If both invoices are currently valid, Bob will
> forward
> > an HTLC that uses N1
> > with C2 (because Bob has no way of knowing N1 from the onion, for privacy
> > reasons).
> > The only way I'd see to avoid is would be that Alice needs to share her
> > `decoy_node_id`s with
> > Bob (and the mapping to a `decoy_scid`) which means more state to
> > manage...but maybe I'm just
> > missing a better mitigation?
>
> No, Bob can include the scid he used in the update_add_htlc message, so
> Alice can check.
>
> I'm extremely nervous about custodial lightning services restricting
> what they will pay to.  This is not theoretical: they will come under
> immense KYC pressure in the near future, which means they cannot pay
> arbitrary invoices.
>
> Thus my preference for a system which doesn't add any requirements on
> the payer.
>
> Cheers,
> Rusty.
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-04 Thread Rusty Russell
Bastien TEINTURIER  writes:
> Hey again,
>
> Otherwise Mallory gets two invoices, and wants to know if they're
>> actually the same node.  Inv1 has nodeid N1, routehint Bob->C1, Inv2 has
>> nodeid N2, routehint Bob->C2.
>
> I think this attack is interesting. AFAICT my proposal defends against this
> because of the way
> `payment_secret` and `decoy_key` are both used to derive the `decoy_scid`
> (but don't trust me, do
> verify that I'm not missing something).
>
> If Mallory doesn't use both the right `decoy_node_id` and `payment_secret`
> to compute `P_I`, Bob
> will not decode that to a valid real `scid` and will return an
> `unknown_next_peer` which is good
> for privacy.

But Mallory can do the same attack, I think.  Just include the P_I from
the wrong invoice for Bob.

> It seems to me that
> https://github.com/lightningnetwork/lightning-rfc/pull/681 cannot defend
> against this attack. If both invoices are currently valid, Bob will forward
> an HTLC that uses N1
> with C2 (because Bob has no way of knowing N1 from the onion, for privacy
> reasons).
> The only way I'd see to avoid is would be that Alice needs to share her
> `decoy_node_id`s with
> Bob (and the mapping to a `decoy_scid`) which means more state to
> manage...but maybe I'm just
> missing a better mitigation?

No, Bob can include the scid he used in the update_add_htlc message, so
Alice can check.

I'm extremely nervous about custodial lightning services restricting
what they will pay to.  This is not theoretical: they will come under
immense KYC pressure in the near future, which means they cannot pay
arbitrary invoices.

Thus my preference for a system which doesn't add any requirements on
the payer.

Cheers,
Rusty.
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-04 Thread Bastien TEINTURIER
Hey again,

Otherwise Mallory gets two invoices, and wants to know if they're
> actually the same node.  Inv1 has nodeid N1, routehint Bob->C1, Inv2 has
> nodeid N2, routehint Bob->C2.
>

I think this attack is interesting. AFAICT my proposal defends against this
because of the way
`payment_secret` and `decoy_key` are both used to derive the `decoy_scid`
(but don't trust me, do
verify that I'm not missing something).

If Mallory doesn't use both the right `decoy_node_id` and `payment_secret`
to compute `P_I`, Bob
will not decode that to a valid real `scid` and will return an
`unknown_next_peer` which is good
for privacy.

It seems to me that
https://github.com/lightningnetwork/lightning-rfc/pull/681 cannot defend
against this attack. If both invoices are currently valid, Bob will forward
an HTLC that uses N1
with C2 (because Bob has no way of knowing N1 from the onion, for privacy
reasons).
The only way I'd see to avoid is would be that Alice needs to share her
`decoy_node_id`s with
Bob (and the mapping to a `decoy_scid`) which means more state to
manage...but maybe I'm just
missing a better mitigation?

Cheers,
Bastien

Le mar. 4 févr. 2020 à 15:09, Bastien TEINTURIER  a
écrit :

> I'm a bit confused, I don't know if the implementation work you're
> mentioning refers to my proposal
> or yours :).
>
> When you say `temporary id`, could you clarify whether you mean a
> temporary `node_id` or `scid`?
>
> Firstly, need to brute-force the onion against your N keys.
>
>
> This is probably the part that confuses me. Are you talking about Bob or
> Alice there?
> Alice can easily have her `decoy_node_id` be derived from her real
> `node_id`'s privacy key and the
> `payment_hash` or `payment_preimage`. When she receives a payment, she
> knows which `decoy_node_id`
> should have been used so she doesn't need to brute-force.
>
> That means Alice doesn't even have to change how she stores invoices. When
> Alice retrieves the
> invoice from her DB, if it has the `decoy_node_id` feature bit set, she
> knows she needs to derive
> the correct `node_id`. If it doesn't have that feature bit set, it's a
> "legacy" invoice and she has
> to use her real `node_id`.
>
> Now Mallory uses Bob->C2 to pay to N1 for Inv1. If it works, he knows it's
>> the same node issuing both invoices.
>
>
> Same, that wouldn't work because Alice can easily detect the mismatch and
> pretend she can't decrypt
> the onion (the code doesn't even have to pretend: it will use the expected
> `node_id` and use the
> existing error paths).
>
> Actually, that was too hasty.
>
>
> Ok I think your second email came to the same conclusions and clarifies it
> a bit :).
>
> It's true that this is code where the developer may easily get confused
> between keys (but it's a
> lot simpler than the Sphinx or Noise implementation).
>
> However in my opinion it's still simpler than the `scid` state management
> that needs to happen at
> Alice and Bob in
> https://github.com/lightningnetwork/lightning-rfc/pull/681 (but I would
> need to
> implement both E2E to be able to fairly judge that).
>
> Thanks for the feedback, I'll keep working on improving the proposal.
> Bastien
>
> Le mar. 4 févr. 2020 à 05:29, Rusty Russell  a
> écrit :
> >
> > Rusty Russell  writes:
> > > Bastien TEINTURIER  writes:
> > >> That's of course a solution as well. Even with that though, if Alice
> opens
> > >> multiple channels to each of her Bobs,
> > >> she should use Tor and a different node_id each time for better
> privacy.
> > >
> > > There are two uses for this feature (both of which I started
> implementing):
> > >
> > > 1. Simply always use a temporary id when you have a private channel, to
> > >obscure your onchain footprint.  This is a nobrainer.
> > >
> > > 2. For an extra layer of transience, apply a new temporary id and new
> > >nodeid on every invoice *which applies only for that invoice*.
> > >
> > > But implementing the latter securely is fraught!
> > >
> > > Firstly, need to brute-force the onion against your N keys.  Secondly,
> > > if you use a temporary key, then you *don't* end up using the HTLC to
> > > pay an invoice matching that key, you *MUST* pretend you couldn't
> > > decrypt the onion!  This applies to all code paths between the two,
> > > including parsing the TLV, etc: they must ALL return
> > > WIRE_INVALID_ONION_HMAC.
> > >
> > > Otherwise, Mallory can get an invoice, then send malformed payments to
> > > Alice using the transient key in the invoice and see if she decrypts
> it.
> >
> > Actually, that was too hasty.  You can use the payment_hash as a
> > fastpath:
> >
> > 1. Look up invoice using payment_hash.
> >
> > 2. If there is an invoice, and it has a temporary id associated with it,
> >try using that to decrypt the onion.  If that works, and the onion is
> >on the final hop, and the TLV decodes, and the payment_secret is
> >correct, you can go back and use this temporary key to decrypt the
> onion.
> >Otherwise, go back and use 

Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-04 Thread Bastien TEINTURIER
I'm a bit confused, I don't know if the implementation work you're
mentioning refers to my proposal
or yours :).

When you say `temporary id`, could you clarify whether you mean a temporary
`node_id` or `scid`?

Firstly, need to brute-force the onion against your N keys.


This is probably the part that confuses me. Are you talking about Bob or
Alice there?
Alice can easily have her `decoy_node_id` be derived from her real
`node_id`'s privacy key and the
`payment_hash` or `payment_preimage`. When she receives a payment, she
knows which `decoy_node_id`
should have been used so she doesn't need to brute-force.

That means Alice doesn't even have to change how she stores invoices. When
Alice retrieves the
invoice from her DB, if it has the `decoy_node_id` feature bit set, she
knows she needs to derive
the correct `node_id`. If it doesn't have that feature bit set, it's a
"legacy" invoice and she has
to use her real `node_id`.

Now Mallory uses Bob->C2 to pay to N1 for Inv1. If it works, he knows it's
> the same node issuing both invoices.


Same, that wouldn't work because Alice can easily detect the mismatch and
pretend she can't decrypt
the onion (the code doesn't even have to pretend: it will use the expected
`node_id` and use the
existing error paths).

Actually, that was too hasty.


Ok I think your second email came to the same conclusions and clarifies it
a bit :).

It's true that this is code where the developer may easily get confused
between keys (but it's a
lot simpler than the Sphinx or Noise implementation).

However in my opinion it's still simpler than the `scid` state management
that needs to happen at
Alice and Bob in https://github.com/lightningnetwork/lightning-rfc/pull/681
(but I would need to
implement both E2E to be able to fairly judge that).

Thanks for the feedback, I'll keep working on improving the proposal.
Bastien

Le mar. 4 févr. 2020 à 05:29, Rusty Russell  a écrit
:
>
> Rusty Russell  writes:
> > Bastien TEINTURIER  writes:
> >> That's of course a solution as well. Even with that though, if Alice
opens
> >> multiple channels to each of her Bobs,
> >> she should use Tor and a different node_id each time for better
privacy.
> >
> > There are two uses for this feature (both of which I started
implementing):
> >
> > 1. Simply always use a temporary id when you have a private channel, to
> >obscure your onchain footprint.  This is a nobrainer.
> >
> > 2. For an extra layer of transience, apply a new temporary id and new
> >nodeid on every invoice *which applies only for that invoice*.
> >
> > But implementing the latter securely is fraught!
> >
> > Firstly, need to brute-force the onion against your N keys.  Secondly,
> > if you use a temporary key, then you *don't* end up using the HTLC to
> > pay an invoice matching that key, you *MUST* pretend you couldn't
> > decrypt the onion!  This applies to all code paths between the two,
> > including parsing the TLV, etc: they must ALL return
> > WIRE_INVALID_ONION_HMAC.
> >
> > Otherwise, Mallory can get an invoice, then send malformed payments to
> > Alice using the transient key in the invoice and see if she decrypts it.
>
> Actually, that was too hasty.  You can use the payment_hash as a
> fastpath:
>
> 1. Look up invoice using payment_hash.
>
> 2. If there is an invoice, and it has a temporary id associated with it,
>try using that to decrypt the onion.  If that works, and the onion is
>on the final hop, and the TLV decodes, and the payment_secret is
>correct, you can go back and use this temporary key to decrypt the
onion.
>Otherwise, go back and use the normal node key.
>
> That's still quite a bit of tricky code though...
>
> Cheers,
> Rusty.
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-03 Thread Rusty Russell
Rusty Russell  writes:
> Bastien TEINTURIER  writes:
>> That's of course a solution as well. Even with that though, if Alice opens
>> multiple channels to each of her Bobs,
>> she should use Tor and a different node_id each time for better privacy.
>
> There are two uses for this feature (both of which I started implementing):
>
> 1. Simply always use a temporary id when you have a private channel, to
>obscure your onchain footprint.  This is a nobrainer.
>
> 2. For an extra layer of transience, apply a new temporary id and new
>nodeid on every invoice *which applies only for that invoice*.
>
> But implementing the latter securely is fraught!
>
> Firstly, need to brute-force the onion against your N keys.  Secondly,
> if you use a temporary key, then you *don't* end up using the HTLC to
> pay an invoice matching that key, you *MUST* pretend you couldn't
> decrypt the onion!  This applies to all code paths between the two,
> including parsing the TLV, etc: they must ALL return
> WIRE_INVALID_ONION_HMAC.
>
> Otherwise, Mallory can get an invoice, then send malformed payments to
> Alice using the transient key in the invoice and see if she decrypts it.

Actually, that was too hasty.  You can use the payment_hash as a
fastpath:

1. Look up invoice using payment_hash.

2. If there is an invoice, and it has a temporary id associated with it,
   try using that to decrypt the onion.  If that works, and the onion is
   on the final hop, and the TLV decodes, and the payment_secret is
   correct, you can go back and use this temporary key to decrypt the onion.
   Otherwise, go back and use the normal node key.

That's still quite a bit of tricky code though...

Cheers,
Rusty.
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-03 Thread Rusty Russell
Bastien TEINTURIER  writes:
> That's of course a solution as well. Even with that though, if Alice opens
> multiple channels to each of her Bobs,
> she should use Tor and a different node_id each time for better privacy.

There are two uses for this feature (both of which I started implementing):

1. Simply always use a temporary id when you have a private channel, to
   obscure your onchain footprint.  This is a nobrainer.

2. For an extra layer of transience, apply a new temporary id and new
   nodeid on every invoice *which applies only for that invoice*.

But implementing the latter securely is fraught!

Firstly, need to brute-force the onion against your N keys.  Secondly,
if you use a temporary key, then you *don't* end up using the HTLC to
pay an invoice matching that key, you *MUST* pretend you couldn't
decrypt the onion!  This applies to all code paths between the two,
including parsing the TLV, etc: they must ALL return
WIRE_INVALID_ONION_HMAC.

Otherwise, Mallory can get an invoice, then send malformed payments to
Alice using the transient key in the invoice and see if she decrypts it.

And then I realized that Alice can't do this properly without Bob
telling her what the scid he used to route was.

Otherwise Mallory gets two invoices, and wants to know if they're
actually the same node.  Inv1 has nodeid N1, routehint Bob->C1, Inv2 has
nodeid N2, routehint Bob->C2.

Now Mallory uses Bob->C2 to pay to N1 for Inv1.  If it works, he knows
it's the same node issuing both invoices.

So, update_add_htlc needs a new scid field.

At this point, I think we should just add a new channel_flag, which if
you set it (and feature flag is offered) you get assigned random SCID
from the peer in funding_locked.  This overrides your
funding-transaction-based SCID.

That gets the first case for new channels, without adding much
complexity at all.[1]

Thoughts?
Rusty.

[1] If we want to cover existing channels, we need a new "give me a
replacement scid" msg and reply.  But it can be idempotent (you
only ever get one replacement).
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-03 Thread Bastien TEINTURIER
Hi ZmnSCPxj,

That is precisely what I am referring to, the lowest bits of the node ID
> are embedded in the SCID, which we do not want to openly reveal to Carol.
>

Got it, I wasn't understanding your point correctly. We totally agree on
that.

Though if the point is to prevent Carol from correlating different invoices
> as arising from the same payee, then my scheme fails against that.
>

IMO we should prevent Carol from correlating different invoices by using a
different node_id for each invoice.
This requires minimal changes and happens entirely payee-side (see my
initial mail).

Alice would do better to use multiple Bobs in that case.
>

That's of course a solution as well. Even with that though, if Alice opens
multiple channels to each of her Bobs,
she should use Tor and a different node_id each time for better privacy.

Cheers,
Bastien

Le lun. 3 févr. 2020 à 15:51, ZmnSCPxj  a écrit :

> Good morning t-bast,
>
>
> > > This is relevant if we ever want to hide the node id of the last node:
> Bob could provide a symmetric
> > > encryption key to all its peers with unpublished channels, which the
> peer can XOR with its own true
> > > node id and use the lowest 40 bits (or 46 bits or 58 bits) in the SCID.
> >
> > I don't understand your point here. Alice cannot hide her node_id from
> Bob since the `node_id` is
> > tied to the (unannounced) channel creation.
> >
> > But this is not an issue. What Alice wants to break is the ability to
> link multiple HTLCs together
> > because they use the same `node_id`. Since Alice can use a different
> `node_id` in every invoice,
> > it's easy for her to make sure Carol cannot tie those HTLCs together.
>
> That is precisely what I am referring to, the lowest bits of the node ID
> are embedded in the SCID, which we do not want to openly reveal to Carol.
> Though if the point is to prevent Carol from correlating different
> invoices as arising from the same payee, then my scheme fails against that.
>
> >
> > In order to hide from Bob, the best Alice can do is use a different
> `node_id` for each channel she
> > opens to Bob and use Tor. This way Bob cannot know that node_id_1 and
> node_id_2 both belong to Alice.
> > I don't think we can do better than that.
>
> Alice would do better to use multiple Bobs in that case.
>
>
> Regards,
> ZmnSCPxj
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-03 Thread ZmnSCPxj via Lightning-dev
Good morning t-bast,


> > This is relevant if we ever want to hide the node id of the last node: Bob 
> > could provide a symmetric
> > encryption key to all its peers with unpublished channels, which the peer 
> > can XOR with its own true
> > node id and use the lowest 40 bits (or 46 bits or 58 bits) in the SCID.
>
> I don't understand your point here. Alice cannot hide her node_id from Bob 
> since the `node_id` is
> tied to the (unannounced) channel creation.
>
> But this is not an issue. What Alice wants to break is the ability to link 
> multiple HTLCs together
> because they use the same `node_id`. Since Alice can use a different 
> `node_id` in every invoice,
> it's easy for her to make sure Carol cannot tie those HTLCs together.

That is precisely what I am referring to, the lowest bits of the node ID are 
embedded in the SCID, which we do not want to openly reveal to Carol.
Though if the point is to prevent Carol from correlating different invoices as 
arising from the same payee, then my scheme fails against that.

>
> In order to hide from Bob, the best Alice can do is use a different `node_id` 
> for each channel she
> opens to Bob and use Tor. This way Bob cannot know that node_id_1 and 
> node_id_2 both belong to Alice.
> I don't think we can do better than that.

Alice would do better to use multiple Bobs in that case.


Regards,
ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-03 Thread Bastien TEINTURIER
Thanks for the feedback and discussion. Here are some more comments.

This is relevant if we ever want to hide the node id of the last node: Bob
> could provide a symmetric
> encryption key to all its peers with unpublished channels, which the peer
> can XOR with its own true
> node id and use the lowest 40 bits (or 46 bits or 58 bits) in the SCID.


I don't understand your point here. Alice cannot hide her node_id from Bob
since the `node_id` is
tied to the (unannounced) channel creation.

But this is not an issue. What Alice wants to break is the ability to link
multiple HTLCs together
because they use the same `node_id`. Since Alice can use a different
`node_id` in every invoice,
it's easy for her to make sure Carol cannot tie those HTLCs together.

In order to hide from Bob, the best Alice can do is use a different
`node_id` for each channel she
opens to Bob and use Tor. This way Bob cannot know that node_id_1 and
node_id_2 both belong to Alice.
I don't think we can do better than that.

I really don't want a special marker on Carol; she needs to just pay like
> normal.


I agree that this would be the ideal outcome (and my current proposal
doesn't achieve that, but I'm
hoping I can improve it to achieve that). Do note that even though my
current proposal requires
a code update from Carol, the code-change would be very small. Adding
support for `payment_secret`
did require a change on Carol to improve security; I'm hoping that a small
enough code-change with
a big enough privacy improvement would eventually be supported by all three
implementations (and
then find its way inside wallets).

I must admit I'm a bit turned off by the state management required by your
proposal. I'm afraid it
may be complex to get right, or be subject to fingerprinting and wouldn't
result in the privacy
gain we're hoping.

I think this really needs to be cheap for Bob; if Bob can be DoS-ed by
offering this feature, I
don't think the Bobs out there will activate it.

I really feel some cryptography trick can allow us to find a solution that
requires no more than a
shared secret to be kept between Alice and Bob, and no
synchronization/state management.
I'd like to explore this option further.

Cheers,
Bastien

Le lun. 3 févr. 2020 à 07:51, m.a.holden via Lightning-dev <
lightning-dev@lists.linuxfoundation.org> a écrit :

> > (I'm seeking a clever way that Bob can assign them and trivially tell
> > which ID is assigned to which peer, but I can't figure it out, so I
> > guess Bob keeps a mapping and restricts each peer to 256 live scids?).
>
> Hi Rusty.
>
> Here's a potential way for Alice and Bob to agree a set of 256 scids
> without any additional messages or changes to existing messages beyond a
> feature flag and a flag in open_channel, but comes with a computational
> cost.
>
> Alice and Bob agree on a random integer `r`. This could be negotiated on
> `open_channel`, but we shouldn't need to send additional information
> because we already have a random integer we can use: the
> `temporary_channel_id`. This is not known to anybody besides Alice and Bob.
>
> When a channel is locked, Bob computes n=256 scids, using something
> approximating `concat(n, trunc_bytes(sha256(ec_mult(2^n*r, Q)), 7))`, where
> `Q` is Alice's public key for the channel funding transaction.
>
> The chance of scid collisions between channels is 2^56, which is probably
> no cause for concern.
>
> Instead of keeping a map of 256 scids for each channel, Bob can use a
> cuckoo filter for efficiency. The filter can be used for a quick membership
> test and also as an associative map from scids to channels. It can also
> support scid deletion in the event of channel closure (at the cost of
> recomputing 256 ec_mults again).
>
> So when Bob receives a new HTLC to forward, he tests it against his cuckoo
> filter and retreives a candidate set of possible channels to which it may
> refer. For each channel, he takes the most significant byte of the scid as
> `m` and performs `trunc_bytes(sha256(ec_mult(2^m*r, Q)), 7)` and tests the
> least-significant 7 bytes of the result against the scid.
>
> Alice does not need to keep all of the scids she may use for invoices
> because they can be computed on the fly, but she will need to keep a copy
> of the `temporary_channel_id`.
>
> In the reverse direction of Alice forwarding HTLCs to Bob, Bob's public
> key for the funding transaction is used instead.
>
> Regards,
> Mark Holden
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-02 Thread m.a.holden via Lightning-dev
> (I'm seeking a clever way that Bob can assign them and trivially tell
> which ID is assigned to which peer, but I can't figure it out, so I
> guess Bob keeps a mapping and restricts each peer to 256 live scids?).

Hi Rusty.

Here's a potential way for Alice and Bob to agree a set of 256 scids without 
any additional messages or changes to existing messages beyond a feature flag 
and a flag in open_channel, but comes with a computational cost.

Alice and Bob agree on a random integer `r`. This could be negotiated on 
`open_channel`, but we shouldn't need to send additional information because we 
already have a random integer we can use: the `temporary_channel_id`. This is 
not known to anybody besides Alice and Bob.

When a channel is locked, Bob computes n=256 scids, using something 
approximating `concat(n, trunc_bytes(sha256(ec_mult(2^n*r, Q)), 7))`, where `Q` 
is Alice's public key for the channel funding transaction.

The chance of scid collisions between channels is 2^56, which is probably no 
cause for concern.

Instead of keeping a map of 256 scids for each channel, Bob can use a cuckoo 
filter for efficiency. The filter can be used for a quick membership test and 
also as an associative map from scids to channels. It can also support scid 
deletion in the event of channel closure (at the cost of recomputing 256 
ec_mults again).

So when Bob receives a new HTLC to forward, he tests it against his cuckoo 
filter and retreives a candidate set of possible channels to which it may 
refer. For each channel, he takes the most significant byte of the scid as `m` 
and performs `trunc_bytes(sha256(ec_mult(2^m*r, Q)), 7)` and tests the 
least-significant 7 bytes of the result against the scid.

Alice does not need to keep all of the scids she may use for invoices because 
they can be computed on the fly, but she will need to keep a copy of the 
`temporary_channel_id`.

In the reverse direction of Alice forwarding HTLCs to Bob, Bob's public key for 
the funding transaction is used instead.

Regards,
Mark Holden
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Decoy node_ids and short_channel_ids

2020-02-02 Thread Rusty Russell
Bastien TEINTURIER  writes:
> We can easily get rid of (1.) by leveraging the `payment_secret`. The
> improved scheme is:
>
> * Alice draws a random `decoy_key`
> * Alice computes the corresponding `decoy_node_id = decoy_key * G`
> * Alice draws a random `payment_secret`
> * Alice computes `decoy_short_channel_id = H(payment_secret * decoy_key *
> bob_node_id) xor short_channel_id`
> * Alice uses the `decoy_key` to sign the invoice
> * Carol recovers `decoy_node_id` from the invoice signature
> * Carol includes `P_I = payment_secret * decoy_node_id` in the onion
> payload for Bob
> * Bob can compute `short_channel_id = H(bob_private_key * P_I) xor
> decoy_short_channel_id`
>
> But I don't see how to get rid of (2.). If anyone has a clever idea on how
> to do that, I'd love to hear it!

I really don't want a special marker on Carol; she needs to just pay
like normal.  Not just because it's simple, but because it means that
Carol can use a custodial wallet without having to flag the payment as
somehow special.

AFAICT, having Bob assign scids is the only viable way to do this.  The
current proposal limits to one scid at a time, but it could be extended
to allow multiple scids.

(I'm seeking a clever way that Bob can assign them and trivially tell
which ID is assigned to which peer, but I can't figure it out, so I
guess Bob keeps a mapping and restricts each peer to 256 live scids?).

I've updated and somewhat simplified the PR now.

Cheers,
Rusty.
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev