Sự phát triển của lược đồ chữ ký số kháng lượng tử dựa trên hàm băm

GIỚI THIỆU

Lược đồ chữ ký số dựa trên hàm băm (Hash Based Digital Signature Scheme) không dựa vào các bài toán khó giải như phân tích số nguyên hay logarit rời rạc mà dựa trên các tính chất an toàn của hàm băm mật mã, nên các lược đồ chữ ký số này có thể có khả năng kháng lượng tử [1].

Hiện nay, đã có các phiên bản lược đồ chữ ký số dựa trên hàm băm đã được áp dụng trong thực tế như XMSS tích hợp trong bộ thư viện mật mã OpenSSL, hay giao thức bảo mật WireGuard hoặc SPHINCS+ đã được chuẩn hóa trong tiêu chuẩn đề cử FIPS 205. Các lược đồ này đều có lịch sử phát triển từ các lược đồ chữ ký số một lần và lược đồ chữ ký số dựa trên hàm băm đơn giản. Vì vậy trong bài báo này nhóm tác giả sẽ cùng thảo luận quá trình phát triển các lược đồ chữ ký số này.

LƯỢC ĐỒ CHỮ KÝ SỐ MỘT LẦN

Trong khi đó, lược đồ chữ ký số một lần của Lamport - Diffie (LD-OTS) được Leslie Lamport đề xuất và tiếp tục được Buchmann cùng các cộng sự hoàn thiện [1]. Ý tưởng của lược đồ là tiết lộ một cách có chọn lọc các tiền ảnh là đầu ra của hàm một chiều f , tùy thuộc vào số bit của thông điệp cần ký. Chữ ký số σ cho một thông điệp n bit là một hàm của giá trị thông điệp có kích thước n ² . Quá trình ký không yêu cầu các đánh giá của hàm một chiều f , trong khi quá trình xác minh chữ ký số yêu cầu n đánh giá của hàm một chiều f .

Theo mô tả thuật toán thì quá trình ký số và tạo khóa của LD-OTS là rất hiệu quả nhưng có một số nhược điểm khiến nó không thực tế cho ứng dụng. Thứ nhất, khoá ký của LD-OTS chỉ được sử dụng một lần để chống giả mạo chữ ký. Thứ hai, kích thước của chữ ký số và khóa ký lại khá lớn.

Lược đồ chữ ký số một lần Winternitz (W-OTS), WOTS ^PRF , W-OTS ⁺ có kích thước chữ ký ngắn hơn đáng kể so với kích thước chữ ký trong LD-OTS. Ý tưởng là sử dụng một chuỗi bit trong khóa ký một lần để đồng thời ký một số bit trong giá trị thông điệp [1].

Lược đồ chữ số W-OTS sử dụng các tham số sau: tham số an toàn n ∈ N , độ dài thông điệp m , tham số Winternitz w ∈ N, w ≥ 2 (đây là số bit được ký đồng thời) và t ₁ =[n/w], t ₂ =[[logt ₁ +1+w]/w] , t=t ₁ +t ₂ ; một họ hàm F _n ≔ {f _k :{0,1} ⁿ →{0,1} ⁿ │ k ∈ {0,1} ⁿ } , với x ∈ {0,1} ⁿ , i ∈ N , định nghĩa f _k ⁱ (x)=f(f _k ^i-1 (x)) . Các tham số n, m, t ₁ , t ₂ ,t,w và họ hàm F _n là được công khai.

