Forem: skaunov

Cryptopals-57 solution

skaunov — Fri, 13 Feb 2026 14:59:47 +0000

Cryptopals is a least priority thing I'm enjoying somewhat consistently; hence it has crazy lags. I started #8 in 2024 and here it is; every time I opened the file with the code it was like someone you knew long ago and now hardly recognize. But that's quite an exercise (and maybe a skill) too. That explains why the code sometimes looks funny even to myself; but if I take the time to groom it further I will just never finish as I progress as a developer more often than I open the file. Another explanation needed is about some mistakes preserved in the comments: primarily this code is for me to reflect when I stumble onto it later, and those help me to follow & recollect the things. It doesn't look like I will finish the set, but #57 is here.

use std::collections::HashMap;

use num_bigint::{BigUint, RandBigInt};
use num_traits::{Num, One, Zero};
use rand::{
    rngs::OsRng, 
    seq::SliceRandom
};

const G: &'static str = "4565356397095740655436854503483826832136106141639563487732438195343690437606117828318042418238184896212352329118608100083187535033402010599512641674644143";
const Q: &'static str = "236234353446506858198510045061214171961";

fn biguint_from_str_decimal(s: &str) -> BigUint {
    BigUint::from_str_radix(s, 10).unwrap()
}

fn main() {
    let zero = BigUint::zero();
    let one = BigUint::one();

    let p = biguint_from_str_decimal("7199773997391911030609999317773941274322764333428698921736339643928346453700085358802973900485592910475480089726140708102474957429903531369589969318716771");
    println!("the number of bits `p` takes:");
    println!("{}", p.bits());
    let j = biguint_from_str_decimal("30477252323177606811760882179058908038824640750610513771646768011063128035873508507547741559514324673960576895059570");

    let g = biguint_from_str_decimal(G);
    let q = biguint_from_str_decimal(Q);
    println!("the number of bits `q` takes:");
    println!("{}", q.bits());

    assert!(&j * &q == &p - &one);

    /* 
    > You don't need to factor it all the way. Just find a bunch of factors
    smaller than, say, 2^16. There should be plenty. (Friendly tip: maybe
    avoid any repeated factors. They only complicate things.) */
    /* During debugging I took the advice on the small 
    factors. Until then I went with `HashMap`, and created 
    it `from([2])` (which wasn't the bright idea from a few 
    angles). 
    The logic was that doesn't participate in other small 
    factors, so "let's just add it here".

    I wanted to go the complicated case to play with the 
    degree of each factor. But due to a mistake I had to 
    debug, I just checked that starting from $329$ all the 
    factors are degree $1$, and switched to `HashSet` 
    starting from that number to not change the code I've 
    already debugged. Not taking the suggested short-cut 
    should be an educatory refresher on CRT. 

    I didn't thought though that I brutely sieve here and 
    starting factoring from a number after the 
    tiny/repeating factors will introduce additional 
    factors (here it's one) which absorbs those repeating 
    and brings all the complications we were adviced to 
    avoid. So it's easier to sieve properly; 
    but then repeating factors are still dropped. */
    let mut factors: HashMap<usize, usize> = HashMap::new();

    let mut factoring = j.clone();
    /* obvious optimization is replace the range for 
    the primes; then drop `rayon` in */
    for m in 2..2usize.pow(16) {
        if &factoring % m == zero {
            *factors.entry(m).or_default() += 1;
            // with `HashSet` it was the following
            // let _new = factors.insert(m);
            // debug_assert!(_new);

            factoring /= m;
        }
    }
    let mut factors = factors.into_iter().filter_map(
        |(factor, degree)| 
        if degree == 1 {Some(factor)} else {None}
    ).collect::<Vec<_>>();
    println!("{} factors will be used:", factors.len());
    println!("{:?}", &factors);
    /* 
    > ...we can use these to recover Bob's secret key using
    the Pohlig-Hellman algorithm for discrete logarithms... */

    let bob_key_priv = OsRng::default()
    /* Actually it doesn't make sense to care about drawing 
    the zero since it's plainly improbable, but this is the 
    exclusion thing I still do; in the end of the day let's 
    hope the secret is a non-zero type. Earlier challenges 
    show that a correct way is to generate everything and 
    then check zero (in fact all trivial/special cases) 
    specifically. */
    // .gen_biguint_below(&p)
    .gen_biguint_range(
        /* Continuing the previous note, this exclusion 
        always was mostly a joke or over caution; it was 
        cute to see I did this more than an year ago, and 
        just recently asked in a randomness dedicated group 
        if this ever makes any sense: they just reassured it 
        does not! */
        // &BigUint::from(2u8).pow(80), 
        &one,
        /* To me this is an interesting part of the 
        exercise! It designed so that the key is taken from 
        `q` which makes sense if think about it. But the 
        exercise is an opportunity to try what would happen 
        if we draw from `p`. Usually it's not that 
        interesting since an EC group would have a handful
        of small order subgroups which without cofactor 
        clearance will be cycling pretty quick. But here we 
        have 512-bit field with somewhat sizeable factors. 
        #drawFromP */
        // &p
        &q
    );
    /* I guess over `q` I could try an arithmetic 
    MAC algorithm in this exercise. :notsure: */
    let _bob_key_pub = g.modpow(
        &bob_key_priv, 
        /* At some point I got confused in experimentaion. 
        #modulusConfusion #drawFromP */
        // &q
        &p
    );
    // assert_eq!(_bob_key_pub, g.modpow(
    //     &bob_key_priv, 
    //     &q
    // ));

    let order = &p - &one;
    let k_guess = |r: usize| -> (BigUint, BigUint, usize) {
        /* 
        > 1. Take one of the small factors j. Call it r. We want to find an
        element h of order r. ... */
        assert_eq!(&order % r, zero);
        let r_cofactor = (&order)/r;
        assert_eq!(&r_cofactor % &q, zero);
        let h = loop {
            /* it's like cofactor clearing but for 
            a tiny factor instead of a proper */
            let t = OsRng::default().gen_biguint_range(
                &one, &p
            ).modpow(&r_cofactor, &p);
            if 
                // dbg!(
                    &t
                // ) 
                > &one {break t;} 
        };
        assert!(
            &h.modpow(&BigUint::from(r), &p) == &one, 
            "we must be in a subgroup `r`"
        );

        /* 
        > 2. You're Eve. Send Bob h as your public key. Note that h is not a
        valid public key! There is no x such that h = g^x mod p. ... */
        let eve_key_pub = &h;

        /* 
        > 3. Bob will compute:
        > 
        >    K := h^x mod p
        > 
        > Where x is his secret key and K is the output shared secret. Bob
        then sends back (m, t), with:
        > 
        >    m := "crazy flamboyant for the rap enjoyment"
        t := MAC(K, m) */
        let x = &bob_key_priv;
        let k = eve_key_pub.modpow(
            x, 
            &p
            // #modulusConfusion
            // &q
        );
        let t = mac::the(&k);

        /* 
        >  4. ...
        > 
        > ...there are only r possible values
    of K that Bob could have generated. We can recover K by doing a
    brute-force search over these values until t = MAC(K, m). */
        let mut k_guessed = h.clone(); // could fail on additive identity, but we have kind of protection while drawing (instead of with types)
        for _ in 0..r { // subgroup size should be $r-1$
            if &t == &mac::the(&k_guessed) {
                break;
            }
            k_guessed = (&k_guessed * &h) 
                // #modulusConfusion
                // % &q;
                % &p;
        }
        // let k_guessed = (0..r).into_par_iter().position_any(|guess| {
        //     &mac(&h.modpow(&guess.into(), &p)) == &t
        // }).unwrap();
        assert_eq!(
            t, mac::the(&k_guessed), 
            "step \"4.\" encountered a problem with `r`:{}, `x`:{}, `t`:{:?}, `x % r`:{}", r, x, t, (x % r)
        );

        // let x_mod_r = (0..r).into_par_iter().position_any(
        //     |i| &k_guessed == &h.modpow(&i.try_into().unwrap(), //&r.into())
        // ).unwrap();
        /* degree of $h$ when it becomes equal to K */
        let x_mod_r = {
            let mut h_runner = one.clone();
            let mut x_runner = 0;
            while &k_guessed != &h_runner {
                x_runner += 1;
                h_runner = (h_runner * &h) 
                    // #modulusConfusion
                    // % &q;
                    % &p;
            };
            x_runner
        };
        println!("{r} was chosen as another factor");
        // dbg!(x_mod_r);
        // dbg!(&bob_key_priv % r);
        assert_eq!(
            BigUint::from(x_mod_r), 
            &bob_key_priv % r
        );

        (k_guessed.into(), r_cofactor, x_mod_r)
    };

    /* 
    > 5. ... */
    // let mut factors = factors.into_iter();
    factors.shuffle(&mut OsRng);

    let mut accumulated = one.clone();
    let mut kk = Vec::new();
    while &accumulated < &q {
        let r = factors.pop().unwrap();
        kk.push((r, k_guess(r)));
        accumulated *= r;
    }

    // > ...reassemble Bob's secret key using the Chinese Remainder Theorem.
    let product_factors_chosen = BigUint::from(
        kk.iter().map(|&(f, ..)| f).product::<usize>()
    );
    let bob_key_priv_guessed = dbg!(kk.into_iter().map(
        |(factor, (_, _cofactor, x_mod_factor))| {
            let cofactor = &product_factors_chosen / factor;
            // dbg!(
                x_mod_factor * &cofactor * cofactor.modinv(
                    &BigUint::from(factor)
                ).unwrap()
            // )
        }
    )
    // .reduce(<BigUint as core::ops::Add>::add)).unwrap()
    .sum::<BigUint>())
    % product_factors_chosen;
    // #drawFromP
    // let mut bob_key_priv_guessed = bob_key_priv_guessed % &p;
    // while dbg!(&bob_key_priv_guessed) >= &p {bob_key_priv_guessed *= bob_key_priv_guessed.clone();}

    debug_assert_eq!(bob_key_priv, &bob_key_priv % &q);
    // dbg!(dbg!(&bob_key_priv % &q) == dbg!(
    //     dbg![&bob_key_priv_guessed]
    //         // .modpow(&j, &p)
    //         % &q
    // ));

    println!("the Private key");
    println!("{}", bob_key_priv);

    // let variants_left = factors_cloned.into_iter().fold(p / q, |dived, factor| dived / factor);
    // dbg!(variants_left);

    assert!(bob_key_priv == bob_key_priv_guessed);
    println!("The private key have been guessed correctly.");

    // a tiny remnant I decided to keep of an experiment
    // let bob_key_pub = mac(&bob_key_priv);
    // if bob_key_pub == mac(&bob_key_priv_guessed) {println!("CORRECT");}
    // else {println!("guessing FAILED");}
}

