Skip to main content

mnemo_engine/keys/
recovery.rs

1//! 12.3: the recovery code, version 1 (the keys note, section 3).
2//!
3//! `MN1-` and thirteen groups of five Crockford Base32 symbols: four data
4//! symbols and a check. The 256-bit key, most significant bit first, then
5//! four zero bits, makes the 52 data symbols. Group `i`'s check is
6//! `i ⊕ α·d0 ⊕ α²·d1 ⊕ α³·d2 ⊕ α⁴·d3` in GF(32) with x⁵ + x² + 1 and α = x,
7//! which catches any one wrong character in a group, any two swapped within
8//! it, and a group typed in another group's place.
9
10use zeroize::Zeroizing;
11
12/// The Crockford Base32 alphabet (no I, L, O or U).
13const ALPHABET: &[u8; 32] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ";
14/// The version prefix.
15const PREFIX: &str = "MN1";
16/// Groups in a code.
17const GROUPS: usize = 13;
18/// Symbols in a group on screen: four data symbols and the check.
19const GROUP_LEN: usize = 5;
20/// Symbols after the prefix.
21const SYMBOLS: usize = GROUPS * GROUP_LEN;
22
23/// x⁵ + x² + 1, the field's polynomial.
24const POLY: u8 = 0b10_0101;
25
26/// Multiply in GF(32).
27fn 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
42/// The weights α¹ to α⁴ of the four data positions (α = 2).
43const WEIGHTS: [u8; 4] = [2, 4, 8, 16];
44
45/// Group `i`'s check symbol over its data symbols `d`.
46fn 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
54/// The code for `key`, as shown: `MN1-` and thirteen hyphenated groups.
55pub 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
73/// The 52 data symbols of `key` (256 bits, then four zero bits).
74fn 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/// Why a typed code was refused. The message names the group (counted
89/// from 1) where it can.
90#[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
101/// One typed character's symbol value, with Crockford's aliases (`I`, `L`
102/// read as `1`, `O` as `0`), case ignored.
103fn 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
115/// Whether `text` looks like a recovery code (it starts with the prefix,
116/// read with the aliases), so a caller can report its errors as a code's.
117pub fn looks_like_code(text: &str) -> bool {
118    let t: String = text.trim().chars().take(3).collect();
119    // M, N and 1 are symbols 20, 21 and 1.
120    t.chars().count() == 3
121        && t.chars().map(symbol).collect::<Option<Vec<_>>>() == Some(vec![20, 21, 1])
122}
123
124/// Read a typed code back into its key.
125///
126/// Case and spaces are ignored, `I`/`L` read as `1` and `O` as `0` (the
127/// prefix included). With the right length, hyphens are ignored wherever
128/// they are. With the wrong length, the hyphens, when there are any, say
129/// which group is short or long; otherwise the error names "group N or the
130/// one before it", or the last group when every complete group checks out.
131pub 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    // The last data symbol holds one key bit and four zero bits.
174    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
195/// Whether group `i` (its five symbols) checks out.
196fn 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
200/// The message for a code of the wrong length.
201fn wrong_length(body: &str, values: &[u8]) -> String {
202    let count = format!(
203        "{} characters after {PREFIX}, {SYMBOLS} expected",
204        values.len()
205    );
206    // With hyphens, the person's own grouping says where.
207    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        // 40R4 with i = 1: 1 ⊕ 8 ⊕ 0 ⊕ 30 ⊕ 10 = 29, which is X.
254        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}