Symmetric key Encryption - Block Cipher

대칭키 기반의 암호화 중에서 Confidentiality를 만족하는 방식 중 OTP(one time pad) 내용을 살펴보았다. 

이번 글에서는 Confidentiality를 위한 또 다른 암호화 기법인

"Block Cipher"

에 대해 알아보자.

 

 

Block cipher는 OTP와 달리 Plaintext의 블록을 통째로 암호화하는 기법이다.

* OTP에서는 bit 단위로 randm bit string인 pad를 생성해 암호화 과정을 거쳤다. 

 

Block cipher는 n bits의 데이터 블록에 k bits의 key를 사용해 암호화하고, 

반대로 n bits의 암호문 블록에 k bits의 key를 사용해 복호화한다. 

 

Block cipher에서는 XOR과 bit shift 연산을 사용하여 암호화 과정을 거치고 보통 k bits는 n bits보다 작다.

또한 Plaintext와 Ciphertext는 Permutation 관계를 만족해야 한다. 

 

* Permutation = 서로 다른 input에 대해 서로 다른 output이 매치되는 것.

(두 개의 input의 결과로 동일한 하나의 output이 나와서는 안된다.)

 

 

 

!! Block cipher의 경우, 보통 고정된 길이를 고려하며(ex. 128 bits) Deterministic 하다는 문제가 있다.

* Deterministic = t0일 때 input a의 output이 b라면, t2, t4, t10,.. 항상 input a의 output이 b인 성질. 

 

그렇다 보니 이 두 문제를 해결하기 위해 연산(Operation)을 거친 block cipher mode를 각각

ECB, CBC, CTR 

이라고 한다.

 

 

---

ECB :: Eletronic Code Book

128 bits 보다 큰 문자열 256 bits의 plaintext가 있다고 상상해 보자. ECB에서는 plaintext를

128 bits x 2 block으로 쪼개서 각각 암호화를 진행하고 그 결과를 이어 붙여서cipher text를 만든다. 

* 이때 두 문자열을 이어 붙이는 것을 표현하는 기호를 이와 같이 나타내며 " || ", concentrate 한다고 표현한다.

 

 

128 bits로 쪼갠 각 block에 key를 이용한 암호화를 거쳐 cipher text를 만든다.

 

길이가 128 bits 보다 긴 plaintext를 암호화하기 위해 block으로 쪼개서 암호화를 진행했지만 여기서 문제가 발생하게 된다. 

 

하나의 메세지에 대해 암호화하는 동안에는 사용하는 key가 동일하다.

이 말은 즉슨 하나의 메세지를 128 bits의 길이로 쪼갠 block을 암호화할 때 사용하는 key가 다 동일하다는 것!

 

메세지를 쪼갠 block 중에서 중복되는 block이 있다면 ciphertext도 동일하게 나올 것이다. [=Deterministic]

따라서 ciphertext를 모으던 공격자에게 이 메세지의 n번째, m번째 block의 plaintext가 같다는 정보를 제공하게 된다. 

 

 

! 항상 input a의 output이 b이기 때문에 이 문제를 해결하기 위해 랜덤 한 성질을 부여할 필요가 있다.

---

CBC :: Cipher Block Chaining

위에서 살펴본 ECB의 경우, 모든 block에 동일한 key를 사용하다 보니 랜덤 한 성질이 부족하다는 문제가 발생하였다. 

이 부분을 해결하기 위해서 CBC mode에서는 IV라고 하는 벡터를 사용하고자 한다.

 

 

첫 번째 block에 IV를 XOR 한 다음, key로 암호화하는 과정을 거친다. 

이렇게 되면 plaintext에 랜덤 한 값이 XOR 되기 때문에 그 결과도 랜덤 하다고 할 수 있다.

 

! 다만, 첫 번째 block에만 IV를 XOR 하게 되면 2~n번째 block에서는 ECB과 동일한 문제가 발생하기 때문에 

2번째 block부터는 i-1번째 block의 ciphertext를 가져와 IV처럼 활용하기로 한다. 

 

첫 번째 block에서 랜덤 한 IV를 사용해 랜덤 한 ciphertext 1을 만들고 나면

그다음 block은 모두 연쇄적으로 랜덤 한 Ci를 도출하게 된다. 

 

 

 

그렇다면 반대로 Decryption 과정은 어떨까??

plaintext를 얻기 위해 각 block에 대해서는 key를 사용한 복호화 과정을 거친 후, IV(or Ci-1)로 XOR 연산을 실행하면 된다.

 

 

CBC mode의 Enc, Dec 과정에서의 차이점이 있다면, 

Encryption) i번 째 block을 암호화하기 위해서는 Ci-1이 필요하기 때문에 이전 block이 암호화되기를

기다려야 한다. 따라서 병렬적으로 모든 block의 암호화가 이뤄질 수 없다.

 

Decryption) 각 cipher block을 복호화하기 위해서는 IV(or Ci-1)와 Ci, key가 필요하다. 

Encryption에서는 Ci-1을 얻기 위해 기다려야 했지만, 이미 필요한 요소가 모두 주어진 상태이기 때문에

