[Information Security] Chapter 20. Symmetric Encryption and Message Confidentiality

이은지·2024년 8월 21일

security

Information Security

목록 보기

3/11

4학년 1학기 Information Security 수업을 듣고, 대칭키 암호화에 대해 정리한 내용이다.

Symmetric Encryption

Conventional encryption, Secret-key or single-key encryption 이라고 하기도 함
1970년에 Public-key encryption이 나오기 전 유일한 대안이었음
5 ingredients
- Plaintext
  - Original message or data that enter into the algorithm as input
  - Unencrypted data that is readable and understandable by the user
- Encryption Algorithm
  - 암호화 알고리즘은 Plaintext에 여러 가지 치환과 변환을 수행
  - 이러한 작업을 통해 평문은 암호화되어 알아볼 수 없는 형태로 변환됨
- Secret key
  - 비밀 키도 알고리즘에 입력되며, 알고리즘이 수행하는 정확한 치환과 변환은 키에 따라 달라짐
  - 이 키는 암호화와 복호화 과정에서 모두 필요하며, 같은 키를 사용
- Cipher text
  - 암호화 과정을 거쳐 출력되는 암호화된 메세지
  - 암호문은 평문과 비밀 키에 의존적이며, 주어진 메시지에 대해 서로 다른 두 개의 키는 서로 다른 두 암호문을 생성
- Decryption algorithm
  - 복호화 알고리즘은 사실상 암호화 알고리즘을 역으로 실행하는 것
  - 이것은 암호문과 동일한 비밀 키를 받아들여 원본 평문을 생성

Encryption Schemes

암호 시스템은 3가지 독립적인 차원을 기준으로 분류됨

1. The types of operations used for transforming plaintext to cipertext

평문을 암호문으로 변환하기 위해 사용되는 연산 유형

Substitution(치환)
- 평문의 각 요소를 다른 요소로 매핑 하는 것
Transposition(전치)
- 평문의 요소들이 재배열 되는 것

2. The number of keys used

Symmetric
- Sender와 Receiver가 동일한 키를 사용
Asymmetric
- Sender와 Receiver가 다른 키를 사용

3. The way in which the plaintext is processed

평문이 처리되는 방식

Block cipher
- 입력을 한번에 블록 단위로 처리하여, 각 입력 블록에 대해 하나의 출력 블록을 생성
Stream cipher
- 입력 요소를 연속적으로 처리하여, 진행하면서 한 번에 하나의 출력을 생성

Types of Attacks on Encrypted Messages

Ciphertext only Attack(COA)

암호문 단독 공격
공격자가 알고 있는 것: Encryption algorithm, Ciphertext to be decoded
어떤 평문이 암호화될 때 이와 동일한 암호문이 되는지 알고 있음 → 어떤 평문이고, 어떤 키로 암호화가 되었는지를 알 수 있음
가장 방어하기 쉬운 공격 유형, Lowest level of attack

Known plaintext Attack(KPA)

기지 평문 공격
공격자가 알고 있는 것: Encryption algorithm, Ciphertext to be decoded, One or more plaintext-ciphertext pairs formed with the secret key
평문의 일부내용과 이것의 암호문을 알고 있는 상태에서 이에 대응하는 전체 암호문을 복호화하는 방식의 공격
예시
- 나이키 에어맥스 97 우먼스 - 코드명: 921733-xxx
- 코드명은 색상에 따라 마지막 3자리가 나뉨
- 암호화 E(나이키 에어맥스 97 우먼스) = 921733
- 복호화 C(921733) = 나이키 에어맥스 97 우먼스
- 공격자는 921733 가 나이키 에어맥스 97 우먼스 인것 까지 알고 있지만 -xxx 이 먼지를 모름
- 921733-006라는 암호문을 훔쳐냈을 때, 무차별적으로 모든 색의 조합을 대입하여 훔친 암호문과 매칭되는 평문을 찾아낼 수 있음

Chosen Plaintext Attack(CPA)

선택 평문 공격
암호 해독 자가 사용된 암호기에 접근할 수 있어 평문 P를 선택하여 그 평문 P에 해당하는 암호문 C를 얻어 키 K나 평문 P를 추정하여 암호를 해독하는 방법
공격자가 알고 있는 것: Encryption algorithm, Ciphertext to be decoded, Plaintext message chosen by cryptanalysist with its corresponding ciphertext generated with the secret key

Chosen ciphertext Attack(CCA)

선택 암호문 공격
암호 해독자가 암호 복호기에 접근할 수 있어 암호문 C에 대한 평문 P를 얻어 내 암호를 해독하는 방법
공격자가 알고 있는 것: Encryption algorithm, Ciphertext to be decoded, Ciphertext chosen by cryptanalysist with its corresponding decrypted plaintext generated with the secret key
예시
- 공격자는 E(나이키 에어맥스 95 에센셜) = at9865를 알고 있으며 C(at9865) = 나이키 에어맥스 95 에센셜 인 것도 알고 있음
- 이 평문/암호문 쌍을 통해 나이키가 어떤 알고리즘으로 코드명을 만들어내는지 알아내는 공격 방법

