NIST SP 800-22 và những cẩn trọng khi sử dụng (Phần I)

Trong các ứng dụng mật mã, việc đánh giá chất lượng của bộ sinh số ngẫu nhiên và giả ngẫu nhiên đóng vai trò cực kỳ quan trọng, và việc đánh giá tính ngẫu nhiên theo thống kê là một yêu cầu cơ bản nhất trong quá trình đánh giá đó. NIST SP 800-22 đã được đưa ra và trở thành một công cụ hữu ích, phổ biến nhất cho việc đánh giá tính ngẫu nhiên theo thống kê đối với các bộ sinh trên. Tuy nhiên, cho đến nay dù được sử dụng khá rộng rãi nhưng vẫn còn những điểm bất cập trong bộ kiểm tra này, khi một số kiểm tra thống kê còn chưa chính xác. Trong nội dung của bài báo, chúng tôi sẽ đưa ra một góc nhìn chung về bộ kiểm tra tính ngẫu nhiên theo thống kê NIST SP 800-22 cho các bộ tạo số ngẫu nhiên và giả ngẫu nhiên, đồng thời trình bày các vấn đề còn tồn tại và đưa ra một vài lưu ý đối với việc sử dụng công cụ này.

MỞ ĐẦU

Các số ngẫu nhiên và giả ngẫu nhiên đã và đang đóng một vai trò quan trọng trong nhiều lĩnh vực, chẳng hạn như cơ học lượng tử, lý thuyết trò chơi, mật mã… Trong mật mã, các số có tính ngẫu nhiên (gồm các số ngẫu nhiên hoặc giả ngẫu nhiên) lại càng quan trọng hơn và được sử dụng nhiều. Chẳng hạn, các hệ mật thường sử dụng các khóa được tạo ra như một đại lượng ngẫu nhiên. Nhiều giao thức mật mã cũng yêu cầu các đầu vào có tính ngẫu nhiên, ví dụ đối với các tham số bổ trợ trong việc sinh chữ ký số hoặc trong việc tạo ra các thách thức ngẫu nhiên trong các giao thức xác thực.

Hơn nữa, độ an toàn của nhiều lược đồ và giao thức mật mã phụ thuộc chủ yếu vào các thành phần (có tính) ngẫu nhiên đó.

Có hai loại bộ sinh số ngẫu nhiên (RNGs) cơ bản được sử dụng để sinh các dãy số ngẫu nhiên: các bộ sinh số ngẫu nhiên thực sự (True Random Number Generators (TRNGs)) và các bộ sinh số giả ngẫu nhiên (Pseudo/Deterministic Random Number Generators (PRNGs)). Trong các ứng dụng mật mã, cả hai loại bộ sinh này tạo ra một chuỗi các bit 0 và 1 mà có thể chia thành các chuỗi con hoặc các khối của các số ngẫu nhiên. Đối với việc kiểm tra tính ngẫu nhiên, các kiểm tra dựa trên giả thiết thống kê được sử dụng rộng rãi để đánh giá chất lượng của các bộ sinh số ngẫu nhiên, trong đó kiểm tra xem khi nào các dãy đầu ra có phù hợp với giả thiết cho trước, tức là dãy có tính ngẫu nhiên hoàn thiện (perfect randomness) hay không. Hơn nữa các kiểm tra tính ngẫu nhiên theo thống kê cũng được sử dụng để đánh giá đầu ra của các nguyên thủy mật mã, chẳng hạn như các mã khối, hàm băm để bước đầu đánh giá tính không thể phân biệt được giữa các đầu ra của chúng với đầu ra được chọn ngẫu nhiên. Một số bộ kiểm tra thống kê được sử dụng phổ biến bao gồm: bộ tiêu chuẩn kiểm tra được đề xuất bởi Knuth [1], Diehard [2] được đề xuất bởi Marsaglia và sử dụng phổ biến nhất hiện nay chính là NIST SP 800-22 [3] và được chuẩn hóa bởi Viện Tiêu chuẩn và Công nghệ quốc gia Hoa kỳ (NIST). Theo chúng tôi, một trong những lý do là bởi vì NIST công bố mã nguồn của bộ kiểm tra này. Bộ kiểm tra của NIST ban đầu gồm 16 tiêu chuẩn kiểm tra, sau đó trong bản cập nhật mới nhất năm 2010 rút xuống còn 15 tiêu chuẩn, khi loại bỏ đi tiêu chuẩn nén Lempel-Ziv. Đã có nhiều nghiên cứu chỉ ra rằng, một số tiêu chuẩn kiểm tra của NIST là chưa chính xác và cần phải chỉnh sửa hoặc thay thế bằng cách tiêu chuẩn khác.

