Mã đối xứng hiện đại - Mã khối

• Mã khối (Block Cipher) • Mã khối an toàn lý tưởng Phép toán XOR có một hạn chế là chỉ cần biết một cặp khối bản rõ và bản mã, người ta có thể dễ dàng suy ra được khóa và dùng khóa đó để giải các khối bản mã khác (known- plaintext attack). Xét lại ví dụ đầu chương: Bản rõ: 1111 0000 0011 Khóa: 0101 0101 0101 Bản mã: 1010 0101 0110 Nếu biết bản mã c0 = 1010 Có bản rõ tương ứng là p0 = 1111 Thì có thể dễ dàng suy ra khóa là k = 0101. Nói một cách tổng quát, nếu giữa bản rõ P và bản mã C có mối liên hệ toán học thì việc biết một số cặp bản rõ-bản mã giúp ta có thể tính được khóa K. Do đó để chống phá mã trong trường hợp known-plaintext hay choosen-plaintext, chỉ có thể là làm cho P và C không có mối liên hệ toán học. Điều này chỉ có thể thực hiện được nếu ta lập một bản tra cứu ngẫu nhiên giữa bản rõ và bản mã. Ví dụ: Lúc này khóa là toàn bộ bảng trên. Người gởi cũng như người nhận phải biết toàn bộ bảng trên để mã hóa và giải mã. Đối với người phá mã, nếu biết một số cặp bản rõ - bản mã thì cũng chỉ biết được một phần của bảng tra cứu trên. Do đó không suy ra được bản rõ cho các bản mã còn lại. Hay nói cách khác, muốn phá mã thì phải biết được tất cả các cặp bản rõ và bản mã. Nếu chọn kích thước của khối là 64 bít thì số dòng của bảng khóa là 264, một con số rất lớn (và có khoảng 264! bảng khóa như vậy). Lúc này việc nắm tất cả các cặp bản rõ-bản mã của bảng khóa là điều không thể đối với người phá mã. Trường hợp này ta gọi là mã khối an toàn lý tưởng. Tuy nhiên, khi kích thước khối lớn thì số dòng của bảng khóa cũng lớn và gây trở ngại cho việc lưu trữ cũng như trao đổi khóa giữa người gởi và người nhận. Bảng khóa có 264 dòng mỗi dòng 64 bít do đó kích thước khóa sẽ là 64x 264= 270 ≈ 1021 bít. Do đó mã khối an toàn lý tưởng là không khả thi trong thực tế. Mạng SPN Trong thực tế, người ta chỉ tìm cách để chỉ cần dùng một khóa có kích thước ngắn để giả lập một bảng tra cứu có độ an toàn xấp xỉ độ an toàn của mã khối lý tưởng. Cách thực hiện là kết hợp hai hay nhiều mã hóa đơn giản lại với nhau để tạo thành một mã hóa tổng (product cipher), trong đó mã hóa tổng an toàn hơn rất nhiều so với các mã hóa thành phần. Các mã hóa đơn giản thường là phép thay thế (substitution, S-box) và hoán vị (Permutation, P-box). Do đó người ta hay gọi mã hóa tổng là Substitution-Permutation Network (mạng SPN). Hình dưới minh họa một mạng SP. Việc kết hợp các S-box và P-box tạo ra hai tính chất quan trọng của mã hóa là tính khuếch tán (diffusion) và tính gây lẫn (confusion). Hai tính chất này do Claude Shannon giới thiệu vào năm 1946, và là cơ sở của tất cả các mã khối hiện nay. Tính khuếch tán: một bít của bản rõ tác động đến tất cả các bít của bản mã, hay nói cách khác, một bít của bản mã chịu tác động của tất cả các bít trong bản rõ. Việc làm như vậy nhằm làm giảm tối đa mối liên quan giữa bản rõ và bản mã, ngăn chặn việc suy ra lại khóa. Tính chất này có được dựa vào sử dụng P-box kết hợp S-box. Tính gây lẫn: làm phức tạp hóa mối liên quan giữa bản mã và khóa. Do đó cũng ngăn chặn việc suy ra lại khóa. Tính chất này có được dựa vào sử dụng S-box. Mô hình mã Feistel Mô hình mã Feistel là một dạng tiếp cận khác so với mạng SP. Mô hình do Horst Feistel đề xuất, cũng là sự kết hợp các phép thay thế và hoán vị. Trong hệ mã Feistel, bản rõ sẽ được biến đổi qua một số vòng để cho ra bản mã cuối cùng: F là một hàm mã hóa dùng chung cho tất cả các vòng. Hàm F đóng vai trò như là phép thay thế còn việc hoán đổi các nửa trái phải có vai trò hoán vị. Bản mã C được tính từ kết xuất của vòng cuối cùng: C = Cn = (Ln, Rn) Để giải mã quá trình được thực hiện qua các vòng theo thứ tự ngược lại: Và cuối cùng bản rõ là P = (L0, R0). Hệ mã Feistel có điểm quan trọng là việc chia các bản mã thành hai nửa trái phải giúp cho hàm F không cần khả nghịch (không cần có F-1). Mã hóa và giải mã đều dùng chiều thuận của hàm F. Hàm F và thuật toán sinh khóa con càng phức tạp thì càng khó phá mã. Ứng với các hàm F và thuật toán sinh khóa con khác nhau thì ta sẽ có các phương pháp mã hóa khác nhau, phần tiếp theo sẽ trình bày mã hóa DES, là một phương pháp mã hóa dựa trên nguyên tắc của hệ mã Feistel. • Mã TinyDES Vào năm 1973, khi lĩnh vực máy tính ngày càng phát triển, nhu cầu ứng dụng bảo mật vào các mục đích dân sự được đặt ra. Lúc này Cục tiêu chuẩn quốc gia Hoa Kỳ kêu gọi các công ty Mỹ thiết lập một chuẩn mã hóa quốc gia. Mã hóa Lucifer của công ty IBM được chọn và sau một vài sửa đổi của cơ quan an ninh Hoa Kỳ, mã hóa Lucifer đã trở thành mã tiêu chuẩn DES (Data Encryption Standard). Qua quá trình sử dụng mã DES đã chứng tỏ độ an toàn cao và được sử dụng rộng rãi. Tương tự như mã dòng A5/1 và RC4, chúng ta cũng sẽ xem xét một mô hình thu nhỏ của mã DES là TinyDES. Mã TinyDES có các tính chất sau: Là mã thuộc hệ mã Feistel gồm 3 vòng  Kích thước của khối là 8 bít Kích thước khóa là 8 bít Mỗi vòng của TinyDES dùng khóa con có kích thước 6 bít được trích ra từ khóa chính. Sơ đồ mã TinyDES trên gồm hai phần, phần thứ nhất là các vòng Feistel, phần thứ hai 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. Các vòng của TinyDES Hình sau minh họa một vòng Feistel của TinyDES Trong đó hàm Expand vừa mở rộng vừa hoán vị Ri-1 từ 4 bít lên 6 bít. Hàm S-boxes biến đổi một số 6 bít đầu vào thành một số 4 bít đầu ra. Hàm P-box là một hoán vị 4 bít. Mô tả của các hàm trên là như sau:  Expand: gọi 4 bít của Ri-1 là: b0b1b2b3. Hàm Expand hoán vị và mở rộng 4 bít thành 6 bít cho ra kết quả: b2b3b1b2b1b0. Ví dụ: R0 = 0110 Expand(R0) = 101110  S-box: Gọi b0b1b2b3b4b5 là 6 bít đầu vào của S-box, ứng với mỗi trường hợp của 6 bít đầu vào sẽ có 4 bít đầu ra. Việc tính các bít đầu ra dựa trên bảng sau: Hai bít b0b1 xác định thứ tự hang.  Bốn bít b1b2b3b4 xác định thứ tự cột của bảng. Từ đó dựa vào bảng tính được 4 bít đầu ra. Để cho đơn giản, ta có thể viết lại bảng trên dưới dạng số thập lục phân. Ví dụ: X = 101010. Tra bảng ta có S-box(X) = 0110. P-box: Thực hiện hoán vị 4 bít đầu b0b1b2b3 cho ra kết quả b2b0b3b1. Thuật toán sinh khóa con của TinyDES Khóa K 8 bít ban đầu được chia thành 2 nửa trái phải KL0 và KR0 , mỗi nửa có kích thước 4 bít. Tại vòng thứ nhất KL0 và KR0 được dịch vòng trái 1 bít để có được KL1 và KR1. Tại vòng thứ hai KL1 và KR1 được dịch vòng trái 2 bít để có được KL2 và KR2. Tại vòng tại vòng thứ 3 KL2 và KR2 được dịch vòng trái 1 bít để có KL3 và KR3. 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 (compress) 8 bít của: KLi và KRi (k0k1k2k3k4k5k6k7) Thành kết quả gồm 6 bít : k5k1k3k2k7k0. Ví dụ vềTinyDES Ví dụ: mã hóa bản rõ P = 0101.1100 (5C) với khóa K = 1001.1010 TinyDES Khả năng chống phá mã known-plaintext của TinyDES : Xét trường hợp mã TinyDES chỉ có 1 vòng, tức P = (L0, R0) và C = (L1, R1). Trong trường hợp này người phá mã biết P và C, tuy nhiên không biết K. Giả sử P = 0101.1100 và C = 1100.0001. Người phá mã tiến hành tính K như sau: Từ R0 tính X =001011. Từ L0 và R1 tính Z = 0100, và từ Z tính Y = 1000. Tra cứu bảng S-box với đầu ra là 1000, ta xác định được các đầu vào X K1 có thể xảy ra là: {100101, 100111, 001110, 011111} Như vậy khóa K1 là một trong các giá trị {101110, 101100, 000101, 010100} Thử tiếp với 1 vài cặp bản rõ-bản mã khác ta sẽ tìm được K1 = 101110 và từ đó tính được K = 1001.1010 Tuy nhiên với mã TinyDES ba vòng, việc phá mã không còn đơn giản như vậy, người phá mã chỉ biết được input của vòng đầu là P và output của vòng cuối là C. Giá trị trung gian L1R1, L2R2 bị ẩn giấu nên không thể giới hạn miền tìm kiếm của các khóa K1, K2, K3 theo phương pháp trên. Dưới tác động của S-box, việc thay đổi 1 bít trong bản rõ hoặc khóa K sẽ ảnh hưởng đến nhiều bít khác nhau trong các giá trị trung gian L1R1, L2R2 (trong phần mã DES ta sẽ gọi là hiệu ứng lan truyền), nên khó phân tích mối liên quan giữa bản rõ, bản mã và khóa. Việc phá mã còn khó khăn hơn nữa trong trường hợp mã DES gồm 16 vòng và kích thước khối là 64 bít.