rsa/algorithms/
pkcs1v15.rs

1//! PKCS#1 v1.5 support as described in [RFC8017 § 8.2].
2//!
3//! # Usage
4//!
5//! See [code example in the toplevel rustdoc](../index.html#pkcs1-v15-signatures).
6//!
7//! [RFC8017 § 8.2]: https://datatracker.ietf.org/doc/html/rfc8017#section-8.2
8
9use alloc::vec::Vec;
10use const_oid::AssociatedOid;
11use crypto_bigint::{Choice, CtAssign, CtEq, CtSelect};
12use digest::Digest;
13use rand_core::TryCryptoRng;
14use zeroize::Zeroizing;
15
16use crate::errors::{Error, Result};
17
18/// Fills the provided slice with random values, which are guaranteed
19/// to not be zero.
20#[inline]
21fn non_zero_random_bytes<R: TryCryptoRng + ?Sized>(
22    rng: &mut R,
23    data: &mut [u8],
24) -> core::result::Result<(), R::Error> {
25    rng.try_fill_bytes(data)?;
26
27    for el in data {
28        if *el == 0u8 {
29            // TODO: break after a certain amount of time
30            while *el == 0u8 {
31                rng.try_fill_bytes(core::slice::from_mut(el))?;
32            }
33        }
34    }
35
36    Ok(())
37}
38
39/// Applied the padding scheme from PKCS#1 v1.5 for encryption.  The message must be no longer than
40/// the length of the public modulus minus 11 bytes.
41pub(crate) fn pkcs1v15_encrypt_pad<R>(
42    rng: &mut R,
43    msg: &[u8],
44    k: usize,
45) -> Result<Zeroizing<Vec<u8>>>
46where
47    R: TryCryptoRng + ?Sized,
48{
49    if msg.len() + 11 > k {
50        return Err(Error::MessageTooLong);
51    }
52
53    // EM = 0x00 || 0x02 || PS || 0x00 || M
54    let mut em = Zeroizing::new(vec![0u8; k]);
55    em[1] = 2;
56    non_zero_random_bytes(rng, &mut em[2..k - msg.len() - 1]).map_err(|_: R::Error| Error::Rng)?;
57    em[k - msg.len() - 1] = 0;
58    em[k - msg.len()..].copy_from_slice(msg);
59    Ok(em)
60}
61
62/// Removes the encryption padding scheme from PKCS#1 v1.5.
63///
64/// Note that whether this function returns an error or not discloses secret
65/// information. If an attacker can cause this function to run repeatedly and
66/// learn whether each instance returned an error then they can decrypt and
67/// forge signatures as if they had the private key. See
68/// `decrypt_session_key` for a way of solving this problem.
69#[inline]
70pub(crate) fn pkcs1v15_encrypt_unpad(em: Vec<u8>, k: usize) -> Result<Vec<u8>> {
71    let (valid, out, index) = decrypt_inner(em, k)?;
72    if valid == 0 {
73        return Err(Error::Decryption);
74    }
75
76    Ok(out[index as usize..].to_vec())
77}
78
79/// Removes the PKCS1v15 padding It returns one or zero in valid that indicates whether the
80/// plaintext was correctly structured. In either case, the plaintext is
81/// returned in em so that it may be read independently of whether it was valid
82/// in order to maintain constant memory access patterns. If the plaintext was
83/// valid then index contains the index of the original message in em.
84#[inline]
85fn decrypt_inner(em: Vec<u8>, k: usize) -> Result<(u8, Vec<u8>, u32)> {
86    if k < 11 {
87        return Err(Error::Decryption);
88    }
89
90    let first_byte_is_zero = em[0].ct_eq(&0u8);
91    let second_byte_is_two = em[1].ct_eq(&2u8);
92
93    // The remainder of the plaintext must be a string of non-zero random
94    // octets, followed by a 0, followed by the message.
95    //   looking_for_index: 1 iff we are still looking for the zero.
96    //   index: the offset of the first zero byte.
97    let mut looking_for_index = Choice::TRUE;
98    let mut index = 0u32;
99
100    for (i, el) in em.iter().enumerate().skip(2) {
101        let equals0 = el.ct_eq(&0u8);
102        index.ct_assign(&(i as u32), looking_for_index & equals0);
103        looking_for_index &= !equals0;
104    }
105
106    // The PS padding must be at least 8 bytes long, and it starts two
107    // bytes into em.
108    // TODO: WARNING: THIS MUST BE CONSTANT TIME CHECK:
109    // Ref: https://github.com/dalek-cryptography/subtle/issues/20
110    // This is currently copy & paste from the constant time impl in
111    // go, but very likely not sufficient.
112    let valid_ps = Choice::from_u8_lsb((((2i32 + 8i32 - index as i32 - 1i32) >> 31) & 1) as u8);
113    let valid = first_byte_is_zero & second_byte_is_two & !looking_for_index & valid_ps;
114    index = u32::ct_select(&0, &(index + 1), valid);
115
116    Ok((valid.to_u8(), em, index))
117}
118
119#[inline]
120pub(crate) fn pkcs1v15_sign_pad(prefix: &[u8], hashed: &[u8], k: usize) -> Result<Vec<u8>> {
121    let hash_len = hashed.len();
122    let t_len = prefix.len() + hashed.len();
123    if k < t_len + 11 {
124        return Err(Error::MessageTooLong);
125    }
126
127    // EM = 0x00 || 0x01 || PS || 0x00 || T
128    let mut em = vec![0xff; k];
129    em[0] = 0;
130    em[1] = 1;
131    em[k - t_len - 1] = 0;
132    em[k - t_len..k - hash_len].copy_from_slice(prefix);
133    em[k - hash_len..k].copy_from_slice(hashed);
134
135    Ok(em)
136}
137
138#[inline]
139pub(crate) fn pkcs1v15_sign_unpad(prefix: &[u8], hashed: &[u8], em: &[u8], k: usize) -> Result<()> {
140    let hash_len = hashed.len();
141    let t_len = prefix.len() + hashed.len();
142    if k < t_len + 11 {
143        return Err(Error::Verification);
144    }
145
146    // EM = 0x00 || 0x01 || PS || 0x00 || T
147    let mut ok = em[0].ct_eq(&0u8);
148    ok &= em[1].ct_eq(&1u8);
149    ok &= em[k - hash_len..k].ct_eq(hashed);
150    ok &= em[k - t_len..k - hash_len].ct_eq(prefix);
151    ok &= em[k - t_len - 1].ct_eq(&0u8);
152
153    for el in em.iter().skip(2).take(k - t_len - 3) {
154        ok &= el.ct_eq(&0xff)
155    }
156
157    // TODO(tarcieri): avoid branching here by e.g. using a pseudorandom rejection symbol
158    if !ok.to_bool() {
159        return Err(Error::Verification);
160    }
161
162    Ok(())
163}
164
165/// prefix = 0x30 <oid_len + 8 + digest_len> 0x30 <oid_len + 4> 0x06 <oid_len> oid 0x05 0x00 0x04 <digest_len>
166#[inline]
167pub(crate) fn pkcs1v15_generate_prefix<D>() -> Vec<u8>
168where
169    D: Digest + AssociatedOid,
170{
171    let oid = D::OID.as_bytes();
172    let oid_len = oid.len() as u8;
173    let digest_len = <D as Digest>::output_size() as u8;
174    let mut v = vec![
175        0x30,
176        oid_len + 8 + digest_len,
177        0x30,
178        oid_len + 4,
179        0x6,
180        oid_len,
181    ];
182    v.extend_from_slice(oid);
183    v.extend_from_slice(&[0x05, 0x00, 0x04, digest_len]);
184    v
185}
186
187#[cfg(test)]
188mod tests {
189    use super::*;
190    use rand::rngs::ChaCha8Rng;
191    use rand_core::SeedableRng;
192
193    #[test]
194    fn test_non_zero_bytes() {
195        for _ in 0..10 {
196            let mut rng = ChaCha8Rng::from_seed([42; 32]);
197            let mut b = vec![0u8; 512];
198            non_zero_random_bytes(&mut rng, &mut b).unwrap();
199            for el in &b {
200                assert_ne!(*el, 0u8);
201            }
202        }
203    }
204
205    #[test]
206    fn test_encrypt_tiny_no_crash() {
207        let mut rng = ChaCha8Rng::from_seed([42; 32]);
208        let k = 8;
209        let message = vec![1u8; 4];
210        let res = pkcs1v15_encrypt_pad(&mut rng, &message, k);
211        assert_eq!(res, Err(Error::MessageTooLong));
212    }
213}
rsa/algorithms/pkcs1v15.rs

rsa/algorithms/
pkcs1v15.rs
