Category Archives: Crypto

Tổng quan về Cryptography

Bài viết hy vọng có thể giúp ích cho những ai mong muốn tìm hiểu lĩnh vực nghiên cứu về việc giấu thông tin và tìm hiểu một số phương pháp tấn công hệ thống thông tin mã hóa.

Cryptography, được dịch là “mật mã học”, là một ngành có nhiều thuật ngữ có thể làm cho nhiều người “ngơ ngác”: như “hash function”, “one-time pad” hay Rijndael… Bài viết này giải thích các khái niệm thường dùng trong ngành mật mã học, hy vọng có thể giúp ích cho những ai mong muốn tìm hiểu về lĩnh vực này.

Cryptography (hay crypto) – mật mã học – ngành khoa học nghiên cứu về việc giấu thông tin. Cụ thể hơn, mật mã học là ngành học nghiên cứu về những cách chuyển đổi thông tin từ dạng “có thể hiểu được” thành dạng “không thể hiểu được” và ngược lại. Cryptography giúp đảm bảo những tính chất sau cho thông tin:

• Tính bí mật (confidentiality): thông tin chỉ được tiết lộ cho những ai được phép.

• Tính toàn vẹn (integrity): thông tin không thể bị thay đổi mà không bị phát hiện.

• Tính xác thực (authentication): người gửi (hoặc người nhận) có thể chứng minh đúng họ.

• Tính không chối bỏ (non-repudiation): người gửi hoặc nhận sau này không thể chối bỏ việc đã gửi hoặc nhận thông tin.

Mật mã có rất nhiều ứng dụng trong thực tế như bảo vệ giao dịch tài chính (rút tiền ngân hàng, mua bán qua mạng), bảo vệ bí mật cá nhân… Nếu kẻ tấn công đã vượt qua tường lửa và các hệ thống bảo vệ khác thì mật mã chính là hàng phòng thủ cuối cùng cho dữ liệu của bạn.

Cần phân biệt khái niệm cryptography với khái niệm steganography (tạm dịch là giấu thông tin). Điểm khác nhau căn bản nhất giữa hai khái niệm này là: cryptography là việc giấu nội dung của thông tin, trong khi steganography là việc giấu sự tồn tại của thông tin đó.

Sơ đồ mã hóa vã giải mã một thông điệp

Cryptosystem (viết tắt của cryptographic system): hệ thống mã hóa thông tin, có thể là phần mềm như PGP, Ax-Crypt, Truecrypt… giao thức như SSL, IPsec… hay đơn giản là một thuật toán như DES.

Encrypt (encipher): mã hóa – quá trình biến đổi thông tin từ dạng ban đầu – có thể hiểu được thành dạng không thể hiểu được, với mục đích giữ bí mật thông tin đó.

Decrypt (decipher): giải mã – quá trình ngược lại với mã hóa, khôi phục lại thông tin ban đầu từ thông tin đã được mã hóa.

Plaintext (cleartext): dữ liệu gốc (chưa được mã hóa).

Ciphertext: dữ liệu đã được mã hóa.

Lưu ý: từ text (hay message) ở đây được dùng theo quy ước, được hiểu là tất cả những dữ liệu được mã hóa (hay giải mã) chứ không chỉ là văn bản chữ như nghĩa thông thường. Khi dịch ra tiếng Việt, từ “văn bản” và từ “thông điệp” cũng tuân theo quy ước tương tự.

Cipher (hay cypher): thuật toán dùng để thực hiện quá trình mã hóa hay giải mã. Trong khuôn khổ bài viết này gọi tắt là thuật toán.

Key: chìa khóa – thông tin dùng cho qui trình mã hóa và giải mã.

Code: cần phân biệt code trong mật mã học với code trong lập trình hay code trong Zip code… Trong cryptography, code (mã) có ý nghĩa gần như là cipher (thuật toán). Chúng chỉ khác nhau ở chỗ: code biến đổi thông tin ở tầng nghĩa (từ, cụm từ) còn cipher biến đổi thông tin ở tầng thấp hơn, ví dụ chữ cái (hoặc cụm chữ cái) đối với các thuật toán cổ điển hay từng bit (hoặc nhóm bit) đối với các thuật toán hiện đại.

