블록 암호 - DES, AES, 운영 모드

Gunter·2024년 1월 28일

Cryptography 암호학

Cryptography

목록 보기

3/7

블록 암호 : DES

DES(Data Encryption Standart)는 미국 국가 안보국 NSA에서 IBM의 루시퍼 알고리즘을 개량해 만든 대칭키 암호. 키 길이를 56비트로 줄이고, 사용하는 알고리즘도 일부 변경.

DES는 8바이트(16비트)를 한 블록으로 하는 블록 암호.
현대에는 공격 기법이 많이 연구되어 DES를 더 이상 블록암호의 표준으로 사용하지 않음.

전체 구조는 초기 순열(IP), 최종 순열(FP), 페이스텔(Feistel) 구조의 16라운드, 그리고 각 라운드에 사용되는 48비트의 키를 생성하는 키 생성 함수(Key Generation)로 구성됨.

💡 백도어(Backdoor)

컴퓨터 보안에서 시스템을 쉽게 장악할 수 있도록 만들어진 비밀통로

.
.
.

DES는 혼돈 성질을 만족하기 위해 치환(Substitution), 확산 성질을 만족하기 위해 순열(Permutation) 사용

치환, 순열을 한번 적용하면 암호학적 효과 X
여러번 교차해서 반복적용하면 암호학적 안전성 확보 = 곱 암호(Product Cipher)

DES에서 라운드 함수를 적용하는 전체 과정은 페이스텔(Feistel) 구조를 이룸

(1)입력으로 들어온 블록을 동일한 길이의 왼쪽 블록 L과 오른쪽 블록 R으로 나눔
(2)각 라운드마다 오른쪽 블록은 다음 라운드의 왼쪽 블록으로 입력됨
(3)왼쪽 블록은 오른쪽 블록에 라운드 함수 F를 적용한 결과와 xor 되어 다음 라운드의 오른쪽 블록으로 입력됨

.
.

이를 정형화하면 ( P=입력으로 들어온 평문, K=각 라운드에서 생성된 키 )

+)apple pages_ 위 첨자 입력 : Control-Shift-Command +
아래 첨자 입력 : Control-Command -

페이스텔 암호의 특징

블록 암호는 평문을 복호화 할 수 있어야 하므로 보통 역함수가 존재
페이스텔 구조는 F가 복호화 과정에서 ⊕ 로 상쇄되므로 역함수 존재 X
암호화와 복호화의 구조가 동일해서 암호화에 사용한 라운드 키를 역순으로 입력하면
복호화가 이뤄짐

DES의 과정

시작할 때 초기순열(IP)을, 마지막에는 최종 순열(FP)을 수행한다.
초기 순열과 최종 순열은 정해진 테이블을 이용해 64비트 입력을 비트 단위로 전치함.
테이블의 n번째 값이 m일 때, 출력의 n번째 비트는 입력의 m번째 비트가 된다.

초기 순열과 최종 순열은 각각 초기 순열 테이블(IPT)과 최종 순열 테이블(FPT)을 이용.
초기 순열과 최종 순열은 서로 역관계에 있음.
임의의 64비트 데이터에 초기 순열을 적용하고, 최종 순열을 적용하면 입력 값이 그대로 출력됨.

라운드 함수

라운드 함수 F에는 오른쪽 블록만 입력되므로, 입력의 길이는 32비트이다.
라운드 함수는 확장 순열(Expansion P-Box), 라운드 키 결합(XOR), 치환 테이블(S-Box) 그리고 고정 순열(Straight P-Box)로 이루어져 있다.

확장 순열(Expansion P-Box)은 입력을 비트 단위로 전치하는 동시에, 전체 길이를 48비트로 확장함.
이 과정에서 32비트의 입력값을 4비트씩 8개의 부분으로 나누고, 테이블을 참조하여 각각을 6비트로 확장한다.

S-Box(Substitution-Box)는 라운드 키 결합에서 출력된 48비트 결과값을 32비트로 축소함.
S-Box는 4개의 행과 16개의 열로 이루어진 표를 사용하는데, 표의 각 값은 4비트로 표현되는 수임.

S-Box가 적용되는 과정
(1)입력을 여섯 비트씩 8개의 부분으로 나눔
(2)여섯 비트 중 첫 번째와 마지막 비트로 행을 결정하고, 나머지 네개의 비트로 열을 결정한다.
(3)그 뒤, S-Box의 표에서 행과 열을 참조하여 값을 반환함
(4)DES에서는 여섯 비트로 자른 부분마다 다른 S-Box를 사용한다
(5)S-Box로 길이를 축소하고 나면, 고정 순열(Straight P-Box)로 다시 비트 단위 전치가 이뤄짐

키 생성 함수(Key Scheduling)는 64비트의 입력을 받아 각 라운드에 필요한 48비트 라운드 키를 생성하는 함수이다.
패리티 비트 제거(Parity Bit Drop), 쉬프트(Shift), 압축 순열(Compression P-Box)로 구성되어 있다.

