From a956a579def8fd4d618a0b1a1a9c206b22f2d1b1 Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Mon, 15 Apr 2019 11:00:26 -0400 Subject: problem 32 --- Cargo.lock | 66 ++++++++++++++++++++++++++++++++ Cargo.toml | 1 + src/crack.rs | 118 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++- src/lib.rs | 3 +- tests/set4.rs | 39 ++++++++++++++++++- 5 files changed, 224 insertions(+), 3 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 7fe5b8e..9d96c98 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -1,3 +1,5 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. [[package]] name = "MacTypes-sys" version = "2.1.0" @@ -323,6 +325,15 @@ dependencies = [ "smallvec 0.6.9 (registry+https://github.com/rust-lang/crates.io-index)", ] +[[package]] +name = "crossbeam-deque" +version = "0.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "crossbeam-epoch 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)", + "crossbeam-utils 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)", +] + [[package]] name = "crossbeam-deque" version = "0.7.1" @@ -332,6 +343,20 @@ dependencies = [ "crossbeam-utils 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)", ] +[[package]] +name = "crossbeam-epoch" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "arrayvec 0.4.10 (registry+https://github.com/rust-lang/crates.io-index)", + "cfg-if 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)", + "crossbeam-utils 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)", + "lazy_static 1.3.0 (registry+https://github.com/rust-lang/crates.io-index)", + "memoffset 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)", + "nodrop 0.1.13 (registry+https://github.com/rust-lang/crates.io-index)", + "scopeguard 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)", +] + [[package]] name = "crossbeam-epoch" version = "0.7.1" @@ -353,6 +378,14 @@ dependencies = [ "crossbeam-utils 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)", ] +[[package]] +name = "crossbeam-utils" +version = "0.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "cfg-if 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)", +] + [[package]] name = "crossbeam-utils" version = "0.6.5" @@ -367,6 +400,11 @@ name = "dtoa" version = "0.4.3" source = "registry+https://github.com/rust-lang/crates.io-index" +[[package]] +name = "either" +version = "1.5.2" +source = "registry+https://github.com/rust-lang/crates.io-index" + [[package]] name = "encoding" version = "0.2.33" @@ -726,6 +764,7 @@ dependencies = [ "openssl 0.10.20 (registry+https://github.com/rust-lang/crates.io-index)", "rand 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)", "rand_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "rayon 1.0.3 (registry+https://github.com/rust-lang/crates.io-index)", "reqwest 0.9.14 (registry+https://github.com/rust-lang/crates.io-index)", "serde 1.0.90 (registry+https://github.com/rust-lang/crates.io-index)", "serde_derive 1.0.90 (registry+https://github.com/rust-lang/crates.io-index)", @@ -1127,6 +1166,27 @@ dependencies = [ "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)", ] +[[package]] +name = "rayon" +version = "1.0.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "crossbeam-deque 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)", + "either 1.5.2 (registry+https://github.com/rust-lang/crates.io-index)", + "rayon-core 1.4.1 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rayon-core" +version = "1.4.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "crossbeam-deque 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)", + "lazy_static 1.3.0 (registry+https://github.com/rust-lang/crates.io-index)", + "libc 0.2.51 (registry+https://github.com/rust-lang/crates.io-index)", + "num_cpus 1.10.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + [[package]] name = "rdrand" version = "0.4.0" @@ -1918,11 +1978,15 @@ dependencies = [ "checksum crc 1.8.1 (registry+https://github.com/rust-lang/crates.io-index)" = "d663548de7f5cca343f1e0a48d14dcfb0e9eb4e079ec58883b7251539fa10aeb" "checksum crc32fast 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ba125de2af0df55319f41944744ad91c71113bf74a4646efff39afe1f6842db1" "checksum crossbeam-channel 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)" = "0f0ed1a4de2235cabda8558ff5840bffb97fcb64c97827f354a451307df5f72b" +"checksum crossbeam-deque 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "f739f8c5363aca78cfb059edf753d8f0d36908c348f3d8d1503f03d8b75d9cf3" "checksum crossbeam-deque 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)" = "b18cd2e169ad86297e6bc0ad9aa679aee9daa4f19e8163860faf7c164e4f5a71" +"checksum crossbeam-epoch 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "927121f5407de9956180ff5e936fe3cf4324279280001cd56b669d28ee7e9150" "checksum crossbeam-epoch 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)" = "04c9e3102cc2d69cd681412141b390abd55a362afc1540965dad0ad4d34280b4" "checksum crossbeam-queue 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7c979cd6cfe72335896575c6b5688da489e420d36a27a0b9eb0c73db574b4a4b" +"checksum crossbeam-utils 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "2760899e32a1d58d5abb31129f8fae5de75220bc2176e77ff7c627ae45c918d9" "checksum crossbeam-utils 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)" = "f8306fcef4a7b563b76b7dd949ca48f52bc1141aa067d2ea09565f3e2652aa5c" "checksum dtoa 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)" = "6d301140eb411af13d3115f9a562c85cc6b541ade9dfa314132244aaee7489dd" +"checksum either 1.5.2 (registry+https://github.com/rust-lang/crates.io-index)" = "5527cfe0d098f36e3f8839852688e63c8fff1c90b2b405aef730615f9a7bcf7b" "checksum encoding 0.2.33 (registry+https://github.com/rust-lang/crates.io-index)" = "6b0d943856b990d12d3b55b359144ff341533e516d94098b1d3fc1ac666d36ec" "checksum encoding-index-japanese 1.20141219.5 (registry+https://github.com/rust-lang/crates.io-index)" = "04e8b2ff42e9a05335dbf8b5c6f7567e5591d0d916ccef4e0b1710d32a0d0c91" "checksum encoding-index-korean 1.20141219.5 (registry+https://github.com/rust-lang/crates.io-index)" = "4dc33fb8e6bcba213fe2f14275f0963fd16f0a02c878e3095ecfdf5bee529d81" @@ -2008,6 +2072,8 @@ dependencies = [ "checksum rand_os 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "7b75f676a1e053fc562eafbb47838d67c84801e38fc1ba459e8f180deabd5071" "checksum rand_pcg 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "abf9b09b01790cfe0364f52bf32995ea3c39f4d2dd011eac241d2914146d0b44" "checksum rand_xorshift 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cbf7e9e623549b0e21f6e97cf8ecf247c1a8fd2e8a992ae265314300b2455d5c" +"checksum rayon 1.0.3 (registry+https://github.com/rust-lang/crates.io-index)" = "373814f27745b2686b350dd261bfd24576a6fb0e2c5919b3a2b6005f820b0473" +"checksum rayon-core 1.4.1 (registry+https://github.com/rust-lang/crates.io-index)" = "b055d1e92aba6877574d8fe604a63c8b5df60f60e5982bf7ccbb1338ea527356" "checksum rdrand 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "678054eb77286b51581ba43620cc911abf02758c91f93f479767aed0f90458b2" "checksum redox_syscall 0.1.54 (registry+https://github.com/rust-lang/crates.io-index)" = "12229c14a0f65c4f1cb046a3b52047cdd9da1f4b30f8a39c5063c8bae515e252" "checksum regex 1.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "559008764a17de49a3146b234641644ed37d118d1ef641a0bb573d146edc6ce0" diff --git a/Cargo.toml b/Cargo.toml index 2e5e276..84f1504 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -29,6 +29,7 @@ hex = "0.3" openssl = "0.10" rand = "0.6" rand_core = "0.4" +rayon = "1.0" reqwest = "0.9" serde = "1.0" serde_derive = "1.0" diff --git a/src/crack.rs b/src/crack.rs index 388dde5..49507f4 100644 --- a/src/crack.rs +++ b/src/crack.rs @@ -1,4 +1,5 @@ use rand::Rng; +use rayon::prelude::*; use std::borrow::ToOwned; use std::collections::{HashMap, HashSet}; @@ -578,7 +579,7 @@ pub fn crack_md4_mac_length_extension( .collect() } -pub fn crack_hmac_timing( +pub fn crack_hmac_timing_basic( _data: &str, request: impl Fn(&str) -> bool, ) -> Vec { @@ -605,6 +606,121 @@ pub fn crack_hmac_timing( unreachable!() } +fn crack_hmac_timing_advanced_rec( + file: &str, + request: &F, + key: [u8; 20], + idx: usize, + timing_cutoff: u128, +) -> Option<(Vec<(u8, u128)>, [u8; 20])> +where + F: Sync + Send + Fn(&str) -> bool, +{ + let get_timing_for = |i: u8| { + let mut key = key.clone(); + key[idx] = i; + let guess = hex::encode(key); + + let mut params = std::collections::HashMap::new(); + params.insert("file", file.to_string()); + params.insert("signature", guess.to_string()); + let uri = format!( + "{}{}", + "http://localhost:9000/?", + crate::http::create_query_string(¶ms) + ); + + let start = std::time::Instant::now(); + let success = request(&uri); + (success, start.elapsed().as_micros()) + }; + + let initial_timings: Vec<_> = (0..256) + .into_par_iter() + .map(|i| (i as u8, get_timing_for(i as u8))) + .collect(); + + for (i, (success, _)) in initial_timings.iter() { + if *success { + let mut key = key.clone(); + key[idx] = *i; + return Some((vec![], key)); + } + } + + let (_, (_, min_dur)) = initial_timings + .iter() + .cloned() + .min_by_key(|(_, (_, dur))| *dur) + .unwrap(); + + let mut timings: Vec<_> = (0..256) + .into_par_iter() + .map(|i| { + let (_, (_, mut dur)) = initial_timings[i as usize]; + let mut count = 0; + while dur > min_dur + 2500 && count < 100 { + let res = get_timing_for(i as u8); + dur = res.1; + count += 1; + } + (i as u8, dur) + }) + .collect(); + + timings.par_sort_by_key(|(_, dur)| *dur); + + // eprintln!( + // "got timings for byte {} ranging from {} to {} (expected: >{})", + // idx, timings[0].1, timings[255].1, timing_cutoff + // ); + + if timings[0].1 < timing_cutoff { + return None; + } + + // if idx > 0 { + // eprintln!("byte {} confirmed to be {}", idx - 1, key[idx - 1]); + // } + + for (i, _dur) in timings.iter().rev() { + let mut new_key = key.clone(); + new_key[idx] = *i; + // eprintln!("guessing that byte {} is {} (dur {})", idx, i, _dur); + let rec = crack_hmac_timing_advanced_rec( + file, + request, + new_key, + idx + 1, + timings[0].1 + 2500, + ); + if rec.is_some() { + return rec; + } + } + + unreachable!() +} + +pub fn crack_hmac_timing_advanced(file: &str, request: F) -> Vec +where + F: Sync + Send + Fn(&str) -> bool, +{ + let pool = rayon::ThreadPoolBuilder::new() + .num_threads(3) + .build() + .unwrap(); + + let key = pool.install(|| { + let (_, key) = + crack_hmac_timing_advanced_rec(file, &request, [0; 20], 0, 0) + .unwrap(); + key + }); + + key.to_vec() +} + 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 69bea3e..ae69401 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -20,7 +20,8 @@ pub use crack::crack_cbc_iv_key; pub use crack::crack_cbc_padding_oracle; pub use crack::crack_ctr_bitflipping; pub use crack::crack_fixed_nonce_ctr_statistically; -pub use crack::crack_hmac_timing; +pub use crack::crack_hmac_timing_advanced; +pub use crack::crack_hmac_timing_basic; pub use crack::crack_md4_mac_length_extension; pub use crack::crack_padded_aes_128_ecb; pub use crack::crack_padded_aes_128_ecb_with_prefix; diff --git a/tests/set4.rs b/tests/set4.rs index 89581e2..3f927d3 100644 --- a/tests/set4.rs +++ b/tests/set4.rs @@ -213,7 +213,7 @@ fn problem_31() { let key = hex::decode(ready_r.recv().unwrap()).unwrap(); let file = "filename.txt"; - let got = matasano::crack_hmac_timing(file, |guess| { + let got = matasano::crack_hmac_timing_basic(file, |guess| { let mut params = std::collections::HashMap::new(); params.insert("file", file.to_string()); params.insert("signature", guess.to_string()); @@ -231,3 +231,40 @@ fn problem_31() { kill_w.send(()).unwrap(); } + +#[test] +#[ignore] +fn problem_32() { + let exe_path = std::env::current_exe().unwrap(); + let exe_dir = exe_path.parent().unwrap().parent().unwrap(); + let server_bin = exe_dir.join("timing_attack"); + + let (ready_w, ready_r) = std::sync::mpsc::channel(); + let (kill_w, kill_r) = std::sync::mpsc::channel(); + std::thread::spawn(move || { + let mut child = std::process::Command::new(server_bin) + .args(&["5"]) + .stdout(std::process::Stdio::piped()) + .spawn() + .unwrap(); + let mut key = [0u8; 32]; + let _ = child.stdout.as_mut().unwrap().read_exact(&mut key); + ready_w.send(key).unwrap(); + + let _ = kill_r.recv(); + child.kill().unwrap(); + child.wait().unwrap(); + }); + + let key = hex::decode(ready_r.recv().unwrap()).unwrap(); + + let file = "filename.txt"; + let got = matasano::crack_hmac_timing_advanced(file, |uri| { + let res = reqwest::get(uri).unwrap(); + res.status().is_success() + }); + let expected = matasano::sha1_hmac(file.as_bytes(), &key); + assert_eq!(got, expected); + + kill_w.send(()).unwrap(); +} -- cgit v1.2.3