# AES
## Nền tảng
### Trường $GF(2^8)$
Trước khi tìm hiểu về AES, ta phải hiểu rằng AES hoạt động trong một trường riêng biệt, gọi là Trường Galios $GF(2^8)$. Đây là trường hữu hạn có $2^8 = 256$ phần tử.
Trong $GF(2^8)$ , mỗi phần tử không được xem là một con số mà được coi là một đa thức (polynomial), **có bậc tối đa là 7** và có những tính chất sau:
- Các hệ số đa thức chỉ có 2 giá trị: 0 hoặc 1.
- Một đa thức có 8 bit $a_7a_6a_5a_4a_3a_2a_1a_0$ sẽ được biểu diễn dưới dạng $a_7.x^7 + a_6.x^6 + a_5.x^5 + a_4.x^4 + a_3.x^3 + a_2.x^2 + a_1.x + a_0$
- Ví dụ byte `0xF2` được biểu diễn ở dạng nhị phân là `1111 0010`. Vậy trong trường $GF(2^8)$ nó sẽ được biển diễn thành: $1.x^7 + 1.x^6 + 1.x^5 + 1.x^4 + 0.x^3 + 0.x^2 + 1.x + 0$ = $x^7 + x^6 + x^5 + x^4 + x$.
**Kết luận**: mọi byte trong AES (trong State, trong key) đều được coi là một đa thức.
### Các phép toán trong $GF(2^8)$:
Vì ta đang tính toán trên trường $GF(2^8)$ nên phép cộng và phép nhân cũng sẽ khác với thông thường, cụ thể:
- Phép cộng: chính là phép **XOR**
- 0 + 0 = 0
- 0 + 1 = 1
- 1 + 0 = 1
- 1 + 1 = 0.
- Khi ta cộng 2 byte (2 đa thức), thực chất là ta đang **XOR** giữa các hệ số tương ứng với nhau:
- Ví dụ cộng 2 byte `0x57` và `0x83`: `0x57` + `0x83` = `01010111` + `10000011` = `11010100` = `0xD4`
- Phép nhân: Ta vẫn tiến hành nhân 2 đa thức như thông thường nhưng phải chia lấy dư, và nhớ rằng phép cộng là phép XOR.
- Ví dụ: nhân 2 đa thức $(x+1) \times (x^2+1) = x^3 + x^2 + x + 1$
- **Vấn đề**: nếu bậc của đa thức cuối cùng > 7 thì sao?. Nhớ rằng trường $GF(2^8)$ chỉ có thể biểu dẫn đa thức có bậc tối đa là 7, vậy ta phải chia dư đi cho một đa thức $m(x) =x^8+x^4+x^3+x+1$ được quy định sẵn trong AES để có thể khiến bậc của nó giảm xuống nhỏ hơn 7
- Ví dụ cho đa thức $a(x) = x^6 + x^4 + x + 1 =$ `0x53` và $b(x) = x^5 + x^2 + 1$ = `0x25`. Tiến hành nhân $a(x)$ với $b(x)$: $$a(x)\cdot b(x)=x^{11}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1.$$
- Ta thấy bậc lớn nhất = 11 > 7 nên phải chia dư đa thức trên cho $m(x)$ .
- Phần dư ta thu được là $r(x)=x^7 + x^3 + x.$ = `0x8A` (Ta có thể viết gọn lại là (0x53)⋅(0x25) mod m(x) = 0x8A)
### Rijndael S-box
Rijndael S-box là một bảng tra cứu cố định được sử dụng trong AES, giá trị `S-box[B]` được tính bằng 2 bước:
- Bước 1: Tìm một byte $B^{-1}$ sao cho $B. B^{-1} = 1$ trong $GF(2^8)$, điều này có nghĩa là đa thức của byte $B$ nhân với đa thức của $B^{-1}$ mod cho $m(x)$ phải = 1.
- Ví dụ $B = 0x57$ => $B^{-1} = 0xCA$
> Trường hợp byte `0x00` sẽ không có nghịch đảo nên người ta quy định `S-box[0x00]` = `0x00`
- Bước 2: Thực hiện biến đổi Affine (nhân ma trận + XOR)
- Ta lấy 8 bit của $B^{-1}$ (ký hiệu từ $b_0...b_7$) và tính toán nên 8 bit mới (ký hiệu là $b^{'}_0...b^{'}_7$)
- Về cơ bản, nó thực hiện phép nhân ma trận trong $GF(2)$
$$
\begin{bmatrix}
b'_0 \\ b'_1 \\ b'_2 \\ b'_3 \\ b'_4 \\ b'_5 \\ b'_6 \\ b'_7
\end{bmatrix} =
\begin{bmatrix}
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 1 & 1 & 1
\end{bmatrix} \times \begin{bmatrix}
b_0 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ b_7
\end{bmatrix}
$$
* $b'_0 = b_0 \oplus b_4 \oplus b_5 \oplus b_6 \oplus b_7$
* $b'_1 = b_0 \oplus b_1 \oplus b_5 \oplus b_6 \oplus b_7$
* $b'_2 = b_0 \oplus b_1 \oplus b_2 \oplus b_6 \oplus b_7$
* ....
* $b'_i = b_i \oplus b_{(i+4) \bmod 8} \oplus b_{(i+5) \bmod 8} \oplus b_{(i+6) \bmod 8} \oplus b_{(i+7) \bmod 8}$
- Sau đó tiến hành XOR các bit mới vừa tính được với một hằng số cố định $c$ có giá trị là `0x63` = `01100011`.
- Kết quả cuối cùng: $s_i = b'_i \oplus c_i$
- Trong đó $c_i$ là các bit của `0x63`.
* $s_0 = b'_0 \oplus 1$
* $s_1 = b'_1 \oplus 1$
* $s_2 = b'_2 \oplus 0$
* $s_3 = b'_3 \oplus 0$
* $s_4 = b'_4 \oplus 0$
* $s_5 = b'_5 \oplus 1$
* $s_6 = b'_6 \oplus 1$
* $s_7 = b'_7 \oplus 0$
Ta nhận thấy rằng để tính được bảng S-box cần những phép tính rất phức tạp, sẽ rất tốn kém nếu mỗi lần mã hóa AES đều cần tính lại bảng này, do đó người ta đã tính sẵn 256 giá trị và lưu vào một bảng tra cứu cố định:
- Ví dụ: `0x19` sẽ tương ứng với hàng `10` cột `09`, tương đương với `0xd4`
### Rcon (Round Constant - Hằng số vòng)
Rcon là một hằng số được dùng trong quá trình **KeyExpansion** (mình sẽ nói rõ ở phần sau), Rcon được dùng để phá vỡ tính đối xứng giữa các khóa con ở mỗi vòng (đảm bảo RoundKey ở mỗi vòng sẽ khác nhau)
Rcon là một mảng 4 byte, nhưng chỉ byte đầu tiên có giá trị, nó được định nghĩa như sau:
$$Rcon[i] = [x^{i-1}, 0, 0, 0]$$
- Trong đó $x^{i-1}$ được tính trong $GF(2^8)$
- `Rcon[1]` = $x^{1-1} = 1 =$ `0x01`
- `Rcon[2]` = $x^{1} = x =$ `0x02`
- `Rcon[3]` = $x^{2} = x^2 =$ `0x04`
- ...
- `Rcon[9]` = $x^{8}\pmod {m(x)} = x^4 + x^3 + x + 1 =$ `0x1B`
- `Rcon[10]` = `0x36`
## Cách hoạt động
AES là một mã khối (block cipher). Nó không mã hóa từng bit một, mà chia dữ liệu thành các khối có kích thước cố định, gọi là block và có kích thước luôn là 128 bit, rồi xử lý từng khối bằng thuật toán mã hóa.
Đối với thuật toán mã hóa AES:
- Độ dài của **input block**, **output block** luôn là một khối 128 bit.
- Độ dài của **key bí mật** có thể là **128, 192, hoặc 256 bits.**. Và tương ứng với mỗi độ dài của key, ta sẽ có số vòng được lặp lại khác nhau:
Hình minh họa quá trình mã hóa và giải mã của AES:
Mình sẽ chọn:
- `Plaintext: 00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff`
- ` Key: 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f`
Giờ hãy cùng phân tích cụ thể cách mà AES-128 hoạt động.
### Encryption
Plaintext đầu vào có 128 bits, tức 16 byte và sẽ được chia ra làm 16 phần sau đó được nạp vào ma trận `State` 4x4 để bắt đầu các quá trình mã hóa
$$
State =
\begin{bmatrix}
00 & 44 & 88 & cc \\
11 & 55 & 99 & dd \\
22 & 66 & aa & ee \\
33 & 77 & bb & ff
\end{bmatrix}
$$
#### KeyExpansion
Quá trình này sẽ tạo **11** **Round keys** (khóa vòng) từ khóa bí mật ban đầu mà ta chọn, chúng ta phải tạo 11 Round keys vì ngoài việc sử dụng 10 Round keys cho vòng lặp tính toán thì ta cần 1 Round keys cho bước `AddRoundKey` ban đầu nữa.
- Các Round keys thứ `i` cũng được coi là một ma trận 4x4 được ký hiệu là `Roundkey[i]`
$$Roundkey = \begin{bmatrix}
K_{0,0} & K_{0,1} & K_{0,2} & K_{0,3} \\
K_{1,0} & K_{1,1} & K_{1,2} & K_{1,3} \\
K_{2,0} & K_{2,1} & K_{2,2} & K_{2,3} \\
K_{3,0} & K_{3,1} & K_{3,2} & K_{3,3}
\end{bmatrix}$$
Và để tiện cho việc tính toán thì người ta ký hiệu mỗi **cột** trong một `Roundkey` là một `word`. Vậy tương ứng thì mỗi `word` sẽ có 4 byte, và vì ta có tổng cộng 11 `Roundkey` nên ta sẽ có 44 `word`
- Với ma trận trên thì ta được:
- `word[0] = [K0,0, K1,0, K2,0, K3,0]`
- `word[1] = [K0,1, K1,1, K2,1, K3,1]`
- `word[2] = [K0,2, K1,2, K2,2, K3,2]`
- ` word[3] = [K0,3, K1,3, K2,3, K3,3]`
Ta khởi tạo như sau:
- 4 word đầu tiên (từ `w[0]` đến` w[3]`) chính bằng khóa bí mật ban đầu. Đây chính là `Roundkey[0]`
- `word[0] = [00, 01, 02, 03]`
- `word[1] = [04, 05, 06, 07]`
- `word[2] = [08, 09, 0a, 0b]`
- ` word[3] = [0c, 0d, 0e, 0f]`
Với các `word[i]` (với i từ 4 đến 43) tiếp theo: w[i] = **w[i-4] $\oplus$ temp**. Với `temp = w[i-1]`.
- **Trong trường hợp đặc biệt** Nếu `word[i]` là **word đầu tiên** trong một `Roundkey` nào đó (hay nói cách khác là **i chia hết cho 4**), cụ thể trong trường hợp muốn tính `word[4]` ta sẽ thực hiện 5 bước:
- Gán `temp = w[i-1] = w[3]` =$\begin{bmatrix}
0c\\ 0d\\ 0e\\ 0f
\end{bmatrix}$
- `RotWord(temp)`: dịch tất cả 4 byte trong `temp` lên trên 1 vị trí:
$$
temp = \begin{bmatrix}
0c\\ 0d\\ 0e\\ 0f
\end{bmatrix}
\overset{RotWord}{\rightarrow}
\begin{bmatrix}
0d\\
0e\\
0f\\
0c\\
\end{bmatrix}$$
- Sau đó `SubWord(temp)`: Áp dụng S-box (bảng tra cứu mà ta đã tính ở phần trước) cho từng byte trong word[i-1]:
$$
temp = \begin{bmatrix}
0d\\
0e\\
0f\\
0c\\
\end{bmatrix}
\overset{S-box}{\rightarrow}
\begin{bmatrix}
d7\\ ab\\ 76 \\ fe
\end{bmatrix}$$
- Tiến hành `XOR Rcon`: XOR **byte đầu tiên** của `temp` với giá trị **Rcon** tương ứng (`Rcon[i/4]`)
$$temp = temp \oplus Rcon[1]$$
$$ temp = \begin{bmatrix}
d7 \\[4pt]
ab \\[4pt]
76 \\[4pt]
fe
\end{bmatrix} \oplus\begin{bmatrix} 01 \\[4pt] 00 \\[4pt] 00 \\[4pt] 00 \end{bmatrix} = \begin{bmatrix} d6 \\[4pt] ab \\[4pt] 76 \\[4pt] fe \end{bmatrix}$$
- Tính `word[4]` = **word[0] $\oplus$ temp**
$$
word[4] =
\begin{bmatrix}
d6 \\[4pt]
ab \\[4pt]
76 \\[4pt]
fe
\end{bmatrix}
\oplus
\begin{bmatrix}
00 \\[4pt]
01 \\[4pt]
02 \\[4pt]
03
\end{bmatrix}
=
\begin{bmatrix}
d6 \\[4pt]
aa \\[4pt]
74 \\[4pt]
fd
\end{bmatrix}
$$
- **Trường hợp bình thường** thì `temp = w[i-1]` nên `w[i]` = `w[i-4]` $\oplus$ `w[i-1]`
Ta cứ tính như vậy cho đến `w[43]` thì đã đủ 11 `Roundkey`.
**Tại sao lại phải phức tạp như vậy?** Việc dùng S-box và Rcon trong việc tạo khóa là để ngăn chặn các cuộc tấn công liên quan đến khóa (related-key attacks). Nó đảm bảo các `Roundkey` không có mối liên hệ tuyến tính đơn giản với nhau.
#### Pre-Round
Đây là vòng ban đầu, trước khi tính toán thì ta sẽ chuyển Plaintext thành ma trận `State`
Thực hiện `AddRoundKey(State, RoundKey[0]`):
- XOR từng byte giữa hai ma trận này với nhau:
$$\underset{State}{\underbrace{\begin{bmatrix}
00 & 44 & 88 & cc \\
11 & 55 & 99 & dd \\
22 & 66 & aa & ee \\
33 & 77 & bb & ff
\end{bmatrix}}}
\bigoplus
\underset{RoundKey[0]}{\underbrace{\begin{bmatrix}
00 & 04 & 08 & 0c \\
01 & 05 & 09 & 0d \\
02 & 06 & 0a & 0e \\
03 & 07 & 0b & 0f \\
\end{bmatrix}}}
=
\begin{bmatrix}
00 & 40 & 80 & c0 \\
10 & 50 & 90 & d0 \\
20 & 60 & a0 & e0 \\
30 & 70 & b0 & f0 \\
\end{bmatrix}$$
Sau khi thực hiện bước này xong thì dữ liệu sẽ được tính toán bằng 10 vòng lặp, mỗi vòng sẽ thực hiện các quá trình: SubBytes, ShiftRows, MixColumns, AddRoundKey.
#### SubBytes
Mỗi byte trong `State` sẽ được thay thế tương ứng với giá trị của nó khi tra cứu trong bảng **S-box**:
Ta sẽ `SubBytes` ma trận State vừa tính được ở trên:
$$
\begin{bmatrix}
00 & 40 & 80 & c0 \\
10 & 50 & 90 & d0 \\
20 & 60 & a0 & e0 \\
30 & 70 & b0 & f0
\end{bmatrix}
\longrightarrow
\begin{bmatrix}
63 & 09 & cd & ba \\
ca & 53 & 60 & 70 \\
b7 & d0 & e0 & e1 \\
04 & 51 & e7 & 8c
\end{bmatrix}
$$
#### ShiftRows
Tiến hành dịch các bytes trong hàng của ma trận qua trái theo nguyên tắc:
- Hàng đầu tiên: Không thay đổi
- Hàng thứ 2: Dịch qua trái 1 lần
- Hàng thứ 3: Dịch qua trái 2 lần
- Hàng thứ 4: Dịch qua trái 3 lần
Vậy áp dụng cho ma trận $\begin{bmatrix}
63 & 09 & cd & ba \\
ca & 53 & 60 & 70 \\
b7 & d0 & e0 & e1 \\
04 & 51 & e7 & 8c
\end{bmatrix}$
- `Row[0]: [63,09,cd,ba] → [63,09,cd,ba]`
- `Row[1]:[ca,53,60,70] → [53,60,70,ca]`
- `Row[2]:[b7,d0,e0,e1] → [e0,e1,b7,d0]`
- `Row[3]:[04,51,e7,8c] → [8c,04,51,e7]`
Vậy sau bước này ta thu được ma trận: $$\begin{bmatrix}
63 & 09 & cd & ba \\
53 & 60 & 70 & ca \\
e0 & e1 & b7 & d0 \\
8c & 04 & 51 & e7
\end{bmatrix}$$
#### MixColumns
Thực hiện nhân từng cột ma trận State với một ma trận [$C$](https://en.wikipedia.org/wiki/Rijndael_MixColumns) được xây dựng từ các hệ số của đa thức $c(x) = 03x^3 + 01x^2 + 01x + 02$, và được định nghĩa như sau:
$$C = \begin{bmatrix}
02 & 03 & 01 & 01 \\
01 & 02 & 03 & 01 \\
01 & 01 & 02 & 03 \\
03 & 01 & 01 & 02 \\
\end{bmatrix}$$
- Trong đó mọi phép toán là **trên trường $GF(2^8)$**, nghĩa là:
+ Phép cộng là phép XOR,
- Phép nhân → phép nhân đa thức modulo $m(x) = x^8 + x^4 + x^3 + x + 1$.
Nếu ta triển khai phép nhân ($c(x) \cdot S(x)$), ta thu được quan hệ tuyến tính giữa 4 byte đầu ra và 4 byte đầu vào:
$$\begin{bmatrix}
s'_0 \\ s'_1 \\ s'_2 \\ s'_3
\end{bmatrix} = \begin{bmatrix}
02 & 03 & 01 & 01 \\
01 & 02 & 03 & 01 \\
01 & 01 & 02 & 03 \\
03 & 01 & 01 & 02
\end{bmatrix}\begin{bmatrix}
s_0 \\ s_1 \\ s_2 \\ s_3
\end{bmatrix}
$$
- Ví dụ hàng đầu tiên:
$$s'_0 = (02 \cdot s_0) \oplus (03 \cdot s_1) \oplus (01 \cdot s_2) \oplus (01 \cdot s_3)
$$
- Trong đó:
+ $02 \cdot s_i$: là phép nhân trong $GF(2^8)$, tương đương "nhân x" (dịch trái 1 bit, nếu tràn 8 bit thì XOR với 0x1B).
+ $03 \cdot s_i = (02 \cdot s_i) \oplus s_i$
Ta sẽ thử MixColumns `State` sau:
$$\begin{bmatrix}
63 & 09 & cd & ba \\
53 & 60 & 70 & ca \\
e0 & e1 & b7 & d0 \\
8c & 04 & 51 & e7
\end{bmatrix}$$
- Đầu tiên là nhân cột thứ nhất của `State` với $C$:
$$\begin{bmatrix}
02 & 03 & 01 & 01 \\
01 & 02 & 03 & 01 \\
01 & 01 & 02 & 03 \\
03 & 01 & 01 & 02 \\
\end{bmatrix}
\times
\underset{Column\hspace{1mm}1}{\underbrace{\begin{bmatrix}
63 \\
53 \\
e0 \\
8c \\
\end{bmatrix}}}
=
\begin{bmatrix}
5f \\
72 \\
64 \\
15 \\
\end{bmatrix}$$
- Thử tính byte đầu tiên: $$s'_0 = (\text{02} \cdot \text{63}) \oplus (\text{03} \cdot \text{53}) \oplus (\text{01} \cdot \text{e0}) \oplus (\text{01} \cdot \text{8c})$$
* $02\cdot 0x63 = 0xc6$ $0x63 << 1 = 0xc6$
* $03\cdot 0x53 = 02\cdot 0x53 \oplus 0x53 = 0xa6 \oplus 0x53 = 0xf5$
* $01\cdot 0xe0 = 0xe0$
* $01\cdot 0x8c = 0x8c$
Vậy $s'_0 = c6 \oplus f5 \oplus e0 \oplus 8c = 5f$
- Lập lại các phép tính như vậy ta sẽ tính được cột đầu tiên.
Tương tự:
$$\begin{bmatrix}
02 & 03 & 01 & 01 \\
01 & 02 & 03 & 01 \\
01 & 01 & 02 & 03 \\
03 & 01 & 01 & 02 \\
\end{bmatrix} \times \underset{Column\hspace{1mm}2}{\underbrace{\begin{bmatrix}
09 \\
60 \\
e1 \\
04 \\
\end{bmatrix}}} =
\begin{bmatrix}
57 \\
f5 \\
bc \\
92 \\
\end{bmatrix}$$
$$\begin{bmatrix}
02 & 03 & 01 & 01 \\
01 & 02 & 03 & 01 \\
01 & 01 & 02 & 03 \\
03 & 01 & 01 & 02 \\
\end{bmatrix} \times \underset{Column\hspace{1mm}3}{\underbrace{\begin{bmatrix}
cd \\
70 \\
b7 \\
51 \\
\end{bmatrix}}} =
\begin{bmatrix}
f7 \\
be \\
3b \\
29 \\
\end{bmatrix}$$
$$\begin{bmatrix}
02 & 03 & 01 & 01 \\
01 & 02 & 03 & 01 \\
01 & 01 & 02 & 03 \\
03 & 01 & 01 & 02 \\
\end{bmatrix} \times \underset{Column\hspace{1mm}4}{\underbrace{\begin{bmatrix}
ba \\
ca \\
d0 \\
f7 \\
\end{bmatrix}}} =
\begin{bmatrix}
1d \\
b9 \\
f9 \\
1a \\
\end{bmatrix}$$
Sau khi tính đủ 4 cột thì ta đã thu được ma trận mới:
$$\begin{bmatrix}
5f & 57 & f7 & 1d \\
72 & f5 & be & b9 \\
64 & bc & 3b & f9 \\
15 & 92 & 29 & 1a
\end{bmatrix}$$
Bước này sẽ được thực hiện ở mỗi **Round**. Nhưng riêng **Round** cuối sẽ không có bước này. Lý do là vì:
- `MixColumns` là một phép toán tuyến tính. Thực hiện nó ngay trước khi kết thúc (trước phép `AddRoundKey` cuối) sẽ không thêm bất kỳ giá trị bảo mật nào.
- Bỏ qua nó giúp tiết kiệm tài nguyên tính toán mà không làm giảm độ an toàn.
#### AddRoundKey
Lấy `State` hiện tại XOR với `Roundkey` tương ứng:
$$
\underset{\text{State}}{\underbrace{
\begin{bmatrix}
5f & 57 & f7 & 1d \\
72 & f5 & be & b9 \\
64 & bc & 3b & f9 \\
15 & 92 & 29 & 1a
\end{bmatrix}
}}
\;\bigoplus\;
\underset{\text{RoundKey[1]}}{\underbrace{
\begin{bmatrix}
d6 & d2 & da & d6 \\
aa & af & a6 & ab \\
74 & 72 & 78 & 76 \\
fd & fa & f1 & fe
\end{bmatrix}
}}
\;=\;
\underset{\text{State}'}{\underbrace{
\begin{bmatrix}
89 & 85 & 2d & cb \\
d8 & 5a & 18 & 12 \\
10 & ce & 43 & 8f \\
e8 & 68 & d8 & e4
\end{bmatrix}
}}
$$
### Decryption
Để giải mã, chúng ta phải làm ngược lại mọi thứ, theo thứ tự ngược lại. Chúng ta cần các phép toán "nghịch đảo".
- `AddRoundKey`: Nghịch đảo của nó là chính nó (vì $A \oplus B \oplus B = A$).
- `InvShiftRows`: Nghịch đảo của `ShiftRows`. Dịch các hàng sang phải.
- Hàng 0: Không dịch.
- Hàng 1: Dịch phải 1 vị trí.
- Hàng 2: Dịch phải 2 vị trí.
- Hàng 3: Dịch phải 3 vị trí.
- `InvSubBytes`: Nghịch đảo của SubBytes. Sử dụng một bảng tra cứu **Inverse S-box**. Bảng này cũng cố định và được tính bằng cách làm ngược lại 2 bước (nghịch đảo Biến đổi Affine, rồi nghịch đảo phép nhân trong $GF(2^8)$):
- `InvMixColumns`: Nghịch đảo của `MixColumns`. Nhân các cột của `State` với một ma trận nghịch đảo đặc biệt
# DES
Thuật toán DES (Data Encryption Standard) là một hệ mã hóa khối (block cipher) hoạt động trên các khối dữ liệu 64 bit. Quá trình mã hóa biến đổi đầu vào là văn bản rõ (Plaintext) 64 bit thành văn bản mã (Ciphertext) 64 bit, sử dụng một khóa có độ dài thực tế là 56 bit.
Cấu trúc tổng quát của DES tuân theo mô hình **Mạng Feistel** với 16 vòng lặp. Có thể được chia thành 3 giai đoạn chính:
- Khởi tạo: Hoán vị ban đầu (Initial Permutation) và Sinh khóa con.
- Vòng lặp: 16 vòng xử lý giống nhau về cấu trúc.
- Kết thúc: Hoán vị nghịch đảo.
Sơ đồ quá trình:
## IP - Initial Permutation
Trước khi đi vào các vòng lặp, khối plaintext 64 bit ($P$) được đưa qua một bộ hoán vị cố định gọi là $IP$.
- Mục đích: Xáo trộn vị trí các bit theo một quy tắc bảng cố định (không phụ thuộc vào khóa).
- Ví dụ: Bit thứ 58 của đầu vào được chuyển đến vị trí 1, bit thứ 50 chuyển đến vị trí 2, ...
Cụ thể:
Kết thúc quá trình: Khối dữ liệu $IP(P)$ vẫn là 64-bit, sau đó được chia tách thành hai nửa bằng nhau:
- Nửa trái ban đầu ($L_0$): 32 bit.
- Nửa phải ban đầu ($R_0$): 32 bit.
## Key Schedule
Mặc dù khóa đầu vào ($K$) có độ dài 64 bit, nhưng thực tế thuật toán chỉ sử dụng 56 bit (các bit ở vị trí 8, 16, 24, ..., 64 là các bit kiểm tra chẵn lẻ - parity bits và bị loại bỏ). Từ 56 bit này, DES tạo ra 16 khóa con ($K_1, K_2, ..., K_{16}$), mỗi khóa dài 48 bit để dùng cho 16 vòng lặp.
Quy trình sinh khóa bao gồm:
- Hoán vị PC-1 (Permuted Choice 1): Rút gọn khóa 64-bit xuống còn 56-bit và xáo trộn vị trí.
Kết quả được chia làm hai nửa $C_0$ (28 bit) và $D_0$ (28 bit).
- Dịch vòng trái (Left Circular Shift): Tại mỗi vòng $i$, hai nửa $C$ và $D$ được dịch trái độc lập.
- Dịch **1 bit** tại các vòng: **1, 2, 9, 16**.
- Dịch **2 bit** tại các vòng còn lại.
Ví dụ: nếu chúng ta đang ở vòng 5 và có khóa là `1101101101101101` , thì theo bảng, chúng ta sẽ phải dịch chuyển nó sang trái 2 lần. Do đó, sau vòng này, khóa của chúng ta sẽ là: `0110110110110111` .
-Hoán vị PC-2 (Permuted Choice 2): Tại mỗi vòng, sau khi dịch, các bit từ $C_i$ và $D_i$ được ghép lại và đưa qua PC-2 để chọn ra 48 bit. Đây chính là khóa con $K_i$.
Ta thấy rằng bit thứ 14 của khóa được đặt ở vị trí đầu tiên của khóa hoán vị mới, bit thứ 17 được đặt ở vị trí thứ hai ... cứ thế tiếp tục. Chúng ta có thể thấy khóa mới được tạo ra chỉ có 48 bit, không giống như các khóa trước đó tạo ra 56 bit. Quá trình này được gọi là hoán vị nén (**compression permutation**).
## Các vòng lặp Feistel
DES thực hiện 16 vòng lặp giống hệt nhau về mặt cấu trúc. Tại mỗi vòng thứ $i$ (với $i$ từ 1 đến 16), đầu vào là cặp ($L_{i-1}, R_{i-1}$) và đầu ra là ($L_i, R_i$).
Quy tắc biến đổi như sau:
$$L_i = R_{i-1}$$
$$R_i = L_{i-1} \oplus F(R_{i-1}, K_i)$$
*Trong đó:*
* $K_i$: Khóa con 48-bit của vòng thứ $i$.
* $F$: Hàm Feistel.
Về cơ bản, nửa phải cũ trở thành nửa trái mới. Nửa trái cũ được XOR với kết quả của hàm $F$ để tạo thành nửa phải mới.
## Hàm F (The Feistel Function)
Hàm $F$ là trái tim của DES, nơi thực hiện các phép biến đổi phi tuyến tính để đảm bảo tính bảo mật. Hàm $F$ nhận đầu vào là một khối 32 bit ($R_{i-1}$) và khóa con 48 bit ($K_i$), trả về đầu ra 32 bit.
Quá trình bên trong hàm $F$ gồm 4 bước:
### Expansion - E
* Khối đầu vào **32 bit** được mở rộng thành **48 bit** bằng bảng hoán vị mở rộng (E-table).
* **Cơ chế:** Một số bit của đầu vào được sao chép lặp lại. Điều này giúp kích thước dữ liệu khớp với khóa con ( từ 32 bit lên 48 bit).
### Trộn khóa (Key Mixing)
* Thực hiện phép **XOR** giữa kết quả 48 bit từ bước mở rộng với khóa con $K_i$ (48 bit).
$$R = E(R_{i-1}) \oplus K_i$$
### Substitution - S-box
Đây là thành phần quan trọng nhất tạo nên tính phi tuyến của DES.
* Đầu vào 48 bit được chia thành 8 nhóm, mỗi nhóm 6 bit.
* Mỗi nhóm 6 bit được đưa vào một **S-box** tương ứng (từ $S_1$ đến $S_8$).
* **Quy tắc bảng S-box:** Với đầu vào 6 bit (ví dụ: $b_1b_2b_3b_4b_5b_6$):
* Hai bit ngoài cùng ($b_1b_6$) quyết định chỉ số **Hàng** (0-3).
* Bốn bit giữa ($b_2b_3b_4b_5$) quyết định chỉ số **Cột** (0-15).
* Giá trị tại giao điểm Hàng và Cột là một số 4 bit.
* Kết quả từ 8 hộp S-box được ghép lại thành chuỗi **32 bit**.
### Hoán vị (Permutation - P)
Chuỗi 32-bit đầu ra từ S-box được hoán vị một lần nữa theo bảng P (P-box). Mục đích là để phân tán các bit đầu ra của S-box này sang đầu vào của các S-box khác trong vòng kế tiếp.
### FP (Final Permutation - $IP^{-1}$)
Sau khi kết thúc vòng thứ 16, chúng ta thu được ($L_{16}, R_{16}$).
Tiến hành thực hiện 3 bước:
- Hoán đổi($L_{16}, R_{16}$) thành ($R_{16}, L_{16}$).
- Ghép ($R_{16}, L_{16}$) lại thành khối 64 bit: $R_{16}||L_{16}$.
- Khối 64 bit này đi qua hoán vị $IP^{-1}$ (nghịch đảo của $IP$ ban đầu).
Đầu ra cuối cùng chính là **Ciphertext**
---
## Decryption
Một ưu điểm lớn của cấu trúc Feistel trong DES là quá trình giải mã sử dụng **cùng một thuật toán** như quá trình mã hóa.
* Dữ liệu đầu vào là Ciphertext.
* Cấu trúc vòng lặp, hàm $F$, các hoán vị $IP$, $IP^{-1}$ giữ nguyên.
* **Sự khác biệt duy nhất:** Các khóa con được sử dụng theo thứ tự ngược lại ($K_{16}, K_{15}, ..., K_1$).
## 2DES
Là một biến thể của DES, để tăng cường bảo mật cho DES (do khóa 56 bit quá ngắn), người ta nghĩ đến việc mã hóa 2 lần (Double DES).
### Encryption
Plaintext $P$ được mã hóa lần đầu bằng khóa $K_1$, kết quả thu được tiếp tục được mã hóa lần hai bằng khóa $K_2$ để tạo ra Ciphertext $C$.
$$C = E_{K2}(E_{K1}(P))$$
### Decryption
Quá trình ngược lại, giải mã bằng $K_2$ trước, sau đó giải mã bằng $K_1$.
$$P = D_{K1}(D_{K2}(C))$$
### Nhược điểm
Vì sử dụng 2 khóa 56 bit độc lập, về mặt lý thuyết, độ dài khóa tổng cộng là $56 + 56 = 112$ bit. Vậy tổng giá trị có thể có là $2^{112}$
Với sức mạnh tính toán hiện tại, con số $2^{112}$ được xem là an toàn
**Nhưng trong thực tế**, nó hoàn toàn bị phá vỡ bởi Meet-in-the-Middle Attack. Tấn công này chứng minh rằng độ an toàn của 2DES không phải là $2^{112}$, mà chỉ xấp xỉ $2^{57}$.
Do không mang lại hiệu quả bảo mật tương xứng với chi phí tính toán (gấp đôi DES), 2DES không được đưa vào sử dụng thực tế.
## 3DES(Triple DES)
Triple DES (hay còn gọi là TDEA - Triple Data Encryption Algorithm) là chuẩn mã hóa được tạo ra để khắc phục lỗ hổng của 2DES.
Nó trở thành tiêu chuẩn thay thế DES trong ngành tài chính và thanh toán trong một thời gian dài trước khi AES phổ biến
### Cấu trúc EDE (Encrypt-Decrypt-Encrypt)
Điểm đặc biệt của 3DES là nó không chỉ thực hiện 3 lần mã hóa (EEE) mà còn có thể sử dụng cấu trúc EDE.
- Công thức Mã hóa:$$C = E_{K3}(D_{K2}(E_{K1}(P)))$$
- Công thức Giải mã:$$P = D_{K1}(E_{K2}(D_{K3}(C)))$$
>Tại sao lại có bước Giải mã (D) ở giữa?
Mục đích chính là để đảm bảo tính tương thích ngược (backward compatibility). Nếu ta thiết lập cả 3 khóa giống nhau ($K_1 = K_2 = K_3$), thì:$$C = E_{K1}(D_{K1}(E_{K1}(P))) = E_{K1}(P)$$
Lúc này, hệ thống 3DES hoạt động y hệt như một DES. Điều này cho phép các hệ thống phần cứng mới (hỗ trợ 3DES) vẫn có thể giao tiếp với các hệ thống cũ (chỉ hỗ trợ DES)
### Các chế độ khóa (Keying Options)
Chuẩn 3DES định nghĩa 3 tùy chọn sử dụng khóa, ảnh hưởng trực tiếp đến độ an toàn.
#### Keying Option 1: 3 Khóa độc lập
- $K_1 \neq K_2 \neq K_3$.
- Độ dài khóa: $56 \times 3 = 168$ bit.
- Độ an toàn thực tế: 112 bit. (Do ảnh hưởng của tấn công Meet-in-the-Middle làm giảm hiệu quả của một tầng khóa).
> Đây là chế độ an toàn nhất của 3DES.
#### Keying Option 2: 2 Khóa
- $K_1 = K_3$ và $K_1 \neq K_2$.
- $C = E_{K1}(D_{K2}(E_{K1}(P)))$.
- Độ dài khóa: $56 \times 2 = 112$ bit.
#### Keying Option 3: 1 Khóa
- $K_1 = K_2 = K_3$.
- Tương đương với DES đơn ($56$ bit) hiện nay hoàn toàn không còn an toàn
Ưu và nhược điểm của 3DES
- Ưu điểm: Khắc phục được điểm yếu về độ dài khóa của DES.Độ an toàn (với Option 1) đủ tốt trong thời gian dài.
- Nhược điểm:Hiệu suất thấp, Do phải chạy thuật toán DES 3 lần, 3DES chậm hơn DES đơn 3 lần và chậm hơn nhiều so với AES
---
# Block cipher mode of operation
## ECB (Electronic Codebook)
Đây là mode đơn giản nhất, dữ liệu đầu vào sẽ được chia thành các khối plaintext có kích thước giống nhau và sẽ được mã hóa riêng biệt.
- **Encryption**: $C_i = E_K(P_i)$
- **Decryption**: $P_i = D_K(C_i)$
Vì ECB mã hóa các khối một cách độc lập nên các mẫu dữ liệu thiếu đi tính phức tạp, ngẫu nhiên.
Ví dụ đây là ảnh gốc:
Sau khi mã hoá ECB:
## CBC (Cipher Block Chaining)
CBC là một cải tiến của ECB, trong đó [IV](https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Initialization_vector_(IV)) được sử dụng để tăng tính ngẫu nhiên. Với CBC mode: mỗi block plaintext được XOR với ciphertext block trước đó (hoặc IV cho block đầu), rồi mã hóa:
- **Encryption**: $C_i = E_K(P_i \oplus C_{i-1})$
- **Decryption**: $P_i = D_K(C_i) \oplus C_{i-1}$
- Với: $C_0 = IV$
Dựa vào các công thức này ta có thể rút ra nhận định quan trọng:
> Trong quá trình decryption của CBC mode, việc sử dụng một $IV$ sai sẽ chỉ làm plaintext đầu tiên bị sai, còn các plaintext sau vẫn đúng.
Chứng minh:
- Gọi $IV'$ là $IV$ mà ta sử dụng. Ta có $P_i = D_K(C_i) \oplus C_{i-1}$ nên:
- $P_1 = D_K(C_1) \oplus C_0 = D_K(C_1) \oplus IV'$.
- $P_2 = D_K(C_2) \oplus C_1$
- $P_3 = D_K(C_3) \oplus C_2$
- ...
Do đó, chỉ có $P_1$ bị giải mã sai, còn các $P_i$ khác vẫn được giải mã đúng.
## PCBC (Propagating Cipher Block Chaining)
Là biến thể của CBC, ít được dùng trong thực tế. Ở chế độ này, mỗi khối plaintext được XOR với ciphertext trước đó rồi XOR thêm với cả plaintext trước đó, rồi mới được đem đi mã hóa.
- **Encryption**: $C_i = E_K(P_i \oplus C_{i-1} \oplus P_{i-1})$
- **Decryption**: $P_i = D_K(C_i) \oplus C_{i-1} \oplus P_{i-1}$
- Với $C_0 \oplus P_0 = IV$.
Chính việc XOR thêm với plaintext trước đó nên nếu ta tính toán ra plaintext hiện tại bị sai, sẽ dẫn đến tất cả những plaintext sau đó đều sai, chữ Propagating (lan truyền) trong PCPC bắt nguồn từ hiện tượng này.
## CFB (Cipher Feedback)
CFB là một mode biến block cipher (AES) thành một stream cipher (mã hóa dòng), bằng cách [keystream](https://en.wikipedia.org/wiki/Keystream) tuần tự từ các block mã hóa trước đó.
- **Encryption**: $C_i = E_K(C_{i-1}) \oplus P_i$
- **Decryption**: $P_i = E_K(C_{i-1}) \oplus C_i$
Ta có thể nhận một điểm thú vị là là nó không cần hàm giải mã để giải mã, đó chính là một đặc điểm nổi bật của các chế độ keystream.
Bên cạnh đó còn có các mode khác như (CFB-8, CFB-1, CFB-64 ...), nên về cơ bản CFB không cần padding, vì trong CFB, ta không cần phải xử lý toàn bộ một block trong một lần mã hóa, mà ta có thể chia dữ liệu thành nhiều segment nhỏ hơn, giúp mã hóa theo luồng.
## OFB (Output feedback)
Tương tự tư CFB, nó sẽ biến mã hóa khối thành mã hóa luồng, nhưng đối với OFB, input bước này không phải là ciphertext, mà là keystream của bước trước.
Vì tính chất của phép XOR nên cả quá trình Encryption và Decryption sẽ có mối liên hệ với nhau:
- **Encryption**:
- $O_i = E_K(O_{i-1})$
- $C_i = P_i \oplus O_i$
- **Decryption**:
- $P_i = C_i \oplus O_i$
- Với $O_0 = IV$
So sánh nhanh:
| Đặc điểm | **CFB** | **OFB** |
| --------------------------- | -------------------------------------------- | -------------------------------------------- |
| Input cho $E_K$ | Ciphertext trước đó ($C_{i-1}$) | Keystream trước đó ($O_{i-1}$) |
| Ảnh hưởng lỗi | Lỗi ở 1 ciphertext làm sai vài block sau | Lỗi ở 1 ciphertext chỉ sai đúng block đó |
| Có thể tạo keystream trước? | Không (phụ thuộc ciphertext) | Có (vì chỉ phụ thuộc IV và $E_K$) |
| Cần $E_K$ hay $D_K$ khi giải mã | Chỉ $E_K$ | Chỉ $E_K$ |
>Fun fact: CBC mode có plaintext là 0 sẽ giống OFB mode.
- CBC mode:
- $C_i = E_K(P_i \oplus C_{i-1})$, vì các $P_i = 0$, nên:
- $C_i = E_K(0 \oplus C_{i-1}) = E_K(C_{i-1})$, mà vì $C_0 = IV$, nên input cho $E_K$ sẽ là keystream trước đó, sẽ giống với OFB mode.
## CTR (Counter Mode)
Tương tự với CFB và OFB, CTR sẽ biến mã khối thành mã dòng:
- Cơ chế: CTR dùng **Counter** và **Nonce** làm input cho cipher để sinh keystream.
- **Nonce**(Number used once): Giá trị được sinh ngẫu nhiên cho mỗi lần mã hóa.
- **Couter**: Giá trị thay đổi tăng dần với mỗi lần mã hóa (thường bắt đầu = 0).
- Do vậy, input sẽ có dạng: $Nonce||Counter$, và tổng độ dài của **Nonce + Counter** phải bằng độ dài của block size.
- Encryption:
- $C_i = P_i \oplus E_K(Nonce||Counter_i)$
- Decryption:
- $P_i = C_i \oplus E_K(Nonce||Counter_i)$
CTR có ưu điểm lớn là: không cần padding, có thể truy cập ngẫu nhiên vào bất kỳ khối nào, tốc độ cao, phù hợp cho truyền dữ liệu và bộ nhớ.
Tuy nhiên nếu sử dụng cùng Nonce + Counter cho hai plaintext khác nhau thì toàn bộ bảo mật bị phá. CTR vì thế an toàn, mạnh, nhưng phụ thuộc cực kỳ lớn vào việc đảm bảo **tính duy nhất** của (Nonce, Counter).
# Attacks
## ECB byte-at-a-time attack
Đây là dạng tấn công kinh điển, nó khai thác điểm yếu chí mạng của ECB mode.
**Kịch bản tấn công:**
Hãy tưởng tượng bạn có một máy chủ (hoặc một hàm), gọi là "Oracle". Nó hoạt động như sau:
- Nhận đầu vào (Input) của bạn.
- Nối thông điệp bí mật (Flag) vào sau Input của bạn.
- Mã hóa toàn bộ chuỗi đó bằng AES với mode là ECB.
**Lỗ hổng:** Vì ở ECB mode, các plaintext sẽ được chia thành các block có độ dài bằng nhau và được mã hóa cùng một cách giống nhau. Tức là 2 plaintext giống nhau sẽ cùng được mã hóa thành 2 ciphertext giống nhau. Do đó, nếu ta kiểm soát được các block, ta sẽ có thể "cô lập" từng byte của chuỗi bí mật, từ đó "dò" thử từng byte đó.
**Cơ chế:**
Giả sử kích thước khối (block size) là **16**. Mục tiêu của ta là tìm được **serect** mà không cần biết **Key**.
Bước 1: Ép byte cuối của Flag rơi vào cuối block
- Giả sử ta muốn tìm byte đầu tiên của Flag, lúc này ta cần chọn Input có độ dài ít hơn 1 byte so với block size (tức là 15 bytes).
Ta sẽ nhập Input là 15 chữ "A", ký hiệu byte cần tìm là $c$, vậy lúc này block đầu tiên sẽ được biểu diễn như sau:
Oracel sẽ trả về ciphertext, ta sẽ gọi ciphertext này là **Ciphertext mục tiêu**
Bước 2: Brute-force
- Bây giờ ta muốn biết $c$ là byte gì. Vì 1 byte tương ứng với 256 giá trị, nên $c$ chỉ có 256 khả năng.
- Ta sẽ gửi 256 request mới tới Oracle. Với mỗi request thì ta thay $c$ bằng 1 giá trị cụ thể từ 0 đến 255
- Thử $c$ = "a": Oracle mã hóa $[AAAAAAAAAAAAAAAa]$. Tiến hành so sánh với Ciphertext mục tiêu, khớp không? Không thì tiếp tục.
- Thử $c$ = "b": Oracle mã hóa $[AAAAAAAAAAAAAAAb]$. Tiến hành so sánh với Ciphertext mục tiêu, khớp không? nếu khớp thì dừng lại.
- Vậy ta đã tìm được byte đầu của Flag = "b"
Bước 3: Tiếp tục Brute-force, nhưng phải căn chỉnh padding hợp lý.
Giả sử cần tìm byte thứ 2 khi biết đã dò ra được byte đầu bằng "b", vậy lúc này ta không được pad 15 byte kí tự "A" nữa mà phải là 14 byte "A" + 1 byte là "b" + 1 byte $c$ mà ta muốn tìm. Khi đó chuỗi byte của ta được biểu diễn như sau:
Oracle sẽ mã hóa block plaintext này. Ta sẽ lưu kết quả đó làm Ciphert mục tiêu mới.
Tiếp tục như vậy cho đến khi tìm được đầy đủ Flag.
- Script mô phỏng:
```py=
BLOCK_SIZE = 16
flag = ""
while True:
pad_len = (BLOCK_SIZE - 1) - (len(flag) % BLOCK_SIZE)
padding = "A" * pad_len
ciphertext = oracle(padding)
target_block = ciphertext
found = False
for char_code in range(256):
guess_byte = chr(char_code)
attack_payload = padding + flag + guess_byte
attack_ciphertext = oracle(attack_payload)
attack_block = attack_ciphertext
if attack_block == target_block:
flag += guess_byte
found = True
break
```
Vấn đề đặt ra là nếu Flag lớn hơn 16 byte thì sao. Lúc này ta không thể so sánh như vậy được nữa vì cách đó chỉ có thể hoạt động nếu Flag nhỏ hơn 16 byte. Lúc này ta có 2 cách: 1 là tính toán trị số khối cần tính (block index) và cắt rồi so sánh đúng vị trí đó, 2 là dùng kỹ thuật so sánh đối xứng (Symmetric Comparison)
Bước 1:
- Gọi guess là chuỗi được tạo bới flag + ký tự $c$ cần tìm: `guess = flag + c`
- Tính độ dài của chuỗi pad:
```
pad_len = block_size - (len(guess) % block_size)
```
> Công thức này sẽ đảm bảo độ dài của tổng pad + guess sẽ luôn là bội của block_size
- Tạo plaintext: `pt = pad + guess + pad`
Bước 2: Gửi `pt` vừa tính vào Oracle
- Khi gửi vào Oracle, nó sẽ nói thêm Flag vào cuối: tức là lúc này thật sự $Plaintext = Pad||guess||Pad||Flag$
- Việc này sẽ tạo ra một cấu trúc rất đẹp, phần đầu: $Pad||guess$ gồm Pad + phần Flag đã biết + byte $c$, phần sau: $Pad||Flag$ gồm Pad + độ dài đoạn Flag từ đầu đến ký tự $c$.
- Vậy nếu $E_K(Pad||guess) == E_K(Pad||Flag)$ thì ta đã đoán đúng $c$
- Scipt mô phỏng:
```py=
chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890_{}"
block_size = 16
flag = ""
while True:
for c in chars:
guess = flag + c
pad_len = block_size - (len(guess) % block_size)
pad = "A" * pad_len
pt = pad + guess + pad
ct = oracle(pt)
size = pad_len + len(guess)
part1, part2 = ct[:size], ct[size : size + size]
if part1 == part2:
flag += c
if flag[-1] == "}":
print(flag)
break
```
## CBC Bit-Flipping
Khác với tấn công ECB (chỉ đọc dữ liệu), CBC Bit-Flipping sẽ cho phép bạn thay đổi nội dung giải mã của sever mà không cần biết Key.
**Nguyên lý cốt lõi:**
Quá trình **decryption** của **CBC mode** diễn ra như sau:
- $P_i = D_K(C_i) \oplus C_{i-1}$
Vậy nếu ta thay đổi $C_{i-1}$, thì $P_i$ sẽ bị thay đổi tùy thuộc vào giá trị mà ta đặt cho $C_{i-1}$.
**Công thức tấn công:**
Giả sử chuỗi plaintext hiện tại là `"admin = 0"`, ta muốn biển đổi nó thành `"admin = 1"`. Vậy lúc này ta thực hiện như sau:
- Gọi `"admin = 0"` là $P_i$, `"admin = 1"` là $P'_i$.
- Ta sẽ sửa đổi $C_{i-1}$ lại thành $C_{i-1}'$ với : $$C'_{i-1} = C_{i-1} \oplus P_i \oplus P'_i$$
- Lúc này sever giải mã $P_i$:
$$P_i = D_K(C_i) \oplus C'_{i-1} = D_K(C_i) \oplus C_{i-1} \oplus P_i \oplus P'_i$$
- Mà $D_K(C_i) \oplus C_{i-1} = P_i$, nên $$P_i = P_i \oplus P_i \oplus P'_i = 0 \oplus P'_i = P'_i$$
Vậy ta đã thành công chuyển chuỗi "admin = 0" thành "admin = 1" chỉ bằng cách đổi Ciphertext
> Kiểu attack này sẽ sinh ra một tác dụng phụ là nếu ta tấn công block[i], thì block trước đó là block[i-1] sẽ bị lỗi hoàn toàn, do ta đã thay đổi ciphertext. Trừ trường hợp ta thay đổi $IV$, lúc đó mọi khối dữ liệu khác đều được giữ nguyên.
## CBC padding Oracel
Đây là một loại tấn công nhằm vào các hệ thống sử dụng CBC mode và sử dụng cơ chế đệm (padding).
>Trong bài viết này sẽ chỉ nói về cơ chế PKCS#7 Padding với block size = 16 byte
Đối với PKCS#7 Padding:
- Nếu Plaintext thiếu 1 byte: pad 1 byte có giá trị 0x01 vào cuối: $Plaintext||0x01$
- Nếu Plaintext thiếu 2 byte: pad 2 byte có giá trị 0x02 vào cuối: $Plaintext||0x02||0x22$
....
- Nếu Plaintext đủ 16 byte: vẫn pad 16 byte có giá trị 0x10 vào Plaintext
Đó là quá trình padding, còn unpadding sẽ như sau:
- Đọc byte cuối cùng, gọi giá trị này là $N$.
- Máy sẽ kiểm tra $N - 1$ byte liền trước đó, nếu nó cùng giá trị với $N$ thì pad đúng. Nếu lỗi sẽ báo "Padding Error".
Kẻ tấn công sẽ dựa vào việc sever thông báo pađ đúng hay sai từ đó tìm được Plaintext ban đầu:
- Khi bạn gửi một khối giả mạo và byte cuối giải mã ra là `0x01`. Server kiểm tra: "Byte cuối là 1, cần kiểm tra 0 byte trước đó. Hợp lệ!" -> Server trả về OK.
- Khi byte cuối giải mã ra là `0x02`. Server kiểm tra: "Byte cuối là 0x02, vậy byte liền trước phải là 0x02". Nhưng do bạn gửi random, byte trước đó là 0xB5 (ví dụ). Server thấy 0xB5 != 0x02 -> Server trả về Lỗi.
Chính sự khác biệt giữa phản hồi "OK" (khi vô tình trúng) và "Lỗi" (các trường hợp khác) giúp kẻ tấn công đoán ra được các byte của Plaintext.
Đó là phân tích đơn giản, giờ ta sẽ tấn công thật sự như sau:
Mục tiêu của ta là tìm ra các byte của Plaintext ($P_i$).
Xét khối cuối cùng của bản mã ($C_i$) và khối bản mã trước đó ($C_{i-1}$ - hoặc IV nếu $C_i$ là khối đầu tiên).
- Ta có: $$P_i = D_K(C_i) \oplus C_{i-1}$$
- Ta có thể viết lại: $$P_i[j] = [D_K(C_i)]_j \oplus C_{i-1}[j]$$
- Trong đó:
- $P_i[j]$ là byte thứ $j$ của $P_i$.
- $[D_K(C_i)]_j$ là byte thứ $j$ của kết quả giải mã khối $C_i$ (gọi là Intermediate Byte $I_j$).
- $D_K(C_i)$ là giá trị bí mật ta muốn tìm .
- $C_{i-1}[j]$ là byte thứ $j$ của khối bản mã trước đó $C_{i-1}$.
- Mục tiêu là tìm Intermediate Byte $I_j$. Khi tìm được $I_j$, ta có thể tìm được $P_i[j]$ vì:$$P_i[j] = I_j \oplus C_{i-1}[j]$$
Các bước tiến hành:
1: Tìm byte cuối cùng $P_i[N]$
- Ta muốn $P_i[N]$ có giá trị đệm là 0x01 (tức là $I_N \oplus C_{i-1}[N] = 0x01$).
- Ta thay đổi byte cuối cùng của khối trước đó $C'_{i-1}[N]$ (các byte khác được giữ nguyên).
- Ta gửi $(C'_{i-1}, C_i)$ đến Oracle và lặp qua 256 giá trị có thể có cho $C'_{i-1}[N]$ (từ 0x00 đến 0xFF).
- Khi Oracle trả lời "pad hợp lệ", điều đó có nghĩa là:$$I_N \oplus C'_{i-1}[N] = 0x01$$
- Từ đó, ta tính được Intermediate Byte cuối cùng $I_N$:$$I_N = 0x01 \oplus C'_{i-1}[N]$$
- Bây giờ, ta tìm được byte cuối cùng của Plaintext gốc $P_i[N]$:$$P_i[N] = I_N \oplus C_{i-1}[N]$$
2. Tìm byte thứ hai từ cuối ($P_i[N-1]$)
- Ta muốn hai byte cuối cùng của $P_i$ có giá trị đệm là 0x02 0x02 (tức là $I_N = 0x02$ và $I_{N-1} = 0x02$).
- Ta đã biết $I_N$ từ bước 1. Nên cần tính toán $C''_{i-1}[N]$ để đảm bảo $P_i[N]$ là 0x02:$$C''_{i-1}[N] = I_N \oplus 0x02$$
- Bằng cách lặp qua 256 giá trị cho byte $C''_{i-1}[N-1]$.Khi Oracle trả lời "Pad Hợp lệ", điều đó có nghĩa là $P_i[N-1]$ là 0x02:$$I_{N-1} \oplus C''_{i-1}[N-1] = 0x02$$
- Từ đó, ta tính được $I_{N-1}$:$$I_{N-1} = 0x02 \oplus C''_{i-1}[N-1]$$
- Cuối cùng, ta tìm được $P_i[N-1]$:$$P_i[N-1] = I_{N-1} \oplus C_{i-1}[N-1]$$
3. Lặp lại
- Tiến hành lặp lại quá trình này cho đến khi giải mã được tất cả các byte của khối $P_i$. Sau đó, ta chuyển sang khối trước đó, sử dụng khối $C_{i-1}$ vừa giải mã như là khối ciphertext trước đó ($C_{i-2}$), và cứ thế tiếp tục.
Để hiểu sâu hơn về cách attack này, ta sẽ tiến hành giải challenge Pad Thai trên Cryptohack.
source code sever:
```py=
#!/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)
```
Phân thích source code:
```py=
self.message = urandom(16).hex()
```
Challenge tạo một chuỗi message ngẫu nhiên rồi tiến hành encrypt nó bằng CBC mode
Bên cạnh đó ta có hàm `check_padding()`:
```py=
def check_padding(self, ct):
...
try:
unpad(pt, 16)
except ValueError:
good = False
else:
good = True
return {"result": good}
```
Hàm này hoạt động như một Padding Oracle.
- Nó nhận ciphertext, giải mã và cố gắng unpad theo chuẩn PKCS#7.
- Nếu padding sai quy chuẩn: trả về False.
- Nếu padding đúng quy chuẩn: trả về True.
=> Đây là dấu hiệu kinh điển của tấn công Padding Oracle Attack. Ta có thể lợi dụng phản hồi True/False này để đoán từng byte của message mà không cần biết khóa bí mật.
:::spoiler solve
```py=
from pwn import *
import json
from Crypto.Util.Padding import pad, unpad
HOST = "socket.cryptohack.org"
PORT = 13421
r = remote(HOST, PORT)
r.recvline()
def json_recv():
line = r.recvline()
return json.loads(line.decode())
def json_send(data):
request = json.dumps(data).encode()
r.sendline(request)
def get_ciphertext():
json_send({"option": "encrypt"})
resp = json_recv()
return bytes.fromhex(resp["ct"])
def oracle(ct_hex):
json_send({"option": "unpad", "ct": ct_hex})
resp = json_recv()
return resp["result"]
def check_flag(message):
json_send({"option": "check", "message": message})
print(json_recv())
def decrypt_block(target_block, pre_block):
intermediate = [0] * 16
plaintext_block = [0] * 16
fake_prev_block = bytearray(16)
for byte_index in range(15, -1, -1):
padding_val = 16 - byte_index
for k in range(byte_index + 1, 16):
fake_prev_block[k] = intermediate[k] ^ padding_val
found = False
for guess in range(256):
fake_prev_block[byte_index] = guess
payload = fake_prev_block + target_block
if oracle(payload.hex()):
inter_val = guess ^ padding_val
intermediate[byte_index] = inter_val
pt_val = inter_val ^ pre_block[byte_index]
plaintext_block[byte_index] = pt_val
found = True
break
return bytes(plaintext_block)
full_ct = get_ciphertext()
iv = full_ct[:16]
ct = full_ct[16:]
blocks = [ct[i:i+16] for i in range(0, len(ct), 16)]
recovered_plaintext = b""
pre_block = iv
for block in (blocks):
decrypted_block = decrypt_block(block, pre_block)
recovered_plaintext += decrypted_block
pre_block = block
print(decrypted_block.hex())
ff
final_message = recovered_plaintext
check_flag(final_message.decode())
r.close()
```
:::
::: spoiler Flag
crypto{if_you_ask_enough_times_you_usually_get_what_you_want}
:::
## Meet-in-the-Middle
Đây là kiểu tấn công tìm khóa bí mật trong 2DES, hoặc AES với số lần mã hóa chẵn
Cơ sở lý thuyết:
Giả sử ta có cặp Plaintext - Ciphertext $(P, C)$ được mã hóa bằng 2DES với hai khóa $K_1, K_2$:$$C = E_{K2}(E_{K1}(P))$$
$$P = D_{K_1}(D_{K_2}(C))$$
Nếu ta giải mã $C$ bằng $K_2$:
$$D_{K_2}(C) = D_{K_2}(E_{K_2}(E_{K_1}(P))) = E_{K_1}(P)$$
Suy ra:$$E_{K1}(P) = D_{K2}(C)$$
Tấn công chi tiết:
Thay vì thử tất cả cặp khóa $(K_1, K_2)$ cùng lúc với độ phức tạp $2^{112}$, ta thực hiện như sau:
- Mã hóa $P$ với tất cả $2^{56}$ giá trị có thể của $K_1$.Lưu trữ các cặp kết quả $(E_{K1}(P), K_1)$ vào một bảng.
- Giải mã $C$ với tất cả $2^{56}$ giá trị có thể của $K_2$.Với mỗi kết quả $Y = D_{K2}(C)$, kiểm tra xem $Y$ có tồn tại trong bảng đã tạo ở Bước 1 hay không.
- Nếu tìm thấy $Y$ trong bảng, tức là $E_{K1}(P) = D_{K2}(C)$, ta tìm được một cặp khóa là $(K_1, K_2)$.
Bài tập luyện tập:
```py=
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
```
Phân tích bài toán:
- Đây là AES được mã hóa với số lần chẵn: $$C = E_{k2}(E_{k1}(P))$$
- Key được sinh ra từ `md5(urandom(3))`.
- `urandom(3)` sinh ra 3 bytes ngẫu nhiên.Vậy giá trị chỉ là $2^{24} = 16777216$ trường hợp. Đây là con số hòan toàn có thể brute-force được.
Vấn đề: Để tấn công MITM, ta cần một cặp (Plaintext, Ciphertext) đã biết.
- Ciphertext ($C$): Ta có chuỗi hex đề bài cho.
- Plaintext ($P$): Ta biết flag bắt đầu bằng KCSC{ nhưng như thế chưa đủ 1 block (16 bytes).Ta không biết đoạn giữa.
- Chú ý hint: `assert len(FLAG) % 16 == 1`
- Hàm pad(FLAG, 16) sử dụng chuẩn PKCS7.Nếu độ dài Flag chia 16 dư 1, nghĩa là block cuối cùng chỉ chứa 1 ký tự của Flag, và 15 ký tự còn lại là padding.
-Theo chuẩn PKCS7, nếu thiếu 15 byte, giá trị padding sẽ là \x0f (số 15).
- Ký tự cuối của Flag chắc chắn là }.
=> Ta biết chính xác nội dung của Block Plaintext cuối cùng:$$P_{last} = \} + 0f * 15$$
::: spoiler solve
```py=
from Crypto.Cipher import AES
from hashlib import md5
from tqdm import tqdm
ct = "21477fac54cb5a246cb1434a1e39d7b34b91e5c135cd555d678f5c01b2357adc0c6205c3a4e3a8e6fb37c927de0eec95"
ct = bytes.fromhex(ct)
k1, k2 = 0, 0
known = b'}' + b'\x0f' * 15
last_block_ct = ct[-16:]
lookup_table = {}
for i in tqdm(range(1 << 24)):
seed = i.to_bytes(3, 'big')
key1 = md5(seed).digest()
cipher1 = AES.new(key1, AES.MODE_ECB)
middle_val = cipher1.encrypt(known)
lookup_table[middle_val] = key1
for i in tqdm(range(1 << 24)):
seed = i.to_bytes(3, 'big')
key2 = md5(seed).digest()
cipher2 = AES.new(key2, AES.MODE_ECB)
decrypted_val = cipher2.decrypt(last_block_ct)
if decrypted_val in lookup_table:
key1 = lookup_table[decrypted_val]
k1, k2 = key1, key2
break
c2 = AES.new(k2, AES.MODE_ECB)
middle_full = c2.decrypt(ct)
c1 = AES.new(k1, AES.MODE_ECB)
flag = c1.decrypt(middle_full)
print(flag)
```
:::
::: spoiler Flag
KCSC{MeEt_In_tHe_mIdDLe_AttaCk__}
:::
## Weak Keys
Trong DES, "Weak Key" là những khóa mà khi đi qua thuật toán sinh khóa con (key schedule), nó tạo ra 16 khóa con giống hệt nhau.Điều này dẫn đến một tính chất cực kỳ quan trọng:
Vì tính chất đối xứng của Feistel, thuật toán decryption hoàn toàn giống hệt thuật toán encryption, ngoại trừ một điểm duy nhất: Thứ tự của các khóa con (Sub-keys).
Encryption: Dùng 16 khóa con theo thứ tự:$$K_1 \rightarrow K_2 \rightarrow K_3 \rightarrow \dots \rightarrow K_{16}$$
Decryption): Dùng 16 khóa con theo thứ tự ngược lại:$$K_{16} \rightarrow K_{15} \rightarrow K_{14} \rightarrow \dots \rightarrow K_1$$
Vậy điều gì xảy ra khi dùng Weak Key?
Như đã nói, Weak Key là loại khóa đặc biệt mà thuật toán sinh khóa (Key Schedule) tạo ra 16 khóa con giống hệt nhau:$$K_1 = K_2 = K_3 = \dots = K_{16} = K$$
Vậy thì:
Dãy khóa dùng để Mã hóa: $\{K, K, \dots, K\}$
Dãy khóa dùng để Giải mã (đảo ngược dãy trên): $\{K, K, \dots, K\}$
=> Ta rút ra nhận xét: với một khóa yếu $K_w$, phép mã hóa ($E$) và giải mã ($D$) thực chất là cùng một phép toán:$$E_{K_w}(x) = D_{K_w}(x)$$
Từ đó, ta có tính chất quan trọng: Nếu bạn mã hóa một plaintext 2 lần liên tiếp bằng cùng một khóa yếu, bạn sẽ nhận lại plaintext ban đầu:$$E_{K_w}(E_{K_w}(P)) = P$$
Trong DES, có 4 khóa yếu được biết đến (dưới dạng Hex):
- `0000000000000000`
- `FFFFFFFFFFFFFFFF`
- `E0E0E0E0F1F1F1F1`
- `1F1F1F1F0E0E0E0E`
Chúng ta sẽ áp dụng điều này để giải thử challenge Triple DES:
Link: https://aes.cryptohack.org/triple_des/
source sever:
```py=
from Crypto.Cipher import DES3
from Crypto.Util.Padding import pad
IV = os.urandom(8)
FLAG = ?
def xor(a, b):
# xor 2 bytestrings, repeating the 2nd one if necessary
return bytes(x ^ y for x,y in zip(a, b * (1 + len(a) // len(b))))
@chal.route('/triple_des/encrypt/<key>/<plaintext>/')
def encrypt(key, plaintext):
try:
key = bytes.fromhex(key)
plaintext = bytes.fromhex(plaintext)
plaintext = xor(plaintext, IV)
cipher = DES3.new(key, DES3.MODE_ECB)
ciphertext = cipher.encrypt(plaintext)
ciphertext = xor(ciphertext, IV)
return {"ciphertext": ciphertext.hex()}
except ValueError as e:
return {"error": str(e)}
@chal.route('/triple_des/encrypt_flag/<key>/')
def encrypt_flag(key):
return encrypt(key, pad(FLAG.encode(), 8).hex())
```
Phân tích:
Hàm `encrypt_flag()` sẽ cho ta nhập key tùy ý, sever sẽ mã hóa Flag bằng 3DES từ key ta nhập.
Nhưng hàm `encrypt_flag()` nó sẽ XOR Flag với IV. Server thì sử dụng một IV (8 bytes) ngẫu nhiên mà chúng ta không biết.
Vậy chiến thuật tấn công của ta như sau:
Chúng ta sẽ sử dụng tính chất Weak Key để triệt tiêu IV mà không cần biết giá trị của nó.
Đầu tiên: Chọn một khóa yếu. Ta chọn key là toàn số 0: `0000000000000000` (16 bytes - tương ứng $k1=k2=k3=0$ trong thư viện DES3 của Python khi dùng key 16 bytes thì $k3=k1$).
- Gọi khóa này là $K_w$.Với $K_w$, hàm mã hóa 3DES $E_{K_w}$ có tính chất: $E_{K_w}(E_{K_w}(x)) = x$.
Lúc này ta có ciphertext được mã hóa:
$$C = E_{K_w}(FLAG \oplus IV) \oplus IV$$
Vậy giờ ta lấy chính $C$ đó rồi gửi nó vào hàm `encrypt()` làm plaintext, vẫn sử dụng khóa $K_w$. Thì hàm `encrypt()` xử lý như sau:
$P = C \oplus IV = (E_{K_w}(FLAG \oplus IV) \oplus IV) \oplus IV = E_{K_w}(FLAG \oplus IV)$
Khi Sever tiến hành mã hóa $P$:
$$P = E_{K_w}( E_{K_w}(FLAG \oplus IV) )$$
Và vì ta dùng Weak Key nên:
$$E_{K_w}( E_{K_w}(FLAG \oplus IV) ) = FLAG \oplus IV$$
Vậy sau khi sever tự XOR với IV:
$$P = (FLAG \oplus IV) \oplus IV = FLAG$$
Lúc đầu mình suy nghĩ như vậy, nhưng ý tưởng đó phá sản vì code như vậy thì sever báo lỗi: `Error: Triple DES key degenerates to single DES `.
Lỗi này do thư viện PyCryptodome trên server có cơ chế bảo vệ (sanity check). Nó phát hiện mình đang cố tình sử dụng một khóa mà $K_1 = K_2$ (vì dùng toàn bộ 00), điều này biến 3DES trở về thành DES thường
Nên giờ chúng ta phải nghĩ ra cách phức tạp hơn:
Ta cần kết hợp 2 khóa yếu khác nhau trong chuẩn DES
-Gọi $K_{w1}$ là khóa yếu 1 (`0000000000000000`).
- Gọi $K_{w2}$ là khóa yếu 2 (`FFFFFFFFFFFFFFFF`).
- Ta tạo một khóa 3DES dài 16 bytes bằng cách ghép chúng lại: Key = Kw1 + Kw2.
- Khi dùng key 16 bytes, 3DES tự hiểu $K_1 = K_{w1}, K_2 = K_{w2}, K_3 = K_{w1}$.
Lúc này hàm 3DES là: $E(x) = E_{K1}(D_{K2}(E_{K1}(x)))$
Nếu ta mã hóa 2 lần (gọi hàm $E$ hai lần) với khóa ghép này:$$E(E(x)) = E_{K1}(D_{K2}(E_{K1}({E_{K1}(D_{K2}(E_{K1}(x)))} )))$$
Ta thu gọn từ từ:
- $E_{K1}({E_{K1}(D_{K2}(E_{K1}(x)))}) = D_{K2}(E_{K1}(x))$
- $D_{K2}(D_{K2}(E_{K1}(x))) = E_{K1}(x)$
- $E_{K1}(E_{K1}(x)) = x$
Vậy ta đã thành công áp dụng cho 3DES với việc dùng 2 khóa yếu.
:::spoiler solve
```py=
import requests
import time
URL = "https://aes.cryptohack.org/triple_des"
WEAK_KEY = "0000000000000000" + "FFFFFFFFFFFFFFFF"
r1 = requests.get(f"{URL}/encrypt_flag/{WEAK_KEY}/")
data1 = r1.json()
ciphertext_flag = data1['ciphertext']
r2 = requests.get(f"{URL}/encrypt/{WEAK_KEY}/{ciphertext_flag}/")
data2 = r2.json()
ct = data2['ciphertext']
flag = bytes.fromhex(ct).decode()
print(flag)
```
:::
:::spoiler Flag
crypto{n0t_4ll_k3ys_4r3_g00d_k3ys}
:::
# Cryptohack Challenges
## How AES Works
### Keyed Permutations
AES là thuật toán mã hóa theo khối, nó thực hiện keyed permutation (hóa vị có khóa). Điều này có nghĩa là nó ánh xạ mọi khối đầu vào có thể thành một khối đầu ra duy nhất, với một khóa xác định hoán vị nào cần thực hiện.
Sử dụng cùng một khóa, phép hoán vị có thể được thực hiện ngược lại, ánh xạ khối đầu ra trở lại khối đầu vào ban đầu. Điều quan trọng là phải có sự tương ứng một-một giữa các khối đầu vào và đầu ra, nếu không chúng ta sẽ không thể dựa vào bản mã để giải mã trở lại cùng bản rõ ban đầu
Thuật ngữ toán học cho sự tương ứng một-một là gì?.
- Đó là **song ánh (bijection)**.
Vậy flag là:
:::spoiler Flag
crypto{bijection}
:::
### Resisting Bruteforce
:::info
Việc bruteforce khóa 128-bit có khó không? Có người ước tính rằng nếu bạn dùng toàn bộ sức mạnh của mạng lưới khai thác Bitcoin để bẻ khóa bằng khóa AES-128, sẽ mất hơn một trăm lần tuổi của vũ trụ để bẻ khóa.
:::
Các nhà khoa học đã tìm ra phương pháp attack tốt hơn bruteforce, đó là [Biclique attack](https://en.wikipedia.org/wiki/Biclique_attack).
Vậy flag là:
:::spoiler Flag
crypto{biclique}
:::
### Structure of AES
Challenge kêu ta viết hàm `matrix2bytes` để chuyển đổi ma trận hiện tại thành plaintext ban đầu
:::spoiler matrix.py
```py=
def bytes2matrix(text):
""" Converts a 16-byte array into a 4x4 matrix. """
return [list(text[i:i+4]) for i in range(0, len(text), 4)]
def matrix2bytes(matrix):
""" Converts a 4x4 matrix into a 16-byte array. """
????
matrix = [
[99, 114, 121, 112],
[116, 111, 123, 105],
[110, 109, 97, 116],
[114, 105, 120, 125],
]
print(matrix2bytes(matrix))
```
:::
Ta có thể dùng hàm `chr()` có sẵn để chuyển từng phần tử i trong nó thành chuỗi.
:::spoiler solve.py
```py=
def bytes2matrix(text):
""" Converts a 16-byte array into a 4x4 matrix. """
return [list(text[i:i+4]) for i in range(0, len(text), 4)]
def matrix2bytes(matrix):
""" Converts a 4x4 matrix into a 16-byte array. """
plaintext = ""
for row in matrix:
for i in row:
plaintext += chr(i)
return plaintext
matrix = [
[99, 114, 121, 112],
[116, 111, 123, 105],
[110, 109, 97, 116],
[114, 105, 120, 125],
]
print(matrix2bytes(matrix))
```
:::
::: spoiler Flag
crypto{inmatrix}
:::
### Round Keys
Ta được cung cấp ma trận `State` và một Roundkey, nhiệm vụ của ta là hoàn thành hàm `add_round_key` rồi dùng hàm `matrix2bytes ` để lấy flag
:::spoiler add_round_key.py
```py=
state = [
[206, 243, 61, 34],
[171, 11, 93, 31],
[16, 200, 91, 108],
[150, 3, 194, 51],
]
round_key = [
[173, 129, 68, 82],
[223, 100, 38, 109],
[32, 189, 53, 8],
[253, 48, 187, 78],
]
def add_round_key(s, k):
???
print(add_round_key(state, round_key))
```
:::
Để thực hiện AddRoundKey thì ta chỉ cần **XOR** từng phần tử trong State và `RoundKey` với nhau, ta sẽ thu được ma trận `State` mới, chuyển nó thành chuỗi rồi lấy flag.
:::spoiler solve.py
```py=
state = [
[206, 243, 61, 34],
[171, 11, 93, 31],
[16, 200, 91, 108],
[150, 3, 194, 51],
]
round_key = [
[173, 129, 68, 82],
[223, 100, 38, 109],
[32, 189, 53, 8],
[253, 48, 187, 78],
]
def add_round_key(state, round_key):
row = 4
col = 4
for i in range(row):
for j in range(col):
state[i][j] = state[i][j] ^ round_key[i][j]
def matrix2bytes(state):
flag = ""
for row in state:
for i in row:
flag += chr(i)
return flag
add_round_key(state, round_key)
print(matrix2bytes(state))
```
:::
:::spoiler Flag
crypto{r0undk3y}
:::
### Confusion through Substitution
:::spoiler sbox.py
```py=
s_box = (...)
inv_s_box = (...)
state = [
[251, 64, 182, 81],
[146, 168, 33, 80],
[199, 159, 195, 24],
[64, 80, 182, 255],
]
def sub_bytes(s, sbox=s_box):
???
print(sub_bytes(state, sbox=inv_s_box))
```
:::
Chalenge cho ta một ma trận `State` đã được S-box, nhiệm vụ của ta là phải đảo ngược quá trình này lại để tìm lại `State` ban đầu.
Vì đã được cho sẵn 2 mảng s_box và inv_s_box nên ta chỉ cần lấy giá trị của State rồi tra cứu trực tiếp vào mảng inv_s_box
```py=
state[i][j] = inv_s_box[state[i][j]]
```
:::spoiler solve.py
```py=
s_box = (...)
inv_s_box = (...)
state = [
[251, 64, 182, 81],
[146, 168, 33, 80],
[199, 159, 195, 24],
[64, 80, 182, 255],
]
def inv_sub_bytes(state, sbox=s_box):
row, col = 4,4
for i in range(row):
for j in range(col):
state[i][j] = inv_s_box[state[i][j]]
def matrix2bytes(state):
flag = ""
for row in state:
for i in row:
flag += chr(i)
return flag
inv_sub_bytes(state, sbox= inv_s_box)
print(matrix2bytes(state))
```
:::
::: spoiler Flag
crypto{l1n34rly}
:::
### Diffusion through Permutation
:::spoiler diffusion.py
```py=
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]
def inv_shift_rows(s):
???
# learned from http://cs.ucsb.edu/~koc/cs178/projects/JT/aes.c
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)
def mix_single_column(a):
# see Sec 4.1.2 in The Design of Rijndael
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])
def inv_mix_columns(s):
# see Sec 4.1.3 in The Design of Rijndael
for i in range(4):
u = xtime(xtime(s[i][0] ^ s[i][2]))
v = xtime(xtime(s[i][1] ^ s[i][3]))
s[i][0] ^= u
s[i][1] ^= v
s[i][2] ^= u
s[i][3] ^= v
mix_columns(s)
state = [
[108, 106, 71, 86],
[96, 62, 38, 72],
[42, 184, 92, 209],
[94, 79, 8, 54],
]
```
:::
Ta phải decryption quá trình AES này bằng 2 hàm là `inv_mix_columns` và `inv_shift_rows`.
Đối với AES thông thường, `ShiftRows` sẽ được thực hiện trên 1 cột của ma trận State, nhưng trong chall này thì tác giả `ShiftRows` trên hàng, do đó ta cũng phải `InverseShirtrows` trên hàng. Ta xây dựng hàm `inv_shift_rows` dựa trên hàm `shift_rows` như sau:
```py=
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]
def inv_shift_rows(s):
s[0][1], s[1][1], s[2][1], s[3][1] = s[3][1], s[0][1], s[1][1], s[2][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[1][3], s[2][3], s[3][3], s[0][3]
```
::: spoiler solve.py
```py=
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]
def inv_shift_rows(s):
s[0][1], s[1][1], s[2][1], s[3][1] = s[3][1], s[0][1], s[1][1], s[2][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[1][3], s[2][3], s[3][3], s[0][3]
# learned from http://cs.ucsb.edu/~koc/cs178/projects/JT/aes.c
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)
def mix_single_column(a):
# see Sec 4.1.2 in The Design of Rijndael
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])
def inv_mix_columns(s):
# see Sec 4.1.3 in The Design of Rijndael
for i in range(4):
u = xtime(xtime(s[i][0] ^ s[i][2]))
v = xtime(xtime(s[i][1] ^ s[i][3]))
s[i][0] ^= u
s[i][1] ^= v
s[i][2] ^= u
s[i][3] ^= v
mix_columns(s)
def matrix2bytes(state):
flag = ""
for row in state:
for i in row:
flag += chr(i)
return flag
state = [
[108, 106, 71, 86],
[96, 62, 38, 72],
[42, 184, 92, 209],
[94, 79, 8, 54],
]
inv_mix_columns(state)
inv_shift_rows(state)
print(matrix2bytes(state))
```
:::
::: spoiler Flag
crypto{d1ffUs3R}
:::
### Bringing It All Together
:::spoiler aes_decrypt.py
```py=
N_ROUNDS = 10
key = b'\xc3,\\\xa6\xb5\x80^\x0c\xdb\x8d\xa5z*\xb6\xfe\\'
ciphertext = b'\xd1O\x14j\xa4+O\xb6\xa1\xc4\x08B)\x8f\x12\xdd'
def expand_key(master_key):
"""
Expands and returns a list of key matrices for the given master_key.
"""
# Round constants https://en.wikipedia.org/wiki/AES_key_schedule#Round_constants
r_con = (
0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
)
# Initialize round keys with raw key material.
key_columns = bytes2matrix(master_key)
iteration_size = len(master_key) // 4
# Each iteration has exactly as many columns as the key material.
i = 1
while len(key_columns) < (N_ROUNDS + 1) * 4:
# Copy previous word.
word = list(key_columns[-1])
# Perform schedule_core once every "row".
if len(key_columns) % iteration_size == 0:
# Circular shift.
word.append(word.pop(0))
# Map to S-BOX.
word = [s_box[b] for b in word]
# XOR with first byte of R-CON, since the others bytes of R-CON are 0.
word[0] ^= r_con[i]
i += 1
elif len(master_key) == 32 and len(key_columns) % iteration_size == 4:
# Run word through S-box in the fourth iteration when using a
# 256-bit key.
word = [s_box[b] for b in word]
# XOR with equivalent word from previous iteration.
word = bytes(i^j for i, j in zip(word, key_columns[-iteration_size]))
key_columns.append(word)
# Group key words in 4x4 byte matrices.
return [key_columns[4*i : 4*(i+1)] for i in range(len(key_columns) // 4)]
def decrypt(key, ciphertext):
round_keys = expand_key(key) # Remember to start from the last round key and work backwards through them when decrypting
# Convert ciphertext to state matrix
# Initial add round key step
for i in range(N_ROUNDS - 1, 0, -1):
pass # Do round
# Run final round (skips the InvMixColumns step)
# Convert state matrix to plaintext
return plaintext
# print(decrypt(key, ciphertext))
```
:::
Ta được cung cấp 1 phần code của quá trình **decryption AES-128**. Nhiệm vụ của ta là hoàn thành đoạn code này để tìm ra được **Plaintext** ban đầu.
Chúng ta phải build thêm 4 hàm nữa:
- `AddRoundKey`: vì bản chất phép XOR là: $A \oplus B \oplus B = A$ nên ta chỉ cần AddRoundKey theo thứ tự ngược lại (tức là từ RoundKey[10] đến RoundKey[0]).
- `InvShiftRows`: Tương tự ShiftRows, nhưng thay vì dịch trái thì ta dịch phải
```py=
def inv_shift_rows(s):
s[0][1], s[1][1], s[2][1], s[3][1] = s[3][1], s[0][1], s[1][1], s[2][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[1][3], s[2][3], s[3][3], s[0][3]
```
- `InvSubBytes`: ta sẽ ánh xạ các bytes trong `State` vào bảng `InvSbox`.
```py=
def inv_sub_bytes(state):
for i in range(4):
for j in range(4):
state[i][j] = inv_s_box[state[i][j]]
```
- `InvMixColumns`: Việc tự build lại sẽ khá dài nên mình sẽ lấy hàm này từ challenge trước:
```py=
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)
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])
def inv_mix_columns(s):
# see Sec 4.1.3 in The Design of Rijndael
for i in range(4):
u = xtime(xtime(s[i][0] ^ s[i][2]))
v = xtime(xtime(s[i][1] ^ s[i][3]))
s[i][0] ^= u
s[i][1] ^= v
s[i][2] ^= u
s[i][3] ^= v
mix_columns(s)
```
> Ta phải chú ý 2 điều: Challenge này lưu ciphertext và plaintext theo kiểu hàng chứ không phải theo cột như AES thông thường, và ở Round cuối sẽ không có `InvMixColumns`
:::spoiler solve.py
```py=
s_box = (
0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)
inv_s_box = (
0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D,
)
N_ROUNDS = 10
key = b'\xc3,\\\xa6\xb5\x80^\x0c\xdb\x8d\xa5z*\xb6\xfe\\'
ciphertext = b'\xd1O\x14j\xa4+O\xb6\xa1\xc4\x08B)\x8f\x12\xdd'
def bytes2matrix(text):
return [list(text[i:i+4]) for i in range(0, 16, 4)]
def matrix2bytes(matrix):
byte = b''
for i in range(4):
for j in range(4):
byte += bytes([matrix[i][j]])
return byte
def expand_key(master_key):
"""
Expands and returns a list of key matrices for the given master_key.
"""
# Round constants https://en.wikipedia.org/wiki/AES_key_schedule#Round_constants
r_con = (
0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
)
# Initialize round keys with raw key material.
key_columns = bytes2matrix(master_key)
iteration_size = len(master_key) // 4
# Each iteration has exactly as many columns as the key material.
i = 1
while len(key_columns) < (N_ROUNDS + 1) * 4:
# Copy previous word.
word = list(key_columns[-1])
# Perform schedule_core once every "row".
if len(key_columns) % iteration_size == 0:
# Circular shift.
word.append(word.pop(0))
# Map to S-BOX.
word = [s_box[b] for b in word]
# XOR with first byte of R-CON, since the others bytes of R-CON are 0.
word[0] ^= r_con[i]
i += 1
elif len(master_key) == 32 and len(key_columns) % iteration_size == 4:
# Run word through S-box in the fourth iteration when using a
# 256-bit key.
word = [s_box[b] for b in word]
# XOR with equivalent word from previous iteration.
word = bytes(i^j for i, j in zip(word, key_columns[-iteration_size]))
key_columns.append(word)
# Group key words in 4x4 byte matrices.
return [key_columns[4*i : 4*(i+1)] for i in range(len(key_columns) // 4)]
def inv_shift_rows(s):
s[0][1], s[1][1], s[2][1], s[3][1] = s[3][1], s[0][1], s[1][1], s[2][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[1][3], s[2][3], s[3][3], s[0][3]
def inv_sub_bytes(state):
for i in range(4):
for j in range(4):
state[i][j] = inv_s_box[state[i][j]]
def add_round_keys(state, round_key):
for i in range(4):
for j in range(4):
state[i][j] ^= round_key[i][j]
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)
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])
def inv_mix_columns(s):
# see Sec 4.1.3 in The Design of Rijndael
for i in range(4):
u = xtime(xtime(s[i][0] ^ s[i][2]))
v = xtime(xtime(s[i][1] ^ s[i][3]))
s[i][0] ^= u
s[i][1] ^= v
s[i][2] ^= u
s[i][3] ^= v
mix_columns(s)
def decrypt(key, ciphertext):
round_keys = expand_key(key) # Remember to start from the last round key and work backwards through them when decrypting
# Convert ciphertext to state matrix
state = bytes2matrix(ciphertext)
# Initial add round key step
add_round_keys(state, round_keys[10])
for i in range(N_ROUNDS - 1, 0, -1):
inv_shift_rows(state)
inv_sub_bytes(state)
add_round_keys(state, round_keys[i])
inv_mix_columns(state)
# Run final round (skips the InvMixColumns step)
inv_shift_rows(state)
inv_sub_bytes(state)
add_round_keys(state, round_keys[0])
# Convert state matrix to plaintext
plaintext = matrix2bytes(state)
return plaintext
print(decrypt(key, ciphertext).decode())
```
:::
:::spoiler Flag
crypto{MYAES128}
:::
## Symmetric Starter
### Modes of Operation Starter
Ta được cung cấp đường [link](https://aes.cryptohack.org/block_cipher_starter) đến 1 trang web sử dụng kiểu mã hóa ECB:
Giờ nhiệm vụ\ là lấy được flag từ đây. Đọc source code ta thấy khi nhấn nút Submit ở phần `encrypt_flag()`,,sẽ nhận được phần flag đã bị encrypt. Còn hàm `decrypt()` sẽ decrypt bất kỳ ciphertext mà ta nhập vào.
Vậy giờ ta chỉ cần lấy encrypt_flag mà ta nhận được rồi gửi nó vào hàm `decrypt()` là xong.
:::spoiler Flag
crypto{bl0ck_c1ph3r5_4r3_f457_!}
:::
### Passwords as Keys
Vẫn tiếp tục là cách chơi cũ, nhưng lần này phải nhập đúng key (kết quả của việc băm chuỗi password_hash bằng md5) mới nhận được flag.
Ta được cung cấp một đường [link](https://gist.githubusercontent.com/wchargin/8927565/raw/d9783627c731268fb2935a731a618aa8e95cf465/words) chứa tổng cộng 99171 cái password, nên có thể bruteforce băm từng cái password rồi tính plaintext thử.
Mình sẽ dùng thư viện `request` để tương tác với web này (gửi/nhận dữ liệu)
::: spoiler solve.py
```py=
import requests
import hashlib
from Crypto.Util.number import *
url = "https://aes.cryptohack.org/passwords_as_keys/"
r = requests.get(f"{url}encrypt_flag/")
data = r.json()
ciphertext = data["ciphertext"]
get_password = requests.get(
"https://gist.githubusercontent.com/wchargin/8927565/raw/d9783627c731268fb2935a731a618aa8e95cf465/words"
)
password = get_password.text
for words in password.split("\n"):
key = hashlib.md5(words.encode()).digest()
r = requests.get(f"{url}decrypt/{ciphertext}/{key.hex()}/")
data = r.json()
plaintext = data["plaintext"]
flag = bytes.fromhex(plaintext)
if b"crypto{" in flag:
print(flag)
break
```
:::
::: spoiler Flag
crypto{k3y5__r__n07__p455w0rdz?}
:::
## Block Ciphers 1
### ECB CBC WTF
Link challenge: https://aes.cryptohack.org/ecbcbcwtf.
::: spoiler
```py= source.py
from Crypto.Cipher import AES
KEY = ?
FLAG = ?
@chal.route('/ecbcbcwtf/decrypt/<ciphertext>/')
def decrypt(ciphertext):
ciphertext = bytes.fromhex(ciphertext)
cipher = AES.new(KEY, AES.MODE_ECB)
try:
decrypted = cipher.decrypt(ciphertext)
except ValueError as e:
return {"error": str(e)}
return {"plaintext": decrypted.hex()}
@chal.route('/ecbcbcwtf/encrypt_flag/')
def encrypt_flag():
iv = os.urandom(16)
cipher = AES.new(KEY, AES.MODE_CBC, iv)
encrypted = cipher.encrypt(FLAG.encode())
ciphertext = iv.hex() + encrypted.hex()
return {"ciphertext": ciphertext}
```
:::
Từ source code ta thấy rằng: Flag được mã hóa bằng **CBC** nhưng bị giải mã bằng **ECB**. Và trong `Ciphertext` thì nó có chứa luôn `IV` ở phần đầu
Chú ý vào `Ciphertext` sẽ thấy rằng nó có độ dài là 96 hex = 48 byte. Trong đó `IV` = 16 byte. Vậy `Ciphertext` thật sự sẽ có độ dài = 48 - 16 = 32 byte. **Vậy quá trình mã hóa này sẽ gồm 2 block.**
> Dù dùng bất cứ mode nào trong AES (ECB, CFB, OFB, CTR, ...). Bản thân thuật toán AES sẽ luôn mã hóa theo từng block 16 byte.
Mình sẽ minh họa 2 quá trình encrypt và decrypt như sau:
- CBC encryption
- ECB decryption.
Vì Flag được chia thành 2 block, nên mình sẽ gọi $P_1$ là phần đầu của Flag, còn $P_2$ là phần sau của Flag. Tương đương với đó là $C_1, C_2$ (với $C_1 = E_K(P_1 \oplus IV)$ và $C_2 = E_K(P_2 \oplus C_1)$)
Vậy lúc này ta có: $$Ciphertext = IV + C_1 + C_2$$
Nên nếu tách $C_1$ từ Ciphertext ra rồi gửi nó vô ECB decryption. Ta sẽ nhận được $Plaintext_1$, với $Plaintext_1 = P_1 \oplus IV$. Ta có thể tìm $P_1$ bằng cách lấy $Plaintext_1 \oplus IV = P_1 \oplus IV \oplus IV = P_1$.
Tương tự, ta có thể tìm ra $P_2 = Plaintext \oplus C_1$.
:::spoiler solve.py
```py=
from pwn import *
import requests
url = "https://aes.cryptohack.org/ecbcbcwtf/"
r = requests.get(url + "encrypt_flag/")
data = r.json()
ciphertext = data["ciphertext"]
iv = ciphertext[:32]
c_1 = ciphertext[32:64]
c_2 = ciphertext[64:]
send_c1 = requests.get(url + "decrypt/" + f"{c_1}")
data = send_c1.json()
plaintext_1 = data["plaintext"]
p_1 = xor(bytes.fromhex(plaintext_1), bytes.fromhex(iv))
send_c2 = requests.get(url + "decrypt/" + f"{c_2}")
data = send_c2.json()
plaintext_2 = data["plaintext"]
p_2 = xor(bytes.fromhex(plaintext_2), bytes.fromhex(c_1))
flag = p_1 + p_2
print(flag.decode())
```
:::
::: spoiler Flag
crypto{3cb_5uck5_4v01d_17_!!!!!}
:::
### ECB Oracle
Link web challenge: https://aes.cryptohack.org/ecb_oracle/
::: spoiler source.py
```py=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
KEY = ?
FLAG = ?
@chal.route('/ecb_oracle/encrypt/<plaintext>/')
def encrypt(plaintext):
plaintext = bytes.fromhex(plaintext)
padded = pad(plaintext + FLAG.encode(), 16)
cipher = AES.new(KEY, AES.MODE_ECB)
try:
encrypted = cipher.encrypt(padded)
except ValueError as e:
return {"error": str(e)}
return {"ciphertext": encrypted.hex()}
```
:::
Ta nhận thấy rằng tác giả sử dụng ECB mode, bên cạnh đó Flag được cộng vào phía sau plaintext mà ta nhập vào, rồi sau đó đem cả 2 đi pad để thu được các block có độ dài 16.
Vì flag bị đính kèm theo plaintext như vậy và cộng với việc ta có thể gửi plaintext nhiều lần, nên có thể xác định đây là kiểu tấn công: Chosen Plaintext attack (mình có nói chi tiết hơn ở phần đầu[](https://)).
Đầu tiên mình gửi đi 32 hex (tương đương 16 byte) plaintext có giá trị là 0 để xác định độ dài Flag thử:
```py=
import requests
url = "http://aes.cryptohack.org/ecb_oracle/encrypt/"
def encrypt(pt):
r = requests.get(url + pt)
return r.json()['ciphertext']
test = encrypt("0" * 32)
print(test, len(test))
```
ouput là chuỗi hex: `faf1a9589996d408acb1e774324c195175829521ed58d56e0acbf0641ddee18e10501d0c4f881962fb6fd997db9ae87b` có độ dài là 96 hex = 48 byte = 3 block.
Điều này có nghĩa rằng: $32 < 16 + len(Flag) \le 48$, tương đương $16 < len(Flag) \le 32$
Vậy Flag nằm trên 2 block, do đó ta pad cả 2 phía như sau:
```py=
guess = flag + c
pad_len = block_size - (len(guess) % block_size)
pad = "A" * pad_len
pt = pad + guess + pad
```
với $c$ là ký tự mà ta muốn brute-force, khi ta gửi plaintext này lên sever thì nó được pad thêm với flag và sẽ thành một chuỗi có dạng $pad||guess||pad||flag$, nên ta chỉ cần so sánh $E_K(pad||guess)$ và $E_K(pad||flag)$, nếu nó bằng nhau thì ta đã đoán đúng $c$.
:::spoiler solve.py
```py=
import requests
url = "http://aes.cryptohack.org/ecb_oracle/encrypt/"
def encrypt(pt):
r = requests.get(url + pt.encode().hex())
return bytes.fromhex(r.json()['ciphertext'])
chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890_{}"
block_size = 16
flag = "crypto{"
while True:
for c in chars:
guess = flag + c
pad_len = block_size - (len(guess) % block_size)
pad = "A" * pad_len
pt = pad + guess + pad
ct = encrypt(pt)
size = (pad_len + len(guess))
part1, part2 = ct[:size], ct[size : size + size]
if part1 == part2:
flag += c
if flag[-1] == "}":
print(flag)
break
```
:::
### Flipping Cookie
Link challenge: https://aes.cryptohack.org/flipping_cookie/
source:
```py=
from Crypto.Cipher import AES
import os
from Crypto.Util.Padding import pad, unpad
from datetime import datetime, timedelta
KEY = ?
FLAG = ?
@chal.route('/flipping_cookie/check_admin/<cookie>/<iv>/')
def check_admin(cookie, iv):
cookie = bytes.fromhex(cookie)
iv = bytes.fromhex(iv)
try:
cipher = AES.new(KEY, AES.MODE_CBC, iv)
decrypted = cipher.decrypt(cookie)
unpadded = unpad(decrypted, 16)
except ValueError as e:
return {"error": str(e)}
if b"admin=True" in unpadded.split(b";"):
return {"flag": FLAG}
else:
return {"error": "Only admin can read the flag"}
@chal.route('/flipping_cookie/get_cookie/')
def get_cookie():
expires_at = (datetime.today() + timedelta(days=1)).strftime("%s")
cookie = f"admin=False;expiry={expires_at}".encode()
iv = os.urandom(16)
padded = pad(cookie, 16)
cipher = AES.new(KEY, AES.MODE_CBC, iv)
encrypted = cipher.encrypt(padded)
ciphertext = iv.hex() + encrypted.hex()
return {"cookie": ciphertext}
```
Ta phân tích hàm `get_cookie()`:
```py=
def get_cookie():
expires_at = (datetime.today() + timedelta(days=1)).strftime("%s")
cookie = f"admin=False;expiry={expires_at}".encode()
iv = os.urandom(16)
padded = pad(cookie, 16)
cipher = AES.new(KEY, AES.MODE_CBC, iv)
encrypted = cipher.encrypt(padded)
ciphertext = iv.hex() + encrypted.hex()
return {"cookie": ciphertext}
```
Khi ta bấm nhận **cookie**, ta sẽ nhận được 1 chuỗi **cookie** có 96 hex = 48 byte, 16 byte đầu trong đó sẽ là $IV$, còn 32 byte còn lại là **ciphertext**.
Tiếp theo đến hàm `check_admin()`:
```py=
def check_admin(cookie, iv):
cookie = bytes.fromhex(cookie)
iv = bytes.fromhex(iv)
try:
cipher = AES.new(KEY, AES.MODE_CBC, iv)
decrypted = cipher.decrypt(cookie)
unpadded = unpad(decrypted, 16)
except ValueError as e:
return {"error": str(e)}
if b"admin=True" in unpadded.split(b";"):
return {"flag": FLAG}
else:
return {"error": "Only admin can read the flag"}
```
Hàm này sẽ nhận vào 2 giá trị mà ta nhập: **cookie** và $IV$. nó sẽ dùng **cookie** làm **ciphertext**, $IV$ thì đúng bằng $IV$ mà ta nhập vào để thực hiện quá trình **decrypt** với **CBC mode**. Sau khi **decrypt**, sẽ **split plaintext** ra bằng ký tự `;`, nếu có bất kỳ phần tử nào bằng `b"admin=True"` thì in ra **Flag**, còn không thì in "Only admin can read the flag".
Vậy ta đã xác định được cần phải làm gì rồi. Ta phải sử dụng **cookie** hoặc $IV$ nào đó để **plaintext** giải ra có chuỗi byte b"admin=True;"`
- Trường hợp 1: Thay đổi **cookie** (**ciphertext**)
- Liệu rằng ta có thể thay đổi **cookie**?, câu trả lời là không. Vì ta biết rằng, **cookie** được tạo bằng đoạn code sau:
```py=
cookie = f"admin=False;expiry= {expires_at}".encode()
```
- Nên phần `b"admin=False"` sẽ nằm ở phần đầu (**block 0**), do đó chỉ có thể thay đổi $IV$ (giải thích chi tiết ở phần lý thuyết CBC Bit Flipping Attack).
- Trường hợp 2: thay đổi $IV$
- Ta biết rằng sẽ phải thay đổi $IV$ để plaintext ở **block 0** xuất hiện `b"admin=True"`.
Gọi **plaintext block 0** là $P_1$, ta có $P_1 = D_K(C_i) \oplus IV$, gọi $P_1'$ là **plaintext fake** (plaintext có `b"admin=True"`), để $P_1$ thành $P_1'$ thì ta thay $IV = IV \oplus P_1 \oplus P_1'$, lúc này $D_K(C_i) \oplus IV = D_K(C_i) \oplus IV \oplus P_i \oplus P_i' = P_i \oplus P_i \oplus P_i' = 0 \oplus P_i' = P_i'$
Vậy ta đã tìm ra cách để có được $P_1'$, vấn đề đặt ra là nên đặt $P_1'$ là gì. Câu trả lời là bất cứ chuỗi byte nào có đủ 16 byte, chỉ với điều kiện là có chuỗi con `b"admin=True;"` trong chuỗi $P_1'$ đó, ta làm được điều này là vì tác giả không đọc toàn bộ plaintext của ta, chỉ cần sau khi split plaintext đó ra bằng ký tự `;` mà nó có chuỗi byte `b"admin=True"` thì sẽ thu được Flag.
Còn với $P_1$ thì sẽ bằng 16 byte đầu của **cookie**, dù **cookie** có bị thay đổi theo thời gian nhưng phần đầu `b"admin=False;expi"` thì **cố định**.
:::spoiler solve
```py=
from pwn import *
import requests
url = "https://aes.cryptohack.org/flipping_cookie/"
def get_cookie():
r = requests.get(url + "get_cookie/")
return r.json()["cookie"]
def get_flag(ciphertext, iv):
r = requests.get(url + "check_admin/" + ciphertext + "/" + iv + "/")
return r.json()
cookie = bytes.fromhex(get_cookie())
iv = cookie[:16]
ciphertext = cookie[16:]
p1_fake = b"admin=True;00000"
p1 = b"admin=False;expi"
iv = xor(iv, p1, p1_fake)
flag = get_flag(ciphertext.hex(), iv.hex())
print(flag)
```
:::
:::spoiler Flag
crypto{4u7h3n71c4710n_15_3553n714l}
:::
### Lazy CBC
Link challenge: https://aes.cryptohack.org/lazy_cbc/
source
```py=
from Crypto.Cipher import AES
KEY = ?
FLAG = ?
@chal.route('/lazy_cbc/encrypt/<plaintext>/')
def encrypt(plaintext):
plaintext = bytes.fromhex(plaintext)
if len(plaintext) % 16 != 0:
return {"error": "Data length must be multiple of 16"}
cipher = AES.new(KEY, AES.MODE_CBC, KEY)
encrypted = cipher.encrypt(plaintext)
return {"ciphertext": encrypted.hex()}
@chal.route('/lazy_cbc/get_flag/<key>/')
def get_flag(key):
key = bytes.fromhex(key)
if key == KEY:
return {"plaintext": FLAG.encode().hex()}
else:
return {"error": "invalid key"}
@chal.route('/lazy_cbc/receive/<ciphertext>/')
def receive(ciphertext):
ciphertext = bytes.fromhex(ciphertext)
if len(ciphertext) % 16 != 0:
return {"error": "Data length must be multiple of 16"}
cipher = AES.new(KEY, AES.MODE_CBC, KEY)
decrypted = cipher.decrypt(ciphertext)
try:
decrypted.decode() # ensure plaintext is valid ascii
except UnicodeDecodeError:
return {"error": "Invalid plaintext: " + decrypted.hex()}
return {"success": "Your message has been received"}
```
Challenge này sử dụng CBC mode, nhưng điều đặt biệt là dùng $IV = Key$, điều này sẽ sinh ra lỗ hỏng rất nghiêm trọng.
Mình đã suy nghĩ ra 2 cách để giải bài này:
Cách 1:
Vì $IV = Key$ nên $C_1 = E_K(P_1 \oplus IV) = E_K(P_1 \oplus Key)$, vậy nếu ta chọn $P_1 = 0$ thì $C_1 = E_K(0 \oplus Key) = E_K(Key)$, vậy $Key = D_K(C_1)$, vậy ta chỉ cần gửi $C_1$ vô hàm `receive()` là sẽ nhận được $Key$. Nhưng hàm `receive()` có 1 cái khá khó chịu:
```py=
try:
decrypted.decode() # ensure plaintext is valid ascii
except UnicodeDecodeError:
return {"error": "Invalid plaintext: " + decrypted.hex()}
return {"success": "Your message has been received"}
```
Tức là nếu $C_1$ được decrypt xong mà nó có chứa ký tự Ascii không hợp lệ thì mới được in ra, còn nếu tất cả các ký tự đều hợp lệ thì ta sẽ nhận được thông báo "Your message has been received". Mình đã thử gửi $C_1$ vô hàm này, nó không in ra được plantext ta cần, nên ta phải pad thêm 16 byte trước $C_1$ để làm lỗi plaintext.
Lúc này ta có chuỗi mới $C_1' = pad||C1$, $Key$ sẽ bằng **block thứ 2** của $P_1'$.
::: spoiler solve
```py=
from pwn import *
import requests
url = "https://aes.cryptohack.org/lazy_cbc/"
def encrypt(plaintext):
r = requests.get(url + "encrypt/" + plaintext + "/")
return r.json()["ciphertext"]
def decrypt(ciphertext):
r = requests.get(url + "receive/" + ciphertext + "/")
return r.json()["error"].split(": ")[1]
def get_flag(key):
r = requests.get(url + "get_flag/" + key + "/")
return r.json()["plaintext"]
plaintext = "0" * 32
c1 = encrypt(plaintext)
pad = "0" * 32
c1_padded = pad + c1
p1 = decrypt(c1_padded)
key = p1[32:]
flag = bytes.fromhex(get_flag(key)).decode()
print(flag)
```
:::
::: spoiler Flag
crypto{50m3_p30pl3_d0n7_7h1nk_IV_15_1mp0r74n7_?}
:::
Cách 2:
Cách này thậm chí sẽ không cần dùng hàm `encrypt()`.
Ta biết quá trình decrypt của CBC mode như sau (giả sử với 2 block):
- $P_1 = D_K(C_1) \oplus Key$
- $P_2 = D_K(C_2) \oplus C1$
Vậy nếu ta cố tình chọn $C_2 = C_1$ thì:
- $P_1 = D_K(C_1) \oplus Key \hspace{5mm} (1)$
- $P_2 = D_K(C_1) \oplus C_1 \hspace{5mm} (2)$
Phương trình (2) tương đương với $D_K(C1) = P_2 \oplus C1$, thay $D_K(C_1)$ vào phương trình (1) ta được $P_1 = P_2 \oplus C1 \oplus Key$.
- Vậy $Key = P_1 \oplus P_2 \oplus C1$
> Có thể chọn $C_1 = 0$ để rút gọn phương trình trên trở thành $Key = P_1 \oplus P_2$
::: spoiler solve
```py=
from pwn import *
import requests
url = "https://aes.cryptohack.org/lazy_cbc/"
def encrypt(plaintext):
r = requests.get(url + "encrypt/" + plaintext + "/")
return r.json()["ciphertext"]
def decrypt(ciphertext):
r = requests.get(url + "receive/" + ciphertext + "/")
return r.json()["error"].split(": ")[1]
def get_flag(key):
r = requests.get(url + "get_flag/" + key + "/")
return r.json()["plaintext"]
c1 = "0" * 32
c2 = c1
p = decrypt(c1 + c2)
p1 = p[:32]
p2 = p[32:]
key = xor(bytes.fromhex(p1), bytes.fromhex(p2))
flag = get_flag(key.hex())
print(bytes.fromhex(flag).decode())
```
:::
## Authenticated Encryption
### Paper Plane
source sever:
```py=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import os
KEY = ?
FLAG = ?
class AesIge:
def __init__(self, key):
self.cipher = AES.new(key, AES.MODE_ECB)
def encrypt(self, data, m0=os.urandom(16), c0=os.urandom(16)):
data = pad(data, 16, 'pkcs7')
last_block_plaintext = m0
last_block_ciphertext = c0
result = b''
for i in range(0, len(data), 16):
block = data[i: i + 16]
x = AesIge._xor_blocks(block, last_block_ciphertext)
x = self.cipher.encrypt(x)
x = AesIge._xor_blocks(x, last_block_plaintext)
result += x
last_block_plaintext = block
last_block_ciphertext = x
return result, m0, c0
def decrypt(self, data, m0, c0):
last_block_plaintext = m0
last_block_ciphertext = c0
result = b''
for i in range(0, len(data), 16):
block = data[i: i + 16]
x = AesIge._xor_blocks(block, last_block_plaintext)
x = self.cipher.decrypt(x)
x = AesIge._xor_blocks(x, last_block_ciphertext)
result += x
last_block_ciphertext = block
last_block_plaintext = x
if AesIge._is_pkcs7_padded(result):
return unpad(result, 16, 'pkcs7')
else:
return None
@staticmethod
def _is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))
@staticmethod
def _xor_blocks(a, b):
return bytes([x ^ y for x, y in zip(a, b)])
@chal.route('/paper_plane/encrypt_flag/')
def encrypt_flag():
ciphertext, m0, c0 = AesIge(KEY).encrypt(FLAG.encode())
return {"ciphertext": ciphertext.hex(), "m0": m0.hex(), "c0": c0.hex()}
@chal.route('/paper_plane/send_msg/<ciphertext>/<m0>/<c0>/')
def send_msg(ciphertext, m0, c0):
ciphertext = bytes.fromhex(ciphertext)
m0 = bytes.fromhex(m0)
c0 = bytes.fromhex(c0)
if len(ciphertext) % 16 != 0:
return {"error": "Data length must be a multiple of the blocksize!"}
if len(c0) != 16 or len(m0) != 16:
return {"error": "m0 and c0 must be 16 bytes long!"}
plaintext = AesIge(KEY).decrypt(ciphertext, m0, c0)
if plaintext is not None:
return {"msg": "Message received"}
else:
return {"error": "Can't decrypt the message."}
```
Bài này là một biến thể nâng cao của Padding Oracle Attack, sử dụng IGE mode (Infinite Garble Extension) thay vì CBC thông thường.
Chế độ IGE (Infinite Garble Extension) có công thức giải mã phức tạp hơn CBC một chút vì nó sử dụng cả Ciphertext và Plaintext của khối trước đó để giải mã khối hiện tại.
Phân tích class `AesIge.decrypt()`:
```py=
def decrypt(self, data, m0, c0):
last_block_plaintext = m0
last_block_ciphertext = c0
result = b''
for i in range(0, len(data), 16):
block = data[i: i + 16]
x = AesIge._xor_blocks(block, last_block_plaintext)
x = self.cipher.decrypt(x)
x = AesIge._xor_blocks(x, last_block_ciphertext)
result += x
last_block_ciphertext = block
last_block_plaintext = x
```
Tức là nó sẽ nhận vào 3 tham số:
- Khối Ciphertext hiện tại: $C_i$
- Plaintext $M_{i-1}$
- Khối Ciphertext trước $C_{i-1}$.
Rồi giải mã theo công thức:
$$P_i = D_K(C_i \oplus M_{i-1}) \oplus C_{i-1}$$
Bên cạnh đó ta có hàm `send_msg()` hoạt động như một Oracle như sau:
```py=
def send_msg(ciphertext, m0, c0):
ciphertext = bytes.fromhex(ciphertext)
m0 = bytes.fromhex(m0)
c0 = bytes.fromhex(c0)
if len(ciphertext) % 16 != 0:
return {"error": "Data length must be a multiple of the blocksize!"}
if len(c0) != 16 or len(m0) != 16:
return {"error": "m0 and c0 must be 16 bytes long!"}
plaintext = AesIge(KEY).decrypt(ciphertext, m0, c0)
if plaintext is not None:
return {"msg": "Message received"}
else:
return {"error": "Can't decrypt the message."}
```
Tức là nó nhận vào 3 tham số như hàm decrypt, rồi tiến hành giải mã
- Nếu unpad thành công: trả về `Message received`
- Nếu lỗi padding: trả về `Can't decrypt`
Điểm mấu chốt:Chúng ta có thể kiểm soát hoàn toàn 3 tham số đầu vào của hàm giải mã. nhìn lại công thức:$$P_i = D_K(C_i \oplus M_{i-1}) \oplus C_{i-1}$$
Để tấn công khối $C_i$ của ciphertext gốc:
- Chúng ta cần biết $M_{i-1}$ (Plaintext của khối trước). May mắn là chúng ta giải mã từ đầu đến cuối, nên khi giải mã khối 2, ta đã biết Plaintext khối 1.
- Chúng ta gửi request lên server với:
- `ciphertext`: gửi khối $C_i$ cần giải mã.
- `m0`: Gửi $M_{i-1}$ thật (đã biết).
- `c0`: Đây là cái ta sẽ thay đổi để thực hiện Padding Oracle, giống như ta thay đổi IV trong CBC attack.
Khi đó Server sẽ tính:$$P'_{i} = D_K(C_i \oplus M_{i-1}) \oplus c0_{fake}$$
Công thức kiểu này hoàn toàn giống với CBC. Ta sẽ tìm được giá trị trung gian $I = D_K(C_i \oplus M_{i-1})$.
Sau khi tìm được $I$, Plaintext thật của khối đó là:$$P_i = I \oplus C_{i-1}$$
- ($C_{i-1}$) là ciphertext thật của khối trước)
||phân tích thì đơn giản nhưng để mà viết script thì nó .....||
::: spoiler solve
```py=
from pwn import *
import json
import requests
URL = "https://aes.cryptohack.org/paper_plane/"
def get_encrypt_flag():
r = requests.get(f"{URL}/encrypt_flag/")
data = r.json()
return (bytes.fromhex(data['ciphertext']), bytes.fromhex(data['m0']), bytes.fromhex(data['c0']))
def oracle(ct_block, m0, c0):
url = f"{URL}/send_msg/{ct_block.hex()}/{m0.hex()}/{c0.hex()}/"
r = requests.get(url)
resp = r.json()
if "error" in resp:
return False
return True
def decrypt(target_ct_block, pre_pt, pre_ct):
I = [0] * 16
pt = [0] * 16
fake_c0 = bytearray(16)
for byte_index in range(15, -1, -1):
pad = 16 - byte_index
for k in range(byte_index + 1, 16):
fake_c0[k] = I[k] ^ pad
for guess in range(256):
#print(guess)
fake_c0[byte_index] = guess
if oracle(target_ct_block, pre_pt, fake_c0):
i_val = guess ^ pad
I[byte_index] = i_val
pt_val = i_val ^ pre_ct[byte_index]
pt[byte_index] = pt_val
break
return bytes(pt)
full_ct, real_m0, real_c0 = get_encrypt_flag()
blocks = [full_ct[i:i+16] for i in range(0, len(full_ct), 16)]
pt = b""
prev_pt = real_m0
prev_ct = real_c0
for block in blocks:
decrypted = decrypt(block, prev_pt, prev_ct)
pt += decrypted
prev_pt = decrypted
prev_ct = block
print(pt)
```
:::
::: spoiler Flag
crypto{h3ll0_t3l3gr4m}
:::
Sign in with Wallet
Connect another wallet