Tại sao chúng ta không thể chờ đợi các thuật toán chữ ký hậu lượng tử mới?

2026-07-09

25 phút đọc

RSA và ECC, những thuật toán mật mã mà tất cả chúng ta đã tin dùng trong nhiều thập kỷ, đều dễ bị tổn thương trước các cuộc tấn công từ máy tính lượng tử đủ mạnh. Những máy tính lượng tử như vậy hiện chưa tồn tại, nhưng có vẻ như chúng đang đến sớm hơn dự kiến. May mắn thay, giải pháp đã có sẵn: chuyển đổi sang mã hóa ML-KEM và chữ ký ML-DSA, vốn được thiết kế để chống lại các cuộc tấn công lượng tử. Chúng đã được Viện Tiêu chuẩn và Công nghệ Quốc gia Hoa Kỳ (NIST) chuẩn hóa vào năm 2024 sau một cuộc thi quốc tế công khai kéo dài tám năm.

Quá trình chuyển đổi sang mật mã hậu lượng tử hiện đang diễn ra mạnh mẽ. Tại thời điểm viết bài, phần lớn lưu lượng truy cập do Cloudflare xử lý đã sử dụng mã hóa ML-KEM, nhờ đó được bảo mật trước mối đe dọa đối với dữ liệu từ các cuộc tấn công "thu thập trước, giải mã sau" (harvest-now-decrypt-later). Nhưng mã hóa chỉ là một phần của phương trình: để bảo mật hoàn toàn trước các máy tính lượng tử có khả năng phá vỡ mật mã cổ điển, chúng tôi đặt mục tiêu triển khai chữ ký hậu lượng tử nhằm bảo vệ các hệ thống xác thực khỏi sự truy cập trái phép. Chúng tôi đang hướng tới năm 2029 để Cloudflare đạt được trạng thái bảo mật hậu lượng tử hoàn toàn.

ML-DSA, lược đồ chữ ký hậu lượng tử toàn diện tốt nhất được chuẩn hóa hiện nay, vẫn có những nhược điểm: kích thước trên đường truyền lớn hơn nhiều và nhiều thủ thuật chúng ta từng thực hiện với RSA và ECC đơn giản là không thể áp dụng với ML-DSA. Có những lược đồ chữ ký hậu lượng tử tốt hơn đang xuất hiện: tháng trước, NIST thông báo rằng họ đang đưa chín lược đồ chữ ký hậu lượng tử vào vòng thứ ba của chương trình "signatures on-ramp". Và một bản dự thảo tiêu chuẩn cho FN-DSA (trước đây là Falcon), vốn được chọn từ cuộc thi trước, dự kiến sẽ sớm được công bố.

Chúng tôi rất quan tâm đến những tiến bộ trong các thuật toán chữ ký hậu lượng tử và đã viết về sự phát triển của chúng trong các năm 2021, 2022, 2024 và 2025. Trong bài đăng trên blog này, chúng tôi sẽ mang đến cho bạn những cập nhật mới nhất một cách chi tiết.

Nhưng trước hết, chúng ta phải giải quyết vấn đề nan giải: Những thuật toán chữ ký mới này sẽ không sẵn sàng kịp thời cho quá trình chuyển đổi PQ — thậm chí còn lâu mới đạt được, như chúng ta sẽ thấy sau đây. Vấn đề đang đến quá nhanh để chúng ta có thể chờ đợi. ML-DSA đã có sẵn ngày hôm nay và nó sẽ phải đảm nhận vai trò cho đợt chuyển đổi đầu tiên. Như Eric Rescorla đã viết vào năm 2024:

Bạn phải ra trận với những thuật toán bạn đang có, chứ không phải những thuật toán bạn ước mình có.

Tuy nhiên, việc tìm kiếm các thuật toán chữ ký hậu lượng tử tốt hơn là rất quan trọng vì nhiều lý do, và chúng tôi tin chắc rằng đó vẫn là cách sử dụng tốt nhất các nguồn lực hạn chế của NIST.

Hãy cùng xem xét chi tiết các thuật toán chữ ký. Sau đó, chúng ta sẽ xem xét lộ trình sẵn sàng của chúng và lý do tại sao chúng ta vẫn cần chúng.

Các thuật toán chữ ký

