leave_me_leave_me_leave_me.alone
New Member
Luận vă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 ThS. Công nghệ thông tin: 60 48 01 04
Nhà xuất bản: ĐHCN
Ngày: 2014
Chủ đề: Công nghệ thông tin
Hệ thống thông tin
Thuật toán MD5
Miêu tả: 56 tr. + CD-ROM
Luận văn ThS. Hệ thống thông tin -- Trường Đại học Công nghệ. Đại học Quốc gia Hà Nội, 2014
MỤC LỤC
LỜI CAM ĐOAN.................................................................................................. 3
MỤC LỤC............................................................................................................. 4
DANH MỤC CÁC KÝ HIỆU VÀ TỪ VIẾT TẮT .............................................. 6
DANH MỤC CÁC BẢNG.................................................................................... 7
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ............................................................... 8
MỞ ĐẦU............................................................................................................... 9
Chương 1: LÝ THUYẾT VỀ HÀM BĂM.......................................................... 11
1.1 Tổng quan về hàm băm ............................................................................. 11
1.1.1. Định nghĩa hàm băm ......................................................................... 11
1.1.2. Đặc tính của hàm băm....................................................................... 11
1.1.3. Tính chất của hàm băm: .................................................................... 12
1.2. Một số hàm băm phổ biến........................................................................ 13
1.2.1 Hàm băm MD4.................................................................................. 14
1.2.2. Hàm băm MD5.................................................................................. 15
1.2.3. Hàm băm chuẩn SHA........................................................................ 15
1.3 Ứng dụng của hàm băm ............................................................................ 16
1.3.1 Bảo vệ mật khẩu................................................................................. 16
1.3.2 Đấu giá trực tuyến.............................................................................. 17
1.3.3 Download file..................................................................................... 18
1.3.4 Hàm băm và chữ ký số....................................................................... 18
Chương 2: HÀM BĂM MD5.............................................................................. 21
2.1 Giới thiệu MD5 ......................................................................................... 21
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi5
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............................................................................................................ 476
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
GPGPU General Purpose computing
GPU Graphic Proccessing Unit
MD Message Digest
MD2 Message Digest 2
MD4 Message Digest 4
MD5 Message Digest 5
RSA Rivest Shamir Adleman
SHA Secure Hash Algorithm
VPU Visual Processing Unit
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi7
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 BẢNG
Bảng 3.1 : Minh họa tốc độ kiểm tra khóa MD5 trên CPU và các GPU
Bảng 3.2 : Minh hoạ hiệu năng thực hiện công việc giải mã MD5 trên CPU và
GPU
Bảng 4.1 Khả năng khôi phục mật khẩu trên một số công cụ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 cách hoạt động của bảng cầu vồng
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi9
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
MỞ ĐẦU
Trong mật mã học MD5 (Message-Digest algorithm 5) là một hàm băm
mật mã được sử dụng phổ biến với giá trị băm (Hash) dài 128 bit. Là một chuẩn
Internet (RFC 1321) MD5 đã được dùng trong nhiều ứng dụng bảo mật và cũng
được dùng phổ biến để kiểm tra tính toàn vẹn của tập tin. Trong ứng dụng
truyền dữ liệu, máy chủ tập tin thường cung cấp một checksum MD5 được tính
toán trước cho tập tin, để người dùng có thể so sánh với checksum của tập tin đã
tải về. Trong ứng dụng chữ ký số, MD5 sẽ băm thông điệp dài thành văn bản đại
diện và việc ký sẽ được thực hiện trên văn bản thay mặt trước khi được truyền đi.
Trong ứng dụng mật khẩu, chương trình sẽ băm từng mật khẩu sang không gian
mã MD5 và so sánh mã này với mã MD5 cần được giải mã.
MD5 được thiết kế bởi Ronald Rivest vào năm 1991 để thay thế cho hàm
băm trước đó là MD4 (vì MD4 đã được chứng minh là không an toàn). Từ năm
1996 người ta đã phát hiện ra một lỗ hổng trong MD5 và các chuyên gia mã hóa
bắt đầu đề nghị sử dụng giải thuật khác như SHA-1, đến năm 2005 nhiều lỗ
hổng hơn được 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.
Trên thực tế trong các ứng dụng bảo vệ mật khẩu giải thuật MD5 vẫn
được sử dụng rộng rãi. Có nhiều phương pháp và kỹ thuật tấn công mật khẩu
được công bố nhưng mức độ thành công của các phương pháp này phụ thuộc lớn
vào tài nguyên của máy tính và cách đặt mật khẩu. Do vậy để có một đánh giá
cụ thể về độ an toàn của thuật toán MD5 trong các ứng dụng của nó, đặc biệt là
ứng dụng lưu trữ mật khẩu, tác giả đã lựa chọn đề tài: “Tìm hiểu và phân tích
đánh giá độ an toàn của thuật toán MD5”.
Với mục tiêu đánh giá độ an toàn của thông tin khi sử dụng thuật toán
băm MD5 trong các ứng dụng của nó, tác giả đã sử dụng phương pháp khảo sát
các kỹ thuật tấn công MD5 hiện nay và đi sâu vào đánh giá mức độ thành công
dò tìm mật khẩu trong các kỹ thuật tấn công từ điển, tấn công brute force và tấn10
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 Thank 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,
Thank 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. Thank 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
Chu Thị Thanh Xuân
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi11
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
Chƣơng 1: LÝ THUYẾT VỀ HÀM BĂM
1.1 Tổng quan về hàm băm
1.1.1. Định nghĩa hàm băm
Hàm băm (tiếng Anh: hash function) là giải thuật nhằm sinh ra các giá
trị băm tương ứng với mỗi khối dữ liệu (có thể là một chuỗi kí tự, một đối
tượng trong lập trình hướng đối tượng, v.v...). Giá trị băm đóng vai gần như
một khóa để phân biệt các khối dữ liệu, tuy nhiên, người ta chấp hiện tƣợng
trùng khóa hay còn gọi là đụng độ và cố gắng cải thiện giải thuật để giảm thiểu
sự đụng độ đó. Hàm băm thường được dùng trong bảng băm nhằm giảm chi phí
tính toán khi tìm một khối dữ liệu trong một tập hợp (nhờ việc so sánh các giá
trị băm nhanh hơn việc so sánh những khối dữ liệu có kích thước lớn)
Giá trị của hàm băm là duy nhất, và không thể suy ngược lại được nội
dung thông điệp từ giá trị băm này.
Ví dụ minh họa về hàm băm (trích từ
Hình 1.1 Minh họa về hàm băm
1.1.2. Đặc tính của hàm băm
Hàm băm h là hàm băm một chiều (one-way hash) với các đặc tính sau:
Với thông điệp đầu vào x thu được bản băm z = h(x) là duy nhất.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 thay mặt 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
lệ, còn x‟ là giả mạo). Tiếp theo, hắn đưa cho ông A và thuyết phục ông này kí
vào bản tóm lược h(x) để nhận được y. Khi đó (x‟, y) là bức điện giả mạo nhưng
hợp lệ.
Để tránh kiểu tấn công này, hàm h phải thỏa mãn tính không va chạm
mạnh: Hàm băm h là không va chạm mạnh nếu không có khả năng tính toán để
tìm ra hai bức thông điệp x và x’ mà x x’ và h(x) = h(x’).
Tính chất 3: Hàm băm h là hàm một chiều:
Xét một kiểu tấn công như sau: Việc giả mạo các chữ ký trên bản tóm
lược z thường xảy ta với các sơ đồ chữ ký số. Giả sử tên giả mạo tính chữ ký
trên bản tóm lược z, sau đó hắn tìm một bản thông điệp x‟ được tính ngược từ
bản thay mặt z, z = h(x‟). Tên trộm thay thế bản thông điệp x hợp lệ bằng bản
thông điệp x‟ giả mạo, nhưng lại có z = h(x‟). Và hắn ký số trên bản đại diện
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi13
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
cho x‟ bằng đúng chữ ký hợp lệ. Nếu làm được như vậy thì (x‟, y) là bức điện
giả mạo nhưng hợp lệ.
Để tránh được kiểu tấn công này, h cần thỏa mãn tính chất một chiều:
Hàm băm h là một chiều nếu khi cho trước một bản tóm lược thông báo z thì
không thể thực hiện về mặt tính toán để tìm ra thông điệp ban đầu x sao cho h(x)
= z .
1.2. 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ứ 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 hay 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 M1,…, Mk, padding if necessary;
2. Let Mk+1 be encoding of |M|;
3. Let h0 = IV;
4. For i = 1 to k +1 let hi = C (hi-1, Mi);
5. Output hk+1.
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 hay 1024 bit (chiều dài các block message là
512 hay 1024 bit là tùy thuộc vào thuật toán) và giá trị của chaining variable của
vòng trước, ta có mô hình như sau:14
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
Hình 1.2 : Cấu trúc lặp của hàm băm MD
1.2.1 Hàm băm MD4
MD4 (Message-Digest 4) được thiết kế bởi giáo sư Ronald Rivest của đại
học MIT vào năm 1990. Nó thực hiện một hàm băm mật mã để sử dụng trong
kiểm tra tính toàn vẹn của thông điệp. Chiều dài của giá trị băm là 128bit.
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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi15
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
ra bản tóm lược thông điệp có kích thước 160 bit, sử dụng 5 thanh ghi 32 bit.
Năm thuật giải SHA là SHA-1 (trả lại kết quả dài 160 bit), SHA-224 (trả
lại kết quả dài 224 bit), SHA-256 (trả lại kết quả dài 256 bit), SHA-384 (trả lại
kết quả dài 384 bit), và SHA-512 (trả lại kết quả dài 512 bit).
Thuật giải SHA là thuật giải băm mật được phát triển bởi cục an ninh
quốc gia Mĩ (National Security Agency hay NSA) và được xuất bản thành chuẩn
của chính phủ Mĩ bởi viện công nghệ và chuẩn quốc gia Mĩ (National Institute
of Standards and Technology hay NIST). Bốn thuật giải sau thường được gọi
chung là SHA-2.
SHA-1 được sử dụng rộng rãi trong nhiều ứng dụng và giao thức an ninh
khác nhau, bao gồm TLS và SSL, PGP,SSH, S/MIME, và IPSec.
Hiện nay, SHA-1 không còn được coi là an toàn bởi đầu năm 2005, ba
nhà mật mã học người Trung Quốc đã phát triển thành công một thuật giải dùng
để 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 SHA-1.
Tuy vậy SHA vẫn được sử dụng phổ biến, đặc biệt là SHA-2, chưa có
phát minh nào tìm ra tính không an toàn của nó.16
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
1.3 Ứng dụng của hàm băm
1.3.1 Bảo vệ mật khẩu
Hầu hết các ứng dụng phần mềm ngày nay, dù trên máy đơn hay trên web
đều có chứng thực người sử dụng. Nghĩa là để sử dụng ứng dụng, người sử dụng
phải qua một cơ chế chứng thực tên người dùng và mật khẩu, và từ đó được
cung cấp các quyền sử dụng phần mềm khác nhau. Do đó vấn đề bảo mật mật
khẩu là vấn đề quan trọng đối với mọi phần mềm. Mật khẩu người sử dụng
thường gồm các chữ cái thường và hoa, cộng thêm các chữ số. Giả sử mật khẩu
được lưu trữ dưới dạng thường, không mã hóa, tại một nơi nào đó trên máy tính
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, hay là người quản
trị administrator, hay là hacker, có thể mở được file dữ liệu hay 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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi17
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
Hình 1.3. Cơ chế hoạt động của lưu trữ mật khẩu dùng hàm băm
1.3.2 Đấu giá trực tuyến
Phương pháp lưu trữ mật khẩu bằng giá trị Hash cũng được áp dụng
tương tự cho việc đấu giá trực tuyến bằng hình thức đấu giá bí mật. Giả sử Bắc,
Nam và Đông cùng tham gia đấu giá, họ sẽ cung cấp mức giá của mình cho
trọng tài. Các mức giá này được giữ bí mật cho đến khi cả ba đều nộp xong. Nếu
ai là người đưa ra mức giá cao nhất thì thắng thầu. Điểm quan trọng của phương
pháp đấu giá này là giá của Bắc, Nam, và Đông phải được giữ bí mật trước khi
công bố. Giả sử mức giá của Bắc là 100, mức giá của Nam là 110, nếu Đông
thông đồng với trọng tài và biết được giá của Bắc và Nam, Đông có thể đưa ra
mức giá 111 và thắng thầu.Có thể tránh những hình thức lừa đảo như vậy bằng
cách sử dụng hàm băm. Từ mức giá bỏ thầu, Bắc và Nam sẽ tính các giá trị băm
tương ứng và chỉ cung cấp cho trọng tài các giá trị băm này. Vì hàm băm là một
chiều, nếu trọng tài và Đông bắt tay nhau thì cũng không thể biết được giá của
Bắc và Nam là bao nhiêu. Đến khi công bố, Bắc, Nam và Đông sẽ đưa ra mức
giá của mình. Trọng tài sẽ tính các giá trị băm tương ứng và so sánh với các giá
trị băm đã nộp để bảo đảm rằng mức giá mà Bắc, Nam và Đông là đúng với ý
định ban đầu của họ. Vì tính chống trùng của hàm băm nên Bắc, Nam và Đông
không thể thay đổi giá so với ý định ban đầu.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 (hay SHA) của file X mà server đã tính sẵn và cung cấp trên trang web là
HX (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 ( hay SHA) HY cho file Y. Như vậy
nếu HX = HY 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
gửi và người nhận trong mã chứng thực thông điệp MAC sẽ gặp phải vấn đề
tính không từ chối tương tự như mã hóa đối xứng. Dùng hàm băm và mã hóa
khóa công khai khắc phục được vấn đề này. Trước tiên xét một mô hình đơn
giản được thể hiện ở hình 1.5
Chƣơng 3: ĐỘ AN TOÀN CỦA THUẬT TOÁN MD5
Đặt vấn đề:
MD5 đã từng được coi là chuẩn Internet, được ứng dụng rộng rãi trong
nhiều lĩnh vực bởi tính không giải ngược của nó và độ dài đầu ra là 128 bit được
tính toán là đủ an toàn cho một thuật toán băm.
Nhưng ngay từ năm 1996, người ta đã tìm thấy lỗ hổng của nó tuy là
không rõ ràng lắm. Đến năm 2005, Xiaoyun Wang cùng cộng sự đã biểu diễn
việc xây dựng hai giấy phép X.509 với các khóa công cộng khác nhau cho cùng
bảng băm MD5. Việc tìm thấy xung đột này sẽ là cơ sở khiến kẻ giả mạo tạo ra
một thông điệp khác có cùng mã MD5 với thông điệp cần kiểm tra. Nhưng theo
tính toán độ phức tạp để tìm ra 2 thông điệp có cùng mã băm MD5 là khoảng 264
bước tính; và độ phức tạp để tìm một thông điệp có cùng mã băm MD5 với
thông điệp đã đánh giá là 2128 bước tính.
Ngày nay MD5 vẫn được dùng rộng rãi để lưu trữ mật khẩu bởi thuật toán
số hóa thông điệp MD5 là khá đơn giản để thực hiện. Nhiều ngôn ngữ lập trình
còn cung cấp thư viện hàm MD5 có sẵn nên để tạo giá trị mã MD5 đúng chuẩn
là dễ dàng. Việc tấn công MD5 bằng cách tìm ra mật khẩu khi biết mã băm của
nó chỉ có thể thực hiện bằng nguyên lý vét cạn mà theo tính toán thì việc làm đó
tốn rất nhiều thời gian. Nhưng với công nghệ hiện đại và khả năng tính toán cao
của các phần cứng cùng phần mềm chuyên dụng đã tăng tốc độ dò tìm mật khẩu
lên rất nhiều.
Để đánh giá độ an toàn của thuật toán băm MD5, tác giả tiến hành tìm
hiểu tính an toàn của hàm băm đối với hiện tượng đụng độ, rồi đi sâu vào tìm
hiểu các kỹ thuật tấn công hàm băm MD5 trong việc khôi phục mật khẩu.
3.1 Tính an toàn của hàm băm MD5 đối với hiện tƣợng đụng độ
Hàm băm được xem là an toàn đối với hiện tượng đụng độ khi rất khó tìm
được hai thông điệp có cùng giá trị băm.
Nhận xét: Trong một tập hợp mà các phần tử mang một trong N giá trị
cho trước với xác suất bằng nhau, chúng ta cần khoảng N phép thử ngẫu nhiên
để tìm ra một cặp phần tử có cùng giá trị.
Như vậy, phương pháp hàm băm được xem là an toàn đối với hiện tượng đụng
độ nếu chưa có phương pháp tấn công nào có thể tìm ra cặp thông điệp có cùng
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi31
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
giá trị hàm băm với số lượng tính toán ít hơn đáng kể so với ngưỡng 2n/2, với n
là kích thước (tính bằng bit) của giá trị băm.
Phương pháp tấn công dựa vào đụng độ:
• Tìm ra 2 thông điệp có nội dung khác nhau nhưng cùng giá trị băm.
• Ký trên một thông điệp, sau đó, người ký sẽ không thừa nhận đây là chữ
ký của mình mà nói rằng mình đã ký trên một thông điệp khác. Như vậy, cần
phải chọn 2 thông điệp “đụng độ” với nhau trước khi ký.
Hàm băm MD5 đã được coi là không an toàn đối với hiện tượng đụng độ
khi một loạt các công bố từ năm 1996 đến năm 2005 chỉ ra những xung đột
MD5 được tìm thấy trong vài giờ thậm chí vài phút trên máy tính xách tay.
Một ví dụ về xung đột hàm băm MD5:
Hình 3.1 Ví dụ xung đột hàm băm MD5
Tuy nhiên trong ứng dụng download file để tìm một tập tin có cùng mã
MD5 với tập tin của nhà cung cấp lại là một việc có độ phức tạp tăng lên gấp
nhiều lần so với việc tìm ra hai thông điệp bất kỳ có cùng mã MD5.
Trong ứng dụng chữ ký số, để tìm ra hai thông điệp có cấu trúc tương tự
nhau (ví dụ như hai bản hợp đồng) có cùng mã MD5 nhằm mục đích giả mạo
hay từ chối trách nhiệm lại là một việc dường như không thể làm được.32
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
Do vậy tùy vào từng mục đích sử dụng hàm băm MD5 trong những ứng
công cụ thể, hàm băm MD5 vẫn đảm bảo được độ an toàn đối với hiện tượng
đụng độ.
3.2 Tính an toàn của hàm băm MD5 đối với tính một chiều.
Hàm băm được xem là hàm một chiều khi cho trước giá trị băm, không
thể tái tạo lại thông điệp ban đầu. Như vậy, trong trường hợp lý tưởng, cần
thực hiện hàm băm cho khoảng 2n thông điệp để tìm ra được thông điệp tương
ứng với một giá trị băm. Nếu tìm ra được một phương pháp tấn công cho phép
xác định được thông điệp tương ứng với một giá trị băm cho trước thì thuật toán
băm sẽ không còn an toàn nữa.
Ta xét tính an toàn của hàm băm MD5:
Giả sử cho trước một giá trị băm MD5 là h(x), hãy tính khả năng tìm ra
thông điệp x khi không biết bất kỳ dữ kiện gì ngoài mã băm h(x). Đến nay chưa
có một phương pháp nào có thể tìm ra x khi biết h(x) bằng cách sử dụng thuật
toán. Cách duy nhất là người ta sẽ duyệt qua tất cả các khả năng có thể có của x
rồi tính giá trị băm h(x), nếu nó trùng với giá trị băm ban đầu thì x chính là
thông điệp cần tìm.
Độ phức tạp ở đây là không gian chứa thông điệp x quá lớn. Giả sử x nằm
trong tập các ký tự có thể in ra được (95 ký tự) thì số các phương án x cần duyệt
là: 951 +952 +953+954+….+9595 ≈ 7x10187
Với máy tính có tốc độ xử lý 1 phép tính / 1micro giây thì phải mất
khoảng 10174 năm, điều đó là không khả thi. Ngay cả với một siêu máy tính có
tốc độ xử lý 1 nghìn tỷ phép tính / giây thì cũng phải mất 1019 năm.
Trên thực tế chẳng có ứng dụng bảo mật nào đi tìm một thông điệp khi
biết giá trị băm của nó mà không có các dữ kiện liên quan. Ví dụ như trong ứng
dụng bảo vệ mật khẩu của hàm băm MD5, việc tìm mật khẩu khi biết giá trị băm
MD5 phải dựa vào căn cứ sau: Mật khẩu là các ký tự thường ( a…z), ký tự hoa
(A…Z), chữ số (0…9) và một số ký tự đặc biệt ( @, _, -, !, $...) và mật khẩu
thường có độ dài tối đa là 15 ký tự. Ngoài ra còn dựa vào thói quen đặt mật khẩu
của người dùng như là các cụm từ có nghĩa như tên email, họ tên, dãy số dễ nhớ,
số điện thoại, ngày tháng năm sinh…
Dựa vào những đặc điểm trên tác giả sẽ đánh giá tính an toàn của MD5
trong ứng công cụ thể, đó là khôi phục mật khẩu khi biết giá trị băm MD5.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Nhà xuất bản: ĐHCN
Ngày: 2014
Chủ đề: Công nghệ thông tin
Hệ thống thông tin
Thuật toán MD5
Miêu tả: 56 tr. + CD-ROM
Luận văn ThS. Hệ thống thông tin -- Trường Đại học Công nghệ. Đại học Quốc gia Hà Nội, 2014
MỤC LỤC
LỜI CAM ĐOAN.................................................................................................. 3
MỤC LỤC............................................................................................................. 4
DANH MỤC CÁC KÝ HIỆU VÀ TỪ VIẾT TẮT .............................................. 6
DANH MỤC CÁC BẢNG.................................................................................... 7
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ............................................................... 8
MỞ ĐẦU............................................................................................................... 9
Chương 1: LÝ THUYẾT VỀ HÀM BĂM.......................................................... 11
1.1 Tổng quan về hàm băm ............................................................................. 11
1.1.1. Định nghĩa hàm băm ......................................................................... 11
1.1.2. Đặc tính của hàm băm....................................................................... 11
1.1.3. Tính chất của hàm băm: .................................................................... 12
1.2. Một số hàm băm phổ biến........................................................................ 13
1.2.1 Hàm băm MD4.................................................................................. 14
1.2.2. Hàm băm MD5.................................................................................. 15
1.2.3. Hàm băm chuẩn SHA........................................................................ 15
1.3 Ứng dụng của hàm băm ............................................................................ 16
1.3.1 Bảo vệ mật khẩu................................................................................. 16
1.3.2 Đấu giá trực tuyến.............................................................................. 17
1.3.3 Download file..................................................................................... 18
1.3.4 Hàm băm và chữ ký số....................................................................... 18
Chương 2: HÀM BĂM MD5.............................................................................. 21
2.1 Giới thiệu MD5 ......................................................................................... 21
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi5
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............................................................................................................ 476
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
GPGPU General Purpose computing
GPU Graphic Proccessing Unit
MD Message Digest
MD2 Message Digest 2
MD4 Message Digest 4
MD5 Message Digest 5
RSA Rivest Shamir Adleman
SHA Secure Hash Algorithm
VPU Visual Processing Unit
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi7
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 BẢNG
Bảng 3.1 : Minh họa tốc độ kiểm tra khóa MD5 trên CPU và các GPU
Bảng 3.2 : Minh hoạ hiệu năng thực hiện công việc giải mã MD5 trên CPU và
GPU
Bảng 4.1 Khả năng khôi phục mật khẩu trên một số công cụ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 cách hoạt động của bảng cầu vồng
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi9
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
MỞ ĐẦU
Trong mật mã học MD5 (Message-Digest algorithm 5) là một hàm băm
mật mã được sử dụng phổ biến với giá trị băm (Hash) dài 128 bit. Là một chuẩn
Internet (RFC 1321) MD5 đã được dùng trong nhiều ứng dụng bảo mật và cũng
được dùng phổ biến để kiểm tra tính toàn vẹn của tập tin. Trong ứng dụng
truyền dữ liệu, máy chủ tập tin thường cung cấp một checksum MD5 được tính
toán trước cho tập tin, để người dùng có thể so sánh với checksum của tập tin đã
tải về. Trong ứng dụng chữ ký số, MD5 sẽ băm thông điệp dài thành văn bản đại
diện và việc ký sẽ được thực hiện trên văn bản thay mặt trước khi được truyền đi.
Trong ứng dụng mật khẩu, chương trình sẽ băm từng mật khẩu sang không gian
mã MD5 và so sánh mã này với mã MD5 cần được giải mã.
MD5 được thiết kế bởi Ronald Rivest vào năm 1991 để thay thế cho hàm
băm trước đó là MD4 (vì MD4 đã được chứng minh là không an toàn). Từ năm
1996 người ta đã phát hiện ra một lỗ hổng trong MD5 và các chuyên gia mã hóa
bắt đầu đề nghị sử dụng giải thuật khác như SHA-1, đến năm 2005 nhiều lỗ
hổng hơn được 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.
Trên thực tế trong các ứng dụng bảo vệ mật khẩu giải thuật MD5 vẫn
được sử dụng rộng rãi. Có nhiều phương pháp và kỹ thuật tấn công mật khẩu
được công bố nhưng mức độ thành công của các phương pháp này phụ thuộc lớn
vào tài nguyên của máy tính và cách đặt mật khẩu. Do vậy để có một đánh giá
cụ thể về độ an toàn của thuật toán MD5 trong các ứng dụng của nó, đặc biệt là
ứng dụng lưu trữ mật khẩu, tác giả đã lựa chọn đề tài: “Tìm hiểu và phân tích
đánh giá độ an toàn của thuật toán MD5”.
Với mục tiêu đánh giá độ an toàn của thông tin khi sử dụng thuật toán
băm MD5 trong các ứng dụng của nó, tác giả đã sử dụng phương pháp khảo sát
các kỹ thuật tấn công MD5 hiện nay và đi sâu vào đánh giá mức độ thành công
dò tìm mật khẩu trong các kỹ thuật tấn công từ điển, tấn công brute force và tấn10
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 Thank 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,
Thank 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. Thank 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
Chu Thị Thanh Xuân
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi11
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
Chƣơng 1: LÝ THUYẾT VỀ HÀM BĂM
1.1 Tổng quan về hàm băm
1.1.1. Định nghĩa hàm băm
Hàm băm (tiếng Anh: hash function) là giải thuật nhằm sinh ra các giá
trị băm tương ứng với mỗi khối dữ liệu (có thể là một chuỗi kí tự, một đối
tượng trong lập trình hướng đối tượng, v.v...). Giá trị băm đóng vai gần như
một khóa để phân biệt các khối dữ liệu, tuy nhiên, người ta chấp hiện tƣợng
trùng khóa hay còn gọi là đụng độ và cố gắng cải thiện giải thuật để giảm thiểu
sự đụng độ đó. Hàm băm thường được dùng trong bảng băm nhằm giảm chi phí
tính toán khi tìm một khối dữ liệu trong một tập hợp (nhờ việc so sánh các giá
trị băm nhanh hơn việc so sánh những khối dữ liệu có kích thước lớn)
Giá trị của hàm băm là duy nhất, và không thể suy ngược lại được nội
dung thông điệp từ giá trị băm này.
Ví dụ minh họa về hàm băm (trích từ
You must be registered for see links
)Hình 1.1 Minh họa về hàm băm
1.1.2. Đặc tính của hàm băm
Hàm băm h là hàm băm một chiều (one-way hash) với các đặc tính sau:
Với thông điệp đầu vào x thu được bản băm z = h(x) là duy nhất.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 thay mặt 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
lệ, còn x‟ là giả mạo). Tiếp theo, hắn đưa cho ông A và thuyết phục ông này kí
vào bản tóm lược h(x) để nhận được y. Khi đó (x‟, y) là bức điện giả mạo nhưng
hợp lệ.
Để tránh kiểu tấn công này, hàm h phải thỏa mãn tính không va chạm
mạnh: Hàm băm h là không va chạm mạnh nếu không có khả năng tính toán để
tìm ra hai bức thông điệp x và x’ mà x x’ và h(x) = h(x’).
Tính chất 3: Hàm băm h là hàm một chiều:
Xét một kiểu tấn công như sau: Việc giả mạo các chữ ký trên bản tóm
lược z thường xảy ta với các sơ đồ chữ ký số. Giả sử tên giả mạo tính chữ ký
trên bản tóm lược z, sau đó hắn tìm một bản thông điệp x‟ được tính ngược từ
bản thay mặt z, z = h(x‟). Tên trộm thay thế bản thông điệp x hợp lệ bằng bản
thông điệp x‟ giả mạo, nhưng lại có z = h(x‟). Và hắn ký số trên bản đại diện
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi13
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
cho x‟ bằng đúng chữ ký hợp lệ. Nếu làm được như vậy thì (x‟, y) là bức điện
giả mạo nhưng hợp lệ.
Để tránh được kiểu tấn công này, h cần thỏa mãn tính chất một chiều:
Hàm băm h là một chiều nếu khi cho trước một bản tóm lược thông báo z thì
không thể thực hiện về mặt tính toán để tìm ra thông điệp ban đầu x sao cho h(x)
= z .
1.2. 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ứ 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 hay 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 M1,…, Mk, padding if necessary;
2. Let Mk+1 be encoding of |M|;
3. Let h0 = IV;
4. For i = 1 to k +1 let hi = C (hi-1, Mi);
5. Output hk+1.
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 hay 1024 bit (chiều dài các block message là
512 hay 1024 bit là tùy thuộc vào thuật toán) và giá trị của chaining variable của
vòng trước, ta có mô hình như sau:14
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
Hình 1.2 : Cấu trúc lặp của hàm băm MD
1.2.1 Hàm băm MD4
MD4 (Message-Digest 4) được thiết kế bởi giáo sư Ronald Rivest của đại
học MIT vào năm 1990. Nó thực hiện một hàm băm mật mã để sử dụng trong
kiểm tra tính toàn vẹn của thông điệp. Chiều dài của giá trị băm là 128bit.
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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi15
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
ra bản tóm lược thông điệp có kích thước 160 bit, sử dụng 5 thanh ghi 32 bit.
Năm thuật giải SHA là SHA-1 (trả lại kết quả dài 160 bit), SHA-224 (trả
lại kết quả dài 224 bit), SHA-256 (trả lại kết quả dài 256 bit), SHA-384 (trả lại
kết quả dài 384 bit), và SHA-512 (trả lại kết quả dài 512 bit).
Thuật giải SHA là thuật giải băm mật được phát triển bởi cục an ninh
quốc gia Mĩ (National Security Agency hay NSA) và được xuất bản thành chuẩn
của chính phủ Mĩ bởi viện công nghệ và chuẩn quốc gia Mĩ (National Institute
of Standards and Technology hay NIST). Bốn thuật giải sau thường được gọi
chung là SHA-2.
SHA-1 được sử dụng rộng rãi trong nhiều ứng dụng và giao thức an ninh
khác nhau, bao gồm TLS và SSL, PGP,SSH, S/MIME, và IPSec.
Hiện nay, SHA-1 không còn được coi là an toàn bởi đầu năm 2005, ba
nhà mật mã học người Trung Quốc đã phát triển thành công một thuật giải dùng
để 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 SHA-1.
Tuy vậy SHA vẫn được sử dụng phổ biến, đặc biệt là SHA-2, chưa có
phát minh nào tìm ra tính không an toàn của nó.16
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
1.3 Ứng dụng của hàm băm
1.3.1 Bảo vệ mật khẩu
Hầu hết các ứng dụng phần mềm ngày nay, dù trên máy đơn hay trên web
đều có chứng thực người sử dụng. Nghĩa là để sử dụng ứng dụng, người sử dụng
phải qua một cơ chế chứng thực tên người dùng và mật khẩu, và từ đó được
cung cấp các quyền sử dụng phần mềm khác nhau. Do đó vấn đề bảo mật mật
khẩu là vấn đề quan trọng đối với mọi phần mềm. Mật khẩu người sử dụng
thường gồm các chữ cái thường và hoa, cộng thêm các chữ số. Giả sử mật khẩu
được lưu trữ dưới dạng thường, không mã hóa, tại một nơi nào đó trên máy tính
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, hay là người quản
trị administrator, hay là hacker, có thể mở được file dữ liệu hay 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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi17
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
Hình 1.3. Cơ chế hoạt động của lưu trữ mật khẩu dùng hàm băm
1.3.2 Đấu giá trực tuyến
Phương pháp lưu trữ mật khẩu bằng giá trị Hash cũng được áp dụng
tương tự cho việc đấu giá trực tuyến bằng hình thức đấu giá bí mật. Giả sử Bắc,
Nam và Đông cùng tham gia đấu giá, họ sẽ cung cấp mức giá của mình cho
trọng tài. Các mức giá này được giữ bí mật cho đến khi cả ba đều nộp xong. Nếu
ai là người đưa ra mức giá cao nhất thì thắng thầu. Điểm quan trọng của phương
pháp đấu giá này là giá của Bắc, Nam, và Đông phải được giữ bí mật trước khi
công bố. Giả sử mức giá của Bắc là 100, mức giá của Nam là 110, nếu Đông
thông đồng với trọng tài và biết được giá của Bắc và Nam, Đông có thể đưa ra
mức giá 111 và thắng thầu.Có thể tránh những hình thức lừa đảo như vậy bằng
cách sử dụng hàm băm. Từ mức giá bỏ thầu, Bắc và Nam sẽ tính các giá trị băm
tương ứng và chỉ cung cấp cho trọng tài các giá trị băm này. Vì hàm băm là một
chiều, nếu trọng tài và Đông bắt tay nhau thì cũng không thể biết được giá của
Bắc và Nam là bao nhiêu. Đến khi công bố, Bắc, Nam và Đông sẽ đưa ra mức
giá của mình. Trọng tài sẽ tính các giá trị băm tương ứng và so sánh với các giá
trị băm đã nộp để bảo đảm rằng mức giá mà Bắc, Nam và Đông là đúng với ý
định ban đầu của họ. Vì tính chống trùng của hàm băm nên Bắc, Nam và Đông
không thể thay đổi giá so với ý định ban đầu.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 (hay SHA) của file X mà server đã tính sẵn và cung cấp trên trang web là
HX (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 ( hay SHA) HY cho file Y. Như vậy
nếu HX = HY 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
gửi và người nhận trong mã chứng thực thông điệp MAC sẽ gặp phải vấn đề
tính không từ chối tương tự như mã hóa đối xứng. Dùng hàm băm và mã hóa
khóa công khai khắc phục được vấn đề này. Trước tiên xét một mô hình đơn
giản được thể hiện ở hình 1.5
Chƣơng 3: ĐỘ AN TOÀN CỦA THUẬT TOÁN MD5
Đặt vấn đề:
MD5 đã từng được coi là chuẩn Internet, được ứng dụng rộng rãi trong
nhiều lĩnh vực bởi tính không giải ngược của nó và độ dài đầu ra là 128 bit được
tính toán là đủ an toàn cho một thuật toán băm.
Nhưng ngay từ năm 1996, người ta đã tìm thấy lỗ hổng của nó tuy là
không rõ ràng lắm. Đến năm 2005, Xiaoyun Wang cùng cộng sự đã biểu diễn
việc xây dựng hai giấy phép X.509 với các khóa công cộng khác nhau cho cùng
bảng băm MD5. Việc tìm thấy xung đột này sẽ là cơ sở khiến kẻ giả mạo tạo ra
một thông điệp khác có cùng mã MD5 với thông điệp cần kiểm tra. Nhưng theo
tính toán độ phức tạp để tìm ra 2 thông điệp có cùng mã băm MD5 là khoảng 264
bước tính; và độ phức tạp để tìm một thông điệp có cùng mã băm MD5 với
thông điệp đã đánh giá là 2128 bước tính.
Ngày nay MD5 vẫn được dùng rộng rãi để lưu trữ mật khẩu bởi thuật toán
số hóa thông điệp MD5 là khá đơn giản để thực hiện. Nhiều ngôn ngữ lập trình
còn cung cấp thư viện hàm MD5 có sẵn nên để tạo giá trị mã MD5 đúng chuẩn
là dễ dàng. Việc tấn công MD5 bằng cách tìm ra mật khẩu khi biết mã băm của
nó chỉ có thể thực hiện bằng nguyên lý vét cạn mà theo tính toán thì việc làm đó
tốn rất nhiều thời gian. Nhưng với công nghệ hiện đại và khả năng tính toán cao
của các phần cứng cùng phần mềm chuyên dụng đã tăng tốc độ dò tìm mật khẩu
lên rất nhiều.
Để đánh giá độ an toàn của thuật toán băm MD5, tác giả tiến hành tìm
hiểu tính an toàn của hàm băm đối với hiện tượng đụng độ, rồi đi sâu vào tìm
hiểu các kỹ thuật tấn công hàm băm MD5 trong việc khôi phục mật khẩu.
3.1 Tính an toàn của hàm băm MD5 đối với hiện tƣợng đụng độ
Hàm băm được xem là an toàn đối với hiện tượng đụng độ khi rất khó tìm
được hai thông điệp có cùng giá trị băm.
Nhận xét: Trong một tập hợp mà các phần tử mang một trong N giá trị
cho trước với xác suất bằng nhau, chúng ta cần khoảng N phép thử ngẫu nhiên
để tìm ra một cặp phần tử có cùng giá trị.
Như vậy, phương pháp hàm băm được xem là an toàn đối với hiện tượng đụng
độ nếu chưa có phương pháp tấn công nào có thể tìm ra cặp thông điệp có cùng
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi31
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
giá trị hàm băm với số lượng tính toán ít hơn đáng kể so với ngưỡng 2n/2, với n
là kích thước (tính bằng bit) của giá trị băm.
Phương pháp tấn công dựa vào đụng độ:
• Tìm ra 2 thông điệp có nội dung khác nhau nhưng cùng giá trị băm.
• Ký trên một thông điệp, sau đó, người ký sẽ không thừa nhận đây là chữ
ký của mình mà nói rằng mình đã ký trên một thông điệp khác. Như vậy, cần
phải chọn 2 thông điệp “đụng độ” với nhau trước khi ký.
Hàm băm MD5 đã được coi là không an toàn đối với hiện tượng đụng độ
khi một loạt các công bố từ năm 1996 đến năm 2005 chỉ ra những xung đột
MD5 được tìm thấy trong vài giờ thậm chí vài phút trên máy tính xách tay.
Một ví dụ về xung đột hàm băm MD5:
Hình 3.1 Ví dụ xung đột hàm băm MD5
Tuy nhiên trong ứng dụng download file để tìm một tập tin có cùng mã
MD5 với tập tin của nhà cung cấp lại là một việc có độ phức tạp tăng lên gấp
nhiều lần so với việc tìm ra hai thông điệp bất kỳ có cùng mã MD5.
Trong ứng dụng chữ ký số, để tìm ra hai thông điệp có cấu trúc tương tự
nhau (ví dụ như hai bản hợp đồng) có cùng mã MD5 nhằm mục đích giả mạo
hay từ chối trách nhiệm lại là một việc dường như không thể làm được.32
Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5
Do vậy tùy vào từng mục đích sử dụng hàm băm MD5 trong những ứng
công cụ thể, hàm băm MD5 vẫn đảm bảo được độ an toàn đối với hiện tượng
đụng độ.
3.2 Tính an toàn của hàm băm MD5 đối với tính một chiều.
Hàm băm được xem là hàm một chiều khi cho trước giá trị băm, không
thể tái tạo lại thông điệp ban đầu. Như vậy, trong trường hợp lý tưởng, cần
thực hiện hàm băm cho khoảng 2n thông điệp để tìm ra được thông điệp tương
ứng với một giá trị băm. Nếu tìm ra được một phương pháp tấn công cho phép
xác định được thông điệp tương ứng với một giá trị băm cho trước thì thuật toán
băm sẽ không còn an toàn nữa.
Ta xét tính an toàn của hàm băm MD5:
Giả sử cho trước một giá trị băm MD5 là h(x), hãy tính khả năng tìm ra
thông điệp x khi không biết bất kỳ dữ kiện gì ngoài mã băm h(x). Đến nay chưa
có một phương pháp nào có thể tìm ra x khi biết h(x) bằng cách sử dụng thuật
toán. Cách duy nhất là người ta sẽ duyệt qua tất cả các khả năng có thể có của x
rồi tính giá trị băm h(x), nếu nó trùng với giá trị băm ban đầu thì x chính là
thông điệp cần tìm.
Độ phức tạp ở đây là không gian chứa thông điệp x quá lớn. Giả sử x nằm
trong tập các ký tự có thể in ra được (95 ký tự) thì số các phương án x cần duyệt
là: 951 +952 +953+954+….+9595 ≈ 7x10187
Với máy tính có tốc độ xử lý 1 phép tính / 1micro giây thì phải mất
khoảng 10174 năm, điều đó là không khả thi. Ngay cả với một siêu máy tính có
tốc độ xử lý 1 nghìn tỷ phép tính / giây thì cũng phải mất 1019 năm.
Trên thực tế chẳng có ứng dụng bảo mật nào đi tìm một thông điệp khi
biết giá trị băm của nó mà không có các dữ kiện liên quan. Ví dụ như trong ứng
dụng bảo vệ mật khẩu của hàm băm MD5, việc tìm mật khẩu khi biết giá trị băm
MD5 phải dựa vào căn cứ sau: Mật khẩu là các ký tự thường ( a…z), ký tự hoa
(A…Z), chữ số (0…9) và một số ký tự đặc biệt ( @, _, -, !, $...) và mật khẩu
thường có độ dài tối đa là 15 ký tự. Ngoài ra còn dựa vào thói quen đặt mật khẩu
của người dùng như là các cụm từ có nghĩa như tên email, họ tên, dãy số dễ nhớ,
số điện thoại, ngày tháng năm sinh…
Dựa vào những đặc điểm trên tác giả sẽ đánh giá tính an toàn của MD5
trong ứng công cụ thể, đó là khôi phục mật khẩu khi biết giá trị băm MD5.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Last edited by a moderator: