nimiq-keys: Denial of service in Ed25519 multisig delinearization via invalid curve points

@@ -4,7 +4,7 @@ use nimiq_hash::Blake2bHasher;
 #[cfg(feature = "serde-derive")]
 use nimiq_utils::merkle::compute_root_from_content;
 
-use super::public_key::DelinearizedPublicKey;
+use super::{error::PartialSignatureError, public_key::DelinearizedPublicKey};
 #[cfg(feature = "serde-derive")]
 use crate::Address;
 use crate::Ed25519PublicKey;
@@ -13,14 +13,14 @@ use crate::Ed25519PublicKey;
 pub fn combine_public_keys(
     public_keys: Vec<Ed25519PublicKey>,
     num_signers: usize,
-) -> Vec<Ed25519PublicKey> {
+) -> Result<Vec<Ed25519PublicKey>, PartialSignatureError> {
     // Calculate combinations.
     let combinations = public_keys.into_iter().combinations(num_signers);
     let mut multisig_keys: Vec<Ed25519PublicKey> = combinations
         .map(|combination| DelinearizedPublicKey::sum_delinearized(&combination))
-        .collect();
+        .collect::<Result<_, _>>()?;
     multisig_keys.sort();
-    multisig_keys
+    Ok(multisig_keys)
 }
 
 /// Given a list of possible public keys, generates an address for which each of the public keys is a possible signer.

@@ -57,15 +57,19 @@ impl Commitment {
     }
 }
 
