Đề tài Mã hóa MD5

Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level Fifth level 5/9/2014 ‹#› Giáo viên hướng dẫn : Mai Văn Hà Nhóm SV thực hiện : Lê Công Tuấn Vũ Trần Văn Hồi Nguyễn Tấn Vĩnh Hoàng MÃ HÓA MD5 KỸ THUẬT TRUYỀN SỐ LIỆU MESSAGE DIGEST 5 1 MÃ HÓA MD5 – MESSAGE DIGEST 5 N Ộ I D U N G 2 MÃ HÓA MD5 – MESSAGE DIGEST 5 I. Giới thiệu về mã hóa và thuật toán MD5 1. Mã hóa là gì ? Mã hóa là phương pháp để biến thông tin từ định dạng bình thường sang dạng thông tin không thể hiểu được nếu không có phương tiện giải mã. Vậy tại sao chúng ta cần phải mã hóa? Nhu cầu riêng tư, tính bảo mật Toàn vẹn của thông tin Mã hóa cũng là nền tảng của chữ ký điện tử, hệ thống PKI… 3 MÃ HÓA MD5 – MESSAGE DIGEST 5 I. Giới thiệu về mã hóa và thuật toán MD5 2. MD5 là gì ? MD5 giải thuật tiêu hóa tập tin là một chuẩn Internet RFC 1321. Có khả năng băm mã hóa tập tin bất kỳ thành chuỗi HEX 32 ký tự, tương đương 128-bit (mỗi ký tự hex 4-bit x 32 ký tự = 128 bit). Hay cách khác MD5 chính là cách để lấy chăm ký tự (digest, alphabeic, …), được gọi là string nhập vào và cho ra 32 ký tự Hexa. 4 MÃ HÓA MD5 – MESSAGE DIGEST 5 I. Giới thiệu về mã hóa và thuật toán MD5 2. MD5 là gì ? Năm 1991, MD5 được thiết kế bởi Ronald Rivest để thay thế cho hàm băm trước đó, MD4. Vào năm 1996, người ta phát hiện ra lỗ hổng trong MD5, trong khi vẫn chưa biết nó có phải là lỗi nghiêm trọng hay không. Những chuyên gia đã nghĩ đến những giải thuật khác, như SHA-1. Năm 2004 nhiều lỗ hổng bị khám phá nhiều hơn khiến cho việc bảo mật của giải thuật này bị đặt nghi vấn. 5 MÃ HÓA MD5 – MESSAGE DIGEST 5 I. Giới thiệu về mã hóa và thuật toán MD5 3. Đặc điểm MD5 • Việc tính MD đơn giản, có khả năng xác định được file có kích thước nhiều Gb. • Không có khả năng tính ngược, khi tìm ra MD. • Do bản chất ngẫu nhiên của hàm băm và số lượng cực lớn các giá trị hash có thể, nên hầu như không có khả năng hai bản tin phân biệt có cùng giá trị hash. • Giá trị MD phụ thuộc vào bản tin tương ứng. • Một chuổi chỉ có duy nhất một hash. • Giá trị MD phụ thuộc vào tất cả các bit của bản tin tương ứng. 6 MÃ HÓA MD5 – MESSAGE DIGEST 5 I. Giới thiệu về mã hóa và thuật toán MD5 1. Đặc điểm MD5 Ví dụ : love is blue -> 03d4ad6e7fee3f54eb46b5ccde58249c love is Blue -> 82b76f8eeb4a91aa640f9a23016c7b1c 7 MÃ HÓA MD5 – MESSAGE DIGEST 5 II. Ứng dụng 1. Bảo toàn thông tin MD5 được dựng rộng rãi trong các phần mềm trên toàn thế giới để đảm bảo việc truyền tập tin được nguyên vẹn. Các nhà phát triển ứng dụng thường dùng MD5 trong việc cho phép download file. Họ sẽ cho “xuất bản” một tín hiệu MD của file download. Khi chúng ta tải file về , thì file chúng ta vừa download sẽ có một chuỗi MD: Nếu tín hiệu này khớp với tín hiệu các nhà phát triển ứng dụng đã “xuất bản” ở trên. Thì OK, ko có vấn đề. Nếu hai tín hiệu này khác nhau, có thể có trong file download có virut hay tập tin đó đã bị thay đổi. 8 MÃ HÓA MD5 – MESSAGE DIGEST 5 II. Ứng dụng 1. Bảo toàn thông tin 9 MÃ HÓA MD5 – MESSAGE DIGEST 5 II. Ứng dụng 1. Bảo mật Mục đích của việc mã hóa 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ông thể nào 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). 10 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán 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ômg 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 Module, và dịch trái. 11 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán 12 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán CÁC BƯỚC THỰC HIỆN Bước 1: Thêm các bit vào chuổi - Thêm bit ‘1’ vào cuối thông điệp để đánh dấu. - Thêm vào k bit ‘0’ sao cho (b bit + bit 1 + k bit 0)mod 512=448 - 64 bit tiếp theo sẽ được thêm vào biểu thị chiều dài của chuổi bit ban đầu. (B bit + bit ‘1’ + k bit ‘0’ + 64 bit chiều dài) mod 512 = 0 Module 512 Qúa trình thêm bit chuổi 384 bit 13 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán Bước 2: Khởi tạo bộ đệm MD Một bộ đệm 4 word (A,B,C,D) được dựng để tính mã số thông điệp. Ở đây mỗi A,B,C,D là một thanh ghi 32 bit. Những thanh ghi này được khởi tạo theo những giá trị hex sau ( các byte thấp trước ) : word A : 01 23 45 67 word B : 89 ab cd ef word C : fe dc ba 98 word D : 76 54 32 10 14 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán Bước 3: Xử lý thông điệp theo từng khối 16 word Các hàm này nhận đầu vào là 3 word 32 bit và tạo ra một word 32 bit. - Đây là quá trình thực hiện xử lý của 4 hàm F ở trên: Quá trình này sử dụng một bảng có 64 giá trị T[1 .. 64] được tạo ra từ hàm sin. Gọi T[i] là phần tử thứ i của bảng, thì T[i]là phần nguyên của 4294967296*|sin(i)| , i được tính theo radian. 15 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán Bước 3: Xử lý thông điệp theo từng khối 16 word Thực hiện: /* Xử lý mỗi khối 16 word */ For (i = 0 to N/16-1) do /* Copy block i into X. */ For j = 0 to 15 do Set X[j] to M[i*16+j]. end /* of loop on j */ /* Lưu A vào AA, B vào BB, C vào CC, D và DD . Làm buffer */ AA = A BB = B CC = C DD = D 16 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán Bước 3: Xử lý thông điệp theo từng khối 16 word 17 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán Bước 3: Xử lý thông điệp theo từng khối 16 word 18 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán Bước 3: Xử lý thông điệp theo từng khối 16 word 19 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán Bước 3: Xử lý thông điệp theo từng khối 16 word 20 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán Bước 3: Xử lý thông điệp theo từng khối 16 word 21 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán Bước 4: In ra Mã số thông điệp được tạo ra là A,B,C,D. Nghĩa là chúng ta bắt đầu từ byte thấp của A, kết thúc với byte cao của D MÃ GIẢ Mã giả cho giải thuật MD5 như sau. //Chú ý: Tất cả các biến đều là biến không dấu 32 bit và bao phủ mô đun 2^32 khi tính toán var int[64] r, k  //r xác định số dịch chuyển mỗi vòng r[ 0..15] := {7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22} r[16..31] := {5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20} r[32..47] := {4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23} r[48..63] := {6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21}  22 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán //Sử dụng phần nguyên nhị phân của sin của số nguyên làm hằng số: for i from 0 to 63 k[i] := floor(abs(sin(i + 1)) × (2 pow 32))  //Khởi tạo biến: var int h0 := 0x67452301 var int h1 := 0xEFCDAB89 var int h2 := 0x98BADCFE var int h3 := 0x10325476  //Tiền xử lý: append "1" bit to message append "0" bits until message length in bits ≡ 448 (mod 512) append bit (bit, not byte) length of unpadded message as 64-bit little-endian integer to message  //Xử lý mẩu tin trong đoạn 512-bit tiếp theo: for each 512-bit chunk of message break chunk into sixteen 32-bit little-endian words w[i], 0 ≤ i ≤ 15  Bước 4: In ra 23 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán //Khởi tạo giá trị băm cho đoạn này: var int a := h0 var int b := h1 var int c := h2 var int d := h3   //Vòng lặp chính: for i from 0 to 63 if 0 ≤ i ≤ 15 then f := (b and c) or ((not b) and d) g := i else if 16 ≤ i ≤ 31 f := (d and b) or ((not d) and c) g := (5×i + 1) mod 16 else if 32 ≤ i ≤ 47 f := b xor c xor d Bước 4: In ra 24 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán g := (3×i + 5) mod 16 else if 48 ≤ i ≤ 63 f := c xor (b or (not d)) g := (7×i) mod 16 temp := d d := c c := b b := b + leftrotate((a + f + k[i] + w[g]) , r[i]) a := temp  //Thêm bảng băm của đoạn vào kết quả: h0 := h0 + a h1 := h1 + b h2 := h2 + c h3 := h3 + d  Bước 4: In ra 25 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán var int digest := h0 append h1 append h2 append h3 //(expressed as little-endian) //định nghĩa hàm dịch trái leftrotate (x, c) return (x > (32-c)); //Khởi tạo giá trị băm cho đoạn này: var int a := h0 var int b := h1 var int c := h2 var int d := h3   Bước 4: In ra 26 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Thuật toán //Vòng lặp chính: for i from 0 to 63 if 0 ≤ i ≤ 15 then f := (b and c) or ((not b) and d) g := i else if 16 ≤ i ≤ 31 f := (d and b) or ((not d) and c) g := (5×i + 1) mod 16 else if 32 ≤ i ≤ 47 f := b xor c xor d g := (3×i + 5) mod 16 else if 48 ≤ i ≤ 63 f := c xor (b or (not d)) g := (7×i) mod 16 Bước 4: In ra 27 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. So sánh MD4 và MD5 MD4 MD5 - Có 3 vòng biến đổi -Có 4 vòng biến đổi =>Tăng mức an toàn - Sử dụng hằng số chung cho mọi thao tác trong một chu kỳ -Các thao tác trong chu kỳ sử dụng các hằng số ti phân biệt Hàm G ở chu kỳ 2: G(X, Y, Z)=((X ∧ Y)∨(X ∧ Z)∨(Y ∧ Z)) Hàm G ở chu kỳ 2: ((X ∧ Z) ∨ (Y ∧ Z)) => nhằm giảm tính đối xứng Mỗi bước biến đổi trong từng chu kỳ chịu ảnh hưởng kết quả của bước trước => nhằm tăng tốc độ hiệu ứng lan truyền -Mỗi chu kỳ sử dụng bốn hệ số dịch chuyển khác nhau 28 MÃ HÓA MD5 – MESSAGE DIGEST 5 III. Kết luận - Thuật toán số hóa thông điệp MD5 khá đơn giản để thực hiện. - Cung cấp một dạng “vân tay“ hay mã số của thông điệp với độ dài tùy ý. - Người ta cho rằng độ khó để tìm được 2 thông điệp có cùng mã số là khoảng 2^64 bước tính, và độ khó để tìm được một thông điệp với mã số cho trước là 2^128 bước tính. -> Với bất kỳ giá trị x, không thể tính được y ≠ x sao cho H(y) = H(x). -> Không thể tính được một cặp (x, y) sao cho H(x) = H(y). - Do đó MD5 được sử dụng rộng rãi trong các ứng dụng, web, bảo mật, và chứng thực… - Tuy nhiên ở một mức độ nào đó thì md 5 vẫn có thể crack được.   29 MÃ HÓA MD5 – MESSAGE DIGEST 5 30 Cảm ơn tất cả mọi người đã theo dõi!