정보보안_3_Crypto

지난 글 마지막에서 암호화의 다양한 타입들에 대해 알아보고 그 중 Hash Function에 대한 이야기를 다뤘다. 이번 글에서는

 

Random Generators - Stream Ciphers

Random permutation - block ciphers 

두 가지 타입에 대한 이야기를 다뤄보겠다.

 

Random bit generation

컴퓨터를 기반으로 암호를 만들때 진정한 난수를 생성할 수 있을까?

아니다. 어떤 Seed를 가지고 암호화를 한다고 해도 Seed에 대한 특징이 존재하기 때문에 완전한 난수는 존재하지 않는다.

다만, 넓은 엔트로피 풀에서 어떤게 나올지를 모르게 한다면 그를 통해 Randomness를 달성할 수 있다.

 

Examples of Randomness

• 하드웨어에서 기반된 랜덤 비트 생성 ( 증폭된 다이오드의 열 잡음, 진동..) 
• 사용자 행동기반 ( 마우스 움직임, 클릭 빈도 )
• 하드웨어의 여러 Interaction들 그들끼리의 커뮤니케이션 시간 간격
• 잡음
• 네트워크 패킷 시간

 

이런 것들을 소스로 누적 엔트로피를 생성하고 그 중 어떤 것을 꺼내서 Seed로 사용해 Randomness를 확보한다.

 

Stream Cipher : RC4

가장 대표적인 스트림 사이퍼의 예이다. 빠르다는 장점을 가지고 있다.

 

1. State를 저장하는 상태배열 S[0] ... S[255]가 존재하고 각 원소는 해당 인덱스의 값을 초깃값으로 갖는다.

S[i] = i;

2. 비밀 key가 존재한다. 해당 키의 길이를 256bit로 맞춰 랜덤 K배열을 만든다. 키의 길이가 256이하일 경우 반복하여 배열을 생성한다.

Ex : key 81920 -> 256bit : 819208192081920...

 

----- 

여기까지가 기본적인 세팅이다. 이어서 K배열을 통해 S배열을 뒤섞는다. (코드는 안 외워도 됨!!! S를 섞어주는게 포인트)

int i=0;
for(i=0;i<256;i++){
	s[i] = i;
    k[i] = key[i%N];
}

int j=0;
for(i=0;i<256;i++){
	j = (j + s[i] + k[i]) % 256 ;
    swap(s[i],s[j]);
}

i = j = 0;

이를 바탕으로 새로운 keystreamByte를 생성할 것이다. 그 방법은 다음과 같다. 

i, j를 구한후 t = (s[i] + s[j]) mod 256

keystreamByte = s[t]

 

이 KeyStreamByte를 사용해 XOR연산을 통해 암호화를 진행한다. 

 

 

BlockCiphers

Block의 크기를 정하고 그 블록 단위로 암호화를 하는 방식을 이야기한다. 일반적으로 많이 사용되는 방식이다.

 

블록 암호화는 중요한 2가지 특성에 기반하여 만든다.

1. Confusion : 평문과 암호문의 관계를 혼란시켜 둘의 관계를 숨겨 평문의 내용을 짐작하기 어렵게 만든다.

2. Diffusion : 평문과 암호문의 통계적분포를 확산시켜 알고리즘 자체를 추론하기 어렵게한다.

 

Types of Attacks on Block Cipher

공격자는 일반적으로 암호문 하나만 알고 있을때 공격이 가장 어렵다. 전수키 조사외에는 할 수 있는 공격이 없기 때문이다. 따라서 몇 가지 소스가 추가된다면 그를 기반으로 key를 알아내 블록 암호화를 위협하는 공격을 할 수 있다. 

 

1. Know plaintext attack : 평문과 그에 해당하는 암호문을 알고 이를 기반으로 진행하는 공격이다. 

그러나 이는 사용자가 key를 바꾼다면 무용지물이 된다.

 

2. Chosen plaintext attack : 암호화 알고리즘은 모르더라도 암호화를 할 수 있는 도구 tool을 가지고 있어 많은 수의 평문을 직접 암호화한 결과를 얻을 수 있어 둘의 연관성을 추측해 key를 알아내는 공격을 의미한다.

 

