Báo cáo bài tập lớn tìm hiểu về giải thuật mã hoá khoá bí mật aes

Vào ngày 26 tháng 11 năm 2001, Ấn bản Tiêu chuẩn Xửlý Thông tin Liên bang 197 đã công bố một dạng tiêu chuẩn hoá của thuật toán Rijndael làm tiêu chuẩn mới cho mã hoá.. - Bước 3: Các vòn

H C VI Ọ ỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

KHOA AN TOÀN THÔNG TIN - -

BÁO CÁO BÀI TẬP LỚN

KHOÁ BÍ MẬT AES

Lớp : D20AT-01_G3

Trịnh Huy Cường - B20DCAT025

Nguyễn Quý Dũng - B20DCAT031

Hoàng Đình Dương - B20DCAT033

Nguyễn Quý Dương - B20DCAT034

Hà Nội, ngày 30 tháng 9 năm 2022

I Giới thi u ệ

Vào ngày 2 tháng 1 năm 1997, Viện Tiêu chuẩn và Công nghệ Quốc gia (NIST)

đã tổ chức một cuộc thi cho một tiêu chuẩn mã hoá mới Tiêu chuẩn trước đó, DES, không còn phù hợp để bảo mật Nó đã trở thành tiêu chuẩn kể từ ngày 23 tháng 11 năm 1976 Sức mạnh tính toán đã tăng lên rất nhiều kể từ đó và thuật toán DES không còn được coi là an toàn nữa Vào năm 1998, DES đã bị bẻ khoá trong vòng chưa đầy

ba ngày bởi một máy tính được chế tạo đặc biệt có tên là DES cracker Công cụ bẻ khoá DES được Electronic Frontier Foundation tạo ra với giá chưa đến 250.000 đô la

và đã giành chiến thắng trong Cuộc thi RSA DES II-2 Sau khi tổ chức cuộc thi trong

ba năm, thuật toán Rijndael đã được NIST lựa chọn Vào ngày 26 tháng 11 năm 2001,

Ấn bản Tiêu chuẩn Xửlý Thông tin Liên bang 197 đã công bố một dạng tiêu chuẩn hoá của thuật toán Rijndael làm tiêu chuẩn mới cho mã hoá Tiêu chuẩn này được gọi

là Tiêu chuẩn Mã hoá Nâng cao (Advanced Encryption Standard) và hiện vẫn là tiêu chu n cho viẩ ệc mã hoá

AES (Advanced Encryption Standard) được xây dựng dựa trên hệ mã hoá Rijndael được phát triển và công bố năm 1998 bởi 2 nhà mật mã học người Bỉ là Joan Daemen và Vincent Rijmen AES là dạng mã hoá khối, với khối dữ liệu có kích thước

128 bit và khoá bí mậ ới kích thước có thể là 128, 192, hoặc 256 bit AES đượt v c thiết

k dế ựa trên mạng hoán vị-thay th (Substitution-ế permutation network) và nó có thể cho tốc độ thực thi cao khi cài đặt trên cả ph n cầ ứng và phần mềm Đặc bi t, giệ ải thuật AES đã được tích hợp vào các bộ vi x ử lý gần đây của hãng Intel dướ ại d ng t p ậ lệnh AES-NI, giúp tăng đáng kể ốc độ thực thi các thao tác mã hoá và giải mã dựa t trên AES

