Security Audit of dalek libraries

Introduction

In June 2019, the Tari Labs asked Quarkslab for a security assessment of some of the dalek libraries [1]. The goal of the audit was also to provide advices about the usage of these libraries in the context of the Tari protocol, a decentralized assets protocol built on top of Monero. This Rust project uses several libraries, among which the dalek libraries, and especially:

• subtle: traits and utilities for constant-time cryptographic implementations.

• curve25519-dalek: implementation of group operations of Ristretto and on Curve25519.

• bulletproofs: implementation of Bulletproofs using Ristretto.

Quarkslab also took a quick look at two other projects built on top of curve25519-dalek: x25519-dalek and ed25519-dalek. The evaluation was spread over about four weeks for a total of 30 days with two engineers.

The subtle library contains several constant time arithmetical primitives, i.e., primitives for which computation time may depend on the types, but never on the actual values or data being used. The library documentation explains that

It represents a best-effort attempt to protect against some software side channels. Because side-channel resistance is not a property of software alone, but of software together with hardware, any such effort is fundamentally limited.

The curve25519-dalek library offers group operations on the Curve25519 [3]. But the library also provides group operations on Ristretto, see [4] and [5], which is a prime-order group whose group elements are represented through points on the Curve25519 using the Edwards form.

Bulletproofs refers to a non-interactive zero-knowledge (NIZK) proof protocol [6]. A bulletproof is mainly used to allow a Prover to convince a Verifier that a given secret value lies within a given range. In addition to an individual proof for each committed value, the protocol is also designed to deal with aggregated rangeproofs, which are smaller than individual proofs concatenated, and multi-party computation (MPC), which aggregates proofs of multiple parties.

Scope

The scope of the analysis was different depending on the libraries.

For the subtle library, the audit verified that the source code and the assembly generated by Rust (version nightly-2019-06-11) do not have any trivial time leak. The audit does not validate that the library is immune to time leaks on a specific piece of hardware or outside the scope of the library.

Concerning the curve25519-dalek library, we have mainly audited the modules referring to Edwards. Ristretto and Scalar, as well as the u64 and avx2 back-ends.

The MPC feature of Bulletproofs is one of the main interests in the context of the Tari Labs. We then reviewed it and particularly focused on the MPC protocol in which the parties are not an an honest-but-curious adversary, since most of the MPC protocol are secure in a passive corruption security or semi-honest security model, which cannot be assumed in the context of the Tari protocol.

Results

We highlight here three issues we have found. More details are provided in the full report [2].

• Overflow in Scalar52 when importing a Scalar with the from_bits method.

• A malicious party can send a crafted serialized message to the dealer that forces the dealer to crash.

• Issue #151 of rmp-serde allows an attacker to allocate more than 2 GB of memory with a short serial. In a memory-constrained environment, this may slow down the system and lead to a crash of the application.

Conclusion

This report summarizes the audit on the subtle, curve25519-dalek and bulletproofs libraries, as well as a more marginal audit of the x25519-dalek and ed25519-dalek libraries. The choice of Rust as a language probably avoided most common problems that may have been found in an implementation with a language such as C. The different projects as well as their code are thoroughly documented. This allows any interested party to validate the implementation choices. We provided some remarks and recommendations, mostly about the usage of the libraries in various contexts. No critical vulnerability was found. It is important to note that some tests are non-deterministic (using randomness seeded at runtime) and may reduce their reproducibility. However this also makes possible to cover a larger variety of inputs across time. We at least recommend to output the seed used during a failed test to enable easier debugging.

These libraries include some mitigations against side-channel attacks, such as constant time operations with linear code and constant memory access. These mitigations are only provided on a best-effort basis and are limited by their scope: hardware issues or updates on the nightly version of the Rust compiler may compromise them (such as unintended new optimizations or features that lead to a code no longer being constant time after compilation). However, the libraries do their best to avoid such mitigation breaks by using some features of the compiler. Nonetheless, we recommend to add additional tests to check for unexpected regressions of mitigations between unstable versions and to periodically check the desired properties on samples of the compiled assembly. We also recommend to use a stable version of the Rust compiler when the required features become stable.

The full report of the assessment can be found at the following address: [2].

We would like to thank the TARI LABS for making this assessment possible. In particular, we would like to thank Cayle Sharrock for keeping a line of communication between our team and the Tari Labs and the authors of the dalek libraries for their feedback.