-
네트워크 보안 - 2 | 고전 암호컴퓨터 공학/보안 2022. 9. 24. 17:53
암호학(Cryptology)
이전 포스트에서 정보보안의 3가지 요소인 CIA를 소개했었다. 이때 기밀성(Confidentiality)과 무결성(Integrity)의 경우, 암호화를 통해 그 목적을 달성할 수 있었다.
따라서 보안을 위해서라면 암호학을 공부하게 되는 것은 사실상 필수적인 과정이라 할 수 있을 것이다.
다만, 실제 현대 암호학의 경우 복잡한 수학적인 이론이 동반되는 경우가 많기 때문에, 단순 네트워크 보안을 위해 암호학을 공부하려는 사람들에게는 너무 깊이 들어가는 것이 너무 어렵고, 비효율적일 수 있다.
이러한 이유로 먼저 깊은 수학적인 지식이 없어도 직관적으로 이해 가능한 고전 암호에 대해 먼저 살펴본 다음, 현대에서 실제 사용하고 있는 암호화 방법에 대해 알아보도록 한다.
암호의 개본 개념
암호 또는 암호체계는 데이터를 암호화하는 데 사용한다. 여기서 암호화를 한다는 뜻은 원본 데이터를 알아보지 못하게끔 변형한다는 뜻으로 생각하면 된다. 하지만 아무런 규칙도 없이 그냥 마구잡이로 데이터를 변형하는 것은, 사실상 정보를 갈가리 찢어버리는 것과도 같다. 정작 필요한 사람도 알아보지 못한다면 그게 무엇이 의미가 있겠는가.
따라서 암호체계에는 암호문을 원래의 평문으로 복원할 수 있는 방법이 존재해야 한다. (물론 복원 자체를 고려하지 않는 경우도 존재한다. 다만, 이 경우에도 정해진 규칙으로 평문이 암호문으로 암호화되어야만 한다.) 이때 이렇게 암호문을 평문으로 복원하는 과정을 '복호화'라고 하고, 이러한 복호화 과정에 필요한 요소를 '키'라고 한다.
하나의 열쇠를 이용해 자물쇠를 잠그고 다시 풀고를 반복할 수 있는 것처럼, 암호화와 복호화 역시 비슷한 과정을 가진다. 평문을 하나의 키를 이용해 암호화를 진행했다면, 이 키를 잘 간직하고 있다가 나중에 복호화에 그대로 사용하면, 암호문이 평문으로 다시 복원되는 것이다.
이렇게 하나의 키를 이용해 암호화와 복호화를 진행하는 암호체계를 대칭키 방식(symmetric key)이라 한다. 반면 암호화와 복호화에 서로 다른 키를 사용하는 방식을 공개키 방식(public key)이라 한다. 이번 포스트에서 알아볼 고전 암호의 경우 모두 대칭키 방식이다.
어쨌든 모든 암호체계의 목표는 정해진 키 이외의 방법으로는 복호화할 수 있는 방법이 없도록 하는 것이다. 공격자가 암호를 만들기 위해 사용된 암호 알고리즘을 완벽하게 알고 있다고 하더라도, 정확한 키 없이는 복호화할 수 없어야지만 안전한 암호체계라 할 수 있는 것이다. 이러한 점은 "암호체계 자체가 비밀이 되어서는 안 된다."라는 커크호프 원칙에서도 알아볼 수 있다. 아무리 신박한 암호체계를 개발했다고 하더라도, 언젠가는 공격자에게 그 알고리즘이 알려질 것이기 때문이다.
※ 만약 암호화에 키를 사용하지 않는다면, 이는 encoding과 decoding으로 부를 수 있다. 마치 ASCII코드에서 문자를 이진수 형태로, 이진수를 문자 형태로 자유롭게 변형할 수 있는 것처럼 말이다. 이는 해당 규칙을 모르는 사람에게는 난해한 암호처럼 보일 수 있지만, ASCII코드표를 가지고만 있다면 매우 쉽게 해석해 낼 수 있다.
단순 치환 암호(Simple Substitution)
여러 종류의 고전 암호 중 가장 먼저 알아볼 것은 '단순 치환 암호'이다. 이는 2000년 이상된 정말 오래된 암호체계로, 매우 단순한 방식으로 데이터를 암호화한다.
해당 암호체계는 현재 문자를 n번째 앞에 있는 문자와 서로 치환해 암호화하는 방식을 사용한다. 이를 보기 쉽게 표로 나타내면 다음과 같다.
n이 3일때의 단순치환 암호표 이때 첫째줄의 소문자가 평문에서의 알파벳이고, 둘째 줄의 대문자가 암호문이다.
이를 바탕으로 "cookiesideanote"라는 데이터를 암호화하면, "FRRNLHVLGHDQRWH"라는 암호화된 문장을 얻을 수 있을 것이다.
해당 암호문에서 키는 해당 암호표가 될 것이다. 각 알파벳에 대응하는 암호를 알 수 있다면, 암호문을 다시 평문으로 복호화할 수 있기 때문이다. 하지만 과연 공격자가 이러한 키가 없다고 해서 복호화를 하지 못할까?
너무나도 단순한 방법으로 n을 0부터 시작해서 25까지 증가시키면서 복호화를 진행해보기만 해도, 언젠가 제대로 복호화된 문장이 만들어질 것이다. 그리고 이러한 과정이 딱히 그렇게까지 어려운 일도 아니다. 컴퓨터가 계산을 즉각적으로 해주는 현대에는 말할 것도 없고, 과거에도 사람이 수작업으로 몇 번 해본다고 해서 그리 시간이 걸리진 않았을 것이다.
즉, 해당 암호체계의 가장 큰 문제는 가능한 키의 수가 너무 적다는 것에 있다. 0부터 25까지만 한 번씩 해보면 모든 키에 대한 조사를 끝낼 수 있는데, 이를 '전수키 조사'라 한다. 이렇듯 전수키 조사에 필요한 시간이 지나치게 짧다면, 그 암호체계는 안전하지 못하다고 할 수 있다.
순열을 이용한 방식
사실 단순 치환 암호방식을 n만큼 이동하는 방법으로 한정할 필요는 전혀 없다. 그냥 아무런 연관 없이 알파벳을 섞어버려도 단순 치환 암호가 가능하다. 이를 복호화할 키로는 암호문으로 사용된 알파벳의 순서를 기록한 순열을 사용할 수 있다. 아래와 같은 표만 있다면, 언제든 복호화할 수 있는 것이다.
무작위로 섞어 서로 매칭한 암호표 실제로 위의 표를 바탕으로 "cookiesideanote"를 암호화하면, "MVVQHGFHZGWOVXG"라는 암호문을 얻을 수 있다. 이처럼 해당 암호체계는 원리 자체는 단순 치환 암호방식의 범주에 존재한다. 하지만 이전과 다른 점이 있다면, 키의 값이 매우 커졌다는 것이다.
이전에 n만큼 알파벳을 이동시키는 방식에서는 가능한 키의 수가 26개밖에 되지 않았다. 하지만 순열을 사용한 경우 가능한 키의 수는 26!, 약 2⁸⁸만큼의 키를 가질 수 있다. 즉, 전수키 조사를 하기 위해서는 엄청난 시간이 걸린다는 뜻이다.
실제로 이는 초당 2⁴⁰개의 키를 테스트할 수 있는 컴퓨터를 사용한다고 하더라도 890만 년이 걸리는 시간이다. 확률적으로 바른 키를 찾는데 절반의 시간이 걸린다고 하더라도 495만 년이 걸린다. 따라서 해당 방식의 전수키 조사는 현대의 기술로도 불가능에 가깝다고 할 수 있다.
그렇다면 이러한 순열을 이용한 암호체계가 안전하다는 것을 의미하는가? 물론 그렇지 않다.
다음은 그 이유에 대해 설명한다.
단순 치환 방식에 대한 암호분석
실제 공격자가 해당 암호문을 복호화하기 위해서 전수키 조사를 하는 것은 현실적으로 불가능하다. 따라서 다른 지름길과 같은 방식(shortcut)을 찾을 것이다. 그리고 실제 단순 치환 암호의 경우 언어의 통계적인 특성을 이용해 빠르게 복호화할 수 있다.
다음은 영어 알파벳을 얼마나 자주 쓰이는지 그 빈도수에 따라 그래프를 그린 것이다.
평문 영어 문자 빈도수 그래프 그리고 이와 똑같은 방식으로 복호화하고자 하는 암호문에서 사용된 알파벳의 빈도수 또한 그래프로 그린다. 그렇다면 통계적으로 암호문의 그래프와 평문의 그래프에서 빈도수가 높은 부분들은 서로 겹칠 확률이 높다.
즉, 암호문에서 K란 단어가 유별나게 많이 나오는 것을 확인한다면, 이를 평문에서 E라고 예상할 수 있는 것이다. 물론 이는 통계적인 특성이므로 아닐 수 있다. 하지만 아니라면 그다음으로 많이 나오는 알파벳으로 예상을 다시 해 보면 될 뿐이다. 어찌 됐든 전수키 조사에 걸리는 500만 년보다는 훨씬 짧게 복호화를 할 수 있을 것이다.
또한 각 문장마다 가장 처음에 나오는 단어는 대부분이 'The'라든지, 단어에서 q뒤에는 u가 항상 따라온다든지와 같은 여러 가지 방법을 추가로 사용한다면, 이러한 복호화 시간은 훨씬 더 짧게 걸릴 것이다.
따라서 단순히 전수키 조사에 걸리는 시간이 매우 길다고 해당 암호체계가 안전하다는 것을 증명하지는 못한다. 이러한 생각지도 못한 특이한 방법으로도 암호문은 언제든 복호화될 수 있는 것이다. 즉, shortcut이 밝혀지지 않아 전수키 조사만이 유일한 방법인 암호체계만이 안전하다고 할 수 있다. 물론 이러한 암호체계 역시 언젠가 shortcut이 밝혀지게 되는 순간, 더 이상 암호로써의 역할을 하지 못하게 될 것이다. (오래 버틸수록 신뢰도가 높아지지만, 언제까지고 영원히 안전할지는 모르는 일이다.)
이중 전위 암호(Double Transposition)
이중 전위 암호는 평문의 순서를 섞어 내용을 이해할 수 없도록 만드는 방식의 암호체계이다. 이는 단순 치환 암호와 달리 평문의 문자 자체를 감추지는 않는다. 하지만 이 방식은 평문의 통계적 특성을 암호문 전체에 걸쳐 흩어지게 만들기 때문에, 이전에 언급된 평문의 통계적 정보에 의존하는 공격을 막을 수 있다.
예를 들어 "attackatdawn"이라는 평문을 이중 전위 암호를 사용하여 암호화한다고 가정하자.
먼저 암호화할 평문을 다음과 같이 3 × 4의 행렬로 정리한다.
a t t a c k a t d a w n 그리고 행과 열을 변형한다. 예를 들어 행을 (1, 2, 3) → (3, 2, 1)로, 열을 (1, 2, 3, 4) → (4, 2, 1, 3)으로 바꾼다고 하자.
그렇다면 행렬이 다음과 같이 변형된다.
n a d w t k c a a t a t 따라서 해당 방법으로 만들어진 암호문은 NADWTKCAATAT가 된다.
즉, attackatdawn을 NADWTKCAATAT로 암호화시킨 것이다.
일회성 암호(One-time Pad)
버넘 암호(Vernam cipher)라고도 불리는 일회성 암호는 그 안전성이 수학적으로 증명된 유일한 암호체계이다.
그렇다면 해당 암호를 이용한다면 절대로 공격자에 의해 복호화되지 않을 텐데, 왜 고전 암호로써 남게 된 것일까? 이는 먼저 해당 암호의 방식을 이해한 다음 알아보도록 하자.
일회성 암호체계를 단순화해서 설명하기 위해 알파벳 문자를 8개로 국한하여 사용한다고 가정하자.
알파벳 e h i k l r s t 이진수 000 001 010 011 100 101 110 111 이때 각 알파벳에 해당하는 이진수를 위의 표와 같이 할당한다. 이러한 매핑은 ASCII 코드를 사용하는 것과 유사한 방식이다. 중요한 것은 이러한 매핑 자체가 비밀이 아니라는 점이다. 해당 표에 대해서는 공격자가 알고 있어도 무방하다.
여기서 암호체계로써 역할을 하기 위해서는 반드시 키가 필요한데, 암호화의 대상이 될 메시지와 같은 길이를 가진 이진수 코드를 키로써 사용한다. (이때 만들어진 키는 위의 평문 코드표와 달리 공격자에게 알려져서는 안 된다.)
이렇게 만들어진 키를 이용해 평문과 함께 XOR 연산을 진행하는 것이 해당 암호체계의 방식이다.
예를 들어 "heilhitler"라는 문자열을 일회성 암호 방식으로 암호화한다고 하자. 먼저 위의 표를 이용해 평문을 이진수 비트열로 변환해야 한다.
001 000 010 100 001 010 111 100 000 101
다음으로 정해진 키를 이용해 암호화를 진행한다. 이때 암호화를 위해 만들어진 키가 다음과 같다고 하자.
111 101 110 101 111 100 000 101 110 000
이후 해당 두 비트열을 XOR연산을 통해 결과물을 만들어낸다.
h e i l h i t l e r 001 000 010 100 001 010 111 100 000 101 111 101 110 101 111 100 000 101 110 000 110 101 100 001 110 110 111 001 110 101 s r l h s s t h s r 이러한 방법으로 "heilhitler"를 "srlhssthsr"로 변환하였다.
이때 변형된 각 알파벳을 잘 확인해보자. 평문에서는 같은 문자였던 것이 암호문에서는 서로 다르게 암호화되고, 서로 같게 암호화된 단어도 평문에서는 서로 다른 단어를 가리키고 있다.
즉, 해당 방식을 적용한 암호문의 경우 특정한 패턴이 드러나지 않는다는 특징이 있다. 따라서 전수키 조사를 제외한 특정한 shortcut이 존재하지 않는다. 이러한 특징 때문에 일회성 암호는 증명된 가장 안전한 암호체계라고 할 수 있다.
복호화
비트 x과 y 간의 XOR연산은 x ⊕ y로 표현할 수 있다. 이때 수학적으로 x ⊕ y ⊕y = x라는 등식이 성립하기 때문에, 암호화에 사용한 y라는 키가 있다면, 이를 암호문에 한번 더 사용하여 x라는 평문을 만들어 낼 수 있다.
따라서 위의 방식을 이용하면 복호화를 간단히 진행할 수 있다.
s r l h s s t h s r 110 101 100 001 110 110 111 001 110 101 111 101 110 101 111 100 000 101 110 000 001 000 010 100 001 010 111 100 000 101 h e i l h i t l e r 문제점
지금까지 확인한 바에 의하면 일회성 암호는 그 안전성이 증명된 완벽한 암호체계이다. 키가 아무런 규칙 없이 임의로 만들어졌다면, 암호문을 탈취한 공격자는 평문의 길이 이외의 정보를 전혀 파악할 수 없다. 해당 길이를 가진 다른 평문 역시 적절한 키만 주어진다면 해당 암호문으로 암호화될 가능성이 있기 때문이다. 심지어 암호화하기 전에 임의의 문자를 평문에 추가하는 절차를 가진다면, 암호문에서 확인할 수 있는 길이조차 정보로써 의미가 없어진다. 즉, 일회성 암호 방식에 의해 생성된 암호문은 평문에 대한 어떠한 정보도 담고 있지 않으므로, 가장 안전한 암호체계라 부를 수 있는 것이다.
하지만 이러한 우수한 점에도 불구하고 일회성 암호체계에는 심각한 단점이 존재한다. 바로 키(key)가 평문의 길이와 동일해야 하며, 복호화를 위해 수신자에게 해당 키가 안전하게 전달되어야 한다는 것이다.
만약 이 키를 수신자에게 안전하게 전달할 수 있는 방법이 있다면, 굳이 암호화를 할 필요 없이 같은 방법으로 평문 자체를 전달하는 것이 낫다. 즉, 이론적으로는 완벽한 암호체계이지만 실제로 키를 전달함에 있어 문제가 있기 때문에, 해당 암호체계는 이 자체로 사용할 수가 없다.
일회성 암호라 불리는 이유
해당 암호 체계가 일회성 암호라 불리는 이유는, 같은 키를 한 번 밖에 사용할 수 없기 때문이다.
예를 들어 두 개의 평문 P₁과 P₂를 키(key) K를 이용해 암호화했다고 하자.
C₁ = P₁ ⊕ K, C₂ = P₂ ⊕ K
즉, 두 개의 평문을 같은 키 K로 암호화를 하였다. 이러한 경우 아래와 같은 방식을 사용하면 키가 사라져 버린다.
C₁ ⊕C₂ = P₁ ⊕ K ⊕ P₂ ⊕ K = P₁ ⊕ P₂
이러한 결과는 공격자가 해당 두 암호문을 비교 분석하여 평문을 예상하는 데에 도움을 줄 수 있다.
즉, shortcut이 생긴다는 것이다.
따라서 일회성 암호를 사용하기 위해서는 항상 평문과 같은 길이의 일회성 키를 매번 다르게 만들어서 사용해야 한다. 이렇게 계속 변하는 키를 수신자에게 전달하는 것은 더욱 어려운 일이기 때문에, 사실상 암호로써의 역할을 하기가 힘들다고 볼 수 있다.
코드북 암호
고전적인 코드북 암호는 특정 단어에 해당하는 코드를 수록하고 있는 사전을 사용하는 암호 체계이다.
예를 들어 아래와 같은 코드북이 있다고 가정하자.
평문 암호문 Hello 13605 I'm 17165 Cookie 19642 이를 이용해 Hello I'm Cookie를 암호화한다면, 13605 17165 19642로 암호화할 수 있다.
해당 방식에서는 위와 같은 코드북 자체가 키라고 할 수 있다.
순열을 추가하는 방식
또는 이러한 코드북 암호에 순열을 적용하여 단어의 순서를 섞는 방법을 함께 사용할 수도 있다.
만약 [9, 3, 6, 1, 10, 5, 2, 7, 4, 8]와 같은 순열이 적용된 암호문이 다음과 같다고 하자.
Warsaw they read all unchanged last are idiots can't situation
이를 해당 순열을 이용해 순서를 다시 재조립하면 다음과 같다.
Can't read last warsaw. Situation unchanged. They are all idiots.
그리고 여기에 추가로 코드북을 이용해 대응되는 암호문을 평문으로 변환해야 한다.
평문 암호문 telegram warsaw 위의 예시에서는 간단하게 코드북 암호를 하나만 사용하였다.
해당 코드북을 이용해 단어까지 복호화하면 다음과 같다.
Can't read last telegram. Situation unchanged. They are all idiots.
암호체계 설계의 두 가지 기본 원칙
물론 위의 암호체계는 매우 간단한 방식인 만큼 취약한 암호체계에 해당한다. 하지만 그럼에도 이렇게 소개하는 이유는 암호체계 설계의 두 가지 기본 원칙인 혼돈(confusion)과 확산(diffusion)을 잘 설명할 수 있기 때문이다.
암호체계에서 혼돈은 평문과 암호문과의 상관관계를 숨기는 것이고, 확산은 평문의 통계적 성격을 암호문 전반에 확산시키는 것을 의미한다. 즉, 지금까지 살펴본 고전 암호 중 단순 치환 암호나 일회성 암호의 경우 혼돈 특성만을 가진다고 할 수 있고, 이중 전위 암호는 확산의 특성만을 가진다고 할 수 있다
마지막으로 방금 살펴본 순열을 섞은 코드북 암호의 경우 이러한 혼돈과 확산의 특성이 모두 섞인 암호체계라고 볼 수 있다. 여기서 순서를 섞은 것은 확산 특성에 해당하고, 코드북 방식을 사용한 것은 혼돈의 특성에 해당한다.