2.1. Phá mã tuyến tính trên TinyDES

2.1.1. Mô tả TinyDES

Trong phần mô tả phá mã vi sai mình đã sử dụng TinyDES để làm ví dụ. Ở đây mình tiếp tục sử dụng TinyDES để ví dụ cho phá mã tuyến tính. Nhằm gợi nhớ cấu trúc của TinyDES thì mình xin chép lại.

TinyDES là một phiên bản thu nhỏ của chuẩn mã hóa DES. TinyDES là mã hóa khối theo mô hình Feistel, kích thước khối là \(8\) bit, kích thước khóa cũng là \(8\) bit. Mỗi vòng khóa con có độ dài \(6\) bit.

Hình 2.10 Một vòng TinyDES

Mã TinyDES khá đơn giản. Theo mô hình Feistel, khối đầu vào \(8\) bit được chia thành hai nửa trái phải \(4\) bit. Nửa phải sẽ đi qua các hàm Expand, \(\mathsf{SBox}\) và PBox, sau đó XOR với nửa trái để được nửa phải mới. Còn nửa trái mới là nửa phải cũ. Tóm lại công thức mô hình Feistel là:

\[L_{i+1} = R_i, \quad R_{i+1} = L_i \oplus F(R_i, K_{i+1})\]

với \(i = 1, 2, 3\) tương ứng \(3\) vòng với đầu vào của khối là \((L_0, R_0)\).

Chúng ta cần các động tác sau:

1. Expand: mở rộng và hoán vị \(R_i\) từ \(4\) bits lên \(6\) bits. Giả sử \(4\) bits của \(R_i\) là \(b_0 b_1 b_2 b_3\) thì kết quả sau khi Expand là \(b_2 b_3 b_1 b_2 b_1 b_0\).

2. SBox: gọi \(6\) bits đầu vào là \(b_0 b_1 b_2 b_3 b_4 b_5\). Khi đó ta tra cứu theo bảng SBox với \(b_0 b_5\) chỉ số hàng, \(b_1 b_2 b_3 b_4\) chỉ số cột. Nói cách khác bảng SBox có \(4\) hàng, \(16\) cột. Kết quả của SBox là một số \(4\) bit.

3. PBox: là hàm hoán vị \(4\) bits \(b_0 b_1 b_2 b_3\) thành \(b_2 b_0 b_3 b_1\).

Như vậy, hàm \(F\) của mô hình Feistel đối với mã TinyDES là:

\[F(R_i, K_i) = \mathsf{PBox}(\mathsf{SBox}(\mathsf{Expand}(R_i) \oplus K_{i+1})).\]

Để sinh khóa con cho \(3\) vòng, khóa ban đầu được chia thành hai nửa trái phải lần lượt là \(KL_0\) và \(KR_0\). TinyDES thực hiện như sau:

1. Vòng 1: \(KL_0\) và \(KR_0\) được dịch vòng trái \(1\) bit để được \(KL_1\) và \(KR_1\);

2. Vòng 2: \(KL_1\) và \(KR_1\) được dịch vòng trái \(2\) bit để được \(KL_2\) và \(KR_2\);

3. Vòng 3: \(KL_2\) và \(KR_2\) được dịch vòng trái \(1\) bit để được \(KL_3\) và \(KR_3\).

Khi đó, khóa \(K_i\) ở vòng thứ \(i\) (với \(i = 1, 2, 3\)) là hoán vị và nén \(8\) bits của \(KL_i\) và \(KR_i\) lại thành \(6\) bits.

Đặt \(8\) bits khi ghép \(KL_i \Vert KR_i\) là \(k_0 k_1 k_2 k_3 k_4 k_5 k_6 k_7\), kết quả là \(6\) bits \(k_5 k_1 k_3 k_2 k_7 k_0\).

tinydes.py

# tindeys.py

sbox = [
    0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8, 0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7,
    0x0, 0xF, 0x7, 0x4, 0xE, 0x2, 0xD, 0x1, 0xA, 0x6, 0xC, 0xB, 0x9, 0x5, 0x3, 0x8,
    0x4, 0x1, 0xE, 0x8, 0xD, 0x6, 0x2, 0xB, 0xF, 0xC, 0x9, 0x7, 0x3, 0xA, 0x5, 0x0,
    0xF, 0xC, 0x8, 0x2, 0x4, 0x9, 0x1, 0x7, 0x5, 0xB, 0x3, 0xE, 0xA, 0x0, 0x6, 0xD
]