/// I remember I wanted to try something I either won't as 
/// MAC is absolutely lateral here -- main point is just 
/// grind the value out of a small set of possible. But to 
/// play with 512-bit numbers and when I had a mistake in 
/// the core thing I settled here with the most boring 
/// variant. Still, again, this doesn't impact anything.
/// 
/// The options I considered for fun were quite different 
/// to see another approaches.
/// https://docs.rs/cmac/latest/cmac/struct.CmacCore.html
/// https://docs.rs/dbl/0.3.2/dbl/trait.Dbl.html
/// https://docs.rs/threefish/latest/threefish/struct.Threefish512.html
mod mac {
    use hmac::{digest::{
        consts::U32, generic_array::GenericArray
    }, Mac};

    pub fn the( 
        k: &num_bigint::BigUint,// m: &[u8]
    ) ->  GenericArray<u8, U32> /* BigUint */ { 
        // let k = k % &p;
        // let mut t = 
        //     <blake2::Blake2bMac::<blake2::digest::consts::U64> as blake2::digest::Mac>::new_from_slice(&k.to_bytes_le()).unwrap();
        // blake2::digest::Update::update(&mut t, m);
        // blake2::digest::Mac::finalize(t).into_bytes().to_vec()

        // g.modpow(k, &p)

        // let k = k % &q; // 128 bits
        // let k_bytes = &k.to_bytes_le();
        // let k_bytes = 
        //     [k_bytes.as_slice(), &[0].repeat(16 - k_bytes.len())].concat();
        // dbg!(k_bytes.len());
        let mut mac = hmac::Hmac::<sha2::Sha256>::
        new_from_slice(k.to_bytes_le().as_slice()).unwrap();
        mac.update(b"crazy flamboyant for the rap enjoyment");
        mac.finalize().into_bytes()
    }
}