이전 block의 연산 처리를 기다릴 필요가 없다.

 

 

CBC mode Encryption & Decryption 

Encryption	Decryption
병렬 처리 불가	병렬 처리 가능

 

 

 

IV를 사용해서 Deterministic 한 성질로 인한 문제를 해결했다.

그렇다면 암호화하고자 하는 데이터 길이가 128 bits의 배수가 아니라면 어떻게 해야 할까?

 

CBC mode에서는 길이에 의한 문제를 해결하기 위해 Padding을 사용할 수 있다.

만약 plaintext의 길이가 291 bits라고 하면, 이는 128 bits block + 128 bits block + 35 bits로 쪼개진다.

이럴 경우, 35 bits에 93 bits Padding을 더해 128 bits 길이를 맞춰주는 것이다. 

 

Padding ) 길이를 맞춰주기 위한 의미 없는 데이터 dummy

1. 부족한 길이만큼 0 bit를 붙이되, 어디서부터 Padding이 시작되었는지 알 수 있게 맨 앞은 1 bit로 시작한다.

ex) 121 data bits + 7 bits padding을 붙여야 한다 → ~~~~1000000

 

2. 지정된 byte 길이 만큼 padding을 붙인다.

ex) 3 byte padding = 03 03 03을 padding으로 만들어 붙인다.

03 03 03 = 00000011 00000011 00000011로 총 24 bits (= 3byte)의 padding이다. 

 

 

 

CBC mode에서는 Randomness를 부여하기 위해 IV를 사용하였고, 

128 bits가 아닌 데이터를 다루기 위해 padding을 붙일 수 있다는 내용을 살펴보았다.

 

이런 CBC mode에서의 문제점은 없는 것일까??

OTP에서 pad를 two time 사용하게 되면 plaintext에 대한 부가적인 정보를 유출할 수 있다고 했다.

 

비슷하게 CBC mode에서도 IV를 재사용하게 되면 Plaintext에 대한 정보를 유출해 Confidentiality를 만족한다고 할 수 없게 된다.

 

메세지가 2개 있다고 할 때, 각 메세지의 block이 다음과 같이 구성된다고 해보자.

M1 = P1 P2 P3 & M2 = P1 P2 P4

 

이런 상황에서 동일한 IV를 사용하게 되면 M1에서 P1~P2를 암호화한 과정의 Ciphertext와 

M2에서 P1~P2까지 암호화한 과정의 ciphertext가 동일하기 때문에 

공격자 입자에서는 M1과 M2의 2번째 block까지의 plaintext 내용이 같다는 정보를 알 수 있게 된다!!

 

---

CTR :: counter mode

CTR mode는 위에서 살펴본 mode와는 다르게 key에 randomness를 부여하는 방식이다. 

CBC mode에서는 plaintext에 IV를 XOR 하여 Randomness를 부여했지만, 

CTR mode에서는 key와 랜덤값으로 암호화를 거친 후 plaintext와 XOR 하는 흐름으로 진행된다.

 

 

CTR에서 사용하는 랜덤 값을 Nonce라고 부른다.

IV처럼 랜덤 한 값에 counter라고 하는 block의 순번을 알 수 있는 수를 뒤에 더한 형태이다. 

 

 

복호화를 하는 과정도 암호화하는 과정과 크게 다를 거 없이 진행된다. 

(ciphertext와 plaintext 자리만 바꿔주면 된다.)

 

 

CBC mode에서는 이전 block의 ciphertext를 가져와서 IV처럼 사용했다 보니 block 간의 상호작용으로 인해

Encryption 과정은 병렬적인 처리가 불가능했다. 

 

하지만 CTR mode에서는 block마다 독립적인 과정으로 암호화/복호화가 진행되기 때문에 

Encryption & Decryption 모두 병렬적인 처리가 가능하다는 것이 CBC mode와의 차이점이다. 

 

또한 plaintext 길이가 크게 상관없기 때문에 padding을 추가하는 과정도 필요 없어지게 된다.

 

다만, IV를 재사용하면 안 되듯이 Nonce를 재사용하게 되면 문제가 생길 수 있다.

M1 = P1 P6 P8 & M2 = P4 P1 P7

nonce를 재사용한 상황에서 두 메세지의 block 중에서 동일한 block이 존재한다고 할 때

counter 값만 변경하면 ciphertext가 동일하게 나오기 때문에 두 메세지에서 각각 1, 2번째 plaintext가

동일하다는 정보를 제공하게 된다. 

 

* 몇 번째 block인지를 보고 counter를 조작할 수 있다.

 

---

[summary]

ECB )

128 bits 보다 긴 plaintext를 block으로 쪼개서 key로 암호화하자. 

 

CBC )

Deterministic : IV or Ci-1을 사용해서 Randomness!

length : padding 붙이자!

 

CTR )

Deterministic : nonce + counter로 Random 하게

length : 신경 안 써도 됨!

 

CBC & CTR ) 

CBC는 복호화만 병렬 처리가 가능하고, CTR은 복호화&암호화 모두 병렬 처리가 가능하다. 

IV, nonce를 재사용하는 것은 confidentiality를 망가트리기 때문에 해서는 안 된다!!