Chosen text

Highest level of attack

Computationally Secure Encryption Schemes

만약 다음 두 가지 기준을 충족하면, 암호화 체계는 계산 상으로 안전함

Cost of breaking cipher exceeds value of information
- 암호를 해독하는 비용이 암호화된 정보의 가치를 초과함
Time required to break cipher exceeds the useful lifetime of the information
- 암호를 해독하는 데 필요한 시간이 정보의 유용한 수명을 초과함

💡 암호문을 성공적으로 분석하는데 필요한 노력의 양을 추정하는 것은 매우 어렵지만, Brute-force attack은 time, cost를 추정하는 것이 가능함

Fiestel Cipher Structure

데이터를 두 부분으로 나누어 좌,우 부분에 교대로 비선형 변환을 적용시키는 구조

특징

DES와 같은 많은 block ciphers에서 사용됨
F에 따라 보안강도가 달라짐
Can easily make the decrytion method

Encrypted Structure

입력: 2w bits plaintext, key
plaintext는 L0, R0 두 부분으로 나뉨
데이터의 두 부분은 n라운드의 처리를 거치고 나서 ciphertext block 생성
각 라운드 i는 이전 라운드에서 파생된 Li-1, Ri-1, 전체 K에서 파생된 부분키 Ki를 입력으로 가짐
부분키 Ki는 K와 다르며, 부분키 생성 알고리즘을 통해 K에서 생성됨
매 라운드
- 오른쪽 절반에 round function F 적용
- F 함수의 출력과 데이터 왼쪽 절반을 XOR (substitution)
- 왼쪽 부분이 Ri, 오른쪽 부분이 Li가 되면서 permuation 수행됨

복호화 방법

아래부터 거꾸로 순서로 타고 올라가면됨. A,B XOR 연산을 통해 C가 나왔으면, A는 C와 B XOR을 통해 얻을 수 있음

따라서 C,B를 알면 A를 알 수 있음

Block Cipher Structure

Fiestel Cipher는 Block Cipher 중에 하나임

Symmetric block cipher(대칭 블록 암호)의 구성요소
- A sequence of rounds with substitutions and permutations controlled by key
Symmetric block cipher는 다음 parameter와 design features에 따라 달라짐
- block size
  - 블록 크기가 크면 클수록 보안성이 높아지지만, 암호화/복호화 속도가 떨어짐.
  - 128비트 블록 크기가 최근 블록 암호 설계에서 거의 보편적
- key size
  - 키 크기가 크면 보안성이 높아지지만, 암호화/복호화 속도가 떨어짐
  - 일반적인 키 길이는 128비트
- number of rounds
  - 전형적인 크기 16라운드
- subkey generation algorithm
- round function
- fast software encryption/decryption
- ease of analysis

DES(Data Encryption Standard)

DES는 세계에서 가장 널리 사용되는 블록 암호로, Fiestel 암호 구조에 기초함
1977년 Natinal Bureau of Standards에서 제정한 대칭키 암호화 알고리즘 중 하나

Triple DES

3개의 키와 DES 알고리즘을 3번 실행
암호화-복호화-암호화 순서를 따르며, 복호화는 단순히 키를 반대로 사용한 것
- 암호화-복호화-암호화 순서인 이유는 단순 DES와의 호환 때문
- 만약 3DES의 키 K1, K2, K3를 같은 키를 사용한다면, A=C가 되고, 3DES는 일반 DES와 동일하게 됨
3개의 서로 다른 키를 사용하여 3DES의 효과적인 키 길이는 56X3=168비트
168bit의 키 길이로 인해 무차별 대입 공격은 사실상 불가능함

AES

AES 개요

DES, Triple DES를 보다 안전하고 효율적인 알고리즘으로 대체하기 위해 만들어짐
key가 128비트이고, 32비트 CPU를 기준으로 생각하면 128bit=16byte=4 word → key는 4 word로 구성이 됨 w[0,3]
- 이 w[0,3]이 Expand Key Algorithm를 통해서 각 Round마다 서로 다른 Key들이 apply됨
각 라운드에서 전체 데이터 블록을 병렬로 처리하며, 매 라운드 단계는 다음과 같음
- Substitute Bytes
- Shift Rows
- Mix Columns
- Add Round Key

AES Encryption Round

1. Substitute Bytes(SubBytes) 과정

