{%hackmd @themes/orangeheart %}

# AES
## AES là gì?
AES là một hệ mật mã khối sử dụng riêng cho mã hóa dữ liệu điện tử, được công bố bởi NIST vào năm 2001. AES có các biến thể khóa là 128, 192 và 256-bit, bên cạnh đó, AES mã hóa dữ liệu với bản rõ 128-bit tạo thành bản mã 128-bit.

Với mỗi biến thể khóa lại có các chu trình khóa với số vòng khác nhau, trong đó AES-128 là 10 vòng, AES-192 là 12 vòng và AES-256 với số vòng là 14.
## Chu trình khóa của AES:
https://en.wikipedia.org/wiki/AES_key_schedule
Chu trình khóa của AES nhằm tạo ra các khóa $k_1,k_2,..k_n$ để đủ cho N vòng mã hóa, tùy theo từng biến thể của AES.

Số round tương ứng với keysize:

## Các bước mã hóa:
Mã hóa AES là mã hóa theo khối (Block Cipher), nên là pt sẽ được chia ra thành từng khối, thường thì mỗi khối sẽ có độ dài là 16bytes. AES sẽ chuyển khối ban đầu của bản rõ thành một ma trận 4x4:

[ b0 | b4 | b8 | b12 |
| b1 | b5 | b9 | b13 |
| b2 | b6 | b10| b14 |
| b3 | b7 | b11| b15 ]

Qua mỗi vòng, thì mỗi khối bản rõ sẽ phải trải qua 4 bước:
### 1. SubBytes
Trong bước này thì mỗi byte bị thay thế bởi byte khác tra cứu từ bảng [S-box](https://www.geeksforgeeks.org/what-is-s-box-substitution/). Kết quả sẽ là một ma trận 4x4 như ban đầu, nhưng các giá trị đã được thay đổi.
<img src="https://hackmd.io/_uploads/Hyjf77Nc1x.png" alt="drawing" style="width:600px;"/>
*Hình ảnh minh họa cho bước SubBytes.*

Code:

def sub_bytes(s):
    for i in range(4):
        for j in range(4):
            s[i][j] = s_box[s[i][j]]

### 2. ShiftRow
Bước này là bước dịch hàng. Quy luật dịch hàng như sau:
* Hàng đầu tiên giữ nguyên.
* Hàng thứ hai dịch trái một lần.
* Hàng thứ ba dịch trái hai lần.
* Hàng thứ tư dịch trái ba lần.

[ b0  | b1  | b2  | b3  ]         [ b0  | b1  | b2  | b3  ]
| b4  | b5  | b6  | b7  |    ->   | b5  | b6  | b7  | b4  |
| b8  | b9  | b10 | b11 |         | b10 | b11 | b8  | b9  |
[ b12 | b13 | b14 | b15 ]         [ b15 | b12 | b13 | b14 ]


Code:

def shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]

### 3. MixColumns
Dịch hàng xong thì trộn cột, sử dụng phép nhân ma trận. Mỗi cột được nhân với một ma trận đặc biệt (ma trận chuyển đổi) trong trường hữu hạn $GF(2^8)$. Kết quả trả về là một ma trận mới có cùng kích thước, tuy nhiên các bytes trong cột đã bị trộn lẫn.

*Ma trận chuyển đổi*

*Quá trình trộn cột và output*
Code:

def mix_single_column(a):
    t = a[0] ^ a[1] ^ a[2] ^ a[3]
    u = a[0]
    a[0] ^= t ^ xtime(a[0] ^ a[1])
    a[1] ^= t ^ xtime(a[1] ^ a[2])
    a[2] ^= t ^ xtime(a[2] ^ a[3])
    a[3] ^= t ^ xtime(a[3] ^ u)

def mix_columns(s):
    for i in range(4):
        mix_single_column(s[i])

### AddRoundKey
Ma trận dữ liệu sau bước 3 khi đến bước này sẽ được xor với roundkey được khởi tạo qua từng vòng. Vì sử dụng phép XOR nên phép biến đổi ngược của AddRoundKey trong cấu trúc giải mã cũng chính là AddRoundKey.

Code:

def add_round_key(s, k):
    for i in range(4):
        for j in range(4):
            s[i][j] ^= k[i][j]

## Nhận bản mã:
Trải qua các quá trình mã hóa, ta nhận được bản mã dưới dạng ma trận. Chuyển đổi matrix thành bytes, ta được bản mã thực sự
Code:

def matrix2bytes(matrix):
    return bytes(sum(matrix, []))

## Giải mã:
Tương ứng các khâu, ta có thể đảo ngược chu trình mã hóa:

