Gần như mọi thứ bạn từng thấy được gắn mác “ngẫu nhiên” trên máy tính từ việc rút thẻ trong game, roll damage crit, cho tới token xác thực OTP – đều là giả. Không phải nó sai, mà theo nghĩa nó được tính toán ra bằng một công thức xác định 100%. Cùng một input, chạy lại bao nhiêu lần cũng ra đúng y kết quả đó.
Nghe có vẻ vô lý nhưng đó chính xác là cách PRNG (Pseudo-Random Number Generator) hoạt động, và nó là một trong những phần “âm thầm” nhất của hạ tầng phần mềm. Ít ai để ý, cho tới khi nó bị làm sai.
Vì sao máy tính không thể ngẫu nhiên thật
CPU là một cỗ máy xác định (deterministic) vì cho nó cùng một trạng thái, cùng một lệnh, nó sẽ luôn cho ra cùng một kết quả. Đó là điều bắt buộc để máy tính hoạt động ổn định vì bạn không muốn 2 + 2 thỉnh thoảng ra 5 (không logic tí nào).
Ngẫu nhiên thật (true randomness) chỉ có thể lấy từ các nguồn vật lý: nhiễu nhiệt trong mạch điện, thời gian giữa các lần gõ phím, độ trễ ngắt của ổ đĩa, phân rã phóng xạ (🐧) hoặc chụp ảnh đèn lava như của Cloudflare. Nhưng lấy entropy vật lý chậm, tốn tài nguyên, và không phải lúc nào cũng đủ nhanh để phục vụ hàng triệu request random mỗi giây.
Giải pháp là lấy một chút entropy thật (gọi là seed), đưa vào một thuật toán, rồi để thuật toán đó kéo dài nó ra thành một chuỗi số trông có vẻ ngẫu nhiên, nhưng thực chất là một chuỗi xác định được tạo từ seed ban đầu. Đó là PRNG.
Vài thuật toán PRNG
Linear Congruential Generator (LCG) là một thuật toán tạo ra một dãy số giả ngẫu nhiên bằng cách sử dụng phương trình truy hồi tuyến tính. Nó dựa trên một giá trị tuyệt đối, một hệ số nhân và một gia số. Công thức chỉ vỏn vẹn:
X(n+1) = (a * X(n) + c) mod mBa hằng số a, c, m được chọn kỹ để chuỗi số sinh ra có chu kỳ dài và phân bố đều. rand() trong C thời xưa, hàm Random cũ của Java, đều dựa trên biến thể của LCG. Ưu điểm: cực nhanh, cực nhẹ. Nhược điểm: nếu bạn biết vài số liên tiếp trong chuỗi, bạn có thể suy ngược ra toàn bộ chuỗi còn lại. Vì vậy LCG tuyệt đối không được dùng cho bất cứ thứ gì liên quan đến bảo mật.
Mersenne Twister là cái tên bạn sẽ gặp nếu từng đọc source code Python (random module), hay hàm mt_rand() trong PHP. Chu kỳ của nó dài tới mức gần như không bao giờ lặp lại trong thực tế sử dụng thông thường. Nó cho phân bố thống kê rất đẹp, chạy nhanh, và là lựa chọn mặc định hợp lý cho hầu hết nhu cầu “ngẫu nhiên cho có” trong ứng dụng thông thường. Điểm yếu của nó là nếu ai đó quan sát đủ nhiều giá trị output liên tiếp, họ có thể suy ngược ra toàn bộ trạng thái nội bộ và đoán chính xác các số tiếp theo. Vì vậy nó ổn cho game, mô phỏng, nhưng không nên dùng cho bất cứ thứ gì liên quan bảo mật.
PCG (Permuted Congruential Generator) ra đời để vá điểm yếu đó mà vẫn giữ tốc độ. Ý tưởng vẫn dùng lõi đơn giản kiểu LCG, nhưng thêm một bước “xáo trộn” (permutation) lên output trước khi trả về, khiến việc suy ngược trạng thái nội bộ khó hơn hẳn. Đây là lựa chọn ngày càng phổ biến trong các thư viện hiện đại vì tốc độ gần bằng LCG nhưng chất lượng thống kê và khả năng chống đoán tốt hơn nhiều.
Xorshift và các biến thể của nó hoạt động bằng cách dịch bit và XOR liên tục lên một trạng thái nội bộ, đơn giản tới mức chỉ vài dòng code là đủ để implement. Cực kỳ nhanh, tận dụng tốt các phép toán bit-level của CPU, nên hay được chọn khi hiệu năng là ưu tiên số một, ví dụ như sinh hàng loạt vị trí hạt (particle) trong game hoặc mô phỏng vật lý. Trình duyệt và Node.js cũng dùng một biến thể của nó đằng sau hàm random tiêu chuẩn.
PRNG thường vs CSPRNG
- PRNG thường (Mersenne Twister, PCG, Xorshift…): tối ưu cho tốc độ và chất lượng thống kê. Dùng cho game, mô phỏng, sinh dữ liệu test, xáo bài trong app không liên quan tiền bạc.
- CSPRNG (Cryptographically Secure PRNG): tối ưu cho việc không thể đoán trước, kể cả khi kẻ tấn công biết thuật toán và quan sát được output trước đó. Đây là loại được dùng ở phía sau /dev/urandom trên Linux, hoặc trong các kết nối TLS.
Nếu bạn dùng Math.random() trong JavaScript để sinh token reset mật khẩu, session ID, hay OTP thì đó là một lỗi bảo mật thật sự vì Math.random() được tối ưu cho tốc độ, không được thiết kế để chống đoán trước, và trạng thái nội bộ của nó có thể bị suy ngược nếu ai đó thu thập đủ output.
Điều cần làm thay vào đó:
- Node.js:
crypto.randomBytes()hoặccrypto.randomUUID() - Browser:
window.crypto.getRandomValues() - PHP:
random_bytes()(không phảirand()haymt_rand()) - .NET:
RandomNumberGenerator.Fill()(namespaceSystem.Security.Cryptography), không dùngSystem.Random
Quy tắc đơn giản dễ nhớ: bất cứ khi nào giá trị ngẫu nhiên đó ảnh hưởng đến bảo mật như token, khóa, salt, session, nonce, … luôn dùng CSPRNG. Còn lại PRNG thường là đủ và nhanh hơn nhiều.
API giúp tạo seed nhanh cho PRNG
League of Entropy là một liên minh các tổ chức độc lập cùng vận hành mạng lưới drand để tạo ra một nguồn ngẫu nhiên công khai, phân tán, không ai có thể thao túng một mình.
Ý tưởng cốt lõi: thay vì một bên duy nhất tạo số ngẫu nhiên (dễ bị nghi ngờ hoặc bị tấn công), nhiều tổ chức độc lập cùng đóng góp entropy để tạo ra một giá trị ngẫu nhiên không thiên vị mà ai cũng có thể kiểm chứng vì kẻ tấn công muốn thao túng kết quả sẽ phải chiếm quyền kiểm soát nhiều bên cùng lúc, thay vì chỉ một bên như các beacon ngẫu nhiên truyền thống.
Thành viên sáng lập gồm Cloudflare, École polytechnique fédérale de Lausanne (EPFL), Kudelski Security, Protocol Labs, và Đại học Chile, và liên minh này vẫn tiếp tục mở rộng thêm thành viên mới.
Cách hoạt động: mỗi node tham gia giữ một phần khóa bí mật (threshold key). Ở mỗi round, các node ký một phần chữ ký BLS trên cùng một thông điệp; khi đủ số node ngưỡng (threshold) ký, các phần đó được kết hợp lại thành một chữ ký tổng hợp duy nhất chính là nguồn gốc của giá trị randomness bạn nhận được qua API. Vì chữ ký BLS mang tính xác định (cùng khóa + cùng thông điệp luôn ra cùng chữ ký), không ai kể cả chính các node có thể tạo ra hai kết quả khác nhau cho cùng một round, nên chuỗi randomness không thể bị “fork” hay giả mạo về sau.
Để tạo seed cho PRNG bạn có thể sử dụng API sau:
Trong đó randomness là SHA256 của chữ ký BLS threshold cho round đó có 32 byte hex, công khai, sinh mới mỗi ~30 giây (chain mặc định) hoặc 3 giây (fastnet). Thường thì chúng ta có thể lấy 4 bytes đầu của randomness là đủ dùng.
Điều quan trọng cần hiểu trước khi dùng: giá trị này là public randomness nên bất kỳ ai cũng lấy được y hệt giá trị đó cùng lúc với bạn. Vì vậy nó phù hợp để làm:
- Seed cho một PRNG khi bạn cần tái lập được và không thiên vị, không cần giữ bí mật.
- Nguồn ngẫu nhiên có thể kiểm chứng công khai (lottery, bốc thăm, chọn seed cho thuật toán mà mọi bên cần đồng thuận, phân bổ tài nguyên công bằng…).
Cảm ơn bạn đọc đã theo dõi bài viết nhé! 🙌
Nguồn tham khảo:
- https://en.wikipedia.org/wiki/Pseudorandom_number_generator
- https://www.cloudflare.com/leagueofentropy/
