This is a new series about the cryptography challenges happened (and the challenges will be grouped into blog post quarter-yearly). I'll be describing the challenge (or the cryptographic parts for the challenge) briefly. Also, I will not be walking through their solutions. In short, the series of the blog posts is served as a directory of crypto challenges happened in CTFs. The objective is to let CTF players on cryptography to identify challenges those they found interesting. In particular, the challenges marked with 🔥 are recommended.

Undeniably, the difficulty is biased and solely determined by the crypto part (i.e., if there are reversing, obfuscation and what-not, they are not included). Look for the solve count if you need an less subjective metric. The list is nowhere complete since I do not play each and every single CTFs...

CTF Challenge Name Solves Difficulty
Pwn2Win CTF 2021 Oh, Anna Julia 49/720
Pwn2Win CTF 2021 t00 rare 🔥 13/720 ⭐⭐
Pwn2Win CTF 2021 cladorhizidae 12/720 ⭐⭐
Pwn2Win CTF 2021 A2S 🔥 10/720 ⭐⭐⭐⭐
Pwn2Win CTF 2021 Kangurei 3/720 ⭐⭐⭐
Zh3r0 CTF 2021 alice_bob_dave 91/509
Zh3r0 CTF 2021 chaos 50/509 ⭐⭐
Zh3r0 CTF 2021 1n_jection 45/509
Zh3r0 CTF 2021 Twist and Shout 29/509
Zh3r0 CTF 2021 b00tleg 26/509
Zh3r0 CTF 2021 Real Mersenne 15/509 ⭐⭐
Zh3r0 CTF 2021 import numpy as MT 13/509 ⭐⭐

Pwn2Win CTF 2021

Oh, Anna Julia

  • Solves: 49/720
  • Difficulty: ⭐
  • Tags: math

Suppose that $h_i \equiv g^{x_{i,1} + x_{i,2} + ... + x_{i,40}}\ (\text{mod}\ q)$ for $i = 1, 2, ...$. We are given $g$, $q$ and $h_i$'s. We are able to control $a_1, a_2, ..., a_{40} \in \{0, 1, 2, ..., 255\}$, pick $k\in\{1, 2, ..., 40\}$ multiple times and obtain

\[\begin{aligned} &c := {h_1}^{x_{2,k}} \cdot {h_3}^{x_{4,k}} \cdot ... \cdot g^{(a_i \oplus s_i) + r}\ \text{mod}\ q \\ &d := {h_2}^{x_{1,k}} \cdot {h_4}^{x_{3,k}} \cdot ... \cdot g^{r}\ \text{mod}\ q \end{aligned},\]

where $r$ is randomly generated each time. The objective is to find $s_k \in \{0, 1, 2, ..., 255\}$ for all $k = 1, 2, ..., 40$.

t00 rare 🔥

  • Solves: 13/720
  • Difficulty: ⭐⭐
  • Tags: ecdsa

We are allowed to obtain ECDSA signatures over P-256 via the given oracle, where the $k$ is generated deterministically from the given digest $h$. The secret key is computed by $a^x\ \text{mod}\ q$, where $q$ is the order of the curve. Notably, the order for $a$ is 40-bit long. Suppose that the signature for the flag is $(r_\text{flag}, s_\text{flag})$ and denote $R$ be a point on the elliptic curve with its x-coordinate being $r_\text{flag}$. The objective is to find $x$ such that $R = xG$.

cladorhizidae

  • Solves: 12/720
  • Difficulty: ⭐⭐
  • Tags: hash

We are given a hash algorithm $\mathcal{H}$ that looks alike to Merkle-Damgard scheme, where

  1. the block size is two,
  2. the length padding does not exist, and
  3. the state is reversible if the message is known.

We are also given an oracle to compute $\mathcal{H}(s + x)$, where $s$ is the secret, from $x$. The objective is to find $\mathcal{H}(s + t)$, given $t$, after accessing to the oracle $2^{16}$ times.

A2S 🔥

  • Solves: 10/720
  • Difficulty: ⭐⭐⭐⭐
  • Tags: two-round aes

We are given three message-ciphertext pairs of AES, where the number of rounds is reduced from ten rounds to two. The objective is to recover the key.

Kangurei

  • Solves: 3/720
  • Difficulty: ⭐⭐⭐
  • Tags: postquantum

We are given a public key for Tsafenat-Paaneah-I (TP-I) and three ciphertexts, where each of them is encrypted from a part of the flag. The objective is to decrypt the ciphertexts for the flag.

