---
# System prepended metadata

title: 'Block Ciphers 2024 [Jella]'
tags: [Crypto]

---

## Block Cipher 1
### Description
- Challenge code:
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5
from os import urandom

FLAG = b"KCSC{???????????????????????????}"
assert len(FLAG) % 16 == 1 # hint

key1 = md5(urandom(3)).digest()
key2 = md5(urandom(3)).digest()
cipher1 = AES.new(key1, AES.MODE_ECB)
cipher2 = AES.new(key2,AES.MODE_ECB)

enc = cipher1.encrypt(pad(FLAG,16))
enc = cipher2.encrypt(enc)

print(enc.hex())

# 21477fac54cb5a246cb1434a1e39d7b34b91e5c135cd555d678f5c01b2357adc0c6205c3a4e3a8e6fb37c927de0eec95
```
### Solution
- Phân tích một chút, bài cho `enc` được mã hóa hai lần qua AES với `key1` và `key2` 3 bytes random rồi được hash MD5. Ý tưởng xuất hiện đầu tiên của mình là brute force nhưng `key1` và `key2` đều là 3 bytes nên không gian sẽ là `256**3 * 256**3 = 256**6`. Đây là không gian khá lớn để brute force được.
- Tuy nhiên, mình nhớ lại về 2DES với cách tấn công `meet-in-the-middle attack`. Khi đó, không gian của ta sẽ nhỏ lại chỉ còn `256**3 + 256**3 = 2**24 + 2**24 = 2**25` nên có thể brute force được `key1`, `key2` dễ dàng. 
- Ta có thuật toán mã hóa như sau:
```
E(flag, key1) = enc1
E(enc1, key2) = enc2 --> D(enc, key2) = enc1
```
- Thuật toán của `meet-in-the-middle attack` khá đơn giản, mình sẽ thực hiện `encrypt` với `256**3` giá trị `key1` và lưu vào bảng, sau đó thực hiện `decrypt` với `256**3` giá trị `key2`. Check với bảng vừa khởi tạo, chắc chắn ta luôn có được một cặp `key1`, `key2` thỏa mãn vì cùng tạo ra đoạn `enc1`.
- Mình đã có `enc2` để `decrypt`, vậy còn `flag` thì sao. Có hint `len(flag) % 16 == 1` nên `len(flag) = 16*k + 1`. Check `len(enc) = 48` nên `len(flag + pad) = 48`, suy ra `len(flag) = 33`. Ta có thể chia `flag` thành hai `block` 16 bytes. Có `block2 = b'}' + b'\x0f'*15` do PKCS#7. Vậy mình sẽ `encrypt` với `block2` này và thực hiện `meet-in-the-middle attack` với `block2` để tìm ra `key1`, `key2` thỏa mãn. 
- Code:
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from tqdm import tqdm as t
from hashlib import md5

ct = '21477fac54cb5a246cb1434a1e39d7b34b91e5c135cd555d678f5c01b2357adc0c6205c3a4e3a8e6fb37c927de0eec95'
ct =  bytes.fromhex(ct)
block2_check = ct[-16:]
block2 = b'}' + b'\x0f'*15
look_up = {}
key1, key2 = b'', b''
for temp in t(range(256**3), desc=':Collecting'):
    temp = temp.to_bytes(3)
    key = md5(temp).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    enc = cipher.encrypt(block2)
    look_up[enc] = key

for temp in t(range(256**3), desc='Checking'):
    temp = temp.to_bytes(3)
    key = md5(temp).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    dec = cipher.decrypt(block2_check)
    if dec in look_up:
        key1 = look_up[dec]
        key2 = key
        print(key1)
        print(key2)
        break

cipher1 = AES.new(key1, AES.MODE_ECB)
cipher2 = AES.new(key2, AES.MODE_ECB)
flag = cipher2.decrypt(ct)
flag = cipher1.decrypt(flag)
flag = unpad(flag, 16).decode()
assert len(flag) % 16 == 1
print(flag)
```
### Flag
> ~~`KCSC{MeEt_In_tHe_mIdDLe_AttaCk__}`~~
### Note
```python=
key1 = b'/\xc5\xe63%\xac\x93\xc1\xaf\xd3\x94\xe5\n\xd3\xf3I'
key2 = b'\x8f\x06\x88\x17\x01\xd9\xd9j\xf5F\xe6\x08_z\xf4\xb1'
```
---
## Block Cipher 2: 2000_ECB_CBC
### Description
- Challenge code:
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import choice
from os import urandom
import socket
import threading

