Báo Cáo Môn Học: Bảo Mật Mạng
Đề Tài:
Tìm hiểu thuật toán
MD5 & SHA
GVHD: Phan Thị Thanh Nga
Nhóm Sinh Viên Thực Hiện:
 Tăng Huy Lương
 Lê Thành Luân
1
Nội Dung Báo Cáo
1. Tìm hiểu về thuật toán md5

MD5 và lịch sử ra đời

Đặc điểm và ứng dụng

MD5

So sánh Md4 với Md5

Khả năng bị tấn công
2. Tìm hiểu về thuật toán sha

SHA và lịch sử ra đời

Đặc điểm và ứng dụng

SHA-1

Ưu nhược điểm


Một vài ví dụ

So sánh sha1-sha2
2
Khái Niệm MD5

Trong mật mã học, MD5 (Message-Digest algorithm 5) là một bộ tạo
Hash mật mã được sử dụng phổ biến với giá trị Hash dài 128-bit .

Là một chuẩn Internet (RFC 1321)

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 thiết kế bởi Ronald Rivest vào năm 1991 để thay thế 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 gia mã hóa bắt đầu đề nghị sử dụng những giải thuật
khác, như SHA-1 (khi đó cũng bị xem là không an toàn). Trong năm 2004,
nhiều lỗ hổng hơn bị khám phá khiến cho việc sử dụng giải thuật này cho
mục đích bảo mật đang bị đặt nghi vấn
3
Đặc điểm và ứng dụng

Đặc Điểm

Việc tính MD đơn giản, có khả năng xác định được file có kích thước
nhiều Gb.

Không có khả năng tính ngược, khi tìm ra MD.


Do bản chất ngẫu nhiên của hàm băm và số lượng cực lớn các giá trị
hash có thể, nên hầu như không có khả năng hai bản tin phân biệt có
cùng giá trị hash.

Giá trị MD phụ thuộc vào bản tin tương ứng.

Một chuổi chỉ có duy nhất một hash.

Giá trị MD phụ thuộc vào tất cả các bit của bản tin tương ứng

Ứng dụng

Bảo toàn thông tin

Bảo mật
4
Ứng Dụng
5
Bảo Mật
Bảo Toàn thông tin
Giải Mã

Về cơ bản MD5 không thể giải mã lại được. Nhưng tại sao trên mạng có
rất nhiều trang web giải mã MD5 ?!? Thật ra thì những trang web này họ
cũng không thể giải mã được MD5 mà là họ tra những password đã được
lưu trữ từ trước.

Ví dụ: Giả sử có Password là: 12345. Password này sau khi mã hóa sẽ
thành chuỗi MD5: 827ccb0eea8a706c4c34a16891f84e => Sau đó họ lưu

vào CSDL. Khi bạn muốn giải mã chuổi
827ccb0eea8a706c4c34a16891f84e thì họ sẽ tra vào CSDL và cho ra
password là : 12345

Một số trang web có thể làm việc này là:
+
+
+
6
Mô tả thuật toán MD5
7
Thuật toán chính của MD5 hoạt động trên một bộ 128 bit. Chia nhỏ nó ra thành 4
từ 32 bít, ký hiệu A, B, C, D. Các giá trị này là các hằng số cố định. Sau đó thuật
toán chính sẽ luân phiên hoạt động trên các khối 512 bit. Quá trình xử lý một khối
thông điệp gồm 4 bước tương tự nhau, gọi là vòng. Mỗi vòng lại gồm 16 quá trình
tương tự nhau dựa trên hàm một chiều F, phép cộng module và phép xoay trái…
Thực hiện qua các 4 bước sau:
Mô tả thuật toán MD5
8

Bước 1: Thêm các bit vào chuổi

Thực hiện nối dài thông điệp. (theo hình vẽ thông điệp là B) để chi nhỏ
thành các module 512.

Ví dụ :Ta có chuỗi 384bit

