Một cách nhìn về NIST SP 800-22

Bài báo giới thiệu các quan điểm mang tính phê phán của Markku-Juhani O. Saarinen về tài liệu NIST SP 800-22, cho rằng SP 800-22 đã bị lỗi thời so với SP 800-90. Việc đánh giá các bộ tạo và các dãy giả ngẫu nhiên nên dựa trên các nguyên tắc phân tích mật mã, chứng minh độ an toàn và phân tích thiết kế, từ đó xác nhận một cài đặt của thuật toán tạo số giả ngẫu nhiên dựa trên mã khối, hàm băm cần tập trung vào tính đúng đắn so với mô tả thuật toán chứ không phải vào tính ngẫu nhiên của đầu ra. Trong phiên bản mới của SP 800-22 nên tập trung vào việc đánh giá mô hình ngẫu nhiên cho các nguồn entropy; các “bộ tạo tham khảo” trong Phụ lục D của SP 800-22 đều không phù hợp để sử dụng trong mật mã hiện đại.

GIỚI THIỆU

Tháng 10/2010, Viện Tiêu chuẩn và Công nghệ Quốc gia Mỹ (NIST) công bố “Các phép kiểm tra thống kê đối với các bộ tạo số ngẫu nhiên và giả ngẫu nhiên cho các ứng dụng mật mã” [1]. Kể từ đó, tài liệu này đã được cộng đồng mật mã quan tâm và sử dụng. Chỉ tính trên trang web của Hiệp hội nghiên cứu mật mã thế giới, từ đầu năm 2022 cho tới ngày 14/2/2022 đã có 4 bài báo viết về tài liệu này [2 - 5].

Theo đó, NIST đã công bố bản chỉnh sửa là NIST SP 800-22 r1a [6]. 15 phép kiểm tra thống kê được mô tả trong đó là:

Tần số đơn
Tần số khối
Kiểm tra loạt
Loạt dài nhất của các số 1
Kiểm tra hạng của ma trận nhị phân
Fourier rời rạc (phổ)
Mẫu không chồng chéo
So khớp mẫu chồng chéo
Thống kê vạn năng Maurer
Kiểm tra độ phức tạp tuyến tính
Kiểm tra nối tiếp (serial test)
Entropy gần đúng
Tổng tích lũy (cusums)
Du ngoạn ngẫu nhiên
Biến thể du ngoạn ngẫu nhiên

15 phép kiểm tra nhận đầu vào là một chuỗi các bit, thường là 1.000.000 bit và tạo ra các P - giá trị dựa trên thông tin đó, nó dẫn đến chỉ số PASS/FAIL (với tỷ lệ dương tính giả rất cao).

Ngày 12/01/2022, NIST đã thông báo đề xuất sửa đổi SP 800-22 r1a [7] với mục đích giải quyết các vấn đề xuất kỹ thuật và các điểm không thống nhất giữa SP 800-22 và loạt SP 800-90. Bên cạnh đó, thông báo cũng làm dễ hiểu hơn cách sử dụng các phép kiểm tra ngẫu nhiên thống kê, đồng thời cải tiến công cụ phần mềm và nâng cao chất lượng biên tập của tiêu chuẩn.

Ngày 14/2/2022, [4] được công bố như là các ý kiến đối với Đề xuất giải quyết [7]. Tên của bài báo có thể dịch là “Bộ kiểm tra NIST SP 800-22 và GM/T 0005-2012: Rõ ràng đã lỗi thời, có thể có hại”. Trong tên của bài báo có nhắc đến GM/T 0005-2012, đó là Tiêu chuẩn công nghiệp mật mã của Trung quốc về kiểm tra tính ngẫu nhiên [8], nó cũng gồm 15 phép kiểm tra rất giống với [6].

Tác giả của [4] là Markku-Juhani O. Saarinen. Từ tháng 9/2018, ông tham gia vào PQShield Ltd (được tách ra từ Đại học Oxford) và nghiên cứu về mật mã hậu lượng tử.

Markku-Juhani O. Saarinen trình bày báo cáo mời tại Hội nghị CTCrypt’16 (Cộng hòa Liên bang Nga)

CÁC QUAN ĐIỂM CỦA MARKKU-JUHANI O. SAARINEN VỀ NIST SP 800-22 R1A

Đánh giá theo kiểu hộp đen và đã bị lỗi thời bởi bộ SP 800-90

