Skip to main content

second_brain_core/keys/
recovery.rs

1use std::fmt;
2
3use age::x25519::{Identity, Recipient};
4use anyhow::{Result, anyhow, bail};
5use hkdf::Hkdf;
6use rusqlite::{OptionalExtension, params};
7use sha2::{Digest, Sha256};
8use zeroize::Zeroizing;
9
10use super::tables::query_envelopes;
11use super::{Envelope, Epoch, IdentityKey, IdentityTag, KeyGuard, hex, wrap};
12use crate::sqlite_store::SqliteStore;
13
14const ENTROPY_LEN: usize = 16;
15const CHECKSUM_LEN: usize = 4;
16const ENCODED_LEN: usize = (ENTROPY_LEN + CHECKSUM_LEN) * 8 / 5;
17const GROUP_LEN: usize = 4;
18const ALPHABET: &[u8; 32] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ";
19const SECRET_KEY_HRP: &str = "age-secret-key-";
20const IDENTITY_SALT: &[u8] = b"second-brain recovery phrase v1";
21const IDENTITY_INFO: &[u8] = b"x25519 recipient";
22const CHECKSUM_DOMAIN: &[u8] = b"second-brain recovery checksum v1";
23const FINGERPRINT_DOMAIN: &[u8] = b"second-brain recovery fingerprint v1";
24const OFFERED_KEY: &str = "recovery_offered_at";
25
26/// A generated recovery secret of 128 bits. It only decrypts: one X25519
27/// recipient derives from it, and every epoch a device holds is wrapped to
28/// that recipient. It is never stored; `Debug` shows only its fingerprint.
29pub struct RecoveryPhrase(KeyGuard<[u8; ENTROPY_LEN]>);
30
31impl RecoveryPhrase {
32    pub fn generate() -> Result<Self> {
33        Ok(Self(KeyGuard::random()?))
34    }
35
36    /// Accepts the phrase in any case, with or without spaces and dashes,
37    /// reading O as 0 and I or L as 1. A wrong checksum is reported as a
38    /// typo, never as a different key.
39    pub fn parse(text: &str) -> Result<Self> {
40        let mut values = Zeroizing::new(Vec::with_capacity(ENCODED_LEN));
41        for c in text.chars() {
42            if c.is_whitespace() || c == '-' {
43                continue;
44            }
45            let c = match c.to_ascii_uppercase() {
46                'O' => '0',
47                'I' | 'L' => '1',
48                other => other,
49            };
50            let Some(value) = ALPHABET.iter().position(|&a| char::from(a) == c) else {
51                bail!("a recovery phrase holds only letters and digits; {c:?} is not one");
52            };
53            values.push(value as u8);
54        }
55        if values.len() != ENCODED_LEN {
56            bail!(
57                "a recovery phrase has {ENCODED_LEN} letters and digits, this one has {}",
58                values.len()
59            );
60        }
61        let bytes = unpack(&values);
62        let mut entropy = KeyGuard::new([0u8; ENTROPY_LEN]);
63        entropy.expose_mut().copy_from_slice(&bytes[..ENTROPY_LEN]);
64        if bytes[ENTROPY_LEN..] != checksum(entropy.expose()) {
65            bail!("the recovery phrase has a typo: its check letters do not match");
66        }
67        Ok(Self(entropy))
68    }
69
70    /// The phrase as shown to the user: groups of four separated by dashes.
71    pub fn expose_text(&self) -> Zeroizing<String> {
72        let mut bytes = Zeroizing::new(Vec::with_capacity(ENTROPY_LEN + CHECKSUM_LEN));
73        bytes.extend_from_slice(self.0.expose());
74        bytes.extend_from_slice(&checksum(self.0.expose()));
75        let values = pack(&bytes);
76        let mut text = Zeroizing::new(String::with_capacity(ENCODED_LEN + ENCODED_LEN / GROUP_LEN));
77        for (i, value) in values.iter().enumerate() {
78            if i > 0 && i % GROUP_LEN == 0 {
79                text.push('-');
80            }
81            text.push(char::from(ALPHABET[usize::from(*value)]));
82        }
83        text
84    }
85
86    pub fn identity(&self) -> Result<Identity> {
87        let mut secret = Zeroizing::new([0u8; 32]);
88        Hkdf::<Sha256>::new(Some(IDENTITY_SALT), self.0.expose())
89            .expand(IDENTITY_INFO, secret.as_mut())
90            .map_err(|e| anyhow!("deriving the recovery key: {e}"))?;
91        let hrp =
92            bech32::Hrp::parse(SECRET_KEY_HRP).map_err(|e| anyhow!("recovery key prefix: {e}"))?;
93        let encoded = Zeroizing::new(
94            bech32::encode_upper::<bech32::Bech32>(hrp, secret.as_ref())
95                .map_err(|e| anyhow!("encoding the recovery key: {e}"))?,
96        );
97        encoded
98            .parse::<Identity>()
99            .map_err(|e| anyhow!("building the recovery key: {e}"))
100    }
101
102    pub fn recipient(&self) -> Result<Recipient> {
103        Ok(self.identity()?.to_public())
104    }
105
106    pub fn fingerprint(&self) -> Result<String> {
107        Ok(recovery_fingerprint(&self.recipient()?.to_string()))
108    }
109}
110
111impl fmt::Debug for RecoveryPhrase {
112    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
113        match self.fingerprint() {
114            Ok(fingerprint) => write!(f, "RecoveryPhrase({fingerprint})"),
115            Err(_) => f.write_str("RecoveryPhrase(..)"),
116        }
117    }
118}
119
120/// The 16 hex characters a device lists in its signed row for a recovery
121/// recipient, so the user can tell phrases apart without seeing them.
122pub fn recovery_fingerprint(recipient: &str) -> String {
123    let digest = Sha256::new()
124        .chain_update(FINGERPRINT_DOMAIN)
125        .chain_update(recipient.as_bytes())
126        .finalize();
127    hex(&digest[..8])
128}
129
130fn checksum(entropy: &[u8; ENTROPY_LEN]) -> [u8; CHECKSUM_LEN] {
131    let digest = Sha256::new()
132        .chain_update(CHECKSUM_DOMAIN)
133        .chain_update(entropy)
134        .finalize();
135    let mut out = [0u8; CHECKSUM_LEN];
136    out.copy_from_slice(&digest[..CHECKSUM_LEN]);
137    out
138}
139
140fn pack(bytes: &[u8]) -> Zeroizing<Vec<u8>> {
141    let mut out = Zeroizing::new(Vec::with_capacity(bytes.len() * 8 / 5));
142    let mut acc: u16 = 0;
143    let mut bits = 0;
144    for &byte in bytes {
145        acc = (acc << 8) | u16::from(byte);
146        bits += 8;
147        while bits >= 5 {
148            bits -= 5;
149            out.push(((acc >> bits) & 0x1f) as u8);
150        }
151        acc &= (1 << bits) - 1;
152    }
153    out
154}
155
156fn unpack(values: &[u8]) -> Zeroizing<Vec<u8>> {
157    let mut out = Zeroizing::new(Vec::with_capacity(values.len() * 5 / 8));
158    let mut acc: u16 = 0;
159    let mut bits = 0;
160    for &value in values {
161        acc = (acc << 5) | u16::from(value);
162        bits += 5;
163        if bits >= 8 {
164            bits -= 8;
165            out.push((acc >> bits) as u8);
166        }
167        acc &= (1 << bits) - 1;
168    }
169    out
170}
171
172/// Wraps every held epoch to each recipient that lacks an envelope for it
173/// and is not retired, under `tag`, with no machine id. Returns how many
174/// envelopes were added.
175pub fn wrap_for_recovery(
176    store: &SqliteStore,
177    tag: &IdentityTag,
178    held: &[(Epoch, &IdentityKey)],
179    recipients: &[Recipient],
180) -> Result<usize> {
181    let retired = store.retired_fingerprints()?;
182    let mut added = 0;
183    for recipient in recipients {
184        let text = recipient.to_string();
185        if retired.contains(&recovery_fingerprint(&text)) {
186            continue;
187        }
188        for (epoch, key) in held {
189            if store.envelope(tag, epoch, &text)?.is_some() {
190                continue;
191            }
192            if store.put_envelope(&wrap(key, epoch.number, tag, recipient, None)?)? {
193                added += 1;
194            }
195        }
196    }
197    Ok(added)
198}
199
200impl SqliteStore {
201    /// The recovery recipients this device wraps `tag`'s epochs to: the
202    /// recipients of its envelopes that name no machine, less retired ones.
203    /// Handshakes only store envelopes addressed to this machine, so a peer
204    /// never adds one.
205    pub fn recovery_recipients(&self, tag: &IdentityTag) -> Result<Vec<Recipient>> {
206        let retired = self.retired_fingerprints()?;
207        let conn = self.reader();
208        let mut stmt = conn.prepare(
209            "SELECT DISTINCT recipient FROM key_envelopes \
210             WHERE identity_tag = ?1 AND machine_id IS NULL ORDER BY recipient",
211        )?;
212        let texts = stmt
213            .query_map(params![tag.as_str()], |r| r.get::<_, String>(0))?
214            .collect::<rusqlite::Result<Vec<_>>>()?;
215        texts
216            .iter()
217            .filter(|text| !retired.contains(&recovery_fingerprint(text)))
218            .map(|text| {
219                text.parse::<Recipient>()
220                    .map_err(|e| anyhow!("recovery recipient {text} is invalid: {e}"))
221            })
222            .collect()
223    }
224
225    /// Every envelope, under any identity, wrapped to `recipient` with no
226    /// machine id.
227    pub fn recovery_envelopes(&self, recipient: &Recipient) -> Result<Vec<Envelope>> {
228        let conn = self.reader();
229        query_envelopes(
230            &conn,
231            "recipient = ?1 AND machine_id IS NULL",
232            params![recipient.to_string()],
233        )
234    }
235
236    pub fn recovery_offered(&self) -> Result<bool> {
237        let value: Option<String> = self
238            .reader()
239            .query_row(
240                "SELECT value FROM index_meta WHERE key = ?1",
241                params![OFFERED_KEY],
242                |r| r.get(0),
243            )
244            .optional()?;
245        Ok(value.is_some())
246    }
247
248    pub fn mark_recovery_offered(&self, now_micros: i64) -> Result<()> {
249        self.conn().execute(
250            "INSERT OR IGNORE INTO index_meta (key, value) VALUES (?1, ?2)",
251            params![OFFERED_KEY, now_micros.to_string()],
252        )?;
253        Ok(())
254    }
255}
256
257#[cfg(test)]
258mod tests {
259    use super::*;
260
261    #[test]
262    fn a_phrase_reads_back_to_the_same_recipient() {
263        let phrase = RecoveryPhrase::generate().unwrap();
264        let text = phrase.expose_text();
265        assert_eq!(text.len(), ENCODED_LEN + ENCODED_LEN / GROUP_LEN - 1);
266        assert_eq!(text.split('-').count(), ENCODED_LEN / GROUP_LEN);
267        let parsed = RecoveryPhrase::parse(&text).unwrap();
268        assert_eq!(
269            parsed.recipient().unwrap().to_string(),
270            phrase.recipient().unwrap().to_string()
271        );
272        assert_eq!(parsed.fingerprint().unwrap(), phrase.fingerprint().unwrap());
273    }
274
275    #[test]
276    fn a_phrase_is_read_in_any_case_and_spacing_with_lookalike_letters() {
277        let phrase = RecoveryPhrase::generate().unwrap();
278        let text = phrase.expose_text();
279        let loose: String = text
280            .chars()
281            .filter(|c| *c != '-')
282            .map(|c| match c {
283                '0' => 'o',
284                '1' => 'l',
285                other => other.to_ascii_lowercase(),
286            })
287            .collect::<Vec<_>>()
288            .chunks(5)
289            .map(|chunk| chunk.iter().collect::<String>())
290            .collect::<Vec<_>>()
291            .join("  ");
292        let parsed = RecoveryPhrase::parse(&loose).unwrap();
293        assert_eq!(parsed.fingerprint().unwrap(), phrase.fingerprint().unwrap());
294    }
295
296    #[test]
297    fn a_typo_is_reported_as_a_typo() {
298        let phrase = RecoveryPhrase::generate().unwrap();
299        let mut text: Vec<char> = phrase.expose_text().chars().collect();
300        text[0] = if text[0] == 'A' { 'B' } else { 'A' };
301        let typo: String = text.into_iter().collect();
302        let err = format!("{:#}", RecoveryPhrase::parse(&typo).unwrap_err());
303        assert!(err.contains("typo"), "{err}");
304
305        let short = &phrase.expose_text()[..10];
306        let err = format!("{:#}", RecoveryPhrase::parse(short).unwrap_err());
307        assert!(err.contains("letters and digits"), "{err}");
308        let err = format!("{:#}", RecoveryPhrase::parse("U!").unwrap_err());
309        assert!(err.contains("only letters"), "{err}");
310    }
311
312    #[test]
313    fn phrases_differ_and_debug_shows_only_the_fingerprint() {
314        let a = RecoveryPhrase::generate().unwrap();
315        let b = RecoveryPhrase::generate().unwrap();
316        assert_ne!(a.fingerprint().unwrap(), b.fingerprint().unwrap());
317        let shown = format!("{a:?}");
318        assert!(shown.contains(&a.fingerprint().unwrap()), "{shown}");
319        assert!(!shown.contains(a.expose_text().as_str()), "{shown}");
320        assert_eq!(a.fingerprint().unwrap().len(), 16);
321    }
322
323    #[test]
324    fn held_epochs_are_wrapped_once_to_each_recipient_and_open_with_the_phrase() {
325        let store = SqliteStore::in_memory("local".to_string()).unwrap();
326        let first = IdentityKey::generate().unwrap();
327        let second = IdentityKey::generate().unwrap();
328        let tag = IdentityTag::migrated(&first.key_id());
329        let epoch = |number, key: &IdentityKey| Epoch {
330            number,
331            key_id: key.key_id(),
332        };
333        let phrase = RecoveryPhrase::generate().unwrap();
334        let recipients = [phrase.recipient().unwrap()];
335
336        let held = [(epoch(0, &first), &first)];
337        assert_eq!(
338            wrap_for_recovery(&store, &tag, &held, &recipients).unwrap(),
339            1
340        );
341        let held = [(epoch(0, &first), &first), (epoch(1, &second), &second)];
342        assert_eq!(
343            wrap_for_recovery(&store, &tag, &held, &recipients).unwrap(),
344            1
345        );
346        assert_eq!(
347            wrap_for_recovery(&store, &tag, &held, &recipients).unwrap(),
348            0
349        );
350
351        let found = store.recovery_recipients(&tag).unwrap();
352        assert_eq!(found.len(), 1);
353        assert_eq!(found[0].to_string(), recipients[0].to_string());
354        let envelopes = store.recovery_envelopes(&recipients[0]).unwrap();
355        assert_eq!(envelopes.len(), 2);
356        let reparsed = RecoveryPhrase::parse(&phrase.expose_text()).unwrap();
357        let identity = reparsed.identity().unwrap();
358        for envelope in &envelopes {
359            assert_eq!(envelope.machine_id, None);
360            envelope.open(&identity).unwrap();
361        }
362        assert!(store.envelopes_for_machine("local").unwrap().is_empty());
363    }
364
365    #[test]
366    fn envelopes_for_a_machine_are_not_recovery_recipients() {
367        let store = SqliteStore::in_memory("local".to_string()).unwrap();
368        let key = IdentityKey::generate().unwrap();
369        let tag = IdentityTag::migrated(&key.key_id());
370        let device = super::super::DeviceKeys::generate().unwrap();
371        store
372            .put_envelope(
373                &wrap(&key, 0, &tag, &device.age_recipient(), Some("local".into())).unwrap(),
374            )
375            .unwrap();
376        assert!(store.recovery_recipients(&tag).unwrap().is_empty());
377    }
378
379    #[test]
380    fn the_offer_is_remembered() {
381        let store = SqliteStore::in_memory("local".to_string()).unwrap();
382        assert!(!store.recovery_offered().unwrap());
383        store.mark_recovery_offered(5).unwrap();
384        store.mark_recovery_offered(9).unwrap();
385        assert!(store.recovery_offered().unwrap());
386    }
387}