Xây dựng các nguồn entropy nhằm tạo ra các đầu ra không thể dự đoán được là rất khó, và đưa ra các chỉ dẫn cung cấp chỉ dẫn cho việc thiết kế và kiểm tra đánh giá chúng còn khó hơn nhiều. NIST đã phát hành tài liệu SP 800-90B nhằm giúp các nhà phát triển hiểu quy trình đánh giá, lập kế hoạch quy trình đánh giá và thực hiện đánh giá nguồn entropy sử dụng cho các bộ tạo số ngẫu nhiên, trong đó giả định rằng các nhà phát triển hiểu rõ cách xử lý của nguồn nhiễu trong nguồn entropy và nỗ lực để đưa ra nguồn entropy ngẫu nhiên. Bài viết dưới đây sẽ giới thiệu về mô hình và đánh giá nguồn entropy sử dụng cho các bộ tạo số ngẫu nhiên theo NIST.

Đôi nét về bộ tiêu chuẩn NIST SP 800-90

Năm 2012, NIST đã công bố các bản dự thảo SP 800-90 [1-3], cung cấp hướng dẫn xây dựng và đánh giá các bộ sinh bit ngẫu nhiên (Random Bit Generators (RBGs)) có dạng bộ sinh bit ngẫu nhiên tất định (Deterministic Random Bit Generators (DRBGs)) hoặc bộ sinh bit ngẫu nhiên không tất định (Non-deterministic Random Bit Generators (NRBGs)) mà có thể được sử dụng trong các ứng dụng mật mã. Dự thảo SP 800-90B [2] mô tả cách thiết kế và đánh giá các nguồn entropy mà có thể được sử dụng bởi RNG (Random Number Generators). Dự thảo SP 800-90A mô tả cấu trúc của các cơ chế sinh bit ngẫu nhiên tất định được phê chuẩn. Năm 2015 dự thảo này đã được rút lại do có một lỗ hổng bảo mật trong thuật toán Dual_ EC_DRBG được mô tả trong bản dự thảo này.

Năm 2016, NIST đã cập nhật bản dự thảo này và loại bỏ thuật toán Dual_EC_DRBG, cùng với đó cập nhật lại dự thảo SP 800-90B, và SP 800-90C. Đến tháng 1/2018, NIST đã công bố bản cập nhật cuối cùng cho chuẩn SP 800-90B [4]. Dự thảo SP 800-90C mô tả cấu trúc các bộ sinh bit ngẫu nhiên từ các cơ chế trong SP 800-90A và các nguồn entropy trong SP 800-90B. Các khuyến nghị này cung cấp một cơ sở cho việc phê chuẩn bởi chương trình phê chuẩn thuật toán mật mã (Cryptographic Algorithm Validation Program (CAVP)) và chương trình phê chuẩn mô-đun mật mã (Cryptographic Module Validation Program (CMVP)) của NIST.

Entropy và mô hình nguồn entropy

Entropy được định nghĩa như một độ đo mức độ bất định của một biến ngẫu nhiên. Nếu ξ là một biến ngẫu nhiên rời rạc được xác định trên không gian xác suất (Ω, F, P) và giả sử các giá trị x₁,x₂,...,x_k, với phân bố xác suất {p_i | i = 1,2,...,k}; p_i = P {ξ = x_i}, khi đó entropy được xác định bởi công thức:

Độ đo này còn được biết đến là entropy Shannon, nó đưa ra độ đo entropy trường hợp trung bình cho một phân bố độc lập của các biến ngẫu nhiên. Theo chuẩn SP 800-90B của NIST [4], một độ đo entropy tốt hơn được sử dụng đó là min-entropy, còn được biết đến là entropy Rényi. Minentropy của một biến ngẫu nhiên rời rạc độc lập X mà nhận các giá trị từ tập A = {x₁,x₂,…,x_k} với xác suất Pr(X = x_i) = p_i với i = 1,...,k được định nghĩa là