# Block Cipher - Modes of Operation:
## Electronic Code Book (ECB):
Là chế độ mã hóa đơn giản nhất. Bản rõ được chia thành các khối đem đi mã hóa với khóa K. Mỗi mảnh pt ứng với một đoạn ct và ngược lại. Các khối được mã hóa riêng biệt và độc lập, vì thế với mỗi khối tin giống nhau sẽ được mã hóa thành những bản mã giống nhau. Để giải mã ECB, chỉ cần đảo ngược chu trình mã hóa.
Mặc dù điểm mạnh mà là nhanh, tiện lợi, mã hóa đồng thời được lượng lớn dữ liệu, nhưng vì thế mà nó kém an toàn vì có thể bị phân tích với bản rõ và bản mã liên hệ trực tiếp với nhau.
Tuy nhiên chế độ này thường được dùng trong mã hóa thông tin lưu trữ, ví dụ như các cơ sở dữ liệu vì nó cho phép từng đơn vị dữ liệu được mã hóa độc lập và do đó có thể cập nhật thay đổi dễ dàng từng phần mà không động chạm đến các phần khác của cơ sở dữ liệu.
## Cipher Block Chaining (CBC)
Là mode phổ biến nhất trong các Operation modes. Như tên gọi thì ở đây, trong thuật toán mã hóa đã có sự móc xích với nhau. Ở chế độ này thì mỗi bản rõ sẽ được xor với khối bản mã được encrypt trước đó, duy chỉ có ở khối mã đầu tiên thì sẽ được xor với một vector khởi tạo (iv). Khi giải mã, ta cần tìm ra được vector khởi tạo iv và khóa.
Nhờ sự móc xích, liên kết mà điểm mạnh của mã hóa CBC là sự an toàn và bảo mật cao hơn, cùng với đó là ngăn attacker có thể cắt xén mã truyền tin nhờ vào việc chỉ thay đổi bất kì bit nào trên các thành phần cũng có thể làm thay đổi toàn bộ bản mã. Khi so sánh với ECB, thay vì là được mã hóa tách biệt từng khối mã thì mỗi khối mã khi được mã hóa đều có sự liên kết với nhau, và các khối tin giống nhau khi đưa vào thì có thể tạo ra các khối mã khác nhau. Tuy nhiên, đối với một số bản rõ không toàn vẹn chia khối được thì cần thêm padding để có thể chia khối và mã hóa.
## Cipher Feedback Mode (CFB)
Mode này cũng sử dụng iv, nhưng có sự khác biệt so với CBC. IV được mã hóa với khóa k, đầu ra được chia thành hai bộ `s-bits` và `b-s bits`. Bộ `s-bits` được xor cùng phần bản mã P1 đầu tiên tạo thành C1, sau đó thì C1 sẽ tiếp tục được đưa vào mã hóa với khóa k tạo thành hai bộ `s-bits` và `b-s bits`. Ở đoạn input có bước `shift-register`, hoạt động bằng cách dịch trái 's-bits', nhờ thế mà một phần dữ liệu sau khi bị dịch bỏ thì khó có thể khôi phục được bằng cách phân tích mật mã. Tuy nhiên, điểm yếu lại là không thể mã hóa song song.
## Output Feedback Mode (OFM)
Xem xét thì nhận thấy rằng cách mã hóa của OFM có sự tương đồng so với CFB ở trên. Một IV được mã hóa ở bước đầu tiên, sau đó dùng output đó xor với P1 của bản rõ tạo ra C1. Output từ hàm encrypt trước trở thành input cho hàm encrypt sau, tiếp tục được xor với P2 để có được C2... Nhận thấy là ở đây, mã hóa đã trở nên riêng rẽ, không còn móc xích như hai chế độ mã hóa trước, nhưng output từ `encrypt` vẫn có sự móc xích với nhau.
Mode mã hóa trên sẽ có ích đối với việc tránh được lỗi bits, tuy nhiên thì lại dễ bị tấn công bởi stream modification attack
## Counter Mode (CTR)
Các giá trị `counter` được khởi tạo, mã hóa với hóa K, sau đó đem xor với các mảnh của bản rõ để thu được các bản mã. Sơ đồ mã hóa rất đơn giản nhưng hiệu quả tính toán lại cao. Nhờ việc có nhiều giá trị `counter` được tạo ra bằng bộ đếm và sử dụng trong mã hóa nên hạn chế sự liên quan trực tiếp giữa bản mã và bản rõ. Mã hóa song song được nhờ việc bước trước không liên quan hay ảnh hưởng đến bước sau. Tuy nhiên, vì thế mà phương pháp này yêu cầu sự đồng bộ cao giữa người gửi và nhận trong việc mã hóa, giải mã.

