Security Audit of Particl Bulletproof and MLSAG

Introduction

In May 2019, Particl asked Quarkslab for a security assessment of these two protocols. The goal of this audit was to verify that both of them were correctly implemented, and that no vulnerability weakens or allows for the bypass of either one.

The zero knowledge proof protocol Bulletproofs allows to verify that an assessment is true without leaking any of the values involved. In the case of cryptocurrency transactions, the goal is to verify that a sum of inputs (amounts being spent) is greater or equal to a sum of outputs (costs and fees).

The ring signature protocol MLSAG allows a member of a ring of participants to produce a signature that can be verified while his identity remains hidden among the other participants. In other words, a verifier can verify that the secret key of one of the ring participants was used to compute the said signature, but cannot determine which one. The goal is to ensure a certain degree of anonymity for the signing participant, while providing to the verifier a proof that the transaction is legitimate.

Scope

The scope of the analysis of the bulletproof prove/verify algorithms and the MLSAG sign/verify algorithms were provided by Particl. The goal was to answer the following questions.

1. Are those implementations conform to the Bulletproof and MLSAG algorithms?

2. Regarding Bulletproof:

• Could an attacker be able to generate a false proof that an honest verifier judges as correct?

• Could an attacker be able to examine an honest prover’s proof and gain information about the hidden amounts or other masked values?

3. Regarding MLSAG:

• Could an attacker be able to generate a false signature that an honest verifier judges as correct?

• Could an attacker be able to examine an honest prover's ring signature and gain information as to which of the ring secret key was used?

The evaluation work that Quarkslab planned included the three following steps:

• Understanding the protocols and isolating the main points of attention regarding these implementations. It is important to note that in 2018, Quarkslab performed a security assessment of the implementation of Bulletproof in Monero [1]. That previous work helped with the assessment of Particl's Bulletproofs implementation.

• Assessing the conformity of the C code, both from a logical and an implementation standpoint. The low level arithmetic primitives used were not part of this assessment scope.

• Looking for vulnerabilities and assessing their severity.

Results

During this assessment, both Bulletproofs and MLSAG implementations were reviewed. The full text of the report contains an in-depth analysis of both protocols and their implementations. Both were found conform to their respective reference papers [BBBPWM18] [SN15] and no vulnerability that could weaken the security of the protocols was found.

Conclusion

In the time frame of the assessment, a detailed overview of both Bulletproofs and MLSAG implementations were conducted. Those implementations were found conform to their respective algorithms and no vulnerabilities were found.

We would like to thank Particl for making this assessment possible. Implementations of protocols like Bulletproof and MLSAG are very interesting from a security standpoint and that work was challenging for our team.

In particular, we would like to thank Henk Shwardt and Ryno Mathee for keeping a line of communication between our team and theirs.