Chuẩn mã DỮ liệU

Khi DES được đề xuất như một chuẩn mật mã, đã có rất nhiều ý kiến phê phán. Một lý do phản đối DES có liên quan đến các hộp S. Mọi tính toán liên quan đến DES ngoại trừ các hộp S đều tuyến tính, tức việc tính phép hoặc loại trừ của hai đầu ra cũng giống như phép hoặc loại trừ của hai đầu vào rồi tính tóan đầu ra. Các hộp S - chứa đựng thành phần phi tuyến của hệ mật là yếu tố quan trong nhất đối với độ mật của hệ thống( Ta đã thấy trong chương 1 là các hệ mật tuyến tính - chẳng hạn như Hill - có thể dễ dàng bị mã thám khi bị tấn công bằng bản rõ đã biết). Tuy nhiên tiêu chuẩn xây dựng các hộp S không được biết đầy đủ. Một số người đã gợi ý là các hộp S phải chứa các "cửa sập" được dấu kín, cho phép Cục An ninh Quốc gia Mỹ (NSA) giải mã được các thông báo nhưng vẫn giữ được mức độ an toàn của DES. Dĩ nhiên ta không thể bác bỏ được khẳng định này, tuy nhiên không có một chứng cớ nào được đưa ra để chứng tỏ rằng trong thực tế có các cửa sập như vậy.

Năm 1976 NSA đã khẳng định rằng, các tính chất sau của hộp S là tiêu chuẩn thiết kế:

P₀ Mỗi hàng trong mỗi hộp S là một hoán vị của các số nguyên 0, 1, . . . , 15.

P₁ Không một hộp S nào là một hàm Affine hoặc tuyến tính các đầu vào của nó.

P₂ Việc thay đổi một bít vào của S phải tạo nên sự thay đổi ít nhất là hai bít ra.

P₃ Đối với hộp S bất kì và với đầu vào x bất kì S(x) và S(x  001100) phải khác nhau tối thiểu là hai bít ( trong đó x là xâu bít độ dài 6 ).

Hai tính chất khác nhau sau đây của các hộp S có thể coi là được rút ra từ tiêu chuẩn thiết kế của NSA.

P₄ Với hộp S bất kì, đầu vào x bất kì và với e, f {0,1}: S(x) S(x  11ef00).

P5 Với hộp S bất kì , nếu cố định một bít vào và xem xét giá trị của một bít đầu ra cố định thì các mẫu vào để bít ra này bằng 0 sẽ xấp xỉ bằng số mẫu ra để bít đó bằng 1.( Chú ý rằng, nếu cố định giá trị bít vào thứ nhất hoặc bít vào thứ 6 thì có 16 mẫu vào làm cho một bít ra cụ thể bằng 0 và có 16 mẫu vào làm cho bít này bằng 1. Với các bít vào từ bít thứ hai đến bít thứ 5 thì điều này không còn đúng nữa. Tuy nhiên phân bố kết quả vẫn gần với phân bố đều. Chính xác hơn, với một hộp S bất kì, nếu ta cố định giá trị của một bít vào bất kì thì số mẫu vào làm cho một bít ra cố định nào đó có giá trị 0 (hoặc 1) luôn nằm trong khoảng từ 13 đến 19).

4. 
   DES TRONG THỰC TẾ.
   

Mặc dù việc mô tả DES khá dài dòng song người ta có thể thực hiện DES rất hữa hiệu bằng cả phần cứng lẫn phần mềm. Các phép toán duy nhất cần được thực hiện là phép hoặc loại trừ các xâu bít. Hàm mở rộng E, các hộp S, các hoán vị IP và P và việc tính toán các giá tri K₁,.. . ,K₁₆ đều có thể thực hiện được cùng lúc bằng tra bảng ( trong phần mền ) hoặc bằng cách nối cứng chúng thành một mạch.

1. 
   Các chế độ hoạt động của DES.
   

Trong các chế độ OFB và CFB dòng khoá được tạo ra sẽ được cộng mod 2 với bản rõ (tức là nó hoạt động như một hệ mã dòng, xem phần 1.1.7). OFB thực sự là một hệ mã dòng đồng bộ: dòng khoá được tạo bởi việc mã lặp véc tơ khởi tạo 64 bít (véc tơ IV). Ta xác định z₀ =IV và rồi tính dòng khoá z₁z₂ . . . theo quy tắc z_i = e_K(z_i-1), i1. Dãy bản rõ x₁x₂ . . . sau đó sẽ được mã hoá bằng cách tính y_i = x_i  z_i,i 1.

Cũng còn một số biến tấu của OFB và CFB được gọi là các chế độ phản hồi K bít (1 < K < 64 ). Ở đây ta đã mô tả các chế độ phản hồi 64 bít. Các chế độ phản hồi 1 bít và 8 bít thường được dùng trong thực tế cho phép mã hoá đồng thời 1 bit (hoặc byte) số liệu.

Trong phần này sẽ mô tả phép tối ưu hoá thời gian - bô nhớ khá lý thú khi phá DES bằng tấn công bản rõ chọn lọc. Ta nhớ lại rằng, trong phép tấn công bản rõ chọn lọc, Oscar đã thu được cặp rõ - mã được tạo bởi khoá K (chưa biết). Bởi vậy, Oscar có x và y, trong đó y = e_K(x) và anh ta muốn xác định được K.

Sau đó Oscar xây dựng một bảng các cặp T = (X(i,t), X(i,0) được sắp xếp theo toạ độ đầu của chúng( tức là chỉ lưu giữ cột đầu và cột cuối của X).

Sau khi thu được bản mã y ( là bản mã của bản rõ x đã chọn). Oscar cần phải xác định K và anh ta sẽ xác định được nếu K nằm trong t cột đầu của bảng X, tuy nhiên anh ta chỉ làm điều này bằng cách chỉ nhìn vào bảng T.
Giả sử rằng K = X(i,t-j) với j nào đó, 1  j  t ( tức giả sử rằng K nằm ở t cột đầu tiên của X). Khi đó rõ ràng là g^j(K) = x(i,t), trong đó g^j kí hiệu hàm nhận được bằng cách lặp g một số lần bằng j. Bây giờ ta thấy rằng:
g^j(K) = g^j-1(g(K))

= g^j-1(R(e_K(x)))

= g^j-1(R(y))
G
iả sử tính ỵ_j,1  j  t, từ quan hệ truy toán

R(y) nếu j = 1

y_i =

g(ỵ_j-1) nếu 2  j  t

Bằng cách phân tích xác suất thành công của thuật toán, có thể chứng tỏ rằng nếu mt²  N = 2⁵⁶ thì xác suất để K = X(i,t-j) với i, j nào đó sẽ vào khoảng 0,8môi trường/N. Thừa số 0,8 tính theo điều kiện không phải tất cả cácX(i,t) đều phân biệt . Điều này gợi ý cho ta nên lấy m  t  N^1/3 và xây dựng khoảng N^1/3 bảng, mỗi bảng dùng một hàm rút gọn R khác nhau. Nếu thực hiện đươc điều này thì yêu cầu về bộ nhớ là 112N^1/3 bít ( vì ta cần lưu trữ 2N^2/3 số nguyên, mỗi số có 56 bít). Thời gian tiền tính toán dễ dàng thấy là cỡ O(N).

Việc phân tích thời gian chạy của thuật toán có khó hơn hơn một chút: Trước hết ta thấy rằng, bước 3 có thể chạy trong một thời gian không đổi (sử dụng phép mã hash) hoặc trong trường hợp xấu nhất, bước 3 có thể chạy với thời gian O(logm) khi dùng phép tmf kiếm nhị phân. Nếu bước 3 không thoả mãn (tức là phép tìm kiếm không thành công) thì thời gian chạy là O(N^2/3). Các phân tích chi tiết hơn chứng tỏ rằng, ngay cả khi tính cả thời gian chạy của các bước 4 và5 thì thời gian chạy trung bình chỉ tăng một lương là hằng số.

6. 
   THÁM MÃ VI SAI (DC).
   

Phương pháp DC do Biham và Shamir đưa ra là một phương pháp tấn công DES rất nổi tiếng. Đây là một phép tấn công với bản rõ chọn lọc. Mặc dù phương pháp này không cho một phương pháp thực tế để phá DES 16 vòng thông dụng, nhưng nó có thể thực hiện thành công trong việc phá DES có số vòng mã hoá ít hơn. Chẳng hạn DES 8 vòng có thể phá được trong vòng vài phút trên một máy tính cá nhân nhỏ.

Giả sử xét hộp S đầu tiên S₁ và XOR vào 110100, khi đó:

(110100) = {(000000,110100), (000001,110100), . . . ,(111111,110100)}

Với mỗi cặp được sắp trong tập(110100) ta tính XOR ra của S₁. Ví dụ S₁(000000) = E₁₆ = 1110 và S₁(110100) = 9₁₆ = 1001, bởi vậy XOR đối với cặp (000000,110100) là 0111.

0000	0001	0010	0011	0100	0101	0110	0111
0	8	16	6	2	0	0	12

1000	1001	1010	1011	1100	1101	1110	1111
6	0	0	0	0	8	0	6

Trong ví dụ 3.1 chỉ có 8 trong 16 XOR ra có thể xuất hiện trên thực tế. Ví dụ cụ thể này có phân bố rất không đều. Nói chung nếu ta cố định một hộp S là S_j và một XOR vào B_j' thì trung bình có khoảng 75-80% các XOR ra là có thể xuất hiện.

Với mỗi hộp trong 8 hộp S có 64 XOR và có thể. Bởi vậy có thể tính được tất cả 512 phân bố và dễ dàng dùng máy tính để lập bảng các phân bố này.

Cần nhớ lại rằng, đầu vào của các hộp S ở vong thứ i là B = E J, trong đó E = E(R_i-1) là một hàm mở rộng của R_i-1 và J = K_i là các bít khoá của vòng thứ i. Bây giờ số XOR vào (cho tất cả 8 hộp) có thể được tính như sau:

B  B^* = (E  J)  (E^*  J)

= E  E^*

Có thể thấy môt điều rất quan trọng là XOR vao không phụ thuộc vào các bít khoá J ( tuy nhiên chắc chắn XOR ra sẽ phụ thuộc vào các bít khóa này.

Các XOR ra	Các xâu vào có thể
0000
0001	000011,001111,011110,011111, 101010,101011,110111,111011
0010	000100,000101,001110,010001, 010010,010100,011010,011011, 100000,100101,010110,101110, 101111,110000,110001,111010
0011	000001,000010,010101,100001, 110101,110110
0100	010011,100111
0101
0110
0111	000000,001000,001101,010111 011000,011101,100011,101001 101100,110100,111001,111100
1000	001001,001100,011001,101101 111000,111101
1001
1010
1011
1100
1101	000110,010000,010110,011100 100010,100100,101000,110010
1110
1111	000111,001010,001011,001100 111110,111111