_$t$ out of $n$_ with `dcipher` and without

skaunov — Sun, 10 Aug 2025 10:57:03 +0000

Listeners of Threshold Cryptography Bootcamp were (t)asked to reflect on the first four sessions we got to this date. I guess the most of approaches to the task will be a (LLM-)conspect of the lectures, and I don't want to join this chorus since there's quite a number of threshold crypto guides and I can only produce a worse one. Instead let me think out loud on comparison of the threshold approach and naive multisig. I mean the nature of the lectures advertises the first one quite heavily and as a natural (for a cryptography engineer) skeptic push-back I was constantly tried to think how the things could be done (and often are done currently) without thresholds.

By multisig I mean just counting the signatures on something which obviously can solve the very same problem: to require $t$ out of $n$ sign-offs before going. My current conclusion (probably wrong as I'm just get the feeling of the things) is that thresholds are really superior in the two aspects:

they're much cheaper in the sense they takes both the size and verification computation of one signature; and
they're deterministic which enables a lot of interesting directions to explore.

They have their problems too. The committee (the $n$ out of which we need $t$ sigs) is one way or another is gated and need to go through a fancy procedure to keep the determinism when it changes, and there's not much we know to do now to prevent colluding or just (silently) leaking/loosing their key by a member (i.e. $1$ out of $n$) which leads us to strong or weak but inevitable assumption of some honesty of a committee (which mostly explains its gated nature/requirement). That's was a summary & conclusions, and further I'll try to unpack this with more lengthy thought on these points.

A lot of emphasize was put on BLS signature scheme during the lecture as a corner-stone of threshold cryptography. If I get this correctly it's because the sigs are homomorphic (but not fully; for that they'd need this property over multiplication as well). Okay, we can sum a batch of sigs and the result is the valid (aggregated) sig on the thing. Sounds useful for multisig as well!

