Hệ mật mã khối và các thuật toán mã hóa khối kinh điển: DES - 2DES - 3DES

Trong bài viết trước, mình đã trình bày về cơ chế hoạt động của giao thức trao chuyển khóa đối xứng Needham - Schroeder. Khóa đó là "khóa phiên". Vậy "khóa" đó là cái j và được tạo ra như thế nào, độ phức tạp của việc phá giải cũng như ứng dụng của nó ở đâu? Vân vân và mây mây. Tất cả những điều đó sẽ được mình trình bày trong bài viết này.

Bài viết này mình sẽ giới thiệu về Hệ mật mã khối. Sau đó sẽ trình bày thuật toán mã hóa kinh điển DES và các mở rộng của nó như 2-DES và 3-DES; kèm theo đó là ưu nhươc điểm cũng như cách thức tấn công để phá mã. Sau cùng mình sẽ nêu ra những ứng dụng của Hệ mã khối cũng như DES.

Có lẽ ko có một chuyên ngành nào của Công nghệ thông tin mà sử dụng nhiều Toán như Lý thuyết Mật mã học trong An Toàn Thông Tin cả, mà lại toàn Toán khó mới đểu chứ! Đến bây giờ khi ngồi tự học Cryptography, mình mới thấy sức mạnh thật sự của môn Số Học hồi cấp 2. Hồi trước khi Sư Phụ dạy trên lớp, mình cũng đã thấy được sự bá đạo của các định lý Số Học như Fermat (nhỏ), Euler, Wilson, "Phần dư Trung Hoa" rồi; nhưng có lẽ bây giờ mới tự nhiên thấy được sự ảo diệu của các định lý này. Các bài toán (NP) khó được tìm ra, nếu ko giải được thì ta vẫn có thể sử dụng được nó! Nghe có vẻ xàm xí, đã ko giải được thì biết áp dụng như thế nào? Đúng vậy; chính vì cả thế giới ko thể giải được, thế nên "hacker cũng ko thể giải được nốt"! Do đó, nếu ta sử dụng nó vào việc mã hóa thì chỉ có ta mới biết Backdoor để phá giải được mã thôi! Toán Học thật ảo diệu và thâm sâu phải ko!

Hệ mật mã khối (Block Cipher).

Mã khối là cái j? Thế có mã "ko khối" ko? Đương nhiên là có mã "ko khối" nhé. Mã "ko khối" là loại thuật toán mã hóa mà tiến hành mã hóa riêng lẻ từng ký tự trong bản rõ (plain text) thành bản mã (cipher text). Còn "mã khối" là loại thuật toán mã hóa tiến hành mã hóa 1 lúc tất cả các ký tự trong 1 khối của 1 văn bản được chia ra thành nhiều khối nhỏ.

Các loại mật mã "ko khối" được gọi chung là "hệ mật mã cổ điển". Ví dụ tiêu biểu và cổ xưa bậc nhất có lẽ là "Mật mã Caesar" (Caesar là tên của Pharaoh Xê-da); thực hiện mã hóa thay thế từng ký tự bằng cách tịnh tiến bảng chữ cái từ chữ a thành chữ n. Bạn có thể sử dụng Regex (Regular Expression) được hỗ trợ trong tr (translate) command của Linux để mã hóa cũng như giải mã theo ý bạn như sau:

tr a-zA-Z n-za-mN-ZA-M

Mã khối thì khác. Thay vì mã hóa từng ký tự, thuật toán sẽ chia văn bản thành từng cụm vài ký tự một; rồi mã hóa 1 phát toàn bộ mọi ký tự trong từng cụm đó. Do đó, có thể thấy rằng "mã khối" phức tạp và khó phá hơn "mã cổ điển". Tuy nhiên như vậy vẫn là chưa đủ. Để đánh giá tính an toàn của một hệ mã khối, ta cần dựa vào các điều kiện:

• Kích thước của khối mã hóa phải đủ lớn để ngăn chặn việc phá giải tấn công bằng phương pháp "thống kê" như ở mã cổ điển. Tuy nhiên nếu kích thước khối càng lớn thì tỷ lệ thuận theo đó sẽ là thời gian mã hóa lại càng lâu.
• Không gian khóa phải đủ lớn để việc Bruteforce attack (vét cạn không gian khóa) gần như là bất khả thi. Tuy nhiên kích thước khóa lại phải đủ bé để đảm bảo mã hóa cũng như giải mã nhanh gọn.

