네트워크 보안 - 3 | 대칭키 암호

현대 암호의 분류

2차 세계대전과 함께 놀랍도록 발전한 암호학은 고전 암호에서 현대 암호로 성장하게 되었다. 고전 암호에 비해 훨씬 수학적이고 학문적인 깊이가 깊어진 현대 암호는 시간이 지나면서 계속해서 발전해오고 있다.

 

여러 암호체계가 새로 생겨나고 또 도태되어 사라지면서, 현대 암호체계를 다양하게 분류할 수 있는데, 그중에서도 크게 세 가지 주제로 이를 분류할 수 있다.

 

바로 대칭키 암호체계, 공개키 암호체계, 해시함수이다. 이 중에서도 이번 포스트에서 알아볼 내용은 바로 대칭키 암호체계이다. 대칭키 암호체계는 대칭인 키를 이용하는 암호체계를 말하는데, 여기서 말하는 대칭키란 암호화와 복호화에 필요한 키가 서로 같다는 뜻이다. 즉, 데이터를 전송함에 있어 송신자와 수신자가 서로 같은 키를 공유해야 한다는 뜻이다.

 

이러한 대칭키 암호체계 역시 크게 스트림 암호와 블록 암호의 형식으로 나눌 수 있다. 물론 현재 스트림 암호의 경우 거의 사용되지 않지만, 그럼에도 해당 두 부분을 모두 살펴보도록 하겠다.

---

스트림 암호

스트림 암호는 고전 암호에서 공부한 일회성 암호의 방식을 사용한다. 분명 일회성 암호는 수학적으로 그 안전성이 증명된 암호 체계였지만, 매 암호화마다 평문의 길이와 동일한 크기의 키를 생성해야 하고, 이를 송신자와 수신자가 모두 같이 공유해야 한다는 단점이 있었다.

 

여기서 암호화를 진행할 때마다 평문의 길이와 동일한 크기의 키가 필요하다는 문제를 해결한 것이 바로 스트림 암호이다. 또 하나의 문제점인, 송수신자가 서로 같은 키를 공유해야 한다는 문제는 대칭키 암호체계의 전반적인 문제점인데, 이는 이후에 배울 공개키 암호체계를 이용해 해결할 수 있으므로 우선은 신경 쓰지 않도록 하자.

 

스트림 암호의 경우 암호를 다루기 쉽도록 상대적으로 작은 키를 사용할 수 있게 하였다. 하지만 이로 인해 일회성 암호가 가지는 수학적인 안전성은 다소 희생할 수밖에 없다. 중요한 것은 실제로 사용하기에는 무리가 있었던 일회성 암호 체계를 일반적으로 사용 가능한 형태로 변형하여 사용할 수 있었다는 것이다.

스트림 암호 원리

그렇다면 스트림 암호는 평문과 동일한 크기의 키가 필요하다는 점을 어떻게 해결하여 작은 키로도 작동할 수 있을까?

 

스트림 암호는 작은 길이를 가지고 있는 키를 이용하여, 이를 긴 키스트림으로 늘인다. 이때 이 키스트림이 실제 평문과 XOR연산을 하여 암호문을 만드는 데 사용된다. 즉, 간단히 말해서 스트림 암호는 상대적으로 작은 키를 긴 키스트림으로 변환하는 방식이 바로 핵심이다. 그리고 이 키스트림이 일회성 암호의 키와 동일하게 작동을 한다.

 

이러한 스트림 암호의 종류로는 A5/1과 RC4가 있는데 매우 간단하게 알아보도록 하겠다.

A5/1

A5/1은 소프트웨어보다는 하드웨어로 구현하도록 설계된 암호이다. 물론 소프트웨어를 이용해 구현할 수도 있지만, 암호 체계의 최초 목적이 하드웨어를 이용한 암호화와 복호화라는 뜻이다.

 

A5/1은 X, Y, Z라고 불리는 3개의 선형 피드백 시프트 레지스터(LFSR, Linear Feedback Shift Registers)를 사용한다. 이때 X, Y, Z 레지스터는 각각 19비트, 22비트, 23비트로 구성되고, 해당 레지스터 3개를 모두 합하면 64비트가 되도록 설계되었다.

 

키는 이에 맞추어 64비트를 사용하는데, 해당 키가 3개의 레지스터의 초기 값으로 채워지고 나면, 스트림 암호의 본래 목적인 키스트림을 연속적으로 생성할 준비가 완료된다. 키스트림이 연속적으로 생성되는 원리를 알아보기 위해 먼저 레지스터 X, Y, Z에서 어떠한 연산이 일어나는지를 확인하면 다음과 같다.

 

X 레지스터 단계

1. $ t \ = \ x_{13} \ \oplus \ x_{16} \ \oplus \ x_{17} \ \oplus \ x_{18} $
2. $ x_{i} \ = \ x_{i-1} $ ($ i = 18,\ 17,\ 16,\ ... \ ,\ 1 $)
3. $ x_{0} \ = \ t $

Y 레지스터 단계

