Phân tích khác biệt của SPN

Tham khảo: Hướng dẫn của HM Heys

Nếu chúng tôi tìm thấy một dấu vết vi sai giữ với một số xác suất không đáng kể cho n-1 vòng đối với cấu trúc SPN n vòng, thì chúng tôi có thể khôi phục một số bit của khóa con vòng cuối cùng.

Điều gì xảy ra khi chúng ta chỉ quản lý một đường khác biệt có xác suất không đáng kể chỉ trong một vài vòng R trong đó R < n-1? Làm thế nào để chúng tôi tiến hành trong trường hợp đó để thực hiện một cuộc tấn công khôi phục khóa?

Tôi thực sự sẽ đánh giá cao một số gợi ý để suy nghĩ về điều này.

tự học

Tôi không đồng ý với câu trả lời của @kodlu. Trong phân tích mật mã vi sai cổ điển, chúng tôi không trả "xác suất" cho các vòng cuối cùng, mà thay vào đó chúng tôi trả tiền cho việc liệt kê các bit khóa liên quan. Nói cách khác, việc giải mã không mang tính thống kê.

Và đó là những gì làm cho việc sử dụng nhỏ hơn $R$ khó khăn: các dự đoán chính. Mật mã có khả năng khuếch tán tốt và với mỗi vòng bổ sung để giải mã một phần cuối cùng, số lượng bit khóa cần được đoán để xác minh sự khác biệt đầu ra (hiện tại, theo thống kê, trên mỗi lần đoán khóa) tăng rất nhanh.

Ngoài ra, các hình dạng của sự khác biệt đầu ra cũng quan trọng: nếu nó có trọng số cao (kích hoạt nhiều hộp S trong các vòng tiếp theo), thì cần phải đoán nhiều bit chính hơn.

Lưu ý rằng $R$ và số lượng bit chính để đoán là một sự đánh đổi: nhỏ hơn $R$ tăng xác suất vi sai, nhưng cũng tăng số lượng bit chính để đoán. Thông thường, mức tăng xác suất chênh lệch bằng cách đi từ $R=n-1$ đến $R=n-2$ không cân bằng với sự gia tăng độ phức tạp đoán khóa khi giải mã một phần 2 vòng thay vì 1.

Nguyên nhân $R=n-1$ (hoặc $R=1,$ áp dụng cho ánh xạ giải mã) được sử dụng như sau. Tất cả các xấp xỉ vi phân riêng lẻ cũng như đường vi phân được chọn trên $R$ sản lượng vòng thống kê các mối quan hệ.

Tuy nhiên, giờ đây người ta có thể sử dụng đầu ra bản mã, chạy ngược lại các Sbox trong vòng cuối cùng và có điều kiện cho mỗi lần đoán cho các phím tròn được XOR vào đầu vào của $n^{th}$ hộp tròn có đoán không ngẫu nhiên và chính xác cho kết quả đầu ra của các Hộp được nhắm mục tiêu từ vòng $n-1.$ Điều này có nghĩa là một thử nghiệm thống kê đáng tin cậy có thể được chạy và xác suất chênh lệch theo kinh nghiệm của chênh lệch đầu ra đầu vào đã chọn có thể được tính toán một cách đáng tin cậy.

Ở giai đoạn này, khi đã cung cấp đủ các cặp P/C, dự đoán chính dẫn đến xác suất thực nghiệm lớn nhất được tuyên bố là dự đoán chính có khả năng nhất.

Xem câu trả lời của tôi cho câu hỏi sau để biết thêm chi tiết cụ thể.

Hướng dẫn phá mã vi sai của Howard M. Heys

Chỉnh sửa: Cảm ơn @fractalice vì đã nắm bắt được phần cuối cẩu thả trong câu trả lời của tôi. Thực sự, độ phức tạp tính toán của việc đi qua các dự đoán chính của các Hộp thư "hoạt động" trong vòng cuối cùng mới là điều đáng kể. Vậy xác suất vi phân của $\epsilon$ sau đó $n-1$ đặc điểm khác biệt có nghĩa là bạn cần sử dụng khoảng $c/\epsilon$ Các cặp P/C cho đặc tính theo kinh nghiệm là đặc tính chiếm ưu thế và nếu có $k$ Sboxes hoạt động trong vòng cuối cùng, bạn sẽ cần phải thử $2^{4k}$ (vì Sbox rộng 4 bit) các khóa được đoán trong khi cố gắng quyết định khóa được đoán nào có khả năng nhất.