Đăng ký Đăng nhập
Trang chủ Nghiên cứu độ an toàn của hàm băm md5...

Tài liệu Nghiên cứu độ an toàn của hàm băm md5

.DOC
64
229
144

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN HỮU HOÀNG NGHIÊN CỨU ĐỘ AN TOÀN CỦA HÀM BĂM MD5 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2013 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN HỮU HOÀNG NGHIÊN CỨU ĐỘ AN TOÀN CỦA HÀM BĂM MD5 Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Hồ Văn Canh Thái Nguyên - 2013 i MỤC LỤC MỞ ĐẦU..........................................................................................................1 CHƯƠNG 1 LÝ THUYẾT VỀ HÀM BĂM..................................................2 1.1. Định nghĩa hàm băm.............................................................................2 1.2. Các tính chất của hàm băm..................................................................3 1.3. Xung đột băm.........................................................................................3 1.4. Ứng dụng................................................................................................4 1.5. Một số hàm băm phổ biến.....................................................................4 1.5.1. Hàm băm MD4..................................................................................6 1.5.2. Hàm băm SHA-1...............................................................................6 1.5.3. Hàm băm SHA-256...........................................................................8 1.5.4. Hàm băm SHA-384, SHA-512........................................................10 CHƯƠNG 2 HÀM BĂM MD5.....................................................................15 2.1. Giới thiệu..............................................................................................15 2.2. Khái niệm..............................................................................................15 2.3. Ứng dụng..............................................................................................16 2.4. Thuật giải..............................................................................................16 2.5. Sự khác nhau MD4 và MD5................................................................24 CHƯƠNG 3 ĐÁNH GIÁ ĐỘ AN TOÀN MD5 DỰA TRÊN THỬ NGHIỆM TẤN CÔNG.................................................................................25 3.1. Tấn công hàm băm..............................................................................25 3.2. Các phương pháp tấn công hàm băm phổ biến................................25 3.2.1. Tấn công dựa trên lý thuyết ngày sinh............................................25 3.2.2. Tấn công mở rộng chiều dài trên MD5 (Length-Extension Attack)27 3.2.3. Tấn công thuật toán.........................................................................29 3.2.4. Tấn công theo nguyên lý vét cạn.....................................................36 ii 3.3. Đánh giá độ an toàn MD5 dựa trên việc sử dụng các bô ô xử lý đồ họa GPU để tính toán khôi phục mâ ôt khẩu................................................36 3.3.1. Những ưu điểm của GPU so với CPU.............................................37 3.3.2. Sử dụng Cluster GPU tính toán khôi phục mâ ât khẩu MD5.............39 3.3.3. Kết luận về độ an toàn MD5............................................................48 KẾT LUẬN....................................................................................................52 TÀI LIỆU THAM KHẢO...............................................................................53 iii LỜI CẢM ƠN Đầu tiên, tôi xin gửi lời cảm ơn chân thành và sắc nhất tới Tiến sỹ Hồ Văn Canh, thầy đã tận tình chỉ bảo và giúp đỡ tôi trong suốt quá trình làm luận văn. Bên cạnh những kiến thức tôi còn học hỏi được ở thầy tinh thần làm việc khoa học và nghiêm túc. Tôi xin chân thành cám ơn tới Khoa CNTT Trường Đại học Công nghệ thông tin và Truyền thông, các thầy cô đã giúp đỡ và tận tình truyền đạt các kiến thức cho tôi trong suốt quá trình học tập và nghiên cứu. Tôi xin cảm ơn ban chủ nhiệm khoa và các cán bộ đã tạo điều kiện tốt nhất cho chúng tôi trong quá trình học tập và hoàn thành luận văn của mình. Tôi xin bày tỏ lòng biết ơn tới gia đình, bạn bè, đồng nghiệp và những người thân đã động viên khích lệ tinh thần và giúp đỡ tôi hoàn thành luận văn này. iv LỜI CAM ĐOAN Tôi xin cam đoan, toàn bộ nội dung liên quan tới đề tài được trình bày trong luận văn là bản thân tôi tự tìm hiểu và nghiên cứu, dưới sự hướng dẫn của Thầy giáo TS. Hồ Văn Canh. Các tài liệu, số liệu tham khảo được trích dẫn đầy đủ nguồn gốc. Tôi xin chịu trách nhiệm trước pháp luật lời cam đoan của mình. Học viên thực hiện Nguyễn Hữu Hoàng v THUẬT NGỮ VIẾT TẮT Số thứ tự Thuật Ngữ Tên Đầy Đủ 1 MAC Message Authentication Code 2 HMAC Keyed-Hash Message Authentication Code 3 opad Outer pad 4 ipad Inner pad 5 SHA Secure Hash Algorithm 6 MD Merkle-Damgård 7 TLS Transport Layer Security 8 CA Certification Authority 9 IPSec Internet Protocol Security 10 GPU Graphic Proccessing Unit 11 SM Streaming Multiprocessor Ý NGHĨA CÁC KÝ HIỆU Số thứ tự Ký hiệu Ý nghĩa vi 1  Phép toán XOR 2 <<< Phép dịch bít vòng 3 || Phép ghép chuỗi 4 Phép OR 5   6 ⌐ Phép phủ định 7 + Phép cộng module 2 32 8 ROTR n (x) Dịch xoay vòng x sang bên phải n bít 9 SHR n (x) Dịch bít của số x sang bên phải n bít Phép AND DANH MỤC HÌNH VẼ Hình 1.2. Cấu trúc lặp của hàm băm MD.........................................................5 Hình 2.1. Thuật toán mô tả MD5/SHA-1........................................................19 Hình 3.1. Cấu trúc lặp Merkle-Damgård (sao chép từ Wikipedia)...............28 Hình 3. 2. Tấn công mở rộng chiều dài..........................................................28 vii Hình 3. 3. Biểu đồ so sánh sự phát triển của GPU và CPU..........................38 Hình 3.4. So sánh số nhân của GPU và CPU.................................................38 Hình 3.5. Mô tả chiến lược kiểm tra mật khẩu song song..............................40 Hình 3. 6. Chia mật khẩu vào các nhóm.........................................................41 Hình 3.7. Tạo giá trị băm cho mật khẩu........................................................49 Hình 3.8. Add giá trị băm của mật khẩu vào phần mềm.................................50 Hình 3.9. Quá trình tạo và kiểm tra mật khẩu................................................50 Hình 3.10. Tìm kiếm mật khẩu thành công.....................................................51 viii DANH MỤC BẢNG BIỂU Bảng 1. 1.Bảng so sánh các loại hàm băm.....................................................13 Bảng 3.1. Kiểu tấn công các hàm băm............................................................27 Bảng 3. 2. Modify multiple message...............................................................35 Bảng 3.16. So sánh tốc độ của Tạo và Kiểm tra các khóa trên CPU / GPU. .47 Bảng 3.17. Thời gian cho Phục hồi mật khẩu trên GPU................................47 1 MỞ ĐẦU Ngày nay, các giao dịch thương mại qua mạng internet trở nên rất phổ biến và do đó cần phải có biện pháp để đảm bảo an toàn cho các giao dịch này. Một trong các biện pháp đó là việc sử dụng hàm băm (hash function) trong công tác bảo an. Hàm băm không những đảm bảo được sự toàn vẹn của các giao dịch mà còn có thể đảm bảo sự bí mật về dữ liệu của các bên giao dịch[1][2]. Người ta đã khẳng định rằng: “sự ra đời của các hệ mật mã khóa công khai cùng với các hàm băm là một cuộc cách mạng của kỹ thuật mật mã và được coi như một phương thức mật mã không dùng khóa”[2]. Hàm băm cũng đóng vai trò hết sức quan trọng trong việc ứng dụng chứng chỉ số mà cụ thể nhất là trong chữ kí số. Ngoài ra, hàm băm còn là một công cụ hữu hiệu để bảo vệ các passwords người dùng và bảo vệ dữ liệu có hiệu quả trong các cơ sở dữ liệu phân tán. Hiện nay, hàm băm được sử dụng nhiều ở Việt Nam cũng như trên thế giới là MD5 và họ SHA. Do tầm quan trọng của hàm băm mà hiện nay đã có nhiều công trình nghiên cứu về hàm băm và mức độ an toàn của chúng[3][4][5][6]. Vậy, một câu hỏi được đặt ra hiện nay là: Mức độ an toàn của các hàm băm đến đâu trong thực tế khi mà công nghệ tính toán ngày càng phát triển mạnh mẽ như hiện nay? Trong Luận văn này tôi trình bày mô tâ cách tiếp câ ân mới đó là viê âc sử dụng các bô â xử lý đồ họa đa lõi hiê ân đại để tính toàn khôi phục thông điệp MD5[14][16][17]. 2 Chương 1 LÝ THUYẾT VỀ HÀM BĂM A. Định nghĩa hàm băm Hàm băm H nhận đầu vào là chuỗi dữ liệu M có chiều dài bất kỳ và tạo ra chuỗi đầu ra (hay còn gọi là "hash value") có chiều dài cố định theo công thức sau. h = H (M). Ví dụ minh họa về hàm băm. Hình 1.1. Minh họa về hàm băm - h được gọi là giá trị đầu ra của hàm băm, có chiều dài cố định (h còn gọi là message digest hoặc hash value). - M là bức thông điệp có chiều dài bất kỳ hữu hạn (chiều dài của M không vượt quá 2 64 bít, nếu chiều dài của M vượt quá 2 64 bít thì chỉ có 2 64 bít đầu được sử lý, còn tất cả các bít được bỏ qua trong quá trình tính toán của hàm băm). 3 - Hàm băm được sử dụng trong việc mã hóa password, chữ ký số, giao dịch điện tử, kiểm tra sự toàn vẹn của một file, v.v. Hàm băm được sử dụng phổ biến nhất là hàm băm một chiều (one-way) MD5 và SHA-*[9][12] 1.1. Các tính chất của hàm băm Tính chất 1: Hàm băm H là không va chạm yếu. Hàm băm H phải có phi xung đột yếu (weak-collision) cao, điều đó có nghĩa là cho trước M ta khó có thể tìm được bức thông điệp M’  M sao cho H(M) = H(M’) . Tính chất 2: Hàm băm H là không va chạm mạnh. Hàm băm H có tính phi đụng độ cao (strong collision), điều đó có nghĩa là ta khó có thể tìm được cặp thông điệp (M, M’) M’  M sao cho H(M)=H(M’). Tính chất 3: Hàm băm H là hàm một chiều. Hàm băm H có tính một chiều (one-way) có nghĩa là cho trước M việc tính H(M) được thực hiện nhanh chóng nhưng nếu cho trước giá trị H(M) thì sẽ khó có thể tìm được giá trị M[9]. B. Xung đột băm Có nghĩa là hai thông điệp khác nhau khi băm thì chúng tạo ra cùng giá trị băm. Gọi M, M’ là hai thông điệp sao cho M  M’, H là hàm băm, xung đột băm xảy ra khi H(M)=H(M’). Về mặt lý thuyết thì hoàn toàn ta có thể tìm được hai thông điệp khác nhau mà chúng cho ra cùng một giá trị băm, nhưng thực tế việc này làm rất khó khăn, và ngay cả khi chúng ta tạo được hai thông điệp với nội dung khác nhau nhưng chúng cùng tạo ra giá trị băm, nhưng nội dung đó không có ý nghĩa với con người có nghĩa là nếu cho trước một thông điệp ta hoàn toàn có thể tìm được thông điệp thứ hai khác tạo ra cùng giá trị băm nhưng chúng ta khó có thể điều khiển được nội dung thông điệp này sao cho nó có ý nghĩa với con người, do vậy có thể kết luận các hàm băm hiện tại vẫn đủ an toàn[9]. 4 1.2. Ứng dụng Hàm băm được sử dụng rộng rãi trong thế giới phần mềm để đảm bảo rằng tập tin tải về không bị hỏng. Người sử dụng có thể so sánh giữa thông số kiểm tra phần mềm bằng Hàm băm được công bố với thông số kiểm tra phần mềm tải về bằng Hàm băm. Hệ điều hành Unix sử dụng MD5 để kiểm tra các gói mà nó phân phối, trong khi hệ điều hành Windows sử dụng phần mềm của hãng thứ ba. Hàm băm cũng được dùng để mã hóa mật khẩu. Mục đích của việc mã hóa này 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ó có thể 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). Tạo mã chứng thực thông điệp ứng dụng trong chứng chỉ số, sự ra đời của các hệ mật mã khóa công khai cùng với các hàm băm là một cuộc cách mạng của kỹ thuật mật mã. Chính vì vậy nhiều người nói rằng hàm băm là một phương thức mật mã không dùng khóa. Một ứng dụng quan trọng không thể thiếu đối với hàm băm là ứng dụng trong chữ ký số[2][12][13]. C. 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ứ 2 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 bit). Ở thời điểm bắt đầu các “chaining variable” có giá trị khởi tạo (giá trị 5 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 [1][2][4][5]. Thuật toán chung cho các hàm băm này như sau. 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 bít (chiều dài các block message là 512 hay 1024 bít là tùy thuộc vào thuật toán) và giá trị của chainging variable của vòng trước, ta có thể mô hình như sau: Hình 1.1. Cấu trúc lặp của hàm băm MD 1. Hàm băm MD4 MD4 (Message-Digest thuật toán 4) là một thuật toán (thứ tư trong loạt a) được thiết kế bởi Giáo sư Ronald Rivest của MIT vào năm 1990. Nó thực 6 hiện một hàm băm mật mã để sử dụng trong kiểm tra tính toàn vẹn thông điệp. Chiều dài của giá trị băm là 128 bit. 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 [9]. 2. Hàm băm SHA-1 Thuật toán cho hàm băm này nhận đầu vào là bức thông điệp có chiều dài hữu hạn bất kỳ cho đầu ra là chuỗi có chiều dài cố định, hàm băm SHA-1 có chiều dài đầu ra là 160 bit. - Việc đệm được thực hiện tương tự việc đệm trong thuật toán cho hàm băm MD5. - Chia bức thông điệp thành các khối 512 bit. - Thực hiện việc khởi tạo cho các biến chaining variable như sau: H (00 ) =0x67452301 H 1( 0 ) =0xefcdab89 7 H (20 ) =0x98badcfe H 3( 0 ) =0x10325476 H (40 ) =0xc3d2e1f0. - Thực hiện sử lý các khối. Xây dựng hàm biến đổi khối đầu vào theo công thức sau. - Khởi tạo các biến làm việc như sau ở vòng thứ i-1. a=H (0i 1) b=H 1( i 1) c=H (2i 1) d=H 3( i 1) e=H (4i 1) - Thực hiện việc biến đổi như sau. For (t=0; t<=79; t++) { T = ROLT 5 (a) + ft (b, c, d) + e + K t +W t e=d d=c c= ROLT 30 (b) b=a a=T } - Tính toán chuỗi đầu ra như sau. H (0i ) = a + H (0i 1) 8 H 1( i ) = b + H 1( i 1) H (2i ) = c + H (2i 1) H 3( i ) = d + H 3( i 1) H (4i ) = e + H (4i 1) 3. Hàm băm SHA-256 Thuật toán này nhận chiều vào là bức thông điệp có chiều dài bất kì hữu hạn cho đầu ra là chuỗi có chiều dài cố định là 256 bít. - Việc đệm được thực hiện tương tự việc đệm trong thuật toán cho hàm băm MD5. - Chia bức thông điệp thành các khối 512 bit. - Thực hiện việc khởi tạo cho các biến chaining variable như sau: H (00 ) =0x6a09e667 H 1( 0 ) =0xbb67ae85 H (20 ) =0x3c6ef372 H 3( 0 ) =0xa54ff53a H (40 ) =0x510e527f. H 5( 0 ) =0x9b05688c H (60 ) =0x1f83d9ab H (70 ) =0x5be0cd19 Thực hiện sử lý các khối. - Xây dựng hàm biến đổi khối đầu vào theo công thức sau - Khởi tạo các biến làm việc như sau . a=H (0i 1) b=H 1( i 1) 9 c=H (2i 1) d=H 3( i 1) e=H (4i 1) f=H 5( i 1) g=H (6i 1) h=H (7i 1) - Thực hiện việc biến đổi như sau For (i=0; i<=63; i++) { { 256}  (e) + Ch (e, f, g) +K T 1 = h+ 1 T2 = { 256}  (a ) +Maj (a, b, c) 0 h=g g=f f=e e=d + T 1 d=c c=b b=a a= T 1 + T 2 } - Tính toán kết quả cuối cùng như sau. H (0i ) = a + H (0i 1) H 1( i ) = b + H 1( i 1) H (2i ) = c + H (2i 1) H 3( i ) = d + H 3( i 1) { 256} t +W t 10 H (4i ) = e + H (4i 1) H 5( i ) = f + H 5( i 1) H (6i ) = g + H (6i 1) H (7i ) = e + H (7i 1) Trong đó: Ch(x, y, z) = (x ^ y)  (⌐x  z) Maj(x, y, z) = x ^ y)  (y ^ z)  (z ^ x). { 256}  ( x) = ROTR 2 (x)  ROTR 13 (x)  ROTR 22 (x) 0 { 256}  ( x) = ROTR 6 (x)  ROTR 11 (x)  ROTR 25 (x) 1  {0256} = ROTR 7 (x)  ROTR 18 (x)  SHR 3 (x)  1{256} = ROTR 17 (x)  ROTR 19 (x)  SHR 10 (x) 4. Hàm băm SHA-384, SHA-512 Các thuật toán này nhận đầu vào là bức thông điệp có chiều dài bất kỳ hữu hạn cho đầu ra (message digest) là chuỗi có chiều dài cố định (SHA-384, SHA-512 là 1024 bit). - Việc đệm được thực hiện tương tự việc đệm trong thuật toán cho hàm băm MD5. - Chia bức thông điệp thành các khối 1024 bit. - Thực hiện việc khởi tạo cho các biến chaining variable như sau: Với hàm băm SHA-384 các giá trị chaining variable được khởi tạo như sau: H (00 ) =0xcbbb9d5dc1059ed8 H 1( 0 ) =0x629a292a367cd507 H (20 ) =0x9159015a3070dd17
- Xem thêm -

Tài liệu liên quan