Báo cáo Kỹ thuật truyền số liệu: Mã hóa MD5

K THU T TRUY N S LI U

Ề Ố Ệ

Ậ

Ỹ

MÃ HÓA MD5

MESSAGE DIGEST 5

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 – MESSAGE DIGEST 5

N Ộ I D U N G

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ì ?

ng pháp đ bi n thông tin t ể ế

đ nh d ng bình ạ ừ ị c n u không ể ể ượ ế

th có ph i mã. Mã hóa là ph ườ ươ ươ ng sang d ng thông tin không th hi u đ ạ ng ti n gi ả ệ

• Nhu c u riêng t ầ

V y t ậ ạ i sao chúng ta c n ph i mã hóa? ầ ả

• Toàn v n c a thông tin ẹ ủ

ư , tính b o m t ậ ả

Mã hóa cũng là n n t ng c a ch ữ ủ

ký đi n t ề ả , h th ng PKI… ệ ử ệ ố

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 ấ ỗ ng 128-bit ký t , t ự ươ (m i ký t ự ự ỗ = 128 bit).

ng đ hex 4-bit x 32 ký t

• Hay cách khác MD5 chính là cách đ l y chăm ký t ự c ượ (digest, alphabeic, …), đ g i là string nh p vào và cho ậ ọ Hexa. ra 32 ký t

ể ấ

ự

MÃ HÓA MD5 – MESSAGE DIGEST 5

I. Gi

i thi u v mã hóa và thu t toán MD5

ớ

ệ ề

ậ

• Năm 1991, MD5 đ

2. MD5 là gì ?

t k b i Ronald Rivest đ thay th cho ế ế ở ể ế

hàm băm tr c thi ượ c đó, MD4. ướ

• Vào năm 1996, ng ư

h ng trong MD5, trong khi ườ

ế ẫ i ta phát hi n ra l ỗ ỗ ổ ọ ữ ả

v n ch a bi chuyên gia đã nghĩ đ n nh ng gi ệ i nghiêm tr ng hay không. Nh ng i thu t khác, nh SHA-1. t nó có ph i là l ế ữ ư ả ậ

• Năm 2004 nhi u l ề ỗ ổ ậ

h ng b khám phá nhi u h n khi n cho vi c b o ệ ả ế ề ơ

ị i thu t này b đ t nghi v n. ị ặ m t c a gi ậ ủ ấ ả

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 ể

ặ

c file ả ị ượ

• Vi c tính MD đ n gi n, có kh năng xác đ nh đ ệ có kích th ơ ả c nhi u Gb. ề ướ

c, khi tìm ra MD. • Không có kh năng tính ng ả ượ

ả ố ượ ủ ự ẫ

ư ầ

ng c c • Do b n ch t ng u nhiên c a hàm băm và s l ấ 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. ấ ộ ổ ộ ỉ

t c các bit ộ ấ ả

• Giá tr MD ph thu c vào t ụ ị ng ng. c a b n tin t ứ ươ ả ủ

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

MÃ HÓA MD5 – MESSAGE DIGEST 5

II. ng d ng

Ứ

ụ

1. B o toàn thông tin ả

c d ng r ng rãi trong các ph n m m trên toàn th gi i đ ế ớ ể ự

• MD5 đ ả

• Các nhà phát tri n ng d ng th

đ m b o vi c truy n t p tin đ ầ c nguyên v n. ượ ả ệ ượ ộ ề ậ ề ẹ

ng dùng MD5 trong vi c cho phép ệ ụ

ộ ể ứ ọ ẽ ủ ệ

i file v , thì file chúng ta v a download s có m t ả ừ ẽ ề ộ

ể ứ ụ ệ ế ớ ớ

ấ ả ở ề

ế

ườ 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 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. ậ ổ ị

MÃ HÓA MD5 – MESSAGE DIGEST 5

II. ng d ng

Ứ

ụ

1. B o toàn thông tin ả

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 ạ đo n mã đó không th t ạ ể ừ i m t kh u. nào l n tr l ẩ ầ i mã Có nghĩa là vi c gi ả ệ 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).

MÃ HÓA MD5 – MESSAGE DIGEST 5

III. Thu t toán

ậ

ậ ạ ộ ạ

• Gi 4 t h ng s c đ nh. ằ

ượ c kh i t o v i nh ng i thu t MD5 chính ho t đ ng trên tr ng thái 128-bit, đ 32-bit, v i ký hi u A, B, C và D. Chúng đ ở ạ c chia thà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.

ố ụ ố ự ỗ

ế ộ ị

MÃ HÓA MD5 – MESSAGE DIGEST 5

III. Thu t toán

ậ

MÃ HÓA MD5 – MESSAGE DIGEST 5

III. Thu t toán

ậ

CÁC B C TH C HI N ƯỚ Ự Ệ