3. Chosen ciphertext attack : 선택 암호문 공격, 공격자가 복호화가 가능해 다수의 암호문에서 평문을 얻을 수 있는 공격을 의미한다.

 

4. Related key attack : 찾으려는 Key K와 관련있는 k+1, k+2를 이용해 평문 / 암호문을 얻어 이를 비교 연관성을 통해 암호문을 해독하는 공격을 의미함.

 

Block 암호화 예시

DES : Data Encryption Standard

1970년대에 개발된 암호화 기법으로 디자인 과정이 비공개 되어 다소 논란이 있었던..

 

1. Key 길이가 128bit -> 56bit로 줄었다. 그 결과 보안성이 저하될 우려가 존재한다.

2. Feistel Cipher : 전체를 두 부분으로 나누어 암호화를 진행하는 방

3. 특정계산 함수를 반복적으로 적용하는 Round Function을 사용하는 암호화 방식이다. 

DES 방식은 16 라운드가 존재한다.

 

64 bit 길이의 블록이 존재하고 key의 길이는 56bit이다. 그 중 48bits의 key가 각 라운드마다 사용된다. (subkey)

 

아무튼, DES는 key의 길이가 56bit로 작아 실제로 이틀만에 뚫릴 정도로 취약한 암호화 기법이었다. 실제로 키의 길이가 80bit 정도를 넘으면 이상적인 보안성을 얻을 수 있었다. 

따라서, 이를 보완하기 위한 방법으로 Tripple DES (3DES)가 등장했다. 

 

2개의 키를 사용하여 DES를 진행하는데 과정은 다음과 같다.

평문을 P , 암호문을 C, 두개의 56bit 키를 K1, K2라 할때

C = Ek1(Dk2(Ek1(P))) 로 암호화(k1) 복호화(k2) 암호화(k1)의 방식을 사용했다. 

이렇게 진행을 하면 Key가 2개이기 때문에 key이 길이가 112bit로 길어져 원하는 수준의 보안성을 얻을 수 있었다.

 

 

새로운 암호화 기법이 등장하지 않고 왜 DES를 활용?

기존 시스템에서 DES를 사용하는 시스템이 많았기에 이와 호환이 되는 방식이 필요했다.

기존 시스템에 적용하기 위해 위 3DES 방식에서 K1 == K2 인 경우를 생각해보자.

C = Ek(Dk(Ek(P))) 

C = Ek(P)가 되어 기존의 DES 방식과 호환이 가능해졌다.

 

 

왜 Double DES는 하지 않았어?

Double DES도 구현이 가능하지만 이는 Meet in the MIddle Attack (MIM)에 치명적인 단점이 있었다. 

공격자가 Plaintext와 Ciphertext를 아는 Known Plaintext Atatck을 시도하는 경우를 생각해보자.

 

C = Ek2(Ek1(P))이고 이를 복호화 하기 위해 

Dk2(Ek2(Ek1(P))) = Dk2(C) 연산을 하게 되면

Ek1(P) = Dk2(C)라는 식이 성립한다. 공격자는 각 평문과 암호문에 대해서 원하는 결과를 얻기 위해 56bit의 키를 찾기 위한 노력을 할 것이다.

그 노력은 각각 2^56 , 2^56의 시도를 한 후 얻은 결과 set에서 두 계산 값이 같은 key값 k1, k2를 찾을 수 있게 된다.

따라서, 2 * 2^56 에다가 추가적으로 비교연산을 해주는 과정.. 약 2^60정도의 연산으로 k1, k2를 찾을 수 있다는 문제가 발생한다.

 

즉, 키를 두 개 사용하여 2^112정도의 보안성을 기대했으나 2^60정도에 뚫릴 수 있는 보안성을 갖는다는 문제가 있다.

 

AES : Advanced Encryption Standard

DES가 잘 뚫린다는 문제점이 있으니 이를 대체하기 위해 등장한 암호화 기법이다. 90년대 후반에 공모를 했고 결과적으로 Rijndael Algorithm이 선택되었다.

 

