Re: [Lightning-dev] Mitigations for loop attacks

[Chris Gough]

On Fri, May 11, 2018 at 9:18 AM, Jim Posen  wrote:
> Hmm, I'm not quite following the situation. What do you mean by "directs
> normal traffic"? Since the sender constructs the entire circuit, routing
> nodes do not get any discretion over which nodes to forward a payment to,



> only whether to forward or fail. What an attacker could do is perform a loop
> attack and send a payment to another node that they control and delay the
> payment on the receiving end. Note that the sending node loses no
> reputation, only the receiving node. Since the hops being attacked are the
> ones in the middle and they are faithfully enforcing the reputation
> protocol, the receiving node's reputation should be penalized properly,
> making it unlikely the attack will succeed in a second attempt.

So the attacker can purchase reputation for the sacrificial node by
sending them legitimate payments, and then spend that reputation (at
the mutual expense of hops) by delaying targeted transactions. But my
question about obscuring the collusion by artificially lowering
reported risk was nonsense based on misunderstanding. Thanks for
helping me understand.

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

Re: [Lightning-dev] Mitigations for loop attacks

[Jim Posen]

Hmm, I'm not quite following the situation. What do you mean by "directs
normal traffic"? Since the sender constructs the entire circuit, routing
nodes do not get any discretion over which nodes to forward a payment to,
only whether to forward or fail. What an attacker could do is perform a
loop attack and send a payment to another node that they control and delay
the payment on the receiving end. Note that the sending node loses no
reputation, only the receiving node. Since the hops being attacked are the
ones in the middle and they are faithfully enforcing the reputation
protocol, the receiving node's reputation should be penalized properly,
making it unlikely the attack will succeed in a second attempt.

On Thu, May 10, 2018 at 2:56 PM, Chris Gough 
wrote:

> hello, I'm a curious lurker trying to follow this conversation:
>
> On Thu, 10 May 2018, 2:40 pm ZmnSCPxj via Lightning-dev, <
> lightning-dev@lists.linuxfoundation.org> wrote:
>
>>
>> The concern however is that the CLTV already partly leaks the distance
>> from the payee, whereas the reputation-loss-rate leaks distance from the
>> payer.  It is often not interesting to know that some entity is getting
>> paid, but it probably far more interesting to know WHO paid WHO, so leaking
>> both distances simultaneously is more than twice as worse as leaking just
>> one distance.
>>
>
> Consider an asymetrically-resourced malevolent node that wants the ability
> to harm a specific small nodes without aquiring a bad reputation (and is
> willing to pay for it). In preparation, this bad boss node directs normal
> traffic to sacrificial nodes they control, while understating the
> reputation-risk (truthfully as it turns out, because they have out of band
> influence over the node). When the time comes, the sacrificial node
> inflicts delay on the victim node and they both suffer, while the boss
> keeps her nose clean.
>
> Is it the case that understating risk of legitimate traffic from boss node
> to sacrificial node effectively allows transfer of reputation to the
> sacrificial node in preparation for attack, while at the same time
> obscuring their association?
>
> Chris Gough
>
>>
> ___
> 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] Mitigations for loop attacks

[Chris Gough]

hello, I'm a curious lurker trying to follow this conversation:

On Thu, 10 May 2018, 2:40 pm ZmnSCPxj via Lightning-dev, <
lightning-dev@lists.linuxfoundation.org> wrote:

>
> The concern however is that the CLTV already partly leaks the distance
> from the payee, whereas the reputation-loss-rate leaks distance from the
> payer.  It is often not interesting to know that some entity is getting
> paid, but it probably far more interesting to know WHO paid WHO, so leaking
> both distances simultaneously is more than twice as worse as leaking just
> one distance.
>

Consider an asymetrically-resourced malevolent node that wants the ability
to harm a specific small nodes without aquiring a bad reputation (and is
willing to pay for it). In preparation, this bad boss node directs normal
traffic to sacrificial nodes they control, while understating the
reputation-risk (truthfully as it turns out, because they have out of band
influence over the node). When the time comes, the sacrificial node
inflicts delay on the victim node and they both suffer, while the boss
keeps her nose clean.