def Xor(a: list[int], b: list[int]) -> list[int]:
    return [x^y for x, y in zip(a, b)]


def Expand(R: list[int]) -> list[int]:
    return [R[2], R[3], R[1], R[2], R[1], R[0]]


def SBox(R: list[int]) -> list[int]:
    row = int("".join(map(str, [R[0], R[5]])), 2)
    col = int("".join(map(str, R[1:5])), 2)

    return list(map(int, format(sbox[row*16 + col], "04b")))


def PBox(R: list[int]) -> list[int]:
    return [R[2], R[0], R[3], R[1]]


def PBox_inv(R: list[int]) -> list[int]:
    return [R[1], R[3], R[0], R[2]]


def Compress(K: list[int], round: int) -> list[int]:
    left, right = K[:4], K[4:]
    if round == 0 or round == 2:
        left = left[1:] + left[:1]
        right = right[1:] + right[:1]
    elif round == 1:
        left = left[2:] + left[:2]
        right = right[2:] + right[:2]

    Ki = left + right
    return left, right, [Ki[5], Ki[1], Ki[3], Ki[2], Ki[7], Ki[0]]


def encrypt_block(plaintext: list[int], key: list[int]) -> list[int]:
    keys = [key]
    left, right = key[:4], key[4:]
    for i in range(3):
        left, right, key = Compress(left + right, i)
        keys.append(key)

    left, right = plaintext[:4], plaintext[4:]
    for i in range(3):
        left, right = right, Xor(left, PBox(SBox(Xor(Expand(right), keys[i+1]))))

    return left + right

#print(encrypt_block([0, 1, 0, 1, 1, 1, 0, 0], [1, 0, 0, 1, 1, 0, 1, 0]))

2.1.2. Phá mã tuyến tính trên TinyDES

Trong các phép biến đổi trên TinyDES thì chỉ có \(\mathsf{SBox}\) là không tuyến tính. Tuy nhiên nếu chỉ xét một số bit nhất định giữa đầu vào và đầu ra thì ta có quan hệ tuyến tính.

Nhắc lại, một biến đổi \(f: \mathbb{F}_2^n \to \mathbb{F}_2^m\) gọi là tuyến tính nếu với mọi \(\bm{x}_1, \bm{x}_2 \in \mathbb{F}_2^n\) ta đều có

\[f(\bm{x}_1 \oplus \bm{x}_2) = f(\bm{x}_1) \oplus f(\bm{x}_2).\]

Ta sẽ xét các phép biến đổi trong TinyDES.

2.1.2.1. Phép XOR key

Gọi \(K\) là khóa con ở vòng nào đó trong thuật toán. Khi đó nếu đặt \(Y_1 = X_1 \oplus K\) và \(Y_2 = X_2 \oplus K\) thì ta có \(Y_1 \oplus Y_2 = X_1 \oplus X_2\). Như vậy phép XOR là biến đổi tuyến tính.

2.1.2.2. Phép PBox

Phép PBox bảo toàn số bit (hoán vị \(4\) bits thành \(4\) bits) và cách xây dựng hoán vị là một biến đổi tuyến tính. Việc hoán vị \(4\) bits \(b_0 b_1 b_2 b_3\) thành \(b_2 b_0 b_3 b_1\) tương đương với phép nhân ma trận

\[\begin{split}\begin{pmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix} \cdot \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \end{pmatrix} = \begin{pmatrix} b_2 \\ b_0 \\ b_3 \\ b_1 \end{pmatrix}.\end{split}\]

Do đó nếu đặt \(Y_1 = \mathsf{PBox}(X_1)\) và \(Y_2 = \mathsf{PBox} (X_2)\) thì

\[Y_1 \oplus Y_2 = \mathsf{PBox}(X_1) \oplus \mathsf{PBox}(X_2) = \mathsf{PBox} (X_1 \oplus X_2).\]

2.1.2.3. Phép Expand

Tương tự, phép Expand cũng là biến đổi tuyến tính và nếu đặt \(Y_1 = \mathsf{Expand}(X_1)\) và \(Y_2 = \mathsf{Expand}(X_2)\) thì

\[Y_1 \oplus Y_2 = \mathsf{Expand}(X_1) \oplus \mathsf{Expand}(X_2) = \mathsf{Expand}(X_1 \oplus X_2).\]

