DES có thể bị phá vỡ bằng phương pháp giải mã vi phân không?

/ / Xuất bản năm An ninh mạng, Các nguyên tắc cơ bản về mật mã cổ điển EITC/IS/CCF, Hệ thống mật mã khối DES, Tiêu chuẩn mã hóa dữ liệu (DES) - Lịch trình khóa và giải mã

Phân tích mật mã vi sai là một hình thức phân tích mật mã áp dụng chủ yếu cho mật mã khối, bao gồm việc phân tích ảnh hưởng của những khác biệt cụ thể trong các cặp đầu vào đến những khác biệt ở đầu ra. Phương pháp này được Eli Biham và Adi Shamir giới thiệu vào cuối những năm 1980 và từ đó đã trở thành một công cụ cơ bản trong bộ công cụ của nhà giải mã. Tiêu chuẩn mã hóa dữ liệu (DES), một thuật toán khóa đối xứng để mã hóa dữ liệu số, là một trong những đối tượng chính của phân tích mật mã vi sai.

Thuật toán DES do IBM thiết kế vào đầu những năm 1970 và được Viện Tiêu chuẩn và Công nghệ Quốc gia (NIST) áp dụng làm tiêu chuẩn liên bang vào năm 1977, hoạt động trên các khối dữ liệu 64 bit sử dụng khóa 56 bit. DES sử dụng 16 vòng của mạng Feistel, trong đó mỗi vòng bao gồm một loạt các thay thế và hoán vị được xác định theo lịch trình chính.

Để hiểu liệu DES có thể bị phá vỡ bằng phân tích mật mã vi sai hay không, điều quan trọng là phải xem xét các chi tiết cụ thể của cả cấu trúc DES và các nguyên tắc của phân tích vi phân.

Cấu trúc DES và lịch trình khóa

DES được xây dựng dựa trên sự kết hợp của các phép toán thay thế và hoán vị. Mỗi vòng DES bao gồm các bước sau:
1. Mở rộng (E-box): Nửa khối 32 bit được mở rộng thành 48 bit bằng cách sử dụng hoán vị mở rộng.
2. Trộn phím: Nửa khối mở rộng được XOR với khóa tròn bắt nguồn từ khóa chính bằng cách sử dụng lịch trình khóa.
3. Thay thế (hộp S): Kết quả 48 bit được chia thành 6 đoạn 4 bit, mỗi đoạn được truyền qua hộp S tương ứng để tạo ra đầu ra 4 bit. Tám đầu ra 32 bit được nối với nhau để tạo thành khối XNUMX bit.
4. Hoán vị (P-box): Khối 32 bit được hoán vị bằng bảng hoán vị cố định.
5. XOR và Swap: Khối được hoán vị được XOR với nửa còn lại của khối dữ liệu và các nửa được hoán đổi.

Lịch trình khóa tạo ra một chuỗi gồm 16 khóa tròn, mỗi khóa có độ dài 48 bit, từ khóa 56 bit ban đầu. Quá trình này bao gồm các phép toán lựa chọn hoán vị và dịch chuyển vòng trái.

Nguyên tắc phân tích mật mã vi phân

Phân tích mật mã vi sai liên quan đến việc nghiên cứu sự khác biệt trong các cặp bản rõ lan truyền qua mật mã như thế nào để tạo ra sự khác biệt trong bản mã. Ý tưởng cơ bản là chọn các cặp bản rõ có sự khác biệt cụ thể, mã hóa chúng và phân tích sự khác biệt của bản mã thu được. Bằng cách quan sát những khác biệt này phát triển như thế nào qua các vòng mã hóa, kẻ tấn công có thể suy ra thông tin về khóa.

Các khái niệm chính trong phân tích mật mã vi sai bao gồm:
– Sự khác biệt: Sự khác biệt XOR giữa hai giá trị. Ví dụ, nếu P và P' là hai bản rõ, hiệu của chúng là \Delta P = P \oplus P'.
– Đặc điểm: Một chuỗi các khác biệt mô tả cách một vi sai đầu vào lan truyền qua các vòng mã hóa.
– Xác suất: Khả năng một chênh lệch đầu vào nhất định sẽ tạo ra một chênh lệch đầu ra cụ thể sau một số vòng nhất định.

Ứng dụng vào DES