Ở đây xuất hiện 1 khái niệm là "trade-off"; có thể hiểu nôm na là "đánh đổi". Khái niệm này có mặt ở hầu hết mọi khía cạnh trong cuộc sống. Để đạt được hiệu quả ở một khía cạnh này, ta bắt buộc phải đánh đổi bằng sự hiệu quả của một hoặc một vài khía cạnh khác! Còn thuật ngữ này, công nhận là mình chỉ thấy có ở Lab Sư Phụ mình là hay dùng. Sư Phụ dùng nhiều, nên các anh Nghiên cứu sinh cũng dùng nhiều, rồi đến bọn sinh viên như mấy đứa chúng mình cũng nghe quen và hay dùng.

Thế gian an đắc song toàn pháp - Bất phụ Như Lai, bất phụ khanh?

Đừng lo, ngoài câu thơ (xuất phát từ 1 điển cố buồn) trên, chúng ta còn có câu "Thế gian tự hữu song toàn pháp - Bất phụ mộng tưởng, bất phụ khanh" nữa. 😁

Thuật toán DES (Data Encryption Standard).

Chuẩn mật mã DES là hệ mã được giới thiệu bởi Cục An ninh quốc gia Mỹ (NSA); là hệ mã được sử dụng rộng rãi nhất trong nhiều năm liền trước khi chuẩn mật mã nâng cao AES được công bố. Trong thời gian đó, DES cũng tạo ra khá nhiều nghi ngờ tranh cãi xung quanh việc thiết kế của thuật toán đảm bảo tính bảo mật, chiều dài khóa ngắn, cũng như việc NSA có thể còn che giấu Backdoor để đơn giản hóa quá trình phá giải mã.

Tổng quan.

Đầu vào và đầu ra của DES là 1 chuỗi bit độ dài 64, sử dụng một khóa có độ dài 64 bit làm khóa chính. Tuy nhiên thực tế, chỉ có 56 bit của khóa là được sử dụng, 8 bit còn lại chỉ đóng vai trò kiểm tra tính chẵn/lẻ. Do đó "độ dài thực tế" của khóa chỉ là 56 bit.

Sơ đồ thuật toán sinh mã DES với 16 vòng lặp (sách của Sư Phụ)

Từ hình trên, ta thấy DES được cấu tạo bởi 16 vòng lặp; mỗi lần lặp sẽ thực hiện 1 phép toán logic với hàm logic f như trong hình. Hàm f này có cấu trúc phức tạp sẽ trình bày sau, nhưng nó chứa một phép toán logic XOR các thành phần con của bản rõ (plain text) sau khi được "số hóa" bởi tác tử IC. 2 tác tử IC và IC^-1 sẽ chỉ có tác dụng biến đổi văn bản thành chuỗi nhị phân để máy tính hiểu được.

Có thể thấy rằng trong mỗi lần lặp, chuỗi bit sẽ được cắt đôi, mỗi nửa sẽ có độ dài 32 bit. Nửa đầu của chuỗi mới sẽ là nửa sau của chuỗi cũ (L_i = R_{i - 1}); nửa sau của chuỗi mới sẽ là kết quả của việc thực hiện logic XOR với kết quả sinh ra từ hàm f:

R_i = L_{i - 1} 𐌈 f(R_{i - 1}, K_i)

Có thể thấy rằng mỗi vòng lặp sẽ thực hiện với một giá trị K_i khác nhau. Các giá trị này sẽ được tạo ra từ khóa chính của DES bằng thuật toán sinh khóa con, và độ dài của chúng là giống nhau và đều bằng 48 bit. Đây là lưu đồ mô tả "thuật toán sinh khóa con" của DES.

Thuật toán lập lịch Khóa con.

Key scheduler của DES (Wikipedia)

