6.1 Lack of uniqueness check of party ID's when computing lagrange coefficients
In combine_commitments(...) it is required to compute the lagrange coefficients for the provided contributing parties. However, there is no check that the contributing parties are unique. This means it is possible to use duplicate party IDs and commitments. Maliciously this can be used to inflate the number of shares and produce an incorrect secret from the secret sharing.
Recommendation
Before computing the lagrange coefficients for the contributing parties, check that:
set(contributing_parties).len() == contributing_parties.len();
This will ensure only unique party IDs are being used in the commitment combination.
6.2 Non-constant time implementation of field arithmetic leading to timing attack vulnerability
The underlying field arithmetic used for the following functions uses branching conditions that branch based on the secret values used. Here we provide a list of key functions we believe are vulnerable to such attacks and why:
shamir.rs/dh_key_derivation(...) performs multiplication of a scalarfield element and an affine element performing group multiplication for affine coordinates using the double-and-add method;oprf.rs/unblind_response(...) is used to unblind the server response using the prepared blinding factor performed with the double-and-add method;dlog_equality.rs/partial_commitments(...) performs multiplication over the secret share x_share using the double-and-add method;shamir.rs/single_lagrange_from_coeff(...) and shamir.rs/evaluate_poly(...) performs field multiplication for a prime field, the ScalarField nor BaseField types do not implement constant-time multiplication;
Recommendation
Implement constant time field arithmetic.
Resolution
Most low-level field arithmetic operations in ark-ff are constant time, with a few exceptions like the subtraction that does a branching on potential overflows. We accept this for now and will re-evaluate in the future if we want to address this further by changing out the underlying field arithmetic completely.
6.3 EdDSA vulnerable to timing attacks
Timing attacks are side channel attacks that enable attackers to infer values of secret keys by noticing changes in the time it takes to perform cryptographic operations. As stated by RFC 8032, such attacks stem from the secret key influencing the set of instructions and memory accesses executed by the code. It was found that the implementation of EdDSA is vulnerable to such attacks after running dudect to measure the signature generation speed against a fixed key and a random key. Specifically, the code run was with 1 million samples:
/// Differential time analysis of signing, fixed key & msg vs. fixed msg & random key
fn eddsa_sign_ct_vary_sk(runner: &mut CtRunner, rng: &mut BenchRng) {
let msg = BaseField::from(0u64);
let mut sk_rng = rand::thread_rng();
let mut keys = Vec::with_capacity(N_SAMPLES);
let mut classes = Vec::with_capacity(N_SAMPLES);
for _ in 0..N_SAMPLES {
if rng.next_u32() & 1 == 0 {
// Left: fixed key
keys.push(EdDSAPrivateKey::from_bytes([0x13; 32]));
classes.push(Class::Left);
} else {
// Right: random key
keys.push(EdDSAPrivateKey::random(&mut sk_rng));
classes.push(Class::Right);
}
}
for (class, sk) in classes.into_iter().zip(keys.into_iter()) {
runner.run_one(class, || {
let sig = sk.sign(msg);
core::hint::black_box(sig);
});
}
}
It was found that this issue stems from the branching condition found in the scalar multiplication in ark-ec/src/twisted_edwards/mod.rs which implements affine multiplication using the double-and-add method:
/// Default implementation of group multiplication for affine coordinates
fn mul_affine(base: &Affine<Self>, scalar: &[u64]) -> Projective<Self> {
let mut res = Projective::<Self>::zero();
for b in ark_ff::BitIteratorBE::without_leading_zeros(scalar) {
res.double_in_place();
if b {
res += base
}
}
res
}
The attack is possible here as an attacker can measure how many times a value is added and how many times it is multiplied. This is because the time to compute a multiplication and the time to complete an addition is different, allowing the attacker to infer information about the key.
Recommendation
We recommend using a constant time implementation of the fields to prevent this attack. However, as far as we understand, there does not exist a constant time implementation of the BabyJubJub curve enabling the usage of constant time curve operations. Arkworks does not implement constant time field operations. Thus, the suggestion is to reimplement a rust crate like Sylow, which uses constant time field operations for BN254, for BJJ.
For Arkworks, a solution could be to implement constant time scalar multiplication to bypass this through the Montgomery ladder method. Various solutions are provided in the paper Elliptic Curves and Side-Channel Analysis.
6.4 their_pk is not validated during share generation
gen_share public function accepts their_pk as an argument, but it does not validate it being on-curve.
There is no code calling this function in the audit scope (outside of local tests). There is a validation performed if their_pk is obtained specifically via checked versions of deserialize_* methods of CanonicalDeserialize trait.
If obtained by other means though, there's no safeguard against their_pk being off-curve, thus making private key vulnerable to invalid curve attack.
Recommendation
We recommend checking their_pk being on curve and in the correct subgroup inside the gen_share function itself.
6.5 Debug Assertions in Poseidon2 permutation
The Poseidon2 permutation file contains some debug assertions. These are not part of the release build and will enable users to instantiate Poseidon2 internal matrices with different parameters than the recommended.
/// The matrix multiplication in the internal rounds of the Poseidon2 permutation.
pub fn matmul_internal(&self, input: &mut [F; T]) {
match T {
2 => {
// Matrix [[2, 1], [1, 3]]
debug_assert_eq!(self.mat_internal_diag_m_1[0], F::one());
debug_assert_eq!(self.mat_internal_diag_m_1[1], F::from(2u64));
let sum = input[0] + input[1];
input[0] += ∑
input[1].double_in_place();
input[1] += sum;
}
3 => {
// Matrix [[2, 1, 1], [1, 2, 1], [1, 1, 3]]
debug_assert_eq!(self.mat_internal_diag_m_1[0], F::one());
debug_assert_eq!(self.mat_internal_diag_m_1[1], F::one());
debug_assert_eq!(self.mat_internal_diag_m_1[2], F::from(2u64));
[...]
Resolution
They acknowledged they are aware of the issue. But it is a minor one, as the library is intended for internal use. Additionally, they would like to explore verification at compile time to avoid incurring additional runtime costs for the assertions. The issue is presented in an informational manner to help keep track of the problem.
6.6 G1/G2 point deserialization accepts point at infinity
serde deserialization of G1 points via intended #[serde(deserialize_with = "ark_serde_compat::CURVE::deserialize_g1")] boils down to G1Visitor called with const CHECK == true. This CHECK enforces the deserialized point to be on curve and in the subgroup of the correct order, otherwise deserialization will error out. However, it does explicitly allow point at infinity (a.k.a zero point).
Using a point at infinity in certain context may lead to the soundness property of a proof system being broken.
All of the above applies to G2 points as well.
This deserialization routine is used e.g. in VerificationKey of circom_types::plonk and circom_types::groth16, where no additional validation is being done.
Recommendation
Care should be taken when using this deserialization, with additional validation performed accordingly on deserialized entities where this might impact security guarantees.
Resolution
They say that the validation is done on the contract side, so PaI won't reach the deserialization.
6.7 Some assertions can be made constant
The Poseidon2 permutation file contains some assertions that can be updated to be done at compile time.
/// Creates a new instance of the Poseidon2 permutation with given parameters
pub const fn new(
mat_internal_diag_m_1: [F; T],
round_constants_external: [[F; T]; ROUNDS_F],
round_constants_internal: [F; ROUNDS_P],
) -> Self {
assert!(T == 2 || T == 3 || ((T <= 24) && (T % 4 == 0)));
assert!(D % 2 == 1);
assert!(ROUNDS_F % 2 == 0);
Self {
mat_internal_diag_m_1,
round_constants_external,
round_constants_internal,
}
}
These assertions only involved information known at compile time. They can be defined within a const block (stabilized since Rust 1.79)
pub const fn new(
mat_internal_diag_m_1: [F; T],
round_constants_external: [[F; T]; ROUNDS_F],
round_constants_internal: [F; ROUNDS_P],
) -> Self {
const {
assert!(T == 2 || T == 3 || ((T <= 24) && (T % 4 == 0)));
assert!(D % 2 == 1);
assert!(ROUNDS_F % 2 == 0);
}
// [...]
}
Alternatively, use static_assertions.
This ensures the checks are done at compile time instead of runtime:
- Avoiding wrong configurations for Poseidon2;
- Transforms a potential panic into a compilation error;
6.8 combine_proofs asks for contributing_parties
One argument to DLogEqualityCommitments::combine_proofs and DLogCommitmentsShamir::combine_proofs methods is contributing_parties listing parties that contributed to proof generation. However, DLogEqualityCommitments (and by extension, its wrapper DLogCommitmentsShamir) already contains contributing_parties vector.
Having contributing_parties argument is unnecessary and introduces risk of misusing it.
Recommendation
We recommend removing contributing_parties argument from combine_proofs and pass in.
6.9 Nonce can be reused during share generation
gen_share public function accepts nonce as an argument. While there's no code calling this function in the audit scope (outside of local tests), it opens the opportunity for it to be misused by passing the same nonce multiple times. If allowed, it might make party's secret key vulnerable.
Recommendation
We recommend passing in the secure RNG and generating nonce in the gen_share function itself.
