대칭키 암호: 개념, 블록 암호, 파이스텔, SPN, 스트림 암호, DES, AES

1. 대칭키 암호의 개념

• 암호화와 복호화에 하나의 같은 비밀키를 사용하는 암호 방식

C = Ek(P)

P = Dk(P)


이때 E는 암호화 함수, D는 복호화 함수를 의미한다.

• 다양한 이름으로 불린다: 대칭키 암호, 비밀키 암호, 단일키 암호, 관용 암호

대칭키 암호는 블록암호화 스트림 암호로 나눌 수 있다.


먼저 블록 암호부터 살펴보자.

2. 블록 암호

개념

• 평분을 고정된 크기의 블록으로 나누어 각 블록마다 암호화 과정을 수행하여 블록 단위로 암호문을 얻는 대칭키 암호 방식

예를 들어 다음과 같이 하나의 평문을 4개의 블록으로 나눈뒤, 각 블록을 대칭키 암호 방식으로 각각 암호화한다.


여기서는 하나의 키를 이용하여 모든 블록을 암호화한다. 암호화된 각 블록을 다시 연결하면 원래 평문에 대한 암호문이 완성된다.

블록 암호 알고리즘의 구조

• 출력 블록의 각 비트는 입력 블록과 키의 모든 비트에 영향을 받는다
• 주로 단순한 함수를 반복적으로 적용함으로써 암호학적으로 강한 함수를 만든다
  • 라운드 함수: 반복되는 함수
  • 라운드 키: 라운드 함수에 작용하는 키
  • 키 스케줄: 키를 입력하여 라운드 키를 발생시키는 과정

1) 파이스텔 구조

파이스텔(Fiestel) 구조는 하나의 입력 블록을 분할하여 좌우 두 개의 블록으로 구분한 후 짝수 번의 라운드를 진행하는 구조이다. 이때 각 라운드의 출력 블록이 다음 라운드의 입력 블록이 된다.

스텝을 쉽게 생각해보면 1. 분할과정, 2. 변환과정, 3 혼합 및 반복 과정으로 볼 수 있다. 라운드를 거듭할 수록 보안성이 강화된다.

• 하나의 입력 블록을 분할하여 좌우 두 개의 블록으로 구분 후 짝수 번의 라운드를 진행
• 각 라운드의 출력 블록이 다음 라운드의 입력 블록이 됨
• i 번째 라운드 처리 과정

$$
L_i = R_{i-1}
$$

$$
R_i = L_{i-1} \oplus f(R_{i-1}, K_i)
$$

여기서 ( f )는 라운드 함수, ( K_i )는 라운드 키를 의미한다.

라운드 함수와 관계없이 역변환이 가능하며(즉, 라운드 키를 역순으로 적용한다는 점을 제외하면 암/복호화 과정이 같음), 두 번의 수행으로 블록 간의 완전한 확산이 이루어진다. 알고리즘 수행속도가 빠르고 하드웨어 및 소프트웨어 구현 용이, 아직 구조상 문제점이 발견되지 않았다는 장점이 있다.

DES, SEED 등 많은 블록 암호에 사용되었다.

2) SPN 구조

SPN(Substitution Permutation Network) 구조는 하나의 입력 블록을 여러 개의 소블록으로 나눈 후 라운드를 진행하는 구조이다. 한 라운드의 처리 과정을 살펴보면, 각 소블록을 S-box로 입력하여 치환(substitution)하고, S-box의 출력을 P-box로 전치(Permutation)하여 출력 블록을 생성한다.

한 블록의 크기가 8비트이고 네 개의 소블록으로 나누는 구조의 한 라운드를 살펴보면 다음과 같다.

• SPN 구조는 라운드 함수가 역변환이 가능해야 한다는 제약이 있다.
• 더 많은 병렬성을 제공하여 고속을 요구하는 최근의 추세에 부응한다.
• AES, ARIA 등 최근의 블록 암호에 사용되고 있다.

블록 암호의 사용 모드

1) 전자 코드 북 모드

• Electronic Code Book

• 암, 복호화시 병렬 처리 가능
• 암호문 블록의 오류가 다른 블록에 영향을 미치지 않음
• 동일한 평문 블록은 동일한 암호문 생성(패턴 분석 가능)

2) 암호 블록 연결 모드

• CBC: Cipher Block Chaining
• 생성한 암호문 블록이 다음 평문 블록에 영향을 미치게 암호화한다.
  -> 즉, 암호문 블록과 다음 평문 블록을 XOR한 후 암호화한다.

• 따라서 평문 블록 내용이 동일하더라도 서로 다른 암호문을 생성하게 된다.
• 대신 병렬 처리 불가능
• 암호화시 평문 블록 오류가 그 다음 모든 암호문에 영향 -> 메시지 인증에 사용된다.

3) 암호 피드백 모드

• Cipher FeedBack
• 초깃값 IV를 암호화한 값과 평문 블록을 XOR하여 암호문 블록을 생성하고, 그 암호문을 초깃값으로 하여 다시 암호화한 값과 평문 블록을 XOR 하여 암호문 블록을 반복하여 생성하는 방식
• 암호화시 특정 입력이 이후로 영향을 미친다. -> 메시지 인증에 사용

• 복호화 함수 필요 없음

4) 출력 피드백 모드

• OFB: Output FeedBack
• 초깃값 IV를 암호화하고 그 값을 다시 암호화하는 과정을 반복함으로써 생성된 수열과 평문 수열을 XOR하여 암호문을 생성하는 방식
  -> 스트림 암호처럼 사용