패리티 비트 제거(Parity Bit Drop)
- 입력에서 패리티 비트를 제거하고, 남은 56비트에 순열을 적용하는 과정
- DES의 비밀키에서 각 바이트의 가장 오른쪽 비트는 자신이 속한 바이트의
나머지 7비트에 대한 홀수 패리티 비트(Odd parity Bit) 이다.
홀수 패리티 비트란 한 바이트를 이진수로 표현했을 때, 1의 개수가 홀수가
되도록 덧붙인 비트
ex) 1010101 에는 1이 4개 존재. 홀수 패리티 비트를 적용하면 끝에 비트 1 추가
10101011 을 전송해야 한다
- 통신 중에 비트 반전이 일어나지 않았음을 보증하는 역할을 함
- 홀수 패리티 비트를 사용하여 통신할 때, 수신한 바이트 중 1의 갯수가 짝수인
바이트가 있다면 그 바이트에서 임의의 비트에 반전이 일어났음을 수신자가 앎
- 확인한 수신자는 손상되지 않은 데이터를 얻기 위해 재전송 요구 가능

쉬프트(Shift)
- 입력을 왼쪽 28비트와 오른쪽 28비트로 나누어 각각을 1비트나 2비트만큼
왼쪽으로 순환 쉬프트(Cyclic Shift)하는 과정이다.
- 1, 2, 9, 16 라운드에서는 1비트, 나머지 라운드에서는 2비트만큼 쉬프트한다.
- 10101111을 왼쪽으로 1비트 순환 쉬프트하면, 왼쪽 끝의 비트가 오른쪽 끝으로
이동하여 0101111이 됨.
- 마찬가지고 2비트를 왼쪽으로 순환 쉬프트 하면 왼쪽 끝의 ’10’이 오른쪽으로
이동하여 10111110이 된다.

압축 순열(Compression P-Box)
- 56비트의 입력을 48비트 길이로 압축하는 과정

DES의 응용 - 다중 DES
- 다중 DES는 서로 다른 키를 사용하는 DES 모듈을 여러 개 이어붙여서 DES의 약 점을 보완한 암호 시스템이다.
- DES를 두 겹으로 사용하는 이중 DES(2-DES)는 112비트, 삼중 DES(3-DES)는 168비트의 키를 사용한다.
- 늘어난 키 만큼 단일 DES 보다 안전할 것 같지만, 중간 일치 공격으로 인해 안전 성을 획기적으로 높이지는 못한다.
- 이중 DES는 단일 DES와 비슷한 안전성을 갖고 있으며, 삼중 DES는 키 길이를 2 배로 늘리는 효과밖에 얻지 못한다.

중간 일치 공격(Meet-in-the-Middle Attack)

공격자가 어떤 평문 p, p를 암호화한 암호문 c를 알 때, 수행할 수 있는 공격

56비트 키 공간 K에서 가능한 모든 키 K1으로 p를 암호화하여 집합 S1을 생성한다.
S1 = { Ek1℗ | K1 ∈ K }
(2) K에서 가능한 모든 키 k2로 c를 복호화하여 집합 S2를 생성한다.
S2 = { Dk2© | k2 ∈ K }
(3) S1의 모든 원소와 S2의 모든 원소에 대해 EK1(p)=DK2(c)를 만족하는 k1, k2의 쌍으
로 후보키의 집합 CK를 생성한다.
CK = {(k1, k2) | Ek1℗ = Dk2©, Ek1℗ ∈ S1, Dk2© ∈ S2 }
(4) 다른 평문 p’과 p’을 암호화한 암호문 c’을 생성한다.
(5) CK의 모든 원소에 대해 Ek1(p’) = Dk2(c’)을 만족하는 k1, k2 쌍으로 집합 CK 갱신
CK = {(k1, k2) | Ek1(p’) = Dk2(c’), (k1, k2) ∈ CK }
(6) CK의 원소가 하나가 될 때까지 4와 5의 과정을 반복한다.

블록 암호 : AES

AES(Advanced Encryption Starndard)는 연산 능력의 향상으로 DES가 안전하지 않게 되자, 새롭게 표준으로 선정된 블록암호. 여러 암호 알고리즘들 중 Rijndael 구조 채택.

치명적인 취약점이 발견되지 않아, 현대에서 대칭키 암호 알고리즘을 사용할 때 일반적으로 AES 사용.
갈루아 필드(Galois Field), 체(Field), 군(Group)에 대한 이해 필요.

SPN(Substitution Permutation Network)

AES는 SPN이라는 암호 구조 사용.
SPN은 곱 암호의 일종으로, S-Box를 사용하는 치환과 P-Box를 사용하는 순열을 여러 라운드에 걸쳐 반복

AES 구조

AES는 라운드마나 128비트 크기의 블록을 암호화하는 블록 암호.
키의 길이는 128, 192, 256 비트 중 하나를 선택할 수 있고 라운드 수는 키의 길이에 따라 10, 12, 14 로 결정

AES는 암호화를 할 때, 가장 먼저 각 블록을 4행 4열의 상태 배열로 재구성.
State의 각 칸에는 8비트(1바이트)가 저장됨

AES 라운드 함수

SubBytes

- subbytes는 state의 각 바이트를 S-Box를 참조하여 치환하는 함수
- 바이트의 상위 4비트가 행, 하위 4비트가 열을 결정
- ex) 어떤 바이트가 2A면 해당 바이트는 S-Box의 2행 A열을 참조해 E5로 치환

ShiftRows

- shiftRows는 State의 각 행을 구성하는 바이트들을 쉬프트 하는 함수.
- 4가지 함수 중 유일하게 순열의 역할을 수행
- 예시 사진처럼 2행은 왼쪽으로 1칸, 3행은 왼쪽으로 2칸, 4행은 왼쪽으로 3칸 밈
- 복호화 할땐 반대로 2행, 3행, 4행을 각각 오른쪽으로 1칸, 2칸, 3칸씩 밈

MixColumns

- Mixcolumns는 열 단위로 치환을 수행하는 함수
- 갈루아 필드 내에서 행렬 연산으로 수해짐. 
- 최적화를 위해 곱셈 결과가 미리 계산된 lookup table을 만들어 사용.

AddRoundKey

- 키 생성 함수(Key Schedule)로 생성된 라운드 키의 state를 각 바이트별로
   XOR 함.
- 복호화할 땐 XOR의 성질을 이용해 동일한 키를 state에 XOR함.

Key Schedule

AES는 암복호화를 시작할 때 매 라운드마다 AddRoundKey를 적용.
RotWord -> 열을 위로 한번 회전시킴
SubWord -> SubBytes에서 사용한 것과 동일한 S-Box를 사용해 각 바이트를 치환
Rcon -> 최상위 바이트를 XOR함

블록 암호 : 운영 모드

DES는 64비트, AES는 128비트의 평문을 한 블록으로 처리함. 각각 8글자, 16글자를 한번에 암호화. 일반적으로 평문의 길이는 이 길이들을 넘는 경우가 많으니까
다양한 크기의 데이터를 처리하는 운영 모드(Mode of Operation)를 이용.

패딩 - 평문을 블록 단위로 만드는 데 사용

대표적인 운영모드 ECB, CBC, CTR

패딩

평문에 데이터를 붙여서 평문의 크기가 블록 크기의 배수가 되도록 만드는 과정
패딩된 암호문을 복호화 할 땐 복호화된 평문에서 패딩을 제거해야 원래 평문을 얻을 수 있음
비트 패딩(Bit Padding) - 마지막 블록에서 평문이 채우지 못하는 비트 중 최상위 비트를 1로 설정하고, 나머지는 모두 0으로 채우는 패딩 기법
비트 패딩을 적용할 때는 평문의 크기가 블록 크기의 배수이면, 패딩으로 한 블록을 추가함
바이트 패딩 - 바이트 패딩은 바이트 단위로 패딩을 수행하는 기법.
바이트 패딩 : ANSI X.923 - 마지막 블록의 남는 바이트를 임의의 값(0)으로 채우고, 마지막 바이트에 패딩의 길이를 기록하는 기법.
바이트 패딩 : PKCS#7 - 공개키 암호의 표준 문서. 추가할 패딩의 바이트 크기로 마지막 블록을 채우는 패딩 기법

ECB 모드 (Electronic Code Book)

가장 간단한 운영모드, 블록들은 모두 같은 키로 암호화 됨.
장점 : 여러 블록을 병렬적으로 암호화 가능
단점 : 다른 운영모드에 비해 암호학적 안전성 부족, 혼돈 성질 약함
같은 블록은 같은 암호문으로 암호화 되므로, 공격자가 암호문에서 평문의 정보를 습득하거나, 리플레이 공격 수행 가능
리플레이 공격(재전송 공격, Replay Attack) - 어떤 데이터를 재전송하여 시스템이 의도치 않은 행동을 하게 하는것

CBC 모드 (Cipher Block Chaining)

어떤 블록을 암호화 하기 전에, 이 블록을 직전 블록의 암호문과 XOR함.
첫 번째 블록은 초기 벡터(IV)라고 불리는 데이터와 XOR

초기 벡터는 일반적으로 논스(Nonce) 라는 무작위 값 사용, 공격자가 알아도 안전성에 영향 X
만약 조작할 수 있으면, 복호화 결과 첫번째 블록 조작 가능
따라서 CBC 모드를 사용할 땐 초기 벡터의 무결성을 함께 보장해야 함
한 블록을 암호화 할 때 직전 블록의 암호화 결과를 사용하므로 여러 블록을 병렬적으로 암호화 X
복호화 할 땐, 모든 암호문 블록을 알고 있으므로 병렬적 처리 가능
재전송 공격에 강인, 높은 혼돈성을 가짐

CBC Bit-Flipping Attack
공격자가 초기 벡터를 원하는 값으로 조작하여 복호화된 첫번째 블록 조작 공격