Quá trình sinh khóa, ký và kiểm tra chữ ký của lược đồ chữ ký số W-OTS yêu cầu t(2 ^w -1) phép tính sử dụng hàm f _k . Khóa bí mật và chữ ký có kích thước là tn bit. Kích thước của khóa công khai là (t+1)n bit. Các tham số w làm cho W-OTS rất linh hoạt. Nó cho phép cân bằng giữa độ dài của một chữ ký và cặp khóa. Nếu w được tăng lên, nhiều bit của giá trị băm không được xử lý đồng thời và độ dài chữ ký giảm. Tuy nhiên, có nhiều đánh giá của hàm một chiều f được yêu cầu trong quá trình sinh khóa và tạo chữ ký. Giảm w có tác dụng ngược lại. Việc sử dụng w = 2 đòi hỏi số lượng ít nhất đánh giá của hàm một chiều f cho mỗi bit.

Sau đó, có một phiên bản điều chỉnh nhỏ của W-OTS là WOTS ^PRF được đề xuất bởi Buchmann và cộng sự năm 2011 bằng việc thay đổi hàm băm f thành PRF (hàm giả ngẫu nhiên) có khóa f _k và sử dụng hơi khác so với W-OTS. Tuy nhiên, WOTS ^PRF được chứng minh không an toàn trong thực tế. Chính vì vậy, lược đồ W-OTS+ (một biến thể của lược đồ W-OTS) đã được Andreas Hulsing đề xuất. Lược đồ chữ ký số này có độ dài chữ ký ngắn hơn nhiều so với các biến thể khác và đạt được mức an toàn cao hơn. Lược đồ W-OTS+ được chứng minh là không thể giả mạo chữ ký mạnh dưới các tấn công thông báo lựa chọn thích nghi (an toàn SU-CMA) trong mô hình chuẩn, nếu hàm băm sử dụng trong lược đồ chữ ký số này là một hàm băm an toàn với các tính chất kháng tiền ảnh thứ hai, không thể phát hiện và một chiều. Trong lược đồ W-OTS+, hàm băm được sử dụng trong một chế độ lặp đặc biệt nên không yêu cầu họ hàm băm kháng va chạm mà vẫn đảm bảo được sự an toàn.

Đây cũng là một trong số những ưu điểm của lược đồ này so với các biến thể khác và giúp W-OTS ⁺ được sử dụng trong các lược đồ chữ ký số dựa trên hàm băm kháng lượng tử XMSS và SPHINCS. Năm 2016, Hulsing và cộng sự đã xác định được các kiểu tấn công đa mục tiêu vào các hàm băm liên quan đến XMSS và WOTS ⁺ . Để ngăn chặn các tấn công như vậy, các tác giả đề xuất các lược đồ XMSS-T và WOTS-T chống lại các cuộc tấn công đa mục tiêu (cả trong cài đặt và hậu lượng tử) với chi phí hiệu suất nhỏ và đã được chuẩn hóa trong RFC 8391 vào tháng 5/2018.

LƯỢC ĐỒ CHỮ KÝ SỐ MERKLE

Hạn chế của các lược đồ chữ ký số một lần 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. 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ế. Năm 1979, Ralph Merkle đề xuất sử dụng một cây băm nhị phân đầ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. Merkle gọi cấu trúc này là cây xác thực và thường được gọi là cây băm hoặc cây Merkle. Kết quả là lược đồ chữ ký Merkle (MSS). 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 nhị phân độ cao H , 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. Nút cha được tính bằng cách tính giá trị băm của hai nút con của nó. Việc xây dựng đường dẫn xác thực của một lá bao gồm tất cả các nút trên đường đi của nó về nút gốc.

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à H , lược đồ chữ ký số MSS có thể tạo ra 2 ^H chữ ký số, mỗi chữ ký ứng với một khóa xác minh một lần. Tuy nhiên, để lưu trữ tất cả 2 ^H khóa một lần là không thể. Vì vậy, khóa cần được tạo ra theo yêu cầu bằng cách sử dụng một bộ tạo số giả ngẫu nhiên. Bảng 1 chỉ ra mức an toàn cho một số chiều dài đầu ra n của hàm băm. Bảng này cũng chỉ ra giá trị lớn nhất cho H sao cho mức an toàn đó được duy trì.

