Skip to main content

alien_signing/
recovery.rs

1//! The recovery code and the key it derives.
2//!
3//! The code is 128 random bits, shown once to the first admin as 32
4//! characters: the bits and a 32-bit check, in Crockford base32. The key is
5//! derived from it with HKDF-SHA256 to 48 bytes and reduced into the P-256
6//! scalar range (FIPS 186-5 A.2.1), so the same code always gives the same
7//! key and the code is never stored anywhere.
8
9use std::fmt;
10
11use alien_error::AlienError;
12use hmac::{Hmac, Mac};
13use sha2::{Digest, Sha256};
14
15use crate::error::{ErrorData, Result};
16use crate::key::SecretKey;
17
18const ALPHABET: &[u8; 32] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ";
19const SECRET_BYTES: usize = 16;
20const CHECK_BYTES: usize = 4;
21
22/// P-256 group order minus one, big-endian.
23const ORDER_MINUS_ONE: [u64; 4] = [
24    0xFFFF_FFFF_0000_0000,
25    0xFFFF_FFFF_FFFF_FFFF,
26    0xBCE6_FAAD_A717_9E84,
27    0xF3B9_CAC2_FC63_2550,
28];
29
30/// A recovery code.
31#[derive(Clone, PartialEq, Eq)]
32pub struct RecoveryCode([u8; SECRET_BYTES]);
33
34impl fmt::Debug for RecoveryCode {
35    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
36        f.write_str("RecoveryCode(..)")
37    }
38}
39
40impl RecoveryCode {
41    /// A new code from the operating system's generator.
42    pub fn generate() -> Result<Self> {
43        let mut secret = [0u8; SECRET_BYTES];
44        getrandom::fill(&mut secret)
45            .map_err(|error| invalid(format!("the system random source failed: {error}")))?;
46        Ok(Self(secret))
47    }
48
49    /// Read a code as the admin typed it. Case, spaces and dashes don't
50    /// matter, and the letters people confuse with digits read as those
51    /// digits. A typo fails the check rather than deriving another key.
52    pub fn parse(text: &str) -> Result<Self> {
53        let mut bits: u128 = 0;
54        let mut extra: u64 = 0;
55        let mut count = 0usize;
56        for character in text.chars() {
57            if character == '-' || character.is_whitespace() {
58                continue;
59            }
60            let value = decode_char(character)
61                .ok_or_else(|| invalid(format!("'{character}' is not in a recovery code")))?;
62            // The first 128 bits are the secret, the last 32 the check.
63            if count < 25 {
64                bits = (bits << 5) | u128::from(value);
65            } else if count == 25 {
66                bits = (bits << 3) | u128::from(value >> 2);
67                extra = u64::from(value & 0b11);
68            } else {
69                extra = (extra << 5) | u64::from(value);
70            }
71            count += 1;
72        }
73        if count != 32 {
74            return Err(invalid("a recovery code has 32 characters"));
75        }
76        let secret = bits.to_be_bytes();
77        let code = Self(secret);
78        if extra != u64::from(u32::from_be_bytes(code.check())) {
79            return Err(invalid(
80                "the recovery code doesn't check out; look for a mistyped character",
81            ));
82        }
83        Ok(code)
84    }
85
86    /// The code in groups of four, as shown to the admin.
87    pub fn display(&self) -> String {
88        let mut bytes = [0u8; SECRET_BYTES + CHECK_BYTES];
89        bytes[..SECRET_BYTES].copy_from_slice(&self.0);
90        bytes[SECRET_BYTES..].copy_from_slice(&self.check());
91        let characters = encode(&bytes);
92        characters
93            .as_bytes()
94            .chunks(4)
95            .map(|chunk| String::from_utf8_lossy(chunk).into_owned())
96            .collect::<Vec<_>>()
97            .join("-")
98    }
99
100    /// Whether `typed` is the last four characters of the code, read as
101    /// [`parse`](Self::parse) reads them. Those characters are part of the
102    /// check, not of the secret, so asking for them proves the admin saw the
103    /// code without typing it back.
104    pub fn ends_with(&self, typed: &str) -> bool {
105        let typed: Vec<char> = typed
106            .chars()
107            .filter(|character| *character != '-' && !character.is_whitespace())
108            .collect();
109        if typed.len() != 4 {
110            return false;
111        }
112        let shown = self.display().replace('-', "");
113        let tail = &shown.as_bytes()[shown.len() - 4..];
114        typed
115            .iter()
116            .zip(tail)
117            .all(|(character, expected)| decode_char(*character) == decode_char(*expected as char))
118    }
119
120    /// The recovery key of `project`.
121    pub fn key(&self, project: &str) -> Result<SecretKey> {
122        let okm = hkdf_sha256(&self.0, format!("recovery\u{0}{project}").as_bytes())?;
123        let mut scalar = reduce_mod_order_minus_one(&okm);
124        add_one(&mut scalar);
125        let mut bytes = [0u8; 32];
126        for (index, limb) in scalar.iter().enumerate() {
127            bytes[index * 8..index * 8 + 8].copy_from_slice(&limb.to_be_bytes());
128        }
129        SecretKey::from_secret_bytes(&bytes)
130    }
131
132    fn check(&self) -> [u8; CHECK_BYTES] {
133        let digest = Sha256::digest(self.0);
134        [digest[0], digest[1], digest[2], digest[3]]
135    }
136}
137
138/// Crockford base32 of `bytes`, without padding. `bytes` is a multiple of 5.
139pub fn encode(bytes: &[u8]) -> String {
140    let mut out = String::new();
141    for chunk in bytes.chunks(5) {
142        let mut buffer = [0u8; 8];
143        buffer[3..3 + chunk.len()].copy_from_slice(chunk);
144        let value = u64::from_be_bytes(buffer);
145        for index in (0..chunk.len() * 8 / 5).rev() {
146            out.push(ALPHABET[((value >> (index * 5)) & 31) as usize] as char);
147        }
148    }
149    out
150}
151
152fn decode_char(character: char) -> Option<u8> {
153    let character = match character.to_ascii_uppercase() {
154        'O' => '0',
155        'I' | 'L' => '1',
156        other => other,
157    };
158    ALPHABET
159        .iter()
160        .position(|&letter| letter as char == character)
161        .map(|position| position as u8)
162}
163
164fn hkdf_sha256(ikm: &[u8], info: &[u8]) -> Result<[u8; 48]> {
165    let mut extract =
166        Hmac::<Sha256>::new_from_slice(&[0u8; 32]).map_err(|_| invalid("HKDF could not start"))?;
167    extract.update(ikm);
168    let prk = extract.finalize().into_bytes();
169    let mut okm = [0u8; 48];
170    let mut previous: Vec<u8> = Vec::new();
171    for (counter, block) in okm.chunks_mut(32).enumerate() {
172        let mut expand =
173            Hmac::<Sha256>::new_from_slice(&prk).map_err(|_| invalid("HKDF could not expand"))?;
174        expand.update(&previous);
175        expand.update(info);
176        expand.update(&[counter as u8 + 1]);
177        let output = expand.finalize().into_bytes();
178        block.copy_from_slice(&output[..block.len()]);
179        previous = output.to_vec();
180    }
181    Ok(okm)
182}
183
184/// `value mod (n - 1)`, one bit at a time; the input is 384 bits.
185fn reduce_mod_order_minus_one(value: &[u8; 48]) -> [u64; 4] {
186    // Five limbs leave room for the shifted remainder before subtracting.
187    let modulus = [
188        0,
189        ORDER_MINUS_ONE[0],
190        ORDER_MINUS_ONE[1],
191        ORDER_MINUS_ONE[2],
192        ORDER_MINUS_ONE[3],
193    ];
194    let mut remainder = [0u64; 5];
195    for byte in value {
196        for bit in (0..8).rev() {
197            let mut carry = u64::from((byte >> bit) & 1);
198            for limb in remainder.iter_mut().rev() {
199                let next = *limb >> 63;
200                *limb = (*limb << 1) | carry;
201                carry = next;
202            }
203            if remainder >= modulus {
204                let mut borrow = 0u64;
205                for index in (0..5).rev() {
206                    let (difference, first) = remainder[index].overflowing_sub(modulus[index]);
207                    let (difference, second) = difference.overflowing_sub(borrow);
208                    remainder[index] = difference;
209                    borrow = u64::from(first || second);
210                }
211            }
212        }
213    }
214    [remainder[1], remainder[2], remainder[3], remainder[4]]
215}
216
217fn add_one(value: &mut [u64; 4]) {
218    for limb in value.iter_mut().rev() {
219        let (sum, overflow) = limb.overflowing_add(1);
220        *limb = sum;
221        if !overflow {
222            return;
223        }
224    }
225}
226
227fn invalid(reason: impl Into<String>) -> AlienError<ErrorData> {
228    AlienError::new(ErrorData::KeyInvalid {
229        reason: reason.into(),
230    })
231}
232
233#[cfg(test)]
234mod tests {
235    use super::*;
236
237    #[test]
238    fn a_code_reads_back_as_typed_and_derives_the_same_key() {
239        let code = RecoveryCode::generate().unwrap();
240        let shown = code.display();
241        assert_eq!(shown.len(), 39, "{shown}");
242        let typed = shown.to_lowercase().replace('-', " ");
243        let read = RecoveryCode::parse(&typed).unwrap();
244        assert_eq!(read, code);
245        assert_eq!(
246            read.key("prj_a").unwrap().public_key(),
247            code.key("prj_a").unwrap().public_key()
248        );
249        assert_ne!(
250            code.key("prj_a").unwrap().public_key(),
251            code.key("prj_b").unwrap().public_key()
252        );
253    }
254
255    #[test]
256    fn the_last_four_characters_are_checked_as_typed() {
257        let code = RecoveryCode([7u8; SECRET_BYTES]);
258        let other = RecoveryCode([9u8; SECRET_BYTES]);
259        let shown = code.display();
260        let tail = &shown[shown.len() - 4..];
261        let other_shown = other.display();
262        assert_ne!(tail, &other_shown[other_shown.len() - 4..]);
263        assert_ne!(tail, &shown[..4]);
264
265        assert!(code.ends_with(tail));
266        assert!(code.ends_with(&tail.to_lowercase()));
267        assert!(code.ends_with(&format!("  {tail}\n")));
268        assert!(!code.ends_with(""));
269        assert!(!code.ends_with(&shown[shown.len() - 3..]));
270        assert!(!code.ends_with(&shown[shown.len() - 6..]));
271        assert!(!code.ends_with(&shown[..4]));
272        assert!(!code.ends_with(&other_shown[other_shown.len() - 4..]));
273    }
274
275    #[test]
276    fn a_mistyped_code_is_refused() {
277        let shown = RecoveryCode::generate().unwrap().display();
278        let mut characters: Vec<char> = shown.chars().collect();
279        characters[0] = if characters[0] == 'A' { 'B' } else { 'A' };
280        let typo: String = characters.into_iter().collect();
281        RecoveryCode::parse(&typo).expect_err("typo");
282        RecoveryCode::parse(&shown[..30]).expect_err("short");
283    }
284
285    #[test]
286    fn hkdf_matches_rfc_5869_case_3() {
287        // RFC 5869 A.3: zero-length salt and info, 42 bytes out. The salt of
288        // HMAC-SHA256's block of zeros equals a zero-length salt.
289        let ikm = [0x0bu8; 22];
290        let okm = hkdf_sha256(&ikm, b"").unwrap();
291        assert_eq!(
292            hex::encode(&okm[..42]),
293            "8da4e775a563c18f715f802a063c5a31b8a11f5c5ee1879ec3454e5f3c738d2d9d201395faa4b61a96c8"
294        );
295    }
296
297    #[test]
298    fn reduction_keeps_small_values_and_wraps_at_the_order() {
299        let mut small = [0u8; 48];
300        small[47] = 7;
301        assert_eq!(reduce_mod_order_minus_one(&small), [0, 0, 0, 7]);
302        let mut order_minus_one = [0u8; 48];
303        for (index, limb) in ORDER_MINUS_ONE.iter().enumerate() {
304            order_minus_one[16 + index * 8..24 + index * 8].copy_from_slice(&limb.to_be_bytes());
305        }
306        assert_eq!(reduce_mod_order_minus_one(&order_minus_one), [0, 0, 0, 0]);
307        order_minus_one[47] += 1;
308        assert_eq!(reduce_mod_order_minus_one(&order_minus_one), [0, 0, 0, 1]);
309    }
310}