From a1e398621eec9472ad67f1eafeba9ff23b012c2f Mon Sep 17 00:00:00 2001 From: slopulus Date: Tue, 17 Nov 2026 19:57:56 +0100 Subject: keys: a party's key may be ecdsa-sha2-nistp256, its signature low-S only A party's keys may be held where no file has them, in a Secure Enclave or a phone, and those are ECDSA keys on NIST P-256. Everywhere a party's key counts (a version's keys, a key set, the key an event is signed with) such a key is taken beside an Ed25519 one, spelled as `ssh-keygen` writes it, without a comment: `ecdsa-sha2-nistp256`, a space, and the base64 of its SSH encoding, its point uncompressed and on the curve. Its signature is SSHSIG as an Ed25519 one is, hashed with `sha512`, its inner signature over SHA-256 as SSH signs with such a key. ECDSA signatures are malleable: of `s` and the curve's order less `s`, both check. So the federation takes one spelling alone: `s` low, at most half the order, `r` and `s` each SSH's shortest mpint, and the blob reading back to itself as an Ed25519 one does. What anyone makes of a party's signature is then none, as before. The vectors are a key `ssh-keygen -t ecdsa -b 256` made, a first version naming it, and a write and a key set `ssh-keygen -Y sign` signed with it, each taken; the signature's high-S twin, which checks as ECDSA, and its `r` spelled longer are none. Ed25519 keys and signatures are spelled and checked as they were. --- src/federation/keys.rs | 283 +++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 253 insertions(+), 30 deletions(-) (limited to 'src/federation/keys.rs') diff --git a/src/federation/keys.rs b/src/federation/keys.rs index 7df0bd9..ee5f01e 100644 --- a/src/federation/keys.rs +++ b/src/federation/keys.rs @@ -1,28 +1,109 @@ //! Keys, node IDs and signatures, each spelled one way (`docs/federation.md`, Events): //! -//! * a key: `ssh-ed25519`, one space, and the key's base64, padded and canonical, with no -//! comment, its 32 bytes an Ed25519 public key; +//! * a key: its type, one space, and the base64 of its SSH encoding, padded and canonical, +//! with no comment: `ssh-ed25519`, its 32 bytes an Ed25519 public key, or +//! `ecdsa-sha2-nistp256`, its point on NIST P-256 uncompressed; //! * a node ID: as continuum spells it, `continuum:` and the 64 lower-case hex digits of //! the node's Ed25519 public key; //! * a signature: SSHSIG of version 1 over the event's bytes without `sig`, for the //! namespace `continuum-federation`, hashed with `sha512`, its reserved field empty, its -//! key the event's, in base64, padded and canonical, unarmored; checked strictly. +//! key the event's, in base64, padded and canonical, unarmored; checked strictly. An +//! ECDSA signature's `r` and `s` are SSH's shortest mpints, and its `s` low: at most +//! half the curve's order, as `s` and the order less `s` both check. //! //! So nobody but its signer makes another event of what a party signed. use base64::{Engine, engine::general_purpose::STANDARD as BASE64}; use ed25519_dalek::{SigningKey, VerifyingKey}; +use p256::ecdsa::signature::Verifier; +use sha2::{Digest, Sha512}; -use crate::access::sshsig::{self, PublicKey}; +use crate::access::sshsig::{self, PublicKey, Reader, string}; use crate::identity; /// What a party's signature is for. pub(crate) const NAMESPACE: &str = "continuum-federation"; +const ED25519: &str = "ssh-ed25519"; +const P256: &str = "ecdsa-sha2-nistp256"; +const CURVE: &[u8] = b"nistp256"; + +/// A party's key. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub(crate) enum Key { + Ed25519(PublicKey), + /// ECDSA on NIST P-256: its point, SEC1-encoded, uncompressed. + P256([u8; 65]), +} + +impl Key { + /// From an `authorized_keys` line: its type, its base64, and maybe a comment. + pub(crate) fn parse(line: &str) -> Result { + let mut parts = line.split_whitespace(); + let (Some(kind), Some(encoded)) = (parts.next(), parts.next()) else { + return Err(format!("not `{ED25519}|{P256} [comment]`")); + }; + match kind { + ED25519 => return PublicKey::parse(line).map(Key::Ed25519), + P256 => {} + _ => { + return Err(format!( + "a {kind} key: only {ED25519} and {P256} keys are taken" + )); + } + } + let blob = BASE64 + .decode(encoded) + .map_err(|error| format!("its base64 doesn't decode: {error}"))?; + let mut reader = Reader(&blob); + if reader.string()? != P256.as_bytes() || reader.string()? != CURVE { + return Err(format!("not an {P256} key")); + } + let point: [u8; 65] = reader + .string()? + .try_into() + .map_err(|_| "a point that isn't 65 bytes".to_owned())?; + reader.end()?; + p256::ecdsa::VerifyingKey::from_sec1_bytes(&point) + .map_err(|_| "not a point on NIST P-256".to_owned())?; + Ok(Key::P256(point)) + } + + fn kind(&self) -> &'static str { + match self { + Key::Ed25519(_) => ED25519, + Key::P256(_) => P256, + } + } + + /// Its SSH encoding. + pub(crate) fn blob(&self) -> Vec { + match self { + Key::Ed25519(key) => key.blob(), + Key::P256(point) => { + let mut blob = Vec::new(); + string(&mut blob, P256.as_bytes()); + string(&mut blob, CURVE); + string(&mut blob, point); + blob + } + } + } + + /// As an `authorized_keys` line has it, without a comment. + pub(crate) fn line(&self) -> String { + format!("{} {}", self.kind(), BASE64.encode(self.blob())) + } +} + /// The key `text` spells, where it spells one as the federation does. -pub(crate) fn key(text: &str) -> Option { - let key = PublicKey::parse(text).ok()?; - (key.line() == text && VerifyingKey::from_bytes(&key.0).is_ok()).then_some(key) +pub(crate) fn key(text: &str) -> Option { + let key = Key::parse(text).ok()?; + let valid = match &key { + Key::Ed25519(public) => VerifyingKey::from_bytes(&public.0).is_ok(), + Key::P256(_) => true, + }; + (key.line() == text && valid).then_some(key) } /// Whether `text` is a node ID spelled as continuum spells one. @@ -31,19 +112,77 @@ pub(crate) fn node_id(text: &str) -> bool { } /// Whether `sig` is `key`'s signature of `message`, spelled as the federation spells one. -pub(crate) fn verifies(key: &PublicKey, sig: &str, message: &[u8]) -> bool { +pub(crate) fn verifies(key: &Key, sig: &str, message: &[u8]) -> bool { let Ok(blob) = BASE64.decode(sig) else { return false; }; - if BASE64.encode(&blob) != sig || blob.len() < 64 { + if BASE64.encode(&blob) != sig { return false; } // The blob reads back to itself: what signing with this key writes around its - // signature, the last 64 bytes. - if blob != written(key, &blob[blob.len() - 64..]) { + // signature, all that follows what it writes around none. + let Some(signature) = blob.get(written(key, &[]).len()..) else { + return false; + }; + if blob != written(key, signature) { return false; } - sshsig::verify_blob(&blob, NAMESPACE, message).is_ok_and(|signer| signer == *key) + match key { + Key::Ed25519(public) => { + sshsig::verify_blob(&blob, NAMESPACE, message).is_ok_and(|signer| signer == *public) + } + Key::P256(point) => p256_verifies(point, signature, message), + } +} + +/// Whether `signature`, `r` and `s` as SSH's mpints, is the P-256 key `point`'s of +/// `message`, spelled one way: each mpint its shortest, `s` low. +fn p256_verifies(point: &[u8; 65], signature: &[u8], message: &[u8]) -> bool { + let Some(parsed) = ecdsa_signature(signature) else { + return false; + }; + if mpints(&parsed) != signature || parsed.normalize_s() != parsed { + return false; + } + p256::ecdsa::VerifyingKey::from_sec1_bytes(point) + .is_ok_and(|key| key.verify(&signed(message), &parsed).is_ok()) +} + +/// An ECDSA signature from `r` and `s`, SSH's mpints, where each is an integer from 1 to +/// below the curve's order, spelled any way SSH reads. +fn ecdsa_signature(bytes: &[u8]) -> Option { + /// A non-negative mpint of up to 32 bytes, leading zeros aside, as 32 bytes. + fn scalar(mpint: &[u8]) -> Option<[u8; 32]> { + if mpint.first().is_some_and(|byte| byte & 0x80 != 0) { + return None; + } + let digits = &mpint[mpint.iter().take_while(|byte| **byte == 0).count()..]; + let mut out = [0; 32]; + out.get_mut(32usize.checked_sub(digits.len())?..)? + .copy_from_slice(digits); + Some(out) + } + let mut reader = Reader(bytes); + let r = scalar(reader.string().ok()?)?; + let s = scalar(reader.string().ok()?)?; + reader.end().ok()?; + p256::ecdsa::Signature::from_scalars(r, s).ok() +} + +/// `signature`'s `r` and `s`, each SSH's shortest mpint. +fn mpints(signature: &p256::ecdsa::Signature) -> Vec { + let (r, s) = signature.split_bytes(); + let mut out = Vec::new(); + for value in [r, s] { + let digits = &value[value.iter().take_while(|byte| **byte == 0).count()..]; + let mut mpint = Vec::new(); + if digits.first().is_some_and(|byte| byte & 0x80 != 0) { + mpint.push(0); + } + mpint.extend_from_slice(digits); + string(&mut out, &mpint); + } + out } /// `message` signed with `key`, as the federation spells a signature: what @@ -54,11 +193,22 @@ pub(crate) fn sign(key: &SigningKey, message: &[u8]) -> String { BASE64.encode(blob) } +/// What a signature of `message` is made over: SSHSIG's signed data, hashed with `sha512`. +fn signed(message: &[u8]) -> Vec { + sshsig::signed_data( + NAMESPACE.as_bytes(), + b"", + b"sha512", + &Sha512::digest(message), + ) +} + /// The SSHSIG blob of a signature by `key`, of version 1, for the federation's namespace, -/// its reserved field empty, hashed with `sha512`: as `ssh-keygen` writes it. -fn written(key: &PublicKey, signature: &[u8]) -> Vec { +/// its reserved field empty, hashed with `sha512`: as `ssh-keygen` writes it around +/// `signature`, the key type's own. +fn written(key: &Key, signature: &[u8]) -> Vec { let mut inner = Vec::new(); - string(&mut inner, b"ssh-ed25519"); + string(&mut inner, key.kind().as_bytes()); string(&mut inner, signature); let mut blob = b"SSHSIG".to_vec(); blob.extend_from_slice(&1u32.to_be_bytes()); @@ -70,36 +220,55 @@ fn written(key: &PublicKey, signature: &[u8]) -> Vec { blob } -fn string(out: &mut Vec, bytes: &[u8]) { - out.extend_from_slice(&(bytes.len() as u32).to_be_bytes()); - out.extend_from_slice(bytes); -} - #[cfg(test)] mod tests { use super::*; + use crate::federation::event::Event; + use crate::federation::jcs::{self, Json}; + use crate::federation::vectors::{ECDSA_KEY, ECDSA_WRITE}; fn signer(seed: u8) -> SigningKey { SigningKey::from_bytes(&[seed; 32]) } - fn public(key: &SigningKey) -> PublicKey { - PublicKey(key.verifying_key().to_bytes()) + fn public(key: &SigningKey) -> Key { + Key::Ed25519(PublicKey(key.verifying_key().to_bytes())) } #[test] fn a_key_is_spelled_one_way() { - let line = public(&signer(1)).line(); - assert!(key(&line).is_some()); - assert!(key(&format!("{line} comment")).is_none()); - assert!(key(&line.replacen(' ', " ", 1)).is_none()); - assert!(key(&format!(" {line}")).is_none()); - let unpadded = line.trim_end_matches('='); - if unpadded != line { - assert!(key(unpadded).is_none()); + for line in [public(&signer(1)).line(), ECDSA_KEY.to_owned()] { + assert_eq!(key(&line).map(|key| key.line()), Some(line.clone())); + assert!(key(&format!("{line} comment")).is_none()); + assert!(key(&line.replacen(' ', " ", 1)).is_none()); + assert!(key(&format!(" {line}")).is_none()); + let unpadded = line.trim_end_matches('='); + if unpadded != line { + assert!(key(unpadded).is_none()); + } } } + #[test] + fn an_ecdsa_key_is_a_point_on_the_curve_uncompressed() { + let Some(Key::P256(point)) = key(ECDSA_KEY) else { + panic!("an ECDSA key"); + }; + let line = |point: &[u8]| { + let mut blob = Vec::new(); + string(&mut blob, P256.as_bytes()); + string(&mut blob, CURVE); + string(&mut blob, point); + format!("{P256} {}", BASE64.encode(blob)) + }; + assert_eq!(line(&point), ECDSA_KEY); + let compressed = [&[2 + (point[64] & 1)], &point[1..33]].concat(); + assert!(Key::parse(&line(&compressed)).is_err()); + let mut off = point; + off[64] ^= 1; + assert!(Key::parse(&line(&off)).is_err()); + } + #[test] fn a_node_id_is_spelled_one_way() { let id = identity::node_id_of(&signer(2).verifying_key().to_bytes()); @@ -144,4 +313,58 @@ mod tests { b"an event" )); } + + /// The ECDSA vector's write: its key, its `sig`, and the bytes it signs. + fn ecdsa_write() -> (Key, String, Vec) { + let event = jcs::read(ECDSA_WRITE.as_bytes()).expect("JCS"); + let sig = event.get("sig").and_then(Json::as_str).expect("a sig"); + ( + key(ECDSA_KEY).expect("a key"), + sig.to_owned(), + event.without("sig").bytes(), + ) + } + + /// The `r` and `s` of `sig`, a signature by `key` as the federation spells one. + fn rs<'a>(key: &Key, sig: &'a [u8]) -> &'a [u8] { + &sig[written(key, &[]).len()..] + } + + #[test] + fn an_ecdsa_signature_is_low_s_and_spelled_one_way() { + let (key, sig, message) = ecdsa_write(); + assert!(verifies(&key, &sig, &message)); + assert!(!verifies(&key, &sig, b"another event")); + let blob = BASE64.decode(&sig).expect("base64"); + let ours = ecdsa_signature(rs(&key, &blob)).expect("r and s"); + let refused = |rs: &[u8]| { + let other = BASE64.encode(written(&key, rs)); + assert!(!verifies(&key, &other, &message)); + assert!(Event::read(ECDSA_WRITE.replace(&sig, &other).as_bytes()).is_none()); + }; + // Its twin of the order less `s`, high, checks as ECDSA, and is none here. + let (r, s) = ours.split_scalars(); + let twin = p256::ecdsa::Signature::from_scalars(r, -s).expect("a signature"); + let Key::P256(point) = key else { + unreachable!("an ECDSA key") + }; + let verifying = p256::ecdsa::VerifyingKey::from_sec1_bytes(&point).expect("a point"); + assert!(verifying.verify(&signed(&message), &twin).is_ok()); + assert_ne!(twin, ours); + assert_eq!(twin.normalize_s(), ours); + refused(&mpints(&twin)); + // `r` with a zero byte more in front: the same number to SSH, and none here. + let mut reader = Reader(rs(&key, &blob)); + let (r, s) = (reader.string().unwrap(), reader.string().unwrap()); + let mut longer = Vec::new(); + string(&mut longer, &[&[0], r].concat()); + string(&mut longer, s); + assert_eq!(ecdsa_signature(&longer), Some(ours)); + refused(&longer); + // Nor a negative `r`. + let mut negative = Vec::new(); + string(&mut negative, &[&[0x80], r].concat()); + string(&mut negative, s); + refused(&negative); + } } -- cgit v1.3.1