I feel that $t$ out of $n$ problem is hairy either on the initial end or on the final end; and it's the insight or way to look at the problem of this write-up. Multisig approach lean to be hairy in the finish, and threshold approach leans to be hairy on the start (but there are good news to it below - spoiler #standardization). Btw, it's a reason why multisig is "naive" here: it's easy to start with just the primitives you already have and count the sigs until there are $t$ of those. But further we go with it -- more challenges to solve we get: remembering the sigs (or the fact of verification), management of the committee membership, time to verify or parallelization and trust in this process. All these problems are solvable, and multisig itself isn't naive when done sophisticated, but anyway the solution of the problems are in the end of a thing, closer to when verification happens; and the size is something which can't be workaround without loosing verifiability.

Let's briefly get over the main moving parts to better appreciate the benefit(s) of a threshold approach.

I just came up with committee key but I feel it's a descriptive term! Also the diagram source is available in the end of the page.

[! A fun insight I got]
All the VRF and everything else is just something a committee signs in the same way. Just give them instead of the generator a specific value which represents something you need (timestamp, block height, some data - all will be hashed to the curve anyway) and sign in the same fashion --- the resulted point is that deterministic piece of data you will be building upon.

A single public key sounds like a miracle, it's a huge enabler indeed! But what if the committee needs to be changed (and here goes all the other challenges mentioned earlier for multisig)? The answer is that we need to preserve the polynomial which defines the key during all the manipulations. And it's at least as hairy as the other approach, but now it should be dealt before we get to signing anything --- that's why I present it as the other end of the process. We need to do quite complex protocols (which are still advances rapidly; see distributed key generation - it's the main rabbit hole here) before getting to sign things, but then we have nice, clean, and deterministic system in our hands. Why determinism here such a great deal? It enables of the thing with "auto-": auto-reveal, auto-decryption, auto-confirmation, and so on. Because while multisig is busy with its hairy stuff threshold approach has one stage less on the finish and doesn't need an additional interactions thanks to using that known public key defined by the polynomial (multisig never knows which members come up with signatures in the end of the day, so after sign-off another action is needed).

I nearly abused the word "hairy" today, but let's end this with a major note. What's appealing to me dcipher (personally I think tcipher would be a cuter name) do the #standardization effort so that we could have nice and clean abstraction on the initial end of the threshold approach as well. I guess it's a process, and not all the standards catch-up immediately especially when the domain pace is high (👋 https://zkproof.org/), but I feel that all these efforts are not in vain and helps us even when a next effort overcome the current wave. Let's "stand on the shoulders of giants!"

graph LR
    subgraph Threshold_t["any $t$ out of $n$ keys are sufficient"]
        A[Personal Key 1] -->|Contains| P[Polynomial of Degree $t-1$]
        B[Personal Key 2] -->|Contains| P
        C[Personal Key t] -->|Contains| P
    end
    D[Personal Key t+1] -->|Contains| P
    E[Personal Key n] -->|Contains| P
    P -->|Defines| CK[Committee Key]
    CK -->|Signs| G[the Generator]
    G -->|Produces| PK[Deterministic Public Key]

