Cây băm Merkle là một kiến trúc dữ liệu đã được công bố từ thập niên 70 của thế kỉ trước, tuy nhiên những năm gần đây mới được đưa vào ứng dụng nhiều trong hệ thống công nghệ thông tin. Bài viết này sẽ trình bày chi tiết về cách thức xây dựng, các lợi ích chính và một số ứng dụng phổ biến của cây băm Merkle trong bảo mật thông tin.

GIỚI THIỆU

Trong [1], cây băm Merkle được giới thiệu trong luận án Tiến sỹ của chính Ralph Charles Merkle tại trường đại học Standford vào năm 1979. Về cơ bản, cây băm Merkle là một cây nhị phân bao gồm các nút có thứ tự được thiết lập từ một dãy các đối tượng dữ liệu (d1, d2,..., dn) sử dụng một hàm băm mật mã H. Các nút lá của cây là các giá trị băm H(d_i ) đối với 1 ≤ i ≤ n. Các nút khác của cây băm Merkle đều sẽ bao gồm hai nút con, một nút con bên trái (left) và một nút con bên phải (right). Các nút dưới cùng của cây là các nút lá, các nút tiếp theo sẽ chứa giá trị băm H(left,right), trong đó left là giá trị băm chứa ở nút bên trái, right là giá trị băm lưu ở nút bên phải và được ghép nối với nhau. Nút trên cùng của cây được gọi là nút gốc hay root.

CÁCH THỨC XÂY DỰNG CÂY BĂM MERKLE

Quá trình xây dựng cây băm Merkle được trình bày thông qua ví dụ trong Hình 1. Đầu vào chúng ta có dữ liệu 1, 2, 3, 4: đây có thể là các tập tin dữ liệu hoặc các khối dữ liệu. Cách thức xây dựng cây băm Merkle được thực hiện theo các bước sau:

- Tiến hành băm các dữ liệu 1, 2, 3, 4 với một hàm băm mật mã H để thu được các giá trị băm là H₁, H₂, H₃, H_4.

- Lưu các giá trị băm vào các nút lá cây Merkle. Với hai nút lá thì thành lập được một nút tiếp theo của cây băm Merkle. Các nút này chứa nội dung là giá trị băm H(left,right), trong đó thì left là giá trị nút bên trái và right là giá trị nút bên phải của nút vừa thành lập.

- Tiến hành xây dựng các nút còn lại của cây băm Merkle với nội dung là giá trị băm H(left,right) để thu được nút cuối cùng gọi là nút gốc hay root.

Hình 1. Mô tả cách xây dựng cây băm Merkle

Với số lượng dữ liệu là lũy thừa của 2 thì cây Merkle được xây dựng tuần tự như các bước đã nêu trên. Trường hợp khác thì các nút lá còn thiếu của cây Merkle sẽ nhận giá trị băm của dữ liệu cuối cùng.

LỢI ÍCH CÂY BĂM MERKLE

Trong [2, 3], các tác giả nêu ra ba lợi ích chính của cây băm Merkle như sau:

- Cung cấp cơ chế xác minh tính toàn vẹn và hợp lệ của dữ liệu dựa vào tính chất an toàn của hàm băm mật mã trong kiến trúc. Đối với tập dữ liệu xây dựng cây băm Merkle thì chỉ cần kiểm tra nút gốc cây băm để xác định có sự thay đổi hay không. Ngoài ra, cây băm Merkle cũng cung cấp cơ chế xác định đơn lẻ một dữ liệu bị thay đổi hay không thông qua việc lưu giá trị băm theo đường dẫn xác thực.

- Đòi hỏi ít bộ nhớ hoặc dung lượng ổ đĩa vì cây băm Merkle có thể được xây dựng dễ dàng nhanh chóng và chỉ phải lưu trữ giá trị nút gốc hoặc đường dẫn xác thực.

- Tiết kiệm băng thông với thông tin xác minh được gửi đi (chỉ cần gửi giá trị nút root hoặc đường dẫn xác thực).

MỘT SỐ ỨNG DỤNG CHÍNH CỦA CÂY BĂM MERKLE TRONG BẢO MẬT THÔNG TIN

Xác minh tính toàn vẹn và hợp lệ của dữ liệu chia sẻ

Người dùng, doanh nghiệp hoặc tổ chức thực hiện lưu trữ và chia sẻ một tập tin dữ liệu lớn (có thể được chia làm nhiều phần) trên 1 máy chủ tin cậy. Vấn đề đặt ra là máy chủ cần cung cấp cơ chế xác minh tính toàn vẹn và hợp lệ của tập tin. Giải pháp thường được sử dụng là áp dụng hàm băm mật mã như trong Hình 2.

Trong giải pháp này, máy chủ lưu trữ có gắn kèm thêm mã băm của tập tin để người dùng khi tải về có thể xác minh tính toàn vẹn và hợp lệ của tập tin.

Hình 2. Sử dụng hàm băm trong xác minh toàn vẹn tập tin

