kopis/
kem.rs

1//! This file implements the IND-CCA-secure Kopis KEM scheme
2
3use crate::{
4    consts::{DOMSEP_FO, DOMSEP_NOREJECT},
5    pke::{self, PkePublicKey, PkeSecretKey, ciphertext_len, expand_decap_key, max_ciphertext_len},
6    turboshake256_hash,
7};
8
9use rand_core::CryptoRng;
10use subtle::{ConditionallySelectable, ConstantTimeEq};
11use turboshake::CTurboShake256;
12use turboshake::digest::{ExtendableOutput, Update, XofReader};
13use zeroize::{Zeroize, ZeroizeOnDrop};
14
15/// A public key for the IND-CCA-secure Kopis KEM scheme
16pub struct KemPublicKey<const L: usize> {
17    /// The PKE public key
18    pke_pk: PkePublicKey<L>,
19    /// The hash of `pke_pk`
20    hash_pke_pk: [u8; 32],
21}
22
23impl<const L: usize> KemPublicKey<L> {
24    pub(crate) const SERIALIZED_LEN: usize = PkePublicKey::<L>::SERIALIZED_LEN;
25
26    /// Serializes just `pke_pk`
27    pub(crate) fn serialize(&self, out_buf: &mut [u8]) {
28        self.pke_pk.serialize(out_buf);
29    }
30
31    /// Deserializes from `pke_pk`, and recomputes `hash_pke_pk`
32    pub(crate) fn from_bytes(bytes: &[u8]) -> Self {
33        let pke_pk = PkePublicKey::from_bytes(bytes);
34        let hash_pke_pk = pke_pk.hash();
35
36        KemPublicKey {
37            pke_pk,
38            hash_pke_pk,
39        }
40    }
41}
42
43/// The shared secret of a KEM operation
44pub type SharedSecret = [u8; 32];
45
46/// A secret key for the IND-CCA-secure Kopis KEM scheme.
47///
48/// The canonical secret key is a 32-byte seed. This struct stores the expanded form for
49/// efficiency (avoiding re-expansion on every decapsulation).
50///
51/// The secret components (`seed`, `z`, and `pke_sk`) are zeroed from memory when the key is
52/// dropped. The remaining fields (`pke_pk`, `hash_pke_pk`) are public values, so they are left
53/// untouched.
54#[derive(ZeroizeOnDrop)]
55pub struct KemSecretKey<const L: usize> {
56    /// The 32-byte seed (the canonical secret key, used for serialization)
57    seed: [u8; 32],
58    /// Used for deriving pseudorandom shared secrets when decap fails
59    z: [u8; 32],
60    /// The PKE secret key (expanded from seed)
61    pke_sk: PkeSecretKey<L>,
62    /// The PKE public key that `pke_sk` generated
63    #[zeroize(skip)]
64    pke_pk: PkePublicKey<L>,
65    /// The hash of `pke_pk`
66    #[zeroize(skip)]
67    hash_pke_pk: [u8; 32],
68}
69
70impl<const L: usize> KemSecretKey<L> {
71    /// Construct a secret key from a 32-byte seed by expanding it via `ExpandDecapKey`.
72    pub fn expand_from_seed<const MU: usize>(seed: &[u8; 32]) -> KemSecretKey<L> {
73        let (pke_sk, z, pke_pk, hash_pke_pk) = expand_decap_key::<L, MU>(seed);
74
75        KemSecretKey {
76            seed: *seed,
77            z,
78            pke_sk,
79            pke_pk,
80            hash_pke_pk,
81        }
82    }
83
84    /// Generate a fresh secret key by sampling a random 32-byte seed.
85    pub fn generate<const MU: usize>(rng: &mut impl CryptoRng) -> KemSecretKey<L> {
86        let mut seed = [0u8; 32];
87        rng.fill_bytes(&mut seed);
88        let out = Self::expand_from_seed::<MU>(&seed);
89
90        seed.zeroize();
91        out
92    }
93
94    /// Returns the seed that produced this secret key
95    pub fn seed(&self) -> &[u8; 32] {
96        &self.seed
97    }
98
99    pub(crate) fn public_key(&self) -> KemPublicKey<L> {
100        KemPublicKey {
101            pke_pk: self.pke_pk.clone(),
102            hash_pke_pk: self.hash_pke_pk,
103        }
104    }
105}
106
107/// Encapsulate a shared secret to the given public key using the given `randomness`.
108/// Returns the shared secret. `out_buf` MUST have length `ciphertext_len::<L, T>()`.
109pub(crate) fn encap_deterministic<const L: usize, const MU: usize, const T: usize>(
110    randomness: &[u8; 32],
111    kem_pk: &KemPublicKey<L>,
112    out_buf: &mut [u8],
113) -> SharedSecret {
114    let KemPublicKey {
115        pke_pk,
116        hash_pke_pk,
117    } = kem_pk;
118
119    // k || r = TurboSHAKE256()
120    let mut k = [0u8; 32];
121    let mut r = [0u8; 32];
122
123    let mut xof = {
124        let mut hasher = CTurboShake256::<DOMSEP_FO>::default();
125        hasher.update(randomness);
126        hasher.update(hash_pke_pk);
127        hasher.finalize_xof()
128    };
129    xof.read(&mut k);
130    xof.read(&mut r);
131
132    // c = PkeEncrypt(r, pk, randomness)
133    pke::encrypt_deterministic::<L, MU, T>(pke_pk, randomness, &r, out_buf);
134
135    k
136}
137
138/// Decapsulates a shared secret from the given ciphertext and secret key.
139/// Returns the shared secret or a pseudorandom value if the ciphertext is invalid.
140/// `ciphertext` MUST have length `ciphertext_len::<L, T>()`.
141pub fn decap<const L: usize, const MU: usize, const T: usize>(
142    sk: &KemSecretKey<L>,
143    ciphertext: &[u8],
144) -> SharedSecret {
145    assert_eq!(ciphertext.len(), ciphertext_len::<L, T>());
146
147    // randomness = PkeDecrypt(sk, c)
148    let randomness = pke::decrypt::<L, T>(&sk.pke_sk, ciphertext);
149
150    // k || rprime = TurboSHAKE256()
151    let mut k = [0u8; 32];
152    let mut rprime = [0u8; 32];
153
154    let mut xof = {
155        let mut hasher = CTurboShake256::<DOMSEP_FO>::default();
156        hasher.update(&randomness);
157        hasher.update(&sk.hash_pke_pk);
158        hasher.finalize_xof()
159    };
160    xof.read(&mut k);
161    xof.read(&mut rprime);
162
163    // cprime = PkeEncrypt(rprime, pk, randomness)
164    let mut buf = [0u8; max_ciphertext_len()];
165    let reconstructed_ct = &mut buf[..ciphertext_len::<L, T>()];
166    pke::encrypt_deterministic::<L, MU, T>(&sk.pke_pk, &randomness, &rprime, reconstructed_ct);
167
168    // Compute rejection value: TurboSHAKE256(z || c, 32, DOMSEP_NOREJECT)
169    let reject_val = turboshake256_hash::<DOMSEP_NOREJECT>(&sk.z, ciphertext);
170
171    // Constant-time select: return k if c == cprime, else return reject_val
172    let reconstruction_matched = reconstructed_ct.ct_eq(ciphertext);
173    <[u8; 32]>::conditional_select(&reject_val, &k, reconstruction_matched)
174}
175
176#[cfg(test)]
177mod test {
178    use super::*;
179    use crate::consts::*;
180
181    use rand::Rng;
182
183    #[test]
184    fn kopis512_cca_kem() {
185        test_encap_decap::<KOPIS512_L, KOPIS512_MU, KOPIS512_T>();
186    }
187
188    #[test]
189    fn kopis768_cca_kem() {
190        test_encap_decap::<KOPIS768_L, KOPIS768_MU, KOPIS768_T>();
191    }
192
193    #[test]
194    fn kopis1024_cca_kem() {
195        test_encap_decap::<KOPIS1024_L, KOPIS1024_MU, KOPIS1024_T>();
196    }
197
198    fn test_encap_decap<const L: usize, const MU: usize, const T: usize>() {
199        let mut rng = rand::rng();
200        let mut backing_buf = [0u8; max_ciphertext_len()];
201
202        for _ in 0..100 {
203            let sk = KemSecretKey::<L>::generate::<MU>(&mut rng);
204            let pk = sk.public_key();
205            let ct_buf = &mut backing_buf[..ciphertext_len::<L, T>()];
206
207            let randomness: [u8; 32] = rng.random();
208            let ss1 = encap_deterministic::<L, MU, T>(&randomness, &pk, ct_buf);
209            let ss2 = decap::<L, MU, T>(&sk, ct_buf);
210            assert_eq!(ss1, ss2);
211
212            // Check that the Fujisaki-Okamoto transform was implemented properly. That is, a
213            // perturbed ciphertext should yield a secret key that is totally unguessable to the
214            // encapsulator
215            let perturbed_ct = ct_buf;
216            // XOR the ciphertext with a random (nonzero) byte in a random location
217            let idx = (rng.random::<u32>() as usize) % perturbed_ct.len();
218            let byte = loop {
219                let b = rng.random::<u8>();
220                if b != 0 {
221                    break b;
222                }
223            };
224            perturbed_ct[idx] ^= byte;
225            // Decapsulate the perturbed ciphertext
226            let ss1 = decap::<L, MU, T>(&sk, perturbed_ct);
227            // Try to guess what the decapsulation would be. If we messed up the F-O transform
228            // and returned k regardless of the equality check, the adversary (who knows
229            // randomness and pk) could compute k.
230            let ss2 =
231                recompute_shared_secret_for_pertrubed_ciphertext::<L, MU, T>(&randomness, &pk);
232            assert_ne!(ss1, ss2);
233        }
234    }
235
236    /// Model an adversary who has encapsulated a value to a given public key and has perturbed the
237    /// ciphertext. If Fujisaki-Okamoto is not implemented, they could predict the shared secret
238    /// by recomputing k from the randomness and public key hash.
239    pub(crate) fn recompute_shared_secret_for_pertrubed_ciphertext<
240        const L: usize,
241        const MU: usize,
242        const T: usize,
243    >(
244        randomness: &[u8; 32],
245        kem_pk: &KemPublicKey<L>,
246    ) -> SharedSecret {
247        // Recompute pkh
248        let hash_pke_pk = kem_pk.pke_pk.hash();
249
250        // k || r = TurboSHAKE256(randomness || pkh, 64, DOMSEP_FO)
251        let mut k = [0u8; 32];
252
253        let mut xof = {
254            let mut hasher = CTurboShake256::<DOMSEP_FO>::default();
255            hasher.update(randomness);
256            hasher.update(&hash_pke_pk);
257            hasher.finalize_xof()
258        };
259        xof.read(&mut k);
260
261        k
262    }
263}
kopis/kem.rs

kopis/
kem.rs