1. $ t \ = \ y_{20} \ \oplus \ y_{21} $
2. $ y_{i} \ = \ y_{i-1} $ ($ i = 21,\ 20,\ 19,\ ... \ ,\ 1 $)
3. $ y_{0} \ = \ t $

Z 레지스터 단계

1. $ t \ = \ x_{7} \ \oplus \ x_{20} \ \oplus \ x_{21} \ \oplus \ x_{22} $
2. $ z_{i} \ = \ z_{i-1} $ ($ i = 22,\ 21,\ 20,\ ... \ ,\ 1 $)
3. $ z_{0} \ = \ t $

이때 각각의 클록 펄스에서 산출되는 값은 다음과 같다. $ m \ = \ maj(x_{8}, \ y_{10}, \ z_{10}) $

여기서 maj(x, y, z)함수의 경우 x, y, z의 비트 중 과반수 이상인 값을 결과로 반환하는 함수이다. (다수결 기능)

 

X, Y, Z 레지스터는 다음 규칙에 따라 진행된다.

$ x_{8} \ = \ m $이면, X 레지스터 단계를 수행
$ y_{10} \ = \ m $이면, Y 레지스터 단계를 수행
$ z_{10} \ = \ m $이면, Z 레지스터 단계를 수행

이후 키스트림 $s$는 다음과 같이 만들어진다. $ s \ = \ x_{18} \ \oplus \ y_{21} \ \oplus \ z_{22} $

 

이는 한 번에 이해하기에는 많이 복잡해 보인다. 따라서 아래의 유튜브 영상을 참고하는 게 좋을 듯하다.

RC4

RC4도 스트림 암호의 한 종류로, A5/1과는 달리 소프트웨어로 구현되도록 설계되어 있다.

RC4의 알고리즘은 아직 완벽하게 공부하지 못했으므로, 이후에 내용을 정리하여 여기에 추가하도록 하겠다.

---

블록 암호

블록 암호는 스트림 암호와 같은 대칭키 암호방식 중 하나로, 점점 사라지는 스트림 암호와는 달리 현재 가장 많이 쓰이고 있는 대칭키 암호방식이다. 블록 암호는 평문을 일정한 크기의 블록으로 나누어 암호문을 생산하는데, 여러 번의 회전에 걸쳐 함수를 반복 수행하는 방식을 사용한다. 이때 각 블록의 크기는 완전히 동일해야 하므로, 데이터 끝 부분에는 의미 없는 데이터를 넣어서라도 각 블록의 크기를 동일하게 유지해야 한다. (이를 패딩이라고 한다.)

 

이러한 블록 암호의 종류는 여러 가지가 있는데, 대표적으로 DES, 3DES, AES가 있다. 각각의 암호 체계에 대해 알아보기 전에 먼저 블록 암호에 공통적으로 적용될 수 있는 암호 설계 원리를 먼저 알아보도록 한다.

페이스텔 암호

블록 암호의 선구자인 호스트 페이스텔의 이름을 이용해 명명한 페이스텔 암호는, 특정한 암호체계를 지칭하는 것이 아니라 일반적인 암호의 설계 원리를 의미한다. 실제 DES, 3DES와 같은 암호 체계의 경우 이런 페이스텔 암호방식을 사용하였다.

 

페이스텔 암호에서는 먼저 평문 P를 왼쪽과 오른쪽으로 반반씩 나눈다. $ P \ = \ (L_{0}, \ R_{0}) $

그리고 회전을 반복하게 되는데, 각 $i$번째 회전에서 좌측과 우측으로 나뉜 부분은 다음과 같은 규칙에 따라 계산된다.

$ L_{i} \ = \ R_{i-1} $
$ R_{i} \ = \ L_{i-1} \ \oplus \ F(R_{i-1}, \ K_{i} ) $

이때 $F$는 각 회전마다 사용되는 함수인 회전 함수를 의미하고, $K_{i}$는 $i$번째 회전에 사용되는 보조키를 의미한다. 이후 최종으로 암호문 $C$는 n번의 반복 후에 나온 좌측 부분과 우측 부분을 합해 만들어진다.

 

페이스텔 암호의 가장 큰 장점은 특정한 회전 함수 $F$에 무관하게 복호화가 가능하다는 것이다. 실제 페이스텔 암호의 복호화는 암호화의 역순으로 다음과 같은 규칙을 가진다.

$ R_{i-1} \ = \ L_{i} $
$ L_{i-1} \ = \ R_{i} \ \oplus \ F(R_{i-1}, \ K_{i}) $

이후 최종 결과로 나오는 평문 $P$는 $ P \ = \ (L_{0}, \ R_{0}) $이다.

 

물론 가능한 모든 회전 함수 $F$를 사용할 수 있다는 말이, 모든 회전 함수에 대해 안전하다는 것은 아니다. 회전 함수에 따라 암호의 안전성이 달라지게 되는데, 이러한 이유로 페이스텔 암호를 사용하는 암호체계에서는 회전 함수를 분석하는 데에 초점을 맞춘다.

---

블록 암호 - DES

DES란 Data Encyption Standard의 줄임말로 데이터 암호화 표준이라는 뜻이다. 이는 1970년대 후반에 개발된 암호체계로 굉장히 단순한 형태의 블록 암호이지만, 그에 비해 강력한 암호 안전성을 가지고 있다. 물론 이후 DES에 대한 공격 방법이 밝혀지긴 했지만, 그럼에도 해당 암호체계에 대해 공부하고 이해하는 것은 다른 암호체계를 공부함에 있어 도움이 될 것이다.

 

DES는 크게 다음과 같은 특징을 가진다.

• DES는 16개의 회전을 갖는 페이스텔 암호 형식이다.
• DES는 64비트의 블록 길이를 가진다.
• DES는 56비트의 키를 사용한다. (64비트 중 8비트 버림)
• DES의 각 회전은 48비트의 보조키를 사용한다. (56비트의 키에서 보조키 48비트를 구성해 사용)

One round of DES

먼저 DES의 블록 크기는 64비트 이므로, $L_{i}$와 $R_{i}$는 각각 32비트가 된다. $R_{i-1}$의 경우 아무런 작업 없이 그대로 $L_{i}$가 되는 것을 확인할 수 있다. 하지만 $L_{i-1}$의 경우 회전 함수의 영향을 받아 $R_{i}$가 된다.

 

이때 DES의 회전 함수 $F$는 다음 식과 같이 표현할 수 있다.

$ F(R_{i-1}, \ K_{i}) \ = \ Pbox(Sboxes(Expand(R_{i-1}) \ \oplus \ K_{i})) $

이를 글로 풀어서 설명하면 다음과 같은 순서로 진행된다.

1. 32비트의 $R_{i-1}$이 확장 함수를 거쳐 48비트로 확장된다.
2. 48비트로 확장된 $R_{i-1}$과 같은 48비트의 $K_{i}$보조키와 $ \oplus $(XOR)연산을 진행한다.
3. 이를 Sboxes에 넣는다.
4. 3의 결과를 Pbox에 넣는다.

이후 만들어진 회전 함수의 결과물을 $L_{i-1}$과 XOR연산을 진행하여 $R_{i}$를 만들어낸다.

페이스텔 암호에서 $ R_{i} \ = \ L_{i-1} \ \oplus \ F(R_{i-1}, \ K_{i} ) $이기 때문이다.

확장 순열

먼저 32비트의 $R_{i-1}$이 확장 함수를 거쳐 48비트가 되는 과정을 확인해 본다. 해당 확장 방식은 확장 순열을 이용하는데, DES 확장 순열의 48비트 결과는 아래와 같다.

31	0	1	2	3	4	3	4	5	6	7	8
7	8	9	10	11	12	11	12	13	14	15	16
15	16	17	18	19	20	19	20	21	22	23	24
23	24	25	26	27	28	27	28	29	30	31	0

이는 0부터 31까지의 순서를 가지고 있는 32비트를 위의 순서에 맞춰서 재배치시키라는 뜻이다. 중간중간 몇몇 비트는 중복으로 사용되기도 하면서 32비트를 48비트로 변환하는 것이다.

보조키 생성

DES에서는 각 회전마다 서로 다른 키를 사용하기 때문에, 처음 넣어준 키를 이용하여 보조키 $K_{i}$를 생성하는 과정이 필요하다. 이때 보조키는 다음의 과정을 통해 생성된다. (56비트의 DES키를 가지고 시작한다고 가정)

 

먼저 56비트의 DES키를 왼쪽(LK)과 오른쪽(RK)으로 분리하는 작업이 필요하다. 56비트의 키가 0부터 시작하여 55까지의 순서를 가진다고 한다면, LK와 RK는 각 순서에 따라 다음과 같은 순열로 나눌 수 있다.

 

LK 키 비트

49	42	35	28	21	14	7
0	50	43	36	29	22	15
8	1	51	44	37	30	23
16	9	2	52	45	38	31

RK 키 비트

55	48	41	34	27	20	13
6	54	47	40	33	26	19
12	5	53	46	39	32	25
18	11	4	24	17	10	3

이후 56비트의 키가 LK와 RK로 나뉘었다면, 각 LK와 RK에 좌측으로 시프트 연산을 진행한다.

이때 얼마만큼 시프트를 진행할지는 회전수 $i$에 대한 아래의 표를 참고한다.

$i$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$r_{i}$	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

간단히 말해 회전이 1, 2, 9, 16일 때는 왼쪽으로 1비트 시프트, 그 외에는 2비트 시프트 연산을 진행한다.

 

이렇게 시프트 연산이 끝났다면, 이를 이용해 48비트의 보조키를 생성한다. 이때 각 LK와 RK를 이용해 보조키를 생성하는 방식은 아래의 순열에 따라 결정된다.

 

순열 LP (LK 키 비트에 적용)

13	16	10	23	0	4	2	27	14	5	20	9
22	18	11	3	25	7	15	6	26	19	12	1

순열 RP (RK 키 비트에 적용)

12	23	2	8	18	26	1	11	22	16	4	19
15	20	10	27	5	24	17	13	21	7	0	3