Is it the case that understating risk of legitimate traffic from boss node
to sacrificial node effectively allows transfer of reputation to the
sacrificial node in preparation for attack, while at the same time
obscuring their association?

Chris Gough

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

Re: [Lightning-dev] Mitigations for loop attacks

[ZmnSCPxj via Lightning-dev]

Good morning Jim,

> One more point in terms of information leakage is that noise can be added to 
> the "this is the rate that you'll lose reputation at" field to help obfuscate 
> the number of upstream hops. I proposed setting it to "this is the upstream 
> rate that I'm losing reputation at" + downstream HTLC value, but a node can 
> decide to add noise. If they make it too low however, there's a risk of 
> insufficiently punishing bad nodes and if they make it too high, there's a 
> heightened risk that the payment fails because the downstream reputation is 
> insufficient along the route.

I was about to propose this.

Indeed, I intend to implement CLTV-delay randomization for payments in 
C-lightning, i.e. "shadow routes", since that is a way to obfuscate the 
intermediate node distance from the payee.  Randomizing the 
reputation-loss-rate is similar.

The concern however is that the CLTV already partly leaks the distance from the 
payee, whereas the reputation-loss-rate leaks distance from the payer.  It is 
often not interesting to know that some entity is getting paid, but it probably 
far more interesting to know WHO paid WHO, so leaking both distances 
simultaneously is more than twice as worse as leaking just one distance.

Regards,
ZmnSCPxj

> This is why I say it's kind of symmetric to the CLTV value: if the delta is 
> too low, there's risk of loss of funds, if the delta is too high, someone 
> might decide to fail the payment instead of taking the delay risk.
>
> On Wed, May 9, 2018 at 10:23 AM, Jim Posen  wrote:
>
>> Thanks for the thoughtful responses.
>>> You missed the vital detail: that you must prove channel closure if you
>>> can't unpeel the onion further.  That *will* hit an unresponsive party
>>> with a penalty.
>>
>> Ah, that is a good point. I still find the proposal overall worryingly 
>> complex in terms of communication overhead, time it takes to prove channel 
>> closure, all of your points in [1], [2], [3], etc. Furthermore, this 
>> mandates that immediate channel closure is the only allowed reaction to a 
>> party delaying an HTLC for a time period above a threshold -- the node 
>> reputation approach gives more discretion to the preceding hop. 
>> Deobfuscating the route may turn out to be the right option, but I think the 
>> reputation system has certain advantages over this.
>>> The models we tried in Milan all created an incentive to fail payments,
>>> which is a non-starter.
>>
>> Do you mind elaborating or summarizing the reasons? The way I'm analyzing 
>> it, even if there's a nominal spam fee paid to routing nodes that fail 
>> payments, as long as it's low enough (say 2-5% for arguments sake), the 
>> nodes still have more to gain by forwarding the payment and earning the full 
>> fee on a completed payment, and possibly the reputation boost associated 
>> with completing a payment if that system was in effect. Moreover, a node 
>> that constantly fails payments will be blacklisted by the sender eventually 
>> and stop receiving HTLCs from them at all. Overall, I don't think this is a 
>> profitable strategy. Furthermore, I think it works quite well in combination 
>> with the reputation system.
>>> This seems like we'd need some serious evaluation to show that this
>>> works, because the risks are very high.
>>
>> I agree that it needs to be evaluated. I may start working on some network 
>> simulations to test various DOS mitigation strategies.
>>
>>> I can destroy your node's reputation by routing crap through you; even
>>> if it costs me marginaly more reputation than it does you, that just
>>> means that the largest players can force failure upon smaller players,
>>> centralizing the network.  And I think trying to ensure that it costs me
>>> more reputation than the sum of downstream reputation loss leaks too
>>> much information
>>
>> I will add to ZmnSCPxj's response, which is mostly on point. The key here is 
>> that the only way to lose significant reputation is to delay a payment 
>> yourself or forward to a malicious downstream that delays -- neither of 
>> these can be forced by the sender alone. This amounts to a system where you 
>> are on the hook for any malicious behavior of your downstream peers, which 
>> is why you must keep a reputation score for each which they earn over time. 
>> This should keep all links in the network high quality and quickly 
>> disconnect off delaying nodes if the incentives are right.
>>
>> While I agree that a lot of reputation is leaked by aggregating the losses 
>> along the route, this serves exactly to prevent large nodes with high 
>> reputation from ruining links elsewhere. There are two things a node looking 
>> to cause reputation loss could do. 1) Identify a node (not itself) it thinks 
>> will delay a payment and send to them. This locks up funds on their behalf, 
>> but is actually good behavior because it identifies a faulty node and 
>> rightfully forces a loss in their 