Cryptanalysis: nếu coi mật mã học là việc cất dữ liệu của bạn vào một cái hộp sau đó dùng chìa khóa khóa lại, thì cryptanalysis là ngành nghiên cứu những phương pháp mở hộp để xem dữ liệu khi không có chìa khóa.

KHÁI NIỆM VỀ CHÌA KHÓA

Password: mật khẩu, là một hay nhiều từ mà người dùng phải biết để được cấp quyền truy cập.

Trong thực tế, mật khẩu do người dùng tạo ra thường không đủ độ an toàn để được dùng trực tiếp trong thuật toán. Vì vậy, trong bất cứ hệ thống mã hóa dữ liệu nghiêm túc nào cũng phải có bước chuyển đổi mật khẩu ban đầu thành chìa khóa có độ an toàn thích hợp. Bước tạo chìa khóa này thường được gọi là key derivation, key stretching hay key initialization.

Key Derivation Function: là một hàm hash (sẽ giải thích rõ hơn ở phần sau) được thiết kế sao cho chìa an toàn hơn đối với tấn công kiểu brute-force hay cổ điển. Hàm này được thực hiện lại nhiều lần trên mật khẩu ban đầu cùng với một số ngẫu nhiên để tạo ra một chìa khóa có độ an toàn cao hơn. Số ngẫu nhiên này gọi là salt, còn số lần lặp lại là iteration.

Ví dụ một mật khẩu là “pandoras B0x”, cùng với salt là “230391827″, đi qua hàm hash SHA-1 1000 lần cho kết quả là một chìa khóa có độ dài 160 bit như sau: 3BD454A72E0E7CD6959DE0580E3C19F51601C359 (thể hiện dưới dạng số thập lục phân).

Keylength (Keysize): Độ dài (hay độ lớn) của chìa khóa. Nói một chìa khóa có độ dài 128 bit có nghĩa chìa đó là một số nhị phân có độ dài 128 chữ số. Một thuật toán có chìa khóa càng dài thì càng có nhiều khả năng chống lại tấn công kiểu brute-force.

THUẬT TOÁN MÃ HÓA

Cổ điển

• Substitution: thay thế – phương pháp mã hóa trong đó từng kí tự (hoặc từng nhóm kí tự) của văn bản ban đầu được thay thế bằng một (hay một nhóm) kí tự khác. Tuy không còn được sử dụng nhưng ý tưởng của phương pháp này vẫn được tiếp tục trong những thuật toán hiện đại.

• Transposition: hoán vị – phương pháp mã hóa trong đó các kí tự trong văn bản ban đầu chỉ thay đổi vị trí cho nhau còn bản thân các kí tự không hề bị biến đổi.

Hiện đại

• Symmetric cryptography: mã hóa đối xứng, tức là cả hai quá trình mã hóa và giải mã đều dùng một chìa khóa. Để đảm bảo tính an toàn, chìa khóa này phải được giữ bí mật. Vì thế các thuật toán loại này còn có tên gọi khác là secret key cryptography (hay private key cryptography), tức là thuật toán mã hóa dùng chìa khóa riêng (hay bí mật). Các thuật toán loại này lý tưởng cho mục đích mã hóa dữ liệu của cá nhân hay tổ chức đơn lẻ nhưng bộc lộ hạn chế khi thông tin đó phải được chia sẻ với một bên thứ hai.

Giả sử nếu Alice chỉ gửi thông điệp đã mã hóa cho Bob mà không hề báo trước về thuật toán sử dụng, Bob sẽ chẳng hiểu Alice muốn nói gì. Vì thế bắt buộc Alice phải thông báo cho Bob về chìa khóa và thuật toán sử dụng tại một thời điểm nào đó trước đấy. Alice có thể làm điều này một cách trực tiếp (mặt đối mặt) hay gián tiếp (gửi qua email, tin nhắn…). Điều này dẫn tới khả năng bị người thứ ba xem trộm chìa khóa và có thể giải mã được thông điệp Alice mã hóa gửi cho Bob.

Mã hóa đối xứng có thể phân thành hai nhóm phụ:

– Block ciphers: thuật toán khối – trong đó từng khối dữ liệu trong văn bản ban đầu được thay thế bằng một khối dữ liệu khác có cùng độ dài. Độ dài mỗi khối gọi là block size, thường được tính bằng đơn vị bit. Ví dụ thuật toán 3-Way có kích thước khối bằng 96 bit.

