이 장에서는

• Symmetric encryption vs. authenticated encryption
• 유명한 authenticated encryption algorithms
• 그 외 symmetric encryption

Confidentiality(기밀성)은 원치 않는 사람들로부터 데이터를 숨기는 것
Encryption(암호화)는 Confidentiality를 달성하는 방법

Cipher란?

Alice와 Bob이 비공개로 메세지를 교환하고 싶다!
메세지의 내용을 암호화하고자 한다.

encryption algorithm (cipher)

1. 암호화 과정

   • secret key : 예측 불가능하고, random하며, 잘 보호되어야 한다.
   • 평문(메세지)

   암호화를 거친 후에는, ciphertext(암호문)이 생성된다.

2. 복호화 과정

   • secret key : 암호화할때와 동일한 key. 대칭키이다.
   • ciphertext: 암호화된 암호문이다

인증된 암호화의 기본요소를 설명하기 전에 암호화가 어떻게 작동하는지 설명하겠다.

The Advanced Encryption Standard(AES) block cipher

DES(Data Encryption Standard)를 대체하기 위해 1997년 NIST는 데이터 암호화를 대체하기 위한 Advanced Encryption Standard(AES) 대회를 개최하였다.

대회는 3년 간 진행되었고, 여러 국가에서 15개의 다른 디자인이 제출되었다.

대회가 끝날 무렵, Vincent Rijmen, Joan Daemen이 우승했다.

FIPS(Federal Information Processing Standard) 197 publication의 일부분으로 AES를 출시했다.

How much security does AES provide?

AES는 세 가지 버전이 있다.

• AES-128 : 128 bit (16 byte) 키 사용
• AES-192 : 192 bit (24 byte) 키 사용
• AES-256 : 256 bit (32 byte) 키 사용

key의 길이는 보안 수준을 결정한다 (key 길이가 길수록 강력)

그럼에도, 대부분의 애플리케이션은 128 bit 보안을 제공한다.

Bit security는 upper bound
128 bit의 key가 128 bit의 보안을 제공한다는 건 AES에만 해당한다.
128 bit의 key는 128 bit의 보안보다 낮은 보안일 순 있지만, 그 이상을 제공하진 못한다.

The interface of AES

AES는 대칭 암호화 알고리즘이다
데이터를 암호화/복호화할 때 같은 키를 사용한다.
기본 인터페이스는 다음과 같다.

input

• key : 가변 길이의 비밀 키 (128bit, 192bit, 256bit)
• plaintext : 정확히 128 bit 크기의 데이터블록

output

• ciphertext : 정확히 128 bit 크기의 암호화된 데이터

AES는 고정된 크기의 블록(128 bit)을 처리하므로, 길이가 긴 데이터를 암호화하려면 특정한 암호화 모드(ex. CBC, CTR)을 사용해야 한다

블록 암호(block cipher)화 순열(Permutation)
블록 암호 : 고정된 크기의 입력과 출력을 다루는 암호화 (AES는 입력된 128 bit 데이터를 비밀 키를 사용해 암호화된 128 bit 출력으로 변환한다.)

순열로서의 블록 암호 : 블록 암호는 입력 평문의 모든 가능한 값(128 bit 크기)을 특정한 출력 암호문에 매핑한다. 순열처럼 동작한다.

• ex. 특정 키를 사용하면 "0000...01"이라는 입력은 "d48c...ed19"라는 출력으로 매핑된다
• 키를 변경하면 매핑도 변경되므로, 서로 다른 키는 서로 다른 순열을 생성한다

복호화 동작(decryption operation)
AES의 복호화는 암호화의 반대 과정

• 입력: 128 bit 암호문과 동일한 키
• 출력: 원래의 128 bit 평문

암호화와 복호화 과정은 결정적(deterministic)이므로, 동일한 입력과 키로 호출하면 항상 동일한 결과를 얻는다.

PRP(Pseudorandom Permutation) : 의사난수 순열
AES와 같은 블록 암호는 모든 평문-암호문 매핑을 미리 나열할 수 없기에, 대신 PRP를 사용한다.

PRP란? 랜덤 순열처럼 보이지만, 키에 의해 결정되는 순열.
AES가 PRP를 기반으로 동작한다. 키를 바꿈으로써 서로 다른 순열을 생성할 수 있다.

The internals of AES

AES 내부의 기본 구조

