[Cryptography] STAGE 3

[Cryptography] STAGE 3

 

1) AES

 

AES (Advanced Encryption Standard)

- 2001년에 새롭게 표준으로 선정된 블록 암호 알고리즘

- Vincent Rijmen, Joan Daemen이 제안한 Rijndael 구조

- 기밀성을 위협하는 치명적인 취약점이 발견되지 않음

- 현대에는 대칭키 암호 알고리즘을 사용할 때, 일반적으로 AES 사용

 

 

SPN (Substitution Permutation Network)

- 곱 암호의 일종

-  S-Box를 사용하는 치환(Substitution)과 P-Box를 사용하는 순열(Permutation)을 여러 라운드에 걸쳐 반복

- 페이스텔 구조와 달리 라운드마다 입력 전체에 라운드 함수를 적용

- 같은 수의 라운드를 사용할 때 SPN이 페이스텔 구조에 비해 두 배의 암호학적 안전성을 가짐

 

 

AES 구조

- 라운드마다 128비트 크기의 블록을 암호화하는 블록 암호

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

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

- 블록을 4행 4열의 상태 배열(State)로 재구성

- 재구성된 입력에 대해 AddRoundKey 함수를 적용

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

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

- AES의 라운드 함수들은 역함수가 존재

- 역함수를 이용하여 AES 복호화

 

 

SubBytes

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

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

 

 

ShiftRows

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

- 유일하게 순열의 역할을 수행

 

 

MixColumns

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

- 갈루아 필드 내에서의 행렬 연산으로 구해짐

 

 

AddRoundKey

- 키 생성 함수(Key Schedule)로 생성된 라운드 키의 state를 각 바이트별로 XOR 연산

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

 

 

Key Schedule

- 입력된 키로부터 각 라운드에 쓰일 라운드 키를 생성

 

 

 

QUIZ

Q1. 다음 중 옳지 않은 것을 고르시오.

(1) 한 라운드를 거친 뒤 DES는 평문의 전체가 바뀌지만 AES는 평문의 절반만 바뀐다.

(2) DES는 페이스텔 구조이지만 AES는 SPN 구조이다.

(3) DES는 순열이 비트 단위로 이루어지지만 AES는 바이트 단위로 이루어진다.

(4) DES는 S-box의 역함수가 존재하지 않지만 AES는 S-box의 역함수가 존재한다.

 

Q2. AES에서 순열을 수행하는 함수는 무엇일까요?

(1) SubBytes

(2) ShiftRows

(3) MixColumns

(4) AddRoundKey

 

 

 

 

 

2) DES

 

DES (Data Encryption Standard)

- 미국의 국가 안보국(National Security Agency, NSA)에서 IBM의 루시퍼 알고리즘을 개량하여 만든 대칭키 암호

- 키 길이를 56비트로 줄였고, 내부에서 사용하는 알고리즘도 일부 변경

- 현대에는 DES에 대한 공격 기법이 많이 연구되어 DES를 더이상 블록 암호의 표준으로 사용하지 않음

- 8바이트(64비트)를 한 블록으로 하는 블록 암호

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

 

 

순열과 치환

- 혼돈 성질을 만족하기 위해 치환 (Substitution) 사용

- 확산 성질을 만족하기 위해 순열(Permutation) 사용

- 순열과 치환을 여러 번 교차해서 반복 적용하면 혼돈과 확산의 성질을 모두 만족

- 치환이나 순열 같은 단순한 연산들로 한 라운드로 구성

- 곱 암호(Product Cipher): 각 라운드를 여러 번 반복하여 암호학적 안전성을 확보하는 암호

 

 

페이스텔 구조 (Feistel)

- 일반적으로 암호화를 구성하는 각 함수들에 역함수가 존재

- 페이스텔 구조를 사용하면 FF가 복호화 과정에서 \oplus⊕로 상쇄되므로 역함수가 존재 X

- 암호화와 복호화의 구조가 동일하므로, 암호화에 사용한 라운드 키를 역순으로 입력하면 복호화

- 비페이스텔 암호와 같은 안전성을 갖기 위해 두 배 정도 라운드를 사용해야한다는 단점

 

 

초기 순열 / 최종 순열 (IP / FP)

- 시작할 때 초기 순열 수행

- 마지막에는 최종 순열 수행

-  정해진 테이블을 이용하여 64비트 입력을 비트 단위로 전치

- 테이블의 n번째 값이 m일 때, 출력의 n번째 비트는 입력의 m번째 비트

