Security reflections
This section aims to analyze the level of privacy provided by Möbius. We study both the design of Möbius as described in S. Meiklejon, R. Mercer. Möbius: Trustless Tumbling for Transaction Privacy, and the current implementation (up to commit c7b83813bdb2f41d63180ba7c96b849cbf119e6a, Friday 2nd of March 2018).
In order to carry out the security analysis of Möbius, we reasoned using different scales and different assumptions:
- Analyze the security and the privacy provided by Möbius at the Ring level (ie: The ring size is the size of the anonymity set)
- Consider Möbius as a whole and measure the security of the entire system. In this case, Möbius is considered as a system receiving requests from users (ie: The anonymity set is the sum of the sizes of all the rings. All rings are included/taken into consideration).
See: http://www.coinjoinsudoku.com for the description of the attack.
The idea behind CoinJoin gather multiple participants' bitcoin (UTXO model) transactions into a single transaction, in order to obfuscate the transaction graph. Moreover, in the case where all users were restricted to each contribute and receive the exact same amount of funds, no one could distinguish between the inputs, which one was intended to fund a given non-change output.
Because the original approach does not permit for change addresses, all participants must have equivalent balances in their input addresses before participating in CoinJoin. This is not convenient in practice. As most people will not be interested in the same denominations of transfer, this would introduce a lot of latency in the system. Thus, in order to make the model more acceptable for wide use, Gregory Maxwell proposed a solution that is more flexible than the initial CoinJoin, where all N users could agree on a uniform output (output target) size and provide inputs amounting to at least that size. Now, a transaction has N inputs, and N + Epsilon outputs (where Epsilon corresponds to the number of change address in case where the value of the inputs is bigger than the output target).
The relaxed version detailed above still implies that users have an interest in receiving the same output, which remains too rigid to keep a low latency in the system.
In an attempt to provide users with an online CoinJoin-like service, 'Blockchain.info' implemented SharedCoin. The design of SharedCoin is such that transactions have drastically different numbers of inputs and outputs. In other words, there are either many change addresses that are included as outputs, OR, SharedCoin attempts to obscure the path of customer funds by splitting and joining them into a random number of addresses.
While this online mixing tool seemed robust, Kristov Atlas showed in his article that this system was flawed. The CoinJoin Sudoku attack tries to identify individual participants in a SharedCoin transaction by searching for common ownership of inputs and outputs. This attack allows an attacker to know whether a set pf input addresses and a set of output addresses belong to the same owner. In other words, CoinJoin Sudoku enables to Reduce the anonymity set for participants, and to make it much smaller than the number of inputs and outputs. This attack uses the difference in denominations in order to give an attacker a speedup compare to a classic "brute force" attack.
SharedCoin was a solution implemented to be used with Bitcoin transactions. Thus using UTXOs as inputs of each transaction and using change addresses in case where the inputs value was bigger than the output. Moreover, as stated above, this tool relaxed many assumptions from the initial CoinJoin proposal, in order to keep a latency as low as possible in the system. Thus, payments of different denominations could be part of the same SharedCoin transaction.
Möbius, however, is a smart contract on Ethereum (no more UTXOs in Ethereum), and its current design gather payments of same denominations together. Thus, it appears that the CoinJoin Sudoku attack - as it is described in Atlas' article - does not apply here.
While SharedCoin splits payments into multiple denominations inside the same transaction, Möbius splits complex payments from Alice to Bob, into multiple rings. Moreover, the sender is only present in the sender anonymity set and does not have change addresses in the recipient anonymity set.
In order to measure the level of privacy provided by Möbius, we decided to lead our reasoning using an example.
Let's assume that:
- Alice is the sender
- Bob is the recipient
- Alice wants to send Bob 1.23 ETH
- We use 3 rings of size *N*, of respective denominations: 1ETH, 0.20ETH and 0.03ETH
If we continue the comparison with SharedCoin, Alice's payment would be split in M payments, all included in the same SharedCoin transaction. Thus, in the case where an attacker is able to infer that all these payments belong to Alice, he would be able to diminish the size of the anonymity set drastically.
Indeed, if we denote by I the size of the input set (I = |inputs|), and by O the size of the output set (O = |outputs|), an attacker is able to infer that M inputs and R outputs belong to the same user, would be able to reduce the anonymity sets drastically, going from I to I-M and from O to O-R. See [image of the SharedCoin attack on the CoinJoin Sudoku website]
However, in the case of Mobius EACH RING ACTS AS AN ANONYMITY SET. Thus, if Alice does a payment of 1.23ETH to Bob, she will be present only once in every ring anonymity set. An attacker, would be able to find out that Alice is sending money over multiple rings, BUT an attacker will not be able to reduce the anonymity as in SharedCoin.
The entire security and privacy levels of Möbius rely on unique ring signatures, stealth keys and stealth addresses.
- Unique ring signatures: Guarantee that the anonymity of the recipient is not revealed when a withdrawal is done to the Mixer. Plus, it prevents a malicious recipient from doing multiple withdrawals (cf: The notion of linkability introduced in linkable signatures)
- Stealth keys: Enable the sender to protect the identity of the recipient by deriving a stealth public key from his master public key. This stealth key is used to constitute the ring. The
stealthinessproperty ensures that any stealth address are distributed at random (ie: Indistinguishably between stealth keys and randomly generated keys). - Stealth addresses: Ensure that the recipient's identity is not revealed when he tries to withdrawal his funds.
Let's consider the following cases:
- Case 1: Alice does one payment of 1ETH to Bob, through ONE ring of size N and denomination 1ETH
- Case 2: Alice does multiple payments of 1ETH to Bob, through ONE ring of size N and denomination 1ETH
- Case 3: Alice does multiple payments of 1ETH to Bob, through MULTIPLE rings of size N and denomination 1ETH (ie: Alice wants to send M ETH to Bob, but this payment is split into M payments of 1ETH dispatched through M rings of size N and denomination 1ETH)
- Case 4: Alice does one payment of 1.23ETH to Bob, through ONE ring of denomination 1ETH, ONE ring of denomination 0.20ETH and ONE ring of denomination 0.03ETH
- Case 5: Alice does multiple payments of 1.23ETH to Bob, through MULTIPLE rings of respective denominations 1ETH, 0.20ETH and 0.03ETH
An attacker is likely to be interested in answering:
- Question 1: "Which recipient (of the recipients set) is Alice exchanging money with ? (Which recipient the link between sender is interacting with ?)"
- Question 2: "What is the identity of the recipient Alice is interacting with ?"
Answering Question 1: Requires to link the stealth public key of the recipient with the recipient's stealth address. Indeed, looking at the design of Möbius, the sender does a 'Deposit()' which results, among others, in the addition of the recipient's stealth public key to the ring. When the recipient tries to withdraw his funds, he should do it from a stealth address. Being able to answer this question implies that the attacker is able to differentiate between recipients. Nevertheless, the link between Alice and Bob is obfuscated by the stealthiness property and also, by the fact that Bob and Alice never interact directly with each other. While, the Bitcoin uses UTXOs, which give an attacker the possibility to track coins, Möbius does not provide such a degree of liberty to any malicious users.
AliceS funds are all added to the contract's balance (they are all mixed together, which makes coin tracking impossible), and BobS stealth addresses get credited from the contract address. Thus funds get "randomly" attributed - see the msg.sender.transfer instruction in the Mixer.
Answering Question 2: Requires that the attacker already identified recipient Alice is interacting with. In order to unveil the identity of the recipient, the attacker would need to link the stealth address of the recipient with the identity of the recipient. From a pure THEORETICAL point of view doing so is hard and requires solving known complex mathematical problems. In fact, in Ethereum, the addresses are the hashes of public keys. The "one-wayness" of hash functions makes it hard to find the pre-image, and thus the public key hashed. In addition, the attacker would need to find the private key used to derive the public key ('x' in 'xG'), but this is not feasible in less than a few million years of computation if the security parameters are well-chosen (this is the ECDLP). In short, theoretically, retrieving the identity of the recipient with the stealth address only is not possible nowadays (no one knows shortcuts to solve the DLP today).
- Denomination: Value of the transfer/Denomination of a ring
- Timing information: Time at which a function call is done to the Mixer (time of deposits and withdrawals)
- Gas information: Amount of Gas used by a function call. Knowing the gas specified and gas consumed can be useful for an attacker. It can be used to infer whether a function call has failed (revert), or, infer the function that has been called. In fact, all functions (Deposit and Withdraw) have a specific Gas fingerprint (a deposit costs less gas than a withdrawal for instance).
- Events triggered by the Mixer: An attacker has access to all events emitted by the Mixer contract. Thus, an attacker can know when a Deposit/Withdraw has occurred, when a ring is ready (meaning that recipients are going to withdraw their funds), when a ring is deleted. Finally, an attacker can get the ring GUID and ring message form the "MixerReady" event. Such information can be used by a malicious user in order to know when to attack for instance.
- Remaining data of the transaction object/block object: All data from the blocks and transactions, that have not been listed above can prove to be useful to carry out an attack
Note: We take N = 4 for the rest of the section.
A passive attacker will see:
| Address | Action | Amount |
|---|---|---|
| Alice | Deposit | 1 |
| Charlie | Deposit | 1 |
| George | Deposit | 1 |
| Eve | Deposit | 1 |
| Recipient1 | Withdraw | 1 |
| Recipient2 | Withdraw | 1 |
| Recipient3 | Withdraw | 1 |
| Recipient4 | Withdraw | 1 |
Since Alice protects Bob's anonymity by using a stealth public key, and since, Bob generates a temporary address from a stealth private key, his identity is not revealed. Thus, Bob is indistinguishable from the other recipients.
MAJOR PROBLEM: Bob needs to have gas on his stealth address in order to be able to call the Withdraw() function of the Mixer. Thus, he needs to transfer funds from one of his address to his stealth address, which links the stealth address with Bob's identity.
What appeared to be secure from a theoretical point of view does not seem to be secure in practice...
A solution to this problem has to be found (How to create a funded stealth address ? How to prevent the recipient from paying gas to withdraw ? Should we make the sender pay ? If yes, which problem does it imply ?...)
It appears at this point that the current design of Möbius does not provide enough privacy to the recipient, despite the use of strong cryptographic primitives. The funding of stealth addresses is the weak link that leaks a lot of information to the attacker.
In order to study the potential attacks in the cases 2,3,4 or 5, we consider Möbius as a system receiving 'Deposit()' requests from a set of senders, and receiving 'Withdraw()' requests from a set of recipients.
Here, it does not matter whether Alice and Bob do multiple transfer using a single ring or a set of rings. We assume that they interact multiple times. In all these cases, the attacker will see Alice interacting with a ring (this is the only link the attacker can see), without knowing the link that binds Alice with the recipient.
However, in order to keep Alice and Bob's link as opaque as possible, they should generate new stealth addresses/keys for all of their payment together. While this can be acceptable in so cases, it can also introduce a consequent overhead in the case where a payment is split. Indeed, keeping latency low is key in order to keep Möbius usable in real life. Thus, we might need to implement a system to create rings of common/popular denominations, in order to make sure that rings get filled as quickly as possible. The problem is that in such as case, a big transfer of an "unpopular" denomination would be split into multiple transfers of "popular" denominations, meaning that Bob and Alice would need to generate as many stealth addresses/keys as there are payments in order to proceed to this "big transfer". Generating keys/addresses has cost, off chain certainly, that will increase the time of the transfer. Plus, the problem of funding stealth addresses gets even worse in this scenario.
Moreover, timing information can be used to link payments with each other. Take for example the case where Alice desires to send 1.23ETH to Bob through rings of denominations 1ETH, 0.20 and 0.03 (we assume here that the denomination 1.23ETH is not "popular", and thus split into denominations of 1ETH, 0.20 and 0.03 which are said to be "popular". Note that the "popularity" of a denomination can be established by looking at the most frequent payments done on the network, during a test phase for instance). We assume that Alice and Bob really want their transfer to be private. Then, they both use 3 stealth addresses. The passive attacker, will see:
An attacker can still extract valuable information by observing the interactions with the system. In fact, it depends on how the "splitter" would be implemented, but it is likely that Alice's payment of 1.23ETH being split into 3 payments that would be deposited in their respective rings in a time interval of [t, t+delta] (let's say that the deposit of 1ETH is done at time t, the deposit of 0.20ETH is done at time t+d1, and the deposit of 0.003 is done at time t+d2, with d1,d2 < delta). Then, a timing analysis reveals that these three payments, coming from different addresses certainly, are likely to come from the same sender. Coupled with the link introduced by the funding of these addresses, the attacker is almost certain of the identity of the sender. Same applies when the recipient withdraw his funds (although he might defer his withdrawals of a significant time to prevent time correlation, but this makes the withdrawal longer and might affect the user-friendliness of thee system).
Note that the bigger the denomination two parties want to exchange, the more the transfer is split into smaller denominations and the easier the attack.
While splitting the payments into common denominations helps keeping a low latency in the system, it is also a way to give attackers the possibility to infer valuable information. We could indeed think about adding a feature to active/deactivate the denomination splitting, however if Alice wants to send an "odd" payment to Bob (let's say 137.33456 ETH), chances are very little that N-1 other participants will fill the N-1 entries of the ring; resulting in funds being stuck for ever (or for a very long time) on a contract.
As mentioned here, Withdraw() calls can be replayed.
In the case where an honest recipient wants to claim his funds, but does not specify enough gas to his Withdraw() call, the contract will run out of gas while trying to execute the withdrawal. This will result in a revert(), and the honest recipient will have to try to claim his funds again, but specifying a bigger amount of gas this time. However, an attacker observing the activity on Möbius would be able to see the reverted transaction, and thus would have the opportunity to replay the 'Withdraw()' before the honest user. In fact, the ring signature is given as a parameter of the Withdraw() function, and the private key used by Möbius to produce signatures is different from the user's wallet private key. Thus, an active attacker could easily extract the ring signature form a reverted Withdraw() call and replay it with a sufficient amount of gas.
While the scenario described above implies that the honest user mistakenly set the gas of his function call, we thought about potential attack scenarios in which the active attacker would have more possibilities.
Let's imagine that Oscar, an active attacker, observes the activity of the Mixer on the blockchain. Then, Oscar watches the different events emitted by the Mixer, as well as all incoming requests to the Mixer. Oscar receives a MixerReady event when a ring is full. Thus, he knows that a ring of denomination X is full (The denomination can be inferred by looking at the Deposit() call that is the closer in time with the event emission). Oscar can thus prepare his attack.
Oscar might want to know the profitability of his attack (How many funds he can steal). This information is given by the value specified in the deposits and by the ring denominations.
Since the Mixer contract's code is public knowledge, the attacker can study the code, understand the behavior of the system and see that all deposits of value X are put into rings of denominations X.
Then, Oscar could implement a few functions on his client in order to keep track of the state of Möbius at any time. Counting the number of deposits, watching the MixerReady event, observing their 'value' field and counting the number of withdrawals, give Oscar all the pieces of information he needs in order to craft a "map" of all the rings in the Mixer. He can know their state (how many entries does a ring of a specific denomination has at time t for instance). Since the RING_SIZE is public knowledge (part of the contract), a simple computation would be:
state_of_rings_of_denomination_X_at_time_t = number_of_observed_deposit_of_value_X_at_time_t / RING_SIZE
The entire part of state_of_rings_of_denomination_X_at_time_t corresponds of the number of FULL rings of size RING_SIZE and of denomination X (we call this number nbFullRing), and the decimal part of state_of_rings_of_denomination_X_at_time_t leaks the number of participants in the ring nbFullRing + 1.
Conclusion: Being able to infer the state of Möbius at time t gives another degree of liberty to the attacker, and we can imagine how this would be useful to trigger attacks (knowing that a ring of denomination X only contains one entry could be used by a group of malicious users to collude and trigger a Sybil attack to de-anonymize the only honest user already in the ring, for instance).
The message replay attack could be made even worse in the case where the 'RING_SIZE' is big. In fact, the current benchmark of Möbius reveals a linear relation between the RING_SIZE and the gas consumption of a Withdraw(). While, it takes around 750k gas to execute a Withdraw() with a RING_SIZE of 4, it can take up to 1.7million gas to do the same operation with a RING_SIZE of 10. In the best case, a few withdrawals fit in one block (if the gas limit is big enough in the block). Nevertheless, this means that if all recipients claim their funds at (almost) the same time, only a few of them will be mined first, the others will be added to the transaction pool. At this moment, an attacker could use this behavior in order to extract the ring signature form a pending withdrawal and replay it with an enormous gas. Since rational miners want to increase their profits, they'll prioritize the malicious withdrawal. Thus, the malicious Withdraw() call will overtake the honest call in the transaction pool and be executed before it, resulting in a theft of funds. The time blocks are mined depends on the consensus algorithm used in the system, but we can imagine that such a threat is realistic. In the worst case, the Withdraw() gas consumption becomes too big to even fit in a block, and the system becomes unusable.
Mobius is vulnerable to a deposit withholding attacks where a participant deliberately withholds depositing into a ring. This results in any funds deposited into a ring being locked and preventing withdrawals. This has the effect of stalling transactions on the network and locking funds into the contract. This attack is also zero cost to the attacker since there is no action and no gas to pay.
Suppose Alice is paying Bob and Mallory is paying Charlie. Both are making payments of 1 ETH. Their payment go through a ring of two with a denomination of 1 ETH. Assuming the off-chain data has been generated and distributed to participants Alice makes a deposit of 1 ETH into the Mobius contract. Mallory does not make a payment into the contract. This means that the MixerReady event is not fired and that it is not possible to withdraw from the contract. Furthermore Alice's funds are locked in the contract.
Mitigations against the attack include a destruction mechanism by which the ring can be destroyed and funds returned to the recipients. It would also be possible to create a "dummy payment" system to fill up rings, although this would require knowledge of the private keys required to deposit and this introduces another attack vector.
Overall, Möbius is quite exposed to side channel attacks. While the cryptography primitives used are known to be secure, an attacker is still able to access a large amount of data. Such data can be used to acquire valuable information about the transfer being done and carry out an inference. Here is a non-exhaustive list of the potential analysis that an attacker could carry out:
- Timing analysis can be carried out on the deposit and withdraw events (see above)
- Frequency analysis along with denomination analysis can be carried out in order to infer the nature of the payment. Example: if an attacker is able to see a payment of 2000£ sent from X to Y every last day of the month, one can infer from the value and the frequency of this transfer (once every month), that this is a payroll. The attacker can thus infer that the sender is an employer and the recipient his employee. Using additional sources of information, the attacker could be able to undermine the privacy of both parties. Indeed, if by any mean the attacker managed to know the sender (the company), the attacker could be able to infer the recipient using his own knowledge. Let's assume that the attacker has worked as an intern for the company before and was paid 2000£/month at the time, and that Charlie is the new intern in the company, then the attacker knows with a high probability that Charlie is the recipient of the payment.
- Addresses analysis: An attacker could track the funding/defunding of a stealth address to a "public"/"known" address in order to guess the identity of the recipient/sender. One could argue that the recipient could spend the received amount directly from the stealth address to an online commerce for instance. Nevertheless, this leaks information to the attacker. First, the attacker saw that the recipient funded the stealth address with another address. Second, if the recipient does a payment form his stealth address to an online shop for instance, one could use information from this transfer to link to the recipient. Example: If I send funds from my public address to my stealth address, receive 0.03ETH on my stealth address, and do a transfer to an online shoes shop to by shoes with the money I received from Alice, then, a persistent attacker could see that I consulted online shoes shop frequently for the last few weeks and use this to strengthen the link between my identity and my stealth address (Here the attacker used the funding of the stealth address and my consumption habits as attack vectors). The third scenario is where I can't spend the funds directly from my stealth addresses. Let's take the case where Alice sends me 20ETH so that I can buy a car. Since the systems aims to ensure low latency, Alice's deposit is split into 20 deposits of 1ETH. I create 20 stealth addresses and get credited 1ETH on each. Problem, I need to do one big payment to buy my car. Thus, I need to gather the funds of my different stealth addresses into one address: Doing so leaks information, and the attacker knows that all these stealth addresses belong to the same recipient.
- Denomination analysis: Allow an attacker to gain knowledge about the potential nature or activity of a sender/recipient. For instance, a payment equivalent to 1billion dollars is very unlikely to involve a "normal" person, or a little company. Thus, the attacker can infer that it might involve governments/banks or big companies, and thus narrow down his research to theses potential parties.
IP tracking is possible on non-anonymous networks (Note that such attack are could also happen in the case of private networks in the case of an insider attacker). If Möbius is not used on top of anonymous network solutions, an attacker could also have the liberty to track nodes' activity at the network level. If Möbius were to be deployed for production use, it would be deployed on top of an onion-routing service (Tor for instance). However, we do not know whether using Möbius with Tor would be practical and ensure a low latency.
Sybil attack are also a threat in the case of Möbius. One malicious user (with many identities on the network) or a group of malicious users could collude in order to constitute the 'RING_SIZE-1' entries in a ring and de-anonymize the only honest party.
After analyzing the vulnerabilities of Möbius, we list below a set of potential improvements that could be done:
- Implement Confidential Transactions to hide the amount of transactions.
- Deploy Möbius on top of anonymity networks such as Tor
- Research on solutions to the stealth addresses funding.(Subtract the gas of the withdrawal for the funds being sent ? If yes, what happens in the funds transferred are lower than the gas necessarily to execute the
Withdraw()call ? ...) - Research on solutions to the events broadcasting. As it is implemented today, the Mixer emits events each time a Deposit/Withdraw is made. This can be used by an attacker to monitor the activity of the ring. Thus, even someone who is not involved in a payment in Möbius could simply declare a "watcher" and receive all events emitted by the Mixer. As it is the intrinsic nature of Blockchain to store all transactions (and thus events) in the public ledger, one question would be to know whether, we could find a way to hide to arguments of the
MixerReadyevent (the ring GUID and the ring message) to the parties that are not involved in the exchange. However, a myriad of problems seem to be raised by this potential solution. How would it be implemented ? (Is it even possible ?) How would this be a threat to privacy of the parties involved in the payment ? An attacker might be able to use another side channel source of information here, which would be the absence and presence of information. In such a case, if an attacker (lacking the ring GUID and ring message in his 'MixerReady' event were to know that someone received this pieces of data, then he would directly know that this "someone" is doing a payment in the ring !) - Have multiple rounds of mixing/multiple layers of Mixers (of different sizes ?) in order to spread payments (randomly ?) among these internal rings. This would decrease drastically the probability of the attacker guessing the parties involved in a transfer. Problem: this solution adds more latency to the system (increases the time to process a transaction, and the gas cost).
While Möbius appears to be an elegant and lightweight solution to provide users with "plausible deniability" during transfers (the goal is to keep a system auditable), the proof of concept we implemented reveals major flaws. Some weaknesses described in this section can be solved, we still need to evaluate the cost of such solutions. This cost should be measured in term of:
- Privacy/Security added
- Performances overhead
- Time of development
Privacy on a blockchain is a very dynamic field of research today. Some companies designed models that distinguished themselves from the rest: Monero and ZCash. We follow these project with great interest, and are well aware of their advantages, but also their flaws. Indeed, despite the Byzantium hard fork on Ethereum, zk-SNARKs remain costly (a private transaction would cost between 1.5 and 2million gas), and many tools have to be built in order to be able to use them properly. Thus, Möbius has been implemented as a proof of concept in order to challenge the theoretical design and measure its performances. We are well aware of the flaws of the design and, we need to measure the potential overhead introduced by the improvements that need to be done.
In short, We need to determine the relation R in:
overhead(Mobius) + overhead(Tor) + overhead(CTs) + overhead(off-chain) R overhead(zk-SNARKS)
where, CT represent the implementation of the Confidential Transactions, and off-chain corresponds to the off-chain computation required to generate the stealth addresses/keys and ring signature.
If R turned out to be the relation <, then it might be worth to try to improve the design of Möbius. Nonetheless, if we figure out that R is > then, Möbius might not be a suitable solution, and we would need to focus our research on improving existing privacy solutions.
- http://www.coinjoinsudoku.com/advisory/
- https://medium.com/@nopara73/new-bitcoin-anonymity-technique-the-clusterfuck-wallet-d48aa1787324
- https://en.bitcoin.it/wiki/Friendly_addresses_with_enhanced_privacy
- https://github.com/monero-project/mininero
- https://elementsproject.org/elements/confidential-transactions/
- https://github.com/nopara73/ZeroLink/