DES (mã hóa)

:Mục từ DES đổi hướng về đây; xem các nghĩa khác tại DES (định hướng)
DES (viết tắt của Data Encryption Standard, hay Tiêu chuẩn Mã hóa Dữ liệu) là một phương pháp mật mã hóa được FIPS (Tiêu chuẩn Xử lý Thông tin Liên bang Hoa Kỳ) chọn làm chuẩn chính thức vào năm 1976. Sau đó chuẩn này được sử dụng rộng rãi trên phạm vi thế giới. Ngay từ đầu, thuật toán của nó đã gây ra rất nhiều tranh cãi, do nó bao gồm các thành phần thiết kế mật, độ dài khóa tương đối ngắn, và các nghi ngờ về cửa sau để Cơ quan An ninh quốc gia Hoa Kỳ (NSA) có thể bẻ khóa. Do đó, DES đã được giới nghiên cứu xem xét rất kỹ lưỡng, việc này đã thúc đẩy hiểu biết hiện đại về mật mã khối (block cipher) và các phương pháp thám mã tương ứng.

Hiện nay DES được xem là không đủ an toàn cho nhiều ứng dụng. Nguyên nhân chủ yếu là độ dài 56 bit của khóa là quá nhỏ. Khóa DES đã từng bị phá trong vòng chưa đầy 24 giờ. Đã có rất nhiều kết quả phân tích cho thấy những điểm yếu về mặt lý thuyết của mã hóa có thể dẫn đến phá khóa, tuy chúng không khả thi trong thực tiễn. Thuật toán được tin tưởng là an toàn trong thực tiễn có dạng Triple DES (thực hiện DES ba lần), mặc dù trên lý thuyết phương pháp này vẫn có thể bị phá. Gần đây DES đã được thay thế bằng AES (Advanced Encryption Standard, hay Tiêu chuẩn Mã hóa Tiên tiến).

Trong một số tài liệu, người ta phân biệt giữa DES (là một tiêu chuẩn) và thuật toán DEA (Data Encryption Algorithm, hay Thuật toán Mã hóa Dữ liệu) - thuật toán dùng trong chuẩn DES.

Lịch sử
Khởi nguyên của thuật toán đã có từ đầu thập niên 1970. Vào năm 1972, sau khi tiến hành nghiên cứu về nhu cầu an toàn máy tính của chính phủ Hoa Kỳ, Cục Tiêu chuẩn Liên bang Hoa Kỳ (National Bureau of Standard - NBS), hiện nay đã đổi tên thành Viện Tiêu chuẩn và Công nghệ Quốc gia Hoa Kỳ (National Institute of Standards and Technology - NIST), đã nhận ra nhu cầu về một tiêu chuẩn của chính phủ dùng để mật mã hóa các thông tin mật/nhạy cảm. Vào ngày 15 tháng 5 năm 1973, sau khi tham khảo với NSA, NBS đưa ra kêu gọi thiết kế một thuật toán mã hóa có thể đáp ứng được các tiêu chuẩn nghiêm ngặt. Tuy nhiên không có đề xuất nào đáp ứng được yêu cầu đề ra. Ngày 27 tháng 8 năm 1974, NBS đưa ra kêu gọi lần thứ hai. Lần này công ty IBM đã đưa ra một đề xuất có thể chấp nhận được. Đề xuất này được phát triển trong những năm 1973-1974 dựa trên một thuật toán đã có từ trước - thuật toán mật mã Lucifer của Horst Feistel. Đội ngũ tại công ty IBM liên quan tới quá trình thiết kế bao gồm: Feistel, Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith và Bryant Tuckerman.