- 초기 순열과 최종 순열은 서로 역관계

 

 

라운드 함수

- 라운드 함수 F에는 오른쪽 블록만 입력 (입력 길이 32비트)

- 확장 순열, 라운드 키 결합, 치환 테이블, 고정 순열로 구성

 

 

확장 순열과 라운드 키 결합

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

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

 

 

S-Box와 고정 순열

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

  → 4개의 행과 16개의 열로 이루어진 표를 사용

  → 표의 각 값은 4비트로 표현되는 수

- S-Box로 길이를 축소하고 나면, 고정 순열(Straight P-Box)로 다시 비트 단위 전치가 이루어짐

 

 

키 생성 함수 (Key Scheduling)

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

- 패리티 비트 제거, 쉬프트, 압축 순열로 구성

 

 

패리티 비트 제거 (Parity Bit Drop)

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

- 홀수 패리티 비트: DES의 비밀키에서 각 바이트의 가장 오른쪽 비트

  → 자신이 속한 바이트의 나머지 7비트에 대한 비트

  → 한 바이트를 이진수로 표현했을 때, 1의 개수가 홀수가 되도록 덧붙인 비트

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

 

 

쉬프트 (Shift)

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

- 1, 2, 9, 16 라운드에서는 1비트, 나머지 라운드에서는 2비트만큼

 

 

압축 순열 (Compression P-Box)

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

 

 

 

 

 

QUIZ

Q1. DES의 라운드 수는 16이다.

Q2. DES에 입력되는 키의 길이는 64비트인데, 패리티 비트를 제거하면 실제로 사용되는 키의 길이는 56비트이다.

Q3. DES는 라운드마다 다른 S-Box를 사용한다. X

 

 

 

 

 

 

3) 운영암호

 

운영 모드 (Mode of Operation)

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

- ECB 모드, CBC 모드, CTR 모드

 

 

패딩 (Padding)

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

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

- 비트 패딩, 바이트 패딩

 

 

비트 패딩 (Bit Padding)

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

- 수신자는 평문의 마지막 비트부터 처음으로 값이 1인 비트가 나올 때까지를 패딩으로 인식 가능

  → 이를 제거하여 평문을 복구

- 비트 패딩을 적용할 때는 평문의 크기가 블록 크기의 배수이면, 패딩으로 한 블록을 추가

 

 

바이트 패딩 (Byte Padding)

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

- ASNI X.923

  → 마지막 블록의 남는 바이트를 임의의 값으로 채우고, 마지막 바이트에 패딩의 길이를 기록하는 기법

- PKCS#7 (Public-Key Cryptography Standard)

  → AES와 같은 블록 암호의 패딩 기법

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

 

 

ECB 모드 (Electronic Code Book)

- 가장 간단한 운영모드

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

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

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

- 취약점: 같은 블록은 같은 암호문으로 암호화되는 특징을 이용

  → 공격자는 암호문에서 평문의 정보를 습득하거나, 리플레이 공격(replay attack)을 수행하는 것이 가능해

  → 약한 혼돈 성질: 암호문으로부터 평문의 정보를 유추하기 어려워야 한다는 혼돈 성질이 약함

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

 

 

CBC 모드 (Cipher Block Chaining)

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

- 평문의 첫 번째 블록은  초기 벡터라고 불리는 임의의 데이터와 XOR

- 같은 블록도 전체 평문 및 IV에 따라 암호화 결과가 달라짐

- 한 블록을 암호화할 때 직전 블록의 암호화 결과를 사용하므로 여러 블록을 병렬적으로 암호화할 수 없음

- 복호화의 경우, 모든 암호문 블록을 알고 있으므로 병렬적으로 처리 가능

- 재전송 공격에 강인, 높은 혼돈성

- CBC Bit-Flipping Attack

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

 

 

CTR 모드 (Counter)

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

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

- 병렬로 암복호화 가능

- 구현이 간단함

 

 

 

 

 

QUIZ

Q1. PKCS#7은 공개 키 암호의 패딩 표준을 정의하고 있다. X

Q2. CBC 모드를 사용하면 병렬적으로 암호화할 수 있으므로, 성능상 이점이 있다. X

Q3. CTR 모드에서 난수는 공개돼도 암호의 기밀성에 문제가 없다. O

Q4. CBC 모드에서 각 블록을 암호화할 때 사용되는 키는 이전 블록의 암호화 결과에 따라 달라진다. X