Trong mật mã, tính không thể dự đoán được của các giá trị bí mật (chẳng hạn như các khoá mật mã) là rất cần thiết. Xác suất mà một giá trị bí mật được dự đoán chính xác trong lần thử đầu tiên có liên quan đến min-entropy của phân bố mà giá trị bí mật đó được tạo ra. Nếu X có min-entropy là H, thì xác suất của việc thu được một giá trị bất kỳ của X là không lớn hơn 2^-H. Giá trị lớn nhất có thể cho min-entropy của một biến ngẫu nhiên với k giá trị phân biệt là log₂k , đạt được khi biến ngẫu nhiên có một phân bố xác suất đều, tức là p₁ = p₂ = ... = p_k = 1/k.

Trong SP 800-90B, NIST đã đưa ra một mô hình nguồn entropy tổng quát bao gồm: một nguồn nhiễu (noise source), một thành phần điều chế (conditioning) (tuỳ chọn) và một thành phần kiểm tra chất lượng (health test).

Hình 1. Mô hình nguồn entropy

- Nguồn nhiễu: Nguồn nhiễu là gốc rễ của độ an toàn cho nguồn entropy và cho toàn bộ RBGs. Đây là thành phần chứa hoạt động cung cấp entropy không tất định, chịu trách nhiệm về tính bất định trong các xâu bit đưa ra bởi nguồn entropy.

Các nguồn nhiễu có thể chia thành 2 loại: Các nguồn nhiễu vật lý (Physical noise sources) sử dụng phần cứng chuyên dụng để tạo ra tính ngẫu nhiên; trong khi các nguồn nhiễu phi-vật lý (Nonphysical noise sources) sử dụng dữ liệu hệ thống (chẳng hạn như đầu ra của các hàm giao diện chương trình ứng dụng, dữ liệu RAM hoặc thời gian hệ thống) hoặc đầu vào bởi con người (ví dụ các di chuyển chuột) để tạo ra tính ngẫu nhiên.

Nếu nguồn nhiễu không tạo ra các đầu ra ngẫu nhiên, thì không có thành phần nào khác trong RBGs có thể bù đắp cho việc thiếu entropy; do đó, không thể đảm bảo an toàn cho ứng dụng dựa trên RBGs.

- Thành phần điều chế: Thành phần điều chế (tùy chọn) là một hàm tất định chịu trách nhiệm cho việc giảm độ lệch và/hoặc tăng tỷ lệ entropy của các bit đầu ra thu được.

Có nhiều lựa chọn khác nhau cho thành phần điều chế. Các nhà phát triển nên xem xét các thành phần điều chế được sử dụng và các biến thể trong trạng thái của nguồn nhiễu có thể ảnh hưởng đến tỷ lệ entropy của đầu ra như thế nào. Khi chọn phương pháp cài đặt, nhà phát triển có thể chọn triển khai thuật toán mã hóa được liệt kê chi tiết trong SP 800-90B.

- Kiểm tra chất lượng: Đây là một thành phần quan trọng của nguồn entropy nhằm phát hiện sai lệch so với trạng thái dự kiến của nguồn nhiễu càng nhanh càng tốt và với xác suất cao. Nguồn nhiễu có thể dễ hỏng, và do đó có thể bị ảnh hưởng bởi những thay đổi trong điều kiện vận hành của thiết bị, chẳng hạn như nhiệt độ, độ ẩm hoặc điện trường, và có thể dẫn đến trạng thái không mong muốn.

Kiểm tra chất lượng của nguồn nhiễu thường dựa trên đầu ra kỳ vọng khi lỗi hoặc phát hiện sai lệch so với đầu ra kỳ vọng trong quá trình vận hành chính xác nguồn nhiễu. Kiểm tra chất lượng dự kiến sẽ báo động trong ba trường hợp:

1) Khi có sự sụt giảm đáng kể entropy của đầu ra

2) Khi xảy ra lỗi nguồn nhiễu

3) Khi phần cứng bị lỗi và cài đặt không hoạt động chính xác

Các kiểm tra chất lượng có thể chia thành 3 loại: các kiểm tra khởi động, các kiểm tra liên tục (chủ yếu trên nguồn nhiễu) và các kiểm tra theo yêu cầu.

Đánh giá nguồn entropy