Trong các năm 2015-2021, NIST đã công bố các tài liệu SP 800-90A, SP 800-90B và SP 800-90C [9 - 11], đó cũng là các tài liệu về tính ngẫu nhiên. Trong phiên bản 3 của tài liệu “Các yêu cầu an toàn cho các moule mật mã” [12], NIST đã áp dụng phương pháp luận mạnh hơn của bộ SP 800-90 thay cho SP 800-22. SP 800-22 cũng không thực sự được sử dụng và không nên được sử dụng trong các quy trình xác nhận Bộ tạo bit ngẫu nhiên tất định của NIST (DRBG) và Nguồn Entropy (ENT) [13].

SP 800-90B cũng là cơ sở cho Báo cáo Đánh giá Entropy (Entropy Assessment Report) của Hiệp hội Bảo đảm thông tin Quốc gia, được sử dụng trong Chiến lược an ninh quốc gia của Chính phủ Hoa Kỳ và Hồ sơ Bảo vệ tiêu chí chung [14, 15].

Tài liệu SP 800-22 chủ yếu được sử dụng bởi các nhà mật mã nghiệp dư và các nhà cung cấp các hệ thống không an toàn, vì nó tầm thường hóa việc xác nhận bộ tạo bit ngẫu nhiên bằng kiểm tra thống kê kiểu hộp đen. Việc sử dụng nó làm bằng chứng bảo mật thường báo hiệu rằng các chuyên gia có năng lực đã không tham gia vào việc thiết kế và phân tích bộ tạo bit ngẫu nhiên.

Một vấn đề mang tính hệ thống: độ bảo mật không được xem xét

Các phép kiểm tra SP 800-22 dựa trên giải thích thống kê thuần túy về tính ngẫu nhiên đều và độc lập. Các định nghĩa và mục tiêu đã nêu của các phép kiểm tra không liên quan đến tính không thể phân biệt được về mặt tính toán hoặc khái niệm độ an toàn mật mã liên quan khác.

Từ "thám mã - cryptanalysis" phân tích mật mã có thể được tìm thấy trong phần tóm tắt của SP 800-22 r1a ba lần nhưng không một lần có trong phần nội dung của tài liệu. Tuy nhiên, một số phép kiểm tra đã được đưa vào cho có hương vị thám mã. Như một ví dụ minh họa, "phép kiểm tra độ phức tạp tuyến tính" được đưa vào là do "LFSR" (thanh ghi dịch phản hồi tuyến tính - linear feedback shift register) quá ngắn kéo theo tính không ngẫu nhiên”. Mọi nhà phân tích mật mã đều biết rằng, một LFSR thuần túy không bao giờ là một bộ tạo giả ngẫu nhiên an toàn.

Việc đánh giá độ an toàn của bộ tạo số giả ngẫu nhiên cần phải làm tương tự như đối với các cấu trúc mật mã khác. Tức là phải dựa vào: Phân tích mật mã, Chứng minh độ an toàn và Đánh giá thiết kế (Cryptanalysis, Security Proofs, and Design Reviews). Trên thực tế, người ta muốn chứng minh (thông qua các lập luận toán học) rằng việc phá vỡ một bộ tạo giả ngẫu nhiên (DRBG) ngụ ý việc phá vỡ một thuật toán mật mã đã được xem xét chặt chẽ cơ như AES hoặc SHA-2/3.

Độ an toàn của các nguồn entropy vật lý chủ yếu được đánh giá thông qua việc xem xét và kiểm tra các quy trình sản xuất entropy (các mô hình ngẫu nhiên) và độ tin cậy của cài đặt chúng. Đây là những khía cạnh quan trọng hơn nhiều so với tính đều thống kê của đầu ra cuối cùng, cái này có thể được đảm bảo với điều chỉnh (hậu xử lý) trong mọi trường hợp.

Cần kiểm tra cài đặt, không phải kiểm tra phân phối đều

Mục 4 của [6] gợi ý rằng 15 phép kiểm tra thống kê được áp dụng cho các bộ tạo bit ngẫu nhiên dựa trên các hàm băm mật mã và mật mã khối. Thế nhưng ngay cả với nguyên liệu mầm được lấy một cách khá tùy ý, thì các bộ tạo số giả ngẫu nhiên này vẫn qua được các tiêu chuẩn thống kê.

Động lực hợp lý duy nhất của việc sử dụng các phép kiểm tra thống kê đối với bộ tạo bit giả ngẫu nhiên sẽ là để phát hiện ra các sai sót trong việc cài đặt chúng. Sẽ hữu ích hơn nhiều nếu xác nhận rằng một hàm băm mật mã hoặc mật khối được cài đặt đúng với mô tả chuẩn hơn là xác minh chất lượng thống kê của chúng.