시프트가 끝난 LK와 RK는 각각 28비트로 이루어져 있는데, 이를 다시 0부터 시작하여 27로 순서를 차례대로 정한다. 그리고 위의 순열 표에 맞추어 순서를 재 정렬하며 각각 24비트의 결과물이 만들어진다.

 

28비트의 LK와 RK가 각각 24비트의 결과물이 되어, 결과적으로 56비트의 DES키가 48비트의 보조키로 변하게 된 것이 된다. 즉, 보조키 $K_{i}$의 좌측 반은 LK의 LP비트로 구성되어 있고, 우측 반은 RK의 RP비트로 구성된 셈이다.

보조키 생성

만약 두 번째 회전이라면, 첫 번째 회전에서 시프트 연산이 적용된 LK 키 비트와 RK 키 비트로 만들어진 키를 사용한다. 즉, 첫 번째 연산에서 순열 LP와 RP를 적용하여 56비트를 48비트로 압축하기 직전의 바로 그 56비트를 두 번째 연산의 시작 키로 이용하는 것이다. 해당 키를 이용하여 다시 LK와 RK로 나누고, 시프트 연산을 진행하고, 순열을 적용하는 과정을 거쳐 두 번째 보조키를 생성한다.

 

※ 추가로 인터넷에서 찾아본 여러 순열 표들이 각기 다른 값들을 가지고 있음을 확인하여 처음에는 무척이나 혼란스러웠다. 하지만 순열 표가 만들어진 기준이 64비트를 가지고 56비트를 골라내는 과정까지 포함한 순열 표도 있었고, 순열의 첫 시작을 0이 아닌 1로 시작한 표도 있었다. 따라서 이러한 사실들을 잘 고려하는 것이 필요하다. 어느 표가 틀리고 어느 표가 맞다는 것이 아니었다.

S-boxes

S박스는 DES의 회전 함수에서 사실상 가장 핵심이 되는 부분이다. 이러한 S박스는 총 8개의 박스로 구성되어 있는데, 각각의 박스는 6비트를 4비트로 매핑한다. 48비트의 보조키와 XOR연산을 마친 결과값은 그대로 48비트인데, 이를 S박스의 개수인 8개로 나누면 6비트씩 8개로 나뉘게 된다.

 

이렇게 6비트씩 나뉜 값들은 각각 8개의 S박스에 순서대로 들어가게 되고, 처음 설명한 것처럼 S박스는 들어온 6비트를 4비트로 매핑하여 내보낸다. 따라서 48비트로 들어온 값이 32비트가 되어 나가는 것이다.

 

이때 S박스는 16 × 4 크기의 표인데, 들어온 6비트의 첫 번째 비트와 마지막 비트는 행의 색인으로 사용되고, 나머지 비트는 열의 색인으로 사용된다. 다음의 표는 1번 S박스의 표이다.

1번 S박스의 표

이때 들어오는 6비트가 101101이라 가정하자. 그렇다면 첫 번째 미트와 마지막 비트인 11을 행의 색인으로 사용하여, 가장 마지막 행을 선택하고, 나머지 0110비트를 이용해 7번째 열을 선택한다. 이때 만들어지는 4비트는 바로 0001이다.

S박스를 이용하여 6비트를 4비트로 매핑

이러한 방식으로 총 8개의 S박스에 각각 6비트씩 들어가 4비트로 매핑되는 방식으로, 결과적으로 48비트가 32비트가 된다. S박스는 DES의 회전 함수 중에서 유일하게 비선형적인 부분을 가지고 있기 때문에, 보조키 생성 부분과 더불어 DES의 보안에 가장 중요한 부분으로 꼽힌다.

 

참고로 8개의 S박스의 표는 다음과 같다.

출처: http://orion.towson.edu/~mzimand/cryptostuff/DES-tables.pdf

P-box

마지막으로 S박스를 나온 32비트의 값은 P박스를 거치게 된다. P박스는 32비트를 그대로 32비트로 배출시키는데 단지 순서만을 바꾸는 데 사용된다. 따라서 보안적으로 아무런 의미가 없는 장치이다. 해당 P박스가 존재한 이유가 분명히 존재했겠지만, 현재로서는 해당 부분의 진짜 목적은 알 수가 없다. 아무튼 DES에서 P박스는 제거해도 아무런 보안적 문제가 없는 부분이라는 점만 알고 넘어가면 된다.

15	6	19	20	28	11	27	16
0	14	22	25	4	17	30	9
1	7	23	13	31	26	2	8
18	12	29	5	21	10	3	24

P박스의 순열은 다음과 같다. S박스를 거쳐 나온 32비트의 값은 0부터 시작하여 31까지의 순서를 가지고 위의 순열에 맞춰 재조립된다. 이는 단순 순서 바꾸기 이상의 의미를 가지지 않는다. 또한 해당 P박스 역시 모두에게 공개된 내용이기 때문에 보안적으로도 아무런 의미가 없다. 단지 처음 DES가 설계되었을 때 P박스가 존재했기 때문에 그대로 사용하는 것뿐이다.

---

블록 암호 - 3DES

