Quarkslab team performed a cryptographic & security assessment of the Bulletproof protocol, a new non-interactive zero-knowledge proof protocol, to be used by the Monero open-source cryptocurrency (XMR). We found several issues, some possibly critical, during the analysis.
Introduction
In January 2018, Monero Research Lab, through the Open Source Technology Improvement Fund, asked Quarkslab for a statement of work detailing the steps of a security evaluation. The main target, in the Monero open-source cryptocurrency (XMR), was their implementation of a new cryptographic proof: Bulletproof.
Their motivation to move from Borromean range proofs to bulletproofs is the size of the proof, as it would significantly reduce the transactions size, thus bring down transaction fees on the platform by an estimated 70-80%.
This audit was sponsored by Monero Research Lab, The Monero Community, Private Internet Access, and OSTIF. Three senior engineers reviewed Monero’s implementation of Bulletproof, a new non-interactive zero-knowledge proof protocol. The general idea behind those schemes is to be able to cryptographically verify that something is true without revealing anything else (e.g. a number is in a given range, without disclosing information about its value itself). It is used in Monero to prove that amounts lie in a given positive interval, which is crucial in validating a transaction and make sure nobody create fraudulent coins out of thin air.
The full text of the report is made available on this blogpost [1].
Scope
The scope of the analysis of the bulletproof prove/verify algorithms was provided by the Monero Research Lab. The goal was to answer as many of the following questions as possible:
Does their code accurately represent the Bulletproof prove/verify algorithms?
Does their implementation allow an attacker to generate a false proof that an honest verifier judges as correct?
Does their implementation allow an attacker to examine an honest prover’s proof and gain information about the hidden amount or other masks?
The evaluation work that Quarkslab planned included the three following steps:
Understanding the protocols and isolating the main points of attention regarding implementation. It is important to note that the bulletproofs research results are recent, and at the time of the request, they were to be published at IEEE S&P 2018 [BBBPWM18], with only the research paper preprint available.
Assessing the conformity of the C++ code (ringct amounted to around 3500 lines) to the specifications (and the reference source code in Java) both from a logical and an implementation standpoint, including the underlying elliptic curve arithmetic used.
Looking for vulnerabilities and assessing their severity.
Results
During our security assessment of the Bulletproof implementation, we found several vulnerabilities.
Proofs functions
Four major vulnerabilities can be triggered by untrusted inputs to the proof verification function. Besides allowing to produce wrong output values, they could be the first steps towards making a verifier accept a false proof:
An arithmetic overflow in the double scalar multiplication function which is used either to compute a proof or to verify a proof with inputs under direct control of the prover.
Two algorithmic mistakes each in one version of the multi-exponentiation [Gordon98] function (Bos-Coster [BoCo89] and Pippenger [Pipp80]) which is used in the proof verification, allowing either to output erroneously the identity point or to silently discard an element in the computation. Inputs to these functions are directly deduced from attacker inputs although not in a straightforward manner.
A lack of proper security checks on the inputs of the main proof verification function although these inputs are all controlled by a potential attacker. This lack of checks makes the three former vulnerabilities all the more critical as they are directly exposed to malformed inputs (non-reduced scalars, points either not on the curve or not in the main subgroup of the curve).
Data deserialization
Three medium vulnerabilities in deserialization procedures (including an improper size validation) were also found. Because deserialization occurs on untrusted inputs, under control of an attacker, the bugs can lead at least to exceptions and potential denials of service.
Implementation of cryptographic specifications
Two bugs that correspond to extremely improbable events triggered by internal computations of some cryptographic functions have also been reported. Although these events are highly unlikely to happen by chance, nobody can foretell all the future applications and contexts of use of these pieces of code and that these values cannot be manipulated more precisely than by chance in some use cases. Adding relevant checks to implement the intended semantics and to reach a greater code robustness is definitely advised.
Values hashing to zero to produce challenges in the protocol: zero value challenges ruin the security of the protocol, furthermore, they cannot be inverted as it is needed for some of them by the protocol.
A null random value given as input to the Schnorr signature leads to a private key compromise. If the hash value is null, then the signature does not depend on the private key.
Consequences
In the time frame of the assessment, none of the vulnerabilities found has led to a practical exploit allowing to either produce a false proof accepted by a verifier or to reveal information on a proof. However, it does not mean it is impossible, especially when considering all the vulnerabilities in the verification directly linked to inputs controlled by an attacker. We preferred to focus on a search for weaknesses as wide as possible, rather than on how to exploit the discovered flaws.
Our evaluation work also produced a list of weaknesses, i.e. characteristics of the target implementation that could turn into vulnerabilities during code evolution. We also proposed several improvements to reach a simpler and more robust code.
Conclusion
Monero is well known for being at the forefront of cryptographic innovations in crypto-currencies, incorporating the latest cutting-edge improvements. It made the review particularly challenging and interesting and we hope we helped improve the project’s overall security.
During the evaluation, we were in contact with Sarang Noether of Monero Research Lab who helped us get the relevant inputs for the assessment and ensured the link with the development team. They took into account our findings very quickly, with fixes to address some of the suggestions in the report. Some more delay was needed to fix the DoS issue present outside of the Bulletproof code.
We would like to thank him and, of course, Derek Zimmer from OSTIF (and their sponsors) for having made the study possible.
Timeline
2018-01-18: initial request for a statement of work to assess the security of the bulletproof implementation in Monero
2018-03-08: the three assessment projects are fully funded
2018-04-18: start of the audit by the Quarkslab team
2018-07-17: end of the audit by the Quarkslab team
2018-07-24: bugs reported to Monero Research Lab
2018-07-27: agreement to wait until the development team can confirm the plan for patching some of the issues
2018-08-16: delay due to a vulnerability impact bigger than expected
2018-09-09: decision to postpone the report publication until the next regular release patching the DoS vulnerability
2018-10-18: Monero 0.13.0 "Beryllium Bullet" Release
2018-10-22: report publication by Monero Research Lab, OSTIF and Quarkslab
| [BBBPWM18] | Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille and Greg Maxwell. "Bulletproofs: Short Proofs for Confidential Transactions and More," 2018 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, US, pp. 319-338. doi:10.1109/SP.2018.00020 |
| [Gordon98] | Daniel M. Gordon. A survey of fast exponentiation methods. Journal of Algorithms 27 (1998), 129–146. |
| [BoCo89] | Jurjen Bos and Matthijs Coster. Addition chain heuristics. In Advances in Cryptology – Proceedings of Crypto’89, volume 435, pages 400–407. Springer-Verlag, 1990. |
| [Pipp80] | Nicholas Pippenger. On the evaluation of powers and monomials. SIAM Journal on Computing 9 (1980), 230–250. |
| [1] | Full report of the assessment |