Trước tiên nó sẽ chèn bit 1 vào cuối
thông điệp.


Thêm vào k bit ‘0’ sao cho (b bit + bit 1
+ k bit 0)mod 512=448

64 bit tiếp theo sẽ được thêm vào biểu thị
chiều dài của chuổi bit ban đầu. (B bit +
bit ‘1’ + k bit ‘0’ + 64 bit chiều dài) mod
512 = 0
Mô tả thuật toán MD5

Bước 2: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 3: 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
9
Mô tả thuật toán MD5

Với lần lượt là XOR, AND, OR, NOT

Quá trình thực hiện qua các vòng:


Vòng 1: [abcd k s t] là các bước thực hiện của phép toán.
a= b + ((a + F1(b,c,d) + X[k] + T[i]) <<< s)
Với t từ 1 …16 và k từ 0…15

Vòng 2: [abcd k s t] là các bước thực hiện của phép toán.
a= b + ((a + F2(b,c,d) + X[k] + T[i]) <<< s)
Với t từ 17 …32 và k =(1+5t)mod 16

Vòng 3: [abcd k s t] là các bước thực hiện của phép toán.
a= b + ((a + F3(b,c,d) + X[k] + T[i]) <<< s)
Với t từ 33 …48 và k =(5+3t)mod 16

Vòng 4: [abcd k s t] là các bước thực hiện của phép toán.
a= b + ((a + F4(b,c,d) + X[k] + T[i]) <<< s)
Với t từ 49 …64 và k =(7t)mod 16
10
Mô tả thuật toán MD5

Bước 4: 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.

Hàm băm MD5 trả về một chuổi số thập lục phân gồm 32 số liên tiếp.

Dưới đây là các ví dụ mô tả các kết quả thu được sau khi băm.

MD5("The quick brown fox jumps over the lazy dog") =
9e107d9d372bb6826bd81d3542a419d6

Thậm chỉ chỉ cần một thay đổi nhỏ cũng làm thay đổi hoàn toàn kết quả
trả về:

MD5("The quick brown fox jumps over the lazy cog") =
1055d3e698d289f2af8663725127bd4b
Ngay cả một chuổi rổng cũng cho ra một kết quả phức tạp:
MD5("") = d41d8cd98f00b204e9800998ecf8427e
11
Mô tả thuật toán MD5
12
Bao gồm 64 tác vụ thế này, nhóm
trong 4 vòng 16 tác vụ.
F là 1 hàm phi tuyết, một hàm được
dùng trong mỗi vòng.
M i chỉ ra một khối tin nhập vào 32
bit
Ki chỉ một hằng số 32 bit, khác nhau
cho mỗi tác vụ.
<<<<s chỉ sự xoay bit về trái s đơn vị,
s thay đổi tùy theo từng tác vụ.
chỉ cộng thêm với modulo 232 .
Hàm băm MD5 sẽ trả về một chuỗi số
thập lục phân gồm 32 số liên tiếp.
Hình mô tả quá trình trong 1 vòng.
Một vòng của thuật toán
13

Vòng 4 đã được thêm vào

Mỗi bước đều được thêm vào một hằng số duy nhất


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.

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

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

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.
So sánh MD5 với MD4
Khả năng bị tấn công

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ó để tìm được một thông điệp với mã số
cho trước là 2^128 bướctính.

Với bất kỳ giá trị x, không thể tính được y ≠ x sao cho
H(y) = H(x).

Không thể tính được một cặp (x, y) sao cho H(x) = H(y).

Do đó MD5 được sử dụng rộng rãi trong các ứng dụng, web, bảo mật, và
chứng thực…

Tuy nhiên ở một mức độ nào đó thì md 5 vẫn có thể crack được
14
Khả năng bị tấn công


