RC4 암호화 알고리즘 정리 및 예제 (feat SSTF2023)

RC4 알고리즘이란?

- 암호화와 복호화에 동일한 shared key를 사용하는 symmetric encryption

- 스트림 암호 중 하나로 전송 계층 보안(TLS, SSL) 등 여러 프로토콜에 사용되었던 암호 방식

- 256바이트 이내의 key와 256바이트 초기배열 S를 이용해 PlainText와 동일한 길이의 Key Stream을 생성하고, 각 바이트 XOR을 통해 key stream을 생성한다

- key stream을 안다면 xor을 통해 암호화 및 복호화가 가능하다

 

RC4 알고리즘 동작 방식

Step1. 초기 상태 벡터 S와 임의 벡터 T를 생성한다

- S와 T는 256바이트 벡터

- S[i]=i (i=0~255) 인덱스 값을 채우고, T에는 key를 반복적으로 채운다

 

Step2. KSA 알고리즘에 의해 초기 상태 벡터 S를 섞는다

j=0 , S[i]=0, T[i]=75

S[0]과 S[75] swap, i=1 사이클에서 j=75인채로 시작하겠지

- i=0~255 까지 증가시켜나간다, j의 초기값은 0이다

- 각 턴에서  j= (j + S[i] + T[i]) mod 256 를 구하고, 인덱스 i와 j를 서로 swap 한다

- S의 모든 인덱스를 건들며 섞일 것이다. key가 동일하면 shuffle 후의 S 벡터도 동일하겠지

 

i=255 에서 permuted State Vector 생성

for i from 0 to 255
    S[i] = i
j = 0
for i from 0 to 255
    j = (j + S[i] + key[i mod keylength]) mod 256
    swap S[i] and S[j]

Step3. PRGA 알고리즘에 의해 plaintext와 동일한 길이의 Key Stream을 생성한다

i=1, j=S[i]=170, i번째 원소와 j번째 원소를 swap

S[i]+S[j] mod 256 인덱스에 있는 값을 가져온다, S[251] = 149, 이것이 Keystream의 첫바이트

이런 식으로 KeyStream을 한 바이트씩 구해나간다

i = j = 0
while len(Generated)<len(Plaintext):
    i = (i + 1) mod 256
    j = (j + S[i]) mod 256
    swap S[i] and S[j]
    K = S[(S[i] + S[j]) mod 256]
    output K
endwhile

 

Step4. 생성된 KeyStream과 평문을 한 바이트씩 XOR한다

- 암호화 과정 자체는 단순

- 영상은 : https://www.youtube.com/watch?v=kfdvlaOD1ig&t=172s&ab_channel=MohamedAsaad

 

취약점 분석 예제 1

from Crypto.Cipher import ARC4
from binascii import hexlify
from secret import key, flag

def encrypt(data):
	return ARC4.new(key).encrypt(data)

ct = b""
for ch in flag:
	ct += encrypt(ch)

print("Ciphertext =", hexlify(ct).decode())

'''
$ python3 challenge.py
Ciphertext = 6f47474c06086f47085c47085c404d08464d505c085b5c494f4d09
'''

- ciphertext 생성과정을 보니 플래그에서 한 바이트씩 받아와서 1 Byte RC4 암호화 

- 동일한 key를 사용하므로 매 encrypt()에 사용되는 키 스트림 한 바이트도 동일할 것

 

0~255 브포 돌려서 유효한 Plaintext 나오는 경우 파악

from Crypto.Cipher import ARC4
from binascii import unhexlify

ct = unhexlify(b'6f47474c06086f47085c47085c404d08464d505c085b5c494f4d09')

for i in range(1,256):
    plain = ""
    for ch in ct:
        plain += chr(i^ch)

    print(str(i) + " " + plain) # 40 Good. Go to the next stage!

 

취약점 분석 예제 2

from Crypto.Cipher import ARC4
from secret import key, flag
from binascii import hexlify

#RC4 encrypt function with "key" variable.
def encrypt(data):
	#check the key is long enough
	assert(len(key) > 128)

	#make RC4 instance
	cipher = ARC4.new(key)

	#We don't use the first 1024 bytes from the key stream.
	cipher.encrypt("0"*1024)

	#encrypt given data, and return it.
	return cipher.encrypt(data)

msg = "RC4 is a Stream Cipher, which is very simple and fast."

print (hexlify(encrypt(msg)).decode())
print (hexlify(encrypt(flag)).decode())
'''
634c3323bd82581d9e5bbfaaeb17212eebfc975b29e3f4452eefc08c09063308a35257f1831d9eb80a583b8e28c6e4d2028df5d53df8
624c5345afb3494cdd6394bbbf06043ddacad35d28ceed112bb4c8823e45332beb4160dca862d8a80a45649f7a96e9cb
'''

- RC4 알고리즘을 이용해 msg와 flag를 암호화했다. 동일한 key 사용했으므로 동일한 key stream과 xor 되었을 것

- PT1 xor KS = CT1 , PT2 xor KS = CT2 일 때, CT1 xor CT2 = PT1 xor PT2 즉 PT2 = PT1 xor CT1 xor CT2

- 즉 flag는 우리가 아는 cipher text 2개와 msg를 xor 해서 구할 수 있겠다

그림으로 표현하면...

 

from binascii import unhexlify

ct1 = unhexlify(b'634c3323bd82581d9e5bbfaaeb17212eebfc975b29e3f4452eefc08c09063308a35257f1831d9eb80a583b8e28c6e4d2028df5d53df8')
ct2 = unhexlify(b'624c5345afb3494cdd6394bbbf06043ddacad35d28ceed112bb4c8823e45332beb4160dca862d8a80a45649f7a96e9cb')

msg1 = b'RC4 is a Stream Cipher, which is very simple and fast.'

msg2 = ''
for c1, c2, m1 in zip(ct1,ct2,msg1):
    msg2 += chr(c1 ^ c2 ^ m1)

print(msg2)

// zip 함수는 길이가 제일 짧은 element 기준으로 동작한다