라운드(round), DES

<DES Function>
- DES의 핵심은 DES함수이다
- DES함수란 라운드 함수에 사용된 f(Rl-1, Kl)를 기리킨다
- DES함수는 32비트 출력 값을 산출하기 위하여 가장 오른쪽의 32비트(Rl-1)에 48비트를 적용한다
- DES는 2^56개의 원소로 이루어진 키 집합을 의미한다


<확장 P-박스(Expansion P-box)>
- Rl-1는 32비트 입력 값이고, Kl는 48비트 라운드 키이기 때문에
  우선 32비트 Rl-1을 48비트 값으로 확장할 필요가 있다



<Whitener(XOR)>
- 확장치환을 적용한 이후에, DES는 확장치환의 출력 값에 라운드 키를 XOR 연산한다
- 이 때, 확장치환의 출력 값과 라운드 키 값 모두 48비트이다
- 라운드 키는 이 연산에서만 사용된다



<S-Boxes>
- S-박스는 실제로 섞어주는 역할을 수행한다
  즉, 혼돈(confusion)역할을 수행한다(암호문과 키의 문을 숨긴다)

- DES는 각각 6비트 입력 값과 4비트 출력 값을 갖는 8개의 S-박스를 사용한다



<단순 치환(Straight Permutation)>
- mixer와 swapper를 사용함으로써 16라운드를 갖는 암호
  알고리즘과 복호 알고리즘(reverse cipher)을 만들 수 있다

- 이 목표를 달성하기 위한 하나의 접근 방법은
  마지막 라운드(라운드 16) 함수를 나머지 라운드 함수들과 다르게 만드는 것이다
  마지막 라운드 함수에는 swapper가 없고 mixer만 존재한다
  즉, 첫 번째 접근 방법에서 마지막 라운드는 swapper가 없다



<대체 접근방법(Alternativie Approach)>
- 16번째 라운드에는 swapper가 없다

- 이 경우, 암호 알고리즘의 마지막 라운드에 사용된 mixer
  부분과 복호 알고리즘의 첫 번째 라운드에 사용된 mixer
  부분이 서로 잘 맞아야 한다



<키 생성(Key Generation)>
- 라운드 키 생성기(round-key generator)는 56비트 암호키로부터 16개의 48비트 라운드키를 만들어 낸다



<DES ANALYSIS>
- 비평가들은 DES를 분석하기 위하여 강력한 돋보기를 사용해왔다
- 블록암호가 지녀야 할 몇 가지 성질들에 대한 안전도(strength)를 측정하기 위해 여러 시도가 있었다




<성질(Properties)>
- 블록암호가 지녀야 할 두 가지 성질로
  쇄도효과(avalache effect)와 완비성(completeness)이 있다


<완비성 효과(Completeness effect)>
- 완비성 효과는 암호문의 각 비트는 평문의 비티들에 의존할 필요가 있다는 것을 의미한다
- DES에서 P-박스와 S-박스에 의해 야기된 확산(diffusion)과 혼돈(confusion)은 매우 강한 완비성 효과를 보여준다



<S-Boxes>
- S-박스는 각 라운드로부터 그 다음 라운드까지 혼돈과 확산 성질을 만족하게끔 설계되었다



<P-Boxes>
- P-박스는 동시에 비트들을 확산(diffusion)시킨다



<Number of Rounds>
- DES는 각 라운드가 Feistel 암호인 16개의 라운드로 구성된다
- 8라운드 이후에는 각 암호문이 모든 평문과 비트와 키 비트의 함수임이 증명되었다
  즉, 평문을 입력으로 받아 암호문으로 출력하는 랜덤 함수이다




<키 보수(Key Complement)>
- 사이즈가 인 키 집합에서 원소들 중 반은 나머지 반의 보수(complement)로 표현될 수 있다
- 키의 보수는 키의 각 비트를 거꾸로한다
  (0을 1로 바꾸거나 1을 0으로 바꾸는 것)으로써 만들어진다
- Q : 키 보수는 암호해독의 작업을 간단하게 하는가? 
  A : 그렇다
  - Eve는 키의 전수조사 공격을 수행하기 위해서 가능한 후보키들 중의 절반(가지)만을 이용하면 된다

- 키와 평문에 모두 보수를 취하여 암호화하면, 원래의 암호문의 보수인 암호문을 얻게 된다
- Eve는 모든 개의 가능한 키들을 모두 검사하지 않고, 절반만 검사하고 나머지 키에 대해서는 보수 성질을 이용하여 값을 얻을 수 있다



<다중 DES(Multiple DES)>
- DES에 대한 주요 비판은 키 길이에 있다
- 현재 이용 가능한 기술력과 병렬 처리의 가능성을 이용하면 DES에 대한 전수조사 공격은 실행 가능하다
  - 하나의 해결책은 DES를 폐기하고 새로운 알고리즘을 설계
  - 두 번째 해결책은 여러 개의 키를 가지고 DES를 여러 번 암호화 하는 것이다

- 모든 가능한 출력과 입력을 대응시키는 대치(substitution)은 군(Group)이 된다

- 첫 번째 접근방법은 이중 DES(2DES)를 사용하는 것이다
  - 중간일치공격(Meet-in-the-Middle Attack)
    - 얼핏 보기에, 이중 DES는 키를 탐색하기 위한 탐색 횟수가 2^56번(하나의 DES에 대응)에서
      2^122번(두 개의 DES에 대응)으로 증가하는 것 처럼 보이지만 
      중간일치공격과 같은 기지평문공격을 사용하면 2^122가 아닌 2^57로 약간의 향상만 있을뿐임을 증명할 수 있다



<3개의 키를 갖는 삼중 DES(Triple DES with Three Keys)>
- 2개의 키를 갖는 삼중 DES에 대한 기지평문공격의 가능성 때문에
  어떤 응용프로그램은 3개의 키를 갖는 삼중 DES를 사용한다

- 3개의 키를 갖는 삼중 DES는 PGP와 같은 많은 응용프로그램에서 사용되고 있다



<DES의 안전성(Security of DES)>
- 블록암호 DES의 경우 여러 가지 안전성 분석 방법들이 정밀하게 시행되었다
- 시도된 공격들 중에서, 전수조사 공격, 차분 공격(differential attack), 선형 공격(linear attack)과 같은 세 가지 공격 방법이 중요하다



<전수조사 공격(Brute-Force Attack)>
- DES는 짧은 길이의 암호키를 사용한다는 취약성이 있다
- 키 보수 성질과 같은 취약성을 이용하면 
  2^55번의 DES암호화 과정을 통해서 키를 찾을 수 있다



<차분 공격(Differential Cryptanalysis)>
- DES의 설계자들은 차분공격에 대하여 이미 알고 있는 상태에서 S-박스를 설계했었다
- DES가 이런 종류의 공격에 특히 안전성을 갖도록 라운드 수를 16으로 선택했다는 것이 후에 밝혀졌다



<선형 공격(Linear Crytanalysis)>
- 선형공격은 차분공격보다 나중에 개발되었다
- 아마도 이런 종류의 공격은 DES의 설계자들에게 알려지지 않았기 때문에 DES는 차분공격보다 선형공격에 더 취약하다
- S-박스는 선형공격에 대해 좋은 저항성을 가지지 않는다
- 그래서 DES를 2^43개의 기지평문 쌍을 가지고 깰 수 있다
- 하지만, 실제적인 관점에서 그렇게 많은 평문 쌍을 얻는 것은 쉽지 않다