블록 암호

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

블록 암호는 두 개의 알고리즘, 즉 암호화와 복호화로 구성되며, 고정된 크기의 입력 블록과 키를 받아 동일한 크기의 출력 블록을 생성하는 대칭 암호 방식이다. 암호화는 평문을 암호문으로 변환하고, 복호화는 암호문을 평문으로 되돌리는 역함수 관계를 갖는다. 블록 암호는 곱 암호, 반복 암호, 치환-순열 네트워크(SPN), Feistel 구조, Lai-Massey 구조 등 다양한 구조를 가질 수 있으며, 데이터 암호화 표준(DES), 고급 암호화 표준(AES) 등이 널리 사용된다. 블록 암호는 ARX 연산, S-box, P-box 등 다양한 연산을 사용하며, ECB, CBC, CTR 등 다양한 운용 방식을 통해 가변 길이 메시지를 처리한다. 블록 암호의 안전성은 무차별 대입 공격, 차분 분석, 선형 분석, 적분 분석, 사이드 채널 공격 등 다양한 암호 분석 기법에 대한 저항성을 기반으로 평가되며, 증명 가능한 보안 모델을 통해 안전성을 검증한다.

더 읽어볼만한 페이지

블록 암호 - 데이터 암호화 표준
데이터 암호화 표준(DES)은 미국 국립표준기술연구소에서 개발되어 널리 사용되었던 대칭키 암호 알고리즘이지만, 짧은 키 길이와 취약점 때문에 고급 암호화 표준(AES)으로 대체되었고, 트리플 DES 형태로 일부 시스템에서 사용되며 암호학 발전에 기여한 역사적 의미가 있다.
블록 암호 - 고급 암호화 표준
고급 암호화 표준(AES)은 미국 국립표준기술연구소에서 제정한 대칭 키 암호화 블록 암호 표준으로, 치환-순열 네트워크 구조에 기반하여 128비트 블록 크기와 다양한 키 크기를 지원하며, 빠른 속도와 효율성으로 널리 사용된다.

블록 암호
암호학
종류	대칭 키 암호
블록 크기	(암호에 따라 다름)
키 크기	(암호에 따라 다름)
일반적인 구조
Feistel 암호	DES Triple DES
SPN (Substitution-Permutation Network) 암호	AES PRESENT
Lai-Massey 암호	IDEA
작동 모드
블록 암호 작동 방식	CBC CFB CTR ECB OFB

2. 정의

블록 암호는 암호화와 복호화, 두 쌍의 알고리즘으로 구성된다.^[1] 두 알고리즘 모두 두 개의 입력을 받는다. 크기가 비트인 입력 블록과 크기가 비트인 키를 입력받으며, 둘 다 비트의 출력 블록을 생성한다. 복호화 알고리즘 는 암호화의 역함수로 정의되며, 즉, 이다.^[2]^[3]

좀 더 형식적으로, 블록 암호는 암호화 함수로 지정된다.

:

E_K(P) := E(K,P): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n,

이 함수는 비트 길이 (''키 크기'')의 키 와 길이 (''블록 크기'')의 비트 문자열 를 입력으로 받아 비트의 문자열 를 반환한다. 는 평문이라고 하며, 는 암호문이라고 한다. 각 에 대해, 함수 ()는 에서 가역적인 매핑이어야 한다. 의 역은 다음과 같은 함수로 정의된다.

:

E_K^{-1}(C) := D_K(C) = D(K,C): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n,

키 와 암호문 를 입력으로 받아 평문 값 를 반환하며, 다음을 만족한다.

:

\forall P: D_K(E_K(P)) = P.

예를 들어, 블록 암호 암호화 알고리즘은 128비트 평문 블록을 입력으로 받아 해당 128비트 암호문 블록을 출력할 수 있다. 정확한 변환은 두 번째 입력인 비밀 키를 사용하여 제어된다. 복호화도 유사하다. 이 예에서 복호화 알고리즘은 128비트 암호문 블록과 비밀 키를 입력으로 받아 원래의 128비트 평문 블록을 생성한다.^[4]

각 키 ''K''에 대해, ''E_K''는 입력 블록 집합에 대한 순열 (전단사 매핑)이다.

블록 암호는

b

비트의 블록과

n

비트의 키를 입력으로 받아

b

비트의 블록을 출력한다. 암호화(encryption)

E

와 복호화(decryption)

E^{-1}

의 두 가지 알고리즘으로 구성된다. 임의의 키

k

에 대해 복호화 알고리즘은 암호화 알고리즘의 역함수가 되며, 다음을 만족한다.

:

E_k^{-1}(E_k(m))=m

(

m

은 임의의 블록).

암호화 알고리즘의 입력 블록 및 복호화 알고리즘의 출력 블록은 평문, 암호화 알고리즘의 출력 블록 및 복호화 알고리즘의 입력 블록은 암호문이라고 한다.

3. 역사

현대적인 블록 암호 설계는 반복적인 곱 암호 개념에 기반을 두고 있다. 1949년 클로드 섀넌은 그의 저서 ''비밀 시스템의 통신 이론''에서 곱 암호를 대체 암호와 전치 암호 같은 간단한 연산을 결합하여 보안을 효과적으로 향상시키는 수단으로 제안했다.^[5]

호르스트 파이스텔의 이름을 딴 파이스텔 네트워크는 DES 암호에서 특히 구현되었다.^[6] AES와 같은 많은 다른 블록 암호 구현은 대체-순열 네트워크로 분류된다.

지불 카드 산업 데이터 보안 표준 (PCI DSS) 등에서 사용되는 모든 암호화 블록 형식의 근원은 아탈라 키 블록 (AKB)에 있으며, 이는 최초의 하드웨어 보안 모듈 (HSM)인 아탈라 박스의 핵심 혁신이었다. 이는 1972년 모하메드 M. 아탈라에 의해 개발되어 1973년에 출시되었다. AKB는 대칭 키 또는 PIN을 은행 산업의 다른 주체와 안전하게 교환하는 데 필요한 키 블록이었다.^[7] 1998년 기준으로 아탈라 박스는 가동 중인 모든 ATM 네트워크의 90% 이상을 보호했으며,^[8] 2014년 기준으로 여전히 전 세계 ATM 거래의 대다수를 보호하고 있다.^[9]

1977년 미국 국립 표준국(이후 미국 국립 표준 기술 연구소, NIST)에 의한 DES 암호의 출판은 현대 블록 암호 설계에 대한 대중의 이해에 근본적인 영향을 미쳤다. 또한 암호 분석 공격의 학문적 발전에 영향을 미쳤다. 차분 암호 분석과 선형 암호 분석 모두 DES 설계 연구에서 비롯되었다.

블록 암호는 여러 법에 기초한 큰 블록의 치환식 스트림 암호와 전치 암호를 조합하여 해독하기 매우 어려운 암호를 구성할 수 있다.

대표적인 블록 암호로, 미국 국립 표준 기술 연구소(NIST)가 제정한 DES와 트리플 DES, AES가 있다. 일본에서 개발된 블록 암호로는 MISTY1과 Camellia 등이 알려져 있다.

블록 암호의 역사를 시간 순으로 정리하면 다음과 같다.

연도	내용
1971년경 ~ 1976년	IBM의 호르스트 파이스텔이 개발한 루시퍼는 최초의 민간용 블록 암호로 여겨진다. 1977년에는 루시퍼를 기반으로 DES가 제정되었다.
1987년 ~ 1991년	1987년 NTT의 시미즈 아키히로와 미야구치 쇼지에 의해 FEAL이 발표되었다. 1991년 엘리 비함과 아디 샤미르에 의해 차분 분석이 발표되었고, FEAL은 차분 분석에 의해 효율적으로 해독될 수 있음이 밝혀졌다.
1992년 ~ 1995년	1992년 미쓰비시 전기의 마쓰이 미쓰루에 의해 선형 분석이 발표되었고, 1993년 - 1994년에 걸쳐 DES의 해독과 실험이 이루어졌다. 1995년에는 MISTY1 및 MISTY2가 발표되었다.
1997년 ~ 2001년	1997년 RSA 시큐리티사가 DES 챌린지를 기획, 96일 후에 키가 발견되었다. 1998년에는 하드웨어에 의한 키 탐색 전용기 DES 크래커가 개발되어, DES의 키를 56시간 만에 탐색했다. 1997년 차세대 암호 (AES)의 제정 준비(공모)가 시작됨과 함께, 1999년에는 TripleDES가 제정되었다. 2001년 11월에 AES가 제정되었다.
2002년 ~	AES와 CRYPTREC, NESSIE의 표준 암호와는 별도로, 특수 용도에 특화된 블록 암호의 설계가 연구되고 있다. FPGA나 IC 칩으로 구현했을 때 회로 규모나 실행 속도가 최적화되도록 설계된 CLEFIA 등이 있다. 또한, 구현된 하드웨어나 소프트웨어에 대한 공격(사이드 채널 공격)도 활발해졌다.

