# Crypto in CTF: Q3 2021

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 | Twist and Shout | 29/509 (⭐) |

Zh3r0 CTF 2021 | Real Mersenne | 15/509 (⭐⭐) |

Zh3r0 CTF 2021 | import numpy as MT | 13/509 (⭐⭐) |

0CTF 2021 Quals | zer0lfsr- 🔥 | 35/464 (⭐⭐⭐) |

0CTF 2021 Quals | zer0lfsr+ | 2/464 (⭐⭐⭐⭐⭐) |

0CTF 2021 Quals | zer0lfsr++ | 1/464 (⭐⭐⭐⭐⭐) |

0CTF 2021 Quals | cloudpass | 3/464 (⭐⭐) |

redpwnCTF 2021 | baby | 827/1418 (-) |

redpwnCTF 2021 | blecc | 146/1418 (⭐) |

redpwnCTF 2021 | yahtzee | 103/1418 (⭐) |

redpwnCTF 2021 | scrambled-elgs | 70/1418 (⭐) |

redpwnCTF 2021 | Keeper of the Flag | 42/1418 (⭐⭐) |

redpwnCTF 2021 | retrosign | 26/1418 (⭐⭐⭐) |

Google CTF 2021 Quals | H1 | 23/379 (⭐⭐) |

Google CTF 2021 Quals | pythia 🔥 | 65/379 (⭐⭐⭐) |

Google CTF 2021 Quals | story | 32/379 (⭐⭐) |

Google CTF 2021 Quals | tiramisu | 28/379 (⭐⭐⭐) |

Google CTF 2021 Quals | tonality | 30/379 (⭐⭐) |

ImaginaryCTF 2021 | Rock Solid Algorithm | 149/1018 (⭐) |

ImaginaryCTF 2021 | Lines | 128/1018 (⭐) |

ImaginaryCTF 2021 | Flip Flops | 160/1018 (⭐) |

ImaginaryCTF 2021 | New Technology | 50/1018 (⭐) |

ImaginaryCTF 2021 | Roll it back | 58/1018 (⭐) |

ImaginaryCTF 2021 | Primetime | 41/1018 (⭐⭐) |

ImaginaryCTF 2021 | ZKPoD | 19/1018 (⭐⭐) |

Crypto CTF 2021 | Robert | 19/444 (⭐⭐) |

Crypto CTF 2021 | Rohald | 21/444 (⭐⭐) |

Crypto CTF 2021 | Ecchimera 🔥 | 11/444 (⭐⭐⭐) |

Crypto CTF 2021 | My Sieve | 1/444 (❓) |

Crypto CTF 2021 | Hyper Normal | 69/444 (⭐) |

Crypto CTF 2021 | KeyBase | 118/444 (⭐) |

Crypto CTF 2021 | Triplet | 50/444 (⭐) |

Crypto CTF 2021 | DoRSA 🔥 | 2/444 (⭐⭐⭐⭐) |

Crypto CTF 2021 | Hamul | 56/444 (⭐) |

Crypto CTF 2021 | Double Miff | 16/444 (⭐⭐⭐) |

Crypto CTF 2021 | Elegant Curve | 16/444 (⭐⭐) |

Crypto CTF 2021 | Improved | 37/444 (⭐⭐) |

Crypto CTF 2021 | Polish | 1/444 (⭐⭐⭐) |

Crypto CTF 2021 | Ferman | 31/444 (⭐) |

Crypto CTF 2021 | Trunc | 7/444 (⭐⭐) |

Crypto CTF 2021 | Frozen | 29/444 (⭐⭐) |

Crypto CTF 2021 | Wolf | 33/444 (⭐) |

Crypto CTF 2021 | Salt and Pepper | 69/444 (⭐) |

Crypto CTF 2021 | Tiny ECC | 16/444 (⭐⭐) |

Crypto CTF 2021 | Lower | 0/444 (⭐⭐⭐⭐) |

Crypto CTF 2021 | LINDA | 23/444 (⭐⭐) |

Crypto CTF 2021 | RSAphantine | 29/444 (⭐⭐) |

Crypto CTF 2021 | Onlude | 48/444 (⭐) |

Crypto CTF 2021 | Tuti | 71/444 (⭐) |

Crypto CTF 2021 | Maid | 36/444 (⭐⭐) |

UIUCTF 2021 | dhke_adventure | 64/658 (⭐) |

UIUCTF 2021 | pow_erful | 16/658 (⭐⭐) |

RaRCTF 2021 | sRSA | 220/845 (-) |

RaRCTF 2021 | unrandompad | 89/845 (⭐) |

RaRCTF 2021 | Shamir's Stingy Sharing | 85/845 (⭐) |

RaRCTF 2021 | babycrypt | 108/845 (⭐) |

RaRCTF 2021 | rotoRSA | 29/845 (⭐⭐) |

RaRCTF 2021 | PsychECC | 39/845 (⭐⭐) |

RaRCTF 2021 | snore | 17/845 (⭐⭐) |

RaRCTF 2021 | randompad | 24/845 (⭐⭐) |

RaRCTF 2021 | A3S | 4/845 (⭐⭐⭐) |

RaRCTF 2021 | mini-A3S | 1/845 (⭐⭐⭐⭐) |

corCTF 2021 | 4096 | 219/904 (-) |

corCTF 2021 | dividing_secrets | 121/904 (⭐) |

corCTF 2021 | supercomputer | 85/904 (⭐) |

corCTF 2021 | babyrsa | 50/904 (⭐) |

corCTF 2021 | babypad | 35/904 (⭐) |

corCTF 2021 | babyrand | 29/904 (⭐⭐) |

corCTF 2021 | LCG_k | 25/904 (⭐⭐) |

corCTF 2021 | bank | 25/904 (⭐⭐) |

corCTF 2021 | mystery_stream | 10/904 (⭐⭐⭐) |

corCTF 2021 | fried_rice 🔥 | 6/904 (⭐⭐⭐) |

corCTF 2021 | leave_it_to_chance 🔥 | 5/904 (⭐⭐⭐) |

CakeCTF 2021 | discrete log | 55/157 (-) |

CakeCTF 2021 | improvisation | 34/157 (-) |

CakeCTF 2021 | Together as one | 21/157 (⭐⭐) |

CakeCTF 2021 | Matrix Cipher | 14/157 (⭐⭐) |

CakeCTF 2021 | Party Ticket 🔥 | 12/157 (⭐⭐⭐) |

FwordCTF 2021 | Leaky Blinders | 121/429 (-) |

FwordCTF 2021 | Boombastic | 55/429 (⭐) |

FwordCTF 2021 | Invincible | 29/429 (⭐⭐) |

FwordCTF 2021 | Login | 11/429 (⭐⭐) |

FwordCTF 2021 | Transfer 🔥 | 6/429 (⭐⭐⭐) |

FwordCTF 2021 | Procyon 🔥 | 4/429 (⭐⭐⭐) |

ALLES! CTF 2021 | Secure Flag Service | 46/523 (⭐) |

RCTF 2021 | Uncommon Factors I 🔥 | 14/483 (⭐⭐⭐) |

RCTF 2021 | Uncommon Factors II 🔥 | 29/483 (⭐⭐) |

CSAW'21 CTF | forgery | 127/1216 (⭐⭐) |

CSAW'21 CTF | Bits 🔥 | 24/1216 (⭐⭐⭐) |

ACSC 2021 | RSA stream | 121/483 (-) |

ACSC 2021 | CBCBC | 35/483 (⭐⭐) |

ACSC 2021 | Secret Saver | 12/483 (⭐⭐) |

ACSC 2021 | Swap on Curve | 34/483 (⭐) |

ACSC 2021 | Wonderful Hash 🔥 | 11/483 (⭐⭐) |

ACSC 2021 | Two Rabin 🔥 | 20/483 (⭐⭐⭐) |

ACSC 2021 | Share the Flag 🔥 | 1/483 (⭐⭐⭐) |

## 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

- the block size is
*two*, - the length padding does not exist, and
- 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')
```

### 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).

### 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()`

.

## 0CTF 2021 Quals⌗

### zer0lfsr- 🔥⌗

- Solves: 35/464
- Difficulty: ⭐⭐⭐
- Tags:
`lfsr`