Vì MD5 chỉ dò qua dữ liệu một lần, nếu hai tiền tố với cùng bảng băm
được xây nên, thì cùng một hậu tố có thể cùng được thêm vào để khiến cho
đụng độ dễ xảy ra. Tức là hai dữ liệu vào (input) X và Y hoàn toàn khác
nhau nhưng có thể ra (output) được một md5 hash giống nhau . Tuy nhiên
xác suất để xảy ra điều này là khá nhỏ.

Vì những kỹ thuật tìm đụng độ hiện nay cho phép các trạng thái băm trước
đó được xác định một cách ngẫu nhiên, có thể tìm thấy xung đột đối với
bất kỳ tiền tố mong muốn nào; có nghĩa là, đối bất kỳ một chuỗi các ký tự
X cho trước, hai tập tin đụng độ có thể được xác định mà đều bắt đầu với
X.

Giải Pháp

Bất cứ thuật toán mã hóa nào rồi cũng bị giải mã. Với MD5, ngay từ
năm1996, người ta đã tìm thấy lỗ hổng của nó. Mặc dù lúc đó còn chưa rõ
ràng lắm nhưngcác chuyên gia mã hóa đã nghĩ đến việc phải đưa ra một
thuật giải khác, như là SHA-1,SHA-2,
15
SHA

SHA và lịch sử ra đời

SHA(Secure Hash Algorithm hay thuật giải băm an toàn) là các thuật
giải dùng để chuyển một đoạn dữ liệu nhất định thành một đoạn dữ liệu
có chiều dài không đổi với xác suất khác biệt cao.

- SHA được phát triển bởi cục quốc gia an ninh Hoa Kỳ gọi tắt là(NSA)
và được xuất bản thành chuẩn của chính phủ Hoa Kỳ bởi viện công

nghệ và chuẩn quốc gia Hoa Kỳ(NIST) vào năm 1993 và được gọi là
SHA-0.Các thuật toán của SHA bao gồm: SHA-1,SHA-224,SHA-
384,SHA-512,SHA-256

Vào năm 1995 có 1 thay đổi nhỏ của SHA-0 dẫn đến sự ra đời của
SHA-1,và SHA-1 được công bố trong FIPS PUB 180-1

SHA-256,SHA-384,SHA-512 đầu tiên được xuất bản vào năm 2001
như dự thảo FIPS PUB 180-2 và phát hành như là tiêu chuẩn chính thức
vào năm 2002

SHA-224 được xuất bản vào năm 2004 như là thông báo thay đổi cho
FIPS PUB 180-2
16
SHA

Các Loại SHA

SHA-1 : tạo chuỗi 40 kí tự hệ 16. Trả lại kết quả dài
160bit.

SHA-256 : tạo chuỗi 64 kí tự thệ 16Trả lại kết quả dài
256bit.

SHA-384: tạo chuỗi 96 kí tự hệ 16. Trả lại kết quả dài
384 bit.

SHA-512 : tạo chuỗi 128 ký tự hệ 16. Trả lại kết quả
dài 512 bit.
17

SHA

Đặc điểm và ứng dụng

Đặc điểm:
•
Cho một giá trị băm nhất định được tạo nên bởi một
trong những thuật giải SHA, việc tìm lại được đoạn dữ
liệu gốc là không khả thi.
•
Việc tìm được hai đoạn dữ liệu nhất định có cùng kết
quả băm tạo ra bởi một trong những thuật giải SHA là
không khả thi
•
Bất cứ thay đổi nào trên đoạn dữ liệu gốc, dù nhỏ, cũng
sẽ tạo nên một giá trị băm hoàn toàn khác với xác suất
rất cao.
18
SHA

SHA được sử dụng rộng rãi trong nhiều ứng
dụng và giao thức an ninh khau nhau : TLS và
SSL, GPG, SHH, IPSec.
19
SHA-1

Thuật toán SHA-1

Khởi gán các biến:
•

h0 := 0x67452301
•
h1 := 0xEFCDAB89
•
h2 := 0x98BADCFE
•
h3 := 0x10325476
•
h4 := 0xC3D2E1F0

