mail_auth/dkim2/
recipe.rs

1/*
2 * SPDX-FileCopyrightText: 2020 Stalwart Labs LLC <hello@stalw.art>
3 *
4 * SPDX-License-Identifier: Apache-2.0 OR MIT
5 */
6
7use crate::AuthenticatedMessage;
8use crate::dkim2::Dkim2Error;
9use crate::dkim2::canonicalize::{cmp_ignore_ascii_case, is_non_signed_header};
10use similar::{Algorithm, DiffOp, capture_diff_slices};
11use std::cmp::Ordering;
12use std::collections::BTreeMap;
13
14#[derive(Debug, PartialEq, Eq, Clone, Default)]
15pub struct Recipe {
16    pub headers: Vec<HeaderRecipe>,
17    pub body: BodyRecipe,
18}
19
20#[derive(Debug, PartialEq, Eq, Clone)]
21pub struct HeaderRecipe {
22    pub name: String,
23    pub steps: Vec<Step>,
24}
25
26#[derive(Debug, PartialEq, Eq, Clone, Default)]
27pub enum BodyRecipe {
28    #[default]
29    None,
30    Steps(Vec<Step>),
31    Unreconstructable,
32}
33
34#[derive(Debug, PartialEq, Eq, Clone)]
35pub enum Step {
36    Copy { start: u32, end: u32 },
37    Data(Vec<String>),
38}
39
40struct LowerHeader<'x>(&'x [u8]);
41
42impl<'x> LowerHeader<'x> {
43    fn new(header: &'x [u8]) -> Self {
44        LowerHeader(header.trim_ascii())
45    }
46}
47
48impl PartialEq for LowerHeader<'_> {
49    fn eq(&self, other: &Self) -> bool {
50        self.0.eq_ignore_ascii_case(other.0)
51    }
52}
53
54impl Ord for LowerHeader<'_> {
55    fn cmp(&self, other: &Self) -> Ordering {
56        cmp_ignore_ascii_case(self.0, other.0)
57    }
58}
59
60impl PartialOrd for LowerHeader<'_> {
61    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
62        Some(self.cmp(other))
63    }
64}
65
66impl Eq for LowerHeader<'_> {}
67
68impl std::hash::Hash for LowerHeader<'_> {
69    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
70        for byte in self.0 {
71            state.write_u8(byte.to_ascii_lowercase());
72        }
73    }
74}
75
76#[derive(Default)]
77struct HeaderDiff<'x> {
78    original: Vec<&'x [u8]>,
79    modified: Vec<&'x [u8]>,
80}
81
82#[derive(Default)]
83struct HeaderApply<'x> {
84    current: Vec<&'x [u8]>,
85    recipe: Option<&'x HeaderRecipe>,
86}
87
88impl Recipe {
89    /// Generates the recipe that turns `modified` back into `original`.
90    pub fn diff(
91        original: &AuthenticatedMessage<'_>,
92        modified: &AuthenticatedMessage<'_>,
93    ) -> Recipe {
94        let mut header_diffs: BTreeMap<LowerHeader<'_>, HeaderDiff> = BTreeMap::new();
95
96        for (name, value) in &original.headers {
97            if !is_non_signed_header(name) {
98                header_diffs
99                    .entry(LowerHeader::new(name))
100                    .or_default()
101                    .original
102                    .push(value.trim_ascii());
103            }
104        }
105        for (name, value) in &modified.headers {
106            if !is_non_signed_header(name) {
107                header_diffs
108                    .entry(LowerHeader::new(name))
109                    .or_default()
110                    .modified
111                    .push(value.trim_ascii());
112            }
113        }
114
115        let mut headers = Vec::new();
116        for (header, mut values) in header_diffs {
117            if values.original != values.modified {
118                values.original.reverse();
119                values.modified.reverse();
120
121                let steps = diff_steps(&values.original, &values.modified);
122                headers.push(HeaderRecipe {
123                    name: std::str::from_utf8(header.0)
124                        .map(str::to_ascii_lowercase)
125                        .unwrap_or_else(|_| String::from_utf8_lossy(header.0).to_ascii_lowercase()),
126                    steps,
127                });
128            }
129        }
130
131        let orig_body = original.raw_body();
132        let mod_body = modified.raw_body();
133        let body = if orig_body == mod_body {
134            BodyRecipe::None
135        } else {
136            let orig_lines = body_lines(orig_body);
137            let mod_lines = body_lines(mod_body);
138            BodyRecipe::Steps(diff_steps(&orig_lines, &mod_lines))
139        };
140
141        Recipe { headers, body }
142    }
143
144    /// Applies this recipe to reconstruct the previous message state.
145    pub fn apply(&self, headers: &[(&[u8], &[u8])], body: &[u8]) -> crate::Result<Vec<u8>> {
146        let mut header_apply: BTreeMap<LowerHeader<'_>, HeaderApply> = BTreeMap::new();
147
148        for (name, value) in headers {
149            if !is_non_signed_header(name) {
150                header_apply
151                    .entry(LowerHeader::new(name))
152                    .or_default()
153                    .current
154                    .push(value.trim_ascii());
155            }
156        }
157
158        for recipe in &self.headers {
159            header_apply
160                .entry(LowerHeader::new(recipe.name.as_bytes()))
161                .or_default()
162                .recipe = Some(recipe);
163        }
164
165        let mut out = Vec::new();
166        for (name, apply) in header_apply {
167            let header_values = if let Some(recipe) = apply.recipe {
168                apply_header_recipe(&apply.current, &recipe.steps)
169            } else {
170                apply.current
171            };
172
173            for current in header_values {
174                out.extend_from_slice(name.0);
175                out.extend_from_slice(b": ");
176                out.extend_from_slice(current);
177                out.extend_from_slice(b"\r\n");
178            }
179        }
180
181        out.extend_from_slice(b"\r\n");
182
183        match &self.body {
184            BodyRecipe::None => {
185                out.extend_from_slice(body);
186            }
187            BodyRecipe::Unreconstructable => {
188                return Err(crate::Error::Dkim2(Dkim2Error::Modified));
189            }
190            BodyRecipe::Steps(steps) => {
191                let lines = body_lines(body);
192                apply_body_recipe(&lines, steps, &mut out);
193            }
194        }
195
196        Ok(out)
197    }
198
199    pub fn to_json(&self, out: &mut Vec<u8>) -> crate::Result<()> {
200        serde_json::to_writer(out, self).map_err(|_| crate::Error::Dkim2(Dkim2Error::Modified))
201    }
202
203    pub fn from_json(bytes: &[u8]) -> crate::Result<Recipe> {
204        serde_json::from_slice(bytes).map_err(|_| crate::Error::Dkim2(Dkim2Error::Modified))
205    }
206}
207
208fn body_lines(body: &[u8]) -> Vec<&[u8]> {
209    let mut lines = Vec::with_capacity(16);
210
211    for line in body.split(|ch| *ch == b'\n') {
212        lines.push(line.strip_suffix(b"\r").unwrap_or(line));
213    }
214
215    if lines.last().is_some_and(|l| l.is_empty()) {
216        lines.pop();
217    }
218
219    lines
220}
221
222fn apply_header_recipe<'x>(instances: &[&'x [u8]], steps: &'x [Step]) -> Vec<&'x [u8]> {
223    let mut emitted: Vec<&'x [u8]> = Vec::new();
224
225    for step in steps {
226        match step {
227            Step::Copy { start, end } => {
228                let high = (*end).min(instances.len() as u32);
229                for i in *start..=high {
230                    if let Some(line) = instances
231                        .len()
232                        .checked_sub(i as usize)
233                        .and_then(|idx| instances.get(idx))
234                    {
235                        emitted.push(*line);
236                    }
237                }
238            }
239            Step::Data(values) => {
240                for value in values {
241                    emitted.push(value.as_bytes());
242                }
243            }
244        }
245    }
246
247    emitted.reverse();
248    emitted
249}
250
251fn apply_body_recipe(lines: &[&[u8]], steps: &[Step], out: &mut Vec<u8>) {
252    let mark = out.len();
253
254    for step in steps {
255        match step {
256            Step::Copy { start, end } => {
257                let high = (*end).min(lines.len() as u32);
258                for i in *start..=high {
259                    if let Some(idx) = (i as usize).checked_sub(1)
260                        && let Some(line) = lines.get(idx)
261                    {
262                        out.extend_from_slice(line);
263                        out.extend_from_slice(b"\r\n");
264                    }
265                }
266            }
267            Step::Data(values) => {
268                for value in values {
269                    out.extend_from_slice(value.as_bytes());
270                    out.extend_from_slice(b"\r\n");
271                }
272            }
273        }
274    }
275
276    if out.len() == mark {
277        out.extend_from_slice(b"\r\n");
278    }
279}
280
281fn diff_steps(original: &[&[u8]], modified: &[&[u8]]) -> Vec<Step> {
282    let mut steps: Vec<Step> = Vec::new();
283    let mut data: Vec<String> = Vec::new();
284
285    for op in capture_diff_slices(Algorithm::Myers, modified, original) {
286        match op {
287            DiffOp::Equal { old_index, len, .. } => {
288                if !data.is_empty() {
289                    steps.push(Step::Data(std::mem::take(&mut data)));
290                }
291                steps.push(Step::Copy {
292                    start: old_index as u32 + 1,
293                    end: (old_index + len) as u32,
294                });
295            }
296            DiffOp::Insert {
297                new_index, new_len, ..
298            }
299            | DiffOp::Replace {
300                new_index, new_len, ..
301            } => {
302                for line in &original[new_index..new_index + new_len] {
303                    data.push(unfold_lossy(line));
304                }
305            }
306            DiffOp::Delete { .. } => {}
307        }
308    }
309    if !data.is_empty() {
310        steps.push(Step::Data(data));
311    }
312    steps
313}
314
315fn unfold_lossy(value: &[u8]) -> String {
316    let mut result = Vec::with_capacity(value.len());
317    let mut last_is_crlf = false;
318
319    for &ch in value {
320        match ch {
321            b'\r' | b'\n' => {
322                last_is_crlf = true;
323            }
324            _ => {
325                if last_is_crlf && !ch.is_ascii_whitespace() && !result.is_empty() {
326                    result.push(b' ');
327                }
328                result.push(ch);
329                last_is_crlf = false;
330            }
331        }
332    }
333
334    String::from_utf8(result)
335        .unwrap_or_else(|err| String::from_utf8_lossy(err.as_bytes()).into_owned())
336}
337
338#[cfg(test)]
339mod test {
340    use super::*;
341
342    fn r_headers(name: &str, steps: Vec<Step>) -> Recipe {
343        Recipe {
344            headers: vec![HeaderRecipe {
345                name: name.to_string(),
346                steps,
347            }],
348            body: BodyRecipe::None,
349        }
350    }
351
352    fn json(recipe: &Recipe) -> Vec<u8> {
353        let mut out = Vec::new();
354        recipe.to_json(&mut out).unwrap();
355        out
356    }
357
358    #[test]
359    fn to_json_byte_equality() {
360        let r1 = r_headers("list-unsubscribe", vec![]);
361        assert_eq!(json(&r1), b"{\"h\":{\"list-unsubscribe\":[]}}");
362
363        let r2 = Recipe {
364            headers: vec![],
365            body: BodyRecipe::Steps(vec![Step::Copy { start: 1, end: 1 }]),
366        };
367        assert_eq!(json(&r2), b"{\"b\":[{\"c\":[1,1]}]}");
368
369        let r3 = r_headers(
370            "subject",
371            vec![Step::Data(vec![" Simple test message".to_string()])],
372        );
373        assert_eq!(
374            json(&r3),
375            b"{\"h\":{\"subject\":[{\"d\":[\" Simple test message\"]}]}}"
376        );
377
378        let r4 = r_headers(
379            "authentication-results",
380            vec![Step::Copy { start: 1, end: 3 }],
381        );
382        assert_eq!(
383            json(&r4),
384            b"{\"h\":{\"authentication-results\":[{\"c\":[1,3]}]}}"
385        );
386    }
387
388    #[test]
389    fn from_json_round_trips() {
390        let cases: [&[u8]; 4] = [
391            b"{\"h\":{\"list-unsubscribe\":[]}}",
392            b"{\"b\":[{\"c\":[1,1]}]}",
393            b"{\"h\":{\"subject\":[{\"d\":[\" Simple test message\"]}]}}",
394            b"{\"h\":{\"authentication-results\":[{\"c\":[1,3]}]}}",
395        ];
396        for case in cases {
397            let recipe = Recipe::from_json(case).unwrap();
398            assert_eq!(json(&recipe), case);
399        }
400    }
401
402    #[test]
403    fn from_json_rejects_null_header() {
404        assert!(Recipe::from_json(b"{\"h\":null}").is_err());
405        assert!(Recipe::from_json(b"{\"h\":{\"subject\":null}}").is_err());
406    }
407
408    #[test]
409    fn from_json_body_null_unreconstructable() {
410        let recipe = Recipe::from_json(b"{\"b\":null}").unwrap();
411        assert_eq!(recipe.body, BodyRecipe::Unreconstructable);
412    }
413
414    #[test]
415    fn from_json_ignores_z_step() {
416        let recipe = Recipe::from_json(b"{\"b\":[{\"c\":[1,2]},{\"z\":true}]}").unwrap();
417        assert_eq!(
418            recipe.body,
419            BodyRecipe::Steps(vec![Step::Copy { start: 1, end: 2 }])
420        );
421    }
422
423    fn diff_bytes(original: &[u8], modified: &[u8]) -> Recipe {
424        let o = crate::AuthenticatedMessage::parse(original).unwrap();
425        let m = crate::AuthenticatedMessage::parse(modified).unwrap();
426        Recipe::diff(&o, &m)
427    }
428
429    fn apply_bytes(recipe: &Recipe, message: &[u8]) -> crate::Result<Vec<u8>> {
430        let p = crate::AuthenticatedMessage::parse(message).unwrap();
431        recipe.apply(&p.headers, p.raw_body())
432    }
433
434    fn signed_hashes(message: &[u8]) -> (Vec<u8>, Vec<u8>) {
435        use crate::common::crypto::HashAlgorithm;
436        let p = crate::AuthenticatedMessage::parse(message).unwrap();
437        (
438            HashAlgorithm::Sha256
439                .headers_hash(p.headers.iter().copied())
440                .as_ref()
441                .to_vec(),
442            HashAlgorithm::Sha256
443                .body_hash(p.raw_body())
444                .as_ref()
445                .to_vec(),
446        )
447    }
448
449    #[test]
450    fn diff_apply_round_trips() {
451        let cases: &[(&str, &[u8], &[u8])] = &[
452            (
453                "body_change",
454                b"Subject: test\r\n\r\nhello\r\nworld\r\ngoodbye\r\n",
455                b"Subject: test\r\n\r\nhello\r\nMODIFIED\r\ngoodbye\r\n",
456            ),
457            (
458                "body_insert_delete",
459                b"From: a\r\n\r\nline1\r\nline2\r\nline3\r\nline4\r\n",
460                b"From: a\r\n\r\nline1\r\nline3\r\nline4\r\nextra\r\n",
461            ),
462            (
463                "header_add",
464                b"Subject: hi\r\nFrom: a\r\nTo: b\r\n\r\nbody\r\n",
465                b"From: a\r\nTo: b\r\n\r\nbody\r\n",
466            ),
467            (
468                "header_remove",
469                b"From: a\r\nTo: b\r\n\r\nbody\r\n",
470                b"From: a\r\nSubject: spam\r\nTo: b\r\n\r\nbody\r\n",
471            ),
472            (
473                "header_value_change",
474                b"Subject: original subject\r\nFrom: a\r\n\r\nbody\r\n",
475                b"Subject: changed subject\r\nFrom: a\r\n\r\nbody\r\n",
476            ),
477            (
478                "dup_header_change",
479                b"From: a\r\nList-Id: one\r\nList-Id: two\r\n\r\nbody\r\n",
480                b"From: a\r\nList-Id: one\r\nList-Id: CHANGED\r\n\r\nbody\r\n",
481            ),
482            (
483                "unchanged",
484                b"From: a\r\nTo: b\r\n\r\nbody line\r\n",
485                b"From: a\r\nTo: b\r\n\r\nbody line\r\n",
486            ),
487            (
488                "header_reorder",
489                b"Subject: one\r\nComment: two\r\nSubject: three\r\n\r\nbody\r\n",
490                b"Comment: two\r\nSubject: three\r\nSubject: one\r\n\r\nbody\r\n",
491            ),
492            (
493                "body_multi_range",
494                b"From: a\r\n\r\none\r\ntwo\r\nthree\r\nfour\r\nfive\r\n",
495                b"From: a\r\n\r\nzero\r\none\r\ntwo\r\nthree\r\nbanana\r\nfour\r\n",
496            ),
497        ];
498        for (label, original, modified) in cases {
499            let recipe = diff_bytes(original, modified);
500            let reconstructed = apply_bytes(&recipe, modified).unwrap();
501            assert_eq!(
502                signed_hashes(&reconstructed),
503                signed_hashes(original),
504                "case {label}: recipe={recipe:?} reconstructed={:?}",
505                String::from_utf8_lossy(&reconstructed)
506            );
507        }
508    }
509
510    #[test]
511    fn myers_diff_serialization() {
512        let cases: &[(&str, &[u8], &[u8], &str)] = &[
513            (
514                "deleted",
515                b"Comment: two\r\nSubject: three\r\nSubject: four\r\nSubject: one\r\n\r\nbody\r\n",
516                b"Comment: two\r\nSubject: three\r\nSubject: one\r\n\r\nbody\r\n",
517                r#"{"h":{"subject":[{"c":[1,1]},{"d":["four"]},{"c":[2,2]}]}}"#,
518            ),
519            (
520                "ranges",
521                b"Subject: one\r\nSubject: two\r\nSubject: three\r\nSubject: four\r\nSubject: five\r\n\r\nbody\r\n",
522                b"Subject: zero\r\nSubject: one\r\nSubject: two\r\nSubject: three\r\nSubject: banana\r\nSubject: four\r\n\r\nbody\r\n",
523                r#"{"h":{"subject":[{"d":["five"]},{"c":[1,1]},{"c":[3,5]}]}}"#,
524            ),
525            (
526                "reorder",
527                b"Subject: one\r\nComment: two\r\nSubject: three\r\n\r\nbody\r\n",
528                b"Comment: two\r\nSubject: three\r\nSubject: one\r\n\r\nbody\r\n",
529                r#"{"h":{"subject":[{"d":["three"]},{"c":[1,1]}]}}"#,
530            ),
531            (
532                "body_multi_range",
533                b"From: a\r\n\r\nl1\r\nl2\r\nl3\r\nold-line\r\nl5\r\n",
534                b"From: a\r\n\r\nl1\r\nl2\r\nl3\r\nnew-line\r\nl5\r\n",
535                r#"{"b":[{"c":[1,3]},{"d":["old-line"]},{"c":[5,5]}]}"#,
536            ),
537        ];
538        for (label, original, modified, want) in cases {
539            let recipe = diff_bytes(original, modified);
540            let mut json = Vec::new();
541            recipe.to_json(&mut json).unwrap();
542            assert_eq!(String::from_utf8_lossy(&json), *want, "case {label}");
543            let reconstructed = apply_bytes(&recipe, modified).unwrap();
544            assert_eq!(
545                signed_hashes(&reconstructed),
546                signed_hashes(original),
547                "case {label} round-trip"
548            );
549        }
550    }
551
552    #[test]
553    #[allow(clippy::type_complexity)]
554    fn apply_header_oracles() {
555        fn headers_of(message: &[u8]) -> Vec<(String, String)> {
556            let p = crate::AuthenticatedMessage::parse(message).unwrap();
557            let mut headers: Vec<(String, String)> = p
558                .headers
559                .iter()
560                .map(|(n, v)| {
561                    (
562                        String::from_utf8_lossy(n).trim().to_ascii_lowercase(),
563                        String::from_utf8_lossy(v).trim().to_string(),
564                    )
565                })
566                .collect();
567            headers.sort();
568            headers
569        }
570
571        let input = b"Subject: one\r\nComment: two\r\nSubject: three\r\n\r\n";
572        let cases: &[(&str, &[u8], &[(&str, &str)])] = &[
573            (
574                "copy_one",
575                br#"{"h":{"subject":[{"c":[2,2]}],"comment":[]}}"#,
576                &[("subject", "one")],
577            ),
578            (
579                "preserve_unmentioned",
580                br#"{"h":{"comment":[]}}"#,
581                &[("subject", "one"), ("subject", "three")],
582            ),
583            (
584                "no_change",
585                br#"{}"#,
586                &[("comment", "two"), ("subject", "one"), ("subject", "three")],
587            ),
588        ];
589
590        for (label, json, want) in cases {
591            let recipe = Recipe::from_json(json).unwrap();
592            let reconstructed = apply_bytes(&recipe, input).unwrap();
593            let mut want: Vec<(String, String)> = want
594                .iter()
595                .map(|(n, v)| (n.to_string(), v.to_string()))
596                .collect();
597            want.sort();
598            assert_eq!(
599                headers_of(&reconstructed),
600                want,
601                "case {label}: {}",
602                String::from_utf8_lossy(&reconstructed)
603            );
604        }
605    }
606
607    #[test]
608    fn apply_unreconstructable_errors() {
609        let recipe = Recipe {
610            headers: vec![],
611            body: BodyRecipe::Unreconstructable,
612        };
613        assert!(apply_bytes(&recipe, b"From: a\r\n\r\nbody\r\n").is_err());
614    }
615
616    #[test]
617    fn to_json_non_ascii_round_trips() {
618        let recipe = r_headers("subject", vec![Step::Data(vec!["café \u{1}".to_string()])]);
619        let encoded = json(&recipe);
620        assert_eq!(
621            encoded,
622            "{\"h\":{\"subject\":[{\"d\":[\"café \\u0001\"]}]}}".as_bytes()
623        );
624        let decoded = Recipe::from_json(&encoded).unwrap();
625        assert_eq!(decoded.headers[0].steps, recipe.headers[0].steps);
626    }
627
628    #[test]
629    fn copy_range_huge_end_is_bounded() {
630        let recipe = Recipe {
631            headers: vec![],
632            body: BodyRecipe::Steps(vec![Step::Copy {
633                start: 1,
634                end: u32::MAX,
635            }]),
636        };
637        let start = std::time::Instant::now();
638        let out = apply_bytes(&recipe, b"From: a\r\n\r\nline1\r\nline2\r\n").unwrap();
639        assert!(start.elapsed().as_secs() < 1);
640        assert!(out.windows(5).any(|w| w == b"line1"));
641    }
642
643    #[test]
644    fn non_utf8_body_round_trips() {
645        let original: &[u8] = b"From: a\r\n\r\nhel\x80lo\r\nworld\r\n";
646        let modified: &[u8] = b"From: a\r\n\r\nhel\x80lo\r\nWORLD\r\n";
647        let recipe = diff_bytes(original, modified);
648        let reconstructed = apply_bytes(&recipe, modified).unwrap();
649        assert_eq!(signed_hashes(&reconstructed), signed_hashes(original));
650        assert!(reconstructed.contains(&0x80));
651    }
652
653    #[test]
654    fn copy_out_of_range_does_not_panic() {
655        let recipe = Recipe {
656            headers: vec![],
657            body: BodyRecipe::Steps(vec![Step::Copy { start: 5, end: 10 }]),
658        };
659        let out = apply_bytes(&recipe, b"From: a\r\n\r\nline1\r\nline2\r\n").unwrap();
660        assert!(String::from_utf8_lossy(&out).contains("\r\n\r\n"));
661    }
662
663    #[test]
664    fn copy_zero_start_does_not_panic() {
665        let recipe = Recipe {
666            headers: vec![],
667            body: BodyRecipe::Steps(vec![Step::Copy { start: 0, end: 2 }]),
668        };
669        apply_bytes(&recipe, b"X: y\r\n\r\nl1\r\nl2\r\n").unwrap();
670    }
671
672    #[test]
673    fn from_json_huge_copy_is_bounded_on_apply() {
674        let r = Recipe::from_json(b"{\"b\":[{\"c\":[4294967295,4294967295]}]}").unwrap();
675        let out = apply_bytes(&r, b"X: y\r\n\r\nl1\r\n").unwrap();
676        assert!(String::from_utf8_lossy(&out).contains("\r\n\r\n"));
677    }
678
679    #[test]
680    fn apply_inserts_missing_header() {
681        let recipe = Recipe {
682            headers: vec![HeaderRecipe {
683                name: "subject".to_string(),
684                steps: vec![Step::Data(vec!["Injected".to_string()])],
685            }],
686            body: BodyRecipe::None,
687        };
688        let out = apply_bytes(&recipe, b"From: a\r\nTo: b\r\n\r\nbody\r\n").unwrap();
689        assert!(String::from_utf8_lossy(&out).contains("subject: Injected"));
690    }
691
692    fn assert_chain_reconstructs(versions: &[&[u8]], via_json: bool) {
693        assert!(versions.len() >= 2, "a chain needs at least two versions");
694
695        let recipes: Vec<Recipe> = versions
696            .windows(2)
697            .map(|pair| {
698                let recipe = diff_bytes(pair[0], pair[1]);
699                if via_json {
700                    Recipe::from_json(&json(&recipe)).unwrap()
701                } else {
702                    recipe
703                }
704            })
705            .collect();
706
707        let mut current = versions[versions.len() - 1].to_vec();
708        for (hop, recipe) in recipes.iter().enumerate().rev() {
709            let reconstructed = apply_bytes(recipe, &current).unwrap();
710            let expected = versions[hop];
711            assert_eq!(
712                signed_hashes(&reconstructed),
713                signed_hashes(expected),
714                "hop {hop} (via_json={via_json}) recipe={recipe:?}\n  reconstructed={:?}\n  expected={:?}",
715                String::from_utf8_lossy(&reconstructed),
716                String::from_utf8_lossy(expected),
717            );
718            current = reconstructed;
719        }
720    }
721
722    fn assert_chain(versions: &[&[u8]]) {
723        assert_chain_reconstructs(versions, false);
724        assert_chain_reconstructs(versions, true);
725    }
726
727    #[test]
728    fn chain_header_value_changes() {
729        assert_chain(&[
730            b"From: alice@example.com\r\nTo: bob@example.com\r\nSubject: v0\r\n\r\nHello world\r\n",
731            b"From: alice@example.com\r\nTo: bob@example.com\r\nSubject: v1\r\n\r\nHello world\r\n",
732            b"From: alice@example.com\r\nTo: carol@example.com\r\nSubject: v2\r\n\r\nHello world\r\n",
733            b"From: alice@example.com\r\nTo: carol@example.com\r\nSubject: final\r\n\r\nHello world\r\n",
734        ]);
735    }
736
737    #[test]
738    fn chain_header_insertions() {
739        assert_chain(&[
740            b"From: a\r\nTo: b\r\n\r\nbody\r\n",
741            b"From: a\r\nTo: b\r\nSubject: added\r\n\r\nbody\r\n",
742            b"From: a\r\nReply-To: r\r\nTo: b\r\nSubject: added\r\n\r\nbody\r\n",
743            b"From: a\r\nReply-To: r\r\nTo: b\r\nSubject: added\r\nList-Id: <l>\r\n\r\nbody\r\n",
744        ]);
745    }
746
747    #[test]
748    fn chain_header_deletions() {
749        assert_chain(&[
750            b"From: a\r\nReply-To: r\r\nTo: b\r\nSubject: s\r\nList-Id: <l>\r\n\r\nbody\r\n",
751            b"From: a\r\nTo: b\r\nSubject: s\r\nList-Id: <l>\r\n\r\nbody\r\n",
752            b"From: a\r\nTo: b\r\nList-Id: <l>\r\n\r\nbody\r\n",
753            b"From: a\r\nTo: b\r\n\r\nbody\r\n",
754        ]);
755    }
756
757    #[test]
758    fn chain_mixed_header_insert_change_delete() {
759        assert_chain(&[
760            b"From: a\r\nTo: b\r\nSubject: original\r\n\r\nbody\r\n",
761            b"From: a\r\nReply-To: r\r\nTo: b\r\nSubject: original\r\n\r\nbody\r\n",
762            b"From: a\r\nReply-To: r\r\nTo: b\r\nSubject: edited\r\n\r\nbody\r\n",
763            b"From: a\r\nReply-To: r\r\nTo: b\r\n\r\nbody\r\n",
764        ]);
765    }
766
767    #[test]
768    fn chain_duplicate_header_evolution() {
769        assert_chain(&[
770            b"From: a\r\nComments: alpha\r\nComments: beta\r\n\r\nbody\r\n",
771            b"From: a\r\nComments: alpha\r\nComments: beta\r\nComments: gamma\r\n\r\nbody\r\n",
772            b"From: a\r\nComments: alpha\r\nComments: gamma\r\n\r\nbody\r\n",
773            b"From: a\r\nComments: ALPHA\r\nComments: gamma\r\n\r\nbody\r\n",
774        ]);
775    }
776
777    #[test]
778    fn chain_duplicate_header_interleaved_changes() {
779        assert_chain(&[
780            b"From: a\r\nReceived-SPF: a\r\nComments: 1\r\nComments: 2\r\nComments: 3\r\nComments: 4\r\nComments: 5\r\n\r\nbody\r\n",
781            b"From: a\r\nReceived-SPF: a\r\nComments: 1\r\nComments: 2\r\nComments: THREE\r\nComments: 4\r\nComments: 5\r\n\r\nbody\r\n",
782            b"From: a\r\nReceived-SPF: a\r\nComments: 1\r\nComments: THREE\r\nComments: 5\r\n\r\nbody\r\n",
783            b"From: a\r\nReceived-SPF: a\r\nComments: 0\r\nComments: 1\r\nComments: THREE\r\nComments: 5\r\nComments: 6\r\n\r\nbody\r\n",
784        ]);
785    }
786
787    #[test]
788    fn chain_body_line_changes() {
789        assert_chain(&[
790            b"From: a\r\n\r\nline1\r\nline2\r\nline3\r\n",
791            b"From: a\r\n\r\nline1\r\nCHANGED\r\nline3\r\n",
792            b"From: a\r\n\r\nFIRST\r\nCHANGED\r\nlast\r\n",
793            b"From: a\r\n\r\nFIRST\r\nCHANGED\r\nLAST\r\n",
794        ]);
795    }
796
797    #[test]
798    fn chain_body_insertions() {
799        assert_chain(&[
800            b"From: a\r\n\r\nline1\r\nline2\r\n",
801            b"From: a\r\n\r\nline1\r\ninserted\r\nline2\r\n",
802            b"From: a\r\n\r\nline1\r\ninserted\r\nline2\r\nappended\r\n",
803            b"From: a\r\n\r\nprepended\r\nline1\r\ninserted\r\nline2\r\nappended\r\n",
804        ]);
805    }
806
807    #[test]
808    fn chain_body_deletions() {
809        assert_chain(&[
810            b"From: a\r\n\r\nl1\r\nl2\r\nl3\r\nl4\r\nl5\r\n",
811            b"From: a\r\n\r\nl1\r\nl2\r\nl4\r\nl5\r\n",
812            b"From: a\r\n\r\nl2\r\nl4\r\nl5\r\n",
813            b"From: a\r\n\r\nl2\r\nl4\r\n",
814        ]);
815    }
816
817    #[test]
818    fn chain_body_and_headers_each_hop() {
819        assert_chain(&[
820            b"From: a\r\nSubject: s0\r\n\r\nintro\r\nmiddle\r\nclose\r\n",
821            b"From: a\r\nSubject: s1\r\n\r\nintro\r\nMIDDLE\r\nclose\r\n",
822            b"From: a\r\nSubject: s2\r\nX-Tag: keep\r\n\r\nintro\r\nMIDDLE\r\nadded\r\nclose\r\n",
823            b"From: a\r\nSubject: s2\r\nX-Tag: keep\r\n\r\nMIDDLE\r\nadded\r\n",
824        ]);
825    }
826
827    #[test]
828    fn chain_with_noop_hop() {
829        assert_chain(&[
830            b"From: a\r\nSubject: keep\r\n\r\nbody line\r\n",
831            b"From: a\r\nSubject: keep\r\n\r\nbody line\r\n",
832            b"From: a\r\nSubject: changed\r\n\r\nbody line\r\n",
833        ]);
834    }
835
836    #[test]
837    fn chain_body_emptied_then_refilled() {
838        assert_chain(&[
839            b"From: a\r\n\r\nfirst\r\nsecond\r\n",
840            b"From: a\r\n\r\n",
841            b"From: a\r\n\r\nbrand new line\r\n",
842        ]);
843    }
844
845    #[test]
846    fn chain_empty_header_value() {
847        assert_chain(&[
848            b"From: a\r\nSubject: hello\r\n\r\nbody\r\n",
849            b"From: a\r\nSubject:\r\n\r\nbody\r\n",
850            b"From: a\r\nSubject: world\r\n\r\nbody\r\n",
851        ]);
852    }
853
854    #[test]
855    fn chain_non_utf8_body_copied_lines() {
856        assert_chain(&[
857            b"From: a\r\n\r\nhel\x80lo\r\nworld\r\n\xff\xfe binary\r\n",
858            b"From: a\r\n\r\nhel\x80lo\r\nWORLD\r\n\xff\xfe binary\r\n",
859            b"From: a\r\n\r\nhel\x80lo\r\nWORLD\r\ninserted\r\n\xff\xfe binary\r\n",
860        ]);
861    }
862
863    #[test]
864    fn chain_body_without_trailing_crlf() {
865        assert_chain(&[
866            b"From: a\r\n\r\nl1\r\nl2\r\nl3",
867            b"From: a\r\n\r\nl1\r\nCHANGED\r\nl3",
868            b"From: a\r\n\r\nl1\r\nCHANGED",
869        ]);
870    }
871
872    #[test]
873    fn chain_header_reinserted_after_deletion() {
874        assert_chain(&[
875            b"From: a\r\nSubject: present\r\n\r\nbody\r\n",
876            b"From: a\r\n\r\nbody\r\n",
877            b"From: a\r\nSubject: back again\r\n\r\nbody\r\n",
878        ]);
879    }
880
881    #[test]
882    fn chain_internal_whitespace_changes_are_reconstructed() {
883        assert_chain(&[
884            b"From: a\r\nSubject: spaced   out   value\r\n\r\nbody\r\n",
885            b"From: a\r\nSubject: spaced out value\r\n\r\nbody\r\n",
886        ]);
887    }
888
889    #[test]
890    fn diff_numbers_duplicate_headers_bottom_up() {
891        let recipe = diff_bytes(
892            b"From: a\r\nComments: top\r\nComments: middle\r\nComments: bottom\r\n\r\nbody\r\n",
893            b"From: a\r\nComments: top\r\nComments: bottom\r\n\r\nbody\r\n",
894        );
895        let header = recipe
896            .headers
897            .iter()
898            .find(|h| h.name.eq_ignore_ascii_case("comments"))
899            .expect("comments recipe present");
900        assert_eq!(
901            header.steps,
902            vec![
903                Step::Copy { start: 1, end: 1 },
904                Step::Data(vec!["middle".to_string()]),
905                Step::Copy { start: 2, end: 2 },
906            ],
907        );
908    }
909
910    #[test]
911    fn diff_numbers_body_lines_top_down() {
912        let recipe = diff_bytes(
913            b"From: a\r\n\r\nfirst\r\nsecond\r\nthird\r\n",
914            b"From: a\r\n\r\nfirst\r\nCHANGED\r\nthird\r\n",
915        );
916        assert_eq!(
917            recipe.body,
918            BodyRecipe::Steps(vec![
919                Step::Copy { start: 1, end: 1 },
920                Step::Data(vec!["second".to_string()]),
921                Step::Copy { start: 3, end: 3 },
922            ]),
923        );
924    }
925
926    #[test]
927    fn diff_encodes_full_add_and_remove() {
928        let added = diff_bytes(
929            b"From: a\r\nSubject: was here\r\n\r\nbody\r\n",
930            b"From: a\r\n\r\nbody\r\n",
931        );
932        let subject = added
933            .headers
934            .iter()
935            .find(|h| h.name.eq_ignore_ascii_case("subject"))
936            .unwrap();
937        assert_eq!(
938            subject.steps,
939            vec![Step::Data(vec!["was here".to_string()])]
940        );
941
942        let removed = diff_bytes(
943            b"From: a\r\n\r\nbody\r\n",
944            b"From: a\r\nSubject: injected\r\n\r\nbody\r\n",
945        );
946        let subject = removed
947            .headers
948            .iter()
949            .find(|h| h.name.eq_ignore_ascii_case("subject"))
950            .unwrap();
951        assert!(
952            subject.steps.is_empty(),
953            "empty recipe removes all instances"
954        );
955    }
956
957    #[test]
958    fn diff_copy_ranges_are_strictly_ascending() {
959        let recipe = diff_bytes(
960            b"From: a\r\nComments: 1\r\nComments: 2\r\nComments: 3\r\nComments: 4\r\nComments: 5\r\n\r\nbody\r\n",
961            b"From: a\r\nComments: 1\r\nComments: TWO\r\nComments: 3\r\nComments: FOUR\r\nComments: 5\r\n\r\nbody\r\n",
962        );
963        let header = recipe
964            .headers
965            .iter()
966            .find(|h| h.name.eq_ignore_ascii_case("comments"))
967            .unwrap();
968        assert_copy_ranges_ascending(&header.steps);
969
970        let body = diff_bytes(
971            b"From: a\r\n\r\na\r\nb\r\nc\r\nd\r\ne\r\nf\r\n",
972            b"From: a\r\n\r\na\r\nB\r\nc\r\nd\r\nE\r\nf\r\n",
973        )
974        .body;
975        if let BodyRecipe::Steps(steps) = body {
976            assert_copy_ranges_ascending(&steps);
977        } else {
978            panic!("expected body steps");
979        }
980    }
981
982    fn assert_no_crlf_in_data(recipe: &Recipe) {
983        let check = |values: &[String], ctx: &str| {
984            for value in values {
985                assert!(
986                    !value.contains('\r') && !value.contains('\n'),
987                    "{ctx} data string contains CR/LF: {value:?}"
988                );
989            }
990        };
991        for header in &recipe.headers {
992            for step in &header.steps {
993                if let Step::Data(values) = step {
994                    check(values, &format!("header {}", header.name));
995                }
996            }
997        }
998        if let BodyRecipe::Steps(steps) = &recipe.body {
999            for step in steps {
1000                if let Step::Data(values) = step {
1001                    check(values, "body");
1002                }
1003            }
1004        }
1005    }
1006
1007    #[test]
1008    fn data_strings_never_contain_crlf() {
1009        let recipes = [
1010            diff_bytes(
1011                b"From: a\r\nSubject: short value\r\n\r\nbody\r\n",
1012                b"From: a\r\nSubject: a much longer replacement subject value\r\n\r\nbody\r\n",
1013            ),
1014            diff_bytes(
1015                b"From: a\r\nSubject: one\r\n two\r\n three\r\n\r\nbody\r\n",
1016                b"From: a\r\nSubject: unrelated\r\n\r\nbody\r\n",
1017            ),
1018            diff_bytes(
1019                b"From: a\r\nSubject: line one;\r\n\tline two;\r\n\tline three\r\n\r\nbody\r\n",
1020                b"From: a\r\n\r\nbody\r\n",
1021            ),
1022            diff_bytes(
1023                b"From: a\r\n\r\nplain\r\nbody\r\n",
1024                b"From: a\r\n\r\nplain\r\ndifferent\r\n",
1025            ),
1026        ];
1027        for recipe in &recipes {
1028            assert_no_crlf_in_data(recipe);
1029        }
1030    }
1031
1032    #[test]
1033    fn unfold_lossy_replaces_terminators_with_space() {
1034        assert_eq!(unfold_lossy(b"one\r\n two"), "one two");
1035        assert_eq!(unfold_lossy(b"alpha\r\nbeta"), "alpha beta");
1036        assert_eq!(unfold_lossy(b"lone\rcr"), "lone cr");
1037        assert_eq!(unfold_lossy(b"lone\nlf"), "lone lf");
1038        assert_eq!(unfold_lossy(b"no terminators"), "no terminators");
1039    }
1040
1041    /// A folded header reconstructed from a "d" step must hash identically to the
1042    /// original folded header: the fold collapses to whitespace either way.
1043    #[test]
1044    fn folded_header_data_step_is_hash_equivalent() {
1045        let recipe = diff_bytes(
1046            b"From: a\r\nSubject: part one\r\n part two\r\n\r\nbody\r\n",
1047            b"From: a\r\n\r\nbody\r\n",
1048        );
1049        assert_no_crlf_in_data(&recipe);
1050        let reconstructed = apply_bytes(&recipe, b"From: a\r\n\r\nbody\r\n").unwrap();
1051        assert_eq!(
1052            signed_hashes(&reconstructed),
1053            signed_hashes(b"From: a\r\nSubject: part one part two\r\n\r\nbody\r\n"),
1054        );
1055    }
1056
1057    #[test]
1058    fn chain_folded_header_round_trips() {
1059        assert_chain(&[
1060            b"From: a\r\nSubject: a folded header\r\n value spanning\r\n three lines\r\n\r\nbody\r\n",
1061            b"From: a\r\nSubject: now unfolded and changed\r\n\r\nbody\r\n",
1062            b"From: a\r\nSubject: refolded value\r\n that wraps again\r\n\r\nbody\r\n",
1063        ]);
1064    }
1065
1066    fn assert_copy_ranges_ascending(steps: &[Step]) {
1067        let mut prev_end = 0u32;
1068        for step in steps {
1069            if let Step::Copy { start, end } = step {
1070                assert!(
1071                    *start > prev_end,
1072                    "copy start {start} must exceed previous end {prev_end}: {steps:?}"
1073                );
1074                assert!(
1075                    start <= end,
1076                    "copy start {start} after end {end}: {steps:?}"
1077                );
1078                prev_end = *end;
1079            }
1080        }
1081    }
1082}
mail_auth/dkim2/recipe.rs

mail_auth/dkim2/
recipe.rs
