A Cryptographic Flaw in Zerocoin (and Two Critical Coding Issues)
In this article, we present a cryptographic flaw in the Zerocoin cryptographic scheme (not Zerocash), which allows an attacker to burn coins of honest users. On the way, we identified two more critical coding issues in a software library implementing Zerocoin, allowing an attacker to create money out of thin air and stealing coins from honest users. Zerocoin is used by multiple cryptocurrencies (Zcoin, PIVX, SmartCash, Zoin, and Hexxcoin), and some of them are still vulnerable to specific attacks. If you use one of these cryptocurrency, please see our “FAQ for users” below.It is often believed that cryptocurrencies provide anonymity but for the vast majority of cryptocurrencies including Bitcoin that’s just not true. Even though users are not strictly required to reveal their identities, all transactions are publicly available on the blockchain, and users typically reveal at least a part of their identity to the people with whom they perform transactions. These two facts together make most cryptocurrencies far from anonymous.
One of the technologies that aims to improve anonymity is “Zerocoin”, a cryptographic scheme, which has been deployed in several cryptocurrencies. This post reports several security issues in Zerocoin, which led to vulnerabilities in the cryptocurrencies Zcoin, PIVX, SmartCash, Hexxcoin, and Zoin; some of those vulnerabilities are still exploitable.
Zerocoin
Zerocoin has initially been proposed by the cryptographers Ian Miers, Christina Garman, Matthew Green, and Aviel D. Rubin, and this scheme is used in practice. A second scheme, providing the same functionality and potentially better efficiency, has been proposed by Jens Groth and Markulf Kohlweiss, but this scheme has never been deployed in practice.
Basic idea
The basic idea of Zerocoin is to achieve anonymity with two operations called “mint” and “spend”. The “mint” operation produces a zerocoin with a public coin and a secret key. In all of the aforementioned currencies, you can perform a mint transaction that gives up one regular coin of a base currency (e.g., one hexxcoin) to be allowed to mint one zerocoin. So a mint operation basically allows you to exchange one regular coin for one zerocoin.
The second operation is called “spend”. If you spend a zerocoin, you provide a proof that you are the owner of a zerocoin (technically, that you know the secret key) and authorize the spending. This is where the anonymity comes into play: The proof that you provide when spending is a zero-knowledge proof and it hides which zerocoin in the blockchain is spent. Instead of telling the world that a particular zerocoin is spent, the proof reveals only that the person is eligible to spend one zerocoin, but without telling which one it is — it could be any of the minted coins in the blockchain.
Preventing double-spending
The basic idea raises the impression that double-spending is easily possible. If verifiers do not know which zerocoin is spent, how can they verify that the current zerocoin was not spent before?
The solution to this problem is that each zerocoin has a supposedly unique serial number. Only when you spend a zerocoin, the protocol requires you to reveal this serial number and to prove in zero-knowledge that it is the right serial number. Now verifiers can just keep a set of already used serial numbers. If they see a spend transaction with a serial number, which has already been recorded in the set of used serial numbers, they know that this transaction is a double-spend and invalid.
A denial-of-spending attack on Zerocoin
In both of the proposed Zerocoin schemes, a minted zerocoin is represented by a public bitstring, which is a commitment to the serial number but hides the serial number at the time of minting. Users are supposed to choose a random serial number to ensure that it is unique (with very high probability). However, an attacker can, instead of taking a new random serial number, freely choose the serial number when he mints a zerocoin.
This leads to the following attack: An honest user tries to spend her (honestly generated) zerocoin and sends the spend transaction (including the serial number) to the network. An attacker, which is assumed to have control over the victim’s network, now blocks that message such that it never reaches the nodes of the cryptocurrency. Then the attacker mints a new malicious zerocoin with the exact same serial number. The attacker can now spend this maliciously zerocoin, revealing the serial number.
As soon as this spend transaction performed by the attacker is confirmed, the nodes in the cryptocurrency network record this serial number as used. As a result, the honest user cannot spend her zerocoin anymore. Whenever she tries, her spend transaction will be rejected as a double-spend, because the serial number has already been recorded as used. This effectively burns the zerocoin of the honest user!
Performing the attack in practice
There are several issues which make it difficult to perform this attack in practice:
- An attacker needs to be able to intercept and block network messages sent by the victim. This often requires the attacker to be in a somewhat privileged position in the network, e.g., the ISP of the victim or a malicious Tor exit node if the victim uses the Tor network. Also, being a miner will help the attacker.
- If the attacker is not able to block network messages reliable, it may actually happen that the spend transaction of the victim is included in the blockchain before the spend transaction of the attacker. If that happens, then the zerocoin of the attacker and not that of the victim becomes unspendable, i.e., the attack backfires. As a consequence, it is risky to try to perform the attack in practice.
- This is even further complicated, because zerocoins minted in one block can only be spent in a later block, and more than one block distance may be necessary depending on the consensus rules of the cryptocurrency. That means that the attacker may need to be able to block network messages for a longer period to avoid the risk of a backfire.
However, we cannot rely on the fact that nobody will try to perform an attack, and none of the mentioned issues make an attack impossible.
Financial interest to launch the attack in practice
The attack allows to burn the coins of a third party. The financial gain for an attacker may come from a loss of reputation in the currency when making the attack public. That is, an attacker may bet on a dropping currency before launching the attack. After attacking several participants, he discloses the attack. The loss of confidence makes this currency fall.
Provable security
Both zerocoin schemes have been proven secure, i.e., they come with correct mathematical proofs which demonstrate that the schemes fulfill certain security properties. Moreover, when it comes to the handling of serial numbers, the implementation used in practice work exactly as designed.
The problem is in the security properties, or more exactly in the mathematical definitions, which describe what “secure” means. While there was a definition that mandates for instance that no zerocoins can be stolen, there was just no definition that mandates that no zerocoins owned by honest users can be burned. In other words, the requirement that it should not be able to burn zerocoins had simply been forgotten.
Research paper
We described the attack informally as well as proved the necessary new security properties in our paper.
Fixing the problem
A simple fix is to use a new random public key of a signature scheme as a serial number (instead of a random bitstring). Spend transactions must be additionally signed under the public key (= serial number). Then an attacker can still see the serial number, and can still mint zerocoins with the same serial number, but the attacker won’t be able to spend those malicious zerocoins, because the private key is required to do so.
More issues
During our analysis of the code of libzerocoin, two more critical issues we found. Those were not issues in the Zerocoin scheme itself but implementation issues in the library libzerocoin, which is used by all mentioned cryptocurrencies (all projects maintain their own copy of libzerocoin). We need to stress that libzerocoin was initially built by the authors of the Zerocoin paper as a research prototype that come with huge warnings about its security and non-readiness for deployment (see https://github.com/Zerocoin/libzerocoin#warning) It is irresponsible to use such implementations without a thorough code audit.
Both implementation issues have been discovered independently and reported by the PIVX developers, who audited and fixed their local copy of libzerocoin before deploying it PIVX.
Inflation
The first issue was in the handling of serial numbers. The serial number is an element in a finite group, i.e., a number modulo some larger number N. The implementation didn’t check that a given serial number is in the “smallest” representation, which is unambiguous. (For example, 3 and 13 are different representation of the same number modulo 10, but only 3 is the smallest representation of this number modulo 10.) Remember that the serial number is used to identify double-spends of the same zerocoin, and on the mathematical side the zero-knowledge proof will work irrelevant of the representation used. Hence the same zerocoin could be spend multiple times using different representation of the essentially same serial number. This made it possible for attackers to create money out of thin air and inflate the currency. This bug can be easily fixed by rejecting spend transaction that reveal serial numbers in the wrong representation. Only numbers in the range [0; N[ should be accepted.
A very similar issue affected cryptocurrencies based on CryptoNote, e.g., Monero, in the past; the difference is just in the structure of the finite group: in the original Zerocoin scheme, the group consists of numbers modulo a fixed number, whereas in CryptNote, it is an elliptic curve group.
Improperly signed transactions
The second issue is related to signing spend transactions. The original Zerocoin scheme uses a signature of knowledge, a special form of a zero-knowledge proof, which additionally acts like a digital signature.
However, in libzerocoin, this “signature” did not cover a hash of the transaction to be signed. This allowed everybody, who sees a valid spend transaction sending zerocoins to some address A, to effectively replace the transaction with his own transaction sending the zerocoins to a different address B. So it was possible for attackers to steal money.
Which cryptocurrencies are affected?
Zcoin, PIVX, SmartCash, Zoin, and Hexxcoin have been vulnerable to the denial-of-spending attack. Of those currencies, Zcoin, and Zoin are still vulnerable at the time of writing.
Zcoin, SmartCash, Zoin, and Hexxcoin have been vulnerable to the inflation bug that made it possible to print money. To the best of our knowledge, none of those currencies is vulnerable anymore.
Zcoin, SmartCash, Zoin, and Hexxcoin have been vulnerable to the bug that led to improperly signed transactions. To the best of our knowledge, none of those currencies is vulnerable anymore.
We’d like to stress that we haven’t verified the patches that have already been applied. If we say that a currency is not vulnerable anymore to a specific attack, then this claim is based on statements from the maintainers.
Are my coins safe?
First make sure that run the latest release of your wallet software, which can be downloaded from the website of your cryptocurrency project. (At the time of writing, the latest releases are version 0.13.5.7 for Zcoin, version 3.0.6 for PIVX, version 0.13.1.5 for Zoin, version 1.1.1 for SmartCash, and version 4.0.3.0 for Hexxcoin.) If you have unspent minted zerocoins in Zcoin or Zoin (in the “Zerocoin” tab in the GUI), we recommend not to spend them at the moment, even if you run the latest software available at the time of writing of this post. It’s only safe to spend minted zerocoins once a wallet with additional fixes and patches has been released and/or appropriate chainforks have been performed.
We recommend the maintainers of all affected currencies and wallets to release a statement about their plans to fix the remaining issues; if in doubt please contact your maintainers and don’t contact us.
SmartCash and Hexxcoin disabled all features related to Zerocoin. Also, PIVX disabled all features related to Zerocoin for a planned upgrade. As a result your unspend zerocoins are not at risk if you use SmartCash, Hexxcoin or PIVX. However this means that these minted zerocoins cannot be accessed, at least not at the moment. The SmartCash team seems to refund owners of unspent mints, please contact them for support. The Hexxcoin team told us that they plan a fork to enable the Zerocoin features again after applying the appropriate fixes. The PIVX is working on a larger upgrade for their Zerocoin implementation and will enable the Zerocoin features again after the upgrade.
If you have questions, please contact the maintainers of your currencies and wallets. Don’t contact us.
Did you contact the developers of the cryptocurrencies?
When we discovered the denial-of-spending vulnerability, we contacted only Zcoin, because this was the only implementation of Zerocoin that we were aware of. The Zcoin team hired Tim from our team to work on patches. During the work on the patches, we discovered that other cryptocurrencies using libzerocoin were affected as well, e.g., PIVX, SmartCash, Zoin and Hexxcoin. We eventually contacted developers of all these cryptocurrencies, and we apologize if we reached out to some teams late — we were simply not aware of these cryptocurrencies and our goal was certainly not to give some currencies an edge over others.
What is the relation to Zerocash and Zcash? Are these affected?
Zcash is a cryptocurrency that is entirely unrelated to our findings. It is based on the Zerocash protocol, not on the Zerocoin protocol. Even though they have some similarities, and Zerocash can be seen as a successor to Zerocoin, the Zerocash protocol is not vulnerable to the attacks described in this post.
Has this been exploited? How much money is affected?
Regarding the inflation vulnerability, the Zcoin team announced that 17000 Zcoins have been generated out of thin air, and the SmartCash team announced that that 2.1 million SmartCash have been generated. A Zoin maintainer told us that no zoins have been generated. Also, a Hexxcoin maintainer told us that no hexxcoins have been generated.
We have verified none of these numbers. We encourage interested users to look at the blockchains and verify the numbers.
We are not aware that any of the other vulnerabilities has been exploited. However, if it has been exploited, then there is no public record of it in the blockchain.
Are there other implementations of the Zerocoin protocol?
We are only aware of libzerocoin.
I need help. Who should I contact?
Please don’t contact us for technical support, contact the developer teams of your cryptocurrencies instead.
Feel free to contact us if you have questions, comments or observations that are of general interest, or if you feel that there is something wrong in the post. However, please be aware that we do not plan to update this post, so please don’t contact us if the information here is outdated.
What can we learn from the bugs?
We think that it boils down to these main points, none of which are novel insights:
- Provable security is not a magic bullet. Even academic papers with detailed security models and proofs provide no perfect guarantee that a piece of cryptography is secure. Extra effort is necessary when putting cryptography in practice, e.g., as has been done with Zcash.
- Don’t deploy cryptography that you don’t understand. Unfortunately, this seems to be a common pattern in the cryptocurrency space. Cryptography is hard. Just because many new projects and companies in the cryptocurrency space work on cryptography, this does not mean that inventing and deploying cryptography has suddenly become easy.
- Don’t use libraries that come with big bold security warnings.
Are there other cryptocurrencies that use libzerocoin?
To the best of our knowledge, only the five aforementioned cryptocurrencies are affected by our findings. However, even though we tried our best do keep an overview, we cannot guarantee that we haven’t overlooked any cryptocurrencies. Another cryptocurrency that indeed uses libzerocoin is Zerovert, but it is an abandoned and dead predecessor of Zcoin.
We note that it is particularly hard to keep an overview, because, there are hundreds of other cryptocurrencies that copied the original libzerocoin into their code base, e.g., Regalcoin or Abjcoin. In fact, a GitHub search reveals over 1600 repositories with a distinctive code pattern (you need to be logged in to click this link and perform this search). While we haven’t checked all of them, it seems that they are all pretty similar. In all of them, all code parts related to libzerocoin are *turned off*, so these are false positives and do not seem to be affected by our bug.
Some of them may be actual cryptocurrencies with a few nodes running, and some may not. We don’t know. We conjecture that all of these repositories have been created using an automated tool, and we have no idea why this tool includes an unused copy of libzerocoin in the repositories. We suspect that the tool is related to a service provider, which claims to sell cryptocurrency projects, including “ICO Website” and “unique genesis block, the source code and a compiled Linux & Windows client”. Our conjecture is based on the fact that the website mentioned Regalcoin as an example but we have not investigated this further, so we could be wrong.
I saw a talk in which you claimed that the denial-of-spending vulnerability is fixed already?
Yes, Tim from our team gave a talk at the Genesis London Conference 2018. At this time, we (wrongly) assumed through discussions with the Zcoin maintainers that the vulnerability had been fixed in Zcoin, and that Zoin had integrated the fixed code from Zcoin already. However, this turned out to be wrong: Later we were surprised to see that fixes were not fully deployed yet in Zcoin (and consequently neither in Zoin) in contrary to our understanding of the statements made by the Zcoin maintainers.
For PIVX the situation was different: We knew that the problem was unfixed, but we had forgotten to include this fact on the slides. We are very sorry for any confusion which this mistake may have created.
Are you personally involved, invested or affiliated with the cryptocurrencies?
None of us owns or has ever owned any coins of the affected cryptocurrencies or was otherwise invested. The Zcoin team hired Tim from our team as a cryptographic advisor, primarily to work on patches for libzerocoin to fix some of the discovered vulnerabilities. The contract was terminated shortly after delivering the patches. Zoin offered us a bug bounty as an award for contacting them and explaining them how to solve the problem. We have not accepted it so far but we may accept it in the future.
Tim Ruffing, Sri Aravinda Krishnan Thyagarajan, Viktoria Ronge, and Dominique Schröder
Tim is a researcher at Saarland University, Sri Aravinda Krishnan, and Viktoria, are researchers at Friedrich-Alexander-Universität Nürnberg-Erlangen in Germany. All people are supervised by Professor Dominique Schröder, who holds the Chair of Applied Cryptography (ChaAC) at Friedrich-Alexander-Universität Nürnberg-Erlangen in Germany.