– Stream ciphers: thuật toán dòng – trong đó dữ liệu đầu vào được mã hóa từng bit một. Các thuật toán dòng có tốc độ nhanh hơn các thuật toán khối, được dùng khi khối lượng dữ liệu cần mã hóa chưa được biết trước, ví dụ trong kết nối không dây. Có thể coi thuật toán dòng là thuật toán khối với kích thước mỗi khối là 1 bit.

• Asymmetric cryptography: mã hóa bất đối xứng, sử dụng một cặp chìa khóa có liên quan với nhau về mặt toán học, một chìa công khai dùng để mã hoá (public key) và một chìa bí mật dùng để giải mã (private key). Một thông điệp sau khi được mã hóa bởi chìa công khai sẽ chỉ có thể được giải mã với chìa bí mật tương ứng. Do các thuật toán loại này sử dụng một chìa khóa công khai (không bí mật) nên còn có tên gọi khác là public-key cryptography (thuật toán mã hóa dùng chìa khóa công khai).

Quay lại với Alice và Bob, nếu Alice muốn gửi một thông điệp bí mật tới Bob, cô ta sẽ tìm chìa công khai của Bob. Sau khi kiểm tra chắc chắn chìa khóa đó chính là của Bob chứ không của ai khác (thông qua chứng chỉ điện tử – digital certificate), Alice dùng nó để mã hóa thông điệp của mình và gửi tới Bob. Khi Bob nhận được bức thông điệp đã mã hóa anh ta sẽ dùng chìa bí mật của mình để giải mã nó. Nếu giải mã thành công thì bức thông điệp đó đúng là dành cho Bob. Alice và Bob trong trường hợp này có thể là hai người chưa từng quen biết. Một hệ thống như vậy cho phép hai người thực hiện được giao dịch trong khi không chia sẻ trước một thông tin bí mật nào cả.

Một trong những hạn chế của các thuật toán mã hóa bất đối xứng là tốc độ chậm, do đó trong thực tế người ta thường sử dụng một hệ thống lai tạp trong đó dữ liệu được mã hóa bởi một thuật toán đối xứng, chỉ có chìa dùng để thực hiện việc mã hóa này mới được mã hóa bằng thuật toán bất đối xứng.

MỘT SỐ PHƯƠNG PHÁP TẤN CÔNG HỆ THỐNG THÔNG TIN MÃ HÓA
Bất cứ ai cũng có thể tạo ra một hệ thống thông tin mã hóa cho riêng mình. Nhưng để có một hệ thống an toàn và hiệu quả đòi hỏi người thiết kế phải có kiến thức toán học sâu sắc, có kinh nghiệm về bảo mật và am hiểu các phương pháp tấn công.
• Brute-force attack (exhaustive key search): phương pháp tấn công bằng cách thử tất cả những chìa khóa có thể có. Đây là phương pháp tấn công thô sơ nhất và cũng khó khăn nhất.
Theo lý thuyết, tất cả các thuật toán hiện đại đều có thể bị đánh bại bởi brute-force nhưng trong thực tiễn việc này chỉ có thể thực hiện được trong thời gian hàng triệu, thậm chí hàng tỉ năm. Vì thế có thể coi một thuật toán là an toàn nếu như không còn cách nào khác để tấn công nó dễ hơn là brute-force.
Ví dụ: Thuật toán DES có độ dài chìa khóa là 56 bit tức là có tổng cộng tất cả 256 chìa để dùng. Nếu ai đó muốn “bẻ khoá” DES bằng cách thử hàng loạt chìa (brute-force attack) thì sẽ phải thử đến 256 lần (khoảng hơn 70 triệu tỉ lần).
• Frequency analysis: thống kê tần suất, chỉ có thể áp dụng được đối với các thuật toán cổ điển dùng phương pháp thay thế, ví dụ phương pháp Caesar. Để thực hiện phương pháp này ta cần một lượng văn bản đã mã hóa đủ lớn để phép thống kê được chính xác. Ngoài ra còn phải biết ngôn ngữ sử dụng trong văn bản ban đầu, nếu văn bản ban đầu là tiếng Anh thì nhiều khả năng kí tự xuất hiện nhiều nhất trong văn bản đã mã hóa là do chữ e mã hóa thành, kí tự nhiều thứ nhì bắt nguồn từ chữ a…
• Differential cryptanalysis: Eli Biham và Adi Shamir tìm ra phương pháp này vào khoảng cuối những năm 1980; nó thường được sử dụng để tấn công các thuật toán khối (block cipher – sẽ nói rõ hơn ở phần sau). Phương pháp này dựa trên việc phân tích những biến đổi của hai văn bản gốc có liên quan khi được mã hóa bởi cùng một chìa.
Còn rất nhiều phương pháp khác như Mod-n cryptanalysis, Linear cryptanalysis, Birthday attack, Algebraic attack… mà bất cứ ai thiết kế hệ thống mã hóa cũng phải chú ý tới.

