DES (mã hóa)

Data Encryption Standard
Hàm Feistel trong DES
Thông tin chung
Tác giả	IBM
Năm công bố	1975 (trở thành tiêu chuẩn tháng 1 năm 1977)
Phát triển từ	Lucifer (mã hóa)
Các thuật toán dựa trên	Triple DES, G-DES, DES-X, LOKI89, ICE
Chi tiết thuật toán
Khối dữ liệu	64 bít
Độ dài khóa	56 bít
Cấu trúc	Mạng Feistel
Số chu trình	16
Phá mã
Hiện nay DES được xem là không đủ an toàn vì có thể bị tấn công bạo lực. Tại thời điểm năm 2004, phương pháp thám mã tốt nhất là thám mã tuyến tính với 243 bản rõ và độ phức tạp về thời gian là 239-43 (Junod, 2001); nếu có thể lựa chọn bản rõ, độ phức tạp sẽ giảm đi 4 lần (Knudsen and Mathiassen, 2000).

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

Ngày	Sự kiện
15 tháng 5 năm 1973	NBS đưa ra lời kêu gọi đầu tiên về một thuật toán mã hóa tiêu chuẩn.
27 tháng 8 năm 1974	NBS đưa ra lời kêu gọi thứ hai.
17 tháng 3 năm 1975	DES được công bố trên công báo liên bang Hoa Kỳ để công chúng đóng góp ý kiến.
Tháng 8, 1976	Hội thảo đầu tiên về DES.
Tháng 9, 1976	Hội thảo lần hai, bàn về nền tảng toán học của DES.
Tháng 11, 1976	DES được phê chuẩn làm tiêu chuẩn chính thức.
15 tháng 1 năm 1977	DES được xác nhận làm tiểu chuẩn của FIPS (FIPS PUB 46).
1983	DES được công bố lại lần đầu.
1986	HBO phát sóng chương trình Videocipher II, một kênh TV mã hóa dựa trên DES.
22 tháng 1 năm 1988	DES được xác nhận lần hai với tên FIPS 46-1, thay thế FIPS PUB 46.
1992	Biham và Shamir công bố kiểu tấn công thám mã vi sai (trên lý thuyết) với độ phức tạp thấp hơn tấn công bạo lực. Tuy nhiên, kiểu tấn công này đòi hỏi người tấn công lựa chọn 247 văn bản rõ (một điều kiện không thực tế) .
30 tháng 12 năm 1993	DES được xác nhận lần ba với tên FIPS 46-2.
1994	Thực nghiệm thám mã DES lần đầu tiên được thực hiện với kỹ thuật thám mã tuyến tính .
Tháng 6, 1997	Dự án DESCHALL đã phá vỡ được một bản tin mã hóa bằng DES (lần đầu tiên trước công chúng).
Tháng 7, 1998	Thiết bị thám mã Deep Crack của tổ chức Electronic Frontier Foundation phá được một khóa của DES trong vòng 56 giờ.
Tháng 1, 1999	Deep Crack cùng với distributed.net phá được một khóa của DES trong vòng 22 giờ và 15 phút.
25 tháng 10 năm 1999	DES được xác nhận lần thứ tư với tên FIPS 46-3. Lần này phương pháp Triple DES được khuyến cáo sử dụng còn DES chỉ được dùng cho các hệ thống ít quan trọng.
26 tháng 11 năm 2001	AES được công bố trong FIPS 197
26 tháng 5 năm 2002	AES trở thành tiêu chuẩn
26 tháng 7 năm 2004	Việc bãi bỏ FIPS 46-3 (cùng với một số tiêu chuẩn liên quan khác) được đăng trên công báo liên bang Hoa Kỳ (http://edocket.access.gpo.gov/2004/04-16894.htm).
19 tháng 5 năm 2005	NIST bãi bỏ FIPS 46-3

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

Hình 1 – Cấu trúc thuật toán Feistel dùng trong DES

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 [3]. 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 [4].

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:

Hình 2 – Hàm F (F-function) dùng trong DES

1. 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ơ đồ.
2. 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.
3. 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.
4. 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 – Quá trình tạo khóa con trong DES

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à "<<<" trong sơ đồ) khiến cho các khóa con sử dụng các bit khác nhau của khóa chính; mỗi bit được sử dụng trung bình ở 14 trong tổng số 16 khóa con.

Quá trình tạo khóa con khi thực hiện giải mã cũng diễn ra tương tự nhưng các khóa con được tạo theo thứ tự ngược lại. Ngoài ra sau mỗi chu trình, khóa sẽ được dịch phải thay vì dịch trái như khi mã hóa

An toàn và sự giải mã

Mặc dù đã có nhiều nghiên cứu về phá mã DES hơn bất kỳ phương pháp mã hóa khối nào khác nhưng phương pháp phá mã thực tế nhất hiện nay vẫn là tấn công Brute-force. Nhiều đặc tính mật mã hóa của DES đã được xác định và từ đó ba phương pháp phá mã khác được xác định với mức độ phức tạp nhỏ hơn tấn công bạo lực. Tuy nhiên các phương pháp này đòi hỏi một số lượng bản rõ quá lớn (để tấn công lựa chọn bản rõ) nên hầu như không thể thực hiện được trong thực tế.

