Slide attack là một hình thức phá mã được thiết kế để đối phó với ý tưởng phổ biến rằng ngay cả những mật mã yếu cũng có thể trở nên rất mạnh bằng cách tăng số vòng, điều này có thể ngăn chặn một cuộc tấn công khác biệt.
Slide attack hoạt động theo cách làm cho số vòng trong một mật mã không liên quan. Thay vì xem xét các khía cạnh ngẫu nhiên hóa dữ liệu của mật mã khối, slide attack hoạt động bằng cách phân tích lịch trình chính và khai thác các điểm yếu trong đó để phá vỡ mật mã. Phổ biến nhất là các phím lặp lại theo chu kỳ.
Các bài viết liên quan:
Trong khi hai cuộc tấn công phân tích mật mã chung khác — vi phân và tuyến tính phân tích — tập trung chủ yếu vào các thuộc tính lan truyền của mã hóa engine (giả sử lập lịch khóa mạnh tạo ra các khóa con độc lập), mức độ tương tự của một mật mã được nghiên cứu bởi các cuộc slide attack là một khía cạnh hoàn toàn khác. Tùy thuộc vào thiết kế của mật mã, các cuộc slide attack có phạm vi khai thác các điểm yếu lập lịch trình chính để khai thác các đặc tính cấu trúc chung hơn của mật mã. Phiên bản rõ ràng nhất của cuộc tấn công này thường dễ dàng ngăn chặn bằng cách phá hủy tính tương tự của một quá trình lặp đi lặp lại, ví dụ bằng cách thêm bộ đếm khẩu phần lặp lại hoặc các hằng số ngẫu nhiên cố định. Tuy nhiên các biến thể phức tạp hơn của kỹ thuật này khó phân tích và chống lại hơn.
A Typical Slide Attack
Trong phần này, giả sử mật mã nhận n khối bit và có lịch khóa sử dụng K1 tới Km như các khóa có độ dài bất kỳ. Cuộc slide attack hoạt động bằng cách phá vỡ mật mã thành các hàm hoán vị giống hệt nhau (F) . Hàm F này có thể bao gồm nhiều hơn một vòng mật mã; nó được xác định bởi lịch trình chính.
Bước tiếp theo là thu thập 2n/2 các cặp bản rõ-bản mã. Các cặp này, được biểu thị là (P,C) sau đó được sử dụng để tìm một cặp trượt được ký hiệu là (P0,C0)(P1,C1) .
Một cặp trượt có đặc tính P0=F(P1) và C0=F(C1).
Quá trình tìm một cặp trượt có phần khác nhau đối với mỗi mật mã nhưng tuân theo cùng một sơ đồ cơ bản. Một thực tế là nó tương đối dễ dàng để trích xuất khóa chỉ từ một lần lặp lại của F. Chọn bất kỳ cặp (P0,C0)(P1,C1) và kiểm tra xem các khóa tương ứng với P0=F(P1) và C0=F(C1). Nếu các phím này khớp với nhau, đây là một cặp trượt. Nếu không thì chuyển sang cặp tiếp theo.
Slide Attacks với Feistel Cipher
Các cuộc tấn công plaintext đã biết. Trong trường hợp mật mã Feistel, hàm tròn F ((l, r)) = (r ⊕ f (l), l) chỉ sửa đổi một nửa đầu vào của nó. Do đó, Điều kiện F (x) = x’ có thể được nhận ra bằng cách đơn giản so sánh nửa bên trái của x chống lại nửa bên phải của x’ và điều kiện lọc này loại bỏ tất cả trừ 2 − n / 2 của các cặp sai.
Tính năng lọc cải tiến này cho phép giảm bớt sự phức tạp về thời gian của cuộc tấn công theo mô hình mối đe dọa plaintext đối với 2n / 2 hoạt động ngoại tuyến. Có một điều kiện lọc n-bit trên các cặp trượt tiềm năng, đối với if (Pi, Ci) tạo thành một cặp trượt với (P’j, C’j) thì ta có F (Pi) = P’j và F (Ci) = C’j.
Do đó, các cặp trượt tiềm năng xác định bằng cách sử dụng tra cứu (hoặc được sắp xếp danh sách) với 2n / 2: chúng tôi sắp xếp văn bản đã biết (Pi, Ci) dựa trên các nửa bên trái của Pi và Ci, và đối với mỗi j, chúng tôi tìm kiếm một kết quả với các nửa bên phải của P’j và C’j.
Với kỹ thuật này, chúng tôi hy vọng tìm thấy một cặp trượt với chỉ một báo động giả; các vòng sai dễ dàng bị loại bỏ trong giai đoạn thứ hai. Các cặp trượt cung cấp cho chúng ta khoảng n bit thông tin trên khóa; nếu điều này không tiết lộ tất cả các tài liệu quan trọng, chúng tôi có thể tìm kiếm thêm một vài cặp trượt hoặc tìm kiếm trên còn lại các bit khóa không xác định.
Các cuộc tấn công được chọn-plaintext. Đối với mật mã Feistel, độ phức tạp của dữ liệu có thể được giảm thêm xuống còn khoảng 2n / 4 văn bản khi có sẵn các truy vấn plaintext đã chọn. Chìa khóa để rút gọn văn bản là việc sử dụng các cấu trúc được lựa chọn cẩn thận. Cố định một giá trị n / 2-bit tùy ý x. Chúng tôi chọn một nhóm gồm 2n / 4 bản rõ Pi = (x, yi) bằng cách thay đổi trên 2n / 4 giá trị ngẫu nhiên cho y, rồi chọn nhóm 2n / 4 văn bản có dạng P’j = (y’j, x) bằng cách thay đổi so với 2n / 4 ngẫu nhiên lựa chọn cho y’j. Điều này cung cấp 2n / 2 cặp bản rõ và một cặp bên phải xảy ra với xác suất 2 − n / 2 (cụ thể là khi f (x) = yi ⊕y’j), vì vậy chúng tôi hy vọng sẽ tìm thấy một cặp trượt. Cặp trượt này có thể nhận dạng bằng cách sử dụng điều kiện lọc n / 2-bit trên mật mã, và sau đó chúng ta có thể sử dụng nó để khôi phục n bit như trước.
Các cuộc tấn công có thể xảy ra với plaintext đã biết. Khi các bản rõ chứa một số dư thừa, độ phức tạp dữ liệu của một cuộc slide-attack plaintext đã giảm.
Trước tiên, ở một mô hình đơn giản: plaintext phát ra các khối ở đó bốn bit quan trọng của mỗi byte luôn bằng 0, kết quả bản rõ n-bit chỉ có n / 2 bit entropy. Trong trường hợp này, người ta có thể gắn một slide attack với khoảng 23n / 8 mật mã, ở giữa dữ liệu phức tạp của các cuộc tấn công slide đã chọn-bản rõ (2n / 4) và plaintext-đã biết slide attack (2n / 2, cho các bản rõ được phân phối đồng đều).Quan sát là đối với bất kỳ giá trị cố định x nào có thể xảy ra ở nửa bên trái của một bản rõ, dự kiến thấy khoảng 23n / 8 − n / 4 = 2n / 8 bản rõ có dạng Pi = (x, yi), cùng với 2n / 8 bản rõ khác có dạng P’j = (y’j, x). Mỗi x cho khoảng 2n / 4 cặp văn bản và có 2n / 4 giá trị của x. Giả sử f hoạt động ngẫu nhiên, bất kỳ cặp nào như vậy đều có xác suất 2 − n / 2 để tạo thành một cặp trượt, vì vậy, chúng tôi dự kiến tìm thấy khoảng một cặp trượt trong tất cả 23n / 8 mật mã. Cuộc tấn công này thậm chí có thể được chuyển đổi thành một cuộc tấn công chỉ có bản mã với một chút tăng độ phức tạp. Giả sử điều kiện f (u) = v, f (u’) = v’ xác đinh khóa và khôi phục khóa từ u, u’, v, v’ mất O (1) thời gian. Sau đó tìm thấy khóa với 23n / 8 + 1 mật mã và công việc của O (2n / 2). Trước tiên, chúng tôi lưu ý rằng điều kiện lọc n / 2-bit trên mật mã đưa ra tập hợp 2n / 4 + 2 tiềm năng các cặp trượt, trong đó có khoảng bốn cặp đúng (số còn lại là cặp sai).
Danh sách cặp trượt tiềm năng có thể được xác định với các bước O (23n / 8) bằng cách băm hoặc sắp xếp.Tiếp theo, dự đoán một cặp trượt chính xác Ci, C’j. Thứ ba, cho mỗi người còn lại cặp trượt tiềm năng Ci’, C’j’, tính toán giá trị khóa được đề xuất bởi các phương trình F(Ci) = Ci’, F(C’j) = C’j’, và lưu trữ giá trị khóa n-bit này trong một bảng. Chúng tôi tìm kiếm xung đột trong bảng này (bằng cách băm hoặc sắp xếp). Nếu đoán của chúng tôi ở Ci, C’j thực sự đã cho một cặp trượt đúng, giá trị khóa phù hợp sẽ được đề xuất ba lần. Mặt khác, nghịch lý birthday đảm bảo với chúng ta rằng các giá trị khóa sai sẽ được đề xuất chỉ với xác suất không đáng kể. Điều này tạo ra một cuộc tấn công mất O (2n / 2) thời gian (2n / 4 ở Ci, C’j, thực hiện các phép toán O (2n / 4) cho mỗi lần để xây dựng bảng) và cần 2n / 4 + 2 không gian và khoảng 23n / 8 + 1 mật mã.
Độ phức tạp chính xác của các cuộc tấn công slide chỉ có bản rõ có thể xảy ra và bản mã có thể rất khác nhau: một số bản phân phối bản rõ làm tăng độ phức tạp của các cuộc tấn công slide (hoặc thậm chí kết xuất chúng không thể. Nói chung, số lượng văn bản dự kiến cần thiết để tìm cặp trượt đầu tiên là khoảng 2n / 4 (Px Pr [r =x] Pr [l = x]) – 1/2 mặc dù chi tiết chính xác của cuộc tấn công sẽ phụ thuộc vào việc phân phối các bản rõ.
Slide Attacks với 2K – DES
Giả sử một người đề xuất tăng cường DES theo cách sau. Một tăng số vòng từ 16 lên 64, và mở rộng số bit khóa từ 56 lên 96 theo cách đơn giản sau: cho hai khóa 48 bit độc lập K1, K2 một khóa sử dụng K1 trong các vòng lẻ và K2 trong các vòng chẵn thay vì khóa con DES. Phiên bản này rõ ràng là miễn dịch để tìm kiếm toàn diện. Các cuộc tấn công vi phân và tuyến tính thông thường có lẽ cũng sẽ thất bại do số lượng vòng tăng lên. Câu hỏi là: “Đây có phải là mật mã an toàn hơn DES? ” Dưới đây, chúng tôi hiển thị hai cuộc tấn công vào mật mã này sử dụng tính đối xứng của thuật toán lập lịch khóa và độc lập với số vòng.
Một cách rất đơn giản để tấn công mật mã như sau. Đối với bất kỳ đã biết cặp plaintext-ciphertext (P, C), giải mã bản mã C một vòng dưới tất cả 232 đầu ra có thể có từ hàm f trong vòng cuối cùng. Đối với mỗi trong số 232 văn bản kết quả C0 , yêu cầu mã hóa P0 = EK (C0). Điều này tương đương với giải mã trở lại bản rõ P và xa hơn một vòng nữa để F −1 (P, K2) = P0. Vì F bảo toàn 32 bit đầu vào của nó, người ta có thể kiểm tra một 32 bit lọc điều kiện trên P, P0 để loại bỏ về cơ bản tất cả các dự đoán sai ở C0. Khi chúng tôi tìm thấy một C0, P0 tồn tại trong điều kiện lọc, chúng ta có thể suy ra K2 dễ dàng từ các phương trình F (P0, K2) = P, F (C0, K2) = C (ở đây F bao gồm sự hoán đổi Feistel của các nửa).
Quy trình này chỉ để lại giá trị chính xác của K2 với xác suất cao. Bây giờ K1 có thể được tìm thấy bằng cách tìm kiếm toàn diện; hoặc, cho một tấn công hiệu quả hơn, chúng ta có thể loại bỏ vòng đầu tiên bằng cách sử dụng giá trị đã biết của K2, và lặp lại cuộc tấn công một lần nữa vào mật mã kết quả để học K1. Đơn giản này tấn công sử dụng một cặp bản rõ (P, C) đã biết, 233 bản rõ được chọn thích ứng và 233 lần. Một cuộc tấn công tương tự sẽ thực sự hoạt động đối với bất kỳ lịch trình phí “gần như” không đối xứng nào; xem thêm [3] để biết một ví dụ khác về kiểu tấn công này.
Bất cứ gì giá trị cố định của K1, K2 mật mã này có thể được xem như một dòng thác của r2 giống hệt nha đã cố định các hoán vị. Do đó, với một nhóm 232 bản rõ đã biết, người ta có thể khôi phục tất cả 96 các bit của khóa bí mật chỉ bằng cách kiểm tra tất cả các cặp có thể có trong khoảng 263/64 = 257 các bước đơn giản (mỗi bước tương đương với một thao tác mã hóa 2K-DES). Mỗi cặp bản rõ (P, P ∗) đề xuất 216 ứng viên cho K1 và 216 ứng viên cho K2 được kiểm tra ngay lập tức với một cặp mật mã tương ứng (C, C ∗).
Vì vậy, trung bình sau quá trình này, chúng tôi chỉ còn lại một vài ứng cử viên Các khóa 96 bit có thể được kiểm tra thêm bằng mã hóa thử nghiệm. Sử dụng nhiều hơn phương pháp tiếp cận phức tạp (loại trừ nhiều cặp đồng thời) có thể giảm hệ số công việc đáng kể. Đối với mỗi bản rõ, chúng tôi đoán 24 bit bên trái của K1, cho phép chúng tôi tính toán 16-bit của đầu ra S-box và do đó 16-bit của bản rõ liên quan có thể có và 16-bit của bản mã liên quan. Điều này mang lại một Điều kiện 32-bit về cặp bản rõ / bản mã có thể có liên quan; sau đó phân tích nhóm văn bản sẽ có tổng cộng 224 × 232/64 = 250 bước.