Tiền xử lý:
•
Thêm bit 1 vào cuối thông điệp
•
Thêm vào k bit 0 sao cho độ dài thông điệp nhận được đồng
du 448 (mod 512)
•
Thêm 64 bit biểu diễn độ dài dài của thông điệp gốc (giá trị
lưu dạng big-endian)
20
SHA-1
21

Chia thông điệp (đã padding) thành các
khối 512 bit

Với mỗi khối 512-bit:

Chia thành 16 word (32 bit, big-endian)
w[0 15]


Mở rộng 16 word (32 bit) thành 80
word (32 bit)

w[i]=(w[i-3]⊕ w[i-8] ⊕ w[i-14] ⊕ w[i-
16]) <<< 1 với 16 ≤ i < 80

A= h0, B= h1, C= h2, D= h3, E= h4

80 chu kỳ xử lý

h0+=A, h1+=B, h2+=C, h3+=D, h4+=E

Kết quả:= h0 | h1 | h2 | h3 | h4
SHA-1
22

Chu kỳ xử lý:

t là số thứ tự của chu kỳ

A, B, C, D, E là 5 word (32 bit) của trạng thái

F là hàm phi tuyến (thay đổi tùy theo chu kỳ)

<<< n là phép quay trái n vị trí

⊞ phép cộng modulo 232.

Kt là hằng số .

[ ]
( )
( ) ( )( )
( ) ( ) ( )







≤≤⊕⊕
≤≤∧∨∧∨∧
≤≤⊕⊕
≤≤∧¬∨∧
=
7960 ,
5940 ,
3920 ,
190 ,
,,
tZYX
tZYZXYX
tZYX
tZXYX
ZYXtF








≤≤
≤≤
≤≤
≤≤
=
7960,
5940,
3920,
190,
t
t
t
t
K
t
0xca62c1d6
0x8f1bbcdc
0x6ed9eba1
0x5a827999
SHA-1

Ưu điểm SHA-1

Bảng băm là một cấu trúc dung hòa giữa thời gian
truy xuất và dung lượng :
•
Nếu không có sự giới hạn về bộ nhớ : có thể

xây dựng bảng băm với mỗi ứng dụng với một
địa chỉ với mong muốn thời gian truy xuất tức
thời.
•
Nếu dung lượng bộ nhớ có giợi hạn : tổ chức
một số khóa có cùng địa chỉ truy xuất giảm.
•
Cáp phép toán tren bảng băm hạn chế số lần so
sánh, giảm được thời gian truy xuất.
23
SHA-1

Nhược điểm:

Hiện nay vấn đề bảo mật của SHA-1 không cong
được tin tưởng sử dụng vì :
•
Đầu năm 2005, Rijmen và Oswald đã công bố 1 cuộc tấn
công vao phiên rút gọn của SHA-1 bằng cách tìm đụng
độ bằng cách tính ít hơn 2^80 phép tính.
•
2-2005, một cuộc tán công bởi 3 nhà vật mật mã học
thuộc đại học ShanDong(Trung Quốc) đã tìm ra được sự
đụng độ trong phiên bản SHA-1 chỉ với 2^69 phép tính
nhanh hơn khoản 2000 lần so với cách tấn công trước.
•
8-2005, tại hội nghị mật mã, họ đã công bố và thuyết
trình việc tấn công này và chỉ ra 1 vụ va chạm tại vòng
58 của SHA-1 chỉ với 2^33 phép tính….
24

SHA-1

Một vài ví dụ :

Text1:
Text: Xin Chao CTK33
SHA-1 :3c2225cd7740da98d80545085f216b373e7c1e01

Text2:
Text: Xin Chao CTK33.
SHA-1: 9830a511b3b4f044566f0491661b43751ccc52a9
-
Text3 :
Text :
SHA-1:da39a3ee5e6b4b0d3255bfef95601890afd80709
25