Cây băm Merkle và ứng dụng

09:00 | 09/03/2023 | MẬT MÃ DÂN SỰ

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,ilà 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.

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ã)

‹ › ×

Tin liên quan

Ứng dụng cây Merkle và công nghệ blockchain cho cơ sở dữ liệu phân tán

18:00 | 22/09/2023

Do lưu giữ những thông tin quan trọng nên cơ sở dữ liệu thường nằm trong tầm ngắm của nhiều tin tặc. Ngày nay, các cuộc tấn công liên quan đến cơ sở dữ liệu để đánh cắp hay sửa đổi thông tin càng trở nên khó lường và tinh vi hơn, vì vậy việc quản lý cơ sở dữ liệu đặt ra những yêu cầu mới với các tổ chức, doanh nghiệp. Trong hệ thống phân tán, khi dữ liệu được phân mảnh và phân phối trên các vị trí khác nhau có thể dẫn đến khả năng mất toàn vẹn của dữ liệu. Thông qua sử dụng cây Merkle và công nghệ Blockchain ta có thể xác minh tính toàn vẹn của dữ liệu. Trong bài viết này, nhóm tác giả sẽ trình bày các nghiên cứu về ứng dụng cây Merkle và công nghệ Blockchain để bảo đảm tính toàn vẹn dữ liệu cho cơ sở dữ liệu phân tán, đồng thời đảm bảo hiệu năng của hệ thống.

Phân tích 64 lược đồ hàm nén trong mô hình hàm băm dựa trên mã khối

13:00 | 12/08/2019

Tóm tắt— Cấu trúc cho các hàm băm lặp dựa trên mã khối đã được nghiên cứu, trong đó kích thước giá trị băm bằng kích cỡ khối và kích cỡ khóa đã được quan tâm nghiên cứu rộng rãi. Bài báo này, chúng tôi chi tiết 64 lược đồ theo mô hình tổng quát được đề xuất bởi B. Preneel và các đồng sự, dựa trên 5 tấn công cơ bản. Chi tiết hóa phân loại lược đồ theo số lượng các biến đầu vào và thực hiện đánh giá độ an toàn của một trong số các lược đồ an toàn theo quan điểm thám mã vi sai.

Đề xuất S-hộp có tính chất mật mã tốt cho hoán vị của hàm băm Keccak

11:00 | 01/02/2021

CSKH-01.2020. Tóm tắt—Keccak là hàm băm giành được chiến thắng trong cuộc thi SHA-3 của Viện Tiêu chuẩn và Công nghệ Mỹ (NIST) tổ chức. Có nhiều tấn công thám mã khai thác bậc đại số thấp trong hoán vị của hàm băm này. Chính những kết quả này mà nhóm tác giả thiết kế Keccak đã tăng số vòng từ 18 lên 24 trong hoán vị của nó. Trên cơ sở đó, bài báo tập trung phân tích tính chất đại số của hoán vị Keccak-f trong hàm băm này, sau đó đề xuất một thành phần S-hộp mới có tính chất mật mã tốt để sử dụng trong hoán vị của hàm băm Keccak.

Giới thiệu về thuật toán hàm băm Whirlpool

14:00 | 07/12/2017

Hàm băm Whirlpool được đề xuất trong dự án NESSIE vào năm 2000, hàm băm này dựa trên mã khối và được đánh giá là an toàn. Hàm nén sử dụng mã khối W (được xem như là một biến thể của AES) được thiết kế dành cho hàm băm và không sử dụng cho hàm mã hóa nhằm khắc phục điểm yếu của các hàm băm dựa trên mã khối.

Tin cùng chuyên mục

Giới thiệu tiêu chuẩn về phương pháp kiểm thử và phân tích cho các bộ tạo bit ngẫu nhiên

15:00 | 17/06/2024

Các ứng dụng mật mã đòi hỏi các số ngẫu nhiên cho nhiều tác vụ khác nhau. Một bộ tạo bit ngẫu nhiên mật mã mạnh phù hợp với các ứng dụng mật mã chung được kỳ vọng sẽ cung cấp các chuỗi bit đầu ra không thể phân biệt với bất kỳ khả năng nỗ lực tính toán thực thể và trên thực tế bất kỳ kích thước mẫu từ các chuỗi bit có cùng độ dài được lấy ngẫu nhiên một cách đồng nhất. Hơn nữa, một RBG như vậy được kỳ vọng sẽ cung cấp khả năng tăng cường an toàn. Bài viết này sẽ giới thiệu tới độc giả những nội dung chính trong tiêu chuẩn ISO/IEC 20543:2019 về phương pháp kiểm thử và phân tích cho các bộ tạo bit ngẫu nhiên.

Giới thiệu Tiêu chuẩn TCVN 13178-4:2020

13:00 | 29/12/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ớ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ọ.

Hội nghị tập huấn về mật mã dân sự 2023

16:00 | 21/07/2023

Ngày 20/7, tại Thành phố Hồ Chí Minh, Cục Quản lý mật mã dân sự và Kiểm định sản phẩm mật mã, Ban Cơ yếu Chính phủ đã tổ chức Hội nghị tập huấn về mật mã dân sự năm 2023 và triển khai Nghị định số 32/2023/NĐ-CP ngày 09/6/2023 của Chính phủ.

Lấy ý kiến xây dựng Báo cáo tổng kết thi hành Nghị định số 58/2016/NĐ-CP

10:00 | 24/03/2023

Sau một thời gian triển khai thực hiện, Nghị định số 58/2016/NĐ-CP quy định 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ự gặp phải một số hạn chế, bất cập. Để có cơ sở báo cáo, đề nghị Chính phủ sửa đổi, bổ sung, Ban Cơ yếu Chính phủ gửi văn bản đề nghị tổ chức, doanh nghiệp cung cấp thông tin để xây dựng Báo cáo tổng kết thi hành Nghị định.