Một số thuật toán nổi tiếng

• One-time Pad (OTP): xuất hiện từ đầu thế kỉ 20 và còn có tên gọi khác là Vernam Cipher, OTP được mệnh danh là cái chén thánh của ngành mã hóa dữ liệu. OTP là thuật toán duy nhất chứng minh được về lý thuyết là không thể phá được ngay cả với tài nguyên vô tận (tức là có thể chống lại kiểu tấn công brute-force). Để có thể đạt được mức độ bảo mật của OTP, tất cả những điều kiện sau phải được thỏa mãn:

– Độ dài của chìa khóa phải đúng bằng độ dài văn bản cần mã hóa.

– Chìa khóa chỉ được dùng một lần.

– Chìa khóa phải là một số ngẫu nhiên thực.

Mới nghe qua có vẻ đơn giản nhưng trong thực tế những điều kiện này khó có thể thỏa mãn được. Giả sử Alice muốn mã hóa chỉ 10MB dữ liệu bằng OTP, cô ta phải cần một chìa khóa có độ dài 10MB. Để tạo ra một số ngẫu nhiên lớn như vậy Alice cần một bộ tạo số ngẫu nhiên thực (TRNG – True Random Number Generator). Các thiết bị này sử dụng nguồn ngẫu nhiên vật lý như sự phân rã hạt nhân hay bức xạ nền vũ trụ. Hơn nữa việc lưu trữ, chuyển giao và bảo vệ một chìa khóa như vậy cũng hết sức khó khăn.

Dễ dàng hơn, Alice cũng có thể dùng một bộ tạo số ngẫu nhiên ảo (PRNG – Pseudo Random Number Generator) nhưng khi đó mức độ bảo mật giảm xuống gần bằng zero hay cùng lắm chỉ tương đương với một thuật toán dòng như RC4 mà thôi.

Do có những khó khăn như vậy nên việc sử dụng OTP trong thực tế là không khả thi.

• DES: viết tắt của Data Encryption Standard. DES là một thuật toán khối với kích thước khối 64 bit và kích thước chìa 56 bit. Tiền thân của nó là Lucifer, một thuật toán do IBM phát triển. Cuối năm 1976, DES được chọn làm chuẩn mã hóa dữ liệu của nước Mỹ, sau đó được sử dụng rộng rãi trên toàn thế giới. DES cùng với mã hóa bất đối xứng đã mở ra một thời kì mới cho ngành mã hóa thông tin. Trước DES, việc nghiên cứu và sử dụng mã hóa dữ liệu chỉ giới hạn trong chính phủ và quân đội. Từ khi có DES, các sản phẩm sử dụng nó tràn ngập thị trường. Đồng thời, việc nghiên cứu mã hóa thông tin cũng không còn là bí mật nữa mà đã trở thành một ngành khoa học máy tính bình thường.

Trong khoảng 20 năm sau đó, DES đã trải qua nhiều khảo sát, phân tích kỹ lưỡng và được công nhận là an toàn đối với các dạng tấn công (tất nhiên, ngoại trừ brute-force).

Tới tháng 7 năm 1998, EFF (Electronic Frontier Foundation) đã “brute-force” thành công DES trong 56 giờ. Ít lâu sau đó cùng với mạng tính toán ngang hàng Distribute.net, tổ chức này đã lập nên kỉ lục mới là 22 giờ 15 phút. Sự kiện này chứng tỏ cỡ chìa 56 bit của DES đã lỗi thời và cần được thay thế.

