# RC4 và FMS attack


Rivest Cipher 4 là một loại mã hóa đã có từ những năm 1980. Đây là một trong những mật mã dòng phổ biến nhất và sớm nhất. Nó đã được sử dụng rộng rãi trong các giao thức **Secure Socket Layer** (SSL) và Transport Layer Security (TLS), Wireless Equivalent Protocol (WEP) và tiêu chuẩn mạng LAN không dây IEEE 802.11.

Mặc dù việc sử dụng nó khá phổ biến trong nhiều năm qua vì tốc độ và tính dễ sử dụng nhưng ngày nay, RC4 được coi là tiềm ẩn nhiều rủi ro về bảo mật.

# Cấu trúc stream cipher


Stream cipher hay mật mã dòng điển hình mã hóa văn bản gốc mỗi lần một byte, mặc dù mật mã dòng có thể được thiết kế để hoạt động trên từng bit một hoặc trên các đơn vị lớn hơn một byte mỗi lần. Trong cấu trúc này, một khóa được đưa vào bộ tạo bit giả ngẫu nhiên để tạo ra một dòng số 8 bit dường như là ngẫu nhiên, thực chất những giá trị ngẫu nhiên này được tạo ra từ 1 thuật toán cụ thể nhưng ta khộng thể đoán trước được nếu không sở hữu khóa đầu vào (input key) _ ta có thể tạm gọi quá trình này là trình tạo khóa dòng ngẫu nhiên. Đầu ra cảu quá trình này được gọi là **keysteam (khóa dòng),** bằng cách ****kết hợp từng byte tại một thời điểm với bản rõ bằng cách sử dụng phép toán bitwise exclusive**-**OR (XOR).

Ví dụ:

		11001100  plaintext
xor
		01101100  key stream
=>  10100000  ciphertext

Viêc giải mã yêu cầu phải sử dụng cùng 1 **keystream**:

		10100000  ciphertext
xor
		01101100  key stream
=>  11001100  plaintext

Với bộ tạo số giả ngẫu nhiên được thiết kế phù hợp, mật mã dòng có thể được đảm bảo an toàn như mật mã khối có độ dài khóa tương đương. Ưu điểm chính của mật mã luồng là mật mã luồng hầu như luôn nhanh hơn và sử dụng ít mã hơn nhiều so với mật mã khối. RC4 có thể được triển khai chỉ bằng một vài dòng mã. Tuy nhiên, nếu hai bản rõ được mã hóa bằng cùng một khóa bằng cách sử dụng mật mã dòng thì việc phân tích mật mã thường khá đơn giản. Nếu hai bản mã cùng streamkey của Stream cipher được XOR cùng nhau thì kết quả sẽ là XOR của bản rõ ban đầu. Nếu bản rõ là chuỗi văn bản, số thẻ tín dụng hoặc các stream byte khác có thuộc tính đã biết thì việc phân tích mật mã có thể thành công.


# **The RC4 Algorithm**

Thuật toán RC4 rất đơn giản và khá dễ giải thích. Khóa có độ dài thay đổi từ 1 đến 256 byte (8 đến 2048 bit) được sử dụng để khởi tạo vectơ trạng thái (**initialize vector**) 256 byte-**S**, với các phần tử S[0], S[1], ..., S[255]. Tại mọi thời điểm, **S** chứa hoán vị của tất cả các số 8 bit từ 0 đến 255. Để mã hóa và giải mã, một byte **K** được tạo ra từ **S** bằng cách chọn một trong 255 phần tử theo cách có hệ thống. Khi mỗi giá trị của **K** được tạo ra, các phần tử trong **S** lại được hoán vị.


## Khởi tạo S _ KSA (Key Schedule Algorithm)

Để bắt đầu, các phần tử của S được đặt bằng các giá trị từ 0 đến 255 theo thứ tự tăng dần; đó là; `S[0] = 0, S[1] = 1, ..., S[255] = 255`. Một vectơ tạm thời T cũng được khởi tạo. Nếu độ dài của khóa `K` là 256 byte thì `K` được chuyển sang `T`. Mặt khác, đối với khóa có độ dài `keylen` byte, các phần tử khóa đầu tiên của `T` được sao chép từ `K` và sau đó `K` được lặp lại nhiều lần nếu cần thiết để điền vào `T`. Ta có thể tóm tắt qua mã giải như sau:

/* Initialization */
for  i = 0 to 255 do
	S[i] = i;
	T[i] = K[i mod keylen];

Tiếp theo, chúng ta sử dụng `T` để tạo ra hoán vị ban đầu của `S`. Điều này bao gồm việc bắt đầu từ `S[0]` và đến `S[255]`, và với mỗi `S[i]`, hoán đổi `S[i]` với một byte khác trong `S` theo sơ đồ được quyết định bởi `T[i]`:

