스트림 암호(Stream Cipher) #RC4

인터넷에서는 이해하기 어려운 내용이 주를 이뤄 검색해도 알아듣기가 쉽지 않았다.(그들은 과연 모두 이해하고 그렇게 올린것일까) 그래서 스스로 수없이 검색해보고 이해해 보며 조금이나마 이해하기 쉽게 서술해보려 한다. 내용에 부족한 부분이 있어도 이해해주시고, 바로잡아주시면 감사드릴것 같다.

RC4란?

스트림 암호의 종류 중 하나로, 전송 계층 보안(TLS/SSL)이나 WEP 등 여러 프로토콜에 사용되었었던 암호방식이다. 현재는 취약점이 발견되어 권장하고있지 않고있다고 한다. 바이트 단위로 처리하기 때문에 다른 비트 단위 암호보다 실행속도가 빠르다. 

RC4 암호체계

RC4 역시 다른 대부분의 스트림 암호와 비슷하게 XOR 연산을 통해 암호화를 진행한다. 하지만 이해하기 어려웠던 부분은 그 암호화를 하기까지의 과정이다. 

자세하기 들어가기 전에 RC4암호체계가 어떻게 구성되어 있는지 큰 단위로 살펴보면 아래와 같다

- 키 스트림이 만들어지기 위한 재료로서 임의의 배열 선언

- 배열을 안에 각 인덱스를 값으로 넣음 ( S[] = {0,1,2,3,4,5,6,7,8, ... } )

- 키값을 통해 배열의 값을 섞는다

- 정해진 규칙으로 배열을 이용해 키 스트림 생성

- XOR을 통한 암호문 생성

크게 보면 원리는 그리 복잡하지 않다. 단순히 순차적이지 않은 어떠한 테이블을 기반으로 정해진 규칙에 의해 키 스트림을 만들어내는 방식이다. 즉, 키가 배열을 구성하고, 배열이 키 스트림을 구성하고, 키 스트림이 암호문을 만들어낸다고 이해하면 좋다. 친절하지 않은 블로그가 좀 많은것 같아서 이해하기 어려웠던것 같다.

이제 조금 전문적으로 암호체계를 이해해보자

기본구성

- 256바이트의 룩업 테이블(Lookup table)이 존재 (아래 설명에서 배열S로 표시된다)

- 1byte(8bit)의 인덱스 포인터 두개가 존재 (아래 설명에서 i와 j로 표시된다)

알고리즘

- Key와 Plaintext를 받는다

- KSA을 통해 배열S를 구성한다

- PRGA을 통해 키 스트림을 구성하고, 평문을 암호화시킨다

KSA(Key-Scheduling Algorithm)

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

첫 번째 for문을 살펴보면 배열S에 각자 인덱스를 값을 대입하고 있음을 알 수 있다. 두 번째 for문에서는 정해진 규칙에 의해 배열 S를 섞는 과정을 진행한다. 해당 규칙은 아래와 같다

j = ( j + S[i] + key[ i % len(key) ] ) % 256
S[i] <------(swap)------> S[j]

이렇게 i를 0부터 배열S의 크기만큼 증가시키며 S의 모든 인덱스를 건들어 섞는다.

키가 동일하다면 배열S의 구성이 같아질 것이고, 여기서 도출된 키 스트림 또한 같아질 것이므로 암/복호화가 가능하게된다.

PRGA(Pseudo-Random Gerneration Algorithm) 

i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    K := S[(S[i] + S[j]) mod 256]
    output K
endwhile

키 스트림을 구성하는 알고리즘으로, 반복을 통해 배열 S도 바꾸면서 키를 출력한다. 위의 코드에서는 키 스트림의 일부를 K로 반환하고있다. K가 만들어지는 원리는 다음과 같다.

i = (i+1) % 256
j = (j+S[i]) % 256
S[i] <----(swap)----> S[j]
K = S[ S[i]+S[j] ] % 256

위의 규칙을 반복하면서 생성되는 K의 흐름이 키 스트림이된다. 이를 평문의 한 바이트와 XOR연산을 진행하여 암호문을 생성하게 된다. 이렇듯 비트단위가 아닌 바이트 단위로 처리하기 때문에 소프트웨어적으로 속도가 빠르다고 할 수 있다.