Bài giảng Bảo mật thông tin - Bài 3: Mã hóa đối xứng hiện đại

Trình bày: Ths. Lương Trần Hy Hiến http://hienlth.info/hutech/baomatthongtin

1. Mã dòng

2. Mã khối

3. DES

4. Một số thuật toán mã khối khác

5. Các mô hình ứng dụng mã khối

6. Bố trí công cụ mã hóa

7. Quản lý trao đổi khóa bí mật

2

 Kích thước một đơn vị mã hóa: gồm k bít.

Bản rõ được chia thành các đơn vị mã hóa: P p0p1p2…pn-1 (pi: k bit)

 Một bộ sinh dãy số ngẫu nhiên: dùng một khóa K

ban đầu để sinh ra các số ngẫu nhiên có kích thước bằng kích thước đơn vị mã hóa:

StreamCipher(k)  S = s0s1s2 …sn-1 (si: k bit)

 Mỗi số ngẫu nhiên được XOR với đơn vị mã hóa

của bản rõ để có bản mã. C0 = p0  s0, c1 = p1  s1… ; C= c0c1c2… cn-1

3

 Quá trình giải mã được thực hiện ngược lại,

bản mã C được XOR với dãy số ngẫu nhiên S để cho ra lại bản rõ ban đầu:

 p0 = c0  s0, p1 = c1  s1, …

4

 Tiny RC4  RC4

5

 Đơn vị mã hóa của TinyRC4 là 3 bít.  TinyRC4 dùng 2 mảng S và T mỗi mảng gồm 8

số nguyên 3 bít.

 Khóa là một dãy gồm N số nguyên 3 bít.  Bộ sinh số mỗi lần sinh ra 3 bít để sử dụng

trong phép XOR.

 Quá trình sinh số của TinyRC4 gồm hai giai

đoạn:

6

Trong giai đoạn này, trước tiên dãy S gồm các số nguyên 3 bít từ 0 đến 7 được sắp thứ tự tăng dần. Sau đó dựa trên các phần tử của khóa K, các phần tử của S được hoán vị lẫn nhau đến một mức độ ngẫu nhiên nào đó.

Ví dụ: mã hóa bản rõ P = 001000110 (từ “bag‟) với khóa K gồm 3 số 2, 1, 3 (N=3). (xem giáo trình) 7

b) Giai đoạn sinh số

Trong giai đoạn này, các phần tử của S tiếp tục được hoán vị. Tại

mỗi bước sinh số, hai phần tử của dãy S được chọn để tính ra số k 3 bít

là số được dùng để XOR với đơn vị mã hóa của bản rõ.

8

Cơ chế hoạt động của RC4 cũng giống như TinyRC4 với các đặc tính sau:  Đơn vị mã hóa của RC4 là một byte 8 bít.  Mảng S và T gồm 256 số nguyên 8 bít  Khóa K là một dãy gồm N số nguyên 8 bít với N

có thể lấy giá trị từ 1 đến 256.

 Bộ sinh số mỗi lần sinh ra một byte để sử dụng

trong phép XOR.

(xem giáo trình)

9

• So với mã hóa dòng

– Mã hóa khối xử lý thông báo theo từng khối – Mã hóa luồng xử lý thông báo 1 bit hoặc 1 byte mỗi

lần

• Giống như thay thế các ký tự rất lớn ( 64 bit) – Bảng mã hóa gồm 2n đầu vào (n là độ dài khối) – Mỗi khối đầu vào ứng với một khối mã hóa duy nhất

– Độ dài khóa là n x 2n bit quá lớn • Xây dựng từ các khối nhỏ hơn • Hầu hết các hệ mã hóa khối đối xứng dựa trên

cấu trúc hệ mã hóa Feistel

• Tính thuận nghịch

10

• Mạng thay thế (S) - hoán vị (P) đề xuất bởi

Claude Shannon vào năm 1949

• Là cơ sở của các hệ mã hóa khối hiện đại • Dựa trên 2 phép mã hóa cổ điển

– Phép thay thế : Hộp S – Phép hoán vị : Hộp P • Đan xen các chức năng

– Khuếch tán : Hộp P (kết hợp với hộp S)

– Gây lẫn : Hộp S

• Làm phức tạp hóa mối quan hệ giữa bản mã và khóa

