MD5 – Wikipedia tiếng Việt

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

MD5 được phong cách thiết kế bởi Ronald Rivest vào năm 1991 để thay thế sửa chữa cho hàm băm trước đó, MD4. Vào năm 1996, người ta phát hiện ra một lỗ hổng trong MD5 ; trong khi vẫn chưa biết nó có phải là lỗi nghiêm trọng hay không, những chuyên viên mã hóa mở màn đề xuất sử dụng những giải thuật khác, như SHA-1 ( khi đó cũng bị xem là không bảo đảm an toàn ). Trong năm 2004, nhiều lỗ hổng hơn bị mày mò khiến cho việc sử dụng giải thuật này cho mục tiêu bảo mật thông tin đang bị đặt nghi vấn .

Lịch sử và thuật toán[sửa|sửa mã nguồn]

Tiêu hóa Tin nhắn là một loạt những thuật toán đồng điệu thông tin được phong cách thiết kế bởi Giáo sư Ron Rivest của trường MIT ( Rivest, 1994 ). Khi việc làm nghiên cứu và phân tích chỉ ra rằng giải thuật trước MD5 – MD4 – có vẻ như không bảo đảm an toàn, ông đã phong cách thiết kế ra MD5 vào năm 1991 để sửa chữa thay thế bảo đảm an toàn hơn. ( Điểm yếu của MD4 sau đó đã được Hans Dobbertin tìm thấy ) .

Vào năm 1993, Den Boer và Bosselaers đã tìm ra, tuy còn giới hạn, một dạng “xung đột ảo” của hàm nén MD5; đó là, với hai véc-tơ khởi tạo I và J khác nhau 4 bit, dẫn đến:

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

Trong năm 1996, Dobbertin đã thông tin có xung đột của hàm nén MD5 ( Dobbertin, 1996 ). Dù nó không phải là một cuộc tiến công vào hàng loạt hàm băm MD5, nhưng nó đủ gần để những chuyên viên mã hóa đề xuất sử dụng kỹ thuật khác để sửa chữa thay thế, như WHIRLPOOL, SHA-1 hay RIPEMD-160 .Kích thước của bảng băm-128 bit-đủ nhỏ để bị tiến công bruteforce. MD5CRK là một dự án Bất Động Sản phân bổ mở màn vào tháng 3 năm 2004 với tiềm năng chứng tỏ rằng MD5 không bảo đảm an toàn trên thực tiễn bằng cách tìm ra những xung đột sử dụng tiến công bruteforce .MD5CRK kết thúc nhanh gọn sau ngày 17 tháng 8 năm 2004, khi xung đột so với hàng loạt MD5 được công bố bởi Xiaoyun Wang, Dengguo Feng, Xuejia Lai, và Hongbo Yu [ 1 ] [ 2 ]. Cuộc tiến công nghiên cứu và phân tích của họ được báo cáo giải trình là chỉ diễn ra có 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 đã trình diễn [ 3 ] việc thiết kế xây dựng hai giấy phép X. 509 với những khóa công cộng khác nhau và cùng bảng băm MD5, một sự xung đột thực thế đáng được trình diễn. Sự thiết kế xây dựng gồm có những khóa riêng tư cho cả hai khóa công cộng. Vài ngày sau, Vlastimil Klima đã diễn đạt [ 4 ] một giải thuật nâng cao, có thẻ thiết kế xây dựng những 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 đã phát hành một giải thuật [ 5 ] hoàn toàn có thể tìm thấy đụng độ trong vòng một phút bằng một máy tính xách tay, sử dụng một phương pháp mà anh gọi là bắt đường hầm .
Các đồng hóa MD5 được dùng thoáng rộng trong những ứng dụng trên toàn quốc tế để bảo vệ việc truyền tập tin được nguyên vẹn. Ví dụ, sever tập tin thường cung ứng một tổng kiểm ( checksum ) MD5 được thống kê giám sát trước cho tập tin, để người dùng hoàn toàn có thể so sánh với tổng kiểm của tập tin đã tải về. Những hệ quản lý dựa trên nền tảng Unix luôn kèm theo tính năng MD5 sum trong những gói phân phối của họ, trong khi người dùng Windows sử dụng ứng dụng của hãng thứ ba .Tuy nhiên, lúc bấy giờ thuận tiện tạo ra xung đột MD5, một người hoàn toàn có thể tạo ra một tập tin để tạo ra tập tin thứ hai với cùng một tổng kiểm, do đó kỹ thuật này không hề chống lại một vài dạng trá hình nguy hại. Ngoài ra, trong một số ít trường hợp tổng kiểm không hề tin cậy được ( ví dụ, nếu nó được lấy từ một lệnh như tập tin đã tải về ), trong trường hợp đó MD5 chỉ hoàn toàn có thể có tính năng kiểm tra lỗi : nó sẽ nhận ra một lỗi hoặc tải về chưa xong, rất dễ xảy ra khi tải tập tin lớn .MD5 được dùng thoáng đãng để tàng trữ mật khẩu. Để giảm bớt sự dễ thương tổn đề cập ở trên, ta hoàn toàn có thể thêm muối ( salt ) vào mật khẩu trước khi băm chúng. Một vài hiện thực hoàn toàn có thể vận dụng vào hàm băm hơn một lần – xem làm mạnh thêm khóa .
Hình 1. Một thao tác MD5—MD5 bao gồm 64 tác vụ thế này, nhóm trong 4 vòng 16 tác vụ. F là một hàm phi tuyết; một hàm được dùng trong mỗi vòng. Mi chỉ ra một khối tin nhập vào 32-bit, và Ki chỉ một hằng số 32-bit, khác nhau cho mỗi tác vụ. s chỉ sự xoay bit về bên trái s đơn vị; s thay đổi tùy theo từng tác vụ. 32.
MD5 chuyển một đoạn thông tin chiều dài đổi khác thành một tác dụng chiều dài không đổi 128 bit. Mẩu tin nguồn 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 : tiên phong một bit đơn, 1, được gắn vào cuối mẩu tin. Tiếp theo là một dãy những 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 thay mặt 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 ∧ Y ) ∨ ( ¬ X ∧ Z ) { \ displaystyle F ( X, Y, Z ) = ( X \ wedge { Y } ) \ vee ( \ neg { X } \ wedge { Z } ) }

