Mã DES (Data Encryption Standard)

In document AN TOÀN VÀ BẢO MẬT THÔNG TIN (Page 43-49)

CHƯƠNG 3. MÃ HÓA ĐỐI XỨNG HIỆN ĐẠI

3.4 Mã DES (Data Encryption Standard)

43 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.

3.4 Mã DES (Data Encryption Standard)

44

Hình 3-6. Các vòng Feistel của mã DES

Sơ đồ mã DES trên 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.

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

Ta đánh số các bít của khối 64 bít theo thứ tự từ trái sang phải là 0, 1, …, 62, 63:

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

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

57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 56 48 40 32 24 16 8 0 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 Hoán vị khi to

Bn rõ 64 bít

….

Vòng 1 64

Vòng 2 64

Vòng 16

Đổi 2 nửa đầu, cuối

Hoán vị kết thúc

Khóa 64 bít

Dịch vòng trái Nén khóa

56 Nén khóa

Nén khóa

….

56

48 56

48 56

48 56

64 64

64

Bản mã 64 bít

Dịch vòng trái

Dịch vòng trái Hoán vị khóa

56

45 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 known-plaintext hay chosen-known-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.4.2 Các vòng của DES

Hình sau minh họa một vòng Feistel của DES

Hình 3-7. Cấu trúc một vòng của mã 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 S-boxes 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: đá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:

Li-1 Ri-1

Ki

Li Ri

32 Expand

S-boxes

P-box

32

32

48

32

32

Compress

28 28

48

28

KLi-1 KRi-1

Left Shift

KLi KRi

Left Shift 28 39 7 47 15 55 23 63 31

38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 32 0 40 8 48 16 56 24

46

S-boxes:

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 S-box đầu tiên, hộp S1, giống hoàn toàn như S-box của TinyDES, tức có nội dung như sau:

Chi tiết các hộp còn lại được trình bày trong Phụ lục 1. Có thể thấy, mỗi hàm S-box con 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: hàm P-box cũng thực hiện hoán vị 32 bít đầu vào theo quy tắc:

3.4.3 Thuật toán sinh khóa con của DES

15 6 19 20 28 11 27 16 0 14 22 25 4 17 30 9 1 7 23 13 31 26 2 8 18 12 29 5 21 10 3 24

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 00 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 0111 01 0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 1000 10 0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 0000 11 1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101

\

b1b2 b3b4

b0b5

48 bít

S1 S2 S3 S4 S5 S6 S7 S8

32 bít

31 0 1 2 3 4 3 4 5 6 7 8 7 8 9 10 11 12 11 12 13 14 15 16 15 16 17 18 19 20 19 20 21 22 23 24 23 24 25 26 27 28 27 28 29 30 31 0

48 bít

47 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:

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:

1 1 2 9 16 2

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:

3.4.4 Hiệu ứng lan truyền (Avalanche Effect)

Một tính chất quan trọng cần thiết của mọi thuật toán mã hóa là chỉ cần một thay đổi nhỏ trong bản rõ hay trong khóa sẽ dẫn đến thay đổi lớn trong bản mã. Cụ thể, chỉ cần thay đổi một bít trong bản rõ hay khóa thì dẫn đến sự thay đổi của nhiều bít bản mã. Tính chất này được gọi là hiệu ứng lan truyền. Nhờ có tính chất này mà người phá mã không thể giới hạn miền tìm kiếm của bản rõ hay của khóa (dù phá mã theo known-plaintext hay chosen-plaintext) nên phải thực hiện vét cạn khóa.

DES là một phương pháp mã hóa có hiệu ứng lan truyền này. Xét hai bản rõ sau (64 bít):

P1: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 P2: 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

Hai bản rõ trên được mã hóa bằng DES với khóa:

K: 0000001 1001011 0100100 1100010 0011100 0011000 0011100 0110010 Bảng 2-1.a cho biết số bít khác nhau của bản mã tương ứng với P1 và P2 qua các vòng của DES:

13 16 10 23 0 4 2 27 14 5 20 9 22 18 11 3 25 7 15 6 26 19 12 1 40 51 30 36 46 54 29 39 50 44 32 47 43 48 38 55 33 52 45 41 49 35 28 31

56 48 40 32 24 16 8 0 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 60 52 44 36 28 20 12 4 27 19 11 3

56 bít

48 bít

48

Vòng thứ Số bít khác nhau Vòng thứ Số bít khác nhau

0 1 0 0

1 6 1 2

2 21 2 14

3 35 3 28

4 39 4 32

5 34 5 30

6 32 6 32

7 31 7 35

8 29 8 34

9 42 9 40

10 44 10 38

11 32 11 31

12 30 12 33

13 30 13 28

14 26 14 26

15 29 15 34

16 34 16 35

a) b)

Bảng 3-1. Hiệu ứng lan truyền

Chỉ cần đến vòng thứ 2, số bít khác nhau giữa hai bản mã đã là 21 bít, sau 16 vòng số bít khác nhau là 34 bít (khoảng 1/2 tổng số bít của bản rõ)

Xét bản rõ sau (64 bít):

P: 01101000 10000101 00101111 01111010 00010011 01110110 11101011 10100100 Dùng hai khóa sau đây để mã hóa bản rõ trên (hai khóa này chỉ khác nhau 1 bít):

K1: 1110010 1111011 1101111 0011000 0011101 0000100 0110001 11011100 K2: 0110010 1111011 1101111 0011000 0011101 0000100 0110001 11011100 Bảng 2-1.b cho biết số bít khác nhau của bản mã tương ứng với K1 và K2 qua các vòng của DES. Sau 16 vòng, số bít khác nhau là 35 bít, cũng khoảng 1/2 tổng số bít của bản rõ.

3.4.5 Độ an toàn của DES

Ta hãy xem xét tính an toàn của DES trước một vài phương pháp tấn công phá mã.

1) 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.

49 2) 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.

3) 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.

3.5 Một số phương pháp mã khối khác

In document AN TOÀN VÀ BẢO MẬT THÔNG TIN (Page 43-49)