Rõ ràng, một phép kiểm tra thống kê là một cách tồi để xác minh rằng một thuật toán tất định đã được thực hiện một cách chính xác. Thông thường, ít nhất người ta sẽ chạy DRBG với các đầu vào đã biết hoặc đã được chọn và sử dụng Phép kiểm tra câu trả lời đã biết (KATs-Known Answer Tests) với các vectơ kiểm tra tham chiếu. Đây là một trong những việc mà Chương trình xác nhận thuật toán mật mã của NIST đã làm.

Cần chú ý tới Mô hình ngẫu nhiên

Có một khía cạnh thống kê của việc tạo bit ngẫu nhiên mà việc thay thế SP 800-22 có thể giải quyết: Mô hình Thống kê Nguồn Entropy. Trong khi các mô hình ngẫu nhiên được đề cập đến ở mục 3.2.2 của [10] thì việc tạo ra các mô hình ngẫu nhiên không thực sự được đề cập trong loạt SP 800-90 hiện tại.

Vấn đề "Mô hình ngẫu nhiên" đã được giải quyết tốt trong [16] sẽ có lợi cho cả các nhà cung cấp và các phòng thí nghiệm nếu các yêu cầu của NIST và Văn phòng Liên bang về bảo mật trong CNTT của Đức (Bundesamt für Sicherheit in der Informationstechnik - BSI) được hòa đồng hơn nữa. Định nghĩa của một mô hình ngẫu nhiên cho một nguồn entropy (hoặc TRNG) trong hai tài liệu rất giống nhau.

Mô hình ngẫu nhiên là một mô tả toán học (về các thuộc tính có liên quan) của một nguồn entropy bằng cách sử dụng các biến ngẫu nhiên. Mô hình ngẫu nhiên (sử dụng để phân tích nguồn entropy) được sử dụng để hỗ trợ ước tính entropy của dữ liệu số hóa và cuối cùng là của dữ liệu thô. Đặc biệt, mô hình này nhằm cung cấp một họ các phân bố, mà có chứa phân bố đúng (nhưng chưa biết) của các đầu ra nguồn nhiễu. Hơn nữa, mô hình ngẫu nhiên nên cho phép hiểu về các yếu tố có thể ảnh hưởng đến entropy. Phân bố của nguồn entropy cần phải được duy trì trong họ các phân bố, ngay cả khi chất lượng của dữ liệu số hóa đi xuống. [10, Phụ lục B, Trang 65].

Trong thực tế, người ta nghiên cứu nguồn nhiễu và xác định các quá trình ngẫu nhiên tạo ra entropy. Việc hiểu quá trình tạo entropy cho phép phát triển một mô hình ngẫu nhiên, phân phối đầu ra và các ước tính min - entropy. Nó cũng giúp tìm ra các thông số ngưỡng bác bỏ (failure threshold) cho các phép kiểm tra thể chất (health test) theo yêu cầu của SP 800-90B. Mô hình ngẫu nhiên cũng có thể có các thành phần môi trường (ví dụ, nhiệt độ, điện áp,…).

Việc kiểm tra giả thuyết thống kê (trong xác nhận nguồn entropy) chủ yếu liên quan đến việc kiểm tra xem một nguồn entropy vật lý có hoạt động như dự đoán của mô hình ngẫu nhiên của nó hay không.

Phân tích các bộ tạo tham khảo trong Phụ lục D của SP 800-22.

Phụ lục D của SP 800-22 có đưa ra 10 bộ tạo số giả ngẫu nhiên tham khảo với mục đích để thử nghiệm 15 phép kiểm tra thống kê, bao gồm:

Bộ tạo đồng dư tuyến tính (LCG)

Bộ tạo đồng dư bậc hai I (QCG-I)
Bộ tạo đồng dư bậc hai II (QCG-II)
Bộ tạo đồng dư bậc ba (CCG)
Bộ tạo Exclusive OR (XORG)
Bộ tạo lũy thừa modulo (MODEXP)
Bộ tạo hàm băm an toàn (G-SHA1)
Bộ tạo Blum-Blum-Shub (BBSG)
Bộ tạo Micali-Schnorr (MSG)
Các số vô tỷ đại số

Trong [4] đã trình bày các lý do mà các bộ tạo số ngẫu nhiên trên là không an toàn do mắc phải một hoặc nhiều trong số các yếu điểm sau: do có cửa hậu, do có điểm yếu trong thiết kế, do sử dụng nguyên thủy mật mã yếu, không kháng được máy tính lượng tử,…

KẾT LUẬN

Trong [5] Markku-Juhani O. Saarinen đã trình bày các quan điểm của mình về NIST SP 800-22. Ông đưa ra ý kiến: trái với sự mong đợi của nhiều nhà mật mã, SP 800-22 không bị thu hồi mà sẽ được sửa đổi thay thế. Đó là do các bộ yếu nhất trong số các bộ tạo số giả ngẫu nhiên cũng dễ dàng vượt qua các phép kiểm tra của SP 800-22, điều này thúc đẩy sự tin tưởng sai lầm vào các hệ thống không an toàn.