,`nfsr`

We are given three generators those composed of LFSRs (and NFSRs):

`Generator1`

composes of a 48-bit NFSR and a 16-bit LFSR,`Generator2`

composes of a 16-bit NFSR and a 48-bit LFSR, and`Generator3`

composes of a 64-bit LFSR.

Notably, the outputs for each of the generators are non-linear from the state.

We are asked to crack two of the three generators within 50 seconds. For each of the generators, we are given 40K bits from its output. The objective is to recover the initial state.

### zer0lfsr+⌗

- Solves: 2/464
- Difficulty: ⭐⭐⭐⭐⭐
- Tags:
`lfsr`

,`nfsr`

This is a sequel to *zer0lfsr-* and the generators are reused.

We are given 160K bits from $\text{MAJ}(o_1, o_2, o_3)$ (the majority function), where $o_i$ is an output bit from the $i$-th generator. Each generator has a different initial state $k_1, k_2, k_3$ and there is a function $\text{KDF}$ such that $k_2 = \text{KDF}(k_1)$ and $k_3 = \text{KDF}(k_2)$. The objective is to recover all of the $k_i$'s within 100 seconds.

### zer0lfsr++⌗

- Solves: 1/464
- Difficulty: ⭐⭐⭐⭐⭐
- Tags:
`lfsr`

,`nfsr`

This is a sequel for *zer0lfsr+* to kill an unintended solution.

The problem is similar to *zer0lfsr+* but the $k_i$'s are generated independently. On the other hand, we are given the first 16 bits for either $k_1$, $k_2$ or $k_3$. The objective is to recover all of the $k_i$'s within 180 seconds.

### cloudpass⌗

- Solves: 3/464
- Difficulty: ⭐⭐
- Tags:
`keepass`

There is a challenge server that allow us to import (or to create) a `.kbdx`

file with a given password. We are allow to perform the following operations:

- Add an entry given group $g$, title $t$, username $u$ and password $p$: $\text{Add}_\mathcal{E}(g, t, u, p)$,
- Add a group given parent group $g_p$ and group $g$: $\text{Add}_\mathcal{G}(g_p, g)$,
- Add binary given blob $b$: $\text{Add}_\mathcal{B}(b)$,
- List entries: Return all the $(t, u)$'s,
- List groups: Return all the groups $g$'s,
- List binaries: Return all the $b$'s,
- Add the flag via $\text{Add}_\mathcal{E}(g_\text{root}, \text{flag}, \text{0ops}, \mathcal{F})$ and change the master password to 32 random bytes, and
- Export the
`.kdbx`

and terminate the program.

The objective is to recover the flag $\mathcal{F}$.

**Addendum (2021.07.28).** I have lowered the estimated difficulty. From @RBTree_, the challenge composes of 60% reversing, 30% forensics and 10% cryptography. Reversing the `pykeepass`

package and learning the file structure constitutes the majority of the challenge. The cryptographic element itself is not particularly hard.

## redpwnCTF 2021⌗

### baby⌗

- Solves: 827/1418
- Difficulty: -
- Tags:
`rsa`

We are given a 128-bit RSA modulus $n$ and the public exponent $e = 65537$. The goal is to decrypt a given ciphertext $c$. Notably, the factors of $n$ is available in factordb before the CTF begins.

### blecc⌗

- Solves: 146/1418
- Difficulty: ⭐
- Tags:
`ecc`

Given an elliptic curve $\mathcal{C}: y^2 = x^3 + ax + b$ over a prime field $\text{GF}(p)$ (where $p$ is a 64-bit prime). Also, the largest prime factor of the curve's order is 28-bit long. Find $d$ such that $Q = dG$ for given $G$ and $Q$.

*Credits: TWY.*

### yahtzee⌗

- Solves: 103/1418
- Difficulty: ⭐
- Tags:
`ctr`

,`repeated nonce`

We are allowed to retrieve $c$, computed by the below procedure, for an arbitrary number of times.

- Randomly pick a message $m$ from one of the 25 possible messages.
- Insert the flag in a random position of $m$.
- Randomly pick the nonce $\nu$ from one of the 11 candidates.
- Encrypt $m$ with nonce being $\nu$ with AES-CTR - and denote it by $c$.
- Return $c$ to the player.

The objective is to recover the flag.

### scrambled-elgs⌗

- Solves: 70/1418
- Difficulty: ⭐
- Tags:
`elgamal`

We are given a generator $g$ of the symmetric group with 25000 elements and a public key $h$. Given also a ciphertext $(c_1, c_2)$ encrypted with ElGamal cryptosystem, the goal is to find the corresponding message.

### Keeper of the Flag⌗

- Solves: 42/1418
- Difficulty: ⭐⭐
- Tags:
`dsa`

We are allowed to sign two different messages using DSA-SHA1 with the given oracle, where the nonce is *somehow predictable*. The objective is to forge a signature for a particular message (of course you cannot sign it during the first phase).

### retrosign⌗

- Solves: 26/1418
- Difficulty: ⭐⭐⭐
- Tags:
`oss`

Given $k$, $h$ and a composite modulus $n$, find $x$, $y$ such that $x^2 + ky^2 = h\ (\text{mod}\ n)$. This is also known as the OSS signature scheme.

**Note.**This challenge existed in TokyoWesterns CTF 2020 (

*Circular*).

## Google CTF 2021 Quals⌗

### H1⌗

- Solves: 23/379
- Difficulty: ⭐⭐
- Tags:
`ecdsa`

,`ecdh`

Alice and Bob have a private key $d_A, d_B$ respectively and they are used for both ECDSA and ECDH. They derive a shared secret for encryption with ECDH and sign with ECDSA-SHA512.

We are given four messages those are sent between Alice and Bob (two from Alice and two from Bob). Denote the $i$-th message, ciphertext and signature being respectively $m_i$, $c_i$ and $(r_i, s_i)$ - Hereby $m_1$ and $m_3$ are signed by Alice and the rest are signed by Bob. We are given all of them except $m_3$. The objective is to recover $m_3$ where the flag is hidden.

Notably, the entropy for the `RNG`

while generating ECDSA nonces is 128 bits long.

### pythia 🔥⌗

- Solves: 65/379
- Difficulty: ⭐⭐⭐
- Tags:
`gcm`

A nine-letter password is split into three parts. Three keys are derived from each part of the passwords (namely $k_0, k_1, k_2$). We are given the below operations:

**Set key**specifies the key $\mathcal{K} = k_i$ we will be using in the subsequent operations.**Read flag**requests the user to send the password. If it is correct, then the flag is revealed.**Decrypt text**decrypts a specified ciphertext using $\mathcal{K}$ with AES-GCM.*Only*return if the ciphertext is decrypted successfully.

The goal is to read the flag within 150 calls.

### story⌗

- Solves: 32/379
- Difficulty: ⭐⭐
- Tags:
`crc`

When connected to the server, we are asked to send a message $m_1$ and $\text{CRC}(m_1)$ will be returned (We do not have the source code for the CRC). The server then sends a target $c_2$. The objective is to send $m_2$ such that

- $c_2 = \text{CRC}(m_2)$ and,
- the lowercase for $m_1$ is the same as the lowercase for $m_2$.

### tiramisu⌗

- Solves: 28/379
- Difficulty: ⭐⭐⭐
- Tags:
`ecdh`

When connected to the server, it sends a `ServerHello`

message that includes the server's public key for ECDH (on the curve *P-224*), as well as the flag encrypted with server's ECDH private key. We will be replying a `ClientHello`

message that the point should be either on *P-224* or *P-256*. We will be sending `SessionMessage`

s which is a encrypted and HMACed payload when a secure channel is established. If the HMAC is correct and the content can be correctly decrypted, the server will be responding with another `SessionMessage`

with a slightly changed IV. The objective is to decrypt the flag.

Note that the server's key does not change upon reconnect.

### tonality⌗

- Solves: 30/379
- Difficulty: ⭐⭐
- Tags:
`ecdsa`

The server generates a private key $x$ on *P-256* upon connect. We are allowed to pick $\alpha$ and the server will sign $m_0$ with the private key $\alpha x$. The objective is to forge a signature for $m_1$ using the private key $x$ in a subsequent request.

