Hàm băm MD5 và SHA-1

MD5 được phát minh bởi Ron Rivest, người cũng đã tham gia xây dựng RSA. MD5, viết tắt từ chữ „Message Digest‟, được phát triển lên từ MD4 và trước đó là MD2, do MD2 và MD4 không còn được xem là an toàn. Kích thước giá trị băm của MD5 là 128 bít, mà chúng ta coi như là an toàn (theo nghĩa không tìm được 2 thông điệp có cùng giá trị băm).

Tuy nhiên vào năm 1994 và 1998, một phương pháp tấn công MD5 đã được tìm thấy và một số thông điệp có cùng giá trị băm MD5 được chỉ ra (vi phạm tính chống trùng mạnh).

Tuy vậy ngày nay MD5 vẫn còn được sử dụng phổ biến.

Vì MD5 không còn được xem là an toàn, nên người ta đã xây dựng thuật toán băm khác. Một trong những thuật toán đó là SHA-1 (Secure Hash Algorithm) mà đã được chính phủ Mỹ chọn làm chuẩn quốc gia. SHA-1 có kích thước giá trị băm là 160 bít. Ngày nay còn có ba phiên bản khác của SHA là SHA-256, SHA-384, SHA-512 mà có kích thước giá trị băm tương ứng là 256, 384 và 512 bít.

Tương tự như mã hóa đối xứng, các hàm băm mạnh đều có hiệu ứng lan truyền (avalanche effect). Chỉ cần thay đổi 1 bít trong thông điệp đầu vào thì ½ các bít của giá trị băm sẽ thay đổi theo. Điều này làm cho người phá hàm băm không thể thử sai theo kiểu chosen-plainttext, nghĩa là không tồn tại cách tấn công nào khác được và buộc phải thử vét cạn 2^n/2 thông điệp khác nhau, mà chúng ta đã chứng minh là bất khả thi về mặt thời gian.

a) MD5

Sau đây chúng ta sẽ tìm hiểu hàm băm MD5 với kích thước giá trị băm là 128 bít, được dùng để tính giá trị băm của thông điệp có kích thước tối đa là 2⁶⁴ bít.

Sơ đồ tổng thể:

85 Trước tiên thông điệp được thêm dãy bit padding 100….00. Sau đó thêm vào chiều dài (trước khi padding) của thông điệp được biểu diễn bằng 64 bít. Như vậy chiều dài của dãy bít padding được chọn sao cho cuối cùng thông điệp có thể chia thành N block 512 bít M1, M2, … , MN.

Quá trình tính giá trị băm của thông điệp là quá trình lũy tiến. Trước tiên block M1

kết hợp với giá trị khởi tạo H0 thông qua hàm F để tính giá trị hash H1. Sau đó block M2

được kết hợp với H1 để cho ra giá trị hash là H2 . Block M3 kết hợp với H2 cho ra giá trị H3. Cứ như vậy cho đến block MN thì ta có giá trị băm của toàn bộ thông điệp là HN.

H0 là một dãy 128 bít được chia thành 4 từ 32 bít, ký hiệu 4 từ 32 bít trên là abcd. a, b, c, d là các hằng số như sau (viết dưới dạng thập lục phân):

a = 01234567 b = 89abcdef c = fedbca98 d = 76543210

Tiếp theo ta sẽ tìm hiểu cấu trúc của hàm F.

Message 100…00 Length

N x 512 bít

64 bít

M₁ M₂ M_N

512 bít 512 bít 512 bít

…. ….

F ⊞

IV (H₀) 128

128 H₁

F ⊞

128 H₂ H_N-1

F ¹²⁸ ⊞^HN

…. Hash value

N block

512 512 512

86

Tại mỗi bước lũy tiến, các giá trị abcd của giá trị hash Hi-1 được biến đổi qua 64 vòng từ 0 đến 63. Tại vòng thứ j sẽ có 2 tham số là Kj và Wj đều có kích thước 32 bít. Các hằng số Kj được tính từ công thức:

Kj là phần nguyên của số 2 n với i biểu diễn theo radian.

Giá trị block Mi 512 bít được biến đổi qua một hàm message schedule cho ra 64 giá trị W0, W1,…, W63 mỗi giá trị 32 bít. Block Mi 512 bít được chia thành 16 block 32 bít ứng với các giá trị W0, W1, …, W15 (16×32=512). Tiếp theo, 16 giá trị này được lặp lại 3 lần tạo thành dãy 64 giá trị.

Sau vòng cuối cùng, các giá trị abcde được cộng với các giá trị abcd của Hi-1 để cho ra các giá trị abcd của Hi. Phép cộng ở đây là phép cộng modulo 2³².

Tiếp theo ta tìm hiểu cấu trúc của một vòng. Việc biến đổi các giá trị abcd trong vòng thứ i được thể hiện trong hình bên dưới.

a b c d Hi-1

Mi

K0 32 512 128

Round 63

a b c d

K63 32

….

⊞ ⊞



⊞ ⊞

Hi 128

W0

32

W63

32 Message Schedule

Round 0

87 Ở đây bc, cd, da. Giá trị b được tính qua hàm:

, s) Trong đó:

 Hàm f(x, y, z):

nếu là vòng 0 đến 15 nếu là vòng 16 đến 31 nếu là vòng 32 đến 48 nếu là vòng 49 đến 63

 Hàm ROTL(t, s): t được dịch vòng trái s bít, với s là các hằng số cho vòng thứ i như sau:

i s

0, 4, 8, 12 7

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

 Phép + (hay ⊞) là phép cộng modulo 2³² b) SHA-1

a b c d