Re: [Lightning-dev] Mitigations for loop attacks

[Jim Posen]

One more point in terms of information leakage is that noise can be added
to the "this is the rate that you'll lose reputation at" field to help
obfuscate the number of upstream hops. I proposed setting it to "this is
the upstream rate that I'm losing reputation at" + downstream HTLC value,
but a node can decide to add noise. If they make it too low however,
there's a risk of insufficiently punishing bad nodes and if they make it
too high, there's a heightened risk that the payment fails because the
downstream reputation is insufficient along the route.

This is why I say it's kind of symmetric to the CLTV value: if the delta is
too low, there's risk of loss of funds, if the delta is too high, someone
might decide to fail the payment instead of taking the delay risk.

On Wed, May 9, 2018 at 10:23 AM, Jim Posen  wrote:

> Thanks for the thoughtful responses.
>
> > You missed the vital detail: that you must prove channel closure if you
> > can't unpeel the onion further.  That *will* hit an unresponsive party
> > with a penalty.
>
> Ah, that is a good point. I still find the proposal overall worryingly
> complex in terms of communication overhead, time it takes to prove channel
> closure, all of your points in [1], [2], [3], etc. Furthermore, this
> mandates that immediate channel closure is the only allowed reaction to a
> party delaying an HTLC for a time period above a threshold -- the node
> reputation approach gives more discretion to the preceding hop.
> Deobfuscating the route may turn out to be the right option, but I think
> the reputation system has certain advantages over this.
>
> > The models we tried in Milan all created an incentive to fail payments,
> > which is a non-starter.
>
> Do you mind elaborating or summarizing the reasons? The way I'm analyzing
> it, even if there's a nominal spam fee paid to routing nodes that fail
> payments, as long as it's low enough (say 2-5% for arguments sake), the
> nodes still have more to gain by forwarding the payment and earning the
> full fee on a completed payment, and possibly the reputation boost
> associated with completing a payment if that system was in effect.
> Moreover, a node that constantly fails payments will be blacklisted by the
> sender eventually and stop receiving HTLCs from them at all. Overall, I
> don't think this is a profitable strategy. Furthermore, I think it works
> quite well in combination with the reputation system.
>
> > This seems like we'd need some serious evaluation to show that this
> > works, because the risks are very high.
>
> I agree that it needs to be evaluated. I may start working on some network
> simulations to test various DOS mitigation strategies.
>
> > I can destroy your node's reputation by routing crap through you; even
> > if it costs me marginaly more reputation than it does you, that just
> > means that the largest players can force failure upon smaller players,
> > centralizing the network.  And I think trying to ensure that it costs me
> > more reputation than the sum of downstream reputation loss leaks too
> > much information
>
> I will add to ZmnSCPxj's response, which is mostly on point. The key here
> is that the only way to lose significant reputation is to delay a payment
> yourself or forward to a malicious downstream that delays -- neither of
> these can be forced by the sender alone. This amounts to a system where you
> are on the hook for any malicious behavior of your downstream peers, which
> is why you must keep a reputation score for each which they earn over time.
> This should keep all links in the network high quality and quickly
> disconnect off delaying nodes if the incentives are right.
>
> While I agree that a lot of reputation is leaked by aggregating the losses
> along the route, this serves exactly to prevent large nodes with high
> reputation from ruining links elsewhere. There are two things a node
> looking to cause reputation loss could do. 1) Identify a node (not itself)
> it thinks will delay a payment and send to them. This locks up funds on
> their behalf, but is actually good behavior because it identifies a faulty
> node and rightfully forces a loss in their reputation, eventually resulting
> in them being booted from the network. Everyone upstream loses some
> reputation for having connectivity to them, but less because of the loss
> aggregation along the route. 2) Delay a payment oneself and force upstream
> reputation loss. This is why I think it's important that the reputation
> loss aggregate so that the malicious party loses the most.
>
> As for the amount of information leaked, yes, it helps determine the
> number of upstream hops in a route. However, the CLTV values help determine
> the number of downstream hops in a route in exactly the same way. I see
> these as symmetric in a sense.
>
> To address ZmnSCPxj's point:
>
> > But it also looks more and more like a policy of "just
> `update_htlc_fail`" keeps our reputation high: indeed 