## ImaginaryCTF 2021⌗

### Rock Solid Algorithm⌗

- Solves: 149/1018
- Difficulty: ⭐
- Tags:
`rsa`

We are given the RSA public $n$ and $e := 5$ and a ciphertext $c$ (of the message $m$). Given that $0 < m^5 < 1000 n$, find $m$.

### Lines⌗

- Solves: 128/1018
- Difficulty: ⭐
- Tags:
`math`

We are given a $p$ and $g$. Two numbers $a$ and $b$ are generated privately and the shared secret $s := g^{ab}\ (\text{mod}\ p)$ is computed. Messages are encrypted as $c = m\cdot s\ (\text{mod}\ p)$.

Two pairs of messages $(m_1, c_1)$ and $(m_2, c_2)$ are encrypted in this way. We are given $c_1, m_2, c_2$ and the objective is to find $m_1$ - which is the flag.

### Flip Flops⌗

- Solves: 160/1018
- Difficulty: ⭐
- Tags:
`cbc`

We are given a server that performs the following operations:

- Encrypts an user-defined message (that does not contain
`gimmeflag`

) with a secret key $\mathcal{K}$ and an initial vector $\mathcal{IV}$ in AES-CBC. - Sends the flag to the user if the user sends a ciphertext that the corresponding plaintext contains
`gimmeflag`

.

The objective is to win the flag via the second operation.

### New Technology⌗

- Solves: 50/1018
- Difficulty: ⭐
- Tags:
`math`

We are given $n$ such that $n = p_1^{k_1}p_2^{k_2}...p_5^{k_5}$ where $p_i$'s are all primes and $1 \leq k_i \leq 3$. The key $k$ defined below is used to derive an AES key that encrypts the flag. The goal is to decrypt the ciphertext.

\[k = \sum_{d_1|n}\sum_{d_2|d_1} d_2 \cdot \varphi(d_2) \cdot \varphi\left(\frac{d_1}{d_2}\right)\]

### Roll it back⌗

- Solves: 58/1018
- Difficulty: ⭐
- Tags:
`lfsr`

There is a LFSR in this challenge. We are given the feedback polynomial and the state after clocked 421337 times. The objective is to recover the initial state, which is the flag.

### Primetime⌗

- Solves: 41/1018
- Difficulty: ⭐⭐
- Tags:
`dh`

,`math`

This challenge implements Diffie-Hellman in a handcrafted group (called `Element`

), where addition and scalar multiplication is defined. A generator $G$ is given and the shared secret is computed by $H := abG$, where $a, b\in\mathbb{Z}$ are two private keys from the two parties. We are also given $C := mH$ where $m\in\mathbb{Z}$ is the flag. The objective is to recover $m$.

### ZKPoD⌗

- Solves: 19/1018
- Difficulty: ⭐⭐
- Tags:
`rsa`

We are given a pair of RSA public key $(n, e)$, an encrypted flag $c_0$ and a pair of constants $g, p$ (will be mention later). We are also given an oracle $\mathcal{O}$ that "signs" a message given a ciphertext $c$. The objective is to recover the flag from $c_0$. Below is the procedure for $\mathcal{O}$:

- Compute $m := c^d\ (\text{mod}\ n)$, i.e., decrypt with RSA.
- Generate $k \in [0, p)$.
- Compute $r := g^k\ (\text{mod}\ p)$.
- Compute $e := F(r)$ for a given deterministic function $F$.
- Compute $s := k - me\ (\text{mod}\ p-1)$.
- Return $(r, s)$.

## Crypto CTF 2021⌗

### Robert⌗

- Solves: 19/444
- Difficulty: ⭐⭐
- Tags:
`math`

We are given a number of integers $m$'s and the objective is to find a corresponding $n$ such that $\lambda(n) = m$, where $\lambda$ is the Carmichael's lambda function.

### Rohald⌗

- Solves: 21/444
- Difficulty: ⭐⭐
- Tags:
`ecc`

Suppose that $\mathcal{C}$ is a curve defined by $u^2 + v^2 \equiv c^2 (1 + du^2v^2)\ (\text{mod}\ p)$ (the parameters $c$, $d$ nor $p$ are given). We are given four points on the curve: $P$, $Q$, $sP$ and $tQ$. The objective is to find $s$ and $t$, where each of them encodes half of the flag. Note that the prime factors of the curve order does not exceed $2.5 \times 10^9$.

### Ecchimera 🔥⌗

- Solves: 11/444
- Difficulty: ⭐⭐⭐
- Tags:
`ecc`

We are given a curve $\mathcal{C}: y^2 \equiv x^3 + Ux^2 + Vx + W\ (\text{mod}\ n)$ and two points $G, H\in \mathcal{C}$ with $H := sG$. The objective is to find $s$.

The parameters are given below:

```
n = 43216667049953267964807040003094883441902922285265979216983383601881964164181
U = 18230294945466842193029464818176109628473414458693455272527849780121431872221
V = 13100009444194791894141652184719316024656527520759416974806280188465496030062
W = 5543957019331266247602346710470760261172306141315670694208966786894467019982
G = (6907136022576092896571634972837671088049787669883537619895520267229978111036, 35183770197918519490131925119869132666355991678945374923783026655753112300226)
H = (14307615146512108428634858855432876073550684773654843931813155864728883306026, 4017273397399838235912099970694615152686460424982458188724369340441833733921)
```

### My Sieve⌗

- Solves: 1/444
- Difficulty: ❓
- Tags: ❓

**Needs more information.**I am not totally clear about this challenge. Please let me know if you have a better picture on this one!

We are given a corrupted `pubkey.pem`

where four characters are redacted.

```
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCB*QKBgQCkRgRCyTcSwlBKmERQV/BHkurS
5QnYz7Rm18OjxuuWT3A*Ueqzq7fHISey2NEEtral/*E7v2Dy59DYHoRAAouWQd03
ZYWnvU5mWoYRcpNmHIj8q*+FOtBWcCGzMZ8uxOxaV74vqqerjxyRI14rXZ+QOcNM
/TMM84h0rl/IKqqWsQIDAQAB
-----END PUBLIC KEY-----
```

On top of that, we are also given a `msieve.dat`

and `enc.txt`

. The objective to decrypt `enc.txt`

for the flag.

### Hyper Normal⌗

- Solves: 69/444
- Difficulty: ⭐
- Tags:
`adhoc`

We are given a $55\times55$ matrix $W$ defined by

\[ W = \begin{bmatrix} r_{1,1}x_1 & 2r_{1,2}x_2 & 3r_{1,3}x_3 & ... & 55r_{1,55}x_{55} \\ r_{2,1}x_1 & 2r_{2,2}x_2 & 3r_{2,3}x_3 & ... & 55r_{2,55}x_{55} \\ && \vdots && \\ r_{55,1}x_1 & 2r_{55,2}x_2 & 3r_{55,3}x_3 & ... & 55r_{55,55}x_{55} \\ \end{bmatrix}\ \text{mod}\ p, \]

hereby $r_{ij}, x_j \in [0, 126]$ for all $i, j \in \{1, 2, ..., 55\}$ and $p = 8443$. The objective is to find $x_j$, which each of them represents one character of the encoded flag.

### KeyBase⌗

- Solves: 118/444
- Difficulty: ⭐
- Tags:
`cbc`

We are given the flag $c_0$ encrypted with AES-CBC under a fixed IV and key. Although the IV is unknown, we have 14 bytes (out of 16) of the key. We are also given an oracle $\mathcal{O}$ that encrypts a 32-byte message $m$ and return the corresponding ciphertext with part of the first block redacted.

### Triplet⌗

- Solves: 50/444
- Difficulty: ⭐
- Tags:
`rsa`

We are asked to find three RSA moduli $n_1 = p_1q_1, n_2 = p_2q_2$ and $n_3 = p_3q_3$ and a pair of exponents $e, d$ such that the below conditions hold for all $i = 1, 2, 3$:

\[p_i, q_i > 2^{160}\qquad \text{and} \qquad 1 < e, d < \varphi(n_i) \qquad \text{and} \qquad ed \equiv 1\ (\text{mod}\ \varphi(n_i)).\]

