Tài liệu Nghiên cứu về hàm băm trên cơ sở mạng hoán vị thay thế điều khiển được và ứng dụng trong mã hóa xác thực văn bản

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG ––––––––––––––––– ĐỖ THU HOÀI NGHIÊN CỨU VỀ HÀM BĂM TRÊN CƠ SỞ MẠNG HOÁN VỊ THAY THẾ ĐIỀU KHIỂN ĐƯỢC VÀ ỨNG DỤNG TRONG MÃ HÕA XÁC THỰC VĂN BẢN Chuyên ngành: Khoa học máy tính Mã số : 62.48.01 LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Thái Nguyên, năm 2013 Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 1 LỜI CAM ĐOAN Em xin cam đoan toàn bộ luận văn: “Nghiên cứu về hàm băm trên cơ sở mạng hoán vị thay thế điều khiển đƣợc và ứng dụng trong mã hóa xác thực văn bản” là do bản thân tìm hiểu, nghiên cứu. Không có sự sao chép nội dung từ các luận văn khác. Tất cả nội dung hoặc hình ảnh minh họa đều có nguồn gốc xuất xứ rõ ràng từ các tài liệu tham khảo ở nhiều nguồn khác nhau mà xây dựng nên. Ngoài ra còn có sự góp ý và định hƣớng của thầy giáo TS Vũ Đức Thái. Em xin cam đoan những lời trên là đúng, mọi thông tin sai lệch em xin hoàn toàn chịu trách nhiệm trƣớc Hội đồng. Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 2 MỤC LỤC LỜI CAM ĐOAN ............................................................................................................................... 1 MỤC LỤC........................................................................................................................................... 2 DANH MỤC CÁC CHỮ VIẾT TẮT ................................................................................................. 4 DANH MỤC HÌNH ẢNH .................................................................................................................. 5 DANH MỤC BẢNG BIỂU ................................................................................................................ 7 CHƢƠNG 1 TỔNG QUAN VỀ HÀM BĂM ................................................................................... 10 1.1 Giới thiệu về hàm băm ......................................................................................................10 1.1.1 Định nghĩa về hàm băm ............................................................................................10 1.1.2 Lịch sử phát triển của hàm băm ................................................................................11 1.1.3 Thuộc tính an toàn của hàm băm ..............................................................................13 1.1.4 Các quan niệm an toàn ..............................................................................................15 1.2 Ứng dụng của hàm băm ....................................................................................................16 1.3 Xu hƣớng thiết kế ..............................................................................................................17 1.3.1 Hàm băm không khóa và có khóa .............................................................................17 1.3.2 Hàm băm lặp .............................................................................................................18 1.3.3 Hàm băm dựa trên hình cây ......................................................................................28 1.3.4 Hàm nén ....................................................................................................................29 CHƢƠNG 2 KIẾN TRÚC MẠNG CHUYỂN VỊ THAY THẾ ĐIỀU KHIỂN ĐƢỢC ................... 30 2.1 Các phần tử mã hóa cơ bản điều khiển đƣợc dựa trên mạng chuyển vị thay thế ..............30 2.1.1 Phần tử điều khiển cơ bản .........................................................................................30 2.1.2 Phân loại các phần tử cơ bản. ....................................................................................32 2.1.3 Nhóm phụ của các phần tử U2/1 với một đầu ra tuyến tính ........................................37 2.2 Tô pô đối xứng ..................................................................................................................41 CHƢƠNG 3 XÂY DỰNG VÀ CÀI ĐẶT CHƢƠNG TRÌNH MÔ PHỎNG ................................... 51 3.1 Bài toán ứng dụng .............................................................................................................51 3.2 Thiết kế CSDL, thuật toán và giao diện chƣơng trình hàm băm .......................................51 3.2.1 Thiết kế cơ sở dữ liệu .......................................................................................................51 3.2.2 Thuật toán thực hiện .........................................................................................................53 3.2.3 Phân tích các modul chƣơng trình chính ..........................................................................54 3.2.4 Giao diện chƣơng trình ....................................................................................................58 Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 3 3.3 Cài đặt chƣơng trình ..........................................................................................................58 3.4 Tích hợp Add-In vào cho phần mềm Microsoftword 2007 ...............................................59 3.5 Thử nghiệm và đánh giá kết quả .......................................................................................60 3.5.1 Một số kết quả thử nghiệm của chƣơng trình...................................................................60 3.5.2 Đánh giá kết quả ..............................................................................................................61 3.6 Nghiên cứu sử dụng công nghệ FPGA để cấu hình các phần tử điều khiển đƣợc. ..........62 3.7 Kết luận .............................................................................................................................69 KẾT LUẬN ....................................................................................................................................... 71 TÀI LIỆU THAM KHẢO .................................................................................................................72 PHỤ LỤC .......................................................................................................................................... 74 Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 4 DANH MỤC CÁC CHỮ VIẾT TẮT Từ viết tắt AES CE CSPN DES DDP FPGA HMAC NIST NMAC MAC MD5 MDP NL PKC RIPEMD RO SHA SPN TT UOWHFs Nghĩa tiếng Anh Advanced Encryption Standard Controlled Element Controlled Substitution Permutation Network Data Encrypt Standar Data Dependent Permutation (datadriven permutation) Field Programmable Gate Array Nghĩa tiếng Việt Tiêu chuẩn mã hóa tiên tiến Phần tử điều khiển đƣợc Mạng Hoán vị-Thay thế điều khiển đƣợc Chuẩn mã hóa dữ liệu Hoán vị phụ thuộc vào dữ liệu Thiết bị lập trình có khá năng tái cấu hình. Hashed Message Authentication Xác thực thông điệp bằng hàm băm Code National Institute of Standards and Viện Tiêu chuẩn và Công nghệ Technology Quốc gia của Mỹ Non-Message Authentication Code Không mã xác thực thông điệp Message Authentication Code Mã xác thực thông điệp Message-Digest algorithm 5 Giải thuật tóm tắt thông điệp Message-Digest Permutation Hoán vị tóm tắt thông điệp Non Linearity Phi tuyến Public Key Cryptographic Mật mã khóa công khai Race Integrity Primitives Phân loại đánh giá tính toàn vẹn Evaluation Message Digest nguyên thủy của thông điệp Reverse Osmosis Thẩm thấu ngƣợc Secure Hash Algorithm Thuật giải băm an toàn Substitution Permutation Network Mạng hoán vị thay thế Truth Table Bảng giá trị chân lý của các phép toán logic Universal One -Way Hash Hàm băm 1 chiều phổ dụng Functions Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 5 DANH MỤC HÌNH ẢNH Hình 1.1. Hoạt động của một hàm băm ............................................................................................11 Hình 1.2. Sơ đồ biểu diễn các thuộc tính khả năng chống đụng độ, ngăn sự nghịch ảnh và nghịch ảnh thứ 2............................................................................................................................................14 Hình 1.3. Thuật toán bƣớc đệm Merkle-Damgard. ...........................................................................20 Hình 1.4. Cấu trúc Merkle-Damgard ................................................................................................20 Hình 1.5. Tấn công đa đụng độ .........................................................................................................21 Hình 1.6. Cấu trúc kim cƣơng. ..........................................................................................................24 Hình 1.7. Cấu trúc NMAC (a) và HMAC (b) ...................................................................................27 Hình 1.8. Cấu trúc MDP. ..................................................................................................................28 Hình 1.9. Cấu trúc cây mẫu...............................................................................................................29 Hình 2.1. Phần tử cơ bản F2/1: a. Sơ đồ tổng quát; b. Sơ đồ dạng hàm Logic với 3 biến vào; c. Sơ đồ dạng 2 phép thế; d,e. Biểu diễn CE thuộc loại P2/1; f. Đặc trƣng vi phân của F2/1 ......................30 Hình 2.2. Mô tả trực quan toàn bộ các khả năng có thể có của hộp S 2x2 ......................................34 Hình 2.3. Tô pô của các phần tử F8/12 (a), F-18/12 (b), F32/96 (c), và F-132/96 (d) ...............................44 Hình 2.4. Cấu trúc của các phần tử 32/96 (a), -1 32/96 (b), 64/384 (c) và -1 64/384 (d) .......................45 Hình 2.5. Cấu trúc các phần tử đối xứng F2n/4m (a), P16/32 (b) và F64/256 ..........................................46 Hình 3.1: Kết quả thử nghiệm với file *.doc.....................................................................................52 Hình 3.2 : Kết quả thử nghiệm với file *.txt .....................................................................................53 Hình 3.3. Các phần tử cơ bản (a,e), (e,g), (f,i), (p,h), (x,d). ..............................................................55 Hình 3.4. Phần tử CP F8/12 .................................................................................................................55 Hình 3.5. Phần tử CP F-18/12 ...............................................................................................................56 Hình 3.6. Phần tử F96/1 .......................................................................................................................56 Hình 3.7. Phần tử F32/96 (a), F -132/96 (b). ............................................................................................57 Hình 3.8. Phần tử F32/32 .....................................................................................................................57 Hình 3.9. Giao diện chƣơng trình .....................................................................................................58 Hình 3.10. Xây dựng thƣ viện HashDLL.dll.....................................................................................59 Hình 3.11. Giao diện sử dụng Add-In “Ez Hash Function” trong word 2007. .................................60 Hình 3.12. Phần tử (a) đƣợc biểu diễn thành một cặp hàm logic 4 biến (b) hoặc thành 4 phép thế 2x2 (c). .......................................................................................................................................64 Hình 3.13. Cấu trúc tổng quát của các phần tử Số hóa bởi Trung tâm Học liệu n/m ........................................................................65 http://lrc.tnu.edu.vn/ 6 Hình 3.14. Các đặc trƣng vi phân có thể của các phần tử F2/2..........................................................66 Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 7 DANH MỤC BẢNG BIỂU Bảng 1.2. Một số thuật ngữ về hàm băm ..........................................................................................18 Bảng 2.1. Xác suất của các đặc trƣng vi phân của các phần tử ...35 Bảng 2.2. Toàn bộ các phần tử điều khiển đƣợc thỏa mãn tiêu chí lựa chọn ....................................36 Bảng 2.3. Tập các đối hợp phi tuyến tính cơ bản điều khiển đƣợc ...................................................38 Bảng 2.4. Xác suất tập của các đặc trƣng vi phân của các phần tử và .........................................................................................................................................40 Bảng 2.5. Các phần tử hoán vị điều khiển đƣợc với cấu trúc đối xứng ...........................................47 Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 8 MỞ ĐẦU Mật mã (Cryptography) là ngành khoa học nghiên cứu các nội dung về toán học, kỹ thuật nhằm cung cấp các dịch vụ bảo vệ thông tin trong quá trình tuyền tin. Khoa học mật mã đã ra đời và phát triển từ rất sớm, các kết quả nghiên cứu của lĩnh vực này đƣợc sử dụng nhiều trong lĩnh vực quân sự, chính trị, ngoại giao... Ngày nay, khi công nghệ thông tin phát triển các ứng dụng mã hóa và bảo mật thông tin đang đƣợc sử dụng rộng rãi sang nhiều lĩnh vực khác nhƣ kinh tế, thƣơng mại điện tử, ngân hàng… Với sự phát triển của công nghệ truyền thông và các mạng giao dịch toàn cầu, việc trao đổi thông tin ngày càng đơn giản và thuận tiện hơn, bên cạnh đó cũng nảy sinh nhiều yêu cầu cao hơn về bảo mật thông tin trong các hệ thống và các ứng dụng điện tử. Xã hội càng phát triển, nhu cầu sử dụng các dịch vụ mạng ngày càng lớn và chúng không ngừng đƣợc nâng cao về mọi mặt để có thể đáp ứng xu thế thời đại. Trong môi trƣờng mạng, việc truy nhập, lƣu giữ và trao đổi thông tin (trong đó có các thông tin rất nhạy cảm) đƣợc phát triển với tốc độ cao. Điều này đã tạo điều kiện cho các hoạt động phi pháp trên mạng ngày càng gia tăng. Việc xâm phạm dƣới các hình thức khác nhau có thể gây ra các hậu quả nặng nề cho các cá nhân và tổ chức xã hội. Và trên thực tế đã hình thành mâu thuẫn giữa nhu cầu phát triển các ứng dụng mạng với các nguy cơ an toàn về thông tin. Do nhu cầu thực tế, khoa học mật mã không ngừng đƣợc nghiên cứu, phát triển và ứng dụng. Trên thực tế, mật mã có thể phân chia hình thức thành ba hƣớng chính - mật mã khóa bí mật, mật mã khóa công khai, hàm băm mật mã. Trong đó các hàm băm mật mã đóng một vai trò vô cùng quan trọng trong các ứng dụng bảo vệ an toàn thông tin (xác thực, kiểm tra tính toàn vẹn, chữ ký số, …). Trong những năm qua vấn đề nghiên cứu về mật mã tại Việt Nam cũng còn nhiều hạn chế bởi nhiều lý do hoặc có những kết quả nghiên cứu chỉ mang nội dung cơ bản, đặc thù áp dụng trong những tình huống cụ thể của mỗi đơn vị sử dụng. Còn Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 9 lại đa số các công nghệ, kỹ thuật mã hóa trong các ứng dụng và thiết bị đều theo các mô hình mã hóa của thế giới nhƣ DES, AES, MD5,... Do đó, việc nghiên cứu và phát triển các hàm băm mật mã tốt, luôn đƣợc sử dụng trong thực tiễn nhằm phát triển các thuật toán ngày càng tối ƣu, hoặc các thuật toán phù hợp cho các ứng dụng - một trong những mục tiêu chính đƣợc đặt ra nhằm nâng cao tính độc lập trong xây dựng các giải pháp an toàn thông tin. Với mục đích phát triển một hàm băm có độ phức tạp cao có khả năng ứng dụng trong thực tiễn em đã chọn đề tài: “Nghiên cứu về hàm băm trên cơ sở mạng hoán vị thay thế điều khiển được và ứng dụng trong mã hóa xác thực văn bản” cho luận văn tốt nghiệp của mình. Nội dung đề tài nghiên cứu gồm có: Tìm hiểu thuật toán về hàm băm; mạng chuyển vị thay thế điều khiển đƣợc; xây dựng và cài đặt mô phỏng thuật toán băm; mã hóa xác thực văn bản; đánh giá độ tin cậy của thuật toán và đề xuất khả năng ứng dụng. Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 10 CHƢƠNG 1 TỔNG QUAN VỀ HÀM BĂM 1.1 Giới thiệu về hàm băm 1.1.1 Định nghĩa về hàm băm Hàm băm (hash function) là một ánh xạ, ánh xạ các chuỗi nhị phân có độ dài tuỳ ý thành các chuỗi nhị phân có độ dài cố định đƣợc gọi là giá trị băm. Hàm băm 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, ...). Giá trị băm đóng vai trò 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 nhận 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). Trong ngành mật mã học, một hàm băm mật mã học (Cryptographic hash function) là một hàm băm với một số tính chất bảo mật nhất định để phù hợp việc sử dụng trong nhiều ứng dụng bảo mật thông tin đa dạng, chẳng hạn nhƣ chứng thực (authentication) và kiểm tra tính nguyên vẹn của thông điệp (message integrity). Một hàm băm nhận đầu vào là một xâu ký tự dài, thông điệp có độ dài tùy ý và tạo ra kết quả là một xâu ký tự có độ dài cố định, đôi khi đƣợc gọi là tóm tắt thông điệp (message digest) hoặc chữ ký số (digital fingerprint). Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 11 Hình 1.1. Hoạt động của một hàm băm Nói rộng ra, một hàm băm mật mã học phải hoạt động càng giống với một hàm ngẫu nhiên càng tốt, trong khi vẫn có tính chất đơn định và xử lý có hiệu quả. Một hàm băm mật mã học đƣợc coi là không an toàn nếu một trong các việc sau là khả thi về mặt xử lý: - Cho một tóm tắt (digest), tìm một thông điệp chƣa biết khớp với tóm tắt đó. - Tìm các "xung đột băm" (hash collision), trong đó hai thông điệp khác nhau có tóm tắt trùng nhau. Nếu có thể thực hiện một trong hai việc trên, một ngƣời có thể tấn công bằng cách dùng các cách trên để thay một thông điệp không đƣợc xác nhận (unauthorized message) vào chỗ của một thông điệp đƣợc xác nhận. Về lý tƣởng, việc tìm hai thông điệp có tóm tắt rất giống nhau cũng không mấy khả thi; ngƣời ta không muốn một kẻ tấn công có thể tìm hiểu đƣợc điều gì đó hữu ích về một thông điệp nếu biết tóm tắt. 1.1.2 Lịch sử phát triển của hàm băm Các hàm băm mật mã học trên thực tế đã đƣợc chứng minh là công cụ đáng tin cậy của mật mã học hiện đại. Tầm quan trọng của chúng đƣợc công nhận lần đầu tiên khi PKC (Public Key Cryptographic- Mật mã học với khóa phổ biến) đƣợc phát minh bởi Diffie và Hellman vào năm 1976 và từ đây nó trở thành một phần không thể thiếu của PKC [3]. Các tiến bộ gần đây trong lĩnh vực phá mã đã tìm ra nhiều khuyết điểm trong hầu hết các hàm băm phổ biến, điều này đã gây chú ý cho các nhà nghiên cứu quan tâm đến lĩnh vực này. Các nhà nghiên cứu đã phát triển hai hƣớng nghiên cứu chính: hoặc là chỉnh sửa lại các cấu trúc hiện có này bằng việc điều chỉnh chúng một chút để xóa bỏ các nhóm nhƣợc điểm cụ thể, hoặc là thiết kế các hàm băm mới hoàn toàn từ vạch xuất phát. Theo hƣớng thứ nhất, nếu khám phá ra đƣợc các nhƣợc điểm đang tồn tại thì các quy định để thiết kế hàm băm còn chƣa đƣợc hoàn mỹ và nếu chúng không đƣợc chỉnh sửa lại một cách tổng thể thì những Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 12 nhƣợc điểm này sẽ vẫn còn tồn tại, mặc dù có vẻ nhƣ chúng đã đƣợc chỉnh sửa lại bằng một số biện pháp nhỏ. Tƣơng tự, theo hƣớng thứ hai, nếu một hàm băm đƣợc thiết kế lại từ đầu thì vẫn có thể còn tồn tại nhiều nhƣợc điểm, nhƣng nó cũng bị ảnh hƣởng ngầm từ các nhƣợc điểm (có thể là các nhƣợc điểm lớn hơn nhiều) mà không đƣợc nhận ra từ thời kỳ đầu của phát triển. Mặt khác, các cấu trúc hiện thời lại có ƣu điểm là đã đƣợc nghiên cứu và phân tích sâu rộng qua nhiều năm, do vậy nếu các hàm băm mới không đƣợc thiết kế cẩn thận, chúng có thể sẽ bị tấn công nhiều hơn là chống lại. Các hàm băm thƣờng là những hàm nhiều ứng dụng do chúng ánh xạ các đầu vào có độ dài bất kỳ thành các đầu ra có độ vào cố định và đầu vào thƣờng lớn hơn đầu ra (hàm băm là các hàm nén). Do đó, các vụ đụng độ (các thông điệp khác nhau băm thành cùng một giá trị) ở hàm băm thƣờng là không tránh đƣợc do quy luật ngăn hộc. Yuval là nhà nghiên cứu đầu tiên thảo luận về vấn đề làm thế nào để tìm ra những vụ đụng độ trong hàm băm bằng sự sử dụng Birthday Paradox, việc này dẫn đến một hiện tƣợng khá phổ biến hiện nay đó là sự tấn công ngày sinh nhật [6]. Ở kiểu tấn công này, ngƣời ta tìm ra một vụ đụng độ với xác suất là sau khi q truy vấn đến một hàm băm cho ra các giá trị với độ dài n-bit. Dù khả năng chống lại sự đụng độ chắc chắn là một thuộc tính rất quan trọng mà hàm băm nên có nhƣng đó không phải là thuộc tính duy nhất, thậm chí trong một số ứng dụng thì thuộc tính này là không bắt buộc. Ví dụ nhƣ khả năng chống nghịch ảnh (tính bất khả nghịch) là một thuộc tính khó có đƣợc và mang tính thực tiễn hơn. Trên thực tế, ở hầu hết các ứng dụng để có thể nghịch đảo một giá trị băm thì sẽ tổn thất hơn nhiều là tìm ra một vụ đụng độ giữa hai thông điệp bất kỳ. Do đó, chính ứng dụng mà sử dụng hàm băm sẽ quyết định các thuộc tính an toàn mà hàm băm cần bảo tồn. Tuy nhiên điều này đã thay đổi từ năm 2005 khi giáo sƣ Xiaoyun Wang đã thông báo một tấn công lƣợng sai lên hàm băm SHA-1[4]. Cùng với những cải tiến tiếp theo của giáo sƣ Wang, tấn công này đƣợc đánh giá là tìm đƣợc một va chạm Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 13 băm (hai thông báo có cùng giá trị băm) với khối lƣợng công việc ƣớc tính khoảng 263 phép toán, thay cho một cách lý tƣởng là 280 phép toán nhƣ ngƣời ta mong đợi cho SHA-1 hoặc một hàm băm tốt bất kỳ có độ dài đầu ra bằng 160 bit. Đây là một khối lƣợng tính toán lớn, nhƣng 263 phép toán rõ ràng là nằm trong khả năng của một kẻ tấn công có nhiều tài nguyên. NIST (Viện Tiêu chuẩn và Công nghệ quốc gia Hoa Kỳ) công nhận rằng giáo sƣ Wang đã thực sự tìm đƣợc một tấn công va chạm thực hành lên SHA-1, ngƣời ta còn chứng tỏ rằng SHA-1 (tại thời điểm đó) vẫn chƣa đủ mạnh và chƣa thể chống lại đƣợc các vụ đụng độ nhƣ vẫn đƣợc mong đợi. Do điều này mà vào tháng 11/2007 NIST đã công bố 1 cuộc thi mở rộng để lựa chọn 1 tiêu chuẩn hàm băm mới gọi là SHA-3. NIST nhận đƣợc 64 đơn đăng ký, 51 đơn trong số đó đƣợc lựa chọn vào vòng 1 của cuộc thi vào tháng 12 năm 2008. Tháng 7 năm 2009, chỉ có 14 đơn dự thi lọt qua vòng 1 đƣợc vào tiếp vòng 2. Tháng 12/2010, 5 ứng cử viên cuối cùng đƣợc chọn ra (đó là BLAKE, Grostl, JH, Keccak and Skein), và sẽ công bố giải nhất vào quý 2 năm 2012. Vòng chung kết đƣợc tiến hành cuối năm 2011 chƣa ai nói trƣớc đƣợc Skein hay Keccak sẽ đƣợc chọn làm SHA- 3 nhƣng dƣ luận chung công nhận rằng cả hai đều là thuật toán vạn năng, chúng không chỉ thực hiện phép băm mà còn có thể thực hiện hàng loạt các chức năng mật mã khác, điều này cho phép trên thực tế có thể đơn giản hóa nhiều giao thức mật mã, cả những giao thức đang tồn tại và cả những giao thức đang đƣợc thiết kế. Do đó, dù thuật toán nào đƣợc lựa chọn thì điều đó đều đánh dấu một bƣớc tiến quan trọng trong nghiên cứu hàm băm. 1.1.3 Thuộc tính an toàn của hàm băm Các thuộc tính an toàn cơ bản (truyền thống) mà một hàm băm nên có đó là [8]: chống đƣợc sự đụng độ, ngăn đƣợc sự nghịch ảnh và nghịch ảnh thứ 2. Hình 1.2 minh họa các thuộc tính này theo sơ đồ. Mặc dù đây là những thuộc tính an toàn phổ biến mà một hàm băm nên có thì ở một số ứng dụng cụ thể vẫn có thể có một Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 14 số thuộc tính phụ khác mà hàm băm cần phải có nếu chúng đƣợc sử dụng trong một ứng dụng cụ thể. Nhìn chung, khi ta nói rằng một cuộc tấn công phá vỡ đƣợc một hàm băm cụ thể thì không nhất thiết nó có nghĩa rằng hàm băm đó hoàn toàn bị phá hủy trong thực tiễn. nếu một cuộc tấn công có thể chứng minh đƣợc rằng một hàm băm có thể bị phá hỏng bởi cuộc tấn công ngày sinh nhật hay tấn công bạo lực (ví dụ nhƣ: tìm ra một vụ đụng độ, hay nghịch ảnh, hay nghịch ảnh thứ 2) với khối lƣợng công việc ít hơn truy vấn; hàm băm đƣợc coi là bị phá vỡ, mặc dù lƣợc công việc truy vấn để phá vỡ nó vẫn chƣa làm đƣợc trong thực tiễn (đây đƣợc gọi là sự tấn công trên lý thuyết). Thực vậy, tìm ra các điểm chƣa hoàn chỉnh nhƣ vậy ở một hàm băm là một bằng chứng cho các yếu điểm về cấu trúc mà có thể bị phá hủy ở phạm vi lớn hơn để biến sự tấn công trên lý thuyết này trở thành thực tế; mẫu đầu tiên là MD5, thuật toán này đầu tiên bị phá vỡ trên lý thuyết, sau đó các cuộc tấn công dần dần đƣợc cải biến và ngày nay các vụ đụng độ thật có thể đƣợc tìm thấy ở MD5. Hình 1.2. Sơ đồ biểu diễn các thuộc tính khả năng chống đụng độ, ngăn sự nghịch ảnh và nghịch ảnh thứ 2. a, Khả năng chống đụng độ Một vụ đụng độ hàm băm xảy ra khi hai thông điệp khác nhau bất kỳ băm thành cùng một giá trị. Tức là với một hàm băm chống đụng độ H, thì nó không thể tính toán để tìm ra hai thông điệp M và M' bất kỳ sao cho trong khi . Điều này cũng có thể áp dụng cho họ hàm băm (tức là các hàm băm có khóa, ở đây các thành viên của họ hàm băm đƣợc thống kê bởi các khóa khác nhau). Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 15 Chính thức thì ƣu điểm của một kẻ thù A của việc tìm ra đụng độ trong một hàm băm H đƣợc xác định nhƣ sau [8]: b, Khả năng chống lại sự nghịch ảnh Với mọi mục đích thực tiễn, các hàm băm cần phải là bất khả nghịch. Khi một thông điệp đƣợc băm, nó phải không có khả năng khôi phục đƣợc thông điệp gốc từ các giá trị băm lấy đƣợc. Tức là, với một hàm băm chống đƣợc sự nghịch ảnh H, giá trị băm H(M) cho trƣớc của một thông điệp cụ thể M thì nó phải không có khả năng khôi phục thông điệp gốc M, hoặc tạo ra bất kỳ thông điệp sao . Ngắn gọn hơn: cho c, Khả năng chống lại sự nghịch ảnh thứ 2 Cho 1 hàm băm H có khả năng chống sự nghịch ảnh và 1 thông điệp M, thì 1 kẻ tấn công A sẽ không thể tìm đƣợc một thông điệp cả đều băm thành cùng 1 giá trị, khác sao cho và . Ngắn gọn hơn đó là: Với H đƣợc coi là có khả năng ngăn chặn sự nghịch ảnh thứ 2, kiểu tấn công có hiệu quả nhất vào H là kiểu tấn công bạo lực (tức là với độ phức tạp công việc đối với 1 hàm băm có kích thƣớc đầu ra n). Sự tấn công nghịch ảnh thứ 2 cũng còn đƣợc gọi là khả năng chống đụng độ yếu. 1.1.4 Các quan niệm an toàn Những thuộc tính an toàn ngoài những thuộc tính cơ bản truyền thống bên trên, ngƣời ta cho rằng các hàm băm cũng cần phải bảo tồn một số thuộc tính khác và hầu hết các thuộc tính này phụ thuộc vào ứng dụng cụ thể. Ở phần này, sẽ nói về các quan niệm an toàn mà đang nhanh chóng trở thành truy vấn phổ biến cho hầu hết các ứng dụng. Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 16 - Tính không khác biệt. - Tính không phân biệt đƣợc. - Tính không thể làm giả đƣợc. 1.2 Ứng dụng của hàm băm Một ứng dụng điển hình của một hàm băm mật mã học nhƣ sau [3]: Giả sử Alice đƣa cho Bob một câu đố khó và tuyên bố rằng cô ấy đã giải đƣợc rồi. Bob muốn tự giải, nhƣng cũng muốn chắc chắn là Alice đúng là đã giải đƣợc. Do đó, Alice viết đáp án, gắn thêm một khóa ngẫu nhiên, tính giá trị băm của nó, và đƣa kết quả băm cho Bob (trong khi vẫn giữ bí mật đáp án và khóa). Bằng cách này, khi Bob tự giải xong, Alice có thể chứng minh rằng cô đã có đáp án từ trƣớc bằng cách đƣa khóa cho Bob. Trong thực tiễn, Alice và Bob thƣờng là các chƣơng trình máy tính và bí mật thƣờng là cái gì đó không dễ lừa bằng một lời giải cho câu đố. Ứng dụng trên đƣợc gọi là một hệ thống tin cậy (commitment scheme). Một ứng dụng quan trọng khác của các hàm băm bảo mật là sự kiểm tra tính toàn vẹn của thông điệp. Ví dụ, việc xác định xem một file hay một thông điệp có bị sửa đổi hay không có thể thực hiện bằng cách so sánh tóm tắt đƣợc tính trƣớc và sau khi gửi (hoặc một sự kiện bất kỳ nào đó). Có thể dùng tóm tắt thông điệp làm một phƣơng tiện đáng tin cậy cho việc nhận dạng file. Một ứng dụng có liên quan là kiểm tra mật khẩu. Mật khẩu thƣờng không đƣợc lƣu dƣới dạng văn bản rõ (clear text), mà ở dạng tóm tắt. Để xác thực một ngƣời dùng, mật khẩu do ngƣời đó nhập vào đƣợc băm và so sánh với kết quả băm đƣợc lƣu trữ. Do các lý do cả về bảo mật và hiệu năng chƣơng trình, đa số các thuật toán chữ ký số nói rằng chỉ có tóm lƣợc của thông điệp, chứ không phải toàn văn thông điệp, đƣợc "ký". Các hàm băm còn có thể đƣợc dùng để tạo các bit giả ngẫu nhiên (pseudorandom). Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 17 SHA-1, MD5, và RIPEMD-160 nằm trong số các thuật toán tóm tắt thông điệp đƣợc dùng rộng rãi nhất của năm 2005 [4]. Tháng 8 năm 2004, các nhà nghiên cứu đã tìm đƣợc các điểm yếu của một loạt hàm băm, trong đó có MD5, SHA-0 và RIPEMD. Tháng 2 năm 2005, ngƣời ta ghi nhận một tấn công đối với SHA-1. Tháng 8 năm 2005, ngƣời ta lại ghi nhận thêm một tấn công khác đối với SHA-1. Các hàm băm đƣợc dùng để nhận dạng các file trong các mạng chia sẻ tệp đồng đẳng. Ví dụ [5], trong một ed2k link, một biến thể của MD4 đƣợc kết hợp với kích thƣớc file để cung cấp thông tin cho việc xác định nguồn file, tải xuống và kiểm tra nội dung. 1.3 Xu hƣớng thiết kế 1.3.1 Hàm băm không khóa và có khóa Nhìn chung, các hàm băm đƣợc phân loại thành có khóa hoặc không có khóa. Các hàm băm không có khóa chấp nhận một thông điệp M có chiều dài biến động và cho ra một giá trị băm cố định ( . Mặt khác, các hàm băm có khóa chấp nhận cả thông điệp có chiều dài biến động M và khóa có chiều dài cố định K để cho ra 1 giá trị băm cố định, . Hàm băm có khóa còn đƣợc tiếp tục phân loại dựa trên việc khóa là khóa bí mật hay khóa công khai. Các hàm băm có khóa bí mật thƣờng đƣợc sử dụng để xây dựng thông điệp các mã xác thực thông điệp (MAC - Message Authentication Code) , một ví dụ phù hợp tiêu chuẩn này đó là (HMAC - Hashed Message Authentication Code) rõ hơn về MAC. Tuy nhiên, nếu các hàm băm có khóa công khai, thì chúng đƣợc biết đến nhƣ các hàm băm có khóa chuyên dụng. Các hàm băm đƣợc thiết kế cho trƣờng hợp khóa chuyên dụng là họ các hàm băm mà ở đây các hàm thành viên đƣợc đánh số bởi các khóa khác nhau. Trong trƣờng hợp này, nếu một thành viên của họ hàm băm bị phá thì sẽ có một số ảnh hƣởng nhỏ tới các thành viên khác trong cùng một họ (điều này không đúng trong trƣờng hợp hàm băm không khóa mà một cuộc tấn công đơn độc vào một hàm và phá hủy hoàn toàn hàm đó). Tuy nhiên Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 18 một yếu điểm rất rõ ràng của hàm băm trong trƣờng hợp khóa chuyên dụng đó là hiệu quả bị thấp đi vì trong trƣờng hợp này hàm băm ngoài có đầu vào (thông điệp) phải có thêm đầu vào (khóa). Xem bảng 1.1 để rõ hơn về các định nghĩa ngắn gọn (không chính thức) của thuật ngữ về hàm băm đƣợc sử dụng trong toàn bài. Bảng 1.1. Một số thuật ngữ về hàm băm Thuật ngữ Định nghĩa không chính thức Một khối cấu trúc tiêu chuẩn của hàm băm với miền lớn hơn phạm vi. Cấu trúc, chuyển đổi, chế độ hoạt động, Một thuật toán mà gọi một khối cấu trúc chế độ chuỗi, chuyển đổi mở rộng (thƣờng là một hàm nén) theo tính hệ miền, sơ đồ tổ hợp. thống để băm một thông điệp. Hàm nén. Biến số chuỗi, giá trị chuỗi, sự băm Đầu ra của một hàm nén đƣợc sử dụng trung gian, biến số tính trạng bên trong. nhƣ đầu vào cuộc gọi với hàm nén theo sau. Giá trị băm, giá trị băm cuối cùng, mật Kết quả cuối cùng của việc băm một mã băm, kết quả băm, băm, phân loại. thông điệp, gọi là một chuỗi có chiều dài cố định. Tóm lại, một hàm băm (có khóa hay không khóa) đƣợc xây dựng bằng hai bộ phận là: Một hàm nén f và cấu trúc H. Hàm nén là một hàm ánh xạ một đầu vào có kích thƣớc lớn hơn (nhƣng cố định) đến một đầu ra có kích thƣớc nhỏ hơn , ở đây . Cấu trúc là cách hàm nén đƣợc gọi lặp đi lặp lại để xử lý một thông điệp. 1.3.2 Hàm băm lặp Khi các hàm băm xuất hiện lần đầu tiên, ngƣời ta nhận ra rằng cách thuận tiện nhất để băm một thông điệp đó là trƣớc tiên phải chia nó thành một vài khối và sau đó xử lý các khối này lặp đi lặp lại theo hệ thống. Ngày nay, phƣơng pháp này vẫn là phƣơng pháp đƣợc sử dụng rộng rãi nhất, mặc dù với sự có mặt của một số bộ xử lý song song (mà ít nhất theo quy tắc thì phải tạo điều kiện thuận lợi cho các hàm băm song song). a, Cấu trúc Merkle-Damgard. Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/ 19 Hầu hết các hàm băm hiện nay nhƣ MD5 và SHA-1 đều dựa trên cấu trúc không nổi tiếng đó là cấu trúc Merkle-Damgard (còn gọi là cấu trúc tầng) đƣợc đề xuất độc lập bởi Merkle và Damgard vào năm 1989 (dù vậy, cấu trúc của Damgard là có khóa còn của Merkle thì không) [6]. Tuy nhiên trƣớc đây một cấu trúc tƣơng tự đã đƣợc Rabin đƣa ra vào năm 1978, điều này nảy sinh vấn đề rằng liệu rằng nó có phải đƣợc gọi là cấu trúc của Rabin hay không. Tuy vậy, trong khi trên thực tế là do Rabin đƣa ra cấu trúc này nhƣng chính Merkle và Damgard mới là ngƣời chính thức chứng minh rằng cấu trúc này có thể ngăn chặn sự đụng độ. Trong cấu trúc của Merkle và Damgard, thông điệp M trƣớc tiên đƣợc chia đều thành các khối có kích thƣớc nhƣ nhau . Nếu khối cuối cùng có kích thƣớc nhỏ hơn thì khối này đƣợc đệm lót thêm cho. Để có thể ngăn chặn sự đụng độ, độ dài của thông điệp đƣợc gắn vào thông điệp (sau khi đã đệm) và nó đƣợc đặt tên là sự củng cố Merkle-Damgard (đƣợc đặt lần đầu tiên bởi Lai và Massey ở mặc dù đã đƣợc đề xuất bởi Merkle và Damgard); Hình 1.3 minh họa thuật toán bƣớc đệm, ở đây L là 1 mã hóa 64 bit của độ dài thông điệp và m là độ dài của 1 khối đơn. Tiếp đó thông điệp này đƣợc lặp lại bằng việc gọi một hàm nén có chiều dài đầu vào cố định (FIL) chấp nhận hai đầu vào đó là: một khối thông điệp (của độ dài m) và hoặc là một véc tơ khởi tạo IV (khi băm khối thứ nhất) hoặc là một biến chuỗi (mà sẽ do đầu vào của hàm f trƣớc đó gọi), cả hai đầu vào đều thuộc độ dài n; hình 1.4 miêu tả mã làm giả của cấu trúc Merkle-Damgard. * Algorithm Pads (M) d = M + 1 +64 mod m M 64 → → M1 ... ML Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/