Hãy xem xét một biến thể của thuật toán DES, được gọi là DES-WEAK. Trong DES-Yếu,
không có hoán vị P trong một vòng và tất cả các hộp S được thay thế. Tất cả các hộp S mới đều
giống hệt nhau và được định nghĩa như sau. Cho b0, . . ., b5 đại diện cho sáu bit đầu vào của hộp S và a0,
a1, a2 và a3 bốn bit đầu ra. Khi đó, a0 = b3 â b0b1b5, a1 = b0 â b1b3b5, a2 = b1 â b2b3b5,
và a3 = b2 â b4 â b1b3b5.
• Thiết kế một thuật toán để phá DES-WEAK 16 vòng một cách hiệu quả nhất có thể.
Chúng tôi đã tiếp cận thiết kế này giống như cách tôi đã đề cập bên dưới..
Chúng tôi sử dụng phương pháp phân tích mật mã vi phân để khôi phục khóa. xem xét
chênh lệch 000100 đi vào S-box S2. Hãy để một trong hai
đầu vào với sự khác biệt nhất định
là b0b1b2b3b4b5 và đầu ra tương ứng là a0a1a2a3. để cho
đầu ra cho đầu vào thứ hai (= b0b1b2b2(b3 â 1)b4b5) be a 0 0 a 0 1 a 0 2
một 0 3 . Khi đó, a0 â a 0 0 = 1, a1 â a 0 1 = b1b5, a2 â a 0 2 = b2b5
và a3 â a 0 3 = b1b5. Do đó chênh lệch đầu ra là 1000 trên
đưa ra sự khác biệt đầu vào với
xác suất 1 2 + 1 2 · 1 4 = 5 8 (b5 bằng không hoặc b5 bằng một và
cả b1, b2 đều bằng không).
Vấn đề với sản lượng chênh lệch này là, trong vòng tiếp theo,
sau khi mở rộng, hai hộp S sẽ có vi sai khác không. Cho rằng
rằng, trong vòng đầu tiên, chênh lệch của S1 là 000000 và
nửa trái vi sai cũng là tất cả số không. Sau đó, trong vòng tiếp theo,
chênh lệch vào S1 sẽ là 000001 và vào S2 sẽ là 010000. Hãy để
chúng tôi phân tích cả hai. Đầu tiên hãy xem xét S1. Với cùng một ký hiệu cho lần đầu tiên
đầu vào và hai đầu ra (bây giờ đầu vào thứ hai là b0b1b2b3b4(b5 â
1)), ta được a0 â a 0 0 = b0b1, a1 â a 0 1 = b1b3, a2 â a 0 2 = b2b3
và a3 â a 0 3 = b1b3. Do đó đầu ra
chênh lệch là 0000 với xác suất 1 2 · 3 4 + 1 2 · 1 4 = 1 2
(hoặc b3 bằng 0 và một trong b0, b1 bằng 0 hoặc
b3 là một và cả b1, b2 đều bằng không). Xét S2. Bây giờ đầu vào thứ hai
là b0(b1 â 1)b2b3b4b5, và do đó ta có a0 â a 0 0 = b0b5,
a1 â a 0 1 = b3b5, a2 â a 0 2 = 1 và a3 â a 0 3 = b3b5. Vì thế
chênh lệch đầu ra là 0010 với
xác suất 1 2 + 1 2 · 1 4 = 5 8 (b5 bằng không hoặc b5 bằng một và
cả b0, b3 đều bằng 0). Ở vòng tiếp theo, sau khi áp dụng mở rộng,
sự khác biệt trong hai hộp S này trở thành 000000 000100, đó là
chính xác cùng một sự khác biệt đã đi vào vòng đầu tiên vào
hai người này! Sử dụng phân tích này, bây giờ chúng ta có thể rút ra một đặc điểm
với xác suất cao như sau. Đặt Z là viết tắt của vi sai bằng không trên
32 bit, P viết tắt của vi phân 0000 0010 0000 0000 0000 0000 0000
0000
, và PË là viết tắt của vi phân
0000 1000 0000 0000 0000 0000 0000 0000
. Phân tích trên cho thấy trình tự biến đổi sau đây của
vi phân: [P, Z] p=1 âââ [Z, P] p= 5 8 ââââ [P, PË] p= 5 16 ââââ
[P , Z Ë ] p=1 âââ [Z, PË] p= 5 16 ââââ [P , P Ë ] p= 5 8 ââââ [P,Z].
Xác suất chung của đặc điểm trên là 5 4 2 14 .
Lặp lại điều này một lần nữa và sau đó chỉ thực hiện hai vòng đầu tiên
của điều này, chúng tôi nhận được đặc trưng tròn mười bốn với xác suất 5 9 2
31 â 9 Ã 10â4
. Do đó, sử dụng vài nghìn cặp bản rõ, DES-WEAK có thể bị phá vỡ.
Bây giờ chúng tôi có một thử thách mới và bị mắc kẹt trong đó. Thiết kế được đề cập dưới đây là một sửa đổi nhỏ của câu hỏi được đề cập ở trên mà chúng tôi đã nghiên cứu. Thiết kế diễn ra như sau..
Hãy xem xét một biến thể của thuật toán DES trong đó tất cả các hộp S được
thay thế. Các hộp S mới đều giống hệt nhau và được định nghĩa như sau.
Đặt b1, b2, · · · , b6 đại diện cho sáu bit đầu vào của hộp S. Của nó
đầu ra là b1 â(b2 · b3 · b4), (b3 · b4 · b5) â b6, b1 â (b4 · b5 ·
b2), (b5 ·b2 ·b3)âb6. Ở đây âââ là thao tác XOR theo bit và â·â
là phép nhân bitwise. Thiết kế thuật toán phá DES 16 vòng
với các hộp S mới hiệu quả nhất có thể.
Trong thiết kế này, hoạt động hoán vị vẫn hiện diện và đầu ra hộp S là khác nhau. Vì vậy, làm thế nào chúng ta có thể tiếp cận điều này giống như cách chúng ta đã làm ở trên, với điều kiện là Hộp hoán vị vẫn còn đó.
