대칭키 암호 시스템, DES와 AES

Intro

본 포스팅에서는 대칭키 암호 시스템 중 DES와 AES에 대해 다룬다.

DES(Data Encryption Standard)

• 1973년 미국의 연방 표준국(National Bureau of Standards, NBS, 현재의)에서 DES 공모
• IBM은 자사의 루시퍼(Lucifer)를 제출하였다.
• 미 연방 표준국은 1977년 루시퍼를 수정하여 DES로 선정하였다.
  • FIPS PUB 46
  • 국가안보국(National Security Agency, NSA)는 루시퍼에서 사용된 64비트 키를 56비트로 변경함
  • Most widely used block cipher in world
• 64-bit 데이터 블록, 56-bit 암호키를 사용한다.
• 현재는 DES를 사용하지 않고 3-DES(triple DES)와 AES(Advanced Encryption Standard) 사용한다.

| DES가 안전하지 않은 이유?
56bit짜리 key를 사용하기 때문이다.


56bit 정도만 전수조사를 진행하면 가능한 키의 경우의 수가 좁혀지게 되어 있다.
또, 이 DES 같은 암호는 하드웨어에 내장되어 있어 소프트웨어적으로 업데이트가 불가능하다.
그래서 DES를 2중으로 쓰는 방법을 고안해냈다.

2중 DES

설계 의도

---

56bit짜리 DES를 두 번 씀으로서 총 112bit의 효과를 내고자 하였다.
하지만 실질적으로 112bit의 효과가 나지 않는다.

중간 일치 공격 (Man In The Middle, MITM)

---

평문에서 암호화를 한 번 진행한다.
암호문에서 복호화를 한 번 진행한다.

이렇게 양쪽에서 암/복호화를 진행 후, 일치한 것들을 찾고 정렬하면 암호는 쉽게 꺠진다.
56 * 2 = 112bit의 효과를 기대했지만, 두 암/복호화 결과 표에서 정렬하고 검색하는 연산까지 포함하면 약 2^63번의 계산이면 암호 시스템을 무너뜨리기에 충분하다.

3중 DES

National Institute of Standards and Technology (NIST) 표준으로 사용되고 있는 방식이다.
이렇게 3중으로 설계하면 안전하다.

왜 EDE(Encrypt, Decrypt, Encrypt) 형태인가?

---

호환성 때문이다.
key를 동일하게 암/복호화를 3번 진행하면 3 DES 시스템을 1 DES 처럼 활용도 가능하다.
하드웨어적 한계로 인해 3 DES 시스템과 1 DES 시스템이 통신할 경우에 사용된다.

호환성을 생각 안 하면 EEE 구조로 사용하면 된다.
물론, EEE나 EDE나 암호학적 안정성은 동일하다.
-> key를 기반으로 하기 때문에 암/복호화 중 무엇을 선택하는 지는 중요하지 않기 때문이다.

AES(Advanced Encryption Standard)

AES 공모 시 필요조건

• 블록의 크기는 기본적으로 128bit이다
• 세 종류의 키를 가진다. (128bit, 192bit, 256bit)
• 소프트웨어 / 하드웨어 적으로 모두 효율적이이여야 한다.
• 전수조사 이외에 알려진 모든 공격 (e.g. MITM)들로부터 안전해야 한다.

AES의 구조

AES는 기본적으로 블럭 암호 체계이다.
input과 output의 크기가 128bit로 고정되어 있다. (AES 128bit기준)
input이 AES 암호화 체계에 들어가면, 10 라운드를 거쳐 output의 output이 나오게 된다. (AES 128bit기준)

128bit AES : 10 rounds
192bit AES : 12 rounds
256bit AES : 14 rounds

| KDF(Key Derivation Function)이란?
키 확장 함수이다.
기존의 패스워드나 기존의 키로부터 새로운 키를 생성하는 함수이다.
이 함수를 사용하여 보안 수준을 높일 수 있다.
이렇게 키를 확장해나갈때, 처음 key값을 seed(값)이라 표현하는데, 이 값만 잘 숨기면 훌륭한 암호체계가 된다.
하단의 영상에서 자세한 KDF과정을 다룬다.
Key Expansion in AES | Round Constant and g function in Key Expansion in AES

AES 암호화 과정

한 블럭이 128bit 단위로 시행되는 AES 128bit 기준으로 설명한다.
원소가 1 byte(8bit)인 4*4 matrix로 변환된다. (4*4*8 = 128bit)
이 하나의 행렬을 state라 부른다.

state를 10 rounds를 통해 암호화를 진행한다.
마지막 round 에서는 MixedColumns 과정을 수행하지 않는다.

One Round Consisted of 4 Layers

---

한 round는 4 가지 계층으로 구성된다.


| SubBytes
DES의 S-Box에 해당하며 한 바이트 단위로 치환을 수행한다.
state의 한 byte를 대응되는 S-Box의 한 바이트로 치환한다. (혼돈의 원리)

| ShiftRows
state의 한 행 안에서 바이트 단위로 자리바꿈이 수행된다. (분산의 원리)

| MixColumns
state가 한 열 안에서 혼합이 수행된다. (분산의 원리)

| AddRoundKey
state와 seed를 이용한 KDF 부터 생성된 각 round 별 128bit의 키를 XOR 연산을 진행한다.

즉, AES 암복호화 과정은 혼돈과 확산의 연속이다.

암복호화 과정을 그림으로 나타내면 이렇게 된다.

영상을 보면 이해가 더 잘 된다.
AES Rijndael Cipher explained as a Flash animation

암/복호화 예제

---

plain text(block) :"EASYCRYPTOGRAPHY"

1. Substitute Bytes(SubBytes)

X-Box 기반 substitution 결과

2. ShiftRows

• 첫 번째 행은 shift 되지 않는다.
• 두 번째 행은 왼쪽으로 한 번 shift 된다.
• 세 번째 행은 왼쪽으로 한 번 shift 된다.
• 마지막 행은 왼쪽으로 세 번 shift 된다.

3. MixedColumns

비트 단위로 열을 섞어준다.

복호화 시에는 Inverse MixedColumn, 역행렬을 통해 MixedColumns를 진행한다.

자세한 bit 단위 계산 과정은 아래 링크를 참고하자. 특별한 규칙이 적용되어 있는 것을 이해하기 쉽게 정리해놓았다.
감사합니다!
[정보보호] AES알고리즘 중, MIX Column 계산하는 법

4. AddRoundKey

KDF로 생성된 각 round key와 XOR연산을 진행한다.

AES의 안전성

---

• 취약키(Weak Keys), 차분 분석 방법(Differential Cryptanalysis), 선형 분석 방법 (Linear Cryptanalysis)등을 이용한 공격에 안전하다.

감사합니다.

---

Ref

보안프로그래밍(2023), 숭실대학교 소프트웨어학부 조효진 교수님

Beginning Cryptography with Java/David Hook/Wrox press/2005