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}