Phá mã vi sai (Differential Cryptanalysis)

Trong chương 3, chúng ta đã tìm hiểu hiệu ứng lan truyền của mã DES, dưới tác động của các S-box và khóa K, chỉ cần thay đổi một bít trong bản rõ hay trong khóa sẽ dẫn đến sự thay đổi của nhiều bít trong các giá trị trung gian LiRi và trong bản mã. Do đó người phá mã khó phân tích được mối liên quan giữa bản rõ, bản mã và khóa – cho dù phá mã trong trường hợp known-plaintext hay chosen-plaintext.

Tuy nhiên, nếu xét dưới góc độ giá trị vi sai (differential) thì tác dụng lan truyền của khóa K và hàm S-box lại mất hiệu lực. Ta định nghĩa khái niệm vi sai như sau:

Giả sử hai giá trị X1 và X2 cùng số bít, thì vi sai giữa X1 và X2 là: X = X1  X2

Tính chất của giá trị vi sai qua các phép biến đổi:

1) Phép XOR với giá trị khóa:

Cho 

 thì:  

như vậy input XOR bằng output XOR, điều đó có nghĩa là giá trị vi sai không chịu tác động của khóa. Đây là yếu tố quan trọng của phá mã vi sai.

2) Phép P-box:

Cho -

-

Li-1 Ri-1

Ki

Li Ri

Expand

S-box

P-box X

Y

Z

122

thì:  - 

điều đó có nghĩa là nếu vi sai của đầu vào (input XOR) là cố định thì vi sai của đầu ra (output XOR) cũng cố định. Phép biến đổi P-box là tuyến tính, ứng với mỗi giá trị đầu vào có 1 giá trị đầu ra và ngược lại.

3) Phép Expand:

Cho

thì:  

tương tự như hàm P-box, trong hàm Expand, nếu input XOR là cố định thì output XOR cũng cố định. Hàm Expand cũng là phép biến đổi tuyến tính.

4) Phép S-box

Xét S-box của mã TinyDES (cũng là hộp S1 của mã DES) với 6 bít đầu vào và 4 bít đầu ra:

Cho -

-

Trong trường hợp này output XOR  không cố định và S-box không phải là phép biến đổi tuyến tính. Ví dụ, xét bảng dưới đây trong trường hợp input XOR là 000001:

X1 X2 X1  X2 Y1 Y2 Y1  Y2

000000 000001 000001 1110 0000 1110

001000 001001 000001 0010 1110 1100

100000 100001 000001 0100 1111 1011

… … … … … …

Ứng với mỗi giá trị của X1 thì có một X2 tương ứng để giá trị XOR là 000001.

Do đó bảng trên có 2⁶ = 64 dòng tương ứng với 64 cặp (X1, X2). Tương tự như vậy đối với các input XOR khác. Dù rằng ứng với cùng một input XOR thì các giá trị output XOR là khác nhau, nhưng nếu xét dưới góc độ thống kê thì vẫn tồn tại mối quan hệ giữa input XOR và output XOR, điều đó được thể hiện qua bảng sau:

123

Input XOR (6 bít)

Output XOR (4 bít)

0 1 2 3 4 5 6 7 8 9 A B C D E F

0 64

1 6 2 4 4 10 12 4 10 6 2 4

2 8 4 4 4 6 8 6 12 6 4 2

3 14 4 2 2 10 6 4 2 6 4 4 2 2 2

4 6 10 10 6 4 6 4 2 8 6 2

5 4 8 6 2 2 4 4 2 4 4 12 2 4 6

6 4 2 4 8 2 6 2 8 4 4 2 4 2 12

7 2 4 10 4 4 8 4 2 4 8 2 2 2 4 4

8 12 8 8 4 6 2 8 8 2 2 4

9 10 2 4 2 4 6 2 2 8 10 2 12

A 8 6 2 2 8 6 6 4 6 4 2 10

B 2 4 10 2 2 4 2 6 2 6 6 4 2 12

C 8 6 6 6 6 4 6 6 14 2

D 6 6 4 8 4 8 2 6 6 4 6 2 2

E 4 8 8 6 6 4 6 6 4 4 8

F 2 2 4 4 6 4 2 4 8 2 2 2 6 8 8

10 2 14 6 6 12 4 6 8 6

11 6 8 2 4 6 4 8 6 4 6 6 4

12 8 4 2 6 6 4 6 6 4 2 6 6 4

13 2 4 4 6 2 4 6 2 6 8 4 6 4 6

14 8 8 10 4 2 8 2 2 4 4 8 4

15 4 6 4 2 2 4 10 6 2 10 4 6 4

16 8 10 8 2 2 6 10 2 2 6 2 6

17 4 4 6 10 6 2 4 4 4 6 6 6 2

18 6 6 8 4 2 2 2 4 6 8 6 6 2 2

19 2 6 2 4 8 4 6 10 4 4 2 8 4

1A 6 4 4 6 6 6 6 22 2 4 4 6 8

1B 4 4 2 4 10 6 6 4 6 2 2 4 2 2 4 2