기존 DES 는 64bit의 block을 반으로 쪼개어 라운드마다 일부만 암호화하고 나머지는 그대로 넘기는 방식으로 암호화를 하는 Feistal cipher였는데 이는 전체를 한번에 암호화 한다는 특징을 갖는다. 따라서 진행되는 라운드수도 DES(16라운드)에 비해 적다.

 

Block Size : 128bit 

Key Length : 128,192,256로 블록사이즈와 별개다. 

총 10~14라운드를 가지고 있는데 라운드마다 4개의 function 3 Layer를 가지고 있다. 

1. Bytesub layer : 주어진 128bit의 블록을 1byte단위 (8bit)로 치환한다. (표를 기반으로 함)

2. ShiftRow Layer : 행별로 지정된 값만큼 shift연산을 수행함

3. MixColumn Layer : 표를 기반으로 열단위로 섞어주는 연산(shift,xor)을 진행함

4. AddRoundKey Layer : 라운드에 해당되는 key로 XOR 연산을 수행함.

 

 

Modes of Operation for Dealing Mutiple Blocks

자, 이러한 암호화 방식은 알겠고 그것보다 중요한 것은 암호화된 다수의 블록을 어떻게 운용하는지가 더 중요한 문제이다.

블록을 누가 가로채거나했을때 어떻게 처리할지와 같은 운용에 대한 고민이 필요한데 다음과 같은 이슈들이 있다.

1. 다수의 블록을 어떻게 암호화할지?

2. 블록마다 새로운 키를 만들어야할지?

3. 블록끼리 서로 독립적으로 할지, 의존성있게 설정할지?

4. 남는 블록은 어떻게 처리할지?

 

이런 이슈를 기반으로 다양한 모드들이 존재한다.

 

1. ECB : Electronic CodeBook

2. CBC : Cipher Block Chain 

3. CTR : Counter Mode 

4. CFB / OFB : Cipher/Output Feedback Mode

5. GCM : Galois Counter Mode 

 

 

ECB : Electronic CodeBook

각 블록끼리 앞/뒤 상관없이 완전 독립적으로 암호화를 진행한다. Key는 동일하지만 각 블록간의 연관성을 두지 않고 각각 암호화한다.

 

문제 : 동일한 key를 사용하기에 동일한 단어에 대해서 동일한 결과를 얻게 된다.

즉, 같은 평문에 같은 암호문이 나와 평문과 암호문의 결과 분포가 같아진다는 문제가 발생하고 이를 바탕으로 원문을 유추할 수 있다는 문제가 발생한다.

 

이를 보완하기 위해선 어떻게 해야할까?

우선 블록마다 Key값을 다르게 해야한다. 

1. Random key를 블록마다 생성

2. 앞 block의 무언가를 별첨소스(freshness)로 포함시켜 다음 블록을 암호화하면 되지 않을까?

---> CBC의 등장이다.

 

CBC : Cipher Block Chainging

우선 초기 랜덤 벡터 RND가 주어진다. 해당 값을 C0로 하고 이 값과 P1을 XOR 연산 후 Key로 암호화한다.

이후 얻게 되는 결과 C1과 다시 P1을 XOR 연산하고 동일한 key로 암호화를 진행한다.

 

 

이렇게 되면 같은 평문에 대해서 동일한 키를 사용해도 이전 블록의 영향력 때문에 같은 결과가 나오지 않는다.

 

따라서, CBC를 통해 앞에서 살폈던 이슈인 같은 평문에 대해 같은 결과를 얻게되는 이슈를 해결할 수 있었다. 

 

또한 CBC를 하면 오류를 복구하기 쉽다는 장점도 존재한다. 

 

 

C1이 깨진 결과가 C2, C3, 키에 영향을 주지 않기에 실제로는 가까운 2개정도의 블록에만 영향을 주고 그 이후에는 영향을 주지 않는다는 특징을 가진다.

 

또한 CBC를 수정해 MAC으로 활용해 무결성 확인이 가능하다.

