Replay Attacks and possible mitigations

Development and Technical Discussion
1

In a recent thread [1], Kurt outlined some possible replay attacks, and suggested consensus changes to avoid them.
Since then there has been some more keybase discussion of the seriousness of these attacks, as well as alternative ways to deal with them.
In this post I’d like to provide a summary of our current understanding of replay attacks and the options for mitigation.

Let’s consider the simplest possible form of a replay: that of a transaction tx with single input A, single output B, and single kernel K. In practice, replayed transactions would probably feature a change output as well, but they don’t fundamentally change the nature of the problem, so in the interest of clarity we’ll leave them out. A replay of tx happens when

tx: A --> B (K)

appears for the 2nd time on chain, say at height h2, after an earlier occurence at height h1. This is only possible under certain circumstances:

i) The same output can appear multiple times in the output MMR.
This is actually always possible in MimbleWimble with cut-through, since the consensus model doesn’t include the set of all spent outputs. Duplicate unspent outputs are not allowed simultaneously though: an output can appear at most once in the UTXO set. So B must have been spent in between h1 and h2, let’s say by some tx2.

ii) The same kernel can appear multiple times in the kernel MMR.
Since the Mimblewimble consensus model does include the set of all kernels, it’s up to each MW implementation whether to allow reoccurence of kernels, or to enforce unique kernels. The latter comes at a nontrivial cost though; necessitating a lookup of every new kernel in the set of existing ones. For the sake of efficiency, and simplicity of the consensus model, Grin chose not to do that.

iii) Output A must be re-created. This is not possible with publicly available wallet implementations. An attacker would need to make some minor changes to the source code to achieve this.

With all 3 circumstances holding, tx can then be replayed. At first glance this appears to be just giving free money to Bob, the original owner of B. But the following scenario shows how this could be an attempt to defraud Bob.

Let’s say that in the past, Alice paid Bob with tx to buy 1 trinket, and that Bob
ends up spending output B in tx2 to pay Charlie: A -> B -> C. Bob doesn’t realize that Charlie is colluding with Alice (or simply is an alter ego for Alice).

Now Alice proposes to buy another trinket from Bob, and they construct a transaction tx3 to pay for it. But instead of publishing tx3, Alice replays tx.
Bob’s wallet will notice output B as one it has generated.

If the wallet simply shows B as part of Bob’s spendable balance, and fails to show the pending status of tx3, then Bob may easily be fooled into accepting the replay as payment for another trinket. In which case Alice plans to replay tx2 as well after receiving the trinket. and thereby recover some or all of her payment, defrauding Bob.

This is what we must prevent from happening.

As mentioned before, one way is to change the consensus model, and enforce unique kernels, at some loss in efficiency.
The other way is to make wallets aware of previously spent utxos.

If the wallet still remembers that output B was spent earlier (in tx2), then it should consider new appearances of B as invalid, and either ignore them completely, or mark them as replayed so that Bob may realize the defrauding attempt.
This appears to be suffice for mitigating replay attacks, but we cannot guarantee that wallets remember all earlier spends, since they may become corrupted or inaccessible. In that case Bob would perform a wallet restore from his backed-up seed phrase.

Recall that we said above that “Bob’s wallet will notice output B as one it has generated.”
We can now see that this should be strengthened to “Bob’s wallet will notice output B as one it has generated after its last restore” if the wallet was in fact restored.

If the wallet should find an output that was generated before the last restore, then it cannot know whether it was spent before. Such outputs should be marked as suspect, and would not contribute to the spendable balance.
Instead, the user should be given the option to either spend them back to oneself, or mark them as safe, with the user accepting any possible risk of replay.

This leaves the wallet restore process itself, that also finds lots of previously generated unspent outputs. This presents the greatest burden on the user (but there are other reasons why a restore cannot generally be expected to be a seamless experience).
They could again be given the above options for each output, or to sets of outputs that they group together. Perhaps they would respend all those above a certain value and accept the risk of replay on smaller ones.

Together, these suggested wallet behaviours should make replay attacks mostly pointless.
They do come at the cost of some UX complications in the presence of attacks or in the case of a wallet restore, hopefully both rare events.

[1] https://forum.grin.mw/t/enforcing-that-all-kernels-are-different-at-consensus-level/

10 Likes
2