DES được thiết kế đặc biệt để chống lại việc phân tích mật mã vi sai, phương pháp này chưa được biết đến rộng rãi vào thời điểm thiết kế nhưng đã được IBM và NSA hiểu rõ. Các hộp S trong DES được lựa chọn cẩn thận để giảm thiểu xác suất của các đặc tính vi phân, làm cho việc phân tích mật mã vi sai trở nên khó khăn hơn.

Tuy nhiên, Biham và Shamir đã chứng minh rằng DES không tránh khỏi việc giải mã vi sai. Họ đã chỉ ra rằng, mặc dù DES 16 vòng đầy đủ có khả năng chống lại các cuộc tấn công vi phân trong thực tế, nhưng các phiên bản rút gọn của mật mã vẫn dễ bị tấn công. Cụ thể, họ phát triển các cuộc tấn công vào DES với ít hơn 16 vòng.

Ví dụ: một cuộc tấn công vào DES 8 vòng có thể được tiến hành với độ phức tạp khoảng 2 ^ {47} bản rõ được chọn, hiệu quả hơn đáng kể so với tấn công vũ phu vào toàn bộ không gian khóa. Đối với DES 16 vòng đầy đủ, độ phức tạp của việc phân tích mật mã vi sai cao hơn nhiều, khiến nó không thực tế với các tài nguyên tính toán có sẵn tại thời điểm nghiên cứu của họ.

Ví dụ về phân tích mật mã vi sai trên DES

Để minh họa cách hoạt động của phân tích mật mã vi phân, hãy xem xét một ví dụ đơn giản với DES vòng rút gọn:

1. Chọn một sự khác biệt: Chọn một chênh lệch đầu vào cụ thể \Delta P. Để đơn giản, giả sử \Delta P chỉ ảnh hưởng đến một vài bit.
2. Tạo cặp văn bản thuần túy: Tạo ra một số lượng lớn các cặp bản rõ (P, P') như vậy mà P \oplus P' = \Delta P.
3. Mã hóa cặp văn bản thuần túy: Mã hóa từng cặp để thu được bản mã (C, C').
4. Phân tích sự khác biệt đầu ra: Tính toán chênh lệch đầu ra \Delta C = C \oplus C' cho mỗi cặp.
5. Xác định đặc điểm: Xác định các mẫu trong sự khác biệt đầu ra gợi ý các đặc điểm cụ thể của cấu trúc bên trong của mật mã.
6. Suy ra thông tin chính: Sử dụng các đặc điểm đã xác định để suy ra thông tin về các phím tròn và cuối cùng là phím chính.

Cân nhắc thực tế

Trong khi phân tích mật mã vi sai là một công cụ mạnh mẽ, ứng dụng thực tế của nó vào DES đòi hỏi nguồn lực tính toán đáng kể và một số lượng lớn các bản rõ được chọn. Các phương pháp mã hóa hiện đại đã phát triển để sử dụng các thuật toán phức tạp và an toàn hơn, chẳng hạn như Tiêu chuẩn mã hóa nâng cao (AES), được thiết kế để chống lại không chỉ việc phân tích mật mã vi sai mà còn chống lại một loạt các cuộc tấn công phân tích mật mã khác.

Phân tích mật mã vi phân là một kỹ thuật đã có từ lâu trong lĩnh vực mật mã, có thể được sử dụng để phân tích và trong một số trường hợp có thể phá vỡ các mật mã khối như DES. Trong khi DES 16 vòng đầy đủ có khả năng chống lại các cuộc tấn công khác biệt trong thực tế, thì các phiên bản DES rút gọn lại dễ bị tấn công. Thiết kế của DES, đặc biệt là các hộp S của nó, phản ánh nhận thức về các nguyên tắc phân tích mật mã vi phân, thể hiện tầm quan trọng của việc thiết kế mật mã cẩn thận trong việc đảm bảo an ninh.

Các câu hỏi và câu trả lời gần đây khác liên quan đến Tiêu chuẩn mã hóa dữ liệu (DES) - Lịch trình khóa và giải mã:

Xem thêm câu hỏi và trả lời trong Tiêu chuẩn mã hóa dữ liệu (DES) - Lập lịch khóa và giải mã

Thêm câu hỏi và câu trả lời:

Gắn thẻ theo: , , , , ,