[암호학] 3. 고전대칭 키 암호 - (1) 대칭 키 암호

CRYPTOGRAPHY

 

학습목표

이 장의 학습 목표는 다음과 같다.

• 대칭 키 암호의 개념과 용어를 정의한다.
• 고전 대칭 키 암호의 두 범주를 논의하고 암호 분석 기법을 설명한다.
• 스트림 암호와 블록 암호와 관련한 개념을 소개한다.

---

1. 대칭 키 암호

그림 1. 대칭 키 암호의 일반적인 개념

위의 그림은 대칭 키 암호에 대한 일반적인 개념을 나타낸 것이다.

이 때의 전제는, Alice는 안전하지 않은 채널(Insecure channel)을 통해 Bob에게 메시지를 보낼 수 있으며, 단, 공격자 Eve가 단순히 채널을 도청해서는 메시지의 내용을 알 수 없다.

 

Alice가 Bob에게 보내는 원래의 메시지를 평문(plaintext)이라 하고, 채널을 통해 보내는 메시지를 암호문(ciphertext)라 한다.

Alice는 암호 알고리즘(encryption algorithm)과 Bob과 공유하는 비밀 키(shared secret key)를 사용한다.

암호문으로부터 평문을 생성하기 위해 Bob은 복호 알고리즘(decryption algorithm)과 Alice와 공유하는 비밀 키를 사용한다.

암호/복호 알고리즘을 암호(cipher)라고 부른다. 또한, 키(key)는 암호가 동작하는 데 필요한 값(숫자)들의 집합을 의미한다.

 

대칭 키 암호화(symmetric-key encipherment)에서는 암·복호화 과정 모두 동일한 한 개의 키를 사용한다.

거기에, 암호 알고리즘과 복호 알고리즘은 서로 역관계이다.

만약 P가 평문, C가 암호문, K가 키라면, 암호 알고리즘 E_k($x$)와 D_k($x$)는 서로 역관계라고 가정한다.

Bob에 의해 생성된 평문이 Alice에 의해 작성된 원래의 평문과 같음을 증명할 수 있다.

Bob이 P₁ = P 임을 다음과 같이 증명한다.

 

 대칭 키 암호에서 고려해야 할 요소는 나중에 다룰 Kerckhoff 원리에 의해 암·복호 알고리즘은 공개하고 공유하는 키만 비밀로 하는 것이 낫자는 점이다.

또 다른 하나는, 키의 개수이다. Alice가 또 다른 사용자 David와 통신을 하기 위해서는 다른 비밀 키가 필요하다.

만약 m명의 사용자가 서로 통신해야 한다면, 총 $(m × (m-1))/2$개의 키가 필요하다.

 

암호화는 메시지가 들어있는 상자에 자물쇠를 채우는 것으로 비유할 수 있다.

복호화는 상자의 자물쇠를 여는 것으로 생각할 수 있다. 대칭 키 암호화에서는 다음 그림과 같이 동일한 키로 자물쇠를 채우고 연다.

 

그림 2. 동일한 키로 자물쇠를 채우고 여는 방법으로서의 대칭 키 암호화

---

1.1. Kerckhoff의 원리

Kerchhoff의 원리는 현대암호에서의 암·복호 알고리즘을 숨길 필요가 없다는 것을 말한다.지금까지 정리한 내용에 기반해보면, 암호는 암·복호 알고리즘과 비밀키에 의존하여 그 안전성을 보장한다.단점은 알고리즘이 복잡해지며 컴퓨터에서 알고리즘과 비밀키를 모두 저장할 공간이 부족해진다는 것이다.

 

하지만, 현대 암호에서는 비밀 키를 추측하는 것이 매우 어려워져서 알고리즘을 비공개로 할 필요가 없어졌다.이것이 바로 Kerckhoff의 원리라고 부른다.이때, 현대 암호에서는 각각의 알고리즘에 대하여 키 공간(key domain)이 매우 크기에 공격자가 키를 추측하기 어렵다고 말한다.

 

---

1.2. 암호 해독

암호(cryptography)가 비밀 코드를 생성하는 과학이자 기술인 것과 같이, 암호 해독(cryptanalysis)은 코드를 깨는 과학이자 기술이다.아래 그림과 같이 암호 해독 공격에는 4가지 종류가 있다. 이제부터 다룰 것이다.

 

그림 3. 암호 해독 공격

 

(1) 암호문 단독 공격(Ciphertext-only attack) 

 

그림 4. 암호문 단독 공격

