Tiêu chuẩn Mã hóa Nâng cao

Thuật toán này được phát triển bởi hai nhà mật mã học người Bỉ là Joan Daemen và Vincent Rijmen. Khi tham gia cuộc thi thiết kế AES, thuật toán được gọi là 'Rijndael' và phát âm là 'Rhine dahl' theo phiên âm quốc tế (IPA: [ɹaindal]).

Quá trình phát triển

Thuật toán này dựa trên thiết kế Square, một sáng tạo trước đó của Daemen và Rijmen; và Square lại được xây dựng dựa trên Shark.

Khác với DES sử dụng mạng Feistel, Rijndael áp dụng mạng thay thế-hoán vị. AES có thể thực hiện với tốc độ cao bằng phần mềm hoặc phần cứng và yêu cầu bộ nhớ thấp. Là một tiêu chuẩn mã hóa mới, AES đang được triển khai rộng rãi.

Mô tả thuật toán

Dù hai tên AES và Rijndael thường được dùng thay thế nhau, thực tế chúng không hoàn toàn giống nhau. AES chỉ xử lý khối dữ liệu 128 bit và khóa có độ dài 128, 192 hoặc 256 bit, trong khi Rijndael có thể làm việc với dữ liệu và khóa có độ dài tùy ý, là bội số của 32 bit trong khoảng từ 128 đến 256 bit. Các khóa con trong quá trình mã hóa được sinh ra từ việc tạo khóa con Rijndael, mỗi khóa con là một cột gồm 4 byte. Phần lớn các phép toán trong AES được thực hiện trong trường byte hữu hạn. Một khối dữ liệu 128 bit được chia thành 16 byte (mỗi byte 8 bit), có thể sắp xếp thành 4 cột, mỗi cột gồm 4 phần tử hoặc thành một ma trận 4x4 byte, gọi là ma trận trạng thái, hay đơn giản là trạng thái (tiếng Anh: state). Trong quá trình mã hóa, các phép toán được áp dụng để biến đổi ma trận trạng thái này.

Mô tả tổng quan về thuật toán

Mở rộng khóa (KeyExpansion)

Quá trình tạo các vòng khóa từ khóa chính, mỗi khóa con bao gồm 4 byte.

Quá trình mã hóa

Gồm các bước sau:

1. Khởi đầu vòng lặp
   1. AddRoundKey — Kết hợp từng cột của trạng thái đầu tiên với một khóa con theo thứ tự từ đầu dãy khóa.
2. Vòng lặp chính
   1. SubBytes — Thực hiện phép thay thế phi tuyến, mỗi byte trong trạng thái được thay bằng một byte khác dựa vào bảng tra (Rijndael S-box).
   2. ShiftRows — Dịch chuyển các hàng trong trạng thái theo số bước khác nhau.
   3. MixColumns — Trộn các cột trong khối dữ liệu bằng một phép biến đổi tuyến tính.
   4. AddRoundKey
3. Vòng lặp cuối
   1. SubBytes
   2. ShiftRows
   3. AddRoundKey

Trong vòng lặp cuối, bước MixColumns không được thực hiện.

Bước SubBytes

Các byte được thay thế qua bảng S-box, quá trình phi tuyến của thuật toán. S-box được tạo ra từ một phép biến đổi khả nghịch trong trường hữu hạn GF(2), với tính chất phi tuyến. Để ngăn chặn các cuộc tấn công dựa trên đặc điểm đại số, S-box kết hợp phép nghịch đảo với một phép biến đổi affine khả nghịch và được thiết kế để tránh các điểm cố định (fixed point).

Bước ShiftRows

Các hàng được dịch chuyển theo một số bước cụ thể. Trong AES, hàng đầu tiên không thay đổi. Mỗi byte của hàng thứ hai được dịch sang trái một vị trí. Các hàng thứ ba và thứ tư được dịch lần lượt 2 và 3 vị trí. Do đó, mỗi cột của khối đầu ra sẽ bao gồm các byte từ tất cả 4 cột của khối đầu vào. Đối với Rijndael với độ dài khối khác, số bước dịch cũng thay đổi.

Bước MixColumns