/* Initial Permutation of S */
j = 0;
for  i = 0 to 255 do
	j = (j + S[i] + T[i]) mod 256;
	Swap (S[i], S[j]);

Bởi vì thao tác duy nhất trên `S` là `swap` nên hiệu ứng duy nhất là hoán vị. `S` vẫn chứa tất cả các giá trị từ 0 đến 255.

python code:

N = 256
# Generates a permutation S: [0..255] -> [0..255]
def ksa(k: bytes, rounds: int = N) -> list[int]:
    S = list(range(N)) # identity permutation
    j = 0
    for i in range(rounds):
        j = (j + S[i] + k[i % len(k)]) % N
        S[i], S[j] = S[j], S[i] # swap

    return j, S

## PRGA ( Pseudo Random Generation Algorithm)

Sau khi S được khởi tạo, Input Key sẽ không được sử dụng nữa. Ta sẽ tiếp tục khởi tạo keystream K mới dựa trên S đã được khởi tạo thông qua thuật toán được qui ước sẵn. Ta sẽ tiếp tục hoán vị vị trí của từng giá trị của S nhưng đầu ra của ta sẽ phụ thuộc vào độ dài của bản rõ.

/* Stream Generation */
i, j = 0;
while (true)
	i = (i + 1) mod 256;
	j = (j + S[i]) mod 256;
	Swap (S[i], S[j]);
	t = (S[i] + S[j]) mod 256;
	k = S[t];

Để mã hóa ta sẽ xor k được khởi tạo mỗi vòng với với từng bytes của bản rõ đến khi tất cả các bytes trong bản rõ được xor. Ngược lại để giải mã, ta chỉ việc tái tạo lại K và xor với bản mã sẽ thu được bản rõ ban đầu.

python code:

# Generates a stream based on a given permutation S
def prga(S: list[int]):
    i = j = 0
    while 1:
        i = (i + 1) % N
        j = (j + S[i]) % N
        S[i], S[j] = S[j], S[i]

        k = S[(S[i] + S[j]) % N]
        yield k

def decrypt(ct: bytes, key: bytes):
    _, S = ksa(key)
    stream = prga(S)
    return bytes(a ^ b for a, b in zip(ct, stream))

# Điểm yếu của RC4

1. Các Lỗ Hổng về Khóa:
- Sự Yếu Điểm trong Thiết Lập Khóa: RC4 có một lỗ hổng trong thuật toán thiết lập khóa của nó, điều này có nghĩa là một số khóa cụ thể có thể dẫn đến việc xuất ra dữ liệu mất cân đối. Điều này có thể dẫn đến rò rỉ thông tin một phần hoặc hoàn toàn về khóa.
2. Sự Thiên Lệch Thống Kê:
- Byte Ban Đầu: Các byte ban đầu của dãy khóa RC4 bị thiên lệch. Điều này có nghĩa là các byte đầu tiên của dãy khóa không ngẫu nhiên như nên, làm cho việc dự đoán chúng dễ dàng hơn đối với kẻ tấn công.
- Lập Lịch Khóa: Thuật toán lập lịch khóa của thuật toán có thể tạo ra sự thiên lệch thống kê trong dãy khóa, làm cho việc khôi phục lại khóa mã hóa dễ dàng hơn đối với kẻ tấn công.
3. Dễ Bị Tấn Công Thống Kê:
- Tấn Công Fluhrer-McGrew: Đây là một tấn công thống kê đã biết đối với RC4 có thể được sử dụng để xác định khóa trong một số trường hợp. Nó khai thác các sự thiên lệch trong dãy khóa mà phát sinh từ các khóa yếu.

# **Fluhrer, Mantin and Shamir attack (FMS attack)**

### WEP


WEP được đưa vào làm thành phần bảo mật của tiêu chuẩn IEEE 802.11 ban đầu được phê chuẩn vào năm 1997, sử dụng RC4 để bảo mật và tổng kiểm tra CRC-32 để đảm bảo tính toàn vẹn.

### **Recover the key in WEP**

Như ta thấy KEY ở trên sẽ bao gồm 2 phần là IV và SHARED KEY.

Quy ước:

- `K`: KEY
- `IV`: iv
- `SK`: SHARED KEY.
- `l`: độ dài của khóa `K`

K = [IV[0], IV[1], IV[2], SK[0], SK[1],....SK[l - 1 - i]]

Gỉa sử ta được chọn IV cho một hệ thống mã hóa RC4 nào đó. Để có thể recover KEY tại vị trí (A+3), khi đã biết các vị trí phía trước của khóa (nếu chưa biết được byte nào thì chọn A = 0), ta sẽ dùng weak IV có dạng như sau:

IV = [A+3, n-1, V] = [A+3, 255, V]

Trong đó:

`A` là một byte bất kì