Đối với người dùng khi tiếp cận bộ tiêu chuẩn này sẽ có 3 vấn đề chính được đặt ra. Thứ nhất, đọc hiểu và nắm được chi tiết và chính xác nội dung trong tài liệu mà NIST đã công bố. Các nội dung chính trong tài liệu này sẽ được chúng tôi trình bày sơ lược trong phần II. Vấn đề thứ hai đó là việc khai thác sử dụng chính xác mã nguồn của bộ kiểm tra, đồng thời kiểm tra tính đúng đắn, đối chiếu giữa mã nguồn và mô tả lý thuyết trong tài liệu. Ở mức cao hơn, người dùng có thể tùy chỉnh mã nguồn để chính xác hóa các công thức hoặc bổ sung các kiểm tra khác theo ý muốn. Vấn đề cuối cùng, cũng là khó khăn nhất đó chính là đảm bảo cơ sở lý thuyết cho các kiểm tra của bộ kiểm tra này. Trong tài liệu mà NIST công bố, họ không đưa ra cơ sở lý thuyết một cách rõ ràng mà chỉ liệt kê các tài liệu liên quan đến kiểm tra tương ứng. Theo đánh giá của chúng tôi, có những kiểm tra đã có cơ sở lý thuyết một cách rõ ràng như kiểm tra tần số, kiểm tra tần số trong một khối; lại có những kiểm tra có thể làm rõ được cơ sở lý thuyết theo các tài liệu công bố như kiểm tra loạt, hạng ma trận, so khớp mẫu, độ phức tạp tuyến tính, tổng tích lũy; nhưng cũng có những kiểm tra không dễ để có thể làm rõ cơ sở lý thuyết như kiểm tra DFT, Serial, phổ quát của Maurer, entropy xấp xỉ, viếng thăm ngẫu nhiên và biến thể viếng thăm ngẫu nhiên.

CÁC NỘI DUNG CHÍNH TRONG NIST SP 800-22

Như đã trình bày, vấn đề đầu tiên đối với người dùng là đọc hiểu và nắm được chi tiết tài liệu báo cáo mà NIST công bố. Tài liệu NIST SP 800-22 Revision 1a dài 131 trang, được chia làm 5 Mục và 7 Phụ lục. Mục 1 của tài liệu đưa ra một số khái niệm về tính ngẫu nhiên, độ bất định, các bộ sinh số ngẫu nhiên và giả ngẫu nhiên cùng với một số khái niệm và ký hiệu toán học. Mục 2 chiếm phần lớn nội dung khi trình bày về mục đích, cách gọi hàm, mô tả, phân phối tham chiếu, mức ý nghĩa, tham số khuyến cáo và ví dụ cho 15 kiểm tra thống kê. Trong tài liệu này, NIST không trình bày chi tiết về cơ sở lý thuyết cho các kiểm tra mà chỉ trích dẫn đến các tài liệu đã được công bố. Mục 3 liệt kê các tài liệu trên đối với mỗi kiểm tra thống kê. Mục 4 trình bày chiến lược phân tích thống kê cho một RNG (Random Number Generators). Mục 5 trình bày hướng dẫn sử dụng mã nguồn cài đặt của bộ kiểm tra này.

Ngoài ra, một số thông tin khác được trình bày trong các phụ lục: Phụ lục A trình bày về mã nguồn cài đặt của bộ kiểm tra. Phụ lục B trình bày một số kết quả thực nghiệm đối với các dữ liệu mẫu. Phụ lục C giúp người dùng có thể tùy chỉnh mã nguồn để bổ sung các kiểm tra khác. Phụ lục D mô tả của các bộ sinh số giả ngẫu nhiên có sẵn trong mã nguồn cài đặt của bộ kiểm tra. Phụ lục E trình bày một số hàm số học tính toán được sử dụng trong các kiểm tra như hàm gamma, hàm lỗi. Phụ lục F trình bày một số phần mềm hỗ trợ tính toán như Mathematica để tính toán một số hàm trung gian trong các kiểm tra.

Kính mời quý độc giả xem chi tiết bài báo tại đây