Report: “Wrapped Serials” Attack
- by PIVX Core Developers Furszy & Random.Zebra
On March 6th 2019, an attack was detected on the PIVX network zerocoin protocol, or zPIV. This blog post provides detailed information about the vulnerability, how it was detected, where it arises from and how it is possible to exploit it, how it was fixed, the steps taken to protect the PIVX ecosystem and how it was disclosed.
The “Wrapped Serials” vulnerability is fixed on #PR-837.
The vulnerability allows an attacker to fake serials accepted by the network and thus to spend zerocoins that have never been minted. As severe as it is, it does not harm users’ privacy and does not affect their holdings directly (it does indirectly though, through inflation, as we will see).
On March 3rd, it was noticed that block 1679090 was crashing any wallet compiled with the GMP library bignum implementation (which was added in #PR-681) while wallets compiled with the original OpenSSL library were able to normally process the same block.
While looking for possible inconsistencies between the two libraries, we discovered that there was something bigger going on. The GMP “bug” was, in fact, highlighting an implementation problem which was bypassed in the OpenSSL library due to the following different behavior:
getuint256()method of the
BigNumclass does not throw an error when the number has more than 256 bits. It just returns the least significant 256 bits of it.
After noticing in the failed block (and in many subsequent blocks) such strange serial numbers, bigger than 256 bits, but with the last 256 bits equal to other valid serials, it was immediately clear that the GMP crash was not due to a bug in the library. It was caused by an implementation flaw which was being exploited.
Zerocoin functionality was disabled on the network right after the problem was identified, using one of the PIVX “sporks”, while conducting the investigation of the issue and coding the proper fix to the problem.
Sporks are multi-phased forks, a mechanism introduced by Dash to safely deploy new features to the network through network-level variables to avoid the risk of unintended network forking during upgrades.
The attack started on block 1,679,090 (Sat, 02 Mar 2019 01:40:53 UTC), and finished (due to the spork activation) on block 1,686,229 (Thu, 07 Mar 2019 02:13:11 UTC).
Over the course of five days, it involved the spending of 477 zerocoins, of various denominations (for a detailed list, see section “blockchain analysis”), with invalid serials (belonging to coins that were never minted). This resulted in the creation of a total of 568,897 PIV (roughly 438,000 USD at current valuation) out of thin air.
There were two main distinguished issues which enabled this attack. They are described below.
1) The serial number S was represented on the system with the
BigNumclass [/src/libzerocoin/Coin.h#L139] which allows to store (unlike
uint256) values with size bigger than 256 bits. The transaction signature check was performed only over the last 256 bits of the
BigNum object [/src/libzerocoin/CoinSpend.cpp#L140] using the
getuint256() method mentioned before, and not over the whole object (which should have only 256 bits anyway).
2) The Signature of Knowledge verification, as it is done after the coin spend signature verification, was not checking the bitsize of the serial number [/src/libzerocoin/SerialNumberSignatureOfKnowledge.cpp#L125] (assuming it’s already checked a priori in the coin spend signature verification) and thus allowed for serials with more than 256 bits.
“Wrapped Serials” unwrapped
We now explain the construction that allows the exploitation of the bug and verify it on the collected data.
Minting a zerocoin C requires the calculation of the Pedersen commitment over a serial number, S, and a randomness number, v:
Here p is a prime number, while g and h are two generators of a multiplicative subgroup of prime order q embedded in the field Fp (hence q divides the order ϕ(p) = p-1) .
The values of these constant parameters of the zPIV protocol are:
p = e5f1c46cf7c4676f8e17f88373e340d6678a6054f55dc93694479a2844706f5e
q = a33a39fceb03fef51aa5f50322b557664a8364d7ad0ada150487fae8576af9e3
g = 9a7fd6508dfa79258e50019ab6cb59b4f91b2823dcd9250fb3ccf9fd8263b29a
h = ccbbdd469de23cfba19728b625ee7b197b60389eebb7383ec63184fe6ddc94ac
or, in decimal representation:
p = 161472451372577012801537365723922556211848315807594124571141764504999544408362125454072210505394654546158172195415400420843049128478444392858426591864457908932595588930280642318371343109552712010176780306349674252280901839211018654763617444978825645960598892468748168577682155499188091216022125857543517086273
q = 73829871667027927151400291810255409637272593023945445234219354687881008052707
g = 108493142922526728666632567817665003170796919105635379209392198423511598366861400891077767613510689994661458247627782967131380742158803028619370850599707720731033316825396014640162292085141754403426615747531818926542832854769301325069842551396491200417945280389398187668412942712019408916579750269745817796962
h = 143768995274515109916888615338023796202313741184535853350599647575636989065333362353091304549805392264078663304320988432201880421827463211723771823949879552174363526461270186191043021150237526637849110930802283354306286109510594071984169318215708259157133799891029533089380569710081411838705163403395345909282
As easily verifiable, the number q (the multiplicative order of g and h in Fp) has exactly 256 bits. It is crucial to allow only for serial numbers within the order q.
Failing to do so will result, as we will show, in the possibility to create different serials for the same coin.
The attack starts with a “normal” zerocoin mint. The attacker -let’s call him Bob- picks valid serial and randomness, performs the calculation in eq.1 to obtain the value of the coin C and embeds it in the script of an output of a mint transaction.
When the mint transaction is verified, the value of the coin C is added to the required accumulator. Later, when the coin is spent, the value of the serial number S is revealed and recorded by each node to check against double spends.
Therefore, Bob’s goal now is to create a second serial number S₂ ≠ S for the same coin C, in order to be able to do another zerocoin spend, without having to first make a second mint. Essentially “double spending” the zerocoin C.
The new serial has to verify three conditions:
- It has to be different from the previous spent serial (in order to pass the double-spending checks and being accepted as valid by the network).
- Committing to it (with the same randomness v) should result in the same coin C obtained by committing to S.
- The last 256 bits of it must correspond to those of S, as they represent a valid public key, and the spend transaction input must be signed with the corresponding private key.
We can rewrite these three conditions as:
We can rewrite eq.2 to obtain a condition on the value, ΔS, that has to be added to S to obtain the new serial S₂:
Therefore ΔS = S₂ -S is divisible by q (due to eq.2) and is divisible by 2²⁵⁶ (due to eq.3) and so (being q and 2²⁵⁶ co-primes) it is divisible by their product:
for some value K∈ℕ*.
In conclusion, the new serial S₂ can be obtained from S, simply by adding multiples of the quantity q 2²⁵⁶ to it :
It can be easily checked that each of the 477 invalid serials S₂ found in the inspection (as next section outlines) embeds in its least significant 256 bits another (but valid, and already spent) serial number S and they together verify eq.4.
The first invalid serial number appears in block 1679090 in the following transaction:
It has 1280 bits:
or in decimal representation:
S2 = 20450098045454915962170487974429567257328353950088365367869203709830543347472565587134369791143246022166697167199462884475206304511831153452859104452952148246048491332691052132461372940576887735260893469346461936609587285779710136184912768172173457408962089346056037194524521835189103394043526953550170506424167895983467187120294346069059651545609133212621478433080190186711509976422050
Taking the right-most 256 bits (last line of hex representation of S₂), and calling S the resulting number:
S = f80892e78c30a393ef4ab4d5a9d5a2989de6ebc7b976b241948c7f489ad716a2
or in decimal representation:
S = 112188735122646332673120264475492645110759969755119099599400488524274592061090
we find that it represents another serial number, which is valid, and was already spent on block 1678364 (about 9 hours earlier) in the following transaction:
These two serial numbers verify eq.4 with the following value for the coefficient K (and the constant value of q used in the zPIV implementation):
K = 2392127870481312541145280337317481839146801113778185419328783964239554699853736031170164664341183575233474638104486328939741346789623623859106648377096122414199636895656600751535550828562194042393152005312327207228295031606121091730
With such big coefficient the resulting ΔS is divisible, not only by q but also by ϕ(p) = p-1.
A particular example is offered on block 1681524, in the following transaction:
Here there is a 512-bits serial:
Hex(S2) = a33a39fceb03fef51aa5f50322b557664a8364d7ad0ada150487fae8576af9e3
S2 = 8548915088448100358830025159294609927638754396015919844019766466875902660870255092292366521175660752441608968674693395141285263301578379760229038424307200
embedding the valid serial, S:
Hex(S) = f4fd4d7248e6a51f1d854ddd2a4965996154acc6b8de5aa6c83d4775b283b600
S = 110811881877285919779333627674890084097834865631989961861384957298979004200448
which was already spent on block 1681503 in the transaction:
In this case
K=1 thus it holds exactly S₂ = S + q 2²⁵⁶. Therefore:
Or, in other words, the new serial S₂ is obtained simply concatenating the 256 bits of q
q = a33a39fceb03fef51aa5f50322b557664a8364d7ad0ada150487fae8576af9e3
with the 256 bits of the valid serial S
S = f4fd4d7248e6a51f1d854ddd2a4965996154acc6b8de5aa6c83d4775b283b600
This is the minimum possible bitsize (512) for an invalid zerocoin serial number verifying the conditions outlined in the previous section wrapping a valid serial of exactly 256 bits.
To perform an extensive search of the blockchain, the new
getserials RPC call has been added to the wallet. This call looks at the inputs of any transaction in a range of blocks and returns the serial numbers for any coinspend found. When the
fVerbose flag is set to
True the same method provides additional information related to the zerocoin spend:
- Receiver Address
- Transaction ID
- Block number
The following python script has then been used to collect the data and filter out the valid serial numbers. For each invalid serial number, the script extrapolates the latest 32 bytes (the wrapped valid serial) and looks for the relative transaction id (makes use of auxiliary methods like these).
Results of the investigation:
- Block range: 1679090–1686229
- Total number of invalid serials: 477
- Average bitsize: 1093.72
- Total number of valid “wrapped” serials: 123
- Total amount of PIV from invalid spends: 568897
- Amount of invalid 1-denom. coins: 7
- Amount of invalid 5-denom. coins: 6
- Amount of invalid 10-denom. coins: 36
- Amount of invalid 50-denom. coins: 22
- Amount of invalid 100-denom. coins: 244
- Amount of invalid 500-denom. coins: 22
- Amount of invalid 1000-denom. coins: 42
- Amount of invalid 5000-denom. coins: 98
- Total number of addresses involved: 177
The following chart shows which denomination has been minted with each block and how the amount of total created PIV grew over time
It’s easy to see how the bulk of the amount has been created in just few blocks (those containing the 5000-denomination zerocoins). More than 81% of the total PIVs come from 7 blocks:
With 44% of the total amount in just the latest two.
getuint256method now throws a
std::range_errorif the bignum has more than 256 bits (both for OpenSSL and for GMP libraries).
HasValidSignaturemethods catch the
std::range_errorthrown by the
getuint256method (and the former returns version 2 in that case).
IsValidSerialnow checks for the correct bitsize.
SerialNumberSignatureOfKnowledge::Verifynow ensures that both the serial number and the commitment to the coin are within the proper ranges.
In #PR-837 the
zerocoin_wrapped_serial_spend_test case has been added to the
zerocoin_coinspend_tests suite to check that a coinSpend verification fails when the serial number is outside the max range.
In #PR-838 a new
zerocoin_wrapped_serials.py test has been added to the the functional testing suite to cover the whole attack on regtest.
It uses a new RPC call
spendrawzerocoin , introduced in the same pull-request, to spend zerocoins providing denomination, serial, randomness, and private-key values.
The test correctly passes after the addition of #PR-837 due the coinSpend validation failing on a serial number out of range.
Projects affected by the current vulnerability have been promptly contacted and advised to freeze their zerocoin functionality until the details of the attack were disclosed and a fix to the issue was made available.
The following projects have responded and successfully activated their sporks:
Hopefully this article provides enough insight for the remaining ones that have not responded or that we didn’t reach to rapidly update their sources using the available fix.
— random.zebra and furszy