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 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 p0p1p2pn-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 7Trong 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) b) Giai đoạn sinh số 8 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õ. 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 • Tính thuận nghịch – Độ 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 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) • Phát tỏa cấu trúc thống kê của nguyên bản khắp bản mã – 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 0 1 2 3 4 5 6 7 Đầu vào 3 bit 0 1 0 0 1 2 3 4 5 6 7 1 1 0 Đầu ra 3 bit Lưu ý : Hộp S có tính thuận nghịch Lưu ý : Hộp P có tính thuận nghịch Đầu vào 4 bit 1 1 0 1 1 0 1 1 Đầu ra 4 bit • Đề 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 w bitL0 R0 Vòng 1 K1 L1 R1 F+ Kn Ln Rn F+Vòng n . . . . . . Ln+1 Rn+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 thuận vòng 1 K1 vòng 2 K2 vòng n Kn giao hoán nghịch Bản mã (64 bit) hoán đổi 32 bit Khóa 56 bit . . . giao hoán dịch vòng tráigiao hoán dịch vòng tráigiao hoán dịch vòng tráigiao hoán . . . Li- 1 mở rộng g/hoán hộp S giao hoán Ri-1 x K i x Li Ri --- 48 bit --- 48 bit --- 32 bit --- 32 bit  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 • Sử dụng 3 khóa và chạy 3 lần giải thuật DES – Mã hóa : C = EK3 [DK2 [EK1 [p]]] – Giải mã : p = DK1 [EK2 [DK3 [C]]] • Độ dài khóa thực tế là 168 bit – Không tồn tại K4 = 56 sao cho C = EK4 (p) • Vì sao 3 lần : tránh tấn công "gặp nhau ở giữa" – C = EK2 (EK1 (p))  X = EK1 (p) = DK2 (C) – 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 Mã hóa p1 C1 K Mã hóa C2 K Mã hóa CN K... Mã hóa Giải mã C1 p1 K Giải mã C2 p2 K Giải mã CN pN K... Giải mã p2 pNIV CN-1 CN-1IV • 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 khối bản mã về sau • 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 • 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 PSN : Packet-switching node Công cụ mã hóa đầu cuối 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) • Dùng mã hóa dữ liệu trong một phiên kết nối • Hủy bỏ khi hết phiên – Khóa chủ (lâu dài) • Dùng để mã hóa các khóa phiên, đảm bảo phân phối chúng một cách an toàn 51 • Khóa có thể được chọn bởi bên A và gửi theo đường vật lý đến bên B • Khóa có thể được chọn bởi một bên thứ ba, sau đó gửi theo đường vật lý đến A và B • Nếu A và B đã có một khóa dùng chung thì một bên có thể gửi khóa mới đến bên kia, sử dụng khóa cũ để mã hóa khóa mới • Nếu mỗi bên A và B đều có một kênh mã hóa đến một bên thứ ba C thì C có thể gửi khóa theo các kênh mã hóa đó đến A và B 1. Host gửi gói tin yêu cầu kết nối 2. FEP đệm gói tin; hỏi KDC khóa phiên 3. KDC phân phối khóa phiên đển 2 host 4. Gói tin đệm được truyền đi FEP = Front End Processor KDC = Key Distribution Center 54