CVE-2019-7167

[zebambam]

Hey. I think you should look at this to see if you're vulnerable. I've raised a ticket with github to let you know through their notification system. The CVE details were submitted this morning but haven't been changed at the mitre end yet.

Title

BCTV14 setup produces elements that violate soundness leading to Counterfeiting Vulnerability in Zcash and others

Description

The construction described by [BCTV14] in Appendix B, is a variant of the [PGHR13] zk-SNARK scheme with modifications to improve performance. This scheme was used in the original 2016 launch of Zcash and has been independently implemented by several other projects.

Ariel Gabizon, while working for the Zcash company, discovered a soundness bug in [BCTV14] that is described in this security notice:

The key generation procedure of [BCTV14], in step 3, produces various elements that are the result of evaluating polynomials related to the statement being proven. Some of these elements are unused by the prover and were included by mistake; but their presence allows a cheating prover to circumvent a consistency check, and thereby transform the proof of one statement into a valid-looking proof of a different statement. This breaks the soundness of the proof system. We refer to these elements as “bypass elements.”

The [BGG17] multi-party computation (MPC) protocol that produces parameters for the [BCTV14] construction follows the setup procedure closely, and so the bypass elements are produced. They are not included in the actual proving key distributed to Zcash nodes since they are explicitly excluded from the parameter file format used by the proving routine implementation of [BCTV14] in the “libsnark” library (used by Sprout). However, these elements do appear in the MPC ceremony transcript. Consequently, anyone with access to the ceremony transcript would have been able to create false proofs.

The vulnerability also affects an older MPC scheme [BCGTV15]. This vulnerability was also included in some independent implementations of [BCTV14], such as [snarkjs], even though they do not require an MPC. Similar flaws can be found in the [BBFR14] and [Fuchsbauer17] zk-SNARK schemes, which are adaptations of [BCTV14].

Impact

The ability to break soundness in the proving system permits the creation of false proofs. Zero-knowledge proofs are used in a system like Zcash to ensure that transactions are valid, so this bug this implies the ability to create an unlimited amount of shielded coins where the verifier is affected by this bug.

Credit

This vulnerability was discovered by Ariel Gabizon while he was working for the Zerocoin Electric Coin Company.

What is affected?

Any project that implements [BCTV14] and does not completely dispose of the bypass elements as part of the setup process.

That includes but is not limited to any project that depends on the trusted setup used by the original Sprout system that was distributed in the initial 2016 launch of Zcash. This original Sprout system for shielded funds is comprised of the original Sprout circuit, the [BCTV14] proving system using libsnark, and the parameters generated by an MPC ceremony [BGG17]. It was used by the 1.x series of Zcash software (which also carried the “Sprout” name).

[BCTV14] is available at https://eprint.iacr.org/2013/879

The original Sprout circuit implementation is here: https://github.com/zcash/zcash/tree/32d3a3352e45457f689585cc49d554599583bbd0/src/zcash/circuit

The original Sprout zk-SNARK parameters are here: https://z.cash/downloads/sprout-proving.key (sha256sum: 8bc20a7f013b2b58970cddd2e7ea028975c88ae7ceb9259a5344a16bc2c0eef7) and https://z.cash/downloads/sprout-verifying.key (sha256sum: 4bd498dae0aacfd8e98dc306338d017d9c08dd0918ead18172bd0aec2fc5df82)

The Sprout proving and verifying routines are here: https://github.com/zcash/zcash/blob/685c0ab07fd90b244dac5e2cb1f069ac6151ec5c/src/zcash/JoinSplit.cpp

The BCTV14 proving system implementation (in libsnark) is here: https://github.com/zcash/zcash/tree/c938fb1f179d9bdefc5bc7e55fc6330a8b8d3713/src/snark/libsnark/zk_proof_systems/ppzksnark/r1cs_ppzksnark

What is not affected?

The newer Sprout-on-Groth16 system used by Zcash mainnet for Sprout addresses ever since the Sapling activation (block 419200 at 28 Oct 2018) is not affected by the counterfeiting vulnerability. It uses a new Sprout circuit, that runs on the Groth16 proving system, with new parameters, and operates on the BLS12-381 curve implemented in the Bellman library. The newer Sapling system for shielded funds, activated at the same time and using a new address format, is not vulnerable either.

The vulnerability is not present in the algorithms of [PGHR13] (which underlies [BCTV14]), nor in [BCGTV13], which used similar techniques. It is also not present in other zk-SNARKs constructions, such as [GM17] or [BG18], or in zero-knowledge proof systems that do not rely on a structured reference string. It is not present in libsnark when used with its built-in parameter generator.

The new Sprout-on-Groth16 circuit implementation is located here at time of publishing this information: https://github.com/zcash-hackworks/sapling-crypto/tree/master/src/circuit

The new Sprout-on-Groth16 zk-SNARK parameters are located here at time of publishing this information: https://z.cash/downloads/sprout-groth16.params

The new Sprout-on-Groth16 proving and verifying routines are located in the librustzcash library (at time of publishing): https://github.com/zcash/librustzcash

The Groth16 proving system is implemented in the Bellman Rust library: https://github.com/zkcrypto/bellman

Mitigation

Users of projects still affected by this issue should change the zk-SNARK parameters to some that are not affected by this bug. Zcash switched to new parameters using a new “Sprout-on-Groth16” proving system as of the Sapling network upgrade on October 28th 2018, and so is not affected by the bug.

Therefore, users of Zcash do not need to take any action.

Projects still affected by this vulnerability that do not wish to switch proving systems might instead wish to perform their own parameter setup to produce replacement parameters. Projects following this path are strongly encouraged to use a large, public MPC with thorough security analysis. In the interim, they are advised to disable functionality (e.g., shielded transactions) that relies on the affected proof system.

References

[BCTV14] https://eprint.iacr.org/2013/879

[PGHR13] https://eprint.iacr.org/2013/279

[BGG17] https://eprint.iacr.org/2017/602

[Parno15] https://eprint.iacr.org/2015/437

[BCGTV15] https://www.ieee-security.org/TC/SP2015/papers-archived/6949a287.pdf

[snarkjs] https://github.com/iden3/snarkjs

Papers inheriting this issue from [BCTV14]:

[BBFR14] https://eprint.iacr.org/2014/617

[Fuchsbauer17] https://eprint.iacr.org/2017/587

[zebambam]

Is anyone able to take a look at this issue?

[kennethmyhra]

This has been taken care of https://medium.com/@skellers/zclassic-upgrade-notice-faad6998ed39 and the active repository is now located here: https://github.com/ZclassicCommunity/zclassic