Sự tham gia của Cơ quan An ninh quốc gia Hoa Kỳ trong quá trình thiết kế
Ngày 17 tháng 3 năm 1975, đề xuất về DES được công bố trên công báo liên bang Hoa Kỳ (Federal Register) để công chúng tham gia ý kiến. Trong năm tiếp theo, hai hội thảo mở rộng được tổ chức để xem xét đề xuất này. Đã có rất nhiều ý kiến chỉ trích được nêu ra, trong đó bao gồm ý kiến của các nhà khoa học tiên phong về mật mã khóa công khai (public-key cryptography) là Martin Hellman và Whitfield Diffie về các vấn đề như độ dài khóa và thành phần của thuật toán không được công khai: S-box. Điều sau được xem như là sự can thiệp (không hợp lý) của NSA làm giảm độ an toàn của thuật toán và cho phép NSA (và không ai khác) có thể dễ dàng đọc được thông tin đã được mã hóa. Alan Konheim, một trong những thành viên thiết kế DES, nói rằng: "Chúng tôi đã gửi thiết kế của S-box tới Washington. Khi trở lại thì mọi thứ đã được thay đổi." Trong một báo cáo mật của ủy ban của Thượng viện Hoa Kỳ được cử để điều tra những sửa đổi của NSA công bố năm 1978 đã viết:
:"Trong quá trình phát triển DES, NSA thuyết phục IBM rằng độ dài (56 bit) của khóa là đủ an toàn; gián tiếp hỗ trợ sự phát triển cấu trúc của S-box; và chứng nhận rằng thuật toán DES không có điểm yếu về mặt thống kê và toán học."

Tuy nhiên, báo cáo cũng viết:
:"NSA không can thiệp vào quá trình thiết kế thuật toán dưới bất kỳ hình thức nào. IBM đã phát minh và thiết kế ra thuật toán, đưa ra các quyết định, và cho rằng độ dài của khóa là nhiều hơn cần thiết cho các ứng dụng thương mại (mục tiêu của DES)."

Một thành viên khác tham gia phát triển DES là Walter Tuchman được cho là đã phát biểu: "Chúng tôi phát triển DES hoàn toàn bên trong IBM và chỉ sử dụng các nhân viên của IBM. NSA đã không ép buộc bất kỳ điều gì!"

Những nghi ngờ về điểm yếu được giấu của S-box được giảm bớt trong thập niên 1990 khi Eli Biham và Adi Shamir công bố những nghiên cứu độc lập về thám mã vi sai (differential cryptanalysis, một trong những phương pháp phổ biến để thám mã các dạng mật mã khối). S-box trong cấu trúc của DES có khả năng chống lại dạng tấn công này hiệu quả hơn so với khi nó được chọn một cách ngẫu nhiên. Điều này có thể là do IBM đã biết về dạng tấn công này từ thập niên 1970. Khả năng này một lần nữa được chứng tỏ vào năm 1994 khi Don Coppersmith công bố những tiêu chuẩn ban đầu của việc thiết kế S-box. Sau khi đảm bảo DES có khả năng chống lại đã được kỹ thuật thám mã vi sai, IBM đã giữ bí mật về nó theo yêu cầu của NSA. Coppersmith cũng giải thích thêm: "Nguyên nhân là vì thám mã vi sai là một kỹ thuật rất hiệu quả và công bố thông tin về nó điều này có thể gây nguy hại cho an ninh quốc gia." Ngay cả Shamir cũng nhìn nhận rằng: "Tôi có thể nói rằng, trái với suy nghĩ của nhiều người, không có bằng chứng về sự can thiệp vào thiết kế làm giảm độ an toàn của DES."

Lý do mà NSA đưa ra để giải thích về việc giảm độ dài khóa từ 64 bit xuống 56 bit là để dành 8 bit cho việc kiểm tra lỗi (parity checking). Những ý kiến chỉ trích cho rằng đây chỉ là nguyên cớ chứ không phải là nguyên nhân thực sự. Nhiều người tin rằng quyết định giảm độ dài khóa xuống 56 bit là để NSA có thể thực hiện thám mã bằng phương pháp bạo lực (brute force attack) trước vài năm so với phần còn lại của thế giới.

DES với vai trò là một tiêu chuẩn
Bất chấp những chỉ trích, DES được chọn làm tiêu chuẩn liên bang (Hoa Kỳ) vào tháng 11 năm 1976 và được công bố tại tài liệu có tên là FIPS PUB 46 vào ngày 15 tháng 1 năm 1977 cho phép sử dụng chính thức đối với thông tin không mật. DES tiếp tục được khẳng định là tiêu chuẩn vào các năm 1983, 1988 (với tên FIPS-46-1), 1993 (FIPS-46-2) và 1998 (FIPS-46-3). Lần cuối cùng quy định dùng "Triple DES" (xem thêm ở phần sau). Ngày 26 tháng 5 năm 2002, DES được thay thế bằng AES sau một cuộc thi rộng rãi (xem thêm Quá trình AES). Tuy nhiên, tại thời điểm năm 2004, DES vẫn còn được sử dụng khá phổ biến.

