Block Cipher

미노·2025년 6월 12일

Computer Network

목록 보기

21/23

Block Cipher

Plain text를 block 단위로 나누어 암호화 수행
Plain text + Key -Decryption→ Cipher text

DES (Data Encryption Standard)

현재는 취약점이 드러나 사용되지 않는 기법
Plain text : 64 bit
Cipher text : 64 bit
Key : 56 bit + Parity : 8 bit ⇒ 64bit
- 56비트를 7비트로 나눔 → 8개의 parity bit

$K_{16}$ , key를 16번 넣음 → 15Round
페이스텔 네트워크 1Round 처리순서
1. Input을 $L_0$ (32bit), $R_0$ (32bit)로 나눈다. → Plain text가 64bit
2. $R_0$ 를 $R_1$ 에 대입 → 이는 향후 $L_1 \leftarrow R_1$
3. 대입 후 $R_0$ 는 라운드 함수 $f(R_0)$ 에 대입
4. 라운드 함수 $F$ 는 $R_0$ 과 키값인 $K_1$ 을 입력값으로 연산을 실행 → $f(R_0, K_1)$
5. $R_1 = L_0 \oplus f(R_0, K_1)$ , $L_1 = R_0$ 으로 사용
6. 1라운드 종료, 위 과정을 반복
DES는 symmetric key를 사용하기 때문에 특징이 있음
- 송신자, 수신자 둘 다 같은 key를 사용해야함

$f() \ function$

$f(R_{n}, k)$ 는 $R_{n+1}$ 을 만드는 함수
32비트의 $R_n$ 을 Expansion을 통해 48bit로 만든 후 table을 통해 다시 32bit로 줄임
6 X 8 TABLE로 값으로는 1~32만 있음 → R의 32bit를 48bit로 늘려줌

$s() \ function$

$f()$ 내에 있는 $s()$ 는 48bit에서 쪼개진 6bit를 4bit로 줄여줌
예시로 input block : 011011
- 첫 번째 비트와 마지막 비트는 Row number, 나머지 가운데 비트는 Column number를 의미함
- 즉, row num : 01 → 1 / col num : 1101 → 13 ⇒ 5 = 0101로 바뀜
Key schedule : 64bit의 main key를 라운드동안 돌릴 sub key로 변환하는 작업
- 64bit (58 + 6)의 key를 48bit의 sub key로 변환

Cryptanalysis of DES

Week Keys(64bit) : Week key는 DES의 16 라운드 암호화 과정에서 생성되는 서브키들이 반복되거나 동일한 값을 가지는 키임
이러한 week key는 암호를 쉽게 해독할 수 있어서 취약점이 드러남
- 01010101 01010101
- FEFEFEFE FEFEFEFE
Brute Force Attack : 모든 경우의 수를 대입해서 공격 $2^{56}$ (key space) → 해독 가능한 수준
- 현대에는 $2^{56}$ 의 경우의 수를 대입해서 공격하는 게 불가능하지 않음
Attack on DES
- Differential Cryptanalysis (차분해독법) :
  - 공격자가 Plain Text, Cipher Text 둘 다 알고 있을 때, 두 Text의 XOR연산을 통해 분포도를 파악한 다음 Key를 추출
- Linear Cryptanalysis (선형해독법) :
  - 공격자가 Plain Text, Cipher Text를 다량으로 모은 후, 이 둘의 관계를 해석해 경우의 수를 줄임
  - 기존 $2^{56}$ 이었던 경우의 수가 더욱 줄어들어 차후 Brute Force Attack을 통해 Key를 추출

AES (Advanced Encryption Standard)

Background

DES를 대체하기 위한 암호화 알모리즘 공모
- 조건
  - 무료
  - C, JAVA로 구현
  - 알고리즘 공개 → 표준화를 위함
  - 알고리즘 평가

Summary

Key size : 128, 192, 256 / 기존의 DES의 key size는 64
Block size : 128 / AES-128, AES-192, AES-256 모두 동일한 Block size를 가짐
Round 수 : 10, 12, 14 / Key size가 커질수록 많아짐
구조 :
- substitution-permutation network (치환-순열, 각 라운드마다 128비트 서브키)
- DES : 페이스텔 네트워크 (각 라운드마다 48비트 서브키)

AES : Cipher

Overall Procedure
각 라운드마다 네 개의 함수를 통해 서브키를 생성, 암호화 → 라운드를 다 돌면 Ciphertext완성
AES-128, AES-192, AES-256

key size와 Block size를 워드 단위로 표현
과정
AES-128 기준
state는 input text를 행렬로 변환한 것
한 라운드마다 네 개의 암호화 함수를 실행
- SubBytes() : 각 Byte를 s-box를 통해 대체함
  - Non-linear byte operation using s-box (substitution table) :
    
    $b' = Ab + C$
- ShiftRows() : 대체된 b’을 shift 연산을 통해 순환이동
  - R0 : 이동하지않음
  - R1 : 왼쪽으로 한 칸 이동
  - R2 : 왼쪽으로 두 칸 이동
  - R3 : 왼쪽으로 세 칸 이동
- MixColumns() : 열을 연산을 통해 대체하는 과정 / AES가 복잡해지는 특성을 갖게 하는 함수
  
  $s' = As$
- AddRoundKey() : 앞서 세 함수를 통해 복잡해진 행렬을 현재 키와 다시 연산을 진행하여 더욱 복잡하게 만드는 과정, AES-128은 이 과정을 10번 진행
  
  AES : Key expansion
- Cipher key를 이용하여 sub key를 생성
- AES-128의 경우, 초기키값 + 10번의 라운드동안 수행할 키 = 11개의 키가 필요
  - 각 sub key size : 128bit
  
  AES : Decipher
- InvShiftRows() $\to$ InvSubBytes() $\to$ AddRoundKey() $\to$ InvMixColumns()
- Encryption과 완벽한 역순이 아님
  
  InvShiftRows() : ShiftRow()의 역순으로 진행
  - R0 : 이동 X
  - R1 : 오른쪽으로 한 칸 이동
  - R2 : 오른쪽으로 두 칸 이동
  - R3 : 오른쪽으로 세 칸 이동
    
    InvSubBytes()
  - SubBytes()를 통해 대체된 행렬을 다시 되돌아가는 subtitution table을 이용
    
    InvMixColumns()
  - MixColumns()의 $s' = As$ 의 역행렬을 곱함
    $s = A^{-1}s'$