Hàm băm và ứng dụng (Phần 1)

Published in

ZaloPay Engineering

9 min readOct 4, 2019

Hàm băm là một giải thuật được sử dụng để ánh xạ dữ liệu có kích thước tùy ý sang dữ liệu có kích thước cố định. Ý tưởng này xuất phát vào năm 1953, từ một kỹ sư IBM — Hans Peter muốn viết một bảng ghi nhớ IBM nội bộ trong đó các thông tin được đưa vào các bucket được đánh số để tăng tốc tìm kiếm. Qua nhiều thập kỷ, các nhà khoa học máy tính, lập trình viên đã cải tiến các phương pháp của Luhn và áp dụng chúng vào những trường hợp mới mẻ hơn. Tuy nhiên, ý tưởng ban đầu vẫn giống nhau: Dùng các vấn đề toán học để tổ chức dữ liệu vào các bucket sao cho việc tìm kiếm và thu hồi là nhanh nhất. Các thuật toán băm đã trở nên quan trọng trong các lĩnh vực như mã hóa, đồ họa, liên lạc thông tin và sinh học... Trong Computer Science, hàm băm được ứng dụng rất nhiều trong các bài toán về message integrity, proof of work, digital signature... Bài viết sẽ chia làm hai phần để nói về hai loại hàm băm: Hàm băm mật mã và hàm băm phi mật mã. Mỗi phần sẽ nghiên cứu các tính chất và cách thức hoạt động của các thuật toán băm tiêu biểu.

Ở phần 1 này, ta sẽ cùng nhau tìm hiểu về loại hàm băm phổ biến: hàm băm mật mã.

Hàm băm mật mã (Cryptographic hash function)

Hàm băm mật mã là một lớp đặc biệt của hàm băm với mục đích cung cấp tính bảo mật.

Tính chất

Hàm băm mật mã có 6 tính chất sau:

Tính xác định — Deterministic: cùng một chuỗi đầu vào, hàm băm luôn trả về một kết quả giống nhau.
Nhanh chóng — Quick: tiêu tốn ít thời gian để tính toán giá trị băm của bất kì chuỗi đầu vào nào.
Hàm một chiều — One-way function: không khả thi (không thể) để tìm được giá trị chuỗi đầu vào khi biết giá trị băm của nó trừ khi thử hết tất cả các giá trị có thể.
Hiệu ứng lan truyền — Avalanche effect: chỉ một sự thay đổi nhỏ của message có thể thay đổi đáng kể kết quả hash đến nỗi ta không biết được mối liên hệ với kết quả hash cũ.
Ngăn chặn đụng độ — Collision resistant: không khả thi (không thể) để tìm được giá trị 2 chuỗi đầu vào có cùng kết quả giá trị băm.
Ngăn chặn tấn công tiền ảnh — Pre-image attack resistant: Một cách tấn công vào các hàm băm mật mã thường cố tìm một message có giá trị hash đã cho trước. Các hàm băm mật mã phải chống lại được kiểu tấn công này.

Ứng dụng

So với các hàm hash thông thường, hàm băm mật mã thường có xu hướng sử dụng nhiều tài nguyên tính toán hơn. Vì lí do này, các hàm băm mật mã thường chỉ được dùng trong các bối cảnh cần bảo vệ, chống thông tin giả mạo trước các đối tượng độc hại.

Sau đây là một số ứng dụng của hàm băm mật mã:

Kiểm tra tính toàn vẹn của message và file: bằng cách so sánh giá trị băm của message trước và sau khi truyền để xác định xem liệu có thay đổi nào đã xảy ra trong quá trình truyền hay không.
Xác thực mật khẩu: ta có thể lưu trữ mật khẩu bằng giá trị băm của nó để tăng tính bảo mật. Để kiểm tra, password được user đưa vào sẽ được hash và so sánh với giá trị băm đã được lưu. Để phòng chống tấn công bằng brute force, ta có thể tăng thời gian kiểm tra bằng cách sử dụng key stretching. Ngoài ra ta có thể sử dụng thêm salt để tránh trường hợp: 2 password giống nhau có kết quả lưu trữ giống nhau. Xem thêm về cách lưu trữ password tại đây.
Bằng chứng công việc — Proof of Work (PoW): được sử dụng trong blockchain để chống lại DOS, spam bằng cách yêu cầu một số công việc từ bên muốn truy cập. Đặc điểm chính của công việc này là: công việc phải có độ khó cao tốn nhiều thời gian (nhưng khả thi) ở phía requester nhưng lại dễ kiểm tra cho provider. Vì vậy hàm băm được sử dụng ở đây. Ví dụ công việc được đưa ra là tìm một message, sao cho giá trị băm của nó bắt đầu với 20 bit 0. Trung bình mỗi requester cần thử 2¹⁹ lần để tìm ra một message đúng.

Để lấy ví dụ cho hàm băm mật mã, sau đây bài viết sẽ giới thiệu về SHA-3.

SHA-3

Giới thiệu

SHA-3 (Secure Hash Algorithm 3) là thành viên mới nhất của họ các thuật toán băm mật mã (cryptographic hash function), được công bố bởi NIST (Viện Tiêu chuẩn và Kỹ thuật quốc gia Hoa Kỳ).

Vào giai đoạn 2005–2006, MD5 và SHA-1 được cho là không còn an toàn, trong khi đó SHA-2 cũng dựa vào các nguyên lí dùng cho MD5 và SHA-1, do vậy NIST đã tổ một cuộc thi để tìm ra tìm ra một thuật toán băm mới SHA-3. SHA-3 ra đời, SHA-3 là một phần của họ các thuật toán băm lớn được gọi là KECCAK. SHA-3 đem lại sự khác biệt khi sử dụng cấu trúc bọt biển (Sponge construct), trong đó dùng hàm hoán vị để xử lí và đưa ra output đồng thời các hàm này cũng được dùng cho việc xử lí các input tiếp theo được đưa vào hàm hash.

