[Crypto] Dreamhack STAGE 3

https://dreamhack.io/lecture/roadmaps/3

Cryptography

---

[ Crypto stage 3 _ 블록 암호 ]

 

* AES(Advanced Encryption Standard)

 - SPN 구조: S-Box를 사용하는 치환(substitution) + P-Box를 사용하는 순열(permutation)을 여러 라운드에 걸쳐 반복

   -> 파이스텔 구조와 달리 라운드마다 입력 전체에 라운드 함수를 적용 -> 같은 수의 라운드를 사용할 때 SPN이 파이스텔 구조에 비해 두 배의 암호학적 안전성을 가짐

 

키 길이	라운드 수
128비트	10	AES-128
192비트	12	AES-192
256비트	14	AES-256

 

=> 암호화 방법

 1. 각 블록을 4행 4열의 상태 배열(STATE)로 재구성함 (STATE의 각 칸에는 8비트(1바이트)가 저장됨)

 2. 이후 입력에 대해 AddRoundKey 함수를 적용

 3. 마지막 라운드 전까지 매 라운드마다 Subbytes, ShiftRows, MixColumns, AddRoundKey 함수를 반복하여 적용

 4. 마지막 라운드에서 MixColumns를 제외한 나머지 함수들만 적용

=> AES의 라운드 함수들은 역함수가 존재하므로, 역함수를 이용하여 AES 복호화가 이뤄집니다.

 

 

1) SubBytes 함수 (위 오른쪽 그림)

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

 : 바이트의 상위 4비트가 행, 하위 4비트가 열을 결정

 

2) ShiftRows 함수

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

 : 4가지 함수 중 유일하게 순열의 역할 수행

 : 2행은 왼쪽으로 1칸, 3행은 왼쪽으로 2칸, 4행은 왼쪽으로 3칸 밀기

-> 복호화할 때는 반대로 2행, 3행, 4행을 각각 오른쪽으로 1,2,3칸 밀기

 

3) MixColumns 함수

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

 

 

4) AddRoundKey 함수

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

 : 복호화할 때는 XOR의 성질을 이용하여 동일한 키를 state에 XOR 함

 

 

 

<Key Schedule>

 : AES 암복호화를 시작할 때와 매 라운드마다 AddRoundKey를 적용

   -> 따라서 AES-128에서는 라운드 키가 11개 필요함

 : RotWord, SubWord, Rcon을 반복하여 W43(키 행렬의 43번째 열)까지 생성하고, 이를 4열씩 각 라운드에 사용

 : [W0, W1, W2, W3]은 암호화를 시작할 때 사용했으므로, 1라운드에서는 [W4, W5, W6, W7] 사용

1) RotWord

 : 열을 위로 한 번 회전시킴 (위로 밀기)

2) SubWord

 : subbytes에서 사용한 것과 동일한 s-box를 사용하여 각 바이트를 치환

3) Rcon

 

 

 

 

* DES(Data Encryption Standard)

 : 구성: 초기 순열(IP), 최종 순열(FP), 파이스텔 구조의 16라운드, 키 생성 함수(KEY GENERATION/각 라운드에서 사용되는 48비트의 키 생성)

 : 혼돈 성질을 만족하기 위해 치환(substitution)을, 확산 성질을 만족하기 위해 순열(permutation) 사용

 : 곱 암호(product cipher): 치환이나 순열 같은 단순한 연산들로 한 라운드를 구성하고, 각 라운드를 여러 번 반복하여 암호학적 안전성을 확보하는 암호

 

 

1) 파이스텔 구조

(1)L0​=P[:len(P)/2], R0​=P[len(P)/2:]

(2)Ln+1​=Rn​

(3)Rn+1​=Ln​⊕F(Rn​,Kn​)

 

-> (1): 입력으로 들어온 블록을 동일한 길이의 왼쪽 블록(L)과 오른쪽 블록(R)으로 나눔

-> (2): 각 라운드마다 오른쪽 블록은 다음 라운드의 왼쪽 블록으로 입력됨

-> (3): 왼쪽 블록은 오른쪽 블록에 라운드 함수 F를 적용한 결과와 XOR 되어 다음 라운드의 오른쪽 블록으로 입력됨

 

 

2) 라운드 함수

: 라운드 함수 F에는 오른쪽 블록만 입력되므로, 입력 길이는 32비트임

-> 확장 순열, 라운드 키 결합, 치환 테이블, 고정 순열로 이루어짐

(1) 확장 순열과 라운드 키 결합

   : 확장 순열은 입력을 비트 단위로 전치하는 동시에, 전체 길이를 48비트로 확장함

   : 이 과정에서 32비트의 입력값을 4비트씩 8개의 부분으로 나누고, 테이블을 참조하여 각각을 6비트로 확장

   : 초기 순열과 최종 순열은 테이블만 다를 뿐, 같은 방식으로 이루어짐

   -> 라운드 키 결합 : 확장 순열로 나온 출력을 라운드 키 K와 XOR 하는 것

 (2) S-Box와 고정 순열

   : S-Box는 라운드 키 결합에서 출력된 48비트 결과 값을 32비트로 축소

   : 입력을 여섯 비트씩 8개의 부분으로 나눈 후, 여섯 비트 중 첫 번째와 마지막 비트로 행을 결정하고, 나머지 네 개의 비트로 열을 결정, 그 후, s-box의 표에서 행과 열을 참조하여 값을 반환

   : s-box로 길이를 축소하고 난 후, 고정 순열로 다시 비트 단위 전치가 이루어짐

 

 

 