2.1.2.4. Phép SBox

Phép SBox là một biến đổi không tuyến tính với input \(6\) bits và output \(4\) bits.

Đặt \(\bm{y} = \mathsf{SBox}(\bm{x})\) với \(\bm{x} = (x_0, x_1, x_2, x_3, x_4, x_5) \in \mathbb{F}_2^6\) và \(\bm{y} = (y_0, y_1, y_2, y_3) \in \mathbb{F}_2^4\).

Gọi \(\bm{a} = (a_0, a_1, a_2, a_3, a_4, a_5) \in \mathbb{F}_2^6\) với biểu diễn thập phân là các số từ \(1\) tới \(63\), nghĩa là trừ vector không.

Tương tự, gọi \(\bm{b} = (b_0, b_1, b_2, b_3) \in \mathbb{F}_2^4\) với biểu diễn thập phân là các số từ \(1\) tới \(15\), ta cũng không xét vector không.

Tích vô hướng là một biểu diễn tuyến tính giữa \(\bm{a}\) và \(\bm{x}\):

\[\langle \bm{a}, \bm{x} \rangle = a_0 x_0 \oplus a_1 x_1 \oplus a_2 x_2 \oplus a_3 x_3 \oplus a_4 x_4 \oplus a_5 x_5 \oplus a_6 x_6.\]

Tương tự, quan hệ tuyến tính giữa \(\bm{b}\) và \(\bm{y}\) là

\[\langle \bm{b}, \bm{y} \rangle = b_0 y_0 \oplus b_1 y_1 \oplus b_2 y_2 \oplus b_3 y_3.\]

Lúc này ta sẽ quan tâm xem với các vector \(\bm{a}\) và \(\bm{b}\) nào sẽ khiến nhiều bit của \(\bm{y}\) phụ thuộc tuyến tính vào các bit của \(\bm{x}\), cụ thể là khi \(\langle \bm{x}, \bm{a} \rangle = \langle \bm{y}, \bm{b} \rangle\).

Với hai vector \(\bm{a} \in \mathbb{F}_2^6\) và \(\bm{b} \in \mathbb{F}_2^4\), gọi \(S(\bm{a}, \bm{b})\) là số lượng cặp vector \((\bm{x}, \bm{y})\) sao cho

\[\langle \bm{x}, \bm{a} \rangle = \langle \bm{y}, \bm{b} \rangle.\]

Bảng dưới liệt kê các giá trị \(S(\bm{a}, \bm{b}) - 32\) với hàng đầu là các vector \(\bm{b}\) từ \(1\) tới \(15\), và cột đầu là các vector \(\bm{a}\) từ \(1\) tới \(32\).

	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)	\(11\)	\(12\)	\(13\)	\(14\)	\(15\)