삼중 DES(Triple DES)라고 불리는 3DES는 DES의 키 길이를 확장하는 데 사용되는 DES의 변형이다. DES는 전수키 조사보다 약간 적은 작업량을 요구하는 공격 방법이 이론적으로 계발되기도 했지만, 실질적으로는 전수키 조사가 유일한 방법이기에 큰 문제없이 작동했다. 그럼에도 56비트에 불과한 키의 길이는 비교적 짧다는 문제가 있어서 DES의 약점이라고 여겨졌다. 특히 하드웨어 성능이 점점 더 좋아짐에 따라 전수키 조사에 걸리는 시간이 점점 더 짧아져왔기 때문에, DES의 키 길이를 더 늘일 방법이 필요했다.

 

물론 DES와 동일한 구조를 가지면서 키의 길이만 늘리도록 새로운 암호체계를 설계한다면 끝날 일이긴 하다. 하지만 DES는 미국 NBS에서 국가 표준으로 정한 암호체계였기 때문에, 국가기관을 비롯해서 여러 기업들까지 널리 사용하던 암호체계였다. 따라서 최대한 기존의 DES를 활용하면서 동시에 키의 길이를 늘일 수 있는 방식이 필요했다.

이중 DES

가장 먼저 생각해 볼 수 있는 방법은 DES를 두 번 연속으로 사용하는 것이다. 그러면 연산 시간이 두 배로 걸리긴 하지만, 112비트의 키를 사용할 수 있는 좋은 방법처럼 보인다. 하지만 단일 DES를 공격하는 데에 필요한 수준의 작업으로 이중 DES를 공격할 수 있는 방법이 있기 때문에, 이중 DES는 사실상 유효하지 못한 방어법이다.

 

먼저 DES의 암호화 표기법은 $ C \ = \ E(P, \ K) $로 나타낼 수 있다. C는 암호문, P는 평문, E는 암호화를 나타낸다. 이를 이용해 이중 DES를 표기하면 $ C \ = \ E(E(P,\ K_{1}),\ K_{2}) $로 나타낼 수 있다. 해당 표기법을 이용해 이중 DES를 공격하는 방법을 설명하면 다음과 같다.

 

먼저 특정한 평문 P에 대한 암호문을 획득하는 공격을 수행한다. 가능한 모든 키값을 이용해 평문 $P$를 모두 암호화하여 각 $K$에 해당하는 $ E(P, \ K) $를 $2^{56}$크기의 표로 미리 계산한다. 이때 미리 수행하는 해당 계산은 단일 DES에 대한 전수키 조사와 동일한 연산이다.

이후 최종적으로 얻고자 하는 암호문 $C$와 랜덤 한 키 $\tilde{K}$를 이용해 미리 만들어 둔 표에 내용과 동일한 값이 나올 때까지 C를 복호화한다. 이는 다음의 수식으로 표현할 수 있다.

$$D(C,\ \tilde{K} ) \ = \ E(P, \ K)$$

 

해당 식이 실제로 옳은지 확인해 보자. $D(C,\ \tilde{K} ) \ = \ E(P, \ K)$의 식 양변을 $\tilde{K}$로 암호화해 보면 다음과 같은 식을 확인할 수 있다.

$$ C \ = \ E(E(P, \ K), \ \tilde{K} ) $$

 

즉, 처음에 이중 DES를 나타내기 위한 식인 $ C \ = \ E(E(P,\ K_{1}),\ K_{2}) $와 비교해 본다면,

$K_{1} \ = \ K$, $K_{2} \ = \ \tilde{K}$가 된다.

 

물론 해당 공격을 실행하기 위해서는 초기에 $2^{56}$에 해당하는 거대한 표를 미리 계산하고 저장해야 한다는 문제가 있다. 하지만 단 한 번만 표를 만들어두기만 한다면, 이후로 이중 DES를 공격할 때마다 사용할 수 있을 것이다. 따라서 실질적인 연산 수는 단일 DES를 공격할 때와 마찬가지로 하나의 키만 찾으면 된다.

 

이러한 문제로 이중 DES는 단일 DES와 보안성에서 큰 차이가 없다고 볼 수 있다. (단일 DES의 짧은 키 문제를 해결할 수 없다.)

삼중 DES

따라서 사용되는 방식이 바로 삼중 DES인 3DES 방식이다. DES를 두 번 실행하는 이중 DES가 안전하지 않다는 것이 밝혀졌는데, 과연 DES를 세 번 실행하는 삼중 DES는 안전하다고 할 수 있을까?

 

3DES에서는 이중 DES의 공격 방법과 유사한 중간만남 공격(meet-in-the-middle attack)을 실행하기가 쉽지 않고, 매 공격 때마다 수행해야 하는 작업령이 실행 불가능한 수준이기 때문에 적어도 3DES는 안전하다고 할 수 있다.

 

이때 $C=E(E(E(P,K_{1}),K_{2}),K_{3})$가 물론 적절한 방법이긴 하지만, 실제 3DES에서는 $C=E(D(E(P,K_{1}),K_{2}),K_{1})$ 방식을 사용한다. 이는 기존에 사용하던 단순 DES와의 호환성을 위한 것이다. 3DES에서는 암호화-복호화-암호화 방식을 사용하기 때문에 키는 2개가 필요하다. 이때 2개의 키가 같다면, 단순 DES와 사실상 완전히 같아지기 때문에 반드시 서로 다른 키를 사용해야 한다.

