# RC4 và FMS attack

# 1. Thuật thoán RC4
- RC4 là một thuật toán mã hóa dòng chuyển nhanh (stream cipher) được phát triển bởi Ronald Rivest vào năm 1987. Tên đầy đủ của RC4 là "Rivest Cipher 4" và nó đã được sử dụng rộng rãi trong các ứng dụng bảo mật thông tin
- RC4 hoạt động bằng cách tạo ra một dãy số ngẫu nhiên được sử dụng làm khóa mã hóa. Khóa được tạo ra bằng cách sử dụng một khóa bí mật và một thuật toán pha trộn. Dãy số ngẫu nhiên này sau đó được sử dụng để mã hóa dữ liệu thông qua phép XOR (phép loại trừ) với dữ liệu gốc
- Dưới đây là mô tả cơ bản về cách RC4 hoạt động:

- Khởi tạo và tạo khóa: RC4 bắt đầu bằng cách khởi tạo một mảng 256 byte gọi là permutation array (S-box) và một khóa bí mật có độ dài từ 1 đến 256 byte. Mảng permutation array được đánh số từ 0 đến 255 và được lấp đầy với các giá trị từ 0 đến 255 theo thứ tự.

- Khởi tạo trạng thái ban đầu: Dựa trên khóa bí mật, permutation array sẽ được xáo trộn bằng cách hoán đổi các giá trị trong mảng theo một số vòng lặp. Quá trình xáo trộn này tạo ra một trạng thái ban đầu của permutation array.

- Tạo keystream: Khi cần mã hóa dữ liệu, RC4 sử dụng permutation array để tạo ra keystream. Keystream là một dãy byte ngẫu nhiên có cùng độ dài với dữ liệu cần mã hóa. Nó được tạo ra bằng cách lặp lại quá trình xáo trộn permutation array và lấy ra các giá trị từ mảng xáo trộn để tạo thành keystream.

- Mã hóa dữ liệu: Keystream được tạo ra từ bước trước được sử dụng để mã hóa dữ liệu ban đầu. Mã hóa được thực hiện bằng phép XOR (phép loại trừ) giữa byte của dữ liệu ban đầu và byte của keystream tương ứng.

- Giải mã dữ liệu: Quá trình giải mã dữ liệu tương tự như quá trình mã hóa, với việc sử dụng keystream được tạo ra từ permutation array để thực hiện phép XOR với dữ liệu đã được mã hóa.

def KSA(key):
    key_length = len(key)
    S = list(range(256))
    j = 0
    for i in range(256):
        j = (j + S[i] + key[i % key_length]) % 256
        S[i], S[j] = S[j], S[i]
    return S

def PRGA(S, n):
    i = 0
    j = 0
    key = []
    while n > 0:
        i = (i + 1) % 256
        j = (j + S[i]) % 256
        S[i], S[j] = S[j], S[i]
        key.append(S[(S[i] + S[j]) % 256])
        n -= 1
    return key

def RC4(key, plaintext):
    S = KSA(key)
    keystream = PRGA(S, len(plaintext))
    ciphertext = [chr(ord(plaintext[i]) ^ keystream[i]) for i in range(len(plaintext))]
    return ''.join(ciphertext)

# 2. FMS attack
- Cuộc tấn công FMS (Fluhrer, Mantin, and Shamir) trên RC4 là một loại tấn công cụ thể nhằm vào thuật toán mã hóa RC4. Cuộc tấn công này tận dụng các sai lệch thống kê trong dãy số ngẫu nhiên được tạo bởi RC4 để khôi phục lại khóa bí mật được sử dụng cho việc mã hóa.

- Trong RC4, dãy số ngẫu nhiên được tạo ra bằng cách kết hợp một khóa bí mật với một hoán vị ngẫu nhiên các byte được gọi là mảng hoán vị (permutation array). Cuộc tấn công FMS khai thác một điểm yếu trong thuật toán lập lịch khóa của RC4, dẫn đến các sai lệch trong các byte đầu của dãy số ngẫu nhiên.

- Cuộc tấn công hoạt động bằng cách thu thập một tập hợp các thông điệp đã được mã hóa sử dụng cùng một khóa bí mật nhưng khác nhau về nội dung. Bằng cách phân tích các tính chất thống kê của các byte trong dãy số ngẫu nhiên tương ứng với nội dung đã biết, kẻ tấn công có thể suy ra thông tin về khóa bí mật. Với đủ thông điệp đã thu thập và phân tích thống kê, kẻ tấn công cuối cùng có thể khôi phục lại toàn bộ khóa bí mật.

- Cuộc tấn công FMS trên RC4 được giới thiệu lần đầu bởi Fluhrer, Mantin và Shamir vào năm 2001. Nó làm nổi bật những lỗ hổng đáng kể trong RC4, đặc biệt là trong ngữ cảnh của các mạng không dây sử dụng giao thức WEP (Wired Equivalent Privacy). Cuộc tấn công này đã chứng minh rằng RC4 không phù hợp cho các truyền thông an toàn và dẫn đến việc không khuyến nghị sử dụng RC4 trong các tiêu chuẩn và giao thức bảo mật.
- Có rất nhiều biểu diễn của RC4 chọn `key = IV + secret`, ta sẽ chọn một trong những weak IV là `(A + 3, 255, v)` với `A` là byte của `secret` mà chúng ta muốn khai thác.
- Ở đây chúng ta sẽ chọn secret = `very_secret_key`

secret_decr = []
sl = len(secret) # assume you know the secret length 
for A in range(sl):
    probs = [0] * 256 # init a frequency array 
    for v in range(256): # for each custom byte
        plaintext = b'A' * (A + 3) # doesn't matter the plaintext
        nonce = bytes([A+3, 255, v]) # weak nonce (L, n-1, v)
        
        ciphertext = ARC4.new(nonce + secret).encrypt(plaintext) # this line is send to the oracle and we receive the ciphertext
        
        keystream = xor(plaintext, ciphertext) # compute the keystream

        # simulate first known rounds to get j
        key = nonce + bytes(secret_decr)
        Sbox = [i for i in range(256)]  # init sbox
        j = 0
        for i in range(A + 3): # A + 3 because we know the first 3 bytes from nonce
            j = (j + Sbox[i] + key[i % len(key)]) % 256
            Sbox[i], Sbox[j] = Sbox[j], Sbox[i]
            if i == 1:
                o0, o1 = Sbox[0], Sbox[1] # keep original 2 values to filter for swaps

        # Resolved condition
        i = A + 3
        if Sbox[1] < i and Sbox[1] + Sbox[Sbox[1]] == A + 3:
            if (o0 != Sbox[0] or o1 != Sbox[1]): # check for swaps
                continue
            key_byte = (keystream[0] - j - Sbox[i]) % 256 # first byte of the keystream is K3 = first byte of the key. Follow the equation
            probs[key_byte] += 1
    secret_decr.append(probs.index(max(probs))) # argmax from the array of probs
    print(bytes(secret_decr))

# 3. Reference
- https://en.wikipedia.org/wiki/RC4
- https://en.wikipedia.org/wiki/Fluhrer,_Mantin_and_Shamir_attack
- youtube.com/watch?v=2o3Hs-JDWLs