SE 03) 1. 현대 대칭키 암호

(1) 현대 블록 암호

 

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

 

   (A) 개요

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

     ② 공격 방지 암호를 제공하기 위해 현대의 블록 암호는 이동요소(shift), 교환요소(swap), 분할요소(split), 조합요소 뿐만 아니라 전치 장치(transposition, P-box)와 치환 장치(substitution, S-box)와 XOR연산 (exclusive-OR)의 조합으로 만들어진다.

 

 * 혼돈과 확산

  ⊙ 혼돈(confusion) : 암호문과 키의 상관관계를 숨김

  ⊙ 확산(diffusion) : 평문의 통계적 성질을 암호문 전반에 퍼뜨려 숨김

 

 * 유사 용어 정리

  ⊙ 대칭키 암호 = 관용 암호 = 공통키 암호 = 단일키 암호 = 비밀키 암호

  ⊙ 비대칭키 암호 = 공개키 암호

 

   (B) P-박스

    :: P-박스는 문자 단위로 암호화를 수행하였던 고전 전치 암호를 병렬적으로 수행한다. 현대 블록 암호에서는 단순(straight) P-박스, 확장(expansion) P-박스, 축소(compression) P-박스라는 세 가지 종류의 P-박스를 볼 수 있다. 

     ① 축소 P-박스

        ⊙ 축소 P-박스는 n비트를 입력 받아 m비트를 출력하는 P-박스로서 n>m을 만족한다. 입력 비트 중 특정 비트는 소실되어 출력되지 않는다.

        ⊙ 축소 P-박스는 비트를 치환하고 동시에 다음 단계를 위한 비트의 수를 줄이고자 할 때 사용한다.

     ② 확장 P-박스

        ⊙ 확장 P-박스는 n비트를 입력받아 m비트를 출력하는 P-박스로서 n<m을 만족한다. 입력 비트 중 특정 비트는 한 개 이상의 출력비트와 연결된다.

        ⊙ 확장 P-박스는 비트를 치환하고 동시에 다음 단계에서 비트의 양을 증가시키고자 할 때 사용한다.

     ③ 역함수의 존재성

        ⊙ 단순 P-박스는 역함수가 존재한다.

        ⊙ 축소 P-박스와 확장 P-박스는 역함수가 존재하지 않는다.

 

  2) S-박스

 

  3) 합성 암호 (Product Crphers)

 

   (A) 개요

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

 

   (B) 확산 (Diffusion)과 혼돈 (Confusion)

     ① Shannon이 도입한 합성 암호의 주된 개념은 설계된 블록 암호가 확산과 혼돈이라는 두 가지 중요한 성질을 갖도록 하는 것이다.

     ② 확산(diffusion)의 개념은 암호문과 평문 사이의 관계를 숨기는 것이다. 확산은 암호문에 대한 통계 테스트를 통하여 평문을 찾고자 하는 공격자를 좌절시킨다.

     ③ 혼돈(confusion)의 개념은 암호문과 키의 관계를 숨기는 것이다. 혼돈은 암호문을 이용하여 키를 찾고자 하는 공격자를 좌절시킨다. 다시 말하면, 키의 단일 비트가 변하면 암호문의 거의 모든 비트가 변한다.

 

   (C) 라운드 (Rounds)

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

 

 * 중요 체크

  - 확산은 암호문과 평ㅇ문 사이의 관계를 숨긴다.

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

  - 혼돈은 입력(평문과 암호화 키)이 복잡한 변환들을 거친다는 뜻이고, 확산은 그러한 변환들이 입력의 모든 비트에 동일하게 의존한다는 뜻이다. 개념적으로 혼돈은 깊이에 관한 것이고, 확산은 너비에 관한 것이다.

 

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

 

   (A) Feistel 암호

     ① 페이스텔 구조에서 네트워크라는 이름은 그 구성도가 그물을 짜는 것과 같이 교환되는 형태로 구성되어 있기 때문에 붙여진 것이다.

     ② Feistel* 암호 방식의 암호 강도를 결정 짓는 요소는 평문 블록의 길이, 키 K의 길이, 라운드의 수이다. 그러므로 충분한 안정성을 보장받기 위해서는 평문 블록의 길이는 64비트 이상, 키 K의 길이는 64비트 내외, 라운드 수는 16회 이상이어야 한다. 그러나 최근에는 128비트의 키 길이를 권장하고 있다.

     ③ Feistel 암호 방식의 복호화 과정은 암호화 과정과 동일하다. 복호화 과정의 입력은 암호문과 보조키 K(_i)의 입력 순서는 암호화 과정의 입력 순서와 반대가 된다. 즉, 복호화 과정의 첫 라운드에 K(_n-1), 마지막 라운드에 K(_1)의 보조키를 입력시킨다. (* _ < 아래 작은 글자)

 

 * Feistel 구조

  ⊙ 페이스텔 구조는 3라운드 이상이며, 짝수 라운드로 구성된다. 이러한 페이스텔 구조는 라운드 함수와 관계없이 역반환이 가능하며, 두 번의 수행으로 블록간의 완전한 확산(diffusion)이 이루어진다. 알고리즘의 수행속도가 빠르고, 하드웨어 및 소프트웨어구현이 용이하고, 아직 구조상에 문제점이 발견되고 있지 않는다는 장점을 지니고 있다.

  ⊙ 페이스텔 구조는 입력을 좌우 블록으로 분할하여 한 블록을 라운드 함수에 적용시킨 후의 출력 값을 다른 블록에 적용하는 과정을 좌우블록에 대해 반복적으로 시행하는 방식이다. 라운드 키가 역순으로 복호화 과정이 동일하고 라운드 함수에 대한 제약 조건이 없어 DES를 비롯한 대부분의 블록 암호에 채택되어 사용되고 있다.

 

   (B) Feistel 암호 특징 

     ① 페이스텔 구조에서 입력 n비트를 두 개의 블록 (L(_0),R(_0))으로 나누어 라운드 함수를 F, 라운드키를 K(_i)라 할 때, i번째 라운드 과정은 다음과 같다. 주의할 점은 최종 라운드에서는 좌우 블록을 한 번 더 교환해야 한다.

        ⊙ L(_i) = R(_i-1)

        ⊙ R(_i) = L(_i-1) ＋F(_i)(R(_i-1), K(_i)) ==== +는 원 안에 플러스

     ② 페이스텔 네트워크는 많은 블록 암호 알고리즘에서 이용되고 있다. AES 최종 후보로 남은 5개 중에 3개의 알고리즘(MARS, RC6, Twofish)에서 사용되고 있다. (단, AES로 최종 선정된 Rijndael은 사용 안함)

 

   (C) SPN 구조

     ① 대부분의 블록 암호는 라운드 함수를 반복적으로 적용하는 바업에 따라 크게 두 가지 형태로 구별되는데 바로 Suvstitution-permutation(SP) network와 Feistel 구조 이다.

     ② SP Network는 " 여러 개의 함수를 중첩하면 개별 함수로 이루어진 암호보다 안전하다. "는 Shannon의 이론에 근거하여 고전 암호의 일종인 Substitution Cipher와 Permutation Cipher를 중첩하는 형태로 개발한 암호이다.

     ③ 입력을 여러 개의 소블록으로 나누고 각 소블록을 S-box로 입력하여 대치(substitution) 시키고 S-box의 출력을 P-box로 전치(permutation)하는 과정을 반복하는 방식이다.

 

  5) 블록 암호에 대한 공격

 

   (A) 차분 분석 (차분 해독법, Differential Cryptanalysis)

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

     ② 즉, 블록 암호를 보면 입력되는 평문이 한 비트라도 달라지면 암호문은 전혀 다른 비트 패턴으로 변화하게 된다. 그래서 암호문의 변화 형태를 조사하여 해독의 실마리를 얻는 해독 방법이다.

 

   (B) 선형 분석 (선형 해독법, Linear Cryptanalysis)

     ① 1993년 마츠이(Matsui)에 의해 개발된 기지 평문 공격의 한 종류로 알고리즘 내부의 비선형 구조를 적당히 선형화시켜 키를 찾는 방법이다.

     ② 먼저 암호화 과정에서의 근사적 선형 관계식을 찾는 것을 목적으로 한다. 근사 선형 관계성을 찾았다면, 이를 통해 기지 평문 공격에서 Chosen Plaintext 공격을 수행할 수 있다.

 

   (C) 전수 공격법 (Exhaustive key search) 

     ① 1977년 Diffie와 Hellman이 제안한 방법으로 암호화할 때 일어날 수 있는 가능한 모든 경우에 대하여 조사하는 방법이며, 경우의 수가 적을 때는 가장 정확한 방법이지만, 일반적으로 경우의 수가 많은 경우에는 실현 불가능한 방법이다.

 

   (D) 통계적 분석 (Statistical analysis)

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

 

   (E) 수학적 분석 (Mathematical analysis)

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

 