---

블록 암호 - AES

AES는 Advanced Encryption Standard의 줄임말로, 1990년대 초반 미 국가표준기술국(NIST)에서 DES를 대체하기 위해 채택한 새로운 암호체계이다. DES와 마찬가지로 AES 역시 블록 암호의 한 종류이지만, AES의 알고리즘은 페이스텔 암호의 형식이 아니다. 즉, 복호화를 진행하기 위해서 고난도의 수학적 구조를 가지고 있는 형태이기 때문에, 해당 암호체계를 깊고 자세하게 알기는 무척이나 까다롭다.

 

그럼에도 최대한 간단하게 AES에 대해 알아보자면, AES는 다음과 같은 특징을 가진다.

• 128비트, 192비트, 256비트 세 가지 블록 크기가 가능하다.
• 블록의 크기에 상관없이 128비트, 192비트, 256비트 세 가지 키 길이가 가능하다.
• 회전의 수는 키 길이에 따라 10에서 14까지 변화된다.
• 한 블록을 바이트 단위의 행렬로 간주한다. (예를 들어 192비트의 경우 4 × 6 바이트의 행렬)
• 각 회전은 4개의 함수로 구성된다.

Function	Layer	Description
ByteSub	비선형층	DES의 S박스에 해당하는 함수로, 바이트 단위의 행렬로 구성된 블록을 검색표를 이용하여 새로운 바이트 단위의 행렬로 치환한다.
ShiftRow	선형혼합층	행렬의 한 행에서 바이트 단위로 시프트 연산을 수행한다.
MixColumn	비선형층	행열의 한 열에서 바이트 단위로 자리바꿈이 수행된다. 이때의 연산은 시프트 연산과 XOR 연산으로 구성된다. ByteSub처럼 DES의 S박스와 유사한 목적으로 사용된다.
AddRoundKey	키추가층	DES와 유사하게 키 스케줄 알고리즘이 각 회전마다 보조키를 생성하기 위해 사용된다. 이때의 연산은 XOR 연산을 이용한다.

이때 사용되는 4개의 함수는 모두 역함수가 존재한다. 따라서 전체 알고리즘의 역이 성립되고, 이를 토대로 복호화가 가능하다.

---

블록 암호 모드

블록 암호의 경우 암호화할 평문의 길이가 어떻든 간에 일정한 크기의 블록으로 그 크기를 나누어서 처리하는 방식을 사용한다. 이때 보통 암호화하려는 데이터의 경우 블록의 길이보다 큰 크기를 가지고 있기에, 여러 개로 나뉜 각 블록들을 여러 번에 걸쳐 암호화를 진행하는 경우가 대부분이다.

 

블록 암호를 딱 한 블록만 암호화를 하는 경우에는 큰 문제가 없다. 하지만 같은 암호 방식을 이용해서 여러 블록들을 반복해서 암호화하게 되면, 여러 가지 문제가 생길 수 있다.

 

예를 들어 평문을 블록 단위로 나눴는데, 특정 블록 몇 개가 완전히 동일한 경우가 있을 수 있다. 그렇다면 당연히 이를 암호화한 부분 역시 서로 동일할 것이다. 따라서 공격자가 $C_{i} = C_{j}$인 블록을 서로 발견한다면, 해당 암호 블록을 복호화한 평문 역시 $P_{i} = P_{j}$임을 알 수 있다. 만약 $P_{i}$나 $P_{j}$의 값을 공격자가 이미 알고 있다면, 나머지 하나의 값도 자연스럽게 알 수 있게 된다. 설령 $P_{i}$나 $P_{j}$ 값을 공격자가 모르는 상태라고 해도, 두 블록이 서로 같은 내용이라는 정보가 노출되는 것은 결코 좋은 일이 아니다.

 

물론 일반적인 문자열 형태의 데이터의 경우 같은 크기로 나눈 블록이 서로 같은 값을 가질 경우가 적긴 하다. 하지만 그렇다고 해서 위와 같은 문제를 무시할 수 있는 것은 아니다. 아래와 같이 이미지 형태의 데이터를 암호화한다고 가정하자. 이때 기존의 블록 암호 방식으로 이미지를 암호화한다면 다음과 같은 결과를 가져오게 된다.

기존의 블록 암호 방식으로 이미지를 암호화

이러한 흑백 이미지에서는 하얀 부분과 검은 부분 등 서로 같은 데이터 값을 가지는 블록이 반복되는 경우가 많기 때문에, 암호화를 하더라도 이러한 특정 패턴이 나타날 수 있는 것이다.

 

따라서 블록 암호 방식에서는 여러 모드를 이용해서 이러한 문제를 해결하고자 한다.

ECB모드

먼저 가장 기본적인 모드인 ECB모드에 대해서 알아보자.

 

ECB(Electronic Code Block)모드는 가장 단순한 모드로, 이전에 설명했던 "기존의 블록 암호 방식"에 해당하는 모드이다. 따라서 위에서 보여준 흑백 이미지의 암호화와 같은 특수한 경우에 암호화가 제대로 진행되지 않고, 특정한 패턴이 반복적으로 나타날 수 있다.