Ban đầu, từ 64 bit của Khóa chính, PC1 (Permuted Choice 1) sẽ chọn 56 bit để sử dụng, loại bỏ 8 bit. 56 bit này được chia làm 2 phần bằng nhau và xử lý độc lập. Sau mỗi vòng lặp, các phần nhỏ này sẽ được dịch 1 hoặc 2 bit tùy thuộc vào số thứ tự của vòng lặp. (Nếu là vòng lặp 1, 2, 9, 16 thì dịch 1 bit, còn lại sẽ dịch 2 bit). Mỗi phần nhỏ 28 bit này sau khi đi qua PC2 (Permuted Choice 2) sẽ giảm xuống còn 24 bit mỗi phần. Và sau đó sẽ hợp 2 phần con này lại thành 1 khóa con có độ dài 48 bit. Các bộ biến đổi PC (Permuted choice - lựa chọn có hoán vị) chỉ đơn giản là các bộ vừa chọn lọc vừa hoán vị.

Cấu trúc cụ thể của hàm f.

Hàm Feistel (f) trong DES (Wikipedia)

Hình trên diễn tả cấu trúc và hoạt động cụ thể của hàm f (Feistel). Cụ thể ta thấy rằng, ở mỗi vòng lặp, 32 bit của R_{i - 1} sẽ được mở rộng thành 48 bit thông qua biến đổi E (Expainsion - mở rộng với sự lặp lại của 1 số bit), sau đó đem XOR với 48 bit của khóa con K_i. Kết quả sau XOR có độ dài 48 bit sẽ bị phân thành 8 nhóm, mỗi nhóm dài 6 bit. Mỗi nhóm này sẽ được đưa vào một biến đổi S_i mà được gọi là S-box, tổng cộng có 8 S-box. Mỗi S-box này nhận đầu vào 6 bit sẽ cho đầu ra 4 bit. Sau cùng, kết quả hợp thành một chuỗi 32 bit và nó chính là giá trị R_i.

Cấu trúc của S-box.

Trong mật mã học, S-box (Substitution-box) là một thành phần căn bản của Thuật toán mã hóa đối xứng SKC, có chức năng thay thế. Trong Hệ mã khối, bao gồm cả DES, S-box có chức năng che giấu mỗi quan hệ giữa bản mã (cipher text) và bản rõ (plain text), nhằm tăng tính hỗn độn (confusion) của thuật toán.

Về mặt tổng quát, S-box nhận đầu vào là 1 chuỗi m bit, sau đó sẽ biến đổi và tạo ra đầu ra n bit (m và n không nhất thiết phải bằng nhau). Một m×n S-box có thể được thực thi như 1 bảng tra cứu với 2^m từ, mỗi từ có độ dài n bit.

Dưới đây là bảng minh họa cho 6×4 S-box của DES.

6×4 S-box (Wikipedia)

Cụ thể với 6×4 S-box trên, ta có thể thấy rằng trong 6 bit vào, 2 bit ngoài cùng (bit thứ 0 và bit thứ 5) sẽ để chọn "bảng thế" trong 4 bảng thế trên; nên 2 bit này còn được gọi là các bit điều khiển trái và phải (CL và CR). Còn lại 4 bit chính nằm giữa sẽ là tổ hợp để lựa chọn biến đổi thay thế. Ví dụ có thể thấy nếu INPUT là 011011 thì sẽ lựa chọn bảng thế 01 cho từ mã 1101, do đó ta thu được OUTPUT là 1001.

Tuy rằng nguyên lý hoạt động khá là đơn giản, nhưng các nguyên tắc thiết kế S-box đã được Chính phủ Mỹ đưa vào lớp các thông tin mật. Mặc dù vậy, NSA vẫn tiết lộ 3 thuộc tính của S-box để khẳng định tính hỗn độn (confusion) và khuếch tán (deffusion):

• Các bit ra (OUTPUT bit) phụ thuộc phi tuyến (ko tuyến tính) vào các bit vào (INPUT bit).
• Sửa đổi 1 bit INPUT sẽ làm thay đổi ít nhất 2 bit OUTPUT.
• Khi INPUT giữ cố định 1 bit và thay đổi 5 bit thì S-box cho ra kết quả là 1 phân phối đều liên tục (Uniform Distribution). Điều này khiến cho việc sử dụng phương pháp "thống kê" trở lên vô ích.