`V` là một byte bất kì.

Với dạng iv như vậy ta sẽ recover lại được `KEY[A+3]` . Ta có thể hình dung tại sao như sau

Sau round đầu tiên của KSA, S_BOX có trạng thái như sau:


Sau round thứ 2, S_BOX sẽ thành:


Round tiếp theo `j` sẽ có giá trị là `j1+V+2`. Và ta có thể tiếp tục như vậy đến khi biểu thức của ta cho đến khi gặp biểu thức chứa `K[A+3]` .

Và với các giá trị V khác nhau, có khoảng 5% sau khi kết thúc KSA thì 2 là [A+3, 0] không bị thay đổi vị trí. Và nếu không bị thay đổi S_BOX sẽ như sau:


Ta sẽ áp dụng biểu thức sau:

$$
K[0] = S[S[1] + S[S[1]]] = S[0 + s[0]
$$

$$
= S[A+3] = S_A + 2[j_{A+3}]
$$

$$
= S_A + 2[j_{A+2} + S_{A+2}[A+3] + K[A+3]]
$$

Từ đó ta có thể tìm được K[A+3], cứ tiếp tục như vậy đến khi thu được toàn bộ KEY

# CTF Challenge

## CRYPTOHACK/****SYMMETRIC CIPHERS/Oh SNAP****

[https://aes.cryptohack.org/oh_snap/](https://aes.cryptohack.org/oh_snap/)

from Crypto.Cipher import ARC4

FLAG = ?

@chal.route('/oh_snap/send_cmd/<ciphertext>/<nonce>/')
def send_cmd(ciphertext, nonce):
    if not ciphertext:
        return {"error": "You must specify a ciphertext"}
    if not nonce:
        return {"error": "You must specify a nonce"}

    ciphertext = bytes.fromhex(ciphertext)
    nonce = bytes.fromhex(nonce)

    cipher = ARC4.new(nonce + FLAG.encode())
    cmd = cipher.decrypt(ciphertext)
    if cmd == b"ping":
        return {"msg": "Pong!"}
    else:
        return {"error": f"Unknown command: {cmd.hex()}"}

### Solution

import requests
from Crypto.Util.Padding import unpad
from Crypto.Cipher import ARC4
from Crypto.Util.number import*
from tqdm import tqdm

# Helper function, which swaps two values in the box.
def swapValueByIndex(box, i, j):
    temp = box[i]
    box[i] = box[j]
    box[j] = temp

# Initialize S-box.
def initSBox(box):
    if len(box) == 0:
        for i in range(256):
            box.append(i)
    else:
        for i in range(256):
            box[i] = i

def send_cmd(ciphertext, nonce):
    res = requests.get(f"http://aes.cryptohack.org/oh_snap/send_cmd/{ciphertext.hex()}/{nonce.hex()}/")
    return res.json()

key = [None]*3
for i1 in tqdm(range(len(key)-3,34)):
    prob = [0] * 256
    for i2 in tqdm(range(256)):
        key[0] = i1+3
        key[1] = 255
        key[2] = i2
        j = 0
        box = []
        initSBox(box)
        # Simulate the S-Box after KSA initialization.
        for i in tqdm(range(key[0])):
            j = (j + box[i] + key[i]) % 256
            swapValueByIndex(box, i, j)
            # Record the original box[0] and box[1] value.
            if i == 1:
                original0 = box[0]
                original1 = box[1]
        i = key[0] #A+3
        z = box[1] #0

        # if resolved condition is possibly met.
        if z + box[z] == key[0]:
            # If the value of box[0] and box[1] has changed, discard this possibility.
            if (original0 != box[0] or original1 != box[1]):
                continue
            nonce = long_to_bytes(key[0])+long_to_bytes(key[1])+long_to_bytes(key[2])
            a = send_cmd(b'\x00',nonce)['error']
            keyStreamByte = int(a.split(': ')[1],16)
            keyByte = (box.index(keyStreamByte) - j - box[i]) % 256
            prob[keyByte] += 1
        # Assume that the most hit is the correct password.
        higherPossibility = prob.index(max(prob))
    key.append(higherPossibility)
    print(higherPossibility, chr(higherPossibility))

for i in key[3:]:
    print(chr(i),end="")

**References**

[https://people.computing.clemson.edu/~jmarty/courses/commonCourseContent/AdvancedModule-SecurityConceptsAndApplicationToLinux/RC4ALGORITHM-Stallings.pdf](https://people.computing.clemson.edu/~jmarty/courses/commonCourseContent/AdvancedModule-SecurityConceptsAndApplicationToLinux/RC4ALGORITHM-Stallings.pdf)

[https://link.springer.com/content/pdf/10.1007/3-540-45537-X_1.pdf](https://link.springer.com/content/pdf/10.1007/3-540-45537-X_1.pdf)