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