tor_proto/crypto/ll/
kdf.rs

1//! Key derivation functions
2//!
3//! Tor has three relevant key derivation functions that we use for
4//! deriving keys used for relay encryption.
5//!
6//! The *KDF-TOR* KDF (implemented by `LegacyKdf`) is used with the old
7//! TAP handshake.  It is ugly, it is based on SHA-1, and it should be
8//! avoided for new uses.
9//!
10//! The *HKDF-SHA256* KDF (implemented by `Ntor1Kdf`) is used with the
11//! Ntor handshake.  It is based on RFC5869 and SHA256.
12//!
13//! The *SHAKE* KDF (implemented by `ShakeKdf` is used with v3 onion
14//! services, and is likely to be used by other places in the future.
15//! It is based on SHAKE-256.
16
17use crate::{Error, Result};
18use digest::{ExtendableOutput, Update, XofReader};
19use tor_bytes::SecretBuf;
20use tor_llcrypto::d::{Sha1, Sha256, Shake256};
21use zeroize::Zeroize;
22
23/// A trait for a key derivation function.
24pub(crate) trait Kdf {
25    /// Derive `n_bytes` of key data from some secret `seed`.
26    fn derive(&self, seed: &[u8], n_bytes: usize) -> Result<SecretBuf>;
27}
28
29/// A legacy KDF, for use with TAP.
30///
31/// This KDF is based on SHA1.  Don't use this for anything new.
32pub(crate) struct LegacyKdf {
33    /// Starting index value for the TAP kdf.  should always be 1.
34    idx: u8,
35}
36
37/// A parameterized KDF, for use with ntor.
38///
39/// This KDF is based on HKDF-SHA256.
40pub(crate) struct Ntor1Kdf<'a, 'b> {
41    /// A constant for parameterizing the kdf, during the key extraction
42    /// phase.
43    t_key: &'a [u8],
44    /// Another constant for parameterizing the kdf, during the key
45    /// expansion phase.
46    m_expand: &'b [u8],
47}
48
49/// A modern KDF, for use with v3 onion services.
50///
51/// This KDF is based on SHAKE256
52pub(crate) struct ShakeKdf();
53
54impl LegacyKdf {
55    /// Instantiate a LegacyKdf.
56    pub(crate) fn new(idx: u8) -> Self {
57        LegacyKdf { idx }
58    }
59}
60impl Kdf for LegacyKdf {
61    fn derive(&self, seed: &[u8], n_bytes: usize) -> Result<SecretBuf> {
62        use digest::Digest;
63
64        let mut result = SecretBuf::with_capacity(n_bytes + Sha1::output_size());
65        let mut k = self.idx;
66        if n_bytes > Sha1::output_size() * (256 - (k as usize)) {
67            return Err(Error::InvalidKDFOutputLength);
68        }
69
70        let mut digest_output = Default::default();
71        while result.len() < n_bytes {
72            let mut d = Sha1::new();
73            Digest::update(&mut d, seed);
74            Digest::update(&mut d, [k]);
75            d.finalize_into(&mut digest_output);
76            result.extend_from_slice(&digest_output);
77            k += 1;
78        }
79        digest_output.zeroize();
80
81        result.truncate(n_bytes);
82        Ok(result)
83    }
84}
85
86impl<'a, 'b> Ntor1Kdf<'a, 'b> {
87    /// Instantiate an Ntor1Kdf, with given values for t_key and m_expand.
88    pub(crate) fn new(t_key: &'a [u8], m_expand: &'b [u8]) -> Self {
89        Ntor1Kdf { t_key, m_expand }
90    }
91}
92
93impl Kdf for Ntor1Kdf<'_, '_> {
94    fn derive(&self, seed: &[u8], n_bytes: usize) -> Result<SecretBuf> {
95        let hkdf = hkdf::Hkdf::<Sha256>::new(Some(self.t_key), seed);
96
97        let mut result: SecretBuf = vec![0; n_bytes].into();
98        hkdf.expand(self.m_expand, result.as_mut())
99            .map_err(|_| Error::InvalidKDFOutputLength)?;
100        Ok(result)
101    }
102}
103
104impl ShakeKdf {
105    /// Instantiate a ShakeKdf.
106    pub(crate) fn new() -> Self {
107        ShakeKdf()
108    }
109}
110impl Kdf for ShakeKdf {
111    fn derive(&self, seed: &[u8], n_bytes: usize) -> Result<SecretBuf> {
112        let mut xof = Shake256::default();
113        xof.update(seed);
114        let mut result: SecretBuf = vec![0; n_bytes].into();
115        xof.finalize_xof().read(result.as_mut());
116        Ok(result)
117    }
118}
119
120#[cfg(test)]
121mod test {
122    // @@ begin test lint list maintained by maint/add_warning @@
123    #![allow(clippy::bool_assert_comparison)]
124    #![allow(clippy::clone_on_copy)]
125    #![allow(clippy::dbg_macro)]
126    #![allow(clippy::mixed_attributes_style)]
127    #![allow(clippy::print_stderr)]
128    #![allow(clippy::print_stdout)]
129    #![allow(clippy::single_char_pattern)]
130    #![allow(clippy::unwrap_used)]
131    #![allow(clippy::unchecked_duration_subtraction)]
132    #![allow(clippy::useless_vec)]
133    #![allow(clippy::needless_pass_by_value)]
134    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
135    use super::*;
136    use hex_literal::hex;
137
138    #[test]
139    fn clearbox_tap_kdf() {
140        // Calculate an instance of the TAP KDF, based on its spec in
141        // tor-spec.txt.
142        use digest::Digest;
143        let input = b"here is an example key seed that we will expand";
144        let result = LegacyKdf::new(6).derive(input, 99).unwrap();
145
146        let mut expect_result = Vec::new();
147        let mut k0: Vec<u8> = Vec::new();
148        k0.extend(&input[..]);
149        for x in 6..11 {
150            k0.push(x);
151            expect_result.extend(Sha1::digest(&k0));
152            k0.pop();
153        }
154        expect_result.truncate(99);
155
156        assert_eq!(&result[..], &expect_result[..]);
157    }
158
159    #[test]
160    fn testvec_tap_kdf() {
161        // Taken from test_crypto.c in Tor, generated by a python script.
162        fn expand(b: &[u8]) -> SecretBuf {
163            LegacyKdf::new(0).derive(b, 100).unwrap()
164        }
165
166        let expect = hex!(
167            "5ba93c9db0cff93f52b521d7420e43f6eda2784fbf8b4530d8
168             d246dd74ac53a13471bba17941dff7c4ea21bb365bbeeaf5f2
169             c654883e56d11e43c44e9842926af7ca0a8cca12604f945414
170             f07b01e13da42c6cf1de3abfdea9b95f34687cbbe92b9a7383"
171        );
172        assert_eq!(&expand(&b""[..])[..], &expect[..]);
173
174        let expect = hex!(
175            "776c6214fc647aaa5f683c737ee66ec44f03d0372e1cce6922
176             7950f236ddf1e329a7ce7c227903303f525a8c6662426e8034
177             870642a6dabbd41b5d97ec9bf2312ea729992f48f8ea2d0ba8
178             3f45dfda1a80bdc8b80de01b23e3e0ffae099b3e4ccf28dc28"
179        );
180        assert_eq!(&expand(&b"Tor"[..])[..], &expect[..]);
181
182        let brunner_quote = b"AN ALARMING ITEM TO FIND ON A MONTHLY AUTO-DEBIT NOTICE";
183        let expect = hex!(
184            "a340b5d126086c3ab29c2af4179196dbf95e1c72431419d331
185             4844bf8f6afb6098db952b95581fb6c33625709d6f4400b8e7
186             ace18a70579fad83c0982ef73f89395bcc39493ad53a685854
187             daf2ba9b78733b805d9a6824c907ee1dba5ac27a1e466d4d10"
188        );
189        assert_eq!(&expand(&brunner_quote[..])[..], &expect[..]);
190    }
191
192    #[test]
193    fn fail_tap_kdf() {
194        let result = LegacyKdf::new(6).derive(&b"x"[..], 10000);
195        assert!(result.is_err());
196    }
197
198    #[test]
199    fn clearbox_ntor1_kdf() {
200        // Calculate Ntor1Kdf, and make sure we get the same result by
201        // following the calculation in the spec.
202        let input = b"another example key seed that we will expand";
203        let result = Ntor1Kdf::new(&b"key"[..], &b"expand"[..])
204            .derive(input, 99)
205            .unwrap();
206
207        let kdf = hkdf::Hkdf::<Sha256>::new(Some(&b"key"[..]), &input[..]);
208        let mut expect_result = vec![0_u8; 99];
209        kdf.expand(&b"expand"[..], &mut expect_result[..]).unwrap();
210
211        assert_eq!(&expect_result[..], &result[..]);
212    }
213
214    #[test]
215    fn testvec_ntor1_kdf() {
216        // From Tor's test_crypto.c; generated with ntor_ref.py
217        fn expand(b: &[u8]) -> SecretBuf {
218            let t_key = b"ntor-curve25519-sha256-1:key_extract";
219            let m_expand = b"ntor-curve25519-sha256-1:key_expand";
220            Ntor1Kdf::new(&t_key[..], &m_expand[..])
221                .derive(b, 100)
222                .unwrap()
223        }
224
225        let expect = hex!(
226            "5521492a85139a8d9107a2d5c0d9c91610d0f95989975ebee6
227             c02a4f8d622a6cfdf9b7c7edd3832e2760ded1eac309b76f8d
228             66c4a3c4d6225429b3a016e3c3d45911152fc87bc2de9630c3
229             961be9fdb9f93197ea8e5977180801926d3321fa21513e59ac"
230        );
231        assert_eq!(&expand(&b"Tor"[..])[..], &expect[..]);
232
233        let brunner_quote = b"AN ALARMING ITEM TO FIND ON YOUR CREDIT-RATING STATEMENT";
234        let expect = hex!(
235            "a2aa9b50da7e481d30463adb8f233ff06e9571a0ca6ab6df0f
236             b206fa34e5bc78d063fc291501beec53b36e5a0e434561200c
237             5f8bd13e0f88b3459600b4dc21d69363e2895321c06184879d
238             94b18f078411be70b767c7fc40679a9440a0c95ea83a23efbf"
239        );
240        assert_eq!(&expand(&brunner_quote[..])[..], &expect[..]);
241    }
242
243    #[test]
244    fn testvec_shake_kdf() {
245        // This is just one of the shake test vectors from tor-llcrypto
246        let input = hex!(
247            "76891a7bcc6c04490035b743152f64a8dd2ea18ab472b8d36ecf45
248             858d0b0046"
249        );
250        let expected = hex!(
251            "e8447df87d01beeb724c9a2a38ab00fcc24e9bd17860e673b02122
252             2d621a7810e5d3"
253        );
254
255        let result = ShakeKdf::new().derive(&input[..], expected.len());
256        assert_eq!(&result.unwrap()[..], &expected[..]);
257    }
258}
tor_proto/crypto/ll/kdf.rs

tor_proto/crypto/ll/
kdf.rs