c 1ướ : Thêm các bit vào

ố

ệ ể

Module 512

c thêm ẽ ượ ủ ể

ổ

B 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 đ ế 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 ề

Qúa trình thêm bit chu i 384 bit ổ

MÃ HÓA MD5 – MESSAGE DIGEST 5

III. Thu t toán

ậ

B c 2ướ : Kh i t o b đ m MD ở ạ ộ ệ

ộ ộ ệ ể

đây c d ng đ tính mã s thông đi p. ệ Ở c kh i t o theo ở ạ ượ

M t b đ m 4 word (A,B,C,D) đ ố m i A,B,C,D là m t thanh ghi 32 bit. Nh ng thanh ghi này đ ộ 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

MÃ HÓA MD5 – MESSAGE DIGEST 5

III. Thu t toán

ậ

ử c 3ướ : X lý thông đi p theo t ng kh i 16 word ố ệ

ạ ầ ậ ộ

B ừ 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.

trên: ủ ở

c t o ra t hàm ừ

ượ ạ ủ ầ ọ

- Đây là quá trình th c hi n x lý c a 4 hàm F ệ ử ự Quá trình này s d ng m t b ng có 64 giá tr T[1 .. 64] đ ử ụ ị ộ ả sin. G i T[i] là ph n t ầ ử ứ ủ ả 4294967296*|sin(i)| , i đ c tính theo radian. th i c a b ng, thì T[i]là ph n nguyên c a ượ

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

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 ử ừ ố ệ

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 ử ừ ố ệ

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 ử ừ ố ệ

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 ừ ử ố ệ

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 ử ừ ố ệ

MÃ HÓA MD5 – MESSAGE DIGEST 5

III. Thu t toán

ậ

B c 4ướ : In ra

ệ

byte th p c a A, k t thúc v i byte cao c a D Mã s thông đi p đ ố b t đ u t ấ ắ ầ ừ c t o ra là A,B,C,D. Nghĩa là chúng ta ượ ạ ủ ủ ế ớ

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}

MÃ HÓA MD5 – MESSAGE DIGEST 5

III. Thu t toán

ậ

B c 4ướ : In ra

ị ằ ầ ử ụ ủ ố

ở ạ

ử ẩ

//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 23

MÃ HÓA MD5 – MESSAGE DIGEST 5

III. Thu t toán

ậ

B c 4ướ : In ra

ạ ở ạ

//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 24

MÃ HÓA MD5 – MESSAGE DIGEST 5

III. Thu t toán

ậ

B c 4ướ : In ra

ả ế ạ ả

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

MÃ HÓA MD5 – MESSAGE DIGEST 5

III. Thu t toán

ậ

B c 4ướ : In ra

ị

ở ạ

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 << c) or (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

MÃ HÓA MD5 – MESSAGE DIGEST 5

III. Thu t toán

ậ

B c 4ướ : In ra

//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

MÃ HÓA MD5 – MESSAGE DIGEST 5

III. So sánh MD4 và MD5

MD4 MD5

-Có 4 vòng bi n đ i =>Tăng m c an toàn - Có 3 vòng bi n đ i ổ ế ứ ế ổ

ử ụ ọ ử ụ

- 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 t h ng s ti phân bi ệ ằ ố

chu kỳ 2: ((X (Y Z)) ở ∧ ở ∧

Hàm G (X Y) (Y chu kỳ 2: G(X, Y, Z)=((X Z)) Z) ∨ ∧ ∨ ∧ Hàm G Z) ∧ ∨ => nh m gi m tính đ i x ng ằ ố ứ ả

c bi n đ i trong t ng chu kỳ

c tr ừ ả ủ ướ ổ ế

M i b ỗ ướ ế c ch u nh h ng k t qu c a b ướ ị ả ưở => 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 ể

MÃ HÓA MD5 – MESSAGE DIGEST 5

III. K t lu n ế

ậ

ậ ệ ả

ể ự ệ

ố ộ ạ ằ ể ệ ố

ơ ố ủ c 2 thông đi p có cùng mã s là kho ng ả c là c m t thông đi p v i mã s cho tr ấ i ta cho r ng đ khó đ tìm đ ộ c tính, và đ khó đ tìm đ ộ ướ ướ ượ ể ệ ố ộ ớ

- 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 ượ ườ 2^64 b 2^128 b c tính. ướ

c y ≠ x sao cho H(y) = H(x). ớ ấ ể

ộ ặ ể

-> V i b t kỳ giá tr x, không th tính đ ị -> Không th tính đ ượ ượ ử ụ ượ c m t c p (x, y) sao cho H(x) = H(y). c s d ng r ng rãi trong các ng d ng, web, b o m t, và ả ứ ụ ậ ộ

ứ ự

m t m c đ nào đó thì md 5 v n có th crack đ c. ở ộ ứ ộ ể ẫ ượ