Secret sharing crate allows zero shares on reconstruction

[MarcIlunga]

The secret sharing crate does not check that indices associated with shares are not zero during the reconstruction of the secret. While the crate prevents using 0 as an index during share creation, it doesn't enforce the same constraints during reconstruction. A malicious party that can freely define the index of its share during reconstruction controls and knows the reconstructed value.

Shamir's secret sharing does not aim to provide integrity or verifiability. Nevertheless, it is desirable to prevent zero indices during reconstruction to provide additional guarantees to the crate's users.

The Juicebox implementation is not affected at all since it ensures that all shares have non-zero indices through higher-level mechanisms. Furthermore, even after a successful attack due to a misuse of the crate, the wrongly recovered secret is still statistically independent of the original secret. However, the crate is meant to be used independently, and users may not be aware of this issue and fail to perform the required validation.

The POC below demonstrates a misuse of the secret sharing crate that can lead to a security vulnerability. Consider a protocol for distributed storage and recovery of secrets. In this protocol, the user shares their encryption key with multiple servers using the secret sharing scheme only. Assuming the user performs encryption for the first time after recovering a secret key, a malicious server could provide a share with an index 0. If the user does not perform an additional check of the indices, the secret key used for encryption is known to the malicious server.

use curve25519_dalek::scalar::Scalar;
use juicebox_secret_sharing::{create_shares, recover_secret, Index, Share};
use rand_core::OsRng;

// This POC demonstrates a potential misuse of the secret sharing scheme that can lead to a security vulnerability.
// While the crate prevents using 0 as an index during share creation, it doesn't validate the integrity of shares during reconstruction.
// Share validation is left to the caller.
// There isn't a clear use case for share creation and reconstruction having different domains of indices.
// An attacker can manipulate the recovered secret by injecting a malicious share,
// potentially compromising the security of any system relying on this recovered secret.
// Reference: See https://www.zkdocs.com/docs/zkdocs/protocol-primitives/shamir/#the-zero-share-problem for more discussion on zero-share issues.

fn main() {
    let rng = &mut OsRng;
    // Generate a random secret
    let secret = Scalar::random(rng);
    // Create 5 shares with a threshold of 3
    let mut shares: Vec<_> = create_shares(&secret, 3, 5, rng).collect();

    let recovered_secret = recover_secret(shares);

    // Create a malicious share with index 0 (which wasn't used in the original share creation)
    let new_share = Share {
        index: Index(0),
        secret: Scalar::random(rng), // Random value chosen by the attacker
    };

    // Replace the first share with the malicious one
    shares[0] = new_share.clone();
    // Attempt to recover the secret using the manipulated set of shares
    let recovered_secret = recover_secret(&shares as &[Share<Scalar>]).unwrap();
    // Verify that the recovered secret matches the attacker's chosen value
    assert_eq!(recovered_secret, new_share.secret);
    // Confirm that the recovered secret is likely different from the original
    assert_ne!(recovered_secret, secret);
}

The lack of index validation during reconstruction increases the risk of misuse. Furthermore, there isn't a clear use case for creating and reconstructing shares with different domains of indices.