Skip to main content

hide_sign/
challenge.rs

1//! Proving possession of an identity to a live verifier.
2//!
3//! A detached signature proves possession *at some point*; it says nothing
4//! about when, or to whom. Replayed to a second service it is just as valid,
5//! which is why a captured signature must not be usable as a login.
6//!
7//! A challenge fixes all three. The verifier chooses a random nonce, so the
8//! prover cannot have answered in advance; names an audience, so an answer
9//! given to one service is meaningless at another; and stamps a time, so an
10//! old answer expires. All three are signed, and a verifier that does not
11//! check them is not doing anything a plain signature could not.
12//!
13//! The nonce alone is what makes replay detectable. Audience and expiry narrow
14//! the window; the record of spent nonces is what closes it, and that record
15//! must be kept by the verifier because a prover has no reason to co-operate.
16
17use crate::{SIGNATURE_LENGTH, SignError, SigningIdentity, VerifyingIdentity};
18
19/// Separate from every other use of an identity. A container signature or a
20/// detached file signature must never verify as a login, whatever an attacker
21/// can arrange for the other side to sign.
22const CHALLENGE_CONTEXT: &[u8] = b"HIDE/0.5 challenge";
23
24/// Long enough that guessing or colliding is not a strategy.
25pub const NONCE_LENGTH: usize = 32;
26
27/// A challenge exists to prove liveness within one request. A lifetime longer
28/// than this keeps a nonce spendable for no reason, so it is refused as a
29/// mistake rather than accepted.
30pub const MAX_CHALLENGE_LIFETIME: u64 = 3600;
31
32/// A verifier's demand: prove you hold the key, to me, now.
33#[derive(Clone, Debug, PartialEq, Eq)]
34pub struct Challenge {
35    nonce: [u8; NONCE_LENGTH],
36    audience: String,
37    issued_at: u64,
38    valid_for: u64,
39}
40
41impl Challenge {
42    /// `audience` names the verifier, and must be a name the prover can check
43    /// rather than one it is told at the time of proving. An empty audience
44    /// names nobody, so it is refused.
45    pub fn new(audience: impl Into<String>, now: u64, valid_for: u64) -> Result<Self, SignError> {
46        let audience = audience.into();
47        if audience.is_empty() || valid_for == 0 || valid_for > MAX_CHALLENGE_LIFETIME {
48            return Err(SignError::MalformedChallenge);
49        }
50        let mut nonce = [0_u8; NONCE_LENGTH];
51        getrandom::fill(&mut nonce).map_err(|_| SignError::Random)?;
52        Ok(Self {
53            nonce,
54            audience,
55            issued_at: now,
56            valid_for,
57        })
58    }
59
60    pub fn nonce(&self) -> &[u8; NONCE_LENGTH] {
61        &self.nonce
62    }
63
64    pub fn audience(&self) -> &str {
65        &self.audience
66    }
67
68    pub fn expires_at(&self) -> u64 {
69        self.issued_at.saturating_add(self.valid_for)
70    }
71
72    /// What both sides sign. Every field is length-prefixed so that no two
73    /// different challenges can produce the same bytes by shifting a boundary
74    /// between the audience and what follows it.
75    fn to_signed_bytes(&self) -> Vec<u8> {
76        let audience = self.audience.as_bytes();
77        let mut bytes = Vec::with_capacity(NONCE_LENGTH + audience.len() + 24);
78        bytes.extend_from_slice(&self.nonce);
79        bytes.extend_from_slice(&(audience.len() as u64).to_be_bytes());
80        bytes.extend_from_slice(audience);
81        bytes.extend_from_slice(&self.issued_at.to_be_bytes());
82        bytes.extend_from_slice(&self.valid_for.to_be_bytes());
83        bytes
84    }
85
86    /// Answers the challenge. The prover signs the challenge as the verifier
87    /// stated it, so a verifier that alters any field will not verify its own.
88    pub fn answer(&self, identity: &SigningIdentity) -> [u8; SIGNATURE_LENGTH] {
89        identity.sign(CHALLENGE_CONTEXT, &self.to_signed_bytes())
90    }
91}
92
93/// Why an answer was not accepted. A caller should log this but tell the
94/// prover only that authentication failed.
95#[derive(Clone, Copy, Debug, PartialEq, Eq)]
96pub enum ChallengeError {
97    /// The signature does not verify, or was made over a different challenge.
98    NotSigned,
99    /// The challenge was answered after it expired.
100    Expired,
101    /// This nonce was already spent. Either a replay, or a duplicate delivery.
102    Replayed,
103    /// The challenge names a different audience than this verifier. An answer
104    /// given to another service must be worthless here.
105    WrongAudience,
106}
107
108/// The nonces already spent. Kept by the verifier, because a prover has no
109/// incentive to remember. Entries are dropped once no live challenge could
110/// still carry them, so this does not grow without bound.
111#[derive(Debug, Default)]
112pub struct SpentNonces {
113    audience: String,
114    seen: Vec<([u8; NONCE_LENGTH], u64)>,
115}
116
117impl SpentNonces {
118    /// `audience` is the name this verifier answers to, exactly as it was used
119    /// to issue challenges. Binding it here rather than at each `accept` is
120    /// what makes the check impossible to forget: a verifier that takes the
121    /// challenge bytes back from the client still refuses an answer minted for
122    /// another service, because the record itself knows who it is.
123    pub fn new(audience: impl Into<String>) -> Self {
124        Self {
125            audience: audience.into(),
126            seen: Vec::new(),
127        }
128    }
129
130    /// The audience this record accepts answers for.
131    pub fn audience(&self) -> &str {
132        &self.audience
133    }
134
135    /// Accepts an answer once. A second call with the same nonce is a replay,
136    /// even if the signature is perfectly valid — which is the point.
137    pub fn accept(
138        &mut self,
139        challenge: &Challenge,
140        signature: &[u8],
141        prover: &VerifyingIdentity,
142        now: u64,
143    ) -> Result<(), ChallengeError> {
144        // Audience first: an answer minted for another service must never
145        // reach the signature check, and there is no reason to spend a nonce
146        // on it either. An empty expectation accepts nothing, so a caller that
147        // forgot to name its audience fails closed.
148        if self.audience.is_empty() || challenge.audience() != self.audience {
149            return Err(ChallengeError::WrongAudience);
150        }
151        // Check freshness before spending the nonce, so an expired answer
152        // cannot consume a nonce that a live challenge still needs.
153        if now > challenge.expires_at() {
154            return Err(ChallengeError::Expired);
155        }
156        prover
157            .verify(CHALLENGE_CONTEXT, &challenge.to_signed_bytes(), signature)
158            .map_err(|_| ChallengeError::NotSigned)?;
159
160        self.forget_expired(now);
161        if self
162            .seen
163            .iter()
164            .any(|(nonce, _)| nonce == challenge.nonce())
165        {
166            return Err(ChallengeError::Replayed);
167        }
168        self.seen.push((*challenge.nonce(), challenge.expires_at()));
169        Ok(())
170    }
171
172    fn forget_expired(&mut self, now: u64) {
173        self.seen.retain(|(_, expires_at)| *expires_at >= now);
174    }
175
176    pub fn len(&self) -> usize {
177        self.seen.len()
178    }
179
180    pub fn is_empty(&self) -> bool {
181        self.seen.is_empty()
182    }
183}
184
185/// A challenge is not secret, so it may be handed to the prover as bytes.
186/// Kept explicit rather than derived, so the wire form cannot drift silently.
187impl Challenge {
188    pub fn encode(&self) -> Vec<u8> {
189        self.to_signed_bytes()
190    }
191
192    pub fn decode(bytes: &[u8]) -> Result<Self, SignError> {
193        let (nonce, rest) = bytes
194            .split_at_checked(NONCE_LENGTH)
195            .ok_or(SignError::MalformedChallenge)?;
196        let (length, rest) = rest
197            .split_at_checked(8)
198            .ok_or(SignError::MalformedChallenge)?;
199        // `as usize` would wrap on a 32-bit target and accept a length that
200        // does not fit, selecting the wrong slice.
201        let length = usize::try_from(u64::from_be_bytes(
202            length.try_into().expect("split at eight"),
203        ))
204        .map_err(|_| SignError::MalformedChallenge)?;
205        let (audience, rest) = rest
206            .split_at_checked(length)
207            .ok_or(SignError::MalformedChallenge)?;
208        let (issued_at, rest) = rest
209            .split_at_checked(8)
210            .ok_or(SignError::MalformedChallenge)?;
211        let (valid_for, rest) = rest
212            .split_at_checked(8)
213            .ok_or(SignError::MalformedChallenge)?;
214        if !rest.is_empty() {
215            return Err(SignError::MalformedChallenge);
216        }
217        let audience =
218            String::from_utf8(audience.to_vec()).map_err(|_| SignError::MalformedChallenge)?;
219        let valid_for = u64::from_be_bytes(valid_for.try_into().expect("split at eight"));
220        // The same bounds a freshly issued challenge must satisfy, so a decoded
221        // challenge is never one that `new` would have refused.
222        if audience.is_empty() || valid_for == 0 || valid_for > MAX_CHALLENGE_LIFETIME {
223            return Err(SignError::MalformedChallenge);
224        }
225        Ok(Self {
226            nonce: nonce.try_into().expect("split at the nonce length"),
227            audience,
228            issued_at: u64::from_be_bytes(issued_at.try_into().expect("split at eight")),
229            valid_for,
230        })
231    }
232}
233
234#[cfg(test)]
235mod tests {
236    use super::*;
237    use crate::SEED_LENGTH;
238
239    const NOW: u64 = 1_000_000;
240    const WINDOW: u64 = 60;
241
242    fn identity() -> SigningIdentity {
243        SigningIdentity::from_bytes(&[0x42; SEED_LENGTH]).expect("a 32-byte seed is valid")
244    }
245
246    fn challenge() -> Challenge {
247        Challenge::new("ssh://host.example", NOW, WINDOW).expect("randomness is available")
248    }
249
250    fn spent() -> SpentNonces {
251        SpentNonces::new("ssh://host.example")
252    }
253
254    /// A challenge that names nobody, or that lives longer than a request could
255    /// plausibly last, is a mistake and must not be issued.
256    #[test]
257    fn an_empty_audience_or_absurd_lifetime_is_refused() {
258        assert!(Challenge::new("", NOW, WINDOW).is_err());
259        assert!(Challenge::new("ssh://host.example", NOW, 0).is_err());
260        assert!(Challenge::new("ssh://host.example", NOW, MAX_CHALLENGE_LIFETIME + 1).is_err());
261        assert!(Challenge::new("ssh://host.example", NOW, MAX_CHALLENGE_LIFETIME).is_ok());
262    }
263
264    /// A verifier that takes the challenge back from the client still refuses
265    /// an answer minted for another service: the record knows its own audience.
266    #[test]
267    fn the_record_refuses_an_answer_for_another_audience() {
268        let identity = identity();
269        let elsewhere = Challenge::new("ssh://attacker.example", NOW, WINDOW).unwrap();
270        let answer = elsewhere.answer(&identity);
271        let mut spent = spent();
272        assert_eq!(
273            spent.accept(&elsewhere, &answer, &identity.verifying_key(), NOW),
274            Err(ChallengeError::WrongAudience)
275        );
276        // A wrong-audience answer must not spend the nonce either.
277        assert!(spent.is_empty());
278    }
279
280    /// A record with no audience accepts nothing rather than everything.
281    #[test]
282    fn a_record_without_an_audience_accepts_nothing() {
283        let identity = identity();
284        let challenge = challenge();
285        let answer = challenge.answer(&identity);
286        let mut spent = SpentNonces::new("");
287        assert_eq!(
288            spent.accept(&challenge, &answer, &identity.verifying_key(), NOW),
289            Err(ChallengeError::WrongAudience)
290        );
291    }
292
293    /// A declared audience length above `usize::MAX` must be refused, not
294    /// truncated by an `as usize` cast that would wrap on a 32-bit target.
295    #[test]
296    fn an_oversized_audience_length_is_refused() {
297        let mut bytes = vec![0u8; NONCE_LENGTH];
298        bytes.extend_from_slice(&u64::MAX.to_be_bytes());
299        bytes.extend_from_slice(&[0u8; 16]);
300        assert!(matches!(
301            Challenge::decode(&bytes),
302            Err(SignError::MalformedChallenge)
303        ));
304    }
305
306    #[test]
307    fn an_honest_answer_is_accepted_once() {
308        let identity = identity();
309        let challenge = challenge();
310        let answer = challenge.answer(&identity);
311        let mut spent = spent();
312        assert_eq!(
313            spent.accept(&challenge, &answer, &identity.verifying_key(), NOW),
314            Ok(())
315        );
316    }
317
318    /// The whole reason a challenge exists. A captured answer is still a valid
319    /// signature, so only the record of spent nonces can refuse it.
320    #[test]
321    fn the_same_answer_replayed_is_refused() {
322        let identity = identity();
323        let challenge = challenge();
324        let answer = challenge.answer(&identity);
325        let mut spent = spent();
326        spent
327            .accept(&challenge, &answer, &identity.verifying_key(), NOW)
328            .expect("the first answer is honest");
329        assert_eq!(
330            spent.accept(&challenge, &answer, &identity.verifying_key(), NOW),
331            Err(ChallengeError::Replayed)
332        );
333    }
334
335    #[test]
336    fn an_answer_after_the_window_is_refused() {
337        let identity = identity();
338        let challenge = challenge();
339        let answer = challenge.answer(&identity);
340        let mut spent = spent();
341        assert_eq!(
342            spent.accept(
343                &challenge,
344                &answer,
345                &identity.verifying_key(),
346                NOW + WINDOW + 1
347            ),
348            Err(ChallengeError::Expired)
349        );
350    }
351
352    /// An answer given to one service must be worthless at another, or a
353    /// malicious verifier could relay it to log in somewhere else. The
354    /// signature covers the audience, so even a verifier that names itself
355    /// after the other service cannot accept the relayed answer.
356    #[test]
357    fn an_answer_for_another_audience_does_not_verify() {
358        let identity = identity();
359        let asked = challenge();
360        let answer = asked.answer(&identity);
361
362        let mut elsewhere = asked.clone();
363        elsewhere.audience = "ssh://attacker.example".to_string();
364
365        // Match the mutated audience, so the only thing left to fail is the
366        // signature: this is what proves the audience is signed, not just read.
367        let mut spent = SpentNonces::new("ssh://attacker.example");
368        assert_eq!(
369            spent.accept(&elsewhere, &answer, &identity.verifying_key(), NOW),
370            Err(ChallengeError::NotSigned)
371        );
372    }
373
374    #[test]
375    fn an_answer_for_another_nonce_does_not_verify() {
376        let identity = identity();
377        let asked = challenge();
378        let answer = asked.answer(&identity);
379
380        let mut other = asked.clone();
381        other.nonce = [0x11; NONCE_LENGTH];
382
383        let mut spent = spent();
384        assert_eq!(
385            spent.accept(&other, &answer, &identity.verifying_key(), NOW),
386            Err(ChallengeError::NotSigned)
387        );
388    }
389
390    #[test]
391    fn another_identity_cannot_answer_for_this_one() {
392        let challenge = challenge();
393        let impostor = SigningIdentity::from_bytes(&[0x07; SEED_LENGTH]).expect("valid seed");
394        let answer = challenge.answer(&impostor);
395        let mut spent = spent();
396        assert_eq!(
397            spent.accept(&challenge, &answer, &identity().verifying_key(), NOW),
398            Err(ChallengeError::NotSigned)
399        );
400    }
401
402    /// P5.2: a signature made for any other purpose must not authenticate a
403    /// login, however the attacker arranges for it to be produced.
404    #[test]
405    fn a_signature_from_another_context_is_not_a_valid_answer() {
406        let identity = identity();
407        let challenge = challenge();
408        let forged = identity.sign(b"HIDE/0.5 detached", &challenge.to_signed_bytes());
409        let mut spent = spent();
410        assert_eq!(
411            spent.accept(&challenge, &forged, &identity.verifying_key(), NOW),
412            Err(ChallengeError::NotSigned)
413        );
414    }
415
416    /// And the converse: answering a challenge must not hand out a signature
417    /// that verifies over a file.
418    #[test]
419    fn an_answer_is_not_a_valid_detached_signature() {
420        let identity = identity();
421        let challenge = challenge();
422        let answer = challenge.answer(&identity);
423        assert!(
424            identity
425                .verifying_key()
426                .verify(b"HIDE/0.5 detached", &challenge.to_signed_bytes(), &answer)
427                .is_err()
428        );
429    }
430
431    #[test]
432    fn two_challenges_never_share_a_nonce() {
433        assert_ne!(challenge().nonce(), challenge().nonce());
434    }
435
436    /// An expired nonce is forgotten, or a long-lived verifier would grow
437    /// without bound. Forgetting it is safe: expiry already refuses it.
438    #[test]
439    fn spent_nonces_are_forgotten_once_nothing_can_use_them() {
440        let identity = identity();
441        let first = challenge();
442        let answer = first.answer(&identity);
443        let mut spent = spent();
444        spent
445            .accept(&first, &answer, &identity.verifying_key(), NOW)
446            .expect("honest");
447        assert_eq!(spent.len(), 1);
448
449        let later = Challenge::new("ssh://host.example", NOW + WINDOW + 1, WINDOW).expect("random");
450        let later_answer = later.answer(&identity);
451        spent
452            .accept(
453                &later,
454                &later_answer,
455                &identity.verifying_key(),
456                NOW + WINDOW + 1,
457            )
458            .expect("honest");
459        assert_eq!(spent.len(), 1, "the first nonce should have been dropped");
460    }
461
462    /// An expired answer must not consume the nonce, or a hostile party could
463    /// spend nonces belonging to challenges that are still live.
464    #[test]
465    fn an_expired_answer_does_not_spend_the_nonce() {
466        let identity = identity();
467        let challenge = challenge();
468        let answer = challenge.answer(&identity);
469        let mut spent = spent();
470        assert_eq!(
471            spent.accept(
472                &challenge,
473                &answer,
474                &identity.verifying_key(),
475                NOW + WINDOW + 1
476            ),
477            Err(ChallengeError::Expired)
478        );
479        assert!(spent.is_empty());
480        assert_eq!(
481            spent.accept(&challenge, &answer, &identity.verifying_key(), NOW),
482            Ok(())
483        );
484    }
485
486    #[test]
487    fn a_challenge_survives_a_round_trip() {
488        let original = challenge();
489        let decoded = Challenge::decode(&original.encode()).expect("our own encoding");
490        assert_eq!(decoded, original);
491    }
492
493    #[test]
494    fn every_truncation_of_a_challenge_is_refused() {
495        let encoded = challenge().encode();
496        for length in 0..encoded.len() {
497            assert!(
498                Challenge::decode(&encoded[..length]).is_err(),
499                "accepted a challenge truncated to {length} bytes"
500            );
501        }
502    }
503
504    #[test]
505    fn trailing_bytes_after_a_challenge_are_refused() {
506        let mut encoded = challenge().encode();
507        encoded.push(0);
508        assert!(Challenge::decode(&encoded).is_err());
509    }
510
511    /// A length prefix is a promise, not a fact.
512    #[test]
513    fn a_lying_audience_length_is_refused_without_panicking() {
514        let mut encoded = challenge().encode();
515        encoded[NONCE_LENGTH..NONCE_LENGTH + 8].copy_from_slice(&u64::MAX.to_be_bytes());
516        assert!(Challenge::decode(&encoded).is_err());
517    }
518}