Máy tính có thực sự random một số không?

1. Tính ngẫu nhiên (randomness)

Thế kỷ 3 Trước Công Nguyên, ở Athen, người ta đã sử dụng Kleroterion - một thiết bị dùng để chọn ngẫu nhiên các công dân vào bồi thẩm đoàn, văn phòng và hội đồng nhà nước. Đó là nền tảng của cái mà ngày nay chúng ta gọi là dân chủ. Hàng thiên niên kỷ sau, tính ngẫu nhiên không còn được sử dụng trong quá trình bầu cử. Tuy nhiên, nó cũng đã tìm được chỗ đứng trong những lĩnh vực khác mà đặc biệt là ở bộ môn số học giúp mọi người đổi đời sau 6h30.

Hình 1: Kleroterion

Lập trình là để phục vụ cuộc sống, vậy nên trong lập trình, tính ngẫu nhiên cũng được sử dụng rất nhiều:

• Mô phỏng: Tính ngẫu nhiên được sử dụng để thực hiện mô phỏng Monte Carlo, một kỹ thuật toán học dự đoán kết quả có thể xảy ra của một sự kiện không chắc chắn.

• Mật mã và bảo mật: Trong bảo mật, random thường được sử dụng để tạo key, id, mã OTP hoặc tạo salt trong hàm băm (hash).

• Phát triển game: Trò chơi sử dụng tính ngẫu nhiên để tạo ra những trải nghiệm độc đáo, mới lạ cho mỗi người chơi và mỗi lần chơi, giúp tăng tỉ lệ chơi lại, chẳng hạn như cấp độ, vật phẩm và vị trí của kẻ thù được tạo ngẫu nhiên.

• Load Balancing: Random là một thuật toán được ứng dụng trong load balancing để giúp các load balancer phân phối ngẫu nhiên các yêu cầu đến server.

• Testing: A/B Test thường sử dụng random để chỉ định ngẫu nhiên người dùng vào những nhóm khác nhau.

2. Máy tính có thực sự random một số không?

Câu trả lời là: Không!

Đối với con người, việc tạo ra một giá trị ngẫu nhiên khá dễ dàng. Bạn có thể tung đồng xu, xúc xắc hay rút một lá bài hay chọn ngẫu nhiên một số trong đầu... Nhưng đối với máy tính thì khác, mọi hoạt động của máy tính đều dựa trên lập trình mà bản chất là logic.

Một chương trình máy tính dựa trên các câu lệnh if-then: Nếu đáp ứng một số điều kiện nhất định thì hãy thực hiện hành động được chỉ định này. Cùng một đầu vào vào một chương trình sẽ dẫn đến cùng một đầu ra ở mọi thời điểm. Vậy nên, về mặt thiết kế, máy tính không có khả năng tạo ra các số thực sự ngẫu nhiên.

Đó lý do tại sao xổ số vẫn sử dụng các trình tạo ngẫu nhiên cơ học như lồng quay chứa các quả bóng được đánh số. Tuy nhiên, máy tính cần các số ngẫu nhiên cho rất nhiều ứng dụng nên người ta đã phát triển những phương pháp cực kỳ phức tạp (gọi là trình giả ngẫu nhiên - Pseudorandom Number Generator, viết tắt là PRNG) để thu được cái gọi là số giả ngẫu nhiên (pseudo-random).

Lịch sử phát triển PRNG

Trình giả ngẫu nhiên đầu tiên được tạo ra bởi Von Neumann, gọi là middle square. Đây là một phương pháp đơn giản và khá dễ dự đoán. Sau này, người ta đã thay thế nó bằng phương pháp Mersenne Twister - khó dự đoán hơn nhiều (tuy nhiên vẫn có thể dự đoán được nếu quan sát đủ).

Vấn đề bảo mật