Zh3r0 CTF 2021

alice_bob_dave

  • Solves: 91/509
  • Difficulty: ⭐
  • Tags: rsa

Two RSA keys $\mathcal{K}_1$ and $\mathcal{K}_2$ are generated and two different messages $m_i$ are encrypted with $\mathcal{K}_i$. Suppose that the moduli of the two keys shared a common prime factor. We are given the private keys $d_1$, $d_2$, ciphertexts $c_1$, $c_2$ and $e=65537$ (Note that we do not have the moduli). The objective is to retrieve the $m_i$'s.

chaos

  • Solves: 50/509
  • Difficulty: ⭐⭐
  • Tags: hash

We are given the hash algorithm below. Find a pair of hash collision.

def hash(text:bytes):
    text = pad(text)
    text = [int.from_bytes(text[i:i+4],'big') for i in range(0,len(text),4)]
    M = 0xffff
    x,y,z,u = 0x0124fdce, 0x89ab57ea, 0xba89370a, 0xfedc45ef
    A,B,C,D = 0x401ab257, 0xb7cd34e1, 0x76b3a27c, 0xf13c3adf
    RV1,RV2,RV3,RV4 = 0xe12f23cd, 0xc5ab6789, 0xf1234567, 0x9a8bc7ef
    for i in range(0,len(text),4):
        X,Y,Z,U = text[i]^x,text[i+1]^y,text[i+2]^z,text[i+3]^u
        RV1 ^= (x := (X&0xffff)*(M - (Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A)
        RV2 ^= (y := (Y&0xffff)*(M - (Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B)
        RV3 ^= (z := (Z&0xffff)*(M - (U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C)
        RV4 ^= (u := (U&0xffff)*(M - (X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D)
    for i in range(4):
        RV1 ^= (x := (X&0xffff)*(M - (Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A)
        RV2 ^= (y := (Y&0xffff)*(M - (Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B)
        RV3 ^= (z := (Z&0xffff)*(M - (U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C)
        RV4 ^= (u := (U&0xffff)*(M - (X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D)
    return int.to_bytes( (RV1<<96)|(RV2<<64)|(RV3<<32)|RV4 ,16,'big')

1n_jection

  • Solves: 45/509
  • Difficulty: ⭐
  • Tags: math

The flag is encoded into an integer by the below algorithm recursively. The goal is to retrieve the flag given the integer.

def nk2n(nk):
    l = len(nk)
    if l==1:
        return nk[0]
    elif l==2:
        i,j = nk
        return ((i+j)*(i+j+1))//2 +j
    return nk2n([nk2n(nk[:l-l//2]), nk2n(nk[l-l//2:])])

Twist and Shout

  • Solves: 29/509
  • Difficulty: ⭐
  • Tags: mt19937

We are given 624 consecutive outputs (32-bit) from MT19937. The objective is to recover the state (where the flag is hidden inside).

b00tleg

  • Solves: 26/509
  • Difficulty: ❓
  • Tags: guessing

There are eight stages and we are given an encryption oracle $\mathcal{E}$ along with a target ciphertext $c_0$ in each stage. The objective is to find $m_0$ such that $c_0 = \mathcal{E}(m_0)$. Examples:

Stage 1 (Deterministic)

- Target Ciphertext:
    69666d6d70217870736d6522214d667574216866752168706a6f68
- Sample Message-Ciphertext Pairs:
    0001020304 -> 0102030405
    fffefdfcfb -> 00fffefdfc
    feff000102030405 -> ff00010203040506

Stage 2 (Deterministic)

- Target Ciphertext:
    167536933462626657495469026094356252520425094567558410085605026028734973776349984140755605180214900
- Sample Message-Ciphertext Pairs:
    0000000000 -> 0
    0123456789 -> 4886718345
    2020202020 -> 137977929760

Stage 3 (Random)

- Sample Target Ciphertext:
    f968146888f7fb56f7185218fb18526814f7884144ec14188818404118887444ec411852d9ec
- Sample Message-Ciphertext Pairs:
    0000000000 -> 0606060606
    0001020304 -> 06c693194a
    fffefdfcfb -> 422321d07a
    000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f404142434445464748494a4b4c4d4e4f505152535455565758595a5b5c5d5e5f606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3b4b5b6b7b8b9babbbcbdbebfc0c1c2c3c4c5c6c7c8c9cacbcccdcecfd0d1d2d3d4d5d6d7d8d9dadbdcdddedfe0e1e2e3e4e5e6e7e8e9eaebecedeeeff0f1f2f3f4f5f6f7f8f9fafbfcfdfeff -> 06c693194a9ec20cfe60a831462fd4963af6a5e9f2a43027730b811094f5724b88ae24ad20e5b75bceb6af7557438eac625d1fa786e8f4c5a205823298b56c55b8385a64c07ba33bab2c8a9d3f2e7f1c1d7e336980b2bb588ba604fd831387d28d415674e1ecd3d14052dc5c12f91468778444f718fbd937b171f85e6d78540ddd926f28c1cbe4a199c8e70889700edfefe2e6fa03bd019f2d6a53450fde369a91225134b36150491e63f33cbcdacd393deed84c3511d7d66e2b7c66e0d5cc15f09c48ed268cfc760247c4b49bb059ea1695a9853ebf0a07aaf12aff1a97db29be4d7d6b17651b09c3eb7900cfc7c95f25caba67e38fb9904e4fa07ad0212342

Stage 4 (Random)

- Sample Target Ciphertext:
    1f7a1bd7392dbe89443529ce1ce120d26e366bb940b310329c567421308d8c5c35f55e7438f70454d464c375fdb3
- Sample Message-Ciphertext Pairs:
    00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 -> 06a0bdd8e07fe8e461d7d6ab89e71506a0bdd8e07fe8e461d7d6ab89e71506a0bdd8e07fe8e461d7d6ab89e71506

Stage 5 (Random)

- Sample Target Ciphertext:
    fa4daac2124f93d1a57b77fd98d0d78aec88d34ddd9cdc9398dd3de37de91c4dbaadc8ad650d4f16471d55cbbeb16c098de76fb18be9c99fb9ac52ced396c7a7accaadb4076b8ddc50116c02bbb9
- Sample Message-Ciphertext Pairs:
    00000000000000000000 -> e0201fe1d52b659b1ae640c00000728e9f6144bc
    000102030405060708090a0b0c0d0e0f10111213 -> 0d2b046513082c016e1e07210a6b19023a1774040d2a066617

Stage 6 (Random)

- Sample Target Ciphertext:
    0ed047cc9231d015c8c236d05bcd9232dd5089d923cc15dedb32dd15d0dd33c715dada2fc11989c22ad054dad766d15ac7c666c150c5de66d45bd0dd28d0a0a5e346b535a9b2
- Sample Message-Ciphertext Pairs:
    00000000000000000000 -> fad9125ff0fad9125ff0fad9125ff0
    000102030405060708090a0b0c0d0e0f10111213 -> 0d2b046513082c016e1e07210a6b19023a1774040d2a066617

Stage 7 (Random)

- Sample Target Ciphertext:
    60222238880808415315564662869981908505440642260045046563389299584917948074872824491944912250223659352966280390848850996171250596163088184092161597483453986170765362572648185435705259158362825458429760212885576737096932930824507304116954082792861401760259427685220832812095883949676159043987107595388920804411
- Sample Message-Ciphertext Pairs:
    02 -> 8
    03 -> 27
    ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff -> 94573654061867776611935540980114390054836021647550174119343078050818349541547354395131489087456718988004941535435454452028489210462458952036164582940967775738884640201444144067903492683077284812112295176291230089048199818157474376406642481790871903869416383956024955929491943438970626870294265451574423219577

Stage 8 (Random)

- Sample Target Ciphertext:
    34248000799602134005032201251775659290344087231532407044121142051028353597123494333179305555704200248208385884487490454228734858501794078144190090763423945275479240010489707153814934733865199575035758408544651649878681423115783481800433673479421207570310142675649777421242182223888776686800935109578083765660
- Sample Message-Ciphertext Pairs:
    02 -> 10141204801825835211973625643008
    03 -> 13915193059764305937984450503671774362956903094027
    ffff -> 8239825207483342945403772594011105873193687375110276116117075150028748347891031172164610764769228050404350448178327644106605659572477624385183220706571800203167642057909473471911878412444165156467056562866947921869615495140542561600780724868906137285781937906324779216682223045718281196918475467251933010545

Credits: TWY for the examples.

import numpy as MT

  • Solves: 15/509
  • Difficulty: ⭐⭐
  • Tags: mt19937

We are given the flag encrypted with AES-CBC twice, with the keys and IVs each round are numpy.random.bytes(16). The objective is to retrieve the flag.

Real Mersenne

  • Solves: 13/509
  • Difficulty: ⭐⭐
  • Tags: mt19937

We are given $\approx 1000$ outputs from random.random(). The objective is to predict the upcoming values of random.random().