[정보보안기사] Part2-3 대칭키 암호

1. 현대 대칭키 암호

1) 현대 블록 암호의 구성요소

• 현대 블록 암호는 확산과 혼돈과 같은 성질을 만족시키기 위해 전치 요소(P-박스)와 치환 요소(S-박스) 그리고 그 밖의 구성 요소를 결합하여 설계된다.

(1) P-박스

• 문자 단위로 암호화를 수행했던 고전 전치 암호를 병력적으로 수행한다. 단순 P-박스, 확장 P-박스, 축소 P-박스가 있다.

① 축소 P-박스

• n비트를 입력받아 m비트를 출력하는 P-박스로 n > m을 만족한다.
• 입력 비트 중 특정 비트는 소실되어 출력되어 않는다.
• 치환하고 동시에 다음 단계를 위한 비트의 수를 줄일 때 사용한다. 

② 확장 P-박스

• n비트를 입력받아 m비트를 출력하는 P-박스로 n < m을 만족한다. 
• 입력 비트 중 특정 비트는 한 개 이상의 출력비트와 연결된다.
• 치환하고 동시에 다음 단계를 위한 비트의 수를 늘일때 사용한다. 

③ 역함수의 존재성

• 단순 P-박스는 역함수가 존재한다.
• 축소 P-박스, 확장 P-박스는 역함수가 존재하지 않는다.

(2) S-박스

 

① 입력과 출력의 개수가 달라도 된다. (입력 n비트와 출력 m비트가 같을 필요는 없다.)

② 역함수의 존재성

• S-박스는 역함수가 존재할 수도 있고, 존재하지 않을 수도 있다.
• 역함수가 존재하는 S-박스는 입력 비트와 출력 비트의 개수가 동일하다.

(3) 합성 암호(Product Ciphers)★

• Shannon은 합성 암호의 개념을 소개하였음. 합성 암호는 치환, 전치 그리고 그 밖의 구성요소를 결합한 복합적인 암호이다.

① 확산(Diffusion)과 혼돈(Confusion)★

• Shannon이 도입한 합성 암호의 주된 개념은 블록 암호가 확산과 혼돈이라는 두 개의 중요한 성질을 갖도록 하는 것이다.
• 확산(Diffusion) : 암호문과 평문 사이의 관계를 숨기는 것, 평문을 찾고자 하는 공격자를 좌절시킴
• 혼돈(Confusion) : 암호문과 키의 관계를 숨기는 것, 암호문을 이용하여 키를 찾고자 하는 공격자를 좌절시킴

② 라운드(Rounds)

• 확산과 혼돈은 각 반복이 S-박스, P-박스, 기타 구성 요소와 결합의 반복적 합성 암호를 사용하여 얻는다.
• 반복적으로 사용되는 합성 암호를 라운드(Round)라고 칭한다.

 

Shannon의 업적
확률론을 기초로 한 정보이론(Information Theory) 창시자
일회용 패드(One-Time Pad)의 안전성 증명
혼돈(Confusion)과 확산(Diffusion)을 정의

 

 (4) 두 가지 종류의 합성 암호★★★

 

① Feistel 암호

그물을 짜는 것과 같이 교환되는 형태로 구성되어 있어서 붙여진 이름이다.

암호 강도를 결정짓는 요소는 평문 블록의 길이, 키 K의 길이, 라운드의 수이다.

충분한 안전성을 보장받기 위해서는 평문 블록의 길이는 64비트 이상, 키 K의 길이 64비트 내외, 라운드 수는 16회 이상(최근에는 128비트의 키 길이를 권장)

복호화 과정과 암호화 과정이 동일하다.

② Feistel 암호 특징

최종 라운드에서는 좌우 블럭을 한 번 더 교환해야 한다.

AES 최종 후보로 남은 5개 중 3개(MARS, RC6, Twofish)에서 사용되고 있다.

③ SPN

