1use alloc::{vec, vec::Vec};
4use core::marker::PhantomData;
5use dcrypt_algorithms::hash::HashFunction;
6use dcrypt_algorithms::mac::hmac::Hmac;
7use dcrypt_api::{error::Error as ApiError, Result as ApiResult, ZeroizingBytes};
8use dcrypt_internal::{boxed_bytes_zeroed, Choice, Zeroize, Zeroizing};
9
10fn nonce_error(_message: &'static str) -> ApiError {
11 ApiError::InvalidParameter {
12 context: "RFC 6979 nonce generation",
13 #[cfg(feature = "std")]
14 message: _message.into(),
15 }
16}
17
18fn hmac_parts<H: HashFunction + Clone>(key: &[u8], parts: &[&[u8]]) -> ApiResult<ZeroizingBytes> {
19 let mut mac = Hmac::<H>::new(key).map_err(ApiError::from)?;
20 for part in parts {
21 mac.update(part).map_err(ApiError::from)?;
22 }
23 mac.finalize().map_err(ApiError::from)
24}
25
26fn replace_zeroized(destination: &mut ZeroizingBytes, replacement: ZeroizingBytes) {
27 *destination = replacement;
28}
29
30fn subtract_be(value: &mut [u8], modulus: &[u8]) {
31 let mut borrow = 0u16;
32 for index in (0..value.len()).rev() {
33 let difference = value[index] as i16 - modulus[index] as i16 - borrow as i16;
34 if difference < 0 {
35 value[index] = (difference + 256) as u8;
36 borrow = 1;
37 } else {
38 value[index] = difference as u8;
39 borrow = 0;
40 }
41 }
42}
43
44fn shift_right_be(value: &mut [u8], shift: usize) {
45 debug_assert!(shift < 8);
46 if shift == 0 {
47 return;
48 }
49 let mut carry = 0u8;
50 for byte in value {
51 let next_carry = *byte << (8 - shift);
52 *byte = (*byte >> shift) | carry;
53 carry = next_carry;
54 }
55}
56
57fn bits2int(input: &[u8], qlen: usize, rolen: usize) -> ApiResult<ZeroizingBytes> {
59 if qlen == 0 || rolen == 0 || qlen > rolen * 8 || qlen <= (rolen - 1) * 8 {
60 return Err(nonce_error("invalid subgroup-order bit length"));
61 }
62
63 let mut output = Zeroizing::new(boxed_bytes_zeroed(rolen));
64 if input.len() >= rolen {
65 output.copy_from_slice(&input[..rolen]);
66 shift_right_be(&mut output, rolen * 8 - qlen);
67 } else {
68 output[rolen - input.len()..].copy_from_slice(input);
69 }
70 Ok(output)
71}
72
73pub(crate) fn bits2octets(hash: &[u8], order: &[u8], qlen: usize) -> ApiResult<ZeroizingBytes> {
75 let rolen = order.len();
76 let mut output = bits2int(hash, qlen, rolen)?;
77 if &output[..] >= order {
78 subtract_be(&mut output, order);
79 }
80 Ok(output)
81}
82
83fn ct_valid_nonce(candidate: &[u8], order: &[u8]) -> Choice {
84 if candidate.len() != order.len() {
85 return Choice::from(0);
86 }
87
88 let mut nonzero = 0u8;
89 let mut less = 0u8;
90 let mut greater = 0u8;
91 for (&candidate_byte, &order_byte) in candidate.iter().zip(order) {
92 nonzero |= candidate_byte;
93 let undecided = (less | greater) ^ 1;
94 let byte_less = ((candidate_byte as u16).wrapping_sub(order_byte as u16) >> 15) as u8;
95 let byte_greater = ((order_byte as u16).wrapping_sub(candidate_byte as u16) >> 15) as u8;
96 less |= byte_less & undecided;
97 greater |= byte_greater & undecided;
98 }
99
100 let is_nonzero = ((nonzero | nonzero.wrapping_neg()) >> 7) & 1;
101 Choice::from(is_nonzero & less)
102}
103
104pub(crate) struct Rfc6979<H> {
110 k: ZeroizingBytes,
111 v: ZeroizingBytes,
112 order: Vec<u8>,
113 qlen: usize,
114 candidate_was_returned: bool,
115 hash: PhantomData<H>,
116}
117
118impl<H: HashFunction + Clone> Rfc6979<H> {
119 pub(crate) fn new(
120 secret_scalar: &[u8],
121 message_hash: &[u8],
122 order: &[u8],
123 qlen: usize,
124 ) -> ApiResult<Self> {
125 if secret_scalar.len() != order.len() || !bool::from(ct_valid_nonce(secret_scalar, order)) {
126 return Err(nonce_error("secret scalar is not canonical"));
127 }
128 let mut h1 = bits2octets(message_hash, order, qlen)?;
129 let output_len = H::output_size();
130 if output_len == 0 {
131 return Err(nonce_error("hash output is empty"));
132 }
133
134 let mut k = Zeroizing::new(boxed_bytes_zeroed(output_len));
135 let mut v = Zeroizing::new(boxed_bytes_zeroed(output_len));
136 v.fill(1);
137 let initialization = (|| -> ApiResult<()> {
138 let next_k = hmac_parts::<H>(&k, &[&v, &[0], secret_scalar, &h1])?;
139 replace_zeroized(&mut k, next_k);
140 let next_v = hmac_parts::<H>(&k, &[&v])?;
141 replace_zeroized(&mut v, next_v);
142 let next_k = hmac_parts::<H>(&k, &[&v, &[1], secret_scalar, &h1])?;
143 replace_zeroized(&mut k, next_k);
144 let next_v = hmac_parts::<H>(&k, &[&v])?;
145 replace_zeroized(&mut v, next_v);
146 Ok(())
147 })();
148 h1.zeroize();
149 if let Err(error) = initialization {
150 k.zeroize();
151 v.zeroize();
152 return Err(error);
153 }
154 Ok(Self {
155 k,
156 v,
157 order: order.to_vec(),
158 qlen,
159 candidate_was_returned: false,
160 hash: PhantomData,
161 })
162 }
163
164 fn retry_step(&mut self) -> ApiResult<()> {
165 let next_k = hmac_parts::<H>(&self.k, &[&self.v, &[0]])?;
166 replace_zeroized(&mut self.k, next_k);
167 let next_v = hmac_parts::<H>(&self.k, &[&self.v])?;
168 replace_zeroized(&mut self.v, next_v);
169 Ok(())
170 }
171
172 pub(crate) fn next_nonce(&mut self) -> ApiResult<ZeroizingBytes> {
173 if self.candidate_was_returned {
174 self.retry_step()?;
175 self.candidate_was_returned = false;
176 }
177
178 loop {
179 let mut t = Zeroizing::new(boxed_bytes_zeroed(self.order.len()));
180 let mut written = 0;
181 while written < self.order.len() {
182 let next_v = hmac_parts::<H>(&self.k, &[&self.v])?;
183 replace_zeroized(&mut self.v, next_v);
184 let needed = self.order.len() - written;
185 let take = core::cmp::min(needed, self.v.len());
186 t[written..written + take].copy_from_slice(&self.v[..take]);
187 written += take;
188 }
189
190 let mut candidate = bits2int(&t, self.qlen, self.order.len())?;
191 if bool::from(ct_valid_nonce(&candidate, &self.order)) {
192 self.candidate_was_returned = true;
193 return Ok(candidate);
194 }
195 candidate.zeroize();
196 self.retry_step()?;
197 }
198 }
199}
200
201impl<H> Drop for Rfc6979<H> {
202 fn drop(&mut self) {
203 self.k.zeroize();
204 self.v.zeroize();
205 self.order.zeroize();
206 self.qlen.zeroize();
207 self.candidate_was_returned.zeroize();
208 }
209}
210
211pub(crate) fn is_high_s(s: &[u8], order: &[u8]) -> bool {
216 if s.len() != order.len() {
217 return true;
218 }
219 let mut carry = 0u8;
220 for (&scalar_byte, &order_byte) in s.iter().zip(order) {
221 let half_order_byte = (order_byte >> 1) | (carry << 7);
222 let next_carry = order_byte & 1;
223 if scalar_byte != half_order_byte {
224 return scalar_byte > half_order_byte;
225 }
226 carry = next_carry;
227 }
228 false
229}
230
231pub(crate) fn is_canonical_nonzero_scalar(value: &[u8], order: &[u8]) -> bool {
235 value.len() == order.len() && value.iter().any(|&byte| byte != 0) && value < order
236}
237
238#[derive(Clone, Debug)]
240pub struct SignatureComponents {
241 pub r: Vec<u8>,
242 pub s: Vec<u8>,
243}
244
245impl SignatureComponents {
246 pub fn to_der(&self) -> Vec<u8> {
248 let mut der = Vec::new();
250
251 der.push(0x30);
253
254 let r_bytes = self.encode_integer(&self.r);
255 let s_bytes = self.encode_integer(&self.s);
256
257 let mut sequence = Vec::with_capacity(2 + r_bytes.len() + 2 + s_bytes.len());
258 sequence.push(0x02); Self::encode_length(&mut sequence, r_bytes.len());
260 sequence.extend_from_slice(&r_bytes);
261
262 sequence.push(0x02); Self::encode_length(&mut sequence, s_bytes.len());
264 sequence.extend_from_slice(&s_bytes);
265
266 Self::encode_length(&mut der, sequence.len());
267 der.extend_from_slice(&sequence);
268 der
269 }
270
271 pub fn from_der(der: &[u8]) -> ApiResult<Self> {
273 if der.len() < 2 {
274 return Err(ApiError::InvalidSignature {
275 context: "ECDSA DER parsing",
276 #[cfg(feature = "std")]
277 message: "DER signature too short".to_string(),
278 });
279 }
280
281 if der[0] != 0x30 {
283 return Err(ApiError::InvalidSignature {
284 context: "ECDSA DER parsing",
285 #[cfg(feature = "std")]
286 message: "Invalid DER SEQUENCE tag".to_string(),
287 });
288 }
289
290 let (seq_len, mut pos) = Self::parse_length(der, 1)?;
291 let seq_end = pos
292 .checked_add(seq_len)
293 .ok_or_else(|| ApiError::InvalidSignature {
294 context: "ECDSA DER parsing",
295 #[cfg(feature = "std")]
296 message: "DER sequence length overflow".to_string(),
297 })?;
298
299 if seq_end != der.len() {
300 return Err(ApiError::InvalidSignature {
301 context: "ECDSA DER parsing",
302 #[cfg(feature = "std")]
303 message: "DER sequence length mismatch".to_string(),
304 });
305 }
306
307 let r = Self::parse_integer(der, &mut pos, "r")?;
308 let s = Self::parse_integer(der, &mut pos, "s")?;
309
310 if pos != seq_end {
311 return Err(ApiError::InvalidSignature {
312 context: "ECDSA DER parsing",
313 #[cfg(feature = "std")]
314 message: "Trailing data after ECDSA signature".to_string(),
315 });
316 }
317
318 Ok(SignatureComponents {
319 r: Self::decode_integer(&r),
320 s: Self::decode_integer(&s),
321 })
322 }
323
324 fn encode_integer(&self, bytes: &[u8]) -> Vec<u8> {
326 let mut start = 0usize;
327 while start + 1 < bytes.len() && bytes[start] == 0x00 {
328 start += 1;
329 }
330
331 let trimmed = if bytes.is_empty() {
332 &[0x00][..]
333 } else {
334 &bytes[start..]
335 };
336
337 if trimmed[0] & 0x80 == 0 {
338 trimmed.to_vec()
339 } else {
340 let mut result = vec![0x00];
341 result.extend_from_slice(trimmed);
342 result
343 }
344 }
345
346 fn decode_integer(bytes: &[u8]) -> Vec<u8> {
348 let mut result = bytes.to_vec();
349 while result.len() > 1 && result[0] == 0x00 {
350 result.remove(0);
351 }
352 result
353 }
354
355 fn encode_length(out: &mut Vec<u8>, len: usize) {
356 if len < 0x80 {
357 out.push(len as u8);
358 return;
359 }
360
361 let mut buf = [0u8; core::mem::size_of::<usize>()];
362 let mut written = 0usize;
363 let mut value = len;
364
365 while value > 0 {
366 buf[buf.len() - 1 - written] = (value & 0xFF) as u8;
367 value >>= 8;
368 written += 1;
369 }
370
371 out.push(0x80 | written as u8);
372 out.extend_from_slice(&buf[buf.len() - written..]);
373 }
374
375 fn parse_length(der: &[u8], pos: usize) -> ApiResult<(usize, usize)> {
376 let first = *der.get(pos).ok_or_else(|| ApiError::InvalidSignature {
377 context: "ECDSA DER parsing",
378 #[cfg(feature = "std")]
379 message: "Missing DER length".to_string(),
380 })?;
381
382 if first & 0x80 == 0 {
383 return Ok((first as usize, pos + 1));
384 }
385
386 let num_len_bytes = (first & 0x7F) as usize;
387 if num_len_bytes == 0 {
388 return Err(ApiError::InvalidSignature {
389 context: "ECDSA DER parsing",
390 #[cfg(feature = "std")]
391 message: "Indefinite DER lengths are not allowed".to_string(),
392 });
393 }
394 if num_len_bytes > core::mem::size_of::<usize>() {
395 return Err(ApiError::InvalidSignature {
396 context: "ECDSA DER parsing",
397 #[cfg(feature = "std")]
398 message: "DER length is too large".to_string(),
399 });
400 }
401
402 let len_end = pos + 1 + num_len_bytes;
403 let len_bytes = der
404 .get(pos + 1..len_end)
405 .ok_or_else(|| ApiError::InvalidSignature {
406 context: "ECDSA DER parsing",
407 #[cfg(feature = "std")]
408 message: "Truncated DER length".to_string(),
409 })?;
410
411 if len_bytes.first() == Some(&0x00) {
412 return Err(ApiError::InvalidSignature {
413 context: "ECDSA DER parsing",
414 #[cfg(feature = "std")]
415 message: "DER length must use minimal encoding".to_string(),
416 });
417 }
418
419 let mut len = 0usize;
420 for &byte in len_bytes {
421 len = len
422 .checked_shl(8)
423 .ok_or_else(|| ApiError::InvalidSignature {
424 context: "ECDSA DER parsing",
425 #[cfg(feature = "std")]
426 message: "DER length overflow".to_string(),
427 })?;
428 len |= byte as usize;
429 }
430
431 if len < 0x80 {
432 return Err(ApiError::InvalidSignature {
433 context: "ECDSA DER parsing",
434 #[cfg(feature = "std")]
435 message: "DER length must use short form".to_string(),
436 });
437 }
438
439 Ok((len, len_end))
440 }
441
442 fn parse_integer(der: &[u8], pos: &mut usize, _name: &'static str) -> ApiResult<Vec<u8>> {
443 let tag = *der.get(*pos).ok_or_else(|| ApiError::InvalidSignature {
444 context: "ECDSA DER parsing",
445 #[cfg(feature = "std")]
446 message: format!("Missing DER INTEGER tag for {_name}"),
447 })?;
448 if tag != 0x02 {
449 return Err(ApiError::InvalidSignature {
450 context: "ECDSA DER parsing",
451 #[cfg(feature = "std")]
452 message: format!("Invalid DER INTEGER tag for {_name}"),
453 });
454 }
455 *pos += 1;
456
457 let (len, next_pos) = Self::parse_length(der, *pos)?;
458 *pos = next_pos;
459 if len == 0 {
460 return Err(ApiError::InvalidSignature {
461 context: "ECDSA DER parsing",
462 #[cfg(feature = "std")]
463 message: format!("DER INTEGER {_name} cannot be empty"),
464 });
465 }
466
467 let int_end = pos
468 .checked_add(len)
469 .ok_or_else(|| ApiError::InvalidSignature {
470 context: "ECDSA DER parsing",
471 #[cfg(feature = "std")]
472 message: format!("DER INTEGER {_name} length overflow"),
473 })?;
474
475 let value = der
476 .get(*pos..int_end)
477 .ok_or_else(|| ApiError::InvalidSignature {
478 context: "ECDSA DER parsing",
479 #[cfg(feature = "std")]
480 message: format!("Truncated DER INTEGER {_name}"),
481 })?;
482
483 if value[0] & 0x80 != 0 {
487 return Err(ApiError::InvalidSignature {
488 context: "ECDSA DER parsing",
489 #[cfg(feature = "std")]
490 message: format!("DER INTEGER {_name} must not be negative"),
491 });
492 }
493
494 if value.len() > 1 && value[0] == 0x00 && value[1] & 0x80 == 0 {
495 return Err(ApiError::InvalidSignature {
496 context: "ECDSA DER parsing",
497 #[cfg(feature = "std")]
498 message: format!("DER INTEGER {_name} is not minimally encoded"),
499 });
500 }
501
502 *pos = int_end;
503 Ok(value.to_vec())
504 }
505}
506
507#[cfg(test)]
508mod tests {
509 use super::*;
510 use dcrypt_algorithms::hash::sha2::{Sha224, Sha256, Sha384, Sha512};
511
512 fn rfc6979_vector<H: HashFunction + Clone>(
513 secret_hex: &str,
514 order_hex: &str,
515 qlen: usize,
516 expected_nonce_hex: &str,
517 ) {
518 let secret = hex::decode(secret_hex).unwrap();
519 let order = hex::decode(order_hex).unwrap();
520 let digest = H::digest(b"sample").unwrap();
521 let mut generator = Rfc6979::<H>::new(&secret, digest.as_ref(), &order, qlen).unwrap();
522 let nonce = generator.next_nonce().unwrap();
523 let expected = hex::decode(expected_nonce_hex).unwrap();
524 assert_eq!(nonce.as_slice(), expected.as_slice());
525 }
526
527 #[test]
528 fn rfc6979_prime_curve_nonce_vectors() {
529 rfc6979_vector::<Sha256>(
531 "6FAB034934E4C0FC9AE67F5B5659A9D7D1FEFD187EE09FD4",
532 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831",
533 192,
534 "32B1B6D7D42A05CB449065727A84804FB1A3E34D8F261496",
535 );
536 rfc6979_vector::<Sha224>(
537 "F220266E1105BFE3083E03EC7A3A654651F45E37167E88600BF257C1",
538 "FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D",
539 224,
540 "C1D1F2F10881088301880506805FEB4825FE09ACB6816C36991AA06D",
541 );
542 rfc6979_vector::<Sha256>(
543 "C9AFA9D845BA75166B5C215767B1D6934E50C3DB36E89B127B8A622B120F6721",
544 "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551",
545 256,
546 "A6E3C57DD01ABE90086538398355DD4C3B17AA873382B0F24D6129493D8AAD60",
547 );
548 rfc6979_vector::<Sha384>(
549 concat!(
550 "6B9D3DAD2E1B8C1C05B19875B6659F4DE23C3B667BF297BA9AA47740787137D8",
551 "96D5724E4C70A825F872C9EA60D2EDF5"
552 ),
553 concat!(
554 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF",
555 "581A0DB248B0A77AECEC196ACCC52973"
556 ),
557 384,
558 concat!(
559 "94ED910D1A099DAD3254E9242AE85ABDE4BA15168EAF0CA87A555FD56D10FBCA",
560 "2907E3E83BA95368623B8C4686915CF9"
561 ),
562 );
563 rfc6979_vector::<Sha512>(
564 concat!(
565 "00FAD06DAA62BA3B25D2FB40133DA757205DE67F5BB0018FEE8C86E1B68C7E75C",
566 "AA896EB32F1F47C70855836A6D16FCC1466F6D8FBEC67DB89EC0C08B0E996B83",
567 "538"
568 ),
569 concat!(
570 "01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
571 "FA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386",
572 "409"
573 ),
574 521,
575 concat!(
576 "01DAE2EA071F8110DC26882D4D5EAE0621A3256FC8847FB9022E2B7D28E6F1019",
577 "8B1574FDD03A9053C08A1854A168AA5A57470EC97DD5CE090124EF52A2F7ECBF",
578 "FD3"
579 ),
580 );
581 }
582
583 #[test]
584 fn canonical_scalar_check_rejects_zero_order_and_larger_values() {
585 let order = [0x01, 0x00];
586 assert!(is_canonical_nonzero_scalar(&[0x00, 0xff], &order));
587 assert!(!is_canonical_nonzero_scalar(&[0x00, 0x00], &order));
588 assert!(!is_canonical_nonzero_scalar(&order, &order));
589 assert!(!is_canonical_nonzero_scalar(&[0x01, 0x01], &order));
590 assert!(!is_canonical_nonzero_scalar(&[0xff], &order));
591 }
592
593 #[test]
594 fn test_der_encoding() {
595 let sig = SignatureComponents {
596 r: vec![0x01, 0x23, 0x45, 0x67],
597 s: vec![0x89, 0xAB, 0xCD, 0xEF],
598 };
599
600 let der = sig.to_der();
601 let parsed = SignatureComponents::from_der(&der).unwrap();
602
603 assert_eq!(sig.r, parsed.r);
604 assert_eq!(sig.s, parsed.s);
605 }
606
607 #[test]
608 fn test_der_with_high_bit() {
609 let sig = SignatureComponents {
611 r: vec![0xFF, 0x23, 0x45, 0x67],
612 s: vec![0x79, 0xAB, 0xCD, 0xEF],
613 };
614
615 let der = sig.to_der();
616
617 assert_eq!(der[3], 5); assert_eq!(der[4], 0x00); assert_eq!(der[5], 0xFF); let parsed = SignatureComponents::from_der(&der).unwrap();
624 assert_eq!(sig.r, parsed.r);
625 assert_eq!(sig.s, parsed.s);
626 }
627
628 #[test]
629 fn test_der_long_form_sequence_length_roundtrip() {
630 let sig = SignatureComponents {
631 r: vec![0x7F; 66],
632 s: vec![0x80; 66],
633 };
634
635 let der = sig.to_der();
636 assert_eq!(der[0], 0x30);
637 assert_eq!(der[1], 0x81);
638
639 let parsed = SignatureComponents::from_der(&der).unwrap();
640 assert_eq!(sig.r, parsed.r);
641 assert_eq!(sig.s, parsed.s);
642 }
643
644 #[test]
645 fn test_der_rejects_truncated_lengths_without_panicking() {
646 let malformed = [0x30, 0x06, 0x02, 0x02, 0x01];
647 assert!(SignatureComponents::from_der(&malformed).is_err());
648 }
649
650 #[test]
651 fn test_der_rejects_trailing_bytes() {
652 let der = [0x30, 0x08, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01, 0x00, 0x00];
653 assert!(SignatureComponents::from_der(&der).is_err());
654 }
655
656 #[test]
657 fn test_der_rejects_negative_integers() {
658 let negative_r = [0x30, 0x06, 0x02, 0x01, 0x80, 0x02, 0x01, 0x01];
659 let negative_s = [0x30, 0x06, 0x02, 0x01, 0x01, 0x02, 0x01, 0xff];
660 assert!(SignatureComponents::from_der(&negative_r).is_err());
661 assert!(SignatureComponents::from_der(&negative_s).is_err());
662 }
663}