# Some attacking methods
## 1. Meet-in-the-middle
### Challenge ví dụ
>Thuật ngữ meet-in-the-middle trong giải thuật là một thuật toán tìm kiếm được sử dụng khi đầu vào nhỏ nhưng lớn hơn so với giới hạn vét cạn (brute force). Giống như thuật toán chia để trị, nó chia vấn đề thành hai nửa và giải quyết mỗi nửa trước khi hợp chúng lại. Độ phức tạp của thuật toán meet-in-the-middle tốt nhất là $O_(2^n/2 * n)$.

Trong Cryptography, thì [MITD](https://en.wikipedia.org/wiki/Meet-in-the-middle_attack) là một kiểu tấn công *Known-plaintext attack* chống lại những hệ thống mã hóa phụ thuộc vào việc biểu diễn dưới dạng bội 2 hoặc nhiều hàm mã hóa (giải mã). Meet-In-The-Middle Attack có thể giảm đáng kể số lần brute-force key so với brute-force theo cách thông thường. Phương thức tấn công trên thường được áp dụng vào các hệ thống được mã hóa bởi các thuật toán mã hóa nhiều lớp như Double DES hay Triple DES (Tham khảo tại [đây](https://www.geeksforgeeks.org/double-des-and-triple-des/)). Còn đối với AES cũng tương tự, nó sẽ chỉ hiệu quả đối với các thuật toán sử dụng Multiple AES, ví dụ như sau:

#!/usr/bin/env python3

from hashlib import sha256
from random import choices

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


with open('flag.txt', 'rb') as f:
    FLAG = f.read().strip()

chars = b'crew_AES*4=$!?'
L = 3

w, x, y, z = (
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
)

k1 = sha256(w).digest()
k2 = sha256(x).digest()
k3 = sha256(y).digest()
k4 = sha256(z).digest()

print(w.decode(), x.decode(), y.decode(), z.decode())

pt = b'AES_AES_AES_AES!'
ct = AES.new(k4, AES.MODE_ECB).encrypt(
         AES.new(k3, AES.MODE_ECB).encrypt(
             AES.new(k2, AES.MODE_ECB).encrypt(
                 AES.new(k1, AES.MODE_ECB).encrypt(
                     pt
                 )
             )
         )
     )

key = sha256(w + x + y + z).digest()
enc_flag = AES.new(key, AES.MODE_ECB).encrypt(pad(FLAG, AES.block_size))

with open('output.txt', 'w') as f:
    f.write(f'pt = {pt.hex()}\nct = {ct.hex()}\nenc_flag = {enc_flag.hex()}')  

Output:

pt = 4145535f4145535f4145535f41455321
ct = edb43249be0d7a4620b9b876315eb430
enc_flag = e5218894e05e14eb7cc27dc2aeed10245bfa4426489125a55e82a3d81a15d18afd152d6c51a7024f05e15e1527afa84b

Ở chall này thì rõ ràng là ta thấy rằng hàm mã hóa là 4 lần mã hóa AES ECB, mỗi lần đều sử dụng 1 key riêng biệt. Mục tiêu là khôi phục lại key để có thể giải mã.
Ở đây thì với bốn khóa con, mỗi khóa con có 3 ký tự từ 15 ký tự khả dụng, nếu tấn công vét cạn tổng số tổ hợp sẽ cần phải thử sẽ là rất lớn. Thay vào đó, MITM chia quá trình thành hai phần: mã hóa từ bản rõ và giải mã từ bản mã, sau đó tìm điểm gặp nhau ở giữa, giảm số tổ hợp khóa phải thử.
### Các bước thực hiện tấn công
#### Bước 1: Mã hóa từ bản rõ (pt)
* Tạo tất cả các tổ hợp 3 ký tự có thể cho (tạm gọi là `w`) từ tập hợp kí tự `crew_AES*4=$!?'`
* Với mỗi `w`, `tính k1 = SHA-256(w)`, rồi mã hóa `pt = AES_AES_AES_AES!` bằng với khóa `k1` để được kết quả `enc`. Lưu cặp `(enc, w)` vào một dict.
* Tiếp theo, với mỗi `enc` trong dict, tạo tất cả các tổ hợp 3 ký tự cho `x`, tính `k2 = SHA-256(x)`, rồi mã hóa`enc` bằng `k2` để được `enc2`.
* Lưu cặp `(enc2, w + x)` vào dict2. Dict2 này sẽ chứa tất cả các giá trị trung gian sau khi mã hóa 2 lớp.
#### Bước 2: Giải mã từ bản mã (ct)
* Tạo tất cả các tổ hợp 3 ký tự cho `z`, tính `k4 = SHA-256(z)`, rồi giải mã ct bằng `AES(k4)` để được kết quả `dec`. Lưu cặp `(dec, z)` vào dict3.
* Với mỗi giá trị của `dec` trong dict3, tạo tất cả các tổ hợp 3 ký tự cho `y`, tính `k3 = SHA-256(y)`, rồi giải mã `dec` bằng AES(k3) để được `dec2`.
* Lưu cặp (dec2, z + y) vào từ điển dict4.
#### Bước 3: Tìm điểm giao nhau
* So sánh các giá trị `dec2` trong dict4 với các giá trị `enc2` trong dict2. Nếu có giá trị trùng nhau, nghĩa là: `pt → AES(k1) → AES(k2) = ct → AES(k4)^(-1) → AES(k3)^(-1)`.
* Tại điểm này, ta tìm được bộ khóa đầy đủ: `(w, x, y, z)`.

### Code triển khai:

from hashlib import sha256
from itertools import product

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

pt = '4145535f4145535f4145535f41455321'
ct = 'edb43249be0d7a4620b9b876315eb430'
enc_flag = 'e5218894e05e14eb7cc27dc2aeed10245bfa4426489125a55e82a3d81a15d18afd152d6c51a7024f05e15e1527afa84b'
pt = bytes.fromhex(pt)
ct = bytes.fromhex(ct)
enc_flag = bytes.fromhex(enc_flag)

L = 3
chars = b'crew_AES*4=$!?'
char_keys = list(map(bytes, product(chars, repeat=L)))


def encrypt_aes(key, plaintext):
    return AES.new(key, AES.MODE_ECB).encrypt(plaintext)


def decrypt_aes(key, ciphertext):
    return AES.new(key, AES.MODE_ECB).decrypt(ciphertext)


def mitm():
    middle = {}

    for w in char_keys:
        k1 = sha256(w).digest()

        for x in char_keys:
            k2 = sha256(x).digest()
            enc = encrypt_aes(k2, encrypt_aes(k1, pt))
            middle[enc] = (w, x)

    for z in char_keys:
        k4 = sha256(z).digest()

        for y in char_keys:
            k3 = sha256(y).digest()
            dec = decrypt_aes(k3, decrypt_aes(k4, ct))

            if dec in middle:
                return middle[dec] + (y, z)


wxyz = mitm()
assert wxyz is not None, 'MITM attack failed'

w, x, y, z = wxyz

k1 = sha256(w).digest()
k2 = sha256(x).digest()
k3 = sha256(y).digest()
k4 = sha256(z).digest()

assert ct == encrypt_aes(k4, encrypt_aes(k3, encrypt_aes(k2, encrypt_aes(k1, pt)))), 'Wrong keys found'

key = sha256(b''.join(wxyz)).digest()
FLAG = unpad(decrypt_aes(key, enc_flag), AES.block_size)
print(FLAG.decode())

Flag: `crew{m1tm_at74cK_1s_g0lD_4nd_py7h0n_i5_sl0w!!}`

## 2. Chosen Plaintext Attack
Như tên, đây là phương thức tấn công sử dụng plaintext để exploit. Mục tiêu của CPA là tìm ra các thông tin về khóa mã hóa hay thuật toán để có thể giải mã các dữ liệu khác.
Cách hoạt động của CPA:
* Attacker chọn plaintext nhập vào, có quyền kiểm soát đầu vào (plaintext) đưa vào hệ thống mã hóa.
* Mã hóa dữ liệu: Hệ thống mã hóa văn bản thuần túy thành bản mã.
* Phân tích bản mã: Attacker quan sát đầu ra và cố gắng tìm ra quy luật hoặc thông tin về khóa mã hóa.

Ví dụ rõ ràng nhất và dễ hiểu nhất có lẽ chính là cách khai thác tấn công vào chế độ ECB của mã hóa AES. Ví dự thì như ở bài Extremely Convenient Breaker sau:

#!/usr/local/bin/python3

from Crypto.Cipher import AES
import os

key = os.urandom(16)
with open("flag.txt", "r") as f:
    flag = f.readline().strip()
cipher = AES.new(key, AES.MODE_ECB)

flag_enc = cipher.encrypt(flag.encode())
print("Here's the encrypted flag in hex: ")
print(flag_enc.hex())
print("Alright, lemme spin up my Extremely Convenient Breaker (trademark copyright all rights reserved). ")

while True:
    ecb = input("What ciphertext do you want me to break in an extremely convenient manner? Enter as hex: ")
    try:
        ecb = bytes.fromhex(ecb)
        if not len(ecb) == 64:
            print("Sorry, it's not *that* convenient. Make your ciphertext 64 bytes please. ")
        elif ecb == flag_enc:
            print("No, I'm not decrypting the flag. ")
        else:
            print(cipher.decrypt(ecb))
    except Exception:
        print("Uh something went wrong, please try again. ")

Vì chế độ mã hóa được sử dụng là ECB, từng khối 16bytes được mã hóa riêng lẻ không móc xích, vì thế mà ta có thể chia ct nhận về thành từng khối 16bytes, để đưa lên đánh lừa sever giải mã:
Bài không nhất thiết phải code full script vì chỉ cần chia chuỗi thành 4 phần, copy, lặp lại 4 lần rồi gửi đi nên mình sẽ chỉ code phần tách chuỗi:

def split_string(input_string):
    part_size = len(input_string) // 4  
    parts = [input_string[i:i + part_size] for i in range(0, len(input_string), part_size)]
    return parts

input_string = input()
parts = split_string(input_string)

for i, part in enumerate(parts, 1):
    print(f"Phần {i}: {part}")

## 3. Padding Oracle:
Đối với các mode AES, mã hóa thường cần chia bản rõ thành các khối với độ dài cố định. Vì thế trong trường hợp mà độ dài bản rõ không chia hết cho độ dài yêu cầu thì phần đệm là cần thiết. Ở đây chủ yếu thì mình sẽ đi sâu và CBC vì nó phổ biến nhất, các mode khác cũng có thể áp dụng tương tự.
Khái quát thì cách tấn công này như sau:
Trước khi thực sự đi sâu vào tìm hiểu về cách thức tấn công, ta cần tìm hiểu về PKCS#7 Padding.
### PKCS#7 Padding là gì?
Padding là thêm vào một lượng byte để cho khối bản rõ đạt đến một kích thước cố định. Nguyên tắc này quy định giá trị được sử dụng để lấp đầy vào khối bản rõ cuối cùng. Một cách tổng quát, nếu khối bản rõ cuối cùng còn cần phải lấp đầy thêm x byte để đạt được yêu cầu thì giá trị được điền đầy vào x byte này sẽ chính bằng x.
### Padding Oracle Attack
Phương thức tấn công này dựa vào 2 điểm yếu cơ bản:
* Phép xor ( $A \text{^} B = C -> B = A \text{^} C$ ).
* Phần padding được Server kiểm tra và đáp lại bằng việc phần Padding có đúng định dạng hay không, Do đó dựa vào tín hiệu hồi đáp này, ta có thể vét cạn và phát lại để xác định được khi nào thì Padding có giá trị là “1” (\x01) (Đây chính là Oracle).

Giả sử như sơ đồ mã hóa của CBC mode như trên. Thường thì với padding oracle attack sẽ là khôi phục ngược từ phải sang trái, cho nên sẽ bắt đầu với block 2.
* Trước tiên, ta sẽ lấy một ct mới (gọi là `ct1'`) sao cho `ct1'` chính là 15 bytes đầu của `ct1`, rồi sau đó thêm 1 byte (`new_byte`), ta sẽ có `ct1' ^ decrypt2 = pt2'`. Ở đây ta sẽ có: `ct1' = abcdefjhijklmno + new_byte`
* Giờ công việc sẽ là tìm giá trị `new_byte` sao cho `ct1[15]' ^ decrypt2[15] = \x01` để có thể unpad theo PKCS#7. Ở đây sẽ là tìm để `new_byte ^ 7 = \x01`
* Giờ ta có thể thu được `decrypt2[15] == \x01 ^ new_byte`. Tìm lại được giá trị của byte cuối decrypt2 tức 7.
* Tiếp theo, ta sẽ lấy `decrypt2[15] ^ ct1[15]` => thu được `pt2[15]`.
* Đến với `pt2[14]`, ta cần điều chỉnh để padding là `\x02\x02` thì ta lại lấy thêm 1 `ct1''` có chức năng tương tự với `ct1'`, nhưng ở đây sẽ mất đi 2 bytes cuối. Ta sẽ cần `ct1'' = ct1[:14] + new_byte + (decrypt2[15] ^ \x02)`
* Đến đây, tìm `new_byte` sao cho `new_byte ^ decrypt2[14] == \x02`. Tìm được `decrypt2[14]` và thu lại được `pt2[14]`.
Ví dụ với chall Pad Thai từ cryptohack như sau:

#!/usr/bin/env python3

from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from os import urandom

from utils import listener

FLAG = 'crypto{?????????????????????????????????????????????????????}'

class Challenge:
    def __init__(self):
        self.before_input = "Let's practice padding oracle attacks! Recover my message and I'll send you a flag.\n"
        self.message = urandom(16).hex()
        self.key = urandom(16)

    def get_ct(self):
        iv = urandom(16)
        cipher = AES.new(self.key, AES.MODE_CBC, iv=iv)
        ct = cipher.encrypt(self.message.encode("ascii"))
        return {"ct": (iv+ct).hex()}

    def check_padding(self, ct):
        ct = bytes.fromhex(ct)
        iv, ct = ct[:16], ct[16:]
        cipher = AES.new(self.key, AES.MODE_CBC, iv=iv)
        pt = cipher.decrypt(ct)  # does not remove padding
        try:
            unpad(pt, 16)
        except ValueError:
            good = False
        else:
            good = True
        return {"result": good}

    def check_message(self, message):
        if message != self.message:
            self.exit = True
            return {"error": "incorrect message"}
        return {"flag": FLAG}

    #
    # This challenge function is called on your input, which must be JSON
    # encoded
    #
    def challenge(self, msg):
        if "option" not in msg or msg["option"] not in ("encrypt", "unpad", "check"):
            return {"error": "Option must be one of: encrypt, unpad, check"}

        if msg["option"] == "encrypt": return self.get_ct()
        elif msg["option"] == "unpad": return self.check_padding(msg["ct"])
        elif msg["option"] == "check": return self.check_message(msg["message"])

import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13421)

