Vũ Đức Mạnh - K19 HTTT - Mã HV: 12025057

1

MỤC LỤC
Nội dung Trang
I. Tổng quan về thám mã vi sai: 2
1. Khái niệm 2
2. Lịch sử 2
3. Quy trình thám mã vi sai 3
II. Chuẩn mã hóa dữ liệu (Data Encryption Standard - DES) 4
1. Đặc điểm, mô hình hoạt động của DES 4
a) Mô hình cơ bản 4
b) Cấu trúc Hàm F 5
c) Xác định khóa chính, khóa vòng (subkey) 5
2. Độ an toàn của DES 6
IV. Cơ sở khoa học của thám mã vi sai đối với DES 6
1. Phân tích các điểm yếu của hàm F (các hộp S) 6
2. Có thể bỏ qua khóa k trong giai đoạn tính đầu vào cho hộp S 7
3. Dựa trên các bước thực hiện dò tìm khóa cơ bản 7
V. Ví dụ về tấn công thám mã vi sai đối với DES một vòng 9
1. Tiền tính toán 9
2. Dò tìm khóa 10
V. Kết luận và hướng phát triển tiếp theo 13
Tài liệu tham khảo 16 Vũ Đức Mạnh - K19 HTTT - Mã HV: 12025057

2


Cho đến năm 1990 những đồn đại, nghi nghờ về những hộp S “yếu” mới được
làm rõ. Trong năm đó, Eli Biham và Adi Shamir công bố bài báo về kỹ thuật thám mã
mới: “Thám mã vi sai”. Từ đó, NSA đã thay đổi các hộp S để tăng cường sức mạnh để
DES chống lại kiểu tấn công mới này.

Vũ Đức Mạnh - K19 HTTT - Mã HV: 12025057

3

3. Quy trình thám mã vi sai
Khi có được khác nhau của các cặp bản rõ cần thiết, người tấn công thực hiện
tính toán giá trị khác nhau giữa các cặp bản mã tương ứng nhằm khám phá ra được
các mẫu thống kê quy luật trong sự phân bổ của chúng. Cặp kết quả giá trị khác nhau
(vào - ra) được gọi là vi sai (differential).
Các mẫu thống kê có được từ sự phân tích là phụ thuộc vào đặc tính tự nhiên
của các hộp S. Người tấn công phân tích các vi sai (X, Y) của mỗi hộp S, trong
đó:
X = X
1
⊕
⊕⊕
⊕ X
2
Y = Y
1
⊕
⊕⊕
⊕ Y
2
= S(X

Đối với bất kỳ hệ mã hóa nào, để việc thám mã thành công thì giá trị khác nhau đầu
vào cần phải được lựa chọn cẩn thận. Đồng thời, việc phân tích bên trong của thuật
toán là rất quan trọng và phải được thực hiện đồng thời. Phương pháp chuẩn chính là
theo dõi một “đường dẫn” vi sai với xác suất xuất hiện cao thông qua các giai đoạn
của việc mã hóa, được gọi là đặc tính vi sai.

Vũ Đức Mạnh - K19 HTTT - Mã HV: 12025057

4

II. Chuẩn mã hóa dữ liệu (Data Encryption Standard – DES)
1. Đặc điểm, mô hình hoạt động của DES
a) Mô hình cơ bản
DES là hệ mật mã khối 64 bit, với 64 bit vào bản rõ và tạo ra 64 bit bản mã
thông qua một chuỗi phép hoán vị và hàm Feistel (hàm F):
64 bit đầu vào trước hết được hoán vị IP và chia thành 2 nửa 32 bit. Trong mỗi vòng
của DES, một nửa được giữ nguyên trong khi nửa còn lại được chạy qua hàm F. Đầu
ra của hàm F tiếp tục được XOR với nửa còn lại.
Hai nửa được hoán vị cho nhau, và bắt đầu lặp lại vòng tiếp theo.

Hình 1: Cấu trúc hoạt động của DES
Vũ Đức Mạnh - K19 HTTT - Mã HV: 12025057

5

b) Cấu trúc Hàm F:
Trong hàm F, 32 bit đầu vào được mở rộng thành 48 bit bởi hàm mở rộng E. 48
bit này sau đó được XOR với một khóa con được dẫn xuất từ khóa chính của DES.
Kết quả 48 bit sau khi XOR với khóa con được chạy qua 8 hộp S (S-Boxes) làm
giảm 48 bit xuống còn 32 bit. Cuối cùng, 32 bit được chuyển qua hàm hoán vị P.

hổng” nhất định. Trong đó, hộp S
1
và hộp S
5
được coi là “yếu” nhất, hộp S
7
được coi
là an toàn nhất.
Độ an toàn của Hộp S-7: với bất kỳ giá trị khác nhau đầu vào 6 bít (


I
) nào
khác không nào cho trước,

sẽ không nhiều hơn 8 trong số 32 cặp đầu vào với 


I
cho
cùng kết quả giá trị khác nhau đầu ra 


