[Cryptography] DES(Data Encryption Standard)

DES(Data Encryption Standard)

Modern Block Cipher

- 고전 암호에서 Substitution과 Transposition이 결합되어 사용되면서 Modern Cipher로 넘어옴

- 암호화 알고리즘에서 넓게 사용

- 기밀성, 인증

- DES가 Modern block cipher에 속함

Block Cipher vs Stream Cipher

Block Cipher

- plaintext를 특정 크기의 block으로 나눠 암호화, 복호화 수행

- block 단위로 수행

- stream cipher보다는 속도가 느림

- 현재는 block cipher가 더 많이 쓰임

- Encryption Algorithm과 Decryption Algorithm은 같을 수도 있고 다를 수도 있음(DES는 같음)

- 원래의 block cipher는 entry = n bit 일 때, n*(2^n) 만큼의 table이 필요함

Stream Cipher

- plaintext의 연속적인 스트림을 순차적으로 key stream과 xor하여 암호화, 복호화 수행

- bit, byte 단위로 수행

- 암호화 키와 복호화 키가 같고 키로 key stream을 생성

- block cipher보다 속도가 빠름    

Confusion, Diffusion

Confusion(혼돈)

- plaintext와 ciphertext 사이의 관계를 숨겨 ciphertext와 key 간의 관계를 알기 어렵게 함

- Substitution 암호화

Diffusion(확산)

- ciphertext와 plaintext 사이의 관계를 알기 어렵게 함

- Permutation 암호화

Feistel Structure

S-P network

- Shannon이 고안한 substituion-permutation network

- substitution(S-Box)

- permutation(P-Box)

- Confusion, Diffusion 제공

Feistel Cipher Structure

1. 특징

- 16개의 round로 구성

- 16개의 subkey로 구성

- 암호화 시, 64bit의 plaintext를 반으로 나누어 32bit씩 총 16 round 수행

- 오른쪽 반은 permutation 수행, 왼쪽 반은 substituion 수행

2. 암호화/복호화

1) 암호화

- LEn = REn-1

- REn = F(Kn, REn-1) xor LEn-1

2) 복호화

- REn-1 = LEn

- LEn-1 = REn xor F(Kn, LEn = REn-1)

Data Encryption Standard(DES)

Lucifer Cipher

- DES전에 사용되던 block cipher

- 64bit block과 128 bit key 사용

DES

- 64bit block과 56 bit key 사용

- Feistel structure 사용

- Initial Permutation 후 feistel 구조와 같이 16 round 수행

- 마지막에 32bit swap 후, Initial Permutation 역수행

1. Initial Permutation(IP)

- 처음 64 bit block의 input는 IP를 거침

2. F(Function)

 - 32 bit의 R half와 48 bit의 subkey를 인자로 가짐

- 함수 내에서 E-box(Expansion Permutation)을 거쳐 32 bit의 R half를 48 bit로 확장

1) S-Box

- 확장된 48 bit의 R half와 48 bit의 subkey를 xor하여 S-box의 INPUT으로 사용

- 8개의 S-Box 사용

- Input : 6bit , Output : 4bit

- 6개의 bit(b1 b2 b3 b4 b5 b6) 중 b1, b6을 행으로 b2 b3 b4 b5을 열로 사용

ex) b = 101011

- b1 = 1, b6 = 1, b1,b6 = 11(3) -> 3행

- b2 = 0, b3 = 1, b4 = 0, b5 = 1, b2,b3,b4,b5 = 0101(5) -> 5열

2) P-box

- S-box 8개의 output(32bit)을 P-box의 input으로 사용

- P-box(Input : 32 bit, output : 32 bit)

3. Permuted Choice 1

- 64bit의 key에서 8 bit parity를 제외한 나머지 56bit에 permutation을 수행해 56bit를 선택

- input : 64 bit

- output : 56 bit

4. Permuted Choice 2

- Permuted Choice 1 수행 후, 각 round에서 left circular shift를 수행하고 permuted choice 2 수행

- input : 56 bit

- output : 48 bit

5. DES Avalanche(쇄도 효과)

- Avalanche : 평문의 작은 차이가 암호문에서 많은 차이를 야기

- DES는 평문에서 하나의 bit 차이만 나더라도 암호문에서 많은 bit 차이를 만듬

- diffusion 만족

- 가장 이상적인 Avalanche : 반 개의 차이

Strength of DES

Timing Attack

- 계산을 하는데 소요되는 시간을 측정하는 것을 기반으로 하는 공격

- 데이터의 이동 시간을 측정하여 통계적 분석을 통해 비밀키를 알아낼 수 있음

Differential Cryptanalysis

- 선택 평문 공격(CPA : Chosen Plaintext Attack)을 가정하여 사용

- Feistel cipher를 공격하기 위한 통계적 방법

- 입력 값에 따른 출력 값의 변화를 이용하여 공격

- 평문 P1과 비슷한 평문 P2를 이용하여 암호화한 결과 C1, C2를 구하고 (P1 xor P2) -> dP와 (C1 xor C2) -> dC 쌍을 이용

- 취약할 경우, dP에 대해 특정 dC가 나타날 확률이 더 커짐

- 큰 차이가 나타나는 쌍을 찾은 경우, round에 사용된 subkey를 찾을 수 있음

- plaintext xor 쌍을 이용하여 원하는 ciphertext xor 쌍이 나올 때 까지 반복

Linear Cryptanalysis

- 암호화 과정에서의 근사적 선형 관계식을 찾는 것을 목적으로 함

- 통계학적 성질 사용

Multi DES

Double DES(2-DES)

- DES의 형태를 유지하며 두 개의 Key로 두 번의 암호화 수행

- Encryption : E(E(P, K1), K2)

- Decryption : D(D(C,K2), K1)

- Key : 56bit * 2 --> Space : (2^56)^2 = 2^112

- 112bit의 key를 가진 DES와 같은 역할

1. Meet in the middle Attack

- 1차 Encryption의 결과인 X를 통해 암호 해독

- E(P, K1) = x = D(C, K2) 를 만족하는 값을 찾아내는 공격

Triple DES(TDES)

1. 2 KEY TDES

- 2개의 key를 이용하여 3번의 암호화 진행

- Key1 = Key3

- Key size = 112 bits, Key Space : 2^112

2. 3 KEY TDES

- 3개의 key를 이용하여 3번의 암호화 진행

- Key1 != Key2 != Key3

- Key size = 168 bits, Key Space : 2^112

DES-X

- C = E((K1 xor P), K) xor K2

- Key Size : 184 bits(56 + 2*64), Key Space : 2^120