Re: [Lightning-dev] Mitigations for loop attacks

[Jim Posen]

Thanks for the thoughtful responses.

> You missed the vital detail: that you must prove channel closure if you
> can't unpeel the onion further.  That *will* hit an unresponsive party
> with a penalty.

Ah, that is a good point. I still find the proposal overall worryingly
complex in terms of communication overhead, time it takes to prove channel
closure, all of your points in [1], [2], [3], etc. Furthermore, this
mandates that immediate channel closure is the only allowed reaction to a
party delaying an HTLC for a time period above a threshold -- the node
reputation approach gives more discretion to the preceding hop.
Deobfuscating the route may turn out to be the right option, but I think
the reputation system has certain advantages over this.

> The models we tried in Milan all created an incentive to fail payments,
> which is a non-starter.

Do you mind elaborating or summarizing the reasons? The way I'm analyzing
it, even if there's a nominal spam fee paid to routing nodes that fail
payments, as long as it's low enough (say 2-5% for arguments sake), the
nodes still have more to gain by forwarding the payment and earning the
full fee on a completed payment, and possibly the reputation boost
associated with completing a payment if that system was in effect.
Moreover, a node that constantly fails payments will be blacklisted by the
sender eventually and stop receiving HTLCs from them at all. Overall, I
don't think this is a profitable strategy. Furthermore, I think it works
quite well in combination with the reputation system.

> This seems like we'd need some serious evaluation to show that this
> works, because the risks are very high.

I agree that it needs to be evaluated. I may start working on some network
simulations to test various DOS mitigation strategies.

> I can destroy your node's reputation by routing crap through you; even
> if it costs me marginaly more reputation than it does you, that just
> means that the largest players can force failure upon smaller players,
> centralizing the network.  And I think trying to ensure that it costs me
> more reputation than the sum of downstream reputation loss leaks too
> much information

I will add to ZmnSCPxj's response, which is mostly on point. The key here
is that the only way to lose significant reputation is to delay a payment
yourself or forward to a malicious downstream that delays -- neither of
these can be forced by the sender alone. This amounts to a system where you
are on the hook for any malicious behavior of your downstream peers, which
is why you must keep a reputation score for each which they earn over time.
This should keep all links in the network high quality and quickly
disconnect off delaying nodes if the incentives are right.

While I agree that a lot of reputation is leaked by aggregating the losses
along the route, this serves exactly to prevent large nodes with high
reputation from ruining links elsewhere. There are two things a node
looking to cause reputation loss could do. 1) Identify a node (not itself)
it thinks will delay a payment and send to them. This locks up funds on
their behalf, but is actually good behavior because it identifies a faulty
node and rightfully forces a loss in their reputation, eventually resulting
in them being booted from the network. Everyone upstream loses some
reputation for having connectivity to them, but less because of the loss
aggregation along the route. 2) Delay a payment oneself and force upstream
reputation loss. This is why I think it's important that the reputation
loss aggregate so that the malicious party loses the most.

As for the amount of information leaked, yes, it helps determine the number
of upstream hops in a route. However, the CLTV values help determine the
number of downstream hops in a route in exactly the same way. I see these
as symmetric in a sense.

To address ZmnSCPxj's point:

