1use k256::{
8 ProjectivePoint, Scalar, U256,
9 ecdsa::{
10 RecoveryId, Signature as EcdsaSignature, VerifyingKey, signature::hazmat::PrehashVerifier,
11 },
12 elliptic_curve::{ops::Reduce, point::AffineCoordinates, scalar::IsHigh},
13};
14use rand_core::CryptoRng;
15
16use crate::{
17 curve::{decode_scalar, encode_point, encode_scalar},
18 error::{Error, Result},
19 hd::HdPath,
20 params::Params,
21 ssid::Ssid,
22 transcript::Transcript,
23};
24
25pub mod client;
26pub mod server;
27
28pub use client::ClientSign;
29pub use server::{ServerSign0, ServerSign1};
30
31#[derive(Clone, Copy, Debug, PartialEq, Eq)]
33pub struct Signature {
34 pub r: Scalar,
35 pub s: Scalar,
36 pub recid: u8,
38}
39
40impl Signature {
41 pub fn to_bytes(&self) -> [u8; 64] {
43 let mut out = [0u8; 64];
44 out[..32].copy_from_slice(&encode_scalar(&self.r));
45 out[32..].copy_from_slice(&encode_scalar(&self.s));
46 out
47 }
48
49 pub fn to_ecdsa(&self) -> Result<EcdsaSignature> {
50 EcdsaSignature::from_scalars(self.r, self.s).map_err(|_| Error::InvalidEncoding)
51 }
52
53 pub fn recovery_id(&self) -> Result<RecoveryId> {
54 RecoveryId::from_byte(self.recid).ok_or(Error::InvalidEncoding)
55 }
56}
57
58pub(crate) fn digest_scalar(digest: &[u8; 32]) -> Scalar {
60 <Scalar as Reduce<U256>>::reduce(&U256::from_be_slice(digest))
61}
62
63pub(crate) fn check_digest(digest: &[u8; 32]) -> Result<()> {
66 if bool::from(k256::elliptic_curve::Field::is_zero(&digest_scalar(digest))) {
67 return Err(Error::InvalidEncoding);
68 }
69 Ok(())
70}
71
72pub(crate) fn signing_key(
75 x_pub: &ProjectivePoint,
76 hd: Option<&HdPath>,
77) -> Result<(ProjectivePoint, Scalar)> {
78 match hd {
79 None => Ok((*x_pub, Scalar::ZERO)),
80 Some(h) => {
81 let delta = h.delta(x_pub)?;
82 Ok((*x_pub + ProjectivePoint::GENERATOR * delta, delta))
83 }
84 }
85}
86
87pub(crate) fn tx_base(params: &Params, ssid: &Ssid, role: &str) -> Transcript {
89 let mut t = Transcript::new("sign");
90 t.append("params_id", &[params.id as u8]);
91 t.append("ssid", &ssid.encode());
92 t.append("role", role.as_bytes());
93 t
94}
95
96pub(crate) fn nonce_challenge(
98 params: &Params,
99 ssid: &Ssid,
100 x_pub: &ProjectivePoint,
101 r1: &ProjectivePoint,
102 r: &ProjectivePoint,
103 digest: &[u8; 32],
104) -> Scalar {
105 let mut t = Transcript::new("ro/sign-nonce");
106 t.append("params_id", &[params.id as u8]);
107 t.append("ssid", &ssid.encode());
108 t.append("X", &encode_point(x_pub));
109 t.append("R1", &encode_point(r1));
110 t.append("R", &encode_point(r));
111 t.append("m", digest);
112 t.challenge("e").scalar()
113}
114
115pub(crate) fn hedged_nonce<R: CryptoRng + ?Sized>(
117 rng: &mut R,
118 label: &str,
119 secret: &Scalar,
120 context: &[u8],
121) -> Scalar {
122 let mut fresh = [0u8; 32];
123 for i in 0u32.. {
124 rng.fill_bytes(&mut fresh);
125 let mut t = Transcript::new("hedged-nonce");
126 t.append("label", label.as_bytes());
127 t.append("rng", &fresh);
128 t.append("secret", &encode_scalar(secret));
129 t.append("ctx", context);
130 t.append("ctr", &i.to_be_bytes());
131 let k = t.challenge("k").scalar();
132 if !bool::from(k256::elliptic_curve::Field::is_zero(&k)) {
133 return k;
134 }
135 }
136 Scalar::ONE
137}
138
139pub(crate) fn ecdsa_verify(
141 x_pub: &ProjectivePoint,
142 digest: &[u8; 32],
143 sig: &Signature,
144) -> Result<()> {
145 let vk = VerifyingKey::from_affine(x_pub.to_affine()).map_err(|_| Error::VerificationFailed)?;
146 vk.verify_prehash(digest, &sig.to_ecdsa()?)
147 .map_err(|_| Error::VerificationFailed)
148}
149
150pub(crate) fn finalize(r_point: &ProjectivePoint, r: Scalar, s: Scalar) -> Signature {
152 let affine = r_point.to_affine();
153 let y_odd: bool = affine.y_is_odd().into();
154 let x_reduced = encode_scalar(&r) != affine.x().as_slice();
155 let mut recid = u8::from(y_odd) | (u8::from(x_reduced) << 1);
156 let mut s = s;
157 if bool::from(s.is_high()) {
158 s = -s;
159 recid ^= 1;
160 }
161 Signature { r, s, recid }
162}
163
164pub(crate) fn decode_signature(r: &[u8], s: &[u8], recid: u8) -> Result<Signature> {
166 let sig = Signature {
167 r: decode_scalar(r)?,
168 s: decode_scalar(s)?,
169 recid,
170 };
171 sig.recovery_id()?;
172 Ok(sig)
173}
174
175#[cfg(test)]
176mod tests {
177 extern crate std;
178 use super::*;
179 use crate::hd::HdPath;
180 use crate::{
181 keygen::{ClientKeyShare, ServerKeyShare},
182 testutil::{fx, keygen, params},
183 };
184 use k256::ecdsa::VerifyingKey;
185 use rand_chacha::ChaCha8Rng;
186 use rand_core::{Rng, SeedableRng};
187 use std::{collections::BTreeSet, time::Instant, vec::Vec};
188
189 fn sign_once(
191 rng: &mut ChaCha8Rng,
192 c: &ClientKeyShare,
193 s: &ServerKeyShare,
194 digest: &[u8; 32],
195 ) -> (Signature, Vec<u8>) {
196 let (s1, m1) =
197 ServerSign0::start(rng, &fx().server_view, s, b"client-1", digest, None).unwrap();
198 let m2 = ClientSign::respond(rng, &fx().setup, c, b"client-1", digest, &m1, None).unwrap();
199 s1.finish(&fx().server_view, fx().sk.paillier_sk(), &m2)
200 .unwrap()
201 }
202
203 fn digest(rng: &mut ChaCha8Rng) -> [u8; 32] {
204 let mut d = [0u8; 32];
205 rng.fill_bytes(&mut d);
206 d
207 }
208
209 #[test]
210 fn honest_signatures_verify_and_recover() {
211 let (c, s) = keygen(21);
212 let mut rng = ChaCha8Rng::seed_from_u64(1);
213 let vk = VerifyingKey::from_affine(c.public_key().to_affine()).unwrap();
214 let mut parities = BTreeSet::new();
215 for _ in 0..40 {
216 let d = digest(&mut rng);
217 let (sig, m3) = sign_once(&mut rng, &c, &s, &d);
218 vk.verify_prehash(&d, &sig.to_ecdsa().unwrap()).unwrap();
220 assert!(!bool::from(sig.s.is_high()));
222 let rec = VerifyingKey::recover_from_prehash(
224 &d,
225 &sig.to_ecdsa().unwrap(),
226 sig.recovery_id().unwrap(),
227 )
228 .unwrap();
229 assert_eq!(rec, vk);
230 assert_eq!(
232 ClientSign::verify_final(¶ms(), &c, &d, &m3, None).unwrap(),
233 sig
234 );
235 parities.insert(sig.recid & 1);
236 }
237 assert_eq!(parities.len(), 2, "both y parities must occur");
238 }
239
240 #[test]
243 fn setup_and_shares_do_not_depend_on_l0() {
244 use crate::{params::Params, setup::SetupData};
245 let (c, s) = keygen(24);
246 let old = Params {
247 ell0: 8,
248 ..params()
249 };
250 let bytes = fx().data.to_bytes().unwrap();
251 let data = SetupData::from_bytes_with(&bytes, &old, &fx().fac).unwrap();
252 assert_eq!(data.hash().unwrap(), fx().data.hash().unwrap());
253 let setup = data.verify_with(&old, &fx().fac).unwrap().with_tables();
254 let server_view = data.assume_verified(&old).unwrap().with_tables();
255 let mut rng = ChaCha8Rng::seed_from_u64(24);
256 let d = digest(&mut rng);
257 let vk = VerifyingKey::from_affine(c.public_key().to_affine()).unwrap();
258 let (s1, m1) =
259 ServerSign0::start(&mut rng, &server_view, &s, b"client-1", &d, None).unwrap();
260 let m2 = ClientSign::respond(&mut rng, &setup, &c, b"client-1", &d, &m1, None).unwrap();
261 let (sig, _) = s1.finish(&server_view, fx().sk.paillier_sk(), &m2).unwrap();
262 vk.verify_prehash(&d, &sig.to_ecdsa().unwrap()).unwrap();
263 }
264
265 #[test]
266 fn same_digest_gives_fresh_nonces() {
267 let (c, s) = keygen(22);
268 let mut rng = ChaCha8Rng::seed_from_u64(2);
269 let d = digest(&mut rng);
270 let (a, _) = sign_once(&mut rng, &c, &s, &d);
271 let (b, _) = sign_once(&mut rng, &c, &s, &d);
272 assert_ne!(a.r, b.r);
273 }
274
275 #[test]
276 fn corrupted_messages_are_rejected() {
277 let (c, s) = keygen(23);
278 let mut rng = ChaCha8Rng::seed_from_u64(3);
279 let d = digest(&mut rng);
280 let (s1, m1) =
281 ServerSign0::start(&mut rng, &fx().server_view, &s, b"client-1", &d, None).unwrap();
282
283 for i in [4usize, 10, 30, 36, 50, m1.len() - 1] {
284 let mut bad = m1.clone();
285 bad[i] ^= 1;
286 assert!(
287 ClientSign::respond(&mut rng, &fx().setup, &c, b"client-1", &d, &bad, None)
288 .is_err(),
289 "msg1 flip {i}"
290 );
291 }
292 let m2 =
293 ClientSign::respond(&mut rng, &fx().setup, &c, b"client-1", &d, &m1, None).unwrap();
294 let positions = [
295 4usize,
296 20,
297 40,
298 80,
299 120,
300 200,
301 400,
302 m2.len() / 2,
303 m2.len() - 60,
304 m2.len() - 1,
305 ];
306 for i in positions.iter().copied().filter(|i| *i < m2.len()) {
307 let mut bad = m2.clone();
308 bad[i] ^= 1;
309 let r = s1
310 .test_clone()
311 .finish(&fx().server_view, fx().sk.paillier_sk(), &bad);
312 assert!(r.is_err(), "msg2 flip {i}");
313 }
314 assert!(
315 s1.test_clone()
316 .finish(
317 &fx().server_view,
318 fx().sk.paillier_sk(),
319 &m2[..m2.len() - 1]
320 )
321 .is_err()
322 );
323 assert!(
324 s1.finish(&fx().server_view, fx().sk.paillier_sk(), &m2)
325 .is_ok()
326 );
327 }
328
329 #[test]
330 fn session_binding() {
331 let (c, s) = keygen(24);
332 let (c_other, _) = keygen(25);
333 let mut rng = ChaCha8Rng::seed_from_u64(4);
334 let (d1, d2) = (digest(&mut rng), digest(&mut rng));
335
336 let (s1, m1) =
338 ServerSign0::start(&mut rng, &fx().server_view, &s, b"client-1", &d1, None).unwrap();
339 let m2 =
340 ClientSign::respond(&mut rng, &fx().setup, &c, b"client-1", &d2, &m1, None).unwrap();
341 assert!(
342 s1.finish(&fx().server_view, fx().sk.paillier_sk(), &m2)
343 .is_err()
344 );
345
346 let (s1, m1) =
348 ServerSign0::start(&mut rng, &fx().server_view, &s, b"client-1", &d1, None).unwrap();
349 let m2 =
350 ClientSign::respond(&mut rng, &fx().setup, &c, b"client-X", &d1, &m1, None).unwrap();
351 assert!(
352 s1.finish(&fx().server_view, fx().sk.paillier_sk(), &m2)
353 .is_err()
354 );
355
356 let (_, m1a) =
358 ServerSign0::start(&mut rng, &fx().server_view, &s, b"client-1", &d1, None).unwrap();
359 let m2a =
360 ClientSign::respond(&mut rng, &fx().setup, &c, b"client-1", &d1, &m1a, None).unwrap();
361 let (s1b, _) =
362 ServerSign0::start(&mut rng, &fx().server_view, &s, b"client-1", &d1, None).unwrap();
363 assert!(
364 s1b.finish(&fx().server_view, fx().sk.paillier_sk(), &m2a)
365 .is_err()
366 );
367
368 let (_, m1) =
370 ServerSign0::start(&mut rng, &fx().server_view, &s, b"client-1", &d1, None).unwrap();
371 assert!(
372 ClientSign::respond(&mut rng, &fx().setup, &c_other, b"client-1", &d1, &m1, None)
373 .is_err()
374 );
375 }
376
377 fn hd(chain: u8, path: &[u32]) -> HdPath {
378 HdPath::new([chain; 32], path.to_vec()).unwrap()
379 }
380
381 #[test]
382 fn hd_signatures_verify_under_the_derived_key_only() {
383 let (c, s) = keygen(28);
384 let mut rng = ChaCha8Rng::seed_from_u64(7);
385 let x = VerifyingKey::from_affine(c.public_key().to_affine()).unwrap();
386 for path in [
387 hd(1, &[0]),
388 hd(2, &[44, 0, 0, 0, 7]),
389 hd(3, &[5, 6, 1_000_000]),
390 ] {
391 let d = digest(&mut rng);
392 let (st, m1) = ServerSign0::start(
393 &mut rng,
394 &fx().server_view,
395 &s,
396 b"client-1",
397 &d,
398 Some(&path),
399 )
400 .unwrap();
401 let m2 =
402 ClientSign::respond(&mut rng, &fx().setup, &c, b"client-1", &d, &m1, Some(&path))
403 .unwrap();
404 let (sig, m3) = st
405 .finish(&fx().server_view, fx().sk.paillier_sk(), &m2)
406 .unwrap();
407
408 let derived = path.delta(c.public_key()).unwrap();
409 let derived_pk = VerifyingKey::from_affine(
410 (*c.public_key() + ProjectivePoint::GENERATOR * derived).to_affine(),
411 )
412 .unwrap();
413 let ecdsa = sig.to_ecdsa().unwrap();
414 derived_pk.verify_prehash(&d, &ecdsa).unwrap();
415 assert!(
416 x.verify_prehash(&d, &ecdsa).is_err(),
417 "must not verify under the master key"
418 );
419 let rec =
420 VerifyingKey::recover_from_prehash(&d, &ecdsa, sig.recovery_id().unwrap()).unwrap();
421 assert_eq!(rec, derived_pk);
422 assert_eq!(
423 ClientSign::verify_final(¶ms(), &c, &d, &m3, Some(&path)).unwrap(),
424 sig
425 );
426 assert!(ClientSign::verify_final(¶ms(), &c, &d, &m3, None).is_err());
427 }
428 }
429
430 #[test]
431 fn hd_paths_must_agree() {
432 let (c, s) = keygen(29);
433 let mut rng = ChaCha8Rng::seed_from_u64(8);
434 let d = digest(&mut rng);
435 let p = hd(1, &[1, 2]);
436 let (_, m1) =
437 ServerSign0::start(&mut rng, &fx().server_view, &s, b"client-1", &d, Some(&p)).unwrap();
438 for other in [Some(hd(1, &[2, 1])), Some(hd(9, &[1, 2])), None] {
440 let r = ClientSign::respond(
441 &mut rng,
442 &fx().setup,
443 &c,
444 b"client-1",
445 &d,
446 &m1,
447 other.as_ref(),
448 );
449 assert!(r.is_err());
450 }
451 let (_, m1) =
453 ServerSign0::start(&mut rng, &fx().server_view, &s, b"client-1", &d, None).unwrap();
454 assert!(
455 ClientSign::respond(&mut rng, &fx().setup, &c, b"client-1", &d, &m1, Some(&p)).is_err()
456 );
457 }
458
459 #[test]
460 fn zero_digest_is_rejected_by_both_sides() {
461 let (c, s) = keygen(27);
462 let mut rng = ChaCha8Rng::seed_from_u64(6);
463 let zero = [0u8; 32];
464 assert!(
465 ServerSign0::start(&mut rng, &fx().server_view, &s, b"client-1", &zero, None).is_err()
466 );
467 let order = crate::curve::order();
469 let mut n = [0u8; 32];
470 let bytes = order.to_be_bytes();
471 n.copy_from_slice(&bytes[bytes.len() - 32..]);
472 assert!(
473 ServerSign0::start(&mut rng, &fx().server_view, &s, b"client-1", &n, None).is_err()
474 );
475 let d = digest(&mut rng);
476 let (_, m1) =
477 ServerSign0::start(&mut rng, &fx().server_view, &s, b"client-1", &d, None).unwrap();
478 assert!(
479 ClientSign::respond(&mut rng, &fx().setup, &c, b"client-1", &zero, &m1, None).is_err()
480 );
481 }
482
483 #[test]
484 fn signmsg3_is_checked_by_the_client() {
485 let (c, s) = keygen(26);
486 let mut rng = ChaCha8Rng::seed_from_u64(5);
487 let d = digest(&mut rng);
488 let (sig, m3) = sign_once(&mut rng, &c, &s, &d);
489 let p = params();
490 assert!(ClientSign::verify_final(&p, &c, &digest(&mut rng), &m3, None).is_err());
491 let mut bad = m3.clone();
492 let n = bad.len();
493 bad[n - 5] ^= 1; assert!(ClientSign::verify_final(&p, &c, &d, &bad, None).is_err());
495 let wrong_recid = crate::messages::SignMsg3 {
496 r: encode_scalar(&sig.r).to_vec(),
497 s: encode_scalar(&sig.s).to_vec(),
498 recid: sig.recid ^ 1,
499 }
500 .encode(&p)
501 .unwrap();
502 assert!(ClientSign::verify_final(&p, &c, &d, &wrong_recid, None).is_err());
503 }
504
505 #[test]
506 #[ignore = "long: run with --release --ignored; N from TECDSA_SIGN_COUNT (default 10000)"]
507 fn many_signatures_reduced() {
508 let n: usize = std::env::var("TECDSA_SIGN_COUNT")
509 .ok()
510 .and_then(|v| v.parse().ok())
511 .unwrap_or(10_000);
512 let (c, s) = keygen(30);
513 let vk = VerifyingKey::from_affine(c.public_key().to_affine()).unwrap();
514 let mut rng = ChaCha8Rng::seed_from_u64(30);
515 let t = Instant::now();
516 for _ in 0..n {
517 let d = digest(&mut rng);
518 let (sig, _) = sign_once(&mut rng, &c, &s, &d);
519 vk.verify_prehash(&d, &sig.to_ecdsa().unwrap()).unwrap();
520 let rec = VerifyingKey::recover_from_prehash(
521 &d,
522 &sig.to_ecdsa().unwrap(),
523 sig.recovery_id().unwrap(),
524 )
525 .unwrap();
526 assert_eq!(rec, vk);
527 }
528 std::eprintln!("{n} signatures in {:?}", t.elapsed());
529 }
530
531 #[test]
532 #[ignore = "full-size: run with --release --ignored --nocapture"]
533 fn full_size_sign() {
534 use crate::{params::PARAMS_128, setup::server_setup};
535 let p = PARAMS_128;
536 let mut rng = ChaCha8Rng::seed_from_u64(77);
537 let (data, sk) = server_setup(&mut rng, &p, [1u8; 32], b"server").unwrap();
538 let client_view = data.verify(&p).unwrap().with_tables();
539 let server_view = data.assume_verified(&p).unwrap().with_tables();
540 std::eprintln!("tables: {} KiB", client_view.tables_size_bytes() / 1024);
541 let clock = crate::testutil::TestClock(core::cell::Cell::new(0));
542 let (s1, m1) = crate::keygen::ServerKeygen0::start(&mut rng, &p, &data, b"client").unwrap();
543 let (c1, m2) =
544 crate::keygen::ClientKeygen0::on_msg1(&mut rng, &clock, &client_view, b"client", &m1)
545 .unwrap();
546 let (s_share, m3) = s1.on_msg2(&mut rng, &m2).unwrap();
547 let c_share = c1.on_msg3(&clock, &m3).unwrap();
548 let (mut tc, mut ts1, mut ts3) = (Vec::new(), Vec::new(), Vec::new());
549 let mut size2 = 0;
550 let count: usize = std::env::var("TECDSA_FULL_SIGN_COUNT")
551 .ok()
552 .and_then(|v| v.parse().ok())
553 .unwrap_or(20);
554 for _ in 0..count {
555 let d = digest(&mut rng);
556 let t = Instant::now();
557 let (st, m1) =
558 ServerSign0::start(&mut rng, &server_view, &s_share, b"client", &d, None).unwrap();
559 ts1.push(t.elapsed());
560 let t = Instant::now();
561 let m2 =
562 ClientSign::respond(&mut rng, &client_view, &c_share, b"client", &d, &m1, None)
563 .unwrap();
564 tc.push(t.elapsed());
565 size2 = m2.len();
566 let t = Instant::now();
567 let (sig, _) = st.finish(&server_view, sk.paillier_sk(), &m2).unwrap();
568 ts3.push(t.elapsed());
569 let vk = VerifyingKey::from_affine(c_share.public_key().to_affine()).unwrap();
570 vk.verify_prehash(&d, &sig.to_ecdsa().unwrap()).unwrap();
571 }
572 let med = |v: &mut Vec<core::time::Duration>| {
573 v.sort();
574 v[v.len() / 2]
575 };
576 std::eprintln!(
577 "sign (median of {count}): S1 {:?} | client {:?} (SignMsg2 {size2} B) | S3 {:?}",
578 med(&mut ts1),
579 med(&mut tc),
580 med(&mut ts3)
581 );
582 }
583}