cfxkey/
extended.rs

1// Copyright 2015-2019 Parity Technologies (UK) Ltd.
2// This file is part of Parity Ethereum.
3
4// Parity Ethereum is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8
9// Parity Ethereum is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12// GNU General Public License for more details.
13
14// You should have received a copy of the GNU General Public License
15// along with Parity Ethereum.  If not, see <http://www.gnu.org/licenses/>.
16
17//! Extended keys
18
19pub use self::derivation::Error as DerivationError;
20use crate::{secret::Secret, Public};
21use cfx_types::H256;
22
23/// Represents label that can be stored as a part of key derivation
24pub trait Label {
25    /// Length of the data that label occupies
26    fn len() -> usize;
27
28    /// Store label data to the key derivation sequence
29    /// Must not use more than `len()` bytes from slice
30    fn store(&self, target: &mut [u8]);
31}
32
33impl Label for u32 {
34    fn len() -> usize { 4 }
35
36    fn store(&self, target: &mut [u8]) {
37        let bytes = self.to_be_bytes();
38        target[0..4].copy_from_slice(&bytes);
39    }
40}
41
42/// Key derivation over generic label `T`
43pub enum Derivation<T: Label> {
44    /// Soft key derivation (allow proof of parent)
45    Soft(T),
46    /// Hard key derivation (does not allow proof of parent)
47    Hard(T),
48}
49
50impl From<u32> for Derivation<u32> {
51    fn from(index: u32) -> Self {
52        if index < (2 << 30) {
53            Derivation::Soft(index)
54        } else {
55            Derivation::Hard(index)
56        }
57    }
58}
59
60impl Label for H256 {
61    fn len() -> usize { Self::len_bytes() }
62
63    fn store(&self, target: &mut [u8]) {
64        (&mut target[0..32]).copy_from_slice(self.as_bytes());
65    }
66}
67
68/// Extended secret key, allows deterministic derivation of subsequent keys.
69pub struct ExtendedSecret {
70    secret: Secret,
71    chain_code: H256,
72}
73
74impl ExtendedSecret {
75    /// New extended key from given secret and chain code.
76    pub fn with_code(secret: Secret, chain_code: H256) -> ExtendedSecret {
77        ExtendedSecret { secret, chain_code }
78    }
79
80    /// New extended key from given secret with the random chain code.
81    pub fn new_random(secret: Secret) -> ExtendedSecret {
82        ExtendedSecret::with_code(secret, H256::random())
83    }
84
85    /// New extended key from given secret.
86    /// Chain code will be derived from the secret itself (in a deterministic
87    /// way).
88    pub fn new(secret: Secret) -> ExtendedSecret {
89        let chain_code = derivation::chain_code(*secret);
90        ExtendedSecret::with_code(secret, chain_code)
91    }
92
93    /// Derive new private key
94    pub fn derive<T>(&self, index: Derivation<T>) -> ExtendedSecret
95    where T: Label {
96        let (derived_key, next_chain_code) =
97            derivation::private(*self.secret, self.chain_code, index);
98
99        let derived_secret = Secret::from(derived_key.0);
100
101        ExtendedSecret::with_code(derived_secret, next_chain_code)
102    }
103
104    /// Private key component of the extended key.
105    pub fn as_raw(&self) -> &Secret { &self.secret }
106}
107
108/// Extended public key, allows deterministic derivation of subsequent keys.
109pub struct ExtendedPublic {
110    public: Public,
111    chain_code: H256,
112}
113
114impl ExtendedPublic {
115    /// New extended public key from known parent and chain code
116    pub fn new(public: Public, chain_code: H256) -> Self {
117        ExtendedPublic { public, chain_code }
118    }
119
120    /// Create new extended public key from known secret
121    pub fn from_secret(
122        secret: &ExtendedSecret,
123    ) -> Result<Self, DerivationError> {
124        Ok(ExtendedPublic::new(
125            derivation::point(**secret.as_raw())?,
126            secret.chain_code.clone(),
127        ))
128    }
129
130    /// Derive new public key
131    /// Operation is defined only for index belongs [0..2^31)
132    pub fn derive<T>(
133        &self, index: Derivation<T>,
134    ) -> Result<Self, DerivationError>
135    where T: Label {
136        let (derived_key, next_chain_code) =
137            derivation::public(self.public, self.chain_code, index)?;
138        Ok(ExtendedPublic::new(derived_key, next_chain_code))
139    }
140
141    pub fn public(&self) -> &Public { &self.public }
142}
143
144pub struct ExtendedKeyPair {
145    secret: ExtendedSecret,
146    public: ExtendedPublic,
147}
148
149impl ExtendedKeyPair {
150    pub fn new(secret: Secret) -> Self {
151        let extended_secret = ExtendedSecret::new(secret);
152        let extended_public = ExtendedPublic::from_secret(&extended_secret)
153            .expect("Valid `Secret` always produces valid public; qed");
154        ExtendedKeyPair {
155            secret: extended_secret,
156            public: extended_public,
157        }
158    }
159
160    pub fn with_code(secret: Secret, public: Public, chain_code: H256) -> Self {
161        ExtendedKeyPair {
162            secret: ExtendedSecret::with_code(secret, chain_code.clone()),
163            public: ExtendedPublic::new(public, chain_code),
164        }
165    }
166
167    pub fn with_secret(secret: Secret, chain_code: H256) -> Self {
168        let extended_secret = ExtendedSecret::with_code(secret, chain_code);
169        let extended_public = ExtendedPublic::from_secret(&extended_secret)
170            .expect("Valid `Secret` always produces valid public; qed");
171        ExtendedKeyPair {
172            secret: extended_secret,
173            public: extended_public,
174        }
175    }
176
177    pub fn with_seed(seed: &[u8]) -> Result<ExtendedKeyPair, DerivationError> {
178        let (master_key, chain_code) = derivation::seed_pair(seed);
179        Ok(ExtendedKeyPair::with_secret(
180            Secret::from_unsafe_slice(master_key.as_bytes())
181                .map_err(|_| DerivationError::InvalidSeed)?,
182            chain_code,
183        ))
184    }
185
186    pub fn secret(&self) -> &ExtendedSecret { &self.secret }
187
188    pub fn public(&self) -> &ExtendedPublic { &self.public }
189
190    pub fn derive<T>(
191        &self, index: Derivation<T>,
192    ) -> Result<Self, DerivationError>
193    where T: Label {
194        let derived = self.secret.derive(index);
195
196        Ok(ExtendedKeyPair {
197            public: ExtendedPublic::from_secret(&derived)?,
198            secret: derived,
199        })
200    }
201}
202
203// Derivation functions for private and public keys
204// Work is based on BIP0032
205// https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
206mod derivation {
207    use super::{Derivation, Label};
208    use crate::{math::curve_order, SECP256K1};
209    use cfx_crypto::crypto::keccak::Keccak256;
210    use cfx_types::{BigEndianHash, H256, H512, U256, U512};
211    use hmac::{Hmac, Mac};
212    use secp256k1::key::{PublicKey, SecretKey};
213    use sha2::Sha512;
214    use std::convert::TryInto;
215
216    type HmacSha512 = Hmac<Sha512>;
217
218    #[derive(Debug)]
219    pub enum Error {
220        InvalidHardenedUse,
221        InvalidPoint,
222        MissingIndex,
223        InvalidSeed,
224    }
225
226    // Deterministic derivation of the key using secp256k1 elliptic curve.
227    // Derivation can be either hardened or not.
228    // For hardened derivation, pass u32 index at least 2^31 or custom
229    // Derivation::Hard(T) enum
230    //
231    // Can panic if passed `private_key` is not a valid secp256k1 private key
232    // (outside of (0..curve_order()]) field
233    pub fn private<T>(
234        private_key: H256, chain_code: H256, index: Derivation<T>,
235    ) -> (H256, H256)
236    where T: Label {
237        match index {
238            Derivation::Soft(index) => {
239                private_soft(private_key, chain_code, index)
240            }
241            Derivation::Hard(index) => {
242                private_hard(private_key, chain_code, index)
243            }
244        }
245    }
246
247    fn hmac_pair(
248        data: &[u8], private_key: H256, chain_code: H256,
249    ) -> (H256, H256) {
250        let private: U256 = private_key.into_uint();
251
252        // produces 512-bit derived hmac (I)
253        let mut skey = HmacSha512::new_from_slice(chain_code.as_bytes())
254            .expect("HmacSha512 failed");
255        skey.update(data);
256        let i_512 = skey.finalize().into_bytes().to_vec();
257
258        // left most 256 bits are later added to original private key
259        let hmac_key: U256 = H256::from_slice(&i_512[0..32]).into_uint();
260        // right most 256 bits are new chain code for later derivations
261        let next_chain_code = H256::from_slice(&i_512[32..64]);
262
263        let child_key =
264            BigEndianHash::from_uint(&private_add(hmac_key, private));
265        (child_key, next_chain_code)
266    }
267
268    // Can panic if passed `private_key` is not a valid secp256k1 private key
269    // (outside of (0..curve_order()]) field
270    fn private_soft<T>(
271        private_key: H256, chain_code: H256, index: T,
272    ) -> (H256, H256)
273    where T: Label {
274        let mut data = vec![0u8; 33 + T::len()];
275
276        let sec_private =
277            SecretKey::from_slice(&SECP256K1, private_key.as_bytes())
278                .expect("Caller should provide valid private key");
279        let sec_public = PublicKey::from_secret_key(&SECP256K1, &sec_private)
280            .expect("Caller should provide valid private key");
281        let public_serialized = sec_public.serialize_vec(&SECP256K1, true);
282
283        // curve point (compressed public key) --  index
284        //             0.33                    --  33..end
285        data[0..33].copy_from_slice(&public_serialized);
286        index.store(&mut data[33..]);
287
288        hmac_pair(&data, private_key, chain_code)
289    }
290
291    // Deterministic derivation of the key using secp256k1 elliptic curve
292    // This is hardened derivation and does not allow to associate
293    // corresponding public keys of the original and derived private keys
294    fn private_hard<T>(
295        private_key: H256, chain_code: H256, index: T,
296    ) -> (H256, H256)
297    where T: Label {
298        let mut data: Vec<u8> = vec![0u8; 33 + T::len()];
299        let private: U256 = private_key.into_uint();
300
301        // 0x00 (padding) -- private_key --  index
302        //  0             --    1..33    -- 33..end
303        private.to_big_endian(&mut data[1..33]);
304        index.store(&mut data[33..(33 + T::len())]);
305
306        hmac_pair(&data, private_key, chain_code)
307    }
308
309    fn private_add(k1: U256, k2: U256) -> U256 {
310        let sum = U512::from(k1) + U512::from(k2);
311        modulo(sum, curve_order())
312    }
313
314    // todo: surely can be optimized
315    fn modulo(u1: U512, u2: U256) -> U256 {
316        let m = u1 % U512::from(u2);
317        m.try_into()
318            .expect("U512 modulo U256 should fit into U256; qed")
319    }
320
321    pub fn public<T>(
322        public_key: H512, chain_code: H256, derivation: Derivation<T>,
323    ) -> Result<(H512, H256), Error>
324    where T: Label {
325        let index = match derivation {
326            Derivation::Soft(index) => index,
327            Derivation::Hard(_) => {
328                return Err(Error::InvalidHardenedUse);
329            }
330        };
331
332        let mut public_sec_raw = [0u8; 65];
333        public_sec_raw[0] = 4;
334        public_sec_raw[1..65].copy_from_slice(public_key.as_bytes());
335        let public_sec = PublicKey::from_slice(&SECP256K1, &public_sec_raw)
336            .map_err(|_| Error::InvalidPoint)?;
337        let public_serialized = public_sec.serialize_vec(&SECP256K1, true);
338
339        let mut data = vec![0u8; 33 + T::len()];
340        // curve point (compressed public key) --  index
341        //             0.33                    --  33..end
342        data[0..33].copy_from_slice(&public_serialized);
343        index.store(&mut data[33..(33 + T::len())]);
344
345        // HMAC512SHA produces [derived private(256); new chain code(256)]
346        let mut skey = HmacSha512::new_from_slice(chain_code.as_bytes())
347            .expect("HmacSha512 failed");
348        skey.update(data.as_slice());
349        let i_512 = skey.finalize().into_bytes().to_vec();
350
351        let new_private = H256::from_slice(&i_512[0..32]);
352        let new_chain_code = H256::from_slice(&i_512[32..64]);
353
354        // Generated private key can (extremely rarely) be out of secp256k1 key
355        // field
356        if curve_order() <= new_private.into_uint() {
357            return Err(Error::MissingIndex);
358        }
359        let new_private_sec = SecretKey::from_slice(&SECP256K1, new_private.as_bytes())
360			.expect("Private key belongs to the field [0..CURVE_ORDER) (checked above); So initializing can never fail; qed");
361        let mut new_public =
362            PublicKey::from_secret_key(&SECP256K1, &new_private_sec)
363                .expect("Valid private key produces valid public key");
364
365        // Adding two points on the elliptic curves (combining two public keys)
366        new_public
367            .add_assign(&SECP256K1, &public_sec)
368            .expect("Addition of two valid points produce valid point");
369
370        let serialized = new_public.serialize_vec(&SECP256K1, false);
371
372        Ok((H512::from_slice(&serialized[1..65]), new_chain_code))
373    }
374
375    fn sha3(slc: &[u8]) -> H256 { slc.keccak256().into() }
376
377    pub fn chain_code(secret: H256) -> H256 {
378        // 10,000 rounds of sha3
379        let mut running_sha3 = sha3(secret.as_bytes());
380        for _ in 0..99999 {
381            running_sha3 = sha3(running_sha3.as_bytes());
382        }
383        running_sha3
384    }
385
386    pub fn point(secret: H256) -> Result<H512, Error> {
387        let sec = SecretKey::from_slice(&SECP256K1, secret.as_bytes())
388            .map_err(|_| Error::InvalidPoint)?;
389        let public_sec = PublicKey::from_secret_key(&SECP256K1, &sec)
390            .map_err(|_| Error::InvalidPoint)?;
391        let serialized = public_sec.serialize_vec(&SECP256K1, false);
392        Ok(H512::from_slice(&serialized[1..65]))
393    }
394
395    pub fn seed_pair(seed: &[u8]) -> (H256, H256) {
396        let mut skey = HmacSha512::new_from_slice(b"Bitcoin seed")
397            .expect("HmacSha512 failed");
398        skey.update(seed);
399        let i_512 = skey.finalize().into_bytes().to_vec();
400
401        let master_key = H256::from_slice(&i_512[0..32]);
402        let chain_code = H256::from_slice(&i_512[32..64]);
403
404        (master_key, chain_code)
405    }
406}
407
408#[cfg(test)]
409mod tests {
410    use super::{
411        derivation, Derivation, ExtendedKeyPair, ExtendedPublic, ExtendedSecret,
412    };
413    use crate::secret::Secret;
414    use cfx_types::{H128, H256, H512};
415    use std::str::FromStr;
416
417    fn master_chain_basic() -> (H256, H256) {
418        let seed = H128::from_str("000102030405060708090a0b0c0d0e0f")
419            .expect("Seed should be valid H128")
420            .as_bytes()
421            .to_vec();
422
423        derivation::seed_pair(&*seed)
424    }
425
426    fn test_extended<F>(f: F, test_private: H256)
427    where F: Fn(ExtendedSecret) -> ExtendedSecret {
428        let (private_seed, chain_code) = master_chain_basic();
429        let extended_secret =
430            ExtendedSecret::with_code(Secret::from(private_seed.0), chain_code);
431        let derived = f(extended_secret);
432        assert_eq!(**derived.as_raw(), test_private);
433    }
434
435    #[test]
436    fn smoky() {
437        let secret = Secret::from_str(
438            "a100df7a048e50ed308ea696dc600215098141cb391e9527329df289f9383f65",
439        )
440        .unwrap();
441        let extended_secret =
442            ExtendedSecret::with_code(secret.clone(), H256::zero());
443
444        // hardened
445        assert_eq!(&**extended_secret.as_raw(), &*secret);
446        assert_eq!(
447			**extended_secret.derive(2_147_483_648.into()).as_raw(),
448			H256::from_str("0927453daed47839608e414a3738dfad10aed17c459bbd9ab53f89b026c834b6").unwrap(),
449		);
450        assert_eq!(
451			**extended_secret.derive(2_147_483_649.into()).as_raw(),
452			H256::from_str("44238b6a29c6dcbe9b401364141ba11e2198c289a5fed243a1c11af35c19dc0f").unwrap(),
453		);
454
455        // normal
456        assert_eq!(**extended_secret.derive(0.into()).as_raw(), H256::from_str("bf6a74e3f7b36fc4c96a1e12f31abc817f9f5904f5a8fc27713163d1f0b713f6").unwrap());
457        assert_eq!(**extended_secret.derive(1.into()).as_raw(), H256::from_str("bd4fca9eb1f9c201e9448c1eecd66e302d68d4d313ce895b8c134f512205c1bc").unwrap());
458        assert_eq!(**extended_secret.derive(2.into()).as_raw(), H256::from_str("86932b542d6cab4d9c65490c7ef502d89ecc0e2a5f4852157649e3251e2a3268").unwrap());
459
460        let extended_public = ExtendedPublic::from_secret(&extended_secret)
461            .expect("Extended public should be created");
462        let derived_public = extended_public
463            .derive(0.into())
464            .expect("First derivation of public should succeed");
465        assert_eq!(
466			*derived_public.public(),
467			H512::from_str("f7b3244c96688f92372bfd4def26dc4151529747bab9f188a4ad34e141d47bd66522ff048bc6f19a0a4429b04318b1a8796c000265b4fa200dae5f6dda92dd94").unwrap(),
468		);
469
470        let keypair = ExtendedKeyPair::with_secret(
471			Secret::from_str("a100df7a048e50ed308ea696dc600215098141cb391e9527329df289f9383f65").unwrap(),
472			H256::from_low_u64_be(64),
473		);
474        assert_eq!(
475			**keypair.derive(2_147_483_648u32.into()).expect("Derivation of keypair should succeed").secret().as_raw(),
476			H256::from_str("edef54414c03196557cf73774bc97a645c9a1df2164ed34f0c2a78d1375a930c").unwrap(),
477		);
478    }
479
480    #[test]
481    fn h256_soft_match() {
482        let secret = Secret::from_str(
483            "a100df7a048e50ed308ea696dc600215098141cb391e9527329df289f9383f65",
484        )
485        .unwrap();
486        let derivation_secret = H256::from_str(
487            "51eaf04f9dbbc1417dc97e789edd0c37ecda88bac490434e367ea81b71b7b015",
488        )
489        .unwrap();
490
491        let extended_secret = ExtendedSecret::with_code(secret, H256::zero());
492        let extended_public = ExtendedPublic::from_secret(&extended_secret)
493            .expect("Extended public should be created");
494
495        let derived_secret0 =
496            extended_secret.derive(Derivation::Soft(derivation_secret));
497        let derived_public0 = extended_public
498            .derive(Derivation::Soft(derivation_secret))
499            .expect("First derivation of public should succeed");
500
501        let public_from_secret0 = ExtendedPublic::from_secret(&derived_secret0)
502            .expect("Extended public should be created");
503
504        assert_eq!(public_from_secret0.public(), derived_public0.public());
505    }
506
507    #[test]
508    fn h256_hard() {
509        let secret = Secret::from_str(
510            "a100df7a048e50ed308ea696dc600215098141cb391e9527329df289f9383f65",
511        )
512        .unwrap();
513        let derivation_secret = H256::from_str(
514            "51eaf04f9dbbc1417dc97e789edd0c37ecda88bac490434e367ea81b71b7b015",
515        )
516        .unwrap();
517        let extended_secret =
518            ExtendedSecret::with_code(secret, H256::from_low_u64_be(1));
519
520        assert_eq!(
521			**extended_secret.derive(Derivation::Hard(derivation_secret)).as_raw(),
522			H256::from_str("2bc2d696fb744d77ff813b4a1ef0ad64e1e5188b622c54ba917acc5ebc7c5486").unwrap(),
523		);
524    }
525
526    #[test]
527    fn match_() {
528        let secret = Secret::from_str(
529            "a100df7a048e50ed308ea696dc600215098141cb391e9527329df289f9383f65",
530        )
531        .unwrap();
532        let extended_secret =
533            ExtendedSecret::with_code(secret, H256::from_low_u64_be(1));
534        let extended_public = ExtendedPublic::from_secret(&extended_secret)
535            .expect("Extended public should be created");
536
537        let derived_secret0 = extended_secret.derive(0.into());
538        let derived_public0 = extended_public
539            .derive(0.into())
540            .expect("First derivation of public should succeed");
541
542        let public_from_secret0 = ExtendedPublic::from_secret(&derived_secret0)
543            .expect("Extended public should be created");
544
545        assert_eq!(public_from_secret0.public(), derived_public0.public());
546    }
547
548    #[test]
549    fn test_seeds() {
550        let seed = H128::from_str("000102030405060708090a0b0c0d0e0f")
551            .expect("Seed should be valid H128")
552            .as_bytes()
553            .to_vec();
554
555        // private key from bitcoin test vector
556        // xprv9wTYmMFdV23N2TdNG573QoEsfRrWKQgWeibmLntzniatZvR9BmLnvSxqu53Kw1UmYPxLgboyZQaXwTCg8MSY3H2EU4pWcQDnRnrVA1xe8fs
557        let test_private = H256::from_str(
558            "e8f32e723decf4051aefac8e2c93c9c5b214313817cdb01a1494b917c8436b35",
559        )
560        .expect("Private should be decoded ok");
561
562        let (private_seed, _) = derivation::seed_pair(&*seed);
563
564        assert_eq!(private_seed, test_private);
565    }
566
567    #[test]
568    fn test_vector_1() {
569        // xprv9uHRZZhk6KAJC1avXpDAp4MDc3sQKNxDiPvvkX8Br5ngLNv1TxvUxt4cV1rGL5hj6KCesnDYUhd7oWgT11eZG7XnxHrnYeSvkzY7d2bhkJ7
570        // H(0)
571        test_extended(
572			|secret| secret.derive(2_147_483_648.into()),
573			H256::from_str("edb2e14f9ee77d26dd93b4ecede8d16ed408ce149b6cd80b0715a2d911a0afea")
574				.expect("Private should be decoded ok")
575		);
576    }
577
578    #[test]
579    fn test_vector_2() {
580        // xprv9wTYmMFdV23N2TdNG573QoEsfRrWKQgWeibmLntzniatZvR9BmLnvSxqu53Kw1UmYPxLgboyZQaXwTCg8MSY3H2EU4pWcQDnRnrVA1xe8fs
581        // H(0)/1
582        test_extended(
583			|secret| secret.derive(2_147_483_648.into()).derive(1.into()),
584			H256::from_str("3c6cb8d0f6a264c91ea8b5030fadaa8e538b020f0a387421a12de9319dc93368")
585				.expect("Private should be decoded ok")
586		);
587    }
588}
cfxkey/extended.rs

cfxkey/
extended.rs
