1use crate::{SIGNATURE_LENGTH, SignError, SigningIdentity, VerifyingIdentity};
18
19const CHALLENGE_CONTEXT: &[u8] = b"HIDE/0.5 challenge";
23
24pub const NONCE_LENGTH: usize = 32;
26
27pub const MAX_CHALLENGE_LIFETIME: u64 = 3600;
31
32#[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 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 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 pub fn answer(&self, identity: &SigningIdentity) -> [u8; SIGNATURE_LENGTH] {
89 identity.sign(CHALLENGE_CONTEXT, &self.to_signed_bytes())
90 }
91}
92
93#[derive(Clone, Copy, Debug, PartialEq, Eq)]
96pub enum ChallengeError {
97 NotSigned,
99 Expired,
101 Replayed,
103 WrongAudience,
106}
107
108#[derive(Debug, Default)]
112pub struct SpentNonces {
113 audience: String,
114 seen: Vec<([u8; NONCE_LENGTH], u64)>,
115}
116
117impl SpentNonces {
118 pub fn new(audience: impl Into<String>) -> Self {
124 Self {
125 audience: audience.into(),
126 seen: Vec::new(),
127 }
128 }
129
130 pub fn audience(&self) -> &str {
132 &self.audience
133 }
134
135 pub fn accept(
138 &mut self,
139 challenge: &Challenge,
140 signature: &[u8],
141 prover: &VerifyingIdentity,
142 now: u64,
143 ) -> Result<(), ChallengeError> {
144 if self.audience.is_empty() || challenge.audience() != self.audience {
149 return Err(ChallengeError::WrongAudience);
150 }
151 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
185impl 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 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 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 #[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 #[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 assert!(spent.is_empty());
278 }
279
280 #[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 #[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 #[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 #[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 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 #[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 #[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 #[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 #[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 #[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}