We will be given the flag if all of the conditions hold.

### DoRSA 🔥⌗

- Solves: 2/444
- Difficulty: ⭐⭐⭐⭐
- Tags:
`rsa`

Four 256-bit numbers $u, v, x$ and $y$ are generated and compute $p = uv+1, q = uy+1$ and $r = xy+1$. If $p, q$ and $r$ are all primes, generate a 256-bit number $e$ and find the corresponding $d \in \mathbb{Z}$ such that there exists $k \in \mathbb{Z}$ with $ed - k \varphi(pr) = 1$.

Define also $s = kv+1$, which should also be a prime. Compute the modulus $n_1 = pr$ and $n_2 = qs$. We are given $n_1, n_2$, a common public exponent $e$ and two ciphertexts $c_1, c_2$ being the encrypted $m$ (the flag) with respectively $(n_1, e)$ and $(n_2, e)$ using RSA. The objective is to recover the flag.

### Hamul⌗

- Solves: 56/444
- Difficulty: ⭐
- Tags:
`rsa`

We are given a modulus $n$ and $e = 65537$ for RSA and the encrypted flag $c$. The objective is to recover the flag.

In particular, the primes $p$ and $q$ are derived by concatenating two 64-bit primes $u$ and $v$ in the following way:

\[p = u\ \|\ v\ \|\ v\ \|\ u\qquad\text{and}\qquad q = v\ \|\ u\ \|\ u\ \|\ v.\]

### Double Miff⌗

- Solves: 16/444
- Difficulty: ⭐⭐⭐
- Tags:
`ecc`

,`math`

Suppose that there is a curve $\mathcal{C}: ax(y^2 - 1) \equiv by(x^2 - 1)\ (\text{mod}\ p)$ (we are not given the parameters) where the addition operator is defined. We are given $A, B, C\in \mathcal{C}$ such that $A = P+Q$, $B = Q+Q$ and $C = P+P$. The objective is to find $P$ and $Q$, and each of their $x$-coordinates encodes half of the flag.

### Elegant Curve⌗

- Solves: 16/444
- Difficulty: ⭐⭐
- Tags:
`ecc`

When connected to the server, we are asked to send a pair of triples $(a, b, p)$ and $(c, d, q)$ satisfying the below conditions:

- $0 < a, b < p$ and $0 < c, d < q$, and
- $p, q$ are both 160 bits long and $0 < q - p < 2022$.

Two curves are defined by $\mathcal{C}_1: y^2 \equiv x^3 + ax + b\ (\text{mod}\ p)$ and $\mathcal{C}_2: y^2 \equiv x^3 + cx + d\ (\text{mod}\ q)$. We are then given $G, rG \in \mathcal{C}_1$ and $H, sH \in \mathcal{C}_2$ and asked for $r, s$ to redeem the flag.

### Improved⌗

- Solves: 37/444
- Difficulty: ⭐⭐
- Tags:
`math`

We are given a hash algorithm $\mathcal{H}$ where the procedures when given an integer $m$ are defined below:

- Asserts that $1 < m < n^2 - 1$.
- Computes $e := m^f \text{mod}\ n^2$.
- Computes $u := (e - 1) / n$.
- Computes $L := u\cdot v\ \text{mod}\ n$.
- Returns $\text{SHA256}(L)$ as the digest.

The objective is to find a pair of collisions. Note that the parameters $n$, $f$ and $v$ are given.

### Polish⌗

- Solves: 1/444
- Difficulty: ⭐⭐⭐
- Tags:
`rsa`

,`math`

We are given a 773-bit RSA modulus $n$, $e = 65537$ and the lowest 221 bits for $d$. We are also given an equation on $x$ and $y$:

\[x^2 (y - s) + y^2 (x - s) = t,\]

where $s$ and $t$ are given constants. We are also given $c := (x^2 + m + y)^e\ \text{mod}\ n$. The goal is to recover $m$, the flag.

### Ferman⌗

- Solves: 31/444
- Difficulty: ⭐
- Tags:
`math`

When connected to the server, we are asked to find $p$ and $q$ such that

\[(p - s)^2 + (q - t)^2 = u^7,\]

for some given constants $s, t$ and $u$ (will be changed in different connections).

### Trunc⌗

- Solves: 7/444
- Difficulty: ⭐⭐
- Tags:
`ecc`

,`signature scheme`

When connected to the server, a private key of SECP256k1 is generated (denote by $x$). We are given the corresponding public key and a signature oracle, $\mathcal{O}$, to sign messages. The goal is to forge a signature $(u, v, s)$ such that it is a valid for $m_0$, which cannot be signed via $\mathcal{O}$.

Specifically, the signature scheme is handcrafted and defined below. Suppose that we are given a message $m$ (of length not exceeding 14):

- Generates $k, l$ randomly.
- Computes $u$ and $v$ are respectively the $x$-coordinates of $kG$ and $lG$, where $G$ is the generator for SECP256k1.
- Computes $h = \text{SHA256}(m)$.
- Computes $s = k^{-1} (hu - vx)\ (\text{mod}\ n)$.
- Returns $(u, v, s)$ as the signature.

### Frozen⌗

- Solves: 29/444
- Difficulty: ⭐⭐
- Tags:
`lcg`

We are given a 128-bit prime $p$ and $r \in [1, p)$ as the parameters. A secret number $s$ is generated and five numbers $u_1, u_2, ..., u_5$ is defined by $u_k = r^ks\ \text{mod}\ p$ for $k = 1, 2, ..., 5$.

We are also given those $u_k$'s except that the lowest 32 bits are redacted. The goal is to fully recover the $u_k$'s.

### Wolf⌗

- Solves: 33/444
- Difficulty: ⭐
- Tags:
`gcm`

When connected to the server, a nonce of size $r\in[1, 11]$ (denoted by $\eta$) is generated. We are given the key $k$, the flag encrypted under AES-GCM with key $k$ and nonce $\eta$. We are also given an oracle $\mathcal{O}$ that encrypts arbitrary messages $m$ under the same key and nonce under AES-GCM. The goal is to recover the flag.

### Salt and Pepper⌗

- Solves: 69/444
- Difficulty: ⭐
- Tags:
`hash`

We are asked to forge an authentication token such that the username contains `n3T4Dm1n`

and password contains `P4s5W0rd`

, where the authentication token for a given username and password is defined by:

\[\text{SHA1}(\text{pepper}\ ||\ \text{password}\ ||\ \text{MD5}(\text{salt}\ ||\ \text{username}))\]

We are also given $\text{SHA1}(\text{pepper})$ and $\text{MD5}(\text{salt})$, and their lengths are both 19.

### Tiny ECC⌗

- Solves: 16/444
- Difficulty: ⭐⭐
- Tags:
`ecc`

When connected to the server, we are asked to provide $a, b$ and $p$ satisfying the below conditions:

- $p$ is 128-bit long, and
- $p$ and $q = 2p+1$ are both primes, and
- $a, b \neq 0$.

Two curves are defined by $\mathcal{C}_1: y^2 \equiv x^3 + ax + b\ (\text{mod}\ p)$ and $\mathcal{C}_2: y^2 \equiv x^3 + ax + b\ (\text{mod}\ p)$. We are then given $P, kP \in \mathcal{C}_1$ and $Q, lQ \in \mathcal{C}_2$ and asked for $k, l$ to redeem the flag. (This challenge is similar to *Elegant Curve* but with relaxed conditions)

### Lower 🔥⌗

- Solves: 0/444
- Difficulty: ⭐⭐⭐⭐
- Tags: ❓

When connected to the server, $e_1, e_2, ..., e_5 \in \text{GF}(127)$ are randomly generated. Also, $x_1, x_2, ..., x_{20} \in \text{GF}(127)$ represent the flag. We can request an arbitrary amount of equations, each of them in the form of:

\[s = c_1 x_1 + c_2 x_2 + ... + c_{20} x_{20} + e_k,\]

where we are given $c_1, c_2, ..., c_{20}$ and $s$. Also, $k \in \{1, 2, ..., 5\}$ is picked randomly. The goal is to find $x_i$'s, i.e., the flag.

### LINDA⌗

- Solves: 23/444
- Difficulty: ⭐⭐
- Tags:
`elgamal`

