사자자리
[암호학] 블록 암호: DES 본문
DES(Data Encryption Standard)
- 미국의 국가 안보국(National Security Agency, NSA)에서 IBM의 루시퍼 알고리즘을 개량하여 만든 대칭키 암호
- 루시퍼에서 128비트 키를 사용했던 것과 달리 키 길이를 56비트로 줄였고, 내부에서 사용하는 알고리즘도 일부 변경했다.
- 일각에서 NSA가 도감청을 위해 DES에 백도어를 숨겨놓았다는 의혹을 제기하기도 했지만, 미국 국립표준기술연구소(National Institute of Standards and Technology, NIST)는 DES를 1976년부터 2002년까지 표준 블록 암호로 인정했다. 현대에는 DES에 대한 공격 기법이 많이 연구되어 DES를 더 이상 블록 암호의 표준으로 사용하지 않는다.
백도어(Backdoor)
- 시스템을 쉽게 장악할 수 있도록 만들어진 비밀 통로
- 해커가 시스템을 장악하고 나중을 위해 백도어를 남겨두기도 하지만,
- 제품의 설계자가 사용자를 해킹하려고 백도어를 심어서 출시하는 경우도 드물게 존재한다.
DES의 구조
- 8바이트(64비트)를 한 블록으로 하는 블록 암호
- 전체 구조
- 초기 순열(IP, Initial Permutation)
- 최종 순열(FP, Final Permutation)
- 페이스텔(Feistel) 구조의 16 라운드
- 키 생성 함수(Key Generation): 각 라운드에 사용되는 48비트의 키를 생성
곱 암호(Product Cipher)
- DES는 혼돈 성질을 만족하기 위해 치환(Substitution)을, 확산 성질을 만족하기 위해 순열(Permutation)을 사용한다.
- 치환과 순열은 매우 단순한 연산이므로, 이들을 평문에 한 번 적용한다고 해서 암호학적 효과를 기대할 수 없다.
- 그러나 이들을 여러 번 교차해서 반복 적용하면, 혼돈과 확산 성질을 모두 만족하게 된다.
- 곱 암호: 치환과 순열 같은 단순한 연산들로 한 라운드를 구성하고, 각 라운드를 여러 번 반복하여 암호학적 안전성을 확보하는 암호
페이스텔(Feistel) 구조
- DES에서 라운드 함수를 적용하는 전체 과정은 페이스텔 구조를 이루고 있다.
- 페이스텔 구조를 따르는 DES는
- 입력으로 들어온 블록을 동일한 길이의 왼쪽 블록 L과 오른쪽 블록 R로 나눈다.
- 각 라운드마다 오른쪽 블록은 어떠한 처리도 없이 다음 라운드의 왼쪽 블록으로 입력된다.
- 왼쪽 블록은 오른쪽 블록에 라운드 함수 F를 적용한 결과와 xor되어 다음 라운드의 오른쪽 블록으로 입력된다.
- 2번(오른쪽 블록은 어떠한 처리도 없음) 특성으로 인해, 페이스텔 암호는 비페이스텔 암호화 같은 안전성을 갖기 위해 2배 정도 라운드를 사용해야 하는 단점이 있다.
- 블록 암호는 평문을 복호화할 수 있어야하므로, 일반적으로 암호화를 구성하는 각 함수들의 역함수가 존재한다.
- 그러나 페이스텔 구조를 사용하면 F가 복호화 과정에서 ⊕로 상쇄되므로 역함수가 존재하지 않아도 된다.
- 또한 암호화와 복호화의 구조가 동일하므로, 암호화에 사용한 라운드 키를 역순으로 입력하면 복호화가 이뤄진다.
DES의 과정
Step 1 초기 순열
Step 2 라운드 함수
Step 3 최종 순열
초기 순열과 최종 순열
- DES는 시작할 때 초기 순열(IP)을, 마지막에 최종 순열(FP)을 수행한다.
- 초기 순열과 최종 순열은 정해진 테이블을 이용하여 64비트 입력을 비트 단위로 전치한다.
- 테이블의 n번째 값이 m일 때, 출력의 n번째 비트는 입력의 m번째 비트가 된다.
- 초기 순열은 초기 순열 테이블(IPT)을, 최종 순열은 최종 순열 테이블(FPT)을 이용한다.
- 초기 순열과 최종 순열은 서로 역관계에 있다.
- 임의의 64비트 데이터에 초기 순열을 적용하고, 최종 순열을 적용하면 입력값이 그대로 출력된다.
라운드 함수
- 라운드 함수 F에는 오른쪽 블록만 입력되므로, 입력의 길이는 32비트이다.
- 라운드 함수의 구조
- 확장 순열(Expansion P-Box)
- 라운드 키 결합(XOR)
- 치환 테이블(S-Box)
- 고정 순열(Straight P-Box)
1. 확장 순열(Expansion P-Box)
- 확장 순열은 입력을 비트 단위로 전치하는 동시에, 전체 길이를 48비트로 확장한다.
- 이 과정에서 32비트의 입력값을 4비트씩 8개의 부분으로 나누고, 테이블을 참조하여 각각을 6비트로 확장한다.
- 이 과정은 테이블만 다를 뿐, 초기 순열과 최종 순열과 같은 방식으로 이뤄진다.
2. 라운드 키 결합(XOR)
- 확장 순열로 나온 출력을 라운드 키 K와 xor하는 것
3. 치환 테이블(S-Box, Substitution-Box)
- S-Box는 라운드 키 결합에서 출력된 48비트 결과값을 32비트로 축소한다.
- S-Box는 4개의 행과 16개의 열로 이루어진 표를 사용한다. 표의 각 값은 4비트로 표현되는 수이다.
- S-Box가 적용되는 과정
- 입력을 6비트씩 8개의 부분으로 나눈다.
- 6비트 중 1번째와 6번째 비트로 행을 결정하고, 나머지 4개의 비트로 열을 결정한다.
- S-Box의 표에서 행과 열을 참조하여 값을 반환한다. DES에서는 6비트로 자른 부분마다 다른 S-Box를 사용한다.
4. 고정 순열(Straight P-Box)
- S-Box로 길이를 축소하고 나면, 고정 순열로 다시 비트 단위 전치가 이뤄진다.
- 이 과정은 다른 순열 과정들과 같다.
키 생성 함수(Key Scheduling)
- 64비트의 입력을 받아 각 라운드에 필요한 48비트 라운드 키를 생성하는 함수
- 키 생성 함수의 구조
- 패리티 비트 제거(Parity Bit Drop)
- 쉬프트(Shift)
- 압축 순열(Compression P-Box)
패리티 비트(Parity Bit)
- 오류를 탐지하는 간단한 방법 하나는 각 비트 패턴 안의 1의 개수를 홀수 개가 되도록 조작하고, 1의 개수가 짝수 개인 비트 패턴이 발견될 경우 오류가 발생한 것으로 판단하는 것이다. 오류가 발생한 것을 확인한 수신자는 손상되지 않은 데이터를 얻기 위해 재전송을 요구할 수 있다.
- 이를 구현하기 위한 쉬운 방법은 기존 비트 패턴에 패리티 비트라는 여분 비트를 추가하는 것이다. 기존 비트 패턴의 1의 개수가 짝수 개이면 1을 배정하여 홀수 개를 만들고, 기존 비트 패턴의 1의 개수가 홀수 개이면 0을 배정하여 홀수 개를 유지한다. 이런 패리티 체계를 홀수 패리티(Odd Parity)라고 하며, 이와 반대로 각 패턴이 짝수 개의 1을 포함하도록 하는 짝수 패리티(Even Parity) 체계도 있다.
- 패리티 비트는 사용하기 간단하지만 한계가 있다. 홀수 패리티 체계의 비트 패턴에서 짝수 개의 비트에 오류가 발생하였을 경우, 1의 개수는 여전히 홀수 개일 것이며, 따라서 패리티 체계는 오류를 탐지하지 못한다.
1. 패리티 비트 제거(Parity Bit Drop)
- 입력에서 패리티 비트를 제거하고, 남은 56비트에 순열을 적용하는 과정
- DES의 비밀키에서 각 바이트의 가장 오른쪽 비트는 홀수 패리티 비트(Odd Parity Bit)이다.
2. 쉬프트(Shift)
- 입력을 왼쪽 28비트와 오른쪽 28비트로 나누어, 각각을 1비트나 2비트만큼 왼쪽으로 순환 쉬프트(Cyclic Shift)하는 과정
- 1, 2, 9, 16 라운드에서는 1비트, 나머지 라운드에서는 2비트만큼 쉬프트한다.
- 왼쪽으로 1비트 순환: 10101111 → 01011111
- 왼쪽으로 2비트 순환: 10101111 → 10111110
3. 압축 순열(Compression P-Box)
- 56비트의 입력을 48비트 길이로 압축하는 과정
- 수행 방법은 앞서 셜명한 순열들과 같다.
DES의 응용: 다중 DES
- 연산 능력이 증대되고 관련된 공격 기법이 연구됨으로 인해, DES는 더 이상 안전한 암호 시스템이 아니다.
- 다중 DES: 서로 다른 키를 사용하는 DES 모듈을 여러 개 이어붙여서 DES의 약점을 보완한 암호 시스템
- 이중 DES(Double DES, 2-DES)는 112비트, 삼중 DES(Triple DES, 3-DES)는 168비트의 키를 사용한다.
- 삼중 DES에서 중간에 암호화가 아닌 복호화를 하는 이유
- 이중 DES나 삼중 DES는 늘어난 키 길이만큼 단일 DES보다 안전할 것 같지만, 중간 일치 공격으로 인해 안전성을 획기적으로 높이지는 못한다.
- 이중 DES는 단일 DES와 비슷한 안전성을 갖고 있으며, 삼중 DES는 키 길이를 2배로 늘리는 효과밖에 얻지 못한다.
중간 일치 공격(Meet-in-the-Middle Attack)
- 공격자가 어떤 평문 p와, p를 암호화한 암호문 c를 알 수 있을 때, 수행할 수 있는 공격
- 이중 DES에 중간 일치 공격을 수행할 때, 연산량에 유의미한 영향을 미치는 것은 1과 2에서 수행되는 2^56번의 DES 암복호화이다. 3에서의 후보키 생성과정은 퀵정렬과 이분탐색으로 빠르게 수행할 수 있으며, 4, 5, 6의 과정은 반복의 횟수가 많지 않다. 따라서 공격자가 어떤 평문 p와, p를 암호화한 암호문 c를 알 수 있을 때, 이중 DES의 안전성은 DES의 두 배 정도에 그친다. 이는 이중 DES에 기대되는, 112비트 키를 사용하는 DES의 안전성에 비해 한참 부족하다.
- 삼중 DES(3-DES)는 이 공격을 적용해면 112비트 키를 사용하는 DES 이상의 안전성을 가진다고 알려져 있습니다. 따라서 다중 DES를 사용할 때는 일반적으로 삼중 DES를 사용합니다.
마치며
Q1. DES의 라운드 수는 [ ]이다.
A1. 16
Q2. DES에 입력되는 키의 길이는 64비트인데, 패리티 비트를 제거하면 실제로 사용되는 키의 길이는 [ ] 비트이다.
A2. 56
Q3. DES는 라운드마다 다른 S-Box를 사용한다.
A3. X
#!/usr/bin/python3
# Name: des.py
from Crypto.Cipher import DES
# Initial/Final Permutation Table
IPT = [58, 50, 42, 34, 26, 18, 10, 2,
60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6,
64, 56, 48, 40, 32, 24, 16, 8,
57, 49, 41, 33, 25, 17, 9, 1,
59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5,
63, 55, 47, 39, 31, 23, 15, 7]
FPT = [40, 8, 48, 16, 56, 24, 64, 32,
39, 7, 47, 15, 55, 23, 63, 31,
38, 6, 46, 14, 54, 22, 62, 30,
37, 5, 45, 13, 53, 21, 61, 29,
36, 4, 44, 12, 52, 20, 60, 28,
35, 3, 43, 11, 51, 19, 59, 27,
34, 2, 42, 10, 50, 18, 58, 26,
33, 1, 41, 9, 49, 17, 57, 25]
# Expansion P-Box Table
EPT = [32, 1, 2, 3, 4, 5,
4, 5, 6, 7, 8, 9,
8, 9, 10, 11, 12, 13,
12, 13, 14, 15, 16, 17,
16, 17, 18, 19, 20, 21,
20, 21, 22, 23, 24, 25,
24, 25, 26, 27, 28, 29,
28, 29, 30, 31, 32, 1]
# S-Boxs
S = [
# S1
[
[14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7],
[0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8],
[4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0],
[15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13]
],
# S2
[
[15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10],
[3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5],
[0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15],
[13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9],
],
# S3
[
[10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8],
[13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1],
[13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7],
[1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12],
],
# S4
[
[7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15],
[13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9],
[10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4],
[3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14],
],
# S5
[
[2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9],
[14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6],
[4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14],
[11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3],
],
# S6
[
[12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11],
[10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8],
[9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6],
[4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13],
],
# S7
[
[4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1],
[13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6],
[1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2],
[6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12],
],
# S8
[
[13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7],
[1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2],
[7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8],
[2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11],
]
]
# Straight P-Box Table
SPT = [16, 7, 20, 21, 29, 12, 28, 17,
1, 15, 23, 26, 5, 18, 31, 10,
2, 8, 24, 14, 32, 27, 3, 9,
19, 13, 30, 6, 22, 11, 4, 25]
# Parity Bit Drop Table
PBDT = [57, 49, 41, 33, 25, 17, 9,
1, 58, 50, 42, 34, 26, 18,
10, 2, 59, 51, 43, 35, 27,
19, 11, 3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15,
7, 62, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29,
21, 13, 5, 28, 20, 12, 4]
# Compression P-Box Table
CPBT = [14, 17, 11, 24, 1, 5, 3, 28,
15, 6, 21, 10, 23, 19, 12, 4,
26, 8, 16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55, 30, 40,
51, 45, 33, 48, 44, 49, 39, 56,
34, 53, 46, 42, 50, 36, 29, 32]
def plain2bitstring(plain: str):
return "".join(format(ord(c), "0>8b") for c in plain)
def plain2bitarray(plain: str):
bitstring = plain2bitstring(plain)
encoded = bytearray([int(b) for b in bitstring])
return encoded
def bitarray2plain(bitarray: bytearray):
bitstring = bitarray2bitstring(bitarray)
encoded = "".join([chr(int(bitstring[i*8:i*8+8], 2))
for i in range(len(bitstring)//8)])
return encoded
def bitarray2bitstring(bitarray: bytearray):
return "".join([str(b) for b in bitarray])
def bitarray2bytes(bitarray: bytearray):
bitstring = bitarray2bitstring(bitarray)
return bytes([int(bitstring[8*i:8*i+8], 2) for i in range(len(bitstring)//8)])
def permutation(block: bytearray, table: list[int], outlen: int):
permutated = bytearray(outlen)
for n in range(len(table)):
m = table[n]-1
permutated[n] = block[m]
return permutated
def substitution(block: bytearray, table: list[int]):
row = (block[0] << 1) + block[5]
column = (block[1] << 3) + (block[2] << 2) + (block[3] << 1) + block[4]
val = table[row][column]
binary = bin(val)[2:].zfill(4)
return bytearray([int(b) for b in binary])
def key_scheduling(key: bytearray):
shift_1 = [0, 1, 8, 15]
round_keys = []
# Drop parity bit
parity_erased = permutation(key, PBDT, 56)
left = parity_erased[:28]
right = parity_erased[28:]
# Shift
for i in range(16):
if i in shift_1:
left = left[1:] + left[0:1]
right = right[1:] + right[0:1]
else:
left = left[2:] + left[:2]
right = right[2:] + right[:2]
# Compression
round_keys.append(permutation(left+right, CPBT, 48))
return round_keys
plain = "DEScrypt"
key = "DreamCry"
# Key scheduling
round_keys = key_scheduling(plain2bitarray(key))
bitarray = plain2bitarray(plain)
# Initial permutation
initial_permutated = permutation(bitarray, IPT, 64)
# Feistel
left_half = initial_permutated[:32]
right_half = initial_permutated[32:]
# Iterate 16 rounds
for round in range(16):
# Expansion
expansioned = permutation(right_half, EPT, 48)
# XOR with round key
for bit_idx in range(48):
expansioned[bit_idx] ^= round_keys[round][bit_idx]
# Substitution
substituted = bytearray(32)
for block_idx in range(8):
substituted[4*block_idx:4*block_idx+4] = substitution(expansioned[6*block_idx:6*block_idx+6], S[block_idx])
# Straight
straighted = permutation(substituted, SPT, 32)
tmp = bytearray(right_half)
for i in range(32):
right_half[i] = left_half[i] ^ straighted[i]
left_half = tmp
# Final permutation
encrypted = permutation(right_half+left_half, FPT, 64)
encrypted = bitarray2bytes(encrypted)
assert(encrypted == DES.new(b"DreamCry", DES.MODE_ECB).encrypt("DEScrypt"))'Dreamhack > 암호학 Cryptography' 카테고리의 다른 글
| [암호학] 블록 암호: 운영 모드 (0) | 2022.08.07 |
|---|---|
| [암호학] 블록 암호: AES (0) | 2022.08.06 |
| [암호학] 현대 암호 (0) | 2022.07.31 |
| [암호학] 고전 암호 (0) | 2022.07.31 |
| [암호학] 배타적 논리합과 합동식 (0) | 2022.07.24 |