Ngày nay, để chống sự tập trung và độc quyền sở hữu dữ liệu của các tập đoàn lớn cung cấp dịch vụ máy chủ lưu trữ thì mô hình mạng phân tán (Git, IPFS, BitTorrent, Cassandra…) đã và đang được sử dụng ngày càng phổ biến hơn (Hình 3).

Trong mô hình mạng phân tán thì máy chủ tin cậy có thể chỉ lưu trữ giá trị băm của tập tin chia sẻ và đóng vai trò xác minh tính toàn vẹn tập tin dữ liệu. Nội dung tập tin dữ liệu được chia thành nhiều phần và lưu trữ trong các peer (máy tính hay các node) trong mô hình mạng.

Cách tiếp cận cơ chế xác minh tính toàn vẹn tập tin (có kích thước lớn) lưu trữ trong cả hai mô hình mạng tập trung và phi tập trung đều tồn tại các nhược điểm sau:

(1) Chỉ có thể tiến hành xác minh sau khi thu thập đủ toàn bộ tập tin: nếu dữ liệu phân tán trên hàng ngàn peer, sẽ có vấn đề là một số phần sẽ được gửi đến sớm, và một số sẽ đến muộn. Việc chỉ chờ đợi toàn bộ được gửi đến để có thể xác thực là sự lãng phí thời gian.

(2) Không thể xác định được thành phần nào sai lệch (do chỉ kiểm tra khi toàn bộ các thành phần đã được gộp lại).

(3) Tính đồng bộ quá cao: chỉ 1 bit thay đổi trong tập tin cũng dẫn đến việc tính toán lại mã băm toàn bộ tệp và lưu trữ lại tại máy chủ.

(4) Máy chủ lưu trữ mã băm là điểm yếu trong cả hai mô hình mạng.

Hình 3. Lưu trữ, chia sẻ tập tin trong mô hình mạng phân tán

Một cách tiếp cận vấn đề khác là có thể dùng hàm băm mật mã để tính mã băm từng phần. Việc lưu trữ mã băm cùng từng phần trên máy chủ có thể là giải pháp cho vấn đề (1), (2) bằng cách xác minh từng phần và một phần nào đó của vấn đề (3) vì có thể chỉ cập nhật lại phần dữ liệu thay đổi. Tuy nhiên, vẫn còn những nhược điểm như: tăng khả năng trùng lặp mã băm; toàn bộ mạng vẫn cần dựa vào một máy chủ. Việc máy chủ bị giả mạo (bị chặn bắt phản hồi giá trị băm rồi gửi lại mã băm khác cho người dùng) phản hồi mã băm sai lệch là một vấn đề mà cách tiếp cận này chưa giải quyết.

Cách thức sử dụng cây băm Merkle sẽ giải quyết trọn vẹn tất cả các vấn đề trên. Máy chủ sẽ thiết lập được một cây băm Merkle từ các phần của tập tin (Hình 4). Máy chủ chỉ hiển thị thông tin về nút gốc của cây băm Merkle. Người dùng tải về một phần nào đó của tập tin thì có thể gửi yêu cầu xác minh phần này có thuộc tập tin hay không tới cho máy chủ. Khi này máy chủ sẽ phản hồi lại cho máy người dùng thông tin đường dẫn kiểm tra. Dựa trên thông tin đường dẫn kiểm tra nhận được người dùng có thể tính toán được nút gốc cây băm và so sánh giá trị nút gốc công bố trên máy chủ: hai giá trị giống nhau thì khẳng định thành phần đã tải về thuộc tập tin quan tâm, còn khác nhau thì sẽ loại bỏ thành phần tập tin đã tải về.

Hình 4. Sử dụng cây băm Merkle trong xác minh dữ liệu chia sẻ

Ví dụ: User1 trong mạng phân tán muốn xác minh rằng đoạn Y tồn tại trong tệp tin của User2 và chưa bị sửa đổi (User2 đã chia sẻ tập tin qua mạng phân tán và thông tin xác thực là cây băm Merkle trên máy chủ tin cậy). User1 gửi yêu cầu xác minh tới máy chủ, khi này máy chủ sẽ trả về thông tin H(Z) và H(WX), hay chính là đường dẫn kiểm tra. Sau đó, User1 có thể tính toán:

- H(YZ) từ H(Y) là mã băm của đoạn dữ liệu Y User1 có và H(Z) mà máy chủ tin cậy đã cung cấp.

- H(WXYZ) từ H(YZ) mà User1 vừa tính toán và H(WX) mà máy chủ tin cậy đã cung cấp.

Cuối cùng, User1 có thể so sánh H(WXYZ) được tính với mã băm gốc ban đầu được sử dụng để xác minh trên máy chủ tin cậy thuộc mạng phân tán. Nếu hai giá trị hàm băm giống nhau thì đoạn dữ liệu là hợp lệ và toàn vẹn, ngược lại thì User1 có thể hủy đoạn dữ liệu này và yêu cầu đoạn tương tự từ một máy ngang hàng khác trong mạng. Quá trình này còn được gọi là bằng chứng kiểm toán.

Hình 5. Xác minh dữ liệu bằng cây băm Merkle