Năm 1994, thêm một phương pháp tấn công khác (trên lý thuyết) được công bố là thám mã tuyến tính. Tuy nhiên thời điểm nhu cầu thay thế DES trở nên thực sự cấp thiết là vào năm 1998 khi một cuộc tấn công bạo lực chứng tỏ rằng DES có thể bị phá vỡ trên thực tế. Các phương pháp thám mã này sẽ được miêu tả kỹ hơn ở phần sau.

Sự xuất hiện của DES đã tạo nên một làn sóng nghiên cứu trong giới khoa học về lĩnh vực mật mã học, đặc biệt là các phương pháp thám mã mã khối. Về điều này, Bruce Schneier viết:
: "NSA coi DES là một trong những sai lầm lớn nhất. Nếu họ biết trước rằng chi tiết của thuật toán sẽ được công bố để mọi người có thể viết chương trình phần mềm, họ sẽ không bao giờ đồng ý. DES đã tạo nên nguồn cảm hứng nghiên cứu trong lĩnh vực thám mã hơn bất kỳ điều gì khác: Giới khoa học đã có một thuật toán để nghiên cứu - thuật toán mà NSA khẳng định là an toàn."

Quá trình

Quá trình thay thế DES
Từ cuối thập niên 1980, đầu thập niên 1990, xuất phát từ những lo ngại về độ an toàn và tốc độ thấp khi áp dụng bằng phần mềm, giới nghiên cứu đã đề xuất khá nhiều thuật toán mã hóa khối để thay thế DES. Những ví dụ tiêu biểu bao gồm: RC5, Blowfish, IDEA (International Data Encryption Algorithm, hay Thuật toán mã hóa dữ liệu quốc tế), NewDES, SAFER, CAST5 và FEAL. Hầu hết những thuật toán này có thể sử dụng từ khóa 64 bit của DES mặc dù chúng thường được thiết kế hoạt động với từ khóa 64 bit hay 128 bit.

Ngay bản thân DES cũng có thể được sử dụng một cách an toàn hơn. Những người sử dụng DES trước đây có thể dùng Triple DES (hay TDES). Đây là phương pháp được một trong những người phát minh ra DES miêu tả và kiểm tra (Xem thêm FIPS PUB 46-3). Triple DES sử dụng DES ba lần cho một văn bản với những khóa khác nhau. Hiện nay Triple DES được xem là an toàn mặc dù tốc độ thực hiện khá chậm. Một phương pháp khác ít đòi hỏi khả năng tính toán hơn là DES-X với việc tăng độ dài từ khóa bằng cách thực hiện phép XOR từ khóa với phần thêm trước và sau khi thực hiện DES. Một phương pháp nữa là GDES được đề xuất làm tăng tốc độ mã hóa nhưng nó được chứng tỏ là không an toàn trước tấn công vi sai (differential cryptanalysis).

Năm 2001, sau một cuộc thi quốc tế, NIST đã chọn ra một thuật toán mới, AES, để thay thế cho DES. Thuật toán được trình diện dưới tên là Rijndael. Những thuật toán khác có tên trong danh sách cuối cùng của cuộc thi AES bao gồm: RC6, Serpent, MARS và Twofish.

Mô tả thuật toán

:Phần miêu tả sau đây lược bỏ những chi tiết cụ thể về quá trình chuyển đổi và hoán vị của thuật toán. Những thông tin chính xác có thể được xem thêm tại: thông tin bổ sung về DES.

