Padding Oracle Attack

nc 103.69.194.137 6000
Source code
chall.py

from Crypto.Cipher import AES
from os import urandom
import string


chars = string.ascii_lowercase + string.ascii_uppercase + string.digits + '!_{}'
FLAG = b'KCSC{___}'
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()
    
    
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.'


if __name__ == '__main__':
    key = urandom(16)
    while True:
        choice = input()
        if choice == 'encrypt':
            print(encrypt(key))
        elif choice == 'decrypt':
            c = input('Ciphertext: ')
            try:
                print(decrypt(c,key))
            except:
                continue

Đọc qua source code có thể thấy Flag chỉ gồm kí tự chữ cái hoa,thường + kí tự số và !_{}
Flag được pad cho đủ khối rồi đem đi mã hóa bằng AES mode CBC

Vì IV và key đều random ,nên chúng ta không thể biết cũng không thể vét cạn .Brute forcing key của AES-128 là một nhiệm vụ rất khó khăn và tốn nhiều thời gian. Vì AES-128 sử dụng một khóa độ dài 128 bit, có tổng cộng 2^128 khóa khả dĩ. Điều này có nghĩa là số lượng khóa có thể có của AES-128 là rất lớn và khó có thể tìm ra khóa đúng bằng cách thử và sai một cách ngẫu nhiên.

Thời gian cần thiết để brute force một khóa AES-128 tùy thuộc vào số lượng khóa mà bạn muốn thử trong một giây, còn được gọi là "tốc độ thử". Nếu bạn có một tốc độ thử khóa rất nhanh, ví dụ như một triệu khóa mỗi giây, thì thời gian brute force để tìm ra khóa đúng có thể chỉ mất khoảng vài triệu năm.

Tuy nhiên, trong thực tế, việc brute force khóa AES-128 rất khó và thường được coi là không khả thi bởi vì một tốc độ thử khóa nhanh như vậy không thể đạt được bằng các phương pháp hiện tại của máy tính.

Vì không thể tìm được key nên không thể khái thác theo hướng này.Trong hàm decrypt có phần sử dụng để xác thực phần padding.Phần padding sẽ có dạng:

'\x01'
'\x02\x02'
'\x03\x03\x03'
'\x04\x04\x04\x04'
'\x05\x05\x05\x05\x05'
'\x06\x06\x06\x06\x06\x06'
'\x07\x07\x07\x07\x07\x07\x07'
'\x08\x08\x08\x08\x08\x08\x08\x08'
'\t\t\t\t\t\t\t\t\t'
'\n\n\n\n\n\n\n\n\n\n'
'\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b'
'\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c'
'\r\r\r\r\r\r\r\r\r\r\r\r\r'
'\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e'
'\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'

Sau một thời gian tìm kiếm,mình tìm được một kiểu tấn công có tên là Padding oracle attack

Trong mật mã đối xứng, cuộc tấn công oracle đệm có thể được áp dụng cho chế độ hoạt động CBC, trong đó "oracle" (thường là máy chủ) rò rỉ dữ liệu về việc liệu phần đệm của tin nhắn được mã hóa có chính xác hay không. Dữ liệu như vậy có thể cho phép những kẻ tấn công giải mã (và đôi khi mã hóa) tin nhắn thông qua oracle bằng cách sử dụng khóa của oracle mà không cần biết khóa mã hóa.
Việc triển khai tiêu chuẩn của giải mã CBC trong mật mã khối là giải mã tất cả các khối bản mã, xác thực phần đệm, xóa phần đệm PKCS7 và trả về văn bản thuần túy của tin nhắn. Nếu máy chủ trả về lỗi "đệm không hợp lệ" thay vì lỗi chung "giải mã không thành công", kẻ tấn công có thể sử dụng máy chủ như một oracle đệm để giải mã (và đôi khi mã hóa) message.

Công thức toán học để giải mã CBC là

$P_i$ =

$D_K(C_i)$

$\oplus$

$C_{i-1}$,

$C_0$ =

$IV$

Sau 7749 lần search tung gg để tìm code tấn công ,mình tìm được kha khá code Padding Oracle attack ,nhưng khi chạy thì nó lạ lắm :))

Bản chất của Padding Oracle attack là sửa đổi byte cuối cùng của khối bản mã trước đó, chúng ta có thể thay đổi byte cuối cùng của khối bản rõ cuối cùng.

Liệt kê 256 byte, chúng ta có thể tìm thấy thời điểm khi last_plain_text = 1. Oracle sẽ không báo lỗi trong trường hợp này, vì đó sẽ là phần đệm hợp lệ. Bằng cách quan sát thực tế đó, chúng ta có thể kết luận rằng X XOR last_byte_from_encryption_function = 1. Hoặc, last_byte_from_encryption_function = X XOR 1. Và điều này không cần biết khóa! Đây là một thực tế rất quan trọng vì bây giờ chúng ta có thể giải mã last plaintext byte, đó là: last_byte_from_encryption_function XOR original_last_byte_from_previous_ciphertext_block. Một lần nữa, sử dụng thông tin này, chúng ta có thể thay đổi byte cuối cùng từ khối bản mã trước đó sao cho byte cuối cùng của bản rõ của khối cuối cùng sẽ là 2. Và liệt kê tất cả các byte cuối cùng có thể có. Sử dụng phương pháp này, tất cả 16 byte plaintext có thể được khôi phục bằng cách sử dụng tối đa 256*16=4096 lệnh gọi tới 'oracle' .