송신자가 CBC를 통해 암호화한 마지막 블록Cn과 평문P을 보낸다. 

송신자와 같은 Key를 공유한 수신자는 송신자가 보낸 평문을 CBC 방식으로 계산하여 마지막 블록 Cn을 얻는다.

 

수신자는 송신자가 보낸 Cn과 자신이 계산한 값이 맞는지를 확인하여 중간에 내용이 변하였는지를 확인할 수 있다.

 

CTR : Counter Mode

CBC 방식과 비슷..하나 앞에서 전달 받는 Feedback이 없다. 즉, 블록이 서로 종속적이지 않다.

 

1. block마다 번호 Counter가 주어진다. 해당 카운터는 일정 Offset을 기준으로 증가하며 해당 Nonce가 이 암호화에 Randomness를 부여한다.

2. 1에서 구한 값과 Key를 암호화한다.

3. 해당 결과와 PlainText를 XOR연산을 해서 CipherText를 얻는다.

 

각 블록마다 해당 작업을 진행하는데, 앞 블록에서의 결과가 뒷블록을 암호화하는데 영향을 주지 않으므로 병렬처리가 가능하다.

해당 방법은 다음과 같은 장점이 있어 일반적으로 많이 쓰이는 방법이다.

1. 암/복호화 구조가 똑같아 구현이 쉽다.

2. Counter를 활용해 블록의 순서를 찾을 수 있기 때문에 임의의 순서로 블록을 보내도 상관없다.

3. Conter가 앞블록과 상관없이 존재해 병렬처리가 가능하다! 

 

 

CFB : Cipher Feedback Mode

CBC와 매우 유사하나 freshness를 주는 부분이 CipherText이다. 계산된 CipherText와 key가 암호화 연산이 된 후 평문과 XOR 연산을 통해 다음 블록 암호화를 진행한다.

 

즉, Cipher가 Feedback된다! 

 

 

OFM : Output Feedback Mode

1. IV와 key를 암호화한다.

2. 1의 결과를 다음 암호화에 활용한다. Output feedback

3. 1의 결과와 평문을 XOR연산해 CipherText를 만든다.

 

암호화의 출력을 다시 입력으로 사용한다.

 

GCM : Galois Counter Mode

갈루아필드 GF란?

유한체의 집합으로 2^128을 주로 의미하며, 유한체 내에서의 원소로 덧셈, 곱셈등의 연산을 진행하고 그 결과 또한 유한체 내에 존재하는 것을 의미함.

 

AEAD : Autenticated Encryption with Associated Data

관련 데이터를 통해 암호화로 인증하는 방식. 암호화에서 기밀성을 만족하고 인증을 통해 무결성을 만족한다.

그러나, 무결성과 기밀성을 만족하는것은 쉬운일이 아니다. 평문만으로 암호화를 진행할때에는 무결성과 기밀성을 확보하기 어렵다. 따라서, 추가적인 a의 데이터를 활용해 무결성 / 기밀성을 보장한다.

 

GCM : 갈루아 필드내에서 Counter Mode 방식을 활용해 암호화와 인증을 구현하는 방식

 

등장이유 ?
기존에 사용하던 CBC의 단점 때문인데 CBC는 대량의 블럭을 암호화 하는데 비효율적이었다. 

 

GCM은 Galois Field내에서의 counter 모드를 적절히 응용했다. 따라서, 유한체내에서 병렬적인 처리가 가능해 높은 처리량을 갖는다는 장점이 있다. 

위의 그림과 같이 암호화/인증을 동시에 제공하며 높은 처리율을 갖는 방식이다.

 

 

Q&A

1. CBC에서 Automatically Recovery가 발생하는 이유는 C1이 깨져도 C2가 P3을 복호화하는데 영향을 주지 않았기 때문인가?

2. CFM에서는 암호를 복호하할때 Automatically한 recovery가 발생하지 않는가? 

3. CBC MAC에서는 Cn과 평문만을 전달하는가? 

4. AEAD에서 평문만으로 기밀성/무결성을 만족하기가 힘든이유는..?