• AES: viết tắt của Advance Encryption Standard. Tháng 12 năm 1997, viện tiêu chuẩn và công nghệ Mỹ (NIST – National Institute of Standard and Technology) kêu gọi phát triển một thuật toán mới thay thế cho 3DES (một biến thể an toàn hơn của DES với chìa khóa dài 112 bit). Thuật toán được chọn phải là thuật toán khối có kích thước khối là 128 bit, hỗ trợ chìa khóa có kích thước 128 bit, 192 bit và 256 bit.

15 thuật toán được gửi đến từ nhiều nơi trên thế giới, 5 thuật toán lọt vào vòng hai: Rijndael, Twofish, Serpent, RC6 và MARS. Tháng 11 năm 2001, Rijndael đuợc chọn làm AES (một phần nhờ có tốc độ nhanh hơn so với các đối thủ), chính thức thay thế DES trong vai trò chuẩn mã hóa dữ liệu.

• RSA: là một thuật toán mã hóa bất đối xứng được sử dụng rất rộng rãi trong giao dịch điện tử. Cái tên RSA có nguồn gốc từ ba chữ cái đầu của tên ba người đồng thiết kế ra nó: Ronald Rivest, Adi Shamir và Leonard Adleman.

Ngoài ra còn nhiều thuật toán khác nhưng do khuôn khổ bài viết có hạn nên không thể đi sâu, mà chỉ liệt kê một số thuật toán thông dụng:

Các thuật toán đối xứng:

• Thuật toán dòng: RC4, A5/1, A5/2, Chameleon…

• Thuật toán khối: 3DES, RC5, RC6, 3-Way, CAST, Camelia, Blowfish, MARS, Serpent, Twofish, GOST…

Các thuật toán bất đối xứng: Elliptic Curve, ElGamal, Diffie Hellman…

HÀM HASH

Hàm hash (hash function) là hàm một chiều mà nếu đưa một lượng dữ liệu bất kì qua hàm này sẽ cho ra một chuỗi có độ dài cố định ở đầu ra.
Ví dụ, từ “Illuminatus” đi qua hàm SHA-1 cho kết quả E783A3AE2ACDD7DBA5E1FA0269CBC58D.
Ta chỉ cần đổi “Illuminatus” thành “Illuminati” (chuyển “us” thành “i”) kết quả sẽ trở nên hoàn toàn khác (nhưng vẫn có độ dài cố định là 160 bit) A766F44DDEA5CACC3323CE3E7D73AE82.

Hai tính chất quan trọng của hàm này là:
• Tính một chiều: không thể suy ra dữ liệu ban đầu từ kết quả, điều này tương tự như việc bạn không thể chỉ dựa vào một dấu vân tay lạ mà suy ra ai là chủ của nó được.
• Tính duy nhất: xác suất để có một vụ va chạm (hash collision), tức là hai thông điệp khác nhau có cùng một kết quả hash, là cực kì nhỏ.

Một số ứng dụng của hàm hash:
• Chống và phát hiện xâm nhập: chương trình chống xâm nhập so sánh giá trị hash của một file với giá trị trước đó để kiểm tra xem file đó có bị ai đó thay đổi hay không.
• Bảo vệ tính toàn vẹn của thông điệp được gửi qua mạng bằng cách kiểm tra giá trị hash của thông điệp trước và sau khi gửi nhằm phát hiện những thay đổi cho dù là nhỏ nhất.
• Tạo chìa khóa từ mật khẩu.
• Tạo chữ kí điện tử.
SHA-1 và MD5 là hai hàm hash thông dụng nhất và được sử dụng trong rất nhiều hệ thống bảo mật. Vào tháng 8 năm 2004, tại hội nghị Crypto 2004, người ta đã tìm thấy va chạm đối với MD5 và SHA-0, một phiên bản yếu hơn của hàm hash SHA-1. Không bao lâu sau đó, vào khoảng giữa tháng 2 năm 2005, một nhóm ba nhà mật mã học người Trung Quốc đã phát hiện ra một phương pháp có thể tìm thấy va chạm đối với SHA-1 chỉ trong vòng 269 bước tính toán (tức là có thể nhanh hơn brute-force vài nghìn lần).
Người dùng bình thường cũng không cần phải hoảng sợ trước những phát hiện này bởi vì ít nhất phải một vài năm nữa người ta mới có khả năng mang những kết quả đó vào trong thực tế. Tuy vậy, các chuyên gia vẫn khuyên nên bắt đầu chuyển sang các hàm hash an toàn hơn như SHA-256, SHA-384 hay SHA-512.

