블록 암호와 운영 모드

Padding

블록 암호는 블록 단위로 암호화를 하기 때문에 입력의 길이가 정확하게 블록 크기의 배수가 되어야한다.

그러나 일반적으로 평문의 크기는 블록 크기의 배수가 되지 않는다.

이러한 문제를 해결하기 위해서 평문에 데이터를 붙여서 배수로 만드는 과정을 Padding이라고 한다.

 

Padding된 암호문을 복호화할 때는 복호화된 평문에서 Padding을 제거해야

원래의 평문을 얻을 수 있다.

 

 

1. Bit Padding

마지막 블록에서 평문이 채우지 못하는 비트 중 최상위 비트를 1로 설정하고, 나머지는 0으로 채우는 padding 기법

 

수신자는 평문의 마지막 비트부터 처음으로 1이 나올 때까지가 padding임을 알 수 있다.

 

하지만 이 방법은 평문의 크기가 정확히 블록 크기의 배수여서 padding 없는 경우에,

수신자가 메시지의 일부를 padding으로 오해하게 되는 문제가 발생할 수 있다.

이를 막기 위해서 Bit padding 적용 시에는, 평문의 크기가 블록 크기의 배수면 패딩으로 한 블록을 추가한다.

 

 

 

2. Byte Padding : ANSI X.923

바이트 단위로 padding을 수행하는 padding 기법이다.

 

Byte Padding에도 여러 종류가 있다.

그 중 ANSI X.923은 마지막 블록의 남은 바이트를 임의의 값으로 채우고, 마지막 바이트에 padding의 길이를 기록한다.

이 경우에는 마지막 바이트의 값이 4이므로 마지막 4비트인 00 00 00 04가 padding임을 알 수 있다.

 

Bit Padding과 마찬가지로 평문의 크기가 정확히 블록 크기의 배수여서 padding 없는 경우에,

수신자가 메시지의 일부를 padding으로 오해하게 되는 문제가 발생할 수 있다.

이를 막기 위해, 평문의 크기가 블록 크기의 배수면 패딩으로 한 블록을 추가한다.

 

 

 

3. Byte Padding : PKCS#7

PKCS는 공개키 암호의 표준 문서로, 그 중 7번째 문서인 PKCS#7은 AES와 같은 블록 암호의 padding 기법을 제시하고 있다.

 

PKCS#7에 소개된 padding 기법은 추가할 padding의 바이트 크기로 마지막 블록을 채우는 것이다.

 

다른 padding 기법과 동일하게 평문의 크기가 블록 크기의 배수면,

PKCS#7은 08 08 08 08 08 08 08 08을 패딩으로 추가한다.

 

---

 

 

대칭-키 암호화 기법은 현대 블록 암호를 기반으로 수행된다.

DES와 AES와 같은 현대 블록 암호는 고정된 길이의 텍스트 블록을 암복호화한다.

DES는 64비트 블록을, AES는 128비트 블록을 암복호화한다.

하지만, 실제 응용 환경에서는 암호화되는 텍스트의 길이는 가변적이며 64비트/128비트보다 훨씬 길다.

이러한 문제를 해결하기 위해서 임의의 길이의 텍스트를 암호화하는 방법인 운영모드가 설계되었다.

 

ECB(Electronic Codebook) 모드

운영 모드 중 가장 간단한 모드

 

평문을 $N$개의 $n$비트 블록으로 분할한다.

만약 평문의 크기가 블록 크기의 배수가 아니라면,

평문의 마지막 블록은 다른 블록들과 동일한 크기로 만들기 위해 마지막 블록에 padding을 넣는다.

 

각각의 블록을 암복호화하기 위해서 사용되는 키는 동일하다.

 

 

 

암호화 : $C_i = E_k(P_i)$

복호화 : $P_i=D_k(C_i)$

 

$P_i = D_k(C_i) = D_k( E_k(P_i))= P_i$

 

 

 [ 취약점 ]

1. 블록 단위의 패턴이 유지된다.

평문에서 같은 값을 가지는 블록은 대응되는 암호문 블록도 같은 값을 가진다.

 

공격자는 암호문 중에서 1,5,10번째 블록의 값이 서로 같다는 사실을 발견하면

평문의 1,5,10번째 블록의 값도 서로 같다는 것을 알 수 있다.

그러면 공격자는 1,5,10번 블록의 정보를 찾기 위해서 하나의 블록을 선택해 Brute force 공격을 할 수 있다.

 

2. 암호문을 변조할 수 있는 기회를 제공한다.

블록간의 독립성으로 공격자가 키를 알지 못해도 암호문 변조가 가능하다.

 

공격자가 8번째 블록이 항상 특정 정보를 내포하고 있다는 사실을 안다면,

이전에 가로챈 암호문의 8번째 블록으로 이 블록을 대체할 수 있다.

 

3. Replay attack

어떤 데이터를 재전송해서 시스템이 의도치 않은 행동을 하게 하는 것을 Replay attack이라고 한다.

ECB 모드는 약한 혼돈 성질을 가지고 있기 때문에 Replay attack에 약하다.

 

(시나리오)

공격자가 어떤 회사에서 일하고 있고 급여가 매우 적다고 가정하자.

그리고 공격자는 회사에서 직원들에게 지급해야하는 금액에 대한 정보가 7번째 블록에 있다는 것을 알고 있다.

공격자는 회사가 은행에 보내는 암호문을 가로채서

일을 더 많이 한 동료의 급여 정보를 가지는 블록을 복사해서

자신의 급여 정보 블록과 대체할 수 있다.

 

 

[ 응용 ]

안전하지 않은 채널을 통해 두 개 이상의 블록을 가지는 메세지를 암호화하여 전송하는 수단으로는 권장되지 않는다.

