alien_signing/
recovery.rs1use 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
22const 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#[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 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 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 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 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 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 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
138pub 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
184fn reduce_mod_order_minus_one(value: &[u8; 48]) -> [u64; 4] {
186 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 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}