Theo quan điểm cá nhân, những ý kiến của Markku-Juhani O. Saarinen là xác đáng. Tuy nhiên, vẫn cần dùng một hệ tiêu chuẩn kiểm tra thống kê để đánh giá về tính ngẫu nhiên mà một thuật toán mật mã cần có. Tuy nhiên, đó chỉ là công việc ban đầu trong việc đánh giá độ an toàn mật mã (điều kiện cần thiết tối thiểu cần vượt qua). Ngày nay đã có nhiều lý thuyết toán học được sử dụng để nghiên cứu mật mã chứ không chỉ có xác suất thống kê.

Chúng ta cần quan tâm theo dõi phiên bản cập nhật của SP 800-22 xem nó đạt được bao nhiêu mục tiêu đã đạt ra trong [7] cũng như [4]. Có thể nói, mật mã là khoa học về tính ngẫu nhiên, trong khi SP 800-90A [9] đã có bản chỉnh sửa lần thứ nhất thì SP 800-90C mới chỉ có bản dự thảo.

TÀI LIỆU THAM KHẢO

Andrew Rukhin, Juan Soto, James Nechvatal, Miles Smid, Elaine Barker, Stefan Leigh, Mark Levenson, Mark Vangel, David Banks, Alan Heckert, James Dray, and San Vo, A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, NIST Special Publication 800-22, https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22.pdf.
Nicu Neculache and Vlad-Andrei Petcu and Emil Simion, A remark on the NIST 800-22 Binary Matrix Rank Test, https://eprint.iacr.org/2022/061.
Anghel Florin and Asandoaiei David and Tabacaru Robert, A remark on the Discrete Fourier Transform statistical test, https://eprint.iacr.org/2022/061
Markku-Juhani O. Saarinen, NIST SP 800-22 and GM/T 0005-2012 Tests: Clearly Obsolete, Possibly Harmful, https://eprint.iacr.org/2022/169
Corina-Elena Bogos and Razvan Mocanu and Emil Simion, A remark on NIST SP 800-22 serial test, https://eprint.iacr.org/2022/172
Andrew Rukhin, Juan Soto, James Nechvatal, Miles Smid, Elaine Barker, Stefan Leigh, Mark Levenson, Mark Vangel, David Banks, Alan Heckert, JamesDray, and San Vo. A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST Special Publication SP 800-22 Revision 1a, April 2010. doi:10.6028/NIST.SP.800-22r1a.
NIST, Announcement of Proposal to Revise Special Publication 800-22 Revision 1a, January 12, 2022, https://csrc.nist.gov/News/2022/proposal-to-revise-sp-800-22-rev-1
SCA. Randomness test specification. Cryptography Industry Standard of the P.R. China GM/T 0005-2012, March 2012.
Elaine Barker and John Kelsey. Recommendation for random number generation using deterministic random bit generators. NIST Special Publication SP 800- 90A Revision 1, June 2015. doi:10.6028/NIST.SP.800-90Ar1.
Meltem Sönmez Turan, Elaine Barker, John Kelsey, Kerry A. McKay, Mary L. Baish, and Mike Boyle. Recommendation for the entropy sources used for random bit generation. NIST Special Publication SP 800-90B, January 2018. doi:10.6028/NIST.SP.800-90B.
Elaine Barker, John Kelsey, Allen Roginsky, Meltem Sönmez Turan, Darryl Buller, and Aaron Kaufer. Recommendation for random bit generator (RBG) constructions. Draft NIST Special Publication SP 800-90C, March 2021.
NIST. Security requirements for cryptographic modules. Federal Information Processing Standards Publication FIPS 140-3, March 2019. doi:10.6028/NIST.FIPS.140-3.
NIST and CCCS. Implementation guidance for FIPS 140-3 and the cryptographic module validation program. CMVP, November 2021.
NIAP. Clarification to the entropy documentation and assessment annex. National Information Assurance Partnership, Common Criteria Evaluation and Validation Scheme, 2013.
NIAP. Entropy submission and review process. National Information Assurance Partnership, Common Criteria Evaluation and Validation Scheme, 2013.
Wolfgang Killmann and Werner Schindler. A proposal for: Functionality classes for random number generators. AIS 20/AIS 31, Version 2.0, English Translation, BSI, September 2011. URL: https://www.bsi.bund.de/ SharedDocs/Downloads/DE/BSI/Zertifizierung/Interpretationen/ AIS_31_Functionality_classes_for_ random_number_generators_e.html.