interbiznw
commented
5 years ago Thank you @zebambam we are aware since the release of this info and are working on a solution.
Open zebambam opened 5 years ago
interbiznw
commented
5 years ago Thank you @zebambam we are aware since the release of this info and are working on a solution.
zebambam
commented
5 years ago Hey, any update on this?
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