Crypto Review (2)

yeon·어제

Cybersec crypto

보안동아리/E-COPS17.5thPrechall

목록 보기

5/5

AES(Advanced Encryption Standard)는

대칭키 암호 알고리즘이다

대칭키 암호는 암호화와 복호화에 같은 key를 사용하는데, 대표적인 대칭키 암호 알고리즘이 AES이다.

              Key
               ↓
Plaintext → Encryption → Ciphertext

Ciphertext → Decryption → Plaintext
               ↑
              Key

블록 암호(Block Cipher)이다

블록 암호는 입력값으로 들어온 평문 또는 암호문을 정해진 길이의 블록(block)이란 단위로 쪼개서 처리하는 암호 방식을 말한다.

현대의 데이터의 길이가 참 크기 때문에 필연적으로 특정 단위로 쪼개서 처리하는 방식이 필요한 것이다.

AES-128의 블록 길이와 키의 길이는 모두 128bit(=16byte)이다.
따라서 AES에서 Brute Force는 불가능하고(Brute Force Resistance),
이 알고리즘을 거친 평문이나 암호문을 16바이트 단위로 나누면 블록 단위로 분석할 수 있게 된다.

Keyed Permutation이다

처음에는 이 말이 무슨 의미인지 잘 몰랐다.

Permutation은 입력들을 서로 다른 출력에 대응시키는 재배열입니다.

A → C
B → A
C → D
D → B

AES에서는 어떤 plaintext block이 어떤 ciphertext block으로 변환되는지가 key에 따라 달라집니다.
그래서 AES를 Keyed Permutation이라고 설명하는 것이다.

왜 일대일 대응이어야 할까?
다음과 같은 변환이 있다고 생각해봅시다.

A → X
B → X

ciphertext X만 보고는 원래 plaintext가 A인지 B인지 알 수 없습니다.
따라서 복호화가 가능하려면 각 입력과 출력이 서로 하나씩 대응해야 합니다.

AES의 구조

AES-128은 여러 Round 동안 State를 반복적으로 변환하여 데이터를 섞습니다.
AES State
AES에서는 16-byte plaintext를 내부적으로 4×4 byte 구조인 State로 다룹니다.

AES-128에서는 먼저 하나의 key에서 여러 Round Key를 생성합니다.
이를 Key Expansion이라고 합니다.

Key Expansion
      ↓
Initial AddRoundKey
      ↓
Round 1
      ↓
Round 2
      ↓
...
      ↓
Round 9
      ↓
Final Round (10개의 Round)

![[Pasted image 20261002142400.png]]

단, 마지막 Round에서는 MixColumns가 생략됩니다.
SubBytes: 각 byte를 S-box라는 lookup table을 이용해 다른 byte로 치환합니다.
![[Pasted image 20261002142516.png]]

ShiftRows: State의 각 행에 있는 byte의 위치를 이동합니다.
![[Pasted image 20261002142728.png]]

MixColumns: 같은 column에 있는 여러 byte를 수학적으로 섞습니다.
![[Pasted image 20261002142747.png]]
AddRoundKey: 현재 State와 Round Key를 XOR합니다.

AES 운용 모드

AES는 기본적으로 한 번에 16 byte block 하나를 처리합니다.
하지만 실제 메시지는 대부분 16 byte보다 깁니다.
Block Cipher 자체는 block 하나를 변환하는 방법을 정의합니다.
여러 block을 처리하기 위한 별도의 규칙이 필요합니다.
이를 Mode of Operation이라고 합니다.

Mode of Operation은 Block Cipher를 여러 block으로 이루어진 데이터에 적용하는 방법입니다.

AES 운용 모드의 종류에는 ECB, CBC, OFB, CTR, GCM가 있는데,
각 모드의 세부 사항들은 write-up을 작성할 때 같이 정리하는 것으로 하고 본 글에서는 문제 풀이를 해본 ECB, CBC, CTR에 대해서만 가볍게 정리하려고 한다.

ECB