암호문이 비 선형성을 갖도록 하기 위해 바이트 단위로 역 변환이 가능한 S-box 표를 이용하여 블록을 교환
128 bit 블럭 안의 바이트 단위로 쪼개, 16byte를 각 바이트마다 다른 내용으로 치환 함
S-box: 16X16 바이트 값 행렬
State의 각 개별 바이트는 S-box를 참조해 새로운 바이트로 매핑

2. Shift Rows

Shift 연산을 하여 단순히 행과 행을 치환
State의 첫 번째 행을 변경하지 않음
두번째 행에는 1바이트의 순환 좌측 이동이 수행
세번째 행에는 2바이트의 순환 좌측 이동이 수행되고, 네 번째 행에는 3byte의 순환 좌측 이동이 수행됨

3. Mix Columns (열 섞기)

Row shifting이 끝나면, 4개의 블럭을 Group으로 묶어서, Mix Column을 시행

Operate on each column individually
Mapping each byte to a new value that is a function of all four bytes in the column
To provide good mixing of bytes in column
마지막 라운드는 MixColumn을 하지 않음

4. Add round key

Mix Column의 결과물로 나온 값들에 대해서, 해당 Round Key와 XOR 연산을 수행

Simply XOR State with bits of expanded key

Key Expansion Algorithm

initial key를 각 round마다 다르게 적용하기 위해서 initial key→ multiple key로 generate하는 알고리즘
정해져 있는 t값으로 각각 XOR 연산을 해서 새로운 key를 생성해내며, RCon[]은 uncertainty를 더하기 위해 사용된다

Stream Ciphers

블록암호는 블록 단위로 암호화 하지만, 스트림 암호는 연속적인 비트 단위로 암호화
키는 pseuorandom(의사랜덤) bit generator에 입력됨
- 겉보기에는 무작위인 8bit number stream 생성
- 의사랜덤 stream은 키를 알지 않으면 예측불가 하며, 겉보기에는 무작위 특성을 지님
- 생성기의 출력인 key stream은 plaintext와 XOR 연산을 사용하여 한번에 1byte의 암호문을 얻음

Stream Ciphers are Fast

스트림 암호의 주요 장점은 스트림 암호가 항상 더 빠르고 코드 사용량이 적다는 것

RC4

스트림 암호 알고리즘 중 하나
상태(state) 개념을 사용함
- 상태(state) : 256바이트로 구성된 상태(state)의 한 바이트는 암호화 키로서 사용되기 위해 랜덤하게 선택됨

RC4 작동과정

초기화 단계

256바이트의 state vector를 0,1,2…255로 초기화
키배열 K 생성
K를 T에 복사함
- 키의 길이가 256바이트라면 그대로 복사시키고, 256바이트보다 짧다면 T배열이 꽉 찰때까지 반복적으로 복사

Initial permutation of S

이제 생성된 T 배열을 가지고 S 상태배열을 swap
i를 0부터 255까지 반복
초기값 j=0, j=S[i]+T[i] 하여 j값을 구함
S[i]와 S[j]를 swap

/* S의 초기 순열 */
j = 0;
for i = 0 to 255 do
    j = (j + S[i] + T[i]) mod 256;
    Swap (S[i], S[j]);

Stream Generation

완전이 뒤섞여진 상태배열 S가 준비됨
i는 0부터 255까지 반복
j는 j=j+S[i]로 인덱스가 결정되고, S[i], S[j] swap 진행됨
t는 S[i]+S[j]로 계산되어, S[t]가 키k가 됨

/* Stream Generation */
i, j = 0;
while (true)
 i = (i + 1) mod 256;
 j = (j + S[i]) mod 256;
 Swap (S[i], S[j]);
 t = (S[i] + S[j]) mod 256;
 k = S[t]; //키

A Usage of RC4