Sau 1 khi chạy thử khác nhiều đoạn code khác nhau bug và fix bug cả tỉ lần vẫn không được,nhưng vẫn kiên trì không bỏ cuộc mình đã tìm được 1 trang cung cấp mã Padding Oracle attack chạy được và mình đã modify để solve challenge này ,rất may là đã chạy thành công :))

Trong qua trình giải mã plaintext chúng ta sẽ bắt đầu từ khối cuối cùng ,ở challenge này khi gửi option encrypt chúng ta sẽ nhận được 1 dãy hex dài 96 kí tự (48 byte),trong đó 16 byte đầu là IV,còn lại là ciphertext .

Chia ra thành 2 block(16 byte mỗi cái),sau đó sẽ tiến hành giải mã từ khối cuối cùng đầu tiên ,các khối sau đó tiếp tục ,nhưng ở đây chỉ có 2 block thôi.

Ta sẽ thay thế từng byte cuối trong khối lần lượt từ 0 đến 255 (tương đương 00 đến ff).Sau đó gửi khối mã đã sửa lại cho oracle .Hàm check_padding sẽ dùng hàm decrypt để xác thực xem phần pad có đúng không và sẽ khôi phục plaintext theo từng byte một,từ cuối trở về đầu.

Dưới đây là script ,vì đoạn mã tương đối phức tạp ,tên biến khá dài rối mắt nên mình sẽ giữ nguyên comment của tác giả cho dễ hiểu.

solve.py

from Crypto.Cipher import AES
from pwn import *
import copy
host = '103.69.194.137'
port = 6000
conn = remote(host, port)


def xor_two_bytes(b1, b2):
    return bytes(a ^ b for a, b in zip(b1, b2))

def put_to_bytes(buf, buf_idx, new_buf):
    for i in range(len(new_buf)):
        buf[buf_idx+i]=new_buf[i]

def int_to_bytes(i):
    return i.to_bytes(1, byteorder="big")

def check_padding(ciphertext):
    conn.sendline(b'decrypt')
    conn.recvuntil(b'Ciphertext:')
    conn.sendline(ciphertext)
    out = conn.recvline().decode()
    if 'Decrypted successfully.' in out:
        return True
    return False 

oracle_calls=0

# in bytes
AES_BLK_SIZE=16

# prev_cblk_last_byte_idx: index of the last byte in ciphertext of previous block. Then it decrements (during recursion)
# assumed_last_plaintext_bytes: most probable bytes of plaintext, grows
# last_blk_known_outs: known bytes that last encryption function (AES) outputs in the last block, grows
# search_for: padding byte we're looking for, starting at 0x01, up to 0x10 (increased during recursion)
def try_padding_bytes(prev_cblk_last_byte_idx, buf, assumed_last_plaintext_bytes, last_blk_known_outs, search_for):
    global oracle_calls
    print ("plaintext_bytes=", assumed_last_plaintext_bytes)
    if len(assumed_last_plaintext_bytes)==AES_BLK_SIZE:
        return True # stop
    assert prev_cblk_last_byte_idx>=0
    last_byte_prev_cblk=buf[prev_cblk_last_byte_idx]

    buf_to_try=copy.deepcopy(buf)
    # try padding byte:
    for i in range(256):
        # First I tempted to write this. But this was a mistake. Do not skip byte even if you don't modify buf.
        # So I'm leaving this commented, just to remember:
        #if buf[prev_cblk_last_byte_idx]==i:
        #    continue
        buf_to_try[prev_cblk_last_byte_idx]=i
        rt = check_padding(binascii.hexlify(buf_to_try))
        oracle_calls=oracle_calls+1
        if rt == True:
            #print ("success with pad byte 0x%02x" % i)
            # At this point we know that the last plain blk is either ... 01
            #                                                or    ... 02 02
            #                                                or ... 03 03 03
            #                                                ...
            #                                                or    10 ... 10 (16 bytes)

            # assume last plain byte is $search_for$:
            last_byte_after_last_dercypt=i ^ search_for
            #print ("last_byte_after_last_dercypt: 0x%02x" % last_byte_after_last_dercypt)
            last_plain_byte=last_byte_prev_cblk ^ i ^ search_for
            #print ("last plain byte: 0x%02x" % last_plain_byte)
            last_blk_known_outs_new=int_to_bytes(last_byte_after_last_dercypt) + last_blk_known_outs
            # Prepare a new buf for recursive call (so to preserve our current buf as is):
            buf2=copy.deepcopy(buf)
            new_prev_blk=xor_two_bytes(last_blk_known_outs_new, len(last_blk_known_outs_new)*int_to_bytes(search_for+1))
            put_to_bytes(buf2, len(buf)-AES_BLK_SIZE-len(new_prev_blk), new_prev_blk)
            if try_padding_bytes(prev_cblk_last_byte_idx-1, buf2, int_to_bytes(last_plain_byte)+assumed_last_plaintext_bytes, last_blk_known_outs_new, search_for+1):
                return True # stop
    return False # continue

