Skip to main content

ed25519_dalek/
batch.rs

1// -*- mode: rust; -*-
2//
3// This file is part of ed25519-dalek.
4// Copyright (c) 2017-2019 isis lovecruft
5// See LICENSE for licensing information.
6//
7// Authors:
8// - isis agora lovecruft <isis@patternsinthevoid.net>
9
10//! Batch signature verification.
11
12mod transcript;
13
14use alloc::vec::Vec;
15
16use core::convert::Infallible;
17use core::iter::once;
18
19use curve25519_dalek::constants;
20use curve25519_dalek::edwards::EdwardsPoint;
21use curve25519_dalek::scalar::Scalar;
22use curve25519_dalek::traits::IsIdentity;
23use curve25519_dalek::traits::VartimeMultiscalarMul;
24
25pub use curve25519_dalek::digest::Digest;
26
27use transcript::Transcript;
28
29use rand_core::Rng;
30
31use sha2::Sha512;
32
33use crate::VerifyingKey;
34use crate::errors::InternalError;
35use crate::errors::SignatureError;
36use crate::signature::InternalSignature;
37
38/// Domain separation label to initialize the STROBE context.
39///
40/// This is not to be confused with the crate's semver string:
41/// the latter applies to the API, while this label defines the protocol.
42/// E.g. it is possible that crate 2.0 will have an incompatible API,
43/// but implement the same 1.0 protocol.
44const MERLIN_PROTOCOL_LABEL: &[u8] = b"Merlin v1.0";
45
46/// An implementation of `rand_core::Rng` which does nothing. This is necessary because merlin
47/// demands an `Rng` as input to `TranscriptRngBuilder::finalize()`. Using this with `finalize()`
48/// yields a PRG whose input is the hashed transcript.
49struct ZeroRng;
50
51impl rand_core::TryRng for ZeroRng {
52    type Error = Infallible;
53
54    fn try_next_u32(&mut self) -> Result<u32, Self::Error> {
55        rand_core::utils::next_word_via_fill(self)
56    }
57
58    fn try_next_u64(&mut self) -> Result<u64, Self::Error> {
59        rand_core::utils::next_word_via_fill(self)
60    }
61
62    /// A no-op function which leaves the destination bytes for randomness unchanged.
63    ///
64    /// In this case, the internal merlin code is initialising the destination
65    /// by doing `[0u8; …]`, which means that when we call
66    /// `merlin::TranscriptRngBuilder.finalize()`, rather than rekeying the
67    /// STROBE state based on external randomness, we're doing an
68    /// `ENC_{state}(00000000000000000000000000000000)` operation, which is
69    /// identical to the STROBE `MAC` operation.
70    fn try_fill_bytes(&mut self, _dest: &mut [u8]) -> Result<(), Self::Error> {
71        Ok(())
72    }
73}
74
75// `TranscriptRngBuilder::finalize()` requires a `CryptoRng`
76impl rand_core::TryCryptoRng for ZeroRng {}
77
78// We write our own gen() function so we don't need to pull in the rand crate
79fn gen_u128<R: Rng>(rng: &mut R) -> u128 {
80    let mut buf = [0u8; 16];
81    rng.fill_bytes(&mut buf);
82    u128::from_le_bytes(buf)
83}
84
85/// Verify a batch of `signatures` on `messages` with their respective `verifying_keys`.
86///
87/// # Inputs
88///
89/// * `messages` is a slice of byte slices, one per signed message.
90/// * `signatures` is a slice of `Signature`s.
91/// * `verifying_keys` is a slice of `VerifyingKey`s.
92///
93/// # Returns
94///
95/// * A `Result` whose `Ok` value is an empty tuple and whose `Err` value is a
96///   `SignatureError` containing a description of the internal error which
97///   occurred.
98///
99/// ## On Deterministic Nonces
100///
101/// The nonces for batch signature verification are derived purely from the inputs to this function
102/// themselves.
103///
104/// In any sigma protocol it is wise to include as much context pertaining
105/// to the public state in the protocol as possible, to avoid malleability
106/// attacks where an adversary alters publics in an algebraic manner that
107/// manages to satisfy the equations for the protocol in question.
108///
109/// For ed25519 batch verification we include the following as scalars in the protocol transcript:
110///
111/// * All of the computed `H(R||A||M)`s to the protocol transcript, and
112/// * All of the `s` components of each signature.
113///
114/// The former, while not quite as elegant as adding the `R`s, `A`s, and
115/// `M`s separately, saves us a bit of context hashing since the
116/// `H(R||A||M)`s need to be computed for the verification equation anyway.
117///
118/// The latter prevents a malleability attack wherein an adversary, without access
119/// to the signing key(s), can take any valid signature, `(s,R)`, and swap
120/// `s` with `s' = -z1`.  This doesn't constitute a signature forgery, merely
121/// a vulnerability, as the resulting signature will not pass single
122/// signature verification.  (Thanks to Github users @real_or_random and
123/// @jonasnick for pointing out this malleability issue.)
124///
125/// # Examples
126///
127/// ```
128/// use ed25519_dalek::{
129///     verify_batch, SigningKey, VerifyingKey, Signer, Signature,
130/// };
131/// use getrandom::{SysRng, rand_core::{TryRng, UnwrapErr}};
132///
133/// # fn main() {
134/// let mut csprng = UnwrapErr(SysRng);
135/// let signing_keys: Vec<_> = (0..64).map(|_| SigningKey::generate(&mut csprng)).collect();
136/// let msg: &[u8] = b"They're good dogs Brant";
137/// let messages: Vec<_> = (0..64).map(|_| msg).collect();
138/// let signatures:  Vec<_> = signing_keys.iter().map(|key| key.sign(&msg)).collect();
139/// let verifying_keys: Vec<_> = signing_keys.iter().map(|key| key.verifying_key()).collect();
140///
141/// let result = verify_batch(&messages, &signatures, &verifying_keys);
142/// assert!(result.is_ok());
143/// # }
144/// ```
145#[allow(non_snake_case)]
146pub fn verify_batch(
147    messages: &[&[u8]],
148    signatures: &[ed25519::Signature],
149    verifying_keys: &[VerifyingKey],
150) -> Result<(), SignatureError> {
151    // Return an Error if any of the vectors were not the same size as the others.
152    if signatures.len() != messages.len()
153        || signatures.len() != verifying_keys.len()
154        || verifying_keys.len() != messages.len()
155    {
156        return Err(InternalError::ArrayLength {
157            name_a: "signatures",
158            length_a: signatures.len(),
159            name_b: "messages",
160            length_b: messages.len(),
161            name_c: "verifying_keys",
162            length_c: verifying_keys.len(),
163        }
164        .into());
165    }
166
167    // Make a transcript which logs all inputs to this function
168    let mut transcript: Transcript = Transcript::new(b"ed25519 batch verification");
169
170    // We make one optimization in the transcript: since we will end up computing H(R || A || M)
171    // for each (R, A, M) triplet, we will feed _that_ into our transcript rather than each R, A, M
172    // individually. Since R and A are fixed-length, this modification is secure so long as SHA-512
173    // is collision-resistant.
174    // It suffices to take `verifying_keys[i].as_bytes()` even though a `VerifyingKey` has two
175    // fields, and `as_bytes()` only returns the bytes of the first. This is because of an
176    // invariant guaranteed by `VerifyingKey`: the second field is always the (unique)
177    // decompression of the first. Thus, the serialized first field is a unique representation of
178    // the entire `VerifyingKey`.
179    let hrams: Vec<[u8; 64]> = (0..signatures.len())
180        .map(|i| {
181            // Compute H(R || A || M), where
182            // R = sig.R
183            // A = verifying key
184            // M = msg
185            let mut h: Sha512 = Sha512::default();
186            h.update(signatures[i].r_bytes());
187            h.update(verifying_keys[i].as_bytes());
188            h.update(messages[i]);
189            *h.finalize().as_ref()
190        })
191        .collect();
192
193    // Update transcript with the hashes above. This covers verifying_keys, messages, and the R
194    // half of signatures
195    for hram in hrams.iter() {
196        transcript.append_message(b"hram", hram);
197    }
198    // Update transcript with the rest of the data. This covers the s half of the signatures
199    for sig in signatures {
200        transcript.append_message(b"sig.s", sig.s_bytes());
201    }
202
203    // All function inputs have now been hashed into the transcript. Finalize it and use it as
204    // randomness for the batch verification.
205    let mut rng = transcript.build_rng().finalize(&mut ZeroRng);
206
207    // Convert all signatures to `InternalSignature`
208    let signatures = signatures
209        .iter()
210        .map(InternalSignature::try_from)
211        .collect::<Result<Vec<_>, _>>()?;
212    // Convert the H(R || A || M) values into scalars
213    let hrams: Vec<Scalar> = hrams
214        .iter()
215        .map(Scalar::from_bytes_mod_order_wide)
216        .collect();
217
218    // Select a random 128-bit scalar for each signature.
219    let zs: Vec<Scalar> = signatures
220        .iter()
221        .map(|_| Scalar::from(gen_u128(&mut rng)))
222        .collect();
223
224    // Compute the basepoint coefficient, ∑ s[i]z[i] (mod l)
225    let B_coefficient: Scalar = signatures
226        .iter()
227        .map(|sig| sig.s)
228        .zip(zs.iter())
229        .map(|(s, z)| z * s)
230        .sum();
231
232    // Multiply each H(R || A || M) by the random value
233    let zhrams = hrams.iter().zip(zs.iter()).map(|(hram, z)| hram * z);
234
235    let Rs = signatures.iter().map(|sig| sig.R.decompress());
236    let As = verifying_keys.iter().map(|pk| Some(pk.point));
237    let B = once(Some(constants::ED25519_BASEPOINT_POINT));
238
239    // Compute (-∑ z[i]s[i] (mod l)) B + ∑ z[i]R[i] + ∑ (z[i]H(R||A||M)[i] (mod l)) A[i] = 0
240    let id = EdwardsPoint::optional_multiscalar_mul(
241        once(-B_coefficient).chain(zs.iter().cloned()).chain(zhrams),
242        B.chain(Rs).chain(As),
243    )
244    .ok_or(InternalError::Verify)?;
245
246    if id.is_identity() {
247        Ok(())
248    } else {
249        Err(InternalError::Verify.into())
250    }
251}