< 키 생성 함수 >

: 64비트의 입력을 받아 각 라운드에 필요한 48비트 라운드 키를 생성하는 함수

: 패리티 비트 제거 + 쉬프트 + 압축 순열

1) 패리티 비트 제거

 : 입력에서 패리티 비트를 제거하고, 남은 56비트에 순열을 적용하는 과정

 : des 비밀키에서 각 바이트의 가장 오른쪽 비트는 자신이 속한 바이트의 나머지 7비트에 대한 홀수 패리티 비트

-> 홀수 패리티 비트 : 한 바이트를 이진수로 표현했을 때, 1의 개수가 홀수가 되도록 덧붙인 비트

-> 통신 중에 비트 반전이 일어나지 않았음을 보증하는 역할

 

2) 쉬프트

 : 입력을 왼쪽 28비트와 오른쪽 28비트로 나누어 각각을 1비트나 2비트만큼 왼쪽으로 순환 쉬프트 하는 과정

 : 1,2,9,16 라운드에서는 1 비트, 나머지 라운드에서는 2비트만큼 쉬프트함

 

3) 압축 순열

 : 56비트의 입력을 48비트 길이로 압축하는 과정

 

 

* 다중 DES

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

 : 이중 DES -> 112비트, 삼중 DES -> 168비트 키 사용

 : 중간 일치 공격으로 인해 안전성을 획기적으로 높이지는 못함

-> 중간 일치 공격 : 공격자가 어떤 평문 P와 P를 암호화한 암호문 C를 알 수 있을 때 수행할 수 있는 공격

 

 

* 운영모드(Mode of Operation)

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

 

1. 패딩

 : 평문에 데이터를 붙여서 평문의 크기가 블록 크기의 배수가 되도록 만드는 과정

 : 패딩된 암호문을 복호화할 때는 복호화된 평문에서 패딩을 제거해야 원래의 평문을 얻을 수 있음

 : 따라서 패딩된 암호문의 수신자는 어떤 패딩이 적용됐는지 알아야 암호문을 제대로 복호화할 수 있음

 

1) 비트 패딩

: 마지막 블록에서 평문이 채우지 못하는 비트 중 최상위 비트를 1로 설정하고, 나머지는 모두 0으로 채우는 패딩 기법

 : 마지막 비트부터 처음으로 값이 1인 비트가 나올 때까지를 패딩으로 인식할 수 있음

 : 메시지 일부를 패딩으로 오인할 수 있음 -> 비트 패딩을 적용할 때는 평문의 크기가 블록 크기의 배수이면, 패딩으로 한 블록을 추가

 

2) 바이트 패딩

   : 바이트 단위로 패딩을 수행하는 패딩 기법

   : 종류 : ANSI X.923 -> 마지막 블록의 남는 바이트를 임의의 값(일반적으로 0)으로 채우고, 마지막 바이트에 패딩의 길이를 기록하는 기법

 

3) PKCS#

   : AES와 같은 블록 암호의 패딩 기법 제시

   : 추가할 패딩의 바이트 크기로 마지막 블록을 채우는 패딩 기법

 

 

2. 운영 모드

1) ECB모드

: 블록들을 모두 같은 키로 암호화

: 각 블록이 독립적으로 암호화되므로 여러 블록을 병렬적으로 암호화할 수 있다는 장점

: 다른 운영모드에 비해 암호학적 안전성이 부족

 -> 암호문에서 평문의 정보 습득 OR 리플레이 공격 수행이 가능함

 -> 약한 혼돈 성질

-> 재전송 공격

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

 

2) CBC모드

   : 어떤 블록을 암호화하기 전에, 이 블록을 직전 블록의 암호문과 XOR

   : 평문의 첫 번째 블록은 이전 블록이 존재하지 않으므로, 초기 벡터(IV)라고 불리는 임의의 데이터와 XOR 함

   : 각 블록이 서로의 암호화에 영향을 주므로 같은 블록도 전체 평문 및 IV에 따라 암호화 결과가 달라짐

-> IV는 일반적으로 넌스(NONCE)라는 무작위 값을 사용하며, 이는 공격자가 알아도 안전성에 영향을 끼치지 않음

-> 그러나 공격자가 암호문을 중간에 가로채서 이를 조작할 수 있으면, 복호화 결과의 첫 번째 블록을 조작할 수 있음

 => 따라서 CBC 모드를 사용할 경우 IV의 무결성을 함께 보장해야 함

 => 암호화: 여러 블록을 병렬적으로 암호화할 수 없음

     복호화: 모든 암호문 블록을 알고 있으므로 병렬적으로 처리할 수 있음

 => 재전송 공격에 강인하며, 높은 혼돈성을 가지고 있어 블록 암호의 운영 모드로 널리 사용

 

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

 

3) CTR모드

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

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

: 블록을 순서대로 암호화하지 않아도 되므로 병렬로 암복호화할 수 있으며, 구현이 간단함