ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
NGUYỄN HỮU HOÀNG
NGHIÊN CỨU
ĐỘ AN TOÀN CỦA HÀM BĂM MD5
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Thái Nguyên - 2013
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
NGUYỄN HỮU HOÀNG
NGHIÊN CỨU
ĐỘ AN TOÀN CỦA HÀM BĂM MD5
Chuyên 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
Thái Nguyên - 2013
i
MỤC LỤC
MỞ ĐẦU..........................................................................................................1
CHƯƠNG 1 LÝ THUYẾT VỀ HÀM BĂM..................................................2
1.1. Định nghĩa hàm băm.............................................................................2
1.2. Các tính chất của hàm băm..................................................................3
1.3. Xung đột băm.........................................................................................3
1.4. Ứng dụng................................................................................................4
1.5. Một số hàm băm phổ biến.....................................................................4
1.5.1. Hàm băm MD4..................................................................................6
1.5.2. Hàm băm SHA-1...............................................................................6
1.5.3. Hàm băm SHA-256...........................................................................8
1.5.4. Hàm băm SHA-384, SHA-512........................................................10
CHƯƠNG 2 HÀM BĂM MD5.....................................................................15
2.1. Giới thiệu..............................................................................................15
2.2. Khái niệm..............................................................................................15
2.3. Ứng dụng..............................................................................................16
2.4. Thuật giải..............................................................................................16
2.5. Sự khác nhau MD4 và MD5................................................................24
CHƯƠNG 3 ĐÁNH GIÁ ĐỘ AN TOÀ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 toán.........................................................................29
3.2.4. Tấn công theo nguyên lý vét cạn.....................................................36
ii
3.3. Đánh giá độ an toàn MD5 dựa trên việc sử dụng các bô ô xử lý đồ
họa GPU để tính toán khôi phục mâ ôt khẩu................................................36
3.3.1. Những ưu điểm của GPU so với CPU.............................................37
3.3.2. Sử dụng Cluster GPU tính toán khôi phục mâ ât khẩu MD5.............39
3.3.3. Kết luận về độ an toàn MD5............................................................48
KẾT LUẬN....................................................................................................52
TÀI LIỆU THAM KHẢO...............................................................................53
iii
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 quá 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.
Tôi xin chân thành cám ơn tới Khoa CNTT Trường Đại học Công nghệ
thông tin và Truyền thông, các thầy cô đã giúp đỡ và tận tình truyền đạt các
kiến thức cho tôi trong suốt quá trình học tập và nghiên cứu. Tôi xin cảm ơn
ban chủ nhiệm khoa và các cán bộ đã tạo điều kiện tốt nhất cho chúng tôi
trong quá trình học tập và hoàn thành luận văn của mình.
Tôi xin bày tỏ lòng biết ơn tới gia đình, bạn bè, đồng nghiệp và những
người thân đã động viên khích lệ tinh thần và giúp đỡ tôi hoàn thành luận văn này.
iv
LỜI CAM ĐOAN
Tôi xin cam đoan, toàn bộ nội dung liên quan tới đề tài được trình bày
trong luận văn là bản thân tôi tự tìm hiểu và nghiên cứu, dưới sự hướng dẫn
của Thầy giáo TS. Hồ Văn Canh.
Các tài liệu, số liệu tham khảo được trích dẫn đầy đủ nguồn gốc. Tôi
xin chịu trách nhiệm trước pháp luật lời cam đoan của mình.
Học viên thực hiện
Nguyễn Hữu Hoàng
v
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
opad
Outer pad
4
ipad
Inner pad
5
SHA
Secure Hash Algorithm
6
MD
Merkle-Damgård
7
TLS
Transport Layer Security
8
CA
Certification Authority
9
IPSec
Internet Protocol Security
10
GPU
Graphic Proccessing Unit
11
SM
Streaming Multiprocessor
Ý NGHĨA CÁC KÝ HIỆU
Số thứ tự
Ký hiệu
Ý nghĩa
vi
1
Phép toán XOR
2
<<<
Phép dịch bít vòng
3
||
Phép ghép chuỗi
4
Phép OR
5
6
⌐
Phép phủ định
7
+
Phép cộng module 2 32
8
ROTR n (x)
Dịch xoay vòng x sang bên phải n bít
9
SHR n (x)
Dịch bít của số x sang bên phải n bít
Phép AND
DANH MỤC HÌNH VẼ
Hình 1.2. Cấu trúc lặp của hàm băm MD.........................................................5
Hình 2.1. Thuật toá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
vii
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. Quá 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
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
1
MỞ ĐẦU
Ngày nay, các giao dịch thương mại qua mạng internet trở nên rất phổ
biến và do đó cần phải có biện pháp để đảm bảo an toàn cho các giao dịch
này. Một trong các biện pháp đó là việc sử dụng hàm băm (hash function)
trong công tác bảo an. Hàm băm không những đảm bảo được sự toàn vẹn của
các giao dịch mà còn có thể đảm bảo sự bí mật về dữ liệu của các bên giao
dịch[1][2]. Người ta đã khẳng định rằng: “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ã
và được coi như một phương thức mật mã không dùng khóa”[2]. Hàm băm
cũng đóng vai trò hết sức quan trọng trong việc ứng dụng chứng chỉ số mà cụ
thể nhất là trong chữ kí số. Ngoài ra, hàm băm còn là một công cụ hữu hiệu
để bảo vệ các passwords người dùng và bảo vệ dữ liệu có hiệu quả trong các
cơ sở dữ liệu phân tán. Hiện nay, hàm băm được sử dụng nhiều ở Việt Nam
cũng như trên thế giới là MD5 và họ SHA. Do tầm quan trọng của hàm băm
mà hiện nay đã có nhiều công trình nghiên cứu về hàm băm và mức độ an
toàn của chúng[3][4][5][6].
Vậy, một câu hỏi được đặt ra hiện nay là: Mức độ an toàn của các hàm
băm đến đâu trong thực tế khi mà công nghệ tính toán ngày càng phát triển
mạnh mẽ như hiện nay? Trong Luận văn này tôi trình bày mô tâ cách tiếp câ ân
mới đó là viê âc sử dụng các bô â xử lý đồ họa đa lõi hiê ân đại để tính toàn khôi
phục thông điệp MD5[14][16][17].
2
Chương 1
LÝ THUYẾT VỀ HÀM BĂM
A.
Đị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 quá 2 64 bít, nếu chiều dài của M vượt quá 2 64 bít thì chỉ có 2 64
bít đầu được sử lý, còn tất cả các bít được bỏ qua trong quá trình tính toán của
hàm băm).
3
- Hàm băm được sử dụng trong việc mã hóa password, chữ ký số, giao
dịch điện tử, kiểm tra sự toàn vẹn của một file, v.v. Hàm băm được sử dụng
phổ biến nhất là hàm băm một chiều (one-way) MD5 và SHA-*[9][12]
1.1.
Các tính chất của hàm băm
Tính chất 1:
Hàm băm H là không va chạm yếu.
Hàm băm H phải có phi xung đột yếu (weak-collision) cao, điều đó có
nghĩa là cho trước M ta khó có thể tìm được bức thông điệp M’ M sao cho
H(M) = H(M’) .
Tính chất 2: Hàm băm H là không va chạm mạnh.
Hàm băm H có tính phi đụng độ cao (strong collision), điều đó có nghĩa
là ta khó có thể tìm được cặp thông điệp (M, M’) M’ M sao cho
H(M)=H(M’).
Tính chất 3: Hàm băm H là hàm một chiều.
Hàm băm H có tính một chiều (one-way) có nghĩa là cho trước M việc
tính H(M) được thực hiện nhanh chóng nhưng nếu cho trước giá trị H(M) thì
sẽ khó có thể tìm được giá trị M[9].
B.
Xung đột băm
Có nghĩa là hai thông điệp khác nhau khi băm thì chúng tạo ra cùng giá
trị băm. Gọi M, M’ là hai thông điệp sao cho M M’, H là hàm băm, xung
đột băm xảy ra khi H(M)=H(M’).
Về mặt lý thuyết thì hoàn toàn ta có thể tìm được hai thông điệp khác
nhau mà chúng cho ra cùng một giá trị băm, nhưng thực tế việc này làm rất
khó khăn, và ngay cả khi chúng ta tạo được hai thông điệp với nội dung khác
nhau nhưng chúng cùng tạo ra giá trị băm, nhưng nội dung đó không có ý
nghĩa với con người có nghĩa là nếu cho trước một thông điệp ta hoàn toàn có
thể tìm được thông điệp thứ hai khác tạo ra cùng giá trị băm nhưng chúng ta
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 toàn[9].
4
1.2.
Ứ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 khoã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].
C.
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ó
chiều dài là bội số của các khối message block(có chiều dài là 512 hoặc 1024
bit). Ở thời điểm bắt đầu các “chaining variable” có giá trị khởi tạo (giá trị
5
khởi tạo này là tùy thuộc vào hàm băm), và giá trị cuối cùng của các chaining
variable chính là giá trị của hàm băm [1][2][4][5].
Thuật toán chung cho các hàm băm này như sau.
Thuật toán trên hàm băm C được lặp nhiều lần, đầu vào của lần lặp sau
là khối block message có chiều dài là 512 hoặc 1024 bít (chiều dài các block
message là 512 hay 1024 bít là tùy thuộc vào thuật toán) và giá trị của
chainging variable của vòng trước, ta có thể mô hình như sau:
Hình 1.1. Cấu trúc lặp của hàm băm MD
1.
Hàm băm MD4
MD4 (Message-Digest thuật toán 4) là một thuật toán (thứ tư trong loạt
a) được thiết kế bởi Giáo sư Ronald Rivest của MIT vào năm 1990. Nó thực
6
hiện một hàm băm mật mã để sử dụng trong kiểm tra tính toàn vẹn thông
điệp. Chiều dài của giá trị băm là 128 bit.
Thuật toán MD4 nhận dữ liệu đầu vào là một chuỗi bit x có chiều dài b
>= 0 tùy ý và sinh ra mã băm của x có chiều dài cố định 128 bit. Trước tiên
chuỗi bit x được định dạng lại bằng cách thêm r > 0 bit phụ thuộc vào x sao
cho chiều dài của chuỗi bit mới là b’ = b + r là bội số của 512.
Sau đó chia chuỗi bit mới này thành m khối, mỗi khối có độ dài đúng bằng
512 bit. Mỗi khối bit này lại chia thành 16 từ, mỗi từ có 32 bit.
Thuật toán MD4 tuần tự xử lý dãy m khối trong m lượt tính toán. Dữ
liệu đầu vào tại lượt tính toá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 toá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 toá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 toán, trong mỗi vòng gồm có 16 bước, mỗi bước thực hiện tính
toá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 toá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 toá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].
2.
Hàm băm SHA-1
Thuật toá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 toán cho hàm
băm MD5.
- 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 (00 ) =0x67452301
H 1( 0 ) =0xefcdab89
7
H (20 ) =0x98badcfe
H 3( 0 ) =0x10325476
H (40 ) =0xc3d2e1f0.
- 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.
- Khởi tạo các biến làm việc như sau ở vòng thứ i-1.
a=H (0i 1)
b=H 1( i 1)
c=H (2i 1)
d=H 3( i 1)
e=H (4i 1)
- Thực hiện việc biến đổi như sau.
For (t=0; t<=79; t++)
{
T = ROLT 5 (a) +
ft
(b, c, d) + e + K t +W t
e=d
d=c
c= ROLT 30 (b)
b=a
a=T
}
- Tính toán chuỗi đầu ra như sau.
H (0i ) = a + H (0i 1)
8
H 1( i ) = b + H 1( i 1)
H (2i ) = c + H (2i 1)
H 3( i ) = d + H 3( i 1)
H (4i ) = e + H (4i 1)
3.
Hàm băm SHA-256
Thuật toá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 toán cho hàm
băm MD5.
- 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 (00 ) =0x6a09e667
H 1( 0 ) =0xbb67ae85
H (20 ) =0x3c6ef372
H 3( 0 ) =0xa54ff53a
H (40 ) =0x510e527f.
H 5( 0 ) =0x9b05688c
H (60 ) =0x1f83d9ab
H (70 ) =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
- Khởi tạo các biến làm việc như sau .
a=H (0i 1)
b=H 1( i 1)
9
c=H (2i 1)
d=H 3( i 1)
e=H (4i 1)
f=H 5( i 1)
g=H (6i 1)
h=H (7i 1)
- Thực hiện việc biến đổi như sau
For (i=0; i<=63; i++)
{
{ 256}
(e) + Ch (e, f, g) +K
T 1 = h+
1
T2 =
{ 256}
(a ) +Maj (a, b, c)
0
h=g
g=f
f=e
e=d + T 1
d=c
c=b
b=a
a= T 1 + T 2
}
- Tính toán kết quả cuối cùng như sau.
H (0i ) = a + H (0i 1)
H 1( i ) = b + H 1( i 1)
H (2i ) = c + H (2i 1)
H 3( i ) = d + H 3( i 1)
{ 256}
t
+W t
10
H (4i ) = e + H (4i 1)
H 5( i ) = f + H 5( i 1)
H (6i ) = g + H (6i 1)
H (7i ) = e + H (7i 1)
Trong đó:
Ch(x, y, z) = (x ^ y) (⌐x z)
Maj(x, y, z) = x ^ y) (y ^ z) (z ^ x).
{ 256}
( x) = ROTR 2 (x)
ROTR 13 (x) ROTR 22 (x)
0
{ 256}
( x) = ROTR 6 (x)
ROTR 11 (x) ROTR 25 (x)
1
{0256} = ROTR 7 (x) ROTR 18 (x) SHR 3 (x)
1{256} = ROTR 17 (x) ROTR 19 (x) SHR 10 (x)
4.
Hàm băm SHA-384, SHA-512
Các thuật toá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).
-
Việc đệm được thực hiện tương tự việc đệm trong thuật toán cho hàm
băm MD5.
-
Chia bức thông điệp thành các khối 1024 bit.
-
Thực hiện việc khởi tạo cho các biến chaining variable như sau:
Với hàm băm SHA-384 các giá trị chaining variable được khởi tạo như
sau:
H (00 ) =0xcbbb9d5dc1059ed8
H 1( 0 ) =0x629a292a367cd507
H (20 ) =0x9159015a3070dd17
- Xem thêm -