Cấu tạo của S-box đã gây ra tranh cãi rất mạnh mẽ suốt từ 70s - 90s của thế kỷ 20 về khả năng NSA còn che giấu 1 Backdoor giúp cho việc phá giải mã dễ dàng hơn bình thường (giảm không gian khóa xuống dưới 2⁵⁶ để có thể Bruteforce (vét cạn) nhanh hơn. Đặc biệt, sau khi có sự khám phá về hình thức sử dụng "tấn công vi phân" (Differential cryptanalysis) đã củng cố niềm tin rằng nghi ngờ này là có khả năng. Cụ thể Biham và Shamir đã chứng minh rằng chỉ cần tạo ra 1 thay đổi nhỏ trong S-box cũng có thể làm suy yếu đáng kể sức mạnh và sự bảo mật của DES.

Thuật toán sinh và giải mã DES

Quay trở lại DES, mỗi vòng lặp của DES sẽ thực hiện công thức:

(L_i, R_i) = (R_{i - 1,} L_{i - 1} 𐌈 f(R_{i - 1}, L_i))

Ngoài ra cũng có thể biểu diễn ngắn gọn lại như sau:

(L_i, R_i) = T ⋄ F(R_{i - 1}, K_i)

Trong đó, F_i là phép thay thế L_{i - 1} bằng L_{i - 1} 𐌈 f(R_{i - 1}, L_i), còn T là phép đổi chỗ hai thành phần L và R. Tức là mỗi biến đổi vòng lặp DES có thể coi là một tích hàm số của F và T. Trừ vòng lặp cuối cùng là ko có T vì ko xảy ra đổi chỗ L và R. Do đó có thể biểu diễn toàn bộ quá trình mã hóa DES thành công thức tích hàm số sau:

DES = IC-1∘F₁₆∘T∘F₁₅∘T∘ ... ∘F₂∘T∘F₁∘(IC)

Khi đó, thuật toán giải mã DES sẽ được thực hiện theo thứ tự ngược lại, các khóa con cũng sẽ được sử dụng theo thứ tự ngược lại tương ứng.

DES-1 = IC-1∘F₁∘T∘F₂∘T∘ ... ∘F₁₅∘T∘F₁₆∘(IC)

Chú ý rằng mỗi hàm T hay F đều là các hàm đối hợp (tức là f(f(x)) = x, hay f =f-1), nên DES∘DES-1 hay DES-1∘DES cũng đều ra bản rõ ban đầu cả, chỉ yêu cầu thứ tự sử dụng chuỗi khóa con là khác nhau. 

Các mở rộng 2-DES và 3-DES cùng nguy cơ Meet-in-the Middle Attack.

Như ở đầu phần trước, tôi cũng đã nói rằng trong 64 bit của khóa chính, thực chất chỉ có 56 bit là được sử dụng thật vào việc sinh khóa con. Do đó, kích thước khóa thực tế chỉ có độ dài 56, nên không gian (không gian mẫu) tìm kiếm khóa sẽ có độ lớn là 256.

1 khối DES sẽ có độ dài khóa là 56, vậy phải chăng 2 khối DES (2-DES) sẽ có độ dài khóa là 2 * 56 = 112 (bit)? Không, that is "cú lừa" đó! Thực chất độ dài khóa chỉ là 57 bit!

Giả sử với 2 khối DES có khóa tương ứng là k1 và k2 khác nhau, p là bản rõ (plain text) cần mã hóa. Khi đó, ta sẽ có sơ đồ các bản tin thu được qua 2 lần mã hóa bằng DES là:

p →DES(k1, p) → DES(k2, DES(k1, p)) = c

Với c là bản mã (cipher text) sau 2 bước mã hóa bởi DES. Nhìn vào sơ đồ mã hóa trên, đứng ở vị trí 1 hacker, bạn sẽ suy nghĩ j? Hãy cùng xem biến đổi giải mã sau để thấy được sự ảo diệu của phép tấn công "Giao nhau ở giữa" (Meet-in-the middle attack):

c → DES-1(k2, c) =DES-1(k2, DES(k2, DES(k1, p))) = DES(k1, p) 

Hãy chú ý đến kết quả sau: DES-1(k2, c) = DES(k1, p)

Nếu hacker biết 1 cặp (c, p), họ sẽ tiến hành liệt kê ra 256 kết quả sau khi mã hóa 1 lần p và 256 kết quả sau khi giải mã 1 lần c. Độ phức tạp bảo mật để thực hiện 2 thao tác này là O(2 * 256) = O(257). Bạn cần lưu ý, ở đây cái ta quan tâm là độ phức tạp bảo mật, ko phải độ phức tạp tính toán nhé! Vì 1 phép mã hóa/giải mã là 1 thủ tục rất nhiều các bước tương ứng với việc tính toán; do đó khi xét độ phức tạp trong Mật mã học, ta chỉ xét độ phức tạp bảo mật!

Sau đó thì sao, đơn giản thôi, tiến hành matching 2 bảng kết quả đầu ra trên. Thủ tục matching này tuy có độ phức tạp tính toán là 2112, nhưng độ phức tạp bảo mật lại chỉ là 0; do đó độ phức tạp bảo mật sẽ tăng lên thành O(k * 257) =  O(257). 

Sau khi matching xong, ta sẽ được 1 giao điểm duy nhất! Giao điểm này sẽ cho ta biết giá trị 2 khóa k1 và k2. Vậy là DES bị phá giải với độ dài không gian khóa chỉ là 57 chứ không phải 112 như ta "tưởng"!

Nghe có vẻ sida nhỉ? Đúng vậy, tuy 2-DES không đem lại nhiều hiệu quả hơn so với DES; nhưng 3-DES thì thực sự đem lại một giải pháp an toàn bảo mật với độ phức tạp 112 bit. Cụ thể, ta có thể xem 2 sơ đồ mã hóa sau:

• 3 khóa: DES(k3, DES-1(k2, DES(k1, p)))
• 2 khóa: DES(k1, DES-1(k2, DES(k1, p)))

Lý do để thực hiện DES-1 ở bước 2 là vì trong thực tế, người ta chỉ sử dụng DES và 3-DES, nhưng không phải toàn bộ các module khác nhau của hệ thống cũng đều được thống nhất sử dụng DES hoặc 3-DES từ trước; nhất là việc tích hợp 2 hệ thống từ 2 hãng khác nhau lại với nhau. Do đó để đơn giản hóa mà ko làm giảm tính bảo mật của DES, người ta quy ước thực hiện DES-1 ở bước thứ 2. Khi đó nếu k1 = k2, hệ thống DES trở thành chỉ có 2 khóa tồn tại; và sẽ trở về tương đương như 1-DES vậy.

Ứng dụng của các thuật toán DES.

DES và 3-DES được sử dụng thực tế trong các giao thức bảo mật tầng TCP là SSL và TLS (Secure socket layer và Transport layer security). DES tuy ko mạnh, nhưng đơn giản, đảm bảo realtime trong việc mã hóa và giải mã dữ liệu ở Tầng Giao vận. Và đây chính là nguồn gốc của giao thức HTTPS. Chữ "S" ở đây có nghĩa là SSL hoặc TLS.

Với không gian khóa có độ lớn 256, nếu biết 1 cặp (bản mã, bản rõ), giả sử một PC thông thường 1 core 1 thread thực hiện phép thử với 1 trường hợp khóa tốn 10-6 giây, thì máy PC đó sẽ tốn 1011 năm để vét cạn hết toàn bộ không gian khóa và phá thành công 1-DES.

Tuy nhiên, PC đó chỉ là 1 máy tính thông thường. Ngày này, với sức mạnh của vi xử lý máy tính hiện đại, công nghệ ghép nối song song vi xử lý, tính toán phân tán, cộng thêm các kỹ thuật lập trình song song, cũng như việc khai thác Bộ vi xử lý đồ họa (GPU - Graphic Processor Unit); nên nếu muốn phá DES, cũng không phải bất khả thi đến 1011 năm như cuối thế kỷ 20.

Sau khi trở lên thịnh hành được 2 thập kỷ, DES đã bộc lộ nhiều yếu điểm và kém tin tưởng như mình đã đề cập bên trên; do đó ứng dụng hiện nay của nó chỉ có vỏn vẹn trong 1 số khía cạnh trên thôi. Còn việc sử dụng làm "khóa phiên" như trong giao thức Needham - Schroeder thì nó ko còn chỗ nữa. Sau DES, người ta đã phát triển và đưa vào sử dụng thuật toán AES (Advance Encryption Standard) vì tốc độ xử lý cũng như tính tin cậy. Mình sẽ viết một bài riêng về AES sau.