problem 20

i think this is as far as possible, anyway

5 files changed, 166 insertions, 0 deletions

diff --git a/data/20.out.txt b/data/20.out.txt
new file mode 100644
index 0000000..57bf71c
--- /dev/null
+++ b/data/20.out.txt
@@ -0,0 +1,40 @@
+I have met them at close of day
+Coming with vivid faces
+From counter or desk among grey
+Eighteenth-century houses.
+I have passed with a nod of the head
+Or polite meaningless words,
+Or have lingered awhile and said
+Polite meaningless words,
+And thought before I had done
+Of a mocking tale or a gibe
+To please a companion
+Around the fire at the club;
+Being certain that they and i
+But lived where motley is worn:
+All changed, changed utterly:
+A terrible beauty is born.
+That woman's days were spent
+In ignorant good will,
+Her nights in argument
+Until her voice grew shrill.
+What voice more sweet than hers
+When young and beautiful,
+She rode to harriers?
+This man had kept a school
+And rode our winged horse.
+This other his helper and friend
+Was coming into his force;
+He might have won fame in the end,
+So sensitive his nature seemed,
+So daring and sweet his thought.
+This other man I had dreamed
+A drunken, vain-glorious lout.
+He had done most bitter wrong
+To some who are near my heart,
+Yet I number him in the song;
+He, too, has resigned his part
+In the casual comedy;
+He, too, has been changed in his turn,
+Transformed utterly:
+A terrible beauty is born.
diff --git a/data/20.txt b/data/20.txt
new file mode 100644
index 0000000..affd17b
--- /dev/null
+++ b/data/20.txt
@@ -0,0 +1,40 @@
+SSBoYXZlIG1ldCB0aGVtIGF0IGNsb3NlIG9mIGRheQ==
+Q29taW5nIHdpdGggdml2aWQgZmFjZXM=
+RnJvbSBjb3VudGVyIG9yIGRlc2sgYW1vbmcgZ3JleQ==
+RWlnaHRlZW50aC1jZW50dXJ5IGhvdXNlcy4=
+SSBoYXZlIHBhc3NlZCB3aXRoIGEgbm9kIG9mIHRoZSBoZWFk
+T3IgcG9saXRlIG1lYW5pbmdsZXNzIHdvcmRzLA==
+T3IgaGF2ZSBsaW5nZXJlZCBhd2hpbGUgYW5kIHNhaWQ=
+UG9saXRlIG1lYW5pbmdsZXNzIHdvcmRzLA==
+QW5kIHRob3VnaHQgYmVmb3JlIEkgaGFkIGRvbmU=
+T2YgYSBtb2NraW5nIHRhbGUgb3IgYSBnaWJl
+VG8gcGxlYXNlIGEgY29tcGFuaW9u
+QXJvdW5kIHRoZSBmaXJlIGF0IHRoZSBjbHViLA==
+QmVpbmcgY2VydGFpbiB0aGF0IHRoZXkgYW5kIEk=
+QnV0IGxpdmVkIHdoZXJlIG1vdGxleSBpcyB3b3JuOg==
+QWxsIGNoYW5nZWQsIGNoYW5nZWQgdXR0ZXJseTo=
+QSB0ZXJyaWJsZSBiZWF1dHkgaXMgYm9ybi4=
+VGhhdCB3b21hbidzIGRheXMgd2VyZSBzcGVudA==
+SW4gaWdub3JhbnQgZ29vZCB3aWxsLA==
+SGVyIG5pZ2h0cyBpbiBhcmd1bWVudA==
+VW50aWwgaGVyIHZvaWNlIGdyZXcgc2hyaWxsLg==
+V2hhdCB2b2ljZSBtb3JlIHN3ZWV0IHRoYW4gaGVycw==
+V2hlbiB5b3VuZyBhbmQgYmVhdXRpZnVsLA==
+U2hlIHJvZGUgdG8gaGFycmllcnM/
+VGhpcyBtYW4gaGFkIGtlcHQgYSBzY2hvb2w=
+QW5kIHJvZGUgb3VyIHdpbmdlZCBob3JzZS4=
+VGhpcyBvdGhlciBoaXMgaGVscGVyIGFuZCBmcmllbmQ=
+V2FzIGNvbWluZyBpbnRvIGhpcyBmb3JjZTs=
+SGUgbWlnaHQgaGF2ZSB3b24gZmFtZSBpbiB0aGUgZW5kLA==
+U28gc2Vuc2l0aXZlIGhpcyBuYXR1cmUgc2VlbWVkLA==
+U28gZGFyaW5nIGFuZCBzd2VldCBoaXMgdGhvdWdodC4=
+VGhpcyBvdGhlciBtYW4gSSBoYWQgZHJlYW1lZA==
+QSBkcnVua2VuLCB2YWluLWdsb3Jpb3VzIGxvdXQu
+SGUgaGFkIGRvbmUgbW9zdCBiaXR0ZXIgd3Jvbmc=
+VG8gc29tZSB3aG8gYXJlIG5lYXIgbXkgaGVhcnQs
+WWV0IEkgbnVtYmVyIGhpbSBpbiB0aGUgc29uZzs=
+SGUsIHRvbywgaGFzIHJlc2lnbmVkIGhpcyBwYXJ0
+SW4gdGhlIGNhc3VhbCBjb21lZHk7
+SGUsIHRvbywgaGFzIGJlZW4gY2hhbmdlZCBpbiBoaXMgdHVybiw=
+VHJhbnNmb3JtZWQgdXR0ZXJseTo=
+QSB0ZXJyaWJsZSBiZWF1dHkgaXMgYm9ybi4=
diff --git a/src/crack.rs b/src/crack.rs
index 344488b..5bd476d 100644
--- a/src/crack.rs
+++ b/src/crack.rs
@@ -308,6 +308,55 @@ pub fn crack_cbc_padding_oracle<F> (iv: &[u8], ciphertext: &[u8], f: &F) -> Vec<
     return unpad_pkcs7(&plaintext[..]).unwrap().to_vec();
 }
 