FLAG = b'KCSC{Bingo!_PKCS#7_padding}'

class ThreadedServer(object):
    def __init__(self, host, port):
        self.host = host
        self.port = port
        self.sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
        self.sock.bind((self.host, self.port))

    def listen(self):
        self.sock.listen(5)
        while True:
            client, address = self.sock.accept()
            client.settimeout(60)
            threading.Thread(target = self.listenToClient,args = (client,address)).start()

    def listenToClient(self, client, address):
        size = 1024
        for i in range(100):
            x = choice(['ECB','CBC'])
            if x == 'ECB':
                cipher = AES.new(urandom(16), AES.MODE_ECB)
            else:
                cipher = AES.new(urandom(16), AES.MODE_CBC, urandom(16))

            try:
                msg = bytes.fromhex(client.recv(size).strip().decode())
                assert len(msg) <= 16
                client.send(cipher.encrypt(pad(msg,16)).hex().encode() + b'\n')
                ans = client.recv(size).strip().decode()
                assert ans == x
                client.send(b'Correct!\n')
            except:
                client.send(b"Exiting...\n")
                client.close()
                return False

        client.send(FLAG)
        client.close()
        return False


if __name__ == "__main__":
    ThreadedServer('',2000).listen()
```
### Solution
- Phân tích một chút, mình cần gửi cho server một `msg` và server trả về một `ciphertext`. Mình cần trả lời xem `msg` đã được mã hóa theo mode `ECB` hay `CBC`. Trước tiên cần hiểu được sơ đồ của hai mode này:
- ECB:
![Hình ảnh minh họa](https://hackmd.io/_uploads/BJMd3OLiT.png)
- CBC:
![Hình ảnh minh họa](https://hackmd.io/_uploads/BJiunO8s6.png)
- Nếu `block` không đủ 16 bytes thì sẽ được pad thêm theo PKCS#7. Do tất cả mọi thứ đều là random trừ `msg` mình có thể chọn nên mình sẽ hướng theo phân tích `msg` hay nói cách khác là các `block` của mình. 
- Mình sẽ thử với `msg = b'\x00'*16` trên local:
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

key_ECB = b'\xee\xbc\x83\x91\xeaPT\xbe\x10>g\xe9\x9c\xfd\x9d\xee'
key_CBC = b'\xaf\x0f\xcej\x05>\x18\x81\xc4\xa9\xcf\x96\x1a\x04\xb7q'
iv_CBC = b'\xf9_I\x17\xcfs\x8c\xb7\x98\xf3\xa1\r\xd0\xcc69'

msg = b'\x00'*16
cipher1 = AES.new(key_ECB, AES.MODE_ECB)
cipher2 = AES.new(key_CBC, AES.MODE_CBC, iv_CBC)
print(pad(msg, 16))
ct_ECB = cipher1.encrypt(pad(msg, 16))
ct_CBC = cipher2.encrypt(pad(msg, 16))
```
- Một điều cần chú ý ở đây là `pad(msg, 16)` của mình trả về 32 bytes (được đệm thêm 16 bytes `b'\x10'`). Tuy nhiên, mình cũng biết được mode `ECB` mã hóa giống nhau cho các `block` giống nhau, mà `msg` ở dạng hex không được dài quá 16. Chính vì thế, mình sẽ gửi `msg = b'\x10' * 16`. Khi đó nếu `ct[:16] = ct[16:]` thì sure đó là mode `ECB`, nếu không thì là mode `CBC`.
- Code thử trên local:
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

key_ECB = b'\xee\xbc\x83\x91\xeaPT\xbe\x10>g\xe9\x9c\xfd\x9d\xee'

msg = b'\x10'*16
cipher = AES.new(key_ECB, AES.MODE_ECB)
print(pad(msg, 16))
ct_ECB = cipher.encrypt(pad(msg, 16))
block1 = ct_ECB[:16]
block2 = ct_ECB[16:]
if(block1 == block2):
    print('ECB')
```
- Code solve:
```python=
from pwn import *

def send(msg):
    return r.sendline(msg.encode())
r = remote('localhost', 2000)

msg = bytes.hex(b'\x10'*16)
for i in range(100):
    send(msg)
    get = bytes.fromhex(r.recv().decode())
    block1 = get[:16]
    block2 = get[16:]
    send('ECB') if block1 == block2 else send('CBC')
    print(r.recv().decode())
    if i == 99:
        flag = r.recv().decode()
        print(flag)
