02. 대칭키 암호

현대 대칭키 암호

확산과 혼돈

- 확산(diffusion) : 암호문과 평문 사이의 관계를 숨기는 것

- 혼돈(confusion) : 암호문과 키의 관계를 숨기는 것

P-박스와 S-박스

- P-박스

확산을 유지하면서 비트를 전치하는데 사용되는 기법이다. 단순 P-박스는 역삼수가 존재하고 축소 P-박스, 확장 P-박스는 역함수가 존재하지 않는다.

축소 P-박스 : n 비트를 입력받아 m비트를 출력하는 P-박스 (n > m). 입력 비트 중 특정 비트는 소실되어 출력되지 않는다.

확장 P-박스 : n 비트를 입력받아 m비트를 출력하는 P-박스 (n < m). 비트의 양을 증가 시키고자 할 때 사용한다.

단순 P-박스 : n 비트를 입력받아 m비트를 출력하는 P-박스 (n = m).

 

- S-박스

S-박스는 입력값과 출력값 사이의 관계가 대수적 관계로 정의되는 치환 암호이다. 입력 비트 수 n과 출력 비트 수 m이 반드시 같을 필요는 없다.

Feistel와 SPN 암호 구조

왼쪽 Feistel 구조, 오른쪽 SPN 구조 출처 : An introduction to Block Cipher Cryptanalysis

- Feistel 구조

그물을 짜는 것과 같이 교환되는 형태로 구성된 암호 구조이다. 암호와 과정과 복호화 과정이 동일하다. DES와 SEED가 대표적인 예이다.

 

- SPN 구조

여러개의 함수를 중첩하는 형태로 구성된 암호 구조이다. 입력을 여러개의 소블록으로 나누고 대치, 전치 과정을 반복한다. AES, ARIA가 대표적인 예이다.

블록 암호에 대한 공격

차분 분석 : 선택 평문 공격 기법으로 두개의 평문 블록의 비트 차이와 암호문 블록의 비트 차이의 관계를 분석하여 암호키를 찾아내는 방법이다.

선형 분석 : 기지 평문 공격의 한 종류로 알고리즘 내부의 비선형 구조의 함수에 선형적 특성이 나타나는 확률을 분석하여 암호키를 찾아내는 방법이다.

전수공격법 : 암호화할 때 일어날 수 있는 가능한 모든 경우에 대해서 조사하는 방법이다. 경우의 수가 많은 경우에는 실현 불가능하다.

통계적 분석 : 암호문에 대한 평문의 각 단어별 빈도에 관한 자료와 더불어 지금까지 알려진 모든 통계적인 자료를 이용하여 해독하는 방법이다.

수학적 분석 : 통계적인 방법과 수학적인 이론을 이용하여 해독하는 방법이다.

현대 스트림 암호

한번에 1비트 혹은 1바이트의 데이터 흐름을 순차적으로 처리해가는 대칭키 암호 알고리즘이다. 안전한 스트림 암호를 구현하기 위해선 키 스트림의 주기, 키 스트림이 난수열과 비슷한지, 키 길이가 충분히 긴지 고려해야 한다.

동기식 스트림 암호

- OTP (One Time Pad)

OTP 암호는 암호화를 수행할 때마다 램던하게 선택된 키 스트림을 사용한다. 해독이 불가능하다는 것이 1949년 샤논에 의해 증명됨에 따라 이론적으로 해독 불가능하다고 알려져 있다. 평문에 램덤한 수열을 XOR연산 하여 암호화한다.

 

- 귀환 시프트 레지스터 (Feedback Shift Register)

쉬프트 레지스터와 귀환 함수로 구성된다.

 

- 선형 귀환 시프트 레지스터 (LFSR, linear feedback shift reigster)

귀환 함수에 맞춰 한 비트가 연산되고 그 결과 값이 키 스트림으로 사용된다. n개의 레지스터가 존재할 때, 최대 2^n-1 의 주기를 가진다.

 

- 비선형 귀환 쉬프트 레지스터(NLFSR, Nonlinear Feedback Shift Register)

LFSR은 선형성 때문에 공격에 취약하다.

비동기식 스트림 암호

키 스트림이 평문 혹은 암호문으로부터 함수 관계에 의해 생성되는 방식이다. 전송 중 암호문의 비트가 손실 또는 변경되더라도 그 오류의 전파가 유한하다.

---

 

DES (Data Encryption Standard)

DES 구조

