krone
VIP Members
-
26/07/2016
-
141
-
259 bài viết
Secure Random Number Generators - PRNG
Trong mật mã, tính ngẫu nhiên (entropy) đóng vai trò rất quan trọng. Trong nhiều thuật toán, chúng ta cần các số ngẫu nhiên (nghĩa là không thể đoán trước). Nếu những con số này có thể đoán trước được, các thuật toán sẽ bị xâm phạm.
Ví dụ: giả sử chúng ta cần một khóa bí mật, điều đó sẽ bảo vệ tài sản tài chính của chúng ta. Khóa bí mật này phải được tạo ngẫu nhiên theo cách mà không ai khác có thể tạo hoặc có cùng khóa. Nếu chúng ta tạo khóa từ một secure random generator, nó sẽ không thể đoán trước và hệ thống sẽ được bảo mật. Do đó "secure random" có nghĩa đơn giản là "ngẫu nhiên không thể đoán trước".
Chúng ta hãy thảo luận chi tiết hơn về các con số ngẫu nhiên trong khoa học máy tính và vai trò của chúng trong mật mã học, cũng như các trình tạo số giả ngẫu nhiên (PRNG), các trình tạo giả ngẫu nhiên an toàn (CSPRNG) và một số hướng dẫn về cách các nhà phát triển nên tạo và sử dụng các số ngẫu nhiên trong mã của họ.
Random Generators
Trong khoa học máy tính, số ngẫu nhiên thường đến từ bộ tạo số giả ngẫu nhiên (PRNG), khởi tạo bởi một số ngẫu nhiên ban đầu không thể đoán trước (entropy). Trong mật mã, các PRNG an toàn được sử dụng, được gọi là CSPRNG, thường kết hợp entropy với PRNG và các kỹ thuật khác để làm cho tính ngẫu nhiên được tạo ra không thể đoán trước.
Pseudo-Random Number Generators (PRNG)
Trình tạo số giả ngẫu nhiên (PRNG) được sử dụng để tăng kích thước một lượng nhỏ ngẫu nhiên ban đầu thành một số lượng lớn ngẫu nhiên, thường được sử dụng trong các hệ thống mật mã. Lưu ý hơn PRNG không bảo mật bằng mật mã và khác với CSPRNG.
PRNG là các hàm bắt đầu từ một số entropy ban đầu (seed) và tính số ngẫu nhiên tiếp theo bằng một số tính toán không thể đoán trước mà không biết seed. Các tính toán như vậy được gọi là pseudo-random functions.
Các Pseudo-random functions (không an toàn cho mật mã) thường sử dụng state nội bộ. Khi bắt đầu, trạng thái được khởi tạo bởi một seed ban đầu. Khi số ngẫu nhiên tiếp theo được tạo, nó được tính từ state nội bộ (sử dụng một số tính toán hoặc công thức), sau đó state nội bộ của pseudo-random function được thay đổi (sử dụng một số tính toán hoặc công thức). Khi số ngẫu nhiên tiếp theo được tạo, nó lại được tính dựa trên state nội bộ của funtion và state này lại được thay đổi, v.v.
Initial Entropy (Seed)
Để an toàn, một PRNG (là ngẫu nhiên thống kê) nên bắt đầu bằng một seed ban đầu thực sự ngẫu nhiên, điều này hoàn toàn không thể đoán trước. Nếu seed có thể dự đoán được, nó sẽ tạo ra chuỗi số ngẫu nhiên có thể dự đoán được và toàn bộ quá trình tạo ngẫu nhiên sẽ không an toàn. Đó là lý do tại sao có sự ngẫu nhiên không thể đoán trước khi bắt đầu (secure seed) là rất quan trọng.
Làm thế nào để khởi tạo pseudo-random generator một cách an toàn? Câu trả lời rất đơn giản: thu thập ngẫu nhiên (entropy).
Entropy
Trong khoa học máy tính, "entropy" có nghĩa là tính ngẫu nhiên không thể đoán trước và thường được đo bằng bit. Ví dụ: nếu bạn di chuyển chuột máy tính của bạn, nó sẽ tạo ra một số sự kiện khó dự đoán, như vị trí bắt đầu và vị trí kết thúc của con trỏ chuột. Nếu chúng tôi cho rằng chuột đã thay đổi vị trí của nó trong phạm vi [0 ... 255] pixel, entropy được thu thập từ chuyển động chuột này sẽ vào khoảng 8 bit (vì 2 ^ 8 = 255). Một ví dụ khác: nếu người dùng được yêu cầu nghĩ về một số trong phạm vi [0 ... 1000], con số này sẽ chứa khoảng 9-10 bit entropy (vì 2 ^ 10 = 1024). Để thu thập 256 bit entropy (ví dụ: để tạo một số nguyên 256 bit một cách an toàn), bạn sẽ cần tính đến một chuỗi các sự kiện như vậy (như chuyển động chuột và sự can thiệp của bàn phím từ người dùng).
Collecting Entropy
Entropy có thể được thu thập từ nhiều sự kiện khó dự đoán trong máy tính: nhấp chuột trên bàn phím, di chuyển chuột, hoạt động mạng, hoạt động của camera, hoạt động của micrô và các hoạt động khác, kết hợp với thời gian chúng xảy ra. Bộ sưu tập ngẫu nhiên ban đầu này thường được thực hiện bởi hệ điều hành (HĐH), cung cấp API tiêu chuẩn để truy cập nó (ví dụ: đọc từ file /dev/random trong Linux). Trong hệ thống máy tính để bàn, entropy máy tính xách tay hoặc điện thoại di động rất dễ thu thập, trong khi trên một số thiết bị phần cứng hạn chế (như vi điều khiển đơn giản), entropy khó hoặc không thể thu thập được.
Phần mềm ứng dụng có thể thu thập entropy một cách rõ ràng, bằng cách yêu cầu người dùng di chuyển chuột, gõ một cái gì đó vào bàn phím, nói điều gì đó ở micrô hoặc di chuyển trước máy ảnh một lúc. Một ví dụ tuyệt vời về điều này là ứng dụng ví bitaddress.org, kết hợp di chuyển chuột với các sự kiện bàn phím để thu thập entropy:
Khi thu thập đủ entropy, nó được sử dụng để khởi tạo trình tạo ngẫu nhiên.
Insecure Randomness
Random không an toàn hoặc bị xâm phạm có thể làm tổn hại đến mật mã. Một ví dụ điển hình để học hỏi là câu chuyện về Bitcoin bị đánh cắp, do trình tạo ngẫu nhiên bị hỏng trong Android: https://goo.gl/PFE1kr . Đó là lý do tại sao các nhà phát triển nên quan tâm đến tính ngẫu nhiên, khi họ sử dụng mật mã và đảm bảo các trình tạo ngẫu nhiên của họ được an toàn.
Insecure Randomness - Examples
Ví dụ, việc thỏa hiệp bảo mật số ngẫu nhiên trong Python dễ dàng như thế nào (trong các phiên bản cũ của nó), chúng tôi sẽ đưa ra ví dụ mã này:
Đoạn mã trên được cho là tạo ra một số ngẫu nhiên, nhưng con số này có thể dự đoán được. Điều này là do thư viện random trong Python (trong các phiên bản cũ) khởi tạo hạt giống trình tạo ngẫu nhiên theo thời gian hiện tại. Do đó, nếu bạn biết thời gian hiện tại tại máy tạo ra số ngẫu nhiên (rõ ràng bạn biết điều này một cách hơi mù mờ một chút), bạn sẽ có thể dự đoán seed ngẫu nhiên và dự đoán các số ngẫu nhiên được tạo.
Để minh họa rõ hơn điều này, hãy xem ví dụ rõ ràng hơn này tạo ra hai số nguyên 50 chữ số ngẫu nhiên:
Đoạn mã trên sẽ in hai số bằng nhau, cả hai tùy thuộc vào thời gian hiện tại. Rõ ràng là cùng một lúc trong seed ban đầu gây ra các số pseudo-random (có thể dự đoán) giống nhau được tạo ra trong đầu ra.
Bài viết giới thiệu cơ bản về số ngẫu nhiên và mức độ quan trọng của nó trong thực tế. Cám ơn mọi người đã theo dõi.
Ví dụ: giả sử chúng ta cần một khóa bí mật, điều đó sẽ bảo vệ tài sản tài chính của chúng ta. Khóa bí mật này phải được tạo ngẫu nhiên theo cách mà không ai khác có thể tạo hoặc có cùng khóa. Nếu chúng ta tạo khóa từ một secure random generator, nó sẽ không thể đoán trước và hệ thống sẽ được bảo mật. Do đó "secure random" có nghĩa đơn giản là "ngẫu nhiên không thể đoán trước".
Chúng ta hãy thảo luận chi tiết hơn về các con số ngẫu nhiên trong khoa học máy tính và vai trò của chúng trong mật mã học, cũng như các trình tạo số giả ngẫu nhiên (PRNG), các trình tạo giả ngẫu nhiên an toàn (CSPRNG) và một số hướng dẫn về cách các nhà phát triển nên tạo và sử dụng các số ngẫu nhiên trong mã của họ.
Random Generators
Trong khoa học máy tính, số ngẫu nhiên thường đến từ bộ tạo số giả ngẫu nhiên (PRNG), khởi tạo bởi một số ngẫu nhiên ban đầu không thể đoán trước (entropy). Trong mật mã, các PRNG an toàn được sử dụng, được gọi là CSPRNG, thường kết hợp entropy với PRNG và các kỹ thuật khác để làm cho tính ngẫu nhiên được tạo ra không thể đoán trước.
Pseudo-Random Number Generators (PRNG)
Trình tạo số giả ngẫu nhiên (PRNG) được sử dụng để tăng kích thước một lượng nhỏ ngẫu nhiên ban đầu thành một số lượng lớn ngẫu nhiên, thường được sử dụng trong các hệ thống mật mã. Lưu ý hơn PRNG không bảo mật bằng mật mã và khác với CSPRNG.
PRNG là các hàm bắt đầu từ một số entropy ban đầu (seed) và tính số ngẫu nhiên tiếp theo bằng một số tính toán không thể đoán trước mà không biết seed. Các tính toán như vậy được gọi là pseudo-random functions.
Các Pseudo-random functions (không an toàn cho mật mã) thường sử dụng state nội bộ. Khi bắt đầu, trạng thái được khởi tạo bởi một seed ban đầu. Khi số ngẫu nhiên tiếp theo được tạo, nó được tính từ state nội bộ (sử dụng một số tính toán hoặc công thức), sau đó state nội bộ của pseudo-random function được thay đổi (sử dụng một số tính toán hoặc công thức). Khi số ngẫu nhiên tiếp theo được tạo, nó lại được tính dựa trên state nội bộ của funtion và state này lại được thay đổi, v.v.
Initial Entropy (Seed)
Để an toàn, một PRNG (là ngẫu nhiên thống kê) nên bắt đầu bằng một seed ban đầu thực sự ngẫu nhiên, điều này hoàn toàn không thể đoán trước. Nếu seed có thể dự đoán được, nó sẽ tạo ra chuỗi số ngẫu nhiên có thể dự đoán được và toàn bộ quá trình tạo ngẫu nhiên sẽ không an toàn. Đó là lý do tại sao có sự ngẫu nhiên không thể đoán trước khi bắt đầu (secure seed) là rất quan trọng.
Làm thế nào để khởi tạo pseudo-random generator một cách an toàn? Câu trả lời rất đơn giản: thu thập ngẫu nhiên (entropy).
Entropy
Trong khoa học máy tính, "entropy" có nghĩa là tính ngẫu nhiên không thể đoán trước và thường được đo bằng bit. Ví dụ: nếu bạn di chuyển chuột máy tính của bạn, nó sẽ tạo ra một số sự kiện khó dự đoán, như vị trí bắt đầu và vị trí kết thúc của con trỏ chuột. Nếu chúng tôi cho rằng chuột đã thay đổi vị trí của nó trong phạm vi [0 ... 255] pixel, entropy được thu thập từ chuyển động chuột này sẽ vào khoảng 8 bit (vì 2 ^ 8 = 255). Một ví dụ khác: nếu người dùng được yêu cầu nghĩ về một số trong phạm vi [0 ... 1000], con số này sẽ chứa khoảng 9-10 bit entropy (vì 2 ^ 10 = 1024). Để thu thập 256 bit entropy (ví dụ: để tạo một số nguyên 256 bit một cách an toàn), bạn sẽ cần tính đến một chuỗi các sự kiện như vậy (như chuyển động chuột và sự can thiệp của bàn phím từ người dùng).
Collecting Entropy
Entropy có thể được thu thập từ nhiều sự kiện khó dự đoán trong máy tính: nhấp chuột trên bàn phím, di chuyển chuột, hoạt động mạng, hoạt động của camera, hoạt động của micrô và các hoạt động khác, kết hợp với thời gian chúng xảy ra. Bộ sưu tập ngẫu nhiên ban đầu này thường được thực hiện bởi hệ điều hành (HĐH), cung cấp API tiêu chuẩn để truy cập nó (ví dụ: đọc từ file /dev/random trong Linux). Trong hệ thống máy tính để bàn, entropy máy tính xách tay hoặc điện thoại di động rất dễ thu thập, trong khi trên một số thiết bị phần cứng hạn chế (như vi điều khiển đơn giản), entropy khó hoặc không thể thu thập được.
Phần mềm ứng dụng có thể thu thập entropy một cách rõ ràng, bằng cách yêu cầu người dùng di chuyển chuột, gõ một cái gì đó vào bàn phím, nói điều gì đó ở micrô hoặc di chuyển trước máy ảnh một lúc. Một ví dụ tuyệt vời về điều này là ứng dụng ví bitaddress.org, kết hợp di chuyển chuột với các sự kiện bàn phím để thu thập entropy:
Khi thu thập đủ entropy, nó được sử dụng để khởi tạo trình tạo ngẫu nhiên.
Insecure Randomness
Random không an toàn hoặc bị xâm phạm có thể làm tổn hại đến mật mã. Một ví dụ điển hình để học hỏi là câu chuyện về Bitcoin bị đánh cắp, do trình tạo ngẫu nhiên bị hỏng trong Android: https://goo.gl/PFE1kr . Đó là lý do tại sao các nhà phát triển nên quan tâm đến tính ngẫu nhiên, khi họ sử dụng mật mã và đảm bảo các trình tạo ngẫu nhiên của họ được an toàn.
Insecure Randomness - Examples
Ví dụ, việc thỏa hiệp bảo mật số ngẫu nhiên trong Python dễ dàng như thế nào (trong các phiên bản cũ của nó), chúng tôi sẽ đưa ra ví dụ mã này:
Đoạn mã trên được cho là tạo ra một số ngẫu nhiên, nhưng con số này có thể dự đoán được. Điều này là do thư viện random trong Python (trong các phiên bản cũ) khởi tạo hạt giống trình tạo ngẫu nhiên theo thời gian hiện tại. Do đó, nếu bạn biết thời gian hiện tại tại máy tạo ra số ngẫu nhiên (rõ ràng bạn biết điều này một cách hơi mù mờ một chút), bạn sẽ có thể dự đoán seed ngẫu nhiên và dự đoán các số ngẫu nhiên được tạo.
Để minh họa rõ hơn điều này, hãy xem ví dụ rõ ràng hơn này tạo ra hai số nguyên 50 chữ số ngẫu nhiên:
Đoạn mã trên sẽ in hai số bằng nhau, cả hai tùy thuộc vào thời gian hiện tại. Rõ ràng là cùng một lúc trong seed ban đầu gây ra các số pseudo-random (có thể dự đoán) giống nhau được tạo ra trong đầu ra.