Mỗi cột của 4 byte được kết hợp qua một phép biến đổi tuyến tính khả nghịch. Một khối 4 byte đầu vào tạo ra một khối 4 byte đầu ra, với mỗi byte đầu vào ảnh hưởng đến tất cả bốn byte đầu ra. Cùng với bước ShiftRows, MixColumns cung cấp tính chất khuếch tán cho thuật toán. Mỗi cột được coi là một đa thức trong trường hữu hạn và nhân với đa thức $c\left(x\right)=3x^3+x^2+x+2$ (modulo $x^4+1$). Vì vậy, bước này có thể xem là phép nhân ma trận trong trường hữu hạn.

Bước AddRoundKey

Trong bước này, khóa con được áp dụng lên các khối dữ liệu. Mỗi khóa con trong mỗi vòng được tạo ra từ khóa chính thông qua quá trình sinh khóa con Rijndael; mỗi khóa con có kích thước tương tự như các khối dữ liệu. Việc kết hợp được thực hiện bằng cách XOR từng bit của khóa con với dữ liệu khối.

Tối ưu hóa

Đối với hệ thống 32-bit trở lên, có thể tăng tốc thuật toán bằng cách kết hợp các bước SubBytes, ShiftRows, MixColumns và chuyển chúng thành dạng bảng. Có tổng cộng bốn bảng với 256 mục, mỗi mục là một từ 32-bit, chiếm 4096 byte trong bộ nhớ. Khi đó, mỗi vòng lặp bao gồm 16 lần tra bảng và 12 lần thực hiện phép XOR 32-bit cùng với 4 phép XOR trong bước AddRoundKey.

Nếu kích thước các bảng vẫn lớn so với khả năng của thiết bị thực hiện, chỉ cần sử dụng một bảng duy nhất và kết hợp tra bảng với hoán vị vòng quanh.

An toàn

Đến năm 2006, phương pháp tấn công duy nhất thành công vào AES là tấn công kênh bên. Vào tháng 6 năm 2003, chính phủ Hoa Kỳ khẳng định rằng AES có thể được áp dụng cho thông tin mật.

'Thiết kế và kích thước khóa của AES (128, 192 và 256 bít) đủ mạnh để bảo vệ thông tin ở cấp độ TỐI MẬT. Đối với thông tin TUYỆT MẬT, cần sử dụng khóa 192 hoặc 256 bít. Các phiên bản AES dùng để bảo vệ an ninh quốc gia phải được NSA kiểm tra và chứng nhận trước khi triển khai.' - [4] Lưu trữ 2007-09-27 tại Wayback Machine

Đây là lần đầu tiên công chúng được tiếp cận với thuật toán mã hóa được NSA phê duyệt cho thông tin TUYỆT MẬT. Nhiều phần mềm thương mại hiện tại sử dụng khóa 128 bít làm mặc định.

Các phương pháp tấn công phổ biến nhất đối với mã hóa khối thường thử nghiệm các kiểu tấn công trên phiên bản giảm số vòng. AES có 10 vòng cho khóa 128 bít, 12 vòng cho khóa 192 bít và 14 vòng cho khóa 256 bít. Đến năm 2006, các tấn công thành công đã được biết đến là 7 vòng đối với khóa 128 bít, 8 vòng với khóa 192 bít và 9 vòng với khóa 256 bít.

Một số nhà nghiên cứu mật mã lo ngại về độ an toàn của AES, cho rằng khoảng cách giữa số vòng của thuật toán và số vòng cần phá vỡ là quá hẹp. Họ cảnh báo rằng với sự tiến bộ của các kỹ thuật tấn công, AES có thể bị phá vỡ. Ở đây, 'phá vỡ' có nghĩa là bất kỳ phương pháp tấn công nào hiệu quả hơn phương pháp brute-force. Do đó, một tấn công yêu cầu 2 vòng cũng được coi là thành công, mặc dù nó vẫn chưa thể thực hiện trong thực tế. Hiện tại, nguy cơ này không đáng lo ngại và có thể được bỏ qua. Tấn công brute-force quy mô lớn nhất từng được thực hiện là do distributed.net đối với hệ thống RC5 64 bít vào năm 2002 (theo định luật Moore, tương đương với việc tấn công hệ thống 66 bít hiện nay).