+pub fn crack_fixed_nonce_ctr_statistically (input: Vec<Vec<u8>>) -> Vec<Vec<u8>> {
+    let min_len = input.iter().map(|line| line.len()).min().unwrap();
+    let max_len = input.iter().map(|line| line.len()).max().unwrap();
+
+    let mut plaintext_lines = vec![];
+    for _ in input.iter() {
+        plaintext_lines.push(vec![]);
+    }
+
+    let mut full_key = vec![];
+    for len in min_len..(max_len + 1) {
+        let mut idxs = vec![];
+        let ciphertext: Vec<u8> = input
+            .iter()
+            .enumerate()
+            .filter(|&(idx, line)| {
+                if line.len() >= len {
+                    idxs.push(idx);
+                    true
+                }
+                else {
+                    false
+                }
+            })
+            .flat_map(|(_, line)| line.iter().take(len))
+            .map(|x| *x)
+            .collect();
+
+        let (key, _) = crack_repeating_key_xor_with_keysize(
+            &ciphertext[..],
+            len
+        );
+        for i in full_key.len()..key.len() {
+            full_key.push(key[i])
+        }
+
+        for idx in idxs {
+            let line = repeating_key_xor(&input[idx][..], &full_key[..])
+                .iter()
+                .take(full_key.len())
+                .map(|x| *x)
+                .collect();
+            plaintext_lines[idx] = line;
+        }
+    }
+
+    return plaintext_lines;
+}
+
 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 c1f8cf8..6d04106 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -31,3 +31,4 @@ pub use crack::crack_cbc_padding_oracle;
 pub use crack::find_single_byte_xor_encrypted_string;
 pub use crack::crack_single_byte_xor;
 pub use crack::crack_repeating_key_xor;
+pub use crack::crack_fixed_nonce_ctr_statistically;
diff --git a/tests/lib.rs b/tests/lib.rs
index 65380cf..ec214f4 100644
--- a/tests/lib.rs
+++ b/tests/lib.rs
@@ -2,6 +2,7 @@ extern crate matasano;
 extern crate rustc_serialize as serialize;
 extern crate rand;
 
+use std::ascii::AsciiExt;
 use std::borrow::ToOwned;
 use std::collections::HashMap;
 use std::io::prelude::*;
@@ -27,6 +28,14 @@ fn read_as_base64_lines (filename: &str) -> Vec<Vec<u8>> {
         .collect();
 }
 
+fn read_as_lines (filename: &str) -> Vec<Vec<u8>> {
+    let fh = File::open(filename).unwrap();
+    return std::io::BufStream::new(fh)
+        .lines()
+        .map(|line| line.unwrap().as_bytes().to_vec())
+        .collect();
+}
+
 fn read_as_base64 (filename: &str) -> Vec<u8> {
     let fh = File::open(filename).unwrap();
     return std::io::BufStream::new(fh)
@@ -426,3 +435,30 @@ fn problem_18 () {
 //         .collect();
 //     let plaintexts = matasano::crack_fixed_nonce_ctr_substitutions();
 // }
+
+#[test]
+fn problem_20 () {
+    fn normalize (line_list: Vec<Vec<u8>>, len: usize) -> Vec<Vec<u8>> {
+        line_list
+            .iter()
+            .map(|line| line.to_ascii_lowercase())
+            .map(|line| line.iter().take(len).map(|x| *x).collect())
+            .collect()
+    }
+
+    let key = random_aes_128_key();
+    let ciphertexts = read_as_base64_lines("data/20.txt")
+        .iter()
+        .map(|line| matasano::aes_128_ctr(&line[..], &key[..], 0))
+        .collect();
+    let expected = read_as_lines("data/20.out.txt");
+
+    let plaintexts = matasano::crack_fixed_nonce_ctr_statistically(
+        ciphertexts
+    );
+
+    assert_eq!(
+        normalize(plaintexts, 27),
+        normalize(expected, 27)
+    );
+}