Bảng 1. Mức an toàn của lược đồ chữ ký MSS

Năm 2005, Garcia đã chứng minh rằng tính an toàn của lược đồ MSS phụ thuộc vào khả năng kháng va chạm của hàm băm và độ an toàn của OTS cơ bản được sử dụng. Do đó, Buchmann và các cộng sự đã xây dựng lược đồ chữ ký Merkle mở rộng (XMSS), sau đó được Hulsing và các cộng sự chuẩn hóa thành chuẩn Internet trong [2]. Lược đồ chữ ký số XMSS được xây dựng dựa trên lược đồ chữ ký số MSS. XMSS được xem là một lược đồ chữ ký số kháng lượng tử hiệu quả với những giả định an toàn tối thiểu. Một trong những lợi ích chính của XMSS với WOTS ⁺ là nó không dựa vào tính kháng va chạm mà dựa vào khả năng kháng tiền ảnh thứ hai của các hàm băm.

Năm 2012, XMSS ⁺ được Hulsing và cộng sự đề xuất với mục đích tối ưu hóa đặc biệt XMSS nhằm sử dụng trên các tài nguyên hạn chế. XMSS ⁺ sử dụng hai lớp các cây XMSS có cùng chiều cao với XMSS ban đầu, tạo chữ ký phân tán và chữ ký một lần WOTS ^PRF . Năm 2013, Hulsing và cộng sự công bố một phiên bản mới khác của XMSS gọi là XMSSMT với ý tưởng chuỗi cây giống XMSS ⁺ nhưng kết hợp với những cải tiến của thuật toán BDS (Binary Decision Tree) từ XMSS ⁺ và nhiều lớp của XMSS với chiều cao khác nhau trên mỗi lớp. XMSS ^MT sử dụng chữ ký một lần WOTS ^PRF . Năm 2016, Hulsing và cộng sự đã giới thiệu cả lược đồ chữ ký nhiều lần mới XMSS-T và chữ ký một lần WOTS-T. WOTS-T được đề xuất để chống lại các cuộc tấn công đa mục tiêu làm giảm mức độ phức tạp của việc phá vỡ một hàm băm. XMSS-T dựa trên XMSS ^MT với một số thay đổi như sử dụng chữ ký một lần WOTS-T, có lược đồ địa chỉ nhằm thắt chặt an toàn. XMSS-T được thay thế XMSS trong dự thảo tiêu chuẩn và xuất bản với tên gọi RFC 8391 [2].

Một nhánh khác của lược đồ chữ ký số Merkle là lược đồ chữ ký số một lần LMS và phiên bản siêu cây của LMS là HSS được công bố trong tiêu chuẩn RFC8554. Thay vì sử dụng WOTS+ như trong XMSS thì LMS vẫn sử dụng lược đồ WOTS kết hợp cây Merkle trong kiến trúc của mình.

LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN HÀM BĂM CÓ TRẠNG THÁI VÀ CHỮ KÝ SỐ DỰA TRÊN HÀM BĂM KHÔNG TRẠNG THÁI

XMSS có một nhược điểm lớn là có trạng thái (stateful): phải nhớ cặp khóa dùng một lần nào đã được sử dụng để tạo chữ ký [2]. Ngoài ra, khi một bản sao trước đó của trạng thái khóa được khôi phục hoặc khi trạng thái khóa bị mất, tính an toàn của các lược đồ trạng thái sẽ nhanh chóng suy giảm. Vì trạng thái này, việc sử dụng cùng một cặp khóa trên các thiết bị khác nhau cũng rất khó quản lý. XMSS không phải lúc nào cũng có thể thay thế RSA hoặc ECDSA.