We are given a ElGamal cryptosystem variant with public key $(p, u, v, w)$. To encrypt a message $m \in [0, p)$, two random numbers $r, s \in [1, p)$ are generated and the ciphertext is $(u^r\ \text{mod}\ p, v^s\ \text{mod}\ p, mw^{r+s}\ \text{mod}\ p)$. We are given the public key and the encrypted flag. We are also given an oracle $\mathcal{O}$ to encrypt arbitrary messages. The objective is to find the flag. Note that the prime factors of $p-1$ does not exceed $10^{10}$.

### RSAphantine⌗

- Solves: 29/444
- Difficulty: ⭐⭐
- Tags:
`math`

We are given $r, s$ and $t$ and three equations related to $x, y$ and $z$:

\[ \begin{cases}\begin{aligned} 2z^5 - x^3 + yz &= r \\ x^4 + y^5 + xyz &= s \\ y^6 + 2z^5 + zy &= t \end{aligned}\end{cases}. \]

$x, y$ and $z$ are used to derive the primes for RSA modulus by:

\[ \begin{cases}\begin{aligned} p &= \text{NextPrime}(2^{76} \cdot (x^2 + z^2 + y^2)) \\ q &= \text{NextPrime}((z^2 + y^3 - yxz) \oplus 67) \end{aligned}\end{cases}. \]

We are also given the encrypted flag $c$, encrypted with $e = 31337$ and $n = pq$ - and the objective is to recover the flag.

### Onlude⌗

- Solves: 48/444
- Difficulty: ⭐
- Tags:
`math`

We are given four $11 \times 11$ matrices $E$, $LUL$, $L^{-1}S^2L$ and $R^{-1}S^8$. Here $L$ and $U$ are respectively a lower and upper triangular matrix such that $S = LU$.

The objective is to find the matrix $X$, the encoded flag, such that $E = U(X + R)$.

### Tuti⌗

- Solves: 71/444
- Difficulty: ⭐
- Tags:
`math`

We are asked to find $(x, y)$ such that $(x^2 + 1)(y^2 + 1) - 2(x - y)(xy - 1) = 4(k + xy)$ for a given $k$. In particular, each $x$ and $y$ encodes half of the flag.

### Maid⌗

- Solves: 36/444
- Difficulty: ⭐⭐
- Tags:
`rabin`

We are given an encryption oracle $\mathcal{E}$ and a decryption oracle $\mathcal{D}$ of a variant of the Rabin cryptosystem, where the modulus is defined by $n = p^2q$ instead of the product of the two primes.

On top of that, we are also given the flag, $c$, encrypted with *RSA* with modulus $pq$ and the public exponent $e = 65537$. The objective is to recover the flag.

## UIUCTF 2021⌗

### dhke_adventure⌗

- Solves: 64/658
- Difficulty: ⭐
- Tags:
`dh`

Upon connected to the server, we are asked to send a prime $p$ which is between 1024 and 2048 bits. The generator $g = 2$ is used and two random private keys $a, b \in [2, p)$ are generated. Denote $A := g^a\ (\text{mod}\ p)$ and $B := g^b\ (\text{mod}\ p)$ and $c$ be the flag encrypted with the key derived from $g^{ab}\ (\text{mod}\ p)$. The objective is to decrypt the flag given $A$, $B$ and $c$.

### pow_erful⌗

- Solves: 16/658
- Difficulty: ⭐⭐
- Tags:
`hash`

We are given 64 proof-of-work challenges. In the $k$-th round, we are given a two-byte prefix and we are asked to find $x$ such that $\text{SHA256}(\text{prefix} + x)$ has $k$ trailing zero bits. We will be given the flag after solving the proof-of-work challenges.

## RaRCTF 2021⌗

### sRSA⌗

- Solves: 220/845
- Difficulty: -
- Tags:
`math`

We are given a public key of RSA $n, e$ and an encrypted flag $c$. However the encryption algorithm is $c \equiv me\ (\text{mod}\ n)$. The goal is to recover the flag.

### unrandompad⌗

- Solves: 89/845
- Difficulty: ⭐
- Tags:
`rsa`

Upon connected to the server, we are given a RSA public key $n, e = 3$. We can also retrieve flag encrypted with the aforementioned public key. The objective is to recover the flag.

### Shamir's Stingy Sharing⌗

- Solves: 85/845
- Difficulty: ⭐
- Tags:
`math`

Upon connected to the server, a degree 30 polynomial $p(n)$ with integral coefficients generated randomly in $[0, 2^{128})$ is produced. We are allowed to supply $k\neq 0$ and get the $k$-th share (defined by $p(k)$). On top of that, the flag xorred with a random stream seeded by $p(0)$ is given. The objective is to recover the flag.

### babycrypt⌗

- Solves: 108/845
- Difficulty: ⭐
- Tags:
`rsa`

Upon connected to the server, we are given a RSA public key $n, e$, a hint defined by $d\ \text{mod}\ (q-1)$ and an encrypted flag $c$. The objective is to recover the flag.

### rotoRSA⌗

- Solves: 29/845
- Difficulty: ⭐⭐
- Tags:
`math`

,`rsa`

Upon connected to the server, we are given a RSA public key $n, e = 11$ and $a_0, a_1, ..., a_{15}$ are generated in $[0, 128)$ and they are used to build $p_0(x) = a_0 + a_1 x + ... + a_{15} x^{15}$, $p_1(x) = a_1 + a_2 x + ... + a_{15} x^{14} + a_0 x^{15}$, ..., $p_{15}(x) = a_{15} + a_0 x + a_1 x^2 + ... + a_{14} x^{15}$.

We are able to access the oracle $\mathcal{O}$ many times - On the $k$-th time, we can:

- supply a message $m$ and obtain an encrypted copy of $p_{k\ \text{mod}\ 16}(m)$ with RSA, or
- obtain an encrypted copy of $p_{k\ \text{mod}\ 16}(m_0)$, where $m_0$ is the flag.

The objective is to recover the flag.

### PsychECC⌗

- Solves: 39/845
- Difficulty: ⭐⭐
- Tags:
`ecc`

We are asked to send a point $P$ on P-256 (they does not check if $P$ lies on the curve though) and they generated a random $k$ between 1 and the curve's order and compute $Q = kP$. We are also asked too send a point $\hat{Q}$ and will be given the flag if $\hat{Q} = Q$ while $\hat{Q} \not\in \{P, O\}$.

### snore⌗

- Solves: 17/845
- Difficulty: ⭐⭐
- Tags:
`signature scheme`

A 32 byte secret $s$ is generated at the beginning. Other than that, $x \in [0, p)$ is randomly generated and $y = g^x\ \text{mod}\ p$.

The challenge uses a variant of the data signature algorithm. To sign a message $m$, the following steps are performed:

- Compute $k$ by xorring $s$ and (part of) $m$.
- Compute $r = g^k\ \text{mod}\ p$.
- Compute $e = \text{SHA224}(r\ ||\ m)$.
- Compute $s = k - xe\ \text{mod}\ (p-1)$.
- Return $(r, s)$ as the signature.

We are given $g$, $p$ and $y$ as well as six pairs of message-signature pairs. We are also given the flag encrypted with the key derived from $x$. The objective is to recover the flag.

### randompad⌗

- Solves: 24/845
- Difficulty: ⭐⭐
- Tags:
`mt19937`

,`rsa`

Upon connected to the server, we are given a RSA public key $n, e = 3$. We are allowed to encrypt arbitrary messages and retrieve an encrypted flag padded with PKCS#1 v1.5 (using streams generated from predictable random). The objective is to recover the flag.

### A3S⌗

- Solves: 4/845
- Difficulty: ⭐⭐⭐
- Tags:
`aes variant`

We are given a custom block cipher called *A3S*, which looks like AES but uses a trit (a ternary digit) instead of a bit as the base unit. On top of that, we are given a message-ciphertext pair and the encrypted flag with the same key. The objective is to recover the flag.

### mini-A3S⌗

- Solves: 1/845
- Difficulty: ⭐⭐⭐⭐
- Tags:
`aes variant`