라운드 함수를 반복적으로 적용하는 방법에 따라 Feistel구조, SPN(Substitution-Permutation Network) 구조로 구별된다.

입력을 여러 개의 소블록으로 나누고 각 소블록을 S-box로 입력하여 대치시키고 S-box의 출력을 P-box로 전치하는 과정을 반복한다.

 

대칭 블록 암호 구현★★
▶ 블록 크기(Block size) : 블록 길이가 크다는 것은 더 강한 보안을 의미함. 그러나 길이가 길면 암,복호화 속도가 떨어진다. 128비트의  
                                          블록 크기는 이 두 가지를 조화시키는 합리적인 크기이다.
▶ 키 길이(Key size) : 키 길이가 길다는 것은 더 강한 보안을 의미함. 그러나 길이가 길면 암,복호화 속도는 떨어진다. 보편적인 키 길이                                          
                                   는 128비트이다.
▶ 라운드 수(Number of rounds) : 단일 과정으로는 보안이 부족하지만 라운드 수를 증가시켜 여러 번 수행 시 보안을 강화할 수 있다
                                                        는 것이 Feistel 암호의 핵심, 전형적인 라운드 수는 16이다.
▶ 서브키 생성 알고리즘(Subkey generation algorithm) : 이 알고리즘이 복잡할수록 암호해독이 어려워진다.
▶ 라운드 함수(Round function) : 복잡하면 복잡할수록 암호해독이 어려워진다.

 

 

(5) 블록 암호에 대한 공격

① 차분 분석(Differential Cryptanalysis)

• 1990년 Biham과 Shamir에 의해 개발된 선택 평문 공격법, 두 개 평문 블록들의 비트 차이에 대하여 대응되는 암호문 블록들의 비트 차이를 이용하여 암호키를 찾아내는 방법

② 선형 분석(Linear Cryptanalysis)

• 1993년 Matsui에 의해 개발된 기지평문 공격, 비선형 구조를 선형화 시켜 키를 찾는 방법

③ 전수공격법(Exhaustive key search)

• 1997년 Diffie와 Hellman이 제안한 방법으로 암호화할 때 일어날 수 있는 가능한 모든 경우에 대하여 조사하는 방법, 경우의 수가 많으면 실현 불가능한 방법이다.

④ 통계적 분석(Statistical analysis)

• 암호문에 대한 평문의 각 단어별 빈도에 관한 자료 및 지금까지 알려진 모든 통계적인 자료를 이용하여 해독하는 방법

⑤ 수학적 분석(Mathematical analysis)

• 통계적인 방법을 포함하여 수학적 이론을 이용하여 해독하는 방법

 

2) 현대 스트림 암호

• 현대 스트림 암호에서 암호화와 복호화는 한 번에 r비트를 생성한다.
• 키 스트림을 어떻게 생성하는지가 현대 스트림 암호의 주된 관심사이다.
• 동기식, 비동기식 두 가지 종류로 분류된다.

 

※ 스트림 암호 설계시 고려사항

• 암호화의 연속은 긴 주기를 가져야 한다.
• 키 스트림은 진 난수 스트림과 최대한 비슷해야 한다. ( 1과 0의 개수가 거의 동일해야 한다.)
• 전사적 공격에 대응하기 위해서는 키가 충분히 길어야 한다. (키 길이는 128비트인 것이 바람직하다.)

(1) 동기식 스트림 암호★★

암호문을 복호화하여 평문을 찾을 때 키 스트림과 암호문 사이에 동기가 필요하다.

키스 트림과 암호문의 독립성으로 인해 인가자 외 불법 사용자에게 정보 유출 가능성이 적다.

 

① One-Time Pad

