Nghiên cứu xây dựng bộ sinh số ngẫu nhiên tích hợp với nhiều hệ điều hành

Bài viết này trình bày một nghiên cứu thiết kế bộ sinh số dựa trên hiện tượng jitter thời gian của CPU sử dụng trên hệ điều hành Linux và Windows. Số ngẫu nhiên sinh ra được đánh giá và vượt qua hầu hết các phép test thống kê của NIST.
Nội dung trích xuất từ tài liệu:
Nghiên cứu xây dựng bộ sinh số ngẫu nhiên tích hợp với nhiều hệ điều hành Công nghệ thông tin & Cơ sở toán học cho tin học<br /> <br /> NGHIÊN CỨU XÂY DỰNG BỘ SINH SỐ NGẪU NHIÊN<br /> TÍCH HỢP VỚI NHIỀU HỆ ĐIỀU HÀNH<br /> Nguyễn Thị Tuyết Trinh*, Nguyễn Hồng Quang, Đinh Tiến Thành<br /> Tóm tắt: Hầu hết các bộ tạo số ngẫu nhiên thực phi vật lý có được nguồn<br /> entropy dựa vào sự bất ổn trong thời gian hoạt động của các sự kiện phần cứng, do<br /> đó, không đủ đáp ứng những nhu cầu luôn tăng của số ngẫu nhiên có chất lượng<br /> cao. Vì thế, cần tìm thêm các nguồn entropy phi vật lý khác thay thế. Bài báo này<br /> trình bày một nghiên cứu thiết kế bộ sinh số dựa trên hiện tượng jitter thời gian của<br /> CPU sử dụng trên hệ điều hành Linux và Windows. Số ngẫu nhiên sinh ra được<br /> đánh giá và vượt qua hầu hết các phép test thống kê của NIST. Tốc độ sinh bit cao,<br /> không cần thiết kế phần cứng chuyên dụng, phù hợp với nhiều hệ điều hành là<br /> những ưu điểm nổi trội so với các bộ sinh số khác.<br /> Từ khóa: Số ngẫu nhiên, Jitter thời gian của CPU, TRNG, Mật mã, Đánh giá thống kê.<br /> <br /> 1. MỞ ĐẦU<br /> Số ngẫu nhiên đóng vai trò hết sức quan trọng trong rất nhiều lĩnh vực khác nhau mà<br /> đặc biệt là trong mật mã. Sự an toàn của hệ thống mật mã phụ thuộc rất nhiều vào tính<br /> ngẫu nhiên. Các bộ sinh số ngẫu nhiên có nguồn entropy phi vật lý không đòi hỏi phần<br /> cứng chuyên dụng mà khai thác các sự kiện hệ thống (thời gian của máy tính, số liệu trong<br /> RAM,...) và/hoặc sự tương tác người – máy (gõ phím, di chuyển chuột), thiết kế tương đối<br /> đơn giản, dễ thực hiện bằng phần mềm máy tính và giá thành hợp lý.<br /> Hiện nay, mỗi hệ điều hành đều có thể cung cấp nguồn entropy cho bộ sinh số ngẫu<br /> nhiên thực phi vật lý. Bộ sinh số ngẫu nhiên Linux (/dev/random) dựa trên bốn nguồn<br /> entropy khác nhau là thời gian giữa các lần gõ bàn phím và di chuột, thời gian truy cập bộ<br /> nhớ và các gián đoạn cụ thể ([2], [8]). Đầu ra được chuyển vào bộ trữ entropy có độ lớn<br /> 512 byte. Tuy nhiên, chất lượng của số ngẫu nhiên không cao, chỉ được đánh giá như số<br /> giả ngẫu nhiên. Tương tự, hệ điều hành Windows cũng cung cấp thư viện mật mã Crypt<br /> API với các tính năng như mã hóa, giải mã, lưu trữ khóa, hàm băm, chữ ký số và và đặc<br /> biệt là bộ sinh số ngẫu nhiên. Nguồn entropy của bộ sinh số này là thời gian xử lý của<br /> CPU, thời gian hiện thời của hệ thống..., sau đó được xử lý qua hàm SHA-512, tạo ra đầu<br /> ra 512 bit ([2]). Tháng 10 năm 2014, Stephan Müller đã đề xuất bộ sinh số ngẫu nhiên<br /> thực phi vật lý dựa trên hiện tượng jitter thời gian của CPU với quá trình xử lý sau phức<br /> tạp, ảnh hưởng đến tốc độ và chỉ chạy trên hệ điều hành Linux ([1], [3]).<br /> Do đó, trong nghiên cứu này chúng tôi đề xuất một phương pháp riêng, xây dựng bộ<br /> sinh số ngẫu nhiên cũng có nguồn entropy là jitter thời gian của CPU nhưng có thiết kế<br /> đơn giản hơn, tốc độ thực thi cao và chạy được trên cả hệ điều hành Linux và Windows.<br /> 2. THIẾT KẾ BỘ SINH SỐ NGẪU NHIÊN<br /> Sau khi nghiên cứu các sản phẩm của các tác giả khác, chúng tôi phân tích hiện tượng<br /> jitter thời gian của CPU sử dụng làm nguồn entropy, tiến hành thiết kế cụ thể, triển khai<br /> thử nghiệm để kiểm chứng.<br /> 2.1. Jitter trong thời gian hoạt động của CPU<br /> Với sự phức tạp cao của các hệ điều hành hiện đại và hạt nhân nguyên khối lớn của<br /> chúng, tất cả các thành phần phần cứng phức tạp đều được sử dụng rộng rãi. Tuy nhiên, do<br /> sự phức tạp, không ai có thể xác định chính xác mức độ lấp đầy của các cache hoặc vị trí<br /> <br /> <br /> 126 N. T. T. Trinh, …, Đ. T. Thành, “Nghiên cứu xây dựng bộ sinh số… nhiều hệ điều hành.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> chính xác của dữ liệu trong bộ nhớ tại một thời điểm nhất định nào đó. Điều đó dẫn đến<br /> việc thực hiện các lệnh có thể có các biến động rất nhỏ trong thời gian thực hiện. Ngoài ra<br /> CPU hiện đại có một bộ đếm thời gian độ phân giải cao, có thể xác định được các biến<br /> động rất nhỏ này. Ví dụ, CPU x86 hiện đại có một bộ định giờ TSC có độ phân giải trong<br /> phạm vi nano giây.<br /> Có thể nhận thấy những thay đổi trong thời gian thực hiện một bộ giống hệt các lệnh<br /> của CPU. Hình 1 minh họa sự biến đổi của thời gian thực hiện đoạn mã sau đây:<br /> static inline void jent_get_nstime(uint64_t *out)<br /> {...<br /> if (clock_gettime(CLOCK_REALTIME, &time) == 0)<br /> ...}<br /> void main(void)<br /> {...<br /> jent_get_nstime(&time);<br /> jent_get_nstime(&time2);<br /> delta = time2 - time;<br /> ...}<br /> Các giá trị của biến delta là không giống nhau giữa các lần lặp lại vòng lặp riêng<br /> lẻ. Khi chạy đoạn mã trên với 1.000.000 vòng lặp trên một hệ thống đang ở trạng thái tĩnh<br /> (không thực hiện các tác vụ khác) để giảm thiểu sai khác về thời gian do các quá trình đó<br /> gây ra.<br /> <br /> <br /> <br /> <br /> Hình 1. Phân bố sự biến đổi thời gian hoạt động của CPU.<br /> 2.2. Mô hình bộ sinh số ngẫu nhiên<br /> Bộ sinh số ngẫu nhiên dựa trên hiện tượng jitter thời gian của CPU sử dụng bộ đọc thời<br /> gian có độ phân giải cao để lấy tem thời gian. Đầu ra của bộ sinh là một số nguyên dương<br /> có ...