```
### Flag
> ~~`KCSC{Bingo!_PKCS#7_padding}`~~
### Note
- Vì `len(msg) <= 16` và một `block` luôn có 16 bytes, bên cạnh đó PKCS#7 pad ngay cả khi `len(block) % 16 == 0` nên bắt buộc phải giải bài với `msg` như trên.
---
## Block Cipher 3: 2003_ECB
### Description
- Challenge code:
```python=
from Crypto.Cipher import AES
from os import urandom
from base64 import b64encode
import string
import socket
import threading


chars = string.ascii_lowercase + string.ascii_uppercase + '!_{}'
FLAG = b'KCSC{Chosen_Plaintext_Attack___ECB_ECB_ECB___you_made_it!}'
assert all(i in chars for i in FLAG.decode())


def pad(msg, block_size):
    if len(msg) % block_size == 0:
        return msg
    return msg + bytes(block_size - len(msg) % block_size)


def chall(usrname):
    key = urandom(16)
    cipher = AES.new(key, AES.MODE_ECB)
    msg = b'Hello ' + usrname + b', here is your flag: ' + FLAG + b'. Have a good day, we hope to see you soon.'
    enc = cipher.encrypt(pad(msg,16))
    return b64encode(enc)

class ThreadedServer(object):
    def __init__(self, host, port):
        self.host = host
        self.port = port
        self.sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
        self.sock.bind((self.host, self.port))

    def listen(self):
        self.sock.listen(5)
        while True:
            client, address = self.sock.accept()
            client.settimeout(60)
            threading.Thread(target = self.listenToClient,args = (client,address)).start()

    def listenToClient(self, client, address):
        size = 1024
        while True:
            try:
                usrname = client.recv(size).strip()
                client.send(chall(usrname) + b'\n')
            except:
                client.close()
                return False


if __name__ == "__main__":
    ThreadedServer('',2003).listen()
```
### Solution
- Đối với bài, mình có một cách để cheat ra độ dài của flag với code:
```python=
from pwn import *
from json import *
from base64 import b64decode as D

def send(msg):
    return r.sendline(msg)

r = remote('localhost', 2003)
for i in range(30):
    usrname = b'\x00'*i
    send(usrname)
    ct = r.recvline().decode()
    ct = D(ct)
    print(i, len(ct))
```
- Sau khi thực thi code, mình nhận được cặp giá trị đặc biệt như sau:
```python=
...
16 144
17 160
...
```
- Giải thích một chút, khi mình gửi lên `usrname` có độ dài là `i`, server sẽ tự động pad thêm để `len(ct) % 16 == 0`
    - Khi độ dài là 16, nhận được `len(ct) = 144` 
    - Khi độ dài là 17, nhận được `len(ct) = 160`
    - Trong đó cơ chế PKCS#7 cũng sẽ pad ngay cả khi `len(ct) % 16 == 0`. 
- Chính vì vậy, tại giá trị thay đổi kia ta tìm được độ dài của flag do `len(txt) + len(usrname) + len(flag) = 144`
- Biết được
```python=
txt = b'Hello , here is your flag: . Have a good day, we hope to see you soon' # len = 69
usrname = b'\x00' * 17 # len = 17
```
- Vì vậy, `len(flag) = 144 - 69 - 17 = 58`. Ta cần dùng số 58 này để assert cũng như thực hiện giải mã dễ dàng hơn.
- Ở [đây](https://exploit-notes.hdks.org/exploit/cryptography/algorithm/aes-ecb-padding-attack/) cũng có một thuật toán giúp tìm lại từng kí tự của flag bằng cách brute force, tuy nhiên chỉ áp dụng được khi `key` là cố định.
- Bài khá khoai khi cho `key` random nhưng mình có sơ đồ ECB như sau:
![image](https://hackmd.io/_uploads/HyXGpPMia.png)
- Điều này chứng tỏ nếu `P1 = P2` thì `C1 = C2` và khắc phục được nhược điểm của thuật toán nói trên. Thay vì brute force lên server nhiều lần, mình sẽ chọn gửi `usrname` giống với phần liền kề ngay trước của `flag` rồi brute force bằng bytes cuối cùng của `usrname`.
- Ý tưởng (thử với chữ đầu của `flag` là `K`):
```python=
block2 = b' is your flag: ' + bruteforce() 
block_real = b' is your flag: K'
Bằng cách nào đó để Enc(block2) = Enc(block_real) thì bruteforce() = K
```
- Mình đã phân tích như sau:
```python=
Hello ########## is your flag: K##########, here is your flag: K
block1 = b'Hello ##########'
block2 = b' is your flag: K'
block3 = b'##########, here'
block4 = b' is your flag: K'
```
- Điều này giúp cho `block2 = block4`, thực tế thì `block2 = b' is your flag: ' + char` và `usrname = ########## is your flag: K##########`
- Thử gửi xem sao:
```python=
from pwn import *
from json import *
from base64 import b64decode as D

def send(msg):
    return r.sendline(msg)

r = remote('localhost', 2003)
LEN = 58
FLAG = ''

usrname = b'########## is your flag: K##########'
send(usrname)
test = D(r.recv().decode())
block2 = test[16:32]
block4 = test[48:64]
print(block2 == block4)
```
- Nhận được `True`, vậy là done :smile_cat:. Tuy nhiên nếu làm như trên thì chỉ thu được một phần `flag` nên mình sẽ thay đổi `usrname` đi sao cho `flag` được cover trong `block` nào đó.
- Code:
```python=
from pwn import *
from json import *
from base64 import b64decode as D

def send(msg):
    return r.sendline(msg)

r = remote('localhost', 2003)
LEN = 58
FLAG = ''
temp = ''
chars = string.ascii_lowercase + string.ascii_uppercase + '!_{}'

prefix = b'#' * (16 - len(b'Hello '))
sub =  b'  is your flag: '
for i in range(58):
    num = 58 - i
    sub = sub[1:] + temp.encode()
    suffix = b'#' * num
    for char in chars:
        usrname = prefix + sub + char.encode() + suffix
        send(usrname)
        get = D(r.recv().decode())
        block2 = get[16:32]
        block_real = get[96:112]
        if block2 == block_real:
            FLAG += char
            temp = char
            print(FLAG)

assert len(FLAG) == LEN
r.close()
print(FLAG)
```
- Giải thích code với trường hợp `i = 0`:
```python=
num = 58 - 0
prefix = b'Hello ' + b'#' * 10
sub = b' is your flag: K'
suffix = b'#' * num
test = prefix + sub + suffix + b', here is your flag: K. Have a good day, we hope to see you soon'

block2 = test[16:32]
block_real = test[96:112]
print(block2 == block_real)
```
### Flag
> ~~`KCSC{Chosen_Plaintext_Attack___ECB_ECB_ECB___you_made_it!}`~~
---
## Block Cipher 4: 2004_CBC
### Descrition
- Challenge code:
```python=
import socket
import threading
from Crypto.Cipher import AES
from os import urandom
import string


chars = string.ascii_lowercase + string.ascii_uppercase + string.digits + '_{}'
FLAG = b'KCSC{CBC_p4dd1ng_0racle_}'
assert all(i in chars for i in FLAG.decode())


def pad(msg, block_size):
    pad_len = 16 - len(msg) % block_size
    return msg + bytes([pad_len])*pad_len


def encrypt(key):
    iv = urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    return (iv + cipher.encrypt(pad(FLAG,16)) ).hex().encode()
    
    
def decrypt(enc,key):
    enc = bytes.fromhex(enc)
    iv = enc[:16]
    ciphertext = enc[16:]
    cipher = AES.new(key, AES.MODE_CBC, iv)
    decrypted = cipher.decrypt(ciphertext)
    pad_len = decrypted[-1]
    if all(i == pad_len for i in decrypted[-pad_len:]):
        return b'Decrypted successfully.'
    else:
        return b'Incorrect padding.'
    
    
class ThreadedServer(object):
    def __init__(self, host, port):
        self.host = host
        self.port = port
        self.sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
        self.sock.bind((self.host, self.port))

    def listen(self):
        self.sock.listen(5)
        while True:
            client, address = self.sock.accept()
            client.settimeout(60)
            threading.Thread(target = self.listenToClient,args = (client,address)).start()

    def listenToClient(self, client, address):
        size = 1024
        key = urandom(16)
        while True:
            try:
                choice = client.recv(size).strip()
                if choice == b'encrypt':
                    client.send(encrypt(key) + b'\n')
                elif choice == b'decrypt':
                    client.send(b'Ciphertext: ')
                    c = client.recv(size).strip().decode()
                    client.send(decrypt(c,key) + b'\n')
            except:
                client.close()
                return False


if __name__ == "__main__":
    ThreadedServer('',2004).listen()
```
### Solution
- Vì server có chức năng check padding PKCS#7 hợp lệ hay không nên mình sẽ sử dụng Padding Oracle Attack cho bài.
- Chi tiết thuật toán ở [đây](https://app.gitbook.com/o/ReP9yeC0bUTTA2QlLOpD/s/cdRw8tNOTeDBfoMGZBvR/padding-oracle-attack)
- Giải thích ngắn gọn:
```=
P[i] = D(C[i]) ^ C[i-1]
P'[i] = D(C[i]) ^ C'[i-1]
```
- Ta sẽ thay đổi `C[i-1]` thành `C'[i-1]` sao cho thỏa mãn PKCS#7 của server để tìm lại `D(C[i])` rồi xor với `C[i-1]` để tìm lại `P[i]`
- Code thử cho một byte cuối cùng:
```python=
from pwn import *

r = remote('localhost', 2004)
r.sendline(b'encrypt')
get = bytes.fromhex(r.recv().decode())
iv = get[:16]
block1 = get[16:32]
block2 = get[32:]

for i in range(256):
    fake = block1[:-1] + bytes([i])
    r.sendline(b'decrypt')
    r.recvuntil(b'Ciphertext: ')
    r.sendline(bytes.hex(iv + fake + block1).encode())
    get = r.recvuntil(b'\n')
    if b'Decrypted successfully.' in get:
        last = xor(b'\x01', i)
        print(xor(last, iv[-1:]))
        break
```
- Giải thích dòng 14 tại sao lại là `iv + fake + block1`:
    - Đơn giản vì `flag` được pad thành 32 bytes nên mình cần gửi 2 blocks.
    - `+ block1` chứ không phải là `+ block2` vì server sẽ thực hiện decrypt `iv + fake + block1`, mình đang thay đổi `fake` để tìm lại `block1` của flag. Chính vì vậy nên nếu có chạy cả 1 tỉ lần code trên thì output vẫn sẽ là `b'g'` (code sai thì output mỗi lần khác nhau)
- Tuy nhiên, cần lưu ý sau khi tìm được byte cuối của `block` trước, ta cần tiếp tục thay đổi byte đó sao cho thỏa PKCS#7 padding cho byte tiếp theo (Ví dụ tìm được byte thỏa `xor` thành `b'\x01'` thì cần thay nó thành một byte khác `xor` thành `b'\x02'`).
- Code (đã đổi tên các biến):
```python=
from pwn import *
from Crypto.Util.Padding import unpad

r = remote('localhost', 2004)
r.sendline(b'encrypt')
get = bytes.fromhex(r.recv().decode())
iv, temp = get[:16], get[16:]
blocks = [temp[:16], temp[16:32]]
flag = b''

for block in blocks:
    mod_pt = b''
    mod_ct = b'\x00'*16
    decrypted = b''
    for i in range(1, 17):
        for j in range(256):
            mod_ct = mod_ct[:-i] + bytes([j]) + mod_pt
            r.sendline(b'decrypt')
            r.recvuntil(b'Ciphertext: ')
            r.sendline(bytes.hex(iv + mod_ct + block).encode())
            get = r.recvuntil(b'\n')
            if b'Decrypted successfully.' in get:
                decrypted = xor(i, j) + decrypted
                mod_pt = xor(decrypted[-i:], bytes([i+1]*i))
                break
    flag += xor(decrypted, iv) if block == blocks[0] else xor(decrypted, blocks[0])

flag = unpad(flag, 16).decode()
print(flag)
```
### Flag
> ~~`KCSC{CBC_p4dd1ng_0racle_}`~~
### Note
- Phần tìm được 2 bytes cuối (trở đi) để ra `b'\x02\x02'` có thể khá khó hiểu nhưng [đoạn video này](https://youtu.be/8Tr2aj6JETg?si=qJwX08dcuD7oEuu_&t=180) giải thích bằng animation cực xịn :100:
- Giải thích dòng 26:
    - Xét mode CBC:
    ![Hình ảnh minh họa](https://hackmd.io/_uploads/BJiunO8s6.png)
    - Decrypted đầu tiên sẽ được xor với `iv` nên mình chỉ cần tìm `P1 = xor(decrypted, iv)`. Đến decrypted tiếp theo thì được xor với `C1` nên `P2 = xor(decrypted, C1)`. Ghép hai `P1` và `P2` nhận được flag.