ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
CHU THỊ THANH XUÂN
TÌM HIỂU VÀ PHÂN TÍCH ĐÁNH GIÁ
ĐỘ AN TOÀN CỦA THUẬT TOÁN MD5 LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN
Hà Nội – 2014
NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. NGUYỄN NGỌC CƢƠNG Hà Nội – 2014
3 Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5 LỜI CAM ĐOAN
Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá
nhân tôi, không sao chép lại của người khác. Trong toàn bộ nội dung của luận
văn, những điều đã trình bày là của cá nhân tôi hoặc là được tôi tổng hợp từ
nhiều nguồn tài liệu. Tất cả các nguồn tài liệu tham khảo có xuất xứ rõ ràng và
được trích dẫn hợp pháp.
Tôi xin chịu toàn bộ trách nhiệm và chịu mọi hình thức kỷ luật theo quy định
cho lời cam đoan của tôi.
Hà Nội, tháng 7 năm 2014
Học viên
Chu Thị Thanh Xuân
4
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
2.2 Ứng dụng của hàm băm MD5 21
2.2.1 Bảo vệ mật khẩu. 21
2.2.2 Kiểm tra tính toàn vẹn của tập tin. 22
2.3 Thuật toán MD5 23
Chương 3: ĐỘ AN TOÀN CỦA THUẬT TOÁN MD5 30
3.1 Tính an toàn của hàm băm MD5 đối với hiện tượng đụng độ 30
3.2 Tính an toàn của hàm băm MD5 đối với tính một chiều. 32
3.3 Tính an toàn của hàm băm MD5 đối với ứng dụng bảo vệ mật khẩu. 33
3.3.1 Kỹ thuật tấn công từ điển ( Dictionary Attack) 35
3.3.2 Kỹ thuật tấn công bảng cầu vồng ( Rainbow Table Attack) 36
3.3.3. Kỹ thuật tấn công brute force (Brute force attack) 37
Chương 4: THỬ NGHIỆM VÀ ĐÁNH GIÁ 40
4.1 Xây dựng cơ sở dữ liệu: 40
4.2 Bảng kết quả 40
KẾT LUẬN 44
TÀI LIỆU THAM KHẢO 45
PHỤ LỤC 47
6 Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
DANH MỤC CÁC KÝ HIỆU VÀ TỪ VIẾT TẮT
CPU
Central Processing Unit
CUDA
Compute Unified Device Architecture
8 Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1 Minh họa về hàm băm
Hình 1.2 Cấu trúc lặp của hàm băm MD
Hình 1.3 Cơ chế hoạt động của lưu trữ mật khẩu dùng hàm băm
Hình 1.4 Đấu giá trực tuyến dùng hàm băm
Hình 1.5 Gửi thông điệp sử dụng hàm hash
Hình 1.6 Hàm Hash hỗ trợ chữ ký số
Hình 2.1 Lưu trữ mật khẩu bằng hàm băm MD5
Hình 2.2 Thêm salt vào mật khẩu trước khi băm MD5
Hình 2.3 Mã MD5 được gửi kèm với file download bản Ghost Windows XP
Hình 2.4 Sử dụng phần mềm MD5 Check để kiểm tra tính toàn vẹn của tập tin
Hình 2.5 Hoạt động hàm MD5
Hình 2.6 Một thao tác MD5
Hình 2.7 Thêm các bít vào bản tin ban đầu
Hình 3.1 Ví dụ xung đột hàm băm MD5
Hình 3.2 Tấn công từ điển trên trang md5decrypter.co.uk
Hình 3.3 Phương thức hoạt động của bảng cầu vồng
9 Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
công sử dụng công nghệ GPU trên hệ thống máy tính hiện tại và các công cụ hỗ
trợ. Tác giả tiến hành khảo sát trên 100 hash MD5 được thu thập từ cơ sở dữ liệu
của các website bị lỗi và được mã hóa từ các mật khẩu do tác giả giả thiết dựa
trên thói quen sử dụng mật khẩu của người dùng.
Cấu trúc của luận văn gồm:
Chương 1: Giới thiệu về lý thuyết hàm băm mật mã, những tính chất của hàm
băm và ứng dụng của nó. Trong chương này cũng giới thiệu tổng quan về một số
hàm băm phổ biến.
Chương 2: Tìm hiểu hàm băm MD5, giải thuật MD5, chương trình cài đặt MD5
và ứng dụng chính của hàm băm MD5.
Chương 3: Độ an toàn của hàm băm MD5. Tìm hiểu về tính an toàn của hàm
băm MD5 đối với hiện tượng đụng độ. Đi sâu khảo sát một số kỹ thuật tấn công
hàm băm trong ứng dụng bảo vệ mật khẩu.
Chương 4: Thử nghiệm và đánh giá trên 100 hash mật khẩu được băm bằng
thuật toán MD5.
Tác giả xin chân thành cảm ơn sự hướng dẫn và chỉ bảo tận tình của thầy
Nguyễn Ngọc Cương – Trưởng khoa Toán Tin, Học viện An ninh nhân dân,
cảm ơn các thầy cô giáo trong khoa Hệ Thống Thông Tin trường Đại học Công
nghệ - Đại học Quốc Gia Hà Nội đã tạo điều kiện giúp tác giả hoàn thành luận
văn này. Cảm ơn gia đình, bạn bè cùng những người thân luôn bên cạnh tác giả
giúp tác giả vượt qua những khó khăn trong cuộc sống.
Trong quá trình thực hiện bản luận văn không tránh khỏi sai sót. Tác giả rất
mong nhận được sự nhận xét, đánh giá cũng như tạo điều kiện giúp đỡ của thầy
cô và các đồng nghiệp.
Hà Nội, tháng 7 năm 2014
Học viên
12 Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
Nếu dữ liệu trong thông điệp x thay đổi hay bị xóa để thành thông điệp x‟
thì h(x‟)
h(x). Cho dù chỉ là một sự thay đổi nhỏ hay chỉ là xóa đi 1 bit dữ liệu
của thông điệp thì giá trị băm cũng vẫn thay đổi. Điều này có nghĩa là: hai thông
điệp hoàn toàn khác nhau thì giá trị hàm băm cũng khác nhau.
Nội dung của thông điệp gốc không thể bị suy ra từ giá trị hàm băm.
Nghĩa là: với thông điệp x thì dễ dàng tính được z = h(x), nhưng lại không thể
(thực chất là khó) suy ngược lại được x nếu chỉ biết giá trị hàm băm h(x).
1.1.3. Tính chất của hàm băm:
Việc đưa hàm băm h vào dùng trong sơ đồ chữ ký số không làm giảm sự
an toàn của sơ đồ chữ ký số vì nó là bản tóm lược thông báo – bản đại diện cho
thông điệp – được ký chứ không phải là thông điệp gốc. Điều cần thiết đối với
hàm băm h là cần thỏa mãn một số tính chất sau để tránh bị giả mạo:
Tính chất 1: Hàm băm h là không va chạm yếu
Hàm băm h là không va chạm yếu nếu khi cho trước một bức điện x,
không thể tiến hành về mặt tính toán để tìm ra một bức điện x’
x mà h(x’) =
h(x).
Tính chất 2: Hàm băm h là không va chạm mạnh:
Xét một kiểu tấn công như sau: Đầu tiên, tên giả mạo tìm ra được hai
bức thông điệp x‟ và x (x‟
x) mà có h(x‟) = h(x) (ta coi bức thông điệp x là hợp
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ứ hai 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 bít). Ở
thời điểm bắt đầu các chaining variable có giá trị khởi tạo (giá trị 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.
Thuật toán chung cho các hàm băm này như sau:
Given: compression function C:{0,1}
n
x {0,1}
m
{0,1}
n
;
n – bit constant IV.
Input: message M
1. Break M into m – bit block M
1
,…, M
k
, padding if necessary;
2. Let M
k+1
be encoding of |M|;
3. Let h
0
= IV;
4. For i = 1 to k +1 let h
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.
15 Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
1.2.2. Hàm băm MD5
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 5‟ đượ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 2004 và 2005, 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 va chạm mạnh). Tuy vậy ngày nay MD5 vẫn còn được sử dụng
phổ biến. Hàm băm MD5 sẽ được giới thiệu chi tiết trong chương 2.
1.2.3. Hàm băm chuẩn SHA
Chuẩn hàm băm SHA phức tạp và chậm hơn dòng MD. SHA được thiết
kế để chạy trên máy kiến trúc endian lớn hơn là trên máy endian nhỏ. SHA tạo
cá nhân hay máy chủ, trong một file dữ liệu hay trong hệ quản trị cơ sở dữ liệu.
Như vậy sẽ xuất hiện một nguy cơ là có một người khác, hoặc là người quản
trị administrator, hoặc là hacker, có thể mở được file dữ liệu hoặc cơ sở dữ liệu
và xem trộm được mật khẩu. Như vậy mật khẩu không thể được giữ bí mật tuyệt
đối. Một phương pháp để bảo vệ mật khẩu là dùng mã hóa, chương trình phần
mềm sẽ dùng một khóa bí mật để mã hóa mật khẩu trước khi lưu mật khẩu
xuống file hay cơ sở dữ liệu. Do đó tránh được vấn đề xem trộm mật khẩu. Tuy
nhiên phương pháp này có yếu điểm là lại phải lo bảo vệ khóa bí mật này. Nếu
khóa bí mật bị lộ thì việc mã hóa không còn ý nghĩa. Phương pháp bảo vệ mật
khẩu hiệu quả nhất là dùng một hàm băm (MD5, SHA). Khi người sử dụng đăng
ký mật khẩu, giá trị băm của mật khẩu được tính bằng một hàm băm nào đó. Giá
trị băm được lưu trữ vào file hay cơ sở dữ liệu. Vì hàm băm là hàm một chiều,
nên dù biết được giá trị băm và loại hàm băm, hacker cũng không thể suy ra
được mật khẩu. Khi người sử dụng đăng nhập, mật khẩu đăng nhập được tính
giá trị băm và so sánh với giá trị băm đang được lưu trữ. Do tính chống va chạm
mạnh, chỉ có một mật khẩu duy nhất có giá trị băm tương ứng, nên không ai
khác ngoài người sử dụng có mật khẩu đó mới có thể đăng nhập ứng dụng.
17 Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
18 Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
Hình 1.4 Đấu giá trực tuyến dùng hàm băm
1.3.3 Download file
Khi chúng ta download file từ mạng internet, nếu chất lượng mạng không
tốt thì có thể xảy ra lỗi trong quá trình download làm cho file tại máy client khác
với file trên server. Hàm băm có thể giúp chúng ta phát hiện ra những trường
hợp bị lỗi như vậy. Gọi file cần download trên server là X, và giá trị hash theo
MD5 (hoặc SHA) của file X mà server đã tính sẵn và cung cấp trên trang web là
H
X
(có thể xem bằng mắt). Gọi Y là file mà người sử dụng download được tại
máy. Người sử dụng sẽ tính giá trị MD5 ( hoặc SHA) H
Y
cho file Y. Như vậy
nếu H
X
= H
Y
thì theo tính chống va chạm của hàm hash, file Y hoàn toàn giống
file X và quá trình download không xảy ra lỗi.
1.3.4 Hàm băm và chữ ký số
Trong phần này tác giả tìm hiểu cách thức ứng dụng hàm băm vào vấn đề
chứng thực mà ta gọi là chữ ký số. Việc sử dụng khóa bí mật chung cho người
Trong mô hình này, Bắc sau khi tính giá trị hash H
A
cho thông điệp M thì sẽ mã
hóa H
A
bằng khóa riêng của Bắc để tạo thành chữ ký số DS. Bắc gửi kèm DS
theo M cho Nam. Nam dùng khóa công khai của Bắc để kiểm tra chữ ký số DS
và có được giá trị hash H
A
của Bắc. Vì Đông không có K
RA
nên không thể sửa
được H
A
. Ngoài ra, vì Bắc là người duy nhất có K
RA
, nên chỉ có Bắc mới có thể
20 Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
tạo DS từ M. Do đó Bắc không thể từ chối là đã gửi bản tin. Chữ ký số chỉ cần
mã hóa giá trị hash mà không cần mã hóa toàn bộ thông điệp M. Vì phương
pháp mã hóa khóa công khai tốn kém thời gian nên nếu M là một thông điệp dài,
thì việc không mã hóa M giúp tiết kiệm được nhiều thời gian.
21 Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
22 Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
Hình 2.1: Lưu trữ mật khẩu bằng hàm băm MD5
Trong thực tế việc mã hóa MD5 một lần những mật khẩu đơn giản dễ bị
tấn công bởi phương pháp tấn công từ điển và tấn công brute force nên các
website hiện nay thường sử dụng mã MD5 nhiều lần hoặc thêm muối (salt) vào
mật khẩu trước khi mã hóa chúng.
Hình 2.2 Thêm salt vào mật khẩu trước khi băm MD5
2.2.2 Kiểm tra tính toàn vẹn của tập tin.
Trong quá trình truyền tập tin, nhất là những tập tin có dung lượng lớn
khó tránh khỏi bị lỗi trên đường truyền. Do đó để kiểm tra xem tập tin tải về có
còn nguyên vẹn hay không thì máy chủ tập tin sẽ băm tập tin bằng hàm băm
MD5 và cung cấp mã MD5 này kèm theo tập tin. Người sử dụng sau khi
download tập tin sẽ sử dụng phần mềm kiểm tra gọi là checksum MD5 để xem
tập tin tải về có mã MD5 trùng với mã MD5 của nhà cung cấp hay không. Nếu
Hình 2.4 Sử dụng phần mềm MD5 Check để kiểm tra tính toàn vẹn của tập tin 2.3 Thuật toán MD5
INPUT: Thông điệp (văn bản) có độ dài tùy ý.
OUTPUT : Bản băm, đại diện cho thông điệp gốc, độ dài cố định 128 bit.
Mẩu tin đầu 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: đầu
tiên một bit đơn 1 được gắn vào cuối mẩu tin. Tiếp theo là một dãy các số 0 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 cho chiều dài của mẩu
tin gốc.
24 Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5 Hình 2.5 Hoạt động hàm MD5
Giải thuật 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. Giải thuật 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 2.6 mô tả một tác vụ trong một vòng; một hàm F được dùng trong mỗi
vòng. M
Một chuỗi các bit có thể được hiểu theo nghĩa như là một chuỗi các byte, và mỗi
nhóm 8 bit được xem như một byte với bit MSB (bit cao) được viết trước.
Một chuỗi các byte được hiểu như là một chuỗi các từ (word) 32 bit.
Trong đó, mỗi nhóm 4 byte này được xem là một từ (word) với byte thấp được
viết trước.
Dấu “+” biểu thị phép cộng các word.
X<<<s : biểu thị giá trị 32 bit thu được từ phép dịch bit quay vòng sang
trái s bit từ X.
Not(X) : phép bù từng bit của X
X v Y : phép OR từng bit X và Y
X xor Y : phép XOR từng bit X và Y
XY : phép AND từng bit X và Y
Mô tả giải thuật MD5
Giả sử chúng ta có một bản tin đầu vào độ dài b và muốn tìm một tóm
lược của nó. Ở đây b là một số nguyên không âm bất kỳ; b có thể là 0, b không
cần là bội của 8, và có thể lớn tùy ý. Hình dung rằng các bit của bản tin được
viết như sau :
m_0 m_1 m_{b-1}
Để tính toán tóm lược của bản tin m , giải thuật thực hiện theo 4 bước
Bƣớc 1: Thêm các bit vào bản tin.
Bản tin đầu vào B được độn thêm các bits sao cho chiều dài của nó đồng
dư với 448 theo modulo 512. Có nghĩa là, bản tin được mở rộng sao cho chỉ cần
thêm 64 bit nữa sẽ là bội của 512. Việc độn luôn được thực hiện, bất kể chiều
dài của bản tin đầu vào đã đồng dư với 448 theo modulo 512.
Copyright: Tài liệu đại học ©