use std::fmt;
use alien_error::AlienError;
use hmac::{Hmac, Mac};
use sha2::{Digest, Sha256};
use crate::error::{ErrorData, Result};
use crate::key::SecretKey;
const ALPHABET: &[u8; 32] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ";
const SECRET_BYTES: usize = 16;
const CHECK_BYTES: usize = 4;
const ORDER_MINUS_ONE: [u64; 4] = [
0xFFFF_FFFF_0000_0000,
0xFFFF_FFFF_FFFF_FFFF,
0xBCE6_FAAD_A717_9E84,
0xF3B9_CAC2_FC63_2550,
];
#[derive(Clone, PartialEq, Eq)]
pub struct RecoveryCode([u8; SECRET_BYTES]);
impl fmt::Debug for RecoveryCode {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str("RecoveryCode(..)")
}
}
impl RecoveryCode {
pub fn generate() -> Result<Self> {
let mut secret = [0u8; SECRET_BYTES];
getrandom::fill(&mut secret)
.map_err(|error| invalid(format!("the system random source failed: {error}")))?;
Ok(Self(secret))
}
pub fn parse(text: &str) -> Result<Self> {
let mut bits: u128 = 0;
let mut extra: u64 = 0;
let mut count = 0usize;
for character in text.chars() {
if character == '-' || character.is_whitespace() {
continue;
}
let value = decode_char(character)
.ok_or_else(|| invalid(format!("'{character}' is not in a recovery code")))?;
if count < 25 {
bits = (bits << 5) | u128::from(value);
} else if count == 25 {
bits = (bits << 3) | u128::from(value >> 2);
extra = u64::from(value & 0b11);
} else {
extra = (extra << 5) | u64::from(value);
}
count += 1;
}
if count != 32 {
return Err(invalid("a recovery code has 32 characters"));
}
let secret = bits.to_be_bytes();
let code = Self(secret);
if extra != u64::from(u32::from_be_bytes(code.check())) {
return Err(invalid(
"the recovery code doesn't check out; look for a mistyped character",
));
}
Ok(code)
}
pub fn display(&self) -> String {
let mut bytes = [0u8; SECRET_BYTES + CHECK_BYTES];
bytes[..SECRET_BYTES].copy_from_slice(&self.0);
bytes[SECRET_BYTES..].copy_from_slice(&self.check());
let characters = encode(&bytes);
characters
.as_bytes()
.chunks(4)
.map(|chunk| String::from_utf8_lossy(chunk).into_owned())
.collect::<Vec<_>>()
.join("-")
}
pub fn ends_with(&self, typed: &str) -> bool {
let typed: Vec<char> = typed
.chars()
.filter(|character| *character != '-' && !character.is_whitespace())
.collect();
if typed.len() != 4 {
return false;
}
let shown = self.display().replace('-', "");
let tail = &shown.as_bytes()[shown.len() - 4..];
typed
.iter()
.zip(tail)
.all(|(character, expected)| decode_char(*character) == decode_char(*expected as char))
}
pub fn key(&self, project: &str) -> Result<SecretKey> {
let okm = hkdf_sha256(&self.0, format!("recovery\u{0}{project}").as_bytes())?;
let mut scalar = reduce_mod_order_minus_one(&okm);
add_one(&mut scalar);
let mut bytes = [0u8; 32];
for (index, limb) in scalar.iter().enumerate() {
bytes[index * 8..index * 8 + 8].copy_from_slice(&limb.to_be_bytes());
}
SecretKey::from_secret_bytes(&bytes)
}
fn check(&self) -> [u8; CHECK_BYTES] {
let digest = Sha256::digest(self.0);
[digest[0], digest[1], digest[2], digest[3]]
}
}
pub fn encode(bytes: &[u8]) -> String {
let mut out = String::new();
for chunk in bytes.chunks(5) {
let mut buffer = [0u8; 8];
buffer[3..3 + chunk.len()].copy_from_slice(chunk);
let value = u64::from_be_bytes(buffer);
for index in (0..chunk.len() * 8 / 5).rev() {
out.push(ALPHABET[((value >> (index * 5)) & 31) as usize] as char);
}
}
out
}
fn decode_char(character: char) -> Option<u8> {
let character = match character.to_ascii_uppercase() {
'O' => '0',
'I' | 'L' => '1',
other => other,
};
ALPHABET
.iter()
.position(|&letter| letter as char == character)
.map(|position| position as u8)
}
fn hkdf_sha256(ikm: &[u8], info: &[u8]) -> Result<[u8; 48]> {
let mut extract =
Hmac::<Sha256>::new_from_slice(&[0u8; 32]).map_err(|_| invalid("HKDF could not start"))?;
extract.update(ikm);
let prk = extract.finalize().into_bytes();
let mut okm = [0u8; 48];
let mut previous: Vec<u8> = Vec::new();
for (counter, block) in okm.chunks_mut(32).enumerate() {
let mut expand =
Hmac::<Sha256>::new_from_slice(&prk).map_err(|_| invalid("HKDF could not expand"))?;
expand.update(&previous);
expand.update(info);
expand.update(&[counter as u8 + 1]);
let output = expand.finalize().into_bytes();
block.copy_from_slice(&output[..block.len()]);
previous = output.to_vec();
}
Ok(okm)
}
fn reduce_mod_order_minus_one(value: &[u8; 48]) -> [u64; 4] {
let modulus = [
0,
ORDER_MINUS_ONE[0],
ORDER_MINUS_ONE[1],
ORDER_MINUS_ONE[2],
ORDER_MINUS_ONE[3],
];
let mut remainder = [0u64; 5];
for byte in value {
for bit in (0..8).rev() {
let mut carry = u64::from((byte >> bit) & 1);
for limb in remainder.iter_mut().rev() {
let next = *limb >> 63;
*limb = (*limb << 1) | carry;
carry = next;
}
if remainder >= modulus {
let mut borrow = 0u64;
for index in (0..5).rev() {
let (difference, first) = remainder[index].overflowing_sub(modulus[index]);
let (difference, second) = difference.overflowing_sub(borrow);
remainder[index] = difference;
borrow = u64::from(first || second);
}
}
}
}
[remainder[1], remainder[2], remainder[3], remainder[4]]
}
fn add_one(value: &mut [u64; 4]) {
for limb in value.iter_mut().rev() {
let (sum, overflow) = limb.overflowing_add(1);
*limb = sum;
if !overflow {
return;
}
}
}
fn invalid(reason: impl Into<String>) -> AlienError<ErrorData> {
AlienError::new(ErrorData::KeyInvalid {
reason: reason.into(),
})
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_code_reads_back_as_typed_and_derives_the_same_key() {
let code = RecoveryCode::generate().unwrap();
let shown = code.display();
assert_eq!(shown.len(), 39, "{shown}");
let typed = shown.to_lowercase().replace('-', " ");
let read = RecoveryCode::parse(&typed).unwrap();
assert_eq!(read, code);
assert_eq!(
read.key("prj_a").unwrap().public_key(),
code.key("prj_a").unwrap().public_key()
);
assert_ne!(
code.key("prj_a").unwrap().public_key(),
code.key("prj_b").unwrap().public_key()
);
}
#[test]
fn the_last_four_characters_are_checked_as_typed() {
let code = RecoveryCode([7u8; SECRET_BYTES]);
let other = RecoveryCode([9u8; SECRET_BYTES]);
let shown = code.display();
let tail = &shown[shown.len() - 4..];
let other_shown = other.display();
assert_ne!(tail, &other_shown[other_shown.len() - 4..]);
assert_ne!(tail, &shown[..4]);
assert!(code.ends_with(tail));
assert!(code.ends_with(&tail.to_lowercase()));
assert!(code.ends_with(&format!(" {tail}\n")));
assert!(!code.ends_with(""));
assert!(!code.ends_with(&shown[shown.len() - 3..]));
assert!(!code.ends_with(&shown[shown.len() - 6..]));
assert!(!code.ends_with(&shown[..4]));
assert!(!code.ends_with(&other_shown[other_shown.len() - 4..]));
}
#[test]
fn a_mistyped_code_is_refused() {
let shown = RecoveryCode::generate().unwrap().display();
let mut characters: Vec<char> = shown.chars().collect();
characters[0] = if characters[0] == 'A' { 'B' } else { 'A' };
let typo: String = characters.into_iter().collect();
RecoveryCode::parse(&typo).expect_err("typo");
RecoveryCode::parse(&shown[..30]).expect_err("short");
}
#[test]
fn hkdf_matches_rfc_5869_case_3() {
let ikm = [0x0bu8; 22];
let okm = hkdf_sha256(&ikm, b"").unwrap();
assert_eq!(
hex::encode(&okm[..42]),
"8da4e775a563c18f715f802a063c5a31b8a11f5c5ee1879ec3454e5f3c738d2d9d201395faa4b61a96c8"
);
}
#[test]
fn reduction_keeps_small_values_and_wraps_at_the_order() {
let mut small = [0u8; 48];
small[47] = 7;
assert_eq!(reduce_mod_order_minus_one(&small), [0, 0, 0, 7]);
let mut order_minus_one = [0u8; 48];
for (index, limb) in ORDER_MINUS_ONE.iter().enumerate() {
order_minus_one[16 + index * 8..24 + index * 8].copy_from_slice(&limb.to_be_bytes());
}
assert_eq!(reduce_mod_order_minus_one(&order_minus_one), [0, 0, 0, 0]);
order_minus_one[47] += 1;
assert_eq!(reduce_mod_order_minus_one(&order_minus_one), [0, 0, 0, 1]);
}
}