We are still using *A3S* mentioned in the above challenge. However, there are some modifications including updating the S-box involved, and reducing the key size. We are given $3^9$ message-ciphertext pairs with the same key $k$, and the flag xorred with $\text{SHA512}(k)$. The objective is to recover the flag.

## corCTF 2021⌗

### 4096⌗

- Solves: 219/904
- Difficulty: -
- Tags:
`rsa`

We are given a RSA modulus $n = p_1 p_2 ... p_{32}$ an encrypted flag $c$. Here each of the $p_i$'s is a 32-bit prime. The objective is to find the flag.

### dividing_secrets⌗

- Solves: 121/904
- Difficulty: ⭐
- Tags:
`math`

We are given a 512-bit prime $p$ and $g$ with $1 \leq g < p$. We are also given $y = g^x\ \text{mod}\ p$ where $x$ is the flag. We are given 64 attempts of the oracle $\mathcal{O}(k)$, where we could obtain $g^{\lfloor x/k \rfloor}\ \text{mod}\ p$ each time. The objective is to recover the flag.

### supercomputer⌗

- Solves: 85/904
- Difficulty: ⭐
- Tags:
`math`

We are given three 2048-bit primes $p, q, r$. Suppose that $n = p^qr$ and $a_1$ is a random number generated in $[0, n]$. Denote $a_2 = n - a_1$ and $t = {a_1}^n + {a_2}^n$. Define $\upsilon: \mathbb{N}^2 \rightarrow \mathbb{Z}_{\ge0}$ by

\[\upsilon(p, k) = \sum_{i=0}^\infty{\lfloor{\frac{p}{k^i}\rfloor}}.\]

The flag is encrypted with the XOR cipher under the key $\upsilon(t, p)$. The objective is to recover the flag.

### babyrsa⌗

- Solves: 50/904
- Difficulty: ⭐
- Tags:
`rsa`

We are given a 1024-bit RSA modulus $n$ and part of the $p$ and $q$ (with 40 digits in the middle missing). We are also given the encrypted flag $c$. The objective is to recover the flag.

### babypad⌗

- Solves: 35/904
- Difficulty: ⭐
- Tags:
`ctr`

,`padding oracle`

When connected to the oracle, a key $k$ is generated. We are given an oracle $\mathcal{O}(\upsilon, c)$ that performs the below procedure:

- Decrypt $c$ using key $k$ and initial counter value being $\upsilon$ using AES-CTR.
- Unpad the above message with PKCS7 padding.

We are also given a ciphertext of the padded flag. The goal is to recover the flag.

### babyrand⌗

- Solves: 29/904
- Difficulty: ⭐⭐
- Tags:
`lcg`

We are given three numbers $c_1, c_2, p$ with $p$ being a 512-bit prime and $c_1 \in [0, p)$. Denote $a = p \oplus c_1 \oplus s_1$ and $b = p \oplus c_2 \oplus s_2$ where $0 \leq s_1, s_2 < 2^{200}$, and $c_2 = (c_1\cdot a + b)\ \text{mod}\ p$.

Suppose that a key is derived by $a$ and $b$ and the flag is encrypted with AES-CBC. The objective is to recover the flag.

### LCG_k⌗

- Solves: 25/904
- Difficulty: ⭐⭐
- Tags:
`ecdsa`

,`lcg`

Suppose $m_0$ is the message `i wish to know the ways of the world`

.

We are given a ECDSA public key $H$ and we can sign four different messages (except $m_0$) that corresponds to $H$. However, the random number, $k$, is generated with a LCG with a known prime modulus. The objective is to send a signed $m_0$ afterwards.

### bank⌗

- Solves: 25/904
- Difficulty: ⭐⭐
- Tags:
`quantum`

When connected to the server, 50 qubits $\lvert q_1 \rangle, \lvert q_2 \rangle, ..., \lvert q_{50} \rangle$ are generated and we are allowed to perform operations on those qubits. The objective is to recover the initial state of the qubits.

*Credits: hoifanrd*

### mystery_stream⌗

- Solves: 10/904
- Difficulty: ⭐⭐⭐
- Tags:
`lfsr`

A flag is inserted to a random position of a large plaintext. It is encrypted with a custom cipher which involves a LFSR, where the initial state is generated with from a particular script (`pub.sage`

). The objective is to recover the flag, given the ciphertext file.

### fried_rice 🔥⌗

- Solves: 6/904
- Difficulty: ⭐⭐⭐
- Tags:
`lcg`

,`discrete log`

When connected to the server, $k, a, b\in \text{GF}(2^{128})$ are generated. We are given $a$ and $b$.

A PRNG parametrised by $k, a, b$ is defined and two 512-bit primes $p, q$ are generated with this PRNG. There are multiple cryptosytems involved:

- $k$ is used to derive an AES key and the flag is encrypted with the key.
- $n = pq$ and $e = 65537$ is used in the RSA key and $d$ is the corresponding private key - and $d_p = d\ \text{mod}\ (p-1)$.

We are allowed to send $m$ and retrieve $f(m)$, defined below, 26 times:

\[f(m) = g^{d_p \oplus m}\ \text{mod}\ r.\]

The objective is to recover the flag.

### leave_it_to_chance 🔥⌗

- Solves: 5/904
- Difficulty: ⭐⭐⭐
- Tags:
`math`

When connected to the server, a 256-bit prime $p$ such that $p \equiv 1\ (\text{mod}\ 4)$ is generated. A number $a$ is generated such that $a^2 \not\equiv 1\ (\text{mod}\ p)$ and $a^4 \equiv 1\ (\text{mod}\ p)$. Furthermore, a private key $(x_0, x_1, ..., x_{15}) \in \mathbb{Z}_p^{16}$ is generated. Denote the function $\mathcal{S}(m)$ by

\[\mathcal{S}(m) = \sum_{i=0}^{15} m^i x_i.\]

We are allowed to perform the three operations:

**[Sign]**We are allowed to send $m \in \mathbb{Z}_p$ (each $m$ could only be signed once). Denote $s = \mathcal{S}(m)$ and we are given $s^4\ \text{mod}\ p$. We are also asked for an number $x$ and two numbers from $\{ -s, as, -as \} \setminus \{ x \}$ are also given as hint.**[Verify]**We send $m, s\in \mathbb{Z}_p$ and we will be told if $s = [\mathcal{S}(m)]^4\ \text{mod}\ p$.**[Guess]**We send $(\hat{x_0}, \hat{x_1}, ..., \hat{x_{15}})$ and we will be given the flag if $\hat{x_i} = x_i$ for all $i$. Otherwise the connection ends immediately.

The objective is to recover the private key and send it via *guess*.

## CakeCTF 2021⌗

### discrete log⌗

- Solves: 55/157
- Difficulty: -
- Tags:
`math`

A 512-bit prime $p$ and $g, r\in[2, p)$ are generated. Let the flag being $m_1, m_2, ..., m_n$ where $m_k \in [0, 256)$. The flag is encrypted into $c_1, c_2, .., c_n$ with

\[c_k = g^{r \cdot m_k}\ \text{mod}\ p.\]

We are given $p$, $g$ and $c_k$'s. The objective is to recover the flag.

### improvisation⌗

- Solves: 34/157
- Difficulty: -
- Tags:
`lfsr`

We are given the taps of a 64-bit LFSR, and an encrypted flag. We are also given the first 8 bytes of the plaintext. The objective is to recover the flag.

### Together as one⌗

- Solves: 21/157
- Difficulty: ⭐⭐
- Tags:
`math`

,`rsa`

Three 512-bit prime $p, q, r$ are generated. We are given $n = pqr$, $x = (p+q)^r\ \text{mod}\ n$ and $y = (p + qr)^r\ \text{mod}\ n$, as well as an flag $c$ encrypted with multi-prime RSA with modulus $n$. The objective is to recover the flag.

### Matrix Cipher⌗

- Solves: 14/157
- Difficulty: ⭐⭐⭐
- Tags:
`ggh`

Two matrices $R, B \in \mathbb{Z}^{46\times 46}$ are generated such that

\[R = kI + E,\qquad B = UR\]

