Lý thuyết AES-DES

# Lý thuyết ## I. AES - **AES** là viết tắt của từ tiếng anh: **Advanced Encryption Standard** *(tiêu chuẩn mã hóa nâng cao)* là thuật toán mã hóa khối tức là nó chia dữ liệu thành các khối có kích thước cố định (16 byte) và áp dụng các phép biến đổi lên từng khối. Các phép biến đổi bao gồm: *hoán vị byte, thay thế byte, xoay hàng, trộn cột và thêm khóa*. - **AES** là loại thuật toán **mã hóa đối xứng** sử dụng cùng một loại khóa cho cả mã hóa và giải mã được chính phủ Hoa Kì áp dụng và được công bố vào 2001. - **AES** sử dụng kích thước khối cố định là 128 bit và kích thước khóa 128, 192 hoặc 256 bit tương ứng với AES-128, AES-192 và AES-256. Các khóa mở rộng sử dụng trong chu trình được tạo ra bởi thủ tục **sinh khóa Rijndael**. - Tùy thuộc vào độ dài của khóa khi sử dụng 128bit, 192bit hay 256bit mà thuật toán được thực hiện với số lần lặp khác nhau. Số vòng: - 10 vòng cho AES-128 - 12 vòng cho AES-192 - 14 vòng cho AES-256 - Hầu hết các phép toán trong thuật toán **AES** đều thực hiện trong một trường hữu hạn của các byte. Mỗi khối dữ liệu đầu vào 128bit được chia thành 16byte, có thể xếp thành 4 cột, mỗi cột 4 byte hay một ma trận 4x4 của các byte, nó gọi là ma trận trạng thái. ![image](https://hackmd.io/_uploads/Sk1okKM8kx.png) ![image](https://hackmd.io/_uploads/Sko0tdMIye.png) - Vòng lặp chính của AES thực hiện các hàm sau: - SubBytes(): thay thế các byte dữ liệu (trạng thái) - ShiftRows(): Dịch vòng dữ liệu (trạng thái) cụ thể là dịch vòng trái - MixColumns(): Trộn cột dữ liệu (trạng thái) vào với một cột dữ liệu khác - AddRoundKey(): Chèn khóa vòng vào khối dữ liệu trạng thái ### Mô hình thuật toán **mã hóa** và **giải mã** của **AES**: ![image](https://hackmd.io/_uploads/Bkuydnz8kx.png) - **Cơ chế mã hóa AES-128:** - Khối dữ liệu trạng thái (state block): Dữ liệu trong quá trình mã hóa lúc này có trạng thái là ma trận 4x4. Trong sơ đồ là plaintext, mỗi byte của khối dữ liệu này sẽ được thao tác trong các bước mã hóa sau. - Trước khi bước vào quá trình mã hóa ta còn thêm một bước chuẩn bị nữa đó là bước **mở rộng khóa** (key expansion). $\Rightarrow$ Đây là bước tạo ra các **khóa vòng** (round keys) từ **khóa ban đầu** (master key). Bước key expansion này từ key ban đầu(dài 16 bytes) tạo ra thêm $10$ key (dài 16 bytes), nghĩa là sau bước **key exoansion** ta có tổng cộng $11$ khóa vòng (1 khóa ban đầu master key + 10 khóa vòng dùng cho các vòng mã hóa). **Note:** Bước key expansion sẽ tạo ra số khóa con để Xor với khối trạng thái ở các bước AddRoundKey $\rightarrow$ số lượng khóa con phụ thuộc vào số lượng bước AddRoungKey trong bước Round (vòng) $\rightarrow$ phụ thuộc vào số vòng. Do đây là mã hóa AES-128 sẽ có 10 vòng nên bước `key expansion` sẽ tạo thêm 10 khóa con $\rightarrow$ Nếu mã hóa AES-192, AES-256 thì bước `key expasion` sẽ tạo thêm lần lượt 12, 14 khóa con. - Tiếp theo ta tới bước **AddRoundKey** đầu tiên trong sơ đồ (chèn khóa vòng vào trạng thái) hay còn gọi là **Initial key addition**. trong bước này ta **XOR** khóa ban đầu (khóa chủ master key) với state block (dữ liệu ban đầu Plaintext), sau khi **XOR** xong ta sẽ có một khối trạng thái (state block) mới. - Sau bước **AddRoundKey** thì ta tới bước **Round** (encryption round + last round) tổng cộng có $10$ vòng (vì AES-128). - Encryption Round (mã hóa vòng): quá trình này được lặp lại 9 vòng. Mỗi vòng gồm 4 bước: **SubBytes, ShiftRows, MixColumns, AddRoundKey**. - Last Round (vòng cuối): gồm có 1 vòng. Vòng cuối này cũng giống với **Encryption Round**, tuy nhiên không có bước **MixColumns** - **Cơ chế giải mã AES-128:** Cơ chế giải mã cũng gồm các bước giống mã hóa. Tuy nhiên ở khác nhau ở thứ tự thực hiện các hàm ở bước Round: - Decryption Round cũng gồm 4 bước nhưng thứ tự khác mã hóa: **invshiftRows, invSubBytes, invMixColumns, AddRoundKey**. - Last Round có 3 bước: **invShiftRows, invSubBytes, AddRoundKey** Tiếp theo chúng ta tìm hiểu các hàm thành phần: **SubBytes, ShiftRows, MixColumns, AddRoundKey.** ### 1. SubBytes - SubBytes(): Thực hiện phép thay thế các byte của khối trạng thái đầu vào bằng cách sử dụng một bảng thế **S-box** (Substitution Box) ![image](https://hackmd.io/_uploads/rkAtoPq81x.png) - S-box: Là một bảng duy nhất, gồm 16x16 (hàng x cột) ![image](https://hackmd.io/_uploads/SyEV1dcLkg.png) Ví dụ ta **SubBytes** khối: ![image](https://hackmd.io/_uploads/BJ2cJu9UJg.png) - Đầu tiên Byte $S_{0,0}$ có giá trị là "$19$" đối chiếu qua S-box (*"1" ở hàng 2 và "9" ở cột 10*) $\rightarrow$ tương ứng với $d4$ - Byte $S_{0,1}$ có giá trị là "$a0$" $\rightarrow$ $e0$ Các Bytes khác cũng so sánh tượng tự như vậy ![image](https://hackmd.io/_uploads/rJDsmu9I1x.png) $\Rightarrow$ **SubBytes** nhầm mục đích giúp phá vỡ tính cấu trúc trong dữ liệu gốc (bản rõ), Kết quả sau SubBytes không còn liên quan trực tiếp đến cấu trúc của bản rõ, làm cho việc dự đoán hoặc giải mã trở nên khó khăn. ### 2. ShiftRows - ShiftRows(): Áp dụng lên khối trạng thái bằng cách dịch vòng ba hàng cuối của khối trạng thái qua bên trái với số byte bị dịch khác nhau. ![image](https://hackmd.io/_uploads/SJe9ykncUJe.png) - Hàng một không dịch - Hàng hai dịch trái 1 byte nghĩa là toàn bộ khối bytes lần lượt dịch sang trái 1 khối - Tương tự hàng ba dịch trái 2 bytes, hàng bốn dịch trái 4 bytes - Ví dụ: Ta tiếp tục **ShiftRows** ma trận \begin{bmatrix} d4& e0& b8& 1e\\ 27& bf& b4& 41\\ 11& 98& 5d& 52\\ ae& f1& e5& 30 \end{bmatrix} - Hàng 1: giữ nguyên - Hàng 2: Mỗi khối byte dịch vòng sang trái 1 ô $$ \begin{bmatrix} 27& bf& b4& 41 \end{bmatrix} \rightarrow \begin{bmatrix} bf& b4& 41& 27 \end{bmatrix} $$ - Hàng 3: Mỗi khối byte dịch vòng sang trái 2 khối bytes $$ \begin{bmatrix} 11& 98& 5d& 52 \end{bmatrix} \rightarrow \begin{bmatrix} 5d&52&11&98 \end{bmatrix} $$ - Hàng 4: Mỗi khối byte dịch vòng sang trái 3 khối $$ \begin{bmatrix} ae&f1&e5&30 \end{bmatrix} \rightarrow \begin{bmatrix} 30&ae&f1&e5 \end{bmatrix} $$ - Cuối cùng sau khi **ShiftRows** ta có ma trận sau: \begin{bmatrix} d4&e0&b8&1e\\ bf&b4&41&27\\ 5d&52&11&98\\ 30&ae&f1&e5 \end{bmatrix} $\Rightarrow$ **ShiftRows** giúp phá vỡ cấu trúc tuyến tính giữa các byte trong cùng một cột của ma trận trạng thái, làm cho mối quan hệ giữa đầu vào và đầu ra trở nên phức tạp hơn, giúp các cột không bị mã hóa độc lập ### 3. MixColumns - **MixColums()**: Làm việc trên các cột của khối trạng thái. Các cột được coi như là đa thức trong trường $GF(2^8)$ và nhân với một ma trận a(X) cố định. - Ma trận hằng số a(X) : \begin{bmatrix} 02&03&01&01\\ 01&02&03&01\\ 01&01&02&03\\ 03&01&01&02 \end{bmatrix} ![image](https://hackmd.io/_uploads/ryQmSsAI1l.png) - Mô tả bằng ma trận như sau: $$ \begin{bmatrix} S^,_{0,c}\\ S^,_{1,c}\\ S^,_{2,c}\\ S^,_{3,c} \end{bmatrix} = \begin{bmatrix} 02&03&01&01\\ 01&02&03&01\\ 01&01&02&03\\ 03&01&01&02 \end{bmatrix} \times \begin{bmatrix} S_{0,c}\\ S_{1,c}\\ S_{2,c}\\ S_{3,c} \end{bmatrix} $$ - Công thức chi tiết cho phần tử của mỗi cột là: $$S^,(X)=a(X) \bigotimes S(X)$$ - $S^,_{0,c}=(02 \times S_{0,c}) \bigoplus (03 \times S_{1,c}) \bigoplus (01 \times S_{2,c}) \bigoplus (01 \times S_{3,c})$ - $S^,_{1,c}=(01 \times S_{0,c}) \bigoplus (02 \times S_{1,c}) \bigoplus (03 \times S_{2,c}) \bigoplus (01 \times S_{3,c})$ - $S^,_{0,c}=(01 \times S_{0,c}) \bigoplus (01 \times S_{1,c}) \bigoplus (02 \times S_{2,c}) \bigoplus (03 \times S_{3,c})$ - $S^,_{0,c}=(03 \times S_{0,c}) \bigoplus (01 \times S_{1,c}) \bigoplus (01 \times S_{2,c}) \bigoplus (02 \times S_{3,c})$ **NOTE:** - Phép $\times$ ở đây là phép nhân trong trường $GF(2^8)$, $\bigoplus$ là phép Xor - Khi nhân với $01$ trong trường $GF(2^8)$ đơn giản là giữ nguyên số đó $01 \times S_{0,c} = S_{0,c}$ - Khi nhân với $02$ trong trường $GF(2^8)$ thì ta dịch số đó sang trái $1$ bit, nếu vượt quá $8$ bit cần phải **xor** với $0x1B$. - Khi nhân với $03$ ta có: $S_{0,c} \times 03 =(S_{0,c}\times 02) \bigoplus S_{0,c}$ - Cụ thể ta sẽ **MixColumns** ma trận sau: \begin{bmatrix} d4&e0&b8&1e\\ bf&b4&41&27\\ 5d&52&11&98\\ 30&ae&f1&e5 \end{bmatrix} - Ta nhân lần lượt từng **cột** của khối trạng thái với $a(X)$: - Cột $1$: $$ \begin{bmatrix} 02&03&01&01\\ 01&02&03&01\\ 01&01&02&03\\ 03&01&01&02 \end{bmatrix} \times \begin{bmatrix} d4\\ bf\\ 5d\\ 30 \end{bmatrix} = \begin{bmatrix} 04\\ 66\\ 81\\ e5 \end{bmatrix} $$ - Tương tự với cột 2,3,4. Sau khi `Mixcolumns` xong ta được khối trạng thái mới: \begin{bmatrix} 04&e0&48&28\\ 66&cb&f8&06\\ 81&19&d3&26\\ e5&9a&7a&4c \end{bmatrix} $\Rightarrow$ Mục đích của việc chuyển đổi này là tạo ra sự phổ biến và nhầm lẫn trong quá trình mã hóa. Khuếch tán đảm bảo rằng một sự thay đổi trong một bit của bản rõ sẽ ảnh hưởng đến nhiều bit trong bản mã. **Chống tấn công vi phân** ### 4. AddRoundKey - AddroundKey là bước Xor khối trạng thái với khối Key (khối key này là khóa chủ ban đầu và khóa con được tạo ra ở bước expansion) ![image](https://hackmd.io/_uploads/ryu6831Pyx.png) - Bây giờ ta thử **AddRoundKey** khối trạng thái với một **khối key**: $$ \begin{bmatrix} 04&e0&48&28\\ 66&cb&f8&06\\ 81&19&d3&26\\ e5&9a&7a&4c \end{bmatrix} \bigoplus \begin{bmatrix} a0&88&23&2a\\ fa&54&a3&6c\\ fe&2c&39&76\\ 17&b1&39&05 \end{bmatrix} = \begin{bmatrix} a4&68&6b&02\\ 9c&9f&5b&6a\\ 7f&ea&35&50\\ f2&2b&43&49 \end{bmatrix} $$ ### 5. KeyExpansion - Bước KeyExpansion tạo các khóa con (round keys) từ khóa gốc ban đầu, những khóa con này được dùng để **XOR** với khối trạng thái trong bước `AddRoundKey` ở mỗi vòng trong quá trình mã hóa và cả giải mã. - Đối với mã hóa AES-128 có $10$ vòng (Round) $\Rightarrow$ có $10$ bước `AddRoundKey` $\Rightarrow$ Chính vì vậy ở bước `KeyExpansion` sẽ tạo thêm $10$ khóa con từ master key. Đối với mã hóa khác như AES-192 và AES-256 cũng dựa vào số vòng để tạo ra các khóa con. **SƠ ĐỒ QUÁ TRÌNH SINH KHÓA:** ![image](https://hackmd.io/_uploads/rJkkCelwkg.png) - Nhìn vào sơ đồ ta thấy bước `KeyExpansion` gồm $4$ bước: - Rotword: chuyển byte đầu tiên xuống cuối cùng và các byte còn lại được đẩy lên một vị trí - SubBytes: Như ta đã tìm hiểu ở trên `subBytes` biến đổi $4$ bytes đầu vào thành $4$ bytes đầu ra bằng cách sử dụng S-box lên từng bytes - Rcon: Mảng chứa hằng số sử dụng trong các vònglặp. - RCON[i] chứa các giá trị nhận được bởi: {${({02}^{i-1}),00,00,00}$} - Trong đó `i` chạy từ $1 \rightarrow 10$ (đối với AES-128) - Ta có bảng RCON sau: ![image](https://hackmd.io/_uploads/HJKblZEPJe.png) - Kết quả là ta sẽ được `Output` là $1$ khóa con để đưa vào vòng lặp $\Rightarrow$ Tùy thuộc vào số khóa con phải tạo ta sẽ lặp lại các bước trên. Ở đây ta cần tạo $10$ khóa con nên sẽ lặp lại các bước trên $10$ lần. - Chi tiết quá trình mở rộng khóa: ![image](https://hackmd.io/_uploads/rkn7uWlPyx.png) - Để tạo khóa con, đầu tiên ta cần tạo cột đầu tiên của khối key con thứ nhất bằng cách lấy cột thứ $4$ của khối key gốc thực hiện Rotword, SubBytes cột thứ $4$ đó sau đó $\bigoplus$ với cột đầu tiên của bảng RCON, sau đó $\bigoplus$ tiếp tục với cột đầu của khối key gốc. - Sau khi ta có cột đầu tiên của khối key con rồi thì tiếp tục tạo cột thứ 2 của khối key con bằng cách: $\bigoplus$cột đầu tiên của khối key con với cột thứ $2$ của khối key gốc. Tương tự để tạo cột thứ $3$, $4$ của khối key con, lần lượt thực hiện: $\bigoplus$ cột thứ 2 của khối key con với cột thứ 3 của khối key gốc, $\bigoplus$ cột thứ 3 của khối key con với cột thứ 4 của khối key gốc. $\Rightarrow$ Như vậy là ta đã tạo xong môt khối key con. - $9$ khối key con còn lại cũng thực hiện tương tự như vậy. Tuy nhiên cách tính tuy giống nhưng mà giá trị tính sẽ được lấy khác. Ví dụ để tạo khối key con thứ 2 cách tính cũng giống khối key con thứ nhất. Chỉ khác là cột đầu tiên của khối key con thứ 2 thì ta $\bigoplus$ cột thứ $2$ của bảng RCON (nếu khối key con thứ 3,4...,10 thì ta lấy lần lượt cột thứ 3,4...,10 của bảng RCON) với cột thứ tư của khối key con thứ nhất sau khi đã Rotword, SubBytes cột này (nếu khối key con thứ 3,4,...,10 thì lấy cột thứ 4 của khối key con 2,3,....9). Các cột thứ $2,3,4$ của khối key con thứ $2$ được tạo bằng cách lần lượt $\bigoplus$ cột đầu tiên của khối key con thứ 2 với cột thứ 2 của khối key con thứ nhất, $\bigoplus$ cột thứ 2 của khối key con thứ 2 với cột thứ 3 của khối key con thứ nhất, $\bigoplus$ cột thứ 3 của khối key con thứ 2 với cột thứ 4 của khối key con thứ nhất (nghĩa là ta sẽ $\bigoplus$ cột phía trước cột của khối key con cần tính với cột có vị trí tương ứng với nó của khối key con được tạo trước gần nó nhất đối với khối key con thứ 2 trở đi) - Ta thực hiện sinh khóa từ key gốc **2b7e151628aed2a6abf7158809cf4f3c**. Ta cần biểu diễn dãy giá trị dưới dạng khối. \begin{bmatrix} 2b&28&ab&09\\ 7e&ae&f7&cf\\ 15&d2&15&4f\\ 16&a6&88&3c \end{bmatrix} - Ta có : - $W_0$, $W_1$, $W_2$, $W_3$ lần lượt là các cột của khối key gốc trên. - $W_i$: là cột của **khối** **Key** **con**, ta có: $W_4,W_5,W_6,W_7$ là số cột của khối Key con thứ nhất. Tương tự ta có tổng cổng số cột của $10$ khối key con là $W_4 \rightarrow W_{43}$ - Đầu tiên ta cần tính cột đầu tiên của khối key con ban đầu là $W_4=t_4 \bigoplus W_0$ - $t_4$ bằng cột cuối cùng của khối key gốc $W_{i-1}=W_3$ sau khi đã thực hiện Rotword, SubBytes rồi **XOR** với cột đầu tiên của **R-CON** - $W_0$ là cột đầu tiên của khối key gốc. Cụ thể: - Đây là $t_4$ sau khi thực hiện các bước `Rotword`, `SubBytes` rồi `xor` với cột đầu tiên của bảng $R-CON$ $$ t_4 = \begin{bmatrix} 8b\\ 84\\ eb\\ 01 \end{bmatrix} $$ $$ \Rightarrow W_4 = t_4 \bigoplus W_0 = \begin{bmatrix} 8b\\ 84\\ eb\\ 01 \end{bmatrix} \bigoplus \begin{bmatrix} 2b\\ 7e\\ 15\\ 16 \end{bmatrix} = \begin{bmatrix} a0\\ fa\\ fe\\ 17 \end{bmatrix} $$ - Sau khi đã tính được cột đầu tiên của khối key con thứ nhất là $W_4$ thì ta tiến hành tính các cột còn lại của khối key con thứ nhất là $W_5$, $W_6$, $W_7$: - $W_5= W_4 \bigoplus W_1$ - $W_6=W_5 \bigoplus W_2$ - $W_7=W_6 \bigoplus W_3$ $\Rightarrow$ Vậy là ta đã tạo thành công khối key con thứ nhất \begin{bmatrix} a0&88&23&2a\\ fa&54&a3&6c\\ fe&2c&39&76\\ 17&b1&39&05 \end{bmatrix} - Tiếp theo để tạo khối key con thứ 2, ta cũng cần tính cột đầu tiên của khối key con thứ 2. $W_8=t_8 \bigoplus W_4$ - $t_8$ bằng cột cuối cùng của khối key con thứ 2 là $W_{i-1}=W_7$ sau khi thực hiện Rotword, SubBytes rồi **XOR** với cột thứ 2 của bảng R-CON - $W_4$ là cột đầu tiên của khối key con thứ nhất - Các cột còn lại của khối key con thứ 2 là $W_9$, $W_{10}$, $W_{11}$ là - $W_9= W_8 \bigoplus W_5$ - $W_{10}=W_5 \bigoplus W_6$ - $W_{11}=W_6 \bigoplus W_7$ - Ta thực hiện tương tự như vậy để tạo các khối key con còn lại. ## II. DES - **Đặc điểm**: - DES là thuật toán mã hóa khối, độ dài mỗi khối là 64 bit - Khóa dùng trong DES có độ dài toàn bộ là 64 bit. Tuy nhiên chỉ có 56 bit thực sự được sử dụng; 8 bit còn lại chỉ dùng cho việc kiểm tra. - DES xuất ra bản mã 64 bit. - Thuật toán thực hiện 16 vòng - Nếu input không chia hết cho $8$ bytes ($64$ bit) thì ta cần phải **padding** - **Điểm khác so với AES**: - DES được biểu diễn dưới dạng khối có kích thước **8x8 (bit)** khác với AES là một ma trận **4x4 (bytes)** - Ngoài ra, khác với AES làm việc với bytes, dùng toán học trong trường $GF(2^8)$. DES làm việc trực tiếp với các bit. ### Sơ đồ khái quát thuật toán DES ![image](https://hackmd.io/_uploads/BkiudX6Yge.png) - Đầu tiên từ khóa $K$ gốc **ban đầu** **dài** $64$ bit ta thực hiện sinh khóa , tổng cộng có $16$ khóa $K_i$ được tạo ra vì trong mã hóa **DES** có $16$ vòng lặp. Mục đích tạo các khóa $K_i$ này là dùng trong các vòng lặp $1,2,...16$ của quá trình mã hóa **input**. Các khóa $K_i$ này dài $48$ bit :::info :bulb: Khóa mật mã $K$ thật ra là một từ $56$ bit, ta chia thành $8$ đoạn, mỗi đoạn $7$ bit, ta thêm cho mỗi đoạn $7$ bit đó một bit thử tính chẵn lẻ vào vị trí cuối để được một từ $64$ bit, ta vẫn ký hiệu là $K$ ::: - Sau khi thực hiện sinh khóa xong ta tiến hành thực hiện mã hóa. Ta thực hiện **hoán vị IP** cho bản rõ. - Sau khi thực hiện **hoán vị IP** cho dữ liệu cần mã hóa, ta tiến hành thực hiện $16$ vòng lặp. Ở mỗi vòng lặp $i$ ta cần khóa $K_i$ tương ứng. Cụ thể ở bước **vòng** này gồm các bước nhỏ nào thì chúng ta sẽ tìm hiểu sau. - Khi thực hiện $16$ vòng lặp xong lúc này ta cần thực hiện thêm bước **hoán vị $32$-bit trái và phải**. :::info :bulb: Việc ta phải thêm bước **hoán vị 32-bit trái và phải** là vì đầu vào của hàm $IP^{-1}$ (hoán vị ngược) yêu cầu dữ liệu phải theo định dạng `R16 || L16` nhưng đầu ra khi thực hiện $16$ vòng lặp là `L16 || R16` nên ta cần phải đổi lại ::: - Và bước cuối cùng là chúng ta thực hiện hoán vị $IP^{-1}$ được bản mã dài $64$-bit. - Để giải mã ta chỉ cần làm ngược lại quá trình mã hóa, thực hiện các bước như trên, nhưng theo thứ tự ngược mà các khóa con(subkey) được thực hiện, nghĩa là thực hiện theo thứ tự $K_{16},..,K_1$. ### 1. Tính các khóa con Ki từ khóa K ![image](https://hackmd.io/_uploads/B1LqhFIC1e.png) **$\star$ BƯỚC 1: Tính hoán vị $PC1(K)$** - Ví dụ ta có khóa $K=133457799BBCDFF1$ - Ta sẽ chuyển nó sang nhị phân: $K= 00010011\\\ 00110100\ 01010111\ 01111001\ 10011011\ 10111100\ 11011111\ 11110001$ - Ta biểu diễn chuỗi bit $k$ dưới dạng bảng **8x8 (bit)** và thực hiện hoán vị $PC1$ với $1,2,3....64$ là lần lượt là thứ tự của các bit trong chuỗi $K$ ![image](https://hackmd.io/_uploads/HJ6vU--Ayx.png) $$ k = \begin{array}{|c|c|c|c|c|c|c|c|} \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ \hline 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ \hline 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ \hline 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ \hline 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \hline \end{array} \Rightarrow PC1 = \begin{array}{|c|c|c|c|c|c|c|c|} \hline 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ \hline 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ \hline 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ \hline 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 \\ \hline 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \hline \end{array} $$ - Ở bước hoán vị $PC1$ này đầu ra là $56$ bit, như đã nói ban đầu chỉ có $56$ bit của khóa $K$ là được sử dụng để sinh khóa. Tám bit còn lại (8, 16, 24, 32, 40, 48, 56, 64) được chỉ định để sử dụng để kiểm tra bit chẵn lẻ bit chẵn lẻ. $$PC1K = 11110000\ 11001100\ 10101010\ 1111 0101\ 01010110\ 01100111\ 10001111 = F0\ CC\ AA\ F5\ 56\ 67\ 8F$$ - Mỗi 1 cặp của mã hex ví dụ $F0, CC,....$ là $1$ bytes $\Rightarrow PC1K$ dài $56$ bit **$\star$** **BƯỚC 2: Tính các giá trị dịch vòng của $C_i, D_i$**: $PC1K =$ ==11110000 11001100 10101010 1111 0101== 01010110 01100111 10001111 $=$ ==F0 CC AA F==5 56 67 8F - Ta chia $PC1K$ dài $56$ bit thành $2$ phần, mỗi phần dài $28$ bit: - $C_0=F0\ CC\ AA\ F$ - $D_0= 5\ 56\ 67\ 8F$ - Sau đó ta tính các giá trị dịch vòng $C_i, D_i$: - $C_i=$ RotLeftShirt$(C_{i-1},S_i)$ - $D_i=$ RotLeftShirt$(D_{i-1},S_i)$ Như ở trên đã nói bước này ta sẽ dịch vòng trái $C_{i-1}$, $D_{i-1}$ với số bit theo $S_i$ ![image](https://hackmd.io/_uploads/BydZy7ZAJe.png) - Đây là kết quả sao khi ta dịch vòng trái $C_1, D_1$ đến $C_{16}, D_{16}$ lần: \begin{array}{|c|c|l|l|} \hline \textbf{i} & \textbf{S_i} & \textbf{C_i} & \textbf{D_i} \\ \hline 0 & & 1111\,0000\,1100\,100\,1010\,1010\,1111 & 0101\,0101\,0110\,0110\,0111\,1000\,1111 \\ 1 & 1 & 1110\,0001\,1001\,1001\,0101\,0101\,1111 & 1010\,1010\,1100\,1100\,1111\,0001\,1110 \\ 2 & 1 & 1100\,0011\,0011\,0010\,1010\,1011\,1111 & 0101\,0101\,1001\,1001\,1110\,0011\,1101 \\ 3 & 2 & 0000\,1100\,1100\,1010\,1010\,1111\,1111 & 0101\,0110\,0110\,0111\,1000\,1111\,0101 \\ 4 & 2 & 0011\,0011\,0010\,1010\,1011\,1111\,1100 & 0101\,1001\,1001\,1110\,0011\,1101\,0101 \\ 5 & 2 & 1100\,1100\,1010\,1010\,1111\,1111\,0000 & 0110\,0110\,0111\,1000\,1111\,0101\,0101 \\ 6 & 2 & 0011\,0010\,1010\,1011\,1111\,1100\,0011 & 1001\,1001\,1110\,0011\,1101\,0101\,0101 \\ 7 & 2 & 1100\,1010\,1010\,1111\,1111\,0000\,1100 & 0110\,0111\,1000\,1111\,0101\,0101\,0101 \\ 8 & 2 & 0010\,1010\,1011\,1111\,1100\,0011\,0011 & 1001\,1110\,0011\,1101\,0101\,0101\,1001 \\ 9 & 1 & 0101\,0101\,0111\,1111\,1000\,0110\,0110 & 0011\,1100\,0111\,1010\,1010\,1011\,0011 \\ 10 & 2 & 0101\,0101\,1111\,1110\,0001\,1001\,1001 & 1111\,0001\,1110\,1010\,1010\,1100\,1100 \\ 11 & 2 & 0101\,0111\,1111\,1000\,0110\,0110\,0101 & 1100\,0111\,1010\,1010\,1011\,0011\,0011 \\ 12 & 2 & 0101\,1111\,1110\,0001\,1001\,1001\,0101 & 0001\,1110\,1010\,1010\,1100\,1100\,1111 \\ 13 & 2 & 0111\,1111\,1000\,0110\,0110\,0101\,0101 & 0111\,1010\,1010\,1011\,0011\,0011\,1100 \\ 14 & 2 & 1111\,1110\,0001\,1001\,1001\,0101\,0101 & 1110\,1010\,1010\,1100\,1100\,1111\,0001 \\ 15 & 2 & 1111\,1000\,0110\,0110\,0101\,0101\,0111 & 1010\,1010\,1011\,0011\,0011\,1100\,0111 \\ 16 & 1 & 1111\,0000\,1100\,1100\,1010\,1010\,1111 & 0101\,0101\,0110\,0110\,0111\,1000\,1111 \\ \hline \end{array} $\star$ **BƯỚC 3: Tính hoán vị $PC2$ và gán giá trị vào $K_i$**: - Sau khi dịch vòng trái $C_i$ và $D_i$ ta ghép $C_i$ và $D_i$ lại sao đó tính hoán vị $PC2$ của chúng, sau đó gán giá trị đó cho $K_i$ (tổng cộng ta thu được $16$ $K$ sau bước sinh khóa này). - Bước $PC2$ loại bỏ $8$ bit nên ta thu được khóa $K_i$ dài 48 bit $$K_i=PC2(C_iD_i)$$ - Bước hoán vị $PC2$ này ta dựa vào: ![image](https://hackmd.io/_uploads/Sy4cjXbRJl.png) $\Rightarrow$ Sau bước $PC2$ này ta thu được các khóa $K$ dài $48$ bit - Ví dụ ta tính $K_1$: $$K_1=PC2(C_1D_1)=00011011\ 00000010\ 11101111\ 11111100\ 01110000\ 01110010 =1B\ 02\ EF\ FC \ 70\ 72$$ - Tương tự ta thu được $16$ khóa $K$: \begin{array}{|c|c|} \hline i & \text{Ki} \\ \hline 1 & \text{1B02EFFC7072} \\ 2 & \text{79AE09DBC9E5} \\ 3 & \text{55FC8A42CF99} \\ 4 & \text{72ADD6DB351D} \\ 5 & \text{7CEC07EB53A8} \\ 6 & \text{63AS3E507B2F} \\ 7 & \text{EC84B7F618BC} \\ 8 & \text{F78A3AC13BFB} \\ 9 & \text{E00BE6EDE781} \\ 10 & \text{B1F347BA464F} \\ 11 & \text{215FD3DE0386} \\ 12 & \text{7571F59467E9} \\ 13 & \text{97C5D1FA8AA1} \\ 14 & \text{5F43B7F2E73A} \\ 15 & \text{BF918D3D3FOA} \\ 16 & \text{CB3D8BOE17F5} \\ \hline \end{array} ### 2. Hoán vị IP - $IP$ là một phép hoán vị vị trí của các ký tự trong mỗi từ $64$ bit, từ vị trí thứ 1 đến vị trí thứ $64$. - Bảng dưới đây cho phép ta hoán vị $IP$, với cách hiểu là bit thứ nhất của $IP(x)$ là bit thứ $58$ của $x$ (có $64$ bit), bit thứ hai của $IP(x)$ là bit thứ $50$ của $x$,...(cách hoán vị cũng khá giống với $PC1$ và $PC2$) ![Screenshot 2025-04-11 134218](https://hackmd.io/_uploads/ByB55NICye.png) - Ví dụ ta mã hóa $M = 0123456789ABCDEF$ - Ta chuyển $M$ sang nhị phân: $M=00000001\ 00100011\ 01000101\ 01100111\ 10001001\ 10101011\ 11001101\ 11101111$ - Sau đó ta thực hiện **hoán vị IP** cho $M$ dựa vào bảng trên. $$ M = \begin{array}{|c|c|c|c|c|c|c|c|} \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \hline 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ \hline 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ \hline 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ \hline 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ \hline 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ \hline 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ \hline \end{array} \Rightarrow IP(M) = \begin{array}{|c|c|c|c|c|c|c|c|} \hline 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ \hline 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ \hline 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ \hline \end{array} $$ - Kết quả hoán vị **IP** là: $$IP(M)= 11001100\ 11000000\ 00000000\ 11001100\ 11111111\ 11110000\ 10101010\ 11110000\ 10101010$$ $$=\ CC00CCFFF0AAF0AA$$ ### 3. Round (Vòng) - Đây là sơ đồ mã hóa trong một vòng: ![image](https://hackmd.io/_uploads/S1RZwHLCye.png) - Sau khi thực hiện **hoán vị IP** cho $M$, ta chia **IP(M)** làm hai nữa: nửa trái $L_0$ ($32$-bit) và nửa phải $R_0$ ($32$-bit) - $R_0$ sẽ là **nửa trái** cho vòng tiếp theo. - $L_0$ dùng để **xor** với $R_0$ sau khi thực hiện hàm $f$ và trở thành **nửa phải** cho vòng lặp tiếp theo, rồi ta cứ lặp lại các bước trên - Tổng cộng chúng ta thực hiện $16$ vòng lặp **Ví dụ:** Lúc nãy ta đã tính được **IP(M)= CC00CCFFF0AAF0AA** - Ta sẽ chia **IP(M)** thành: - $L_0 = CC00CCFF$ - $R_0 = F0AAF0AA$ - Đây là $16$ vòng lặp: ![image](https://hackmd.io/_uploads/rkG1GLLA1x.png) **$\star$ SƠ ĐỒ HÀM $f$:** ![image](https://hackmd.io/_uploads/HkWL3BURkg.png) - Hàm $f$ lấy đầu vào là hai từ: $R$ có $32$ bit và $K$ có $48$ bit, và kết quả ở đầu ra là từ $f(R,K)$ có $32$ bit - Đầu tiên $R$ sẽ được đưa qua $E$ ( mở rộng nửa phải $R$) để mở rộng từ $32$ bit thành $48$ bit để có thể **xor** với khóa $K$ ở bước sau. - $E$ là một phép hoán vị "**mở rộng**" theo nghĩa là nó biến mỗi từ $R$ $32$ bit thành $E(R)$ ($48$-bit) bằng cách hoán vị $32$ bit của $R$ nhưng một số cặp bit được lặp lại để $E(R)$ thành một từ có $48$ bit ![image](https://hackmd.io/_uploads/r1d00SLC1e.png) - Trong đó phần tô màu vàng là thứ tự bit của $R$ - Còn cột ngoài cùng bên trái của bảng là kết quả của dịch vòng của cột ngoài cùng bên phải của phần tô màu - Cột ngoài cùng bên phải bảng là dịch vòng của cột ngoài cùng bên trái phần tô màu. - Lúc nãy ta có $R_0 = F0AAF0AA=1111\ 0000\ 1010\ 1111\ 0000\ 1010\ 1010$ - Sau khi thực hiện mở rộng nửa phải ta thu được $E(R_0)= 011110\ 100001\ 010101\ 010101\ 011110\ 100001\ 010101\ 010101$ - Tiếp theo ta thực hiện **xor** $E(R)$ với khóa $K$, được một từ $48$ bit. $$ \begin{array}{|c|c|} \hline K_i & 000110\ 110000\ 001011\ 101111\ 111111\ 000111\ 000001\ 110010 \\ \hline E(R_0) & 011110\ 100001\ 010101\ 010101\ 011110\ 100001\ 010101\ 010101 \\ \hline K_i + E(R_0) & 011000\ 010001\ 011110\ 111010\ 100001\ 100110\ 010100\ 100111 \\ \hline \end{array} $$ - Ta chia $K_i+E(R_0)=011000\ 010001\ 011110\ 111010\ 100001\ 100110\ 010100\ 100111$ thành $8$ đoạn $B_1,...,B_8$ mỗi $B_j$ dài $6$ bit - Ta sẽ cho các khối $B_j$ ($6$ bit) qua các hộp **S-box** $S_j$ tương ứng thu được $C_j$ :::info :bulb: Mỗi từ $B_j=b_1b_2b_3b_4b_5b_6$ tương ứng với một vị trí $(r,s)$ ở hàng thứ $r$ và cột thứ $s$ trong bảng, các hàng được đánh số từ $0$ đến $3$ ứng với biểu diễn nhị phân $b_1b_6$ và các cột được đánh số từ thứ $0$ đến thứ $15$ ứng với biểu diễn nhị phân $b_1b_3b_4b_5$ ::: - Giá trị $C_j = c_1c_2c_3c_4$ là một từ $4$ bit, biểu diễn nhị phân của số tại hàng $r$ cột $s$ trong bảng **S-box** - Ta có tổng cộng $8$ bảng **S-box**: \begin{array}{|>{\centering\arraybackslash}c|} \hline {S_1} \\ \hline 14 & 4 & 13 & 1 & 2 & 15 & 11 & 8 & 3 & 10 & 6 & 12 & 5 & 9 & 0 & 7 \\ \hline 0 & 15 & 7 & 4 & 14 & 2 & 13 & 1 & 10 & 6 & 12 & 11 & 9 & 5 & 3 & 8 \\ \hline 4 & 1 & 14 & 8 & 13 & 6 & 2 & 11 & 15 & 12 & 9 & 7 & 3 & 10 & 5 & 0 \\ \hline 15 & 12 & 8 & 2 & 4 & 9 & 1 & 7 & 5 & 11 & 3 & 14 & 10 & 0 & 6 & 13 \\ \hline \end{array} \begin{array}{|>{\centering\arraybackslash}c|} \hline {S_2} \\ \hline 15 & 1 & 8 & 14 & 6 & 11 & 3 & 4 & 9 & 7 & 2 & 13 & 12 & 0 & 5 & 10 \\ \hline 3 & 13 & 4 & 7 & 15 & 2 & 8 & 14 & 12 & 0 & 1 & 10 & 6 & 9 & 11 & 5 \\ \hline 0 & 14 & 7 & 11 & 10 & 4 & 13 & 1 & 5 & 8 & 12 & 6 & 9 & 3 & 2 & 15 \\ \hline 13 & 8 & 10 & 1 & 3 & 15 & 4 & 2 & 11 & 6 & 7 & 12 & 0 & 5 & 14 & 9 \\ \hline \end{array} \begin{array}{|>{\centering\arraybackslash}c|} \hline {S_3} \\ \hline 10 & 0 & 9 & 14 & 6 & 3 & 15 & 5 & 1 & 13 & 12 & 7 & 11 & 4 & 2 & 8 \\ \hline 13 & 7 & 0 & 9 & 3 & 4 & 6 & 10 & 2 & 8 & 5 & 14 & 12 & 11 & 15 & 1 \\ \hline 13 & 6 & 4 & 9 & 8 & 15 & 3 & 0 & 11 & 1 & 2 & 12 & 5 & 10 & 14 & 7 \\ \hline 1 & 10 & 13 & 0 & 6 & 9 & 8 & 7 & 4 & 15 & 14 & 3 & 11 & 5 & 2 & 12 \\ \hline \end{array} \begin{array}{|>{\centering\arraybackslash}c|} \hline {S_4} \\ \hline 7 & 13 & 14 & 3 & 0 & 6 & 9 & 10 & 1 & 2 & 8 & 5 & 11 & 12 & 4 & 15 \\ \hline 13 & 8 & 11 & 5 & 6 & 15 & 0 & 3 & 4 & 7 & 2 & 12 & 1 & 10 & 14 & 9 \\ \hline 10 & 6 & 9 & 0 & 12 & 11 & 7 & 13 & 15 & 1 & 3 & 14 & 5 & 2 & 8 & 4 \\ \hline 3 & 15 & 0 & 6 & 10 & 1 & 13 & 8 & 9 & 4 & 5 & 11 & 12 & 7 & 2 & 14 \\ \hline \end{array} $$ \begin{array}{|>{\centering\arraybackslash}c|} \hline {S_5} \\ \hline 2 & 12 & 4 & 1 & 7 & 10 & 11 & 6 & 8 & 5 & 3 & 15 & 13 & 0 & 14 & 9 \\ \hline 14 & 11 & 2 & 12 & 4 & 7 & 13 & 1 & 5 & 0 & 15 & 10 & 3 & 9 & 8 & 6 \\ \hline 4 & 2 & 1 & 11 & 10 & 13 & 7 & 8 & 15 & 9 & 12 & 5 & 6 & 3 & 0 & 14 \\ \hline 11 & 8 & 12 & 7 & 1 & 14 & 2 & 13 & 6 & 15 & 0 & 9 & 10 & 4 & 5 & 3 \\ \hline \end{array} $$ $$ \begin{array}{|>{\centering\arraybackslash}c|} \hline {S_6} \\ \hline 12 & 1 & 10 & 15 & 9 & 2 & 6 & 8 & 0 & 13 & 3 & 4 & 14 & 7 & 5 & 11 \\ \hline 10 & 15 & 4 & 2 & 7 & 12 & 9 & 5 & 6 & 1 & 13 & 14 & 0 & 11 & 3 & 8 \\ \hline 9 & 14 & 15 & 5 & 2 & 8 & 12 & 3 & 7 & 0 & 4 & 10 & 1 & 13 & 11 & 6 \\ \hline 4 & 3 & 2 & 12 & 9 & 5 & 15 & 10 & 11 & 14 & 1 & 7 & 6 & 0 & 8 & 13 \\ \hline \end{array} $$ $$ \begin{array}{|>{\centering\arraybackslash}c|} \hline {S_7} \\ \hline 4 & 11 & 2 & 14 & 15 & 0 & 8 & 13 & 3 & 12 & 9 & 7 & 5 & 10 & 6 & 1 \\ \hline 13 & 0 & 11 & 7 & 4 & 9 & 1 & 10 & 14 & 3 & 5 & 12 & 2 & 15 & 8 & 6 \\ \hline 1 & 4 & 11 & 13 & 12 & 3 & 7 & 14 & 10 & 15 & 6 & 8 & 0 & 5 & 9 & 2 \\ \hline 6 & 11 & 13 & 8 & 1 & 4 & 10 & 7 & 9 & 5 & 0 & 15 & 14 & 2 & 3 & 12 \\ \hline \end{array} $$ $$ \begin{array}{|>{\centering\arraybackslash}c|} \hline {S_8} \\ \hline 13 & 2 & 8 & 4 & 6 & 15 & 11 & 1 & 10 & 9 & 3 & 14 & 5 & 0 & 12 & 7 \\ \hline 1 & 15 & 13 & 8 & 10 & 3 & 7 & 4 & 12 & 5 & 6 & 11 & 0 & 14 & 9 & 2 \\ \hline 7 & 11 & 4 & 1 & 9 & 12 & 14 & 2 & 0 & 6 & 10 & 13 & 15 & 3 & 5 & 8 \\ \hline 2 & 1 & 14 & 7 & 4 & 10 & 8 & 13 & 15 & 12 & 9 & 0 & 3 & 5 & 6 & 11 \\ \hline \end{array} $$ - Các hộp **S-box** là thành phần quan trọng nhất trong việc bảo đảm tính bí mật của **DES** **VD:** $$ \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline B = K_1 + E(R_0) & \color{red}{011000} & 010001 & \color{red}{011110} & 111010 & \color{red}{100001} & 100110 & \color{red}{010100} & 100111 \\ \hline S(B) & 0101 & 1100 & 1000 & 0010 & 1011 & 0101 & 1001 & 0111 \\ \hline \end{array} $$ - Ta có $B_1= 011000$ có bit $b_1$ và bit $b_6$ lần lượt là $00$ $\Rightarrow$ Ta chọn hàng thứ $0$, bit $b_2b_3b_4b_5$ lần lượt là $1100$ $\Rightarrow$ Ta chọn cột thứ $12$ ![image](https://hackmd.io/_uploads/BkZBI_LRyx.png) - Vậy $S(B_1)=C_1= 5_{10}= 0101_2$, tương tự như thế ta có: $$S(B)= 5C\ 82\ B5\ 97$$ - Bước tiếp theo ta thực hiện **hoán vị P** của $S(B)$ ($32$-bit) dựa vào bảng sau: ![image](https://hackmd.io/_uploads/ryoaYuICke.png) - Sau khi thực hiện **hoán vị P** của $S(B)= 5C\ 82\ B5\ 97= 0101\ 1100\ 1000\ 0010\ 1011\ 1001\ 0111$. - Ta thu được $P(S)=0010\ 0011\ 0100\ 1010\ 1001\ 1011\ 1011=23\ 4A\ A9\ BB$ - Vậy là ta đã thực hiện xong hàm $f$ và thu được $f(R_0,K_1)=23\ 4A\ A9\ BB$ gồm ($32$-bit) - Sau đó, ta **xor** $f(R_0,K_1)$ với $L_0$ ta được $R_1$ rồi dùng nó làm **nửa phải** cho vòng hai, còn $R_0$ ban đầu trở thành $L_1$ được lấy làm **nửa trái** cho vòng hai. - Tương tự như vậy, kết quả sau $16$ vòng lặp là: - $L_{16}= 43423234(=0100\ 0011\ 0100\ 0010\ 0011\ 0010\ 0011\ 0100)$ - $R_{16}= OA4CD995(=0000\ 1010\ 0100\ 1100\ 1101\ 1001\ 1001\ 0101)$ ### 4. Hoán vị $IP^{-1}$ - Sau khi thực hiện $16$ vòng lặp xong, trước khi thực hiện hoán vị $IP^{-1}$, ta cần hoán vị $32$-bit trái và phải. Nghĩa là $L_{16}R_{16}$ thành $R_{16}L_{16}$. - Ta dựa vào bảng sau để thực hiện hoán vị $IP^{-1}$: ![image](https://hackmd.io/_uploads/rymdMoLAyx.png) - Kết quả cuối ta có: $$IP^{-1}= 10000101\ 11101000\ 00010011\ 01010100\ 00001111\ 00001010\ 10110100\ 00000101$$ $$= 85E813540F0AB405$$ - Vậy bãn mã của $M$ là $C=85E813540F0AB405$ ## III. 3DES - Trong suốt $30$ năm từ khi được công bố lần đầu tiên, $DES$ tỏ ra rất an toàn và được sử dụng rộng rãi không chỉ ở Hoa Kỳ mà còn trên nhiều quốc gia khác. - Tuy nhiên sau một thời gian dài được coi là một hệ mã an toàn thì những yếu điểm của $DES$ bắt đầu bộc lộ. Vì với độ dài khóa chỉ $56$ bits, số lượng của chìa có thể sinh ra không nhiều so với số lượng chip và tốc độ xử lý của các siêu máy tính ngày nay, nhất là các hệ thống song song chuyên dụng cho việc giiar mã. - Từ đó các biến thể của DES được đưa ra làm giải pháp "cứu cánh" như TDEA (3DES) $\star$ **Mã TDEA (Triple Data Encryption Algorithm)** - Cho $DES_k(I)$ và $DES_k^{-1}(I)$ tương ứng là hàm lập mã và hàm giải mã của $I$ theo thuật toán $DES$ với khóa $K$ tách biệt - Mỗi quá trình MÃ hóa/Giải mã **TDEA** là hợp của các phép mã hóa và giải mã $DES$ ![image](https://hackmd.io/_uploads/ByMkQrw0Je.png) - **Phép mã hóa TDEA**: chuyển bản rõ $I$ $64$ bits thành bản mã $O$ $64$ bits tương ứng được định nghĩa như sau: $$O=DES_{k3}(DES^{-1}_{k2}(DES_{k1}(I)))$$ - **Phép giải mã TDEA:** Chuyển bản mã $O$ $64$ bits, thành bản rõ $I$ $64$ bits tương ứng được định nghĩa như sau: $$I=DES^{-1}_{k1}(DES_{k2}(DES^{-1}_{k3}(O)))$$ - Cách xác định bộ khóa $(K_1K_2K_3)$: - **Lựa chọn 1**: Khóa $K_1$, $K_2$ và $K_3$ là các khóa độc lập. - **Lựa chọn 2:** Khóa $K_1$, $K_2$ độc lập và $K_3=K_1$ - **Lựa chọn 3**: Khóa $K_1=K_2=K_3$ ## IV. PKCS#7 Padding - **PKCS#7 Padding** là kỹ thuật thường được dùng trong các thuật toán **mã hóa khối (block ciphers)** như AES, DES và các thuật toán mã hóa khác, kỹ thuật này được sử dụng để bổ sung dữ liệu sao cho độ dài của khối dữ liệu đạt được kích thước đúng yêu cầu. - Một số chế độ mật mã khối có độ dài cố định như: ECB, CBC,...yêu cầu văn bản thuần túy là bội số của kích thước khối. Nếu ta làm việc với mật mã khối $16$ bytes nhưng văn bản thuần túy chỉ có $7$ bytes thì lúc này ta cần thêm $9$ bytes vào dữ liệu của mình. **$\star$ Cách **PKCS#7 Padding** hoạt động**: - Đầu tiên ta cần tính số bytes cần **Padding** bằng công thức: ``` padding = block_size - (plaintext_length % block_size) ``` - Trong đó: - **block_size:** kích thước khối - **plaintext_length**: kích thước văn bản thuần túy - Như ở ví dụ trên, khi ta làm việc với khối mật mã dài $16$ bytes nhưng văn bản thuần túy của ta chỉ dài $7$ bytes, nên ta thêm $9$ bytes vào văn bản thuần túy mà không phải là $25$ hay $41$ bytes mặt dù khi thêm vào thì kích thước văn bản thuần túy vẫn là bội số của kích thước khối. Việc này nhằm giúp tiếc kiệm dung lượng, mã hóa/giải mã nhanh hơn. - Giá trị của byte padding bằng với số lượng byte cần padding, điều này chỉ đúng khi kích thước khối nhỏ hơn $256$ bit. Vì một byte chỉ có thể có giá trị từ $0$ đến $255$. Vậy khi ta padding $9$ bytes thì bytes được padding có giá trị của `0x09` - Ta padding các bytes vào phần cuối của dữ liệu **VD:** - **Trước khi Padding:** ![image](https://hackmd.io/_uploads/SJQUedDRkx.png) - **Sau khi Padding:** ![image](https://hackmd.io/_uploads/B1kEMdP0Je.png) - **Lưu ý**: - Trường hợp văn bản thuần túy ban đầu đã là bội số của kích thước khối, ta cũng cần phải Padding cho văn bản thêm một khối mới. Ví dụ ta làm việc với khối mật mã $16$ bits và văn bản thuần túy dài $16$ bytes lúc này ta cần Padding thêm một khối cho dữ liệu nữa là $16$ bytes. Mỗi bytes có giá trị là `0x10` - Việc này dùng để phân biệt văn bản thuần túy ban đầu có kích thước vừa khích với kích thước khối, với văn bản thuần túy có kích thước vừa khích với kích thước khối do đã Padding. Không gây nghi ngờ, lẫn lộn cho người giải mã, dễ dàng và chắc chắn loại bỏ đúng số byte đã Padding. - Trước khi Padding: ![image](https://hackmd.io/_uploads/SyeAEjw0Jg.png) - Sau khi Padding: ![image](https://hackmd.io/_uploads/r1USNjw0yl.png) ## V. Block cipher modes of operation Mật mã khối sử dụng khóa đối xứng để mã hóa dữ liệu có độ dài cố định và rất ngắn (kích thước khối), chẳng hạn như 16 byte cho AES. Để đối phó với dữ liệu có độ dài tùy ý, mật mã phải kết hợp với một chế độ hoạt động Các chế độ hoạt động của mã khối xác định cách mã hóa và giải mã an toàn các khối dữ liệu lớn bằng mã khối. ### 1. Electronic Code Book (ECB) - **ECB** là chế độ hoạt động của mật mã khối. Đây là mã hóa khối dễ nhất. Khối dữ liệu rõ (plaintext) được chia thành các khối có kích thước cố định giống nhau, mỗi khối được mã hóa độc lập cùng với một khóa . $\Rightarrow$ Thu được một chuỗi ciphettext, khi ghép các bản ciphertext này lại ta sẽ thu được bản mã \. Khi muốn giải mã thì ta chỉ cần giải mã chuỗi ciphertext với cùng một khóa ban đầu. ![image](https://hackmd.io/_uploads/SyrSjfVvJg.png) - Chính vì ECB đơn giản nên nó được dùng để Ideal cho lượng dữ liệu ngắn. Do có tính độc lập nên có thể mã hóa bất kỳ khối nào một cách nhanh chóng (vì có thể mã hóa song song các khối bit). - Chính vì đơn giản nên ECB không được khuyến khích sử dụng trong mã hóa. Đặc biệt là không an toàn khi mã hóa các tin nhắn dài - Vì ciphertext thiếu đi tính phức tạp dẫn đến dữ liệu dễ bị lộ cấu trúc, dễ bị phân tích mật mã vì có mối quan hệ trực tiếp giữa văn bản thuần túy và văn bản mã hóa. Các khối văn bản thuần túy giống hệt nhau sẽ tạo ra các khối văn bản mã hóa giống hệt nhau, có thể tiết lộ các mẫu. - Ví dụ khi ta mã hóa hình ảnh bằng ECB thì các mẫu và cấu trúc trong hình ảnh gốc vẫn có thể nhận ra trong bản mã hóa. Cụ thể: ![image](https://hackmd.io/_uploads/SyRi00VPJx.png) $\rightarrow$ Ta thấy là hình ảnh được mã hóa bằng ECB vẫn giữ lại các đặc điểm, cấu trúc của ảnh gốc. Chính vì vậy ta vẫn có thể hình dung được ảnh ban đầu. - Còn đây là tấm ảnh chim cánh cụt khi được mã hóa bằng chế độ khác. Tấm ảnh sau khi mã hóa hoàn toàn khác với tấm ban đầu và ta không thể đoán được ảnh gốc của nó. ![image](https://hackmd.io/_uploads/Bkf8kkBwke.png) :::info Vậy làm thế nào để ta có thể mã hóa/giải mã dữ liệu trong python với chế độ ECB ::: - Để mã hóa dữ liệu (cũng như giải mã) ta cần khởi tạo đối tượng mật mã ([tham khảo](https://pycryptodome.readthedocs.io/en/latest/src/cipher/classic.html#ecb-mode)) ![image](https://hackmd.io/_uploads/H1ePwlHwkg.png) Hàm `new()`ở cấp mô-đun trong `crypto.Cipher` khởi tạo một đối tượng mật mã ECB mới cho thuật toán cơ sở có liên quan. Trong định nghĩa sau đây, `<algorthm>` có thể là `AES` - code: ```python= from Crypto.Cipher import AES from Crypto.Random import get_random_bytes key = get_random_bytes(16) cipher = AES.new(key, AES.MODE_ECB) # You can now use use cipher to encrypt or decrypt... ``` $\Rightarrow$ Đoạn code này khởi tạo **một đối tượng mã hóa AES với chế độ ECB**. Sau khi khởi tạo đối tượng, ta có thể dùng trong bước mã hóa hoặc giải mã - `from Crypto.Cipher import AES`: Nhập mô-đun AES từ thư viện PyCryptodome, giúp ta sử dụng thuật toán AES - `from Crypto.Random import get_random_bytes`: Nhập hàm get_random_bytes từ thư viện Crypto.Random để tạo ra các byte ngẫu nhiên. Chúng sẽ dùng hàm này để tạo khóa mật mã (key) ngẫu nhiên. $\Rightarrow$ Sau khi khai báo các hàm cần thiết xong, chúng ta dùng lệnh `key = get_random_bytes(16)` để tạo một key ngẫu nhiên có độ dài 16 bytes và lệnh `cipher = AES.new(key, AES.MODE_ECB)` tạo một đối tượng mã hóa AES mới với chế độ ECB và sử dụng khóa mật mã vừa tạo. - Sao khi khởi tạo đối tượng mật mã xong ta tiến hành mã hóa dữ liệu với chế độ ECB. giả sử ta mã hóa `data= 'test message'` - **Code**: - Ta sẽ khai báo thêm `pad` và `unpad`. `pad` sẽ thêm ký tự đảm bảo sao cho dữ liệu là bội của $16$ bytes trong trường hợp AES và `unpad` sẽ loại bỏ các ký tự dư từ hàm `pad` ```python= from Crypto.Cipher import AES from Crypto.Random import get_random_bytes from Crypto.Util.Padding import pad,unpad key = get_random_bytes(16) data = "test mesage " cipher = AES.new(key, AES.MODE_ECB) # Mã hóa en_data = cipher.encrypt(pad(data.encode(), 16)) print(en_data) # Giải mã de_data = unpad(cipher.decrypt(en_data, 16)) print(de_data) ``` ### 2. Cipher block chaining (CBC) - Chế độ hoạt động của mật mã tiếp theo đó là **Cipher block chaining** hay **CBC** là một chế độ tiến bộ hơn ECB - Nếu đối với ECB khi mã hóa(cũng như giải mã) thì khối văn bản gốc được chia thành các khối có kích thước cố định giống nhau sau đó thực hiện mã hóa **độc lập** các khối đó với cùng một key. Thì đối với chế độ mã hóa CBC khối văn bản gốc cũng được chia thành các khối có kích thước giống nhau, nhưng trong CBC mỗi khối văn bản gốc được XOR-ed với khối văn bản mã hóa trước đó trước khi mã hóa (giữa các khối dữ liệu có mối liên kết với nhau), trong đó khối văn bảng gốc đầu tiên $\bigoplus$ với **IV** trước khi mã hóa, qua trình giải mã thì làm ngược lại ![image](https://hackmd.io/_uploads/Bk3h6bHwJe.png) - Chính vì những khối sau được $\bigoplus$ với khối Ciphertext phía trước chứ không phải khối Plaintext phía trước, nên có một ưu điểm là khi ta giải mã CBC mà ta dùng IV sai thì chỉ có khối Plaintext đầu tiên bị sai chứ những khối sau vẫn đúng - Ưu điểm: - CBC hoạt động tốt với dữ liệu đầu vào lớn . - CBC là một cơ chế xác thực tốt. - Có tính kháng cự tốt hơn đối với việc phân tích mật mã so với ECB. - An toàn hơn ECB vì nó ẩn các mẫu hình. - Nhược điểm: - Yêu cầu khối văn bản mã hóa trước đó để [mã hóa và giải mã](https://www.geeksforgeeks.org/difference-between-encryption-and-decryption/) , khiến việc xử lý song song trở nên khó khăn. :::info Vậy để mã hóa/giải mã dữ liệu theo chế độ mã hóa CBC ta code thế nào? ::: - Đầu tiên ta cũng cần khởi tạo đối tượng mật mã CBC ![image](https://hackmd.io/_uploads/rJhXNGSPye.png) $\Rightarrow$ Hàm `new()` ở cấp **mô-đun** trong `crypto.Cipher` khởi tạo một đối tượng mật mã **CBC** mới cho thuật toán cơ sở có liên quan. Trong định nghĩa sau đây, `<algorthm>` có thể là **AES** $\Rightarrow$ **iv (byte)** – vectơ khởi tạo. Một mẩu dữ liệu không thể đoán trước đối với đối thủ. Nó dài bằng kích thước khối (ví dụ: 16 byte cho AES). Nếu không có, thư viện sẽ tạo ra một giá trị IV ngẫu nhiên. - Các bước mã hóa/giải mã dữ liệu theo chế độ CBC cũng cần bước khởi tạo đối tượng mật mã như ECB, cũng cần phải đảm bảo dữ liệu là bội số của 16 bytes. - Đoạn code: ```python= from Crypto.Cipher import AES from Crypto.Random import get_random_bytes from Crypto.Util.Padding import pad,unpad key = get_random_bytes(16) iv = get_random_bytes(16) data = "test mesage " cipher = AES.new(key, AES.MODE_CBC,iv) # Mã hóa en_data = cipher.encrypt(pad(data.encode(), 16)) print(en_data) # Giải mã de_data = unpad(cipher.decrypt(en_data, 16)) print(de_data) ``` ### 3. Cipher Feedback (CFB) - Đây là một chế độ hoạt động biến mật mã khối thành mật mã luồng, nếu hai chế độ mã hóa trên dữ liệu vào (input) là khối văn bản gốc (đối với ECB) hoặc là khối dữ liệu gốc **XOR** với IV rồi mới đưa chúng vào thuật toán mã hóa (CBC), thì đối với **CFB** input là **IV** ![image](https://hackmd.io/_uploads/SkrPD7Hvyg.png) - Sau khi đưa IV vào thuật toán AES mã hóa với key thì ta sẽ thu được output gọi là **mã hóa dòng** (keystream). Sau đó keytream sẽ XOR với khối dữ liệu gốc (Plaintext) lúc đó ta sẽ thu được Ciphertext và Ciphertext này sẽ được đưa vào thuật toán mã hóa AES tiếp theo (đóng vai trò là input của thuật toán mã hóa tiếp theo) - Chính vì Plaintext chỉ được **XOR** với keystream mà không được đưa qua thuật toán AES. Chính vì vậy khối Plaintext không cần phải được đệm (Pad) để phù hợp với kích thước khối của thuật toán mã hóa AES. Ta thấy đây là điểm khác của CFB so với ECB, CBC. - Ưu điểm: - Do có một số dữ liệu bị mất do sử dụng thanh ghi dịch chuyển nên việc áp dụng phân tích mật mã gặp khó khăn. - Có thể xử lý luồng dữ liệu ở mọi kích thước. - Nhược điểm: - Nhược điểm của CFB cũng giống như nhược điểm của chế độ CBC. Cả mất mát khối và mã hóa đồng thời nhiều khối đều không được mã hóa hỗ trợ. - Tuy nhiên, giải mã có thể song song hóa và chịu được mất mát. Phức tạp hơn một chút và có thể gây ra lỗi. Chế độ phản hồi đầu ra :::info Vậy làm nào đẻ mã hóa/giải mã dữ liệu theo chế độ CFB? ::: - Đầu tiên ta cũng cần khởi tạo đối tượng mật mã CFB ![image](https://hackmd.io/_uploads/H1VDyNBD1x.png) $\Rightarrow$ Hàm new() ở cấp mô-đun trong crypto.Cipher khởi tạo một đối tượng mật mã CBC mới cho thuật toán cơ sở có liên quan. Trong định nghĩa sau đây, <algorthm> có thể là AES $\Rightarrow$ `iv (byte)` – vectơ khởi tạo. Một mẩu dữ liệu không thể đoán trước đối với đối thủ. Nó dài bằng kích thước khối (ví dụ: 16 byte cho AES). Nếu không có, thư viện sẽ tạo ra một giá trị IV ngẫu nhiên. $\Rightarrow$ `segment_size` (số nguyên) – số bit (không phải byte!) palintext và ciphertext được phân đoạn trong (mặc định nếu không được chỉ định: 8 bit = 1 byte). $\Rightarrow$ Các phương thức và của đối tượng mật mã CFB chấp nhận dữ liệu có độ dài bất kỳ (tức là không cần đệm). - Đoạn code: - Mã hóa: ```python= import json from base64 import b64encode from Crypto.Cipher import AES from Crypto.Random import get_random_bytes data = b"secret" key = get_random_bytes(16) cipher = AES.new(key, AES.MODE_CFB) ct_bytes = cipher.encrypt(data) iv = b64encode(cipher.iv).decode('utf-8') ct = b64encode(ct_bytes).decode('utf-8') result = json.dumps({'iv':iv, 'ciphertext':ct}) print(result) {"iv": "VoamO23kFSOZcK1O2WiCDQ==", "ciphertext": "f8jciJ8/"} ``` - Giải mã: ```python= import json from base64 import b64decode from Crypto.Cipher import AES # We assume that the key was securely shared beforehand try: b64 = json.loads(json_input) iv = b64decode(b64['iv']) ct = b64decode(b64['ciphertext']) cipher = AES.new(key, AES.MODE_CFB, iv=iv) pt = cipher.decrypt(ct) print("The message was: ", pt) except (ValueError, KeyError): print("Incorrect decryption") ``` ### 4. Output feedback (OFB) - **OFB** là một chế độ khác dẫn đến mật mã luồng. Cũng có quy trình gần giống **CFB**, tuy nhiên đối với CFB sau khi đưa **IV** vào thuật toán mã hóa **AES** rồ thu được keystream, sau đó dùng keystream được dùng để XOR với khối dữ liệu gốc (plaintext) thu được Ciphertext. Ciphertext đó sẽ trở thành input của thuật toán mã hóa AES tiếp theo, thì đối với **OFB** các bước cũng giống như vậy nhưng sẽ khác chỗ input của thuật toán mã hóa tiếp theo không phải là Ciphertext mà là keystream. Quá trình giải mã thì ta sẽ làm ngược lại ![image](https://hackmd.io/_uploads/S1hb8VBvJe.png) - Ưu điểm: - Trong trường hợp CFB, một lỗi bit đơn trong một khối được truyền đến tất cả các khối tiếp theo. Vấn đề này được giải quyết bằng OFB vì nó không có lỗi bit trong khối văn bản thuần túy. Do đó, lỗi trong quá trình truyền không được truyền. vì **OFB** Chỉ phụ thuộc vào Keystream trước đó (không phụ thuộc vào Plaintext hay Ciphertext trước đó). - Nhược điểm: - Nhược điểm của OFB là do chế độ hoạt động của nó nên dễ bị tấn công sửa đổi luồng tin nhắn hơn CFB. - Nếu luồng khóa được sử dụng lại, tính bảo mật sẽ bị xâm phạm. :::info Vậy làm thế nào để mã hóa/giải mã dữ liệu theo chế độ OFB bằng code? ::: - Đầu tiên ta cần khởi tạo đối tượng mật mã OFB ![image](https://hackmd.io/_uploads/ryCGONHDke.png) $\Rightarrow$ Hàm `new()` ở cấp mô-đun trong crypto.Cipher khởi tạo một đối tượng mật mã CBC mới cho thuật toán cơ sở có liên quan. Trong định nghĩa sau đây, <algorthm> có thể là AES $\Rightarrow$ `iv (byte)` – vectơ khởi tạo. Một mẩu dữ liệu không thể đoán trước đối với đối thủ. Nó dài bằng kích thước khối (ví dụ: 16 byte cho AES). Nếu không có, thư viện sẽ tạo ra một giá trị IV ngẫu nhiên. $\Rightarrow$ Các phương thức và của đối tượng mật mã CFB chấp nhận dữ liệu có độ dài bất kỳ (tức là không cần đệm). - Code: - Mã hóa: ```python= import json from base64 import b64encode from Crypto.Cipher import AES from Crypto.Random import get_random_bytes data = b"secret" key = get_random_bytes(16) cipher = AES.new(key, AES.MODE_OFB) ct_bytes = cipher.encrypt(data) iv = b64encode(cipher.iv).decode('utf-8') ct = b64encode(ct_bytes).decode('utf-8') result = json.dumps({'iv':iv, 'ciphertext':ct}) print(result) {"iv": "NUuRJbL0UMp8+UMCk2/vQA==", "ciphertext": "XGVGc1Gw"} ``` - Giải mã: ```python= import json from base64 import b64decode from Crypto.Cipher import AES # We assume that the key was securely shared beforehand try: b64 = json.loads(json_input) iv = b64decode(b64['iv']) ct = b64decode(b64['ciphertext']) cipher = AES.new(key, AES.MODE_OFB, iv=iv) pt = cipher.decrypt(ct) print("The message was: ", pt) except (ValueError, KeyError): print("Incorrect decryption") ``` ### 5. Counter (CTR) - Chế độ này biến mật mã khối thành mật mã luồng. Mỗi lần một giá trị khởi tạo bộ đếm được mã hóa và đưa vào làm đầu vào cho XOR với văn bản thuần túy, kết quả là khối văn bản mã hóa. Chế độ CTR độc lập với việc sử dụng phản hồi và do đó có thể được triển khai song song. ![image](https://hackmd.io/_uploads/SkagiVrvkg.png) - Ưu điểm: - Vì có giá trị đếm khác nhau cho mỗi khối, nên mối quan hệ trực tiếp giữa văn bản thuần túy và văn bản mã hóa được tránh. - Điều này có nghĩa là cùng một văn bản thuần túy có thể ánh xạ đến các văn bản mã hóa khác nhau. - Nhược điểm: - Thực tế là chế độ CTR yêu cầu bộ đếm đồng bộ ở cả máy phát và máy thu là một nhược điểm nghiêm trọng. Việc khôi phục văn bản thuần túy không chính xác khi mất đồng bộ hóa. :::info Vậy làm thế nào để ta mã hóa/giải mã dữ liệu theo chế độ CTR bằng code? ::: - Trước tiên ta cũng cần khởi tạo đối tượng mật mã **CTR** ![image](https://hackmd.io/_uploads/HkCToNrPyx.png) $\Rightarrow$ **nonce (byte)** - giá trị của nonce cố định. Nó phải là duy nhất cho kết hợp tin nhắn / khóa. Chiều dài của nó thay đổi từ 0 đến kích thước khối trừ 1. Nếu không có, thư viện sẽ tạo ra một nonce ngẫu nhiên có độ dài bằng kích thước khối/2. $\Rightarrow$ **initial_value** (số nguyên hoặc byte) – giá trị của bộ đếm cho khối bộ đếm đầu tiên. Nó có thể là một số nguyên hoặc byte (là cùng một số nguyên, chỉ được mã hóa endian lớn). Nếu không được chỉ định, bộ đếm bắt đầu từ 0. $\Rightarrow$ **counter** – một đối tượng bộ đếm tùy chỉnh được tạo bằng `Crypto.Util.Counter.new()`. Điều này cho phép định nghĩa một khối bộ đếm phức tạp hơn. $\Rightarrow$ Các phương thức và của đối tượng mật mã CTR chấp nhận dữ liệu có độ dài bất kỳ (tức là không cần đệm). Cả hai đều đưa ra một ngoại lệ ngay khi bộ đếm quấn xung quanh để lặp lại bản gốc giá trị - Đoạn code: - Mã hóa: ```python= import json from base64 import b64encode from Crypto.Cipher import AES from Crypto.Random import get_random_bytes data = b"secret" key = get_random_bytes(16) cipher = AES.new(key, AES.MODE_CTR) ct_bytes = cipher.encrypt(data) nonce = b64encode(cipher.nonce).decode('utf-8') ct = b64encode(ct_bytes).decode('utf-8') result = json.dumps({'nonce':nonce, 'ciphertext':ct}) print(result) {"nonce": "XqP8WbylRt0=", "ciphertext": "Mie5lqje"} ``` - Giải mã: ```python= import json from base64 import b64decode from Crypto.Cipher import AES # We assume that the key was securely shared beforehand try: b64 = json.loads(json_input) nonce = b64decode(b64['nonce']) ct = b64decode(b64['ciphertext']) cipher = AES.new(key, AES.MODE_CTR, nonce=nonce) pt = cipher.decrypt(ct) print("The message was: ", pt) except (ValueError, KeyError): print("Incorrect decryption") ``` # Attack ## 1. Meet in the middle attack - Tấn công **Meet-in-the-Middle (MITM)** là một kỹ thuật tấn công mật mã học dùng để giảm độ phức tạp tính toán khi giải các hệ mã hóa khối sử dụng nhiều **lớp mã hóa theo trình tự** như $2DES$, $3DES$ thậm chí cả $AES$ nếu nó sử dụng **chẳn** lần mã hóa hoặc các hệ có dạng $E_{k2}(E_{k1}(P))$ nhưng hiệu quả nhất là đối với $2DES$. - Cũng như $3DES$, $2DES$ cũng là biến thể của thuật toán DES, trong đó bản rõ (plainext) được mã hóa hai lần liên tiếp bằng $2$ khóa $K_1$ và $K_2$. Gọi $P$ là bản rõ, $C$ là bản mã ta có. - Quá trình mã hóa: $$C= E_{k2}(E_{k1}(P))$$ - Quá trình giải mã: $$P=D_{k1}(D_{k2}(C))$$ - Để mã hóa khối như $2DES$ ta cần phải biết khóa $K_1, K_2$. Ý tưởng của phương pháp tấn công này chính là lợi dụng việc ta biết ích nhất một cặp $(P,C)$ và dựa vào đó để tìm $K_1, K_2$ mà không cần thử $2^{112}$ khả năng . Vì ta thấy rằng: $$D_{k2}(C)=D_{k2}(E_{k2}(E_{k1}(P)))=E_{k1}(P)$$ $$\Rightarrow D_{k2}(C)=E_{k1}(P)$$ $\Rightarrow$ Thay vì thử tất cả các cặp khóa $(K_1,K_2)$ tức ( $2^{56} \times 2^{56}= 2^{112}$) khả năng ta chỉ cần brute-force $K_1$ sau đó thế vào $E_{k1}(P)$ và lưu tất cả các giá trị đó vào một list, ta tiếp tục brute $K_2$ và kiểm tra xem $D_{k2}(C)$ bằng với giá trị nào trong list thì $K_1$ và $K_2$ tương ứng đó chính là $K_1$ và $K_2$ ta cần tìm. - Ví dụ: - Source: ```python= from Crypto.Cipher import AES from Crypto.Util.Padding import pad from hashlib import md5 from os import urandom FLAG = b"KCSC{???????????????????????????}" assert len(FLAG) % 16 == 1 # hint key1 = md5(urandom(3)).digest() key2 = md5(urandom(3)).digest() cipher1 = AES.new(key1, AES.MODE_ECB) cipher2 = AES.new(key2,AES.MODE_ECB) enc = cipher1.encrypt(pad(FLAG,16)) enc = cipher2.encrypt(enc) print(enc.hex()) # 21477fac54cb5a246cb1434a1e39d7b34b91e5c135cd555d678f5c01b2357adc0c6205c3a4e3a8e6fb37c927de0eec95 ``` - Ta thấy chall này flag được mã hóa chẵn lần (2 lần) bằng thuật toán **AES**, ta thấy là khi ta mã hóa flag lần $1$ với $key1$ sẽ bằng với ta giải mã $enc$ với $key2$. Ta có sẽ dùng **Meet in the middle attack** để tìm flag. - Để tấn công bằng phương pháp này ta cần phải biết ít nhất một cặp $(C,P)$, rất mai từ $hint$ của bài ta biết được là độ dài của flag có thể là $17, 33, 49,...$ và chall này dùng padding **PKCS#7** nghĩa là block cuối của flag sẽ là `b'}'+b'0x0f'*15` vậy là ta đã biết được $P$, lúc này ta chỉ cần lấy $16$ byte cuối của $enc$ là có được $C$ - Như vậy là ta đã biết được $1$ cặp $(C,P)$ rồi, lúc này chỉ cần áp dụng theo **Meet in the middle attack** ở trên để tìm flag là xong. - Đầu tiên ta cần tìm được cặp khóa $key1$ và $key2$: ```python= from Crypto.Cipher import AES from hashlib import md5 enc_hex = "21477fac54cb5a246cb1434a1e39d7b34b91e5c135cd555d678f5c01b2357adc0c6205c3a4e3a8e6fb37c927de0eec95" enc = bytes.fromhex(enc_hex) last_plain_block = b'}' + b'\x0f'*15 last_enc_block = enc[-16:] def gen_keys(): for i in range(2**24): yield md5(i.to_bytes(3, 'big')).digest() table = {} for key1 in gen_keys(): encrypted = AES.new(key1, AES.MODE_ECB).encrypt(last_plain_block) table[encrypted] = key1 for key2 in gen_keys(): decrypted = AES.new(key2, AES.MODE_ECB).decrypt(last_enc_block) if decrypted in table: key1 = table[decrypted] print("Found keys!") print(f"key1 = {key1.hex()}") print(f"key2 = {key2.hex()}") break #key1 = 2fc5e63325ac93c1afd394e50ad3f349 #key2 = 8f06881701d9d96af546e6085f7af4b1 ``` - Sau khi tìm được khóa rồi thì ta có thể dễ dàng giải mã $enc$ để tìm flag - Script: ```python= from Crypto.Cipher import AES from Crypto.Util.Padding import unpad enc_hex = "21477fac54cb5a246cb1434a1e39d7b34b91e5c135cd555d678f5c01b2357adc0c6205c3a4e3a8e6fb37c927de0eec95" enc = bytes.fromhex(enc_hex) key1 = bytes.fromhex("2fc5e63325ac93c1afd394e50ad3f349") key2 = bytes.fromhex("8f06881701d9d96af546e6085f7af4b1") cipher2 = AES.new(key2, AES.MODE_ECB) cipher1 = AES.new(key1, AES.MODE_ECB) step1 = cipher2.decrypt(enc) plaintext_padded = cipher1.decrypt(step1) flag = unpad(plaintext_padded, 16) print(flag.decode()) ``` :::spoiler Flag KCSC{MeEt_In_tHe_mIdDLe_AttaCk__} ::: ## 2. Padding Oracle Attack - **Oracle** đơn giản là một hộp đen trả lời câu hỏi mà chúng ta đặt ra, nó sẽ trả lời là Yes/No tùy thuộc vào câu hỏi mà nó được thiết kế để trả lời. - Ta dùng **Padding Oracle Attack**: - khi hệ thống dùng `block cipher` có padding `(AES-CBC)` - chúng ta có thể gửi bản mã đến hệ thống và hệ thống sẽ phản hồi khác nhau về lỗi như là tiết lộ thông ting padding là **đúng** hay **sai** qua thông báo lỗi. - Thì Padding Oracle Attack lợi dụng cách hoạt động của **PKCS#7** để thực hiện tấn công (lý thuyết [PKCS#7](https://hackmd.io/7xEdctC2RQG-3C0G70BsnA?view#IV-PKCS7-Padding)). - Bối cảnh của cuộc tấn công: ![image](https://hackmd.io/_uploads/r1e8fIn-ex.png) - Đây là quá trình giải mã block cipher (AES-CBC). - Chúng ta có một số dữ kiện sau: - chúng ta có ciphertext ký hiệu là $C$ (đã biết). - Gọi $C$ sao khi giải mã thông qua **Block cipher Decrytion** cùng với **key** là giá trị trung gian. Ký hiệu là $I$ (ta không có biết được giá trị của $I$ vì ta không biết được $Key)$ - Còn văn bản gốc thuần túy ký hiệu là: $P$ - Mục tiêu của chúng ta là tìm $P$ bằng cách: $$P=I \bigoplus C$$ - Nhưng ta chỉ có được $C$ và không biết được $key$ $\rightarrow$ không biết được $I$ - Nhiệm vụ bây giờ là chúng ta cần tìm $I$ mà không cần $key$ :::info Lưu ý: Nếu chúng ta giải mã $C_1$ thì $P_1= IV \bigoplus I_1$ ::: - Padding Oracle Attack sẽ giúp ta tìm được các $P$ mà không cần biết được $key$. Chỉ cần ta có được các $C$, $IV$. Bằng cách lợi dụng thông báo của hệ thống về padding có hợp lệ hay không. - Bây giờ chúng ta vào vấn đề chính nè :sweat_smile: ![image](https://hackmd.io/_uploads/rJpYLL2Zxg.png) - Nói tóm lại mục tiêu của chúng ta là sẽ tìm $I$ để xor $I$ với khối $C$ đứng trước cipher của chúng ta cần giải mã `P1 = IV xor I1`, `P2=C1 xor I2`,.... Mà không cần biết $key$ - Ví dụ bây giờ ta cần tìm $I_2$ để mã hóa $C_2$, ta sẽ tìm từng byte của $I_2$ từ trái quá phải bằng cách lợi dụng việc $I_2$ là một giá trị cố định không thay đổi ( vì ta không thay đổi $C_2$) mà ta sẽ thay đổi $C_1$ - Khi ta tìm $I_2[15]$ ta sẽ thay đổi byte cuối của $C_1$ là $C_1[15]$ bằng cách brute $0-255$ giá trị gọi là $C_{1fake}[15]$ sao cho $$C_{1fake}[15] \bigoplus I_2[15]=01$$ - Nghĩa là ta ép $P_{2fake}[15]=01$, từ đó ta có thể tìm được $$I_2[15]=C_{1fake}[15] \bigoplus 01$$ $$\Rightarrow P_2[15] = I_2[15] \bigoplus C_1[15]$$ - Tương tự như thế ta có thể tìm được toàn bộ $P_2$ bằng cách lần lượt tìm $P_2[14]= , P_2[13],...P_2[0]$ - Bây giờ ta có thể tìm $P_2[14]$ bằng cách brute force $C_{1fake}[14]$ như lúc nãy, sao cho $P_{2fake}[14]=02$ $$I_2[14]=C_{1fake}[14] \bigoplus 02$$ $$\Rightarrow P_2[14]=I_2[14]\bigoplus C_1[14]$$ - Ta nên chú ý là khi tìm $P_2[14]$ ta không chỉ ép byte $14$ của $P_{2fake}$ là $02$ mà còn ép byte cuối của nó là $02$ nữa (`02=C1fake[14] xor I2[14])`. cụ thể là ta sẽ ép $P_{2fake}$ lần lượt là : $01, 02\ 02, 03\ 03\ 03,...,10\ ^*16$ - Quay trở lại với việc tìm $P_2[14]$, lúc này ta chỉ cần brute force $C_{1fake}[14]$ thôi còn $C_{1fake}[15]$ thì không cần. Vì ta biết $I_2$ là cố định và lúc nãy ta đã có $I_2[15]$ rồi nên bây giờ ta chỉ cần tìm $$C_{1fake}[15]= I_2[15] \bigoplus 02$$ $\Rightarrow$ Lúc này ta đã có $C_{1fake}[15]$ sao cho: $$C_{1fake}[15] \bigoplus I_2[15] = 02$$ - Khi tính $P_2[13]$ ta cũng thực hiện như vậy và ép $3$ byte cuối của $P_{2fake}$ là $03\ 03\ 03$ :::info Vậy tại sao ta phải ép các byte cuối của $P_{fake}$ là $01, 02\ 02,...$ và điều kiện dừng của brute fore là gì? $\Rightarrow$ Việc ta có thể làm như trên là dựa vào cách hoạt động của PKCS#7 và thông báo padding hợp lệ hay không của hệ thống. Ở đây hệ thống sẽ thông báo hợp lệ khi padding là $01, 02\ 02, 03\ 03\ 03,...$ Và đây chính điều kiện dừng để chúng ta tìm được $C_{fake}$ từ đó tìm được $I= C_{fake} \bigoplus P_{fake}$ ::: **Lưu ý:** Đối với bước tìm byte cuối là byte $15$ của block khi ta ép $P_{fake}$ là $01$ thì ta cần chú ý kiểm tra tránh trường hợp hợp **dương tính giả (false positive)** nó có thể là $02\ 02$, $03\ 03\ 03$ chứ không phải là $01$ - Tham khảo [video1](https://www.youtube.com/watch?v=4EgD4PEatA8&t=701s), [video2](https://www.youtube.com/watch?v=uDHo-UAM6_4)