Ở các bài viết sau, tôi sẽ đi vào chi tiết từng thuật toán mã hoá, cụ thể là RSA và AES kết hợp sử dụng hàm hash SHA-256

Base64 encode

I. Giới thiệu:

Từ khi được giới thiệu, Base64 hiện là một giải thuật mã hóa được ứng dụng rộng rãi. Bên cạnh ứng dụng chính là encode dữ liệu truyền trong các ứng dụng mail (Multipurpose Internet Mail Extensions – MIME) base64 còn dùng trong một số lĩnh vực khác nhau.

Ý nghĩa của giải thuật này là chuyển đổi các dữ liệu binary (như file đính kèm) sang dạng plain text để có thể truyền với giao thức mail.

Cách hiện thực base64 đơn giản là dùng bảng mã 6 bit (chỉ bao gồm các ký tự a-z,A-Z,0-9) thay cho bảng mã 8 bit thông dụng.

Các bước Base64 thực hiện như sau:
1. Chuyển đổi các dữ liệu truyền sang nhị phân. Vd: với 3 ký tự ASCII 8 bit ta sẽ có dãy gồm 24 bit.
2. Tách thành các nhóm 6 bit để xử lý
3. Ánh xạ nhóm 6 bit trong bảng mã Base64 để tìm ký tự tương ứng

Hãy xét một ví dụ sau:
Dữ liệu cần chuyển đổi Base64: Man
Bước 1:
M = 77 (ASCII) = 0100.1101
a = 97 (ASCII) = 0110.0001
n = 110 (ASCII) = 0110.1110
Man = 0100.1101.0110.0001.0110.1110
Bước 2: Tách nhóm 6 bit
Man = 010011.010110.000101.101110
Bước 3: Ánh xạ trong bảng mã 64 sau:

Dữ liệu Base64: TWFu

Việc chuyển đổi từ Base64 ra dữ liệu gốc đơn giản có thể làm ngược lại.

Ngoài việc dùng chuyển đổi dữ liệu dùng truyền mail, Base64 còn dùng trong HTTP Basic Authenticate với Web Server. Username và password được truyền đến server bằng Base64 trong HTTP Header. Xem hình sau:


II. Dùng Base64 mã hóa Webshell để Bypass Antivirus:

1. Có 1 Webshell vd: r57.php. Shell này khi upload lên server cài đặt Antivirus sẽ dễ dàng detect được.
2. Dùng Base64 encode. Có thể dùng một số trang web encode online. Vd:http://www.motobit.com/util/base64-decoder-encoder.asp
3. Tạo file Newshell.php dán nội dung encode vào hàm base64_decode
<?php
eval (base64_decode(‘abc’));
?>
Với abc là nội dung shell đã encode.

Thuật toán số hóa thông điệp MD5

1. Mục đích

Bài viết này mô tả thuật toán số hóa thông điệp MD5. Thuật toán nhận vào 1 thông điệp độ dài tùy ý và tạo ra một số 128 bit, là một dạng “vân tay“ hay “mã số thông điệp“ ( message digest ) của đầu vào. Một số người cho rằng sẽ không khả thi về mặt tính toán để tạo ra 2 thông điệp có cùng mã số thông điệp, hoặc tạo ra một thông điệp với mã số cho trước.Thuật toán MD5 được dự tính áp dụng cho những ứng dụng chữ ký điện tử, ở đó một file lớn phải được “nén“ một cách an toàn trước khi mã hóa với một khóa cá nhân ( private key ) dưới một hệ mã hóa công khai như RSA

Thuật toán MD5 được thiết kế để chạy tương đối nhanh trên các máy 32 bit, có thể được thực hiện một cách khá gọn.

