cryptopals

An ongoing attempt at solving the cryptopals crypto challenges in Rust.

Set 1: Basics

1. Convert hex to base64 (solution)
2. Fixed XOR (solution)
3. Single-byte XOR cipher (solution)
4. Detect single-character XOR (solution)
5. Implement repeating-key XOR (solution)
6. Break repeating-key XOR (solution)
7. AES in ECB mode (solution)
8. Detect AES in ECB mode (solution)

Set 2: Block crypto

9. Implement PKCS#7 padding (solution)
10. Implement CBC mode (solution)
11. An ECB/CBC detection oracle (solution)
12. Byte-at-a-time ECB decryption (Simple) (solution)
13. ECB cut-and-paste (notes) (solution)
14. Byte-at-a-time ECB decryption (Harder) (notes) (solution)
15. PKCS#7 padding validation (solution)
16. CBC bitflipping attacks (solution)

Set 3: Block & stream crypto

17. The CBC padding oracle (notes) (solution)
18. Implement CTR, the stream cipher mode (solution)
19. Break fixed-nonce CTR mode using substitutions (notes) (solution)
20. Break fixed-nonce CTR statistically (notes) (solution)
21. Implement the MT19937 Mersenne Twister RNG (notes) (solution)
22. Crack an MT19937 seed (solution)
23. Clone an MT19937 RNG from its output (notes) (solution)
24. Create the MT19937 stream cipher and break it (solution)

Set 4: Stream crypto and randomness

25. Break "random access read/write" AES CTR (solution)
26. CTR bitflipping
27. Recover the key from CBC with IV=Key
28. Implement a SHA-1 keyed MAC
29. Break a SHA-1 keyed MAC using length extension
30. Break an MD4 keyed MAC using length extension
31. Implement and break HMAC-SHA1 with an artificial timing leak
32. Break HMAC-SHA1 with a slightly less artificial timing leak

Notes (spoiler alert!)

Set 2 Challenge 13

This attack relies on crafting an input such that we'd be able to get the desired ciphertext containing the text "role=admin". (In retrospect, the title of the problem is quite a giveaway.)

The first email validation function I wrote only allowed alphanumeric characters and the @ and . characters. Based on a closer reading of the problem statement, I then changed it to only remove & and =, allowing for injecting the padding characters. Since this didn't seem too realistic for a real world email validation function, I was unsure if this was the best approach. But after discussing it with some other Recurse folks working on cryptopals, it seems to be the only approach we can think of (so far!).

One cool thing that I did learn from this is that emails can contain some special characters! From Wikipedia's page on email addresses:

If quoted, it may contain Space, Horizontal Tab (HT), any ASCII graphic except Backslash and Quote and a quoted-pair consisting of a Backslash followed by HT, Space or any ASCII graphic; it may also be split between lines anywhere that HT or Space appears.

So I know that at least the ascii code 9 (HT) is allowed, but unfortunately the padding code that I'd need for this attack is 11 and I can't find anything definitive on its validity from the wiki page or from RFC5322: Internet Message Format.

let ciphertext = [
    // The chosen input here would produce a ciphertext with three blocks
    // and the last block would be
    // "user\u{c}\u{c}\u{c}\u{c}\u{c}\u{c}\u{c}\u{c}\u{c}\u{c}\u{c}\u{c}".
    // We take the first two blocks of this ciphertext.
    &ecb_encrypt(profile_for("[email protected]").as_bytes(), &key)[..32],
    // The chosen input here would produce a ciphertext with the second
    // block being
    // "admin\u{b}\u{b}\u{b}\u{b}\u{b}\u{b}\u{b}\u{b}\u{b}\u{b}\u{b}". We
    // append this block to the previous two blocks above to form our
    // desired role=admin profile.
    &ecb_encrypt(
        profile_for(
            "1234567890admin\u{b}\u{b}\u{b}\u{b}\u{b}\u{b}\u{b}\u{b}\u{b}\u{b}\u{b}\u{b}",
        )
        .as_bytes(),
        &key,
    )[16..32],
]
.concat();

assert_eq!(
    "[email protected]&uid=10&role=admin",
    String::from_utf8(ecb_decrypt(&ciphertext, &key)).unwrap()
);

Set 2 Challenge 14

Now generate a random count of random bytes and prepend this string to every plaintext.

At first I misread and mistakenly thought that the random prefix changes with each call to the oracle function. That would have made the solution much harder, although still possible (I think). Solving for the case when the random prefix is fixed makes the problem much more tractable. Solution sketch:

1. Find the length of the random prefix.
2. Repeat the steps in challenge 12 but ignoring the first n blocks that corresponds to the random prefix when calling the oracle function.

Set 3 Challenge 17

References

1. https://robertheaton.com/2013/07/29/padding-oracle-attack/
2. https://research.nccgroup.com/2021/02/17/cryptopals-exploiting-cbc-padding-oracles/

Set 3 Challenge 19

At first I wasn't quite sure what attacking the cryptosystem piecemeal meant. My initial thought was to use a statistical approach that's much closer to what Challenge 20 is expecting. But, I did find a writeup to this challenge that quite nicely (and interactively) solves the challenge. I didn't exactly follow this approach, since it wasn't as easy to interactively decipher the text using a compiled language without a repl, and I ended up with a solution that's closer to what I did to breaking repeating XOR in Challenge 6. I did have to iterate on the solution a number of times, especially tweaking the acceptable ascii characters in the if-condition, in order to maximize the number of columns decrypted.

Set 3 Challenge 20

The solution to this is quite similar to the previous solution, except that instead of requiring all the characters in plaintext_column to be mostly letters of the alphabet and certain accepted symbols, we simply choose the byte that'll result in the the most number of letters when XOR-ed.

Set 3 Challenge 21

References

1. https://github.com/bmurray7/mersenne-twister-examples/blob/master/python-mersenne-twister.py
2. http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/MT2002/emt19937ar.html
3. https://rust-random.github.io/book/guide-rngs.html

Set 3 Challenge 23

An initial confusion for me was that to recover y in x = y ^ y >> l, y = x ^ x >> l. This assumes that l > (w - l), where w is the word size (32 in this case).

References

1. https://occasionallycogent.com/inverting_the_mersenne_temper/index.html
2. https://gist.github.com/Rhomboid/b1a882c70b7a1901efa9
3. https://www.maths.tcd.ie/~fionn/misc/mt/
4. https://nayak.io/posts/mersenne_twister/