where $k = \lfloor100\sqrt{46}\rfloor$, $E\in \mathbb{Z}^{46\times 46}$ with $-100 \leq E_{ij} \leq 100$ for all $i, j$ and $\text{det}(U) = \pm1$. For a message $M$, a ciphertext $C$ is defined by $C = BM + \mathcal{E}$, where $\mathcal{E} \in \mathbb{Z}^{46}$ with $-50 \leq \mathbb{E}_i \leq 50$ for all $i$.

We are given $B \in \mathbb{Z}^{46\times 46}$ and the encrypted flag $c \in \mathbb{Z}^{46}$. The objective is to recover the flag.

### Party Ticket 🔥⌗

- Solves: 12/157
- Difficulty: ⭐⭐⭐
- Tags:
`rabin signature`

We are given $(b_i, c_i, n_i)$ for $i = 1, 2$, where they satisfy $c_i \equiv m(m + b_i)\ (\text{mod}\ n_i)$. Suppose that $n_i$ is a product of two primes, and $b_i, c_i \in [0, n_i)$. The objective is to recover $m$, which is the flag.

## FwordCTF 2021⌗

### Leaky Blinders⌗

- Solves: 121/429
- Difficulty: -
- Tags: -

Upon connected to the server, a 32-byte AES key $k$ is generated. We are also given the encrypted flag $c_\text{flag}$. We are allowed to perform the below operations:

*Encrypt*encrypts a random 32-byte message $m$ with the key $k$ into ciphertext $c$. However, if $c_i = k_i$ for some $i$, then the ciphertext will not be printed.*Decrypt*takes a ciphertext $c$ and a key $k'$. $c$ will be decrypted with the $k'$. If the plaintext contains`FwordCTF`

, the flag will be printed.

### Boombastic⌗

- Solves: 55/429
- Difficulty: ⭐
- Tags:
`math`

Upon connecting to the server, a 1024-bit prime $p$ and a secret $x\in [1, p)$ is generated. A ticket for code $c$ is generated by compute $y = \text{SHA256}(c)$, and

\[r = \frac{y^2 - 1}{x^2}\ \text{mod}\ p\qquad\text{and}\qquad s = \frac{1 + y}{x}\ \text{mod}\ p.\]

The ticket for code $c$ is given by $(s, r, p)$. Suppose that we are able to make tickets for random code $c$ that we could not control. The objective is to generate a ticket for code `Boombastic`

.

### Invincible⌗

- Solves: 29/429
- Difficulty: ⭐⭐
- Tags:
`ecc`

,`prng`

The service implements `Dual_EC_DBRG`

as a PRNG where we are able to send $P$ (where $P \neq O$) and they pick a $Q$ and a seed. There are 100 challenges afterwards. An AES-key is derived from the PRNG output and a random IV and message is generated (with `os.urandom`

), and we are given the IV and ciphertext. The objective is to decrypt and recover the message for each of the challenges.

### Login⌗

- Solves: 11/429
- Difficulty: ⭐⭐
- Tags:
`rsa`

**Note.**There is a non-crypto part in the challenge and it will be skipped.

We are given the RSA parameters $e, d$ and $p^{-1}\ \text{mod}\ q$. The objective is to sign a given message using the recovered RSA key.

### Transfer 🔥⌗

- Solves: 6/429
- Difficulty: ⭐⭐⭐
- Tags:
`ed25519`

When connected to the server, an *ed25519* signing key is generated. We are allowed perform the below operations:

**Transfer**asks us to provide $m$ which is shorter than 256 bytes. It returns a signed $m$.**Verify**asks us to provide a message $m$ and its corresponding signature $s$. It returns the flag if $s$ is a valid signature of $m$, and $m$ is at least than 256 bytes.

The objective is to successfully provide a pair of $(m, s)$ for the verify command. Additionally, the `sign`

and `verify`

functions used are excerpted below.

```
# Variables:
# - sk is the secret key
# - pk is the public key.
#
# Functions:
# - H(m: bytes) -> bytes
# returns the SHA512 digest of m
# - Hint(m: bytes) -> int
# returns the SHA512 digest (in integer) of m
def sign(m, sk, pk):
m = long_to_bytes(m)
h = H(sk)
a = bytes_to_long(h[:32]) % l
r = Hint(h[32:] + hmac.new(m, h, digestmod=hashlib.sha512).digest())
R = mult(B, r)
S = (r + Hint(point_to_bytes(R) + pk + m) * a) % l
return point_to_bytes(R) + long_to_bytes(S)
def verify(s, m, pk):
m = long_to_bytes(m)
R = bytes_to_point(s[:32])
A = bytes_to_point(pk)
S = bytes_to_long(s[32:])
h = Hint(point_to_bytes(R) + pk + m)
r1 = mult(B, S)
r2 = add(R, mult(A, h))
return r1 == r2
```

### Procyon 🔥⌗

- Solves: 4/429
- Difficulty: ⭐⭐⭐
- Tags:
`dh`

When connected to the server, a 1024-bit prime $p$ is generated and $g = 3$. Alice and Bob will be generating their corresponding Diffie-Hellman secrets, namely, $x$ and $y$. The shared secret, defined by $g^{xy}\ \text{mod}\ p$, is used to encrypt the flag via the below function (hereby $s$ is the shared secret and $t$ is the timestamp in seconds):

\[\text{Enc}_s(m) = t\cdot s + (m \cdot s\ \text{mod}\ p).\]