Thuật toán MD5 là sự mở rộng của thuật toán MD4. MD5 chậm hơn một chút so với MD4 nhưng an toàn hơn. MD5 được thiết kế vì người ta cảm thấy có thể MD4 đã được chấp nhận trong sử dụng quá nhanh so với sự đánh giá nó. MD4 được thiết kế để chạy rất nhanh, nó đã “nằm trên ranh giới“ theo cách nói về nguy cơ của sự thành công trong việc phá mã. MD5 đã lùi lại một chút, từ bỏ một chút tốc độ cho sự bảo mật. Nó kết hợp một số ý kiến góp ý của các chuyên gia, thuật toán MD5 hiện đang được đánh giá và có thể được chấp nhận như một chuẩn.

2. Thuật ngữ và ký hiệu

Trong bài viết này một “word“ là một lượng 32 bit và một “byte“ là một lượng 8 bit. Một dãy các bit có thể được xem như một dãy các byte, trong đó mỗi nhóm 8 bit liên tiếp được xem như một byte với bit cao của mỗi byte đặt trước. Tương tự, mỗi dãy các byte có thể xem như một dãy các word 32 bit, trong đõ mỗi nhóm 4 byte liên tiếp được xem như một word với byte thấp đặt trước.

Ký hiệu x_i nghĩa là phần tử x thứ i (“x sub i“). Nếu số thứ tự đó là một biểu thức ta viết nó trong ngoặc nhọn, ví dụ như x_{i+1} ; ^ ký hiệu cho số mũ.
Ký hiệu “+“ cho phép cộng các word, nghĩa là cộng theo môđun 2^32.
X <<< s ký hiệu giá trị 32 bit nhận được bằng cách dịch chuyển các bit của X (theo kiểu quay vòng ) sang trái s vị trí.
not(X) ký hiệu phép đối lập (NOT) các bit
X v Y ký hiệu phép OR các bit
X xor Y ký hiệu phép XOR các bit
XY ký hiệu phép AND các bit

3. Mô tả thuật toán MD5

Giả sử chúng ta có thông điệp b bit ở đầu vào, và ta muốn tìm mã số của thông điệp. Ở đây b là số không âm bất kỳ; b có thể bằng 0 và không cần chia hết cho 8, độ lớn có thể bất kỳ. Tưởng tượng rằng các bit của thông điệp được viết như sau :
m_0 m_1 m_2 … m_{b-1}

Mã số thông điệp được tính qua 5 bước sau

Bước 1 : Các bit gắn thêm

Thông điệp được mở rộng, thêm bit vào phía sau sao cho độ dài của nó ( tính theo bit ) đồng dư với 448 theo môđun 512. Nghĩa là thông điệp được mở rộng sao cho nó còn thiếu 64 bit nữa thì sẽ có một độ dài chia hết cho 512. Việc này luông được thực hiện ngay cả khi bản thân độ dài thông điệp đã đồng dư với 448 theo môđun 512.

Việc thêm bit này thực hiện như sau : một bit “1“ được thêm vào sau thông điệp, sau đó các bit “0“ được thêm vào để có một độ dài đồng dư với 448 môđun 512. Trong tất cả các trường hợp, có ít nhất 1 và nhiều nhất 512 bit được thêm vào.

Bước 2 : Gắn thêm độ dài

Dạng biểu diễn 64 bit độ dài b của chuỗi ban đầu được thêm vào phía sau kết quả của bước 1. Trong trường hợp b lớn hơn 2^64 thì chỉ có 64 bit thấp của b được sử dụng. ( Các bit này được thêm vào phía sau dưới dạng 2 word 32 bit, gắn word thấp trước theo quy ước ở trên )

Bước 3 : Khởi tạo bộ đệm MD

Một bộ đệm 4 word (A,B,C,D) được dùng để tính mã số thông điệp. Ở đây mỗi A,B,C,D là một thanh ghi 32 bit. Những thanh ghi này được khởi tạo theo những giá trị hex sau ( các byte thấp trước ) :
word A : 01 23 45 67
word B : 89 ab cd ef
word C : fe dc ba 98
word D : 76 54 32 10

Bước 4 : Xử lý thông điệp theo từng khối 16 word

Trước hết ta định nghĩa các hàm phụ, các hàm này nhận đầu vào là 3 word 32 bit và tạo ra một word 32 bit.

F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z)= XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))

Với mỗi bit, F hoạt động như một điều kiện : nếu X thì Y nếu không thì Z. Hàm F có thể định nghĩa bằng phép + thay vì v bởi vì XY và not(X)Z không bao giờ có “1“ ở cùng 1 vị trí bit.Các hàm G,H và I tương tự như F, ở chỗ chúng tác động theo từng bit tương ứng để tạo ra kết quả từ các bit của X,Y và Z

