MD5

Trong lĩnh vực mật mã học, MD5 (viết tắt của Message-Digest algorithm 5, là một hàm băm mật mã được sử dụng phổ biến với giá trị băm dài 128-bit. Là một chuẩn Internet (RFC 1321), MD5 đã được áp dụng rộng rãi trong nhiều ứng dụng bảo mật và kiểm tra tính toàn vẹn của các tập tin. Một bảng băm MD5 thường được biểu diễn bằng một chuỗi thập lục phân 32 ký tự.

MD5 được thiết kế bởi Ronald Rivest vào năm 1991 để thay thế cho hàm băm trước đó là MD4. Tuy nhiên, vào năm 1996, các chuyên gia phát hiện ra một số lỗ hổng trong MD5. Mặc dù vẫn chưa rõ đó có phải là các lỗi nghiêm trọng, nhưng các chuyên gia mật mã đã bắt đầu đề xuất sử dụng các thuật toán khác như SHA-1 (vào thời điểm đó cũng bị coi là không an toàn). Đến năm 2004, các lỗ hổng nhiều hơn được phát hiện, dẫn đến sự nghi ngờ về việc sử dụng MD5 trong các ứng dụng bảo mật.

Lịch sử và thuật toán

Tiêu hoá Tin nhắn là một chuỗi các thuật toán băm thông tin được Giáo sư Ron Rivest của MIT thiết kế (Rivest, 1994). Sau khi phân tích cho thấy MD4, thuật toán trước đó của MD5, có vẻ không an toàn, ông đã thiết kế MD5 vào năm 1991 nhằm cải thiện tính an toàn. (Những điểm yếu của MD4 đã được Hans Dobbertin phát hiện sau đó).

Vào năm 1993, Den Boer và Bosselaers phát hiện ra một dạng 'xung đột giả' của hàm nén MD5, mặc dù nó có hạn chế. Họ đã thử với hai vector khởi tạo I và J khác nhau 4 bit và đạt được kết quả:

MD5compress(I,X) = MD5compress(J,X).

Vào năm 1996, Dobbertin thông báo về việc phát hiện xung đột trong hàm nén MD5 (Dobbertin, 1996). Mặc dù không phải là một cuộc tấn công vào toàn bộ hàm băm MD5, nhưng đó đã đủ để các chuyên gia mật mã đề xuất sử dụng các giải thuật khác như WHIRLPOOL, SHA-1 hoặc RIPEMD-160.

Kích thước của bảng băm là 128 bit, quá nhỏ để chống lại các cuộc tấn công bruteforce. MD5CRK là một dự án phân tán bắt đầu vào tháng 3 năm 2004, với mục tiêu chứng minh rằng MD5 không an toàn trên thực tế bằng cách tìm ra các xung đột sử dụng tấn công bruteforce.

MD5CRK nhanh chóng kết thúc vào ngày 17 tháng 8 năm 2004, khi một cuộc tấn công đã công bố xung đột toàn bộ MD5 bởi Xiaoyun Wang, Dengguo Feng, Xuejia Lai và Hongbo Yu. Cuộc tấn công phân tích của họ được báo cáo chỉ mất một giờ trên nhóm máy IBM p690.

Vào ngày 1 tháng 3 năm 2005, Arjen Lenstra, Xiaoyun Wang và Benne de Weger đã thực hiện việc tạo ra hai chứng nhận X.509 với các khóa công cộng khác nhau nhưng cùng sử dụng bảng băm MD5, chứng tỏ một xung đột thực tế. Quá trình tạo chứng nhận bao gồm các khóa riêng tư cho cả hai khóa công cộng. Vài ngày sau, Vlastimil Klima đã phát triển một giải thuật nâng cao, có thể tạo ra xung đột MD5 trong vài giờ với một máy tính xách tay. Vào ngày 18 tháng 3 năm 2006, Klima đã công bố một giải thuật có thể tìm thấy xung đột trong một phút bằng một máy tính xách tay, sử dụng phương pháp anh gọi là bắt đường hầm.

Ứng dụng

Các đồng hóa MD5 được sử dụng rộng rãi trong phần mềm trên toàn thế giới để đảm bảo tính nguyên vẹn của dữ liệu được truyền. Ví dụ, các máy chủ tập tin thường cung cấp một mã kiểm tra MD5 được tính toán trước cho các tập tin, để người dùng có thể so sánh với mã kiểm tra của tập tin đã tải xuống. Các hệ điều hành dựa trên Unix luôn bao gồm tính năng MD5 sum trong các gói phân phối của họ, trong khi người dùng Windows sử dụng ứng dụng từ bên thứ ba.

Tuy nhiên, hiện nay có thể tạo ra xung đột MD5 một cách dễ dàng, mà một người có thể tạo ra một tập tin để tạo ra một tập tin khác với cùng một mã kiểm tra, do đó, kỹ thuật này không thể chống lại một số loại mạo danh nguy hiểm. Ngoài ra, trong một số trường hợp, mã kiểm tra không thể được tin tưởng (ví dụ, nếu nó được lấy từ một lệnh như tập tin đã tải xuống), trong trường hợp đó, MD5 chỉ có thể phát hiện lỗi hoặc việc tải xuống chưa hoàn thành, điều này xảy ra dễ dàng khi tải xuống các tập tin lớn.

MD5 được sử dụng phổ biến để lưu trữ mật khẩu. Để giảm thiểu các vấn đề bảo mật đã được đề cập, có thể thêm muối (salt) vào mật khẩu trước khi băm chúng. Một số thực tế có thể áp dụng nhiều hơn một lần vào hàm băm để tăng cường bảo mật.

Thuật toán

MD5 chuyển một đoạn thông tin chiều dài thay đổi thành một kết quả chiều dài không đổi 128 bit. Mẩu tin đầu vào được chia thành từng đoạn 512 bit; mẩu tin sau đó được độn sao cho chiều dài của nó chia chẵn cho 512. Công việc độn vào như sau: đầu tiên một bit đơn, 1, được gắn vào cuối mẩu tin. Tiếp theo là một dãy các số zero sao cho chiều dài của mẩu tin lên tới 64 bit ít hơn so với bội số của 512. Những bit còn lại được lấp đầy bằng một số nguyên 64-bit đại diện cho chiều dài của mẩu tin gốc.

Thuật toán MD5 chính hoạt động trên trạng thái 128-bit, được chia thành 4 từ 32-bit, với ký hiệu A, B, C và D. Chúng được khởi tạo với những hằng số cố định. Thuật toán chính sau đó sẽ xử lý các khối tin 512-bit, mỗi khối xác định một trạng thái. Quá trình xử lý khối tin bao gồm bốn giai đoạn giống nhau, gọi là vòng; mỗi vòng gồm có 16 tác vụ giống nhau dựa trên hàm phi tuyến F, cộng mô đun, và dịch trái. Hình 1 mô tả một tác vụ trong một vòng. Có 4 khả năng cho hàm F; mỗi cái được dùng khác nhau cho mỗi vòng:

$F(X,Y,Z)=(X\wedge <!--\; \wedge \; -->Y)\vee <!--\; \vee \; -->(\mathrm{\neg <!--\; \neg \; -->}X\wedge <!--\; \wedge \; -->Z)$

$G(X,Y,Z)=(X\wedge <!--\; \wedge \; -->Z$

) ∨ ( Y ∧ ¬ Z ) {\displaystyle G(X,Y,Z)=(X\wedge {Z})\vee (Y\wedge \neg {Z})}

$H(X,Y,Z)=X\oplus <!--\; \oplus \; -->Y\oplus <!--\; \oplus \; -->Z$

$I(X,Y,Z)=Y\oplus <!--\; \oplus \; -->(X\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}Z)$