DES là thuật toán mã hóa khối: nó xử lý từng khối thông tin của bản rõ có độ dài xác định và biến đổi theo những quá trình phức tạp để trở thành khối thông tin của bản mã có độ dài không thay đổi. Trong trường hợp của DES, độ dài mỗi khối là 64 bit. DES cũng sử dụng khóa để cá biệt hóa quá trình chuyển đổi. Nhờ vậy, chỉ khi biết khóa mới có thể giải mã được văn bản mã. Khóa dùng trong DES có độ dài toàn bộ là 64 bit. Tuy nhiên chỉ có 56 bit thực sự được sử dụng; 8 bit còn lại chỉ dùng cho việc kiểm tra. Vì thế, độ dài thực tế của khóa chỉ là 56 bit.

Giống như các thuật toán mã hóa khối khác, khi áp dụng cho các văn bản dài hơn 64 bit, DES phải được dùng theo một phương pháp nào đó. Trong tài liệu FIPS-81 đã chỉ ra một số phương pháp, trong đó có một phương pháp dùng cho quá trình nhận thực . Một số thông tin thêm về những cách sử dụng DES được miêu tả trong tài liệu FIPS-74 .

Tổng thể
Cấu trúc tổng thể của thuật toán được thể hiện ở Hình 1: có 16 chu trình giống nhau trong quá trình xử lý. Ngoài ra còn có hai lần hoán vị đầu và cuối (Initial and final permutation - IP & FP). Hai quá trình này có tính chất đối nhau (Trong quá trình mã hóa thì IP trước FP, khi giải mã thì ngược lại). IP và FP không có vai trò xét về mật mã học và việc sử dụng chúng chỉ có ý nghĩa đáp ứng cho quá trình đưa thông tin vào và lấy thông tin ra từ các khối phần cứng có từ thập niên 1970. Trước khi đi vào 16 chu trình chính, khối thông tin 64 bit được tách làm hai phần 32 bit và mỗi phần sẽ được xử lý tuần tự (quá trình này còn được gọi là mạng Feistel).

Cấu trúc của thuật toán (mạng Feistel) đảm bảo rằng quá trình mã hóa và giải mã diễn ra tương tự. Điểm khác nhau chỉ ở chỗ các khóa con được sử dụng theo trình tự ngược nhau. Điều này giúp cho việc thực hiện thuật toán trở nên đơn giản, đặc biệt là khi thực hiện bằng phần cứng.

Ký hiệu sau: \oplus thể hiện phép toán XOR. Hàm F làm biến đổi một nửa của khối đang xử lý với một khóa con. Đầu ra sau hàm F được kết hợp với nửa còn lại của khối và hai phần được tráo đổi để xử lý trong chu trình kế tiếp. Sau chu trình cuối cùng thì 2 nửa không bị tráo đổi; đây là đặc điểm của cấu trúc Feistel khiến cho quá trình mã hóa và giải mã trở nên giống nhau.

Hàm Feistel (F)
Hàm F, như được miêu tả ở Hình 2, hoạt động trên khối 32 bit và bao gồm bốn giai đoạn:

Mở rộng: 32 bit đầu vào được mở rộng thành 48 bit sử dụng thuật toán hoán vị mở rộng (expansion permutation) với việc nhân đôi một số bit. Giai đoạn này được ký hiệu là E trong sơ đồ.
Trộn khóa: 48 bit thu được sau quá trình mở rộng được XOR với khóa con. Mười sáu khóa con 48 bit được tạo ra từ khóa chính 56 bit theo một chu trình tạo khóa con (key schedule) miêu tả ở phần sau.
Thay thế: 48 bit sau khi trộn được chia làm 8 khối con 6 bit và được xử lý qua hộp thay thế S-box. Đầu ra của mỗi khối 6 bit là một khối 4 bit theo một chuyển đổi phi tuyến được thực hiện bằng một bảng tra. Khối S-box đảm bảo phần quan trọng cho độ an toàn của DES. Nếu không có S-box thì quá trình sẽ là tuyến tính và việc thám mã sẽ rất đơn giản.
Hoán vị: Cuối cùng, 32 bit thu được sau S-box sẽ được sắp xếp lại theo một thứ tự cho trước (còn gọi là P-box).

Quá trình luân phiên sử dụng S-box và sự hoán vị các bít cũng như quá trình mở rộng đã thực hiện được tính chất gọi là sự xáo trộn và khuếch tán (confusion and diffusion). Đây là yêu cầu cần có của một thuật toán mã hoá được Claude Shannon phát hiện trong những năm 1940.