Bước này sử dụng một bảng 64 giá trị T[1 .. 64] được tạo ra từ hàm sin. Gọi T[i] là phần tử thứ i của bảng, thì T[i]là phần nguyên của 4294967296*|sin(i)| , i được tính theo radian.

Làm như sau :

/* Xử lý mỗi khối 16 word */
For i = 0 to N/16-1 do

/* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */

/* Lưu A vào AA, B vào BB, C vào CC, D và DD . */
AA = A
BB = B
CC = C
DD = D

/* Vòng 1. */
/* Ký hiệu [abcd k s i] nghĩa là thực hiện như sau :
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Thực hiện : */
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]

/* Vòng 2. */
/*Ký hiệu [abcd k s i] nghĩa là thực hiện như sau
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Thực hiện : */
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]

/* Vòng 3. */
/* Ký hiệu [abcd k s t] nghĩ là làm như sau
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Thực hiện :*/
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]

/* Vòng 4. */
/* Ký hiệu [abcd k s t] nghĩa là làm như sau
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Thực hiên: */
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]

/* Then perform the following additions. (That is increment each
of the four registers by the value it had before this block was started.) */

/* Sau đó làm các phép cộng sau. ( Nghĩa là cộng vào mỗi thanh ghi giá trị của nó trước khi vào vòng lặp ) */

A = A + AA
B = B + BB
C = C + CC
D = D + DD

end /* of loop on i */

Bước 5 : In ra

Mã số thông điệp được tạo ra là A,B,C,D. Nghĩa là chúng ta bắt đầu từ byte thấp của A, kết thúc với byte cao của D.

Đến đây đã mô tả xong thuật toán MD5. Mã nguồn tham khảo viết bằng C có thể tìm thấy ở phụ lục.

4. Tổng kết

Thuật toán số hóa thông điệp MD5 khá đơn giản để thực hiện, cung cấp một dạng “vân tay“ hay mã số của thông điệp với độ dài tùy ý. Người ta cho rằng độ khó để tìm được 2 thông điệp có cùng mã số là khoảng 2^64 bước tính, và độ khó để tim được một thông điệp với mã số cho trước là 2^128 bước tính. Thuật toán MD5 đã được dò tìm điểm yếu một cách cẩn thận. Tuy nhiên đây là một thuật toán tương đối mới ( ! ) và việc phân tích cẩn thận về sự an toàn là cần thiết.

5. Sự khác nhau giữa MD4 và MD5

Sau đây là sự khác nhau giữa MD4 và MD5 :

1. Vòng 4 đã được thêm vào

2. Mỗi bước đều được thêm vào một hằng số duy nhất

3. Hàm G ở vòng 2 được đổi từ (XY v XZ v YZ) thành (XZ v Y not(Z)) để làm giảm sự đối xứng trong G.

4. Mỗi bước đều sử dụng kết quả từ bước trước . Điều này nhằm tạo ra “hiệu ứng dây chuyền“ nhanh hơn

5. Thứ tự các word đầu vào ở vòng 2 và vòng 3 được thay đổi, để làm cho hai mẫu này ít giống nhau hơn

6. Số bit dịch chuyển ở mỗi vòng được tối ưu hóa, để tạo ra “hiệu ứng dây chuyền“ nhanh hơn. Lượng dịch chuyển ở mỗi vòng là khác nhau.

Tài liệu tham khảo

[1] Rivest, R., “The MD4 Message Digest Algorithm“, RFC 1320, MIT and
RSA Data Security, Inc., April 1992.

[2] Rivest, R., “The MD4 message digest algorithm“, in A.J. Menezes
and S.A. Vanstone, editors, Advances in Cryptology – CRYPTO `90
Proceedings, pages 303-311, Springer-Verlag, 1991.

[3] CCITT Recommendation X.509 (1988), “The Directory –
Authentication Framework.“

Xem xét về tính bảo mật

Độ bảo mật bàn đến trong bài viết này được coi là đủ để tạo ra những mô hình chữ ký điện tử kết hợp giữa MD5 và một hệ mã hóa công khai

%d bloggers like this: