[Cryptography] Stream Cipher - RNG, RC4

[Cryptography] Stream Cipher - RNG, PRNG, RC4

Random Number

- Stream cipher에서 사용되는 Key stream을 생성하는데 사용

TRNG

- 실제로 랜덤성을 가진 source를 이용하여 random bit stream 생성

PRNG

- Seed를 입력으로하는 알고리즘을 사용하여 random bit stream 생성

- 공격자가 Seed를 알고 있을 경우, 해당 Seed를 이용해 같은 random number 재생성

1. Requirements

- Randomness : random number처럼 보여야함(uniformity, scalability, consistency)

- Unpredictability : Random한 수들의 규칙을 보고 앞, 뒤의 random number를 예측할 수 없어야함

- Seed : 예측 불가능하고 안전해야함

PRF

- 고정된 길이의 random bit stream 생성

Natural Random Noise

- 위에서 설명한 방법도 결국 완전한 Random number는 아니고 Random number처럼 보이게 해주는 Pseudo일 뿐임

- 실제적으로 random number를 발생하기 위해 Real World에 존재하는 여러가지의 natural randomness를 이용하여 random number를 발생시킬 수 있음

- 복합적인 source들을 이용하는 방법

Stream Cipher

Stream Cipher

- bit 단위(stream)으로 message 암호화

- pseudo random keystream 사용

- plaintext와 key stream을 xor하여 암호화/복호화

RC4

- byte-oriented stream cipher

- 다양한 key 길이

- web의 SSL/TLS에 사용되었고 무선 환경의 WEP/WPA에 사용되었음

1. RC4 Key 생성(초기 단계)

for i = 0 to 255:
    S[i] = i
     T[i] = K[i % keylen]
j = 0
for i = 0 to 255:
    j = (j + S[i] + T[i]) % 256                           
    swap(S[i], S[j])

- Byte 단위의 256개 배열 S와 T 생성

- S는 각 index 값으로 초기화

- T는 키를 반복하여 채움

- 0부터 255의 index를 반복하며 j = (j+S[i]+T[i])%256으로 설정하고 S[i]와 S[j] swap

2. RC4 Encryption

i=0
j=0
for message:
     i = (i + 1) % 256
     j = (j + S[i]) % 256
     swap(S[i], S[j])
     t = (S[i] + S[j]) % 256                              
     Ci = Mi XOR S[t]

- i를 1씩 증가시켜가며 message의 길이만큼 반복

- j는 초기화 했던 S의 S[i]를 더해주며 반복

- S[i]와 S[j] swap

- t는 (S[i] + S[j]) % 256의 값으로 설정

- 평문의 i index와 S[t]를 xor하여 암호문 생성

3. Security

- 대부분의 공격에는 안전하다고 되어있음

- RC4는 key를 재사용하지 않음

- WEP가 안쓰이게 된 이유에는 RC4의 문제보다는 key를 잘못 사용했기 때문이라는 말이 있음