• 고정 크기 블록 처리: AES는 16바이트(128비트)의 고정 크기 데이터를 처리하는 블록 암호(block cipher).
• 평문 → 상태(State):
  - AES는 평문을 4×4 바이트 매트릭스로 변환하여 처리.
  - 이 매트릭스는 상태(State)라고 불리며, 암호화 과정 동안 계속 변환

라운드 반복의 효과

• AES는 데이터를 여러 번 변환하여 원본 평문과 전혀 다른 암호문을 생성합니다.
• Avalanche Effect (눈사태 효과):
  - 입력 값의 작은 변화가 출력 값에 큰 변화를 일으킵니다.
  - 예: 평문의 한 비트가 바뀌면, 암호문의 절반 이상의 비트가 바뀝니다.

보안 원리

• Diffusion(확산): 데이터가 암호문 전체에 고르게 퍼지도록 만든다.
• Confusion(혼돈): 키와 암호문 간의 관계를 복잡하게 만들어 보안을 강화한다.

The encrypted penguin and the CBC mode of operation

AES block cipher와 그 내부를 살펴보겠다.

block cipher의 문제점은 오직 자기 자신만 암호화할 수 있다는 것이다.
정확히 128 bit가 아니라면 암호화하기 위해 padding과 mode of operation을 사용해야 한다.

• padding: 긴 메세지를 암호화하려면, AES의 블록 크기인 16 byte로 메세지를 쪼갤 수 있다. 이때, 맨 마지막 글은 16 byte가 아닐 수 있는데, 이 때 마지막글을 16 byte로 맞춰주기 위해 추가하는 것이 padding이다.
  • padding은 가역적(reversible)이어야 한다. 암호문을 복호화해서 평문을 만들었을때, padding되지 않은 원래 메세지를 알 수 있어야 한다는 것
  • PKCS#7 : 가장 많이 사용되는 padding mechanism이다. 각각의 padding byte 값을 필요한 padding의 길이로 설정하는 방법. (평문이 이미 16byte라면 16으로 설정된 전체 padding block을 추가)
• mode of operation:

electronic codebook (ECB) mode of operation: 지금까지 말했던 16byte로 쪼개는 방법

여기서 문제가 생긴다.
암호화는 결정론적(deterministic)이기 때문에, 같은 평문 블록을 두 번 암호화하면 같은 암호문이 생성됨
즉, 각 블록을 개별적으로 암호화하면 결과 암호문에 반복되는 패턴이 있을 수 있다.

이런 반복을 허용하면 평문에 대한 정보가 누출되는 문제가 발생한다.

이 문제의 예시로 ECB 펭귄 사진이 있다.

128bit 이상의 평문을 안전하게 암호화하기 위해선, randomize하는 modes of operation이 있다.
가장 인기있는 AES modes of operation(운영 모드)는 CBC(cipher block chaining, 암호 블록 체인)이다.

• CBC : 초기화 벡터(IV, initialization vector)라는 추가 값을 사용해 무작위로 지정함으로써 모든 결정적 블록 암호에 대해 작동할 수 있다. 이 때문에 IV는 블록 크기(AES는 16byte) 길이여야 하며, ramdom하고 unpredictable해야 한다.

CBC 운영 모드 암호화 과정
1. 16 byte의 랜덤 IV를 생성
2. 생성된 IV와 첫번째 16 byte의 평문을 XOR => 암호화가 랜덤화됨
3. 암호화할 평문이 더 있다면, 이전 ciphertext를 사용해 암호화하기 전에 다음 평문과 XOR

CBC 운영 모드 복호화 과정
1. IV를 암호문과 함께 일반 텍스트로 전송받음
2. 암호화 역순

A lack of authenticity, hence AES-CBC-HMAC

아직까지 ciphertext와 IV는 공격자에 의해 수정될 수 있다.

이 위험성을 보강하기 위하여 MAC(message authentication codes)을 사용할 수 있다.
AES-CBC의 경우, 일반적으로 HMAC(hash-based MAC)을 SHA-256 hash function과 조합하여 무결성을 제공한다.
그 후 평문을 padding하고 암호문과 IV 모두를 암호화한 후 MAC을 적용한다.

이 구조는 Encrypt-then-MAC이라고 한다. 대안인 MAC-then-Encrypt은 때로 Vaudenay padding oracle attack과 같은 공격으로 이어질 수 있기에, 사용을 피한다.

생성된 authentication tag는 IV

• AES-CBC-HMMAC

공개 IV, 암호문, authentication tag를

All-in-one constructions: Authenticated encryption

