Report: “Wrapped Serials” Attack

9 min readMar 15, 2019

- 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).

Discovery

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:

The getuint256() method of the BigNum class 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.

Problem

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:

eq.1

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
    72ae264e793226cac0e59480a0d9037729a47201c7e67d82894bbc986b1b4783
    41649e3d59372cec09f9e2f5dd0815e9d4e93fd4918fe1dd2ec4ee9375ac0be4
    38f82f715c6f5f1d673785d79c962c6097f7961d37c2508d2b933024723ba241q = a33a39fceb03fef51aa5f50322b557664a8364d7ad0ada150487fae8576af9e3-----g = 9a7fd6508dfa79258e50019ab6cb59b4f91b2823dcd9250fb3ccf9fd8263b29a
    15b005c429915cec63e7d3eba1da337f45dd713246c41e39ac671cf2f87adfc6
    d45c842ae7ad21ed291e3a48b2a6e5d39381f6d4a9ab83d5aaa5031d17554df7
    0cf5ecfe10096cf1a565d0f826b71eb4d105a3016afc445613f04ffbd0dd4162h = ccbbdd469de23cfba19728b625ee7b197b60389eebb7383ec63184fe6ddc94ac
    f0e6e68eb49523acff5e4d0c6fd20b744df744c1a7b554140d110e6398040425
    790fe3b9b32e87238f0338c4f52e3f9b84bef7bceace17f26ada12fa5e1ca0d9
    92b79599f0ef29b66c323b88c1471d9367f991604a97414f99f748ead3d38622

or, in decimal representation:

p =   161472451372577012801537365723922556211848315807594124571141764504999544408362125454072210505394654546158172195415400420843049128478444392858426591864457908932595588930280642318371343109552712010176780306349674252280901839211018654763617444978825645960598892468748168577682155499188091216022125857543517086273q =   73829871667027927151400291810255409637272593023945445234219354687881008052707------g =   108493142922526728666632567817665003170796919105635379209392198423511598366861400891077767613510689994661458247627782967131380742158803028619370850599707720731033316825396014640162292085141754403426615747531818926542832854769301325069842551396491200417945280389398187668412942712019408916579750269745817796962h =   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:

eq.2

eq.3

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 :

eq.4

Examples

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:

https://explorer.pivx.link/tx/2537e84a54e4bf8dae16f8ca6baf7137a85e4257c97e6987eb56db14ef4ea3b8

It has 1280 bits:

S2= fb806ed72efed122036a37cfc6c08eea813f595cec5e9413b22e509c0adaf9cf
    4d6e79e5d48eda6dc2fb1a6cafed5bca558bdcb1f2a41946c62ad646b525d637
    8f860d13199459222ae9503ce9c0d7f7c0df1dd07f355f09eb2764f148b42d01
    9e4f73e3fd19d00828e4ba63d3444089a636cc2ff4fc881a67a8fca7dcf13976
    f80892e78c30a393ef4ab4d5a9d5a2989de6ebc7b976b241948c7f489ad716a2

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:

https://explorer.pivx.link/tx/caf7ee443214b4fb3162cd753b1faa35fce7c42c7520b825246d6968d0ddff34

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:

https://explorer.pivx.link/tx/f5d00f3f06765a106e676159f2c1ec34ec1247262cb78caf7cc1c2626cd82b42

Here there is a 512-bits serial:

Hex(S2) =     a33a39fceb03fef51aa5f50322b557664a8364d7ad0ada150487fae8576af9e3
f4fd4d7248e6a51f1d854ddd2a4965996154acc6b8de5aa6c83d4775b283b600S2 = 8548915088448100358830025159294609927638754396015919844019766466875902660870255092292366521175660752441608968674693395141285263301578379760229038424307200

embedding the valid serial, S:

Hex(S) = f4fd4d7248e6a51f1d854ddd2a4965996154acc6b8de5aa6c83d4775b283b600S = 110811881877285919779333627674890084097834865631989961861384957298979004200448

which was already spent on block 1681503 in the transaction:

https://explorer.pivx.link/tx/12baceaca92e937cee2015e075c8fa9710f3f14010fc57b85d602bbd9a179376

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

resulting in

s2= a33a39fceb03fef51aa5f50322b557664a8364d7ad0ada150487fae8576af9e3
    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.

Blockchain Analysis

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:

Denomination
Bitsize
Receiver Address
Transaction ID
Blocktime
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:

1681581 (45K)
1681588 (50K)
1681599 (45K)
1681675 (50K)
1681676 (25K)
1682156 (100K)
1682169 (150K)

With 44% of the total amount in just the latest two.

Implemented Fix

getuint256 method now throws a std::range_error if the bignum has more than 256 bits (both for OpenSSL and for GMP libraries).
ExtractVersionFromSerial and HasValidSignature methods catch the std::range_error thrown by the getuint256 method (and the former returns version 2 in that case).
IsValidSerialnow checks for the correct bitsize.
SerialNumberSignatureOfKnowledge::Verify now ensures that both the serial number and the commitment to the coin are within the proper ranges.

Unit Testing:

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.

Functional Testing:

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.

Disclosure

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:

As PIVX currently has more than 700 forks, it wasn’t viable to verify if all of them were vulnerable to the attack. A public warning has been issued on twitter and on the PIVX discord server.

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