Trong bảng dưới đây, chúng tôi so sánh các thuật toán chữ ký ứng viên đã tiến vào vòng thứ ba (đánh dấu bằng 🤔), với các thuật toán cổ điển dễ bị tấn công lượng tử (đánh dấu bằng ❌), và các thuật toán hậu lượng tử đã được chuẩn hóa (✅) hoặc sắp được chuẩn hóa (📝). Mỗi ứng viên đề xuất một vài biến thể. Chúng tôi liệt kê các biến thể phù hợp nhất với TLS, giao thức được sử dụng để bảo mật các kết nối trên Internet. Để khám phá tất cả các biến thể, hãy xem "vườn thú chữ ký" (signatures zoo) của Thom Wigger.

Một vài lưu ý thêm về bảng này: Hầu hết các ứng viên đều có nhiều biến thể ở mọi cấp độ bảo mật. Chúng tôi hiển thị các biến thể phù hợp nhất cho TLS ở cấp độ bảo mật 128-bit, tiêu chuẩn vàng cho bảo mật. Thời gian CPU được lấy từ "vườn thú chữ ký" vào tháng 6 năm 2026, được thu thập từ các tài liệu nộp vòng hai và những tiến bộ sau đó. Các ứng viên được phép thực hiện thay đổi cho vòng thứ ba, điều này sẽ ảnh hưởng đến các con số này. Một số sẽ cải thiện (cả về tính toán và kích thước), trong khi những số khác sẽ suy giảm để chống lại các cuộc tấn công mới. Hãy kiểm tra "vườn thú" để có những con số mới nhất. Chúng tôi đánh dấu việc ký của FN-DSA và SQIsign bằng ⚠️, vì cả hai đều khó triển khai theo cách nhanh chóng và an toàn trước các kênh bên thời gian (timing side-channel). Việc ký của LMS có ⚠️, vì việc ký LMS an toàn đòi hỏi phải duy trì trạng thái giữa các chữ ký, và thời gian ký được liệt kê giả định bộ nhớ đệm 32MB. Biến thể 128-24 của SLH-DSA được đánh dấu ⚠️ vì nó được thiết kế để tạo ra ít hơn 2^24 chữ ký.

Không có thuật toán "toàn năng"

Một điều nổi bật ngay lập tức là thuật toán chữ ký đường cong elliptic Ed25519 dễ bị tổn thương bởi lượng tử cho đến nay vẫn là lựa chọn toàn diện tốt nhất (bỏ qua lỗ hổng lượng tử của nó): nó có các chỉ số tốt nhất trong hầu hết mọi thước đo, bao gồm kích thước khóa công khai, kích thước chữ ký và thời gian ký. Nó chỉ bị đánh bại về thời gian xác minh, nhưng nó vẫn đủ nhanh cho đại đa số các ứng dụng.

Điều này khá khác biệt so với danh sách các thuật toán hậu lượng tử. Thay vì một thuật toán "toàn năng", chúng ta có khoảng hai loại lược đồ: các "chuyên gia" tiếp cận gần với các chữ ký đường cong elliptic đáng tin cậy của chúng ta trên một số chỉ số, nhưng lại có vấn đề ở các chỉ số khác, điều này khiến chúng trở nên tuyệt vời trong các kịch bản triển khai phù hợp. Sau đó là các "nhà tổng quát", chẳng hạn như ML-DSA, không hoạt động tốt bằng các đường cong elliptic trên tất cả các chỉ số, nhưng xét về nhược điểm thì khá cân bằng.

Các chuyên gia

Hãy bắt đầu với các chuyên gia.

SQIsign: chữ ký nhỏ / ký chậm

Nếu bạn chỉ nhìn vào số byte trên đường truyền, thì SQIsign trông giống như một sự thay thế hoàn hảo cho mật mã đường cong elliptic. Với chữ ký 148 byte và khóa công khai 65 byte, nó đánh bại RSA-2048. Thật không may, không có bữa trưa nào miễn phí: SQIsign có ba điểm yếu. Thứ nhất, nó là thuật toán phức tạp nhất trong danh sách. Thứ hai, việc tạo và xác minh chữ ký của nó khá chậm. Cuối cùng, rất khó để triển khai việc tạo chữ ký theo cách an toàn trước kênh bên thời gian và việc làm như vậy còn đi kèm với sự sụt giảm hiệu suất.

Nghe có vẻ không ổn, nhưng trước đây còn tệ hơn nhiều: khi chúng tôi nhìn lại vào năm 2024, vẫn chưa có bất kỳ triển khai nào an toàn trước kênh bên thời gian và việc xác minh chữ ký chậm hơn gấp 20 lần. Hơn nữa, đã có những tiến bộ đáng hoan nghênh trong việc đơn giản hóa lược đồ này.

Bất chấp những cải tiến đáng kể này, khó có khả năng việc ký (an toàn trước kênh bên) sẽ đủ nhanh trong tương lai gần để được sử dụng trong các trường hợp trực tuyến điển hình như bắt tay TLS. Tuy nhiên, đối với các trường hợp ngoại tuyến, chẳng hạn như chữ ký CA hoặc DNSSEC, nơi thời gian xác minh quan trọng hơn thời gian ký, SQIsign có thể có ứng dụng.

Nhưng chủ đề chúng ta thực sự nên thảo luận là bảo mật. SQIsign dựa trên isogeny. Khá nổi tiếng là SIKE, một thuật toán khác dựa trên isogeny, đã bị phá vỡ nghiêm trọng ở giai đoạn cuối của cuộc thi PQC đầu tiên của NIST, nơi đã chuẩn hóa ML-DSA. SIKE thường được đưa ra như một ví dụ cảnh báo cho thấy mật mã hậu lượng tử có thể bị phá vỡ đột ngột. Điều này đòi hỏi một chút sắc thái. Thứ nhất, đã có những lo ngại về bảo mật của SIKE, đặc biệt là các điểm xoắn (torsion points) dẫn đến việc bị phá vỡ. Do những lo ngại này, SIKE đã không được chọn để chuẩn hóa mà được hoãn lại cho một vòng đánh giá bổ sung trước khi nó bị phá vỡ. (Thực tế, đây là một ví dụ cho thấy quy trình của NIST hoạt động tốt). SQIsign không sử dụng các điểm xoắn và không có mối lo ngại tương tự như đối với SIKE.

Một đặc tính bảo mật đáng chú ý khác là các cuộc tấn công tốt nhất được biết đến trên SQIsign là tấn công vét cạn (brute force) chung, giống như các cuộc tấn công cổ điển trên các đường cong elliptic được chọn lọc kỹ lưỡng. Điều này khá khác biệt so với RSA, mạng lưới (lattices) và đa biến (multivariate) nơi các thuật toán tấn công đã dần cải thiện, đẩy các tham số về phía các chữ ký lớn hơn. Tuy nhiên, toán học đằng sau isogeny rất phong phú và so với các thuật toán khác, nó có rất nhiều bề mặt tấn công toán học. Dù vậy, bảo mật của nó có vẻ vững chắc hơn các thuật toán đa biến có cấu trúc mà chúng ta sẽ thảo luận sau.

SQIsign là một thuật toán có tiềm năng to lớn. Sẽ thật đáng tiếc nếu chuẩn hóa nó quá sớm. Với các tác giả, chúng tôi muốn chia sẻ danh sách mong muốn sau:

Lý tưởng nhất là thời gian xác minh được giảm hơn nữa, ngay cả khi phải đánh đổi với thời gian ký và kích thước chữ ký: chữ ký SQIsign đã đủ nhỏ và thời gian ký ngoại tuyến dù sao cũng có một chút dư địa.

Triển khai an toàn trước kênh bên thời gian nên là mặc định, đặc biệt nếu thời gian ký được giảm thêm, điều này sẽ thu hút một số ứng dụng ký trực tuyến.

Nhưng trên hết, mong muốn của chúng tôi là SQIsign được đơn giản hóa.

UOV: chữ ký nhỏ / khóa công khai khổng lồ

UOV (unbalanced oil and vinegar) là một thuật toán chữ ký đa biến cổ điển được đề xuất lần đầu vào năm 1999. Nó có chữ ký cực nhỏ: chỉ 96 byte. Sự đánh đổi là gì? Một khóa công khai khổng lồ: 66kB. Điều đó sẽ không giúp ích gì cho chứng chỉ máy chủ TLS, vốn có khóa công khai được truyền qua đường truyền khi thiết lập kết nối, nhưng nó sẽ hữu ích cho các trường hợp khóa công khai được phân phối trước.

Hãy lấy WebPKI làm ví dụ. Một trình duyệt điển hình tin tưởng khoảng một trăm chứng chỉ gốc (root certificates) và 30 nhật ký minh bạch chứng chỉ (certificate transparency logs), với tổng khóa công khai lên tới khoảng 8MB khi sử dụng UOV.

Các khóa công khai và chữ ký trong một kết nối TLS điển hình.

Vì chứng chỉ gốc được truyền đến máy khách ngoài băng tần (out of band), một ý tưởng là sử dụng chữ ký UOV ở đó. Nhưng đây không phải là một chiến thắng dễ dàng; do kích thước của nó, một chứng chỉ gốc UOV sẽ không thực tế để được ký chéo (cross-signed) khi gốc được sử dụng làm trung gian. Đồng thời, các chữ ký chéo và trung gian dù sao cũng trở nên kém hấp dẫn hơn với bất kỳ chữ ký hậu lượng tử lớn nào. Điều này khuyến khích nhiều chứng chỉ gốc được bao gồm trực tiếp với máy khách hơn. Điều này một lần nữa sẽ ủng hộ UOV, nhưng đến một mức độ nhất định: nếu số lượng chứng chỉ gốc tăng lên trên một nghìn, chúng ta sẽ phải xử lý hơn 66MB dữ liệu khóa, chiếm một phần đáng kể trong kích thước tải xuống của trình duyệt (ví dụ: 90MB cho Firefox 151).

Bảo mật đa biến

Còn về bảo mật thì sao? Qua nhiều năm, nhiều biến thể của UOV đã được đề xuất sử dụng một số cấu trúc toán học bổ sung để giảm kích thước của khóa công khai. Các lược đồ đa biến có cấu trúc này có hồ sơ theo dõi không đồng đều với các lược đồ như Rainbow và GeMMS bị phá vỡ khá nghiêm trọng. Điều quan trọng là phải phân biệt chúng với chính UOV, lược đồ có hồ sơ bảo mật tốt hơn nhiều, nhưng không phải là hoàn hảo.

Như với nhiều lược đồ mật mã, đã có những khó khăn trong những năm đầu khi các cuộc tấn công cơ bản và các cạm bẫy tham số được phát hiện. Trên thực tế, chữ "U" trong UOV là tàn dư của điều đó: nó viết tắt của "unbalanced" (không cân bằng), là một bản sửa lỗi cho sai lầm thiết lập tham số trong lược đồ "oil-and-vinegar" năm 1997 mà UOV dựa trên đó: lược đồ ban đầu có số lượng biến "oil" và "vinegar" bằng nhau trong hệ phương trình bậc hai được sử dụng làm khóa công khai, điều này hóa ra lại cho phép một cuộc tấn công. Trong trường hợp bạn tò mò về cái tên đầy màu sắc này: hệ phương trình chứa các số hạng "vinegar x vinegar" và "oil x vinegar", nhưng không có số hạng "oil x oil". Nó giống như giấm trộn với những giọt dầu nhỏ riêng biệt. Quay lại lịch sử: từ năm 2005 đến 2020 là một giai đoạn yên tĩnh đối với chữ ký đa biến: sự hiểu biết về UOV tăng lên, nhưng không có bất kỳ cuộc tấn công mới nào trên các tham số điển hình.

Điều này đã thay đổi vào năm 2020 với việc phát hiện ra cuộc tấn công giao điểm (intersection attack) dựa trên các ý tưởng của cuộc tấn công ban đầu vào "balanced oil-and-vinegar". Cuộc tấn công giao điểm loại bỏ khoảng 30 bit bảo mật khỏi tập tham số 128-bit được đề xuất lúc bấy giờ. Một đòn giáng đáng kể, nhưng không gây tử vong: việc điều chỉnh nhẹ các tham số sẽ giảm thiểu hoàn toàn cuộc tấn công, với sự gia tăng nhỏ về kích thước khóa và chữ ký.

Một cú sốc lớn hơn là ấn phẩm năm 2025 về ý tưởng sử dụng "wedges" để tấn công các lược đồ đa biến. Tác động ban đầu lên UOV là nhỏ: chỉ vài bit (một lần nữa ở cấp độ bảo mật 128-bit). Mối lo ngại là ý tưởng này xuất hiện từ hư không và không rõ phương pháp này có thể tiến xa đến đâu. Mối lo ngại đó phần nào được chứng minh là có cơ sở: ý tưởng "wedges" rất hiệu quả và một số cuộc tấn công tiếp theo đã được xây dựng dựa trên nó, làm giảm bảo mật khoảng 15 bit. Tuy nhiên, cũng trở nên rõ ràng rằng cuộc tấn công "wedges" và các khái quát hóa của nó có thể được coi là một trường hợp đặc biệt của cuộc tấn công giao điểm trên các vành bị cắt cụt (truncated rings) — do đó quen thuộc hơn chúng ta nghĩ. Một lần nữa, những cuộc tấn công này có thể được giảm thiểu với sự gia tăng chỉ nhỏ về kích thước khóa và chữ ký.