Stream Cipher Phần 2 - RC4

Stream Cipher Phần 2 - RC4

Đây là điểm đến tiếp theo trong chuyến hành trình qua giới cryptography hiện đại của chúng ta - RC4, cipher thuộc một trong những lớp đơn giản nhất.

Sơ lược

RC4 được thiết kế bởi Ron Rivest (ông Rivest này khá nổi trong giới crypto, hãy để mắt tới ông này trong những bài viết tiếp theo) vào năm 1987, vì thế nên cipher còn được biết tới là Rivest's Cipher 4, hay Ron's Code 4, để phân biệt với các phiên bản khác của RC như RC2, RC5 hay RC6.

Thời bấy giờ, những phương thức mã hóa như CSS (Content Scrambling System) dựa vào hardware rất nhiều, vì khi đưa vào vận hành trong software lại thiếu hiệu quả. RC4 giải quyết được vấn đề ấy, khi hiệu quả trong cả hardware lẫn software implementation, cũng như tối ưu về tốc độ lẫn độ đơn giản, vì thế RC4 được coi là thành công trong một khoảng thời gian dài, cho đến khi bị phá.

Kể từ khi thuật toán bị lộ công khai, RC4 được sử dụng phổ biến trong các phương thức và tiêu chuẩn mã hóa, như WEP (Wired Equivalent Privacy) - 1997,  TLS (Transport Security Layer) - 1999 và WPA (Wi-Fi Protected Access) - 2003/2004.

Như mọi stream cipher khác, RC4 thực hiện phép XOR plaintext với một keystream đã được chuẩn bị để thu được ciphertext tương ứng. Trọng tâm chúng ta tìm hiểu sẽ là quá trình hình thành keystream, cũng như những điểm yếu bên trong quá trình này.

Hình thành xâu key - Keystream generation

Cả quá trình này đơn thuần chỉ là một PRNG với seed là key bí mật của chúng ta, từ đó output sẽ là keystream để XOR với plaintext.

Thật ra, vì đây là PRNG, key bí mật là gì cũng được, nhưng càng dài, càng ngẫu nhiên càng tốt.

Khâu chuẩn bị key - KSA

Input của khâu này là key bí mật của chúng ta: [3, 1, 0, 0]
Output của khâu này là một hoán vị của dãy S = [0, 1, 2, 3, 4, 5, 6, 7]

Trong thực tế, dãy S là từ 0 đến 255 để tương thích với hệ ASCII, nhưng ở đây
ta chỉ lấy là 8 cho đơn giản.

Pseudo algorithm sinh ra output sẽ là như sau:
j = 0
for i from 0 to 7:
    j = (j + S[i] + key[i % key_length]) % 8 // Trong trường hợp này key_length = 4
    swap values of S[i] and S[j]
Đơn giản, đúng không?
Phân tích một chút, bạn sẽ thấy giá trị key[i % key_length] là để lặp lại key.
Rút kinh nghiệm từ Vigenere Cipher, ta thấy là key nên dài để tránh bị lặp lại
quá nhiều.
Bạn có thể kiểm chứng rằng output sau khi thực hiện khâu chuẩn bị trên là
[1, 5, 7, 2, 0, 3, 6, 4]

Đây sẽ là input cho khâu tiếp theo của chúng ta.

Thuật toán sinh giả ngẫu nhiên - PRG

Input của khâu này là hoán vị mà chúng ta thu được từ khâu chuẩn bị key:
[1, 5, 7, 2, 0, 3, 6, 4]
Output của khâu này là keystream chúng ta cần.

Pseudo algorithm ở đây hơi dài hơn 1 chút, nhưng vẫn dễ nhìn:
i := 0
j := 0
while output_length < plaintext_length:
    i := (i + 1) mod 8
    j := (j + S[i]) mod 8
    swap values of S[i] and S[j]
    K := S[(S[i] + S[j]) mod 8]
    output K
Thuật toán trên sẽ sinh ra output giả ngẫu nhiên dài tùy thích, tùy vào độ dài
plaintext. Ví dụ:

1) plaintext = [1, 2, 3], output sẽ chỉ sinh ra đến [1, 4, 1], từ đó cho
ciphertext = [1, 2, 3] xor [1, 4, 1] = [0, 6, 2]

2) plaintext = [5, 6, 7, 6, 5, 4, 3, 2, 1], output sẽ sinh ra đến
[1, 4, 1, 5, 7, 7, 7, 0, 5], từ đó cho ciphertext = [4, 2, 6, 3, 2, 3, 4, 2, 4]

Mặc dù sử dụng PRNG đơn giản, RC4 vẫn cung cấp mức độ bảo mật nhất định, cho đến khi điểm yếu đầu tiên được phát hiện vào năm 1995.

Những điểm yếu - Cryptanalysis

Đối với một cipher, để lộ một sơ hở dù rất nhỏ thôi cũng có thể bị phá tanh bành. RC4 lại chứa không ít những sơ hở như vậy.

Tính thiên vị của keystream output

Hóa ra byte thứ 2 của keystream sẽ bằng 00 với xác suất 1/128 (gấp đôi so với 1/256, do có 256 giá trị byte từ 00 đến ff). Thật ra, những byte đầu tiên của keystream đều không "ngẫu nhiên" và có thể được sử dụng để thu được key gốc. Cơ bản thì ta có thể bỏ vài byte đầu (thường là 3072 byte) của keystream để che lấp sơ hở này.

Tuy nhiên, khi phân tích khoảng vài GB output của RC4, tính thiên vị khác được phát hiện: Xác suất để 2 byte kề nhau là (00, 00) là 1/2562 + 1/2563, cao hơn nhiều so với xác suất thông thường 1/2562.

Hầu hết những tấn công lợi dụng sơ hở này của RC4 cũng như những tương quan giữa key và keystream.

Dẫu vậy, trước năm 2015, RC4 vẫn được sử dụng phổ biến trong SSL/TLS, vì thời bấy giờ, RC4 miễn nhiễm trước tấn công BEAST, một tấn công làm khốn đốn nhiều cryptosystem sử dụng trong SSL/TLS. Hơn nữa, cách thức sử dụng RC4 trong SSL/TLS làm giảm thiểu các thiên vị trên, dẫn đến những tấn công "đặc chế" nhằm phá RC4 trong SSL/TLS.

Một ví dụ nổi bật là tấn công NOMORE, có thể phá 1 HTTP cookie 16-byte trong khoảng 75 tiếng đồng hồ bằng cách gửi khoảng 2^30 yêu cầu. Video minh họa

Vì vậy, tiêu chuẩn RFC 7465 do IEFT vào năm 2015 đã cấm RC4 trong TLS. Nhiều biến thể của RC4 cũng được tạo ra hòng làm chặt chẽ thuật toán tạo keystream, như RC4+ hay Spritz, nhưng chúng đều theo vết xe đổ của RC4 khá chóng vánh.

Tạm kết Stream Cipher

Kết luận: RC4 dù đơn giản, nhưng lại quá đơn giản đến mức chưa đủ an toàn.

Trong thực tế, nếu bạn muốn sử dụng stream cipher thì Salsa20/ChaCha là ứng cử viên số một. Tuy nhiên, khi phân tích kĩ, Salsa20 có cơ chế hoạt động gần giống một loại block cipher - lớp hệ thống cryptography chúng ta sẽ nghiên cứu tiếp theo!

Hãy đón xem nhé!