Mã Hóa DES

Giới Thiệu

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

11.     Thuật toán mã hóa DES

1.1.    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ì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.

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

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

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

1.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ình 1.3. Cấu trúc một vòng của DES

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

      F (R_i-1, K_i) = P-box(S-boxes (Expand (R_i-1) K_i))

Trong đó hàm Expand vừa mở rộng vừa hoán vị R_i-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 R_i-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:

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 S-box đầu tiên, hộp S1 có nội dung như sau:

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:

1.4.         Thuật toán sinh khóa con của DES:

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:

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

Cuối cùng khóa K_i 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 KL_i và KR_i thành 48 bít theo quy tắc:

KL_i và KR_i, với r_i đượ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.

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.

22.    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  F₁ xor T xor F₂  xor T ...  xor F₁₅  xorT xor F₁₆ 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.

33.     Độ an toàn của DES

3.1.         Điểm yếu của DES

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 = DES_z(x) =>  =DES_z ( )

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₁ = Z₂= Z₃= ...= Z₁₅= Z₁₆ đ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

 DES_z = 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= DES_z’ hay DES^-1z’= DES

3.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 2⁵⁶ 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ó 2⁴⁷ 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 2⁴³ cặp bản rõ-bản mã (known-plaintext). Tuy nhiên 2⁴³ 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.

Thuật toán Bình phương và nhân

Thuật toán bình phương và nhân là thuật toán  tính nhanh lũy thừa  tự nhiên của một số
(thực hoặc nguyên), trong trường hợp cơ số là số nguyên có thể được rút gọn theo
một môđun  nào đó. Được sử dụng nhiều trong các bài toán mã hóa và giải mã các hệ mã
hóa, đặc biệt là hệ mã hóa công khai.
Tính a^x mod n
Tạo bảng:

Với điều kiện chủ chốt là: X lẻ thì tính, X chẵn thì bỏ qua.
VD 15^35 mod 79

Ta có giả mã của thuật toán bình phương và nhân như sau:

Add new Section to PE file

Bài viết này tôi sẽ nói về cách để thêm một section mới vào trong PE file, và ở đây tôi có việt một chương trình bằng python để dễ dàng thực hiện hơn.

- Đầu tiên để có thể thêm được một section mới ta phải hiểu được cấu trúc file PE, nếu chưa hiểu, bạn nên tìm hiểu về cấu trúc file PE trước.

- Ta sẽ thực hiện các bước sau:

Bước 1: Thay đổi giá trị trong phần PE header:

            + NumberOfSection: Số lượng section trong file PE cần thêm(Tăng giá trị của nó lên)

            + SizeOfImage: tổng kích thước cảu file PE. giá trị này cần thay đổi vì khi thêm mới section kích thước của file sẽ tăng lên.

(size_new = sizeOfImage + sizeSection_new + FileAlignment).

Bước 2: Lấy thông tin của section cuối cùng của file :

-    Virtual Size:  kích thước trên bộ nhớ.

-Virtual Address: địa chỉ trên bộ nhớ.

-Size to Raw data: kích thước của section trên file.

-Pointer to Raw data: offset trỏ đến phần dữ liệu của section đó.

+ Ví dụ: trong file demo ta có thông tin của section .rsrc:

Virtual Size:  8e00

Virtual Address: 34000

Size to Raw data: 2f400

Pointer to Raw data: 8e00

Section Aligenment: 1000

File Aligenment : 200

Bước 3: Điền thông tin vào section table của section mới được tạo, gồm những thông tin:

  - Virtual Size : kích thước trên bộ nhớ của section mới(tùy chọn)

  - Virtual Address: VS(section cuối) + VA(section cuối) và làm tròn với giá trị của section aligenment

Ví dụ: section cuối :Virtual Size:  8e00 ; Virtual Address: 34000 ;section aligenment : 1000

tổng VS + VA = 3ce00 và làm tròn lên sẽ thành = > 3d000

Như vậy virtual address của section mới sẽ là 3d000.

  - Size to Raw data: kích thước của section mới trên file(tùy chọn)

  - Pointer to Raw data:

    - ta có thể tìm đến cuối file và chọn giá trị offset cuối cùng.

    - hoặc sẽ lấy : sizeRaw(section cuối) + pointerRaw(section cuối) và làm tròn với giá trị của File Aligenment

Bước 4 : Sử dụng chương trình hex editer để thêm các byte opcode cho section mới:

- Còn đây là chương trình tôi code bằng python để thêm section mới:

https://www.dropbox.com/s/m05b5pe443g7a75/add_section.py?dl=0

Xây dựng hệ thống phân tích malware tự động

Với mục tiêu xây dựng mộ hệ thống phân tích malware tương tự như Virustotal, Malwr , ta có thể tự mình triển khai một hệ thống phân tích malware cho riêng mình, điều này sẽ hỗ trợ rất tốt cho những người nào làm về malware analysis.

 Hệ thống này là sự kết hợp của 2 phương pháp phân tích tĩnh và phân tích động, thường được sử dụng để có thể phân tích malware hiện nay. Bài viết này tôi sẽ xử dụng cuckoo như là core của hệ thống , xây dựng các sanbox để thực thi malware và tiến hành theo dõi và ghi lại các hành vi trong quá trình mã độc được thực thi.

   Và trước khi ta đi vào xây dựng hệ thống ta cần xác định:

    -  Các loại file ta sẽ phân tích : các file thực thi(.exe...), file văn bản(.pdf..)

    -  nền tảng ta muốn sử dụng để chạy hệ thống: server sử dụng là ubuntu, các sanbox sẽ cài hệ điều hành windows XP sp3

    - Những thông tin ta cần từ file ta phân tích.

Từ việc xác định được những gì cần phân tích ta đi đến phần thiết lập, cài đặt hệ thống.
Đầu tiên.:
1. Cài đặt server:
     - ở đây ta sẽ cài đặt ubuntu server, hay cũng có thể cài đặt ubuntu cho có giao diện dễ thao tác.
    - tiếp đến ta sẽ cài đặt máy ảo virtualbox lên server.
    - Sau đó , sẽ cài đặt hệ điều hành windows XP sp3 trên máy ảo đó.