• 동기식 스트림 암호 중에서 가장 간단하고 안전하다.
• 길버트 버냄(Gilbert Vernam)에 의해 설계되었다.
• 암호화를 수행할 때마다 랜덤 하게 선택된 키 스트림을 사용한다.
• 해독 불가능하다는 것이 Shannon에 의해 1949년에 수학적으로 증명되어 무조건 안전하며, 이론적으로 해독 불가능하다.
• 암호화, 복호화 알고리즘은 배타적 논리합 연산을 사용하는데, 이 성질에 의해 각 알고리즘은 서로 역관계이다.

 

② 귀환 시프트 레지스터(FSR, Feedback Shift Register)

• One-Time Pad의 절충안이다.
• 소프트웨어, 하드웨어 환경에서 모두 구현 가능하지만, 하드웨어 구현이 용이하다.
• FSR은 시프트(Shift) 레지스터와 귀환(Feedback) 함수로 구성된다.

③ 선형 귀환 시프트 레지스터(LFSR, Linear Feedback Shift Register)

• 하드웨어로 쉽게 구현되며, 많은 스트림 암호가 LFSR을 이용한다.

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

• LFSR이 선형성 때문에 공격에 취약한 반면, NLFSR이 보다 안전한 스트림 암호를 설계할 수 있다.

(2) 비동기식 스트림 암호(자기 동기식 스트림 암호)

• 키 스트림이 평문 또는 암호문과 관계를 갖는 자기 동기식 스트림 암호 시스템은 전송 중 암호문의 비트가 손실 또는 변경되더라도 그 오류의 전파가 유한하게 된다.
• 오류 정정의 기능을 포함할 수 있지만, 키 스트림과 암호문의 종속성으로 인해 해독되기 쉽다.

 

2. DES(Data Encryption Standard)★★★

(1) 역사와 개관

• 미국 국립기술표준원(NIST)은 1973년 국가적으로 사용할 대칭키 암호 시스템의 제안요청서를 발표함. Lucifer 프로젝트의 수정판인 IBM의 제안이 DES로 채택되었고, DES는 1975년 3월 연방관보(Federal Register)에서 연방 정보처리기준(FIPS)의 초안으로 공표되었다.
• DES는 발표된 이후 가장 널리 사용되는 대칭키 블록 암호가 되었고, 미국 국립기술표준원은 DES를 세번 반복하는 3중 DES의 사용을 권고하는 새로운 표준을 발표했다.
• 평문의 길이는 64비트, 키의 길이는 56비트이다. 이 보다 긴 평문은 64비트 블록으로 나눈다.
• DES의 구조는 Feistel 네트워크의 변형된 형태이다.
• 라운드 횟수는 16회며, 56비트짜리 원래 키로부터 16개의 서브키를 생성하고 각 라운드에서 사용한다.
• DES의 복호화과정은 근본적으로 암호화 과정과 동일하다.

(2) DES의 구조

• 암호화 과정은 2개의 전치(P-박스)와 16개의 Feistel 라운드 함수로 구성된다. 2개의 P-박스 중 하나는 초기 전치(Initial permutation), 다른 하나는 최종 전치(final permutation)라고 한다.
• 각 라우드는 라운드 키 생성기에 의해 암호키로부터 생성된 48비트 라운드 키를 사용한다.

 

① 라운드 함수

• DES는 16번의 라운드 함수를 사용한다.
• DES의 각 라운드 함수는 Feistel 암호로 되어 있다.
• 이전 라운드 함수의 출력 값 L(i-1)과 R(i-1)을 입력으로 받아, 다음 라운드에 입력으로 전송될 L(i)과 R(i)를 생성한다.
• 각 라운드에는 혼합기(mixer)와 교환기(swapper)라는 2개의 암호 요소가 있다.

② DES 함수

• DES 함수란 라운드 함수에 사용된 f(R(i-1), K(i))를 말한다.
• 32비트 출력값을 산출하기 위해 가장 오른쪽 32비트(R(i-1))에 48비트 키를 적용한다.
• DES 함수는 확장 P-박스, 키 XOR, 8개의 S-박스 그리고 단순 P-박스의 총 4개 부분으로 구성되어 있다.

 