DES는 1973년 NIST에서 발명한 Feistel 구조 블록 암호이다. 평문 또는 키의 작은 변화가 암호문에 큰 변화를 만드는 쇄도 효과가 매우 크다. 따라서 암호문으로부터 평문을 추론하기가 매우 어렵다. DES는 블록의 크기는 64비트, 키의 길이는 56비트, 라운드 횟수는 16회로 구성된다. 56비트 키로부터 16개의 라운드 키를 생성하여 각 라운드에 사용한다.

 

DES 전체구조. 출처 : 위키백과

 

DES 분석

- 설계 기준

S-박스 : 비선형 함수로 한 비트라도 바뀐다면 출력값이 두 비트 이상 바뀌어 혼돈(confusion)을 만족하도록 설계되었다.

P-박스 : 32비트→32비트의 단순 P-박스와 32비트→48비트 확장 P-박스를 활용하여 확산(diffusion)시킨다.

 

F함수, 출처 : 위키백과

 

- DES의 취약점

전사 공격 : DES는 56비트 키를 사용하므로 최대 키 공간의 키는 2^56이다. 현재는 계산 능력이 발전하여 전사 공격에 안전하지 않다.

다중 DES

전사 공격에 안전하지 않다는 점을 보완하기 위하여 DES를 중첩하여 사용하여 키 공간을 늘리는 방법을 사용하였다. 두 개의 키를 갖는 3중 DES는 처음과 마지막에 진행되는 DES에 K1을 사용하고, 중간 DES에 K2를 사용한다. 세 개의 키를 갖는 3중 DES는 각 DES에 다른 키를 사용한다.

---

AES

AES 구조

1997년 NIST에서 DES를 대체하기 위한 암호 알고리즘을 공모하였고 AES가 최종 선택안으로 선정되었다. AES는 SPN 구조 블록 암호로 블록의 크기는 128비트, 키의 길이는 128, 192, 256 비트이고 라운드 횟수는 각각 10, 12, 14회로 구성된다. 키로부터 라운드 키를 생성하여 각 라운드에 사용한다.

DES 전체구조. 출처 : 드림핵

AES 분석

SubBytes : S-박스를 적용하여 바이트를 치환한다.

ShiftRows : 행 단위로 순환 시프트를 수행한다.

MixColumns : 열 단위로 혼합한다.

AddRoundKey : 라운드 키와 XOR 연산을 한다.

---

기타 대칭키 암호 알고리즘

구분	개발 국가	개발 연도	특징	블록 크기	키의 길이	라운드 수
DES	미국	1972	NIST 표준으로 공표	64	56	16
IDEA	유럽	1990	PGP 채택	64	128	8
RC5	미국	1994	알고리즘이 간단, 속도가 빠름	32,64,128	0-2040	1-256
AES	벨기에	1998	현재 가장 널리 사용되는 암호 알고리즘	128	128,192,256	10,12,14
SEED	한국	1999	한국 표준 블록 암호 알고리즘	128	128,256	16,24
ARIA	한국	2003	국가 표준 암호 알고리즘	128	128,192,256	12,14,16
HIGHT	한국	2006	경량화된 블록 암호 알고리즘	64	128	32
LEA	한국	2013	고속, 경량 블록 암호 알고리즘	128	128,192,256	24,28,32

 

---

현대 대칭키암호를 이용한 암호화 기법

모드	장점	단점	비고
ECB	- 각 블록이 독립적으로 암호화되어 병렬 처리 가능	- 동일한 평문 블록은 동일한 암호문을 생성 (패턴 노출 위험)	- 가장 간단한 모드 - 패턴이 중요한 데이터에 부적합
CBC	- 동일한 평문 블록이라도 서로 다른 암호문 생성 - 초기화 벡터(IV)로 안전성 증가	- 암호화는 병렬 처리 불가 (순차적으로 처리됨) - 작은 오류가 다음 블록에 영향	- 초기화 벡터(IV)가 필요 - 데이터 무결성에 사용 가능
CFB	- 스트림 암호처럼 동작 - 암호화와 복호화 알고리즘 동일	- 암호화는 병렬 처리 불가 - 오류 전파 발생 (한 블록 오류가 다음 블록에 영향)	- 데이터 양이 적을 때 유용 - 부분적 전송에 적합
OFB	- 스트림 암호처럼 동작 - 오류가 전파되지 않음	- 병렬 처리 불가 - 동기화 문제 발생 가능	- 오류가 전파되지 않아 안정적 - 주기성 문제 가능
CTR	- 병렬 처리 가능 - 암호화와 복호화 알고리즘 동일 - 스트림 암호처럼 동작	- 초기화 벡터와 카운터 관리 필요 - 동기화 오류 발생 가능	- 가장 유연하고 효율적 - 고속 통신에 적합