Why is Monero a Weak Privacy Argument?Thursday, 20th of June 2019 · by Mohamed ElSeidy
Monero is one of the most popular cryptocurrencies that tries to address privacy. It utilizes different mechanisms to offer privacy for its users, such as decoy keys or mixins to obfuscate transaction inputs. There has been a number of academic research papers that devise attacks - both active and passive- that challenge Monero's promises about privacy guarantees. In this article, we briefly present two of these recent works:
- FloodXMR, a recently proposed active attack that traces transactions by examining the Monero network while interacting with it, i.e., flooding the network with cheap transactions. The proposed attack, according to the authors estimations can trace more than 47% of the entire network.
- A set of passive attacks that trace transactions by only analyzing the Monero blockchain and exploiting weaknesses within. According to their work, around 62% of transaction inputs with one or more mixins are vulnerable to trace. This work has been done by some of the most experienced academics in this field including, Andrew Miller and Arvind Naryanan.
The article concludes by discussing the main weakness of the Monero design that makes it a weak argument for privacy. One of the main ideas behind Monero's approach is obfuscating the transactions' origins, resulting in an obfuscated transaction graph. There is a stark contrast between obfuscation and pure cryptographic approaches that don't reveal any information including the entire transaction graph. The problem with an obfuscated transaction graph is that it reveals information (entropy) that invites current and future attacks to exploit it as we will demonstrate.
Active Attack: FloodXMR, Flood the Network
Recently, a new academic publication- not peer-reviewed yet - came out to challenge Monero's transaction privacy. FloodXMR, proposes a new traceability active-attack, called transaction flooding attack. This is not the first attack on the Monero network, numerous work has been done in Academia - see references [1-5] below - that aim at tracing transactions in Monero.
Left: Monero's obfuscation mechanism in its normal operation. Right: FloodXMR, attacker floods the network with their own transactions and hence when chosen randomly from the network for the next output, the attacker can track down the actual origin transaction.
As illustrated in the figure above, Monero's ring signature transactions obfuscate the original key k, that is actually spending the transaction, with a set of n other decoys (mixins) that are other random keys in the Monero Network. Every time a new transaction is created, a minimum number of mixins must be included in each input. The system selects a sample of mixins from the output keys of previous transactions and adds them to the transaction's input. Each input (tx.in) of transaction tx will have its own set of mixins. Finally, a digital signature is created to allow the receiver to get the payment without knowing the payer's keys.
The flooding attack is based on the principle that if the attacker owns these n other decoys and knows he did not spend anything in this transaction, then he can easily distinguish and trace the original key k. Therefore for this attack to work, one of the basic principles is to own a big list of valid output keys and have it grow along the course of the attack, which can extend to years. The core idea of the transaction flooding attack is simple. The attacker has to create low-cost transactions to build up a big knowledge base (i.e. list of output keys) from which the system might select keys to be used as mixins in future transactions. As discussed before, if the attacker knows all keys except one of the transaction's input tx.in, he can easily find out which key is being spent in that input of the transaction. The main challenge for a successful transaction flooding attack is to have enough keys so that the system selects all mixins of an input tx.in from the attacker's set of keys. To own output keys, the attacker has to flood the network with valid transactions, ideally with a very low-cost, making the attack feasible. Therefore, the attacker takes advantage of Monero's Bulletproof upgrade, which reduces transaction fees, to flood the network with his own transactions and, consequently, remove mixins from transaction inputs.
The authors also presented an analysis of the costs required for an attacker to conduct FloodXMR. According to their model, Assuming an attack timeframe of 12 months, their findings show that an attacker can trace up to 47.63% of the transaction inputs at a cost of ~ 10,500 USD - this number is adjusted to reflect estimations made by this thread.
Is FloodXMR an Imminent Threat?
Is FloodXMR an actual threat to the Monero network? Well, it might be, and it might also not be. What the paper presents is a possible or potential threat to the Monero network. To accurately assess the potential of the attack, the ideal thing to do is to run an active attack on the live network and watch it unfold. However, this was not the authors' approach to evaluation, as it is a very costly path. So, they preferred to assume a model - with parameters - for the Monero network and run simulations. This is a standard procedure in Academia when it empirical data is not within reach for whatever reason.
From my experience, I can tell that the model parameters will most probably not match the actual real world Monero network. Meaning that there are plenty of variables in play in the real network, that the model is most probably,not taking into consideration. Therefore, their assessments to the actual attack and its costs are highly likely to be off. This is why you will find Monero engineers and enthusiasts rebutting the paper in their discussions. All these can be viewed as debates and arguments around variables and parameters to their model assumption. Nonetheless, the threat is out there and theoretically possible.
Till now we gave an example of an online active attack, meaning that it analyzes the blockchain while interacting with the Monero network, i.e. flooding it with cheap transactions. However, there has also been work that targets passive attacks that only rely on analyzing the blockchain network and does not need active interaction with the Monero network. Arvind Naryanan and Andrew Miller et. al empirically evaluate the impact of two weaknesses in Monero's mixin sampling strategy which substantially undermine its privacy guarantees:
Weakness 1- Most Monero transaction inputs prior to February 2017 contain deducible mixins, and can be traced to prior transactions via analysis: 0-mixin transactions not only provide no privacy to the users that created them, but also present a privacy hazard if other users include the provably-spent outputs as mixins in other transactions.
When the Monero client chooses mixins, it does not take into account whether the potential mixins have already been spent. They find that among Monero transaction inputs with one or more mixins, 63% of these are irrefutably deducible. Moreover, they realized that most of the old input transactions did not contain any mixins at all, i.e., 0-mixins. The Monero software allows users to configure the default number of mixins to include in each transaction. Reminiscent of Murphy's law, many users did not know how to appropriately use it.
Weakness 2- Mixins are sampled from a distribution that does not resemble real spending behaviour and thus real inputs can usually be identified: When the Monero client spends a coin, it samples mixins to include by choosing randomly from a triangular distribution over the ordered set of available transaction outputs with the same denomination as the coin being spent. However, when actual users spend coins, the coins they spend are not chosen randomly from the blockchain, but instead appear to be highly skewed - based on empirical observations.
Weakness 3- Correlation between network behavior and Traceability: The authors show that after accounting for the estimated impact of mining pools, which opt-out of privacy by publishing their transactions on webpages, there remain a substantial number of potentially privacy-sensitive transactions, more than a thousand per day. They also emperically estimate that many of these transactions relate to the former underground marketplace AlphaBay. The recent seizure of AlphaBay serves as a reminder of the fragility of these marketplaces, whether due to lawful actions, hacks, or exit scams, leaving users remain at risk of deanonymization.
Obfuscation: Monero's Weak Pillar
Monero's approach towards privacy is obfuscation. Obfuscation is like adding chaff around to make it hard to identify or trace the actual target. This is obviously, better than a transparent public transaction graph, but much weaker than an approach that hides the transaction graph completely. Lets first explore the privacy terrain abstractly.
The Privacy Terrain
A sender is doing a payment. In Bitcoin, the sender origin is associated with a single public address. In Decoy based approaches, the origin is associated with several addresses to obfuscate the original address. Finally, in cryptographic approaches, there is no transaction graph that is revealed. Image taken from Ian Mier's slides.
Since the dawn of crypto, there has been interest in privacy. Since then, several approaches have been proposed:
1- Pseudo-Anonymity: It was once thought at first, that bitcoin transactions provide anonymity. Obviously, as we all know by now, this is far from the truth. The bitcoin network is a public transaction ledger and all the transactions are out there in the wild, the only twist is that transaction addresses are not directly linked to real IDs. With some basic data analytics, e.g., chain analytics, it became easy to track transactions to wallets and actual individuals.
2- Decoy approaches: Then, there is obfuscation-based approaches which typically try to obscure the transaction graph. They achieve this by trying to hide the transactions' origins by obfuscating it with several other decoy sources. Projects like Coinjoin, Mimblewimble, and Monero fall under this category.
3- Cryptographic approaches: Finally, there are purely cryptographic approaches that do not reveal the transaction graph at all. This approach is the most powerful of them all, as it can verify the soundness and correctness of the transactions while not revealing any information. Zcash and Zerocoin fall under this category.
The image below demonstrates the privacy approaches terrain since 2009. We can see that there is a natural progress towards using more cryptographic approaches.
The privacy terrain since 2009. Image taken from Ian Mier's slides.
The Problem with Obfuscation
A transaction graph in Monero resembles a big obfuscated graph with many false edges. The actual sender and receiver are associated with many addresses resulting in an exponential number of possible transaction graphs, and hence obfuscating the actual transaction graph.
However, obfuscation is not a guarantee for privacy. On the contrary, all of the traceability attacks dicussed and in the references below [1–5] include blockchain data analysis within it. Meaning that their attacks rely on analyzing the obfuscated graph while exploiting some weakness.
As we have seen in the previous attacks on Monero, the obfuscated blockchain data is still public and available forever, therefore vulnerabilities discovered at any point can be exploited to compromise privacy retroactively. Privacy is also weakened by the fact that choices made by some users may affect other users detrimentally, such as the mining pools' practice of publishing payout transactions.
I expect there will be more and more attacks in the future that run new exploits to unravel the obfuscated graph. Ian Miers, an upcoming Assistant Professor at University of Maryland , gives a great high-level overview about some of these attacks here.
Privacy is really a hard feature to get right. Cryptocurrency privacy combines the challenges of both anonymous communication and data anonymization.
This has always been a hot and hard topic in academia and practice. Given that, we are still in the very early stages of blockchains, many projects out there, are in fact experimental. While the ecosystem evolves and grows, there will be more data gathered and analyzed, research done, and attacks run. Many of these experimental projects will fail in providing the guarantees they sought for - it is just a matter of time. In Monero, the blockchain data is necessarily public forever and vulnerabilities discovered at any point can be exploited to compromise privacy retroactively.
In this article, we argue that there is a stark contrast between obfuscation approaches and pure cryptographic ones to achieve privacy. Obfuscation still provides the attacker with information that can be later exploited - as we have seen with FloodXMR, whereas purely cryptographic approaches do not leak any entropy. Since Monero's transaction privacy is all based on obfuscation mechanisms it is highly unlikely for Monero to lead this space, let alone, succeed.
I would like to thank Dr. Mohamed Fouda for his feedback, insights, and contributions to this article.
 Kumar, A., Fischer, C., Tople, S., Saxena, P. A traceability analysis of moneros blockchain. In: European Symposium on Research in Computer Security. pp. 153– 173. Springer (2017)
 Lee, K., Miller, A.: Authenticated data structures for privacy-preserving monero light clients. In: IEEE EuroS&PW. pp. 20–28. IEEE (2018)
 Miller, A., Mo ̈ser, M., Lee, K., Narayanan, A.: An empirical analysis of traceability in the monero blockchain. arXiv preprint arXiv:1704.04299 (2017)
 Wijaya, D.A., Liu, J., Steinfeld, R., Liu, D.: Monero ring attack: Recreating zero mixin transaction effect. In: 2018 17th IEEE International Conference On Trust, Security And Privacy In Computing And Communications/12th IEEE Interna- tional Conference On Big Data Science And Engineering (TrustCom/BigDataSE). pp. 1196–1201. IEEE (2018)
Yu, Z., Au, M.H., Yu, J., Yang, R., Xu, Q., Lau, W.F.: New empirical traceability analysis of cryptonote-style blockchains (2019)