③ 암호화 알고리즘과 복호화 알고리즘

• 혼합기와 교환기를 사용하여 16라운드 암호화 알고리즘과 복호화 알고리즘을 만들 수 있다.
• 라운드 키들이 역순으로 적용되어야 한다.
• 즉 암호화 과정에서는 1라운드 = K1 , 16라운드 = K16 복호화 과정에서는 1라운드 = K16 , 16라운드 = K1을 사용한다.

 

④ 키 생성

• 라운드 키 생성(round-key generator)은 56비트 암호키로부터 16개의 48비트 라운드 키를 만들어 낸다.
• 암호화 키는 64비트 키로 주어지고, 이 중 8비트는 패리티 비트로 키 생성과정 전에 제거된다.

 

(3) DES 분석

1) 설계 기준

① S-박스

• 각 라운드에서 다음 라운드까지 혼돈을 만족하도록 설계되었다.
• 비선형 함수이다.
• 입력값의 한 비트를 바꾸면, 출력 값에서는 두 비트 이상 바뀐다.

② P-박스

• 단순 P-박스(32 → 32bit), 확장 P-박스(32 → 48bit)가 있고, 이 2개는 비트들을 동시에 확산시킨다.

2) DES의 취약점

• DES는 56비트 키를 사용하여 개발 당시에는 전사 공격을 감행할 수 없을 정도로 큰 수였지만, 계산 능력이 놀랍도록 발전한 현대에는 더 이상 전사 공격에 안전하지 못하다.
• 컴퓨터 성능 발전으로 해독에 걸리는 시간이 점차 짧아져 지금은 중요 정보의 암호화에는 적용할 수 없는 상태가 되었다.

 

(4) 다중 DES★★

1) 3중 DES 개요

• 두 가지 버전이 있다. 두개의 키를 갖는 3중 DES와 세 개의 키를 갖는 3중 DES이다.

2) 3중 DES 현황

• 3중 DES는 처리 속도는 빠르지 않다. 새로운 용도로 사용하는 경우는 드물다.
• 현재 우리나라에서는 3DES를 표준으로 정하여 사용하고 있지 않다.
• 1999년 9월에 정보통신단체표준(TTA)에서 블록 암호 SEED를 국가 표준으로 정하였다.
• 학계, 연구소, 정부기관으로 구성되어 공동으로 개발한 블록 암호 ARIA가 2004년 산업자원부의 인증을 획득하여 현재 사용하고 있다.

3) 두 개의 키를 갖는 3중 DES

• 두 개의 키 k1과 k2만을 사용한다.
• 첫 번째, 세 번째 단계에서 k1을 사용하고 두 번째 단계에서 k2를 사용한다.
• 암호화 과정의 중간 단계에서 복호화 알고리즘을 사용하고, 복호화 과정에서 DES의 암호화 알고리즘을 사용한다.

4) 세 개의 키를 갖는 3중 DES

• 두 개의 키를 갖는 3중 DES에 대한 기지평문공격 가능성 때문에 세 개의 키를 갖는 3중 DES를 사용한다.
• PGP와 같은 응용 프로그램에서 사용되고 있다.
• 3DES의 복호화는 암호화의 역이 된다. 암호화(암호화 → 복호화 → 암호화) , 복호화(복호화 → 암호화 → 복호화)

5) DES와의 호환성

• 3중 DES에서 모든 키를 동일하게 하면 보통의 DES와 같아진다.
• 과거에 DES로 암호화된 암호문은 3 DES를 사용하여 복호화할 수 있다.
• 즉, 3DES는 DES에 대한 상호 호환성을 갖고 있다.

구분	DES	3중 DES	AES
평문 블록 크기(bits)	64	64	128
암호문 블록 크기(bits)	64	64	128
키 크기(bits)	56	112 or 168	128, 192 or 256