From: Matt Corallo <git@bluematt.me>
Date: Tue, 6 Feb 2024 17:53:41 +0000 (+0000)
Subject: Correct TXT sort order on unlikely edge cases
X-Git-Url: http://git.bitcoin.ninja/index.cgi?p=dnssec-prover;a=commitdiff_plain;h=fb95ca84534249078d82f9d0b26ceb1e52427330

Correct TXT sort order on unlikely edge cases
---

diff --git a/src/rr.rs b/src/rr.rs
index 14826e3..41c0ee2 100644
--- a/src/rr.rs
+++ b/src/rr.rs
@@ -7,7 +7,7 @@ use alloc::vec::Vec;
 use alloc::string::String;
 use alloc::borrow::ToOwned;
 
-use core::cmp::Ordering;
+use core::cmp::{self, Ordering};
 
 use crate::ser::*;
 
@@ -171,8 +171,18 @@ pub struct Txt {
 impl PartialOrd for Txt {
 	fn partial_cmp(&self, o: &Txt) -> Option<Ordering> {
 		Some(self.name.cmp(&o.name)
-			.then_with(|| self.data.len().cmp(&o.data.len()))
-			.then_with(|| self.data.cmp(&o.data)))
+			.then_with(|| {
+				// Compare in wire encoding form, i.e. compare in 255-byte chunks
+				for i in 1..(self.data.len() / 255) + 2 {
+					let start = (i - 1)*255;
+					let self_len = cmp::min(i * 255, self.data.len());
+					let o_len = cmp::min(i * 255, o.data.len());
+					let slice_cmp = self_len.cmp(&o_len)
+						.then_with(|| self.data[start..self_len].cmp(&o.data[start..o_len]));
+					if !slice_cmp.is_eq() { return slice_cmp; }
+				}
+				Ordering::Equal
+			}))
 	}
 }
 impl StaticRecord for Txt {
diff --git a/src/validation.rs b/src/validation.rs
index 30a541a..491cbaa 100644
--- a/src/validation.rs
+++ b/src/validation.rs
@@ -550,6 +550,41 @@ mod tests {
 		(cname_resp, cname_rrsig, txt_resp, txt_rrsig)
 	}
 
+	fn matcorallo_txt_sort_edge_cases_records() -> (Vec<Txt>, RRSig) {
+		let txts = vec![Txt {
+			name: "txt_sort_order.matcorallo.com.".try_into().unwrap(),
+			data: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab".to_owned().into_bytes(),
+		}, Txt {
+			name: "txt_sort_order.matcorallo.com.".try_into().unwrap(),
+			data: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".to_owned().into_bytes(),
+		}, Txt {
+			name: "txt_sort_order.matcorallo.com.".try_into().unwrap(),
+			data: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaa".to_owned().into_bytes(),
+		}, Txt {
+			name: "txt_sort_order.matcorallo.com.".try_into().unwrap(),
+			data: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaba".to_owned().into_bytes(),
+		}, Txt {
+			name: "txt_sort_order.matcorallo.com.".try_into().unwrap(),
+			data: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".to_owned().into_bytes(),
+		}, Txt {
+			name: "txt_sort_order.matcorallo.com.".try_into().unwrap(),
+			data: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab".to_owned().into_bytes(),
+		}, Txt {
+			name: "txt_sort_order.matcorallo.com.".try_into().unwrap(),
+			data: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".to_owned().into_bytes(),
+		}, Txt {
+			name: "txt_sort_order.matcorallo.com.".try_into().unwrap(),
+			data: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaba".to_owned().into_bytes(),
+		}];
+		let rrsig = RRSig {
+			name: "txt_sort_order.matcorallo.com.".try_into().unwrap(),
+			ty: Txt::TYPE, alg: 13, labels: 3, orig_ttl: 30, expiration: 1708449632,
+			inception: 1707234632, key_tag: 34530, key_name: "matcorallo.com.".try_into().unwrap(),
+			signature: base64::decode("elAhELwzkGpUMvzeiYZpg1+yRFPjmOeEd1ir1vYx2Dku9kzsXmAlejOYDPWdaJ6ekvHdMejCN/MtyI+iFAYqsw==").unwrap(),
+		};
+		(txts, rrsig)
+	}
+
 	#[test]
 	fn check_txt_record_a() {
 		let dnskeys = mattcorallo_dnskey().0;
@@ -662,6 +697,27 @@ mod tests {
 		} else { panic!(); }
 	}
 
+	#[test]
+	fn check_txt_sort_order() {
+		let mut rr_stream = Vec::new();
+		for rr in root_dnskey().1 { write_rr(&rr, 1, &mut rr_stream); }
+		for rr in com_dnskey().1 { write_rr(&rr, 1, &mut rr_stream); }
+		for rr in matcorallo_dnskey().1 { write_rr(&rr, 1, &mut rr_stream); }
+		let (mut txts, rrsig) = matcorallo_txt_sort_edge_cases_records();
+		write_rr(&rrsig, 1, &mut rr_stream);
+		for txt in txts.iter() { write_rr(txt, 1, &mut rr_stream); }
+
+		let mut rrs = parse_rr_stream(&rr_stream).unwrap();
+		rrs.shuffle(&mut rand::rngs::OsRng);
+		let verified_rrs = verify_rr_stream(&rrs).unwrap();
+		let mut verified_txts = verified_rrs.verified_rrs
+			.iter().map(|rr| if let RR::Txt(txt) = rr { txt.clone() } else { panic!(); })
+			.collect::<Vec<_>>();
+		verified_txts.sort();
+		txts.sort();
+		assert_eq!(verified_txts, txts);
+	}
+
 	#[test]
 	fn rfc9102_parse_test() {
 		// Note that this is the `AuthenticationChain` field only, and ignores the