Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_crypto/tests/linkring.rs

17.6 KiB, 1 run

created by r1870400018:61083, 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//! `linkring/1` against an independent implementation, `tools/linkring_oracle.py`,
2//! both through vectors it produced and, where `python3` exists, live.
3
4use oxedyne_fe2o3_core::prelude::*;
5use oxedyne_fe2o3_crypto::linkring::{
6 self,
7 Ring,
8 SecretKey,
9};
10
11use std::io::Write;
12use std::process::{
13 Command,
14 Stdio,
15};
16
17use rand::RngCore;
18
19struct Case {
20 name: String,
21 seeds: Vec<Vec<u8>>,
22 signer: usize,
23 scope: Vec<u8>,
24 msg: Vec<u8>,
25 aux: Vec<u8>,
26 fields: Vec<(String, Vec<u8>)>, // ring, digest, tag, body, ok
27}
28
29impl Case {
30 fn get(&self, k: &str) -> Outcome<&Vec<u8>> {
31 match self.fields.iter().find(|(key, _)| key == k) {
32 Some((_, v)) => Ok(v),
33 None => Err(err!("Case {} has no {}.", self.name, k; Missing, Test)),
34 }
35 }
36}
37
38fn unhex(s: &str) -> Outcome<Vec<u8>> {
39 Ok(res!(hex::decode(s).map_err(|e| err!("Bad hex '{}': {}", s, e; Decode, Test))))
40}
41
42fn parse(text: &str) -> Outcome<Vec<Case>> {
43 let mut out = Vec::new();
44 let mut cur: Option<Case> = None;
45 for line in text.lines() {
46 let line = line.trim();
47 if line.is_empty() || line.starts_with('#') {
48 continue;
49 }
50 let (key, val) = line.split_once(' ').unwrap_or((line, ""));
51 match key {
52 "case" => cur = Some(Case {
53 name: val.to_string(), seeds: Vec::new(), signer: 0, scope: Vec::new(),
54 msg: Vec::new(), aux: Vec::new(), fields: Vec::new(),
55 }),
56 "end" => {
57 if let Some(c) = cur.take() {
58 out.push(c);
59 }
60 }
61 _ => {
62 let c = res!(cur.as_mut().ok_or_else(|| err!("'{}' outside a case.", key; Test)));
63 match key {
64 "seeds" => for s in val.split(',') { c.seeds.push(res!(unhex(s))); },
65 "signer" => c.signer = res!(val.parse::<usize>().map_err(|_| err!(
66 "Bad signer '{}'.", val; Decode, Test))),
67 "scope" => c.scope = res!(unhex(val)),
68 "msg" => c.msg = res!(unhex(val)),
69 "aux" => c.aux = res!(unhex(val)),
70 "ok" => c.fields.push((key.to_string(), val.as_bytes().to_vec())),
71 _ => c.fields.push((key.to_string(), res!(unhex(val)))),
72 }
73 }
74 }
75 }
76 Ok(out)
77}
78
79fn keys_of(seeds: &[Vec<u8>]) -> Outcome<(Vec<SecretKey>, Ring)> {
80 let mut keys = Vec::with_capacity(seeds.len());
81 for s in seeds {
82 keys.push(res!(SecretKey::from_seed(s)));
83 }
84 let pubs: Vec<[u8; 32]> = keys.iter().map(|k| k.public_key()).collect();
85 let ring = res!(Ring::from_keys(&pubs));
86 Ok((keys, ring))
87}
88
89fn ring_of(n: usize, label: &str) -> Outcome<(Vec<SecretKey>, Ring)> {
90 let seeds: Vec<Vec<u8>> = (0..n).map(|i| fmt!("{}-{}", label, i).into_bytes()).collect();
91 keys_of(&seeds)
92}
93
94fn oracle_path() -> String {
95 fmt!("{}/tools/linkring_oracle.py", env!("CARGO_MANIFEST_DIR"))
96}
97
98fn run_oracle(mode: &str, input: &str) -> Outcome<Option<String>> {
99 let child = Command::new("python3")
100 .arg(oracle_path())
101 .arg(mode)
102 .stdin(Stdio::piped())
103 .stdout(Stdio::piped())
104 .spawn();
105 let mut child = match child {
106 Ok(c) => c,
107 Err(_) => return Ok(None),
108 };
109 if let Some(mut stdin) = child.stdin.take() {
110 res!(stdin.write_all(input.as_bytes()));
111 }
112 let out = res!(child.wait_with_output());
113 if !out.status.success() {
114 return Err(err!("The oracle exited with {}: {}", out.status,
115 String::from_utf8_lossy(&out.stdout); Test));
116 }
117 Ok(Some(String::from_utf8_lossy(&out.stdout).into_owned()))
118}
119
120// ── External oracle ─────────────────────────────────────────────────────────
121
122#[test]
123fn test_oracle_vectors() -> Outcome<()> {
124 let text = include_str!("data/linkring_vectors.txt");
125 let cases = res!(parse(text));
126 req!((cases.len() >= 6), true, "vector count");
127 for c in &cases {
128 let (keys, ring) = res!(keys_of(&c.seeds));
129 let list: Vec<u8> = ring.keys().concat();
130 req!(&list, res!(c.get("ring")), "{} ring", c.name);
131 req!(&ring.digest().to_vec(), res!(c.get("digest")), "{} digest", c.name);
132 req!(&linkring::ring_digest(&list).to_vec(), res!(c.get("digest")), "{} digest fn", c.name);
133 let key = &keys[c.signer];
134 req!(&res!(linkring::tag(key, &c.scope)).to_vec(), res!(c.get("tag")), "{} tag()", c.name);
135 let (tag, body) = res!(linkring::sign_with_aux(&ring, key, &c.scope, &c.msg, &c.aux));
136 req!(&tag.to_vec(), res!(c.get("tag")), "{} tag", c.name);
137 req!(&body, res!(c.get("body")), "{} body", c.name);
138 req!(res!(linkring::verify(&ring, &c.scope, &c.msg, &tag, &body)), true, "{}", c.name);
139 }
140 Ok(())
141}
142
143#[test]
144fn test_oracle_live() -> Outcome<()> {
145 let mut rng = rand::thread_rng();
146 let mut input = String::new();
147 let mut made = Vec::new();
148 for (ci, n) in [3usize, 16, 18, 29].into_iter().enumerate() {
149 let seeds: Vec<Vec<u8>> = (0..n).map(|_| {
150 let mut s = vec![0u8; 24];
151 rng.fill_bytes(&mut s);
152 s
153 }).collect();
154 let signer = (rng.next_u32() as usize) % n;
155 let mut scope = vec![0u8; 12];
156 let mut msg = vec![0u8; 40];
157 let mut aux = vec![0u8; 8];
158 rng.fill_bytes(&mut scope);
159 rng.fill_bytes(&mut msg);
160 rng.fill_bytes(&mut aux);
161 let (keys, ring) = res!(keys_of(&seeds));
162 let (tag, body) = res!(linkring::sign_with_aux(&ring, &keys[signer], &scope, &msg, &aux));
163 let seeds_hex: Vec<String> = seeds.iter().map(hex::encode).collect();
164 input.push_str(&fmt!("case c{}\nseeds {}\nsigner {}\nscope {}\nmsg {}\naux {}\nend\n",
165 ci, seeds_hex.join(","), signer, hex::encode(&scope), hex::encode(&msg), hex::encode(&aux)));
166 made.push((ring, scope, msg, tag, body));
167 }
168 let signed = match res!(run_oracle("sign", &input)) {
169 Some(s) => s,
170 None => {
171 println!("python3 not found: the live oracle is skipped; the vectors still ran.");
172 return Ok(());
173 }
174 };
175 let cases = res!(parse(&signed));
176 req!(cases.len(), made.len());
177 // The oracle, signing independently, produces the same bytes.
178 for (c, (ring, _, _, tag, body)) in cases.iter().zip(made.iter()) {
179 req!(res!(c.get("ring")), &ring.keys().concat(), "{} ring", c.name);
180 req!(res!(c.get("tag")), &tag.to_vec(), "{} tag", c.name);
181 req!(res!(c.get("body")), body, "{} body", c.name);
182 }
183 // The oracle verifies Rust's bodies and refuses tampered ones.
184 let mut vin = String::new();
185 let mut want = Vec::new();
186 for (i, (ring, scope, msg, tag, body)) in made.iter().enumerate() {
187 let list = hex::encode(ring.keys().concat());
188 let mut other = ring.keys().to_vec();
189 other.swap(0, ring.len() - 1);
190 let mut bad_body = body.clone();
191 let last = bad_body.len() - 1;
192 bad_body[last - 40] ^= 1;
193 let mut bad_msg = msg.clone();
194 bad_msg[0] ^= 1;
195 let variants: Vec<(&str, String, &[u8], &[u8], &[u8], Vec<u8>, bool)> = vec![
196 ("ok", list.clone(), scope, msg, tag, body.clone(), true),
197 ("msg", list.clone(), scope, &bad_msg, tag, body.clone(), false),
198 ("scope", list.clone(), b"x", msg, tag, body.clone(), false),
199 ("body", list.clone(), scope, msg, tag, bad_body, false),
200 ("ring", hex::encode(other.concat()), scope, msg, tag, body.clone(), false),
201 ];
202 for (name, rl, sc, ms, tg, bd, ok) in variants {
203 vin.push_str(&fmt!("case c{}-{}\nring {}\nscope {}\nmsg {}\ntag {}\nbody {}\nend\n",
204 i, name, rl, hex::encode(sc), hex::encode(ms), hex::encode(tg), hex::encode(&bd)));
205 want.push(ok);
206 }
207 }
208 let verified = res!(res!(run_oracle("verify", &vin)).ok_or_else(|| err!("python3 vanished"; Test)));
209 let got = res!(parse(&verified));
210 req!(got.len(), want.len());
211 for (c, ok) in got.iter().zip(want.iter()) {
212 let expect: &[u8] = if *ok { b"true" } else { b"false" };
213 req!(res!(c.get("ok")).as_slice(), expect, "{}", c.name);
214 }
215 Ok(())
216}
217
218// ── Refusals ────────────────────────────────────────────────────────────────
219
220#[test]
221fn test_tamper_each_refuses() -> Outcome<()> {
222 let (keys, ring) = res!(ring_of(21, "tamper"));
223 let scope = b"present/1:https://app.example";
224 let msg = b"{\"v\":\"present/1\"}";
225 let (tag, body) = res!(linkring::sign(&ring, &keys[9], scope, msg));
226 req!(res!(linkring::verify(&ring, scope, msg, &tag, &body)), true, "honest");
227
228 // Ring: a key replaced, two swapped, one dropped, one added.
229 let mut ks = ring.keys().to_vec();
230 ks[3] = res!(SecretKey::from_seed(b"outsider")).public_key();
231 let r = res!(Ring::from_keys(&ks));
232 req!(res!(linkring::verify(&r, scope, msg, &tag, &body)), false, "ring replaced");
233 let mut ks = ring.keys().to_vec();
234 ks.swap(2, 15);
235 let r = res!(Ring::from_keys(&ks));
236 req!(res!(linkring::verify(&r, scope, msg, &tag, &body)), false, "ring swapped");
237 let ks = ring.keys()[..20].to_vec();
238 let r = res!(Ring::from_keys(&ks));
239 req!(res!(linkring::verify(&r, scope, msg, &tag, &body)), false, "ring dropped");
240 let mut ks = ring.keys().to_vec();
241 ks.push(res!(SecretKey::from_seed(b"extra")).public_key());
242 let r = res!(Ring::from_keys(&ks));
243 req!(res!(linkring::verify(&r, scope, msg, &tag, &body)), false, "ring added");
244
245 // Message and scope.
246 req!(res!(linkring::verify(&ring, scope, b"{\"v\":\"present/2\"}", &tag, &body)), false, "msg");
247 req!(res!(linkring::verify(&ring, b"present/1:https://evil.example", msg, &tag, &body)), false,
248 "scope");
249
250 // Tag: another member's, the same key's under another scope, the key itself.
251 let t2 = res!(linkring::tag(&keys[10], scope));
252 req!(res!(linkring::verify(&ring, scope, msg, &t2, &body)), false, "other member's tag");
253 let t3 = res!(linkring::tag(&keys[9], b"present/1:https://other.example"));
254 req!(res!(linkring::verify(&ring, scope, msg, &t3, &body)), false, "other scope's tag");
255 req!(res!(linkring::verify(&ring, scope, msg, &keys[9].public_key(), &body)), false, "pubkey");
256
257 // Body: a valid point or scalar swapped in at every region.
258 let m = linkring::digits(ring.len());
259 let base_pt = keys[0].public_key();
260 for i in 0..(4 + 2 * m) {
261 let mut b = body.clone();
262 b[1 + 32 * i..33 + 32 * i].copy_from_slice(&base_pt);
263 req!(res!(linkring::verify(&ring, scope, msg, &tag, &b)), false, "point {}", i);
264 }
265 let first_sc = 1 + 32 * (4 + 2 * m);
266 for i in 0..(15 * m + 3) {
267 let mut b = body.clone();
268 let off = first_sc + 32 * i;
269 b[off..off + 32].copy_from_slice(&res!(SecretKey::from_seed(b"sc")).to_bytes());
270 req!(res!(linkring::verify(&ring, scope, msg, &tag, &b)), false, "scalar {}", i);
271 }
272
273 // Malformed: wrong length, wrong digit count, non-canonical scalar, bad point.
274 req!(res!(linkring::verify(&ring, scope, msg, &tag, &body[..body.len() - 1])), false, "short");
275 let mut b = body.clone();
276 b.push(0);
277 req!(res!(linkring::verify(&ring, scope, msg, &tag, &b)), false, "long");
278 let mut b = body.clone();
279 b[0] = 3;
280 req!(res!(linkring::verify(&ring, scope, msg, &tag, &b)), false, "m byte");
281 let mut b = body.clone();
282 let off = b.len() - 32;
283 for x in &mut b[off..] { *x = 0xff; }
284 req!(res!(linkring::verify(&ring, scope, msg, &tag, &b)), false, "non-canonical z");
285 let mut b = body.clone();
286 b[1..33].copy_from_slice(&[0xff; 32]);
287 req!(res!(linkring::verify(&ring, scope, msg, &tag, &b)), false, "bad point");
288 req!(res!(linkring::verify(&ring, scope, msg, &tag[..31], &body)), false, "short tag");
289 req!(res!(linkring::verify(&ring, scope, msg, &[0u8; 32], &body)), false, "identity tag");
290 Ok(())
291}
292
293#[test]
294fn test_ring_refuses_bad_keys() -> Outcome<()> {
295 let good = res!(SecretKey::from_seed(b"g")).public_key();
296 req!(Ring::from_list(&[]).is_err(), true, "empty");
297 req!(Ring::from_list(&[0u8; 33]).is_err(), true, "ragged");
298 let mut list = good.to_vec();
299 list.extend_from_slice(&[0u8; 32]);
300 req!(Ring::from_list(&list).is_err(), true, "identity key");
301 let mut list = good.to_vec();
302 list.extend_from_slice(&[0xffu8; 32]);
303 req!(Ring::from_list(&list).is_err(), true, "not an encoding");
304 let ring = res!(Ring::from_list(&good));
305 let outsider = res!(SecretKey::from_seed(b"o"));
306 req!(linkring::sign(&ring, &outsider, b"s", b"m").is_err(), true, "signer not in ring");
307 req!(SecretKey::from_bytes(&[0u8; 32]).is_err(), true, "zero secret");
308 req!(SecretKey::from_bytes(&[0xffu8; 32]).is_err(), true, "non-canonical secret");
309 let k = res!(SecretKey::from_seed(b"rt"));
310 req!(res!(SecretKey::from_bytes(&k.to_bytes())).public_key(), k.public_key(), "round trip");
311 Ok(())
312}
313
314// ── Tags ────────────────────────────────────────────────────────────────────
315
316#[test]
317fn test_tag_stable_per_key_and_scope() -> Outcome<()> {
318 let (keys, ring) = res!(ring_of(7, "stable"));
319 let scope = b"present/1:https://app.example";
320 let (t1, b1) = res!(linkring::sign(&ring, &keys[4], scope, b"first"));
321 let (t2, b2) = res!(linkring::sign(&ring, &keys[4], scope, b"second"));
322 req!(t1, t2, "same key, same scope");
323 req!((b1 != b2), true, "fresh bodies");
324 req!(t1, res!(linkring::tag(&keys[4], scope)), "tag() agrees");
325 // A second ring holding the key gives the same tag: the tag is the key's,
326 // not the ring's.
327 let (more, _) = res!(ring_of(12, "other-ring"));
328 let mut ks: Vec<[u8; 32]> = more.iter().map(|k| k.public_key()).collect();
329 ks.push(keys[4].public_key());
330 let ring2 = res!(Ring::from_keys(&ks));
331 let (t3, _) = res!(linkring::sign(&ring2, &keys[4], scope, b"third"));
332 req!(t1, t3, "same tag over another ring");
333 let (t4, _) = res!(linkring::sign(&ring, &keys[4], b"present/1:https://b.example", b"m"));
334 req!((t1 != t4), true, "scopes differ");
335 let (t5, _) = res!(linkring::sign(&ring, &keys[5], scope, b"m"));
336 req!((t1 != t5), true, "keys differ");
337 Ok(())
338}
339
340// Tags of one key under two scopes should look no more alike than the tags of
341// two different keys. Bit 0 of byte 0 and bit 7 of byte 31 are fixed by the
342// ristretto255 encoding and so are left out.
343#[test]
344fn test_tag_unlinkable_across_scopes() -> Outcome<()> {
345 const K: usize = 400;
346 let s1 = b"present/1:https://a.example";
347 let s2 = b"present/1:https://b.example";
348 let mut t1 = Vec::with_capacity(K);
349 let mut t2 = Vec::with_capacity(K);
350 let mut pk = Vec::with_capacity(K);
351 for i in 0..K {
352 let k = res!(SecretKey::from_seed(fmt!("unlink-{}", i).as_bytes()));
353 t1.push(res!(linkring::tag(&k, s1)));
354 t2.push(res!(linkring::tag(&k, s2)));
355 pk.push(k.public_key());
356 }
357 let free_bit = |b: usize| b != 0 && b != 255;
358 let bit = |x: &[u8; 32], b: usize| (x[b / 8] >> (b % 8)) & 1;
359 let dist = |x: &[u8; 32], y: &[u8; 32]| (0..256).filter(|&b| free_bit(b) && bit(x, b) != bit(y, b)).count();
360 // Mean Hamming distance over the 254 free bits: 127 expected, with a
361 // standard error of about 8/√K ≈ 0.4.
362 let mean = |pairs: &dyn Fn(usize) -> usize| (0..K).map(pairs).sum::<usize>() as f64 / K as f64;
363 let same_key = mean(&|i| dist(&t1[i], &t2[i]));
364 let diff_key = mean(&|i| dist(&t1[i], &t2[(i + 1) % K]));
365 let vs_pub = mean(&|i| dist(&t1[i], &pk[i]));
366 for (name, v) in [("same key", same_key), ("different keys", diff_key), ("tag vs key", vs_pub)] {
367 req!(((v - 127.0).abs() < 3.0), true, "{} mean distance {}", name, v);
368 }
369 req!(((same_key - diff_key).abs() < 3.0), true, "linking gap {} vs {}", same_key, diff_key);
370 // Per-bit agreement between the two scopes: K/2 expected, standard
371 // deviation √K/2 = 10; 5 deviations allowed across 254 bits.
372 for b in (0..256).filter(|&b| free_bit(b)) {
373 let agree = (0..K).filter(|&i| bit(&t1[i], b) == bit(&t2[i], b)).count() as f64;
374 req!(((agree - K as f64 / 2.0).abs() < 50.0), true, "bit {} agrees {} times", b, agree);
375 }
376 Ok(())
377}
378
379// ── Sizes and threads ───────────────────────────────────────────────────────
380
381#[test]
382fn test_sizes_at_scale() -> Outcome<()> {
383 for (n, m, len) in [
384 (256usize, 2usize, 1_313usize),
385 (100_000, 5, 2_945),
386 (1_000_000, 5, 2_945),
387 (10_000_000, 6, 3_489),
388 ] {
389 req!(linkring::digits(n), m, "digits({})", n);
390 req!(linkring::body_len(m), len, "body_len({})", m);
391 }
392 Ok(())
393}
394
395#[test]
396fn test_threads_agree() -> Outcome<()> {
397 let (keys, ring) = res!(ring_of(1100, "threads"));
398 let list: Vec<u8> = ring.keys().concat();
399 let ring4 = res!(Ring::from_list_par(&list, 4));
400 req!(ring4.digest(), ring.digest());
401 let (tag, body) = res!(linkring::sign(&ring, &keys[1099], b"s", b"m"));
402 req!(res!(linkring::verify_par(&ring4, b"s", b"m", &tag, &body, 4)), true, "4 threads");
403 req!(res!(linkring::verify_par(&ring4, b"s", b"x", &tag, &body, 4)), false, "4 threads, bad msg");
404 Ok(())
405}