Phản bác cách tính mức độ bảo mật Kyber-512 của NIST
(blog.cr.yp.to)- Trọng tâm của phê bình là trong quá trình thúc đẩy Kyber-512 thành tiêu chuẩn mật mã hậu lượng tử, NIST đã tính sai chi phí tấn công, qua đó thổi phồng mức độ bảo mật
- Vấn đề nằm ở chỗ cần cộng chi phí tính toán và chi phí truy cập bộ nhớ cho mỗi lần lặp, nhưng NIST dường như đã xử lý chúng như thể đem nhân, rồi cộng “40 bit bảo mật bổ sung” vào ước tính 2^137 của Matzov
- Kyber-512 được trình bày ở mức 2^118 theo Core-SVP, và NIST cố gắng đưa nó khớp với chuẩn AES-128, tức khoảng 2^143 bit operations, nhưng bị phê bình rằng đơn vị và ý nghĩa của các con số được kết hợp không tương thích
- Trong khi Kyber chỉ cung cấp các lựa chọn tham số giới hạn như Kyber-512, Kyber-768, Kyber-1024, NTRU và NTRU Prime được so sánh là cung cấp các lựa chọn kích thước và mức bảo mật dày hơn
- Việc chuẩn hóa Kyber-512 có các vấn đề như sự bất định trong phân tích tấn công, mô hình chi phí bộ nhớ chưa được định lượng, thiếu rà soát công khai; tác giả yêu cầu loại bỏ Kyber-512 và NIST công khai lỗi tính toán của mình
Cốt lõi của lỗi tính toán
- Điểm xuất phát là ví dụ đơn giản: “2^40 + 2^40 không phải là 2^80 mà là 2^41”
- Nếu nhầm lẫn giữa các số cần nhân và các số cần cộng, mức độ bảo mật có thể bị thổi phồng đáng kể
- Cấu trúc gây tranh cãi trong mức độ bảo mật Kyber-512 như sau
- Tấn công gồm nhiều lần lặp (iteration)
- Mỗi lần lặp có chi phí tính toán và chi phí truy cập bộ nhớ
- Tổng chi phí phải được tính là
số lần lặp × chi phí mỗi lần lặp - Trong chi phí mỗi lần lặp, chi phí tính toán và chi phí truy cập bộ nhớ phải được cộng với nhau
- Phê bình cốt lõi là NIST đã tạo ra hiệu ứng như thể nhân chi phí tính toán với chi phí truy cập bộ nhớ, thay vì cộng chúng
- Ví dụ, 2^25 bit operations/iteration và 2^35 bit operations/iteration phải được cộng với nhau
- Nếu nhân chúng, đơn vị trở thành
bitops^2/iter^2, không phải đơn vị chi phí tấn công - Phép nhân kiểu này có thể thổi phồng chi phí tấn công lên hàng triệu lần hoặc hơn
Bối cảnh NISTPQC và Kyber-512
- NIST công bố kế hoạch chuẩn hóa Kyber-512 vào năm 2022, và đưa ra bản dự thảo tiêu chuẩn Kyber-512 vào năm 2023
- Trọng tâm phê bình là NIST đã mắc sai lầm tính toán nghiêm trọng trong quá trình biện minh mức độ bảo mật của Kyber-512
- Tháng 3/2022, một yêu cầu FOIA liên quan đến NSA, NIST, and post-quantum cryptography được nộp; sau đó, thông qua kiện tụng, một phần tài liệu nội bộ của NIST đã được công khai
- Qua so sánh tài liệu công khai và không công khai, tác giả cho rằng mức độ tham gia của NSA trong quy trình NISTPQC lớn hơn so với giải thích công khai của NIST
- Danh sách nhóm
pqc@nist.govnăm 2016 được nêu là có nhiều nhân sự NSA hơn nhân sự NIST - Trong tài liệu công khai năm 2020, NIST từng nói phản hồi của NSA không ảnh hưởng đến quyết định, và chỉ NIST đưa ra quyết định dựa trên thông tin công khai
- Tháng 1/2023, một yêu cầu FOIA mới được nộp liên quan đến tuyên bố về mức độ bảo mật của Kyber-512, và NIST lại trì hoãn phản hồi, dẫn đến một vụ kiện mới
Lựa chọn tham số hạn chế của Kyber
- Kyber bị chỉ ra là khó tăng dần mức bảo mật theo kích thước mong muốn như RSA, ECC, McEliece, NTRU
- Không có Kyber-576; lựa chọn mạnh hơn Kyber-512 là Kyber-768, đòi hỏi tăng 50% số chiều
- Lựa chọn mạnh hơn Kyber-768 là Kyber-1024
- Không có lựa chọn mạnh hơn Kyber-1024
- Tài liệu chính thức của Kyber nêu ưu điểm là có thể xử lý mọi bộ tham số bằng “dimension-256 NTT”, nhưng trong cấu trúc này, các số chiều không phải bội số của 256 đòi hỏi thay đổi thiết kế cốt lõi
- Trong các ứng dụng giới hạn 1KB, khó dùng Kyber-768 và Kyber-512 trở thành lựa chọn Kyber có mức bảo mật cao nhất
- Kyber-768 dùng public key 1184 byte và ciphertext 1088 byte
- Kyber-512 dùng key 800 byte và ciphertext 768 byte
- Với cùng giới hạn 1KB, họ NTRU được so sánh là cung cấp ước tính Core-SVP cao hơn
sntrup653: key 994 byte, ciphertext 897 byte, Core-SVP 2^129- NTRU-677 (
ntruhps2048677): key 931 byte, ciphertext 931 byte, Core-SVP 2^145 - Phiên bản round-3 của Kyber-512 được trình bày là Core-SVP 2^118
- Core-SVP là cơ chế nhóm Kyber dùng để ước tính mức độ bảo mật trong các bản nộp round-1 và round-2, và báo cáo round-2 năm 2020 của NIST cũng dùng Core-SVP để so sánh
Tiêu chí đánh giá của NIST và so sánh với NTRU
- Lời kêu gọi nộp hồ sơ chính thức năm 2016 của NIST đưa tính linh hoạt (flexibility) vào tiêu chí đánh giá
- Với điều kiện có “bảo mật và hiệu năng tổng thể tốt”, phương án linh hoạt hơn được xem là đáp ứng nhiều nhu cầu người dùng hơn
- Văn bản cũng nêu rõ trong cùng một hạng mục có thể đưa ra nhiều bộ tham số để điều chỉnh hiệu năng hoặc biên độ bảo mật
- NIST năm 2020 loại NewHope, trong đó một lý do là Kyber hỗ trợ tự nhiên bộ tham số category 3
- Nếu Kyber-512 không đáp ứng mức bảo mật tối thiểu, Kyber chỉ còn Kyber-768 và Kyber-1024, làm vấn đề kém linh hoạt hơn NTRU trở nên lớn hơn
- Selection report năm 2022 của NIST nói họ tin tưởng vào độ bảo mật của cả Kyber lẫn NTRU, và đánh giá hiệu năng của KEM nói chung là chấp nhận được cho các ứng dụng phổ thông
- Trong điều kiện đó, lập luận là nếu Kyber-512 bị loại, NTRU có lợi thế hơn Kyber vì cung cấp tùy chọn nhỏ hơn, tùy chọn bảo mật cao hơn, và đánh đổi kích thước–bảo mật dày hơn
Bốn phê bình rằng NIST đã làm lệch cuộc cạnh tranh
-
1. Bỏ qua tính linh hoạt bổ sung của NTRU
- Tác giả nói tài liệu NTRU từ lâu đã cho thấy có thể cung cấp nhiều mức bảo mật và lựa chọn kích thước
- NIST năm 2020 công bố rằng “quá nhiều parameter sets khiến việc đánh giá và phân tích khó hơn”
- Trong tiêu chí chính thức, tính linh hoạt được nêu như một điểm tích cực, nhưng giữa chừng lại xuất hiện phê bình “too many”, và NIST bị chỉ ra là không trả lời rõ tiêu chí đó
-
2. Phóng đại chi phí sinh khóa
- Trong benchmark trên Golden Cove, Kyber-512 có encapsulation 25829 cycles, decapsulation 20847 cycles
- NTRU-509 có encapsulation 15759 cycles, decapsulation 25134 cycles, tổng xử lý ciphertext được trình bày là nhỏ hơn Kyber-512 13%
- Ngược lại, key generation của NTRU-509 là 112866 cycles, lớn hơn Kyber-512 với 17777 cycles
- Tuy nhiên, tác giả lập luận rằng KEM có thể tái sử dụng khóa cho nhiều ciphertext, chi phí gửi/nhận byte quan trọng hơn nhiều so với cycle, và có thể tăng tốc key generation của NTRU bằng Montgomery trick
-
3. Che khuất mức bảo mật cao hơn của NTRU
- Trong báo cáo round-2 năm 2020, NIST bắt đầu khuyến nghị mạnh các bộ tham số category 5
- NTRU đưa ra NTRU-1229 và NTRU-HRSS-1373, lần lượt có Core-SVP 2^301 và 2^310, cao hơn Kyber-1024 với 2^254
- NTRU Prime cũng đưa ra các tùy chọn như
sntrup1277,ntrulpr1277với Core-SVP 2^270, 2^271 - Biểu đồ của NIST bị phê bình là không thể hiện đầy đủ các tùy chọn NTRU có bảo mật cao này
-
4. Loại trừ NTRU-509, tùy chọn hiệu năng cao nhất
- Tác giả chỉ ra rằng NIST đã loại NTRU-509 khỏi biểu đồ lớn cũng như khỏi hình và bảng trong selection report sau đó
- NTRU-509 cung cấp key và ciphertext nhỏ hơn Kyber-512, điều này không khớp với mô tả của NIST rằng “NTRU có public key và ciphertext somewhat larger so với Kyber”
- Nếu muốn loại NTRU-509 thì phải nói nó không đạt mức bảo mật tối thiểu AES-128, nhưng tác giả phê bình rằng giữ Kyber-512 theo cùng tiêu chí là một phân biệt rất yếu
Bất định sau Core-SVP
- Core-SVP của Kyber-512 là 2^118, còn chi phí tấn công AES-128 được đặt cao hơn một chút so với 2^140 bit operations
- Các tài liệu nộp Kyber năm 2017 và 2019 từng tuyên bố an toàn hơn Core-SVP ít nhất 30 bit, nhưng một phần căn cứ bị phê bình là sai hoặc không đủ
- rounding noise không áp dụng cho tấn công khóa, nên không phải là căn cứ tăng bảo mật
- Tuyên bố chi phí subexponential của sieving tăng lên là thiếu căn cứ, và asymptotics thực tế có thể nhanh hơn Core-SVP
- Số lần gọi SVP oracle và gate count có thể có phần hợp lý, nhưng dường như không đủ để cứu Kyber-512
- Chi phí truy cập bộ nhớ có thể quan trọng đối với chi phí tấn công thực tế, nhưng tiêu chí chính thức của NIST yêu cầu 2^143 “classical gates”, nên khó dùng trực tiếp làm lập luận cứu Kyber-512
- Bản nộp Kyber round-3 đã thay đổi Kyber-512 và cũng thay đổi định nghĩa Core-SVP để thu được 2^118 thay vì 2^112
- Bản nộp này trình bày bảo mật Kyber-512 là 151 bits ±16, và lập luận rằng ngay cả khi giảm xuống 135 thì cũng không “catastrophic” do yêu cầu bộ nhớ
- Sau đó, nhiều phân tích tấn công lattice như của Matzov xuất hiện, khiến ước tính bảo mật Kyber-512 phức tạp và bất ổn hơn
Lập luận cứu Kyber-512 của NIST
- Lời kêu gọi chính thức của NIST nêu rằng mỗi security category lấy các primitive chuẩn như AES-128 làm ngưỡng dưới theo nhiều metric “potentially relevant”
- Tức là mọi tấn công đều phải đòi hỏi tài nguyên ít nhất bằng chuẩn theo tất cả các metric mà NIST xem là có khả năng liên quan đến bảo mật thực tế
- NIST né tránh trong thời gian dài các yêu cầu định nghĩa rõ “classical gates”, và trong selection report năm 2022 giải thích rằng họ cho phép một lần đọc/ghi bộ nhớ một bit được tính là cost-1 gate
- NIST bị phê bình là khi loại NTRU-509 đã dùng “non-local cost model”, tức tiêu chí xem chi phí truy cập bộ nhớ gần như miễn phí
- Ngược lại, khi giữ Kyber-512 ở category 1, NIST cho rằng nếu xét “realistic memory access costs” thì nó thỏa category 1
- Kết quả là, theo phê bình, NIST đã áp dụng metric bộ nhớ miễn phí cho NTRU-509 và metric bộ nhớ đắt đỏ cho Kyber-512
NISTBS: Phản bác giải thích ngày 7/12/2022
- Ngày 7/12/2022, NIST giải thích lý do họ cho rằng Kyber-512 thỏa NIST category I, và bài viết này gọi phần đó là “NISTBS”
- NISTBS bắt đầu từ việc báo cáo Matzov ước tính chi phí tấn công Kyber-512 là 2^137 bit operations
- Chi phí tấn công cổ điển AES-128 được đặt khoảng 2^143 bit operations
- Vì vậy còn thiếu 6 bit
- NISTBS giải thích rằng tấn công lattice sieving cần truy cập phi cấu trúc vào bộ nhớ lớn, và RAM model bỏ qua chi phí này
- Tiếp đó, NISTBS trích đánh giá trong tài liệu nộp của NTRU và NTRU Prime, tính rằng nếu xét chi phí truy cập bộ nhớ trong tấn công sieving category 1 thì có thể cao hơn RAM model “20~40 bits”
- Vấn đề là NIST dường như đã cộng 40 bit của NTRU Prime vào 2^137 của Matzov và diễn giải thành mức 2^177
- 40 bit của NTRU Prime có vẻ được ước tính từ chênh lệch giữa “real” 2^169 và “free” 2^129 trong
sntrup653 - 2^129 là Core-SVP, tức xấp xỉ số lần lặp, không phải gate count của RAM model mà NIST nói đến
- Chi phí truy cập bộ nhớ phải được cộng vào chi phí mỗi lần lặp; không thể nhân với tổng chi phí tính toán vốn đã được gom thành bit operation, cũng không thể cộng vào số mũ
- 40 bit của NTRU Prime có vẻ được ước tính từ chênh lệch giữa “real” 2^169 và “free” 2^129 trong
Ý nghĩa của các con số thực tế
- Tài liệu NTRU Prime báo cáo Core-SVP 2^129 cho
sntrup653- Đây là ước tính xấp xỉ số lần lặp
- Cùng tài liệu đó ước tính tổng chi phí truy cập bộ nhớ tương đương 2^169 bit operations
- Kyber-512 được trình bày với Core-SVP 2^118
- Nếu ước tính thô chi phí truy cập bộ nhớ theo cùng cách, con số được nói là tương đương 2^154 bit operations
- Ước tính 2^151 “gates” trong tài liệu Kyber không phải là ước tính chi phí truy cập bộ nhớ
- Đây là giá trị ước tính số bit operations bên trong tính toán của tấn công
- Khi xét các “known unknowns”, tài liệu đưa ra phạm vi 2^135~2^167
- Do đó, ước tính chi phí tính toán 2^151 và ước tính chi phí truy cập bộ nhớ không phải là các hạng tử để nhân với nhau, mà là các hạng tử cần quy về cùng ý nghĩa ở cấp chi phí mỗi lần lặp rồi cộng lại
Vì sao lỗi này được cho là dễ phát hiện
- Một sanity check đơn giản như sau
- Tài liệu Kyber ước tính chi phí tính toán tấn công Kyber-512 là 2^135~2^167 bit operations
- NTRU Prime ước tính chi phí truy cập bộ nhớ của
sntrup653, vốn có vẻ khó hơn Kyber-512, là tương đương 2^169 bit operations - Tác giả chỉ ra rằng khi tấn công đã được cải thiện 2^14 lần mà NIST lại tính chi phí tấn công Kyber-512 là 2^177 thì rất kỳ lạ
- NISTBS viết rằng tài liệu NTRU Prime ước tính “40 bits bảo mật bổ sung so với RAM model”, nhưng trong Section 6.11 của tài liệu đó không có cách diễn đạt trực tiếp “40” hay “RAM model”
- Phê bình là để rà soát rõ ràng, NIST lẽ ra phải giải thích chính xác số 40 đến từ đâu, và là giá trị nào của metric nào
- Sau tháng 12/2022, đã có câu hỏi xác nhận về scenario X cụ thể rằng “có đúng là đã tính 137+40=177 không”, nhưng NIST không trả lời
- Sau đó, NIST trả lời rằng email đó “speaks for itself”, và bị phê bình là không xác nhận cách diễn giải cụ thể của phép tính cũng không đưa ra cách diễn giải thay thế
Nghiên cứu cần thiết để tính đúng
- Phép tính đúng cần phân biệt hai hiệu ứng
- Một phần mức tăng ước tính bảo mật so với Core-SVP đến từ chi phí bit operations của tính toán bên trong mỗi lần lặp
- Một phần đến từ vòng lặp ngoài làm tăng chính số lần lặp so với Core-SVP
- Hiệu ứng tăng số lần lặp có thể được nhân với chi phí truy cập bộ nhớ
- Ngược lại, chi phí tính toán bên trong lần lặp và chi phí truy cập bộ nhớ bên trong lần lặp phải được cộng; nhân hai đại lượng này là lỗi cốt lõi
- Phép tính chính xác đòi hỏi phải theo dõi hàng trăm trang bài báo về các lattice attacks tiên tiến nhất, rồi tối ưu lại toàn bộ ngăn xếp tấn công khi bao gồm chi phí truy cập bộ nhớ
- Ví dụ, ngay cả việc trong BKZ thì low-memory enumeration hay high-memory sieving có lợi hơn cũng cần được tính lại khi đưa chi phí truy cập bộ nhớ vào
Dự thảo tiêu chuẩn và vấn đề trách nhiệm
- Tháng 8/2023, NIST công bố dự thảo ML-KEM, tức dự thảo tiêu chuẩn Kyber
- ML-KEM-512 là security category 1
- ML-KEM-768 là category 3
- ML-KEM-1024 được viết là “claimed” thuộc category 5
- Vấn đề là chủ thể của “claimed” không rõ ràng
- Không rõ đó là tuyên bố của NIST, của các nhà thiết kế, hay của ai khác
- Appendix A của dự thảo nhắc lại tiêu chí rằng category phải vượt AES-128, AES-192, AES-256 trên mọi metric potentially relevant
- Phân tích mới nhất trong tài liệu Kyber nêu rằng chi phí tấn công Kyber-512 có thể thấp tới 2^135 “classical gates”, thấp hơn ước tính 2^143 gates của NIST cho AES-128
- Vì vậy cần có phân tích công khai về cách NIST biện minh tuyên bố Kyber-512 đạt từ AES-128 trở lên trên mọi metric liên quan
Kết luận và đề xuất
- Kết luận là bề mặt tấn công lattice còn bất ổn và chưa được hiểu đầy đủ, nên việc chuẩn hóa Kyber-512 là liều lĩnh
- Có khả năng Kyber-512 dễ bị tấn công hơn AES-128 rất nhiều ngay cả khi xét cả các tấn công đã công khai và chi phí truy cập bộ nhớ; cũng có khả năng ngược lại, nên cần nghiên cứu khó để làm rõ trạng thái thực tế
- Bản thân AES-128 trong tấn công đa mục tiêu cũng có thể chỉ cần khoảng 2^88 computations để phá một trong 1 nghìn tỷ khóa, nên mất 10~30 bit là khó xem nhẹ
- Nếu Kyber-512 vẫn là tùy chọn tiêu chuẩn, các ứng dụng đủ sức dùng Kyber-1024 hoặc NTRU-1229 cũng có khả năng chọn tùy chọn nhanh hơn
- Khuyến nghị cuối cùng là loại bỏ Kyber-512, và NIST công khai thừa nhận lỗi tính toán mức độ bảo mật Kyber-512 cùng việc lựa chọn dữ liệu thiếu minh bạch trong quá trình so sánh NTRU
1 bình luận
Các ý kiến trên Hacker News
Điều nhất định cần biết trước khi đọc bài này là NIST và NSA không tạo ra thuật toán này, mà họ chấm cuộc thi
Phần lớn phân tích được thực hiện bởi các đối thủ cạnh tranh và giới học thuật; nhóm Kyber gồm Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, Damien Stehlé, và cả Peter Schwabe, cộng sự của Bernstein
Trong lịch sử, thường chỉ người thắng được áp dụng. Cứ nhìn cuộc thi AES: hãy nghĩ xem Serpent, vốn được đánh giá là có biên độ an toàn lớn hơn Rijndael, được nhắc đến thường xuyên đến mức nào
Có vẻ NIST không đưa ra khuyến nghị dựa trên một phân tích bí mật nào đó
Thực tế đáng tiếc là Bernstein có thể đúng, nhưng rất khó phân biệt liệu phản hồi hoặc sự im lặng từ phía NIST có nên được xem là lừa dối hay chỉ là họ không muốn dây vào một người bước vào với thái độ rất công kích
Ở NIST cũng là những người bình thường làm việc, và có khả năng họ đã tiếp nhận các yêu cầu giải trình sắc bén tương tự như cách phần lớn chúng ta tiếp nhận các báo cáo lỗi mang tính công kích
Những lời cáo buộc phóng đại kiểu “họ bảo dùng Kyber từ lúc giấy phép bằng sáng chế có hiệu lực vào năm 2024, khiến dữ liệu người dùng trong 3 năm bị phơi bày trước kẻ tấn công, và đã không bảo dùng NTRU từ năm 2021” không giúp ích gì. Chắc cũng sẽ chưa có nhiều nơi triển khai ngay mật mã hậu lượng tử độc lập trong một thời gian, và vào năm 2021 NIST cũng có nhiều phương án thay thế có thể đề xuất. SIKE trông khá ổn cho đến trước khi bị phá vỡ vào năm ngoái
NIST không phải là có danh tiếng không tì vết trong lĩnh vực này, nhưng nếu muốn phê phán thuật toán và quy trình thì tốt hơn nên có một bản tóm tắt ngắn gọn về lý do, cùng một hai bằng chứng mang tính quyết định. Việc phân tích vô số email, chỉ so sánh với một bài nộp, rồi cáo buộc kiểu tất cả đều đang câu giờ để hút dữ liệu khiến người ta khó nghiêm túc tiếp nhận. Nếu Kyber-512 thực sự nguy hiểm như vậy thì cần được truyền đạt rõ ràng hơn
Việc trang đó dài tới 17.000 từ cũng là vấn đề lớn. Ngay cả theo chuẩn Harry Potter thì độc giả trung bình cũng phải đọc 70 phút, mà bài này không phải tiểu thuyết, mà đầy những con số, các điểm cần cân nhắc, và những câu phải soi từng lựa chọn từ ngữ như trích dẫn từ NIST. Ngay cả khi có nền tảng đủ để hiểu mật mã hậu lượng tử thì cũng khó đọc nhanh như một cuốn sách bình thường
Lúc đầu tôi bấm vào “That lawsuit has been gradually secret NIST documents, shedding some light on what was actually going on behind the scenes” rồi bị cuốn sang một bài khác, mà trang được liên kết đó lại dài 54.000 từ. Trên di động không có thanh cuộn nên không biết độ dài, cứ lướt tuyến tính, rồi đến một lúc cảm giác như mình vừa đăng ký vào một dự án nghiên cứu tiến sĩ, nên tôi đóng tab và quay lại bài gốc
Độc giả HN có nhiều người thông minh và kỹ thuật, nhưng lĩnh vực rất đa dạng, nên khó đánh giá hợp lý những bằng chứng đầy thuật ngữ chuyên môn nhằm chứng minh “NIST=xấu”. Vì ở lĩnh vực lân cận, tôi nghĩ mình hiểu hơn độc giả trung bình, nhưng vẫn không cảm thấy mình có tư cách phán xét nếu chưa đọc kỹ. Bài viết có giải thích bối cảnh và các chữ viết tắt, nhưng quá dài, nên tôi không biết người chưa biết sẵn có muốn đọc hay không. Không phải mọi bài nộp đều cần ai cũng hiểu, nhưng vì bài này chứa cáo buộc nên tôi nghi ngờ liệu nó có phù hợp với HN không
Vì vậy có lẽ tôi sẽ rút lại một chút những gì nói bên dưới, hoặc ít nhất, xét lịch sử của djb với các khuyến nghị của NIST, tôi thấy giọng điệu công kích dễ hiểu hơn. Thông tin liên quan có ở https://en.wikipedia.org/wiki/Daniel_J._Bernstein#Cryptograp...
Tôi không thích soi hình thức quá mức thay vì nội dung, nhưng trong trường hợp này hình thức của bài blog tệ đến mức khó đánh giá nội dung có giá trị hay không. Tôi không phải người trong ngành mật mã học nên không thể đánh giá phần cốt lõi, nhưng sự mỉa mai và hạ thấp không cần thiết khiến thông điệp trở nên rất đáng ngờ. Dù có vẻ chỉ ra những điểm hay, tổng thể giọng điệu lại giống kiểu video YouTube “WhaT ThE ElITe DoN'T WanT YoU TO KnoW!!”, và dù có nói đúng thì tác giả nghe vẫn khá khó chịu
Tôi cũng tò mò liệu có ai thực sự đọc hết cái này không. Có thể nói Internet đã giết chết khả năng tập trung là đúng, nhưng ngược lại bây giờ có quá nhiều thông tin nên ta phải cực kỳ khắt khe khi chọn dùng thời gian vào đâu. Nếu là bài blog thì các chi tiết liên quan và tóm tắt nên nằm trong vài đoạn đầu, còn nhật ký dài dòng thì để phía sau. Nếu các mảnh quan trọng bị giấu như trò Where's Waldo trong một nhật ký lê thê thì khó kỳ vọng người ta đọc hết
Trọng tâm ông ấy hỏi đi hỏi lại là vì sao tiêu chí đánh giá liên tục bị thay đổi sau đó, vì sao kết quả được trình bày theo cách gây hiểu nhầm, và vì sao lại có lỗi tính toán cơ bản. Những người này là chuyên gia, vậy mà tất cả những việc đó đều có lợi cho một thuật toán
Trong mắt tôi, đó là tín hiệu cho thấy họ muốn biến thuật toán đó thành tiêu chuẩn. Cộng thêm việc mức độ tham gia của NSA lớn hơn nhiều so với những gì đã biết và họ đã cố che giấu điều đó, tôi trở nên cực kỳ nghi ngờ tiêu chuẩn này
Vấn đề là các thuật toán này sắp được tích hợp vào phần cứng
Một khi bản triển khai sẽ được chuẩn hóa đã được quyết định, các hãng phần cứng có khả năng bắt đầu thiết kế các khối tính toán tiêu chuẩn FIPS 203 hiệu quả hơn. Có thể họ đã thiết kế vài cái rồi
Xét việc công bố tiêu chuẩn được dự kiến vào năm 2024, và việc thẩm định NIST CMVP cho mô-đun FIPS mất 1–2 năm, sẽ không ngạc nhiên nếu khoảng giữa năm 2026 xuất hiện các mô-đun phần cứng FIPS 140-3 có ML-KEM (Kyber, v.v.)
Điểm cốt lõi có vẻ là câu trong [1]: “Tuy nhiên, NIST đã không đưa ra một tuyên bố đầu-cuối rõ ràng rằng Kyber-512 có biên độ an toàn N bit trong kịch bản X đối với (N,X) được chỉ định rõ ràng”
Trong [2], djb đã tóm tắt ngắn gọn “kịch bản X” mà ông ấy nói đến, và nói rằng chỉ cần câu trả lời có/không. Ông ấy đang hỏi những người thực sự cần biết vấn đề này và có nền tảng kỹ thuật để thảo luận. Vì không nhận được câu trả lời nên ông ấy đã đăng [1]
Phản hồi của NIST trong [3] đã bác bỏ [1] mà không thảo luận về bản thân vấn đề bảo mật. Đặc biệt đoạn thứ hai khiến tôi thấy bức bối. “Email được trích dẫn (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...) tự nó đã nói lên tất cả. NIST vẫn tiếp tục quan tâm đến ý kiến của mọi người về việc liệu kế hoạch hiện tại nhằm chuẩn hóa Kyber512 có tốt hay không. Các reviewer có quyền, vì vui, thử phản bác những gì có vẻ là tuyên bố của NIST về biên độ an toàn, nhưng kết quả đó sẽ không đặc biệt hữu ích cho quá trình chuẩn hóa. Những tuyên bố trước đây của NIST và cách diễn giải chúng không liên quan đến việc mọi người có tin rằng chuẩn hóa Kyber512 là một ý tưởng hay hay không”
Nếu NIST xem các lập luận liên quan đến bảo mật của các reviewer là “không đặc biệt hữu ích cho quá trình chuẩn hóa”, thì xét việc những reviewer đó là các nhà mật mã học, tại sao công chúng nên tin tưởng tiêu chuẩn đó?
Không thể có bằng chứng quyết định. Bởi chính vấn đề hiện tại là thiếu giải thích rõ ràng. Nếu họ có thể giải thích cách tính độ mạnh bảo mật của Kyber-512 thì đã là chuyện khác
Hiện theo các ước tính của bên thứ ba, giá trị khá mơ hồ gọi là độ mạnh bảo mật của Kyber-512 lại thấp hơn yêu cầu ban đầu, nên có vẻ cần một lời giải thích hoặc biện minh
[1]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
[2]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
[3]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
Nếu bài viết này là của một người vô danh thì có lẽ tôi đã đồng ý, nhưng tác giả là DJB hoặc Tanja Lange, và cả hai đều không phải người vô danh
Những việc như thế này ở một mức độ nào đó không thể tránh khỏi tính đối kháng. Giải mã học cũng cần thái độ như vậy, và cũng vì trong quá khứ đã có nhiều chuyện đáng ngờ. Đây là một phần của lĩnh vực và của chính trị, nên khó tránh khỏi
Đây giống nhật ký hơn là một bài báo. Nhiều thuật ngữ chuyên môn, không được sắp xếp rõ ràng, cứ vòng vo quanh cùng một chỗ, và rất khó theo dõi
Dù vậy, bản thân thông tin có thể quan trọng. Có hàm ý mạnh rằng NIST, với sự trợ giúp của NSA, đã cố ý chuẩn hóa một thuật toán yếu
Ai cũng biết chuyện đó là có thể
Tuy nhiên, nếu có ai theo sát lĩnh vực này hơn, tôi muốn họ giải thích con số ở đây là gì. Tôi luôn nghĩ rằng làm suy yếu mật mã công khai theo cách này là một canh bạc nguy hiểm, vì không thể bảo đảm kẻ tấn công sẽ không độc lập phát hiện ra cùng sự thật đó. Khóa backdoor bí mật thì có thể che giấu. Những nghi ngờ khi Dual_EC_DRBG xuất hiện là như vậy. Nhưng các kết quả toán học thì thật sự rất khó giấu
Tại sao họ lại muốn chấp nhận rủi ro như thế ở đây?
Giờ tôi cũng không hiểu vì sao còn cần những cuộc thảo luận như thế này nữa. Chúng ta không còn cần họ. Các hạn chế xuất khẩu cũng đã biến mất
Điều cần thiết là một consortium thu hút được sự chú ý của các nhà sản xuất phần cứng, và giới hạn NIST cùng NSA ở tư cách người tham gia đơn thuần. Khi đó, kể cả chính phủ có chấp nhận một tiêu chuẩn có backdoor, thì cũng chỉ họ tự dùng với nhau
Tại sao họ phải quan tâm điều đó?
Suy đoán hiện nay về việc có thể đã xảy ra gì với các đường cong elliptic của NIST là theo hướng này
Nếu vậy, trong một thời gian rất dài, nó có thể về thực chất là một backdoor chỉ dành riêng cho Mỹ
Họ nghĩ rằng họ có thể đi trước trong việc tấn công, và đến khi khóa 56 bit nói chung trở nên quá yếu thì DES sẽ được thay thế bằng thứ khác. Có rủi ro không? Có. Nhưng theo một nghĩa nào đó, nó đã “thành công”. Vì vậy tôi sẽ không giả định rằng chuyện tương tự sẽ không bao giờ xảy ra nữa
Lý thuyết nền phía sau được gọi là kleptography. Điều đó cũng có nghĩa là NSA hoang tưởng đến mức nghĩ rằng họ có thể đánh cắp thông tin một cách “an toàn”
Năm ngoái đã có một thread liên quan với 443 bình luận
https://news.ycombinator.com/item?id=32360533 ("NSA, NIST, and post-quantum crypto: my second lawsuit against the US government (cr.yp.to)")
“Tìm hiểu cách NISTPQC vận hành bí mật. Tháng 3/2022, tôi đã nộp một yêu cầu FOIA có tên ‘NSA, NIST, and post-quantum cryptography’. NIST đã vi phạm luật và câu giờ. Hãng luật dân quyền Loevy & Loevy đã thay mặt tôi khởi kiện”
Cá nhân tôi nhìn chung không thích djb, nhưng về mặt nghề nghiệp thì ông ấy đã liên tục truy vấn chính phủ liên bang trước tòa, nên tôi luôn ủng hộ. Rất vui khi thấy ông ấy vẫn tiếp tục làm vậy
Bất kể DJB là một nhân vật quan trọng trong mật mã học, và bất kể tôi không biết khá nhiều chi tiết ở đây, có một điểm khiến độ tin cậy giảm mạnh
Đặc biệt ở phần biểu đồ, ông ấy nói “NIST đã quyết định dùng các thanh màu đỏ mỏng hơn trong biểu đồ băng thông để làm chúng kém nổi bật hơn”, nhưng bằng chứng đó hoàn toàn không chứng minh được điều này. Có một cách giải thích hợp lý hơn nhiều. Biểu đồ có các thanh mỏng hơn là biểu đồ cột có nhiều điểm dữ liệu hơn các biểu đồ khác. Cứ mở bất kỳ công cụ vẽ biểu đồ nào rồi so sánh biểu đồ có 12 điểm dữ liệu với biểu đồ có 9 điểm dữ liệu, việc các đường của biểu đồ 12 điểm trở nên mỏng hơn là điều đương nhiên. Ở điểm này, tôi có cảm giác rất rõ rằng ông ấy đang cố diễn giải mọi hành động theo hướng ác ý nhất có thể
Ở mục tiếp theo, ông ấy phàn nàn rằng họ không dùng trục log dù các giá trị nằm trong cùng một bậc độ lớn. Nghe không giống một trường hợp phù hợp để dùng trục log, và tôi không rõ vì sao trong trường hợp này điều đó có thể được biện minh
Khi biết DJB có liên quan đến NTRU, thật khó gạt bỏ cảm giác rằng phần lớn chuyện này là phản ứng cay cú vì thua trong cuộc cạnh tranh
Giả định điều gì khác, ít nhất với tôi, trông khá ngây thơ
Có đủ lý do để nghi ngờ
Việc các đối thủ trong lĩnh vực này xem xét công trình của nhau là điều tự nhiên
Điều tôi học được khi theo dõi những cuộc đấu nảy lửa giữa các nhà mật mã học như một phần công việc: đừng cược chống lại Bernstein, và đừng tin NIST
NIST đã phản hồi: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VO...
Không rõ N(IST)SA còn chút uy tín nào không
Việc curve25519 được dùng rộng rãi hơn các đường cong P của họ là điều đáng khích lệ, và tôi hy vọng cộng đồng sẽ tiếp tục đi theo hướng này, đồng thời về sau hầu như phớt lờ họ
Chính phủ không nên dẫn dắt hay quyết định. Với FIPS, quy định, v.v., tốt hơn là cấu trúc vai trò của họ xoay quanh việc tập hợp và tuân theo đồng thuận hiện tại