[암호 스터디 #4] 블록 암호

오늘은 블록암호에 대해 알아보자.

미국 정부에서 만든 DES(Data encryption Standard; 자료 암호화 표준), 벨기에에서 개발된 DES의 후계자 AES(Advanced Encryption Standard), KGB가 개발한 GOST 28147-89 의 공통점은 무엇일까?

바로 블록 암호(block cipher)라는 것이다.

 

4.1 블록 암호란 무엇인가?

하나의 블록 암호는 암호화 알고리즘 하나 + 복호화 알고리즘 하나로 구성

​

4.1.1 보안 목표

블록 암호에서의 보안성?? "얼마나 무작위하게 보이는가" --> 반드시 의사무작위 치환(pseudorandom permutation, PRP) = 키를 알지 못하는 한 공격자는 임의의 입력으로부터 블록 암호의 출력을 계산할 수 없어야 한다.

 

4.1.2 블록 크기

블록 암호의 보안성은 (a) 블록의 크기 , (b) 키의 크기 에 의존한다.

DES - 64(2^6)비트 블록

AES - 128(2^7)비트 블록

*현대적인 CPU들이 64비트보다 128비트를 더 효율적으로 처리하며 128비트 블록이 더 안전

* 암호문의 길이나 메모리 사용량을 최대한 아껴야 하는 상황에서는 64비트 블록을 사용할 수 있다.

 

4.1.3 코드북 공격

메모리를 아낀다고 블록을 너무 작게 사용한다면? 코드북 공격(codebook attack)에 당할 수 있다.

코드북 공격은 블록이 작을 때만 효율적으로 작용하는 불록 암호 공격 기법이다. -> 32비트 블록까지는 감당할 수 있지만 블록이 그것보다 더 커지면 현실적으로 불가능!

​

4.2 블록 암호 구성

블록 암호를 구성하는 데 쓰이는 기법의 수는 그리 많지 않다.

1. 실제 쓰이는 블록 암호는 하나의 거대한 알고리즘이 아닌 짧은 라운드들을 반복하는 형태의 알고리즘이다.

2. 라운드를 구축하는 기법은 크게 두가지이다. ( 대입-치환 네트워크, 파이스텔 방안 )

​

4.2.1 블록 암호의 라운드

블록 암호의 알고리즘은 명세와 구현이 쉬운 기본적인 형태의 라운드를 여러 번 반복하는 것으로 구성된다.

ex) 평문을 세 개의 라운드로 암호화하는 블록 암호를 C = R3(R2(R1(P)))로 표현

- 각 라운드마다 서로 다른 라운드 키 존재.

- 각 라운드는 동일한 알고리즘을 사용하되 라운드 키로 매개변수 되서 다른 라운드 키를 가지면 다른 동작을 하게 된다.

- 각 라운드 키는 주 키 K 로부터 생성 ( 키 스케줄 알고리즘 사용 ), 주 키 K와는 다른 값.

 

4.2.2 슬라이드 공격과 라운드 키

모든 라운드가 같아버리면 어떤 일이 일어날까? 슬라이드 공격(slide attack)에 당하게 된다..

위 사진에서는 라운드가 세개라 C2=R(C1) 만 알수 있지만 라운드 수가 늘어나도 항상 성립한다.

공격자가 한 라운드의 입력과 출력을 알아내서 키 복원에 활용할 수 있다.

따라서 라운드 마다 다른 라운드 키를 사용해야 이런 슬라이드 공격을 좌절시킬 수 있다.

 

4.2.3 대입-치환 네트워크 ( substitution-permutation network, SPN )

- 혼돈(confusion) : 입력(평문과 암호화 키)이 복잡한 변환들을 거친다, 깊이에 관한 것

- 확산(diffusion) : 그러한 변환들이 모든 비트에 동일하게 의존한다, 너비에 관한 것

- 대입 연산은 대입 상자(substitution box; S-상자)로 구현된다.

* 대입 상자 : 4비트 또는 8비트의 자료 조각을 변환하는 작은 참조표

- 치환은 그냥 비트들의 순서를 바꾸는 정도로 간단한 치환일 수도 있지만 비트들을 많이 뒤섞진 못한다. 대신 어떤 암호들은 기본적인 선형대수와 행렬 곱셈을 이용해서 비트들을 섞는다.

* 대입-치환 네트워크 알고리즘을 사용하는 대표적인 암호는 AES이다. 뒤에서 자세히 알아보도록 하자.