4. 구조

블록 암호는 암호화 알고리즘 E와 복호화 알고리즘 D, 두 쌍의 알고리즘으로 구성된다.^[1] 두 알고리즘 모두 n 비트 크기의 입력 블록과 k 비트 크기의 키를 입력받아, n 비트 크기의 출력 블록을 생성한다. 복호화 알고리즘 D는 암호화의 역함수로 정의된다. 즉, $D = E^{-1}$ 이다.^[2]^[3]

좀 더 형식적으로, 블록 암호는 다음과 같은 암호화 함수로 표현할 수 있다.

: $E_K(P) := E(K,P): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n,$

이 함수는 비트 길이 k(''키 크기'')의 키 K와 길이 n(''블록 크기'')의 비트 문자열 P를 입력으로 받아 n 비트의 문자열 C를 반환한다. P는 평문, C는 암호문이라고 한다. 각 K에 대해, 함수 E_K(P)는 $\{0,1\}^n$ 에서 가역적인 매핑이어야 한다. E의 역은 다음과 같이 정의된다.

: $E_K^{-1}(C) := D_K(C) = D(K,C): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n,$

키 K와 암호문 C를 입력으로 받아 평문 값 P를 반환하며, 다음을 만족한다.

: $\forall P: D_K(E_K(P)) = P.$

예를 들어, 블록 암호 암호화 알고리즘은 128비트 평문 블록을 입력으로 받아 128비트 암호문 블록을 출력할 수 있다. 이 변환은 비밀 키를 통해 제어되며, 복호화 알고리즘은 128비트 암호문 블록과 비밀 키를 입력으로 받아 원래의 128비트 평문 블록을 생성한다.^[4] 각 키 ''K''에 대해, ''E_K''는 입력 블록 집합에 대한 순열 (전단사 매핑)이며, 각 키는 $(2^n)!$ 가능한 순열 집합에서 하나의 순열을 선택한다.

블록 암호는 b 비트의 블록과 n 비트의 키를 입력으로 받아 b 비트의 블록을 출력한다. 암호화(encryption) E와 복호화(decryption) E^-1의 두 가지 알고리즘으로 구성되며, 임의의 키 k에 대해 복호화 알고리즘은 암호화 알고리즘의 역함수가 된다.

: $E_k^{-1}(E_k(m))=m$

(m은 임의의 블록). 암호화 알고리즘의 입력 블록 및 복호화 알고리즘의 출력 블록은 평문, 암호화 알고리즘의 출력 블록 및 복호화 알고리즘의 입력 블록은 암호문이라고 한다.

블록 암호는 결정적 암호이므로, 키가 고정되면 동일한 평문은 항상 동일한 암호문으로 암호화된다. 즉, 동일한 암호문이 있는 경우 해당 블록의 평문이 동일하다는 정보가 누설된다. 이러한 문제는 암호 운용 방식을 통해 해결할 수 있다.

치환과 전치를 조합한 공통 키 암호는 여러 방법을 통해 큰 블록의 치환식 스트림 암호와 전치 암호를 조합하여 해독하기 어려운 암호를 구성할 수 있다. 대표적인 블록 암호로는 DES, 트리플 DES, AES 등이 있으며, 일본에서 개발된 블록 암호로는 MISTY1, Camellia 등이 있다.

블록 암호는 주로 메인 스크램블러와 확장 키를 생성하는 키 스케줄러로 구성된다. 키 스케줄러는 키를 입력으로 받아 여러 개의 확장 키를 출력하고, 스크램블러는 여러 라운드로 구성되어 각 라운드에서 확장 키를 사용하여 입력의 치환, 전치 등을 수행한다. 이러한 구조를 곱 암호(Product cipher)라고 하며, 라운드가 같은 함수의 반복으로 구성된 경우에는 반복 암호(Iterated cipher)라고 한다.

라운드 함수는 치환, 전치, 논리 연산, 산술 연산 등 단순한 요소로 구성되며, 여러 단 중첩하여 충분한 강도의 암호화를 수행한다. 라운드 단수는 알고리즘 사양에 따라 지정되지만, 보안 파라미터로서 사용자가 선택하는 경우도 있다.

라운드 함수의 주요 구성 방식에는 Feistel 구조와 SPN 구조 두 가지가 있다. DES, MISTY1, Camellia는 Feistel 구조이며, AES는 SPN 구조 암호이다.

4. 1. 반복 블록 암호

대부분의 블록 암호 알고리즘은 반복 블록 암호로 분류되며, 이는 고정 크기의 평문 블록을 동일한 크기의 암호문 블록으로 변환하는 과정을 반복한다. 각 반복은 ''라운드''라고 부르며, ''라운드 함수''라는 가역적 변환을 적용한다.^[10]

일반적으로 라운드 함수 ''R''은 원래 키에서 파생된 ''라운드 키'' ''K_i''를 두 번째 입력으로 사용한다.^[11]

:''M_i'' = ''R_{K_i}''(''M_i-1'')

여기서 ''M₀''은 평문이고 ''M_r''은 암호문이며, ''r''은 라운드 수이다.

이 외에도 키 와이닝이 자주 사용된다. 시작과 끝에서 키 자료(종종 XOR)로 데이터를 수정한다.

:''M₀'' = ''M'' ⊕ ''K₀''

:''M_i'' = ''R_{K_i}''(''M_i-1'') ; ''i'' = 1 ... ''r''

:''C'' = ''M_r'' ⊕ ''K_r+1''

표준 반복 블록 암호 설계 방식에서는 단순히 많은 수의 라운드를 사용하여 암호학적으로 안전한 블록 암호를 구성할 수 있다. 그러나 이는 암호의 효율성을 떨어뜨린다. 따라서 효율성은 전문 암호의 중요한 설계 기준이다. 좋은 블록 암호는 캐시 상태나 실행 시간을 통해 비밀 데이터를 누출할 수 있는 부채널 공격(분기 예측 및 입력 종속 메모리 접근 등)을 피하도록 설계된다. 또한, 암호는 작은 하드웨어나 소프트웨어에서도 간결하게 구현될 수 있어야 한다.

블록 암호는 메인 스크램블러와 키 스케줄러로 구성되는 경우가 많다. 키 스케줄러는 키를 입력받아 여러 개의 확장 키를 생성한다. 스크램블러는 여러 라운드로 구성되며, 각 라운드에서 확장 키를 사용하여 입력 데이터에 치환, 전치 등을 수행한다. 이러한 구조를 곱 암호(Product cipher)라고 한다. 라운드가 같은 함수의 반복으로 구성된 경우에는 반복 암호(Iterated cipher)라고 한다.

라운드 함수는 치환, 전치, 논리 연산, 산술 연산 등 단순한 요소로 구성되며, 여러 단 중첩하여 충분한 강도의 암호화를 수행한다. 라운드 단수는 알고리즘 사양에 따라 지정되지만, 보안 파라미터로서 사용자가 선택하는 경우도 있다.

라운드 함수의 주요 구성 방식에는 Feistel 구조와 SPN 구조 두 가지가 있다. DES, MISTY1, Camellia는 Feistel 구조이며, AES는 SPN 구조 암호이다.

4. 2. 치환-순열 네트워크 (SPN)

'''치환-순열 네트워크(SPN)'''는 블록 암호의 중요한 유형 중 하나로, 평문과 키의 블록을 입력받아 여러 번의 치환 및 순열 단계를 반복하여 암호문 블록을 생성한다.^[12]

각 라운드는 치환 단계와 순열 단계로 구성된다.^[12]

치환 단계: 비선형 치환 단계는 키 비트와 평문 비트를 섞어 섀넌의 혼돈 개념을 구현한다.
순열 단계: 선형 순열 단계는 중복성을 분산시켜 확산 개념을 구현한다.^[13]^[14]

구성 요소:

치환 상자(S-box): 입력 비트의 작은 블록을 다른 출력 비트 블록으로 대체한다. 이 변환은 일대일 대응이어야 하며, 하나의 입력 비트 변경이 평균적으로 출력 비트의 절반을 변경시키는 눈사태 효과를 발생시켜야 한다.^[15]
순열 상자(P-box): 모든 비트의 위치를 섞는다. 모든 S-box의 출력 비트를 섞어 다음 라운드의 S-box 입력으로 전달하며, 각 S-box의 출력 비트가 최대한 많은 S-box 입력에 분산되도록 설계된다.^[16]

각 라운드에서 라운드 키는 S-box 및 P-box를 사용하는 등의 간단한 연산을 통해 키에서 얻어지며, 일반적으로 XOR 연산을 사용하여 결합된다.

복호화는 S-box 및 P-box의 역함수를 사용하고 라운드 키를 역순으로 적용하여 간단히 수행할 수 있다.^[17]

4. 3. Feistel 암호

DES 및 Blowfish와 같은 많은 블록 암호는 Feistel 암호 구조를 사용한다.

'''Feistel 암호'''는 암호화할 평문 블록을 두 개의 동일한 크기로 나누어, 라운드 함수와 서브키를 사용하여 한쪽에 적용한 후 그 결과를 다른 쪽과 XOR 연산을 수행한다. 그 후 두 부분을 서로 바꾼다.^[10]

라운드 함수를

{\rm F}

, 라운드

0,1,\ldots,n

에 대한 서브키를

K_0,K_1,\ldots,K_{n}

라고 할 때, 기본 연산은 다음과 같다.^[10]

평문 블록을 (

L_0

,

R_0

)로 분할한다.

각 라운드

i =0,1,\dots,n

에 대해 다음을 계산한다.

:

L_{i+1} = R_i\,

:

R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)

.

암호문은

(R_{n+1}, L_{n+1})

이다.

암호문

(R_{n+1}, L_{n+1})

의 해독은

i=n,n-1,\ldots,0

에 대해 다음을 계산하여 수행된다.

:

R_{i} = L_{i+1}\,

:

L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})

.

그러면

(L_0,R_0)

이 다시 평문이 된다.

substitution–permutation network(치환-순열 네트워크)와 비교했을 때, Feistel 모델의 장점은 라운드 함수

{\rm F}

가 가역적일 필요가 없다는 것이다.^[10]

Feistel 구조는 DES, MISTY1, Camellia 등의 암호에 사용된다.

4. 4. Lai-Massey 암호

라이-마세이 구조는 페이스텔 구조와 비슷한 보안성을 가지면서도, 라운드 함수

\mathrm F

가 꼭 가역적일 필요가 없다는 장점이 있다. 입력 블록을 두 부분으로 나누는 것도 페이스텔 구조와 유사하다. 하지만, 라이-마세이 구조에서는 라운드 함수를 두 부분의 차이에 적용하고, 그 결과를 두 부분 모두에 더한다.^[10]

\mathrm F

를 라운드 함수,

\mathrm H

를 반 라운드 함수,

K_0, K_1, \ldots, K_n

을 각 라운드

0, 1, \ldots, n

의 서브 키라고 하면, 기본 연산은 다음과 같다.

먼저 평문 블록을

L_0

와

R_0

두 부분으로 나눈다.

각 라운드

i = 0, 1, \dots, n

에서 다음을 계산한다.

:

(L_{i+1}', R_{i+1}') = \mathrm H(L_i' + T_i, R_i' + T_i),

여기서

T_i = \mathrm F(L_i' - R_i', K_i)

이고

(L_0', R_0') = \mathrm H(L_0, R_0)

이다.

최종 암호문은

(L_{n+1}, R_{n+1}) = (L_{n+1}', R_{n+1}')

가 된다.

암호문

(L_{n+1}, R_{n+1})

의 복호화는

i = n, n-1, \ldots, 0

에 대해 다음을 계산하여 수행한다.

:

(L_i', R_i') = \mathrm H^{-1}(L_{i+1}' - T_i, R_{i+1}' - T_i)

여기서

T_i = \mathrm F(L_{i+1}' - R_{i+1}', K_i)

이고

(L_{n+1}', R_{n+1}') = \mathrm H^{-1}(L_{n+1}, R_{n+1})

이다.

그러면

(L_0, R_0) = (L_0', R_0')

가 다시 평문이 된다.

5. 연산

블록 암호는 암호화 알고리즘과 복호화 알고리즘, 두 쌍의 알고리즘으로 구성된다.^[1] 각 알고리즘은 n 비트의 입력 블록과 k 비트의 키를 입력받아, n 비트의 출력 블록을 생성한다. 복호화 알고리즘은 암호화의 역함수이다. 즉, $D = E^{-1}$ 이다.^[2]^[3]

블록 암호는 다음과 같은 암호화 함수로 표현할 수 있다.

: $E_K(P) := E(K,P): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n,$

여기서 k는 키 크기, K는 키, n은 블록 크기, P는 평문, C는 암호문을 의미한다. 함수 E_K(P)는 $\{0,1\}^n$ 에서 가역적인 매핑이어야 한다. E의 역함수는 다음과 같다.

: $E_K^{-1}(C) := D_K(C) = D(K,C): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n,$

이 함수는 키 K와 암호문 C를 입력으로 받아 평문 P를 반환하며, 다음을 만족한다.

: $\forall P: D_K(E_K(P)) = P.$

예를 들어, 128비트 평문 블록을 암호화하는 블록 암호 알고리즘은 128비트 암호문 블록을 출력한다. 이 변환은 비밀 키를 사용하여 제어되며, 복호화 알고리즘은 동일한 비밀 키와 128비트 암호문 블록을 입력으로 받아 원래의 128비트 평문 블록을 생성한다.^[4]

각 키 ''K''에 대해, ''E_K''는 입력 블록 집합에 대한 순열(전단사 매핑)이다.

블록 암호는 메인 스크램블러와 키 스케줄러로 구성되는 경우가 많다. 키 스케줄러는 키를 입력으로 받아 여러 개의 확장 키를 출력하고, 스크램블러는 여러 라운드로 구성되어 각 라운드에서 확장 키를 사용하여 입력의 치환, 전치 등을 수행한다. 이러한 암호를 곱 암호(Product cipher)라고 하며, 라운드가 같은 함수의 반복으로 되어 있는 경우에는 반복 암호(Iterated cipher)라고 한다.

라운드 함수는 치환, 전치, 논리 연산, 산술 연산 등의 단순한 요소로 구성되며, 여러 단 중첩하여 충분한 강도의 스크램블을 수행한다. 라운드 단수는 알고리즘의 사양에 따라 지정되지만, 보안 매개변수로 사용자가 선택하기도 한다.

라운드 함수의 주요 구성법에는 Feistel 구조와 SPN 구조 두 가지가 있다. DES, MISTY1, Camellia는 Feistel 구조이며, AES는 SPN 구조이다.

5. 1. ARX (add-rotate-XOR)

현대 블록 암호와 해시의 상당수는 '''ARX''' 알고리즘인데, 이는 라운드 함수가 세 가지 연산, 즉 (A) 모듈러 덧셈, (R) 고정된 회전량을 갖는 회전, (X) XOR만을 포함한다.^[18] 이러한 ARX 알고리즘을 사용하는 예시로는 ChaCha20, Speck, XXTEA, BLAKE 등이 있다. 많은 저자들이 이러한 라운드 함수를 설명하기 위해 일종의 데이터 흐름 다이어그램인 ARX 네트워크를 그린다.^[18]

ARX 연산은 하드웨어와 소프트웨어에서 비교적 빠르고 저렴하며, 구현이 매우 간단하고, 또한 고정된 시간 내에 실행되므로 타이밍 공격에 면역성이 있어 널리 사용된다. 회전 암호 분석 기법은 이러한 라운드 함수를 공격하려고 시도한다.

5. 2. 기타 연산

RC5와 RC6에서와 같이 데이터에 따라 바뀌는 회전, 데이터 암호화 표준과 AES에서와 같이 룩업 테이블로 구현된 치환 상자(S-box), 순열 상자(P-box), 그리고 IDEA에서와 같은 곱셈 등은 블록 암호에서 자주 사용되는 연산이다.^[1]

6. 운용 방식

블록 암호 자체로는 암호의 블록 길이만큼의 단일 데이터 블록만 암호화할 수 있다. 가변 길이 메시지의 경우, 데이터를 먼저 별도의 암호 블록으로 분할해야 한다. 가장 간단한 방식은 전자 코드북(ECB) 모드인데, 메시지를 먼저 암호의 블록 크기에 따라 별도의 블록으로 나눈 다음(마지막 블록을 패딩 비트로 확장할 수 있음), 각 블록을 독립적으로 암호화하고 해독한다. 그러나 이러한 단순한 방식은 일반적으로 안전하지 않다. 동일한 평문 블록은 (동일한 키의 경우) 항상 동일한 암호문 블록을 생성하므로, 평문 메시지의 패턴이 암호문 출력에 명확하게 드러나기 때문이다.^[19]

이러한 제한을 극복하기 위해, 여러 가지 블록 암호 운용 방식이 설계되었으며,^[19] 미국 국립표준기술연구소(NIST) 800-38A^[20] 및 연방 BSI TR-02102^[21]와 같은 국가 권고안과 ISO/IEC 10116과 같은 국제 표준에 명시되어 있다.^[22] 일반적인 개념은, 초기화 벡터라고 자주 불리는 추가 입력 값을 기반으로 평문 데이터를 무작위화하여 확률적 암호화라고 하는 것을 생성하는 것이다.

널리 사용되는 암호 블록 체이닝(CBC) 모드에서, 암호화가 안전하려면 평문 메시지와 함께 전달되는 초기화 벡터가 무작위 또는 의사 난수 값이어야 하며, 암호화되기 전에 첫 번째 평문 블록에 배타적-OR 방식으로 더해져야 한다. 결과 암호문 블록은 다음 평문 블록의 새로운 초기화 벡터로 사용된다. 암호 피드백(CFB) 모드는, 자체 동기화 스트림 암호를 에뮬레이션하며, 초기화 벡터를 먼저 암호화한 다음 평문 블록에 더한다. 출력 피드백(OFB) 모드는 초기화 벡터를 반복적으로 암호화하여 키 스트림을 생성하여 동기식 스트림 암호를 에뮬레이션한다. 더 새로운 카운터(CTR) 모드는 이와 유사하게 키 스트림을 생성하지만, 초기화 벡터로 고유하고 (의사)난수가 아닌 값만 필요하다는 장점이 있다. 필요한 난수는 초기화 벡터를 블록 카운터로 사용하고 각 블록에 대해 이 카운터를 암호화하여 내부적으로 파생된다.^[20]

보안 이론적 관점에서, 운용 방식은 의미적 보안이라고 알려진 것을 제공해야 한다. 비공식적으로, 이는 알려지지 않은 키로 암호화된 암호문을 주어졌을 때, 암호문을 보기 전에 알았을 내용 외에, 암호문에서 실질적으로 정보를 얻을 수 없다는 것을 의미한다. 위에서 논의된 모든 방식은 ECB 모드를 제외하고, 소위 선택 평문 공격 하에서 이 속성을 제공하는 것으로 나타났다.

7. 패딩

CBC 모드와 같은 일부 모드는 완전한 평문 블록에서만 작동한다. 메시지의 마지막 블록을 0 비트로 단순히 확장하는 것은 수신자가 패딩 비트 수만 다른 메시지를 쉽게 구별할 수 없기 때문에 충분하지 않다. 더 중요한 것은, 이러한 간단한 해결책은 매우 효율적인 패딩 오라클 공격을 야기한다는 점이다.^[23] 따라서 마지막 평문 블록을 암호의 블록 크기로 확장하려면 적절한 패딩 방식이 필요하다. 표준 및 문헌에 설명된 많은 인기 있는 방식이 패딩 오라클 공격에 취약한 것으로 나타났지만,^[23]^[24] ISO/IEC 9797-1에서 "패딩 방식 2"로 표준화된, 1 비트를 추가한 다음 마지막 블록을 0 비트로 확장하는 솔루션은 이러한 공격에 안전한 것으로 입증되었다.^[24]

8. 암호 분석

블록 암호의 안전성을 평가하고 공격하는 방법에는 여러 가지가 있다. 암호 분석은 암호화 키를 찾거나 암호문을 해독하는 것을 목표로 한다.

블록 암호에 대한 공격 모델은 다음과 같이 나눌 수 있다.

암호문 단독 공격
기지 평문 공격
선택 평문 공격
선택 암호문 공격

블록 크기와 키 크기는 암호의 안전성에 영향을 미친다. 생일 공격과 같은 공격은 블록 크기가 작을수록 더 효과적이다. 하지만 큰 블록 크기는 알고리즘의 효율성을 떨어뜨릴 수 있다. DES는 64비트 블록 크기를 사용했지만, AES와 같은 최신 암호는 128비트 이상의 블록 크기를 지원한다.

쇼트컷 공격은 블록 암호 알고리즘의 약점을 이용하여 키 전수 조사보다 적은 계산량으로 키(의 일부)를 찾는 공격 기법을 통칭한다.

쇼트컷 공격이 존재하는 알고리즘은 학술적으로 "해독 가능"하다고 불리지만, 그에 필요한 계산량이 현실적인지는 고려되지 않는다. 학술적으로 해독 가능하다는 것이 반드시 그 암호를 이용한 시스템의 붕괴로 이어지는 것은 아니다. 그러나 설계자가 상정한 강도를 가지고 있지 않다는 사실은, 그 암호 알고리즘이 신뢰성이 낮은 암호 알고리즘임을 의미한다.

8. 1. 무차별 대입 공격

블록 암호는 원래 키 길이

n

비트에 대해

2^n

이상의 계산적 안전성을 가지지 못한다. 즉, 키를 전수 조사하여 반드시 해독할 수 있다(평균 해독 계산량은 절반인

2^{n-1}

이 된다).^[1]

이는 블록 암호의 키 길이를 정할 때 가장 중요한 요소 중 하나이며, 현재 DES(56비트)가 권장되지 않는 이유도 키 길이가 짧기 때문이다.^[1]

블록 길이

b

가

b 인 경우, 어떤 통신문과 암호문 쌍(pair)에 대해 평균 2^{n-b} 개의 키 후보가 존재한다. 하나의 통신문-암호문 쌍에서는 키 후보 안에 진짜 암호화 키가 존재하지만, 어떤 키 후보가 진짜 암호화 키인지는 판별할 수 없다. p 개의 통신문-암호문 쌍이 존재하고, bp>n 이라면, 진짜 암호화 키를 얻을 수 있을 것으로 기대할 수 있다.

^[1]

8. 2. 차분 분석

차분 공격(차분 암호 해독)은 블록 암호 알고리즘의 약점을 이용하여 키의 전수 탐색 이하의 계산량으로 키(의 일부)를 구하는 쇼트컷 공격(ショートカット法)의 대표적인 기법 중 하나이다. 1989년 Biham에 의해 소개되었다.

차분 공격은 입력 차분과 출력 차분 간의 관계를 분석하여 암호를 해독한다. 이 공격은 다음과 같은 다양한 변형이 존재한다.

불가능 차분 공격
절단 차분 공격
고차 차분 공격
Square 공격
포화 공격
부메랑 공격
보간 공격
선형 합 공격

차분 공격이 가능한 알고리즘은 학술적으로는 "해독 가능"이라고 불리지만, 그에 필요한 계산량이 현실적인지는 고려되지 않는다. 학술적으로 해독 가능하다는 것이 반드시 그 암호를 이용한 시스템의 붕괴로 이어지는 것은 아니다. 그러나 설계자가 상정한 강도를 가지고 있지 않다는 사실은, 그 암호 알고리즘이 신뢰성이 낮은 암호 알고리즘임을 의미한다.

8. 3. 선형 분석

선형 암호 분석은 암호의 작용에 대한 아핀 변환 근사식을 찾는 것을 기반으로 하는 암호 분석의 한 형태이다.^[28] 블록 암호에 대한 가장 널리 사용되는 두 가지 공격 중 하나이며, 다른 하나는 차분 암호 분석이다.^[28]

이 기법은 미쓰루 마쓰이가 발견했으며, 처음으로 이 기술을 FEAL 암호에 적용했다.^[29]

8. 4. 적분 분석

'''적분 암호 분석'''은 치환-순열 네트워크를 기반으로 하는 블록 암호에 특히 적용되는 암호 분석 공격 방법이다. 차분 암호 분석이 고정된 XOR 차이를 가진 선택 평문의 쌍을 사용하는 것과 달리, 적분 암호 분석은 부분은 고정되고 다른 부분은 모든 가능성을 통해 변하는 선택 평문의 집합 또는 멀티셋을 사용한다. 예를 들어, 공격은 8비트를 제외한 모든 비트가 동일하지만, 해당 8비트에서 모두 다른 256개의 선택 평문을 사용할 수 있다. 그러한 집합은 필연적으로 XOR 합이 0이며, 이에 상응하는 암호문 집합의 XOR 합은 암호의 작동에 대한 정보를 제공한다. 텍스트 쌍 간의 차이와 더 큰 텍스트 집합의 합 사이의 이러한 대조는 미적분학의 용어를 차용하여 "적분 암호 분석"이라는 이름을 낳았다.^[12]

8. 5. 기타 기법

차분 공격(차분 암호 해독)
불가능 차분 공격
절단 차분 공격
고차 차분 공격
Square 공격
포화 공격
부메랑 공격
보간 공격
선형 합 공격
선형 공격(선형 암호 해독)
차분 선형 공격
절단 선형 공격
슬라이드 공격
카이제곱 공격
mod n 공격
XSL 공격

9. 증명 가능한 보안

블록 암호의 안전성은 암호화 알고리즘 또는 블록 암호가 "안전하다"는 것을 수학적으로 증명하는 것을 의미한다. 이를 위해 공식적인 정의가 필요하며, CBC와 같은 상위 레벨 알고리즘의 속성을 증명하는 데 사용될 수 있는 두 가지 일반적인 개념이 있다. 이러한 접근 방식을 증명 가능한 보안이라고 한다.
표준 모델에서는 공격자가 무작위 키를 가진 블록 암호와 무작위 순열을 구별할 수 없다는 것을 증명한다.^[1] 이를 위해 다음과 같은 게임을 통해 안전성을 정의한다.

1. 게임 실행자는 동전을 던져 앞면이 나오면 무작위 키 ''K''를 선택해 암호화 함수 ''f'' = ''E''_''K''를 정의하고, 뒷면이 나오면 ''n'' 비트 문자열 집합에 대한 무작위 순열 π를 선택해 함수 ''f'' = π를 정의한다.^[1]

2. 공격자는 ''n'' 비트 문자열 ''X''를 선택하고, 게임 실행자는 ''f''(''X'') 값을 알려준다. 이 단계는 총 ''q''번 반복되며, 이러한 상호작용을 ''쿼리''라고 한다.^[1]

3. 공격자는 동전이 어떻게 나왔는지 추측하고, 맞히면 이긴다.^[1]

이때 공격자는 ''적''으로, 쿼리할 수 있는 함수 ''f''는 ''오라클''로 모델링된다.^[1] 공격자는 무작위로 추측하여 50% 확률로 이길 수 있으므로, 적 ''A''가 ''E''에 대해 이 게임에서 이길 확률 ''P''_''E''(''A'')의 ''이점''은 2(''P''_''E''(''A'') − 1/2)로 정의된다.^[1]

블록 암호 ''E''가 ''의사 난수 순열(PRP)''이라는 것은 ''q''와 공격자의 실행 시간에 제한이 있을 때, 어떤 적도 0보다 상당히 큰 이점을 갖지 않는다는 것을 의미한다.^[1] 만약 적이 ''f''(''X'') 대신 ''f''⁻¹(''X'')를 배울 수 있고, 그럼에도 작은 이점만 있다면 ''E''는 "강력한" PRP (SPRP)가 된다.^[1] 적이 게임 시작 전에 모든 ''q''개의 ''X'' 값을 선택하여 이전 쿼리 정보를 사용하지 않는 경우, 이를 ''비적응적''이라고 한다.^[1]

이러한 정의는 다양한 운용 모드의 안전성을 분석하는 데 유용하며,^[1] 상위 수준 알고리즘이 블록 암호의 보안을 상속한다는 개념을 형식화한 것이다.^[1]

9. 1. 표준 모델

블록 암호가 표준 모델에서 안전하다는 것은 공격자가 무작위 키를 가진 블록 암호와 무작위 순열을 구별할 수 없다는 것을 의미한다.^[1]

좀 더 자세히 설명하면, ''n'' 비트 블록 암호 ''E''에 대해 다음과 같은 게임을 생각해 볼 수 있다.^[1]

1. 게임 실행자는 동전을 던진다.^[1]

앞면이 나오면 무작위 키 ''K''를 선택하고 함수 ''f'' = ''E''_''K''를 정의한다.^[1]
뒷면이 나오면 ''n'' 비트 문자열 집합에 대한 무작위 순열 π를 선택하고 함수 ''f'' = π를 정의한다.^[1]

2. 공격자는 ''n'' 비트 문자열 ''X''를 선택하고, 게임 실행자는 ''f''(''X'') 값을 알려준다.^[1]

3. 2단계는 총 ''q''번 반복된다. (이 ''q''번의 상호작용을 ''쿼리''라고 한다.)^[1]

4. 공격자는 동전이 어떻게 나왔는지 추측하고, 맞으면 이긴다.^[1]

이때 알고리즘으로 모델링할 수 있는 공격자를 ''적''이라고 하며, 공격자가 쿼리할 수 있는 함수 ''f''는 ''오라클''이라고 한다.^[1]

공격자는 무작위로 추측하여 50%의 확률로 이길 수 있다.^[1] 따라서 적 ''A''가 ''E''에 대해 이 게임에서 이길 확률을 ''P''_''E''(''A'')라고 할 때, ''A''의 ''이점''은 2(''P''_''E''(''A'') − 1/2)로 정의된다.^[1] 즉, ''A''가 무작위로 추측하면 이점은 0, 항상 이기면 1이 된다.^[1] 블록 암호 ''E''가 ''의사 난수 순열''(PRP)이라는 것은 ''q''와 공격자의 실행 시간에 제한이 있을 때, 어떤 적도 0보다 상당히 큰 이점을 갖지 않는다는 것을 의미한다.^[1] 만약 2단계에서 적이 ''f''(''X'') 대신 ''f''⁻¹(''X'')를 배울 수 있고, 그럼에도 작은 이점만 있다면 ''E''는 "강력한" PRP (SPRP)가 된다.^[1] 적이 게임 시작 전에 모든 ''q''개의 ''X'' 값을 선택하여 이전 쿼리 정보를 사용하지 않는 경우, 이를 ''비적응적''이라고 한다.^[1]

이러한 정의들은 다양한 운용 모드를 분석하는 데 유용하다는 것이 입증되었다.^[1] 예를 들어, 블록 암호 기반 암호화 알고리즘의 보안을 측정하기 위해 유사한 게임을 정의한 다음, 환원 논증을 통해 이 새로운 게임에서 적이 이길 확률이 어떤 ''A''에 대한 ''P''_''E''(''A'')보다 크게 높지 않음을 보일 수 있다.^[1] 즉, 관련된 모든 ''A''에 대해 ''P''_''E''(''A'')가 작으면, 어떠한 공격자도 새로운 게임에서 이길 상당한 확률을 갖지 않는다.^[1] 이는 상위 수준 알고리즘이 블록 암호의 보안을 상속한다는 개념을 형식화한 것이다.^[1]

9. 2. 이상적인 암호 모델

블록 암호가 주어진 운용 방식에서 사용될 때, 그 결과로 나타나는 알고리즘은 이상적으로는 블록 암호 자체만큼 안전해야 한다. 예를 들어, ECB(Electronic Codebook) 모드는 기본 블록 암호가 아무리 안전하더라도 쉽게 공격받을 수 있어 이 속성을 명확히 결여하고 있다. 반면, CBC(Cipher Block Chaining) 모드는 기본 블록 암호가 안전하다는 가정 하에 안전하다고 증명될 수 있다.

이러한 주장을 하기 위해서는 암호화 알고리즘이나 블록 암호가 "안전하다"는 것이 무엇을 의미하는지에 대한 공식적인 수학적 정의가 필요하다. 블록 암호가 가져야 하는 속성에 대한 두 가지 일반적인 개념은 다음과 같으며, 각 개념은 CBC와 같은 상위 레벨 알고리즘의 속성을 증명하는 데 사용할 수 있는 수학적 모델에 해당한다.

상위 레벨 알고리즘(예: CBC)이 구성 요소(예: 블록 암호)에 대한 명시적으로 언급된 가정을 바탕으로 안전하다는 것을 증명하는 이 일반적인 암호학적 접근 방식은 ''증명 가능한 보안''으로 알려져 있다.
표준 모델비공식적으로, 블록 암호는 공격자가 블록 암호(무작위 키 사용)와 무작위 순열 사이의 차이점을 구별할 수 없는 경우 표준 모델에서 안전하다고 간주된다.

좀 더 정확하게 설명하면 다음과 같은 게임을 통해 안전성을 정의할 수 있다.

1. 게임 실행자는 동전을 던진다.

동전이 앞면이면, 무작위 키 ''K''를 선택하고 함수 ''f'' = ''E''_''K''를 정의한다. (''E''는 ''n'' 비트 블록 암호)
동전이 뒷면이면, ''n'' 비트 문자열 집합에 대한 무작위 순열 를 선택하고 함수 ''f'' = 를 정의한다.

2. 공격자는 ''n'' 비트 문자열 ''X''를 선택하고, 게임 실행자는 ''f''(''X'') 값을 알려준다. 이 단계는 총 ''q''번 반복된다. (''q''번의 상호 작용은 ''쿼리''라고 한다.)

3. 공격자는 동전이 어떻게 나왔는지 추측하여 맞히면 승리한다.

여기서 공격자는 ''적''으로, 쿼리할 수 있는 함수 ''f''는 ''오라클''로 모델링된다.

공격자는 무작위로 추측하여 50%의 확률로 승리할 수 있다. 따라서, 적 ''A''가 ''E''에 대해 이 게임에서 이길 확률을 ''P''_''E''(''A'')라 하고, ''A''의 ''이점''을 2(''P''_''E''(''A'') − 1/2)로 정의한다. 블록 암호 ''E''가 ''의사 난수 순열''(PRP)이라는 것은, ''q''와 공격자의 실행 시간에 제한이 있을 때, 어떤 적도 0보다 상당히 큰 이점을 갖지 않는다는 것을 의미한다. 만약 적이 ''f''(''X'') 대신 ''f''⁻¹(''X'')를 배울 수 있는 옵션이 주어지고, 여전히 작은 이점만 있다면, ''E''는 "강력한" PRP (SPRP)이다. 적은 게임 시작 전에 모든 ''q''개의 ''X'' 값을 선택하는 경우(이전 쿼리의 정보를 사용하지 않음) ''비적응적''이다.

이러한 정의는 다양한 운용 모드의 안전성을 분석하는 데 유용하다. 예를 들어, 블록 암호 기반 암호화 알고리즘의 보안을 측정하기 위해 유사한 게임을 정의하고, 환원 논증을 통해 이 게임에서 적이 이길 확률이 어떤 ''A''에 대한 ''P''_''E''(''A'')보다 크게 높지 않음을 보일 수 있다. 이는 상위 수준 알고리즘이 블록 암호의 보안을 상속한다는 개념을 공식화한 것이다.

10. 실제 평가

블록 암호는 실제 사용 환경에서 여러 기준에 따라 평가될 수 있다. 일반적인 평가 요소는 다음과 같다.^[30]

평가 요소	설명
키 크기 및 블록 크기	암호 보안의 상한을 제공한다.
추정 보안 수준	암호 해독에 대한 내성, 수학적 건전성, 실제 공격의 존재 여부를 기반으로 한다.
복잡성	하드웨어나 소프트웨어 구현의 복잡성을 의미하며, 자원 제약 장치에서 중요하다. 하드웨어 구현에서는 게이트 수나 에너지 소비량으로 측정할 수 있다.
성능	다양한 플랫폼에서의 처리량, 메모리 요구 사항 등을 포함한다.
비용	지적 재산권으로 인한 라이선스 요구 사항을 의미한다.
유연성	다양한 키 크기 및 블록 길이를 지원하는 기능을 의미한다.

큰 블록 크기는 생일 공격에 대한 보안을 강화하지만, 알고리즘 작동 효율성을 떨어뜨릴 수 있다. DES는 64비트 블록 크기를 사용했지만, AES와 같은 최신 설계는 128비트 이상의 블록 크기를 지원한다.

11. 주요 블록 암호

현대적인 블록 암호 설계는 반복적인 곱 암호 개념을 기반으로 한다. 클로드 섀넌은 1949년 저서 ''비밀 시스템의 통신 이론''에서 곱 암호를 대체 암호와 전치 암호 같은 간단한 연산을 결합하여 보안을 효과적으로 향상시키는 수단으로 제안했다.^[5] 호르스트 파이스텔의 이름을 딴 파이스텔 네트워크는 DES 암호에서 특히 구현되었고,^[6] AES와 같은 다른 많은 블록 암호는 대체-순열 네트워크로 분류된다.

지불 카드 산업 데이터 보안 표준 (PCI DSS) 및 미국 국립 표준 협회 (ANSI) 표준 내에서 사용되는 모든 암호화 블록 형식의 근원은 아탈라 키 블록 (AKB)이며, 이는 최초의 하드웨어 보안 모듈 (HSM)인 아탈라 박스의 핵심 혁신이었다. AKB는 대칭 키 또는 PIN을 은행 산업의 다른 주체와 안전하게 교환하는 데 필요한 키 블록이었다.^[7] 아탈라 박스는 1998년 기준으로 가동 중인 모든 ATM 네트워크의 90% 이상을 보호했으며,^[8] 2014년 기준으로 여전히 전 세계 ATM 거래의 대다수를 보호하고 있다.^[9]

1977년 미국 국립 표준국(이후 미국 국립 표준 기술 연구소, NIST)에 의한 DES 암호의 출판은 현대 블록 암호 설계에 대한 대중의 이해에 근본적인 영향을 미쳤고, 암호 분석 공격의 학문적 발전에도 영향을 미쳤다. 차분 암호 분석과 선형 암호 분석 모두 DES 설계 연구에서 비롯되었다.

역사적으로 중요하거나 널리 사용되는 주요 블록 암호에는 Lucifer/DES, IDEA, RC5, Rijndael/AES, Blowfish 등이 있다.

Lucifer/DES: 1970년대 IBM에서 개발된 초기 블록 암호로, 이후 미국 정부 표준으로 채택되었다. 56비트의 짧은 키 길이로 인해 보안 취약성이 제기되었다.
IDEA: DES를 대체하기 위해 1991년 개발되었다. 128비트 키와 64비트 블록에서 작동한다.
RC5: 1994년 로널드 리베스트가 설계했으며, 가변 블록 크기, 키 크기, 라운드 수를 갖는다.
Rijndael/AES: DES를 대체하기 위해 개발되었다. 128비트 블록 크기와 128, 192 또는 256비트 키 크기를 갖는다.
Blowfish: 1993년 브루스 슈나이어가 설계했으며, 64비트 블록 크기와 가변적인 키 길이를 가진다. 특허가 없고 공개 도메인에 있다.

암호 표준으로 채택(혹은 권장)된 블록 암호는 다음과 같다.

비트 수	이름	표준
64비트	TDEA	ISO/IEC 18033, CRYPTREC
64비트	MISTY1	ISO/IEC 18033, CRYPTREC, NESSIE
64비트	CAST-128	ISO/IEC 18033
64비트	CIPHERUNICORN-E	CRYPTREC
64비트	Hierocrypt-L1	CRYPTREC
64비트	MULTI2	ARIB 한정 수신 방식
64비트	KASUMI	3GPP W-CDMA 및 GSM용 암호
128비트	AES	ISO/IEC 18033, CRYPTREC, NESSIE
128비트	Camellia	ISO/IEC 18033, CRYPTREC, NESSIE
128비트	SEED	ISO/IEC 18033
128비트	CIPHERUNICORN-A	CRYPTREC
128비트	Hierocrypt-3	CRYPTREC
128비트	SC2000	CRYPTREC
256비트	SHACAL-2	NESSIE

11. 1. Lucifer / DES

루시퍼는 1970년대 IBM에서 호르스트 페이스텔의 연구를 바탕으로 개발된 초기 민간 블록 암호 중 하나이다. 이 알고리즘의 수정된 버전은 미국 정부 연방 정보 처리 표준으로 채택되어 FIPS PUB 46 데이터 암호화 표준(DES)이 되었다.^[32] DES는 1976년에 공개되어 널리 사용되었다.

DES는 NSA에 알려져 있었고 IBM에 의해 재발견되었지만, 1980년대 후반 엘리 비함과 아디 샤미르에 의해 재발견되어 공개되기 전까지는 알려지지 않았던 특정 암호 분석 공격에 저항하도록 설계되었다. 이 기법은 차분 암호 분석이라고 불리며, 블록 암호에 대한 몇 안 되는 일반적인 공격 중 하나이다. 선형 암호 분석도 다른 공격 기법이지만, 미츠루 마츠이에 의해 공개되기 전에는 NSA조차 알지 못했을 수 있다.

DES는 64비트 블록 크기와 56비트 키 크기를 가진다. 1970년대 많은 관찰자들은 DES에 사용된 56비트 키 길이가 너무 짧다고 언급했다. 시간이 지남에 따라, 특히 전자 프론티어 재단이 1998년에 DES를 해독하도록 설계된 특수 목적 머신을 시연한 후, 그 부적절함이 분명해졌다. DES의 확장인 트리플 DES는 두 개의 독립적인 키(112비트 키 및 80비트 보안) 또는 세 개의 독립적인 키(168비트 키 및 112비트 보안)로 각 블록을 세 번 암호화하여 이러한 문제를 해결하였다. 2011년 현재, 세 개의 키를 사용하는 버전은 여전히 안전하다고 간주되지만, 국립 표준 기술 연구소(NIST) 표준은 80비트 보안 수준으로 인해 새로운 애플리케이션에서 두 개의 키를 사용하는 버전의 사용을 더 이상 허용하지 않는다.^[33]

11. 2. IDEA

국제 데이터 암호화 알고리즘(IDEA)은 스위스 취리히 연방 공과대학교(ETH Zurich)의 제임스 매시와 라이쉐자가 설계한 블록 암호이며, 1991년에 처음 공개되어 DES를 대체할 목적으로 개발되었다.

IDEA는 128비트 키를 사용하여 64비트 블록에서 작동하며, 8개의 동일한 변환(''라운드'')과 출력 변환(''하프 라운드'')으로 구성된다. 암호화 및 복호화 과정은 유사하다. IDEA는 서로 다른 군에서 연산을 섞어 보안성을 강화하는데, 여기에는 모듈러 덧셈과 곱셈, 그리고 비트 단위 ''배타적 논리합 (XOR)''이 포함되며, 이러한 연산들은 대수적으로 "호환되지 않는다".

설계자들은 IDEA가 차분 공격에 얼마나 강력한지 분석했고, 특정 가정 하에서 안전하다고 결론 내렸다. 선형 암호 분석 또는 대수적 약점에 대한 성공적인 보고는 없었다.

11. 3. RC5

RC5는 1994년 로널드 리베스트가 설계한 블록 암호로, 가변 블록 크기(32, 64 또는 128비트), 키 크기(0~2040비트), 라운드 수(0~255)를 갖는 점이 특징이다. 원래 제안된 매개변수는 64비트 블록 크기, 128비트 키, 12라운드였다.

RC5의 핵심은 데이터 종속 회전을 사용한다는 것이다. RC5는 모듈러 덧셈과 XOR로 구성되며, 알고리즘의 일반적인 구조는 Feistel 유사 네트워크이다. 암호화 및 복호화 루틴은 몇 줄의 코드로 나타낼 수 있다. 키 스케줄은 더 복잡하며, e와 황금비의 이진 확장을 "아무것도 없는 숫자"의 소스로 사용하여 본질적으로 일방향 함수로 키를 확장한다. 이러한 단순함과 데이터 종속 회전의 참신함은 암호 분석가들에게 RC5를 매력적인 연구 대상으로 만들었다.

12라운드 RC5(64비트 블록)는 2⁴⁴개의 선택된 평문을 사용하는 차분 공격에 취약하다. 18~20 라운드가 충분한 보호를 제공하는 것으로 제안된다.

11. 4. Rijndael / AES

조안 다에멘과 빈센트 라이멘이 개발한 ''Rijndael'' 암호는 DES를 대체하기 위한 5년간의 공개 경쟁에서 우승하여 AES(고급 암호화 표준)가 되었다.^[41]

2001년 NIST에 의해 채택된 AES는 고정된 블록 크기 128비트와 키 크기 128, 192 또는 256비트를 갖는 반면, Rijndael은 최소 128비트에서 32비트의 배수인 모든 블록과 키 크기로 지정할 수 있다. 블록 크기는 최대 256비트이지만 키 크기는 이론적으로 제한이 없다. AES는 바이트의 4×4 열 우선 순서 행렬, 즉 ''상태''에서 작동한다 (Rijndael의 더 큰 블록 크기 버전은 상태에 추가 열이 있다).

11. 5. Blowfish

'''블로우피시'''는 1993년 브루스 슈나이어가 설계한 블록 암호로, 다수의 암호 제품군 및 암호화 제품에 포함되어 있다. 블로우피시는 64비트 블록 크기와 1비트에서 최대 448비트까지의 가변적인 키 길이를 가지며,^[35] 16라운드 Feistel 암호이자, 키에 종속적인 대형 S-box를 사용한다. 설계에서 주목할 만한 특징은 키에 종속적인 S-box와 매우 복잡한 키 스케줄이다.

블로우피시는 노후화된 DES의 대안이자, 다른 알고리즘과 관련된 문제와 제약에서 벗어난 범용 알고리즘으로 설계되었다. 블로우피시가 출시되었을 당시, 다른 많은 설계들은 특허로 보호되거나, 상업적/정부 기밀이었다. 슈나이어는 "블로우피시는 특허가 없으며, 모든 국가에서 특허가 유지되지 않을 것이다. 이 알고리즘은 여기에 공개 도메인에 배치되며, 누구든지 자유롭게 사용할 수 있다."라고 밝혔다. 이는 슈나이어의 후속 알고리즘인 투피시에도 적용된다.

12. 일반화

M. 리스코브, R. 리베스트, D. 와그너는 "tweakable" 블록 암호라는 일반화된 버전의 블록 암호를 설명했다.^[36] Tweakable 블록 암호는 일반적인 평문 또는 암호문 입력 외에 'tweak'라고 불리는 두 번째 입력을 받는다. Tweak은 키와 함께 암호가 계산하는 순열을 선택한다. Tweak 변경이 (키 설정 작업과 비교하여) 가볍다면, 새로운 작동 모드가 가능해진다. 디스크 암호화 이론 문서는 이러한 모드 중 일부를 설명한다.

블록 암호는 전통적으로 알파벳의 이진법을 사용하지만, 다른 알파벳을 사용하는 블록 암호를 원할 수도 있다. 예를 들어, 16자리 신용카드 번호를 암호화하여 암호문도 16자리가 되도록 하는 것은 ''형식 보존 암호화''의 예시이다. 형식 보존 암호화는 유한한 형식 언어에 대한 키가 지정된 순열을 필요로 한다.

12. 1. Tweakable 블록 암호

M. 리스코브, R. 리베스트, D. 와그너는 "tweakable" 블록 암호라는 블록 암호의 일반화된 버전을 설명했다.^[36] Tweakable 블록 암호는 일반적인 평문 또는 암호문 입력 외에 'tweak'라고 불리는 두 번째 입력을 받는다. Tweak은 키와 함께 암호가 계산하는 순열을 선택한다. Tweak 변경이 (일반적으로 상당히 비용이 많이 드는 키 설정 작업과 비교하여) 충분히 가볍다면, 몇 가지 흥미로운 새로운 작동 모드가 가능해진다. 디스크 암호화 이론 문서는 이러한 모드 중 일부를 설명한다.

12. 2. 형식 보존 암호화

블록 암호는 전통적으로 알파벳의 이진법을 사용한다. 즉, 입력과 출력 모두 0과 1로 구성된 ''n'' 비트의 이진 문자열이다. 그러나 어떤 상황에서는 다른 알파벳을 사용하는 블록 암호를 원할 수 있다. 예를 들어, 16자리 신용카드 번호를 암호화하여 암호문도 16자리가 되도록 하면 기존 소프트웨어에 암호화 계층을 추가하는 데 도움이 될 수 있다. 이것이 ''형식 보존 암호화''의 예시이다. 더 일반적으로, 형식 보존 암호화는 어떤 유한한 형식 언어에 대한 키가 지정된 순열을 필요로 한다. 이는 형식 보존 암호화 방식을 (조정 가능한) 블록 암호의 자연스러운 일반화로 만든다. 반대로, CBC와 같은 전통적인 암호화 방식은 고정된 키를 사용하더라도 동일한 평문이 여러 다른 암호문으로 암호화될 수 있기 때문에 순열이 아니다.

13. 다른 암호 요소와의 관계

블록 암호는 다른 암호 요소들을 만드는 데 사용될 수 있다. 마치 레고 블록처럼, 블록 암호를 이용해서 더 복잡하고 다양한 기능을 하는 암호 시스템을 만들 수 있는 것이다.

스트림 암호: OFB 모드나 CTR 모드와 같은 블록 암호 운용 방식을 사용하면 블록 암호를 스트림 암호처럼 작동하게 만들 수 있다. 스트림 암호는 데이터 흐름을 실시간으로 암호화하는 데 유용하다.
암호화 해시 함수: 블록 암호를 사용해서 일방향 압축 함수를 만들고, 이를 통해 암호화 해시 함수를 구축할 수 있다.^[37] One-way compression function^영어는 데이터를 한 방향으로만 압축하는 함수로, 원래 데이터로 되돌릴 수 없다. 이러한 해시 함수는 데이터의 무결성을 확인하는 데 사용된다.
암호학적으로 안전한 의사 난수 생성기 (CSPRNG): 블록 암호를 사용하면 진짜 난수와 구별하기 어려운 가짜 난수를 만들 수 있다.^[38] 이러한 난수는 암호 시스템에서 중요한 역할을 한다.
의사 난수 순열: 블록 암호를 사용하면 특정 집합 안에서 순서를 섞는 안전한 방법을 만들 수 있다. 형식 보존 암호화를 참고하면 된다.
메시지 인증 코드 (MAC): 블록 암호는 메시지가 변조되지 않았는지 확인하는 데 사용되는 메시지 인증 코드를 만드는 데에도 사용된다. CBC-MAC, OMAC, PMAC 등이 그 예시이다.
인증된 암호화: 블록 암호를 사용하면 데이터를 암호화하는 동시에 데이터가 변조되지 않았음을 보장하는 인증된 암호화를 수행할 수 있다. CCM, EAX, GCM, OCB 등이 이러한 기능을 제공한다.

이처럼 블록 암호는 다양한 암호 시스템의 핵심 구성 요소로 활용될 수 있다. 하지만 이러한 요소들이 안전하게 작동하려면 블록 암호를 올바르게 사용해야 한다.

14. 안전성

블록 암호는 암호화 알고리즘( $E$ )과 복호화 알고리즘( $D$ ) 두 가지로 구성된다.^[1] 두 알고리즘은 각각 $n$ 비트의 입력 블록과 $k$ 비트의 키를 입력받아 $n$ 비트의 출력 블록을 생성한다. 복호화 알고리즘 $D$ 는 암호화의 역함수로, $D = E^{-1}$ 이다.^[2]^[3]

블록 암호는 다음과 같은 암호화 함수로 표현된다.

: $E_K(P) := E(K,P): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n,$

여기서 $K$ 는 키(키 크기 $k$ 비트), $P$ 는 평문(블록 크기 $n$ 비트), $C$ 는 암호문( $n$ 비트)이다. 각 $K$ 에 대해, 함수 $E_K(P)$ 는 $\{0,1\}^n$ 에서 가역적인 매핑이어야 한다. $E$ 의 역은 다음과 같다.

: $E_K^{-1}(C) := D_K(C) = D(K,C): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n,$

키 $K$ 와 암호문 $C$ 를 입력으로 받아 평문 $P$ 를 반환하며, 다음을 만족한다.

: $\forall P: D_K(E_K(P)) = P.$

예를 들어, 128비트 블록 암호는 128비트 평문을 128비트 암호문으로 변환하며, 이 변환은 비밀 키에 의해 제어된다. 복호화는 128비트 암호문과 비밀 키를 사용하여 원래의 128비트 평문을 생성한다.^[4] 각 키 ''K''에 대해, ''E_K''는 입력 블록 집합에 대한 순열이다.

블록 암호는 $b$ 비트의 블록과 $n$ 비트의 키를 입력으로 받아 $b$ 비트의 블록을 출력하며, 암호화 $E$ 와 복호화 $E^{-1}$ 알고리즘으로 구성된다. 임의의 키 $k$ 에 대해 복호화 알고리즘은 암호화 알고리즘의 역함수이다.

: $E_k^{-1}(E_k(m))=m$

( $m$ 은 임의의 블록)

평문은 암호화 알고리즘의 입력 블록 및 복호화 알고리즘의 출력 블록이고, 암호문은 암호화 알고리즘의 출력 블록 및 복호화 알고리즘의 입력 블록이다. 암호 운용 방식은 임의의 길이의 평문을 처리하고, 블록 암호가 결정적 암호이기 때문에 발생하는 동일 평문에 대한 동일 암호문 문제를 해결한다.

DES, 트리플 DES, AES 등이 대표적인 블록 암호이다.

블록 암호는 키 길이 $n$ 비트에 대해 $2^n$ 이상의 계산적 안전성을 가지지 못하며, 키 전수 조사로 해독 가능하다. 또한, 다양한 쇼트컷 공격과 사이드 채널 공격에 취약할 수 있다.

14. 1. 계산적 안전성

블록 암호는 원래 키 길이

n

비트에 대해

2^n

이상의 계산적 안전성을 가지지 못한다. 즉, 키의 전수 조사로 반드시 해독이 가능하다(평균 해독 계산량은 절반인

2^{n-1}

이 된다). 이것은 블록 암호의 키 길이를 정할 때 가장 중요한 요소 중 하나이며, 현재 DES(56비트)가 권장되지 않는 것도 그 키 길이의 짧음이 원인 중 하나이다.

다만, 블록 길이

b

가

b 인 경우, 어떤 통신문과 암호문 쌍(pair)에 대해 평균적으로 2^{n-b} 의 키 후보가 존재한다. 하나의 통신문-암호문 쌍에서는 키 후보 안에 진짜 암호화 키가 존재하지만, 어떤 키 후보가 진짜 암호화 키인지는 판별할 수 없다. p 개의 통신문-암호문 쌍이 존재하고, bp>n 이라면, 진짜 암호화 키를 얻을 수 있을 것으로 기대할 수 있다.

14. 2. 쇼트컷 공격

키 전수 조사보다 적은 계산량으로 키를 알아내는 다양한 공격 기법을 통칭하여 쇼트컷 공격이라고 부른다. 쇼트컷 공격에는 많은 종류가 있지만, 대표적인 것은 다음과 같다.

차분 공격(차분 암호 해독)
불가능 차분 공격
절단 차분 공격
고차 차분 공격
Square 공격
포화 공격
부메랑 공격
보간 공격
선형 합 공격
선형 공격(선형 암호 해독)
차분 선형 공격
절단 선형 공격
슬라이드 공격
카이제곱 공격
mod n 공격
XSL 공격

쇼트컷 공격이 존재하는 알고리즘은 학술적으로는 "해독 가능"이라고 불리지만, 그에 필요한 계산량이 현실적인지는 고려되지 않는다. 학술적으로 해독 가능하다는 것이 반드시 그 암호를 이용한 시스템의 붕괴로 이어지는 것은 아니다. 그러나 설계자가 상정한 강도를 가지고 있지 않다는 사실은, 그 암호 알고리즘이 신뢰성이 낮은 암호 알고리즘임을 의미한다.

14. 3. 사이드 채널 공격

사이드 채널 공격은 하드웨어나 소프트웨어에 구현된 암호를 알고리즘이 아닌 소비 전력이나 실행 시간 등의 정보를 사용하여 공격하는 기법이다. 사이드 채널 공격은 구현과 알고리즘 모두에 영향을 받는다.

단순 전력 분석 (Simple Power Analysis)
전력 차분 분석 (Differential Power Analysis)
타이밍 공격 (Timing attack)

참조

_[1] 서적 Cryptographic Boolean functions and applications https://books.google[...] Academic Press
_[2] 서적 Handbook of Applied Cryptography http://cacr.uwaterlo[...] CRC Press 2012-07-15
_[3] 간행물 Introduction to Modern Cryptography http://www.cs.ucdavi[...] 2005-05-11
_[4] 서적 Cryptographic Engineering Springer
_[5] 논문 Communication Theory of Secrecy Systems http://netlab.cs.ucl[...] 2012-04-09
_[6] 서적 Encyclopedia of Cryptography and Security https://books.google[...] Springer
_[7] 웹사이트 The Benefits of the Atalla Key Block https://content.hsm.[...] 2019-08-16
_[8] 웹사이트 Electronic Business without Fear: The Tristrata Security Architecture http://www.standarda[...]
_[9] 웹사이트 Key Management a Fast Growing Space https://securitycurr[...] IT-Harvest 2014-06-17
_[10] 서적 Advanced Linear Cryptanalysis of Block and Stream Ciphers https://books.google[...] IOS Press
_[11] 서적 Serious Cryptography: A Practical Introduction to Modern Encryption https://books.google[...] No Starch Press 2017-11-06
_[12] 서적 Selected areas in cryptography: 6th annual international workshop, SAC'99, Kingston, Ontario, Canada, August 9–10, 1999 : proceedings https://archive.org/[...] Springer
_[13] 서적 Selected areas in cryptography: 13th international workshop, SAC 2006, Montreal, Canada, August 17–18, 2006 : revised selected papers Springer
_[14] 서적 Cryptographic Boolean functions and applications https://books.google[...] Academic Press
_[15] 서적 Introduction to modern cryptography https://archive.org/[...] CRC Press
_[16] 서적 2013 Annual International Conference on Emerging Research Areas and 2013 International Conference on Microelectronics, Communications and Renewable Energy 2013
_[17] 서적 Block Cipher Cryptanalysis: An Overview Indian Statistical Institute
_[18] 서적 Progress in cryptology-- INDOCRYPT 2012 : 13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012, proceedings Springer 2012
_[19] 웹사이트 Block Cipher Modes http://csrc.nist.gov[...] NIST Computer Security Resource Center 2017-01-04
_[20] 간행물 Recommendation for Block Cipher Modes of Operation – Methods and Techniques http://csrc.nist.gov[...] National Institute of Standards and Technology (NIST) 2001-12
_[21] Technische Richtlinie Kryptographische Verfahren: Empfehlungen und Schlüssellängen 2008-06-20
_[22] 웹사이트 ISO/IEC 10116:2006 Information technology — Security techniques — Modes of operation for an n-bit block cipher http://www.iso.org/i[...]
_[23] 서적 Advances in Cryptology — EUROCRYPT 2002 Springer Verlag
_[24] 서적 Security and Cryptography for Networks Springer Verlag
_[25] 간행물 ISO/IEC 9797-1: Information technology – Security techniques – Message Authentication Codes (MACs) – Part 1: Mechanisms using a block cipher http://www.iso.org/i[...] ISO/IEC
_[26] 서적 Everyday Cryptography: Fundamental Principles and Applications https://books.google[...] Oxford University Press
_[27] 서적 Understanding Cryptography: A Textbook for Students and Practitioners https://books.google[...] Springer
_[28] 논문 Linear Cryptanalysis of DES Cipher http://ftp.esat.kule[...]
_[29] conference A new method for known plaintext attack of FEAL cipher
_[30] 간행물 Report on the Development of the Advanced Encryption Standard (AES) http://csrc.nist.gov[...] National Institute of Standards and Technology (NIST) 2000-10
_[32] 문서 FIPS PUB 46-3 Data Encryption Standard (DES) http://csrc.nist.gov[...]
_[33] 웹사이트 NIST Special Publication 800-57 Recommendation for Key Management — Part 1: General (Revised), March, 2007 http://csrc.nist.gov[...] 2014-06-06
_[35] 논문 Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish) http://www.schneier.[...]
_[36] 논문 Tweakable Block Ciphers http://www.cs.colora[...]
_[37] 웹사이트 ISO/IEC 10118-2:2010 ''Information technology — Security techniques — Hash-functions — Part 2: Hash-functions using an n-bit block cipher'' http://www.iso.org/i[...]
_[38] 논문 NIST Special Publication 800-90A ''Recommendation for Random Number Generation Using Deterministic Random Bit Generators'' http://csrc.nist.gov[...]
_[39] 문서 Minimalism in Cryptography: The Even–Mansour Scheme Revisited http://eprint.iacr.o[...]
_[40] 문서 KASUMI처럼 복호가 정의되지 않은 블록 암호도 있다
_[41] 논문 The Data Encryption Standard (DES) and its strength against attacks http://www.research.[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com