Given the already considerable UX challenges in the wallet, I’m very reluctant to add more complexity to it (which means another yet set of concerns for downstream wallet developers to manage) unless there are really no other viable options. I’d also be concerned that informing users that they need to self-spend for 100% safety sends entirely the wrong message.

Would it perhaps be worth some experimentation/modelling to better define the ‘loss of efficiency’ if kernel uniqueness needs to be enforced at consensus level? I’d imagine the straightforward solution would be that every node would need to create, store and maintain a B-Tree of all kernels in the kernel MMR. Redundant, annoying to develop and slightly ugly, agreed, but if validation time is not hugely impacted due to the presence of an efficient lookup tree, this approach seems like it would have zero impact on users or downstream developers at any stage, which may be worth the pain.

3 Likes
3

One difference with kernel uniqueness check is that a fully verifyng node would require having all kernels to check uniqueness for the next kernel. This isn’t true without uniqueness check since we could run a very light full node where one does not keep all the kernels and instead keeps just 1 kernel commitment which is the sum of kernel commitment that the node has checked.
This light full node is not implemented right now though, nor do I know what issues it might bring, but just something to think about.

Edit: it was also mentioned on keybase that NRD kernels would need to not be included in uniqueness check because they are not unique by definition.

1 Like
4

If you consider Grin on the long term, and keep the hypothesis that grin will get massive popularity and use in the future one day, also known as “massive amount of kernels”, verifying kernel uniqueness should be helped with including some “time dependant / block dependant” messages in the kernel signatures to improve a lot efficiency on the check. But yeah, benchmarking first different approaches would be probably best i am guessing

2 Likes
5

So theoretically there are 3 options as far as I can tell:

  1. Build wallet protection - no consensus changes
  2. Check for kernel uniqueness - seems impractical from what I was able to understand. This does have consensus changes but in the form of another validation check
  3. Shorten the attack window time - adding another thing to the kernel like max block height inclusion e.g. if last block is N and we sign max_height=N+2*60 then the transaction is only valid for 2 hours. After the signed block height, the kernel is no longer valid. This means the attacker would need to recreate the signature which they can’t. This also doesn’t really make the problem go away, it just shortens the window of the attack. It also adds more bloat for each kernel which is suboptimal, so we don’t really get a better security model while making the chain bigger.
6

You could couple the max_height with a consensus rule that no duplicate kernels are allowed within the last 120 blocks.

If we ever decide to commit to data in our UTXOs, max_height would be another great candidate to move there, to avoid chain bloat.

7

Is there some additional data we could add to a “payment proof” that would give recipients sufficient context in this situation? Payment timestamp for example.

My understanding of the “replay attack” is roughly as follows -
I am Bob.
Alice sent me funds previously.
I subsequently sent those funds to Charlie.
If Alice were to replay the A->B tx, this would open up possibility of replay of the B->C tx.
I do a full restore.
Alice replays A->B tx and (re)introduces an output into my wallet.
I now have a “raw” wallet with unspent outputs but no context, no tx history etc.
Alice is attempting to convince me that she paid me (a 2nd time) and that I should ship a widget out to her.
Alice is hoping I agree, so she can then “replay” the B->C tx to send those funds to Charlie.

I have no payment proofs as my wallet if restored and I have no tx history.
I effectively have no way of knowing the “state” of outputs in my wallet (w.r.t. replay risk).

So I ask Alice to produce the payment proof that we built together.
Alice reluctantly obliges and produces a payment proof. But this is from the 1st original tx (we never built a 2nd one, it was only replayed). Alice is hoping I don’t look too closely.

According to the payment proof the tx was from several months ago.
But looking at the output it was added on-chain recently.
The discrepancy here is enough to make me question Alice’ motives.

So before I ship the widget out I sweep this output into a new output and wait for enough confirmations to be comfortable. These funds are no longer at risk of replay.

tl;dr Maybe we don’t need to sweep all old outputs during a wallet restore. We can potentially be smarter with identifying “risky” transactions.

8

“Smarter” does not mean to make users having nightmares while using Grin. Otherwise there won’t be having any user soon

4 Likes
9

I think that putting any rules on the UTXOs means that the new nodes won’t be able to validate these rules. It seems that the only place where we can put additional consensus rules are kernels because they don’t disappear and so the history can be validated. Regarding the kernel max_height I mentioned, I’m actually not sure the idea is good. It complicates the validation as we need to be aware at which block the kernel was added.