CBC모드

따라서 이러한 ECB모드가 가지고 있는 약점을 보완하기 위해 보통 암호블록 연결 모드인 CBC(Cipher Block Chaning)모드를 사용한다.

 

CBC모드는 그 이름에서 알 수 있듯이 암호화된 블록들을 체인처럼 쭉 연결해서 사용하는 방식이다. 해당 모드에서는 한 블록에서 만들어진 암호문이 다음 블록의 평문이 암호화되기 전에 이 평문을 모호하게 만든다. 이러한 과정을 암호화 공식으로 표현하면 다음과 같다.

 

먼저 CBC모드의 암호화 공식이다.

$$ C_{i} = E(P_{i} \oplus C_{i-1}, K) $$

 

이를 잘 살펴보면 i번째의 블록을 암호화하기 전에, 평문 상태인 i번째 블록과 직전에 암호화 한 암호화 블록을 서로 XOR연산하는 것을 확인할 수 있다. 그리고 이 이후에 키 K를 이용하여 암호화를 진행한다.

 

즉, CBC모드에서 암호화를 진행하기 위해서는 이전의 블록을 먼저 필수적으로 암호화 한 다음, 그 암호화된 블록을 함께 사용하여야 한다.

 

그런데 가장 첫 블록의 경우는 이전의 암호문 블록이 없는데 어떻게 해야 하는 걸까?

이를 위해 초기화 벡터(IV)가 존재한다. IV는 암호문 블록의 역할을 수행하기 때문에 굳이 비밀일 필요는 없다. 하지만 반드시 임의로 선택되어야 한다.

 

그리고 복호화 공식은 다음과 같다.

$$ P_{i} = D(C_{i} , K) \oplus C_{i-1} $$

 

복호화는 암호화를 수학적으로 반대로 한 것이다.

 

먼저 기존의 암호를 복호화하듯이 키 K를 이용해 암호문을 풀어낸다. 하지만 암호문을 풀어도 읽을 수 없는 상태의 평문이 나온다. CBC모드는 암호화를 하기 전 먼저 이전에 암호화된 블록을 이용해 평문을 모호하게 만들기 때문이다.

 

따라서 이전에 암호화 블록을 가지고 이 평문에 XOR연산을 다시 진행하면, 원래 얻고자 하는 읽을 수 있는 상태의 평문을 얻을 수 있을 것이다.

 

또한 암호화와 마찬가지로, 가장 첫 번째 블록의 복호화를 진행할 때에는 암호화된 이전 블록이 없으므로, 초기화 벡터(IV)를 대신 사용하면 된다.

 

이러한 방식을 사용하는 CBC모드의 장점은 동일한 평문이라도 동일한 암호문을 생산하지 않는다는 것이다. 실제로 CBC모드를 이용하여 이전에 보여주었던 앨리스 이미지를 암호화하면 다음과 같은 결과를 얻을 수 있다.

CBC모드로 이미지를 암호화

ECB모드와는 달리 반복되는 패턴이 존재하지 않고, 그 형태를 완전히 알아볼 수 없게끔 제대로 암호화된 것을 확인할 수 있다. 실제로 이러한 보안성의 이유로 ECB모드에 비해 CBC모드가 더 많이 사용된다.

CBC모드의 오류 전파

물론 CBC모드가 ECB모드에 비해 보안적으로 더 뛰어나다는 것은 극명한 사실이다. 하지만 그럼에도 우려해야 할 사실이 있는데, 바로 오류들의 영향이다.

 

암호문이 무선이든 유선이든 어떠한 방식으로 전파되든 간에, 전송되는 동안 오류가 발생할 수도 있는 일이다. 0이 1이 될 수도 있고, 그 반대가 될 수도 있다. 중요한 것은 CBC모드는 각 블록이 서로 연결되어 있기 때문에 하나의 블록에서 생긴 미세한 오류가 전체 암호문에 영향을 끼칠 수 있는 문제가 생길 수 있다.

 

하지만 다행히도 이러한 오류는 두 개 블록까지만 영향을 끼치고, 그 이후의 블록에는 영향을 끼치지 않는다. 단순하게 생각했을 때에는 모든 블록에 영향을 끼칠 것 같지만, 조금만 곰곰이 생각해 보면 이러한 문제가 왜 생기지 않는지 알 수 있을 것이다.

 

예를 들어 i번째 암호문 블록에 오류가 발생했다고 가정하자. 그렇다면 i번째 평문 블록부터 시작해서 어디까지 오류가 퍼지게 될까?

 

먼저 i번째 평문 블록의 경우 당연히 암호 블록의 오류로 인해 제대로 복호화되지 못할 것이다. 오류가 난 블록인 $C_{i}$가 복호화 식에 존재하기 때문이다.

$$ P_{i} \neq D(C_{i}, K) \oplus C_{i-1} $$

 