(2) 현대 스트림 암호

 

  1) 개요

 

  2) 동기식 스트림 암호

 

   (A) 개요

     ① 암호문을 복호화하여 평문을 찾을 때 키 스트림과 암호문 사이에 동기가 필요한 동기식 스트림 암호 시스템은 키 스트림이 평문과 관계없이 생성되는 것으로 암호문에 들어있는 키스트림과 암호문의 독립성으로 인하여 인가자 이외의 불법 사용자에게 정보 유출의 가능성이 적다.

 

   (B) One-Time Pad 

     ① 동기식 스트림 암호 중에서 가장 간단하고 안전한 암호는 길버트 버냄에 의해 설계되고 특허화된 one-time pad이다. one-time pad* 암호는 암호화를 수행할 때마다 랜덤하게 선택된 키 스트림을 사용한다.

     ② 해독 불가능하다는 것이 샤논에 의해 1949년에 수학적으로 증명되었다. 일회용 패드는 무조건 안전하며 이론적으로 해독 불가능하다고 알려져 있다.

     ③ 암호화 알고리즘과 복호화 알고리즘은 각각 배타적 논리합 연산을 사용한다. 베타적 논리합 연산의 성질에 의해 암호화 알고리즘과 복호화 알고리즘은 서로 역관계이다. 이 암호에서 배타적 논리합 연산을 한 번에 한 비트씩 적용된다.

 

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

     ① one-time pad의 절충안은 귀환 시프트 레지스터(FSR)이다. FSR은 소프트웨어와 하드웨어 환경에서 모두 구현될 수 있지만, 하드웨어 구현이 더욱 용이하다.

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

 

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

     ① LFSR은 하드웨어로 쉽게 구현되며 모든 스트림 암호는 아니지만 많은 스트림 암호가 LFSR을 이용한다.

 

   (E) 비선형 귀환 시프트 레지스터 (NLFSR, Nonlinear feedback shift register)

     ① 주로 LFSR은 선형성 때문에 공격에 취약하다. NLFSR을 이용하여 LFSR보다 안전한 스트림 암호를 설계할 수 있다.

 

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

 

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

     ② 이 방식은 오류 정정의 기능을 포함할 수는 있지만, 키 스트림과 암호문의 종속성으로 인하여 해독되기 쉽다.

     ③ 블록 암호에서 다른 운영 모드를 생성하기 위해 사용되는 한 가지 방법인 CFB 모드 (cipher feedback mode)는 실제로 스트림 암호를 생성한다.