fn_dsa_comm/lib.rs
1#![no_std]
2
3//! This crate contains utility functions which are used by FN-DSA for
4//! key pair generation, signing, and verifying. It is not meant to
5//! be used directly.
6
7/// Encoding/decoding primitives.
8pub mod codec;
9
10/// Computations with polynomials modulo X^n+1 and modulo q = 12289.
11pub mod mq;
12
13/// SHAKE implementation.
14pub mod shake;
15
16/// Specialized versions of `mq` which use AVX2 opcodes (on x86 CPUs).
17#[cfg(all(not(feature = "no_avx2"),
18 any(target_arch = "x86_64", target_arch = "x86")))]
19pub mod mq_avx2;
20
21// Re-export RNG traits to get a smooth dependency management.
22pub use rand_core::{CryptoRng, RngCore, Error as RngError};
23
24/// Symbolic constant for FN-DSA with degree 512 (`logn = 9`).
25pub const FN_DSA_LOGN_512: u32 = 9;
26
27/// Symbolic constant for FN-DSA with degree 1024 (`logn = 10`).
28pub const FN_DSA_LOGN_1024: u32 = 10;
29
30/// Get the size (in bytes) of a signing key for the provided degree
31/// (degree is `n = 2^logn`, with `2 <= logn <= 10`).
32pub const fn sign_key_size(logn: u32) -> usize {
33 let n = 1usize << logn;
34 let nbits_fg = match logn {
35 2..=5 => 8,
36 6..=7 => 7,
37 8..=9 => 6,
38 _ => 5,
39 };
40 1 + (nbits_fg << (logn - 2)) + n
41}
42
43/// Get the size (in bytes) of a verifying key for the provided degree
44/// (degree is `n = 2^logn`, with `2 <= logn <= 10`).
45pub const fn vrfy_key_size(logn: u32) -> usize {
46 1 + (7 << (logn - 2))
47}
48
49/// Get the size (in bytes) of a signature for the provided degree
50/// (degree is `n = 2^logn`, with `2 <= logn <= 10`).
51pub const fn signature_size(logn: u32) -> usize {
52 // logn n size
53 // 2 4 47
54 // 3 8 52
55 // 4 16 63
56 // 5 32 82
57 // 6 64 122
58 // 7 128 200
59 // 8 256 356
60 // 9 512 666
61 // 10 1024 1280
62 44 + 3 * (256 >> (10 - logn)) + 2 * (128 >> (10 - logn))
63 + 3 * (64 >> (10 - logn)) + 2 * (16 >> (10 - logn))
64 - 2 * (2 >> (10 - logn)) - 8 * (1 >> (10 - logn))
65}
66
67/// The message for which a signature is to be generated or verified is
68/// pre-hashed by the caller and provided as a hash value along with
69/// an identifier of the used hash function. The identifier is normally
70/// an encoded ASN.1 OID. A special identifier is used for "raw" messages
71/// (i.e. not pre-hashed at all); it uses a single byte of value 0x00.
72pub struct HashIdentifier<'a>(pub &'a [u8]);
73
74/// Hash function identifier: none.
75///
76/// This is the identifier used internally to specify that signature
77/// generation and verification are performed over a raw message, without
78/// pre-hashing.
79pub const HASH_ID_RAW: HashIdentifier = HashIdentifier(&[0x00]);
80
81/// Hash function identifier: original Falcon design.
82///
83/// This identifier modifies processing of the input so that it follows
84/// the Falcon scheme as it was submitted for round 3 of the post-quantum
85/// cryptography standardization process. When this identifier is used:
86///
87/// - The message is raw (not pre-hashed).
88/// - The domain separation context is not used.
89/// - The public key hash is not included in the signed data.
90///
91/// Supporting the original Falcon design is an obsolescent feature
92/// that will be removed at the latest when the final FN-DSA standard
93/// is published.
94pub const HASH_ID_ORIGINAL_FALCON: HashIdentifier = HashIdentifier(&[0xFF]);
95
96/// Hash function identifier: SHA-256
97pub const HASH_ID_SHA256: HashIdentifier = HashIdentifier(
98 &[0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01]);
99
100/// Hash function identifier: SHA-384
101pub const HASH_ID_SHA384: HashIdentifier = HashIdentifier(
102 &[0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02]);
103
104/// Hash function identifier: SHA-512
105pub const HASH_ID_SHA512: HashIdentifier = HashIdentifier(
106 &[0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03]);
107
108/// Hash function identifier: SHA-512-256
109pub const HASH_ID_SHA512_256: HashIdentifier = HashIdentifier(
110 &[0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x06]);
111
112/// Hash function identifier: SHA3-256
113pub const HASH_ID_SHA3_256: HashIdentifier = HashIdentifier(
114 &[0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x08]);
115
116/// Hash function identifier: SHA3-384
117pub const HASH_ID_SHA3_384: HashIdentifier = HashIdentifier(
118 &[0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x09]);
119
120/// Hash function identifier: SHA3-512
121pub const HASH_ID_SHA3_512: HashIdentifier = HashIdentifier(
122 &[0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x0A]);
123
124/// Hash function identifier: SHAKE128
125pub const HASH_ID_SHAKE128: HashIdentifier = HashIdentifier(
126 &[0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x0B]);
127
128/// Hash function identifier: SHAKE256
129pub const HASH_ID_SHAKE256: HashIdentifier = HashIdentifier(
130 &[0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x0C]);
131
132/// When a message is signed or verified, it is accompanied with a domain
133/// separation context, which is an arbitrary sequence of bytes of length
134/// at most 255. Such a context is wrapped in a `DomainContext` structure.
135pub struct DomainContext<'a>(pub &'a [u8]);
136
137/// Empty domain separation context.
138pub const DOMAIN_NONE: DomainContext = DomainContext(b"");
139
140/// Hash a message into a polynomial modulo q = 12289.
141///
142/// Parameters are:
143///
144/// - `nonce`: 40-byte random nonce
145/// - `hashed_vrfy_key`: SHAKE256 hash of public (verifying) key (64 bytes)
146/// - `ctx`: domain separation context
147/// - `id`: identifier for pre-hash function
148/// - `hv`: message (pre-hashed)
149/// - `c`: output polynomial
150///
151/// If `id` is `HASH_ID_RAW`, then no-prehashing is applied and the message
152/// itself should be provided as `hv`. Otherwise, the caller is responsible
153/// for applying the pre-hashing, and `hv` shall be the hashed message.
154pub fn hash_to_point(nonce: &[u8], hashed_vrfy_key: &[u8],
155 ctx: &DomainContext, id: &HashIdentifier, hv: &[u8], c: &mut [u16])
156{
157 // TODO: remove support for original Falcon when the final FN-DSA
158 // is defined and has test vectors. Since the message is used "as is",
159 // this encoding can mimic all others, and thus bypasses any attempt at
160 // domain separation. Moreover, ignoring the domain separation context
161 // is a potential source of security issues, since the caller might
162 // expect a strong binding to the context value.
163
164 // Input order:
165 // With pre-hashing:
166 // nonce || hashed_vrfy_key || 0x01 || len(ctx) || ctx || id || hv
167 // Without pre-hashing:
168 // nonce || hashed_vrfy_key || 0x00 || len(ctx) || ctx || message
169 // 'len(ctx)' is the length of the context over one byte (0 to 255).
170
171 assert!(nonce.len() == 40);
172 assert!(hashed_vrfy_key.len() == 64);
173 assert!(ctx.0.len() <= 255);
174 let orig_falcon = id.0.len() == 1 && id.0[0] == 0xFF;
175 let raw_message = id.0.len() == 1 && id.0[0] == 0x00;
176 let mut sh = shake::SHAKE256::new();
177 sh.inject(nonce);
178 if orig_falcon {
179 sh.inject(hv);
180 } else {
181 sh.inject(hashed_vrfy_key);
182 sh.inject(&[if raw_message { 0u8 } else { 1u8 }]);
183 sh.inject(&[ctx.0.len() as u8]);
184 sh.inject(ctx.0);
185 if !raw_message {
186 sh.inject(id.0);
187 }
188 sh.inject(hv);
189 }
190 sh.flip();
191 let mut i = 0;
192 while i < c.len() {
193 let mut v = [0u8; 2];
194 sh.extract(&mut v);
195 let mut w = ((v[0] as u16) << 8) | (v[1] as u16);
196 if w < 61445 {
197 while w >= 12289 {
198 w -= 12289;
199 }
200 c[i] = w;
201 i += 1;
202 }
203 }
204}
205
206/// Trait for a deterministic pseudorandom generator.
207///
208/// The trait `PRNG` characterizes a stateful object that produces
209/// pseudorandom bytes (and larger values) in a cryptographically secure
210/// way; the object is created with a source seed, and the output is
211/// indistinguishable from uniform randomness up to exhaustive enumeration
212/// of the possible values of the seed.
213///
214/// `PRNG` instances must also implement `Copy` and `Clone` so that they
215/// may be embedded in clonable structures. This implies that copying a
216/// `PRNG` instance is supposed to clone its internal state, and the copy
217/// will output the same values as the original.
218pub trait PRNG: Copy + Clone {
219 /// Create a new instance over the provided seed.
220 fn new(seed: &[u8]) -> Self;
221 /// Get the next byte from the PRNG.
222 fn next_u8(&mut self) -> u8;
223 /// Get the 16-bit value from the PRNG.
224 fn next_u16(&mut self) -> u16;
225 /// Get the 64-bit value from the PRNG.
226 fn next_u64(&mut self) -> u64;
227}
228
229#[cfg(all(not(feature = "no_avx2"),
230 any(target_arch = "x86_64", target_arch = "x86")))]
231cpufeatures::new!(cpuid_avx2, "avx2");
232
233/// Do a rutime check for AVX2 support (x86 and x86_64 only).
234///
235/// This is a specialized subcase of the is_x86_feature_detected macro,
236/// except that this function is compatible with `no_std` builds.
237#[cfg(all(not(feature = "no_avx2"),
238 any(target_arch = "x86_64", target_arch = "x86")))]
239pub fn has_avx2() -> bool {
240 cpuid_avx2::get()
241}