AES vận hành dựa trên một ma trận vuông 4x4, được gọi là state ạng thái) Ma (tr

trận này gồm 16 phần tử, mỗi phần tử là 1 byte dữ ệu li

State được khởi trị là khối 128 bit bản rõ và qua quá trình biến đổi sẽ chứa khối

128 bit bản mã ở đầu ra Như đã đề ậ c p, AES h ỗ trợ 3 kích thước khoá và kích thước

của khoá quyết định s ố vòng lặp c n th c hiầ ự ện để chuyển đổ ản rõ thành bản mã Sối b vòng lặp AES cần thực hiện theo kích thước khoá như sau:

- 10 vòng lặp với khoá 128 bit;

- 12 vòng lặp với khoá 192 bit;

- 14 vòng lặp với khoá 256 bit

Mỗi vòng bao gồm một số bước xử lý, trong đó có một bước phụ thuộc vào chính khoá mã hoá Một tập hợp các vòng đảo ngược được áp dụng để ến đổ ản mã trở bi i b lại bản rõ ban đầu bằng cách sử ụng cùng một khoá mã hoá d

b0 b4 b8 b3

b1 b5 b9 b7

b2 b6 b10 b11

b3 b7 b11 b13

II Thuật toán AES

1 Quá trình mã hoá

Giải thu t AES th c hiậ ự ện mã hoá khối dữ liệu bản rõ, được minh ho bạ ằng các bước x ửlý, vòng lặp như hình vẽ dưới đây:

D u bữ liệ ản rõ ở ạ d ng text s ẽ được chuy n vể ề mã hex và được bi u diể ễn thông qua ma trận 4x4 Ví dụ input_text = ‘This is a sample'

Giải thu t AES (Advanced Encryption Standard) gậ ồm các bước xử lý chính như sau:

- Bước 1: M rở ộng khoá thực hi n việ ệc sinh các khoá vòng (Round key) dùng trong các vòng lặp từ khoá chính AES sử dụng thủ tục sinh khoá Rijndael

- Bước 2: Vòng khở ại t o th c hiự ện hàm AddRoundKey, trong đó mỗi byte trong state được k t h p vế ợ ới khoá vòng sử ụng phép XOR d

- Bước 3: Các vòng lặp chính, trong đó mỗi vòng thực hiện 4 hàm biến đổi dữ liệu như sau:

+ SubBytes là hàm thay thế phi tuyến tính, trong đó mỗi byte trong state được thay th b ng mế ằ ột byte khác sử ụ d ng b ng tham chi u S-box; ả ế

+ ShiftRows là hàm dịch dòng, trong đó mỗi dòng trong state được dịch một số bước theo chu k ; ỳ

+ MixColumns là làm trộn các cột trong state, kết hợp 4 bytes trong mỗi cột + AddRoundKey là hàm kết hợp state với khoá vòng sử ụng phép XOR d

- Bước 4: Vòng lặp cuối tương tự các vòng lặp chính, nhưng chỉ thực hiện 3 hàm biến

đổ ữ ệi d li u, bao gồm SubBytes, ShiftRows và AddRoundKey

2 M r ở ộng khoá (sinh khoá vòng)

Bước m rở ộng khoá AES sinh các khoá vòng cho các vòng lặp x ử lý dữ liệu s ử

d ng th tụ ủ ục sinh khoá Rijndael như biểu diễn trên hình

Thủ tục sinh khoá Rijndael nhận đầu vào là khoá chính AES và xuất ra một khoá vòng sau mỗi vòng lặp

Một vòng lặp của thủ tục sinh khoá Rijndael gồm các khâu sau:

- Rotword thực hiện quay trái 8 bit từng t 32 bit l y t ừ ấ ừ khoá chính;

Ví dụ: Khoá chính dạng text : “Can you pass it?” được chuyển về dạng Hex biểu diễn dướ ại d ng ma tr n, m i t ậ ỗ ừcó độ dài 4 byte (32 bit) ứng với m t c t c a ma tr n: ộ ộ ủ ậ

Bốn t ừ khoá gốc được c ng tr c ti p ộ ự ế vào phép AddRoundkey ban đầu Phép rotword thực hiện quay trái 8 bít (1 byte) từng từ Ví dụ:

- SubBytes là hàm thay thế phi tuyến tính các byte trong khoá tương tự hàm SubBytes của quá trình mã hoá AES trình bày trong m c 3 ụ

- Rcon thực hi n việ ệc tính toán giá trị Rcon(i) = x (i-1)mod (x8 + x4 + x3 + x + 1) Rcon là một mảng số Mảng này gồm 10 phần tử ứng với 10 vòng trong AES Bốn byte c a m t ph n t ủ ộ ầ ử Rcon(i) là (RC(i), 00, 00, 00) với RC(i) được tính theo

công thức ở trên

Ví dụ ới i=1, ta có phép chia dư v x0 / ( x8+ x4 + x3 + + 1) = 0 dư x 1

=> RC(1) = 1

Với i = 10 ta có:

Phần dư = x5 + x4 + x + x 2 được th c hiện trong trườự ng GF(28) do đó được đưa về

d ng hex: 0011 0110 = 36ạ 2 16

=> RC(10) = 36

Tương ự t với các giá trị I còn lại ta có mảng sau:

- ShiftRows là hàm dịch dòng tương tự hàm ShiftRows của quá trình mã hoá AES

C y p

a o a i

n u s t

s ?

63 79 70 20

61 6f 61 69 6e 75 73 74

20 20 73 3f

20

69

74

3f

69

74 3f

20

SubBytes

Như đã đề cập, AES sử dụng 4 hàm xử lý để ến đổ bi i dữ liệu, bao gồm SubBytes, ShiftRows, MixColumns và AddRoundKey Mục này trình bày chi tiết về các hàm này

a) Hàm SubBytes