개발자의 암호화 사용을 단순화하는 올인원 구조를 표준화하려는 연구가 시작됨

What's authenticated encryption with associated data(AEAD)?

데이터를 암호화하는 가장 최신의 방법은 all-in-one구조(authenticated encrytion with associated data, AEAD)를 사용하는 것이다.

동작 과정

1. Alice와 Bob은 사전에 공유 키를 교환한다. (ex. key 0x8866...)
2. Alice는 메세지를 암호화한다.
   • 평문 "hello"를 연관된 데이터(ad) "from alice"와 함께 넣는다.
   • 결과로 "암호문+인증태그"가 생성된다 (ex. ciphertext+tag)
3. 암호문이 전송 중에 공격자에 의해 가로채지고 변경된다
4. Bob은 동일한 키와 연관된 데이터를 사용해 암호문을 복호화하려 한다.
   • 그러나, 암호문 or 태그가 변경되었기 때문에 복호화가 실패하고 오류 발생.

The AES-GCM AEAD

가장 널리 사용되는 AEAD이다. AES with the Galois/Counter Mode에서 축약된 말이다.
AES-GCM은 (인터넷 웹사이트 연결 보호에 사용되는) TLS 프로토콜을 포함해 암호화 프로토콜에서 사용되는 주요 암호이다.

AES-GCM는 GMAC message authentication code와 CTR(Counter) 운영모드를 결합한다

AES-CTR은 AES를 사용해 평문 대신 숫자(1부터 시작)로 연결된 nonce를 암호화한다.
추가 인수인 "한번만 사용되는 숫자인 nonce"는 AES의 IV와 동일한 목적을 가진다.(비슷한 역할을 한다)
즉, 운영 모드가 AES encryption을 무작위로 지정할 수 있다.
그러나 nonce는 고유해야 하지만, unpredictable여야하지는 않다.
이 16 byte 블록이 암호화되면 결과를 keystream이라고 하며, 실제 평문과 XOR 연산을 통해 암호를 생성한다.

#CTR 모드는 padding이 필요없기 때문에 암호문과 평문이 동일한 길이가 된다(?)
CTR 모드의 특징

• 병렬 처리 가능: 각 블록이 독립적으로 처리되므로 매우 빠르다
• 기밀성 제공: 평문이 키 스트림으로 변환되기 때문에 외부에서는 평문을 알 수 없다

AES-GCM에서 CTR 모드의 장점

• 빠른 속도: 병렬 처리와 하드웨어 가속을 통해 고속 암호화를 지원합니다.
• 유연성: Nonce와 카운터를 조합하여 각 블록을 고유하게 만들기 때문에 반복 암호화에 안전합니다.
• 간단한 복호화: XOR 연산을 사용하므로 복호화가 간단합니다.

nonce
논스는 암호학에서 중요한 개념으로, 일반적으로 반복되지 않아야 합니다. (한번만 사용되는 값을 의미함)
AES-GCM에서 논스는 IV로 불리며, 특정한 역할과 요구사항을 가지고 있습니다.
논스의 정확한 사용법은 알고리즘 매뉴얼에 따르는 것이 중요합니다.

CTR 모드의 주요 구성 요소

1. nonce

   • 12 byte로 설정. 암호화 작업에서 유일해야 하며, 재사용하지 말아야 한다.

2. counter

   • nonce 뒤에 4 byte의 카운터 값이 결합된다.
   • counter는 블록마다 1씩 증가하며, 최대 $2^{32}-1=4,294,967,295$까지 사용할 수 있다.

3. Keystream

   • nonce와 counter를 결합한 값을 AES로 암호화해 생성
   • 키스트림은 평문과 XOR연산으로 암호문을 생성

4. 암호화 및 복호화

   • 암호화: 평문 ⊕ 키 스트림 = 암호문.
   • 복호화: 암호문 ⊕ 키 스트림 = 평문.

특징

• padding이 필요없다: 평문의 길이에 맞게 잘린다
• 스트림 암호화 : 평문 데이터를 바이트 단위로 암호화한다

nonce를 재사용하면?
키 스트림이 동일하게 생성된다. 이로 인해 XOR 공격에 대한 보안 문제가 생길 수 있다

• 동일한 논스를 사용하는 두 암호문 $C_1, C_2$가 있다면
  - $C_1 ⊕ C_2 = (P_1⊕K)⊕(P_2⊕K)=P_1⊕P_2$