O
. Hay nói cách khác, nó cho tỷ lệ xác suất vi
sai ≤ 1/4. Bởi vậy, xác suất cao nhất (cận trên) của toàn bộ cặp bản rõ có cùng giá trị
khác nhau đầu vào cho trước (


I

⊕
⊕⊕
⊕ k) ⊕
⊕⊕
⊕ (m
2
⊕
⊕⊕
⊕ k) = m
1
⊕
⊕⊕
⊕ k ⊕
⊕⊕
⊕ m
2
⊕
⊕⊕
⊕ k
= m
1
⊕
⊕⊕
⊕ m
2
⊕
⊕⊕
⊕ k ⊕
⊕⊕
⊕ k

đều.

Bảng 1: Một phần của Bảng phân bố cặp vi sai Vào – Ra
(cặp XOR) của hộp S
1

Định nghĩa 1: Bảng 1 trên đây được gọi là Bảng phân bổ các cặp XOR. Mỗi tiêu đề
dòng trình diễn giá trị khác nhau đầu vào (XOR vào). Mỗi tiêu đề cột trình diễn giá trị
Vũ Đức Mạnh - K19 HTTT - Mã HV: 12025057

8

khác nhau đầu ra (XOR ra). Các phần tử trong bảng thể hiện số lượng “bộ” có thể với
các XOR vào và các XOR ra tương ứng theo dòng và cột.
(Bảng 1 chỉ là một phần của Bảng phân bố vi sai, vì thực tế Bảng phân bố này có 64
đầu vào, tức là có 64 dòng (input XOR), từ 00
x
đến 3F
x
).
Định nghĩa 2: Cho S’
iI
là giá trị khác nhau đầu vào (XOR vào) và S’
iO
là giá trị khác
nhau đầu ra (XOR ra) của một hộp S
i
nào đó. Chúng ta nói S’
iI
có thể tạo ra S’

) = S
iO
⊕
⊕⊕
⊕ S
*
iO

Từ đó, chúng ta có thể viết S’
iI
 S’
iO
. Hay nói cách khác, giá trị khác nhau đầu vào
S’
iI
dẫn đến giá trị khác nhau đầu ra S’
iO.

Định nghĩa 3: Cho một hộp S (S
i
), định nghĩa tập đầu vào (IN
i
) S
iI
, S
*
iI
sao cho S’
iI


) = | IN
i
(S’
iI
S’
iO
) |
Xác suất để S’
iI
 S’
iO
, là như sau:
P (S’
iI
 S’
iO
) = ( N (S’
iI
 S’
iO
) ) / 64
* Dò tìm khóa:
Dựa vào sự phân bố vi sai không đều của các hộp S: lựa chọn các cặp vi sai
xuất hiện với xác suất cao (để làm nổi bật vai trò khóa k
i
) để xây dựng các bảng tham
chiếu tiếp theo.
Xác định khóa: Giới hạn, cô lập không gian khóa, xác định các bit khóa, vùng
khóa và xác định khóa duy nhất.
* Ví dụ về tham chiếu Bảng 1: Xét đầu vào XOR S’

x
, 4
x
, 7
x
, và 8
x
. Vì vậy, chúng ta có thể viết:
C
x

ե
0
x
, C
x

ե
1
x
, C
x

ե
2
x
, C
x
 3
x


Trong phần này sẽ trình diễn một ví dụ về tấn công DES giảm xuống 1 vòng.
Chúng ta sẽ nhận thấy sự phức tạp của tập các thủ tục xử lý toàn bộ các tính toán liên
quan. Đồng thời trong ví dụ này cũng giảm hệ DES xuống còn 1 hộp S - hộp S
1
. Đối
với việc dò tìm 42 bít khóa dựa vào 7 hộp S còn lại sẽ được thực hiện với thuật toán
tương tự. Tuy nhiên, độ phức tạp khi dò tìm các bít khóa tương ứng với mỗi hộp S là
khác nhau do đặc điểm “mạnh” hay “yếu” của từng hộp S đó.
Việc đơn giản hóa bài toán như vậy chỉ với mục đích thể hiện ý tưởng, phương
pháp thám mã vi sai đối với DES. Tất nhiên khi tăng số vòng của DES lên n vòng (1 <
n < 16) và cuối cùng đối với DES đầy đủ 16 vòng thì thuật toán thám mã cần phải
được thay đổi nhiều đồng thời độ phức tạp của nó cũng tăng lên theo cấp lũy thừa.
1. Tiền tính toán: (Các giá trị được quy về hệ Thập lục phân (HexaDecimal).
 Trong ví dụ này các ký hiệu được hiểu như sau:
- S
1E
, S
*
1E
: cặp giá trị đầu vào Hộp S
1
(6 bit) trước khi XOR với 6 bit của khóa
k.
- S
1I
, S
*
1I
: cặp giá trị đầu vào Hộp S

x.

Thực hiện lần vết các giá trị kết quả của hàm F như sau:
S
1I
= S
1E
⊕
⊕⊕
⊕
S
1k

= 08
x
⊕
⊕⊕
⊕
1A
x

S
*
1I
= S
*
1E
⊕
⊕⊕
⊕

)= A
x