• Phát tỏa cấu trúc thống kê của nguyên bản khắp bản mã

0 1 2 3 4 5 6 7

Đầu vào 3 bit Đầu ra 3 bit

Lưu ý : Hộp S có tính thuận nghịch

Đầu vào 4 bit

Đầu ra 4 bit

1 0

Lưu ý : Hộp P có tính thuận nghịch

• Đề xuất bởi Horst Feistel dựa trên khái niệm hệ mã hóa tích hợp thuận nghịch của Shannon • Phân mỗi khối dài 2w bit thành 2 nửa L0 và R0 • Xử lý qua n vòng • Chia khóa K thành n khóa con K1, K2,..., Kn • Tại mỗi vòng i

– Thực hiện thay thế ở nửa bên trái Li-1 bằng cách XOR

nó với F(Ki, Ri-1)

– F thường gọi là hàm chuyển đổi hay hàm vòng – Hoán vị hai nửa Li và Ri

Nguyên bản (2w bit)

w bit

Vòng 1

. . .

Vòng n

Rn+1

Ln+1

Bản mã (2w bit)

 Được đặt tên của nhà mã hóa Horst Feistel của IBM và

được ứng dụng đầu tiên trong Lucifer cipher

 Mã hóa theo cấu trúc Feistel sử dụng chung thuật toán

cho việc giải mã và mã hóa

 Cấu trúc Feistel bao gồm nhiều vòng xử lý plaintext, mỗi vòng sẽ sử dụng kĩ thuật thay thế trước rồi kĩ thuật thay đổi vị trí.

 Input block tại mỗi vòng được chia làm hai nữa: L và R  Trong mỗi vòng, R không thay đổi, L sẽ thông qua một

xử lý tùy thuộc vào R và khóa.

 Sau đó hoán chuyển L và R. Nghĩa là R vòng trước là L

của vòng hiện tại

• Độ dài khối

– Khối càng lớn càng an toàn (thường 64 bit)

• Độ dài khóa

– Khóa càng dài càng an toàn (thường 128 bit)

• Số vòng

– Càng nhiều vòng càng an toàn (thường 16 vòng)

• Giải thuật sinh mã con

– Càng phức tạp càng khó phá mã

• Hàm vòng

– Càng phức tạp càng khó phá mã

• Ảnh hưởng đến cài đặt và phân tích

 Li, Ri nữa trái và nữa phải của chuỗi input ở

vòng thứ i

 Li = Ri-1  Ri = Li-1 ⊕ F(Ri-1, Ki)  F: hàm Feistel

 ⊕: XOR

 Là quá trình tương tự được thực hiện ngược lại  [A ⊕ B] ⊕ C = A ⊕ [B ⊕ C ]  A ⊕ A = 0  A ⊕ 0 = A

• Giống giải thuật mã hóa, chỉ khác

– Bản mã là dữ liệu đầu vào – Các khóa con được dùng theo thứ tự ngược lại

• Tại mỗi vòng kết quả đầu ra chính là các dữ liệu

đầu vào của quá trình mã hóa – Đối với quá trình mã hóa

• Li = Ri-1 • Ri = Li-1  F(Ri-1, Ki) – Đối với quá trình giải mã

• Ri-1 = Li • Li-1 = Ri  F(Li, Ki)

• DES (Data Encryption Standard) được công nhận

chuẩn năm 1977

• Phương thức mã hóa được sử dụng rộng rãi nhất • Tên giải thuật là DEA (Data Encryption Algorithm) • Là một biến thể của hệ mã hóa Feistel, bổ sung

thêm các hoán vị đầu và cuối

• Kích thước khối : 64 bit • Kích thước khóa : 56 bit • Số vòng : 16 • Từng gây nhiều tranh cãi về độ an toàn

23

24

Nguyên bản (64 bit)

giao hoán

Khóa 56 bit

giao hoán thuận

giao hoán

dịch vòng trái

K1 vòng 1

giao hoán

K2 vòng 2 dịch vòng trái

. . .

giao hoán

dịch vòng trái

Kn vòng n

hoán đổi 32 bit

Bản mã (64 bit)

giao hoán nghịch

<-----32 bit------>

Li- 1

<-----32 bit------> Ri-1

mở rộng g/hoán

--- 48 bit

x

K i

--- 48 bit

hộp S

giao hoán

--- 32 bit

