Trong phần này ta sẽ xem xét các thuật toán mã hóa theo khối, gọi là các thuật toán dùng khóa đơn (single-key), khóa bí mật (private-key) hay thuật toán đối xứng (symmetric).
Đặc thù của các thuật toán block cipher là hai bên gửi và nhận sử dụng chung một khóa để mã hoá và giải mã thông điệp. Do vậy, vai trò của hai bên tham gia vào quá trình trao đổi thông tin là như nhau. Người gửi sử dụng một khoá duy nhất để mã hoá thông điệp và gửi đi và cũng với khoá đó, người nhận sẽ giải mã thông điệp nhận được để có thông điệp nguồn. Khoá đó cần phải giữ bí mật vì nếu lộ ra, kẻ gian có thể dùng nó giải mã và đọc nội dung các thông điệp trao đổi.
Các thuật toán mã hoá cổ điển đều thuộc loại khóa đơn. Nhiều thuật toán mã hóa hiện đại, đang sử dụng rộng rãi ngày nay, đã được phát triển từ hai kỹ thuật thay thế và đổi chỗ cổ điển như: DES, Blowfish, IDEA, LOKi, RC5, Rijndael (AES),.v.v.
Các bài viết liên quan:
Trong thuật toán mã hoá khối, dữ liệu đầu vào (bản nguồn) sẽ được chia thành các khối với độ dài xác định (64 bit, 128 bit,…) và các khối này sẽ được mã hoá bằng cùng một khoá để tạo nên các khối dữ liệu đã được mã hoá và cuối cùng, các khối này sẽ kết hợp với nhau để tạo thành bản mã.
Mạng thay thế – hoán vị Shannon
Năm 1949 nhà toán học người Mỹ Claude Shannon (1916 – 2001) đã đưa ra ý tưởng về mạng thay thế – hoán vị / substitution – permutation networks (mạng S – P) tạo nên cơ sở của các thuật toán mã hoá khối. Mạng S – P dựa trên hai phép biến đổi: thay thế (Substitution) và hoán vị (Permutation). Thay thế và hoán vị là hai kỹ thuật trong mật mã cổ điển áp dụng cho các ký tự. Shannon đã vận dụng chúng và sử dụng cho các bit và ông đã kết hợp chúng liên hoàn với nhau để thành một mạng biến đổi hoàn chỉnh.
Phép thay thế (Substitution operation)
Là phép toán nhằm biến đổi một chuỗi bit có độ dài xác định thành một chuỗi bit khác. Ví dụ như phép thay thế một chuỗi 3 bit thành một chuỗi 3 bit khác có thể được mô tả như sau:
Ba bit đầu vào là 001 sẽ được biểu diễn thành một số 3 bit (nằm trong khoảng [0..7] là số 1. Tuỳ thuộc vào phép biến đổi, số này sẽ ánh xạ đến một số 3 bit khác, ví dụ là 6, tức là sẽ có 3 bit đầu ra là 110 (1102 = 6). Phép biến đổi 3 bit bất kỳ thành 3 bit khác như trên được thực hiện trong một S- box. Có thể thấy, một S-box biến đổi chuỗi n bit chính là một hoán vị của các giá trị {0,1,…, 2n-1}. Độ dài của S-box là 2n và số lượng S-box biến đổi n bit sẽ là một số khá lớn: 2n!
Phép hoán vị (Permutation operation)
Là phép toán cũng nhằm biến đổi một chuỗi bit có độ dài xác định thành một chuỗi bit khác, nhưng việc biến đổi ở đây chỉ đơn thuần là đổi chỗ các bit trong chuỗi bit đầu vào để nhận được chuỗi bit đầu ra. Phép biến đổi như vậy thực hiện trong một P-box. Như vậy, P-box thực chất là một hoán vị thứ tự n bit đầu vào hay là một hoán vị của các giá trị {0,1,…, n}.
Độ dài của P-box là n và số lượng P-box biến đổi n bit sẽ là n!.
Ý tưởng của Shannon là kết hợp các S-box và P-box với nhau thành một mạng S-P. Do S-box xử lý n bit có độ dài 2n – rất lớn so với P-box tương ứng có độ dài n nên Shannon đề xuất sử dụng nhiều S-box để biến đổi chuỗi n bit. Dưới đây là mô hình mạng S-P biến đổi chuỗi 6 bit:
6 bit đầu vào là 011010 đi qua P-box đầu biến thành 001101. Sau đó chuỗi bit này sẽ chia làm đôi: 001 và 101 sẽ lần lượt đi qua hai S-box khác nhau và cho kết quả là 110 và 011. Các bit này lại kết hợp với nhau và đi qua P-box 6 bit thứ hai,… Cứ như vậy, sau một số vòng biến đổi chúng ta sẽ có 6 bit đầu ra. Đó chính là ý tưởng của mạng S-P của Shannon. Các S-box và các P-box hoạt động xen kẽ nhau. S-box tạo ra sự xáo trộn (confusion) các bit đầu vào và P-box tạo ra sự truyền bá (diffusion) các bit sau S-box.
Để bảo đảm an toàn cho các thuật toán mã hoá khối, Webster & Tavares đưa ra các khái niệm gọi là hiệu ứng thác (Avalanche) và hiệu ứng toàn vẹn (Completeness).
Hiệu ứng thác (Avalanche effect)
Là hiệu ứng có được khi trong quá trình mã hoá dữ liệu việc thay đổi một bit nguồn sẽ dẫn đến sự thay đổi hơn một nửa các bit đích. Một hàm f sẽ được coi là có hiệu ứng thác tốt nếu: với mỗi bit i, 0 £ i < m, nếu 2m bản nguồn độ dài m được chia thành 2m-1 cặp X và Xi chỉ khác nhau ở bit thứ i thì trong 2m-1 giá trị Vi = f(X) XOR f(Xi) sẽ có hơn ½ giá trị khác 0. Hiệu ứng này bảo đảm mỗi thay đổi nhỏ của nguồn sẽ dẫn tới sự thay đổi lớn của đích.
Ta sẽ minh hoạ bằng ví dụ hàm băm MD5 cho hai chuỗi ký tự “hello” và “hallo” chỉ khác nhau ở ký tự thứ hai. Chính xác hơn, hai chuỗi e = 0x65
= 011001012 và a = 0x61 = 011000012 chỉ khác nhau có một bit duy nhất. Mặt khác, MD5(“hello”) = 0x5d41402abc4b2a76b9719d911017c592, và MD5(“hallo”) = 0x598d4c200461b81522a3328565c25f7c có hai kết quả khác nhau ở rất nhiều vị trí. Do vậy, có thể nói hàm băm MD5 bảo đảm được hiệu ứng thác.
Hiệu ứng toàn vẹn (Completeness effect)
Là hiệu ứng có được khi mỗi bit đích là hàm phức hợp của tất cả các bit nguồn. Hàm f sẽ được coi là có hiệu ứng toàn vẹn tốt nếu: với mỗi bit thứ j (0 £ j < m) trong các bản mã và “i (0 £ i < m) luôn tìm được ít nhất một cặp bản nguồn X and Xi khác nhau chỉ tại bit thứ i mà f(X) và f(Xi ) khác nhau tại bit thứ j. Hiệu ứng toàn vẹn bảo đảm mỗi bit đích sẽ phụ thuộc vào tất cả các bit nguồn. Do đó, kẻ tấn công sẽ không thể dùng nguyên tắc “chia để trị” để thám mã. Hiệu ứng thác và hiệu ứng toàn vẹn trong các thuật toán mã hoá khối là tính chất khác biệt so với các thuật toán mã hoá cổ điển.
Chuẩn mã hóa DES
DES – viết tắt của cụm từ Data Encryption Standard là một thuật toán mã hoá khối ra đời giữa những năm 1970 và được sử dụng phổ biến trong vòng 30 năm sau đó.
Vào những năm 1973, 1974 máy tính đã bắt đầu được sử dụng nhiều trong các ngân hàng, công ty tài chính lớn. Nhu cầu giữ bí mật thông tin đã trở nên cấp thiết nhưng các thuật toán cổ điển lại không đáp ứng được. Viện chuẩn và công nghệ Hoa Kỳ NIST (National Institute of Standards and Technology) đã kêu gọi xây dựng các thuật toán mã hóa mới và an toàn hơn. Sau đó các ngân hàng Mỹ đã đặt hàng cho công ty IBM – người khổng lồ trong lĩnh vực điện toán thời đó, thiết kế một thuật toán mã hoá hoàn toàn mới. Lúc đầu, IBM đưa ra thuật toán Lucifer và sau đó thuật toán này được thiết kế, chỉnh sửa lại thành thuật toán DES. Năm 1976 DES đã được NIST công nhận là chuẩn mã hoá dữ liệu, và đến năm 1981 DES trở thành chuẩn mật mã của ANSI (American National Standards Institute). DES được sử dụng rộng rãi trên thế giới, đặc biệt là trong các giao dịch ngân hàng, thông tin liên lạc. Định kỳ, ANSI công nhận lại chuẩn mật mã cho thời gian 5 năm tiếp theo. DES là thuật toán mã hóa khối được sử dụng phổ biến trong suốt gần 30 năm, từ năm 1976 đến những năm gần đây.
Quá trình mã hóa một khối 64-bit đầu vào bằng DES thông qua các bước: (1) Hoán vị ban đầu IP (Initial Permutation); (2) 16 vòng tính toán phức tạp có sử dụng khóa; (3) Hoán vị kết thúc, là nghịch đảo của IP. Quy trình mã hoá và tạo khoá của thuật toán DES có thể được mô tả trong sơ đồ sau:
Phần bên trái của hình vẽ là quy trình mã hoá dữ liệu. Phần bên phải là quy trình tạo các khoá con (subkey). Chi tiết hơn, chúng ta có thể xem xét phần dưới đây.
Quy trình biến đổi key
Các bảng PC1 và PC2 là thành phần của thuật toán và có giá trị như sau:
Bắt đầu từ khóa ban đầu 64 bit, ta bỏ các bit là bội số của 8 và nhận được khóa 56 bit. Qua phép biến đổi bảng PC1, ta chọn được hai chuỗi 28 bit C0 và D0.
Các chuỗi Ci và Di được quay trái riêng rẽ đi một bit hay hai bit. Sau đó sử dụng bảng PC2, chúng ta sẽ chọn được 16 khoá 48 bit được sử dụng cho 16 vòng tính toán.
Ví dụ, quá trình tạo khoá sẽ thực hiện các bước như sau: Giả sử khoá 64 bit ban đầu là: K = 0x5b5a57676a56676e. Sau khi bỏ đi bit cuối cùng ở mỗi byte các bit còn lại sẽ được biến đổi bằng PC1 để nhận được 56 bit gồm hai nửa C0 và D0.
Như vậy, PC1(K) = PC1(0x5b5a57676a56676e) = 0x00ffd820ffec9370 = {C0, D0}. Trong đó C0= 0x00ffd820 và D0= 0xffec9370.
Do các chuỗi C0 và D0 có độ dài 28 bit nên để biểu diễn chúng trong 4 byte (32 bit) chúng ta bổ sung thêm vào cuối mỗi chuỗi 4 bit ảo. Các bit ảo này chỉ dùng để biểu diễn, không tham gia vào các quá trình tính toán. Quá trình đó được minh hoạ qua hình dưới đây:
Tiếp theo, các chuỗi C0 và D0 sẽ quay trái 1 bit để được C1, D1 tương ứng. Sau đó, các giá trị C1 và D1 sẽ được biến đổi bằng PC2 để có khoá con 48 bit K(1).
C1 = 0x01ffb040; D1 = 0xffd926f0; PC2(C1, D1) = K(1) =
0x38091b262f3a270f. Các chuỗi C1 và D1 tiếp tục được quay trái để có C2, D2 và sau đó được biến đổi bởi PC2 để có K(2),.v.v. Cứ như vậy, ta sẽ thu được 16 khoá con để tham gia vào 16 vòng tính toán trong quy trình mã hoá. Đối với khoá đầu vào như trên ta sẽ có:
| K(1) = 0x38091b262f3a270f | K(2) = 0x280919321d321f2f |
| K(3) = 0x390529323f2b270b | K(4) = 0x292f0d10192f1d3f |
| K(5) = 0x03251d131f3b372a | K(6) = 0x1b3505193b0d353b |
| K(7) = 0x033c0709133f393e | K(8) = 0x0634261b3f1d3738 |
| K(9) = 0x07342a09373f383c | K(10) = 0x0633260c3e153f38 |
| K(11) = 0x0602330d261f283f | K(12) = 0x1416302c3d373a34 |
| K(13) = 0x300a36242e122f3f | K(14) = 0x340a38272d3f2a17 |
| K(15) = 0x381b18221d321f37 | K(16) = 0x380b082e3d2f0e17 |
Quá trình biến đổi dữ liệu
Dữ liệu được mã hoá sẽ phải qua các biến đổi bởi hoán vị khởi tạo IP, sau đó dữ liệu sẽ tiếp tục với 16 vòng biến đổi và kết thúc bởi hoán vị kết thúc IP-1. Ví dụ, nếu 64 bit dữ liệu đầu vào là 0x675a69675e5a6b5a thì biến đổi IP sẽ như sau:
Biến đổi IP:
Vậy IP(0x675a69675e5a6b5a) = 0xffb2194d004df6fb. Tiếp theo, dữ liệu sẽ đi qua 16 vòng tính toán. Một vòng tính toán thứ i sẽ có dạng
Dữ liệu chia thành hai nửa 32 bit: Li-1 và Ri-1.
- Hàm mở rộng E(Ri-1) biến đổi 32 bit thành 48 bit
- Kết quả XOR với khóa K(i)
- 8 S-box biến đổi 48 bit thành 32 bit
- Hoán vị P xáo trộn 32 bit nhận được
- Kết quả XOR với Li-1 để cho ra Ri
Như vậy:
Ri = Li-1 XOR P[S(E(Ri-1) XOR K(i)] và Li = Ri-1
Ta sẽ xem xét từng phép biến đổi một qua ví dụ cụ thể. Hàm E mở rộng dữ liệu từ 32 bit thành 48 bit như hình dưới đây:
Hàm E biến đổi dữ liệu bằng cách lặp lại một số bit đã có. Kết quả của phép biến đổi là 48 bit sẽ được lưu trong 8 byte, mỗi byte chứa 6 bit. Như vậy ta có: E(R0) = E(0x004df6fb) = 0x2000091b3e2d1f36.
Kết quả nhận được sau hàm E sẽ được XOR với khoá con tương ứng:
Phép XOR được thực hiện theo từng cặp bit tương ứng. Kết quả có thể viết như sau: A = E(R0) XOR K(1) = 0x2000091b3e2d1f36 XOR 0x38091b262f3a270f = 0x1809123d11173839.
Kết quả này sẽ đi qua 8 S- box, mỗi S-box biến đổi 6 bit thành 4 bit:
DES có 8 S-box, được đánh số từ S1 đến S8 như hình trên. S-box cũng như các bảng khác đều là thành phần của DES và được công bố công khai.
Trong ví dụ trên ta có S1(0x18) = 5; S2(0x09) = f,… Tổng hợp lại, ta có: S (0x1809123d11173839) = 0x5fd25e03.
Như vậy, 8 S-box đã biến đổi dữ liệu từ 48 bit thành 32 bit. Tiếp theo, hàm hoán vị P xáo trộn 32 bit nhận được sau các S-box:
Kết quả hoán vị P sẽ được tiếp tục XOR với nửa dữ liệu bên trái:
Kết quả của vòng tính toán đầu ta có:
R1 = L0 XOR P(B) = 0xffb2194d XOR 0x746fc91a = 0x8bddd057.
Trong khi đó L1 = R0 = 0x004df6fb. Thực hiện 16 vòng lặp tương tự như vậy (riêng vòng cuối cùng không đổi chỗ L16 và R16 cho nhau) dữ liệu nhận được sẽ đi qua hoán vị kết thúc IP-1 để có được kết quả cuối cùng của thuật toán:
Cuối cùng ta có kết quả của của thuật toán:
DES (K, PlainText) = DES (0x5b5a57676a56676e, 0x675a69675e5a6b5a) = 0x974affbf86022d1f.
Sử dụng DES trong thực tế
Khoá ban đầu của DES là 64 bit nhưng số bit thực sự sử dụng là 56 để tạo các khoá con 48 bit, do vậy, độ dài khoá của thuật toán DES là 56 bit. Sử dụng khóa 56-bit DES cho tốc độ tính toán nhanh nhưng dễ bị thám mã bằng vét cạn khóa như Diffie & Hellman đã dự báo.
Sau hơn 20 năm kể từ khi ra đời, DES đã bị phá mã bằng phương pháp vét cạn khoá: năm 1997 bằng mạng máy tính lớn trong vài tháng; năm 1998 bằng máy tìm khóa đặc biệt trong vài ngày; năm 1999 bằng tổ hợp các máy trên trong 22 giờ 15‟.
Trên lý thuyết, DES cũng có thể bị thám mã bằng cách sử dụng thám mã vi phân hoặc tuyến tính. Tuy bị phá mã như vậy, nhưng do chi phí để thực hiện khá cao nên DES vẫn tiếp tục được sử dụng trong một vài năm sau đó thông qua các biến thể cải tiến như Triple DES.
Triple DES (DES 3 lớp) thực chất là sử dụng liên tiếp ba lần thuật toán DES để mã hoá/giải mã với ba khoá khác nhau: C = DESK3 { DES-1K2 { DESK1 (P) } }. Khi K1 = K2 = K3 thì đó chính là DES. Trên thực tế, có thể sử dụng hai khoá khi K1 = K3. Ưu điểm của DES 3 lớp là chống lại được tấn công vét cạn khoá nhưng nhược điểm của nó là thời gian mã hoá và giải mã lâu.
Trong quá trình thiết kế thuật toán DES phải chú ý loại bỏ các “khoá yếu”. Khoá yếu là khoá mà từ nó tạo nên các khoá con giống nhau. Khóa k của DES gọi là yếu (weak) nếu Ek(Ek(x)) = x, ” x. Tương tự, cũng cần loại bỏ các cặp “khoá gần yếu”. Cặp khóa (k1, k2) của DES gọi là gần yếu (semi-weak) nếu: Ek1(Ek2(x)) = x. Khoá của thuật toán DES thường được tạo một cách ngẫu nhiên.
Do vậy, trước khi sử dụng cần kiểm tra xem nó có thuộc các loại khoá yếu hay gần yếu hay không? Nếu có, chúng ta phải tạo lại khoá ngẫu nhiên mới. Số lượng khoá yếu và khoá gần yếu không nhiều (16 khoá), do đó, việc kiểm tra này hầu như không tốn thời gian.
Thuật toán DES chỉ cho phép mã hoá/giải mã 64 bit tức là 8 byte dữ liệu. Đối với dữ liệu lớn hơn, người ta sử dụng DES với các các kiểu (mode) khác nhau:
- Kiểu khối: Dữ liệu được chia thành các khối 8 byte và dùng DES để xử lý từng khối đó (ECB và CBC).
- Kiểu dòng: Sử dụng DES như máy tạo dòng khoá và dùng dòng khoá này để mã hoá dữ liệu (OFB và CFB).
