Author markhermy3100 2021-07-21

Stream Cipher Và Pseudo Random Number Generator

Mặc dù One Time Pad là thiếu thiết thực để sử dụng, nó vẫn cho các nhà mật mã học hiện nay một nền móng màu mỡ để xây dựng các cryptosystem được dùng rộng rãi hiện nay. Đặc biệt hơn, một lớp những hệ thống này, Stream Cipher, sử dụng phép XOR y như OTP.

Vậy có những khác biệt gì? Hãy cùng tìm hiểu nào!

Stream Cipher

Stream Cipher (Mã theo dòng) là một loại mã đối xứng (symmetric key cipher). Phương thức encryption là thực hiện phép XOR với plaintext và một stream giả ngẫu nhiên (pseudorandom keystring). Keystream này được sinh ra từ một key ngắn, qua một hàm sinh số giả ngẫu nhiên (pseudorandom number generator). Tất nhiên, những cipher khác nhau sẽ dùng những hàm sinh số khác nhau.

Phép XOR thì đơn giản rồi. Thế còn hàm sinh keystream? Đó là cốt lõi của stream cipher.

Pseudorandom Number Generator (PRNG)

Chắc các bạn đã từng nghe đến RNG (Random Number Generator) rồi nhỉ? Nó đơn giản là một hàm sinh số ngẫu nhiên, được sử dụng cho nhiều mục đích khác nhau, từ mô phỏng, thống kê, cho đến gaming và gambling.

The Random Number Generator Demystified! - title

_{RNG được sử dụng nhiều trong các trò chơi may rủi, như xổ số hay bingo.}

Tuy nhiên, một hàm sinh số HOÀN TOÀN ngẫu nhiên (TRNG) có khá nhiều nhược điểm về mặt lý thuyết. Chúng:

Kém hiệu quả
Có thời gian chạy lâu

Chính vì vậy, PRNG ra đời.

Trước tiên, PRNG phải nhận input, gọi là seed để sinh ra số ngẫu nhiên. Sau đó PRNG sử dụng một hàm số cố định để sinh ra output từ seed đó. Có nghĩa là, output của PRNG hoàn toàn PHỤ THUỘC vào một seed nhất định.

Nếu các bạn đã từng dùng các RNG của các ngôn ngữ lập trình như C++ hay Java, bạn cần phải nhập seed vào để RNG hoạt động được, và nếu bạn không thay đổi seed thì bạn sẽ luôn nhận được 1 kết quả. Đó chính là PRNG!

Vì PRNG sử dụng những hàm số đã được lập trình sẵn, và việc còn lại chỉ là thực hiện các phép tính, PRNG:

Hiệu quả, ít tốn bộ nhớ
Tiết kiệm thời gian chạy

Tuy nhiên, cũng vì tính có sẵn của PRNG mà nó có một điểm yếu khá lớn: Tính tuần hoàn, tức là khi ta sử dụng 1 seed để sinh 1 output, lấy output đó làm seed để sinh ra 1 output mới, lại lấy output mới đó làm seed sinh ra output mới hơn nữa ... đến một lúc nào đó thì ta sẽ thu được một trong những seed trước, từ đó dẫn đến một vòng lặp. Đây là một điểm bất lợi nếu ta sinh ra rất rất nhiều số.

_{So sánh output giữa random.org (bên trái, một TRNG) và hàm rand() của PHP (bên phải, một PRNG)}

"Vậy thì tại sao chúng ta không chuyển sang sử dụng TRNG (True Random Number Generator) hết?" Chúng ta cần những điều kiện hết sức đặc biệt, những điều kiện thu được từ môi trường để có thể sinh ra những con số HOÀN TOÀN ngẫu nhiên. Hiểu đơn giản thì nó giống như việc bạn nối một chiếc máy tính với một cái xúc xắc vậy, chỉ những vật như xúc xắc mới có thể sinh ra những số hoàn toàn ngẫu nhiên.

Những máy tính có TRNG sử dụng phần cứng để đo đạc môi trường xung quanh, một nguồn đảm bảo tính ngẫu nhiên tuyệt đối, từ đó sinh ra những số ngẫu nhiên tuyệt đối, vì thế mà TRNG cũng được gọi là HRNG (Hardware Random Number Generator). Những phần cứng này đo âm thanh khí quyển (random.org), mức phóng xạ (HotBits Service), v.v. Điều này giải thích cho độ chậm chạp và thiếu hiệu quả của TRNG, nhưng đảm bảo độ ngẫu nhiên tuyệt đối.

Vì thế, tùy vào mục đích và nhu cầu sử dụng, những mảng khác nhau dùng những loại RNG khác nhau:

Xổ số, game, cờ bạc: TRNG
Thống kê ngẫu nhiên: TRNG
Minh họa, mô phỏng: PRNG

Thực chất, những PRNG cũng phân chia cấp bậc về "tính ngẫu nhiên". Có PRNG "ngẫu nhiên" hơn PRNG khác, vì thế chúng phù hợp hơn để sử dụng trong cryptography.

