The challenge

This challenge consisted into recovering an ARC4 encrypted flag, using a known-plaintext attack (KPA) to recover the keystream used during encryption.

The files

From the three files provided for this challenge, one of them (chall.py) contained the program that encrypted the flag:

from Crypto.Cipher import ARC4	# pip3 install pycryptodome
import os

KEY = os.urandom(16)
FLAG = "******************* REDUCTED *******************"

menu = """
+--------- MENU ---------+
|                        |
| [1] Show FLAG          |
| [2] Encrypt Something  |
| [3] Exit               |
|                        |
+------------------------+
"""

print(menu)

while 1:
	choice = input("\n[?] Enter your choice: ")

	if choice == '1':
		cipher = ARC4.new(KEY)
		enc = cipher.encrypt(FLAG.encode()).hex()
		print(f"\n[+] Encrypted FLAG: {enc}")

	elif choice == '2':
		plaintext = input("\n[*] Enter Plaintext: ")
		cipher = ARC4.new(KEY)
		ciphertext = cipher.encrypt(plaintext.encode()).hex()
		print(f"[+] Your Ciphertext: {ciphertext}")

	else:
		print("\n:( See ya later!")
		exit(0)

As we can see, the encryption key is randomly generated using os.urandom() which is usually a (relatively) secure way to get random data for encryption.

The other two files were an image and a text, both containning the same output from one execution of this program.

Output

As the key is generated only once for each execution, all the cipher texts on this file, including the flag, were encrypted using the same 16-byte key. You will see why this is relevant next.

ARC4 is broken

First, let’s start with a brief review of how ARC4 (Alleged RC4) works and why it is broken. Without going too much into implementation details, ARC4 works by generating a pseudo-random stream of bits (known as keystream) that can be combined with the plain text through bitwise xor operations, resulting in a cipher text (see RC4 to learn more).

The problem with this is that if we know any number of bytes of the plain text, it is possible to recover the same number of bytes of the keystream even without knowing the original key, by performing a xor of the cipher text against the known plain text. As one key will always generate the same keystream, RC4 is extremely weak when keys are reused.

In practice, this means that if we use the same key to encrypt multiple texts, someone that know part of at least one of them can decrypt an equally large part of all the others.

To solve this challenge, all we need to do is choose from the file out.txt a combination of plain text and cipher text that is at least the same size of the flag. By counting the number of characters into the hexadecimal representation of the encrypted flag and dividing it by 2, we find that the flag has 48 bytes, so any plain text with at least this same size will do. I choosed the following combination that has a length of 52 bytes:

[*] Enter Plaintext: abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz
[+] Your Ciphertext: 3d5d841c4df203758189060d7ba5ef0460c90faeae890dc621dfb563a03cc5f728d42794ae8a08102f2766acece427f3c6514fc7

Next, I recovered 52 bytes of the keystream using IPerl .

IPerl> @plaintext = split //, "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz
IPerl> @ciphertext = map { hex } "3d5d841c4df203758189060d7ba5ef0460c90faeae890dc621dfb563a03cc5f728d42794ae8a08102f2766acece427f3c6514fc7" =~ /.{2}/g
IPerl> @keystream = map { ord($plaintext[$_]) ^ $ciphertext[$_] } 0 .. 51

And finally, I used the keystream the recover the flag:

IPerl> @encflag = map { hex } "385e95136bdb2a66baa0593e27b8df03228f1785ea9925c768d08b74b06bffe27bd17da1aed51c21342026bdacb173f8" =~ /.{2}/g
IPerl> $flag = join '', map { chr($encflag[$_] ^ $keystream[$_]) } 0 .. 47

The flag was: darkCON{RC4_1s_w34k_1f_y0u_us3_s4m3_k3y_tw1c3!!}

And that’s all, folks.