Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_crypto/tests/ed25519_strict.rs

13.6 KiB, 1 run

created by r1870400018:61098, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Ed25519 verification held to the strict rules, against oracles this crate does
2//! not define.
3//!
4//! - The C2SP CCTV edge-case vectors, `tests/data/ed25519vectors.json` (provenance
5//! in `tests/data/PROVENANCE.md`). Each vector is flagged with the edge cases it
6//! exercises, so the verdict a verifier owes it follows from its flags and the
7//! rules alone.
8//! - RFC 8032 §7.1's own examples, which must still verify.
9//! - `ed25519-dalek`'s `verify_strict`, differentially, over honest signatures and
10//! random mutations of them.
11//!
12//! The rules are RFC 8032 §5.1.7 read strictly: the public key and R must each be
13//! the canonical encoding of a point (§5.1.3), S must lie below the group order,
14//! the group equation is the cofactored one the RFC gives first, and a public key
15//! or R of small order is refused whatever the equation says.
16//!
17//! Every check goes through `SignatureScheme::verify` or `verify_batch`, the path
18//! every caller takes, so nothing here can pass while a caller is still exposed.
19
20use oxedyne_fe2o3_core::prelude::*;
21use oxedyne_fe2o3_crypto::sign::SignatureScheme;
22use oxedyne_fe2o3_iop_crypto::{
23 keys::KeyManager,
24 sign::{
25 BatchItem,
26 Signer,
27 },
28};
29use oxedyne_fe2o3_jdat::prelude::*;
30
31use ed25519_dalek::{
32 Signature,
33 Signer as DalekSigner,
34 SigningKey,
35 VerifyingKey,
36};
37use rand::RngCore;
38
39// The edge cases a strict verifier refuses outright. The other flags, a
40// low-order *component* of A or R and a low-order residue that the cofactored
41// equation absorbs, leave a signature to stand or fall by the equation.
42const REFUSED: [&str; 4] = [
43 "low_order_A",
44 "low_order_R",
45 "non_canonical_A",
46 "non_canonical_R",
47];
48
49struct Vector {
50 number: u64,
51 key: Vec<u8>,
52 sig: Vec<u8>,
53 msg: Vec<u8>,
54 flags: Vec<String>,
55}
56
57impl Vector {
58 /// Does a strict verifier owe this vector acceptance?
59 fn acceptable(&self) -> bool {
60 !self.flags.iter().any(|f| REFUSED.contains(&f.as_str()))
61 }
62}
63
64fn unhex(s: &str) -> Outcome<Vec<u8>> {
65 Ok(res!(hex::decode(s).map_err(|e| err!("Bad hex '{}': {:?}", s, e; Decode, Test))))
66}
67
68fn vectors() -> Outcome<Vec<Vector>> {
69 let dat = res!(Dat::decode_string(include_str!("data/ed25519vectors.json")));
70 let list = match dat {
71 Dat::List(list) => list,
72 other => return Err(err!(
73 "The CCTV vector file holds a {:?} where a list was expected.", other.kind();
74 Decode, Test)),
75 };
76 let mut out = Vec::with_capacity(list.len());
77 for item in list.iter() {
78 let number = res!(item.map_get_u64(&dat!("number")));
79 let flags = match res!(item.map_get(&dat!("flags"))) {
80 Some(Dat::List(fs)) => {
81 let mut flags = Vec::with_capacity(fs.len());
82 for f in fs {
83 match f {
84 Dat::Str(s) => flags.push(s.clone()),
85 other => return Err(err!(
86 "Vector {} has a flag of kind {:?}.", number, other.kind();
87 Decode, Test)),
88 }
89 }
90 flags
91 },
92 _ => Vec::new(), // null, the one vector with no edge case
93 };
94 out.push(Vector {
95 number,
96 key: res!(unhex(&res!(item.map_get_string(&dat!("key"))))),
97 sig: res!(unhex(&res!(item.map_get_string(&dat!("sig"))))),
98 msg: res!(item.map_get_string(&dat!("msg"))).into_bytes(),
99 flags,
100 });
101 }
102 Ok(out)
103}
104
105/// Checks one signature the way every caller checks one.
106fn single(public: &[u8], msg: &[u8], sig: &[u8]) -> Outcome<bool> {
107 let bound = res!(SignatureScheme::empty_ed25519().clone_with_keys(Some(public), None));
108 bound.verify(msg, sig)
109}
110
111fn batch(items: &[BatchItem<'_>]) -> Outcome<bool> {
112 SignatureScheme::empty_ed25519().verify_batch(items)
113}
114
115/// A fresh key pair, as `(signing key, public key bytes)`.
116fn pair() -> (SigningKey, Vec<u8>) {
117 let mut seed = [0u8; 32];
118 rand::thread_rng().fill_bytes(&mut seed);
119 let sk = SigningKey::from_bytes(&seed);
120 let pk = sk.verifying_key().to_bytes().to_vec();
121 (sk, pk)
122}
123
124/// The identity point as a public key, with R the identity and S zero, satisfies
125/// the cofactorless equation `[S]B = R + [k]A` for every message, since every term
126/// is the identity whatever k is. A verifier that takes this is a verifier any
127/// stranger can sign for, which is why a strict verifier refuses a small-order
128/// key before it looks at the equation.
129#[test]
130fn a_small_order_key_signs_nothing() -> Outcome<()> {
131 let mut identity = [0u8; 32];
132 identity[0] = 0x01;
133 let mut forged = [0u8; 64];
134 forged[0] = 0x01; // R, the identity; S stays zero.
135 let msgs: [&[u8]; 4] = [
136 b"",
137 b"transfer everything to the forger",
138 b"a message nobody signed",
139 &[0xffu8; 200],
140 ];
141 for msg in msgs.iter() {
142 req!(res!(single(&identity, msg, &forged)), false,
143 "the identity key's forgery was accepted singly over {:?}", msg);
144 req!(res!(batch(&[BatchItem { public: &identity, msg, sig: &forged }])), false,
145 "the identity key's forgery was accepted in a batch over {:?}", msg);
146 }
147 // A forgery must not hide in a batch among sound signatures either.
148 let (sk, pk) = pair();
149 let sound = sk.sign(b"sound").to_bytes();
150 req!(res!(batch(&[
151 BatchItem { public: &pk, msg: b"sound", sig: &sound },
152 BatchItem { public: &identity, msg: b"forged", sig: &forged },
153 BatchItem { public: &pk, msg: b"sound", sig: &sound },
154 ])), false, "the forgery was accepted inside a batch of sound signatures");
155 Ok(())
156}
157
158/// Every CCTV vector earns the strict verdict its flags imply.
159#[test]
160fn the_cctv_edge_cases_earn_the_strict_verdict() -> Outcome<()> {
161 let vs = res!(vectors());
162 req!(vs.len(), 914, "the CCTV file has 914 vectors");
163 let mut wrong = Vec::new();
164 for v in vs.iter() {
165 let got = res!(single(&v.key, &v.msg, &v.sig));
166 if got != v.acceptable() {
167 wrong.push(fmt!("#{} {:?} gave {}", v.number, v.flags, got));
168 }
169 }
170 req!(wrong.len(), 0, "{} vectors earned the wrong verdict: {:?}",
171 wrong.len(), &wrong[..wrong.len().min(8)]);
172 // The file's accepted set is not empty, so the test above is not passed by a
173 // verifier that refuses everything.
174 req!(vs.iter().filter(|v| v.acceptable()).count(), 106,
175 "106 vectors carry only flags a strict verifier accepts");
176 Ok(())
177}
178
179/// The batch accepts each CCTV vector exactly when the single check does, alone
180/// and among sound signatures.
181///
182/// The two are different equations, and Ore's `Envelope::verify_all` promises its
183/// callers that a batch accepts the set the single check accepts, envelope for
184/// envelope. With the cofactorless equation that promise fails for a signature
185/// whose R carries a low-order component: the single check refuses it, and a
186/// batch accepts it whenever the batch's own coefficient happens to annihilate
187/// that component, which a signer can arrange by trying messages.
188#[test]
189fn the_batch_agrees_with_the_single_check_on_every_edge_case() -> Outcome<()> {
190 let (sk, pk) = pair();
191 let sound_msg = b"a sound signature beside the vector";
192 let sound = sk.sign(sound_msg).to_bytes();
193 let mut wrong = Vec::new();
194 for v in res!(vectors()).iter() {
195 let one = res!(single(&v.key, &v.msg, &v.sig));
196 let alone = res!(batch(&[BatchItem { public: &v.key, msg: &v.msg, sig: &v.sig }]));
197 let among = res!(batch(&[
198 BatchItem { public: &pk, msg: sound_msg, sig: &sound },
199 BatchItem { public: &v.key, msg: &v.msg, sig: &v.sig },
200 BatchItem { public: &pk, msg: sound_msg, sig: &sound },
201 ]));
202 if alone != one || among != one {
203 wrong.push(fmt!("#{} {:?}: single {}, alone {}, among {}",
204 v.number, v.flags, one, alone, among));
205 }
206 }
207 req!(wrong.len(), 0, "{} vectors split the batch from the single check: {:?}",
208 wrong.len(), &wrong[..wrong.len().min(8)]);
209 Ok(())
210}
211
212/// RFC 8032 §7.1's examples verify, alone and as one batch, and a signature
213/// moved to another example's message does not.
214#[test]
215fn the_rfc8032_examples_verify() -> Outcome<()> {
216 // (secret, public, message, signature), TEST 1, 2, 3 and SHA(abc).
217 let cases: [(&str, &str, &str, &str); 4] = [
218 (
219 "9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60",
220 "d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a",
221 "",
222 "e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e06522490155\
223 5fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b",
224 ),
225 (
226 "4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb",
227 "3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c",
228 "72",
229 "92a009a9f0d4cab8720e820b5f642540a2b27b5416503f8fb3762223ebdb69da\
230 085ac1e43e15996e458f3613d0f11d8c387b2eaeb4302aeeb00d291612bb0c00",
231 ),
232 (
233 "c5aa8df43f9f837bedb7442f31dcb7b166d38535076f094b85ce3a2e0b4458f7",
234 "fc51cd8e6218a1a38da47ed00230f0580816ed13ba3303ac5deb911548908025",
235 "af82",
236 "6291d657deec24024827e69c3abe01a30ce548a284743a445e3680d7db5ac3ac\
237 18ff9b538d16f290ae67f760984dc6594a7c15e9716ed28dc027beceea1ec40a",
238 ),
239 (
240 "833fe62409237b9d62ec77587520911e9a759cec1d19755b7da901b96dca3d42",
241 "ec172b93ad5e563bf4932c70e1245034c35467ef2efd4d64ebf819683467e2bf",
242 "ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a\
243 2192992a274fc1a836ba3c23a3feebbd454d4423643ce80e2a9ac94fa54ca49f",
244 "dc2a4459e7369633a52b1bf277839a00201009a3efbf3ecb69bea2186c26b589\
245 09351fc9ac90b3ecfdfbc7c66431e0303dca179c138ac17ad9bef1177331a704",
246 ),
247 ];
248 let mut parsed = Vec::with_capacity(cases.len());
249 for (secret, public, msg, sig) in cases.iter() {
250 let (secret, public, msg, sig) =
251 (res!(unhex(secret)), res!(unhex(public)), res!(unhex(msg)), res!(unhex(sig)));
252 // The scheme's own signer reproduces the RFC's signature, Ed25519 being
253 // deterministic, so the vectors are read the way the RFC means them.
254 let signer = res!(SignatureScheme::empty_ed25519()
255 .clone_with_keys(Some(&public), Some(&secret)));
256 req!(res!(signer.sign(&msg)), sig.clone(), "signing reproduces the RFC's signature");
257 req!(res!(single(&public, &msg, &sig)), true, "an RFC 8032 example verifies");
258 parsed.push((public, msg, sig));
259 }
260 let items: Vec<BatchItem<'_>> = parsed.iter()
261 .map(|(public, msg, sig)| BatchItem { public, msg, sig })
262 .collect();
263 req!(res!(batch(&items)), true, "the RFC 8032 examples verify as one batch");
264 req!(res!(single(&parsed[0].0, &parsed[1].1, &parsed[0].2)), false,
265 "a signature moved to another message does not verify");
266 Ok(())
267}
268
269/// Honest signatures verify, and random mutations of the key, the message and
270/// each half of the signature earn the same verdict here as from
271/// `ed25519-dalek`'s `verify_strict`, singly and in a batch.
272///
273/// The two verifiers differ only where a residue of small order survives, which
274/// a random mutation reaches with negligible probability, so any disagreement
275/// here is a fault in this crate.
276#[test]
277fn verdicts_match_dalek_strict_over_honest_and_mutated_signatures() -> Outcome<()> {
278 let mut rng = rand::thread_rng();
279 for round in 0..300 {
280 let (sk, pk) = pair();
281 let mut msg = vec![0u8; (rng.next_u32() % 96) as usize];
282 rng.fill_bytes(&mut msg);
283 let sig = sk.sign(&msg).to_bytes().to_vec();
284 req!(res!(single(&pk, &msg, &sig)), true, "an honest signature verifies (round {})", round);
285
286 // Mutate one of key, message, R or S, by one random bit.
287 let (mut pk2, mut msg2, mut sig2) = (pk.clone(), msg.clone(), sig.clone());
288 match round % 4 {
289 0 => { let i = (rng.next_u32() % 32) as usize; pk2[i] ^= 1 << (rng.next_u32() % 8); },
290 1 => {
291 if msg2.is_empty() {
292 msg2.push(0x00);
293 } else {
294 let i = rng.next_u32() as usize % msg2.len();
295 msg2[i] ^= 1 << (rng.next_u32() % 8);
296 }
297 },
298 2 => { let i = (rng.next_u32() % 32) as usize; sig2[i] ^= 1 << (rng.next_u32() % 8); },
299 _ => { let i = 32 + (rng.next_u32() % 32) as usize; sig2[i] ^= 1 << (rng.next_u32() % 8); },
300 }
301 let mut pk_arr = [0u8; 32];
302 pk_arr.copy_from_slice(&pk2);
303 let dalek = match VerifyingKey::from_bytes(&pk_arr) {
304 // A mutated key that is not a point at all is an error here, as it
305 // always has been; there is nothing to compare.
306 Err(_) => {
307 req!(single(&pk2, &msg2, &sig2).is_err(), true,
308 "a key that is not a point is an error (round {})", round);
309 continue;
310 },
311 Ok(vk) => match Signature::from_slice(&sig2) {
312 Ok(s) => vk.verify_strict(&msg2, &s).is_ok(),
313 Err(_) => false,
314 },
315 };
316 let ours = res!(single(&pk2, &msg2, &sig2));
317 req!(ours, dalek, "the verdict differs from dalek's verify_strict (round {}, case {})",
318 round, round % 4);
319 let batched = res!(batch(&[BatchItem { public: &pk2, msg: &msg2, sig: &sig2 }]));
320 req!(batched, dalek, "the batch verdict differs from dalek's verify_strict (round {})",
321 round);
322 }
323 Ok(())
324}