Việc đánh giá nguồn entropy là rất cần thiết để đạt được sự đảm bảo rằng nguồn entropy sẽ cung cấp đủ tính ngẫu nhiên làm đầu vào cho các bộ sinh bit ngẫu nhiên tất định. NIST đã đưa ra một quy trình chuẩn nhằm đánh giá nguồn entropy. Cụ thể, một nguồn entropy có thể được gửi lên một phòng thí nghiệm đã được công nhận cho việc kiểm tra đánh giá. Nguồn entropy này có thể là của các nhà phát triển hoặc một tổ chức hoặc cá nhân bất kỳ mong muốn đánh giá nguồn entropy đó. Sau khi nguồn entropy được đệ trình cho việc đánh giá, các phòng thí nghiệm sẽ kiểm tra tất cả tài liệu và chứng minh lý thuyết được đệ trình. Các phòng thí nghiệm sẽ đánh giá các khẳng định đó, và có thể yêu cầu làm rõ hơn các chứng minh. Quy trình đánh giá một nguồn entropy gồm 4 giai đoạn chính và 1 giai đoạn bổ sung nếu nguồn entropy có sử dụng thành phần điều chế:

Giai đoạn 1: Thu thập dữ liệu

Người đệ trình sẽ cung cấp các dữ liệu sau cho việc ước lượng entropy, theo các yêu cầu được trình bày trong SP 800-90B. 

Hình 2. Chiến lược ước lượng entropy

1. Một tập dữ liệu mẫu cho việc đánh giá gồm tối thiểu 1.000.000 giá trị liên tiếp được thu trực tiếp từ nguồn nhiễu (tức là dữ liệu thô).

2. Nếu nguồn entropy bao gồm các thành phần điều chế không được liệt kê đầy đủ thì một tập dữ liệu liên tiếp đã được điều chế với tối thiểu 1.000.000 đầu ra của thành phần điều chế sẽ được thu thập để đánh giá.

3. Đối với các kiểm tra khởi động lại, nguồn entropy phải được khởi động lại tối thiểu là 1000 lần; đối với mỗi lần khởi động lại, 1000 mẫu liên tiếp sẽ được thu thập trực tiếp từ nguồn nhiễu. Dữ liệu này được lưu trong một ma trận khởi động M kích thước 1000x1000, trong đó M[i][j] biểu diễn mẫu thứ j từ lần khởi động thứ i.

Giai đoạn 2: Xác định đường (track) dữ liệu - đường IID và đường non-IID

Một ưu điểm của chuẩn SP 800-90B đó là việc đánh giá entropy không cần bất kỳ giả thiết nào về phân bố của tập dữ liệu. Cụ thể, chuẩn SP 800-90B sẽ ước lượng entropy đối với hai trường hợp đối với các mẫu của nguồn nhiễu: một đường phân bố đồng nhất và độc lập (independent and identically distributed (IID)) và một đường non-IID. Đường IID được sử dụng cho nguồn nhiễu mà sinh các mẫu có phân bố đồng nhất và độc lập, trong khi đường non-IID được sử dụng cho các nguồn nhiễu mà không tạo ra các mẫu IID.

NIST đã sử dụng 2 kiểu kiểm tra để kiểm định giả thiết IID: Kiểm tra hoán vị và Kiểm tra X².

Giai đoạn 3: Ước lượng entropy khởi tạo

Người đệ trình sẽ cung cấp một ước lượng entropy cho nguồn nhiễu dựa trên các phân tích đối với nguồn nhiễu. Ước lượng này được ký hiệu là H_submitter.

Sau khi xác định đường để ước lượng entropy, một ước lượng min-entropy trên mẫu, được ký hiệu là H_original, đối với tập dữ liệu tuần tự được tính sử dụng các phương pháp sau:

Đối với đường IID: sử dụng một bộ ước lượng duy nhất

• Ước lượng giá trị phổ biến nhất (The Most Common Value Estimate)

Đối với đường non-IID: sử dụng 10 bộ ước lượng

• Ước lượng giá trị phổ biến nhất (The Most Common Value Estimate),
• Ước lượng va chạm (The Collision Estimate),
• Ước lượng Markov (The Markov Estimate),
• Ước lượng nén (The Compression Estimate),
• Ước lượng t-bộ (The t-Tuple Estimate),
• Ước lượng dãy con lặp lại dài nhất (The Longest Repeated Substring (LRS) Estimate),
• Ước lượng dự đoán nhiều giá trị phổ biến nhất trong cửa sổ (The Multi Most Common in Window Prediction Estimate),
• Ước lượng dự đoán sự trễ (The Lag Prediction Estimate),
• Ước lượng dự đoán MultiMMC (The MultiMMC Prediction Estimate),
• Ước lượng dự đoán LZ78Y (The LZ78Y Prediction Estimate).

