summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJesse Luehrs <doy@tozt.net>2019-04-15 11:00:26 -0400
committerJesse Luehrs <doy@tozt.net>2019-04-15 11:02:57 -0400
commita956a579def8fd4d618a0b1a1a9c206b22f2d1b1 (patch)
tree1dc5655f75e54c66491c701827cf25c774123871
parentae2d0f82a6ec62deb1751696dce51fad0f028e0f (diff)
downloadmatasano-a956a579def8fd4d618a0b1a1a9c206b22f2d1b1.tar.gz
matasano-a956a579def8fd4d618a0b1a1a9c206b22f2d1b1.zip
problem 32
-rw-r--r--Cargo.lock66
-rw-r--r--Cargo.toml1
-rw-r--r--src/crack.rs118
-rw-r--r--src/lib.rs3
-rw-r--r--tests/set4.rs39
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"
@@ -325,6 +327,15 @@ dependencies = [
[[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"
source = "registry+https://github.com/rust-lang/crates.io-index"
dependencies = [
@@ -334,6 +345,20 @@ dependencies = [
[[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"
source = "registry+https://github.com/rust-lang/crates.io-index"
dependencies = [
@@ -355,6 +380,14 @@ dependencies = [
[[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"
source = "registry+https://github.com/rust-lang/crates.io-index"
dependencies = [
@@ -368,6 +401,11 @@ 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"
source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -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)",
@@ -1128,6 +1167,27 @@ dependencies = [
]
[[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"
source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -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<u8> {
@@ -605,6 +606,121 @@ pub fn crack_hmac_timing(
unreachable!()
}
+fn crack_hmac_timing_advanced_rec<F>(
+ 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(&params)
+ );
+
+ 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<F>(file: &str, request: F) -> Vec<u8>
+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();
+}