
Tất Tần Tật Về Block Cipher
Chúng ta đã bàn khá nhiều về stream cipher – một nửa của symmetric-key cipher rồi. Vậy thì bài viết này sẽ khám phá nửa còn lại…block cipher.
Nguyên lý hoạt động chính
Hàm số giả ngẫu nhiên – Pseudo Random Function (PRF)
Nếu cốt lõi của stream cipher là PRNG thì block cipher có PRF làm trụ cột. Vậy, PRF là gì?
Cũng giống như định nghĩa PRNG từ RNG, trước tiên ta sẽ làm rõ Random Function là gì. Random Function là hàm số nhận input trong tập hợp X và cho ra output ngẫu nhiên trong tập hợp Y. Hiểu đơn giản, RF gần giống PRNG ở chỗ nhận input, nhưng tính ngẫu nhiên thì tuyệt đối như True RNG.
Như vậy, Pseudo Random Function cũng nhận input trong tập hợp X, cho ra output trong tập hợp Y, và cố gắng bắt chước tính ngẫu nhiên của RF bằng một thuật toán xác định.
Từ đây sinh ra một khái niệm khác là Pseudo Random Permutation (PRP). Nó chỉ khác PRF ở chỗ output cũng là từ tập hợp X, vì thế ta mới gọi nó là permutation (hoán vị).
Tuy nhiên, có một phân biệt quan trọng hơn:
- Nếu cho output của PRF thì ta không thể tính được input là gì, tức là hàm ngược của hàm PRF (PRF-1) là không tính được, hoặc là khó để tính.
- Mặt khác, hàm ngược của PRP (PRP-1) là hoàn toàn tính được, vì hàm PRP chỉ làm việc trong tập hợp X.
Rất nhiều block cipher sử dụng PRP vì lí do trên, để quá trình decryption (ngược với encryption) được thực hiện dễ dàng.
Phương thức chạy PRF trong block cipher
Block cipher sẽ nhận plaintext có độ dài cố định (có thể là 64 bit) và cho ra ciphertext có độ dài cố định (có thể là 64 bit, thường là bằng với độ dài plaintext).
Nhiều block cipher sẽ hoạt động như sau:
- Plaintext sẽ đi qua nhiều round (vòng) xử lí, xử lí xong thì sẽ cho ra ciphertext. Lấy ví dụ, block cipher của chúng ta sẽ đi qua 10 vòng.
- Từ key chính ta sẽ chia ra làm 10 key, mỗi key cho một vòng tương ứng.
- Mỗi vòng có cấu trúc như sau: Input là output của vòng trước với key tương ứng của vòng (tức là 2 input); 1 vòng được vận hành bởi 1 hoặc nhiều PRP/PRF; từ đó cho ra output để đưa tiếp vào vòng sau.
Cấu trúc của mạng lưới Feistel, được sử dụng trong nhiều block cipher, với 1 vòng là từ Li / Ri đến Li + 1 / Ri + 1
Cấu trúc trên của block cipher sẽ được sắp xếp một cách hợp lí sao cho ta có thể đảo ngược lại, từ ciphertext ta sẽ thu được plaintext (decryption).
Các chế độ vận hành
Tuy nhiên, không phải tin nhắn nào cũng dài 64 bit để ta có thể thực hiện block cipher lên. Vì thế, xuất hiện một số chế độ sau đây để ta thực hiện block cipher.
Chế độ vận hành cũng sẽ quyết định độ bảo mật của block cipher.
Electronic Codebook (ECB)
ECB là chế độ hoạt động đơn giản nhất: Ta chia plaintext ra thành từng khối, mỗi khối có độ dài bằng 64 bit (hay độ dài quy định của block cipher), và thực hiện mã hóa độc lập từng khối.
Hình minh họa cách thức hoạt động của ECB
Tuy nhiên, không khó để nhận ra rằng mã hóa bằng chế độ ECB sẽ ít nhiều để lộ thông tin về tin nhắn gốc. Trong định nghĩa về bảo mật của block cipher, ECB cũng chỉ được đề cập là thiếu an toàn, vì thế không nên sử dụng trong mọi tình huống, bất chấp block cipher có bảo mật đến cỡ nào.
So sánh output giữa ECB (giữa) và chế độ vận hành khác (phải)
Cipher Block Chaining (CBC)
Mã hóa chế độ CBC hoạt động với công thức truy hồi sau:
Ci = EK(Pi ⊕ Ci - 1); C0 = IV
Trong đó:
Pi
là khối plaintext thứ iCi
là khối ciphertext thứ iEK
là thuật toán encryption sử dụng key KIV
nghĩa là Initialization Vector, không được sử dụng lại chung cho nhiều tin nhắn.
Hình minh họa cách thức hoạt động của CBC
Counter (CTR)
Chế độ CTR giới thiệu thêm 2 input nhằm tăng tính ngẫu nhiên cho ciphertext:
- 1 là nonce, một chuỗi bit ngẫu nhiên, không cần phải bí mật.
- 2 là counter, số thứ tự của khối đó trong plaintext.
Từ đó, công thức của mã hóa chế độ CTR là:
Ci = EK(nonce || i) ⊕ Pi
Hình minh họa cách thức hoạt động của CTR
Padding
Một điều đáng buồn khác, độ dài của plaintext phải là bội số của 64 bit (hay độ dài quy định của block cipher) thì mới thực hiện những chế độ trên được. Vậy trong trường hợp plaintext chỉ có độ dài 126 bit, hay một số không phải là bội của 64 thì sao?
Giải pháp ở đây khá đơn giản: padding, tức là bù vào plaintext một vài bit sao cho plaintext có độ dài đúng.
Dẫu vậy, kể cả khi plaintext có độ dài đúng, thường thì ta vẫn cần phải thực hiện padding: thêm vào nguyên cả một khối 64 bit vào plaintext, vì trong quá trình decryption, code của block cipher luôn quy định bỏ đi phần padding. Lỡ khi plaintext có độ dài đúng mà ta không pad, code sẽ cắt đi 1 block cuối của plaintext, làm mất thông tin quan trọng.
Padding cũng có được tiêu chuẩn khác nhau, được quy định chính thức.
Một phương pháp padding đơn giản là thêm những bit 0 vào cuối plaintext, sao cho
plaintext có độ dài phù hợp.
Tuy nhiên, phương pháp này va phải một vấn đề như sau: Xét 1 block cipher hoạt động
với plaintext 8 bit. Ta có 2 plaintext là 1011 và 101100. Khi thực hiện padding bằng
cách trên, cả 2 sẽ trở thành 10110000, như vậy sẽ dẫn đến ciphertext như nhau; và khi
thực hiện giải mã ciphertext đó, ta sẽ không biết cần phải bỏ bao nhiêu bit 0 ở đằng
sau.
Một giải pháp đơn giản là: Ở trước plaintext sẽ là độ dài gốc, và ở sau là số bit 0
cần thiết để plaintext có độ dài phù hợp.
Xét lại ví dụ trên, như vậy plaintext 1011 sẽ pad thành (100)1011(0), và 101100 sẽ pad
thành (110)101100(0000000).
Một giải pháp khác: Ta thêm vào sau plaintext 1 bit 1, sau đó mới thêm đủ số bit 0 cần
thiết.
Tiếp tục xét ví dụ trên, 1011 sẽ thành 1011(1000), và 101100 sẽ thành 101100(10).
Những block cipher tiêu biểu
DES – Data Encryption Standard
DES được NIST phát triển từ một hệ thống tên Lucifer, và được công bố làm tiêu chuẩn xử lí thông tin liên bang (FIPS) của Mĩ vào năm 1977. Năm 1997 đánh dấu lần đầu tiên một tin nhắn mã hóa bởi DES bị phá, cũng đánh dấu cái chết của hệ thống này.
Những thông số đáng chú ý:
- Plaintext: 64 bit
- Key: 64 bit (8 bit coi như thừa, vậy key hiệu quả mang 56 bit)
- Số vòng: 16
- Phương pháp tấn công hiệu quả nhất: Bộ nhớ tốn 243, thời gian tốn 239-243
AES – Advanced Encryption Standard
Đầu năm 1997, NIST công bố tìm kiếm hệ thống mới để thay thế cho DES, gọi là AES. Qua 5 năm chọn lọc, vượt qua 14 đối thủ, Rijndael chính thức được công nhận là AES vào năm 2001, được đưa vào tiêu chuẩn FIPS 197 và ISO/IEC 18033-3.
Minh họa cấu trúc hàm PRF của AES
Những thông số đáng chú ý:
- Plaintext: 128 bit
- Key: 128/192/256 bit
- Số vòng: 10/12/14 (tương ứng với độ dài key)
- Thuật toán tốt nhất phá AES-128 chạy trong thời gian ~2126
Tạm kết
Trên đây là tất tần tật về block cipher, lớp hệ thống cryptography phổ biến nhất trong những symmetric-key cipher.
Chà chà! Vậy là chúng ta đã khám phá xong một mảng khá lớn của cryptography. Mảng nào sẽ được bàn đến tiếp theo nhỉ?
Hãy đón xem trong bài viết mới nhé!
Post Comment