From caaf7016fcecd3a95df53e65150666d50bd0fbcf Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Thu, 18 Apr 2019 02:23:35 -0400 Subject: problem 34 --- Cargo.lock | 17 +++++++ Cargo.toml | 4 +- src/crack.rs | 156 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/dh.rs | 9 ++-- src/lib.rs | 3 ++ tests/set5.rs | 116 +++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 301 insertions(+), 4 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 754df7b..eab48c4 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -316,6 +316,19 @@ dependencies = [ "cfg-if 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)", ] +[[package]] +name = "crossbeam" +version = "0.7.1" +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)", + "crossbeam-channel 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)", + "crossbeam-deque 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)", + "crossbeam-epoch 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)", + "crossbeam-queue 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)", + "crossbeam-utils 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)", +] + [[package]] name = "crossbeam-channel" version = "0.3.8" @@ -760,6 +773,7 @@ dependencies = [ "actix 0.7.9 (registry+https://github.com/rust-lang/crates.io-index)", "actix-web 0.7.19 (registry+https://github.com/rust-lang/crates.io-index)", "base64 0.10.1 (registry+https://github.com/rust-lang/crates.io-index)", + "crossbeam 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)", "hex 0.3.2 (registry+https://github.com/rust-lang/crates.io-index)", "num-bigint 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)", "openssl 0.10.20 (registry+https://github.com/rust-lang/crates.io-index)", @@ -769,6 +783,7 @@ dependencies = [ "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)", + "serde_json 1.0.39 (registry+https://github.com/rust-lang/crates.io-index)", "time 0.1.42 (registry+https://github.com/rust-lang/crates.io-index)", ] @@ -922,6 +937,7 @@ dependencies = [ "num-integer 0.1.39 (registry+https://github.com/rust-lang/crates.io-index)", "num-traits 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)", "rand 0.5.6 (registry+https://github.com/rust-lang/crates.io-index)", + "serde 1.0.90 (registry+https://github.com/rust-lang/crates.io-index)", ] [[package]] @@ -2001,6 +2017,7 @@ dependencies = [ "checksum core-foundation-sys 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "716c271e8613ace48344f723b60b900a93150271e5be206212d052bbc0883efa" "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 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)" = "b14492071ca110999a20bf90e3833406d5d66bfd93b4e52ec9539025ff43fe0d" "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" diff --git a/Cargo.toml b/Cargo.toml index a15f9a6..576b872 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -29,8 +29,9 @@ path = "tests/set5.rs" actix = "0.7" actix-web = "0.7" base64 = "0.10" +crossbeam = "0.7" hex = "0.3" -num-bigint = { version = "0.2", features = ["rand"] } +num-bigint = { version = "0.2", features = ["rand", "serde"] } openssl = "0.10" rand = "0.6" rand_core = "0.4" @@ -38,4 +39,5 @@ rayon = "1.0" reqwest = "0.9" serde = "1.0" serde_derive = "1.0" +serde_json = "1.0" time = "0.1" diff --git a/src/crack.rs b/src/crack.rs index 49507f4..a4e7005 100644 --- a/src/crack.rs +++ b/src/crack.rs @@ -721,6 +721,162 @@ where key.to_vec() } +pub trait DiffieHellmanMessageExchanger { + fn a_channel( + &self, + ) -> ( + &crossbeam::channel::Sender>, + &crossbeam::channel::Receiver>, + ); + fn b_channel( + &self, + ) -> ( + &crossbeam::channel::Sender>, + &crossbeam::channel::Receiver>, + ); +} + +pub struct NullDiffieHellmanMessageExchanger { + a_sender: crossbeam::channel::Sender>, + a_recver: crossbeam::channel::Receiver>, + b_sender: crossbeam::channel::Sender>, + b_recver: crossbeam::channel::Receiver>, +} + +impl NullDiffieHellmanMessageExchanger { + pub fn new() -> NullDiffieHellmanMessageExchanger { + let (a_sender, b_recver) = crossbeam::channel::unbounded(); + let (b_sender, a_recver) = crossbeam::channel::unbounded(); + NullDiffieHellmanMessageExchanger { + a_sender, + a_recver, + b_sender, + b_recver, + } + } +} + +impl DiffieHellmanMessageExchanger for NullDiffieHellmanMessageExchanger { + fn a_channel( + &self, + ) -> ( + &crossbeam::channel::Sender>, + &crossbeam::channel::Receiver>, + ) { + (&self.a_sender, &self.a_recver) + } + + fn b_channel( + &self, + ) -> ( + &crossbeam::channel::Sender>, + &crossbeam::channel::Receiver>, + ) { + (&self.b_sender, &self.b_recver) + } +} + +pub struct ParameterInjectionDiffieHellmanMessageExchanger { + a_sender: crossbeam::channel::Sender>, + a_recver: crossbeam::channel::Receiver>, + b_sender: crossbeam::channel::Sender>, + b_recver: crossbeam::channel::Receiver>, + thread: std::thread::JoinHandle>, +} + +impl ParameterInjectionDiffieHellmanMessageExchanger { + pub fn new() -> ParameterInjectionDiffieHellmanMessageExchanger { + let (a_sender, ma_recver) = crossbeam::channel::unbounded(); + let (ma_sender, b_recver) = crossbeam::channel::unbounded(); + let (b_sender, mb_recver) = crossbeam::channel::unbounded(); + let (mb_sender, a_recver) = crossbeam::channel::unbounded(); + + let thread = std::thread::spawn(move || { + let a_bytes: Vec = ma_recver.recv().unwrap(); + let a: crate::dh::DHKeyPair = + serde_json::from_slice(&a_bytes).unwrap(); + let mut modified_a = a.clone(); + modified_a.pubkey = modified_a.p.clone(); + ma_sender + .send(serde_json::to_vec(&modified_a).unwrap()) + .unwrap(); + + let b_bytes: Vec = mb_recver.recv().unwrap(); + let b: crate::dh::DHKeyPair = + serde_json::from_slice(&b_bytes).unwrap(); + let mut modified_b = b.clone(); + modified_b.pubkey = modified_b.p.clone(); + mb_sender + .send(serde_json::to_vec(&modified_b).unwrap()) + .unwrap(); + + let a_ciphertext = ma_recver.recv().unwrap(); + ma_sender.send(a_ciphertext.clone()).unwrap(); + let a_iv = ma_recver.recv().unwrap(); + ma_sender.send(a_iv.clone()).unwrap(); + + let b_ciphertext = mb_recver.recv().unwrap(); + mb_sender.send(b_ciphertext.clone()).unwrap(); + let b_iv = mb_recver.recv().unwrap(); + mb_sender.send(b_iv.clone()).unwrap(); + + let s = num_bigint::BigUint::from(0 as u8); + let mut aes_key = crate::sha1::sha1(&s.to_bytes_le()).to_vec(); + aes_key.truncate(16); + + let a_plaintext = crate::aes::decrypt_aes_128_cbc( + &a_ciphertext, + &aes_key, + &a_iv, + ) + .unwrap(); + let b_plaintext = crate::aes::decrypt_aes_128_cbc( + &b_ciphertext, + &aes_key, + &b_iv, + ) + .unwrap(); + assert_eq!(a_plaintext, b_plaintext); + + a_plaintext + }); + + ParameterInjectionDiffieHellmanMessageExchanger { + a_sender, + a_recver, + b_sender, + b_recver, + thread, + } + } + + pub fn retrieve_plaintext(self) -> Vec { + self.thread.join().unwrap() + } +} + +impl DiffieHellmanMessageExchanger + for ParameterInjectionDiffieHellmanMessageExchanger +{ + fn a_channel( + &self, + ) -> ( + &crossbeam::channel::Sender>, + &crossbeam::channel::Receiver>, + ) { + (&self.a_sender, &self.a_recver) + } + + fn b_channel( + &self, + ) -> ( + &crossbeam::channel::Sender>, + &crossbeam::channel::Receiver>, + ) { + (&self.b_sender, &self.b_recver) + } +} + 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/dh.rs b/src/dh.rs index 24c2277..0db0bb2 100644 --- a/src/dh.rs +++ b/src/dh.rs @@ -1,10 +1,13 @@ use num_bigint::RandBigInt; +use serde_derive::{Deserialize, Serialize}; +#[derive(Debug, Clone, Serialize, Deserialize)] pub struct DHKeyPair { pub p: num_bigint::BigUint, pub g: num_bigint::BigUint, pub pubkey: num_bigint::BigUint, - privkey: num_bigint::BigUint, + #[serde(skip)] + privkey: Option, } impl DHKeyPair { @@ -15,7 +18,7 @@ impl DHKeyPair { p, g, pubkey, - privkey, + privkey: Some(privkey), } } @@ -23,6 +26,6 @@ impl DHKeyPair { &self, other_pubkey: &num_bigint::BigUint, ) -> num_bigint::BigUint { - other_pubkey.modpow(&self.privkey, &self.p) + other_pubkey.modpow(self.privkey.as_ref().unwrap(), &self.p) } } diff --git a/src/lib.rs b/src/lib.rs index 7c1dc82..8f98763 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -37,6 +37,9 @@ pub use crack::recover_16_bit_mt19937_key; pub use crack::recover_mersenne_twister_seed_from_time; pub use crack::recover_mt19937_key_from_time; pub use crack::BlockCipherMode; +pub use crack::DiffieHellmanMessageExchanger; +pub use crack::NullDiffieHellmanMessageExchanger; +pub use crack::ParameterInjectionDiffieHellmanMessageExchanger; pub use dh::DHKeyPair; pub use http::create_query_string; pub use http::parse_query_string; diff --git a/tests/set5.rs b/tests/set5.rs index d969212..594b420 100644 --- a/tests/set5.rs +++ b/tests/set5.rs @@ -1,3 +1,5 @@ +use rand::Rng; + #[test] fn problem_33() { let p_hex = "ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024\ @@ -19,3 +21,117 @@ fn problem_33() { assert_eq!(s1, s2); } + +#[test] +fn problem_34() { + let p_hex = "ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024\ + e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd\ + 3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec\ + 6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f\ + 24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361\ + c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552\ + bb9ed529077096966d670c354e4abc9804f1746c08ca237327fff\ + fffffffffffff"; + let p = num_bigint::BigUint::parse_bytes(p_hex.as_bytes(), 16).unwrap(); + let g = num_bigint::BigUint::from(2 as u8); + + let a = matasano::DHKeyPair::new(p.clone(), g.clone()); + let b = matasano::DHKeyPair::new(p.clone(), g.clone()); + + let plaintext = b"Summertime and the wind is blowing outside in \ + lower Chelsea and I don't know what I'm doing \ + in the city, the sun is always in my eyes"; + + let null_exchanger = matasano::NullDiffieHellmanMessageExchanger::new(); + run_dh_message_exchange(&null_exchanger, &a, &b, &plaintext[..]); + + let parameter_injection_exchanger = + matasano::ParameterInjectionDiffieHellmanMessageExchanger::new(); + run_dh_message_exchange( + ¶meter_injection_exchanger, + &a, + &b, + &plaintext[..], + ); + assert_eq!( + parameter_injection_exchanger.retrieve_plaintext(), + plaintext.to_vec(), + ); +} + +fn run_dh_message_exchange( + exchanger: &T, + a: &matasano::DHKeyPair, + b: &matasano::DHKeyPair, + plaintext: &[u8], +) where + T: matasano::DiffieHellmanMessageExchanger, +{ + crossbeam::thread::scope(|s| { + let (a_sender, a_recver) = exchanger.a_channel(); + let (b_sender, b_recver) = exchanger.b_channel(); + + let (key_compare_sender_a, key_compare_recver) = + crossbeam::channel::unbounded(); + let key_compare_sender_b = key_compare_sender_a.clone(); + + let a_runner = s.spawn(move |_| { + a_sender.send(serde_json::to_vec(a).unwrap()).unwrap(); + let b_bytes = a_recver.recv().unwrap(); + let b: matasano::DHKeyPair = + serde_json::from_slice(&b_bytes).unwrap(); + let s = a.key_exchange(&b.pubkey); + + let mut aes_key = matasano::sha1(&s.to_bytes_le()).to_vec(); + aes_key.truncate(16); + key_compare_sender_a.send(aes_key.clone()).unwrap(); + let mut iv = [0; 16]; + rand::thread_rng().fill(&mut iv); + + let ciphertext = + matasano::encrypt_aes_128_cbc(plaintext, &aes_key, &iv); + a_sender.send(ciphertext.clone()).unwrap(); + a_sender.send(iv.to_vec()).unwrap(); + let b_ciphertext = a_recver.recv().unwrap(); + let b_iv = a_recver.recv().unwrap(); + let b_plaintext = + matasano::decrypt_aes_128_cbc(&b_ciphertext, &aes_key, &b_iv) + .unwrap(); + + assert_eq!(&plaintext[..], b_plaintext.as_slice()); + assert_ne!(&iv[..], b_iv.as_slice()); + assert_ne!(ciphertext, b_ciphertext); + }); + let b_runner = s.spawn(move |_| { + b_sender.send(serde_json::to_vec(b).unwrap()).unwrap(); + let a_bytes = b_recver.recv().unwrap(); + let a: matasano::DHKeyPair = + serde_json::from_slice(&a_bytes).unwrap(); + let s = b.key_exchange(&a.pubkey); + + let mut aes_key = matasano::sha1(&s.to_bytes_le()).to_vec(); + aes_key.truncate(16); + key_compare_sender_b.send(aes_key.clone()).unwrap(); + let mut iv = [0; 16]; + rand::thread_rng().fill(&mut iv); + + let a_ciphertext = b_recver.recv().unwrap(); + let a_iv = b_recver.recv().unwrap(); + let a_plaintext = + matasano::decrypt_aes_128_cbc(&a_ciphertext, &aes_key, &a_iv) + .unwrap(); + let ciphertext = + matasano::encrypt_aes_128_cbc(&a_plaintext, &aes_key, &iv); + b_sender.send(ciphertext.clone()).unwrap(); + b_sender.send(iv.to_vec()).unwrap(); + }); + + let key1 = key_compare_recver.recv().unwrap(); + let key2 = key_compare_recver.recv().unwrap(); + assert_eq!(key1, key2); + + a_runner.join().unwrap(); + b_runner.join().unwrap(); + }) + .unwrap(); +} -- cgit v1.2.3