Một vài thuật toán PRNG

Một trong những thuật toán PRNG đơn giản nhất và thông dụng nhất là thuật toán bình phương giữa.

Ta sẽ lấy seed là 1 số có 3 chữ số và output là 1 số có 3 chữ số.

Cho seed = 121. Bình phương seed: 121 * 121 = 14641. Lấy 3 chứ số giữa: 464.
Đây là output của chúng ta.

Nếu bạn không ưng ý với output, bạn có thể làm lại lần nữa. 464 * 464 = 215296
= 0215296. 3 chữ số giữa là 152.

Thực ra, bạn có thể làm lại bao nhiêu lần tùy thích, nhưng sau 6 lần nữa, bạn sẽ thu
lại output 464, seed thứ hai của chúng ta, theo tính tuần hoàn.

Đối với seed bắt đầu nào cũng như vậy, vì số lượng số có 3 chữ số là có hạn, nên
có thể bạn sẽ đi qua hết 900 số, và rồi đi qua một số x lần thứ hai.

Trên thực tế, ta có thể sử dụng seed với nhiều chữ số hơn để vòng lặp dài hơn và khó
gặp hơn, nhưng vòng lặp vẫn là không thể tránh khỏi.

Có những thuật toán PRNG phức tạp hơn, sử dụng đủ mọi phép tính toán trên trời dưới đất, như cộng trừ nhân chia lũy, thậm chí có bước đảo bit.

Một trong những thuật toán PRNG thông dụng trong cryptography là LFSR (Linear
Feedback Shift Registers).
Seed và output của chúng ta sẽ là những chuỗi nhị phân có độ dài 8.

Cho seed = 01101001

Ta sẽ chọn 3 vị trí trong seed trên: Vị trí thứ 2, 5, và 7.

Ta XOR những bit của seed ở những vị trí trên:
seed[2] xor seed[5] xor seed[7] = 1 xor 1 xor 0 = 0

Tiếp theo ta sẽ để bit này lên đầu seed: 001101001
Cuối cùng ta bỏ bit cuối của seed: 00110100. Đây là output của chúng ta.

Ta lại có thể tiếp tục thực hiện thuật toán nếu ta không ưng ý với output.

Có tất cả 2^8 = 256 chuỗi nhị phân độ dài 8, vậy số lần thực hiện LFSR nhiều nhất
có thể là 256, trước khi ta đụng phải 1 seed cũ.

Nhưng trong nhiều trường hợp, độ phức tạp không quan trọng, người ta chỉ quan tâm PRNG có sinh ra số trông "ngẫu nhiên" không. Nếu output "giống" một số hoàn toàn ngẫu nhiên thì ta có thể sử dụng nó làm key cho OTP mà vẫn đảm bảo tính bảo mật. Đây chính là cách thức vận hành của những stream cipher.

Từ đây xuất hiện định nghĩa những PRNG an toàn về mặt mật mã, hay đơn thuần là những PRNG an toàn. Trong cryptography, khi chúng ta cần đẩy mức độ an ninh lên mức chắc chắn, TRNG được đưa vào sử dụng. Nhưng trong nhiều trường hợp thì PRNG an toàn được dùng vì tính hiệu quả. PRNG an toàn là cốt lõi của stream cipher.

Cryptographically-secure PRNG (PRNG an toàn)

Vậy 1 PRNG như thế nào được gọi là "an toàn"?

PRNG phải khó đoán. Cụ thể hơn, khi được cho k bit đầu tiên của output, kẻ tấn công không thể đoán chính xác bit tiếp theo với xác suất 50% + ε (thường thì khi ε > 1/2¹²⁸ thì đã coi là thiếu an toàn rồi)
Trong trường hợp một phần hoặc toàn bộ output bị lộ hoặc bị đoán đúng, kẻ tấn công cũng không thể đoán được output của PRNG trước output bị lộ.

Ví dụ: Cho 1 PRNG f(n) với seed là n sẽ xuất ra n chữ số thập phân liên tiếp bất kì của π. Do π, trên thực tế, là một số có pattern ngẫu nhiên, PRNG này thỏa mãn điều kiện đầu tiên. Tuy nhiên, khi output bị lộ, kẻ tấn công có thể dò xem output nằm ở vị trí nào trong số π, qua đó đoán được những output trước: những chữ số thập phân trước đó của π. Vậy đây không phải là 1 PRNG an toàn.

Một phần rất nhỏ các PRNG là an toàn, phần lớn là bởi vì đối với gần như bất kì PRNG nào, ta cũng có thể tạo ra 1 thuật toán "đặc thù" để phá tính an toàn của PRNG đó.

Những PRNG được sử dụng trong stream cipher vì thế cần phải được "đặc chế" để kể cả khi kẻ tấn công biết được cơ chế hoạt động của PRNG, PRNG vẫn phải thỏa mãn 2 điều kiện an toàn trên.