• 암호문 블록의 오류는 한 블록에만 영향을 미침 -> 영상이나 음성 같은 디지털 신호화된 아날로그 신호에 사용
• 복호화 함수 필요 없음

5) 카운터 모드

• CTR: CounTeR
• 초깃값 IV와 IV+1, IV+2, ...를 암호화하여 생성된 평문 수열을 XOR 하여 암호문을 생성하고, 그 암호문을 기초로 하여 다시 암호화한 값과 평문 블록을 XOR하여 암호문 블록을 반복하여 생성

• 병렬 처리 가능
• 오류 확산이 일어나지 않음
• 복호화 함수 필요 없음

3. 스트림 암호

개념

스트림 암호는 평문과 같은 길이의 키 스트림을 생성하여 평문과 키를 비트 단위로 XOR하여 암호무을 얻는 대칭키 암호 방식이다.

키 스트림 생성

임의의 길이의 평문이 주어지더라도 동일한 길이의 키 스트림을 생성해야 한다. 이렇게 생성되는 키 스트림은 규칙성이 없어 예측이 불가능한 랜덤 수열이어야 안전하다.

-> 의사 랜덤 (psedurandom) 수열 생성 필요성

예측이 어려우면서도 자동화된 생성이 가능해야 한다.

한 가지 예시는 선형 귀환 시프트 레지스트(LFSR: Linear Feedback Shift Register)이다. LSFR은 m비트의 초깃값을 이용하여 최대 2^m-1 비트의 주기를 갖는 키 스트림을 생성할 수 있는 방식이다. 즉, 직전 m개의 비트값을 선형 결합하여 새로운 한 비트값을 얻고, 다시 이 비트값을 포함한 직전 m개의 비트 값을 선형 결합하여 또 하나의 새로운 비특밧을 얻는 방식으로 키 스트림을 생성한다.

예를 들어, 3비트의 초기값을 사용하는 LFSR이 있다고 가정해 보자. 이 경우, 최대 (2^3-1) 즉, 7비트 길이의 주기를 갖는 키 스트림을 생성할 수 있다. LFSR의 작동 방식은 간단하다 이전 3개의 비트 값을 선형 결합하여 새로운 비트를 생성하고, 이 비트를 포함해 다시 다음 비트 값을 계산하는 과정을 반복한다.

LFSR의 예시

3비트 LFSR로 주기 7의 키 스트림을 생성하는 예시

초기 상태가 110일 경우, 이후 생성되는 비트 스트림은 다음과 같다.

1101001 1101001 1101001 1101001 ...

단, LFSR만으로는 비트 스트림이 결정적이고 패턴을 추적할 수 있기 때문에, 단독으로 사용하는 경우 쉽게 해독될 수 있다.

4. 대칭키 암호 알고리즘

• 대표적으로 DES와 AES
• 그밖에 IDEA(International Data Encryption Algorithm), SEED, CRYPTON, RC5, FEAL, MISTY, Skipjack, ARIA, LEA, RC4 등

DES

• 1977년 미국에서 데이터 암호 알고리즘의 표준으로 공표
• 블록 암호 알고리즘
  • 블록 크기: 64 bits
  • 키 길이: 56 bits
  • 파이스텔 구조: I6 라운드, 라운드 키 길이 48 bits
• 2001년 새로운 표준인 AES가 나오면서 DES는 표준의 자리를 물러남

TDEA

• DES를 3회 반복한다

• DES의 짧은 키 길이로 인한 안전성 문제 해결
• DES보다 3배 정도 느림

AES

• Advanced Encryption Standard
• DES를 대신하는 새로운 표준
• 블록 암호 알고리즘
  • 블록 크기: 128 bits
  • 키 길이: 128 bits, 192 bits, 256 bits 중 택일
  • SPN 구조

AES 구성

AES 암호화 과정

AES 암호화 과정은 몇 가지 기본 연산을 반복적으로 수행한다.

초기화와 키 추가 (AddRoundKey)

• AES 암호화는 첫 번째 라운드가 시작되기 전에 초기 키를 사용하여 데이터와의 XOR(배타적 논리합) 연산을 수행
• 이 단계에서 사용되는 키는 원본 키에서 파생되며, 이를 '라운드 키'라고 함
• 초기화 단계는 암호화할 데이터(평문)와 첫 번째 라운드 키의 XOR 연산으로 구성된다

주요 라운드

AES 암호화 과정은 데이터의 크기(블록 크기)와 키의 크기에 따라 라운드 수가 결정된다. 일반적으로 128비트 블록에 대해 10, 12, 또는 14 라운드를 수행한다.

1. SubBytes (서브 바이트 변환): 각 바이트를 특정 테이블(S-box)을 사용하여 다른 바이트로 치환하는 과정이다.
2. ShiftRows (행 이동): 각 행을 서로 다른 수의 칸만큼 순환 이동시킨다.
3. MixColumns (열 혼합): 각 열에 대해 특정 수학적 연산을 수행하여 열의 네 바이트를 혼합한다.
4. AddRoundKey (라운드 키 추가): 각 라운드에서 생성된 키를 현재의 데이터 블록과 XOR 연산으로 결합한다.

최종 라운드

AES 암호화의 마지막 라운드에서는 MixColumns 연산이 제외된다.

따라서 최종 라운드는 SubBytes, ShiftRows 및 AddRoundKey 연산만 포함한다. 암호화된 데이터 블록의 최종 형태를 확정짓는 단계이며, 이후 이 데이터 블록은 암호문으로 출력된다.

---

참고자료: 컴퓨터보안 (김진욱,유대현,김희천 공저 | 한국방송통신대학교출판문화원 | 2023)