$\oplus <!--\; \oplus \; -->,\wedge <!--\; \wedge \; -->,\vee <!--\; \vee \; -->,\mathrm{\neg <!--\; \neg \; -->}$ lần lượt chỉ phép XOR, AND, OR và NOT.

Đây là quá trình thực hiện xử lý của 4 hàm F, G, H, I ở trên:

Vòng 1: Ký hiệu [abcd j s i] là bước thực hiện của phép toán a = b + ((a + F(b, c, d) + M[j] + K[i]) <<< s) Quá trình thực hiện 16 bước sau:

[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]

Giải thích: ví dụ biểu thức thứ 2 là [DABC 1 12 2], tương đương với:

D = A + ((D + F(A,B,C) + M[1] + K[2]) <<< 12) Nhận xét: Vòng 1 dùng hàm F, Với giá trị j từ 0 -> 15 và i từ 1 -> 16

Vòng 2: Tương tự, ký hiệu [abcd j s i] là của biểu thức: a = b + ((a + G(b, c, d) + M[j] + K[i]) <<< s) Quá trình thực hiện 16 bước:

[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]

Nhận xét: Vòng 2 dùng hàm G, với i từ 17 -> 32 và j = 1 + 5j mod 16

Vòng 3:

Tương tự, ký hiệu [abcd j s i] là của biểu thức: a = b + ((a + H(b, c, d) + M[j] + K[i]) <<< s)

Quá trình thực hiện 16 bước:

[ABCD 5 4 33] [DABC 8 11 34] [CDAB 1 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 5 16 47] [BCDA 2 23 48]

Vòng 3 sử dụng hàm H, với i từ 33 đến 48 và j = 5 + 3j mod 16.

Vòng 4:

Tương tự, ký hiệu [abcd j s i] là của biểu thức:

a = b + ((a + I(b,c,d) + M[j] + K[i]) <<< s)

Quá trình thực hiện 16 bước:

[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]

Nhận xét: Vòng 4 sử dụng hàm I, với i từ 49 đến 64 và j = 7j mod 16

/* Sau đó thực hiện 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 /* của vòng lặp trên i */

Bước 5: Tính kết quả tiêu hoá thông điệp. Sau khi hoàn thành bước 4, thông điệp thu gọn nhận được từ 4 thanh ghi A, B, C, D, bắt đầu từ byte thấp của thanh ghi A và kết thúc với byte cao của thanh ghi D bằng phép nối như sau: Message Digest = A || B || C || D. (|| là phép nối)

Mã giả

Mã giả cho thuật toán MD5 được minh họa như sau.

//Chú ý: Tất cả các biến đều là biến không dấu 32 bit và bao phủ mô đun 2^32 khi tính toán
var int[64] r, k

//r xác định số dịch chuyển mỗi vòng
r[ 0..15]:= {7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22} 
r[16..31]:= {5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20}
r[32..47]:= {4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23}
r[48..63]:= {6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21}

//Sử dụng phần nguyên nhị phân của sin của số nguyên làm hằng số:
for i from 0 to 63
 k[i]:= floor(abs(sin(i + 1)) × (2 pow 32))

//Khởi tạo biến:
var int h0:= 0x67452301
var int h1:= 0xEFCDAB89
var int h2:= 0x98BADCFE
var int h3:= 0x10325476

//Tiền xử lý:
append '1' bit to message
append '0' bits until message length in bits ≡ 448 (mod 512)
append bit (bit, not byte) length of unpadded message as 64-bit little-endian integer to message

//Xử lý mẩu tin trong đoạn 512-bit tiếp theo:
for each 512-bit chunk of message
 break chunk into sixteen 32-bit little-endian words w[i], 0 ≤ i ≤ 15

 //Khởi tạo giá trị băm cho đoạn này:
 var int a:= h0
 var int b:= h1
 var int c:= h2
 var int d:= h3

 //Vòng lặp chính:
 for i from 0 to 63
 if 0 ≤ i ≤ 15 then
 f:= (b and c) or ((not b) and d)
 g:= i
 else if 16 ≤ i ≤ 31
 f:= (d and b) or ((not d) and c)
 g:= (5×i + 1) mod 16
 else if 32 ≤ i ≤ 47
 f:= b xor c xor d
 g:= (3×i + 5) mod 16
 else if 48 ≤ i ≤ 63
 f:= c xor (b or (not d))
 g:= (7×i) mod 16

 temp:= d
 d:= c
 c:= b
 b:= b + leftrotate((a + f + k[i] + w[g]), r[i])
 a:= temp

 //Thêm bảng băm của đoạn vào kết quả:
 h0:= h0 + a
 h1:= h1 + b 
 h2:= h2 + c
 h3:= h3 + d

var int digest:= h0 append h1 append h2 append h3 //(expressed as little-endian)

Ghi chú: Thay vì hàm hóa RFC 1321 gốc như trên, phần sau có thể được dùng để tăng độ hiệu quả (hữu ích nếu ngôn ngữ assembly được dùng - còn không, chương trình dịch sẽ tự động tối ưu hóa đoạn mã ở trên):

(0 ≤ i ≤ 15): f:= d xor (b and (c xor d))
(16 ≤ i ≤ 31): f:= c xor (d and (b xor c))

Các bảng băm MD5

Bảng băm MD5 128 bit (16 byte) (còn được gọi là message digests) được biểu diễn bằng chuỗi 32 số thập lục phân. Sau đây cho thấy đầu vào ASCII 43 byte và bảng băm MD5 tương ứng:

MD5('The quick brown fox jumps over the lazy dog') 
= 9e107d9d372bb6826bd81d3542a419d6

Thậm chí một sự thay đổi nhỏ trong mẩu tin cũng dẫn đến thay đổi hoàn toàn bảng băm, do hiệu ứng thác. Ví dụ, thay d thành e:

MD5('The quick brown fox jumps over the lazy eog') 
= ffd93f16876049265fbaef4da268dd0e

Bảng băm của một chuỗi rỗng là:

MD5('') 
= d41d8cd98f00b204e9800998ecf8427e