From 14b532933eaef71ead0d716b7b23db3c22df00d6 Mon Sep 17 00:00:00 2001
From: Jesse Luehrs <doy@tozt.net>
Date: Wed, 13 May 2015 19:01:17 -0400
Subject: problem 29

---
 src/crack.rs  | 22 ++++++++++++++++++++++
 src/lib.rs    |  1 +
 tests/set4.rs | 22 ++++++++++++++++++++++
 3 files changed, 45 insertions(+)

diff --git a/src/crack.rs b/src/crack.rs
index 5b387bb..a05155f 100644
--- a/src/crack.rs
+++ b/src/crack.rs
@@ -474,6 +474,28 @@ pub fn crack_cbc_iv_key<F1, F2> (encrypt: &F1, verify: &F2) -> Vec<u8> where F1:
     }
 }
 
+pub fn crack_sha1_mac_length_extension (input: &[u8], mac: [u8; 20], extension: &[u8]) -> Vec<(Vec<u8>, [u8; 20])> {
+    let mut sha1_state: [u32; 5] = unsafe { ::std::mem::transmute(mac) };
+    for word in sha1_state.iter_mut() {
+        *word = u32::from_be(*word);
+    }
+
+    (0..100).map(|i| {
+        let new_input: Vec<u8> = input
+            .iter()
+            .chain(::sha1::sha1_padding(i + input.len() as u64).iter())
+            .chain(extension.iter())
+            .map(|x| *x)
+            .collect();
+        let new_hash = ::sha1::sha1_with_state(
+            extension,
+            sha1_state,
+            i + new_input.len() as u64
+        );
+        (new_input, new_hash)
+    }).collect()
+}
+
 fn crack_single_byte_xor_with_confidence (input: &[u8]) -> (u8, f64) {
     let mut min_diff = 100.0;
     let mut best_key = 0;
diff --git a/src/lib.rs b/src/lib.rs
index 2252129..54321fe 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -51,3 +51,4 @@ pub use crack::recover_mt19937_key_from_time;
 pub use crack::crack_aes_128_ctr_random_access;
 pub use crack::crack_ctr_bitflipping;
 pub use crack::crack_cbc_iv_key;
+pub use crack::crack_sha1_mac_length_extension;
diff --git a/tests/set4.rs b/tests/set4.rs
index 495f548..1d31a85 100644
--- a/tests/set4.rs
+++ b/tests/set4.rs
@@ -133,3 +133,25 @@ fn problem_27 () {
 }
 
 // problem 28 is just matasano::sha1_mac
+
+#[test]
+fn problem_29 () {
+    let key: Vec<u8> = ::rand::thread_rng()
+        .gen_iter()
+        .take(::rand::thread_rng().gen_range(5, 25))
+        .collect();
+
+    let valid_input = b"comment1=cooking%20MCs;userdata=foo;comment2=%20like%20a%20pound%20of%20bacon";
+    let valid_mac = matasano::sha1_mac(valid_input, &key[..]);
+    let possibles = matasano::crack_sha1_mac_length_extension(valid_input, valid_mac, b";admin=true");
+    assert!(
+        possibles.iter().all(|&(ref input, _)| {
+            input.ends_with(b";admin=true")
+        })
+    );
+    assert!(
+        possibles.iter().any(|&(ref input, ref mac)| {
+            &matasano::sha1_mac(&input[..], &key[..])[..] == &mac[..]
+        })
+    );
+}
-- 
cgit v1.2.3-54-g00ecf