​

4.3.4 파이스텔 방안 ( Feistel scheme )

- 파이스텔 방안의 작동 과정

1. 일단 암호화하려는 정보를 절반으로 잘라서 (L, R) 을 얻는다.

2. L = L xor F(R) // F는 하나의 대입-치환 라운드

3. L과 R을 교환하여 (R,L)을 얻는다

4. 단계 2와 3을 15번 되풀이 한다.

5. L과 R을 연결해서 하나의 64비트 출력 블록을 만든다.

이런 방식으로 동작을 한다. F 함수들이 받는 Ki는 라운드 마다 다르고 48비트 라운드 키이다.

여기서 F는 의사무작위 함수(PRP)일 수도 있고, 의사난수 함수(pseudorandom function, PRF)일 수도 있다.

- PRP : 서로 다른 두 입력에 대해 각각 다른 출력을 산출

- PRF : 서로 다른 두 입력에 대해 같은 출력을 할 수도 있다. ( F가 암호학적으로 강한 함수면 이러한 차이는 무시 )

* 이론적으로 F가 왕왕 강하다면 라운드가 4개만 있어도 충분하지만 현실은 그보다 많은 수의 라운드 사용.

 

4.3 AES(고급 암호화 표준)

* AES는 현재 이 세상에서 가장 많이 쓰이는 암호다.

​

4.3.1 AES의 내부

- AES는 128비트 블록들을 128비트나 192, 256비트 비밀 키 하나를 이용해서 처리한다.

- 가장 널리 쓰이는 것은 128비트. ( 대부분의 응용 프로그램에서 128비트와 256비트의 보안성 차이는 무의미 )

AES는 하나의 16바이트 평문을 2차원 배열로 취급한다. 이 배열을 AES의 내부 상태 (internal "state")

AES의 내부상태

AES는 같은 구조의 SPN과 다수의 라운드를 사용해서 상태를 변환

라운드 수	10	12	14
키	128비트	192비트	256비트

AES의 내부 연산들

위 그림에서 보듯이, 하나의 AES 라운드는 4가지 연산으로 이루어져 있음.

1) SubBytes : 각 바이트(S0, ... , S15)를 대입 상자에 따라 다른 바이트로 대체한다.

2) ShiftRows : 0에서 3 까지의 i에 대해, i번째 행을 i자리 만큼 순환 이동.

3) MixColumns : 상태의 네 열(column)에 대해 동일한 선형변환을 적용. ( 선형변환 : 예측가능 )3

4) AddRoundKey : 라운드 키와 내부 상태의 XOR.

* KeyExpansion이 없으면? 모든 라운드 키가 같음 -> 슬라이드 공격에 취약

* AddRoundKey가 없으면? 누구나 키 없이도 임의의 암호문을 복호화

* SubBytes가 없으면? 한 열의 변화가 다른 열들에 영향을 미치지 않아서 코드북 만들어 깰 수 있음

* MixColumns가 없으면? 참조표를 이용해서 암호문을 복호화할 수 있음

** 복호화 하는 과정은 모든 연산의 역함수 이용

 

4.4 AES의 구현

4.4.1 테이블 기반 구현

4.4.2 전용 기계어 명령

4.4.3 AES는 안전한가?

AES는 블록 암호가 안전할 수 있을 만큼 안전하며, 절대 깨지지 않는다.

왜냐하면 모든 출력 비트가 모든 입력 비트에 어떤 복잡하고도 의사무작위한 방식으로 의존하기 때문이다.

하지만 AES가 모든 가능한 공격에 면역이라는 증명은 없다. ( 우리가 모든 가능한 공격을 모르기 때문에 )

그리고 블록 암호에 대한 가장 큰 위협은 핵심 알고리즘이 아니라 "운영 모드"들에 존재한다.

​

4.5 운영 모드

4.5.1 전자 코드북(ECB) 모드

블록 암호의 암호화에서 가장 간단한 모드!!

하지만 안전하지 않으므로 사용하면 안 된다! -> 같은 키와 같은 평문으로 암호화를 반복하면 같은 암호문이 나옴, 전체 블록 단위의 자료들만 처리할 수 있음

* ECB 암호화는 원래 이미지와 색만 다른 이미지를 산출할 뿐이다.

​

4.5.2 암호 블록 연쇄(CBC) 모드

