Hệ mật DES

Mật mã DES


     Ngày nay, nhu cầu về công nghệ thông tin trong đời sống là đa dạng.  Với việc ứng dụng mã hóa vào việc truyền thông tin trên mạng, mã hóa thông tin là rất cần thiết, góp phần đảm bảo sự toàn vẹn và bảo mật, xác thực cho thông điệp cần gửi đi qua mạng Internet.

     Bài viết này tôi sẽ giới thiệu cho các bạn về thuật toán mã hóa DES.

     DES (viết tắt của Data Encryption Standard, hay Tiêu chuẩn Mã hóa Dữ liệu) là một phương pháp mật mã hóa được FIPS (Tiêu chuẩn Xử lý Thông tin Liên bang Hoa Kỳ) chọn làm chuẩn chính thức vào năm 1976. Sau đó chuẩn này được sử dụng rộng rãi trên phạm vi thế giới. Ngay từ đầu, thuật toán của nó đã gây ra rất nhiều tranh cãi, do nó bao gồm các thành phần thiết kế mật, độ dài khóa tương đối ngắn, và các nghi ngờ về cửa sau để Cơ quan an ninh quốc gia Hoa Kỳ (NSA) có thể bẻ khóa. Do đó, DES đã được giới nghiên cứu xem xét rất kỹ lưỡng, việc này đã thúc đẩy hiểu biết hiện đại về mật mã khối (block cipher) và các phương pháp thám mã tương ứng.

    Hiện nay DES được xem là không đủ an toàn cho nhiều ứng dụng. Nguyên nhân chủ yếu là độ dài 56 bit của khóa là quá nhỏ. Khóa DES đã từng bị phá trong vòng chưa đầy 24 giờ. Đã có rất nhiều kết quả phân tích cho thấy những điểm yếu về mặt lý thuyết của mã hóa có thể dẫn đến phá khóa, tuy chúng không khả thi trong thực tiễn. Thuật toán được tin tưởng là an toàn trong thực tiễn có dạng Triple DES (thực hiện DES ba lần), mặc dù trên lý thuyết phương pháp này vẫn có thể bị phá. Gần đây DES đã được thay thế bằng AES (Advanced Encryption Standard, hay Tiêu chuẩn Mã hóa Tiên tiến).

Sơ đồ mã DES


Hệ mật DES1. Tính chất:

Là mã thuộc hệ mã Feistel gồm 16 vòng, ngoài ra DES có thêm một hoán vị khởi tạo trước khi vào vòng 1 và một hoán vị khởi tạo sau vòng 16

– Kích thước của khối là 64 bít: ví dụ bản tin “meetmeafterthetogaparty” biểu diễn theo mã ASCII thì mã DES sẽ mã hóa làm 3 lần, mỗi lần 8 chữ cái (64 bít): meetmeaf – tertheto – gaparty.

– Kích thước khóa là 56 bít

– Mỗi vòng của DES dùng khóa con có kích thước 48 bít được trích ra từ khóa chính. Hình dưới đây minh họa các vòng của mã DES

Hệ mật DES

Hình 1.1. Mã hóa DES

 – Mã hóa DES gồm ba phần, phần thứ nhất là các hoán vị khởi tạo và hoán vị kết thúc. Phần thứ hai là các vòng Feistel, phần thứ ba là thuật toán sinh khóa con. Chúng ta sẽ lần lượt đi vào chi tiết của từng phần.

2. Hoán vị khởi tạo và hoán vị kết thúc:

– Bản mã được chia thành các khối 64bit và được đánh số các bít của khối 64bit theo thứ tự từ trái sang phải là 0, 1, …, 62, 63 ta sẽ có ma trận hoán vị IP.

Hoán vị khởi tạo sẽ hoán đổi các bít theo quy tắc sau:

Hệ mật DES

Hoán vị kết thúc hoán đổi theo quy tắc sau:

Hệ mật DES

Hoán vị kết thúc chính là hoán vị nghịch đảo của hoán vị khởi tạo. Đối với knownplaintext hay chosen-plaintext attack, hoán vị khởi tạo và hoán vị kết  thúc không có ý nghĩa bảo mật, sự tồn tại của hai hoán vị trên được nhận định là do yếu tố lịch sử.

3. Các vòng của DES:

– Một vòng mã hóa của DES sẽ thực hiện chia khối làm 2 phần mỗi phần 32bit (L và R). Sau đó đem phần R biến đổi qua hàm F rồi thực hiện hoán vị giữa L và R rồi kết hợp lại thành khối 64bit.

Hệ mật DES

Hình 1.3. Cấu trúc một vòng của DES

Trong DES, hàm F của Feistel là:

      F (Ri-1, Ki) = P-box(S-boxes (Expand (Ri-1) Ki))

     Trong đó hàm Expand vừa mở rộng vừa hoán vị Ri-1 từ 32 bít lên 48 bít. Hàm               Sboxes nén 48 bít lại còn 32 bít. Hàm P-box là một hoán vị 32 bít. Mô tả của các           hàm trên là như sau:

     Expand: 32 bit đầu vào được mở rộng thành 48 bit sử dụng thuật toán hoán vị mở rộng (expansion permutation) với việc nhân đôi một số bit.

      Hàm Expand đánh số các bít của Ri-1 theo thứ tự từ trái sang phải là 0, 1, 2, …, 31. Hàm Expand thực hiện vừa hoán vị vừa mở rộng 32 bít thành 48 bít theo quy tắc:

Hệ mật DES

     Trộn khóa: 48 bit thu được sau quá trình mở rộng được XOR với khóa con. Mười sáu khóa con 48 bit được tạo ra từ khóa chính 56 bit theo một chu trình tạo khóa con (key schedule) miêu tả ở phần sau.

      S-BOXES: 48 bit sau khi trộn được chia làm 8 khối con 6 bit và được xử lý qua hộp thay thế S-box. Đầu ra của mỗi khối 6 bit là một khối 4 bit theo một chuyển đổi phi tuyến được thực hiện bằng một bảng tra. Khối S-box đảm bảo phần quan trọng cho độ an toàn của DES. Nếu không có S-box thì quá trình sẽ là tuyến tính và việc thám mã sẽ rất đơn giản.

       Hàm S-boxes của DES biến đổi một số 48 bít thành một số 32 bít. Tuy nhiên, nếu chỉ lập một bảng tra cứu như ở TinyDES thì bảng này phải có 216 dòng và 232 cột, dẫn đến số phần tử của bảng rất lớn. Để giảm kích thước của bảng tra cứu, người ta chia hàm S-boxes thành 8 hàm S-box con, mỗi hàm biến đổi số 6 bít thành số 4 bít (hình dưới):

Hệ mật DES

Hàm S-box đầu tiên, hộp S1 có nội dung như sau:

Hệ mật DES

   Có thể thấy, mỗi hàm S con của S-box của là một phép thay thế Substitution.Các hàm S-box con không khả nghịch, do đó hàm S-boxes cũng không khả nghịch. Sự phức tạp này của S-boxes là yếu tố chính làm cho DES có độ an toàn cao.

    P-BOX: Cuối cùng, 32 bit thu được sau S-box sẽ được sắp xếp lại theo một thứ tự cho trước (còn gọi là P-box).

   Hàm P-box cũng thực hiện hoán vị 32 bít đầu vào theo quy tắc:

Hệ mật DES

4. Thuật toán sinh khóa:

Khóa K 64 bít ban đầu được rút trích và hoán vị thành một khóa 56 bít (tức chỉ sử dụng 56 bít) theo quy tắc PC-1:

Hệ mật DES

Khóa 56 bít này được chia thành 2 nửa trái phải KL0 và KR0, mỗi nửa có kích thước 28 bít. Tại vòng thứ i (i = 1, 2, 3,…,16) , KLi-1 và KRi-1 được dịch vòng trái ri bít để có được KLi và KRi, với ri được định nghĩa:

Hệ mật DES

Cuối cùng khóa Ki của mỗi vòng được tạo ra bằng cách hoán vị và nén 56 bít của KLi và KRi thành 48 bít theo quy tắc:

Hệ mật DES

KLi và KRi, với ri được định nghĩa: Các khóa con 48 bit được tạo thành bởi thuật toán lựa chọn 2 (Permuted Choice 2, hay PC-2) gồm 24 bit từ mỗi phần. Quá trình dịch bit (được ký hiệu là “<<<” trong sơ đồ) khiến cho các khóa con sử dụng các bit khác nhau của khóa chính; mỗi bit được sử dụng trung bình ở 14 trong tổng số 16 khóa con.

Hệ mật DES

    Qua sơ đồ thuật toán sinh khóa con có thể thấy rằng thực sự chỉ có 56 bit của khóa chính được sử dụng, 8 bit còn lại là mã kiểm tra chẵn lẻ (parity bits) và bị lọc ra ở biến đổi PC1. Các bộ biến đổi PC1 và PC2 chỉ đơn giản là các bộ vừa chọn lọc vừa hoán vị (PC = permuted choice = lựa chọncó hoán vị). Các biến đổi R1 và R2 (left rotate 1 bit và 2 bit) tương ứng là các phép đẩy bit trái 1 và 2 vị trí

     Ký hiệu : thể hiện phép toán XOR. Hàm F làm biến đổi một nửa của khối đang xử lý với một khóa con. Đầu ra sau hàm F được kết hợp với nửa còn lại của khối và hai phần được tráo đổi để xử lý trong chu trình kế tiếp. Sau chu trình cuối cùng thì 2 nửa không bị tráo đổi; đây là đặc điểm của cấu trúc Feistel khiến cho quá trình mã hóa và giải mã trở nên giống nhau.

5. Thuật toán giải mã DES

Đối với mã hóa DES thì thuật toán giải mã sẽ làm ngược lại các bước của thuật toán mã hóa ta sẽ có bản rõ ban đầu cần mã hóa.

Thuật toán giải mã được xây dựng giống hệt như thuật toán sinh mã nhưng có các khóa con được sử dụng theo thứ tự ngược lại, tức là dùng khóa K16 cho vòng lặp 1, khóa K15 cho vòng lặp 2 … Vì vậy, thuật toán giải mã có thể được viết lại dưới dạng công thức sau:

               DES-1= (IP)-1  Fxor T xor F xor T …  xor F15  xorT xor F16 xor (IP)

Bây giờ chú ý rằng mỗi hàm T (phép biến đổi L và R) hoặc F đều là các hàm có tính chất đối hợp (f = f-1, hay f (f(x) =x). Do đó nếu ta thực hiện phép tích hàm DES-1  DES hay DES  DES-1 thì sẽ thu được phép đồng nhất. Điều đó giải thích tại sao thuật toán giải mã lại giống hệt như sinh mã chỉ có khác về thứ từ trong chuỗi khóa con.

Độ an toàn của DES


1. Điểm yếu

Tính bù:

Ký hiệu  là phần bù của u (ví dụ 0100101 và 1011010 là bù của nhau) thì DES có tính chất sau:

                y = DESz(x) =>  =DESz ( )

   Cho nên nếu biết MÃ y được mã hóa từ TIN x với khóa z thì ta suy ra được mã hóa từ TIN  với khóa . Tính chất này chính là một điểm yếu của DES bởi vì nhờ đó kẻ tấn công có thể loại trừ một nửa số khóa cần phải thử khi tiến hành phép thử – giải mã theo kiểu tìm kiếm vét cạn không gian khóa.

Khóa yếu

    Các khóa yếu là các khóa mà theo thuật toán sinh khóa con thì tất cả 16 khóa con đều như nhau Z= Z2= Z3= …= Z15= Z16 điều đó khiến cho phép sinh mã và giải mã đối với các khóa yếu này là giống hệt nhau

                 DESz = DES-1z

Có tất cả 4 khóa yếu như sau:

      1) [00000001 00000001 … … 00000001]

      2) [11111110 11111110 … … 11111110]

      3) [11100000 11100000 11100000 11100000

      11110001 11110001 11110001 11110001]

      4) [00011111 00011111 00011111 00011111

      00001110 00001110 00001110 00001110]

Đồng thời có 10 khóa yếu với thuộc tính là tồn tại Z, Z’ sao cho

              DES-1z= DESz’ hay DES-1z’= DES

2. Các dạng tấn công DES:

     Tấn công vét cạn khóa (Brute Force Attack): Vì khóa của mã DES có chiều dài là 56 bít nên để tiến hành brute-force attack, cần kiểm tra 256 khóa khác nhau. Hiện nay với những thiết bị phổ dụng, thời gian gian để thử khóa là rất lớn nên việc phá mã là không khả thi (xem bảng). Tuy nhiên vào năm 1998, tổ chức Electronic Frontier Foundation (EFF) thông báo đã xây dựng được một thiết bị phá mã DES gồm nhiều máy tính chạy song song, trị giá khoảng 250.000$. Thời gian thử khóa là 3 ngày. Hiện nay mã DES vẫn còn được sử dụng trong thương mại, tuy nhiên người ta đã bắt đầu áp dụng những phương pháp mã hóa khác có chiều dài khóa lớn hơn (128 bít hay 256 bít) như TripleDES hoặc AES.

     Phá mã DES theo phương pháp vi sai (differential cryptanalysis) Năm 1990 Biham và Shamir đã giới thiệu phương pháp phá mã vi sai. Phương pháp vi sai tìm khóa ít tốn thời gian hơn brute-force. Tuy nhiên phương pháp phá mã này lại đòi hỏi phải có 247 cặp bản rõ – bản mã được lựa chọn (chosen-plaintext). Vì vậy phương pháp này là bất khả thi dù rằng số lần thử có thể ít hơn phương pháp brute-force.

     Phá mã DES theo phương pháp thử tuyến tính (linear cryptanalysis) Năm 1997 Matsui đưa ra phương pháp phá mã tuyến tính. Trong phương pháp này, cần phải biết trước 243 cặp bản rõ-bản mã (known-plaintext). Tuy nhiên 243 cũng là một con số lớn nên phá mã tuyến tính cũng không phải là một phương pháp khả thi.