G ( X, Y, Z ) = ( X ∧ Z ) ∨ ( Y ∧ ¬ Z ) ∂ 2 ∂ x 1 ∂ x 2 y ∂ 2 ∂ x 1 ∂ x 2 y 1199999999999999999999 { \ displaystyle G ( X, Y, Z ) = ( X \ wedge { Z } ) \ vee ( Y \ wedge \ neg { Z } ) { \ partial ^ { 2 } \ over \ partial x_ { 1 } \ partial x_ { 2 } } y { \ partial ^ { 2 } \ over \ partial x_ { 1 } \ partial x_ { 2 } } y1199999999999999999999 }

H ( X, Y, Z ) = X ⊕ Y ⊕ Z { \ displaystyle H ( X, Y, Z ) = X \ oplus Y \ oplus Z }

I ( X, Y, Z ) = Y ⊕ ( X ∨ ¬ Z ) { \ displaystyle I ( X, Y, Z ) = Y \ oplus ( X \ vee \ neg { Z } ) }

⊕
,
∧
,
∨
,
¬

{\displaystyle \oplus ,\wedge ,\vee ,\neg }

lần lượt chỉ phép XOR, AND, OR và NOT.

Đây là quy trình triển khai giải quyết và 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 thi của phép toán a = b + ( ( a + F ( b, c, d ) + M [ j ] + K [ i ] ) < < < s ) Quá trình thực thi 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 tự với 😀 = 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 -> 16Vò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 thi 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 + 5 j mod 16Vò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 thi 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]

Nhận xét : Vòng 3 dùng hàm H, với i từ 33 -> 48 và j = 5 + 3 j mod 16Vò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 triển khai 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 ][ ABCDb 4 6 61 ] [ DABC 11 10 62 ] [ CDAB 2 15 63 ] [ BCDA 9 21 64 ]Nhận xét : Vòng 4 dùng hàm I, với i từ 49 -> 64 và j = 7 j mod 16/ * Sau đó làm những 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 + AAB = B + BBC = C + CCD = D + DDEnd / * of loop on i * /Bước 5 : Tính tác dụng tiêu hóa thông điệp. Sau khi triển khai xong bước 4, thông điệp thu gọn nhận được từ 4 thanh ghi A, B, C, D, khởi đầ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. ( | | phép toán nối )
Mã giả cho thuật toán MD5 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)

//định nghĩa hàm dịch trái
leftrotate (x, c) 
 return (x << c) or (x >> (32-c));

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[sửa|sửa mã nguồn]

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ự biến hóa nhỏ trong mẩu tin cũng dẫn đến biến hóa trọn vẹ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

Liên kết ngoài[sửa|

sửa mã nguồn]

Source: https://thomaygiat.com
Category : Kỹ Thuật Số