Bây giờ ta muốn xác định 30 bít khoá trong J2, J5, J6, J7 và J8 như cách đã làm trong tấn công 3 vòng. Vấn đề ở đây là XOR được giả định cho vòng 6 chỉ đúng với xác suất 1/16. Bởi vậy 15/16 thời gian ta chỉ thu được các bít ngẫu nhiên không phải là các bít khoá có thể. Bằng một cách nào đó ta phải có khẳ năng xác định được các khoá đúng bằng các số liệu đã cho ( trong đó có 15/16 các số liệu sai). Điều này có vẻ không sáng sủa cho lắm, song rất may mắn là viễn cảnh của ta không tối tăm như vậy.
Định nghĩa 3.6.
Giả sử L0 L0* = L0' và R0 R0* = R0'. Ta nói rằng cặp bản rõ L0R0 và L0*R0* là cặp đúng ứng với một đặc trưng nếu LiLi* = Li' và RiRi* = Ri' với mọi i, 1 i n. Ngược lại, cặp này được xác định là cặp sai.
Hy vọng rằng khoảng 1/16 các cặp là đúng và các cặp còn lại là sai ứng với đặc trưng 3 vòng.
Chiến thuật của ta là tính Ej, Ej* và Cj' ( như đã mô tả ở trên ) sau đó xác định các testj(Ej, Ej*, Cj') vơi j = 2, 5, 6, 7, 8. Nếu bắt đầu bằng một cặp đúng thì các bít khoá đúng cho mỗi Jj sẽ nằm trong tập testj. Nếu cặp này sai thì giá trị của Cj' sẽ không đúng và giả định rằng mỗi tập testj sẽ chủ yếu là ngẫu nhiên có thể coi là có lý:
Có thể nhận ra một cặp sai theo phương pháp sau: Nếu | testj | = 0 với bất kì j {2, 5, 6, 7, 8} thì chắc chắn là ta có một cặp sai. Bây giờ , với một cặp sai cho trước, có thể thấy rằng xác suất để testj = 0 với giá trị j nhất định sẽ xấp xỉ bằng 1/5. Đây là một giả định hợp lý bởi vì Nj(Ej',Cj') = | testj | và như đã nói ở trên, xác suất để Nj(Ej',Cj') = 0 xấp xỉ bằng 1/5. Xác suất để tất cả 5 tập testj có lực lượng dương được ước lượng bằng 0,85 0,33. Bởi vậy xác suất để ít nhất một tập testj có lực lượng bằng 0 sẽ vào khoảng 0,67. Như vậy ta hy vọng loại bỏ được 2/3 số cặp sai bằng cách quan sát đơn giản này ( ta sẽ gọi là phép lọc ). Tỷ lệ các cặp đúng còn lại sau phép lọc xấp xỉ bằng (1/16)/(1/3) = (3/16).
Ví dụ 3.4.
Giả sử ta có cặp mã - rõ sau:
Nhận thấy rằng L0' = 4008000016 và R0' = 0400000016 . Các đầu vào và các đầu ra của các hộp S ở vòng 6 được tính như sau:
-
j
|
Ej
|
Ej*
|
Cj'
|
2
5
6
7
8
|
111100
111101
011010
101111
111110
|
010010
111100
000101
010110
101100
|
1101
0001
0010
1100
1101
|
Khi đó tập testj (2, 5, 6, 7, 8) là:
-
j
|
testj
|
2
|
14, 15, 26, 30, 32, 33, 48,52
|
5
|
|
6
|
7, 24, 36, 41, 54, 59
|
7
|
|
8
|
34, 35, 48, 59
|
Ta thấy tập test5 và test7 là các tập rỗng, bởi vậy cặp này là một cặp sai và sẽ bị loại bỏ bằng phép lọc.
Bây giờ, giả sử rằng ta có một cặp sao cho | testj | > 0, với j = 2, 5, 6, 7, 8, để nó còn tồn tại lại sau phép lọc ( tuy nhiên vẫn chưa biết cặp này đúng hay sai ). Ta nói rằng xâu bít J2 J5 J6 J7 J8 có độ dài 30 là xâu bít được gợi ý bởi cặp trên nếu Jj testj với j = 2,5,6,7,8. Số các xâu bít được gợi ý là:
Thông thường số các xâu bít được gợi ý có giá trị quá lớn ( ví dụ: > 80000).
Giả sử ta đã lập bảng tất cả các xâu bít được gợi ý thu được từ N cặp ( không bị loại bỏ bởi phép lọc). Với một cặp đúng, xâu bít đúng J2 J5 J6 J7 J8 sẽ là một xâu bít được gợi ý. Xâu bít đúng này sẽ xuất hiện vào khoảng 3N/16 lần. Các xâu bít không đúng thường xuất hiện ít hơn nhiều do chúng cơ bản là xuất hiện một cách ngẫu nhiên có 230 khả năng ( một số rất lớn).
Việc lập bảng tất cả các xâu bít được ôựi ý sẽ rất cồng kềnh, bởi vậy ta sẽ dùng một thuật toán yêu cầu ít thời gian và không gian ( bộ nhớ). Ta có thể mã tập testj bất kỳ bằng véc tơ Tj có độ dài 64, trong đó tạo độ thứ i của Tj được đặt về giá trị 1 ( với 0 i 63) nếu xâu bít độ dài 6 ( là biểu diễn nhị phân của i ) nằm trong tập testj . Trong trường hợp ngược lại, toạ độ thứ i được đặt về 0 ( giống như cách biểu diễn mảng bộ đếm đã dùng trong phép tấn công 3 vòng).
Với mỗi cặp còn lại ta xây dượng các véc tơ này như đã mô tả ở trên về ký hiệu chúng là Tji , j = 2,5,6,7,8, 1 i N. Với I {1,. . . ,N} ta nói rằng I là tập được phép nếu với mỗi j {2,5,6,7,8} có ít nhất một toạ độ bằng | I | trong véc tơ Tj (với j I).
Nếu cặp thứ i là một cặp đúng với mọi i I thì I sẽ là tập được phép. Bởi vậy ta tin rằng sẽ có một tạp được phép với kích thước xấp xỉ 3N/16 chứa các bít khoá đúng và ngoài ra không có một tập nào khác. Có thể dễ dàng xây dựng các tập được phép I bằng một thuật toán đệ quy.
Ví dụ 3.5.
Một số chương trình máy tính đã được thực hiện để kiêmr tra phương pháp này. Trong đó đã tạo ra một mẫu ngẫu nhiên gồm 120 cặp bản rõ với các XOR xác định và các bản rõ này đã được mã hoá bằng cùng một khoá ( ngẫu nhiên ). Bảng 3.1 đưa ra 120 cặp các bản rõ và các bản mã tương ứng ở dạng mã hexa.
Khi tính các tập được phép ta thu được ni tập được phép có lực lượng như sau:
-
i
|
ni
|
2
3
4
5
6
7
8
9
10
|
111
180
231
255
210
120
45
10
1
|
Tập được phép duy nhất có lực lượng 10 là:
{24,29,30,48,50,52,55,83,92,118}
Thực tế tập được tạo ra theo 10 cặp đúng. Chỉ có tập được phép này mới chứa các bít khoá đúng cho J2, J5, J6, J7, J8. Chúng có giá trị như sau:
J2 = 011001
J5 = 110000
J6 = 001001
J7 = 101010
J8 = 100011
Chú ý rằng tất cả các tập được phép có lực lượng tối thiểu là 6 không kể 3 tập được phép có lực lượng là 5 sinh ra từ các cặp đúng bởi vì
v ới 6 i 10.
Phương pháp này sẽ cho ta biết 30 bít trong 56 bít khoá. Bằng một đặc trưng 3 vòng khác ( nêu ở hình 3.14 ), ta có thể tính thêm 12 bít khoá nữa ( các bít này nằm trong J1 và J4). Bây giờ chỉ còn lại 14 bít khoá chưa biết. Vì 214 = 16384 là một số quá nhỏ nên có thể dùng phép tìm kiếm vét cạn để xác định nốt chúng.
Hình 3.14.
L0' = 0020000816 R0' = 0000040016
L1' = 0000040016 R1' = 0000000016 p = 1/4
L2' = 0000000016 R2' = 0000040016 p = 1
L3' = 0000040016 R3' = 0020000816 p = 1/4
|
Toàn bộ khoá ( ở dạng hexa, kể cả các bít kiểm tra chẵn lẻ ) sẽ là:
34E9F71A20756231
Như đã nói ở trên, 120 cặp được cho ở bảng 3.1. Trong cột thứ hai, dấu (*) kí hiệu cặp đúng, dấu (**) kí hiệu cặp sai nhận biết được và nó sẽ bị loại bỏ bởi phép lọc. Trong số 120 cặp, có 73 cặp được xác định là các cặp sai nhờ quá trình lọc, bởi vậy 47 cặp còn lại sẽ là các cặp đúng có thể.
3.6.3. Các ví dụ khác về DC.
Các kỹ thuật DC có thể được sử dụng để tấn công DES có trên 6 vòng. Với DES 8 vòng cần 214 bản rõ chọn lọc, DES 10, 12, 14, 16 vòng có thể phá được với tương ứng là 224, 231, 239 và 247 bản rõ chọn lọc. Vào thời điểm hiện tại, tấn công DES có trên 10 vòng là không thực tế.
Một loại mã tích hoán vị - thay thế khác với DES cũng có thể dùng DC để phá ( ở mức độ khác nhau ). Trong các hệ này, có một số hệ mật hoán vị - thay thế đã được đưa ra trong những năm gần đây như FEAL,REDOC-II và LOKI.
Ghi chú ( của người dịch ): theo công bố của Micheal Wiener vào 1993, với 107 USD có thể xây dựng thiết bị chuyên dụng để phá DES trong khoảng 21 phút. Với 108 USD, các bản tin DES có thể bị phá trong khoảng 2 phút. Như vậy, DES không còn bí mật đối với NAS. Tuy nhiên cũng không cần một thiết bị chuyên dụng đắt tiền như vậy để phá DES. Các thông báo được mã hoá bằng DES có thể bị phá bằng các máy tính thông thường trên với điều kiẹen có vẻ siêu thực: có trên 243 26 bít rõ - mã với một khoá 56 bít cố định, tuy nhiên bạn phải chờ lâu hơn.
Trong hội nghị CRYPTO'94 M.Matsui đã trình bày một kỹ thuật phá DES mới được gọi là " thám mã tuyến tính". Sử dụng 243 (8.796.093.022.208) bản mã đã biết. Matsui có thể phá một khoá DES trong 50 ngày bằng một máy tính cá nhân.
3.7. Các chú giải và tài liệu dẫn.
Smid và Branstad đã có một bài báo hay về lịch sử của DES [SB 92]. Các công bố về Chuẩn xử lý thông tin liên bang (FIPS) liên quan đến DES gồm: mô tả DES [NBS 77]; ứng dụng và sử dụng DES [NBS 81]; các chế độ làm việc của DES [NBS 80]; xác thực bằng DES [NBS 85].
Một số tính chất của các hộp S được Brickell, Moore và Purtill [BMP87] nghiên cứu. Chíp giải mã DES được mô tả trong [EB 93]. Thiết bị tìm khoá của Wiener được mô tả ở CRYPTO' 93 [Wi 94]. Phép tối ưu hoá thời gian - bộ nhớ tổng quát hơn được trình bày bởi Fiat và Naor trong [FN 91]. Kỹ thuật DC được phát triển bởi Biham và Shamir [BS 91] ( cũng có thể xem [BS93A] và sách của họ [BS 93] trong đó cũng thảo luận thám mã hệ mật khác). Cách trình bày về DC trong chương này phần lớn dựa trên [BS93]. Một phương pháp mã thám mới có thể dùng để tấn công DES và các hệ mật tương ứng khác là phương pháp thám mã tuyến tính của Matsui [MA 94], [MA 94A].
Các mô tả về hệ mật hoán vị - thay thế khác có thể tìm trong các tài liệu sau: LUCIFER [FE 73], FEAL [MI 91], REDOC-II [CW 91] và LOKI [BKPS 90].
Bảng 3.1. Mã thám DES 6 vòng.
CẶP
|
CẶP ĐÚNG
|
BẢN RÕ
|
BẢN MÃ
|
1
|
**
|
86FA1C2B1F51D3BE
C6F21CC2B1B51D3BE
|
1E23ED7F2F551971
296DE2BG87AC6310
|
2
|
**
|
EDC439EC935E1ACD
ADCC39EC975E1ACD
|
0F847EFE90466588
93E84839E374440B
|
3
|
**
|
9468A0BE00166155
D460A0BE04166155
|
3D6A906A6566D0BF
3BC3B23698379E1
|
4
|
**
|
D4FF2B18A5A8AACB
94F72B18A1A8AAC8
|
26B14738C2556BA4
15753FDE86575ABF
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Chia sẻ với bạn bè của bạn: |