Web 브라우저와 서버 간 통신을 위해 정의된 SSL/TTL 표준에서 사용됨
IEEE 802.11 무선 LAN 표준의 일부인 WEP(유선 동등 개인 정보 보호) 프로토콜과 최신 WiFi Protected Access (WPA) 프로토콜에서도 사용
WEP encryption algorithm
- IV값 = 키 스트림 초기화를 위해 사용하는 난수 24bit=3byte
- Shared Key i (WEP 키) = 사전에 서로 가지고 있는 대칭 키
- 암호화 과정
- WEP+IV값은 RC4알고리즘에 입력으로 들어가 키스트림 생성
- Plaintext+ICV(평문의 무결성을 확인하기 위한 값, 키스트림을 XOR 연산하여 Ciphertext 생성
- 최종 암호화된 데이터 = IV/KeyID(암호화안됨)+Ciphertext(암호화됨)
- 복호화 과정
- IV값과 WEP대칭키를 이용하여 암호화 과정과 똑같이 키 스트림 생성
- Ciphertext를 키스트림과 XOR해서 Plaintext+ICV를 얻음
- Plaintext를 Integrity Check Algorithm에 넣어 나온 ICV’값과 실제 ICV값 일치하는 값을 찾음

WPA3 process
- Wi-Fi 무선 네트워크 통신을 위한 보안
- AES GCMP-256 authenticated encryption is used
- GCMP-256 AES 암호화 알고리즘을 기반으로 하는 256비트 키를 사용하여 암호화를 진행
  - IV : 암호화 세션마다 고유해야 하는 랜덤한 값으로 암호화 과정의 시작점으로 사용됨
  - Counter : IV에서 시작하여 각 블록 암호화 시마다 증가하는 값으로 IV와 결합하여 각 블록의 암호화에 사용되는 고유한 카운터 값 생성. 이는 키 스트림 생성에 직접적으로 사용됨
  - Shared Key : 256bit의 암호화 키로 AES 암호화 알고리즘을 이용하여 데이터를 암호화하고 복호화 하는데 사용
  - Ek : Shared Key, Counter를 AES 암호화 알고리즘에 입력하여 생성된 키스트림
  1. iv부터 시작하여 Counter은 매 암호화 세션마다 값이 증가함
  2. Counter와 Shared Key에 의해 암호화된 키스트림은 Plaintext와 XOR연산을 거쳐 Ciphertext 생성
  3. 메세지와 함께 보호되어야 하는 추가적인 데이터 Auth Data 는 Mult 과정을 거친 후 생성된 Ciphertext와 또다시 XOR 연산 후 mult 과정을 거침
  4. 이렇게 XOR 연산과 mult연산을 거친 후 Shared Key와 XOR 연산을 통해 Auth Tag를 생성

💡 메세지가 수신자에게 도달했을 때, 수신자는 같은 계산을 수행하여 수신된 인증 태그와 비교함으로써 메시지가 변경되지 않았음을 검증할 수 있음

ChaCha20 Stream Cipher

Adopted as a replacement for RC4 in several algorithms
Uses a pseudorandom round function based on add-XOR-rotate(AXR) operations on an internal state of sixteen 32 bit words arranged as a 4x4 matrix
- 내부 상태를 가지고 있으며, 32bit word 16개로 구성된 4x4 행렬로 배열됨. 알고리즘의 각 라운드에서는 내부 상태에 대해 특정 연산을 수행하는데, 이 연산은 add, XOR, rotate 조합으로 이루어진 가상의 라운드 함수를 기반으로 함

💡 ChaCha20 알고리즘은 AXR 연산을 수행하여 내부 상태를 혼합하고, 이 혼합된 내부 상태에서 키 스트림을 생성함

Block Cipher Modes of Operation

블록 암호 운용 방식으로 하나의 키 아래에 블록 암호를 반복적으로 안전하게 이용하게 하는 절차

Electronic Codebook(ECB)

Each block of plaintext bits is encoded independently using the same key
simplest mode
Plaintext is handled b bits at a time and each block is encrypted using the same key
“Codebook” because have unique ciphertext value for each plaintext block
- Not secure for long messages since repeated plaintext is seen in repeated ciphertext
To overcome security deficiencies you need a technique where the same plaintext block, if repeated, produces different ciphertext blocks

Cipher Block Chaining(CBC)

The input to the encryption algorithm is the XOR of the next block of plaintext and the preceding block of ciphertext

Cipher Feedback(CFB)

Input is processed s bits at a time. Preceding ciphertext is used as input to the encryption algorithm to produce psedorandom output, which is XORed with plaintext to produce next unit of ciphertext
CFB 모드는 블록 암호를 스트림 암호처럼 사용할 수 있게 해주는 암호 운용 모드 중 하나로, 입력 데이터를 s 비트 단위로 처리함
Shift Register : 초기에 IV로 채워지며, 이후의 각 단계에서는 이전 단계의 출력을 사용하여 갱신됨
암호화 과정
1. 초기화 벡터(IV)를 Shift register에 로드
2. Shift register의 내용을 블록 암호 알고리즘에 입력하여 암호화
3. 암호화된 출력의 앞쪽 sbits 만큼을 평문 Pi의 sbits와 XOR연산. 이 연산의 결과가 Ci, 즉 암호문의 i번째 부분이됨
4. Shift register를 왼쪽으로 sbits만큼 shift하고, Ci를 Shift register의 으론쪽 끝에 추가
5. 2~4단계를 모든 평문이 처리될 때까지 반복
복호화 과정
- XOR 연산을 Ci와 수행하여 평문 Pi를 얻음

Counter(CTR) Mode

Each block of plaintext is XORed with an encrypted counter. The counter is incremented for each subsequent block

이은지

소통하는 개발자가 꿈입니다!

이전 포스트

[Information Security] Chapter 2. Cryptographic Tools

다음 포스트

[Information Security] Chapter 20. Symmetric Encryption and Message Confidentiality