Về PRNG không hạt giống và Premature Next
On Seedless PRNGs and Premature Next.
Trình tạo số giả ngẫu nhiên có đầu vào (PRNG) là các thuật toán mật mã tạo ra bit giả ngẫu nhiên từ các đầu vào Entropy tích lũy (ví dụ: các lần nhấn phím, thời gian ngắt, v.v.). Bài nghiên cứu này nghiên cứu cụ thể các PRNG an toàn trước các cuộc tấn công Premature Next (Kelsey và cộng sự, FSE '98), một lớp tấn công tận dụng thực tế là PRNG có thể tạo ra đầu ra (có thể bị bên tấn công nhìn thấy!) trước khi tích lũy đủ Entropy. Các thiết kế thực tế áp dụng phương pháp ước tính Entropy không hợp lý để ngăn chặn các cuộc tấn công như vậy (như trong /dev/random của Linux) hoặc phương pháp tiếp cận dựa trên Pool tinh vi như trong Yarrow (MacOS/FreeBSD) và Fortuna (Windows). Nghiên cứu lý thuyết trước đây duy nhất về các cuộc tấn công Premature Next (Dodis và cộng sự, Algorithmica '17) xem xét một thiết lập có hạt giống hoặc giả định tỷ lệ Entropy không đổi, do đó không cung cấp và xác nhận các thiết kế thực tế. Giả sử tính khả dụng của hạt giống ngẫu nhiên đặc biệt có vấn đề, đầu tiên vì điều này yêu cầu các tác giả phải tạo ra một hạt giống ngẫu nhiên mà không cần sử dụng PRNG, nhưng cũng bởi vì hoj phải đảm bảo các đầu vào Entropy của PRNG vẫn độc lập với hạt giống. Thật vậy, tất cả các thiết kế thực tế đều không có hạt giống. Tuy nhiên, các công việc trước đây về PRNG không có hạt giống (Coretti và cộng sự, CRYPTO '19; Dodis và cộng sự, ITC '21, CRYPTO'21) không xem xét các cuộc tấn công Premature Next. Mục tiêu chính của bài nghiên cứu này là nghiên cứu tính khả thi của các PRNG không hạt giống có lý thuyết vững chắc và an toàn trước các cuộc tấn công Premature Next. Để đạt mục đích này, các tác giả có các đóng góp sau: 1. Các tác giả chứng minh không thể đạt được các PRNG không hạt giống an toàn trước các cuộc tấn công Premature Next, ngay cả trong một mô hình khá yếu. Cụ thể, sự bất khả thi vẫn tồn tại ngay cả khi các đầu vào Entropic của PRNG là độc lập. Đặc biệt, kết quả bất khả thi của các tác giả vẫn tồn tại trong các thiết lập mà các PRNG không hạt giống có thể thực hiện được. 2.Với kết quả bất khả thi nêu trên, các tác giả nghiên cứu xem các phương pháp tiếp cận dựa trên Pool không hạt giống hiện có nhằm khắc phục các cuộc tấn công Premature Next trong các thiết kế thực tế có cung cấp các đảm bảo có ý nghĩa trong một số thiết lập nhất định hay không. Cụ thể, các tác giả trình bày như sau: Họ giới thiệu điều kiện tự nhiên về đầu vào Entropic và chứng minh nó bao hàm tính bảo mật của quá trình tích lũy Entropy vòng tròn PRNG được Windows 10 sử dụng, có tên là Fortuna. Theo trực giác, tình trạng của các tác giả yêu cầu Entropy đầu vào “không thay đổi nhiều” trong một vòng tròn nhất định. Các tác giả chứng minh phương pháp “Root Pool” (cũng được sử dụng trong Windows 10) an toàn cho đầu vào Entropy tổng quát, với điều kiện trạng thái của hệ thống không được thỏa hiệp sau khi khởi động hệ thống.