이는 공격자가 어떤 암호문을 얻어서 대응되는 평문과 키를 찾는 것이다. 

여기서 공격자는 알고리즘을 알고 있고, 암호문을 가로챌 수 있다고 가정한다.

공격자는 이 공격을 위해 암호문만을 필요로 하기 때문에, 암호문 단독 공격은 가장 쉽게 적용될 수 있는 공격이다.

공격자가 메시지를 복호화 하는 것을 막기 위해, 암호는 이런 종류의 공격에 안전해야 한다.

 

(2) 전수조사 공격(brute-force attack)

 

이 방법은 모든 가능한 키를 시도하는 방법이다. 여기서 공격자는 알고리즘과 모든 가능한 키들의 집합인 키 공간을 안다고 가정한다.

공격자는 가로챈 암호문을 모든 가능한 키를 사용하여 복호화하면서 의미 있는 평문을 얻을 때까지 반복하는 것이다.

이런 종류의 공격을 막기 위해서는 가능한 키의 수가 매우 커야 한다.

 

(3) 통계적 공격(statistical attack)

 

암호를 해독하는 사람들은 메시지로 전달하는 단어들의 통계적인 특징을 활용하여 해독을 시도하기도 한다.

이를 통계적 공격이라고 하는데, 예를 들어, 알파벳 E는 영어에서 가장 빈번히 사용된다.

암호해독가는 암호문에서 가장 빈번히 사용된 기호를 찾아서 이에 대응되는 평문이 E라고 가정하고, 여러 쌍을 찾은 후, 해독가는 키를 찾고 메시지를 복구하기 위해 찾은 키를 사용한다.

이런 종류의 공격을 막기 위해서는 암호문이 평문 언어의 특징을 드러나지 않아야 한다.

 

(4) 패턴 공격(pattern attack)

 

평문 언어의 특징은 드러나지 않지만, 암호문에 어떤 패턴이 존재할 수 있다.

암호를 해독하는 사람은 암호문의 패턴을 파악하여 암호를 공격할 것이다.

그러므로 암호문을 랜덤하게 보이도록 만드는 암호를 사용하는 것이 중요하다.

 

(5) 알려진 평문 공격(known-plaintext attack)

 

그림 5. 알려진 평문 공격

 

공격자는 위의 그림과 같이, 해독하려는 암호문 외에 추가로 여러 개의 평문/암호문 쌍을 확보한다.

 

공격자는 공개된 평문/암호문 쌍을 사용하여 Alice가 Bob에게 보내는 다음 비밀 메시지를 알아내는 데 사용한다.

여기서 Alice는 키를 변경하지 않았다고 가정한다. 게다가 공격자는 주어진 평문/암호문 쌍의 연관성으로 다음 암호문을 해독한다.

암호문 단독 공격에 사용되는 방법을 알려진 평문 공격에도 적용할 수 있다.

이 공격은 공격자가 더 많은 정보를 이용하여 해독하기 때문에 해독하기가 더 쉬우나, Alice가 키를 변경하거나, 과거에 보낸 메시지를 노출하지 않을 수도 있기 때문에 적용 가능한 상황이 암호문 단독 공격보다는 드물다.

 

(6) 선택 평문 공격(chosen-plaintext attack)

 

그림 6. 선택 평문 공격

 

이 공격 방법은 알려진 평문 공격과 유사하지만, 공격자가 확보할 수 있는 평문/암호문 쌍은 공격자가 선택한 값이다.

위의 그림은 선택 평문 공격 과정을 나타낸 것이다.

 

예를 들어, 공격자가 Alice의 컴퓨터에 접속할 수 있다면, 이 공격을 적용할 수 있다.

공격자는 자신이 원하는 평문을 선택하고 이에 대응되는 암호문을 얻는다.

물론 키는 보통 송신자에 의해 사용되는 소프트웨어에 포함되어 있기 때문에 키를 알 수 없다.

이런 종류의 공격은 해독하기 더 쉽지만, 적용 가능한 상황은 드물다.

 

(7) 선택 암호문 공격(chosen-ciphertext attack)

 

그림 7. 선택 암호문 공격

 

공격자가 자신이 원하는 암호문을 선택하고 그에 대응되는 평문을 얻는다는 점을 제외하고, 선택 평문 공격과 유사하다.

이 공격은 공격자가 Bob의 컴퓨터에 접속할 수 있어야만 적용할 수 있다. 위 그림은 선택 암호문 공격 과정을 나타낸 것이다.