동일한 키를 사용하면 동일한 평문 블록은 항상 동일한 암호문 블록으로 변환된다.
따라서 이미지나 문서처럼 반복되는 데이터가 존재할 경우, 암호문에서도 블록 단위의 반복 패턴이 드러날 수 있다.

CBC

동일한 평문이라도 IV가 달라지면 암호문이 달라진다.
이전 암호문 블록에 의존하기 때문에 암호화는 순차적으로 진행된다.
평문의 길이가 블록 크기의 배수가 아니라면 일반적으로 PKCS#7 등의 패딩이 필요하다.
암호문만으로 데이터의 무결성을 보장하지 않는다.

보안상 주의점
CBC에서는 이전 암호문 블록을 조작하면 다음 평문 블록의 특정 비트를 변경할 수 있다.
이러한 성질을 악용한 공격이 CBC Bit Flipping이다.
또한 패딩 오류를 외부에 노출하는 시스템에서는 Padding Oracle 공격이 발생할 수 있다.
따라서 CBC를 사용할 때는 별도의 적절한 메시지 인증이 필요하다.
-> flipping cookie 문제

CTR

각 블록을 독립적으로 처리할 수 있어 병렬 암호화가 가능하다.
패딩이 필요하지 않다.

동일한 키와 Counter 입력이 재사용되면 동일한 키 스트림이 생성된다.
이 경우 OFB와 마찬가지로 다음 관계가 성립한다.

C_1\oplus C_2=P_1\oplus P_2

따라서 동일한 키에서 키 스트림이 재사용되지 않도록 Nonce와 Counter를 관리해야 한다.

패딩(Padding)

ECB와 CBC는 입력 길이가 16바이트의 배수여야 하기 때문에 PKCS#7 Padding을 적용한다.

from Crypto.Util.Padding import pad, unpad

plaintext = b"HELLO"
padded = pad(plaintext, 16) # 16바이트로 패딩

print(padded.hex())
print(len(padded))  # 16

print(unpad(padded, 16))  # b'HELLO'

본 코드는 5바이트의 b'HELLO'에 바이트 11개를 추가하는 것입니다.

OFB와 CTR은 키 스트림을 필요한 길이만큼 사용하므로 패딩이 필요하지 않기 때문에 문제의 암호화 과정에서 패딩 유무를 확인하고 필요할 때는 제거하는 과정이 필요하다.

복습 질문

Q1. MD5로 비밀번호를 128비트로 만들면 안전한 난수 키가 되는가?
A1. 해시 함수는 입력이 같으면 결과도 동일하므로 난수도 아니며 해시 충돌 저항성의 맥락에서 128비트의 경우 안전할 만큼 충분히 큰 비트 개수도 아니다.

Q2. ECB에서 동일한 평문 블록이 같은 암호문 블록이 되는 이유는?
A2. 모든 블록에 대해 같은 키로 AES 알고리즘을 적용하고, 앞 블록과 무관하게 독립적으로 암호화되기 때문이다.

Q3. CBC 복호화에 이전 암호문이 필요한 이유는?
A3. CBC 복호화 공식 : Pi = D_K(Ci) ⊕ C(i-1)

Q4. ECB CBC WTF에서 AES 키를 몰라도 복호화할 수 있는 이유는?
A4. 일단 CBC 암호화와 ECB 복호화에 사용된 키가 같았고 중간 과정에 도달하면 위의 공식에서도 서술하듯 키는 알 필요가 없다 - 자세한 건 풀이 참고

Q5. OFB에서 키와 IV를 재사용하면 어떤 문제가 있는가?
A5. 똑같은 키가 여러 블록에 재사용되면서 평문 유추가 쉬워진다.

Q6. CBC에서 IV만 바꿔도 첫 평문 블록을 조작할 수 있는 이유는?
A6. CBC에서는 이전 암호문 블록(IV)을 조작하면 첫 평문 블록의 특정 비트를 변경할 수 있기 때문이다. (이러한 성질을 악용한 공격이 CBC Bit Flipping)

yeon

CSE

이전 포스트