-impl From<[u8; Commitment::SIZE]> for Commitment {
-    fn from(bytes: [u8; Commitment::SIZE]) -> Self {
-        Commitment::from_bytes(bytes).unwrap()
+impl TryFrom<[u8; Commitment::SIZE]> for Commitment {
+    type Error = ();
+
+    fn try_from(bytes: [u8; Commitment::SIZE]) -> Result<Self, Self::Error> {
+        Commitment::from_bytes(bytes).ok_or(())
     }
 }
 
-impl<'a> From<&'a [u8; Commitment::SIZE]> for Commitment {
-    fn from(bytes: &'a [u8; Commitment::SIZE]) -> Self {
-        Commitment::from(*bytes)
+impl<'a> TryFrom<&'a [u8; Commitment::SIZE]> for Commitment {
+    type Error = ();
+
+    fn try_from(bytes: &'a [u8; Commitment::SIZE]) -> Result<Self, Self::Error> {
+        Commitment::try_from(*bytes)
     }
 }
 

@@ -27,4 +27,6 @@ impl std::error::Error for InvalidScalarError {
 pub enum PartialSignatureError {
     #[error("Missing nonces")]
     MissingNonces,
+    #[error("Invalid curve point in public key")]
+    InvalidCurvePoint,
 }

@@ -156,9 +156,9 @@ impl CommitmentsBuilder {
     }
 
     /// Creates the aggregate commitment and additional data for the content to be signed.
-    pub fn build(mut self, content: &[u8]) -> CommitmentsData {
+    pub fn build(mut self, content: &[u8]) -> Result<CommitmentsData, PartialSignatureError> {
         self.all_public_keys.sort();
-        let aggregate_public_key = DelinearizedPublicKey::sum_delinearized(&self.all_public_keys);
+        let aggregate_public_key = DelinearizedPublicKey::sum_delinearized(&self.all_public_keys)?;
 
         let mut partial_agg_commitments = Vec::with_capacity(MUSIG2_PARAMETER_V);
 
@@ -193,14 +193,14 @@ impl CommitmentsBuilder {
             agg_commitment_edwards += partial_agg_commitment.0 * scale;
         }
 
-        CommitmentsData {
+        Ok(CommitmentsData {
             nonces: self.nonces,
             commitments: self.all_commitments[0],
             aggregate_public_key,
             aggregate_commitment: Commitment(agg_commitment_edwards),
             all_public_keys: self.all_public_keys,
             b,
-        }
+        })
     }
 }
 
@@ -279,18 +279,22 @@ impl Ed25519PublicKey {
 
     /// Delinearizes a public key by multiplying it with a scalar derived from the hash and the public key itself.
     /// Effective delinearization for multisigs should use the hash over all public keys as an input.
-    pub(crate) fn delinearize(&self, public_keys_hash: &[u8; 64]) -> EdwardsPoint {
+    pub(crate) fn delinearize(
+        &self,
+        public_keys_hash: &[u8; 64],
+    ) -> Result<EdwardsPoint, PartialSignatureError> {
         // Compute H(C||P).
         let mut h: Sha512 = Sha512::default();
 
         h.update(&public_keys_hash[..]);
         h.update(self.as_bytes());
         let s = Scalar::from_hash::<Sha512>(h);
 
-        // Should always work, since we come from a valid public key.
-        let p = self.to_edwards_point().unwrap();
+        let p = self
+            .to_edwards_point()
+            .ok_or(PartialSignatureError::InvalidCurvePoint)?;
         // Compute H(C||P)*P.
-        s * p
+        Ok(s * p)
     }
 
     pub fn verify_partial(
@@ -303,7 +307,10 @@ impl Ed25519PublicKey {
         let public_keys_hash = hash_public_keys(&commitments_data.all_public_keys);
         // And delinearize them.
         // Note that here we delinearize as p^{H(H(pks), p)}, e.g., with an additional hash due to the function delinearize_private_key
-        let delinearized_public_key = self.delinearize(&public_keys_hash);
+        let delinearized_public_key = match self.delinearize(&public_keys_hash) {
+            Ok(p) => p,
+            Err(_) => return false,
+        };
 
         // Compute c = H(R, apk, m)
         let mut hasher = Sha512Hasher::new();

@@ -2,7 +2,10 @@ use std::{borrow::Borrow, iter::Sum};
 
 use curve25519_dalek::{edwards::EdwardsPoint, traits::Identity};
 
-use crate::{multisig::hash_public_keys, Ed25519PublicKey};
+use crate::{
+    multisig::{error::PartialSignatureError, hash_public_keys},
+    Ed25519PublicKey,
+};
 
 /// This structure holds a delinearized public key (which prevents rogue key attacks in multisigs).
 #[derive(Copy, Clone)]
@@ -11,14 +14,16 @@ pub struct DelinearizedPublicKey(EdwardsPoint);
 impl DelinearizedPublicKey {
     /// Delinearizes a public key by multiplying it with a scalar derived from the hash and the public key itself.
     /// Effective delinearization for multisigs should use the hash over all public keys as an input.
-    fn new(public_key: Ed25519PublicKey, hash: &[u8; 64]) -> Self {
-        DelinearizedPublicKey(public_key.delinearize(hash))
+    fn new(public_key: Ed25519PublicKey, hash: &[u8; 64]) -> Result<Self, PartialSignatureError> {
+        Ok(DelinearizedPublicKey(public_key.delinearize(hash)?))
     }
 
     /// Delinearizes a list of public keys and returns the list of delinearized public keys.
     /// Delinearizaion prevents rogue key attacks.
     /// Each public key is multiplied with a scalar derived from the hash over all public keys and the public key itself.
-    pub fn delinearize(public_keys: &[Ed25519PublicKey]) -> Vec<Self> {
+    pub fn delinearize(
+        public_keys: &[Ed25519PublicKey],
+    ) -> Result<Vec<Self>, PartialSignatureError> {
         let mut public_keys = public_keys.to_vec();
         public_keys.sort();
         let h = hash_public_keys(&public_keys);
@@ -30,11 +35,13 @@ impl DelinearizedPublicKey {
 
     /// Delinearizes and aggregates a list of public keys.
     /// Delinearizaion prevents rogue key attacks.
-    pub fn sum_delinearized(public_keys: &[Ed25519PublicKey]) -> Ed25519PublicKey {
-        let d: DelinearizedPublicKey = DelinearizedPublicKey::delinearize(public_keys)
+    pub fn sum_delinearized(
+        public_keys: &[Ed25519PublicKey],
+    ) -> Result<Ed25519PublicKey, PartialSignatureError> {
+        let d: DelinearizedPublicKey = DelinearizedPublicKey::delinearize(public_keys)?
             .into_iter()
             .sum();
-        d.into()
+        Ok(d.into())
     }
 }
 

@@ -5,7 +5,9 @@ use nimiq_keys::{
     multisig::{
         address::{combine_public_keys, compute_address},
         commitment::{Commitment, CommitmentPair, Nonce},
+        error::PartialSignatureError,
         partial_signature::PartialSignature,
+        public_key::DelinearizedPublicKey,
         CommitmentsBuilder,
     },
     Address, Ed25519PublicKey, KeyPair, PrivateKey,
@@ -93,6 +95,13 @@ const VECTORS: [StrTestVector; 4] = [
     },
 ];
 
+/// Bytes that are NOT a valid compressed Edwards Y coordinate on Ed25519.
+/// CompressedEdwardsY(INVALID_CURVE_POINT_BYTES).decompress() returns None.
+const INVALID_CURVE_POINT_BYTES: [u8; 32] = [
+    0xab, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x37,
+];
+
 #[test]
 fn it_can_construct_public_keys() {
     for vector in VECTORS.iter() {
@@ -165,7 +174,7 @@ fn it_can_create_signatures() {
                     builder = builder.with_signer(pks[j], commitments[j]);
                 }
             }
-            let data = builder.build(&test.message);
+            let data = builder.build(&test.message).unwrap();
             let partial_sig = key_pair.partial_sign(&data, &test.message).unwrap();
 
             assert!(
@@ -237,7 +246,8 @@ fn it_can_create_a_valid_multisignature() {
     let combined_public_keys = combine_public_keys(
         vec![keypair_a.public, keypair_b.public, keypair_c.public],
         2,
-    );
+    )
+    .unwrap();
     assert_eq!(compute_address(&combined_public_keys), wallet_address);
 
     let mut tx = "01f4e305f34ea1ccf00c0f7fcbc030d1347dc5eafe000000000000000000000000000000000000000000000000000000000000000a0000000000000000000000000500".to_string();
@@ -255,7 +265,8 @@ fn it_can_create_a_valid_multisignature() {
             commitment_pair_b_2.commitment(),
         ],
     )
-    .build(&tx_content);
+    .build(&tx_content)
+    .unwrap();
 
     assert_eq!(commitments_data_a.aggregate_public_key, signing_public_key);
     assert_eq!(
@@ -281,7 +292,8 @@ fn it_can_create_a_valid_multisignature() {
             commitment_pair_a_2.commitment(),
         ],
     )
-    .build(&tx_content);
+    .build(&tx_content)
+    .unwrap();
 
     assert_eq!(commitments_data_b.aggregate_public_key, signing_public_key);
     assert_eq!(
@@ -318,3 +330,96 @@ fn it_can_create_a_valid_multisignature() {
 
     assert_eq!(&tx, signed_transaction);
 }
+
+fn invalid_curve_point_key() -> Ed25519PublicKey {
+    Ed25519PublicKey::from(INVALID_CURVE_POINT_BYTES)
+}
+
+#[test]
+fn delinearize_rejects_invalid_curve_point() {
+    let valid_kp: KeyPair = from_hex!(
+        "f80793b4cb1e165d1a65b5cbc9e7b2efa583de01bc13dd23f7a1d78af4349904",
+        PrivateKey::SIZE,
+        PrivateKey::from
+    )
+    .into();
+    let invalid_key = invalid_curve_point_key();
+
+    let result = DelinearizedPublicKey::sum_delinearized(&[valid_kp.public, invalid_key]);
+    assert!(
+        matches!(result, Err(PartialSignatureError::InvalidCurvePoint)),
+        "expected InvalidCurvePoint error, got {result:?}"
+    );
+}
+
+#[test]
+fn build_rejects_invalid_public_key() {
+    let mut rng = test_rng(true);
+    let valid_kp: KeyPair = from_hex!(
+        "f80793b4cb1e165d1a65b5cbc9e7b2efa583de01bc13dd23f7a1d78af4349904",
+        PrivateKey::SIZE,
+        PrivateKey::from
+    )
+    .into();
+    let invalid_key = invalid_curve_point_key();
+    let pairs = CommitmentPair::generate_all(&mut rng);
+
+    let builder = CommitmentsBuilder::with_private_commitments(valid_kp.public, pairs)
+        .with_signer(invalid_key, [Commitment::default(); 2]);
+
+    let result = builder.build(b"test message");
+    assert!(
+        matches!(result, Err(PartialSignatureError::InvalidCurvePoint)),
+        "expected InvalidCurvePoint error"
+    );
+}
+
+#[test]
+fn verify_partial_with_invalid_key_returns_false() {
+    let mut rng = test_rng(true);
+    let valid_kp: KeyPair = from_hex!(
+        "f80793b4cb1e165d1a65b5cbc9e7b2efa583de01bc13dd23f7a1d78af4349904",
+        PrivateKey::SIZE,
+        PrivateKey::from
+    )
+    .into();
+    let pairs = CommitmentPair::generate_all(&mut rng);
+    let commitments = CommitmentPair::to_commitments(&pairs);
+
+    // Build valid commitments data first.
+    let data = CommitmentsBuilder::with_private_commitments(valid_kp.public, pairs)
+        .with_signer(valid_kp.public, commitments)
+        .build(b"test")
+        .unwrap();
+    let partial_sig = valid_kp.partial_sign(&data, b"test").unwrap();
+
+    // Verifying with an invalid key should return false, not panic.
+    let invalid_key = invalid_curve_point_key();
+    assert!(!invalid_key.verify_partial(&data, &partial_sig, b"test"));
+}
+
+#[test]
+fn commitment_try_from_rejects_invalid_bytes() {
+    let result = Commitment::try_from(INVALID_CURVE_POINT_BYTES);
+    assert!(
+        result.is_err(),
+        "expected error for invalid curve point bytes"
+    );
+}
+
+#[test]
+fn combine_public_keys_rejects_invalid_key() {
+    let valid_kp: KeyPair = from_hex!(
+        "f80793b4cb1e165d1a65b5cbc9e7b2efa583de01bc13dd23f7a1d78af4349904",
+        PrivateKey::SIZE,
+        PrivateKey::from
+    )
+    .into();
+    let invalid_key = invalid_curve_point_key();
+
+    let result = combine_public_keys(vec![valid_kp.public, invalid_key], 2);
+    assert!(
+        matches!(result, Err(PartialSignatureError::InvalidCurvePoint)),
+        "expected InvalidCurvePoint error, got {result:?}"
+    );
+}

@@ -53,7 +53,8 @@ impl MultiSigAccount {
         let mut sorted_public_keys = public_keys.to_vec();
         sorted_public_keys.sort();
 
-        let multi_sig_keys = combine_public_keys(sorted_public_keys, min_signatures.get() as usize);
+        let multi_sig_keys =
+            combine_public_keys(sorted_public_keys, min_signatures.get() as usize)?;
 
         Ok(Self::new(key_pair, min_signatures, &multi_sig_keys))
     }
@@ -109,7 +110,9 @@ impl MultiSigAccount {
     }
 
     /// Utility method that delinearizes and aggregates the provided slice of public keys.
-    pub fn aggregate_public_keys(public_keys: &[Ed25519PublicKey]) -> Ed25519PublicKey {
+    pub fn aggregate_public_keys(
+        public_keys: &[Ed25519PublicKey],
+    ) -> Result<Ed25519PublicKey, PartialSignatureError> {
         DelinearizedPublicKey::sum_delinearized(public_keys)
     }
 
@@ -178,6 +181,8 @@ pub enum MultiSigAccountError {
     InvalidSignatureFromBytes(#[from] nimiq_keys::SignatureError),
     #[error("Number of signatures must be the same as the minimal signatures")]
     InvalidSignaturesLength,
+    #[error("Invalid curve point in public key")]
+    InvalidCurvePoint(#[from] PartialSignatureError),
     #[error("The public key of keypair must be part of provided public keys")]
     KeyPairNotPartOfList,
     #[error("The provided public keys must not be empty")]

@@ -44,13 +44,15 @@ pub fn it_can_create_valid_transactions() {
             kp2.public,
             CommitmentPair::to_commitments(&commitment_pairs2),
         )
-        .build(&transaction.serialize_content());
+        .build(&transaction.serialize_content())
+        .unwrap();
     let data2 = CommitmentsBuilder::with_private_commitments(kp2.public, commitment_pairs2)
         .with_signer(
             kp1.public,
             CommitmentPair::to_commitments(&commitment_pairs1),
         )
-        .build(&transaction.serialize_content());
+        .build(&transaction.serialize_content())
+        .unwrap();
 
     assert_eq!(data1.aggregate_public_key, data2.aggregate_public_key);
     assert_eq!(data1.aggregate_commitment, data2.aggregate_commitment);
@@ -115,9 +117,12 @@ pub fn aggregated_public_key_order_does_not_matter() {
     let kp2 = KeyPair::from(PrivateKey::from_hex(PRIVATE_KEYS[1]).unwrap());
     let kp3 = KeyPair::from(PrivateKey::from_hex(PRIVATE_KEYS[2]).unwrap());
 
-    let pk1 = MultiSigAccount::aggregate_public_keys(&[kp1.public, kp2.public, kp3.public]);
-    let pk2 = MultiSigAccount::aggregate_public_keys(&[kp2.public, kp3.public, kp1.public]);
-    let pk3 = MultiSigAccount::aggregate_public_keys(&[kp3.public, kp2.public, kp1.public]);
+    let pk1 =
+        MultiSigAccount::aggregate_public_keys(&[kp1.public, kp2.public, kp3.public]).unwrap();
+    let pk2 =
+        MultiSigAccount::aggregate_public_keys(&[kp2.public, kp3.public, kp1.public]).unwrap();
+    let pk3 =
+        MultiSigAccount::aggregate_public_keys(&[kp3.public, kp2.public, kp1.public]).unwrap();
 
     assert_eq!(pk1, pk2);
     assert_eq!(pk1, pk3);

@@ -96,7 +96,7 @@ impl Address {
             return Err(JsError::new("No public keys provided"));
         }
 
-        let combined_public_keys = combine_public_keys(public_keys, num_signers);
+        let combined_public_keys = combine_public_keys(public_keys, num_signers)?;
         Ok(Address::from(compute_address(&combined_public_keys)))
     }
 

@@ -95,7 +95,7 @@ impl Commitment {
                 builder.push_signer(public_key, commitments);
             });
 
-        let commitment_data = builder.build(data);
+        let commitment_data = builder.build(data)?;
 
         Ok(Commitment::from(commitment_data.aggregate_commitment))
     }

@@ -151,7 +151,7 @@ impl PartialSignature {
             commitments_data.push_signer(other_public_keys[i], commitments);
         }
 
-        let signature = own_keypair.partial_sign(&commitments_data.build(data), data)?;
+        let signature = own_keypair.partial_sign(&commitments_data.build(data)?, data)?;
 
         Ok(PartialSignature::from(signature))
     }

@@ -101,15 +101,15 @@ impl PublicKey {
         num_signers: usize,
     ) -> Result<Vec<PublicKey>, JsError> {
         let keys = PublicKey::unpack_public_keys(keys)?;
-        let combined_keys = combine_public_keys(keys, num_signers);
+        let combined_keys = combine_public_keys(keys, num_signers)?;
         Ok(combined_keys.into_iter().map(PublicKey::from).collect())
     }
 
     /// Sums public keys into one combined public key.
     pub fn sum(keys: &PublicKeyAnyArrayType) -> Result<PublicKey, JsError> {
         let keys = PublicKey::unpack_public_keys(keys)?;
         let combined_key =
-            nimiq_keys::multisig::public_key::DelinearizedPublicKey::sum_delinearized(&keys);
+            nimiq_keys::multisig::public_key::DelinearizedPublicKey::sum_delinearized(&keys)?;
         Ok(PublicKey::from(combined_key))
     }