Đây là một chall điển hình sử dụng Padding Oracle Attack điển hình với mã hóa CBC và có hàm `check_padding` trả về các giá trị `True` hoặc `False`.
Áp dụng phương thức tấn công:

from pwn import remote, xor
from json import loads, dumps
from tqdm import trange

io = remote('socket.cryptohack.org', 13421)
io.recv().decode()

def oracle(iv, ct):
    io.sendline(dumps({"option":"unpad", "ct": iv.hex()+ct.hex()}).encode())
    return b'true' in io.recv()

io.sendline(dumps({"option":"encrypt"}).encode())
out = bytes.fromhex(loads(io.recv())["ct"])
iv, ct = out[:16], out[16:]

def attack_block(padding_oracle, iv, c):
    r = bytes()
    for i in reversed(range(16)):
        s = bytes([16 - i] * (16 - i))
        for b in trange(256):
            iv_ = bytes(i) + xor(s, bytes([b]) + r)
            if padding_oracle(iv_, c):
                r = bytes([b]) + r
                break
    return xor(iv, r)

def attack(padding_oracle, iv, c):
    p = attack_block(padding_oracle, iv, c[0:16])
    for i in range(16, len(c), 16):
        p += attack_block(padding_oracle, c[i - 16:i], c[i:i + 16])
        print(p)
    return p