1C 10 10 6 6 12 6 4 2 4 4

1D 4 2 4 8 2 12 2 6 6 6 14

1E 2 6 14 2 6 4 10 8 2 2 6 2

1F 2 4 10 6 2 2 2 8 6 8 4 6 4

20 10 12 8 2 6 4 4 4 2 12

21 4 2 4 4 8 10 4 4 10 4 2 8

22 10 4 6 2 2 8 2 2 2 2 6 4 4 10

23 4 4 8 2 6 6 6 2 10 2 4 10

24 12 2 2 2 2 14 14 2 2 6 2 4

25 6 4 4 12 4 4 4 10 2 2 2 4 2 2 2

26 4 10 10 10 2 4 4 6 4 4 4 2

27 10 4 2 2 4 2 4 8 4 8 8 4 4

28 12 2 2 8 2 6 12 2 6 4 6 2

29 4 2 2 10 2 4 14 10 2 4 6 4

2A 4 2 4 6 2 8 2 2 14 2 6 2 6 2 2

2B 12 2 2 2 4 6 6 2 2 6 2 6 8 4

2C 4 2 2 4 2 10 4 2 2 4 8 8 4 2 6

2D 6 2 6 2 8 4 4 4 2 4 6 8 2 6

2E 6 6 2 2 2 4 6 4 6 2 12 2 6 4

2F 2 2 2 2 2 6 8 8 2 4 4 6 8 3 4 3

30 4 6 12 6 2 2 8 2 4 4 6 2 2 4

31 4 8 2 10 2 2 2 2 6 2 2 4 10 8

32 4 2 6 4 4 2 2 4 6 6 4 8 2 2 8

33 4 4 6 2 10 8 4 2 4 2 2 4 6 2 4

34 8 16 6 2 12 6 8 6

35 2 2 4 8 14 4 6 8 2 14

36 2 6 2 2 8 2 2 4 2 6 8 6 4 10

37 2 2 12 4 2 4 4 10 4 4 2 6 2 2 4

38 6 2 2 2 2 2 4 6 4 4 4 6 10 10

39 6 2 2 4 12 6 4 8 4 2 4 2 4 4

3A 6 4 6 4 6 8 6 2 2 6 2 2 6 4

3B 2 6 4 2 4 6 4 6 8 6 4 4 6 2

3C 10 4 12 4 2 6 4 12 4 4 2

3D 8 6 2 2 6 8 4 4 4 12 4 4

3E 4 8 2 2 2 4 4 14 4 2 2 8 4 4

3F 4 8 4 2 4 2 4 4 2 4 8 8 6 2 2

124

Trong bảng trên tổng của mỗi dòng là 64 (là số cặp X1, X2 ứng với input XOR tương ứng), tuy nhiên số 64 này không phân bố đều trên các output XOR. Ta có kết luận về giá trị vi sai của S-box này như sau:

- Nếu input XOR là 00 thì output XOR chắc chắn là 0.

- Nếu input XOR là 10 thì output XOR là 7 với xác suất 14/64. Bảng dưới liệt kê các cặp đầu vào và đầu ra tương ứng

X1  X2 = 10 Y1  Y2=7

X1 X2 Y1 Y2

08 18 2 5

09 19 E 9

0B 1B 2 5

23 33 C B

24 34 E 9

2C 3C 2 5

2D 3D 1 6

- Nếu input XOR là 34 thì output XOR là 2 với xác suất 16/64. Bảng dưới liệt kê các cặp đầu vào và đầu ra tương ứng

X1  X2 = 34 Y1  Y2=2

X1 X2 Y1 Y2

04 30 D F

05 31 7 5

0E 3A 8 A

11 25 A 8

12 26 A 8

14 20 6 4

1A 2E 9 B

1B 2F 5 7

Từ đó ta có kết luận sau về giá trị vi sai của hàm F trong TinyDES, với input XOR và output XOR của hàm F là 4 bít:

F = P-box(S-box(Expand( Ri-1) Ki))

- Nếu input XOR của F là 0:  output XOR của Expand là 0 (6 bít)  input XOR của S-box là 0 (khóa không ảnh hưởng đến vi sai)  input XOR của P-box (4 bít) chắn chắn là 0  output XOR của F chắn chắn là 0.

- Nếu input XOR của F là 3:  output XOR của Expand là 34  input XOR của P-box (4 bít) là 2 với xác suất 16/64  output XOR của F là 8 với xác suất 16/64 = 1/4.

- Nếu input XOR của F là 1:  output XOR của Expand là 10  input XOR của P-box (4 bít) là 7 với xác suất 14/64  output XOR của F là B với xác suất 14/64 = 7/32.

125 Như vậy, dù không biết giá trị của khóa K nhưng ta vẫn có thể tín được sự lan truyền của giá trị vi sai qua 3 vòng của TinyDES. Xét ví dụ sau:

Chọn và ̅ ̅ ̅ sao cho vi sai ̅ 83 (83: số thập lục phân).

