블록 암호

현대 블록 암호

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

 

- 확산 : 평문의 통계적 성질을 암호문 전반에 퍼뜨려 암호문과 평문 사이의 관계를 숨긴다. 

- 혼돈 : 암호문과 키 사이의 관계를 숨긴다.

 

1) P-박스 (Permutation box)

P-박스는 전치 암호를 병렬적으로 수행한다. P-박스는 단순 P-박스, 확장 P-박스, 축소 P-박스라는 세 가지 종류의 P-박스가 있다.

축소 P-박스는 n 비트를 입력받아 m 비트를 출력하는 박스로서 n>m을 만족한다. 비트를 치환하는 동시에 다음 단계를 위한 비트의 수를 줄이고자 할 때 사용한다.

확장 P-박스는 n 비트를 입력받아 m 비트를 출력하는 박스로서 n<m을 만족한다. 비트를 치환하는 동시에 다음 단계의 비트 양을 증가시킬 때 사용한다.

단순 P-박스는 단순히 비트 치환만 시행한다.

 

단순 P-박스는 비트 전치만 시행하므로 입력 비트와 출력 비트가 1:1 관계이기에 역함수가 존재하지만, 축소 P-박스와 확장 P-박스는 1:1 관계가 아니므로 역함수가 존재하지 않는다.

 

2) S-박스 (Substitution box)

S-박스는 치환 암호의 축소 모형으로 생각할 수 있다. 입력과 출력의 개수가 달라도 되며 이로 인해 역함수가 존재할 수도, 존재하지 않을 수도 있다.

S-박스는 대치(substitution), XOR 연산, Shift 연산, 바꾸기(Swap), 나누기(Split), 결합(Combine) 연산을 수행한다.

 

+ 라운드(Rounds) : 확산과 혼돈을 만족하기 위해 P-박스와 S-박스, 기타 구성 요소의 결합을 의미하는 반복적 합성 암호를 사용한다. 이때 반복적 합성 암호를 라운드라고 한다.

 

두 가지 종류의 합성 암호

• Feistel 구조

Feistel 구조는 3라운드 이상, 짝수 라운드로 구성된다. 역변환이 가능하며 두 번의 수행만으로 블록 간 완전한 확산이 이루어진다. Feistel 암호 방식의 강도를 결정짓는 요소는 평문 블록의 길이, 키 K의 길이, 라운드 수 이다.

충분한 안정성을 보장받기 위해서 평문 블로그이 길이는 최소 64비트 이상(128비트 이상 권장), 키 K의 길이는 128비트, 라운드 수는 16회 이상을 권장하고 있다. 복호화 과정은 암호화 과정과 동일하며 키 순서만 바뀐다.

 

Feistel 구조에서는 입력 n 비트를 두 개의 블록 L,R 으로 나눈다.

그 후 L 블록에는 R 블록을 라운드키 K와 라운드 함수에 대입한 결과를 XOR 연산한다. R 블록은 그대로 둔다.

다음으로는 Swap 과정을 수행한다. 연산된 L 블록과 일반 R 블록의 위치를 서로 바꾸어 다음 라운드의 R과 L 블록으로서 사용한다. 즉, L1 블록과 R1 블록이 각각 R2 블록과 L2 블록이 되는 것이다.

Round 2 에서는 L2 블록과 R2 블록에 위 과정을 그대로 수행하게 된다. 주의할 점은 마지막 라운드에서는 좌우 블록을 한 번 더 교환해야 한다.

 

Feistel 암호는 많은 블록 암호 알고리즘에서 이용되며 AES 최종 후보 중 3 개의 알고리즘 MARS, RC6, Twofish 에서 사용되고 있다. 다만 최종 선정된 Rijndael은 SPN 구조를 사용한다.

 

• SPN 구조 (Substitution-Permutation Network)

Feistel 네트워크는 함수를 여러 번 반복해서 사용하면 한 번 사용한 것보다 안전하다는 개념에서 유래되었고, SPN 구조는 여러 개의 함수를 중첩시키면 개별 함수로 이루어진 암호보다 안전하다는 Shannon의 이론에 근거하여 유래되었다.

영어명에서 볼 수 있듯이 치환 암호와 전치 암호를 중첩하여 사용한다.

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

 

블록 암호 공격

- 차분 분석 (Differential Cryptanalysis)

Biham과 Shamir에 의해 개발된 선택 평문 공격법(CPA)으로, 두 개의 평문 블록들의 비트 차이에 대하여 대응되는 암호문 블록들의 비트 차이를 이용하여 사용된 암호키를 찾아내는 방법이다.

블록 암호를 보면 입력되는 평문이 한 비트라도 달라지면 암호문은 전혀 다른 비트 패턴으로 변화하게 된다. (확산 성질)

따라서 이를 통해 암호문의 변화 형태를 조사하여 해독의 실마리를 얻으려는 해독 방법이다.

 

- 선형 분석 (Linear Cryptanalysis)

Matsui에 의해 개발된 기지평문 공격(KPA)의 한 종류로 알고리즘 내부의 비선형 구조를 적당히 선형화시켜 키를 찾는 방법이다. 암호화 과정에서 근사적 선형 관계식을 찾으면 이를 통해서 KPA -> CPA 공격을 수행할 수 있다.

 

- 전수공격법 (Exhaustive key search)

Diffie와 Hellman이 제안한 방법으로 암호화할 때 일어날 수 있는 모든 경우에 대하여 조사하는 방법이지만 일반적으로 사용하기는 힘들다.

 

- 통계적 분석 (Statistical analysis)

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

 

- 수학적 분석 (Mathematical analysis)

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