Thiết kế

Các tham số liên quan và kí hiệu:

m là input đầu vào
Hàm Padding pad
Hàm hoán vị ngẫu nhiên f gồm 24 round có đầu vào là một state, và trả về một state mới
State: khối bit có độ dài b. Trong SHA-3 b = 1600
Phần thay đổi trong state gọi là rate có độ dài r
Phần còn lại trong state gọi là capacity có độ dài c = b -r.
Độ dài output là d

Dựa vào yêu cầu về độ dài output d của NIST về thuật toán băm mới, các thông số về r và c sẽ thay đổi theo bảng sau:

Trong phần pre-process, input m được chia nhỏ ra làm n các block X có độ dài bằng r. Để có thể chia m thành n block cùng độ dài, ta dùng hàm pad để chèn thêm một lượng các bit vào m sao cho độ dài của m lúc này chia hết cho r.

Lúc này dãy các block Xi (i=0..n-1) sẽ được đưa vào cấu trúc bọt biển.

Cấu trúc bọt biển

SHA-3 sử dụng cấu trúc bọt biển, trong đó dữ liệu sẽ được đi qua 2 giai đoạn:

Absorb: dữ liệu đầu vào (input) được “thấm hút” (absorb) vào bọt biển
Squeeze: Kết quả (output) sẽ được “vắt ra” (squeeze) từ bọt biển

Giai đoạn 1: Absorb

State được khởi tạo với chuỗi bit 0 có độ dài b = 1600
Duyệt qua tất cả các Xi
Thêm vào c bit 0 vào Xi để Xi bây giờ có độ dài b bằng với State
XOR Xi vừa nhận được với State
Đưa kết quả nhận được qua hàm f, hàm f trả về một State mới. Tiếp tục duyệt đến block X(i+1)

Giai đoạn 2: Squeeze

Khởi tạo kết quả Y với chuỗi độ dài 0 bit
Khi độ dài của Y ít hơn độ dài output d:
Lấy r bit của State thêm vào Y
Nếu độ dài Y vẫn nhỏ hơn d, sử dụng hàm f tạo State mới rồi tiếp tục dùng r bit của State mới này để thêm vào Y
Nếu độ dài của Y lớn hơn d: lấy d bit đầu và bỏ phần dư còn lại.

Lưu ý: với SHA-3 ta chỉ cần thực hiện 1 lần bước 2, vì r > d.

Hàm Padding

Để đảm bảo dữ liệu đầu vào m có thể chia ra thành các block đúng r bit. SHA-3 dùng pattern 10*1 trong hàm padding: bắt đầu bằng bit 1, theo sau đó là các bit 0 (tối đa là r-1), và kết thúc bằng bit 1.

Trường hợp có r-1 bit 0 xảy ra khi: Block cuối cùng của dữ liệu đầu vào có độ dài là r-1. Khi đó, block này sẽ được thêm bit 1 vào cuối để đủ độ dài là r, một block khác được thêm vào chứa r-1bit 0 và kết thúc bằng bit 1.

Nếu độ dài block cuối cùng của dữ liệu đầu vào bằng r, nói cách khác độ dài dữ liệu đầu vào chia hết cho r, thì lúc này vẫn cần thêm một block kết thúc. Block kết thúc trong trường hợp này bắt đầu bằng 1, theo đó là r-2bit 0, và kết thúc bằng bit 1.

Hàm hoán vị block (Block permutation)

Trong Keccak, độ dài state có thể được tính theo công thức b = 5 x 5 x w với w = 2^l (l = 1..6, trong trường hợp của SHA-3 w = 64 với l = 6, dẫn đến b = 1600)

Xem state như một mảng 3 chiều 5 x 5 x w kí hiệu là A với: A[i][j][k] = bit thứ (5i + j) x w + k của state.

Hàm hoán vị block bao gồm 12 + 2l round (với SHA-3 là 24 round), mỗi round gồm 5 bước:

1. θ (thê-ta)

Mỗi bit được thay bằng cách XOR tổng của 10 bit “gần kề” và chính nó. Xét bit tại (x,y,z) 10 bit này bao gồm:

5 bit cột “cạnh bên trái” A[x-1][0..4][z]
5 bit cột “chéo bên phải” A[x+1][0..4][z-1]

Lưu ý tất cả các chỉ số được mod cho kích thước của chiều của chỉ số đó, ví dụ A[-1][5][w] == A[4][0][0]

2 & 3. ρ (rô) và π (pi)

Ta tính mảng B từ mảng A:

Mảng offset r được tính theo bảng sau:

4. χ (chi)

Bước χ sử dụng mảng B đã được tính ở bước trước và đặt kết quả vào mảng A.

5. ι (yô-ta)

Với RC khác nhau tùy vào round hiện tại của hàm f (với SHA-3 có 24 round). RC được thể hiện theo bảng sau

Tạm kết

Như đã trình bày, các hàm băm mật mã thường chỉ được dùng trong các bối cảnh cần bảo vệ, chống thông tin giả mạo trước các đối tượng độc hại. Nếu ta không quá quan trọng việc bảo mật, nhưng quan trọng về tốc độ thực thi và độ phân phối tốt ta nên xem xét việc sử dụng hàm phi mật mã.

Phần 2 của bài viết sẽ trình bày về các hàm băm phi mật mã và ứng dụng.

Cám ơn các bạn đã theo dõi.

Bài viết được đồng hành bởi Quyền Phạm Thế. Thanks!