Block Cipher(블록 암호화)

이번에는 Block Cipher와 DES에 대해 알아본다.

우선적으로 Block Cipher는 대칭키 구조를 가진다. 여기서 대칭키란 암/복호화가 같은 키로써 대칭적으로 된다는 뜻이다.

Block Cipher에서는 Block 단위로 나눈 후 해당 Block에 대한 특정 연산을 취한다. 

Stream에서는 XOR를 했던 것처럼 말이다.

대표적으로 Feistel구조에 대해서 알아볼것이다.

 

Feistel구조는 Shanon의 SP Network에서 아이디어를 따왔다.

S-P란 Substitution-Permutation을 뜻한다. 

여기서 각각이 하는 역할은 무엇일까? 

Substitution은 S-Box에 의해서 이루어지며 이는 Confusion을 제공한다.

Permutation은 P-Box에 의해서 이루어지며 이는 Diffusion을 제공한다.

해석을 해보면

Diffusion은 평문과 암호 문간의 통계적인 특성을 최대한 흐트러 트린다.

좋은 Diffusion이란 input과 output을 0과 1로 바꿀 때 확률을 0.5와 같이 혼란이 가장 심하게 하는 것이다.

Confusion은 암호문과 key 간의 관계를 최대한 복잡하게 해서 암호문으로부터 키 값을 얻기 어렵게 한다.

그렇다면 구조를 한번 보자.

일단 L와 R 두 개의 Halves로 나눈다. 

R0 -> L1 : R에 있는 것은 다음 라운드의 L로 이동한다.

반면에 왼쪽에 있는 것들은 오른쪽 부분과 적당히 F함수와 변환하여 R로 이동한다.

위의 과정은 암/복호화 과정을 식으로 요약해둔 것이다. 

Decryption의 경우 얼핏 보면 다른 식처럼 보이지만 Encryption 식을 통해 유추가 가능한 식이다. 

즉 대칭키의 특성을 유지하고 있다.

이런 Feistel 구조를 디자인하는 데에는 여러 가지 요소가 존재할 수 있다. 

하지만 Computer Science에서 당연하듯이 Trade off관계를 가진다.

즉 Block size를 키우면 보안은 좋으나 시간은 오래 걸리며 

Key size가 길이지만 보안은 좋으나 시간이 오래 걸리는 것과 같다.

 

이제 기본 구조를 배웠으니 Block Cipher 하면 가장 먼저 떠오르는 DES에 대해서 알아본다. 

이는 IBM에서 개발한 Lucifer를 수정해서 개발한 것이다. 

그런데 Lucifer는 128bit였으나 DES는 후에 개발된 암호화 기법임에도 64bit이다. 

이에 대해 왜 보안성을 떨어진 걸 줬나 라는 논쟁이 있었다고 한다. 

하지만 검증해보니 문제가 있는 것은 아니었다. 

그럼에도 지금은 쓰지가 않는다. 그 이유는 느려서이다. 

 

 

구조는 이렇다. 

64bit 평문, 즉 블록화 된 평문에 56bit 키를 통해 64bit 암호문을 만들어 낸다. 

기본 연산은 치환, 전치, xor, 그리고 Feistel 구조를 가진다.

64bit의 평문이 들어오면 이러한 평문에 연산이 진행되는데

앞에서 Feistel구조에 대해서 16라운드의 연산을 거친다.

그런데 56bit의 key가 들어오므로 해당 64bit 평문에 맞는 64bit key와 16라운드 

즉 어떻게 보면 1024의 key가 필요하다.

이를 위해 key schedule이 진행된다. 이는 56bit의 key를 통해 각 round에 사용해준 key를 generate 한다.

이제 DES의 연산에 대해 대부분의 퍼즐이 맞춰지고 있다.

이번에는 Feistel구조 안의 라운드 함수에 대해서 보고자 한다.

32-bit가 input으로 들어간다. 이는 기존의 64bit를 2 halves로 나누었기 때문이다.

그리고 이 32bit를 48bit로 expansion 하고 6bit씩 8개로 나눈 후 다시 4bit로 줄여 32bit로 돌린다.

이를 요약해서 큰 그림으로 본다면 위의 사진과 같다.

 

이는 f함수 내에서 permutation 하는 과정이다. 

자세히 보면 matrix는 8x8행렬이고 이 순서대로 주어진 bit가 변경된다.

이는 Expansion이 되는 원리이다. 

해당 input이 duplicate 되면서 expansion이 되는데 이는 matrix가 6x8이므로 32bit 이후 의의 bit는 해당 table을 보고 duplicate 되어

반복된다.

이는 f함수에서 6bit가 4bit로 substitution 되는 과정이다. 

이는 해당 table을 보고 진행된다.

outer bit는 맨 처음 2비트를 의미하고 이에 따라 나머지 4bit를 보고 바뀔 4bit가 결정된다

위의 그림에서는 초록색 row와 주황색 col에 겹치는 노란색 bit로 변하게 된다. 

 

이는 key schedule이다. 

총 16 round에 해당하는 round key를 만들어야 되고 이것이 만들어지는 과정이다.

r1, r2, r3... 는 Left shift이고 Pc1, Pc2는 permuted choice이다. 

64bit key가 pc에 들어가서 k'으로 바뀐다. 

이는 56bit key로 나오게 되고 c0, d0 각각 28bit로 나누어 pc에 들어가서 round key가 생성되는 원리이다.

여기 까지만 봐도 세부적으로 구현되야할 것이 엄청 많다.

시간이 오래 걸릴 수밖에 없는 것 같고 공격하는 입장에서는 까다로울 것 같다.

 

하지만 key의 길이가 56bit이고 이는 2의 56승의 키가 나온다. 

brute force가 어렵지만 컴퓨터 기술의 발달로 생각보다 빨리 찾는다고 한다. 

이에 나온 것이 AES이다. 

 

이런 DES에 대해선 Timing attack, analytic attack 등이 가능하다고 한다.