interesting. So you’re saying you would basically put a timestamp (or block height) in the payment proof that would need to be checked at all times when receiving a payment.

Of course there’s also the more obvious scenario where you have a wallet history, but not long enough to know all the outputs you’ve spent. So let’s say Alice wants to send money to Bob, and they begin the tx forming where Bob creates his output ‘B’ for 10 grins. Alice knows of a previous output from Bob for 10 grins and uses that one instead of the one Bob just send her. Bob sees his balance increase and thinks it’s fine. Alice then does a replay that gives the money to Charlie - which is Alice’s other account. Looking at a payment proof at each receive might help here if it was timestamped.

10

Sure it can. Nodes only need to care about the UTXO set. By having a max height on the UTXO, it’s not possible to replay the transaction after that height.

I have no opinion on whether or not it should be implemented. I was just offering an efficiency improvement.

11

I guess it depends what kind of guarantees the network would provide regarding the rule. I don’t think you can verify that the max_height rule was followed for the utxos that were spent and are out of the horizon. So it was a consensus rule that had to be followed at some point in time, but can’t be verified anymore because the information disappeared. So people spinning a node a year after this rule was set will need to trust that it was followed at all times.
Whether that’s important to people or not is debatable. My current view is that ideally, each rule should be verifiable by a new node.

12

As Phyro said it might be an efficiency improvement but it is a hit in the security /trust models since a new validator would need to trust previous validators if he wants to know that no theft happened before he arrived.
what about be just like bitcoin, add a few bits in each kernels , verify they are different, and having to trust nothing and nobody from the past ?
it just sounds magic to me, considering we use cuttrough/pruning
Why would we make of grin the only coin in this ndustry where some past ownership information cannot be verified trustlessly by everyone

13

Another possible approach to identifying “at risk” outputs after a wallet restore.
I suggest we only need to identify outputs at risk of replay rather than prevent them at the protocol level. If we can identify them we can take steps to resolve the situation.

We find an unspent output in our wallet after a full restore. We’d like to know if it is “at risk” of replay.

  1. We determine the block this output originated in (based on output_mmr_size committed to in the header)
  2. We then determine the set of kernels associated with this block (based on kernel_mmr_size committed to in the header). Some subset of these kernels belong to the tx that produced the output, but we do not know which. So we just treat the whole block as a single aggregate tx.
  3. We can now index this subset of kernels and look for duplicates. This may produce false positives as we used all kernels in the block, but we do not really care. This index can be discarded after restore.

If we find zero duplicates then we know the output is not susceptible to replay. If we find any duplicates then we need to exercise caution with how we handle this output.

2 Likes
14

If I understand correctly, you would like to explain this “caution” to users, am I right? We can assume that many users do not know the technology. You are going to tell them that there is a weird situation somtimes in Grin where you would actually need to re-spend your output in order to avoid problems? Do you expect this sends a positive message, really? Without saying that respending an output contributes to chain bloat. Honestly, I do really hope that it will not be the choice that we will choose. A blockchain should be “spend”, “receive”, “forget”, and you want to make people having weird times using Grin while we can fix the problem at pretty minimal cost. I am sure that for you this would not create any problem and that you would still be happy to use Grin with this added usability complexity, but please put yourself two seconds in the skins of regular joes that would like to peacefully use this coin, and remember what is written on the Grin website regarding usability and access.

1 Like
15

Grin is still at a very experimental stage, no need to hurry at the risk of destroying what makes Grin unique. I think we need to be patient and take it step by step.

1 Like
16

What would destroy Grin? the robustness of an added consensus rule that will hardly hit the scalability of it, or rather the complexity of added wallet trickery that will never be robust and that will make users not knowing what is happening with annoying requirements (re-spending outputs). The answer is pretty clear, I think!

17

Are you suggesting that the Grin devs are just plain stupid?

EDIT: Closing the door to some future full kernel aggregation sounds like a death kiss to me.

18

If i disagree with someone on some points, it never means that i think they are stupid. That would be pretty crazy. Disagreeing with somebody never means that we think they are stupid

19

You state it like fact though. It doesn’t sound like an opinion.

20

i think the robustness aspect, no one can say that wallet trickery will be more robust than a simple, and easy to check, added consensus rule.
what is subjective is that robustness may not be the first thing to consider. I consider it important, maybe other don’t. But that’s it. I stand corrected and instead say “The answer is pretty clear to me”