Hàm Hash và một số ứng dụng

Hàm băm (hàm hash) là một trong những thành phần cốt lõi của mật mã. Sở dĩ mình quyết định giới thiệu về hash là vì nó được sử dụng khá nhiều trong các kỹ thuật về blockchain như: wallet address, digital signature, merkle tree, bloom filter, proof-of-work, zk-rollups, …

Hash là gì?

Hàm hash có các tính chất như sau:

• Pre-Image Resistance: hàm hash \(h\) là hàm một chiều, nghĩa là là không tồn tại một ánh xạ \(h^{-1}\) của nó. Nghĩa là nếu \(h(x)=y\) thì không tồn tại hàm \(h^{-1}(y) = x\), và việc để tìm \(x\) khi biết giá trị của \(y\) là rất khó.

• Second Pre-Image Resistance: Với \(x\) và \(y=h(x)\), rất khó để tìm được \(z \ne x\) sao cho \(h(z)=y\)

• Collision Resistance: Sẽ rất khó tìm một cặp \(x_1 \ne x_2\) sao cho: \(h(x_1) = h(x_2)\)

Vì các tính chất của hash, người ta thường dùng giá trị hash để làm đại diện cho toàn bộ thông điệp để tiết kiệm không gian lưu trữ. Bạn có thể tưởng tượng giá trị hash giống như vân tay hay ADN của một người vậy. Để xác định danh tính của một người, có thể dùng vân tay của họ, vì hầu như không bao giờ có vân tay của ai giống vân tay của ai cả (tính chất #3), ngược lại nếu chỉ nhìn vào vân tay, không thể xác định hay hình dung ra người ấy là ai (tính chất #1), hoặc rất khó thể tìm được một người nào đó có vân tay giống với vân tay người này (tính chất #2).

Một điểm quan trọng nữa mà mọi người rất hay sai lầm đó là hash KHÔNG PHẢI là mã hóa vì hàm hash không có khóa, và cũng không có giải mã vì nó là hàm một chiều (tính chất #1).

Hiện nay, hàm hash đang được sử dụng tại đa số các hệ thống blockchain là hàm SHA256, hàm này biến một chuỗi bất kỳ thành một chuỗi dài 256 bit.

Một số các ứng dụng đơn giản

Vì hàm hash là hàm 1 chiều (tính chất #1), người ta thường lưu trữ giá trị hash ứng dụng vào quá trình authentication. Thay vì lưu trữ một cặp (username, password), người ta lưu cặp (username, hash(password)). Trong khi login, password tại máy người dùng sẽ được chuyển thành giá trị hash, rồi mới gửi lên server. Server nhận giá trị hash và so khớp với giá trị h(password) để cấp quyền truy cập cho người dùng. Điều này nhằm tránh các tấn công Middle-Man-Attack, hoặc tránh việc lộ thông tin nếu database bị rò rỉ, hacker có thể nhìn thấy password gốc và thử login vào một hệ thống khác vì người dùng có thói quen rất ít khi thay đổi password cho các hệ thống khác nhau. Mật khẩu dành cho Facebook cũng giống với mật khẩu cho ngân hàng, và cũng giống mật khẩu cho Apple… (và nhất là thời buổi công nghệ Single Sign-On như hiện nay)

Hàm hash cũng có thể được sử dụng trong chữ ký điện tử. Chữ ký điện tử là một mảnh thông tin được ghép thêm vào một thông điệp để xác nhận tác giả của thông điệp ấy. Mảnh thông tin này thực chất là bản mã hóa của thông điệp gốc, dùng khóa bí mật của tác giả. Để validate chữ ký, người ta dùng khóa công khai để giải mã mảnh thông tin này, sau đó so khớp với thông điệp gốc, nếu khớp thì chữ ký hợp lệ. Lược đồ sau mô tả hoạt động của mô hình chữ ký điện tử:

Ở lược đồ trên, ta thấy thông điệp gốc là “ABC12345“ và chữ ký tương ứng là “^%#&SGRW”, vấn đề là nếu thông điệp gốc quá dài thì phần mã hóa của nó cũng dài theo tương ứng và làm cho thông điệp sau khi ký sẽ có kích thước tăng gấp đôi. Để giải quyết vấn đề này, người ta thay vì mã hóa thông điệp gốc, trước đó, người ta sẽ tính giá trị hash của thông điệp gốc để có một chuỗi có kích thước ngắn gọn hơn, và rồi mã hóa giá trị hash ấy.

Hàm hash còn được sử dụng như một giá trị checksum. Giả sử ta có một file dữ liệu chia sẻ với mọi người được upload lên một host nào đó. Để đảm bảo rằng nội dung file không bị thay đổi vì bất cứ một lý do gì (thay đổi số liệu, hoặc thậm chí cài vào mã độc vào đó), ta có thể lấy toàn bộ nội dung gốc của file này và tính giá trị hash cho nó rồi publish giá trị này lên web gọi là checksum. Như vậy, ai download file này về có thể tính lại giá trị hash và so sánh với checksum trên web. Nếu không khớp thì có thể khẳng định nội dung file lấy về đã bị thay đổi. Việc lưu thông tin checksum chỉ mất 256bit dung lượng, rất nhỏ so với file gốc.

Trong kỹ thuật blockchain, người ta dùng hash để tạo ra wallet address, hoặc ứng dụng trong thuật toán tạo ra số ngẫu nhiên có thể kiểm chứng bằng lược đồ RANDAO, và rất nhiều ứng dụng khác mà mình sẽ có những bài viết chi tiết hơn sau này.