Quá trình lan truyền vi sai qua các vòng TinyDES được thể hiện trong bảng bên dưới.

̅ ̅ ̅ ̅ ̅ 83 Xác suất

1

̅₁ ̅

̅ ̅ ̅ ̅ ̅ 3 1/4

2 1

̅₂ ̅₁

̅ ̅ ̅ ̅ ̅ 3 (1/4)×1

3 2

̅₃ ̅₂

̅ ̅ ̅

̅

̅ ̅ 38 (1/4)×(1/4)

Như vậy vi sai của bản mã là 38 với xác suất 1/16. Điều đó có nghĩa là trung bình trong 16 cặp bản rõ có vi sai là 83 thì sẽ tìm thấy 1 cặp có vi sai bản mã là 38.

Với 1 khóa K cụ thể nào đó, giả sử ta thực hiện chosen-plaintext cho 16 cặp (bản rõ, bản mã) và tìm thấy 1 cặp sau:

2 5 ̅ ̅ ̅ 8 ̅ ̅ ̅ (có vi sai bản rõ là 83 và vi sai bản mã là 38)

Như vậy, tại vòng thứ 3, input của hàm F trong hai trường hợp tương ứng là ̅ ̅ . Do đó output của hàm Expand trong 2 trường hợp là 2F và 1B.

Vì input XOR và output XOR của S-box trong vòng thứ 3 này là 34 và 2. Tra bảng, ta có các khóa K3 có thể có là:

X1  X2 = 34

K3 X1  X2 = 34

K3

X1=2F  K3 X2=1B  K3 X1=1B  K3 X2=2F  K3

04 30 2B 04 30 1F

05 31 2A 05 31 1E

0E 3A 21 0E 3A 15

11 25 3E 11 25 0A

12 26 3D 12 26 09

14 20 3B 14 20 0F

1A 2E 35 1A 2E 01

1B 2F 34 1B 2F 00

Tương tự, chọn và ̅ ̅ ̅ sao cho vi sai ̅ 1. Quá trình lan truyền vi sai qua các vòng TinyDES được thể hiện trong bảng bên dưới.

̅ ̅ ̅ ̅ ̅ 1 Xác suất

1

̅₁ ̅

̅ ̅ ̅ ̅ ̅ 1 7/32

2 1

̅₂ ̅₁

̅ ̅ ̅ ̅ ̅ 1 (7/32)×1

3 2

̅₃ ̅₂

̅ ̅ ̅

̅

̅ ̅ 1 (7/32)²  0.048

126

Như vậy vi sai của bản mã là 1B với xác suất 0.048. Điều đó có nghĩa là trung bình trong 21 cặp bản rõ có vi sai là B1 thì sẽ tìm thấy 1 cặp có vi sai bản mã là 1B.

Với 1 khóa K cụ thể nào đó, giả sử ta thực hiện chosen-plaintext cho 21 cặp (bản rõ, bản mã) và tìm thấy 1 cặp sau:

3 83 ̅ ̅ ̅ 8 ̅ ̅ ̅ 98 (có vi sai bản rõ là B1 và vi sai bản mã là 1B)

Tại vòng thứ 3, input của hàm F trong hai trường hợp tương ứng là 8 ̅ ̅ 9. Do đó output của hàm Expand trong 2 trường hợp là 01 và 11. Vì input XOR và output XOR của S-box trong vòng thứ 3 này là 10 và 7. Tra bảng, ta có các khóa K3 có thể có là:

X1  X2 = 10

K3 X1  X2 = 10

K3

X1=01  K3 X2=11  K3 X1=11  K3 X2=01  K3

08 18 09 08 18 19

09 19 08 09 19 18

0B 1B 0A 0B 1B 1A

23 33 22 23 33 32

24 34 25 24 34 35

2C 3C 2D 2C 3C 3D

2D 3D 2C 2D 3D 3C

Kết hợp 2 bảng, thì K3 phải là giá trị thuộc tập { 09, 0A, 35, 3D }. Gọi 8 bít của khóa K là k0k1k2k3k4k5k6k7 , thì 6 bít của K3 là k5k1k3k2k7k0. Như vậy với từng trường hợp của K3 chúng ta có thể thử các giá trị của k4 và k6. Ví dụ giả sử K3 là 09 (nhị phân 001001), như vậy khóa K có dạng 1001x0x0, và khóa K có 4 trường hợp: 10010000, 10010010, 10011000, 10011010. Lần lượt mã hóa bản rõ 2B với 4 trường hợp trên của khóa K, thì chỉ có trường hợp K = 1001.1010 cho ra bản rõ E5.

Như vậy thay vì vét cạn 256 trường hợp của khóa K, chúng ta chỉ cần thử 16+21= 37 cặp bản rõ-bản mã, sau đó thử thêm 16 trường hợp của khóa K thì tìm ra được giá trị chính xác của K. Điều này chứng tỏ phương pháp phá mã vi sai là có hiệu quả để phá mã TinyDES.

Trong tài liệu AN TOÀN VÀ BẢO MẬT THÔNG TIN (Trang 121-126)