x Ri

 DEA là thuật toán cài đặt DES  32 bit bên phải của 64 bit data được nhân rộng lên thành 48 bit. Bước này gọi là E-step (expansion permutation)  Chi tiết E-step:

 Chia 32 bit thành 8 nhóm, mỗi nhóm 4 bit  Mỗi nhóm thêm 1 bit bên trái và 1 bit bên phải mỗi nhóm 6 bit  Khóa 56 bit được chia làm 2 nữa. Mỗi nữa được dịch (shift) rồi kết hợp với khóa 56 bit để tạo 48-bit round key.

 48 bit output của E-step được XOR với 48 bit round key.  Output được chia thành 8 nhóm 6-bit

• Mỗi nhóm 6bit sẽ được thay thế bằng nhóm 4 bit. Quá trình thay thế này chứa trong S-box, xem hình slide kế

• Sau quá trình thay thế chúng ta có 32 bit • 32 bit này được hoán vị bằng quá trình bên trong P-

box, hình 4

• Kết quả này được XOR với 32 bit nữa trái ban đầu để

tạo đầu ra bên phải cho vòng kế tiếp.

• Mục tiêu của S-box là tạo diffusion (khuếch tán). Diffusion nghĩa là mỗi bit của plaintext phải ảnh hưởng càng nhiều bit của ciphertext càng tốt

• Mục tiêu của P-box là tạo confusion. Confusion ở

đây có nghĩa là mối quan hệ giữa khóa và ciphertext càng phức tạp càng tốt.

• Diffusion và confusion là hai yếu tố cốt lõi của mã hóa

theo block

 Như trong hình slide kế, mỗi input 48-bit được chia thành 8 nhóm, mỗi nhóm 6 bit. Mỗi nhóm này được xử lý qua 1 S-box cho ra 1 nhóm 4- bit. Vậy 8 S-box sẽ cho output 32bit.

 Mỗi một S-box trong 8 S-box sẽ chứa bảng

4x16. Bit đầu tiên và cuối cùng của nhóm 6 bit được giải mã để tìm ra dòng. 4 bit ở giữa đại diện cho cột.

 Mục tiêu của P-Box là hoán vị. Ở hình trên thì bit thứ 16 của input sẽ là bit số 1 của output.  Bit thứ 7 của input sẽ là bit thứ 2 của output.  Và tiếp theo như bảng mô tả  Chú ý chỉ số bắt đầu là 1.

 Khóa khởi đầu là 56bit, (8 byte, bit cuối là parity

bit)

 Đầu tiên 56bit khóa được thông qua hoán vị 1

(Permuation Choice 1)

 Bắt đầu mỗi vòng, khóa 56 bit được chia thành 2 nữa, mỗi nữa 28 bit. Shift vòng mỗi nữa 1 hoặc 2 bit

 Để tạo round key, ghép 2 nữa lại và áp dụng hoán vị 2 (permuation choice 2) để cho ra output 48 bit.

 Bước thay thế tạo diffusion mạnh. Nếu thay đổi 1 bit trong phần dữ liệu input thì sẽ tạo thay đổi khoảng 34 bit trong phần ciphertext

 Việc tạo roundkey giúp cho confusion mạnh. Nếu thay đổi 1 bit trong khóa thì sẽ thay đổi khoảng 35 bit trong ciphertext.

• Khóa 56 bit có 256 = 7,2 x 1016 giá trị có thể • Phương pháp vét cạn tỏ ra không thực tế • Tốc độ tính toán cao có thể phá được khóa

– 1997 : 70000 máy tính phá mã DES trong 96 ngày – 1998 : Electronic Frontier Foundation (EFF) phá mã DES bằng máy chuyên dụng (250000$) trong < 3 ngày

– 1999 : 100000 máy tính phá mã trong 22 giờ • Vấn đề còn phải nhận biết được nguyên bản  Vì vậy NIST đề nghị các tổ chức sử dụng Triple-

DES (3-DES)

 3DES  AES

39

[p]]] [C]]]

