AES (mã hóa)

Bách khoa toàn thư mở Wikipedia

AES
Bước SubBytes, một trong 4 bước của 1 chu trình.
Thông tin chung
Tác giả	Vincent Rijmen và Joan Daemen
Năm công bố	1998
Phát triển từ	Square (mã hóa)
Các thuật toán dựa trên	Crypton (mã hóa), Anubis (mã hóa), GRAND CRU
Chi tiết thuật toán
Khối dữ liệu	128 bít
Độ dài khóa	128, 192 hoặc 256 bít
Cấu trúc	Mạng thay thế-hoán vị
Số chu trình	10, 12 hoặc 14 (tùy theo độ dài khóa)
Phá mã
Tấn công khóa liên quan có thể phá vỡ AES 256 bít với 9 chu trình. Tấn công lựa chọn bản rõ có thể phá vỡ AES 192 và 256 bít với 8 chu trình; AES 128 bít với 7 chu trình (Ferguson et al, 2000).

Trong mật mã học, AES (viết tắt của từ tiếng Anh: Advanced Encryption Standard, hay Tiêu chuẩn mã hóa tiên tiến) là một thuật toán mã hóa khối được chính phủ Hoa kỳ áp dụng làm tiêu chuẩn mã hóa. Giống như tiêu chuẩn tiền nhiệm DES, AES được kỳ vọng áp dụng trên phạm vi thế giới và đã được nghiên cứu rất kỹ lưỡng. AES được chấp thuận làm tiêu chuẩn liên bang bởi Viện tiêu chuẩn và công nghệ quốc gia Hoa kỳ (NIST) sau một quá trình tiêu chuẩn hóa kéo dài 5 năm (Xem thêm: quá trình thiết kế AES).

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

Mục lục 1 Quá trình phát triển 2 Mô tả thuật toán 2.1 Bước AddRoundKey 2.2 Bước SubBytes 2.3 Bước ShiftRows 2.4 Bước MixColumns 2.5 Tối ưu hóa 3 An toàn 3.1 Tấn công kênh bên (Side channel attacks) 4 Xem thêm 5 Liên kết ngoài 5.1 Phần mềm thực hiện AES 6 Ghi chú 7 Tham khảo

[sửa] Quá trình phát triển

Thuật toán được dựa trên bản thiết kế Square có trước đó của Daemen và Rijmen; còn Square lại được thiết kế dựa trên Shark.

Khác với với DES sử dụng mạng Feistel, Rijndael sử dụng mạng thay thế-hoán vị. AES có thể dễ dàng thực hiện với tốc độ cao bằng phần mềm hoặc phần cứng và không đòi hỏi nhiều bộ nhớ. Do AES là một tiêu chuẩn mã hóa mới, nó đang được sử dụng rộng rãi trong nhiều ứng dụng.

[sửa] Mô tả thuật toán

Trong bước AddRoundKey, mỗi byte được kết hợp với một byte trong khóa con của chu trình sử dụng phép toán XOR (⊕).

Trong bước SubBytes, mỗi byte được thay thế bằng một byte theo bảng tra, S; bij = S(aij).

Trong bước ShiftRows, các byte trong mỗi hàng được dịch vòng trái. Số vị trí dịch chuyển tùy thuộc từng hàng.

Trong bước MixColumns, mỗi cột được nhân với một hệ số cố định c(x).

Mặc dù 2 tên AES và Rijndael vẫn thường được gọi thay thế cho nhau nhưng trên thực tế thì 2 thuật toán không hoàn toàn giống nhau. AES chỉ làm việc với khối dữ liệu 128 bít và khóa có độ dài 128, 192 hoặc 256 bít trong khi Rijndael có thể làm việc với dữ liệu và khóa có độ dài bất kỳ là bội số của 32 bít nằm trong khoảng từ 128 tới 256 bít.

Các khóa con sử dụng trong các chu trình được tạo ra bởi quá trình tạo khóa con Rijndael.

Hầu hết các phép toán trong thuật toán AES đều thực hiện trong một trường hữu hạn.

AES làm việc với từng khối dữ liệu 4×4 byte (tiếng Anh: state, khối trong Rijndael có thể có thêm cột). Quá trình mã hóa bao gồm 4 bước:

1. AddRoundKey — mỗi byte của khối được kết hợp với khóa con, các khóa con này được tạo ra từ quá trình tạo khóa con Rijndael.
2. SubBytes — đây là phép thế (phi tuyến) trong đó mỗi byte sẽ được thế bằng một byte khác theo bảng tra (Rijndael S-box).
3. ShiftRows — đổi chỗ, các hàng trong khối được dịch vòng.
4. MixColumns — quá trình trộn làm việc theo các cột trong khối theo một phép biến đổi tuyến tính.

Tại chu trình cuối thì bước MixColumns được thay thế bằng bước AddRoundKey