> But it also looks more and more like a policy of "just
`update_htlc_fail`" keeps our reputation high: indeed never accepting a
forwarding attempt would ensure reputation.
> However, earning via fees should help provide incentive against "Just
`update_htlc_fail`" always.  If the goal is "how do I earn money fastest"
then there is some optimal threshhold > of risk-of-reputation-loss vs.
fee-earnings-if-I-forward that is unlikely to be near the "Just fail it"
spectrum, but somewhere in between.  We hope.

This is exactly the question that your local view of peer reputations helps
solve: are the potential fees here worth the risk of forwarding this
payment to this downstream? If their reputation is high, then you will want
to forward because you think there's a low chance of you incurring
reputation loss. If their reputation is low and the HTLC value is too high,
you will fail it. So I disagree that "just `update_htlc_fail`" is an
optimal strategy. Consider as well that all fees you earn on successful
payments are profit to you as well as a reputation boost in the view of
both of your 

Re: [Lightning-dev] Mitigations for loop attacks

[Rusty Russell]

Jim Posen  writes:
> There are two directions of solutions I have heard: 1) protocol support for
> decrypting the onion route if the HTLC is kept in-flight for too long 2)
> requiring fees even if the payment fails as a cost to the attacker 3) some
> sort of reputation system for nodes.
>
> Option 1 I'm afraid may be quite complex. Say this mechanism kicks in and
> all nodes in the circuit deobfuscate the route and are able to see the
> delays at each hop. The outcome we hope for is that there is one node
> clearly to blame and the prior hop in the route fails all channels with
> them. However, the attacker can of course control multiple successive hops
> in the route, one that looks innocent in front of one that looks guilty,
> then keep the channel alive and try again. So then all nodes need to keep a
> record of the full circuits and iteratively shift blame up the chain if bad
> HTLCs keep going through those channels.

You missed the vital detail: that you must prove channel closure if you
can't unpeel the onion further.  That *will* hit an unresponsive party
with a penalty.[1]

> Option 2 is also problematic because it only protects against the case
> where the sender is colluding with the receiver, and not where a routing
> node is opportunistically delaying payments. This would, however, likely be
> successful against nodes being annoying and sending tons of payments with
> randomly generated payment hashes in order to "ping" a circuit.

The models we tried in Milan all created an incentive to fail payments,
which is a non-starter.

> Option 3 has become my preferred solution. The idea is that that for each
> node that one has channels with, it only forwards payments through them if
> they have a good history, otherwise it fails the payment. Notably, we
> ignore whether the downstream hop is directly responsible for delaying a
> payment or whether they are simply willing to forward to another node that
> is intentionally delaying -- both should be considered bad behavior. In my
> opinion, this type of solution fits best into the Lightning model of
> independent, linked channels where each node has private contracts with its
> direct peers. It also is the simplest in the context of onion routing
> because if you are offered an HTLC to route, the only decision you can make
> is whether to forward it or fail it based on the amount, previous hop, and
> next hop. When I refer to "reputation" hereafter, I do not mean a global
> reputation that is gossiped about -- just a local view of a peer's history.

This seems like we'd need some serious evaluation to show that this
works, because the risks are very high.

I can destroy your node's reputation by routing crap through you; even
if it costs me marginaly more reputation than it does you, that just
means that the largest players can force failure upon smaller players,
centralizing the network.  And I think trying to ensure that it costs me
more reputation than the sum of downstream reputation loss leaks too
much information

If the system doesn't work perfectly, it creates incentive to
de-anonymize payments so you can determine which are likely to fail, and
also means nodes are safest not forwarding payments, lest they ruin
their reputatation.  But nodes which don't forward have much less
privacy.

But I agree, all solutions I've seen to this problem are bad in
different ways.

Cheers,
Rusty.

[1] Proving that you've committed to a particular HTLC in a channel is
difficult, because of dust HTLCs[2] and partially-committed ones[3].

[2] We could have an OP_RETURN output which was a merkle tree of trimmed
HTLCs to cover the dust case.

[3] You committed to an HTLC but the peer didn't respond; you have no
proof.  So you also need to present a merkle tree of uncommitted
HTLCs (limited, say, to 16) otherwise you can create 1M HTLCs, then
claim they were all in that one channel close.
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev