- đợc cũng là một xâu bít có độ dài 48. - Đầu ra của f là một xâu bít. - Với xâu bít có độ dài 6 (Kí hiệu B i = b 1 b 2 b 3 b 4 b 5 b 6. - là một xâu bít có độ dài 4. - Bởi vậy, mỗi S j có thể đợc coi là một hàm mã mà đầu vào là một xâu bít có độ dài 2 và một xâu bít có. - độ dài 4, còn đầu ra là một xâu bít có độ dài 4). - Xâu bít C = C 1 C 2. - Bởi vậy một sai sót đơn lẻ có thể phát hiện đợc trong mỗi nhóm 8 bít. - Đầu ra của thuật toán sẽ là bản rõ x.. - Giả sử ta mã bản rõ (ở dạng mã hexa - hệ đếm 16):. - 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ã. - độ 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.. - Tức với bản rõ x 64 bít và bản mã y tơng ứng, mỗi khoá đều có thể đợc kiểm tra cho tới khi tìm đợc một khoá K. - Cần chú ý là có thể có nhiều hơn một khoá K nh vậy).. - Ngay từ năm 1977, Diffie và Hellman đã gợi ý rằng có thể xây dựng một chíp VLSI (mạch tích hợp mật độ lớn) có khả năng kiểm tra. - Một máy có thể tìm toàn bộ không gian khoá cỡ 10 6 trong khoảng 1 ngày. - 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ền. - ,K 16 đề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.. - Các ứng dụng phần cứng hiện thời có thể đạt đợc tốc độ mã. - Công ty Digital Equipment đã thông báo tại hội nghị CRUPTO'92 rằng họ sẽ chế tạo một chíp có 50 ngàn tranzistor có thể mã hoá với tốc độ 1 Gbít/s bằng cách dùng nhịp có tốc độ 250MHz. - Dãy bản rõ x 1 x 2. - Nh vậy các chế độ CBC và CFB có thể đợc sử dụng rất hiệu quả. - Đặc biệt hơn, các chế độ này có thể đợc dùng để tạo mã xác thực bản tin ( MAC - message authentication code). - Điều đó có thể thực hiện nh sau: Trớc tiên Alice dùng khoá K 1 để tạo MAC cho x 1. - Ngợc lại, Alice có thể dùng K 1 để mã hoá x 1. - Mặt khác, với một bản rõ x cho trớc, Oscar có thể tính trớc y K = e K (x) đối với toàn bộ 2 56 khoá K và xây dựng một bảng các cặp (y K ,K) đợc sắp xếp theo các tạo độ đầu của chúng. - Thuật toán có thể mô tả theo hai tham số m và t là các số nguyên dơng. - Giả sử x là một xâu bản rõ cố định 64. - Hãy xác định hàm g(K 0 ) =R(e Ko (x)) với một xâu bít K 0 có độ dài 56. - 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 2 ≈ N = 2 56 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. - 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. - Đâ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, nhng 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ỏ.. - Bây giờ ta sẽ mô tả những ý tởng cơ bản dùng trong kỹ thuật này, ta có thể bỏ qua phép hoá vị ban đầu IP và phép hoán vị ngợc của nó ( không ảnh hởng tới việc phân tích mã). - Giả sử S j là một hộp S (1 ≤ j ≤ 8. - ta có thể tính XOR ra của S j và lập bảng phân bố kết quả. - Có 64 XOR ra phân bố trong 2 4 = 16 giá trị có thể. - Trong ví dụ 3.1 chỉ có 8 trong 16 XOR ra có thể xuất hiện trên thực tế. - 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.. - Các cặp thực tế có các XOR vào xác định và tạo nên các XOR ra xác định có thể nhận đợc từ tập IN j (B j ',C j. - Ta thấy rằng, tập này có thể đợc phân thành N j (B j ',C j ' )/2 cặp, mỗi cặp có số XOR vào bằng B j. - 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.. - Bây giờ số XOR vào (cho tất cả 8 hộp) có thể đợc tính nh sau:. - 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 xâu vào có thể với XOR vào là 110100.. - Các XOR ra Các xâu vào có thể 0000. - Nếu ta có một bộ ba E 1 ,E 1 * ,C 1 ' thứ hai nh vậy thì có thể thu đ- ợc tập test 1 thứ hai chứa các giá trị có thể chứa các bít khoá trong J 1 . - Nếu ta có vài bộ ba nh vậy thì có thể nhanh chóng xác định đợc các bít khoá trong J 1 . - Có thể biểu thị R 3 nh sau:. - Lúc này R 3 ' đã biết vì có thể tính đợc nó từ hai bản mã. - biết do có thể tính đợc nó từ hai bản rõ. - Điều này có nghiã là ta có thể tính f(R 2 ,K 3. - Bởi vậy, có thể tính. - Nh thế ta đã biết E và E * và C ' của vòng thứ 3 và có thể thực hiện ( nh ở phần trớc) để xây dựng các tệp test 1. - test 8 chứa các giá trị có thể của các bít trong J 1. - Bản rõ Bản mã. - Nếu coi một xâu bít. - Bây giờ ta có thể xây dựng 48 bít của khoá bằng cách nhìn vào bảng khoá đối với vòng 3. - J 8 có thể).. - XOR ra của S 1 sẽ là 1110 với xác suất bằng 14/64 ( vì có thể tính đợc N . - trong đó đã chọn các bản rõ để L 0. - Có thể biểu thị R 6 nh sau:. - f(R 5 ,K 6 ) R 6 * có thể biểu thị theo cách tơng tự và bởi vậy:. - Nếu đây là trờng hợp thực tế thì XOR vào của cá hộp S trong vòng 4 có thể tính đợc theo hàm mở rộng bằng:. - Điều đó có nghĩa là có thể tính các XOR ra của 5 hộp S này ở vòng 6 theo (3.4). - trong đó mỗi C i ' là một xâu bít có độ dài 4. - Các đầu ra của các hộp S ở vòng 6 có thể. - có thể đợc tính theo các bản mã nh đã mô tả trên hình 3.13.. - 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ể.. - Nếu cặp này sai thì giá trị của C j ' sẽ không đúng và giả định rằng mỗi tập test j 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 | test j. - Bây giờ , với một cặp sai cho trớc, có thể thấy rằng xác suất để test j. - Với một cặp đúng, xâu bít. - đúng J 2 J 5 J 6 J 7 J 8 sẽ là một xâu bít đợc gợi ý. - Ta có thể mã tập test j bất kỳ bằng véc tơ T j có độ dài 64, trong đó tạo độ thứ i của T j đợ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 test j . - 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.. - ta có thể tính thêm 12 bít khoá nữa ( các bít này nằm trong J 1 và J 4. - Vì 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.. - đợ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ể.. - 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 2 14 bản rõ chọn lọc, DES vòng có thể phá đợc với tơng ứng là và 2 47 bản rõ chọn lọc.. - 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. - theo công bố của Micheal Wiener vào 1993, với 10 7 USD có thể xây dựng thiết bị chuyên dụng để phá. - Với 10 8 USD, các bản tin DES có thể bị phá trong khoảng 2 phút. - 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:. - Matsui có thể phá một khoá DES trong 50 ngày bằng một máy tính cá nhân.. - cũng có thể xem [BS93A] và sách của họ [BS 93]. - 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]. - Cặp Cặp đúng Bản rõ Bản mã. - 3.1.hãy chứng minh rằng phép giải mã DES có thể thực hiện bằng cách áp dụng thuật toán mã hoá DES cho bản rõ với bảng khoá đảo ng- ợc.. - Chú ý rằng kết quả trên có thể chứng minh đợc chỉ bằng cách sử dụng mô tả "mức cao". - 3.4.Có thể tạo một mã xác thực thông báo bằng chế độ CFB cũng nh chế độ CBC. - Cho dãy các khối bản rõ x 1. - 3.5.Giả sử một dãy các khối bản rõ x 1. - Cho x là bản rõ cố định. - định có thể tìm theo phơng pháp tìm kiếm vét cạn).
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt