An ninh bảo mật - Hàm băm mật mã

Kỷ yếu công trình khoa học 2015 – Phần I HÀM BĂM MẬT MÃ Nguyễn Minh Hòa Khoa Toán-Tin, Đại học Thăng Long Email: mr.nmh175@gmail.com Tóm tắt: Khái niệm hàm băm đã xuất hiện từ lâu trong lĩnh vực máy tính. Nó ánh xạ một xâu nhị phân (văn bản, hình ảnh, âm thanh,) có độ dài bất kỳ thành một xâu có độ dài cố định. Bản chất của mã băm có thể coi như “dấu vân tay” của một văn bản. Nhờ có nó ta có thể đảm bảo rằng một văn bản là chính xác và không bị sửa đổi. Hiện nay trên thế giới có rất nhiều hàm băm phục vụ cho nhiều mục đích khác nhau như quân sự, truyền tin, xác thực Với mong muốn làm chủ mã nguồn, làm chủ chương trình, chúng tôi đã cố gắng tìm hiểu và cài đặt hàm băm SHA-256 phục vụ cho đề tài Xây dựng hệ thống chữ ký số cho trường Đại học Thăng Long. Trong bài báo sẽ mô tả chi tiết về hàm băm này. Từ khóa:Hàm băm, Mã băm, Chữ ký số, SHA-256. 1. Giới thiệu Hàm băm là hàm ánh xạ một xâu nhị phân có độ dài bất kỳ thành một xâu nhị phân có độ dài cố định (thường được gọi là mã băm). Thông thường, độ dài của mã băm có thể là 128, 160, 256 hoặc 512 bit.Hàm băm có thể coi là hàm nén thông điệp một cách hợp lý. Để có thể dùng trong thực tế, hàm băm cần đảm bảo các tính chất như: thời gian tính toán nhanh, mã băm sinh ra phải ngẫu nhiên và thuật toán phải công khai. Nhằm mục đích đáp ứng các tính chất trên, hàm băm SHA-256 đã được xây dựng dựa trên sơ đồ Merkle-Damgard Ứng và hàm nén Davies-Meyer.Ứng dụng của nó là để kiểm tra tính toàn vẹn của thông điệp. Bài báo này sẽ trình bày chi tiết các lý thuyết và cách thức hoạt động của hàm băm SHA-256. Nội dung các phần bao gồm: Phần 2 sẽ mô tả về hàm băm kháng xung đột - một mô hình hàm băm phù hợp với thực tế; Phần 3 mô tả về hàm băm SHA-256; Phần cuối cũng sẽ nói về thực tế cài đặt hàm băm SHA-256 của dự án. 2. Hàm băm kháng xung đột 2.1. Các định nghĩa Định nghĩa 1.Hàm băm là hàm tính được một cách “hiệu quả” Nó ánh xạ một xâu nhị phân độ dài bất kỳ trong không gian thông điệp thành một xâu nhị phân độ dài cố định, gọi là mã băm. Thông thường độ dài của mã băm là d= 128, 160, 256 hoặc 512 bit. Ví dụ 1. Một số hàm băm trong thực tế. Trường Đại học Thăng Long 11 Kỷ yếu công trình khoa học 2015 – Phần I Hàm băm d MD4 128 SHA-1 160 SHA-256 256 SHA-512 512 SHA-3 (Keccak) 224, 256, 384, 512 Giả sử hàm băm được thiết kế một cách lý tưởng (như ngẫu nhiên), khi đó cho trước mã bămx, xác suất tìm được một dữ liệum thỏa mãn H(m) = x chỉ là . Con số này rất gần 0 khi d đủ lớn. Như vậy hàm băm cho ta một biểu diễn nén hợp lý của dữ liệu. Bên cạnh đó, để có thể dùng trong thực tế, hàm băm cần có một số tính chất sau: • Tính hiệu quả: có thuật toán “nhanh” (trong thời gian đa thức ) để tính h. • Tính ngẫu nhiên: giá trị H(m) là khó dự đoán. • Tính công khai. Định nghĩa 2.Một xung đột cho hàm H là một cặp thỏa mãn Rõ ràng, vì kích thước đầu vào của hàm băm lớn hơn so với kích thước đầu ra, nên theo nguyên lý “chuồng bồ câu”, luôn tồn tại xung đột. Tuy vậy, để hàm băm là an toàn thì việc tìm thấy xung đột phải rất “khó”. Có nghĩa rằng, xác suất tìm thấy xung đột phải “nhỏ”. Định nghĩa 3.Hàm H gọi là kháng xung độtnếu với mọi thuật toán (tường minh1) “hiệu quả” A, ta có là nhỏ “không đáng kể”. Hiệnnay, hàm băm , ánh xạ các xâu nhị phân độ dài tối đa sang các xâu độ dài 256, được thừa nhận một cách rộng rãi là kháng xung đột. Mục đích của hàm băm không phải là giữ bí mật không điệp mà là đảm bảo tính toàn vẹn thông điệp. 1Vì xung đột luôn tồn tại, nên ta có ngay thuật toán in ra xung đột đó. Tường minh ở đây hiểu rẳng thuật toán phải xây dựng xung đột từ mô tả của hàm băm, chứ không phải từ xung đột đã có. Trường Đại học Thăng Long 12 Kỷ yếu công trình khoa học 2015 – Phần I 2.2. Tấn công dùng nghịch lý ngày sinh Xét hàm băm . Thuật toán sau đây có thể được dùng để tìm xung đột cho các hàm băm trong thời gian . Thuật toán: 1. Chọn ngẫu nhiên xâu trong : (xác suất chúng đôi một phân biệt là cao). 2. Với , ta tính . 3. Tìm xung đột . Nếu không tìm thấy thì quay lại bước 1. Thuật toán được đánh giá dựa trên định lý sau đây: Định lý 1 (Nghịch lý ngày sinh nhật). Xét là các biến ngẫu nhiên độc lập. Nếu thì Từ định lý trên, ta thấy rằng kỳ vọng tìm được xung đột của thuật toán trên là 2. Thời gian cần cho thuật toán là và không gian cần là . Hàm băm Kích thước mã băm Tốc độ (MB/s) Thời gian tấn công SHA-1 160 153 SHA-256 256 111 SHA-512 512 99 Whirlpool 512 57 2.3. Sơ đồ Merkle-Damgard Để xây dựng hàm băm kháng xung đột, kích thước mã băm tối thiểu nên là 160 bit. Tuy nhiên đầu vào có thể là một xâu với kích thước tùy ý. Trên thực tế, việc thiết kế hàm băm trên miền vô hạn là khó. Bởi vậy người ta thường thiết kế một hàm nén ánh xạ các xâu bit độ dài cố định s thành các xâu bít độ dài cố định d, sau đó thực hiện tính toán lặp với hàm nén để được hàm băm với đầu vào tùy ý. Phép biến đổi Merkle-Damgard là một cách phổ biến để mở rộng một hàm nén kháng xung đột với kích thước đầu vào cố định thành hàm băm kháng xung đột kích thước đầu vào tùy ý. Trong sơ đồ Merkle-Damgard, ta sử dụng hàm nén kích thước đầu vào cố định Trường Đại học Thăng Long 13 Kỷ yếu công trình khoa học 2015 – Phần I Hình 1. Sơ đồ Merkle-Damgard Mục đích của ta là xây dựng hàm băm kích thước đầu vào tùy ý Sơ đồ Merkle-Damgard được mô tả như trong Hình 1. Thuật toán Merkle-Damgard được mô tả như sau: 1. Dữ liệu cần bămm với độ dài |m| = L sẽ được ghép với dãy bit với l là số nguyên không âm nhỏ nhất để độ dài củam||PB chia hết cho k. 2. Thông điệp m||PB sẽ được chia thành các khốik bit: 3. Gán là một dãy d bit cố định. 4. Với i = 0, 1, , t ta tính 5. Output . Tính an toàn của sơ đồ Merkle-Damgard được chỉ ra bởi định lý sau. Định lý 2. Nếu hàm nén h là kháng xung đột, vậy hàm H xây dựng theo sơ đồ Merkle- Damgard cũng là kháng xung đột. 2.4. Xây dựng hàm nén Sơ đồ trước cho phép ta đưa bài toán thiết kế hàm băm kháng xung đột với đầu vào bất kỳ về bài toán thiết kế hàm nén với đầu vào cố định. Bây giờ ta xem xét một cách thiết kế hàm nén dựa trên mã khối an toàn. Xét hệ mã khối E trên không gian khóa K và không gian thông điệp : Hàm nén Davies-Meyer định nghĩa bởi: Trường Đại học Thăng Long 14 Kỷ yếu công trình khoa học 2015 – Phần I Giả sử (E,D) là một hệ mã khối “lý tưởng” (tập gồm |K| hoán vị ngẫu nhiên). Tìm một xung độth(x,y)= h(x',y')cho hàm nén Davies-Meyer định nghĩa ở trên mất lần tính (E, D). Để phù hợp với tiêu chuẩn quốc gia Việt Nam về chữ ký số (TCVN 7635:2007), chúng tôi sử dụng SHA-256 là hàm băm phục vụ dự án chữ ký số của trường Đại học Thăng Long. Hàm băm chuẩn SHA-256 được xây dựng dựa trên sơ đồ Merkle-Damgard,hàm nén Davies-Meyer và hệ mã khối SHACAL-2 với kích thước khối là 256.Phần tiếp theo, chúng ta sẽ mô tả chi tiết SHA-256 và SHACAL-2. 3. Hàm băm SHA-256 Hàm băm SHA256 nhận đầu vào là một xâu bit (ký tự, tập tin) bất kỳ có độ dài tối đa bit và tạo ra một mã băm có độ dài 256 bit và thường được biểu diễn dưới dạng 64 chữ số trong hệ cơ số 16. 3.1. Sơ đồ chung Hàm băm này được xây dựng dựa trên sơ đồ Merkle-Damgard với • Vector khởi tạo là dãy 256 bit được chia thành 8 khối liên tiếp • Dữ liệu đầu vào được chia thành các khối m[i] kích thước 512 bit, và • Hàm nén Davies-Meyer định nghĩa bởi trong đó E là hệ mã khối an toàn 3.2. Hệ mã khối SHACAL-2 Ta sử dụng một số ký hiệu sau để mô tả hệ mã khối SHACAL-2: Ký hiệu Mô tả Trường Đại học Thăng Long 15 Kỷ yếu công trình khoa học 2015 – Phần I ⋀ Phép toán AND ⊕ Phép toán XOR ¬ Phép đảo bit Phép quay phải n bit Phép dịch phải n bit Dựa vào các ký hiệu trên, ta xây dựng các hàm sau Ta cũng sử dụng các hằng số độ dài 32 bit Đây chính là 32 bit đầu tiên của giá trị căn bậc ba của 64 số nguyên tố đầu tiên. Các hằng số này được mô tả dưới đây (ở dạng hexa). Quá trình tính toán diễn ra như sau: Trường Đại học Thăng Long 16 Kỷ yếu công trình khoa học 2015 – Phần I 4. Cài đặt và thử nghiệm Hiện nay có khá nhiều thư viện hỗ trợ sẵn hàm băm SHA-256. Tuy nhiên, với mong muốn làm chủ mã nguồn cũng như giúp chương trình sau này linh hoạt hơn trong việc xử lý, thay thế, nâng cấp các modul, chúng tôi quyết định tự cài đặt lại thuật toán SHA-256 theo các mô tả trong tài liệu FIPS PUB 180-4 và đã cài đặt thành công bằng ngôn ngữ lập trình C++ trên hệ điều hành Windows 8 - 64bits.Chương trình đã được kiểm tra bằng các vector test của NIST cũng như so sánh với các chương trình sinh mã SHA256 khác. Đầu vào của chương trình là đường dẫn một tập tin bất kỳ (văn bản, hình ảnh, âm thanh,). Đầu ra của chương trình là một xâu dài 64 ký tự (mỗi ký tự là một số ở hệ cơ số 16), chính là mã băm SHA-256 của tập tin đầu vào ở dạng hexa. Chúng tôi đã chạy thử nghiệm chương trình trên máy laptop có bộ xử lý Core i5 1.8Ghz, với 4GB Ram, hệ điều hành Windows 8, 64 bit. Thời gian sinh mã băm của chương trình phụ thuộc vào kích thước của tập tin đầu vào. Với những tập tin có kích thước dưới Trường Đại học Thăng Long 17 Kỷ yếu công trình khoa học 2015 – Phần I 200MB, thời gian sinh mã băm trung bình là xấp xỉ 1 giây. Trong quá trình kiểm thử, chúng tôi đã băm một tập tin hình video kích thước 1,05GB, thời gian sinh mã băm là xấp xỉ 13 giây. 5. Tài liệu tham khảo [1]. Khóa học Cryptography I : https://www.coursera.org/course/crypto [2]. Jonathan Katz và Yehuda Lindell, Introduction to Modern Cryptography, Chapman & Hall/CRC, 2007. [3]. NIST, Federal Information Processing Standards Publication 180-4, SecureHash Standards (SHS), March 2012. Abstract: The concept “hash function” has appeared long ago in Computer Science. It maps a binary string (text, images, audio, ...) with any length into a fixed-length string. The nature of the hash code can be viewed as a "fingerprint" of a document.And we can use it to guarantee that a document is correct and not be modified.Today, there are many hash functions which are usedformany different purposes, such as military, communications, authentic ...With a desire to control the source code and program, we have tried to learn and install SHA-256 in digital signature system for Thang Long University project. In the paper, we will describe the details of this hash function. Keyword:Hash function, Hash digest, Digital signature, SHA-256. Trường Đại học Thăng Long 18