• 이를 통해 두 평문의 XOR 결과를 얻을 수 있다.
• 만약 평문 중 하나의 내용을 알고있다면, 다른 평문을 쉽게 복원할 수 있다.

AES-GCM의 두번째 파트 : GMAC
GMAC은 키 해시(GHASH)에서 구성된 MAC이다. GHASHSMS 거의 XOR된 AXU(범용 해시)이며, DUF(Difference unpredictable function)라고도 한다.
이 함수의 요구사항은 해시보다 약하다.
예로, AXU는 collision resistant를 요하지 않는다.
덕분에 GHASH는 훨씬 더 빠르다.

3. AES-GCM의 전체 구조 (Figure 4.17)

AES-GCM은 CTR 모드와 GMAC를 결합하여 기밀성과 무결성을 동시에 제공합니다.

AES-GCM의 동작 과정
평문 암호화 (CTR 모드):

논스와 키를 사용하여 AES-CTR 모드로 평문을 암호화하고 암호문을 생성합니다.
카운터는 1에서 시작하며, 0은 인증 태그 생성에 예약됩니다.
GHASH로 데이터 인증:

GHASH는 추가 데이터(AD)와 암호문을 처리하여 인증 데이터를 생성합니다.
인증 키(H)는 AES 암호화를 통해 생성되며, GHASH의 입력 키로 사용됩니다.
인증 태그 생성:

GHASH 출력과 AES-CTR 암호화를 결합하여 최종 인증 태그를 생성합니다.
이 태그는 암호문과 함께 전송되어 수신자가 데이터의 무결성을 검증할 수 있게 합니다.

AES-GCM은 AES-CTR을 사용해 평문을 암호화하고, GMAC을 사용해 데이터와 암호문의 무결성을 보장합니다.
CTR 모드: 평문의 기밀성 제공.
GMAC (GHASH + AES-CTR): 추가 데이터(AD)와 암호문의 무결성을 인증.

Figure 4.15: GHASH가 입력을 블록 단위로 처리하는 방식.
Figure 4.16: GHASH를 사용해 GMAC 인증 태그를 생성하는 과정.
Figure 4.17: AES-CTR로 평문을 암호화하고 GMAC으로 인증 태그를 생성하여 AES-GCM 전체 동작을 설명.

Birthday Bound Security:

암호화 알고리즘은 이론적으로 $2^{n/2}$ 메시지를 안전하게 암호화할 수 있습니다.
AES-GCM에서는 약 $2^{30}$ 메시지가 현실적인 한계입니다.

대규모 시스템에서 이 한계를 빠르게 초과할 가능성이 큽니다(예: Visa의 거래 처리).

해결책:

• Rekeying: 정기적으로 키를 교체하여 안전성을 유지.
• Beyond Birthday-Bound Security: 한 키로 더 많은 메시지를 암호화할 수 있는 새로운 설계.

ChaCha20-Poly1305

AEAD암호화 방식으로 기밀성과 무결성 제공

두 알고리즘으로 구성
1. ChaCha20 : 스트림 암호화 알고리즘
2. Poly1305 : MAC 알고리즘

2013년 구글이 안드로이드 저사양 프로세서를 사용하는 기기에서 AES를 빠르게 작동하기 위해 표준화
현재는 OpenSSH, TLS, Noise 같은 다양한 인터넷프로토콜에서 널리 사용

1. ChaCha20 스트림 암호

Salsa20 스트림 암호에서 수정된 버전
2005년 Daniel J. Dernstein에 의해 설계

스트림 암호 방식의 특징을 따름

동작 방식
1. 입력: 대칭 키. 논스(각 암호화 작업마다 고유해야 한다)
2. 키 스트림 생성: 키와 논스를 기반으로 랜덤 바이트 시퀀스(키 스트림=평문의 길이와 동일)를 생성한다.
3. 암호화: 키 스트림과 평문을 XOR 연산하여 암호문 생성. 길이 보존 방식(length-preserving). 암호문과 평문의 길이 동일
4. 복호화: 동일한 키와 논스를 사용하여 같은 키 스트림 생성. 암호문과 키 스트림을 XOR 연산하여 원래 평문 복원

Poly1305 MAC

• MAC(메세지 인증 코드). 데이터의 무결성을 확인
• 역할: ChaCha20로 암호화된 데이터와 관련 데이터를 기반으로 인증 태그를 생성
  - 인증 태그는 데이터가 변경되지 않았는지 검증하는 데 사용