\(1\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(2\)	\(0\)	\(-2\)	\(6\)	\(2\)	\(2\)	\(4\)	\(-4\)	\(2\)	\(6\)	\(0\)	\(-4\)	\(0\)	\(-4\)	\(-6\)	\(-18\)
\(3\)	\(0\)	\(-2\)	\(6\)	\(-2\)	\(6\)	\(0\)	\(0\)	\(-2\)	\(2\)	\(4\)	\(0\)	\(0\)	\(4\)	\(2\)	\(-2\)
\(4\)	\(-4\)	\(-6\)	\(2\)	\(-2\)	\(2\)	\(0\)	\(0\)	\(4\)	\(-4\)	\(-6\)	\(-2\)	\(6\)	\(-2\)	\(-4\)	\(0\)
\(5\)	\(4\)	\(-2\)	\(-2\)	\(-2\)	\(2\)	\(-4\)	\(12\)	\(4\)	\(4\)	\(-2\)	\(-6\)	\(-2\)	\(6\)	\(0\)	\(4\)
\(6\)	\(4\)	\(0\)	\(0\)	\(8\)	\(4\)	\(4\)	\(-4\)	\(2\)	\(-2\)	\(6\)	\(-2\)	\(2\)	\(6\)	\(2\)	\(2\)
\(7\)	\(4\)	\(-4\)	\(-4\)	\(4\)	\(0\)	\(4\)	\(-4\)	\(-10\)	\(2\)	\(-2\)	\(6\)	\(2\)	\(6\)	\(-2\)	\(-2\)
\(8\)	\(-2\)	\(-2\)	\(0\)	\(-2\)	\(8\)	\(-4\)	\(-6\)	\(2\)	\(4\)	\(0\)	\(-2\)	\(-4\)	\(2\)	\(-6\)	\(12\)
\(9\)	\(2\)	\(2\)	\(0\)	\(-6\)	\(0\)	\(4\)	\(-10\)	\(2\)	\(0\)	\(4\)	\(6\)	\(-8\)	\(2\)	\(2\)	\(0\)
\(10\)	\(2\)	\(-8\)	\(6\)	\(0\)	\(-2\)	\(4\)	\(-2\)	\(4\)	\(6\)	\(-4\)	\(2\)	\(4\)	\(2\)	\(0\)	\(2\)
\(11\)	\(-2\)	\(4\)	\(6\)	\(-8\)	\(2\)	\(0\)	\(-2\)	\(8\)	\(-2\)	\(4\)	\(6\)	\(8\)	\(-6\)	\(0\)	\(-2\)
\(12\)	\(2\)	\(0\)	\(2\)	\(0\)	\(6\)	\(0\)	\(6\)	\(-2\)	\(0\)	\(2\)	\(-4\)	\(6\)	\(-4\)	\(2\)	\(0\)
\(13\)	\(-2\)	\(8\)	\(-2\)	\(-4\)	\(-2\)	\(4\)	\(-2\)	\(6\)	\(-4\)	\(2\)	\(-8\)	\(2\)	\(12\)	\(6\)	\(0\)
\(14\)	\(-2\)	\(2\)	\(0\)	\(2\)	\(4\)	\(0\)	\(2\)	\(-4\)	\(-2\)	\(-6\)	\(4\)	\(2\)	\(0\)	\(-4\)	\(2\)
\(15\)	\(-6\)	\(-6\)	\(-4\)	\(10\)	\(0\)	\(0\)	\(-2\)	\(0\)	\(6\)	\(-2\)	\(4\)	\(-2\)	\(-8\)	\(8\)	\(2\)
\(16\)	\(2\)	\(-2\)	\(4\)	\(-2\)	\(0\)	\(-4\)	\(-6\)	\(-2\)	\(0\)	\(0\)	\(-2\)	\(-4\)	\(6\)	\(6\)	\(4\)
\(17\)	\(-2\)	\(2\)	\(4\)	\(-2\)	\(-4\)	\(0\)	\(10\)	\(2\)	\(0\)	\(0\)	\(10\)	\(0\)	\(6\)	\(6\)	\(0\)
\(18\)	\(-6\)	\(-4\)	\(2\)	\(0\)	\(2\)	\(0\)	\(6\)	\(4\)	\(2\)	\(4\)	\(6\)	\(0\)	\(6\)	\(4\)	\(-10\)
\(19\)	\(-2\)	\(0\)	\(-6\)	\(-4\)	\(-6\)	\(0\)	\(2\)	\(-4\)	\(-2\)	\(0\)	\(6\)	\(-4\)	\(-2\)	\(4\)	\(2\)
\(20\)	\(-2\)	\(0\)	\(-2\)	\(0\)	\(-2\)	\(8\)	\(-2\)	\(-2\)	\(0\)	\(6\)	\(0\)	\(2\)	\(4\)	\(2\)	\(4\)
\(21\)	\(2\)	\(0\)	\(2\)	\(0\)	\(-6\)	\(0\)	\(2\)	\(2\)	\(-8\)	\(2\)	\(0\)	\(-2\)	\(-4\)	\(-2\)	\(-4\)
\(22\)	\(-2\)	\(-2\)	\(-4\)	\(-6\)	\(0\)	\(4\)	\(2\)	\(0\)	\(-2\)	\(-2\)	\(4\)	\(2\)	\(0\)	\(4\)	\(2\)
\(23\)	\(2\)	\(6\)	\(8\)	\(6\)	\(0\)	\(0\)	\(2\)	\(0\)	\(2\)	\(6\)	\(0\)	\(-2\)	\(0\)	\(0\)	\(2\)
\(24\)	\(0\)	\(0\)	\(0\)	\(0\)	\(4\)	\(0\)	\(-4\)	\(0\)	\(-4\)	\(4\)	\(0\)	\(4\)	\(4\)	\(0\)	\(-8\)
\(25\)	\(0\)	\(8\)	\(0\)	\(4\)	\(0\)	\(4\)	\(0\)	\(4\)	\(-8\)	\(-8\)	\(4\)	\(-4\)	\(-4\)	\(0\)	\(0\)
\(26\)	\(4\)	\(2\)	\(-2\)	\(2\)	\(2\)	\(0\)	\(0\)	\(6\)	\(2\)	\(-4\)	\(0\)	\(0\)	\(0\)	\(2\)	\(2\)
\(27\)	\(4\)	\(2\)	\(6\)	\(2\)	\(2\)	\(8\)	\(0\)	\(6\)	\(-6\)	\(-4\)	\(0\)	\(-8\)	\(0\)	\(2\)	\(2\)
\(28\)	\(4\)	\(2\)	\(2\)	\(-2\)	\(6\)	\(0\)	\(-4\)	\(0\)	\(4\)	\(2\)	\(2\)	\(-2\)	\(-2\)	\(0\)	\(4\)
\(29\)	\(-4\)	\(6\)	\(6\)	\(2\)	\(2\)	\(-8\)	\(4\)	\(-4\)	\(0\)	\(-6\)	\(2\)	\(6\)	\(6\)	\(4\)	\(0\)
\(30\)	\(0\)	\(4\)	\(0\)	\(0\)	\(-4\)	\(0\)	\(0\)	\(2\)	\(6\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(2\)
\(31\)	\(0\)	\(-8\)	\(-4\)	\(0\)	\(4\)	\(4\)	\(4\)	\(2\)	\(-2\)	\(2\)	\(2\)	\(-2\)	\(-2\)	\(2\)	\(-2\)
\(32\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)

check_sbox.py

# check_sbox.py

from tinydes import SBox


S = [[0 for _ in range(15)] for __ in range(63)]

for a in range(1, 64):
    va = list(map(int, f"{a:06b}"))[::-1]
    for b in range(1, 16):
        vb = list(map(int, f"{b:04b}"))[::-1]
        for x in range(64):
            vx = list(map(int, f"{x:06b}"))[::-1]
            vy = SBox(vx)
            u = sum(i * j for i, j in zip(va, vx)) % 2
            v = sum(i * j for i, j in zip(vb, vy)) % 2
            if u == v:
                S[a - 1][b - 1] += 1

print(S)

Sau khi xem bảng phân phối \(S(\bm{a}, \bm{b})\) thì chúng ta quan tâm một số giá trị.

Xét \(S(16, 15) = 14\), tương ứng với vector \(\bm{a} = (0, 1, 0, 0, 0, 0)\) và \(\bm{b} = (1, 1, 1, 1)\), thì

\[x_1 = y_0 \oplus y_1 \oplus y_2 \oplus y_3\]

với xác suất \(14 / 64\).

Ngược lại ta cũng có

\[x_1 \neq y_0 \oplus y_1 \oplus y_2 \oplus y_3\]

với xác suất \(1 - 14 / 64\).

Ta kí hiệu mối quan hệ này là

\[\bm{y}[0, 1, 2, 3] = \bm{x}[1].\]

2.1.2.5. Hàm \(F\)

Xét \(\bm{y} = F(\bm{x}, \bm{k})\) là round function của TinyDES, trong đó

• \(\bm{x} = (x_0, x_1, x_2, x_3) \in \mathbb{F}_2^4\) là đầu vào cho round function (nửa phải);

• \(\bm{k} = (k_0, k_1, k_2, k_3, k_4, k_5, k_6) \in \mathbb{F}_2^6\) là khóa con ở vòng nào đó;

• \(\bm{y} = (y_0, y_1, y_2, y_3) \in \mathbb{F}_2^4\) là đầu ra của round function.

Ta có các động tác biến đổi sau.

Hàm Expand:

\[(x_0, x_1, x_2, x_3) \xrightarrow{\mathsf{Expand}} (x_2, x_3, x_1, x_2, x_1, x_0).\]

Hàm XOR key:

\[(x_2, x_3, x_1, x_2, x_1, x_0) \oplus (k_0, k_1, k_2, k_3, k_4, k_5) \rightarrow (x_0', x_1', x_2', x_3', x_4', x_5').\]

Hàm SBox:

\[\bm{x}' = (x_0', x_1', x_2', x_3', x_4', x_5') \xrightarrow{\mathsf{SBox}} \bm{y}' = (y_0', y_1', y_2', y_3').\]

Hàm PBox:

\[(y_0', y_1', y_2', y_3') \xrightarrow{\mathsf{PBox}} (y_2', y_0', y_3', y_1') \equiv (y_0, y_1, y_2, y_3).\]

Theo phân tích tuyến tính ở trên ta tập trung vào phần \(\mathsf{SBox}\), như vậy

\[\bm{y}'[0, 1, 2, 3] = \bm{x}'[1].\]

Từ PBox suy ra \(y_0 = y_2'\), \(y_1 = y_0'\), \(y_2 = y_3'\) và \(y_3 = y_1'\), nên suy ra

\[\bm{y}'[0, 1, 2, 3] = \bm{y}[0, 1, 2, 3].\]

Điều này có vẻ khá rõ ràng vì tuyến tính \(y_0 \oplus y_1 \oplus y_2 \oplus y_3\) có mặt ở mọi bit nên \(\bm{y}'\) hay \(\bm{y}\) đều như nhau. Tuy nhiên nếu trong các trường hợp tuyến tính không có đủ tất cả bit là \(1\) như \(\bm{b} \neq 15\) thì chúng ta cần chú ý sự biến đổi của PBox.

Tiếp theo, do \(\bm{x}'[1] = x_1' = x_3 \oplus k_1\) nên có thể suy ra quan hệ tuyến tính giữa đầu vào \(\bm{x}\) và \(\bm{y}\) là

\[\bm{y}[0, 1, 2, 3] = \bm{x}[3] \oplus \bm{k}[1].\]

2.1.3. Known-plaintext

Linear attack là một dạng known-plaintext, trong đó chúng ta tận dụng các xác suất ở trên.

2.1.3.1. Phụ thuộc tuyến tính giữa các vòng

Gọi \(P = (L_0, R_0)\) là plaintext ban đầu với \(L_0\) và \(R_0\) là hai nửa trái phải.

Ở vòng 1 ta có

\[L_1 = R_0, \ R_1 = L_0 \oplus F(R_0, K_1),\]

suy ra

(2.14)\[F(R_0, K_1) = R_1[0, 1, 2, 3] \oplus L_0[0, 1, 2, 3] = R_0[3] \oplus K_1[1]\]

với xác suất \(14 / 64\). Ngược lại ta có

(2.15)\[F(R_0, K_1) = R_1[0, 1, 2, 3] \oplus L_0[0, 1, 2, 3] = R_0[3] \oplus K_1[1] \oplus 1\]

với xác suất \(1 - 14 / 64\).

Ở vòng 2 ta có

\[L_2 = R_1, \ R_2 = L_1 \oplus F(R_1, K_2).\]

Ở vòng 3 ta có

\[L_3 = R_2, \ R_3 = L_2 \oplus F(R_2, K_3),\]

suy ra

(2.16)\[F(R_2, K_3) = R_3[0, 1, 2, 3] \oplus L_2[0, 1, 2, 3] = R_2[3] \oplus K_3[1]\]

với xác suất \(14 / 64\). Tương tự ta cũng có

(2.17)\[F(R_2, K_3) = R_3[0, 1, 2, 3] \oplus L_2[0, 1, 2, 3] = R_2[3] \oplus K_3[1] \oplus 1\]

với xác suất \(1 - 14 / 64\).

Ta lại có \(L_2 = R_1\), kết hợp thêm vòng 1 ta có phương trình

\[\begin{split}F(R_2, K_3) & = R_3[0, 1, 2, 3] \oplus R_1[0, 1, 2, 3] \\ & = R_3[0, 1, 2, 3] \oplus L_0[0, 1, 2, 3] \oplus R_0[3] \oplus K_1[1] \\ & = R_2[3] \oplus K_3[1] = L_3[3] \oplus K_3[1],\end{split}\]

tương đương với

\[K_1[1] \oplus K_3[1] = R_3[0, 1, 2, 3] \oplus L_0[0, 1, 2, 3,] \oplus R_0[3] \oplus L_3[3].\]

Phương trình xảy ra:

• với xác suất \((14 / 64)^2\) khi là xảy ra hai phương trình (2.14) và (2.16);

• với xác suất \((1 - 14 / 64)^2\) khi xảy ra hai phương trình (2.15) và (2.17).

Như vậy tổng xác suất là \((14 / 64)^2 + (1 - 14 / 64)^2\) xấp xỉ \(0,66\), khoảng \(2/3\).

2.1.3.2. Tính toán khóa con

Giả sử khóa ban đầu gồm \(8\) bit là

\[KL_0 = (k^{(0)}_0, k^{(0)}_1, k^{(0)}_2, k^{(0)}_3), \ KR_0 = (k^{(0)}_4, k^{(0)}_5, k^{(0)}_6, k^{(0)}_7).\]

Dịch vòng trái \(1\) bit \(KL_0\) và \(KR_0\) ta được \(KL_1\) và \(KR_1\) lần lượt là

\[\begin{split}KL_0 = (k^{(0)}_0, k^{(0)}_1, k^{(0)}_2, k^{(0)}_3) \xrightarrow{\ll 1} KL_1 = (k^{(0)}_1, k^{(0)}_2, k^{(0)}_3, k^{(0)}_0) = (k^{(1)}_0, k^{(1)}_1, k^{(1)}_2, k^{(1)}_3) \\ KR_0 = (k^{(0)}_4, k^{(0)}_5, k^{(0)}_6, k^{(0)}_7) \xrightarrow{\ll 1} KR_1 = (k^{(0)}_5, k^{(0)}_6, k^{(0)}_7, k^{(0)}_4) = (k^{(1)}_4, k^{(1)}_5, k^{(1)}_6, k^{(1)}_7)\end{split}\]

nên suy ra

\[K_1 = (k^{(1)}_5, k^{(1)}_1, k^{(1)}_3, k^{(1)}_2, k^{(1)}_7, k^{(1)}_0).\]

Ở đây, \(K_1[1] = k^{(1)}_1 = k^{(0)}_2\).

Thực hiện tiếp quá trình này sẽ dẫn chúng ta tới \(K_3[1] = k^{(0)}_1\).

Như vậy chúng ta có một mối phụ thuộc giữa hai bit khóa ban đầu \(k^{(0)}_1\) và \(k^{(0)}_2\).

Giả sử ta phá mã known-plaintext với \(100\) cặp plaintext-ciphertext và có được kết quả sau của biểu thức

\[R_3[0, 1, 2, 3] \oplus L_0[0, 1, 2, 3,] \oplus R_0[3] \oplus L_3[3]\]

bằng \(1\) ở \(66\) lần và bằng \(0\) ở \(34\) lần. Như vậy theo phân tích xác suất ở phần phụ thuộc tuyến tính ở trên có thể kết luận \(k^{(0)}_1 \oplus k^{(0)}_2 = 1\). Điều này cho chúng ta hai trường hợp về hai bit của khóa, và nếu ta vét cạn \(6\) bits còn lại thì tổng cộng cần \(2 \cdot 2^6 = 128\) trường hợp. Như vậy chúng ta không phải vét cạn \(8\) bits, tốn \(2^8 = 256\) trường hợp. Hiện tại chúng ta chỉ mới xét một liên hệ giữa \(k^{(0)}_1\) và \(k^{(0)}_2\) nên độ phức tạp chỉ giảm một nửa. Nếu xét thêm các liên hệ khác thì sẽ có thể giảm thêm.

solve.py

# solve.py

from tinydes import encrypt_block, SBox
from functools import reduce
import random

random.seed(4)

secret_key = [1, 1, 0, 1, 0, 0, 1, 0]
count = 0
plaintext = [random.randint(0, 1) for __ in range(8)]
ciphertext = encrypt_block(plaintext, secret_key)

for _ in range(100):
    pt = [random.randint(0, 1) for __ in range(8)]
    ct = encrypt_block(pt, secret_key)
    L0, R0 = pt[:4], pt[4:]
    L3, R3 = ct[:4], ct[4:]
    S = reduce(lambda x, y: x ^ y, R3) ^ reduce(lambda x, y: x ^ y, L0) ^ R0[3] ^ L3[3]
    if S == 1:
        count += 1

if count > 100 - count:
    for k1 in range(2):
        k2 = k1 ^ 1
        for k0 in range(2):         # Bruteforce k_0
            for k in range(2**5):   # Bruteforce k_3 to k_7
                K = [k0, k1, k2] + list(map(int, f"{k:05b}"))
                if encrypt_block(plaintext, K) == ciphertext:
                    print(f"Found key: {K}")