[Vulnerability Disclosure] Post-Mortem of 10-Block-Old Decoy Selection Bug 2023 #8872
Comments
|
I wonder why this disclosure has been delayed until now after a fix in form of 0.18.2.2 has been out for almost two months now and users / wallets / service providers could have been urged to update their daemon to mitigate the implying risk and prevent more transactions like this being created. Especially frequently transacting users have been affected most. Nevertheless, it would be great if someone could run some kind of magic to find out how many transactions have been affected in total and percentage of total transactions. 0.14.1.0 has been released in July 2019, so the bug has been there for almost four years. |
First, I agree this announcement shouldn't have been delayed. It should have gone out close to when the issue was discovered before the release, and definitely along with the release. This was a mistake that I bear some responsibility for that I would like to not see repeated in the future. When I announced a similar bug in the algorithm 1.5 years back, I had some inaccuracies in my initial announcement. I corrected them quickly, but the damage of those inaccuracies was already done as they spread through the media. I continue to feel that damage to this day. Speaking for myself, I was hesitant to make a similar mistake this time around because of that experience. The above isn't an excuse, it's just explaining what led to my personal hesitation. I could have and should have been more proactive ensuring there was clearer messaging for this issue earlier on, both so users can protect themselves, and for wallets in the ecosystem to roll out an update. I take responsibility for this mistake. Ultimately processes for these sorts of announcements can and should be improved. In this case what would have clearly helped at the least was me making it clearer both in IRC and to members of the core team what the ramifications of this issue were straight away. Maybe it also makes sense to bring back dev meetings where people discuss PR's in flight; that might have increased the chances more people would become aware of this PR's ramifications. But, what would have been best was simply taking initiative and not hesitating to deliver the message. Credit goes to @jeffro256 for taking initiative on this.
@jeffro256 has done this. You can see in the chart the percentage of transactions affected has a ceiling of around ~0.6% of all transactions (the dark blue line in the chart). One additional point worth mentioning: I'm not aware of any wallets in the wild that avoided this issue, but it is theoretically possible anyone could have implemented a decoy selection algorithm that avoided it. If some unknown custom wallet software out in the wild did not have this issue (e.g. some high volume merchant), and accounted for a large number of the observed transactions with an output 10 blocks old, then the severity of this bug would be reduced. Off hand, I would say this is probably unlikely, but technically there is no way of knowing if this is the case or not. |
|
Fair enough, I don't want to blame anyone and thanks for this honest reply, @j-berman! I can just talk from the outside, since I didn't make it to a dev / mrl meeting for the last couple of months, so I appreciate your work and this discovery even more. However, like you said we should think about processes how certain issues should be handled. Sure, if funds are at risk you cannot disclose anything until a fix has been done, users urged (maybe for some other reason) to update and only when most of the network is up to date. Issues like this one potentially affecting users' privacy should be published much faster after a review from some other skilled people, without spreading potential misinformation which shouldn't be the case latest when the patch has been reviewed, otherwise we lose credibility.
I've noticed it, however I have some issues with the chart. It mentions inputs, not transactions which can have and mostly(?) have several inputs. If one of those is affected, all of them are (think of a p2pool miner consolidating dozens of inputs but also an incoming tx one or change). On the other hand the chart goes back to early 2017, while 0.14.1.0 came out mid 2019. The peak in the ratio of 10/11 has been mid 2018, were those not affected and only became an issue with some decoy selection tweak? @jeffro256 I would be very grateful if you could run your script to count the total amount of tx from when 0.14.1.0 has been released since from the release notes I don't see what could have caused the current issue. Also are there any rings containing two 10-block decoys? If so, wouldn't this be some kind of evidence of a custom implementation? |
|
After more digging, this off-by-1 bug affects versions released starting from v0.13.0.2 [source]. @janowitz valid response, I agree with pretty much all of your points.
I don't see how that peak could be affected by this bug since that was before the bug was introduced (in October 2018). Versions prior to v0.13.0 appear to be safe because they rely on the same logic that matches consensus to determine which set of outputs were usable. That peak seems like it would be a distinct investigation in its own right. |
|
commenting here for visibility: from @j-berman 's comment
can we then delete this sentence from the disclosure:
|
Yes this metric would likely be even more telling than counting raw ring members. And since inputs within transactions are more or less guaranteed to be created by the same implementation, batching the results by transaction instead of by ring member will give a more "median" look at the data where transactions where large batch transactions do not sway the results as much proportionally. Sorry I have been slow to run new results, I'll look into this soon. |
|
@plowsof: updated |
|
Since this will be added to the blog I will close this issue here. |
Post-Mortem of 10-Block-Old Decoy Selection Bug 2023
Quick Facts
Introduction
When the Monero wallet needs to construct a transaction with a certain input, it also picks decoys inputs from the chain based on a certain distribution called a "gamma distribution". The gamma distribution makes picking recent decoys more likely than picking older decoys, mimicking how real users spend their funds. However, in the gamma picker code, there was a off-by-one bug that didn't allow the gamma picker to pick decoys which are exactly 10 blocks old. The wallet can, however, still spend owned outputs that are exactly 10 blocks old. This means that an external observer can guess the true spend of an input ring with very high likelihood if one of the ring members is exactly 10 blocks old.
This bug has been patched in v0.18.2.2 and it is recommended that all users update their wallets as soon as possible. Since many third-party wallet applications rely on the core "wallet2" code, if you do not use the Monero Core CLI/GUI wallets, ask the development team of your wallet if they have upgraded to the new wallet2 code. Upgrading your wallet to v0.18.2.2 will not only improve your sender anonymity, but will increase the anonymity pool for all other users, including those the older vulnerable wallet code.
Technical Explanation
More In-Depth Background
(Large portions are text below are copied directly from @j-berman's "Post-Mortem of Decoy Selection Bugs" in 2021)
The decoy selection algorithm is designed to select outputs from across the blockchain based on observed spending patterns, as recommended in Moser et al. The paper's analysis uses spending patterns from earlier versions of Monero - where in some cases, the real outputs used in transactions could be deduced with certainty - in order to arrive at a distribution of Monero user spending patterns. The paper highlights that users were more likely to spend outputs received relatively quickly than they were to spend outputs held for a long time. The paper then recommends factoring in the observed spending patterns when selecting outputs from across the blockchain to use as decoys, rather than apply an equal probability to the entire set of outputs from across the blockchain. This way, newer outputs would be more likely to be selected as decoys than older outputs, thus better obfuscating which output is real in users' transactions.
When the paper's recommendation was first implemented in Monero v0.13.0.0, the wallet correctly applied the observed spending pattern from the tip of the blockchain when selecting decoys. However, when the algorithm was upgraded in v0.14.1.0, the algorithm applied the observed spending pattern from 10 blocks prior to the chain tip. This was done because outputs younger than 10 blocks old are locked and cannot be spent, therefore it seemed logical to apply the distribution starting 10 blocks prior to the chain tip so as to only consider spendable outputs.
The Off-By-One Bug
Before picking decoys for a new transaction, the wallet grabs the cumulative distribution of outputs across the blocks for the entire chain using the RPC command /get_output_distrubution.bin. To prevent the gamma picker from picking decoys from blocks that are younger than ten blocks, an "end" pointer is calculated which bounds the chain information that the gamma picker considers. You can see that the calculation does not consider the last 10 blocks (the block unlock time) of chain information. However, since a newly created transactions will not enter the current highest block, but the next future block, the newest information considered at the time of transaction construction is actually 11 blocks older than the next future block (which ostensibily a new transaction will reside in).
However, wallets will still construct transactions with owned ring members that are exactly 10 blocks old. If all wallets adhere to this flawed logic, then the only time an 10-block old ring member will show up in a transaction is if it is the true spend. This heuristic would be devastating for sender anonymity with 10-block old true spends.
The bug was patched in PR #8794.
Emperical Analysis
The graph you see above shows how much 10-block-old ring members vs 11-block-old ring members appeared in transactions over time. The blue line represents the percent of transaction ring members on-chain that are exactly 10 blocks old over time, with yellow representing the same for 11-block-old ring members. The dashed green line shows the ratio between these two values over time. There are a few interesting patterns, but the most relevant to this analysis is the spike in 10-block old ring member usage after the v0.18.2.2 release, the first wallet release with the bug fixed, as well as the increase in ratio between these two ages. Since there is currently no way for the core dev team to track wallet version usage, there isn't any readily available data on the proportions of users using old wallets versus new wallets, information which would help establish correlation in the 10-block old ring member data. However, such a noticeable spike in the number of 10-block old ring member usage coinciding precisely when the patched release was launched suggests that this patch did statistically alter decoy selection for young ring members.
Also, thankfully, the data tells a more complex story than our worst-case heuristic scenario. There were still a lot of 10-block old ring member usage before the bug was patched, likely due to custom wallet software. This makes the deanonymization heuristic less potent than originally anticipated.
Conclusion
Not to beat a dead horse, echoing @j-berman in his original decoy selection bug post-motem: "anyone with a background in statistics and probability theory is encouraged to join in discussions geared toward improving the algorithm." In hindsight, this bug could have been discovered if the statistical distributions had been analyzed carefully. Instead, the bug was stumbled upon by accident while attempting to fix an infinite while loop during decoy selection. This brings me to a second point which I think is important but may be controversial: the wallet2 decoy selection code needs to be completely rewritten. The
wallet2::get_outsfunction is over 600 lines long, with few comments and inadequate testing. Seeing as how the important decoy selection is to the privacy model of Monero, the code which actually implements this functionality in most wallets is of substandard quality. There are a lot of great ongoing discussions relating to decoy selection like non-coinbase-only selection for non-coinbase, coinbase consolidation transactions, ring binning, etc. And while Monero has always been forward focused, it has also been more grounded and battle-tested as compared to other more experimental privacy-preserving coins. This only happens through the hard work and dedication of community members peering over the code and hardening it. Feel free to join the #monero-research-lab and #monero-dev channels on IRC/Matrix to participate and communicate more with existing community members. You can also join relevant Monero Workgroups.The text was updated successfully, but these errors were encountered: