5주차 암호학 정리

1. AES

 

= Advanced Encryption Standard

 

• DES가 더 이상 안전하지 않게 되어, 2001년 새 표준으로 선정된 블록 암호 알고리즘.
• (AES, DES는 모두 블록 암호 알고리즘이다)
• 전세계에서 공모받은 암호 알고리즘 중 심사를 거쳐 선정된 가장 뛰어난 알고리즘.
• 보안성, 효율성, 이식 적합성, 유연성 등에서 Rijndael 구조 채택
• -> 세계적인 논의를 통해 선정된 표준이므로 정보당국 등의 백도어 설치 위험성 배제 가능

 

• 표준 선정 이래로 치명적인 취약점 발견 x
• 제조사들이 전용 명령어를 정의해 주어 암/복호화 성능 뛰어남
• => 현대에서는 대칭키 암호 알고리즘으로 일반적으로 AES 사용

 

• 갈루아 필드(Galois Field)
• 체(Field)
• 군(Group)

 

1-1. SPN (Substitution Permutation Network)

= AES에서 사용하는 암호 구조

• 곱 암호의 일종
• 치환(Substitution, S-Box 사용)과 순열(Permutation, P-Box 사용)을 여러 라운드에 걸쳐 반복
• 라운드마다 입력 전체에 라운드 함수 적용
• -> 라운드 수가 같으면 SPN이 페이스텔 구조 대비 2배의 암호학적 안전성을 가짐

 

라운드마다 128bit 크기의 블록을 암호화한다

키 길이는 128, 192, 256비트 중 하나 선택

키 길이에 따라 AES-128, 192, 256이라고 부름

라운드 수는 키 길이에 따라 10, 12, 14로 결정

 

 

 

1. 각 블록을 4행 4열의 상태 배열(State)로 재구성 (각 칸에 1Byte씩)
2. 재구성된 입력에 대해 AddRoundKey 함수 적용
3. 매 라운드마다 SubBytes, ShiftRows, MixColumns, AddRoundKey 함수 반복 적용
4. 마지막 라운드에서는 MixColumns를 제외하고 나머지 함수들만 적용

 

위 라운드 함수들에는 역함수가 존재 -> 역함수를 이용해 복호화

 

 

 

1) SubBytes

: State의 각 바이트를 S-Box를 참조하여 치환하는 함수

• 바이트의 상위 4비트가 행, 하위 4비트가 열 결정
• ex) 2A -> S-Box의 2행 A열 참조 -> E5로 치환

 

 

2) ShiftRows

: 각 행을 구성하는 바이트들을 쉬프트하는 함수

• 4가지 함수 중 유일하게 순열의 역할 수행
• 2행은 왼쪽으로 1칸, 3행은 2칸, 4행은 3칸 쉬프트
• (복호화할 때는 오른쪽으로)

 

 

3) MixColumns

: 열 단위로 치환을 수행하는 함수

갈루아 필드 내에서의 행렬 연산으로 계산

 

 

4) AddRoundKey

: 키 생성 함수(Key schedule)로 생성된 라운드 키의 state를 각 바이트별로 XOR

복호화 시에는 XOR의 성질을 이용해 동일한 키를 state에 XOR

 

 

5) Key Schedule

: 입력된 키로부터 각 라운드에 쓰일 라운드 키를 생성하는 함수

• 암복호화를 시작할 때와 매 라운드마다 적용됨
• ex) AES-128은 총 10라운드가 있으므로 라운드 키는 11개 필요

 

• 각 라운드 키는 4*4 행렬 -> 4*44열의 키 행렬 생성, 4열씩 나눠서 라운드마다 사용
• 처음 4열은 입력된 4열을 그대로 사용
• 그 다음 4열부터는 현재 자리에 있는 4열에 RotWord, SubWord, Rcon을 적용한 뒤
• 이전 4열과 XOR하여 생성

 

RotWord : 열을 위로 한 번 시프트

SubWord : SubBytes에서 사용한 S-Box를 사용해 각 바이트 치환

Rcon : R=[01,02,04,08,10,20,40,80,1B,36] | R에 대해, Wi​의 최상위 바이트를 R[i/4−1]과 XOR

 

---

2. DES

= Data Encryption Standard

• 미국 국가안보국에서 IBM의 루시퍼 알고리즘을 개량해 만든 대칭키 암호
• 루시퍼의 128비트 대비 절반인 56비트 키 사용, 내부 알고리즘 일부 변경
• 과거 표준이었던 블록 암호. 현대에는 공격 기법이 많이 연구되어 표준으로 사용하지 않음

 

• 8바이트를 한 블록으로 한다.
• 초기 순열(Initial Permutation, IP), 최종 순열(Final Firmutation, FP), Feistel로 이루어진 16라운드를 가진다.
• 각 라운드에는 48비트의 키가 사용되며, 이 키를 생성하는 키 생성 함수(Key Generation)가 있다.

 

2-1. 순열, 치환, 곱 암호

 

• 치환(Substitution): DES에서 혼돈 성질을 만족하기 위해 사용된다.
• 순열(Permutation): DES에서 확산 성질을 만족하기 위해 사용된다.

 

이들은 매우 단순한 연산이므로 한 번 사용한다고 해서 암호학적 효과를 기대할 수는 없으나

여러 번 교차해 반복적용하면 혼돈/확산 성질을 모두 만족하게 된다.

이러한 단순 연산들로 한 라운드를 구성하고 -> 각 라운드를 여러 번 반복하여 안전성을 확보하는 암호를

곱 암호(Product Cipher)라고 한다.

(DES 외에도 많은 현대 블록 암호들이 이 구조를 차용하고 있다.)

 

 

2-2. 페이스텔 구조

: 입력으로 들어온 블록을 좌/우로 이등분한 뒤

우측 블럭은 그대로 다음 라운드의 좌측으로 입력시키고

좌측 블럭은 우측 블럭에 라운드 함수(F)를 적용한 값과 XOR해 다음 라운드의 우측으로 입력시키는 교차구조

 

특징

• 블록 암호는 복호화를 위해 역함수를 두나, 페이스텔 구조의 경우 F가 복호화 과정에서 XOR로 상쇄되므로 역함수 불필요
• 암/복호화의 구조가 동일하여 암호화 시 사용한 라운드 키를 역순으로 입력하면 복호화 가능
• 우측 블럭은 아무 처리 없이 다음 라운드로 넘어가므로 안전성을 위해서는 2베 정도 많은 라운드가 필요

 

 

2-3. DES의 과정

 

초기 순열/최종 순열

• 시작할 때 초기 순열(IP), 마지막에 최종 순열(FP) 수행
• (정해진 테이블을 이용해 64비트 입력을 비트 단위로 전치.
• 테이블에서 n번째 값이 m이라면 출력 n번째 비트는 입력 m번째 비트)
• 각각 초기 순열 테이블(IP Table, IPT)과 최종 순열 테이블(FP Table, FPT) 이용
• 초기 순열과 최종 순열은 서로 역관계.
• 임의 데이터에 초기 순열-최종 순열을 차례로 적용하면 데이터값이 그대로 나옴
• DES의 안전성을 증가시키지는 않으나 하드웨어에 구현하기 쉽게 함

 

라운드 함수(F)

• 오른쪽 블록만 입력됨 => 입력값 길이는 32비트
• 확장 순열(Expansion P-Box) : 입력을 비트 단위로 전치하는 동시에 전체 길이를 48비트로 확장
• 입력값(32비트)을 4비트씩 8등분, 테이블을 참조해 각각을 6비트로 확장
• 라운드 키 결합(XOR) : 확장 순열로 나온 출력을 라운드 키 K와 XOR
• 치환 테이블(S-Box) : 라운드 키 결합에서 출력된 48비트 결과값을 32비트로 축소
• 고정 순열(Straight P-Box) : 축소 후 다시 비트 단위 전치 (타 순열 과정과 동일)

 

키 생성 함수

• 64비트 입력을 받아 각 라운드에 필요한 48비트 라운드 키를 생성하는 함수
• 패리티 비트 제거(Parity Bit Drop) : 입력에서 패리티 비트를 제거하고 남은 56비트에 순열을 적용하는 과정
• (패리티 비트 : 통신 중에 비트 반전(에러)이 일어나지 않았음을 보증하는 비트)
• 쉬프트(Shift) : 입력을 좌우 28비트씩 나누어 각각을 1~2비트만큼 왼쪽으로 순환 쉬프트하는 과정
• 압축 순열(Compression P-Box) : 56비트의 입력을 48비트 길이로 압축하는 과정

 

 

 

2-4. DES의 응용

 

다중 DES

: 서로 다른 키를 사용하는 DES 모듈을 여러 개 이어붙여 약점을 보완한 암호 시스템

• 이중 DES(Double/2-DES)는 112비트, 삼중 DES(Triple/3-DES)는 168비트 키 사용
• 이중은 한번 DES를 적용한 출력값을 한 번 더 DES의 입력값으로 사용하는 방식
• 삼중은 한번 DES를 사용한 뒤, 그것을 복호화하여 다시 암호화하는 방식
• (복호화 시의 키를 그 다음 암호화할 때의 키와 같게 하면 두 키가 상쇄되어 첫 번째 키만을 갖는 단일 DES로도 사용가능하기 때문)
• 중간 일치 공격(Meet-in-the-Middle-Attack)이 있기 때문에 안전성을 획기적으로 높이지는 못함
• (이중 DES는 단일 DES와 안전성이 비슷하고, 삼중은 키 길이를 2배 하는 효과 뿐임)

 

중간 일치 공격

: 공격자가 평문과 그를 암호화한 암호문을 알 때 수행할 수 있는 공격

1. 56비트 키 공간 K에서 가능한 모든 키로 평문을 암호화해 그 결과값들로 집합 S1 생성
2. K에서 가능한 모든 키로 암호문을 복호화해 그 결과값들로 집합 S2 생성
3. S1과 S2의 모든 원소에 대해 서로 암/복호화 결과가 일치하는 쌍들을 선정, 후보키 집합 CK 생성
4. 다른 평문(평문2)와 평문2를 암호화한 암호문2 생성
5. CK의 모든 원소에 대해 평문2-암호문2 간의 암/복호화 관계를 만족시킬 만한 값들의 쌍으로 집합 CK 갱신
6. CK 집합의 원소가 하나만 남을 때까지 위 과정 반복

• 위의 방법을 쓸 경우 연산량에 유의미한 영향을 미치는 것은 1~2번에서의 암복호화뿐(2^56번)
• 3에서의 후보키 생성은 퀵정렬/이분탐색으로 빠르게 수행 가능
• 4~6에서의 과정은 반복 횟수가 많지 않음

 

• 위의 방법으로 인해 평문과 암호문만 알 수 있다면 이중 DES는 그다지 안전성이 높지 못한 방법이 됨
• (112비트 키 DES의 안전성에 비해 부족)
• 삼중 DES는 위 공격을 적용해도 112비트 키 DES 이상의 안전성 확보 가능 => 일반적으로 다중 DES는 삼중으로 사용

 

---

3. 운영모드

= Mode of Operation

= 블록 암호로 다양한 크기의 데이터를 처리할 수 있도록 고안된 사용법

여러 종류가 있으며, 각각의 장단점을 고려해 선택됨

 

 

3-1. 패딩(Padding)

: 평문 크기가 블록 크기로 나누어떨어지지 않는 문제를 해결하기 위해

평문에 데이터를 붙여 배수로 만드는 과정

• 복호화 시 패딩을 제거해야만 원래의 평문을 얻을 수 있기 때문에 수신자 측에서는 적용된 패딩에 대해 알아야 함

 

• 비트 패딩(Bit ~) : 마지막 블록에서 남는 비트 중 최상위 비트는 1, 나머지는 모두 0으로 채우는 기법
• 평문의 마지막 비트부터 처음으로 1 비트가 나올 때까지를 패딩으로 인식하고 지우면 됨
• / 평문 길이가 정확히 블록크기의 배수일 때 평문을 패딩으로 오해할 가능성이 있으므로
• 이 경우 패딩으로 한 블록을 추가함

 

• 바이트 패딩(Byte ~) : 바이트 단위로 패딩을 수행하는 기법
• ANSI X.923 : 마지막 블록의 남는 바이트를 임의 값으로 채우고 마지막 바이트에 패딩의 길이 기록
• 비트 패딩과 마찬가지로 수신자가 평문을 패딩으로 오해할 수 있음. 이 경우 패딩 블록 추가

 

• PKCS(Public-Key Cryptography Standard)#7 패딩 : 추가할 패딩의 바이트 크기로 마지막 블록을 채우는 기법
• 평문 크기가 정확히 배수일 경우 남는 크기를 8바이트로 간주하고 08을 패딩

 

 

3-2. ECB(Electronic Code Book) 모드

: 가장 간단한 운영모드. 블록들을 모두 같은 키로 암호화한다.

각 블록이 독립적으로 암호화되므로 여러 블록을 병렬적으로 암호화할 수 있음

암호학적 안전성이 부족함

= 모든 블록이 같은 방식으로 암호화되기 때문에 암호문에서 평문의 성질 취득 가능(약한 혼돈 성질), 리플레이 공격 가능

 

재전송 공격 (Replay attack)

: 어떤 데이터를 재전송하여 시스템이 의도치 않은 행동을 하게 하는 것

전송된 데이터의 평문과 암호문을 알게 되면 평문 중 일부가 암호화했을 때 어떤 부분이 되는지 알 수 있고

이를 이용해 전송된 메시지를 조작하여 재전송, 시스템의 의도와 다른 일이 벌어지게 함

 

 

3-3. CBC(Cipher Block Chaining) 모드

: 어떤 블록을 암호화하기 전에 해당 블록을 직전 블록의 암호문과 XOR하는 것

• 첫 번째 블록의 경우 이전 블록이 존재하지 않으므로 초기 벡터(Initialization Vector, IV)와 XOR함
• 각 블록이 서로의 암호화에 영향을 줌 -> 같은 블록도 전체 평문/IV에 따라 암호화 결과가 달라짐

 

• 초기 벡터는 일반적으로 논스(Nonce, Number used only ONCE)라는 무작위 값을 사용함
• 공격자가 알아도 안전성에 영향을 끼치지 않음
• / 공격자가 중간에 암호문을 가로채 조작할 수 있다면 복호화 결과의 첫 블록을 조작할 수 있음
• -> CBC 모드에서는 초기 벡터의 무결성 보장이 중요

 

• 여러 블록을 병렬적으로 암호화할 수 없으나 복호화의 경우는 병렬 처리 가능
• 재전송 공격에 강함, 높은 혼돈성 -> 블록 암호의 운영 모드로 널리 사용됨

 

CBC Bit-Flipping Attack

: 공격자가 초기 벡터를 원하는 값으로 조작하여 복호화된 평문의 첫 번째 블록을 조작하는 공격

 

 

3-4. CTR(Counter)모드

: 블록 암호에 논스와 평문 블록의 인덱스(counter)를 결합한 값을 입력함

암호문은 블록 암호의 출력과 평문 블록을 XOR하여 생성

• 블록을 순서대로 암복호화하지 않아도 됨 -> 병렬 암복호화 가능
• 구현이 간단함