Quá trình tạo khóa con

Hình 3 mô tả thuật toán tạo khóa con cho các chu trình. Đầu tiên, từ 64 bit ban đầu của khóa, 56 bit được chọn (Permuted Choice 1, hay PC-1); 8 bit còn lại bị loại bỏ. 56 bit thu được được chia làm hai phần bằng nhau, mỗi phần được xử lý độc lập. Sau mỗi chu trình, mỗi phần được dịch đi 1 hoặc 2 bit (tùy thuộc từng chu trình, nêu đó là chu trình 1,2,9,16 thì đó là dịch 1bit, còn lại thì sẽ được dich 2bit). Các khóa con 48 bit được tạo thành bởi thuật toán lựa chọn 2 (Permuted Choice 2, hay PC-2) gồm 24 bit từ mỗi phần. Quá trình dịch bit (được ký hiệu là "47 văn bản rõ. DES đã được thiết kế để chống lại tấn công dạng này.
Phá mã tuyến tính được tìm ra bởi Mitsuru Matsui và nó đòi hỏi 243 văn bản rõ (Matsui, 1993). Phương pháp này đã được Matsui thực hiện và là thực nghiệm phá mã đầu tiên được công bố. Không có bằng chứng chứng tỏ DES có khả năng chống lại tấn công dạng này. Một phương pháp tổng quát hơn, phá mã tuyến tính đa chiều (multiple linear cryptanalysis), được Kaliski và Robshaw nêu ra vào năm 1994, Biryukov và cộng sự tiếp tục cải tiến vào năm 2004. Nghiên cứu của họ cho thấy mô phỏng tuyến tính đa chiều có thể sử dụng để giảm độ phức tạp của quá trình phá mã tới 4 lần (chỉ còn 241 văn bản rõ). Kết quả tương tự cũng có thể đạt được với kiểu tấn công tuyến tính kết hợp với lựa chọn bản rõ (Knudsen and Mathiassen, 2000). Junod (2001) đã thực hiện một số thực nghiệm để tìm ra độ phức tạp thực tế của phá mã tuyến tính và thấy rằng quá trình thực tế nhanh hơn dự đoán: 239×241.
Phá mã Davies: trong khi phá mã vi sai và phá mã tuyến tính là các kỹ thuật phá mã tổng quát, có thể áp dụng cho các thuật toán khác nhau, phá mã Davies là một kỹ thuật dành riêng cho DES. Dạng tấn công này được đề xuất lần đầu bởi Davies vào cuối những năm 1980 và cải tiến bởi Biham và Biryukov (1997). Dạng tấn công mạnh nhất đòi hỏi 250 văn bản rõ, độ phức tạp là 250 và có tỷ lệ thành công là 51%.

Ngoài ra còn có những kiểu tấn công dựa trên bản thu gọn của DES - DES với ít hơn 16 chu trình. Những nghiên cứu này cho chúng ta biết số lượng chu trình cần có và ranh giới an toàn của hệ thống. Năm 1994, Langford và Hellman đề xuất phá mã vi sai - tuyến tính (differential-linear cryptanalysis) kết hợp giữa phá mã vi sai và tuyến tính. Một dạng cải tiến của phương pháp này có thể phá vỡ DES 9 chu trình với 215.8 văn bản rõ và có độ phức tạp là 229.2 (Biham et al, 2002).

Một vài đặc điểm về cách giải mã
DES có tính chất bù:
:E_K(P)=C \Leftrightarrow E_\overline{K}(\overline{P})=\overline{C}
trong đó \overline{x} là phần bù của x theo từng bít (1 thay bằng 0 và ngược lại). E_K là bản mã hóa của E với khóa K. P và C là văn bản rõ (trước khi mã hóa) và văn bản mã (sau khi mã hóa). Do tính bù, ta có thể giảm độ phức tạp của tấn công bạo lực xuống 2 lần (tương ứng với 1 bít) với điều kiện là ta có thể lựa chọn bản rõ.

Ngoài ra DES còn có 4 khóa yếu (weak keys). Khi sử dụng khóa yếu thì mã hóa (E) và giải mã (D) sẽ cho ra cùng kết quả:
:E_K(E_K(P)) = P or equivalently, E_K = D_K
Bên cạnh đó, còn có 6 cặp khóa nửa yếu (semi-weak keys). Mã hóa với một khóa trong cặp, K_1, tương đương với giải mã với khóa còn lại, K_2:
:E_{K_1}(E_{K_2}(P)) = P or equivalently, E_{K_2} = D_{K_1}
Tuy nhiên có thể dễ dàng tránh được những khóa này khi thực hiện thuật toán, có thể bằng cách thử hoặc chọn khóa một cách ngẫu nhiên. Khi đó khả năng chọn phải khóa yếu là rất nhỏ.

DES đã được chứng minh là không tạo thành nhóm. Nói một cách khác, tập hợp \{E_K\} (cho tất cả các khóa có thể) theo phép hợp thành không tạo thành một nhóm hay gần với một nhóm (Campbell and Wiener, 1992). Vấn đề này đã từng là một câu hỏi mở trong khá lâu và nếu như tạo thành nhóm thì DES có thể bị phá vỡ dễ dàng hơn bởi vì việc áp dụng DES nhiều lần (ví dụ như trong Triple DES) sẽ không làm tăng thêm độ an toàn của DES.

Xem thêm
Thông tin bổ sung về DES
Thuật toán khóa đối xứng
AES
Mật mã Skipjack

Tham khảo
Ehrsam etl a., Product Block Cipher System for Data Security, , Filed 24 tháng 2 năm 1975
Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
Eli Biham, Alex Biryukov: An Improvement of Davies' Attack on DES. J. Cryptology 10(3): 195-206 (1997)
Eli Biham, Orr Dunkelman, Nathan Keller: Enhancing Differential-Linear Cryptanalysis. ASIACRYPT 2002: pp254–266
Eli Biham: A Fast New DES Implementation in Software Cracking DES: Secrets of Encryption Research, Wiretap Politics, and Chip Design, Electronic Frontier Foundation
A.Biryukov, C.De Canniere, M.Quisquater, "On Multiple Linear Approximations", CRYPTO 2004 (to appear); preprint (PDF) .
Keith W. Campbell, Michael J. Wiener: DES is not a Group. CRYPTO 1992: pp512–520
Don Coppersmith. (1994). The data encryption standard (DES) and its strength against attacks. IBM Journal of Research and Development, 38(3), 243–250.
Witfield Diffie, Martin Hellman, "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" IEEE Computer 10(6), tháng 6 năm 1977, pp74–84
John Gilmore, "Cracking DES: Secrets of Encryption Research, Wiretap Politics and Chip Design", 1998, O'Reilly, ISBN 1-56592-520-3.
Pascal Junod, "On the Complexity of Matsui's Attack. Selected Areas in Cryptography", 2001, pp199–211 .
Burton S. Kaliski Jr., Matthew J. B. Robshaw: Linear Cryptanalysis Using Multiple Approximations. CRYPTO 1994: pp26–39
Lars R. Knudsen, John Erik Mathiassen: A Chosen-Plaintext Linear Attack on DES. FSE 2000: pp262–272
Susan K. Langford, Martin E. Hellman: Differential-Linear Cryptanalysis. CRYPTO 1994: 17–25
Steven Levy, Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age, 2001, ISBN 0-14-024432-8.
Mitsuru Matsui: Linear Cryptanalysis Method for DES Cipher. EUROCRYPT 1993: pp386–397
Mitsuru Matsui: The First Experimental Cryptanalysis of the Data Encryption Standard. CRYPTO 1994: pp1–11
National Bureau of Standards, Data Encryption Standard, FIPS-Pub.46. National Bureau of Standards, U.S. Department of Commerce, Washington D.C., tháng 1 năm 1977.

Liên kết ngoài
FIPS 46-3: The official document describing the DES standard (PDF); An older version in HTML.
The EFF DES cracker project
Helger Lipmaa's links for DES
A worked example of the DES algorithm
A Javascript DES calculator showing intermediate values
John Savard's description of DES
A Fast New DES Implementation in Software - Biham
Bit slice implementation of DES
On Multiple Linear Approximations
Full Disk Encryption