a b c d

⊞

⊞

⊞

f

Wj

Kj

ROTL

⊞

88

Hàm băm SHA-1 với giá trị băm có kích thước là 160 bít, được dùng để tính giá trị băm của thông điệp có kích thước tối đa là 2⁶⁴ bít.

Sơ đồ tổng thể của SHA1 cũng giống như của MD5, chỉ có điểm khác là kích thước của giá trị hash tại mỗi bước là 160 bít.

H0 là một dãy 160 bít được chia thành 5 từ 32 bít, ký hiệu 5 từ 32 bít trên là abcde. a, b, c, d, e là các hằng số như sau:

a = 67452301 b = efcdab89 c = 98badcfe d = 10325476 e = c3d2e1f0

Cấu trúc của hàm F của SHA cũng tương tự như MD5, tuy nhiên được thực hiện trên 80 vòng.

Message 100…00 Length

N x 512 bít

64 bít

M₁ M₂ M_N

512 bít 512 bít 512 bít

…. ….

F ⊞

IV (H₀) 160

160 H₁

F ⊞

160 H₂ H_N-1

F ¹⁶⁰ ⊞^HN

….

Hash value N block

512 512 512

89 Giá trị K0, K1,…, K79 là các hằng số sau:

Ki = 5A827999 với 0 ≤ i ≤ 19 Ki = 6ED9EBA1 với 20 ≤ i ≤ 39 Ki = 8F1BBCDC với 40 ≤ i ≤ 59 Ki = CA62C1D6 với 60 ≤ i ≤ 79

Giá trị block Mi 512 bít được biến đổi qua một hàm message schedule cho ra 80 giá trị W0, W1,…, W80 mỗi giá trị 32 bít, theo quy tắc:

Trước tiên block Mi 512 bít được chia thành 16 block 32 bít ứng với các giá trị W0, W1, …, W15 (16×32=512).

Các giá trị Wt (16  t  79) được tính theo công thức:

1 với phép cộng modulo 2³². Việc biến đổi các giá trị abcde trong vòng thứ i được thể hiện trong hình bên dưới.

Message Schedule

Round 0

a b c d e Hi-1

Mi

K0 32 32

W0 512 160

Round 79

a b c d e

K79 32 32

W79

….

⊞ ⊞ ⊞ ⊞ ⊞

Hi 160

90

Ở đây ab, cd, de. Giá trị a và c được tính qua các hàm:

5 3

Trong đó, hàm f(x, y ,z):

nếu là vòng 0 đến 19 nếu là vòng 20 đến 39 nếu là vòng 40 đến 59 nếu là vòng 60 đến 79 Ý nghĩa của hàm Maj và hàm Ch:

 Hàm Maj: giả sử xi, yi, zi là bít thứ i của x, y, z, thì bít thứ i của hàm Maj là giá trị nào chiếm đa số, 0 hay 1 (giống như hàm maj được định nghĩa trong phần thuật toán A5/1).

 Hàm Ch: bít thứ i của hàm Ch là phép chọn: if xi then yi else zi. c) SHA-512

Phương pháp SHA-512 có cấu trúc cũng gần giống như SHA-1, tuy nhiên các khối tính toán có số bít lớn hơn. Bên dưới là sơ đồ tổng thể của SHA-512

Message 100…00 Length

N x 1024 bít

128 bít

M₁ M₂ M_N

1024 bít 1024 bít 1024 bít

…. ….

F ⊞

IV (H₀) 512

512 H₁

F ⁵¹² ⊞^{H2 …. HN-1} F ⁵¹² ⊞^HN

Hash value N block

1024 1024 1024

a b c d e

a b c d e

⊞

⊞

⊞

⊞

f

Wi

Ki ROTL

ROTL

91 Thông điệp được padding có thể chia thành các khối 1024 bít. Giá trị hash tại môi bước có kích thước 512 bít. H0 được chia thành 8 từ 64 bít abcdefgh. a, b, c, d, e, f, g, h được lấy từ phần thập phân của căn bậc 2 của 8 số nguyên tố đầu tiên (ví dụ a có giá trị hexa là 6A09E667F3BCC908).

Cấu trúc của hàm F cũng giống như hàm F của SHA-1.

Hai tham số là Ki và Wi đều có kích thước 64 bít. Giá trị K0, K1,…, K80 được lấy từ phần thập phân của căn bậc 3 của 80 số nguyên tố đầu tiên. Còn W0, W1,…, W79 được tính từ Mi như sau:

Trước tiên block Mi 1024 bít được chia thành 16 block 64 bít ứng với các giá trị W0, W1, …, W15 (16×64=1024).

Các giá trị Wt (16  t  79) được tính theo công thức:

Với:

1  8  7 19  61  6 Trong đó:

 : là hàm dịch phải i bít của một số x 64 bít

 : là hàm dịch vòng phải i bít của một số x 64 bít

 Phép cộng là phép modulo 2⁶⁴ Cấu trúc của một vòng:

Message Schedule

Round 0

a b c d e f g h Hi-1

Mi

K0 64 64

W0 1024 512

Round 79

a b c d e f g h

K79 64 64

W79

….

⊞ ⊞ ⊞ ⊞ ⊞ ⊞ ⊞ ⊞

Hi 512

92

Ở đây gh, fg, ef, cd, bc, ab. Giá trị a và e được tính qua các hàm:

∑

∑ a = T0 + T1

e = d + T1

Trong đó, hàm ∑ và ∑ :

∑ 28  34  39

∑ 14  18  41

Trong tài liệu AN TOÀN VÀ BẢO MẬT THÔNG TIN (Trang 84-92)