sol = attack(oracle, iv, ct)
io.sendline(dumps({"option":"check", "message": sol.decode()}).encode())
print(io.recv())

`Tham khảo tại: https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc/padding_oracle.py`
Ngoài ra, khi lang thang trên mạng thì mình còn tìm được một chương trình khác với hiệu suất nhanh hơn rất nhiều so với cách trên cho bài này. Tham khảo tại [đây](https://github.com/0awawa0/ptCrypt/blob/master/demos/Attacks/Symmetric/CBC/cryptohack_pad_thai.py). Còn đây là [thuật toán](https://github.com/0awawa0/ptCrypt/blob/master/ptCrypt/Attacks/Symmetric/CBC/CbcPkcs7PaddingOracleAttack.py) họ sử dụng.

## 4. Key-Recovery Attacks on GCM with Repeated Nonces
Là phương thức tán công nhắm đến chế độ GCM trong mã hóa AES. Trước tiên cần tìm hiểu 1 chút về GCM (hay còn là Galois/Counter Mode).
Thuật toán đầy đủ của GCM thì có thể xem tại đây.
### Galois/Counter mode hoạt động như thế nào?
Về bản chất, GCM là sự kết hợp giữa AES-CTR và Galois Mode (GMAC) nhằm tăng độ bảo mật và xác thực dữ liệu. Bản rõ ban đầu sẽ được mã hóa bằng AES-CTR, sau đó sẽ được tạo mã xác thực với Galois Mode, trả về ciphertext và Authentication Tag.
Với quá trình giải mã, mã xác thực sẽ được đưa vào để kiểm tra trước tiên (Tag Verification). Nếu mã xác thực hợp lệ, ciphertext sẽ được giải mã ở CTR mode.
### Cách thức tấn công Key-Recovery Attacks on GCM with repeated nonces
Cần hiểu Nonces đóng vai trò như thế nào trong chế độ mã hóa này. Nonce là một giá trị được sử dụng 1 lần cho mỗi khóa mã hóa. Nonces thường có độ dài 96bits (Theo tiêu chuẩn NISTS), được sử dụng để khởi tạo bộ đếm (Counter) trong quá trình mã hóa. Vì thế việc đảm bảo mỗi nonce là duy nhất rất quan trọng, vì nếu một nonce bị lặp lại với cùng một khóa, hệ thống sẽ trở nên dễ bị tấn công nghiêm trọng.
Để hiểu rõ hơn thì thuật toán GMAC như sau (Đọc kĩ và rõ hơn tại [đây](https://viblo.asia/p/cryptopals-set-8-abstract-algebra-challenge-63-66-m68Z0Wb9KkG)):

def gmac(key, msg, aad, nonce):
    '''
    Input:
        @key:   key to be encrypted/GMAC
        @msg:   message to be encrypted
        @aad:   additional associated data
        @nonce: 96-bit of nonce to XOR at the end
    '''
    authkey = AES_encrypt(key, b'\x00' * 16)
    authkey = GF2p128(int.from_bytes(authkey, 'big'))
    if msg is None:
        iv = encrypted = b''
    else:
        iv = generate_key(8)
        encrypted = iv + AES_encrypt(key, msg, 'ctr', iv)
    content = aad + b'\x00' * (-len(aad) % 16) + \
                encrypted + b'\x00' * (-len(encrypted) % 16) + \
                pack('>2Q', len(aad), len(encrypted))
    g = GF2p128(0)
    for i in range(0, len(content), 16):
        b = GF2p128(int.from_bytes(content[i : i + 16], 'big'))
        g += b
        g *= authkey
    s = AES_encrypt(key, nonce + b'\x00\x00\x00\x01')
    s = GF2p128(int.from_bytes(s, 'big'))
    g += s
    mac = int.to_bytes(g.val, 16, 'big')
    if msg is None:
        return mac
    else:
        return encrypted, mac

Sơ đồ đầy đủ của GCM:
> Chú thích về các thành phần sử dụng thì như trong ảnh

Ta biết rằng, trong trường hữu hạn $GF(2^{128})$ thì phép cộng trừ sẽ tương tự với phép xor. Tuy nhiên với phép nhân và chia sẽ tricky hơn chút:
>https://toadstyle.org/cryptopals/63.txt

1. Ta lấy 1 giá trị authentication key `h = E(k, b'\x00' * 16)`.
2. Đệm các byte 0 vào AD và ct cho đáp ứng yêu cầu về độ dài khối thì ta có khối như sau: `a0 || a1 || c0 || c1 || c2`.
3. Thêm một khối gồm ` len(AD) || len(C)`. Ta sẽ có `a0 || a1 || c0 || c1 || c2 || len(AD) || len(C)`
4. Đưa giá trị `h` và block vừa có được, chạy theo thuật toán sau:

g := 0
for b in bs:
    g := g + b
    g := g * h

Cuối cùng, ta sẽ thu được TAG `t = g + s` với `s := E(K, nonce || 1)`.
Ta có công thức tính giá trị TAG:
$t = (((((((((((h \cdot \text{AD0}) + \text{AD1}) \cdot h + \text{c0}) \cdot h + \text{c1}) \cdot h + \text{c2}) \cdot h + \text{len}) \cdot h + \text{s}$.
Viết gọn lại thì sẽ là: $t = a0.h^6 + a1.h^5 + c0.h^4 + c1.h^3 + c2.h^2 + len.h + s$.
Với độ dài thường gặp với pt là 32bytes tức sẽ có 2 khối bản mã 16bytes, ta rút gọn về với 2 giá trị c thì ta sẽ có:
\begin{align*}
t = ((((h \cdot \text{c0}) + \text{c1}) \cdot h + \text{len}) \cdot h + \text{s}
\end{align*}
hay chính là:
\begin{align*}
t = \text{c0} \cdot h^3 + \text{c1} \cdot h^2 + \text{len} \cdot h + \text{s}
\end{align*}
Với 2 giá trị $C_1$ và $C_2$, ta sẽ có hệ như sau:
\begin{align*}
t_1 = C_{10}h^3 + C_{11}h^2 + \text{len}.h + s \\
t_2 = C_{20}h^3 + C_{21}h^2 + \text{len}.h + s \\
\rightarrow t_1 + t_2 = (C_{10} + C_{20})h^3 + (C_{11} + C_{21})h^2
\end{align*}
(`s` và `len.h` đã biến mất vì phép cộng trong trường hữu hạn $GF(2^{128})$ cũng chính là phép xor)
Đến đây thì biết được giá trị $t_1 + t_2$ và các giá trị khác, sẽ dễ dàng tính được $h$.
Từ đó mà có thể tạo được authentication tag nào cho bất kì giá trị $C_3$ nào.
Code tấn công:

from sage.all import GF, PolynomialRing
from Crypto.Util.strxor import strxor
from Crypto.Util.number import long_to_bytes
from bitstring import Bits
from functools import reduce
import requests


def slice_and_pad(b_str, bsize=16):
    b_str += b"\0" * (len(b_str) % bsize)
    return [bytearray(b_str[k : k + bsize]) for k in range(0, len(b_str), bsize)]

def unhex_blocks(h_str, bsize=16):
    return slice_and_pad(bytes.fromhex(h_str), bsize)

def bytes_to_poly(block, a):
    return sum(a ** e for e, bit in enumerate(Bits(block)) if bit)

def poly_to_bytes(poly):
    return long_to_bytes(Bits(list(poly._vector_())).uint)


A = slice_and_pad(b"CryptoHack") #associated_data

C1 = unhex_blocks(
    (
        json := requests.get(
            f"http://aes.cryptohack.org/forbidden_fruit/encrypt/{b'give me the dlag'.hex()}"
        ).json()
    )["ciphertext"]
)
T1 = bytes.fromhex(json["tag"])
IV = bytes.fromhex(json["nonce"])

C2 = unhex_blocks(
    (
        json := requests.get(
            f"http://aes.cryptohack.org/forbidden_fruit/encrypt/{b'give me the elag'.hex()}"
        ).json()
    )["ciphertext"]
)
T2 = bytes.fromhex(json["tag"])
C3 = unhex_blocks(
    requests.get(
        f"http://aes.cryptohack.org/forbidden_fruit/encrypt/{b'give me the flag'.hex()}"
    ).json()["ciphertext"]
)

bit_len_plain = len(C1) // 2 * 8
bit_len_auth = len("CryptoHack") * 8
L = slice_and_pad(long_to_bytes((bit_len_auth << 64) | bit_len_plain))


T = strxor(T1, T2)
C = [strxor(a, b) for (a, b) in zip(C1, C2)]

F, a = GF(2 ** 128, name="a").objgen()
R, X = PolynomialRing(F, name="X").objgen()

Aa_p = [bytes_to_poly(block, a) for block in A]
C1_p = [bytes_to_poly(block, a) for block in C1]
T1_p = bytes_to_poly(T1, a)

C3_p = [bytes_to_poly(block, a) for block in C3]

A_p = [bytes_to_poly(bytearray(16), a)]
C_p = [bytes_to_poly(block, a) for block in C]
T_p = bytes_to_poly(T, a)

L_p = bytes_to_poly(L[0], a)


f1 = reduce(
    lambda poly, term: poly + term[1] * X ** term[0],
    list(reversed(list(enumerate(reversed(Aa_p + C1_p), start=2)))),
    L_p * X + T1_p,
)
f3 = reduce(
    lambda poly, term: poly + term[1] * X ** term[0],
    list(reversed(list(enumerate(reversed(Aa_p + C3_p), start=2)))),
    L_p * X,
)
p = reduce(
    lambda poly, term: poly + term[1] * X ** term[0],
    list(reversed(list(enumerate(reversed(A_p + C_p), start=2)))),
    T_p,
)

for root, _ in p.roots():
    EJ = f1(root)
    tag = poly_to_bytes(f3(root) + EJ)
    if "plaintext" in (
        j := requests.get(
            f"http://aes.cryptohack.org/forbidden_fruit/decrypt/{IV.hex()}/{b''.join(C3).hex()}/{tag.hex()}/{b'CryptoHack'.hex()}"
        ).json()
    ):
        print(bytes.fromhex(j["plaintext"]).decode())

Cách làm được tham khảo từ `https://blog.redrocket.club/2018/03/27/VolgaCTF-Forbidden/`
Flag: `crypto{https://github.com/attr-encrypted/encryptor/pull/22}`
# WRITEUP CRYPTOHACK : [SYMMETRIC CIPHER](https://hackmd.io/@deroise2306/rJx9oLPcJx)