ChaCha20-Poly1305의 특징
1. 소프트웨어 최적화 : 하드웨어 가속이 없는 환경에서도 AES보다 빠르게 작동하도록 설계됨. 저사양에서도 효율 높음
2. 기밀성 및 무결성 : ChaCha20은 데이터를 암호화해 기밀성 제공/Poly1305는 데이터를 인증해 무결성 보장
3. 논스 관리 : 논스는 반드시 고유해야 하며, 재사용 시 보안이 손상될 수 있음
4. 보안 수준 : 강력한 암호화, 인증을 결합해 AEAD의 대표적인 구현 중 하나로 자리잡음

내부적으로 block function을 호출하여 keystream을 생성한다.
블록함수는 아래 세 개를 받는다.

• 256 bit(32 byte) key
• 92 bit(12 byte) nonce
• 32 bit(4 byte) counter

암호화 과정
1. keystream이 충분히 생성될때까지 카운터를 계속 증가시키면서 block function을 실행
2. keystream을 평문 길이로 자른다
3. keystream과 평문을 XOR

Other kinds of symmetric encryption

Key wrapping

Key wrapping은 암호화된 데이터를 보호하기 위해 사용되는 방법으로, 특히 키를 안전하게 암호화하는 데 사용됩니다. 일반적인 nonce 기반 AEAD는 암호화 과정에서 추가적으로 nonce(또는 IV)가 필요하지만, key wrapping 알고리즘은 논스나 IV 없이 동작합니다.

논스가 필요 없는 이유: 암호화된 키 자체가 이미 랜덤성이 높아 추가적인 난수화가 필요하지 않기 때문입니다. 따라서 암호화 과정에서 논스가 반복될 가능성이 큰 문제가 되지 않습니다.
주요 표준: NIST SP 800-38F에서는 key wrapping을 위한 블록 암호 모드와 권장 알고리즘을 정의합니다.
장점: 논스나 IV를 따로 저장할 필요가 없어, 저장 공간을 절약할 수 있습니다.

Nonce misuse-resistant authenticated encryption

Nonce 오용 방지 인증 암호화
SIV(synthetic initialization vector)는 키를 암호화할 뿐만 아니라, nonce를 반복해서 사용해도 괜찮은 범용 AEAD scheme이다.

AEAD에서 암호화할때 사용되는 nonce는 평문 자체에서 생성되므로 두 개의 다른 평문이 동일한 Nonce로 암호화될 가능성이 매우 낮다는 것이 SIV의 핵심이다.

Disk encryption

Database encryption

요약

대칭 암호화는 데이터를 비밀로 유지하기 위해 사용하는 암호학의 기본 도구야. 이 기술의 안전성은 대칭 키라고 불리는 비밀 키에 의존하는데, 이 키는 꼭 비밀로 유지되어야 해.

대칭 암호화는 반드시 인증이 필요해. 인증을 추가하면 이를 인증된 암호화라고 부르지. 왜냐하면 인증이 없으면 암호화된 데이터(암호문)가 제3자에 의해 변조될 수 있기 때문이야.

인증된 암호화는 보통 메시지 인증 코드(MAC)를 대칭 암호화와 함께 사용해 구현할 수 있어. 하지만 요즘 권장되는 방식은 AEAD(Associated Encryption with Associated Data) 알고리즘을 사용하는 거야. AEAD는 암호화와 인증을 한꺼번에 처리할 수 있는 기술로, 잘못 사용하기가 더 어려워.

두 사람이 같은 대칭 키를 알고 있다면, 인증된 암호화를 사용해 서로의 통신 내용을 숨길 수 있어.

AES-GCM과 ChaCha20-Poly1305는 현재 가장 널리 쓰이는 AEAD 알고리즘이야. 요즘 대부분의 애플리케이션은 이 둘 중 하나를 사용하지.

하지만 주의할 점이 있어. Nonce(암호화 과정에서 사용하는 고유 값)를 재사용하면 AES-GCM과 ChaCha20-Poly1305의 인증 기능이 깨질 수 있어. 그래서 AES-GCM-SIV 같은 nonce 재사용에 강한 방식이나, 키를 암호화하는 방식으로 문제를 해결하기도 해. 이 경우 nonce가 필요 없게 되거든.

실제 암호학은 이런 제약들을 다루는 기술이야. AEAD가 모든 상황에 적합하지는 않아. 예를 들어, 데이터베이스 암호화나 디스크 암호화 같은 경우는 새로운 방식이 필요할 수 있어.