Cryptopals set 8 in Rust

skaunov — Thu, 14 Mar 2024 18:43:56 +0000

As I led my current things to some milestones, and now I mostly reading about folding and prove systems I have some time to return to Cryptopals. Quick search doesn't yield Rust solutions to the last set --- add a link, pls, if you know them published somewhere.

(Here's the current things, btw.)

On the best effort basis I will be adding code here, and maybe some notes if a better writings won't jump to me from some page. Usual stuff.

If you have any comments or ideas to this you're welcome to express it in the comments. This is just kind of an announcement dedicated to this purpose. Cheers!

Cryptopals #51 in Rust

skaunov — Fri, 08 Dec 2023 00:28:19 +0000

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 =((")
}

Cryptopals #30: Rust, solution approaches

skaunov — Fri, 27 Oct 2023 21:59:18 +0000

There's few hashing challenges in Cryptopals, and some gave me pretty hard time. This one was solved pretty quickly, I even thought that I could cut too much along the way. Lack of solutions in Rust around got me to ask couple of peers to review the thing. So I received their "ok", and now have a minute to wrap up what I remember and how my approach was different.

As I wanted to learn more of real-world libs than do petty stuff I was trying to employ real encryption in this challenges as much as I can. This time I was seeking a way to recreate a Digest core in some intermediate state, but after some time concluded it's barely possible. Even when needed data appropriately structured there's no good way to deal with the system so that it would let me to run methods from the lib. Basically I'm talking about a structure with private fields and methods to construct it which are too sound and correct to help with the challenge.

So I chose to degrade the lib on purpose by only making respective core fields pub. I guess I would do it in a more clever way now, but at that time to move forward most straight-forward solution was to hover a whole supplementary repo to GitHub just for a couple of lines patch. You can find the final solution there.

I hope things changed since, but those days I couldn't find a clear Rust solution for this one. Though one of my peers added his own. Which I finally compared and report to you that we both handled the challenge with similar ideas!

Which one do you like better?

Cryptopals challenge #48 solution

skaunov — Sun, 22 Jan 2023 18:22:41 +0000

I couldn't find a solution in Rust when I wanted, so I decided to cover this.

This solution received absolutely no optimizations, so there are a lot of space for improvements.

It dates back to November and initial cleaned version have been lost, so I cleaned it again, now without #47 branch, and maybe forgetting some details, but everything important is there.

Also this challenge raised couple of question, which landed to crypto.stackexchange. Namely

Why do we get intervals with their ends interchanged? And
Why does it work to discard intervals in pairs?

If you have ideas to explain any of those, please put them to the comments or on the linked page.

If you find links and explanations in the code not clear enough you're always welcome to leave a comment here, or at the Gist page! https://gist.github.com/skaunov/3c6a5dc68c008bc4865adf720eb589a6#file-main-rs

tiny investigation into Cryptopals #51

skaunov — Fri, 02 Dec 2022 00:47:38 +0000

I wondered why the challenge page doesn't mention https://en.wikipedia.org/wiki/CRIME, which it totally should if you ask me. X) (I would guess it's just already much more lengthy than other, so they decided to save some scrolling for you.)

I wanted to see roughly how many time was there between CRIME and challenge-51, and to our disappointment Cryptopals doesn't have any information on release/modification dates on the challenge page. So the best I got is a Reddit comment which gives approximate date of the challenge novelty. It's 2014, Nov; 8 years ago.

Cryptopals #42: personal impressions

skaunov — Sun, 13 Nov 2022 08:55:46 +0000

Atm I just finished #47, and starting #48. But I need a little break, so I decided get back to this notes and publish them for a bit of relaxation. Spoiler: #47 and #48 are on Mr. Bleichenbacher too. So much of him, a genius man, I guess. But these challenges feel like they worth it, no complains.

This one is easy to find a good write-up, so let me describe how I didn't solve it. Actually I'm not unique here, again. (Will add link to a write-up describing the same problem which blocked me.) Though, I completed the code for the solution, and it was a really well math preparation for next challenges.

So here's a couple of question this challenge left me with, and kind of an answer to one of them, describing what blocked me from solving it.

The first of my question was: does it really still present? I mean "We find new instances of it every other year or so.", but when does this statement is still relevant? Then I was caught by surprise how much this padding scheme still in use as default.

So, it's really hard for me to say how wide these intriguing parameters (exponent = 3) are in use since the time challenges were introduced. But if we take a little bit more global look (especially from perspective of following challenges of the set), then we will conclude that entire PKCS1* scheme is a problem. And 'oh, boy', how default is this one. It turns out that given the frequency of its misuse (remember that once a couple of years note?) it were receiving patchy workarounds one by one, making it even more tricky to implement correctly in turn. So the main conclusion seems to be: use other padding schemes! OAEP, PSS, switch to modern cryptography...

It could be not that bad in this particular challenge, but globally it's very illustrative. And the answer... As soon authors didn't mentioned hash to use with the challenge, I stuck with the most default currently: SHA-256. And the thing is it doesn't leave so much space for garbage in the end of the payload, so you basically run out of variations to construct a cube for most of the messages. So maybe sha-256 kind of solves the local problem that was present to us. (Obviously at the time of introduction SHA-1 was the go to choice, and its solution isn't constrained so tightly.)