Hàm SubBytes thay th m i byte trong ma tr n ế ỗ ậ state ởb i 1 byte trong Rijndael S-box, hay b = S(aij ij) như minh hoạ trên hình:

S-box là mộ ảt b ng tham chi u phi tuyế ến tính, đượ ạc t o ra bằng phép nhân nghịch đảo một s ố cho trước trong trường GF(28)

Bảng S-box

Ví dụ:

54 20 61 6d

68 69 20 70

69 73 73 6c

73 20 61 65

20 b7 ef 3c

45 f9 b7 51 f9 40 40 50

40 b7 ef 4d

ShiftRows

b) Hàm ShiftRows

Hàm ShiftRows được minh ho ạ như hình dưới đây:

Hàm ShiftRows dịch các dòng của ma tr n ậ state theo chu k ỳ sang trái theo nguyên tắc:

+ Hàng số 0 giữ nguyên

+ Hàng số 1 dịch 1 byte sang trái

+ Hàng số 2 dịch 2 byte sang trái

+ Hàng số 3 dịch 3 byte sang trái

Ví dụ :

c) Hàm MixColumns

Hàm MixColumns nhân mỗi cột của ma trận state ới mv ột đa thức c(x), như minh

ho ạ trên hình

20 b7 ef 3c

45 f9 b7 51

f9 40 40 50

40 b7 ef 4d

20 b7 ef 3c f9 b7 51 45

40 50 f9 40 4d 40 b7 ef

Hàm MixColumns nhân mỗi cột của ma trận state ới mv ột đa thức c(x), như minh

ho ạ trên hình Đa thức này được tính theo công thức: c(x) = 3x3+ x2+ x +2 Biến đổi này có thể được biểu diễn như một phép nhân ma trận như sau:

Điều này cũng có thể ểu là: hi

b = 2a + 3a +1a0 0 1 2 + 1a3

b = 1a + 2a +3a1 0 1 2 + 1a3

b = 1a + 1a +2a2 0 1 2 + 3a3

b = 3a + 1a +1a3 0 1 2 + 2a3

Vì phép toán này được thực hiện trong trường Galois của Rijndael, nên phép nhân ở đây thực chất là một quá trình phức tạp

Ví dụ:

Tính b0 = {02 * 20} {03*f9} {01*40} {01*4d}

Xét {02*20} :

0216 = 0000 00102

2016 = 0010 00002

Coi các chữ số trong hệ nhị phân ứng với các hệ ố ủa đa thức: s c

X + X + X + X + X + X + X + 1 7 6 5 4 3 2

-> 0000 0010 = X

0010 0000 = X 5

Nhân 2 đa thức vừa tìm ta được : X * X = X = 0100 0000 -> {02*20} = 0100 0000 5 6

Nếu đa thức có bậc là 8 thì chuyển X = X + X + X + 1, khi c ng 2 ph n t gi ng 8 4 3 ộ ầ ử ố nhau thì triệt tiêu X + X = 0 Làm tương tự cho các phép còn lại :

{03*19} = 1101 0111

{01*40} = 0100 0000

2 3 1 1

1 2 3 1

1 1 2 3

3 1 1 2

20 f9

40 4d

b0

b1

b2

b3

MixColumns

{01*4d} = 0100 1101

Tiếp tục tính phép XOR:

01000000 + 11010111

01000000

01001101

= 10011010

=> b = 10011010 = 9a 0 2

b = 11100010 = e2 1 2

b = 11011110 = de 2 2

b = 00010000 = 10 3 2

d) Hàm AddRoundKey

Hàm AddRoundKey kết h p m i byte c a ma trợ ỗ ủ ận state ớv i một byte tương ứng

của khoá vòng sử ụng phép (XOR), như minh hoạ d  trên hình

