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(di ) đố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.
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à H1, H2, H3, H4.
- 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.
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).
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.
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 2T cặp khóa một lần (ví dụ khóa W-OTS) (Xi Yi) với 0 ≤ i < 2T. Để 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 (Yi ) của các khóa xác minh một lần. Trong đó Xi là các khóa ký và Yi là các khóa xác minh một lần. Các ký hiệu nj,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 2T 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.
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.
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. |
TS. Nguyễn Văn Nghị, Lê Thị Bích Hằng, Võ Xuân Luých (Học viện Kỹ thuật mật mã)
18:00 | 22/09/2023
13:00 | 12/08/2019
11:00 | 01/02/2021
14:00 | 07/12/2017
10:00 | 03/04/2024
Với vai trò là Cơ quan mật mã quốc gia, Ban Cơ yếu Chính phủ đã chỉ đạo tổ chức nghiên cứu, xây dựng thuật toán mã khối dân sự để thiết kế, chế tạo các sản phẩm bảo mật, an toàn thông tin phục vụ phát triển kinh tế số, xã hội số.
15:00 | 20/09/2023
Xác thực các đối tác truyền thông là một trong những dịch vụ mật mã quan trọng nhất. Truyền thông được xác thực ẩn danh liên quan đến việc ẩn định danh của một thực thể được xác thực với đối tác truyền thông của nó và/hoặc với bên thứ ba, trong khi vẫn có tài sản mà người xác minh có thể sử dụng để xác định một cách đáng tin cậy đối tác truyền thông của họ. Các cơ chế xác thực thực thể ẩn danh được thiết kế để hỗ trợ các truyền thông ẩn danh đó. Các cơ chế này được định nghĩa là sự trao đổi thông tin giữa các thực thể và khi cần là sự trao đổi với bên thứ ba đáng tin cậy. Nội dung bài báo sẽ giới thiệu tổng quan về kỹ thuật xác thực thực thể ẩn danh và các nội dung chính của Tiêu chuẩn TCVN 13178-1:2020 Công nghệ thông tin – Các kỹ thuật an toàn – Xác thực thực thể ẩn danh.
10:00 | 14/04/2023
Sau 5 năm ban hành và triển khai, Nghị định số 53/2018/NĐ-CP ngày 16/4/2018 của Chính phủ sửa đổi, bổ sung Nghị định số 58/2016/NĐ-CP ngày 01/7/2016 của Chính phủ quy định chi tiết về kinh doanh sản phẩm, dịch vụ mật mã dân sự và xuất khẩu, nhập khẩu sản phẩm mật mã dân sự đã cho thấy nhiều bất cập cần sửa đổi, bổ sung.
10:00 | 17/02/2023
Trong chiến dịch bảo vệ dữ liệu đang diễn ra của chính phủ Mỹ để chuẩn bị bước vào thời đại máy tính lượng tử trong tương lai, một cuộc tấn công mới và mạnh mẽ đã sử dụng máy tính truyền thống duy nhất để phá vỡ hoàn toàn một ứng cử viên vòng 4 nêu bật lên những rủi ro liên quan đến việc tiêu chuẩn hóa thế hệ thuật toán mã hóa tiếp theo.