그리고 그다음인 i+1번째 평문 블록의 경우에도 다음과 같이 제대로 복호화되지 못할 것이다. 여전히 오류가 난 블록인 $C_{i}$가 복호화 식에 존재하기 때문이다.

$$ P_{i+1} \neq D(C_{i+1}, K) \oplus C_{i}$$

 

하지만 그다음 블록부터는 오류가 전파되지 않는다.

$$ P_{i+2} = D(C_{i+2}, K) \oplus C_{i+1}$$

 

오류가 일어난 블록은 $C_{i}$이고, 해당 오류는 2개의 블록을 뛰어넘게 되면 더 이상 복호화 식에서 사용되지 않기 때문이다.

 

따라서 CBC모드에서 오류가 일어날 수는 있지만, 이 영향이 전체 블록에 영향을 끼치지는 않기 때문에 우리는 해당 모드를 암호화 방식으로 사용할 수 있다. 하지만 실시간 무선 통신과 같은 오류율이 높은 환경에서는 차라리 스트림암호를 사용하는 것이 좋을 수도 있다.

---

무결성

비밀성이 보호할 데이터에 대해 비인가자가 읽는 행위를 방지하는 것이라면, 무결정은 비인가자가 보호할 데이터를 고쳐 쓰는 행위를 방지하는 것이다. 더 정확히 말하자면 누군가가 기존의 데이터를 변조했다면 이를 즉시 알아챌 수 있는 것이 바로 무결성이다.

 

지금까지 비밀성을 위해 스트림암호부터 시작해서 블록암호까지 사용하는 방법을 간단하게 알아보았다. 여기서 데이터의 무결성을 위해서도 블록암호를 사용할 수 있는데, 어떠한 방식으로 가능한지를 알아보자.

MAC

메시지 인증 코드라 불리는 MAC(Message Authentication Code)은 데이터의 무결성을 보장하기 위한 코드이다. 이 MAC은 다른 복잡한 새로운 방식을 사용하는 것이 아니다. 바로 기존의 블록암호 방식을 사용하는데, 데이터를 CBC모드로 암호화 한 다음 생성되는 가장 마지막 블록을 MAC으로 사용하는 것이다.

 

예를 들어 N개의 블록으로 이루어진 데이터에서 MAC을 만들어내기 위해서는 다음과 같은 과정을 반복해야 한다.

$$ C_{0} = E(P_{0} \oplus IV, K), \ C_{1} = E(P_{1} \oplus C_{0}, K), \ ... \ , \ C_{N-1} = E(P_{N-1} \oplus C_{N-2}, K) = MAC $$

 

이러한 MAC을 사용하는 방법은 다음과 같다.

 

먼저 송신자는 평문을 보내면서 동시에 자신이 계산한 MAC을 함께 보낸다. 수신자는 이를 받으면 송신자와 똑같은 과정을 수행하여 MAC을 다시 계산한다. 이때 송신자가 보낸 MAC과 계산한 MAC이 다르면, 데이터가 수신되는 과정에서 변경되었음을 알 수 있다.

 

해당 방법을 사용하기 위해서는 수신자와 송신자가 모두 대칭키 K와 IV를 공유해야 한다는 사실이다. IV는 비밀로 하지 않아도 되지만, 대칭키 K는 반드시 수신자와 송신자만 알고 있어야 한다. 만약 공격자가 대칭키도 알고 있다면 변조한 데이터에 맞게 MAC도 새로 바꿔서 전송할 것이기 때문이다.

MAC의 원리

그렇다면 MAC이 무결성을 보장해 줄 수 있는 원리에 대해 알아보자.

 

먼저 앨리스가 $P_{0}$부터 $P_{3}$까지 4개의 블록으로 이루어진 평문과 이에 맞는 MAC을 밥에게 전송한다고 가정하자. 이때 중간에 공격자인 트루디가 $P_{1}$블록의 내용을 $Q$로 변경했다고 하자. 이 경우 밥이 MAC을 새로 계산하면 다음과 같다.

$$ C_{0}=E(P_{0} \oplus IV, K), \ \tilde{C_{1}} = E(Q \oplus C_{0},K), \ \tilde{C_{2}} = E(P_{2} \oplus \tilde{C_{1}}, K), \ \tilde{C_{3}} = E(P_{3} \oplus \tilde{C_{2}}, K) \neq MAC $$

 

즉, 하나의 평문의 변경이 뒤에 따라오는 모든 블록에 전파되어 MAC의 계산에 영향을 주었다. 분명 CBC모드에서 오류의 전파는 두 블록 이상 퍼지지 않는다고 했는데, 이게 어떻게 된 일일까?

 

이에 대해 더 명확하게 설명하자면, CBC모드에서 오류가 전파되지 않는 경우는 암호문에 오류가 생기고, 이를 복호화하는 경우에 오류가 두 블록 이상 전파되지 않는다는 것이었다.

 

반면 지금과 같이 평문이 변경되었는데 이를 암호화하는 경우에는, 평문 하나의 변경이 뒤에 따라오는 모든 블록에 영향을 끼친다. 따라서 중간에 메시지 하나라도 변경하게 된다면 MAC이 즉시 변하기 때문에 무결성을 보장할 수 있다.