Ví dụ: AddRoundKey

4 Quá trình giải mã

20

f9

40

4d

9a e2

de

10

54 20 61 6d

68 69 20 70

69 73 73 6c

73 20 61 65

63 79 70 20

61 6f 61 69 6e 75 73 74

20 20 73 3f

37 59 11 4d

09 06 41 19

07 06 00 18

53 00 12 5a

Quá trình giải mã trong AES cũng gồm các bước xử lý tương tự như quá trình mã hoá Hình minh hoạ dưới đây biểu diễn quá trình giải mã đối sánh với quá trình mã hoá trong AES Theo đó, ngoài bước Mở rộng khoá, quá trình giải mã gồm Vòng khởi tạo thực thi hàm AddRoundKey, Các vòng giải mã và Vòng cuối để chuyển đổi khối

mã thành khối rõ

Điểm khác biệt chính của quá trình giải mã so với quá trình mã hoá là các hàm đảo được s d ng, bao gồm InvSubBytes, InvShiftRows và InvMixColumns tương ử ụ ứng thay cho các hàm SubBytes, ShiftRows và MixColumns Hàm InvSubBytes thay thế phi tuyến tính các byte của ma trận state s dụng b ng S-ử ả box đảo

Bảng S-box đảo

Hàm InvShiftRows dịch các byte củ ừng dòng trong ma trậa t n state sang phải theo cùng nguyên tắc với ShiftRows:

+ Hàng 0 giữ nguyên

+ Hàng 1 dịch phải 1 byte

+ Hàng 2 dịch phải 2 byte

+ Hàng 3 dịch phải 3 byte

Hàm InvMixColumns nhân các cộ ủt c a ma tr n ậ state ới đa thức c(x) đảo, có thể được v

bi u diể ễn như sau:

Hoặc:

b 14a + 11a +13a + 9a0= 0 1 2 3

b = 9a + 14a +11a1 0 1 2 + 13a3

b = 13a + 9a +14a2 0 1 2 + 11a3

b = 11a + 13a +9a3 0 1 2 + 14a3

Cách tính chi tiết tương tự như hàm MixColumns đã trình bày bên trên

III Ưu điểm và nhược điểm của AES

1 Độ an toàn của AES

Khi s t ố ừ khoá lớn hơn 6, không tồ ại phương pháp tấn công n t

nào hiệu quả hơn phương pháp thử sai

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

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

- Trên thự ế, cho đếc t n hiện nay AES được coi là phương pháp mã hoá tương đối

an toàn, nó chỉ được tấn công bởi phương pháp tấn công kênh bên tức là tấn công trực tiếp vào hệ thống th c hi n thuự ệ ật toán có sơ hở mà không tấn công được vào bản thân thuật toán

2 Các điểm yếu

Về an ninh của AES thì các nhà khoa học đánh giá là chưa cao 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 có độ phức tạp 2 120cũ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ã hoá khác, AES có mô tả toán học khá đơn giản 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

3 Các dạng tấn công vào AES

Mặc dù được coi là phương pháp mã hoá tương đối an toàn, song AES hay rất nhiều các thuật toán khác đều không phải là an toàn tuyệt đối V n t n t i nhẫ ồ ạ ững điểm

yếu và những cách tấn công khai thác điểm y u c a AES ế ủ

• Side- channel attack

- Side Channel (Kênh kề) được định nghĩa là các kênh đầu ra không mong muốn từ một hệ thống

- Tấn công kênh bên hay còn gọi là Tấn công kênh kề là loại tấn công dễ thực hiện trong các loại tấn công mạnh chống lại quá trình triển khai mã hoá, và mục tiêu của loại tấn công này là phân tích các nguyên tố, các giao thức, modul và o các thiết bị trong môi trường hệ thống

- 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ã hoá 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

- Phân loại:

Tấn công thời gian

Tấn công dựa vào lỗi

Tán công phân tích năng lượng

Tấn công phân thích điện từ

• Known attack

Tuy chưa thực sự có một cuộc tấn công thực tế nào nhưng Known attack cũng là một trong những hiểm hoạ tiềm tàng cần lư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 AES trong OpenSL oá gọi là cache timing attack 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

- 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 hoạ một vài dạngcache timing attackkhác Trong đó, một tấn công có thể lấy được khoá 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ã hoá

- 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