Nếu tập dữ liệu không phải nhị phân, thì một ước lượng entropy bổ sung (trên bit), được ký hiệu là H_bitstring, được ước lượng.

• Ước lượng entropy khởi tạo của nguồn nhiễu được tính là:
  • H₁=min(H_original,n * H_bitstring,H_submitter) đối với các nguồn không nhị phân,
  • H1=min(H_original, H_submitter) cho các nguồn nhị phân.

Giai đoạn 4: Các kiểm tra khởi động lại

Ước lượng entropy của nguồn nhiễu, được tính từ một dãy đầu ra dài duy nhất, có thể cung cấp một ước lượng vượt quá nếu nguồn nhiễu tạo ra các dãy có tương quan sau khi khởi động lại. Do đó, một kẻ tấn công sẽ truy cập vào nhiều dãy đầu ra của nguồn nhiễu sau khi khởi động lại có thể dự đoán dãy đầu ra tiếp theo với tỷ lệ thành công tốt hơn ước lượng entropy đề xuất. Các kiểm tra khởi động lại nhằm đánh giá lại ước lượng entropy cho nguồn nhiễu sử dụng các đầu ra khác nhau từ nhiều lần khởi động lại nguồn nhiễu. Các kiểm tra đó được thiết kế nhằm đảm bảo rằng:

- Các đầu ra của nguồn nhiễu được tạo ra sau một lần khởi động lại là được rút từ cùng một phân bố như các đầu ra khác.

- Phân bố của các mẫu trong một chuỗi khởi động lại là độc lập với vị trí của nó trong chuỗi khởi động lại.

- Tri thức về các chuỗi khởi động lại khác không đưa ra một lợi thế nào trong việc dự đoán chuỗi khởi động lại tiếp theo.

Giai đoạn 5: Ước lượng entropy cho các nguồn entropy sử dụng thành phần điều chế

Thành phần điều chế có thể được thiết kế theo nhiều cách khác nhau. SP 800-90B đã cung cấp danh sách các thuật toán/hàm mật mã đã được kiểm tra để điều chỉnh các đầu ra của nguồn nhiễu. Người đệ trình được phép sử dụng các thành phần điều chế khác; tuy nhiên, quá trình đánh giá entropy sẽ khác với trường hợp sử dụng một thành phần điều chế đã được kiểm tra.

Kết luận

Mô hình nguồn entropy và chiến lược đánh giá nguồn entropy đã được đề xuất trong chuẩn SP 800-90B [4] của NIST hướng đến việc xây dựng và đánh giá nguồn entropy để sử dụng cho các bộ sinh số ngẫu nhiên – một thành phần không thể thiếu trong các ứng dụng bảo mật thông tin. Theo đó, một mô hình nguồn entropy bao gồm 3 thành phần chính: nguồn nhiễu, thành phần điều chế (tuỳ chọn) và các kiểm tra chất lượng. Và quan trọng nhất đó là quá trình đánh giá nhằm ước lượng chính xác entropy của một nguồn entropy. Hiện nay, các phương pháp nhằm ước lượng chính xác min-entropy vẫn đang được các chuyên gia của NIST tiếp tục nghiên cứu, cập nhật và phát triển.

Tài liệu tham khảo [1]. Barker, E. and Kelsey, J., NIST special publication 800-90A: Recommendation for random number generation using deterministic random bit generators. 2012  [2]. Barker, E. and Kelsey, J., NIST DRAFT Special Publication 800-90b recommendation for the entropy sources used for random bit generation. 2012  [3]. Barker, E. and Kelsey, J., Recommendation for Random Bit Generator (RBGS) Constructions (DRAFT NIST Special Publication 800-90C). National Institute of Standards and Technology, 2012  [4]. Barker, E. and Kelsey, J., NIST Special Publication 800-90b: Recommendation for the Entropy Sources Used for Random Bit Generation. 2018, National Institute of Standards and Technology.