mnemo_engine/keys/
recovery.rs1use zeroize::Zeroizing;
11
12const ALPHABET: &[u8; 32] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ";
14const PREFIX: &str = "MN1";
16const GROUPS: usize = 13;
18const GROUP_LEN: usize = 5;
20const SYMBOLS: usize = GROUPS * GROUP_LEN;
22
23const POLY: u8 = 0b10_0101;
25
26fn gmul(mut a: u8, mut b: u8) -> u8 {
28 let mut r = 0;
29 while b != 0 {
30 if b & 1 != 0 {
31 r ^= a;
32 }
33 b >>= 1;
34 a <<= 1;
35 if a & 0b10_0000 != 0 {
36 a ^= POLY;
37 }
38 }
39 r
40}
41
42const WEIGHTS: [u8; 4] = [2, 4, 8, 16];
44
45fn check(i: usize, d: &[u8; 4]) -> u8 {
47 let mut c = i as u8;
48 for (w, v) in WEIGHTS.iter().zip(d) {
49 c ^= gmul(*w, *v);
50 }
51 c
52}
53
54pub fn encode(key: &[u8; 32]) -> Zeroizing<String> {
56 let syms = data_symbols(key);
57 let mut out = Zeroizing::new(String::with_capacity(
58 PREFIX.len() + GROUPS * (GROUP_LEN + 1),
59 ));
60 out.push_str(PREFIX);
61 for i in 0..GROUPS {
62 let mut d = [0u8; 4];
63 d.copy_from_slice(&syms[4 * i..4 * i + 4]);
64 out.push('-');
65 for v in d {
66 out.push(ALPHABET[v as usize] as char);
67 }
68 out.push(ALPHABET[check(i, &d) as usize] as char);
69 }
70 out
71}
72
73fn data_symbols(key: &[u8; 32]) -> Zeroizing<[u8; 52]> {
75 let mut syms = Zeroizing::new([0u8; 52]);
76 for (k, sym) in syms.iter_mut().enumerate() {
77 let mut v = 0u8;
78 for b in 0..5 {
79 let bit = 5 * k + b;
80 let set = bit < 256 && key[bit / 8] & (0x80 >> (bit % 8)) != 0;
81 v = (v << 1) | u8::from(set);
82 }
83 *sym = v;
84 }
85 syms
86}
87
88#[derive(Debug, Clone, PartialEq, Eq)]
91pub struct CodeError(pub String);
92
93impl std::fmt::Display for CodeError {
94 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
95 f.write_str(&self.0)
96 }
97}
98
99impl std::error::Error for CodeError {}
100
101fn symbol(c: char) -> Option<u8> {
104 let c = match c.to_ascii_uppercase() {
105 'I' | 'L' => '1',
106 'O' => '0',
107 c => c,
108 };
109 ALPHABET
110 .iter()
111 .position(|&a| a as char == c)
112 .map(|p| p as u8)
113}
114
115pub fn looks_like_code(text: &str) -> bool {
118 let t: String = text.trim().chars().take(3).collect();
119 t.chars().count() == 3
121 && t.chars().map(symbol).collect::<Option<Vec<_>>>() == Some(vec![20, 21, 1])
122}
123
124pub fn parse(text: &str) -> Result<Zeroizing<[u8; 32]>, CodeError> {
132 let typed: Zeroizing<String> =
133 Zeroizing::new(text.chars().filter(|c| !c.is_whitespace()).collect());
134 if !looks_like_code(&typed) {
135 return Err(CodeError(
136 "a recovery code starts with MN1 (this one doesn't, or it was made by a newer mnemo)"
137 .into(),
138 ));
139 }
140 let body = typed[3..].trim_start_matches('-');
141 let mut values: Zeroizing<Vec<u8>> = Zeroizing::new(Vec::with_capacity(SYMBOLS));
142 for (pos, c) in body.chars().filter(|&c| c != '-').enumerate() {
143 match symbol(c) {
144 Some(v) => values.push(v),
145 None => {
146 return Err(CodeError(format!(
147 "{:?} isn't a recovery-code character (group {})",
148 c,
149 (pos / GROUP_LEN + 1).min(GROUPS)
150 )))
151 }
152 }
153 }
154 if values.len() != SYMBOLS {
155 return Err(CodeError(wrong_length(body, &values)));
156 }
157 let bad: Vec<usize> = (0..GROUPS)
158 .filter(|&i| !group_checks(i, &values[GROUP_LEN * i..GROUP_LEN * i + GROUP_LEN]))
159 .collect();
160 if !bad.is_empty() {
161 let names: Vec<String> = bad.iter().map(|i| (i + 1).to_string()).collect();
162 return Err(CodeError(match names.len() {
163 1 => format!(
164 "group {} doesn't check out; look for a typo there",
165 names[0]
166 ),
167 _ => format!(
168 "groups {} don't check out; look for typos there",
169 names.join(", ")
170 ),
171 }));
172 }
173 let last = values[GROUP_LEN * (GROUPS - 1) + 3];
175 if last != 0 && last != 16 {
176 return Err(CodeError(format!(
177 "group {GROUPS} doesn't check out (its fourth character must be 0 or G)"
178 )));
179 }
180 let mut key = Zeroizing::new([0u8; 32]);
181 let mut bit = 0usize;
182 for i in 0..GROUPS {
183 for &v in &values[GROUP_LEN * i..GROUP_LEN * i + 4] {
184 for b in (0..5).rev() {
185 if bit < 256 && (v >> b) & 1 == 1 {
186 key[bit / 8] |= 0x80 >> (bit % 8);
187 }
188 bit += 1;
189 }
190 }
191 }
192 Ok(key)
193}
194
195fn group_checks(i: usize, g: &[u8]) -> bool {
197 g.len() == GROUP_LEN && check(i, &[g[0], g[1], g[2], g[3]]) == g[4]
198}
199
200fn wrong_length(body: &str, values: &[u8]) -> String {
202 let count = format!(
203 "{} characters after {PREFIX}, {SYMBOLS} expected",
204 values.len()
205 );
206 let parts: Vec<&str> = body.split('-').filter(|p| !p.is_empty()).collect();
208 if parts.len() > 1 {
209 let odd: Vec<String> = parts
210 .iter()
211 .enumerate()
212 .filter(|(_, p)| p.chars().count() != GROUP_LEN)
213 .map(|(i, p)| format!("group {} has {}", i + 1, p.chars().count()))
214 .collect();
215 if !odd.is_empty() {
216 return format!("{count}: {}, {GROUP_LEN} expected", odd.join(", "));
217 }
218 }
219 let complete = values.len() / GROUP_LEN;
220 let first_bad = (0..complete.min(GROUPS))
221 .find(|&i| !group_checks(i, &values[GROUP_LEN * i..GROUP_LEN * i + GROUP_LEN]));
222 match first_bad {
223 Some(0) => format!("{count}; group 1 doesn't check out, so look there"),
224 Some(i) => format!(
225 "{count}; groups 1 to {i} check out and group {} doesn't, so look in group {} or \
226 the one before it",
227 i + 1,
228 i + 1
229 ),
230 None => format!(
231 "{count}; every complete group checks out, so look in the last group ({})",
232 (complete + 1).min(GROUPS)
233 ),
234 }
235}
236
237#[cfg(test)]
238mod tests {
239 use super::*;
240
241 #[test]
242 fn the_worked_example_encodes_as_the_note_shows() {
243 let key: [u8; 32] = std::array::from_fn(|i| i as u8);
244 assert_eq!(
245 encode(&key).as_str(),
246 "MN1-000GD-40R4X-0M300-E209K-185G3-R38ED-1W811-24GKZ-2GAH1-C5RR2-34D1B-P70XX-3RFGZ"
247 );
248 assert_eq!(*parse(&encode(&key)).unwrap(), key);
249 }
250
251 #[test]
252 fn group_one_of_the_example_checks_as_the_note_works_it() {
253 assert_eq!(gmul(16, 4), 10);
255 assert_eq!(gmul(8, 24), 30);
256 assert_eq!(check(1, &[4, 0, 24, 4]), 29);
257 assert_eq!(ALPHABET[29], b'X');
258 }
259}