5 Phương pháp phòng chống

Các chuyên gia bảo mật cho rằng AES an toàn khi được triển khai đúng cách Tuy nhiên, các khóa mã hóa AES cần được bảo vệ Ngay cả những hệ thống mật mã mở rộng nhất cũng có thể dễ bị tấn công nếu tin tặc giành được quyền truy cập vào khóa mã hóa

Để đảm bảo tính bảo mật của các khóa AES:

• Sử d ng m t kh u m nh ụ ậ ẩ ạ

• Sử dụng trình quản lý mật kh u ẩ

• Triển khai và yêu cầu xác thực đa yế ốu t ( MFA )

• Triển khai tường lửa và phần m m ch ng ph n mề ố ầ ềm độc h ại

• Tiến hành đào tạo nâng cao nhận thức về bảo mật để ngăn nhân viên trở thành nạn nhân của các cuộ ấn công lừa đảo và kỹc t thuật xã hội

6 Các ứng dụng của chuẩn h oá mật mã AES

• AES là chuẩn mã hoá duy nhất đã được phát hành rộng rãi, được NSA chấp nhận

và được dùng để bảo vệ thông tin chính phủ ở mức cao cấp nhất hiện nay Chính vì

vậy, AES được s d ng trong viử ụ ệc mã hoá dữ liệu của chính phủ ạ t i nhi u qu c gia ề ố trên thế giới nhằm bảo đảm an toàn tối đa cho các tài liệu mật

• Trong Thông tư số 01/2011/TT-BTTTT ngày 04/01/2011 của B ộ Thông tin và Truyền thông Công bố Danh mục tiêu chuẩn k thu t v ng dỹ ậ ề ứ ụng công nghệ thông tin trong cơ quan nhà nước quy định Khuyến nghị áp dụng tiêu chuẩn AES và được

xếp vào nhóm Tiêu chuẩn v ề an toàn thông tin

Bên cạnh ứng dụng trong việc đảm bảo an ninh của các tài liệu chính phủ, AES cũng được áp dụng nhiều trong các linh vực khác nhau Cụ thể:

• Ứng dụng cho tất cả người dùng phổ thông trong quá trình giải mã dữ liệu bằng cách truy cập vào trang web AES Encryption, nhập dữ liệu và áp mã khoá Tuy nhiên, đây chỉ là phương pháp áp dụng cho các tác vụ thông thường và tính bảo mật thường không cao

• Mã hoá thông tin trên phần mềm với các ngôn ngữ ập trình như l

C/C++, Java hay Assembler AES h ỗ trợ ấ r t nhiều cho các hệ điều hành như Linux hay Windows

• AES áp dụng cho các thiết bị phần cứng bao gồm dòng thiết bị dựa trên hoạt động của hệ vi xử lý và dòng thiết bị cắm qua cổng USB hoặc thẻ thông minh Smart Card

• Ứng dụng trong truyền thông tin qua Internet thông qua kết nối HTTPS: Dữ liệu sẽ được mã hoá và giải mã thông qua thuật toán AES, thông tin được bảo mật tốt hơn khi

so sánh với kết nối HTTP Bên cạnh đó, wifi hiện nay cũng được ứng dụng thuật toán AES, khi kết hợp với giao thức WPA2, giao tiếp này trở nên an toàn, hiệu quả hơn nhiều và ngăn chặn tấn công trung gian Bên cạnh đó, AES cũng được sử dụng để mã hoá wifi trên router, kết hợp với giao thức phổ biến WPA2 được gọi là AES/WPA2 AES còn được sử dụng nhằm hỗ trợ mã hoá SSL

IV K t lu n ế ậ

Bài báo cáo đã trình bày về giải thuật mã hoá khoá bí mật AES: giải thuật sinh khoá phụ, mã hoá, giải mã, các điể m y ếu, các dạ ng t ấn công vào AES và cách phòng chống Cụ thể gồm các phần:

- Giớ i thi u v ệ ề giả i thu ật mã hoá AES

- Trình bày kiến trúc, quá trình mã hoá AES

- Giả i thu ật sinh khoá phụ (mở r ộng khoá) AES và chi tiết các hàm

- Độ an toàn, điể m y ếu, cách tấn công và phòng chống đố i với AES

- ng d ng c a chu Ứ ụ ủ ẩn hóa thuật toán AES