[sửa] Bước AddRoundKey

Tại bước này, khóa con được kết hợp với các khối. Khóa con trong mỗi chu trình được tạo ra từ khóa chính với quá trình tạo khóa con Rijndael; mỗi khóa con có độ dài giống như các khối. Quá trình kết hợp được thực hiện bằng cách XOR từng bít của khóa con với khối dữ liệu.

[sửa] Bước SubBytes

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

Xem thêm: Rijndael S-box.

[sửa] Bước ShiftRows

Các hàng được dịch vòng một số vị trí nhất định. Đối với AES, hàng đầu được giữ nguyên. Mỗi byte của hàng thứ 2 được dịch trái một vị trí. Tương tự, các hàng thứ 3 và 4 được dịch 2 và 3 vị trí. Do vậy, mỗi cột khối đầu ra của bước này sẽ bao gồm các byte ở đủ 4 cột khối đầu vào. Đối với Rijndael với độ dài khối khác nhau thì số vị trí dịch chuyển cũng khác nhau.

[sửa] Bước MixColumns

Mỗi cột được kết hợp lại theo một phép biến đổi tuyến tính khả nghịch. Mỗi khối 4 byte đầu vào sẽ cho một khối 4 byte ở đầu ra với tính chất là mỗi byte ở đầu vào đều ảnh hưởng tới cả 4 byte đầu ra. Cùng với bước ShiftRows, MixColumns đã tạo ra tính chất khuyếch tán cho thuật toán. Mỗi cột được xem như một đa thức trong trường hữu hạn và được nhân (mođun x⁴ + 1) với đa thức c(x) = 3x³ + x² + x + 2. Vì thế, bước này có thể được xem là phép nhân ma trận trong trường hữu hạn.

Xem thêm: Rijndael mix columns.

[sửa] Tối ưu hóa

Đối với các hệ thống 32 bít hoặc lớn hơn, ta có thể tăng tốc độ thực hiện thuật toán bằng cách chuyển đổi các bước SubBytes, ShiftRows và MixColumns thành dạng bảng. Mỗi bước sẽ tương ứng với 4 bảng với 256 mục, mỗi mục là 1 từ 32 bít và chiếm 4096 byte trong bộ nhớ. Khi đó, mỗi chu trình sẽ được bao gồm 16 lần tra bảng và 12 lần thực hiện phép XOR 32 bít cùng với 4 phép XOR trong bước AddRoundKey.

Trong trường hợp kích thước các bảng vẫn lớn so với thiết bị thực hiện thì các bước tra bảng sẽ thực hiện lần lượt với từng bảng theo vòng tròn.

[sửa] An toàn

Vào thời điểm năm 2006, dạng tấn công lên AES duy nhất thành công là tấn công kênh bên (side channel attack]). Cơ quan an ninh nội địa Hoa kỳ (NSA) đã xem xét các thuật toán lọt vào vòng chung kết cuộc thi AES và kết luận tất cả các thuật toán (bao gồm cả Rijndael) đủ an toàn để áp dụng cho các thông tin mật của chính phủ Hoa kỳ. Vào tháng 6 năm 2003, chính phủ Hoa kỳ tuyên bố AES có thể được sử dụng cho thông tin mật.

"Thiết kế và độ dài khóa của thuật toán AES (128, 192 và 256 bít) là đủ an toàn để bảo vệ các thông tin được xếp vào dạng MẬT. Các thông tin TỐI MẬT (top secret) sẽ phải dùng khóa 192 hoặc 256 bít. Các phiên bản thực hiện AES nhằm mục đích bảo vệ hệ thống an ninh hay thông tin quốc gia phải được NSA kiểm tra và chứng nhận trước khi sử dụng." - [5]

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

Phương pháp thường dùng nhất để tấn công các dạng mã hóa khối là thử các kiểu tấn công lên phiên bản có số chu trình thu gọn. Đối với khóa 128 bít, 192 bít và 256 bít, AES có tương ứng 10, 12 và 14 chu trình. Tại thời điểm năm 2006, những tấn công thành công được biết đến là 7 chu trình đối với khóa 128 bít, 8 chu trình với khóa 192 bít và 9 chu trình với khóa 256 bít^[1].

Một số nhà khoa học trong lĩnh vực mật mã lo ngại về an ninh của AES. Họ cho rằng ranh giới giữa số chu trình của thuật toán và số chu trình bị phá vỡ quá nhỏ. Nếu các kỹ thuật tấn công được cải thiện thì AES có thể bị phá vỡ. Ở đây, phá vỡ có nghĩa chỉ bất cứ phương pháp tấn công nào nhanh hơn tấn công kiểu duyệt toàn bộ. Vì thế một tấn công cần thực hiện 2¹²⁰ cũng được coi là thành công mặc dù tấn công này chưa thể thực hiện trong thực tế. Tại thời điểm hiện nay, nguy cơ này không thực sự nguy hiểm và có thể bỏ qua. Tấn công kiểu duyệt toàn bộ quy mô nhất đã từng thực hiện là do distributed.net thực hiện lên hệ thống 64 bít RC5 vào năm 2002 (Theo định luật Moore thì nó tương đương với việc tấn công vào hệ thống 66 bít hiện nay).