Bởi vậy, S’
1O
= S
1O
⊕ S*
1O

Bỏ qua khóa S
1k
, tính S’
1E

= S’
Tra Bảng 1 với cặp (XOR v
ào, XOR ra) = (0C
2. Dò tìm khóa:
 Bước 1: T
ừ Bảng 1, xét:
đầu vào là 0C
x
và các giá tr
đầu ra là 0D
x
, ta có:


S
*
1O
= S
1
(S
*
1I
)= S
1
(1E
x
)= 7
x = 0D
x
(XOR ra)
= S’
1I
= (S
1E

. Vậy t
a có các c
, 0D
x
), (12
x
, 1E
x
), 36
x
, 3A
x
)}
1E
) = (08
x
, 04
x
), tính các “khóa có thể” t
heo công th
ảng 3.

Các c
ặ
để
vi sai

- : 12025057
10
ới giá trị khác nhau

)
Từ Bảng 1, xét: S’
1E
= S’
1I
= 0C
x

S’
1I
 S’
1O
<=> 0C
x
 0A
x
 lập Bảng 2, Ta có các cặp đầu vào:
(S
1I
, S*
1I
) ∈ {(22
x
, 2E
x
), (30
x
, 3C
x
), 34

,
đầu vào (S
1E
, S
*
1E
) = (38
x
, 34
x
)
 Bước 3: Từ Bảng 1, xét: S’
1E
= S’
1I
= 10
x
. Chọn giá trị khác nhau đầu vào
(10
x
) và lập Bảng 5.
Cô l
ập vùng khóa  Bước 4: Tham chi
ếu B
S’
1O
<=> 10

ếu Bảng 5, với giá trị
khác nhau đ
ầu ra (A
), Ta có các c
ặp đầu vào:
x
), (21
x
, 31
x
), (2F, 3F)}.
) = (3B
x
, 2B
x
), tính các “khóa có thể” t
heo công th
Các khóa có th
ể đối với cặp vi sai 10x




Ax,
đ
ầu vào (S
1E
, S*
1E
) = (3Bx, 2Bx)

ầu ra là 0Dx
Vũ Đức Mạnh - K19 HTTT - Mã HV: 12025057

13

Như vậy, từ hộp S
1
và

thực hiện tiền tính toán dựa trên hộp S
1
và qua 5 bước xử
lý cùng với 2 cặp bản rõ có lựa chọn (08
x
, 04
x
) và (3B
x
, 2B
x
), chúng ta có thể xác định
được giá trị khóa là “1A” (ở dạng thập lục phân) tương đương 6 bít khóa (011010) ở
dạng nhị phân sử dụng cho hộp S
1
.
Để có thể dò tìm được đầy đủ 48 bít khóa (khóa con) cần sử dụng đủ 8 hộp S (từ S
1

đến S
8

Thám mã vi sai là phương pháp tấn công đầu tiên đối với DES để có thể tìm
thấy khóa nhanh hơn là tìm kiếm vét cạn không gian khóa. Theo lý thuyết, đây là một
kiểu tấn công có tính khả thi. Nhưng theo Bảng 7 dưới đây, tấn công thám mã vi sai là
dường như khó đạt hiệu quả trên thực tế.
Vũ Đức Mạnh - K19 HTTT - Mã HV: 12025057

14 Bảng 7: Tổng hợp về khả năng tấn công thám mã vi sai đối với DES

Đối với phiên bản DES đầy đủ 16 vòng, chúng ta cần có 2
47
bản mã. Điều này
tương đương với xấp xỉ 280 tỷ tỷ phép mã hóa cần phải thực hiện.
Lý do cần rất nhiều cặp bản rõ/bản mã như vậy là bởi vì DES đã được thiết kế
để chống tấn công thám mã vi sai kể từ khi Biham và Shamir công bố hai bài báo về
thám mã vi sai (năm 1990). Tương tự, thì các hệ mật mã mới, xuất hiện sau DES cũng
đều đã được thiết kế để chống lại dạng tấn công này.
Đối với các hệ mật mã được thiết kế cùng với thời kỳ đầu tiên của DES như là
LOKI, FEAL, FEAL-N/NX, chưa được thiết kế lại là rất dễ bị tấn công thám mã vi
sai.
Cải tiến thành công của DES:
Kể từ khi thám mã vi sai được biết đến rộng rãi, nó trở thành một sự quan tâm
đáng kể của những người thiết kế hệ mật mã. Những hệ mã hóa mới cần đều phải
được chứng minh thuật toán có khả năng chống lại kiểu tấn công này. Và đã có nhiều
hệ mã hóa, trong đó có Chuẩn mã hóa tiến bộ (Advanced Encryption Standard – AES)
Vũ Đức Mạnh - K19 HTTT - Mã HV: 12025057

15


 Differential Cryptanalysis Data Encryption Standard – Alan Silvester,
Năm 2004.
 Differential Cryptanalysis of DES-like Cryptosystems – E. Biham và A.
Shamir (Tạp chí Mật mã, Tập 4, số 1, Năm 1990).