We are given the flag encrypted with the shared secret. We are also able to forge Alice's public key and obtain $\text{Enc}_{s'}(m')$ where $s'$ is the forged shared secret and $m'$ is a random 512-bit message. The objective is to recover the flag.

## ALLES! CTF 2021⌗

### Secure Flag Service⌗

- Solves: 46/523
- Difficulty: ⭐
- Tags:
`ctr`

Suppose that there is a master password $\mathcal{P}$ which derives the *encryption key* $k_\mathcal{E}$ and the *MAC key* $k_\mathcal{M}$. A message $m$ is encrypted by the function $\text{Encrypt}(m)$ by:

\[\text{Encrypt}(m) = \nu\ \|\ \text{AESCTR}_{k_\mathcal{E}}\left(\text{Encode}\left(m\ \|\ \text{MAC}_{k_\mathcal{M}}\left(m\right)\right), \text{nonce}=\nu\right).\]

Remarkably, $\text{Encode}$ is a function that encode a $n$-bit message into a $2n$-bit message. Each `0`

bit will be encoded into `00`

and otherwise encoded into either `01`

or `10`

(picked randomly).

We are given an encrypted $\mathcal{P}$ and a oracle $\mathcal{O}$ - we are able to supply a ciphertext $c$:

- If the MAC is incorrect, it prints
`Get off my lawn or I call the police!!!`

. - If $\text{Decrypt}(c) \neq \mathcal{P}$, it prints
`Wrong Password!!!`

. - Otherwise it will print us an encrypted flag.

The objective is to recover the flag.

## RCTF 2021⌗

### Uncommon Factor I 🔥⌗

- Solves: 14/483
- Difficulty: ⭐⭐⭐
- Tags:
`factor`

We are given 512-bit moduli $n_1, n_2, ..., n_{2^{22}}$, where

- $p_k = x + r_k$ with $0 \leq x < 2^{176}$, $0 \leq r_k < 2^{24}$, and
- $q_k$ is a 312-bit prime.

The objective is to recover $x$.

### Uncommon Factor II 🔥⌗

- Solves: 29/483
- Difficulty: ⭐⭐
- Tags:
`factor`

We are given 512-bit moduli $n_1, n_2, ..., n_{2^7}$, where

- $p_k = x + r_k$ with $0 \leq x < 2^{208}$, $0 \leq r_k < 2^{104}$, and
- $q_k$ is a 200-bit prime.

The objective is to recover $x$.

## CSAW'21 CTF⌗

### forgery⌗

- Solves: 127/1216
- Difficulty: ⭐⭐
- Tags:
`dsa`

We are given a set of parameters for digital signature algorithm: the modulus $p$, a generator $g$ and a public key $y$. The objective is to find a triple $(m, r, s)$. Denote $m' = m\ \text{mod}\ 2^{1024}$, the triple needs to satisfy:

- $m$ is a message that contains
`Felicity`

,`Cisco`

or`both`

, - $0 < m' < p-1$ and $0 < r, s < p - 1$, and
- $g^m \equiv y^rr^s\ (\text{mod}\ p)$.

### Bits 🔥⌗

- Solves: 24/1216
- Difficulty: ⭐⭐⭐
- Tags:
`discrete log`

When connected to the server, we are given $n$, $g = 2$ and $y_i$ (where $y_i \equiv g^{x_i}\ (\text{mod}\ n)$ for some integers $x_i$) for $i = 1, 2$. It is also known that the order for $g$ modulo $n$ is of $m$ bits.

We have an oracle $\mathcal{O}(y)$ which finds the $x \in [0, q)$ such that $g^x \equiv y \ (\text{mod}\ n)$ and returns

`-1`

if such $x$ does not exist,`1`

if $x \wedge 2^{m - 123} \neq 0$, or`0`

otherwise.

We are also given a flag encrypted with a shared secret derived by $g^{x_1x_2}\ \text{mod}\ n$. The objective is to decrypt the flag.

## ACSC 2021⌗

### RSA stream⌗

- Solves: 121/483
- Difficulty: -
- Tags:
`rsa`

We are given a modulus for RSA $n$ and three public exponents $e_1$, $e_2$ and $e_3$. Let $m$ be the flag and $k_i = m^{e_i}\ \text{mod}\ n$.

The $k_i$'s are used as a bitstream of stream cipher, i.e., $C_i = M_i \oplus k_i$ for message $M_i$ and ciphertext $C_i$. We are also given $(M_1, C_1)$, $(M_2, C_2)$ and $(M_3, C_3)$. The goal is to recover the flag $m$.

### CBCBC⌗

- Solves: 35/483
- Difficulty: ⭐⭐
- Tags:
`cbc`

,`padding oracle`

Let $\mathcal{K}$ be a key and $\mathcal{IV}_1, \mathcal{IV}_2$ be two IVs. Define the encryption function $\mathcal{E}$ by:

\[\mathcal{E}(m) = \text{AES-CBC}_{\mathcal{K}, \mathcal{IV}_2}\left(\text{AES-CBC}_{\mathcal{K}, \mathcal{IV}_1}\left(m\right)\right)\]

When connected to the server, an AES key $\mathcal{K}$ and two IVs $\mathcal{IV}_1, \mathcal{IV}_2$ are generated. There are two functions provided from the server:

**Create user**requests for a username $n$ and a corresponding token $t$, defined below, is returned.\[t := \mathcal{E}(\text{\{``username":}\ n\text{, ``is\_admin": false\}})\]

If a username is not provided, then the below token is returned (note that we do not know $n_0$):

\[t := \mathcal{E}(\text{\{``username":}\ n_0\text{, ``is\_admin": true\}})\]

**Login**requests a username $n$ and a token $t$ and performs the below routine:- Decrypts $t$ and unpad. Returns
`Failed to login! Check your token again`

if an exception is caught (for example, the ciphertext size is not a multiple of 16, the padding is invalid, etc). - Parses the JSON object. Returns
`Failed to login! Your token is malformed`

if an exception is caught. - Gets the
`username`

and compares with $n$. Returns`Failed to login! Check your username again`

if the values do not match.

- Decrypts $t$ and unpad. Returns

The objective is to login as an admin, i.e., `is_admin`

is truthy.

### Secret Saver⌗

- Solves: 12/483
- Difficulty: ⭐⭐
- Tags:
`compression oracle`

,`crime`

We are given a PHP service with the below source code:

```
<?php
include "config.php";
$msg = $_POST['msg'] ?? "";
$name = $_POST['name'] ?? "";
if ( strlen($name) < 4 || strlen($msg) < 8 )
highlight_file(__FILE__) && exit();
$data = array(
"name" => $name,
"msg" => $msg,
"flag" => "ACSC{" . $KEY . "}" // try to get this flag!
);
$iv = openssl_random_pseudo_bytes(16);
$data = gzcompress(json_encode($data));
$data = openssl_encrypt($data, 'aes-256-ctr', $KEY, OPENSSL_RAW_DATA, $iv);
$data = bin2hex( $iv . $data );
$conn = new mysqli($HOST, $USER, $PASS, $NAME);
$sql = sprintf("insert into msgs (msg, name) values('%s', '%s')", $data, $name);
if (!$conn->query($sql))
die($conn->error);
echo $conn->insert_id;
$conn->close();
```

In short, when we provide the service `message`

and `name`

, a JSON object with fields `message`

, `name`

and `flag`

is created. It is compressed with ZLIB and encrypted with AES-CTR. The end result is stored into the database (note that there is a SQLi issue which allows one to retrieve the length of the ciphertext). The goal is to recover the `flag`

.

### Swap on Curve⌗

- Solves: 34/483
- Difficulty: ⭐
- Tags:
`ecc`

We are given an elliptic curve $y^2 = x^3 + ax + b\ (\text{mod}\ p)$. Let $x_0$ be the flag and it is known that both $(x_0, y_0)$ and $(y_0, x_0)$ lies on the curve. The objective is to recover the flag.

### Wonderful Hash 🔥⌗

- Solves: 11/483
- Difficulty: ⭐⭐
- Tags:
`hash`

Define a hash algorithm $\mathcal{H}$ for messages $m_1 m_2 ... m_k$ (where $m_i$ is a 16-byte message block) as $h(m_1) \oplus h(m_2) \oplus ... \oplus h(m_k)$, where $h(m)$ is defined by the below procedure:

- Let $x_1 = \text{AES}_m(00...00)$ ($x_1$ is the ciphertext of 16 null bytes with key $m$).
- Let $x_2 = \text{ARC4}_{x_1}(00...00)$ ($x_2$ is the ciphertext of 8 null bytes with key $x_1$).
- Let $x_3 = \text{DES}_{x_2}(00...00)$ ($x_3$ is the ciphertext of 8 null bytes with key $x_2$).
- $h(m)$ is the first six bytes of $x_3$.

When connected to the server, a default command $\mathcal{C}_0$ (of 417 bytes) is deployed. We can execute arbitrary commands $\mathcal{C}$ that satisfies the below conditions:

- $\text{len}(\mathcal{C}) = \text{len}(\mathcal{C}_0)$,
- $\mathcal{H}(\mathcal{C}) = \mathcal{H}(\mathcal{C}_0)$, and
- each of the characters of $\mathcal{C}$ is ASCII-printable.

The flag is in `/flag`

. The objective is to print the content of the file.

### Two Rabin 🔥⌗

- Solves: 20/483
- Difficulty: ⭐⭐⭐
- Tags:
`rabin signature`

There are two stages in the challenge. They share the same set of parameters: 1024-bit modulus $n = pq$ and 512-bit $B$. The flag is broken into two parts and each part is 98 bytes long. Denote the Rabin's signature $\mathcal{S}$ for signature $m$ being:

\[\mathcal{S}(m) = m(m + B)\ \text{mod}\ n.\]

- The first half of the flag $m_1$ is padded to 128 bytes with PKCS5, into $m_2$. We are given $c_1 = \mathcal{S}(m_1)$ and $c_2 = \mathcal{S}(m_2)$.
- The second half of the flag $M$ is padded into 128 bytes by $m_i = 256^{30}M + r_i$ where $r_i \in [0, 256^{30})$. We are given $c_1 = \mathcal{S}(m_1)$ and $c_2 = \mathcal{S}(m_2)$.

The objective is to recover the whole flag.

### Share the flag 🔥⌗

- Solves: 1/483
- Difficulty: ⭐⭐⭐
- Tags:
`linear system`

We are given $(x_1, y_1), (x_2, y_2), ..., (x_{15}, y_{15})$ when connected to the server, where

\[y_k = \sum_{i=0}^{31} c_i x_k^i\ \text{mod}\ p.\]

Hereby $p = 251$, $x \in [1, p)$ and $c_i$ are the ASCII values of printable characters. Note that $c_0, c_1, ..., c_{15}$ are unchanged every time and $c_{16}, c_{17}, ..., c_{31}$ will be changed each time. Additionally, $97 \leq c_{16}, c_{17}, ..., c_{31} < 123$ (i.e., they are lowercase alphabet). The objective is to recover $c_0, c_1, ..., c_{15}$, which is the flag.