From 72e8d6fdd8644381ee82dbcbaab208a2547c52ce Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Sat, 4 Apr 2015 02:10:29 -0400 Subject: problem 20 i think this is as far as possible, anyway --- data/20.out.txt | 40 ++++++++++++++++++++++++++++++++++++++++ data/20.txt | 40 ++++++++++++++++++++++++++++++++++++++++ src/crack.rs | 49 +++++++++++++++++++++++++++++++++++++++++++++++++ src/lib.rs | 1 + tests/lib.rs | 36 ++++++++++++++++++++++++++++++++++++ 5 files changed, 166 insertions(+) create mode 100644 data/20.out.txt create mode 100644 data/20.txt 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 (iv: &[u8], ciphertext: &[u8], f: &F) -> Vec< return unpad_pkcs7(&plaintext[..]).unwrap().to_vec(); } +pub fn crack_fixed_nonce_ctr_statistically (input: Vec>) -> Vec> { + 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 = 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> { .collect(); } +fn read_as_lines (filename: &str) -> Vec> { + 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 { 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>, len: usize) -> Vec> { + 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) + ); +} -- cgit v1.2.3-54-g00ecf