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

mail_auth/dkim2/
recipe.rs