Một mối lo khác là về cấu trúc toán học của AES. Không giống như các thuật toán mã hóa khác, AES có một mô tả toán học tương đối đơn giản. Mặc dù điều này chưa dẫn đến nguy cơ cụ thể nào, nhưng một số nhà nghiên cứu lo sợ rằng cấu trúc đơn giản này có thể bị khai thác trong tương lai.

Vào năm 2002, Nicolas Courtois và Josef Pieprzyk đã phát hiện ra một phương pháp tấn công lý thuyết gọi là tấn công XSL và chỉ ra một số điểm yếu tiềm tàng của AES. Tuy nhiên, một số chuyên gia mật mã khác đã chỉ ra những vấn đề trong cơ sở toán học của phương pháp tấn công này và cho rằng các tác giả có thể đã mắc lỗi trong tính toán. Việc tấn công kiểu này có trở thành hiện thực hay không vẫn còn chưa rõ ràng, và cho đến nay, tấn công XSL vẫn chỉ là một giả thuyết.

Tấn công kênh bên (Side channel attacks)

Tấn công kênh bên không nhắm trực tiếp vào thuật toán mã hóa, mà tập trung vào việc khai thác các lỗ hổng trong hệ thống thực thi thuật toán để tiết lộ dữ liệu.

Vào tháng 4 năm 2005, Daniel J. Bernstein đã công bố một phương pháp tấn công vào hệ thống mã hóa AES trong OpenSL. Phương pháp này yêu cầu một máy chủ có khả năng thu thập tối đa thông tin về thời gian và cần đến 200 triệu bản rõ được lựa chọn. Một số ý kiến cho rằng tấn công này không khả thi trên Internet do khoảng cách mạng lưới.

Vào tháng 10 năm 2005, Adi Shamir cùng hai nhà nghiên cứu khác đã trình bày một nghiên cứu về các phương pháp tấn công khác. Trong nghiên cứu, một tấn công có thể thu được khóa AES sau 800 lần ghi trong khoảng 65 mili giây. Để thực hiện tấn công này, kẻ tấn công cần có khả năng chạy chương trình trên hệ thống mã hóa.

• Quá trình thiết kế AES
• Các ứng dụng sử dụng AES

Tài nguyên ngoài

• Trang Rijndael (Tự động chuyển đến AES Lounge, liên kết phiên bản cũ) Lưu trữ 2005-08-30 tại Wayback Machine
• Trang Rijndael (phiên bản cũ) Lưu trữ 2006-12-21 tại Wayback Machine
• Tổng quan tài liệu về AES Lưu trữ 2006-12-21 tại Wayback Machine
• Lưu trữ trang web chính thức cũ của AES Lưu trữ 2002-12-04 tại Wayback Machine
• FIPS PUB 197: tiêu chuẩn chính thức AES (tệp PDF)
• Mô tả thuật toán AES của John Savard

Phần mềm hỗ trợ AES

• Trình tính toán AES bằng Javascript với các giá trị trung gian Lưu trữ 2006-12-24 tại Wayback Machine
• Các phiên bản AES mã nguồn mở BSD của Brian Gladman Lưu trữ 2005-05-24 tại Wayback Machine
• Phiên bản C công khai của Paulo Barreto cho AES Lưu trữ 2005-02-25 tại Wayback Machine
• Phiên bản công khai của AES từ D.J. Bernstein
• Thư viện Nettle có giấy phép GPL cũng bao gồm một cài đặt AES
• Cross-language AES Encryptor/Decryptor cho iOS và Mac bằng Swift

Ghi chú thêm

• Thuật toán Rijndael hỗ trợ các khối dữ liệu với độ dài 128, 160, 192, 224, và 256 bít; trong khi AES chỉ hỗ trợ khối dữ liệu dài 128 bít.
• Thuật toán Rijndael hỗ trợ các khóa với độ dài 128, 160, 192, 224, và 256 bít; còn AES hỗ trợ khóa dài 128, 192, và 256 bít.

• Nicolas Courtois, Josef Pieprzyk, 'Cryptanalysis of Block Ciphers with Overdefined Systems of Equations'. pp267–287, ASIACRYPT 2002.
• Joan Daemen và Vincent Rijmen, 'The Design of Rijndael: AES - The Advanced Encryption Standard.' Springer-Verlag, 2002. ISBN 3-540-42580-2.