Stream Cipher

이번에는 Block, Stream Cipher에 대해 살펴보고 Block Cipher의 대표적인 DES에 대해 살펴볼 것이다.

쉽게 말하자면 Block은 Block단위로 암호화되고 Stream은 한 비트 또는 Byte level로 암호화된다.

물론 Byte를 하나의 Block으로 보진 않는다. 

각 Cipher 과정에 들어가는 Input을 보게 되면 Stream의 경우 x0, x1... xb가 Stream 형식으로 들어가는 것을 표현하였고

Block의 경우 x0,x1 ... xb가 하나의 block으로 들어가는 것을 표현하였다.

 

스트림을 보면 독특한 구조를 가진다. 

이는 평문의 값을 key stream과 xor 하여 암호문이 나온다는 것이다. 

그리고 다시 암호문을 xor 하면 평문이 나온다. 

여기서의 xor는 mod2연산과 동일하게 볼 수가 있다. 

 

그렇다면 bit, byte에 따라 구분한다기보다 스트림에 대해 xor연산을 수행한다는 것을 Stream Cipher로 구분할 수 있겠다.

 

동기화, 비동기화된 Stream Cipher에 대해 알아보자. 

여기서의 동기화란 기존 시그널에(key) 대해 영향을 받았다는 것을 의미한다. 

어떤 k는 key stream generator에 의해서 si로 변한다. 

이 si는 0이나 1이 될 확률, 각각의 확률은 0.5이다. 이때의 엔트로피가 가장 높다고 말한다. 

 

이런 key stream(si)이 key값에만 의존할 때가 동기화

비동기화는 암호문이 다시 Feedback에 걸려서 si에 영향을 준다는 것이다.

 

그렇다면 Stream Cipher의 xor(=mod 2) 연산이 왜 암호학적으로 좋은 것인가? 

 

이는 평문 x에 key si를 xor 연산하여 나온 yi값을 나타낸 것이다. 

xi가 0이라도 yi는 0과 1, 1이라도 0과 1이 나온다. 즉 제일 높은 엔트로피를 보여주며 si의 난수성이 암호문에 그대로 적용이 된다는 것이다.

이번엔 또 다른 Stream Cipher의 예제를 보자

이는 Linear recurrence를 가진다. 

여기서 xm... xm+2는 레지스터이다. 

이 세 개의 register에 0이 아닌 임의의 값이 대입된다. 이를 Initial state라고 한다.

그리고 이 register의 값이 shift 된다. 

즉 이러한 구조는 레지스터를 활용하여 key stream을 생성하는 방법이다. 

xm값은 plain text와 xor가 되어 암호문이 되어 출력되고

xm은 xm+1과 xor연산이 되어 xm+2에 들어간다. 

그리고 xm+1과 xm의 값은 그대로 밀려난다. 

 

하지만 이는 generate 되는 sequence가 linear 하기 때문에 규칙성을 가질 수밖에 없다.

따라서 일정 길이의 평문과 암호문이 있을 때 sequence를 예측하여 공격당할 수가 있다.

 

이는 해당 공격이 이루어지는 과정이다. 

물론 이러한 linear 한 특성을 없앤 다양한 Stream Cipher방법이 있다. 

 

 

이는 휴대폰 GSM의 A5/1 Stream Cipher이다. 

0에서 18까지가 r1레지스터이고 r2, r3레지스터 또한 존재한다. 

각각 비트수가 다르고 tap out 되는 부분과 크기도 다르다.(=xor)

그리고 각 register에 대해 majority를 본다. 이는 0 또는 1로 구할 수가 있다. 

그리고 majority에 해당하는 하나의 레지스터만 left shift가 일어난다. 

즉 불규칙하게 어떤 레지스터는 shift가 일어나고 어떤 건 안 일어나므로 비선형성이라고 할 수 있다.

하지만 이 또한 공격이 당할 수 있다고 한다...

 

 

이는 거의 마지막에 안전하다고 나온 Stream Cipher 모델이라고 한다. 

다른 비트수의 총 3개의 레지스터에 적절히 피드백을 걸고 and 연산도 포함이 되어있다.

이 연산에 따라서 xor 되는 것이 달라지는 구조이다. 

and 연산이 Non-linearity를 살려주는 구조이다. 

조금 더 자세한 구조를 보자면 

초기 벡터는 a에 80비트 정도이고 b에는 80bit 정도의 key가 들어간다.

그리고 c의 109,110,11번째에 1을 넣고 나머지 비트는 0이 들어간다. 

그리고 초기 1152 클락 동안 generation 되는 건 버리고 그 이후부터 사용하는데 이를 warm up 과정이라고 한다.

그 이후에 생성된 것을 평문과 xor 하여 사용된다. 

이는 초기에 생성되는 예측 가능한 stream을 막기 위해서인 것 같다. 

 

앞의 방법과 비교했을 때 비교적 복잡한 방법이지만 결국은 어떠한 key stream을 더욱 안전하게 generator 하는 것이 

issue이고 이러한 key stream과 xor연산을 통해 암호문을 생성한다는 것은 변함이 없는 Stream Cipher의 특성이라는 것을 알 수가 있다.