Với phần lớn các yêu cầu cần tính ngẫu nhiên trong lập trình, thì trình giả ngẫu nhiên đủ để đáp ứng nhu cầu. Tuy nhiên, trong lĩnh vực bảo mật thì lại khác, một trình tạo số thực sự ngẫu nhiên rất quan trọng. Do tất cả các trình giả ngẫu nhiên đều được bắt nguồn từ đâu đó trong hệ thống (seed), nên nó đều có thể dự đoán được.

Trường hợp Hacker News

Và đó cũng chính là lý do Hacker News bị hack. Khi chúng ta đăng nhập vào một trang web, thường sẽ được gán một ID duy nhất cho session đó (khoảng thời gian bạn đăng nhập). ID này phải là duy nhất và người khác không thể đoán được, nếu đoán được thì họ có thể mạo danh chúng ta.

Đối với Hacker News, ID duy nhất là một chuỗi ký tự ngẫu nhiên, chẳng hạn như lBGn0tWMcx7380gZyrUO9B. Chuỗi ký tự "ngẫu nhiên" này thực ra được tạo ra không quá phức tạp với seed là số mili giây tính từ khi Hacker News được khởi động lần cuối.

Một hacker (Dfranke) đã tấn công và làm cho Hacker News phải khởi động lại, từ đó dự đoán được thời điểm khởi động và tìm ra seed. Chi tiết về cuộc tấn công có ở đây.

Kết quả là Hacker News đã phải thay đổi cách tạo ID của mình bằng cách sử dụng /dev/urandom - một trình giả ngẫu nhiên của Linux (không phải một trình tạo số thực sự ngẫu nhiên nhưng đã đủ đảm bảo an toàn).

3. Làm thế nào để máy tính có thể thực sự random một số?

Để tạo ra một số thực sự ngẫu nhiên, bắt buộc phải lấy một nguồn ngẫu nhiên làm cơ sở. Các nguồn ngẫu nhiên thì rất đa dạng, từ những chiếc đèn lava (lava lamps) của Cloudflare, đến bức xạ phóng xạ của Caesium-137 của Hotbits, hay tiếng ồn vô tuyến trong khí quyển của Random.org...

Từ những nguồn ngẫu nhiên này, người ta sẽ thu thập entropy và sử dụng chúng để tạo số ngẫu nhiên.

Ví dụ: Hệ thống đèn lava của Cloudflare

Văn phòng của Cloudflare ở Los Angeles có một bức tường được bố trí khoảng 100 chiếc đèn lava và một camera hướng vào phía những chiếc đèn liên tục chụp ảnh và gửi về server của Cloudflare.

Ở server, những hình ảnh này sẽ được chuyển thành dữ liệu ở dạng chuỗi số, với mỗi pixel thay đổi trên bức ảnh sẽ cho ra một chuỗi số khác nhau. Từ những chuỗi số này, kết hợp cùng với các nguồn ngẫu nhiên khác như hành động của người dùng (di chuyển chuột, gõ trên bàn phím...) để tối đa hóa entropy khi tạo seed. Những seeds này sẽ được Cloudflare dùng để mã hóa SSL/TLS.

Hình 2: Đèn lava trong văn phòng Cloudflare ở San Francisco

Các nguồn ngẫu nhiên khác của Cloudflare

Ngoài đèn lava, Cloudflare còn sử dụng một số nguồn ngẫu nhiên khác như:

• Hệ thống con lắc đôi ở văn phòng London
• Độ phân rã phóng xạ của một viên uranium ở văn phòng Singapore (đương nhiên là rất nhỏ để đảm bảo an toàn)

Hình 3: Hệ thống con lắc đôi trong văn phòng Cloudflare ở London với điều kiện ánh sáng thay đổi

4. Kết luận

Như vậy, máy tính chỉ có thể tạo ra những số giả ngẫu nhiên (pseudo-random) nhờ những trình giả ngẫu nhiên (pseudorandom number generator).

Để có thể tạo ra những số thực sự ngẫu nhiên, máy tính cần dựa vào những nguồn ngẫu nhiên từ bên ngoài như đèn lava, tín hiệu vô tuyến, phóng xạ tự nhiên...