Paper Info
- Paper Name: Remote Side-Channel Attacks on Anonymous Transactions
- Conference: USENIX Security ‘20
- Author List: Florian Tramer, Dan Boneh, and Kenny Paterson
- Link to Paper: here
- Team: Team Stapler
- Food: Pairs well with baklava
Remote Side-Channel Attacks on Anonymous Transactions
Privacy with cryptocurrency is defined by 4 properties:
- Confidentiality: private transaction amount * Untraceability: private fund history * Unlinkability: cannot confirm whether two payments are to the same user * User Anonymity: given an address, cannot determine the connection between the peer-to-peer network node and the wallet To provide these guarantees, privacy oriented cryptocurrencies utilize public-key encryption. Unfortunately this makes verifying transactions more difficult. In order to do this, we need a trusted ‘prover’ that can test the validity of the transactions without revealing the transaction source, destination, and amount. This information about the transaction that is proven to be correct is known as the ‘witness.’
Attack Overview
Certain side channel attacks have been demonstrated to successfully break these privacy guarantees. An example is an attack that reveals the recipient of a transaction, breaking the unlinkability guarantee. This can be done by building a side channel attack within the peer-to-peer network that includes the recipient. The attacker can monitor the traffic either between the wallet and the node, or simply measure traffic between nodes, and observe differences in these messages without the necessity for decryption. After you determine which payments are destined for a particular P2P node, payment addresses/diversified public keys can then be linked to an IP address of the P2P node traced earlier.
A different attack profile is to build a side channel at the sender. The goal of this particular attack is to try to leak the amount of a transaction. This is much harder to obtain, has many limitations, and requires exploiting timing differences in the arithmetic operations of the prover. This type of attack might be possible under certain scenarios, such as when you can trigger a transaction, analyze recurring payments, or when the system outsources proofs to a remote service and these proofs can be monitored.
ZCash Background
ZCash provides unlinkable privacy by public-key encryption with an additional feature - a recipient’s single private key can be used to derive multiple public keys, none of which can be associated with any of the others. You then can use only one public key for each transaction. You derive the public key by multiplying the private key by a random elliptic curve point. Different points on the elliptic curve create different public keys that are equally valid. When you spend that money, you then reference that particular public key that was used to receive the money padded with additional randomness. You do not combine cash amounts together in a traceable way at any time. When sending the money to a different recipient, you derive a shared key with the recipient’s public key and encrypt the new transaction onto the block chain using the shared key. To maintain anonymity, receivers are not notified that money is being sent to them, instead they attempt to decrypt every transaction using their private key to re-derive the shared key (which is attached alongside the transaction node for the purpose of this comparison). If they are successful, this indicates that the payment is for them.
ZCash Attack #1: PING
Two different side channel attacks exist for de-anonymizing ZCash nodes, detecting if a particular node was the recipient of a transaction or not. The first attack simply utilizes ping. Since incoming messages are processed serially, you simply ping the receiver immediately after the node receives a new transaction. Since the response to the ping is sent back only after the transaction is processed, the delay before the ping response indicates how long it took the receiver to decode that particular transaction. Since successful and unsuccessful decoding takes different amounts of time, this indicates whether the node was successful at decrypting a particular packet. This same attack can determine the processing time of new blocks as well, indicating how many transactions inside that block were intended for that node. This attack was demonstrated to reveal payments to nodes with 100% accuracy when the attacker had a 21ms round-trip latency time delay between the attacker and the victim, but it also had success when running over slower networks such as Tor.
ZCash already released 2 patches to fix this, one simply adding multithreading for handling incoming messages, the other requiring additional block handling fixes. Adding a 2nd dedicated “firewall” P2P node and keeping your wallet node one step removed from the network would also prevent this attack from working, but would require you to waste a lot of storage space on your system with 2 complete copies of the block chain.
ZCash Attack #2: REJECT
The 2nd attack only works if you know the victim’s address. When you send out a malformed transaction to a particular destination, the node that successfully decodes this transaction will conveniently respond with an error message. This allows you to link a particular node and particular address together very conveniently. All other nodes other than the victim are unable to decrypt the transaction and will not return an error message. These malformed transactions can also crash the recipient client on validation, leading to additional exploits. All of these issues were fixed by ZCash by treating parsing failures as failed decryption events, rather than notifying the sender.
Attacking Monero
Monero also uses public-key encryption, but unlike ZCash, the transaction amount is the only thing sent with a mutually derivable key. The same conceptual attacks described for ZCash can also be performed. Monero nodes attempt to decrypt all transactions, and timing differences determined by side channel monitoring reveal if the decryption was successful or not. Wallets may be connected to remote nodes or to local nodes. The initial state of any wallet before the entire block chain is downloaded to a person’s device is to connect their wallets to remote P2P nodes. When in this state, anything with the ability to monitor network traffic between the wallet and the remote node may associate the wallet with a particular IP address. There are 3 different wallet implementations, each vulnerable to different attacks. The CLI wallet attack described in the appendix works similar to the REJECT attack above. If the wallet is successful at decrypting a packet containing a transaction requiring a user to manually enter a special 2nd decryption key, the wallet hangs while waiting for this key, and this can be detected by the attacker, allowing them to associate that wallet with that payment address.
Traffic Analysis Attacks
If a wallet is connected to a remote node as described above, and the attacker can monitor this communication, the wallet will directly request known transactions where it is the payee, revealing this to an attacker. Communication requests consist of #1 new transactions, #2 known transactions where it is the payee. Since Monero traffic is slow enough that occasionally no transactions occur between refreshes, occasionally an attacker monitoring traffic will notice that an update will only be sent to a single node instead of all the nodes. This leaks that there were “payee transactions” for that single node since no other nodes were receiving updates containing new transactions.
Monitoring network traffic of remote nodes
Since Monero’s block update algorithm does not simply perform an update every 20 seconds, but rather sleeps for exactly 20 seconds after handling the last batch, the slight time delay past the 20 seconds count reveals the processing time of the last batch. This slight delay is only a couple of milliseconds, and reveals more about the speed of the hardware running the Monero node than anything else. However, if the wallet associated with that node is the recipient of the payment transaction, this requires 2-3ms longer to process than similar processing delays when no transactions are being processed with that node. Other than the time between block requests, you can also look at unconfirmed transaction time. If the node takes longer to confirm a transaction synchronized to occur exactly during a block update than it does for other transaction confirmations, also timed to occur exactly during a block update, then you can derive the block processing time from this information, and perform the same conclusion about that node processing payment transactions or not. If the wallet is on a local node there is no network traffic to intercept, but you could send a request to the victim wallet that you wanted to identify and also simultaneously make a request from an attacker to a node. Since communications to the wallet are performed under a lock, the response back to the attacker will be delayed if that node is communicating with that wallet, revealing this association.
Timing Attacks: zkSNARK Provers
) 
ZCash shows a very slight timing difference when processing transactions of different amounts. When the prover calculates the sum of products, it optimizes away where the item is zero. This reveals the total number of nonzero elements in the witness. Since this Hamming weight corresponds strongly with the transaction amount, you can get a general sense of the scale of the size (of the binary numerical value) of the transaction. This was only successful with ZCash, as Monero uses constant time cryptography.
Discussion
What did this paper contribute to science?
Is this paper more of an engineering contribution, or does it have significant scientific contribution? A scientific contribution could be made if this opens up new directions for research, such as bolstering side channel defense related investigations. In some cases, the researchers find some sort of bug in an application. Often, what researchers will do is take a bug and develop tooling that will enable the detection of the bug in various software. Sometimes, the researchers find additional software that contains the same class of bugs. In that case, the researchers have a solid contribution to science; however, when they fail to find a less systemic problem it lessens the scientific contribution. This paper is a somewhat narrow contribution to science, but it is a positive contribution that benefits science, the industry, and the people who use the technology.
The contribution can also change depending on the chosen venue. For example, if the paper was “Hey we found timing side-channels in the linux kernel that can be exploited with speculative execution” in 2020, it is unlikely it’d be accepted; however, in the crypto exploitable side-channel world, reviewers thought that it was an interesting attack Tip: If an attack paper doesn’t cite a similar attack paper, then it should be rejected. Be sure to cite all the related work when writing your paper.
Is this a paper simply about good crypto implemented poorly? A paper about finding bugs in Acrobat Reader would probably not be significant. Zcash and Monero are real world systems that are at their core designed for anonymity. The paper presents a demonstration of a class of bugs able to break this guarantee for just about any configuration of the protocol.
### Discussion on Remote Side-Channel Attacks on Anonymous Transactions
Does this paper open up the topic of insecure usages of secure algorithms for crypto currencies? There is value in proving that “the fundamental crypto is right”, but this showcases that even with good crypto, people can implement these crypto systems in ways that comprises some of the system’s goals.
The fix presented for Zcash in this paper seems straight forward (i.e., making all responses take the same time as the slowest), so why did they miss this type of attack? It’s possible crypto developers aren’t taking side-channel attacks seriously and maybe this is the first step to get them to notice that there can be huge consequences for ignoring secure practices. As a side note: often when researchers report design level flaws, developers don’t want to fix the issue so they respond to the report saying it’s a non-issue. However, the next generation of researchers that are working on timing side-channels can point to this paper for proof of significant impact and pressure developers to take it more seriously.
Reexamination of a remaining problem can offer scientific value
Sometime in the early 2010s, there was a USENIX paper on floating-point side channel attacks for Firefox and several years later, a very similar paper was published at USENIX. The paper was almost identical because the identified vulnerability had not been fixed. This illustrates that the problem still exists and developers/corporations aren’t taking discovered vulnerabilities as seriously as they should be. Why not fix timing attacks at the protocol level? Eg: replies should always come after 30 seconds from the initial request. It’s a solution that was explicitly pointed to in the paper, so why hasn’t it been implemented in the protocol if the fix is easy? Zcash’s optimizing operations are based on secret information so it’s surprising that this is an issue that was overlooked. Was this something the designers overlooked in design or was it just a bug? How did zcash/money acknowledge this and their take on this? There was no clear response from designers. Sometimes, designers don’t concede flaws. Eg: The SDN flaws paper received a lot of pushback saying that it’s not a problem. 