Tấn công brute-force (vét cạn)

Đối với bất cứ phương pháp mã hóa nào, kiểu tấn công cơ bản và đơn giản nhất là tấn công bằng bạo lực: thử lần lượt tất cả các khóa có thể cho đến khi tìm ra khóa đúng. Độ dài của khóa sẽ xác định số lượng phép thử tối đa cần thực hiện và do đó thể hiện tính khả thi của phương pháp. Trong trường hợp của DES, nghi ngờ về độ an toàn của nó đã được đặt ra ngay từ khi nó chưa trở thành tiêu chuẩn. Người ta cho rằng chính NSA đã ủng hộ (nếu không muốn nói là thuyết phục) IBM giảm độ dài khóa từ 128 bit xuống 64 bit và tiếp tục xuống 56 bit. Điều này dẫn đến suy đoán rằng NSA đã có hệ thống tính toán đủ mạnh để phá vỡ khóa 56 bit ngay từ những năm 1970.

Hệ thống phá mã DES của Hiệp hội EFF được xây dựng với ngân sách 250000 đô la Mỹ. Hệ thống bao gồm 1536 bộ vi xử lý thiết kế riêng và có khả năng duyệt hết mọi khóa DES trong vòng vài ngày. Hình ảnh thể hiện một phần bảng mạch của hệ thống chứa một vài bộ vi xử lý.

Trong giới nghiên cứu, nhiều đề xuất về các hệ thống phá mã DES được đề ra. Năm 1977, Diffie và Hellman dự thảo một hệ thống có giá khoảng 20 triệu đô la Mỹ và có khả năng phá khóa DES trong 1 ngày. Năm 1993, Wiener dự thảo một hệ thống khác có khả năng phá mã trong vòng 7 giờ với giá 1 triệu đô la Mỹ. Những điểm yếu của DES được thực sự chứng minh vào cuối những năm 1990. Vào năm 1997, công ty bảo mật RSA đã tài trợ một chuỗi cuộc thi với giải thưởng 10.000 đô la Mỹ cho đội đầu tiên phá mã được một bản tin mã hóa bằng DES. Đội chiến thắng trong cuộc thi này là dự án DESCHALL với những người dẫn đầu bao gồm Rocke Verser, Matt Curtin và Justin Dolske. Họ đã sử dụng hàng nghìn máy tính nối mạng để phá mã. Khả năng phá mã DES được chứng minh thêm lần nữa vào năm 1998 khi tổ chức Electronic Frontier Foundation (EFF), một tổ chức hoạt động cho quyền công dân trên Internet, xây dựng một hệ thống chuyên biệt để phá mã với giá thành 250000 đô la Mỹ (Xem thêm: hệ thống phá mã DES của EFF). Động cơ thúc đẩy EFF trong hành động này là nhằm chứng minh DES có thể bị phá vỡ trên lý thuyết cũng như trên thực tế: "Nhiều người không tin vào chân lý cho đến khi họ nhìn thấy sự việc bằng chính mắt mình. Xây dựng một bộ máy có thể phá khóa DES trong vòng vài ngày là cách duy nhất chứng tỏ với mọi người rằng họ không thể đảm bảo an ninh thông tin dựa vào DES." Hệ thống này đã tìm được khóa DES bằng phương pháp bạo lực trong thời gian hơn 2 ngày; trong khi vào khoảng thời gian đó, một chưởng lý của Bộ Tư pháp Hoa Kỳ (DOJ) vẫn tuyên bố rằng DES là không thể bị phá vỡ.

Các kiểu tấn công khác hiệu quả hơn phương pháp brute-force

Hiện nay có 3 kiểu tấn công có khả năng phá vỡ DES (với đủ 16 chu trình) với độ phức tạp thấp hơn phương pháp Brute-force: phá mã vi sai (differential cryptanalysis - DC), phá mã tuyến tính (linear cryptanalysis - LC) và phá mã Davies (Davies' attack). Tuy nhiên các dạng tấn công này chưa thực hiện được trong thực tế.

• Phá mã vi sai được Eli Biham và Adi Shamir tìm ra vào cuối những năm 1980 mặc dù nó đã được IBM và NSA biết đến trước đó. Để phá mã DES với đủ 16 chu trình, phá mã vi sai cần đến 2⁴⁷ 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 2⁴³ 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 2⁴¹ 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: 2³⁹×2⁴¹.
• 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 2⁵⁰ văn bản rõ, độ phức tạp là 2⁵⁰ 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 2^15.8 văn bản rõ và có độ phức tạp là 2^29.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, Bằng sáng chế Hoa Kỳ số 3,962,539, 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) Lưu trữ 2007-06-15 tại Wayback Machine.
• 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. [5]
• 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 Lưu trữ 2009-05-27 tại Wayback Machine.
• 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 Lưu trữ 2005-05-24 tại Wayback Machine
• A worked example of the DES algorithm Lưu trữ 2004-08-20 tại Wayback Machine
• A Javascript DES calculator showing intermediate values Lưu trữ 2004-08-24 tại Wayback Machine
• John Savard's description of DES
• A Fast New DES Implementation in Software - Biham Lưu trữ 2005-03-12 tại Wayback Machine
• Bit slice implementation of DES
• On Multiple Linear Approximations
• Full Disk Encryption