use alloc::vec::Vec;
use curve25519_dalek::edwards::{CompressedEdwardsY, EdwardsPoint};
use curve25519_dalek::scalar::Scalar;
use curve25519_dalek::traits::Identity;
use rsa::rand_core::CryptoRngCore;
use rsa::sha2::{Digest, Sha512};
use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};
use zeroize::Zeroizing;
const M_BYTES: [u8; 32] = [
0x5a, 0xda, 0x7e, 0x4b, 0xf6, 0xdd, 0xd9, 0xad, 0xb6, 0x62, 0x6d, 0x32, 0x13, 0x1c, 0x6b, 0x5c,
0x51, 0xa1, 0xe3, 0x47, 0xa3, 0x47, 0x8f, 0x53, 0xcf, 0xcf, 0x44, 0x1b, 0x88, 0xee, 0xd1, 0x2e,
];
const N_BYTES: [u8; 32] = [
0x10, 0xe3, 0xdf, 0x0a, 0xe3, 0x7d, 0x8e, 0x7a, 0x99, 0xb5, 0xfe, 0x74, 0xb4, 0x46, 0x72, 0x10,
0x3d, 0xbd, 0xdc, 0xbd, 0x06, 0xaf, 0x68, 0x0d, 0x71, 0x32, 0x9a, 0x11, 0x69, 0x3b, 0xc7, 0x78,
];
const ORDER: [u8; 32] = [
0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10,
];
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum Role {
Alice,
Bob,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum Spake2Error {
MessageLength(usize),
NotAPoint,
}
impl core::fmt::Display for Spake2Error {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match self {
Self::MessageLength(n) => write!(f, "spake2 message is {n} bytes, not 32"),
Self::NotAPoint => f.write_str("spake2 message does not decode to a curve point"),
}
}
}
impl core::error::Error for Spake2Error {}
fn add_assign(a: &mut [u8; 32], b: &[u8; 32]) {
let mut carry = 0u16;
for i in 0..32 {
let sum = u16::from(a[i]) + u16::from(b[i]) + carry;
a[i] = sum as u8;
carry = sum >> 8;
}
}
fn double_assign(a: &mut [u8; 32]) {
let copy = *a;
add_assign(a, ©);
}
fn left_shift_3(n: &mut [u8; 32]) {
let mut carry = 0u8;
for byte in n.iter_mut() {
let next = *byte >> 5;
*byte = (*byte << 3) | carry;
carry = next;
}
}
fn mul_raw(point: &EdwardsPoint, scalar: &[u8; 32]) -> EdwardsPoint {
let mut acc = EdwardsPoint::identity();
for byte in scalar.iter().rev() {
for bit in (0..8).rev() {
acc = acc + acc;
let sum = acc + point;
let take = Choice::from((byte >> bit) & 1);
acc = EdwardsPoint::conditional_select(&acc, &sum, take);
}
}
acc
}
fn reduce_wide(wide: &[u8; 64]) -> [u8; 32] {
Scalar::from_bytes_mod_order_wide(wide).to_bytes()
}
fn absorb(hash: &mut Sha512, data: &[u8]) {
hash.update((data.len() as u64).to_le_bytes());
hash.update(data);
}
pub struct Spake2 {
role: Role,
my_name: Vec<u8>,
their_name: Vec<u8>,
private_key: Zeroizing<[u8; 32]>,
password_hash: Zeroizing<[u8; 64]>,
password_scalar: Zeroizing<[u8; 32]>,
my_msg: [u8; 32],
}
impl Spake2 {
pub fn new<R: CryptoRngCore>(
role: Role,
my_name: &[u8],
their_name: &[u8],
password: &[u8],
rng: &mut R,
) -> Self {
let mut wide = Zeroizing::new([0u8; 64]);
rng.fill_bytes(wide.as_mut());
let mut private_key = Zeroizing::new(reduce_wide(&wide));
left_shift_3(&mut private_key);
let password_hash = Zeroizing::new(Sha512::digest(password).into());
let password_scalar = Zeroizing::new(Self::password_scalar(&password_hash));
let mask = match role {
Role::Alice => Self::point(&M_BYTES),
Role::Bob => Self::point(&N_BYTES),
};
let base = EdwardsPoint::mul_base(&Scalar::from_bytes_mod_order(*private_key));
let my_msg = (base + mul_raw(&mask, &password_scalar))
.compress()
.to_bytes();
Self {
role,
my_name: my_name.into(),
their_name: their_name.into(),
private_key,
password_hash,
password_scalar,
my_msg,
}
}
pub fn message(&self) -> &[u8; 32] {
&self.my_msg
}
pub fn finish(self, their_msg: &[u8]) -> Result<Zeroizing<[u8; 64]>, Spake2Error> {
let their_msg: [u8; 32] = their_msg
.try_into()
.map_err(|_| Spake2Error::MessageLength(their_msg.len()))?;
let masked = CompressedEdwardsY(their_msg)
.decompress()
.ok_or(Spake2Error::NotAPoint)?;
let peer_mask = match self.role {
Role::Alice => Self::point(&N_BYTES),
Role::Bob => Self::point(&M_BYTES),
};
let unmasked = masked - mul_raw(&peer_mask, &self.password_scalar);
let shared = Zeroizing::new(mul_raw(&unmasked, &self.private_key).compress().to_bytes());
let (alice_name, bob_name, alice_msg, bob_msg) = match self.role {
Role::Alice => (&self.my_name, &self.their_name, &self.my_msg, &their_msg),
Role::Bob => (&self.their_name, &self.my_name, &their_msg, &self.my_msg),
};
let mut hash = Sha512::new();
absorb(&mut hash, alice_name);
absorb(&mut hash, bob_name);
absorb(&mut hash, alice_msg);
absorb(&mut hash, bob_msg);
absorb(&mut hash, shared.as_ref());
absorb(&mut hash, self.password_hash.as_ref());
Ok(Zeroizing::new(hash.finalize().into()))
}
fn password_scalar(password_hash: &[u8; 64]) -> [u8; 32] {
let mut scalar = reduce_wide(password_hash);
let mut order = ORDER;
for bit in 0..3u32 {
let mask = 1u8 << bit;
let set = (scalar[0] & mask).ct_eq(&mask);
let mut addend = [0u8; 32];
for (dst, src) in addend.iter_mut().zip(order.iter()) {
*dst = u8::conditional_select(&0, src, set);
}
add_assign(&mut scalar, &addend);
double_assign(&mut order);
}
debug_assert_eq!(scalar[0] & 7, 0);
scalar
}
fn point(bytes: &[u8; 32]) -> EdwardsPoint {
CompressedEdwardsY(*bytes)
.decompress()
.expect("M and N are curve points, checked by a test")
}
}
#[cfg(test)]
mod tests {
use super::*;
use alloc::vec;
use rsa::rand_core::{CryptoRng, RngCore};
use rsa::sha2::Sha256;
const CLIENT: &[u8] = b"adb pair client\0";
const SERVER: &[u8] = b"adb pair server\0";
struct FixedRng(vec::Vec<u8>);
impl RngCore for FixedRng {
fn next_u32(&mut self) -> u32 {
unimplemented!("only fill_bytes is used")
}
fn next_u64(&mut self) -> u64 {
unimplemented!("only fill_bytes is used")
}
fn fill_bytes(&mut self, dest: &mut [u8]) {
dest.copy_from_slice(&self.0[..dest.len()]);
}
fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), rsa::rand_core::Error> {
self.fill_bytes(dest);
Ok(())
}
}
impl CryptoRng for FixedRng {}
fn seed(from: u8) -> FixedRng {
FixedRng((0..64u8).map(|i| from.wrapping_add(i)).collect())
}
fn hex(bytes: &[u8]) -> alloc::string::String {
bytes.iter().map(|b| alloc::format!("{b:02x}")).collect()
}
#[test]
fn the_mask_points_are_the_hashes_of_their_seeds() {
let m: [u8; 32] = Sha256::digest(b"edwards25519 point generation seed (M)").into();
let n: [u8; 32] = Sha256::digest(b"edwards25519 point generation seed (N)").into();
assert_eq!(m, M_BYTES);
assert_eq!(n, N_BYTES);
}
#[test]
fn the_mask_points_sit_outside_the_prime_order_subgroup() {
for bytes in [M_BYTES, N_BYTES] {
let point = Spake2::point(&bytes);
assert_ne!(
mul_raw(&point, &ORDER),
EdwardsPoint::identity(),
"a point of prime order would make the cofactor fix pointless"
);
}
}
#[test]
fn the_cofactor_fix_clears_three_bits_without_reducing() {
let hash: [u8; 64] = Sha512::digest(b"592781").into();
let scalar = Spake2::password_scalar(&hash);
assert_eq!(scalar[0] & 7, 0, "the low three bits are cleared");
assert_ne!(
scalar,
reduce_wide(&hash),
"and the value is no longer the reduced hash"
);
}
#[test]
fn multiplying_by_eight_matches_the_shift_it_is_named_after() {
let mut n = [0u8; 32];
n[0] = 0xFF;
n[1] = 0x01;
left_shift_3(&mut n);
assert_eq!(n[0], 0xF8);
assert_eq!(n[1], 0x0F);
assert!(n[2..].iter().all(|&b| b == 0));
}
#[test]
fn the_exchange_matches_an_independent_implementation() {
let alice = Spake2::new(Role::Alice, CLIENT, SERVER, b"592781", &mut seed(0));
let bob = Spake2::new(Role::Bob, SERVER, CLIENT, b"592781", &mut seed(64));
assert_eq!(
hex(alice.message()),
"d75922a7455e51fee339250f9b4dcceb4426ef7bb77f24b310ee646e7d9dbf8b"
);
assert_eq!(
hex(bob.message()),
"c1e770dd362fa9def9dc0d18ac3155345f4f5905362ed252ad5b9828d23484ef"
);
assert_eq!(
hex(alice.password_scalar.as_ref()),
"509a79489dd16b364e842cfce8062a604e3e67ebf2f4aaf828b4f299d7a6605c"
);
assert_eq!(
hex(alice.private_key.as_ref()),
"d0e31113846fb901851ab16da0423167ce0aa31e960899d4d306afa52387962b"
);
let key = alice.finish(bob.message()).unwrap();
assert_eq!(
hex(key.as_ref()),
"517fa9aa29d0d1a5b39490907434cb9d8024c2335d8a30970e04332f8d972da7\
e9b62a285021dd5e52bbb8d32fa42ff2887f43416b32db4a0cf9eee5db3a665d"
);
}
#[test]
fn both_sides_reach_the_same_key_when_the_codes_match() {
let alice = Spake2::new(Role::Alice, CLIENT, SERVER, b"314159", &mut seed(7));
let bob = Spake2::new(Role::Bob, SERVER, CLIENT, b"314159", &mut seed(200));
let (to_bob, to_alice) = (*alice.message(), *bob.message());
let from_alice = alice.finish(&to_alice).unwrap();
let from_bob = bob.finish(&to_bob).unwrap();
assert_eq!(from_alice, from_bob);
}
#[test]
fn a_wrong_code_parts_the_two_sides_without_saying_so() {
let alice = Spake2::new(Role::Alice, CLIENT, SERVER, b"314159", &mut seed(7));
let bob = Spake2::new(Role::Bob, SERVER, CLIENT, b"271828", &mut seed(200));
let (to_bob, to_alice) = (*alice.message(), *bob.message());
let from_alice = alice.finish(&to_alice).unwrap();
let from_bob = bob.finish(&to_bob).unwrap();
assert_ne!(from_alice, from_bob);
}
#[test]
fn a_message_of_the_wrong_shape_is_refused() {
let alice = || Spake2::new(Role::Alice, CLIENT, SERVER, b"592781", &mut seed(0));
assert_eq!(
alice().finish(&[0u8; 31]),
Err(Spake2Error::MessageLength(31))
);
let mut not_a_point = [0u8; 32];
not_a_point[0] = 2;
assert_eq!(alice().finish(¬_a_point), Err(Spake2Error::NotAPoint));
}
}