Vào năm 2015, SPHINCS được tạo ra để loại bỏ trạng thái và thay thế cho RSA, ECDSA [3]. Điều này đạt được bằng cách chọn ngẫu nhiên các nút lá để ký, xác suất sử dụng cùng một lá nhiều lần là đủ nhỏ để thực tế không tồn tại. Năm 1986, Goldreich đã đề xuất một lược đồ chữ ký dựa trên hàm băm không trạng thái (stateless) với các chữ ký kích thước cực lớn. SPHINCS giải quyết vấn đề này bằng cách xây dựng một cây trong đó mỗi nút trên thực tế là một cây Merkle. Đây chính là lược đồ quản lý khóa của SPHINCS dựa trên lược chữ ký số một lần WOTS ⁺ và kiến trúc cây HORST [4].

Mặc dù vậy, kiến trúc cây HORST làm cho SPHINCS có kích thước chữ ký lớn (41 KB) và thời gian tính toán lâu. Một kiến trúc cây cải tiến của HORST đã được phát triển để khắc phục nhược điểm về kích thước chữ ký được công bố là FORST, kiến trúc cây này đã được áp dùng vào phiên bản cải tiến của SPHINC là SPHINCS ⁺ , đây là lược đồ chữ ký số đã được đệ trình cho dự án Mật mã kháng lượng tử của NIST, trở thành thuật toán được lựa chọn năm 2022 và đưa vào dự thảo tiêu chuẩn Mật mã kháng lượng tử FIPS 205 [3, 4]. Trong dự thảo SPHINCS ⁺ được gọi là SLH-DSA. SLH-DSA có điểm mới so với SPHINCS+ được lựa chọn là sử dụng WOTS ^PRF và FORS ^PRF cho lược đồ chữ ký số một lần WOTS ⁺ và lược đồ chữ ký số nhiều lần FORS trong quá trình sinh khóa bí mật; hàm giả ngẫu nhiên PRF, hàm băm cũng có những thay đổi nhằm tăng tính an toàn cho SLH-DSA.

TIỀM NĂNG ỨNG DỤNG CỦA LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN HÀM BĂM

Lược đồ chữ ký số dựa trên hàm băm cùng với lược đồ ký số dựa trên lưới toán học là hai hướng phát triển chữ ký số kháng lượng tử đã được NIST công bố chiến thắng trong cuộc thi lựa chọn tiêu chuẩn mật mã kháng lượng tử với các đại diện là SPHINCS ⁺ , CRYSTALS-Dilithium và FALCON. Mặc dù đã được công bố từ lâu nhưng các lược đồ chữ ký số dựa trên lưới mới được chú ý và quan tâm nghiên cứu 5 năm gần đây. Các công trình phân tích sự an toàn của các lược đồ này còn rất thiếu và đang trong tình trạng cần được đào sâu nghiên cứu. Trong khi đó, các lược đồ chữ ký số dựa trên hàm băm đã có được chứng minh về độ an toàn dựa trên rất nhiều nghiên cứu về hàm băm trong thế kỷ này.

Chính vì lý do trên, lược đồ chữ ký số dựa trên hàm băm đã được đưa vào ứng dụng trong các giao thức bảo mật như TLS 1.3 và WireGuard . Đối với Việt Nam nói chung và ngành Cơ yếu nói riêng việc nghiên cứu, đảm bảo độ an toàn các lược đồ chữ ký dựa trên hàm băm và ứng dụng các lược đồ này vào trong các sản phẩm bảo mật mới có khả năng kháng lượng tử là hướng đi lâu dài và vững chắc.

KẾT LUẬN

Bài viết đã trình bày chi tiết các đặc điểm chính của một số lược đồ chữ ký số dựa trên hàm băm điển hình trong lịch sử phát triển của dòng lược đồ chữ ký số này, như lược đồ OTS đơn giản như Lamport hay W-OTS, đến các lược đồ tân tiến hiện nay như XMSS hay SPHINCS+. Qua đó cho thấy tiềm năng ứng dụng cũng như tính khả thi của phiên bản SPHINCS+ trước mối đe dọa lớn của máy tính lượng tử.