Số hóa bởi Trung tâm Học liệu
NGUYỄN HỮU HỒNG NGHIÊN CỨU
ĐỘ AN TỒN CỦA HÀM BĂM MD5
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGUYỄN HỮU HỒNG NGHIÊN CỨU
ĐỘ AN TỒN CỦA HÀM BĂM MD5
Chun
ngành:
Khoa học máy tính
Mã số: 60 48
01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƢỜI HƢỚNG DẪN KHOA HỌC
TS. Hồ Văn Canh
CHƢƠNG 3 ĐÁNH GIÁ ĐỘ AN TỒN MD5 DỰA TRÊN THỬ NGHIỆM
TẤN CƠNG 25
3.1. Tấn cơng hàm băm 25
3.2. Các phƣơng pháp tấn cơng hàm băm phổ biến 25
3.2.1. Tấn cơng dựa trên lý thuyết ngày sinh 25
3.2.2. Tấn cơng mở rộng chiều dài trên MD5 (Length-Extension Attack)27
3.2.3. Tấn cơng thuật tốn 29
3.2.4. Tấn cơng theo ngun lý vét cạn 36
ii
Số hóa bởi Trung tâm Học liệu
3.3. Đánh giá độ an tồn MD5 dựa trên việ
GPU 36
3.3.1. Những ƣu điểm của GPU so với CPU 37
3.3.2. Sử dụ 5 39
3.3.3. Kết luận về độ an tồn MD5 48
KẾT LUẬN 52
TÀI LIỆU THAM KHẢO 53
iii
Số hóa bởi Trung tâm Học liệu
LỜI CẢM ƠN
Đầu tiên, tơi xin gửi lời cảm ơn chân thành và sắc nhất tới Tiến sỹ Hồ
Văn Canh, thầy đã tận tình chỉ bảo và giúp đỡ tơi trong suốt q trình làm
luận văn. Bên cạnh những kiến thức tơi còn học hỏi đƣợc ở thầy tinh thần làm
việc khoa học và nghiêm túc.
Nguyễn Hữu Hồng v
Số hóa bởi Trung tâm Học liệu
THUẬT NGỮ VIẾT TẮT
Số thứ tự
Thuật Ngữ
Tên Đầy Đủ
1
MAC
Message Authentication Code
2
HMAC
Keyed-Hash Message Authentication Code
3
vi
Số hóa bởi Trung tâm Học liệu
Ý NGHĨA CÁC KÝ HIỆU
Số thứ tự
Ký hiệu
Ý nghĩa
1
Phép tốn XOR
2
<<<
Phép dịch bít vòng
3
||
Phép ghép chuỗi
4
Phép OR
5
Phép AND
6
⌐
Phép phủ định
7
+
Hình 2.1. Thuật tốn mơ tả MD5/SHA-1 19
Hình 3.1. Cấu trúc lặp Merkle-Damgård (sao chép từ Wikipedia) 28
Hình 3. 2. Tấn cơng mở rộng chiều dài 28
Hình 3. 3. Biểu đồ so sánh sự phát triển của GPU và CPU 38
Hình 3.4. So sánh số nhân của GPU và CPU 38
Hình 3.5. Mơ tả chiến lược kiểm tra mật khẩu song song 40
Hình 3. 6. Chia mật khẩu vào các nhóm 41
Hình 3.7. Tạo giá trị băm cho mật khẩu 49
Hình 3.8. Add giá trị băm của mật khẩu vào phần mềm 50
Hình 3.9. Q trình tạo và kiểm tra mật khẩu 50
Hình 3.10. Tìm kiếm mật khẩu thành cơng 51
viii
Số hóa bởi Trung tâm Học liệu
DANH MỤC BẢNG BIỂU
Bảng 1. 1.Bảng so sánh các loại hàm băm 13
Bảng 3.1. Kiểu tấn cơng các hàm băm 27
Bảng 3. 2. Modify multiple message 35
Bảng 3.16. So sánh tốc độ của Tạo và Kiểm tra các khóa trên CPU / GPU . 47
Bảng 3.17. Thời gian cho Phục hồi mật khẩu trên GPU 47
Số hóa bởi Trung tâm Học liệu
Chƣơng 1
LÝ THUYẾT VỀ HÀM BĂM
1.1. Định nghĩa hàm băm
Hàm băm H nhận đầu vào là chuỗi dữ liệu M có chiều dài bất kỳ và tạo
ra chuỗi đầu ra (hay còn gọi là "hash value") có chiều dài cố định theo cơng
thức sau.
h = H (M).
Ví dụ minh họa về hàm băm.
Hình 1.1. Minh họa về hàm băm
- h đƣợc gọi là giá trị đầu ra của hàm băm, có chiều dài cố định (h còn
gọi là message digest hoặc hash value).
- M là bức thơng điệp có chiều dài bất kỳ hữu hạn (chiều dài của M
khơng vƣợt q
64
2
bít, nếu chiều dài của M vƣợt q
64
2
bít thì chỉ có
64
2
bít đầu đƣợc sử lý, còn tất cả các bít đƣợc bỏ qua trong q trình tính tốn của
hàm băm).
3
Số hóa bởi Trung tâm Học liệu
khó có thể điều khiển đƣợc nội dung thơng điệp này sao cho nó có ý nghĩa với
con ngƣời, do vậy có thể kết luận các hàm băm hiện tại vẫn đủ an tồn[9].
1.4. Ứng dụng
Hàm băm đƣợc sử dụng rộng rãi trong thế giới phần mềm để đảm bảo
rằng tập tin tải về khơng bị hỏng. Ngƣời sử dụng có thể so sánh giữa thơng số
kiểm tra phần mềm bằng Hàm băm đƣợc cơng bố với thơng số kiểm tra phần
mềm tải về bằng Hàm băm. Hệ điều hành Unix sử dụng MD5 để kiểm tra các
gói mà nó phân phối, trong khi hệ điều hành Windows sử dụng phần mềm của
hãng thứ ba.
Hàm băm cũng đƣợc dùng để mã hóa mật khẩu. Mục đích của việc mã
hóa này là biến đổi một chuổi mật khẩu thành một đoạn mã khác, sao cho từ
đoạn mã đó khó có thể lần trở lại mật khẩu. Có nghĩa là việc giải mã là khơng
thể hoặc phải mất một khỗng thời gian vơ tận (đủ để làm nản lòng các
hacker).
Tạo mã chứng thực thơng điệp ứng dụng trong chứng chỉ số, sự ra đời
của các hệ mật mã khóa cơng khai cùng với các hàm băm là một cuộc cách
mạng của kỹ thuật mật mã. Chính vì vậy nhiều ngƣời nói rằng hàm băm là
một phƣơng thức mật mã khơng dùng khóa.
Một ứng dụng quan trọng khơng thể thiếu đối với hàm băm là ứng dụng
trong chữ ký số[2][12][13].
1.5. Một số hàm băm phổ biến
Các hàm băm chúng ta xem xét dƣới đây có hai thành phần chính.
Thành phần đầu tiên là hàm nén nhận đầu vào là một chuỗi có chiểu dài bất kì
và giá trị chaining variable (giá trị khởi tạo) và cho đầu ra là chuỗi có chiều
dài cố định.
Thành phần thứ 2 là hàm chuẩn chuỗi đầu vào, hàm này có nhiệm vụ biến
chuỗi đầu vào có chiều dài bất kì thành chuỗi các bít, mà chuỗi này là có
Thuật tốn MD4 tuần tự xử lý dãy m khối trong m lƣợt tính tốn. Dữ
liệu đầu vào tại lƣợt tính tốn thứ k (1 <= k <= m) là khối thứ k trong dãy và
mã băm nhận đƣợc sau (k-1) lƣợt tính tốn trƣớc đó ( mã băm đầu vào ứng
với k = 1 đã đƣợc khởi tạo từ trƣớc )
Tại lƣợt tính tốn thứ k này, khối dữ liệu đầu vào 512 bit liên tiếp đi qua 3
vòng tính tốn, trong mỗi vòng gồm có 16 bƣớc, mỗi bƣớc thực hiện tính
tốn với dữ liệu là một từ trong dãy và các kết quả nhận đƣợc sau bƣớc
trƣớc. Kết quả sau khi qua 3 vòng tính tốn trên sẽ đƣợc kết hợp với mã băm
trƣớc đó để sinh ra mã băm mới (cho lƣợt tính tốn thứ k). Sau khi đã xử lý
hết m khối, mã băm nhận đƣợc sau cùng là kết quả ta cần tìm [9].
1.5.2. Hàm băm SHA-1
Thuật tốn cho hàm băm này nhận đầu vào là bức thơng điệp có chiều
dài hữu hạn bất kỳ cho đầu ra là chuỗi có chiều dài cố định, hàm băm SHA-1
có chiều dài đầu ra là 160 bit.
- Việc đệm đƣợc thực hiện tƣơng tự việc đệm trong thuật tốn cho hàm
băm MD5.
7
Số hóa bởi Trung tâm Học liệu
- Chia bức thơng điệp thành các khối 512 bit.
- Thực hiện việc khởi tạo cho các biến chaining variable nhƣ sau:
H
)0(
0
=0x67452301
H
)0(
1
=0xefcdab89
d=H
)1(
3
i
e=H
)1(
4
i
- Thực hiện việc biến đổi nhƣ sau.
For (t=0; t<=79; t++)
{
T =
5
ROLT
(a) +
t
f
(b, c, d) + e + K
t
+W
t
e=d
d=c
c=
30
ROLT
i
= c + H
)1(
2
i
H
)(
3
i
= d + H
)1(
3
i
H
)(
4
i
= e + H
)1(
4
i
1.5.3. Hàm băm SHA-256
Thuật tốn này nhận chiều vào là bức thơng điệp có chiều dài bất kì
hữu hạn cho đầu ra là chuỗi có chiều dài cố định là 256 bít.
- Việc đệm đƣợc thực hiện tƣơng tự việc đệm trong thuật tốn cho hàm
băm MD5.
- Chia bức thơng điệp thành các khối 512 bit.
)0(
7
=0x5be0cd19
Thực hiện sử lý các khối.
- Xây dựng hàm biến đổi khối đầu vào theo cơng thức sau
9
Số hóa bởi Trung tâm Học liệu - Khởi tạo các biến làm việc nhƣ sau .
a=H
)1(
0
i
b=H
)1(
1
i
c=H
)1(
2
i
d=H
)1(
3
i
+ Ch (e, f, g) +K
}256{
t
+W
t
T
2
=
}256{
0
)(a
+Maj (a, b, c)
h = g
g = f
f = e
e=d + T
1
d = c
c = b
b = a
a= T
1
+ T
2
10
Số hóa bởi Trung tâm Học liệu
H
)(
3
i
= d + H
)1(
3
i
H
)(
4
i
= e + H
)1(
4
i
H
)(
5
i
= f + H
)1(
5
i
H
)(
6
)(x
= ROTR
6
(x) ROTR
11
(x) ROTR
25
(x)
}256{
0
= ROTR
7
(x) ROTR
18
(x) SHR
3
(x)
}256{
1
= ROTR
17
(x) ROTR
19
(x) SHR
10
(x)
1.5.4. Hàm băm SHA-384, SHA-512
Các thuật tốn này nhận đầu vào là bức thơng điệp có chiều dài bất kỳ
hữu hạn cho đầu ra (message digest) là chuỗi có chiều dài cố định (SHA-384,
SHA-512 là 1024 bit).
H
)0(
5
=0x8eb44a8768581511
H
)0(
6
=0xdb0c2e0d64f98fa7
H
)0(
7
=0x47b5481dbefa4fa4
Với hàm băm SHA-512 các giá trị chaining variable đƣợc khởi tạo nhƣ sau:
H
)0(
0
=0x6a09e667f3bcc908
H
)0(
1
=0xbb67ae8584caa73b
H
)0(
2
=0x3c6ef372fe94f82b
H
)0(
3
=0xa54ff53a5f1d36f1
H
1
i
c = H
)1(
2
i
d = H
)1(
3
i
e = H
)1(
4
i
f = H
)1(
5
i
g = H
)1(
6
i
h = H
)1(
d = c
c = b
b = a
a= T
1
+ T
2
}
13
Số hóa bởi Trung tâm Học liệu
Tính tốn kết quả cuối cùng nhƣ sau.
H
)(
0
i
= a + H
)1(
0
i
H
)(
1
i
= b + H
)1(
1
)(
5
i
= f + H
)1(
5
i
H
)(
6
i
= g + H
)1(
6
i
H
)(
7
i
= e + H
)1(
7
i
Trong đó
Ch(x, y, z) = (x ^ y) (⌐x z)
Maj(x, y, z) = (x ^ y) (y ^ z) (z ^ x).
}512{
= ROTR
19
(x) ROTR
61
(x) SHR
6
(x)
Tổng kết về các hàm băm trên [6]
Tên hàm
băm
Chiều dài khối
dữ liệu
Độ dài
từ
Chiều dài đầu
ra
Số
vòng
Năm cơng
bố
MD4
512
32
128
64
1990
SHA-1
512
32
160
Copyright: Tài liệu đại học ©