하지만, 메시지 길이가 충분히 짧다면, 안정성은 별 영향을 주지않는다.

 

데이터베이스에 암호화된 레코드를 저장하거나 복호화하는 분야에서는 암호문 블록의 독립성이 유용하다.

블록의 암복호화 순서가 중요하지 않기 때문에,

각각의 레코드가 단일 블록이거나 블록의 배수라면 데이터베이스에 랜덤하게 접근할 수 있다.

그리고 다른 레코드에 영향을 주지 않고도 중간에서부터 암복호화가 가능하다.

 

매우 많은 데이터베이스를 암호화할 때 병렬적으로 처리가 가능하다.

 

 

 

CBC(Cipher Block Chaining) 모드

각각의 평문 블록은 암호화되기 전에 이전 암호문 블록과 XOR된다.

블록이 암호화될 때, 암호화된 블록이 전송되고

이 암호화된 블록은 다음 블록을 암호화할 때 사용되기 위하여 메모리에 저장되어야한다.

 

그리고 첫 번째 블록 암호화할 때는, 이전 블록이 존재하지 않기 때문에 초기 벡터(IV)가 사용된다.

 

 

 

암호화

$C_0 = IV$

$C_i = E_k(P_i \oplus C_{i-1})$

 

복호화

$C_0 = IV$

$P_i = D_k(C_i) \oplus C_{i-1}$

 

 

[ 초기 벡터(IV) ]

초기 벡터는 일반적으로 Nonce값을 사용한다.

초기 벡터(IV)는 송신자 수신자간에 공유되어야 하지만 반드시 비밀일 필요는 없다.

그러나 IV의 무결성은 CBC 모드의 안전성에 중요한 역할을 하므로 IV는 변조되지 않아야한다.

공격자가 IV의 비트 값을 변조할 수 있다면, 첫 번째 블록의 비트 값들이 바뀌게 되는 결과를 초래한다.

 

이를 위해서 송신자가 의사 난수를 선택하고 선택된 난수열을 안전한 채널을 통해 수신자에게 보낸다.

둘 사이에 비밀 키를 공유하고 있다면 송신자와 수신자는 고정된 값을 IV로 공유할 수 있다.

 

 

[ 취약점 ]

1. 한 메시지 내의 동일한 평문 블록들은 서로 다른 암호문 블록으로 암호화된다.

블록 단위의 패턴이 유지되지 않는다.

 

하지만 동일한 IV를 사용하고 두 개의 메시지가 동일한 경우 대응되는 암호문은 동일하다.

서로 다른 두 메시지의 처음 M개의 블록이 같고 IV가 같으면 대응하는 M개의 암호문 블록이 같다.

 

이러한 취약점을 극복하기 위해서 타임스탬프를 IV로 사용하기도 한다.

 

2. 공격자가 암호문 끝에 특정 암호문을 덧붙일 수 있다.

 

3. CBC Bit-flipping attack

공격자가 초기 벡터를 원하는 값으로 조작해서 복호화된 평문의 첫 번째 블록하는 공격이다.

 

첫 번째 암호문의 블록의 복호화 과정 : $P_1 = D_k(C_1) \oplus IV$

 

공격자는 초기 벡터를 $IV' = P_1 \oplus P'_1 \oplus IV$로 조작해 첫 번째 평문을 $P'_1$로 조작할 수 있다.

 

(시나리오)

Alice가 Alice has 10000$라는 평문을 IV가 \x00\x00\x00\x00인 CBC 모드로,

4바이트씩 블록 암호화해서 은행에 전송한다고 가정하자.

만약 Alice가 이 통신을 중간에 가로채서 $IV' = \text{Alic} \oplus \text{Alli} \oplus IV$인 $IV'$로 $IV$를 치환하고,

암호문을 재구성해서 은행에 전송하면

은행은 이를 복호화 했을 때, Allie has 10000$라는 조작된 평문을 얻는다.

 

 

[ 응용 ]

메시지를 암호화하기 위해서 사용된다.

하지만 블록간의 연관성이 존재하기 때문에 병렬처리가 불가능하다.

 

 

 

CTR(Counter) 모드

블록 암호에 Nonce와 평문 블록의 인덱스(counter)를 결합한 값을 입력한다.

암호문은 블록 암호의 출력과 평문 블록을 XOR 연산해 생성한다.

 

n비트 counter는 사전에 결정된 값(IV)로 시작해서 사전에 정의된 규칙($\pmod{2^n}$)에 따라 증가한다.

만약 난수성을 좀 더 강화하기를 원한다면, 카운터의 증가량을 블록의 인덱스에 의존하여 사용하면 된다.

 

 

암호화 : $C_i = P_i \oplus E_{ki}(Counter)$

 복호화 : $P_i = C_i \oplus E_{ki})Counter$

 

 

 

GCM(Galois Counter Mode)

현재 네트워크 통신에서 많이 사용되고 있다.

 

GCM 운영모드는 Authenticated encryption의 형식을 가진다.

즉, 암호화시 태그를 생성하고, 태그가 있어야 복호화가 가능하다.

 

GCM은 기본적으로 CTR 모드를 사용해서 데이터를 암호화한다.

암호화 시 Counter 값을 암호화하고 그 결과를 평문과 XOR해서 암호문을 만든다.

 

GCM의 핵심은 무결성 태그(TAG)을 생성한다는 점이다.

암호화된 데이터가 전송 중에 단 1비트라도 바뀌면 태그 검증이 실패해서 즉시 탐지가 가능하다

이 태그를 만드는 데 Galois Field라는 수학 연산을 사용한다.

 

CTR 기반이기 때문에 병렬 처리가 가능하다.

암호화로 기밀성을 제공하고 Galois Field Tag로 무결성도 제공한다는 장점이 있다.