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_time_subtraction)]
132    #![allow(clippy::useless_vec)]
133    #![allow(clippy::needless_pass_by_value)]
134    #![allow(clippy::string_slice)] // See arti#2571
135    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
136    use super::*;
137    use hex_literal::hex;
138
139    #[test]
140    fn clearbox_tap_kdf() {
141        // Calculate an instance of the TAP KDF, based on its spec in
142        // tor-spec.txt.
143        use digest::Digest;
144        let input = b"here is an example key seed that we will expand";
145        let result = LegacyKdf::new(6).derive(input, 99).unwrap();
146
147        let mut expect_result = Vec::new();
148        let mut k0: Vec<u8> = Vec::new();
149        k0.extend(&input[..]);
150        for x in 6..11 {
151            k0.push(x);
152            expect_result.extend(Sha1::digest(&k0));
153            k0.pop();
154        }
155        expect_result.truncate(99);
156
157        assert_eq!(&result[..], &expect_result[..]);
158    }
159
160    #[test]
161    fn testvec_tap_kdf() {
162        // Taken from test_crypto.c in Tor, generated by a python script.
163        fn expand(b: &[u8]) -> SecretBuf {
164            LegacyKdf::new(0).derive(b, 100).unwrap()
165        }
166
167        let expect = hex!(
168            "5ba93c9db0cff93f52b521d7420e43f6eda2784fbf8b4530d8
169             d246dd74ac53a13471bba17941dff7c4ea21bb365bbeeaf5f2
170             c654883e56d11e43c44e9842926af7ca0a8cca12604f945414
171             f07b01e13da42c6cf1de3abfdea9b95f34687cbbe92b9a7383"
172        );
173        assert_eq!(&expand(&b""[..])[..], &expect[..]);
174
175        let expect = hex!(
176            "776c6214fc647aaa5f683c737ee66ec44f03d0372e1cce6922
177             7950f236ddf1e329a7ce7c227903303f525a8c6662426e8034
178             870642a6dabbd41b5d97ec9bf2312ea729992f48f8ea2d0ba8
179             3f45dfda1a80bdc8b80de01b23e3e0ffae099b3e4ccf28dc28"
180        );
181        assert_eq!(&expand(&b"Tor"[..])[..], &expect[..]);
182
183        let brunner_quote = b"AN ALARMING ITEM TO FIND ON A MONTHLY AUTO-DEBIT NOTICE";
184        let expect = hex!(
185            "a340b5d126086c3ab29c2af4179196dbf95e1c72431419d331
186             4844bf8f6afb6098db952b95581fb6c33625709d6f4400b8e7
187             ace18a70579fad83c0982ef73f89395bcc39493ad53a685854
188             daf2ba9b78733b805d9a6824c907ee1dba5ac27a1e466d4d10"
189        );
190        assert_eq!(&expand(&brunner_quote[..])[..], &expect[..]);
191    }
192
193    #[test]
194    fn fail_tap_kdf() {
195        let result = LegacyKdf::new(6).derive(&b"x"[..], 10000);
196        assert!(result.is_err());
197    }
198
199    #[test]
200    fn clearbox_ntor1_kdf() {
201        // Calculate Ntor1Kdf, and make sure we get the same result by
202        // following the calculation in the spec.
203        let input = b"another example key seed that we will expand";
204        let result = Ntor1Kdf::new(&b"key"[..], &b"expand"[..])
205            .derive(input, 99)
206            .unwrap();
207
208        let kdf = hkdf::Hkdf::<Sha256>::new(Some(&b"key"[..]), &input[..]);
209        let mut expect_result = vec![0_u8; 99];
210        kdf.expand(&b"expand"[..], &mut expect_result[..]).unwrap();
211
212        assert_eq!(&expect_result[..], &result[..]);
213    }
214
215    #[test]
216    fn testvec_ntor1_kdf() {
217        // From Tor's test_crypto.c; generated with ntor_ref.py
218        fn expand(b: &[u8]) -> SecretBuf {
219            let t_key = b"ntor-curve25519-sha256-1:key_extract";
220            let m_expand = b"ntor-curve25519-sha256-1:key_expand";
221            Ntor1Kdf::new(&t_key[..], &m_expand[..])
222                .derive(b, 100)
223                .unwrap()
224        }
225
226        let expect = hex!(
227            "5521492a85139a8d9107a2d5c0d9c91610d0f95989975ebee6
228             c02a4f8d622a6cfdf9b7c7edd3832e2760ded1eac309b76f8d
229             66c4a3c4d6225429b3a016e3c3d45911152fc87bc2de9630c3
230             961be9fdb9f93197ea8e5977180801926d3321fa21513e59ac"
231        );
232        assert_eq!(&expand(&b"Tor"[..])[..], &expect[..]);
233
234        let brunner_quote = b"AN ALARMING ITEM TO FIND ON YOUR CREDIT-RATING STATEMENT";
235        let expect = hex!(
236            "a2aa9b50da7e481d30463adb8f233ff06e9571a0ca6ab6df0f
237             b206fa34e5bc78d063fc291501beec53b36e5a0e434561200c
238             5f8bd13e0f88b3459600b4dc21d69363e2895321c06184879d
239             94b18f078411be70b767c7fc40679a9440a0c95ea83a23efbf"
240        );
241        assert_eq!(&expand(&brunner_quote[..])[..], &expect[..]);
242    }
243
244    #[test]
245    fn testvec_shake_kdf() {
246        // This is just one of the shake test vectors from tor-llcrypto
247        let input = hex!(
248            "76891a7bcc6c04490035b743152f64a8dd2ea18ab472b8d36ecf45
249             858d0b0046"
250        );
251        let expected = hex!(
252            "e8447df87d01beeb724c9a2a38ab00fcc24e9bd17860e673b02122
253             2d621a7810e5d3"
254        );
255
256        let result = ShakeKdf::new().derive(&input[..], expected.len());
257        assert_eq!(&result.unwrap()[..], &expected[..]);
258    }
259}
tor_proto/crypto/ll/kdf.rs

tor_proto/crypto/ll/
kdf.rs
