# RC4 (Stream Cipher)

RC4 là một loại mã hóa dòng mã hóa văn bản gốc mỗi lần một byte. RC4 sẽ tạo ra `keystream` bằng 2 thuật toán KSA và PRGA từ key bí mật của ta.
Sau đó tính `ciphertext = plaintext ^ keystream`


RC4 sẽ mã hóa `k = IV|PSK` của ta để tạo ra `keystream` bằng cách thực hiện 2 hàm: Key Scheduling Algorithm (KSA) và Pseudo Random Generation Algorithm (PRGA).

## Key Scheduling Algorithm (KSA)
Gọi $S_i[k]$ là giá trị thứ k của mảng $S$ sau khi hàm KSA thực hiện được $i$ bước rồi.
Pseudo code:

## Key Random Generation Algorithm (KRGA)
Sau khi đã tạo được mảng $S$, ta sẽ không sử dụng $key$ nữa. Ta sẽ tạo $keystream$ mới dựa trên mảng $S$, ta vẫn sẽ tiếp tục hoán vị mảng $S$ nhưng đầu ra $keystream$ phải đảm bảo bằng với độ dài của $plaintext$.
Pseudo code:

Code RC4:

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

def PRGA(S, n):
    i, j = 0, 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)

## FMS attack
Bây giờ, ta muốn biết được giá trị $key[A+3]$ là gì thì ta sẽ dùng weak IV có dạng là:
`IV = [A+3, 255, x]`

Ở hàm KSA, ta giả sử: $i = L$
$\Rightarrow j_{L + 1} = j_L + S_L[L] + key[L]$
$\Rightarrow key[L] = j_{L+1}-j_L-S_L[L]$ $(*)$

Ở đây, mình sẽ giải thích tại sao với weak IV như vậy thì ta có thể tìm ra được $key$ (giả sử mình muốn tìm $key[3]$ => A = 0 => `IV = [3, 255, x]`):
Round đầu tiên của hàm KSA sẽ được thực hiện như sau:
Sau đó swap(S[i], S[j]).
Round thứ 2:
Sau đó swap(S[i], S[j]).
Round thứ 3:
Sau đó swap(S[i], S[j]).
Round thứ 4:
Sau đó swap(S[i], S[j]).

Sau 4 round thì ta có mảng $S$ hiện tại như thế này:

Note: với các giá trị $x$ khác nhau, có khoảng 5% sau khi kết thúc KSA thì 2 vị trí đầu tiên là $S[0] = A+3, S[1] = 0$ không bị thay đổi vị trí.

Ta có khoảng 5% các giá trị $x$ thì: $Q = j_{L+1}$
Từ $(*)$ suy ra: $key[L] = j_{L+1}-j_L-S_L[L] = Q - j_L - S_L[L]$.

Bây giờ ta muốn tìm được $key[L]$ thì ta phải biết được $Q$.

Ở trong hàm PRGA, khi thực hiện lượt đầu tiên:

Khi tìm được giá trị $Q$ rồi thì ta có thể suy ra được $key[L]$ là gì.
Tương tự, ta có thể lần lượt recover từng vị trí của $key$.

Code (Oh Snap CryptoHack):

from pwn import *
import json
import requests

def send_cmd(nonce, ciphertext):
    url = "http://aes.cryptohack.org/oh_snap/send_cmd/"
    r = requests.get(url + ciphertext + "/" + nonce + "/")
    return r.json()["error"].split()[-1]

secret_key = []
for A in range(50):
    probs = [0] * 256
    for x in range(256):
        nonce = bytes([A + 3, 255, x])
        ciphertext = b"0" * 50
        plaintext = bytes.fromhex(send_cmd(nonce.hex(), ciphertext.hex()))
        keystream = xor(ciphertext, plaintext)

        key = nonce + bytes(secret_key)
        S = list(range(256))
        j = 0
        for i in range(A + 3):
            j = (j + S[i] + key[i % len(key)]) % 256
            S[i], S[j] = S[j], S[i]

            if i == 1:
                o0, o1 = S[0], S[1]

        i = A + 3
        if S[1] + S[S[1]] == A + 3:
            if o0 != S[0] or o1 != S[1]:
                continue
            key_byte = (keystream[0] - j - S[i]) % 256
            probs[key_byte] += 1

    secret_key.append(probs.index(max(probs)))
    print(chr(secret_key[-1]), end = '')