# blk_n=-1 for the last block
# blk_n=-2 for the penultimate block
# etc
# ... like in Python: s[-1] is the last character, s[-2] - penultimate character
def decrypt_blk(buf, blk_n):
    print ("decrypt_blk", blk_n)
    # Find last byte of previous blk:
    prev_cblk_last_byte_idx=(len(buf)+blk_n*AES_BLK_SIZE)-1
    if blk_n==-1:
        rt=try_padding_bytes(prev_cblk_last_byte_idx, buf, b"", b"", 1)
    else:
        # Also slice buf to remove unneded blocks at the end we don't want to handle:
        rt=try_padding_bytes(prev_cblk_last_byte_idx, buf[:(blk_n+1)*AES_BLK_SIZE], b"", b"", 1)

    if rt==False:
        print ("Error. Can't find anything in this block.")

conn.sendline(b'encrypt')
buf = conn.recvline().rstrip(b'\n').decode()
print(buf)
buf = bytes.fromhex(buf)
print(buf)
buf = bytearray(buf)
print(buf)
# Try to decrypt last 3 blocks:
decrypt_blk(buf, -1)
decrypt_blk(buf, -2)
#decrypt_blk(buf,-3)
print ("oracle_calls=", oracle_calls)

Sau khi chạy vài phút thu được kết quả:

[x] Opening connection to 103.69.194.137 on port 6000
[x] Opening connection to 103.69.194.137 on port 6000: Trying 103.69.194.137
[+] Opening connection to 103.69.194.137 on port 6000: Done
416354f30a4458202289a3730f7f8780653226db0e7dcf70605cb4d2fa2b9432a117d25b8f13ccc0fcc1f87bac2f84de
b'AcT\xf3\nDX "\x89\xa3s\x0f\x7f\x87\x80e2&\xdb\x0e}\xcfp`\\\xb4\xd2\xfa+\x942\xa1\x17\xd2[\x8f\x13\xcc\xc0\xfc\xc1\xf8{\xac/\x84\xde'
bytearray(b'AcT\xf3\nDX "\x89\xa3s\x0f\x7f\x87\x80e2&\xdb\x0e}\xcfp`\\\xb4\xd2\xfa+\x942\xa1\x17\xd2[\x8f\x13\xcc\xc0\xfc\xc1\xf8{\xac/\x84\xde')
decrypt_blk -1
plaintext_bytes= b''
plaintext_bytes= b'\x01'
plaintext_bytes= b'\x05'
plaintext_bytes= b'\x05\x05'
plaintext_bytes= b'\x05\x05\x05'
plaintext_bytes= b'\x05\x05\x05\x05'
plaintext_bytes= b'\x05\x05\x05\x05\x05'
plaintext_bytes= b'}\x05\x05\x05\x05\x05'
plaintext_bytes= b'k}\x05\x05\x05\x05\x05'
plaintext_bytes= b'Ck}\x05\x05\x05\x05\x05'
plaintext_bytes= b'aCk}\x05\x05\x05\x05\x05'
plaintext_bytes= b'naCk}\x05\x05\x05\x05\x05'
plaintext_bytes= b'5naCk}\x05\x05\x05\x05\x05'
plaintext_bytes= b'_5naCk}\x05\x05\x05\x05\x05'
plaintext_bytes= b'3_5naCk}\x05\x05\x05\x05\x05'
plaintext_bytes= b'l3_5naCk}\x05\x05\x05\x05\x05'
plaintext_bytes= b'cl3_5naCk}\x05\x05\x05\x05\x05'
plaintext_bytes= b'4cl3_5naCk}\x05\x05\x05\x05\x05'
decrypt_blk -2
plaintext_bytes= b''
plaintext_bytes= b'r'
plaintext_bytes= b'1r'
plaintext_bytes= b'M1r'
plaintext_bytes= b'_M1r'
plaintext_bytes= b'9_M1r'
plaintext_bytes= b'n9_M1r'
plaintext_bytes= b'1n9_M1r'
plaintext_bytes= b'd1n9_M1r'
plaintext_bytes= b'dd1n9_M1r'
plaintext_bytes= b'udd1n9_M1r'
plaintext_bytes= b'Pudd1n9_M1r'
plaintext_bytes= b'{Pudd1n9_M1r'
plaintext_bytes= b'C{Pudd1n9_M1r'
plaintext_bytes= b'SC{Pudd1n9_M1r'
plaintext_bytes= b'CSC{Pudd1n9_M1r'
plaintext_bytes= b'KCSC{Pudd1n9_M1r'
oracle_calls= 3754
[*] Closed connection to 103.69.194.137 port 6000

Để thu được bản gốc 32 bytes oracle được gọi 3754 lần.

Flag: KCSC{Pudd1n9_M1r4cl3_5naCk}