Re: [Lightning-dev] Reason for having HMACs in Sphinx
Corné Plooy writes: >> The total_decorrelation_secrets serves as the payer-generated shared >> secret between payer and payee. B cannot learn this, and thus cannot >> fake its own secret. Even if it instead offers ((I + K[A]) + k[z] * >> G) for a new secret k[z], it cannot know how to change >> total_decorrelation_secrets from k[a] + k[b] to k[a] + k[z] instead. >> > The way things are now, the ephemeral key generation and the payment > hash/preimage generation are completely unrelated. This is what allows > an attacker to use the same payment hash, and use his own ephemeral key > pair to create a new onion packet around it. That is correct, one is generated by the recipient (secret and preimage) and the other one is generated by the sender (ephemeral key). Mixing the two seems very unwise, since the sender has very little control over what the effective ephemeral key that is going to be used for the last hop. This is the same issue that we have with rendez-vous routing, i.e., that if we require the ephemeral key to be something specific at a given node we'd be breaking the hardness assumption of for the ephemeral key rotation. > Primarily, path decorrelation replaces the payment hash/preimage part. > Maybe I still don't understand something, but if that's the only thing > (without changing the ephemeral key / onion shared secret generation), > attacking the direct neighbor should still work; in your case, B would > still offer ((I + K[A]) + K[B]) to C, with an onion packet B created > himself. I'm not familiar enough with the path correlation to understand > what happens after step 6, but for C it looks the same, so she should do > the same. > > > I do see that, if you couple the "H"TLC payment secret generation to the > onion shared secret generation, you can make the attack impossible. Do I > understand correctly that this is the idea? After all, C still needs to > receive k somehow; my crypto math isn't that good, but my intuitive > guess is that i + k is the secret that allows C to claim funds locked in > ((I + K[A]) + K[B]) =? (i + (k[a] + k[b])) * G. If k is submitted from A > to C through some mechanism that replaces the current ephemeral key > system, then I understand what you're at. I can't quite follow where we would be mixing in the ephemeral key here, could you elaborate on that? > Assuming this is the case, it's pretty neat. I do wonder how it > interacts with rendezvous routing. If the sender and receiver each > create the k[..] values for their own part of the route, can the > receiver-generated onion packet still use points of the form ((I + K[A]) > + K[B]), including K[..] values related to the sender side? I need to > dig deeper into this path decorrelation idea. Since we have very little control over what ephemeral key will actually be presented to the last hop if we have a multi-hop route, we can't really hide any information in the ephemeral key itself. What we could do is change the way the last hop generates the shared secret from it, i.e., have a last hop mode and a forwarding hop mode, and mix in the payment secret somehow, but I can't think of a good way to do that, and it seems contorted. Let's just have the sender prove knowledge of the original invoice by adding a TLV field with a shared secret from the invoice instead. Cheers, Christian ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Reason for having HMACs in Sphinx
> * layer 0 (to B): decorrelation_secret = k[b] > * layer 1 (to B): total_decorrelation_secrets = k = k[a] + k[b] I would have less trouble understanding that if it were layer 1 (to C) instead of (to B). > The total_decorrelation_secrets serves as the payer-generated shared secret > between payer and payee. > B cannot learn this, and thus cannot fake its own secret. > Even if it instead offers ((I + K[A]) + k[z] * G) for a new secret k[z], it > cannot know how to change total_decorrelation_secrets from k[a] + k[b] to > k[a] + k[z] instead. > The way things are now, the ephemeral key generation and the payment hash/preimage generation are completely unrelated. This is what allows an attacker to use the same payment hash, and use his own ephemeral key pair to create a new onion packet around it. Primarily, path decorrelation replaces the payment hash/preimage part. Maybe I still don't understand something, but if that's the only thing (without changing the ephemeral key / onion shared secret generation), attacking the direct neighbor should still work; in your case, B would still offer ((I + K[A]) + K[B]) to C, with an onion packet B created himself. I'm not familiar enough with the path correlation to understand what happens after step 6, but for C it looks the same, so she should do the same. I do see that, if you couple the "H"TLC payment secret generation to the onion shared secret generation, you can make the attack impossible. Do I understand correctly that this is the idea? After all, C still needs to receive k somehow; my crypto math isn't that good, but my intuitive guess is that i + k is the secret that allows C to claim funds locked in ((I + K[A]) + K[B]) =? (i + (k[a] + k[b])) * G. If k is submitted from A to C through some mechanism that replaces the current ephemeral key system, then I understand what you're at. Assuming this is the case, it's pretty neat. I do wonder how it interacts with rendezvous routing. If the sender and receiver each create the k[..] values for their own part of the route, can the receiver-generated onion packet still use points of the form ((I + K[A]) + K[B]), including K[..] values related to the sender side? I need to dig deeper into this path decorrelation idea. CJP ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Reason for having HMACs in Sphinx
Christian Decker writes: > Rusty Russell writes: >>> The shared secret doesn't need to be very large: the number of attempts >>> per second (to guess the shared secret) is limited by network latency, >>> bandwidth and maybe some artificial rate limiting. If an attacker can do >>> 100 attempts per second, then a 32-bit shared secret will take (on >>> average) 2^31 / (100*3600*24) = 248 days to crack, for a single guess of >>> which node is the final node. In the mean time, people will have noticed >>> the ongoing attack and will have taken countermeasures. Besides, the >>> transaction lock time will likely have expired in the mean time as well. >> >> We could really just use the last 4 bytes of the signature, AFAICT. > > A stupid idea came to mind that would allow us to use no more space in > the onion at all: store the secret from the invoice in the HMAC > field. That would complicate the final hop checking on the recipient to > either being all 0x00, or some known secret (could also use a partial > HMAC so we can reduce the number of lookups we need to do). Another > option is that we could XOR it with some other field as well. The > recipient already signaled that it supports this by including a secret > in the invoice in the first place anyway, so no need for a lockstep > upgrade either. Well, I think we're heading to a TLV mechanism for the onion "padding" anyway, so it works well there. The only problem with this scheme is timing: 1. It's only useful once it's compulsory, since an adversary can always just not use it (downgrade attack). 2. Will we be able to upgrade the network to make it compulsory before Schnorr and decorrelation make it irrelevant? I think it's a *maybe*, so I suspect we should Just Do It, since it's simple. Cheers, Rusty. ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Reason for having HMACs in Sphinx
Rusty Russell writes: >> The shared secret doesn't need to be very large: the number of attempts >> per second (to guess the shared secret) is limited by network latency, >> bandwidth and maybe some artificial rate limiting. If an attacker can do >> 100 attempts per second, then a 32-bit shared secret will take (on >> average) 2^31 / (100*3600*24) = 248 days to crack, for a single guess of >> which node is the final node. In the mean time, people will have noticed >> the ongoing attack and will have taken countermeasures. Besides, the >> transaction lock time will likely have expired in the mean time as well. > > We could really just use the last 4 bytes of the signature, AFAICT. A stupid idea came to mind that would allow us to use no more space in the onion at all: store the secret from the invoice in the HMAC field. That would complicate the final hop checking on the recipient to either being all 0x00, or some known secret (could also use a partial HMAC so we can reduce the number of lookups we need to do). Another option is that we could XOR it with some other field as well. The recipient already signaled that it supports this by including a secret in the invoice in the first place anyway, so no need for a lockstep upgrade either. Just putting it out there, I'm still unsure if I like it at all, since it mixes field purposes, but it is an option if we decide this is a serious issue. Cheers, Christian ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Reason for having HMACs in Sphinx
Corné Plooy via Lightning-dev writes: > For instance, the attacking intermediate node might guess that the next > node in the route is the final node; it can test this by completely > replacing the onion packet it sends to the next node with a self-written > onion packet that has the next hop as final node, with the same amount > and payment hash as instructed by the incoming payment. If that > succeeds, it has learned that the next node is indeed the final node > (and nobody gets to know about the attack) This is always true, regardless of construction, with our current scheme. > ; if that fails, it might > retry the payment with the original onion packet. In that case, it > learned that the next node is *not* the final node. In this case, the > attack is detectable by the next node though: it first receives an > incoming payment with a payment hash it doesn't recognize, and then it > receives a payment forwarding request with the same payment hash. True. Note that we go as far as preventing forwarding of the same onion (for traffic analysis), but we don't block this more obvious attack. > I think we could stop this type of attack by including some kind of > shared secret in the onion message to the final node: > > * Payee generates shared secret and passes this to payer, as part of the > invoice > > * Payer includes shared secret in the per hop data to payee > > * On receiving the incoming message, payee checks whether the received > shared secret corresponds to the generated one. If this is not the case, > behave in exactly the same way as when the payment hash is unrecognized > (including timing, to prevent timing side-channel attacks). This would indeed be an incremental improvement: I generally prefer not to rely on the privacy of the invoice delivery, but this certainly makes it no worse. > The shared secret doesn't need to be very large: the number of attempts > per second (to guess the shared secret) is limited by network latency, > bandwidth and maybe some artificial rate limiting. If an attacker can do > 100 attempts per second, then a 32-bit shared secret will take (on > average) 2^31 / (100*3600*24) = 248 days to crack, for a single guess of > which node is the final node. In the mean time, people will have noticed > the ongoing attack and will have taken countermeasures. Besides, the > transaction lock time will likely have expired in the mean time as well. We could really just use the last 4 bytes of the signature, AFAICT. Cheers, Rusty. ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Reason for having HMACs in Sphinx
Good morning CJP, > > > I think we could stop this type of attack by including some kind of > > > shared secret in the onion message to the final node: > > > I think we get this "for free" if we switch to path decorrelation and > > > points+privkeys instead of hashes+preimages. > > > > Path decorrelation means that each hop is given a random point, to be added > > to the next SS "HTLC". > > The final node needs to be given the total of the scalars of each hop > > random point along the route, most likely within the last hop of the onion. > > The final node also cannot differentiate between an incorrect total for > > this scalar, or an incorrect "invoice hash"/invoice point. > > Hence, some intermediate node along the way cannot guess this, and the > > final node will give the same error, i.e. "invoice point not found". > > That might indeed stop an attacker from testing 2nd-degree, 3rd-degree > etc. neighbors, making the attack much less versatile. However, for his > direct neighbor in the route, the attacker does learn the point to be > used in that hop. Therefore I think the attacker can still test whether > or not the next node is the final hop. I believe not? For example if the route is A -> B -> C: 1. C creates an invoice secret i, and the invoice point I = i * G, and gives I to node A. 2. A creates two secrets k[a] and k[b], and total sum k = k[a] + k[b]. 3. A creates points K[A] = k[a] * G and K[B] = k[b] * G. 4. A creates an onion as below: * layer 0 (to B): decorrelation_secret = k[b] * layer 1 (to B): total_decorrelation_secrets = k = k[a] + k[b] 5. A offers the HTLC to B, for the secret to the point (I + K[A]). 6. B offers the HTLC to C, for the secret to the point ((I + K[A]) + K[B]). The total_decorrelation_secrets serves as the payer-generated shared secret between payer and payee. B cannot learn this, and thus cannot fake its own secret. Even if it instead offers ((I + K[A]) + k[z] * G) for a new secret k[z], it cannot know how to change total_decorrelation_secrets from k[a] + k[b] to k[a] + k[z] instead. Regards, ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Reason for having HMACs in Sphinx
>> I think we could stop this type of attack by including some kind of >> shared secret in the onion message to the final node: > I think we get this "for free" if we switch to path decorrelation and > points+privkeys instead of hashes+preimages. > > Path decorrelation means that each hop is given a random point, to be added > to the next SS "HTLC". > The final node needs to be given the total of the scalars of each hop random > point along the route, most likely within the last hop of the onion. > The final node also cannot differentiate between an incorrect total for this > scalar, or an incorrect "invoice hash"/invoice point. > > Hence, some intermediate node along the way cannot guess this, and the final > node will give the same error, i.e. "invoice point not found". > > That might indeed stop an attacker from testing 2nd-degree, 3rd-degree etc. neighbors, making the attack much less versatile. However, for his direct neighbor in the route, the attacker does learn the point to be used in that hop. Therefore I think the attacker can still test whether or not the next node is the final hop. CJP ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Reason for having HMACs in Sphinx
Thanks Christian, that makes sense. Unfortunately it's not very clear from the BOLT, at least not for me. Now that I think of this type of attack: *in general* the HMAC prevents this kind of attack, but isn't the attack still possible in certain specific cases? For instance, the attacking intermediate node might guess that the next node in the route is the final node; it can test this by completely replacing the onion packet it sends to the next node with a self-written onion packet that has the next hop as final node, with the same amount and payment hash as instructed by the incoming payment. If that succeeds, it has learned that the next node is indeed the final node (and nobody gets to know about the attack); if that fails, it might retry the payment with the original onion packet. In that case, it learned that the next node is *not* the final node. In this case, the attack is detectable by the next node though: it first receives an incoming payment with a payment hash it doesn't recognize, and then it receives a payment forwarding request with the same payment hash. Given that the attacker has good knowledge of the shape of the Lightning network, this type of attack can be generalized to test whether a certain second-degree neighbor, third-degree neighbor etc. is the final node; it scales pretty badly with increasing network distance though. An additional advantage for the attacker is that this gives plausible deniability: if the attack becomes visible, the attacker can always claim it wasn't him, but some node upstream in the route. A practical difficulty for the attacker might be that the exact amount forwarded in further-away hops is unknown, but it's probably not that difficult to guess. I think we could stop this type of attack by including some kind of shared secret in the onion message to the final node: * Payee generates shared secret and passes this to payer, as part of the invoice * Payer includes shared secret in the per hop data to payee * On receiving the incoming message, payee checks whether the received shared secret corresponds to the generated one. If this is not the case, behave in exactly the same way as when the payment hash is unrecognized (including timing, to prevent timing side-channel attacks). If this shared secret is encrypted like the rest of the per hop data, the attacker can't learn the shared secret, and can't include it in his own replacement onion. He can't copy-paste the encrypted shared secret from the original onion either, since he has to use his own, different ephemeral key in his own onion. With this protocol in place, a final node can no longer be distinguished from a non-final node with this attack. The shared secret doesn't need to be very large: the number of attempts per second (to guess the shared secret) is limited by network latency, bandwidth and maybe some artificial rate limiting. If an attacker can do 100 attempts per second, then a 32-bit shared secret will take (on average) 2^31 / (100*3600*24) = 248 days to crack, for a single guess of which node is the final node. In the mean time, people will have noticed the ongoing attack and will have taken countermeasures. Besides, the transaction lock time will likely have expired in the mean time as well. CJP On 29-11-18 18:13, Christian Decker wrote: > Hi Corne, > > the HMACs are necessary in order to make sure that a hop cannot modify > the packet before forwarding, and the next node not detecting that > modification. > > One potential attack that could facilitate is that an attacker could > learn the path length by messing with different per-hop payloads: set > n=0 the attacker flips bits in the nth per-hop payload, and forwards > it. If the next node doesn't return an error it was the final recipient, > if if returns an error, increment n and flip bits in the (n+1)th per-hop > payload, until no error is returned. Congratulation you just learned the > path length after you. The same can probably be done with the error > packet, meaning you can learn the exact position in the route. Add to > that the information you already know about the network (cltv_deltas, > amounts, fees, ...) and you can probably detect sender and recipient. > > Adding HMACs solves this by ensuring that the next hop will return an > error if anything was changed, i.e., removing the leak about which node > would have failed the route. > > Cheers, > Christian ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Reason for having HMACs in Sphinx
Hi Corne, the HMACs are necessary in order to make sure that a hop cannot modify the packet before forwarding, and the next node not detecting that modification. One potential attack that could facilitate is that an attacker could learn the path length by messing with different per-hop payloads: set n=0 the attacker flips bits in the nth per-hop payload, and forwards it. If the next node doesn't return an error it was the final recipient, if if returns an error, increment n and flip bits in the (n+1)th per-hop payload, until no error is returned. Congratulation you just learned the path length after you. The same can probably be done with the error packet, meaning you can learn the exact position in the route. Add to that the information you already know about the network (cltv_deltas, amounts, fees, ...) and you can probably detect sender and recipient. Adding HMACs solves this by ensuring that the next hop will return an error if anything was changed, i.e., removing the leak about which node would have failed the route. Cheers, Christian Corné Plooy via Lightning-dev writes: > Hi, > > > Is there a reason why we have HMACs in Sphinx? What could go wrong if we > didn't? > > A receiving node doesn't know anyway what the origin node is; I don't > see any attack mode where an attacker wouldn't be able to generate a > valid HMAC. > > A receiving node only knows which peer sent it a Sphinx packet; > verification that this peer really sent this Sphinx packet is (I think) > already done on a lower protocol layer. > > > AFAICS, The only real use case of the HMAC value is the special case of > a 0-valued HMAC, indicating the end of the route. But that's just silly: > it's essentially a boolean, not any kind of cryptographic verification. > > > CJP > > > ___ > 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] Reason for having HMACs in Sphinx
Hey CJP, I am still not 100% through the SPHINX paper so it would be great if at least another pair of eyes could lookt at this. However from the original SPHINX paper I quote: "Besides extracting the shared key, each mix has to be provided with authentic and confidential routing information to direct the message to the subsequent mix, or to its final destination. We achieve this by a simple encrypt-then-MAC mechanism. A secure stream cipher or AES in counter mode is used for encryption, and a secure MAC (with some strong but standard properties) is used to ensure no part of the message header containing routing information has been modified. Some padding has to be added at each mix stage, in order to keep the length of the message invariant at each hop." At first I thought this would mean that the HMAC ensures that the previous hop cannot change the routing information. which was the first answer that I wanted to give. However I am confused now too. The HMAC commits to the next onion. So if the entire onion was exchanged and a new HMAC was provided (as you suggest) the processing hop would not know this. Such a use case would obviously lead to a routing scenario which would not succeed and would hardly be useful (unless the previous hop plans a reverse dos attacks from error messages or some other sabotage attacks which are references in the SPHINX paper but not discussed explicitly). On a second thought I reviewed chapter 2.1 of the Sphinx paper in which the thread model for attackers is described. As far as I understand that section one attack vector for which the HMAC shall help are man in the middle attacks. If HMACs are being used some bitflipping by man in the middles would be detected. However I think if a man in the middle speaks the BOLT protocol they could exchange the entire package and provide a new HMAC as a previous hop could do. Also the Thread model does only speak about security of the message not so much about the reliability of the protocol. I believe it is quite clear that if a routing node wants to manipulate the onion they can do so. In the same way how they can decide not to forward the onion. --> So the mix network itself can make sure that no wrong messages are delivered it cannot make sure that messages (which are unseen and unknown from where they came) are intercepted. Besides the Bitflipping usecase that I mentioned I agree with your criticism and also don't see the necessity of the HMAC anymore. The message is encrypted anyway and if bits are flipped the decrypted version will just be badly formated. If the header was manipulated the next hop would not be able to decrypt. Best regards Rene Am Do., 29. Nov. 2018, 16:31 hat Corné Plooy via Lightning-dev < lightning-dev@lists.linuxfoundation.org> geschrieben: > Hi, > > > Is there a reason why we have HMACs in Sphinx? What could go wrong if we > didn't? > > A receiving node doesn't know anyway what the origin node is; I don't > see any attack mode where an attacker wouldn't be able to generate a > valid HMAC. > > A receiving node only knows which peer sent it a Sphinx packet; > verification that this peer really sent this Sphinx packet is (I think) > already done on a lower protocol layer. > > > AFAICS, The only real use case of the HMAC value is the special case of > a 0-valued HMAC, indicating the end of the route. But that's just silly: > it's essentially a boolean, not any kind of cryptographic verification. > > > CJP > > > ___ > 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
