Ch4. Block Ciphers and the Data Encryption Standard(DES)

필요한 사전 지식: 2020/10/23 - [Computer Security] - [컴퓨터 보안] Classical Encryption Techniques

 

Symmetric encryption(대칭 암호)

• 현대 대칭 암호를 분류할 때, Stream ciphers와 Block ciphers 두 종류로 분류한다.
• Stream cipher
  • 가장 완벽한 암호: bit 단위로 plain text를 쪼개서, 그 plain text와 같은 길이의 랜덤 bit sequence를 key로 만들어, XOR 해 암호화하는 One-time pad 방식
    • 예: Vernam
    • 현실적으로는 이 방식을 안 씀. 왜냐하면, 그 plain text와 같은 길이의 key sequence를 안전하게 송수신자 사이에 공유해야 하는데, 이 정도의 channel이 있으면, 그냥 plain text를 보내는 게 낫지 않겠냐는 말이 있다.
  • Stream Cipher: Vernam cipher처럼 짧은 key를 사용하지만, one-time pad처럼 마치 랜덤해 보이는 key sequence를 사용. 이렇게 만들어진 sequence와 XOR해서 암호화.
  • key bit 생성하는 알고리즘을 key-stream generator 또는 bit-stream generator라고 부름.
    • 이는 deterministic한 알고리즘. 랜덤하지 않음
    • 특정 입력이 주어지면, 거기에 해당하는 출력을 줌 (같은 입력에는 같은 출력)
    • But, 제 3자가 볼 때는, 랜덤 하게 보여야 함. 제삼자가 볼 때 sequence가 예측되면 안 됨.
    • 짧은 generating key(seed value)에서 양쪽 사용자(송수신자)가 모두 bit-stream generator을 생성할 수 있도록 하는 deterministic한 알고리즘임.
    • 일부 sequence가 노출되도, 다음 sequence가 예측되면 안 됨.
• Block cipher
  • Symmetric encryption key(암호키)를 서로(송수신자) 공유하는 한다는 것은 Stream cipher와 같으나, 안전성을 달성하는 방식이 조금 다름
  • 안정성을 달성하는 2가지 접근 방식
    
    • Polyalphabetic cipher: 한 bit가 항상 같은 bit로 대체되는 게 아니라, 그때그때 다르게 대체하는 것
      • 이걸 극단적으로 안전하게 한 게 one-time pad임 
    • Polyalphabetic과 달리 여러 글자 별로 묶어서 한꺼번에 대응시키는 방법이 있는데, 이 것의 대표적인 방법으로 Playfair가 있다.
      • Playfair: 두 글자씩 짝지어서, 두 글자를 다른 두 글자로 대응시키는 방법
  • 한 글자씩 매칭 하는 것보다 playfair처럼 두 글자씩 매칭 했더니 통계적 수치가 줄어들었다. 이를 토대로 대응되는 크기가 클수록 통계가 무뎌지는 것을 확인할 수 있다.
  • 64 bits를 다른 64 bits로 대응시키는 것처럼 대응시키는 단위를 크게 해서, 그것에 대한 통계를 찾기 어렵게 됨. 이렇게 하는 multiple letter encryption을 하는 방식을 일반화하는 게 Block cipher이라고 한다.
    • 즉, plaintext를 bit 단위나 글자 단위로 보는 게 아니라 한 block으로 보는 것.
    • 그것을 통째로 대체시킴.
    • 현대 암호에서는 주로 64bits or 128 bits 사용

이러한 수많은 대응을 표로 정리해서 저장할 수는 없으니, 계산해서 값이 나오는 방식을 이용 

-> 이러한 대표적인 방법이 "Feistel Cipher"

 

 

Feistel cipher

• 암호 알고리즘을 설계하는 기법. Block Cipher의 일종
• Feistel cipher 기법으로 설계된 대표적인 암호 -> The Data Encryption Standard(DES)
• Block cipher에서 block 단위를 보통 128bit를 사용한다. 이때, plaintext를 ciphertext로 변환하는 규칙을 테이블로 작성하게 되면, $2^{128}$x128 bit만큼의 크기를 차지하게 된다. (하나의 테이블이)
  • 이렇게 저장하는 것은 불가능하므로 plaintext를 입력으로 받아서 ciphertext를 출력하는 일종의 함수를 만들어 사용한다.
  • 만약, 이 함수에서 연산 규칙이 유일하다면 안전하지 않다. -> 가능한 여러 테이블(($2^{128}$)!개) 중 한 개만 사용하는 것
  • 그래서, p를 c로 바꾸는 연산에 파라미터를 넣는다. 이 파라미터를 key라고 한다.
    • key에 따라, 같은 plaintext라도 다른 ciphertext가 나올 수 있다. 
    • key가 만약 128bit라면 $2^{128}$ 개의 종류가 있는 것
    • 이 key에 따라 내부 회로를 변화시킨다. 
    • 물론 이 경우 경우의 수가 $2^{128}$개뿐이다. 테이블 기록하는 방식일 때는 ($2^{128}$)! 개였지만
  • 이 함수를 어떻게 구성할 것인가?
    • 여러 개의 Substitution과 permutation의 조합으로 구성한다.

• RE가 F연산을 거쳐서 LE와 XOR한다 -> substitution 연산
• RE와 LE의 순서가 바뀐다. -> transposition 연산

 

Feistel Cipher: Decryption하는 방법

• Decrytion할 때, 역산을 역방향으로 하는 것이 아니라, input에 Ciphertext를 넣고, 순방향으로 돌리기만 하면 된다. ( subkey 순서는 역순)
• 그렇기 때문에, 각 round에서 일어나는 연산은 역연산이 불가능해도 괜찮다.

 

Single round of DES

<한 라운드에서 일어나는 연산>

 

1. Expansion & permuatation:

32 bits를 입력으로 받아 순서를 바꾸면서 48 bits를 만든다.

 

32 bits를 넣었는데 48bit가 된 이유?

-> 32 bits를 16 bits 두 개로 나누고, 하나는 한 번, 나머지 하나는 두 번 사용한다. 

-> 이러면서 위치를 바꿈

 

2. key와 XOR

 

3. Substitution & choice:

48 bits를 32 bits로 변환한다.

 

4. Permutation:

순서를 바꾼다.

 

 

 

 

Data Encryption Standard(DES)

• DES는 표준. 알고리즘은 Data Encryption Algorithm(DEA)
• 64 bits blocks(plaintext)을 56 bits key를 사용해서 암호화하는 구조
• Decryption 할 때, 역순으로 같은 연산 하면 된다. 

 

 

DES의 강점

• DES
  • 56 bits key: $2^56$ ≒ 7.2 x $10^26$ 공간 사용
  • (p, c) 쌍을 알 때, key를 아는데 걸리는 시간 -> 1.125 년
  • 공격자도 key가 56 bits인건 안다. 표준이니까
• Permutation cipher
  • 26! ≒ 4x$10^26$ 공간 사용
  • key 찾는데 걸리는 시간 -> 6.3 억년
• AES
  • 128 bits keys: $2^128$ ≒ 3.4 x $10^38$
  • key 찾는데 걸리는 시간 -> 5.3 x $10^21$

 

 

 

 

 

 

출처:

- [Cryptography and Network Security: Principles and Practices]

- ISLAB 강의 자료