This one turned out to be haunting for me. I started it and had so many more priority things which postponed it (no jokes - start it a year ago). And like most of the things which didn't receive proper treatment I can't say it's done well. Though it's better to put the dot in the story of this one.
As usual I even posting it because I didn't really seen the solution in Rust when I was looking for it. Because it would be cool if someone would show where I did a mistake (is it ChaCha, or padding, or DEFLATE?). And there's a lot of comments/snippets to track how I was thinking during the time I've spent on this one. (The code itself in the end of the text.)
I somehow omitted CTR part and started right from CBC.
There's number of good descriptions of the solution out there. I particularly liked writeup; also really good and helpful are slides from CRIME authors.
I've made all the wrong moves described in the writeup. And I stopped finding 20 strings (including the solution), which is the reason of having that 'gestalt' and some following scattered notes on possible reasons of that.
I guess it's possible to find sweet-spot of CBC and DEFLATE boundaries to get the single result, but given how many requests we did send (and also would generate while searching for the boundary) it looks to me that 20 cookies to try do counts as solution result. (Tbh, this could be said even about 110 results acquired straight-forwardly.)
Maybe results are not that clean as instead of "canonical" for the CRIME zlib here is used miniz_oxide crate, which should be "close enough"/compatible with zlib (as indicates provision of the relevant method), but can differ in whatever details. Frankly, I have no side quests here concerned with compression, so if somebody are interested that much in this aspect it will be cute to read your findings on this!
I'm not sure how ChaCha20Poly1305 play its role in this exercise, AFAIR all write-ups I came across were using something "simpler"/older, and I just wanted to use something "modern"/current. On the other hand the suite already was around and kind of established when the exercise was
released. It's a more relevant topic to me than compression; though chances that it would be me who'd dig this piece are diminishing.
Actual question that I still don't find enough motivation to research is why did all my attempts to find that compression (block) border that is described in references but already having small set of possible solution failed. I feel like translating Python solution, or detailed development of this solution should help, but other things demands this time. So it's a bit, which could be discussed here and returned to once if ever.
use rayon::prelude::*;
mod oracle {
use chacha20poly1305::{ChaCha20Poly1305, aead::{OsRng, KeyInit, Aead, AeadCore}};
use http_serde;
use serde::Serialize;
use http::{Request, Method, HeaderMap/* , version::Http */};
#[derive(Serialize, Debug)]
struct RequestSer {
#[serde(with = "http_serde::method")]
method: Method,
// #[serde(with = "http_serde::uri")]
// uri: Uri,
#[serde(with = "http_serde::header_map")]
headers: HeaderMap,
body: String,
// version: Version
}
// pub struct Oracle {key: Key<ChaCha20Poly1305>}
// impl Oracle {
// pub fn new() -> Oracle {Oracle { key: ChaCha20Poly1305::generate_key(&mut OsRng) }}
pub fn oracle(/* &self, */ p: String) -> usize {
// dbg!(request_format(p.clone()));
let (req_builded_parts, req_builded_body) =
request_format(p).into_parts();
// dbg!(&req_builded_parts);
let req_restiched = RequestSer {
method: (req_builded_parts.method), headers: (req_builded_parts.headers),
body: req_builded_body,
};
// dbg!(&req_restiched);
// let req_serialized: Vec<u8> = req_restiched.serialize(serde_json::Serializer::new(writer));
let req_serialized: Vec<u8> = bincode::serialize(
&req_restiched
).unwrap();
// let compressed = miniz_oxide::deflate::compress_to_vec(
// [req_serialized, Vec::from(p)].concat().as_slice(), 0
// );
let compressed = miniz_oxide::deflate::compress_to_vec(
// let compressed = miniz_oxide::deflate::compress_to_vec_zlib(
req_serialized.as_slice(), 6
);
// dbg!(String::from_utf8_lossy(&compressed));
let cipher = ChaCha20Poly1305::new(
&ChaCha20Poly1305::generate_key(&mut OsRng)
);
let nonce = ChaCha20Poly1305::generate_nonce(&mut OsRng);
let ciphertext = cipher.encrypt(&nonce, compressed.as_ref()).unwrap();
// println!("{ciphertext:?}");
// println!("{:?}", chrono::offset::Local::now());
return ciphertext.len()
}
fn request_format(p: String) -> Request<String> {
Request::builder().method("POST")
.header("Host", "hapless.com").header(
"Cookie", "sessionid=TmV2ZXIgcmV2ZWFsIHRoZSBXdS1UYW5nIFNlY3JldCE="
).header("Content-Length", p.len()).body(p).unwrap()
}
}
fn main() {
/* holds growing strings of best compressed guesses, should converge to the one
that is in the header */
let mut guesses = Vec::new();
guesses.push(/* ( */String::from("")/* , 0) */);
/* loop over each symbol of Base64; suppose we know that _secure cookie_ is
32 bytes represented in Base64 by looking into our own account in the same system;
32 * 8 = 256 div 6 = 42 pad to mod4=0 = 44; 1-based for progress printing */
// (1..=44).into_par_iter().for_each(|pos| {});
for pos in 1..=44 {
/* holds iterated symbols that passed window check
with oracle for current position */
// let mut guesses_new = Vec::new();
/* it turned out to be awful padding for this challenge
let padding = (0..(44-pos)).map(|_| "_").collect::<String>(); */
// proper way would be to use a _base64_ crate
let symbols = ('0'..='9').chain('A'..='Z').chain('a'..='z').chain('='..='='); // sorry for dirty hack in the end, ofc there's more graceful way to make an iterator from a `char`
/* we should try each of the substrings
constructed previously with each of new B64 chars */
let mut guesses_n: Vec<(String, usize)> = guesses.par_iter().map(|guess| {
/* let mut lengs: Vec<(String, usize)> = */ (symbols.clone()).into_iter().filter_map(|ch| {
if !ch.is_alphanumeric() && pos < 41 {None}
else {
let t/* _1 */ = String::from("sessionid=".to_owned() + guess.as_str() + ch.to_string().as_str() /* + padding.as_str() */);
// let t_2 = String::from(
// /* padding.clone() + */ guess.to_owned() + ch.to_string().as_str() + "sessionid=" /* + padding.as_str() */
// );
let t_l = oracle::oracle(t);
// println!("{t_1_l}|{t_2_l}|{guess}|{ch}");
// if t_l < t_2_l {Some(guess.to_owned() + &ch.to_string())}
Some((guess.to_owned() + &ch.to_string(), t_l))
}
}).collect::<Vec<(String, usize)>>()
// let shortest = lengs.iter().map(|x| x.1).min().expect("`lengs` isn't empty");
// lengs.retain(|x| x.1 == shortest);
// lengs.into_iter().map(|x| guess.to_owned() + &x.0.to_string()).collect::<Vec<String>>()
}).flatten().collect()/* .filter(|x| !x.is_empty()) */;
let shortest = guesses_n.iter().map(|x| x.1).min().expect("`lengs` isn't empty");
// dbg!(&shortest);
guesses_n.retain(|x| x.1 == shortest);
guesses = guesses_n.into_iter().map(|x| x.0).collect();
// for guess in &guesses {
// // for ch in ('a'..='z').chain('A'..='Z').chain('0'..='9') {
// for ch in '0'..='z' {
// // skip non-alphanumerics before padding `pos`itions
// if (pos < 41 && ch.is_alphanumeric()) || pos > 41 {
// let t_1 = String::from("sessionid=".to_owned() + guess.as_str() + ch.to_string().as_str() /* + padding.as_str() */);
// let t_2 = String::from(
// /* padding.clone() + */ guess.to_owned() + ch.to_string().as_str() + "sessionid=" /* + padding.as_str() */
// );
// let t_1_l = oracle_the.cast(t_1);
// let t_2_l = oracle_the.cast(t_2);
// // println!("{t_1_l}|{t_2_l}|{guess}|{ch}");
// if t_1_l < t_2_l {guesses_new.push(guess.to_owned() + ch.to_string().as_str());}
// }
// }
// }
dbg!(pos);
dbg!(guesses.len());
// assert!(guesses_new.len() > 0);
// assert!(guesses_new[0].len() == pos/* , "{l}" */);
// yank previous guesses set with extended 1 `pos`ition further
// guesses = guesses_new;
}
println!("{guesses:?}");
let padding = "!@#$%^&*()-`~[]}{";
// 0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz
let guesses = guesses.par_iter().map(|guess| {
let mut padded = Vec::with_capacity(4);
for i in 1..=4 {
let guess_padded = padding[0..i].to_owned() + &guess;
// println!("{:?}", &padding[0..i]);
padded.push((guess_padded.clone(), oracle::oracle(guess_padded)))
}
let shortest = padded.iter().map(|x| x.1).min();
let longest = padded.iter().map(|x| x.1).max();
if shortest != longest {dbg!(&padded);}
(guess.to_owned(), shortest.unwrap())
});
let minimum = guesses.clone().min_by_key(|x| x.1).unwrap().1;
let guesses: Vec<(String, usize)> = guesses.filter(|x| x.1 == minimum).collect();
dbg!(&guesses.len(), guesses);
}
// "abcdefghjjklmnopASBCDEFJIERF1234567890".chars()
// @skeletizzle
// alphanumerics represented as what
// SKaunov — Today at 9:55 PM
// Yep, one symbol, which I append to a String. It could be a char, I guess.
// ari.s — Today at 9:56 PM
// ('A'..'z').into_iter().for_each(|c| println!("{c}"));
// [9:56 PM]
// oops nvm , I didnt think about nums
// skeletizzle — Today at 9:56 PM
// 'a'..='z'.chain('A'..='Z').chain('0'..='9)
// ari.s — Today at 9:58 PM
// Or if you're weird: ('0'..='z').into_iter().filter(|c| c.is_alphanumeric()) (edited)
// https://github.com/wangray/matasano-crypto/blob/master/set7/set7.py#L97
fn get_padding(text: &str) -> String {
let padding_chars = "!@#$%^&*()-`~[]}{";
let base_len = oracle::oracle(text.to_owned());
for i in 0..17 {
let try_the = text.to_owned() + &padding_chars[..=i];
if oracle::oracle(try_the.clone()) > base_len {
return try_the;
}
}
panic!("we didn't found edge of the block =((")
}
Top comments (0)