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 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Chƣơng 1: LÝ THUYẾT VỀ HÀM BĂM 1.1 Tổng quan về hàm băm 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. 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ừ http://vi.1 Minh họa về hàm băm 1.
Đặ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. Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 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). 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 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 đại diện 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 Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 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. 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 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. Break M into m – bit block M1,…, Mk, padding if necessary; 2.
Let Mk+1 be encoding of |M|; 3. For i = 1 to k +1 let hi = C (hi-1, Mi); 5. 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 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: Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 : Cấu trúc lặp của hàm băm MD 1.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. Tìm hiểu và phân tích đánh giá độ an toàn của thuật toán MD5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 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. 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).