On the other hand my conclusion(s) should be taken with a bit of salt. I really tried during the challenge to nullify garbage at all (unsuccessfully), then to solve the problem mathematically, and ended up with computational solution. The one thing that was bugging me is that more mathematical checks were telling that there is a solution, but computational were just exhausting the space for it. Maybe it's the one I could revisit later, though I bet the solution indicated by math approach just need some more space for the garbage bytes.

This one last question would be interesting to discuss with other Cryptopals in anyone would drop a look here! Leave a comment, share your experience.

Cryptopals #46: want a write-up?

skaunov — Fri, 04 Nov 2022 22:24:45 +0000

I wonder if anybody is interested in https://cryptopals.com/sets/6/challenges/46 write-up? I'm finishing it with Nodejs, and it seems like you can easily find code for the challenge, but no actual write-up in English.

It's mostly about how artificial it is (they warned) so I couldn't find a realistic something in OpenSSL or to act as victim.

Cryptopals challenge #38: purpose clarification

skaunov — Thu, 03 Nov 2022 00:01:55 +0000

This text focus not on the solution for the challenge, but on the point of the challenge itself.

As soon as I completed #38 I checked others solutions, as I didn't feel like I grasped everything this challenge offered. It turned out that I went very close to others path: confusion, modular math, seeking the point of the challenge. And when I was out of things to squeeze out it, tried to find a more reasonable solutions...

This time without examples, since people could be quite defensive regarding their solutions. But let's get to the questions: what are we really asked to do in this one.

So in the end of the day I concluded that I mostly miss the point of the challenge.

I was puzzled why was it proposed to play with b value, as it's private. And then found a very suitable link which makes things very explicit. (Kudos to the one who left this link in his solution.)

Most of my solution was based on "simplifications" using modular arithmetic. But... It doesn't make sense to play with the parameters, as dictionary attack doesn't rely on it at all. (The confusion that is found in many solutions...)

After reading the linked section it turns out that it's expected not to simplify calculations with parameters, but to pass the server validity check (an example), without which the dictionary attack would be plainly impossible, since the client would reject guesses!

My previous solution already traveled this path: for zero-key challenge I was required to comment out safeguards in the lib.

So in a more realistic setting most of simplifications would just lead to kind of "SrpAuthError::IllegalParameter".

PS
Good passwords are still able to save the day in many cases. From the first of SRP challenges I used a random password, which boiled down this one to brute force, keeping client pretty secure even with MITM.

Cryptopals challenge #33: Implement Diffie-Hellman

skaunov — Sun, 16 Oct 2022 23:53:43 +0000

As usual, after dealing with a challenge, which taught me something, I looked around to see how my solution differs from others. And this time mine turned out to be rather unique.

No, it's not good (and even not excellent). =) I wanted to see how people solved modexp part, and I was interested in Rust solutions. All I opened were using modpow function of bigint crate.

After all it said "write your own modexp", and it felt as a useful part of the exercise. So I employed crypto_bigint crate, and constructed a function for this particular exercise. It's slow and limited to work with 192 bytes integers, but it's still capable to inspire you to tackle this challenge. (Also it should have a problem with exceed bit for big enough numbers, you can take a bigger bigint type if you want to avoid it.)

use crypto_bigint::{
    U1536, Checked, NonZero, Random, 
    rand_core::OsRng, Encoding, U3072
};
use sha3::{Sha3_256, Digest};

fn main() {
    let p = U1536::from_be_hex("ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff");
    let g = U1536::from(2u64);

    let a = U1536::random(&mut OsRng);
    let a_big = modexp(g, a, p);
    let b = U1536::random(&mut OsRng);
    let b_big = modexp(g, b, p);

    let s = modexp(b_big, a, p);

    println!("{s}");

    let mut hasher = Sha3_256::new();
    hasher.update(s.to_be_bytes());
    let result = hasher.finalize();
    println!("{result:?}");
}

fn modexp(
    base: U1536, exponent: U1536, modulus: U1536
) -> U1536 {
    if modulus == U1536::ONE {return U1536::ZERO;}

    let modulus_ch = Checked::new(modulus);
    /* This algorithm is mostly based on Wikipedia
    listing, and the next line is to test the 
    assertion they have. `unwrap`s below turned out 
    to be much more useful during debuggig. */
    (modulus_ch - Checked::new(U1536::ONE)) 
        * (modulus_ch - Checked::new(U1536::ONE));

    let mut result = Checked::new(U3072::ONE);

    let mut base = U1536::from(base);
    let mut base = base % NonZero::new(modulus)
        .unwrap();

    let mut base = U3072::from_be_bytes(
        pad192(base)
    );
    let mut base = Checked::new(base);

    let mut modulus = U3072::from_be_bytes(
        pad192(modulus)
    );

    let mut exponent = exponent;
    while exponent > U1536::ZERO {
        if exponent % NonZero::new(U1536::from(
            2u64
        )).unwrap() == U1536::ONE {
            result = Checked::new(
                (result * base).0.unwrap() 
                    % NonZero::new(modulus)
                        .unwrap()
            );
        }
        exponent >>= 1;
        base = Checked::new(
            (base * base).0.unwrap() 
                % NonZero::new(modulus).unwrap()
        );
    }
    /* It should be checked that excessive bytes are 
    zero, but today we omit the check. They really 
    should after `% p` */
    U1536::from_be_slice(
        result.0.unwrap().to_be_bytes()[192..]
            .into()
    )
}

fn pad192(uint_192: U1536) -> [u8; 384] {
    let mut res: [u8; 384] = [0; 384];
    res[192..].copy_from_slice(
        &uint_192.to_be_bytes()
    );
    res
}

fn at Rosetta is more ubiquitous, but you still can get the values from there to test this one, created with another crate. Don't forget to make them U1536.

If you want to copy-paste them to employ from_be_hex, here they are:
a:000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006ED80FFACE4DF443C2E9A56155272B9004E01F5DABE5F2181A603DA3EB
b:000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005737DF12ECACC95FF94E28463B3CD1DE0C674CB5D079BD3F4C037E48FF
modulus:000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001D6329F1C35CA4BFABB9F5610000000000

Cryptopals-25: use `edit` as keystream

skaunov — Fri, 30 Sep 2022 08:36:04 +0000

Do you want a slightly simpler solution to #25 "Break "random access read/write" AES CTR"? Did you ever wanted to add a crate release (from git) that isn't at <Crates.io>?

As I mentioned on the previous page I was detailing challenge point and overviewed few solutions. Usually I return back to existing solutions to see the alternatives and check my own solution sanity and correctness. This time was a bit different.

Surprisingly I didn't found my solution among those I viewed, so let me share it with you. Not to repeat common part in all of them, I just link a fresh write-up I liked, and quickly note that instead of getting the key and then deciphering with it, we can just feed our ciphertext to the edit function twice: as the one we want to edit (basically it will get us right length in most implementations) and the second time as "plaintext" we want to re-encrypt. (Offset should be 0, of course. So the key-stream would be aligned.) This simple trick/tweak will just apply the key-stream against ciphertext and as the result of "edit" we get plaintext.

Rust code of the solution: https://github.com/skaunov/challenge-25.

Bonus

I wondered of a clean way to import a particular version of crate from git, as the one I used isn't available from <Crates.io>. And it turned out to be just a few lines to do it neatly.

[dependencies.ctr]
git = "https://github.com/RustCrypto/block-modes.git"
tag = "ctr-v0.9.1"