ECB와는 달리 CBC(Cipher block chaining) 모드는 Ci = E(K,Pi xor Ci-1) 로 암호화한다.

첫 블록 P1을 암호화할 때는 이전 암호문 블록이 없으므로 무작위 초기치(initial value, IV)를 사용.

CBC모드

CBC 모드의 복호화는 암호화와 달리 병렬 처리가 가능하여 더 빠르다.

Pi = D(K,Ci) xor Ci-1

위의 식으로 복호화 될 때 모든 암호문을 알고 있기 때문에 병렬계산과 함께 평문을 얻어낼 수 있다.

​

4.5.3 CBC 모드에서 임의의 길이의 메시지를 암호화하는 방법

EBC 모드의 단점 중 블록 단위 제약을 극복하는 방법 ( 블록 길이의 정수배가 아닌 길이의 평문 처리 방법 )을 두 가지 기법을 통해 알아보도록 하자.

1) 메시지 채우기(padding)

- 마지막 블록이 완전히 '채워질' 때 까지 평문에 여분의 바이트들을 추가한다.

- 블록들을 채우고 15 바이트를 더 채워야 하면 그 값을 0f(십진수로 15)로 메시지 끝에 15개 추가

- 블록들을 채우고 13 바이트를 더 채워야 하면 그 값을 0d(십진수로 13)로 메세지 끝에 13개 추가

- 만약 블록 길이 16의 정수배에 해당하면 그대로 끝내는 게 아닌 10(십진수로 16)로 메세지 끝에 16개 추가

* 복호화 방법

1. 모든 블록(채우기된 상태)을 복호화한다.

2. 마지막 바이트들을 살펴본다. 01이 1개 있는지, 02가 2개 있는지 등등..

3. 혹시 그렇지 않다면 복호화 거부를 하고, 과정2를 만족한다면 채움 바이트를 제거하고 평문 바이트를 돌려준다.

2) 암호문 훔치기(ciphertext stealing)

- 채우기보다 더 복잡하고 덜 쓰이지만 3가지 장점이 있다.

1. 평문이 비트 단위의 길이라서 131비트 같은 평문을 암호화할 수 있다.

2. 암호문이 평문과 같은 길이이다.

3. 채움 오라클 공격에 취약하지 않다.

 

CBC 모드 암호화의 암호문 훔치기

그림에서도 볼 수 있듯이 C2 = P3 xor (이전 암호문 블록의 마지막 비트들) 그 다음 암호화한 결과

C3 = 이전 암호문 블록의 처음 비트들

- 단점 : 별다른 문제점이 없지만, 별로 우아하지 않고 제대로 구현하기가 어렵다.

​

4.5.4 카운터(CTR) 모드

- 암호문 훔치기의 장점을 유지하면서 단점을 피하고 싶을 때 사용하는 모드

- 블록이라는 개념에 의존하지 않고 그냥 비트들을 받아서 비트들을 산출하는 형태의 암호로 바꾸는 역할

CTR 모드

N(논스)은 한 번만 쓰이는 수(number used only once)인 일종의 토큰값으로 한 메시지의 모든 블럭은 같은 논스 값 사용

Ctr(카운터)은 하나의 메시지들이 같은 값을 사용할 수는 없다.

- 동작 과정 : N과 Ctr을 이어붙인 다음 암호화를 해서 나온 값과 평문을 xor 해서 암호문 블록을 만든다. ( 복호화 과정도 이와 동일하기 때문에 하나의 암호화 알고리즘을 암복호화에 사용할 수 있다. )

- 논스가 무작위일 필요가 없지만 각 암호화마다 고유(유일)해야한다.

- 장점 : 그 어떤 모드보다도 빠를 수 있다. ( 병렬화 and 평문 메시지가 주어지기 전에 암호화 시작 가능 )

​

4.6 문제 발생 요인들

블록 암호에 대한 공격 중 두 가지는 반드시 알아 두어야 한다.. 라고 써있네여..

중간값 일치 공격이랑 채움 오라클 공격인데 중간값 일치 공격이랑 중간자 공격이랑 다르대여 ㅋㅋ 같은줄알았는데.. 머-쓱

​

4.6.1 중간값 일치 공격

3DES의 보안 수준이 168비트가 아닌 112비트인 이유가 중간값 일치(meet-in-the-middle, MitM) 공격 때문이다.

 

4.6.2 채움 오라클 공격