Để giúp người dùng có thể xác thực được nguồn gốc tập tin chia sẻ trên máy chủ thì có thể kết hợp kỹ thuật ký số với cây băm Merkle. Cụ thể người sở hữu dùng khóa riêng của mình để ký vào nút gốc của cây băm và yêu cầu máy chủ tin cậy cung cấp hai giá trị là nút gốc cây băm Merkle cùng chữ ký của chính anh ta cho nút gốc này.

Xây dựng lược đồ ký số một lần MSS và XMSS

Hạn chế của các lược đồ chữ ký số một lần (OTS) là mỗi cặp khóa chỉ được sử dụng một lần duy nhất để ký cho một thông điệp dữ liệu. Do đó, các lược đồ chữ ký số này là không phù hợp cho hầu hết các tình huống thực tế. Để khắc phục vấn đề này thì trong [4], Merkle đã đề xuất một lược đồ ký số với tên gọi MSS (Merkle Signature Scheme). MSS sử dụng một cây băm Merkle đầy đủ để có thể gắn nhiều khóa ký một lần với một khóa kiểm tra duy nhất, gốc của cây băm.

Lược đồ ký số MSS hoạt động với bất kỳ hàm băm mật mã và lược đồ chữ ký một lần nào. MSS sử dụng một cây băm Merkle độ cao T như thể hiện trong Hình 6, trong đó mỗi nút lá tương ứng với giá trị băm của một khóa công khai dùng một lần. Theo định nghĩa, lá bắt đầu ở độ cao 0, trong khi gốc là nơi sinh ra khóa công khai MSS và ở độ cao T.

Hình 6. Cây băm Merkle trong ký số MSS với độ cao T=4

Bước tiếp theo là tạo 2^T cặp khóa một lần (ví dụ khóa W-OTS) (X_i Y_i) với 0 ≤ i < 2^T. Để xác định khóa công khai MSS, xây dựng một cây băm Merkle như sau: xem mỗi khóa xác minh một lần Yi như là một chuỗi bit, các lá của cây xác thực là các giá trị băm H (Y_i ) của các khóa xác minh một lần. Trong đó X_i là các khóa ký và Y_i là các khóa xác minh một lần. Các ký hiệu n_j,i là viết tắt của nút thứ i trên độ cao j.

Chữ ký số MSS cho một lá bao gồm: chỉ số của lá, chữ ký số một lần của thông điệp, khóa xác minh một lần và đường dẫn xác thực. Điều này cho phép người kiểm tra xác thực được chữ ký số một lần cũng như khóa xác minh một lần của người ký. Với độ cao của cây là T, lược đồ chữ ký số MSS có thể tạo ra 2^T chữ ký số, mỗi chữ ký ứng với một khóa xác minh một lần.

Trong [5], lược đồ ký số Merkle mở rộng hay còn gọi là XMSS (eXtended Merkle Signature Scheme) được đưa ra với cách thức hoạt động dựa trên cây XMSS mà được xây dựng từ kiến trúc cây băm Merkle, cây L và lược đồ ký số WOTS. Lược đồ ký số này đã được tích hợp trong thư viện mật mã OpenSSL và sử dụng trong cài đặt phiên bản mới của các giao thức bảo mật phổ biến là TLSv1.3 và Wireguard.

Xác minh tính nhất quán và đồng bộ dữ liệu

Các hệ thống phân tán chỉ cho phép dữ liệu được thêm vào mà không thể xoá đi. Vì vậy, cây băm Merkle rất hữu ích trong việc xác thực bất cứ phiên bản mới vào của dữ liệu có chứa các dữ liệu cũ hay không.

Cây băm Merkle có thể thay thế cho việc so sánh toàn bộ dữ liệu để xác định thay đổi. Người dùng chỉ cần so sánh các mã băm trong cây và một khi có nút lá thay đổi, chỉ dữ liệu đó cần đồng bộ hoá với các nút khác trong mạng.

KẾT LUẬN

Bài viết đã trình bày chi tiết và chuyên sâu về hầu hết các khía cạnh của cây băm Merkle. Với các ứng dụng và lợi ích của cây băm Merkle đã đưa ra thì thấy rằng đây là một kiến trúc dữ liệu rất tiềm năng và hiệu quả tốt khi được áp dụng vào trong bảo mật dữ liệu trong hệ thống mạng công nghệ thông tin.

TÀI LIỆU THAM KHẢO 1. Ralph Charles Merkle, “Secrecy, authentication, and public key systems. Electrical Engineering,” PhD. Thesis, Stanford University, 1979. 2. Satwik Kansal, “Merkle Trees: What They Are and the Problems They Solve”, codementor.io, 2020. 3. Marc Clifton, “Understanding Merkle Trees - Why Use Them, Who Uses Them, and How to Use Them”, codeproject.com, 2017. 4. R. Merkle, “A certified digital signature. In Advances in Cryptology - CRYPTO’89”, number 1462 in LNCS, pp. 218-238. Springer, 1989. 5. Hulsing, Butin, Gazdag and Rijneveld, “XMSS: Extended Hash-Based Signatures”, RFC8391, 2018.