Một vấn đề khác nữa là cấu trúc toán học của AES. Không giống với các thuật toán mã hóa khác, AES có mô tả toán học khá đơn giản ^[2], ^[3]. Tuy điều này chưa dẫn đến mối nguy hiểm nào nhưng một số nhà nghiên cứu sợ rằng sẽ có người lợi dụng được cấu trúc này trong tương lai.

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

[sửa] Tấn công kênh bên (Side channel attacks)

Tấn công kênh bên không tấn công trực tiếp vào thuật toán mã hóa mà thay vào đó, tấn công lên các hệ thống thực hiện thuật toán có sơ hở làm lộ dữ liệu.

Tháng 4 năm 2005, Daniel J. Bernstein công bố một tấn công lên hệ thống mã hóa AES trong OpenSL gọi là ^[4]. Một máy chủ được thiết kế để đưa ra tối đa thông tin về thời gian có thể thu được và cuộc tấn công cần tới 200 triệu bản rõ lựa chọn. Một số người cho rằng tấn công không thể thực hiện được trên Internet với khoảng cách vài điểm mạng ^[5].

Tháng 10 năm 2005, Adi Shamir và 2 nhà nghiên cứu khác có một bài nghiên cứu minh họa một vài dạng ^[6] khác. Trong đó, một tấn công có thể lấy được khóa AES với 800 lần ghi trong 65 mili giây. Tấn công này yêu cầu kẻ tấn công có khả năng chạy chương trình trên chính hệ thống thực hiện mã hóa.

[sửa] Xem thêm

• Quá trình thiết kế AES
• Danh sách các ứng dụng dùng AES

[sửa] Liên kết ngoài

• The Rijndael Page (Forwards automaticaly to the AES Lounge use old version link to browse)
• The Rijndael Page (old version)
• Literature survey on AES
• The archive of the old official AES website
• FIPS PUB 197: the official AES standard (PDF file)
• John Savard's description of the AES algorithm

[sửa] Phần mềm thực hiện AES

• A Javascript AES calculator showing intermediate values
• Brian Gladman's BSD licensed implementations of AES
• Paulo Barreto's public domain C implementation of AES
• D.J. Bernstein's public-domain implementation of AES
• The GPL-licensed Nettle library also includes an AES implementation

[sửa] Ghi chú

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

[sửa] Tham khảo

1. ▲ Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner, and Doug Whiting, Improved Cryptanalysis of Rijndael, Fast Software Encryption, 2000 pp213–230 [1]
2. ▲ [2]
3. ▲ [3]
4. ▲ cache timing attack
5. ▲ [4]
6. ▲ cache timing attacks

• Nicolas Courtois, Josef Pieprzyk, "Cryptanalysis of Block Ciphers with Overdefined Systems of Equations". pp267–287, ASIACRYPT 2002.
• Joan Daemen and Vincent Rijmen, "The Design of Rijndael: AES - The Advanced Encryption Standard." Springer-Verlag, 2002. ISBN 3540425802.

Mã hóa khối sửa

Thuật toán: 3-Way | AES | Akelarre | Anubis | Blowfish | Camellia | CAST-128 | CAST-256 | CMEA | CS-Cipher | DEAL | DES | DES-X | FEAL | FOX | FROG | G-DES | GOST | Mã hóa Hasty Pudding | ICE | IDEA | Mã hóa khối Iraq | KASUMI | KHAZAD | Khufu và Khafre | Libelle | LOKI89/91 | LOKI97 | Lucifer | MacGuffin | Madryga | MAGENTA | MARS | MISTY1 | MMB | NewDES | Noekeon | RC2 | RC5 | RC6 | REDOC | Red Pike | S-1 | SAFER | SEED | Serpent | SHACAL | SHARK | Skipjack | SMS4 | Square | TEA | Triple DES | Twofish | XTEA

Thiết kế: Mạng Feistel | Chu trình tạo khóa | Product cipher | S-box | Mạng thay thế-hoán vị   Phá mã: Phá mã kiểu duyệt toàn bộ | Phá mã tuyến tính / Phá mã vi sai | Mod n | Related key | XSL   Tiêu chuẩn: AES | CRYPTREC | NESSIE   Khác: Hiệu ứng thác | Khối | IV | Độ lớn khóa | Chế dộ hoạt động mã hóa khối | Bổ đề Piling-up | Khóa yếu