• Sử dụng 3 khóa và chạy 3 lần giải thuật DES [EK1 [DK3

– Mã hóa : C = EK3 – Giải mã : p = DK1

[DK2 [EK2

• Độ dài khóa thực tế là 168 bit

(p)

– Không tồn tại K4 = 56 sao cho C = EK4

• Vì sao 3 lần : tránh tấn công "gặp nhau ở giữa"

(C)

(p))  X = EK1

(p) = DK2

– C = EK2 (EK1 – Nếu biết một cặp (p, C)

• Mã hóa p với 256 khóa và giải mã C với 256 khóa • So sánh tìm ra K1 và K2 tương ứng • Kiểm tra lại với 1 cặp (p, C) mới; nếu OK thì K1 và K2 là khóa

• AES (Advanced Encryption Standard) được

công nhận chuẩn mới năm 2001

• Tên giải thuật là Rijndael (Rijmen + Daemen) • An toàn hơn và nhanh hơn 3DES • Kích thước khối : 128 bit • Kích thước khóa : 128/192/256 bit • Số vòng : 10/12/14 • Cấu trúc mạng S-P, nhưng không theo hệ Feistel

– Không chia mỗi khối làm đôi

 Electronic Codebook – ECB

 Mã hóa từng khối riêng rẽ

42

• Những khối lặp lại trong nguyên bản có thể thấy

được trong bản mã

• Nếu thông báo dài, có thể – Giúp phân tích phá mã – Tạo cơ hội thay thế hoặc bố trí lại các khối

• Nhược điểm do các khối được mã hóa độc lập • Chủ yếu dùng để gửi thông báo có ít khối

– Ví dụ gửi khóa

 Cipher Block Chaining – CBC

 Khối nguyên bản hiện thời được XOR với khối bản mã trước đó

44

IV p2 pN p1

CN-1

Mã hóa Mã hóa Mã hóa K K K

...

Mã hóa C2 CN

Giải mã

Giải mã Giải mã K K K

...

CN-1

pN p1

p2 Giải mã

• Mỗi khối mã hóa phụ thuộc vào tất cả các khối nguyên

bản trước đó – Sự lặp lại các khối nguyên bản không thể hiện trong bản mã hóa – Thay đổi trong mỗi khối nguyên bản ảnh hưởng đến tất cả các

• Cần 1 giá trị đầu IV bên gửi và bên nhận đều biết

– Cần được mã hóa giống khóa – Nên khác nhau đối với các thông báo khác nhau

• Cần xử lý đặc biệt khối nguyên bản không đầy đủ cuối

cùng

• Dùng mã hóa dữ liệu lớn, xác thực

khối bản mã về sau

• Giải pháp hữu hiệu và phổ biến nhất chống lại các mối đe dọa đến an toàn mạng là mã hóa

• Để thực hiện mã hóa, cần xác định

– Mã hóa những gì – Thực hiện mã hóa ở đâu • Có 2 phương án cơ bản

– Mã hóa liên kết – Mã hóa đầu cuối

47

• Công cụ mã hóa được sắp đặt ở 2 đầu của mọi

liên kết có nguy cơ bị tấn công

• Đảm bảo an toàn việc lưu chuyển thông tin trên

tất cả các liên kết mạng

• Các mạng lớn cần đến rất nhiều công cụ mã hóa • Cần cung cấp rất nhiều khóa • Nguy cơ bị tấn công tại mỗi chuyển mạch

– Các gói tin cần được mã hóa mỗi khi đi vào một

chuyển mạch gói để đọc được địa chỉ ở phần đầu

• Thực hiện ở tầng vật lý hoặc tầng liên kết

• Quá trình mã hóa được thực hiện ở 2 hệ thống

đầu cuối

• Đảm bảo an toàn dữ liệu người dùng • Chỉ cần một khóa cho 2 đầu cuối • Đảm bảo xác thực ở mức độ nhất định • Mẫu lưu chuyển thông tin không được bảo vệ

– Các phần đầu gói tin cần được truyền tải tường minh

• Thực hiện ở tầng mạng trở lên

– Càng lên cao càng ít thông tin cần mã hóa và càng an toàn nhưng càng phức tạp với nhiều thực thể và khóa

Công cụ mã hóa đầu cuối

PSN : Packet-switching node

Công cụ mã hóa liên kết

• Vấn đề đối với mã hóa đối xứng là làm sao phân

phối khóa an toàn đến các bên truyền tin – Thường hệ thống mất an toàn là do không quản lý tốt

việc phân phối khóa bí mật

• Phân cấp khóa

– Khóa phiên (tạm thời)

– Khóa chủ (lâu dài)