03 대칭키

m = maj(X8, Y10, Z10)

if m == X8:
    t = X13 ^ X16 ^ X17 ^ X18
    X.rotate(1)		# Right Shift
    X0 = t

if m == Y10:
    t = Y20 ^ Y21
    Y.rotate(1)		# Right Shift
    Y0 = t

if m == Z10:
    t = Z7 ^ Z20 ^ Z21 ^ Z22
    Z.rotate(1)		# Right Shift
    Z0 = t
        
# Key Stream bit       
S = X18 ^ Y21 ^ Z22

각 단계(Round)에서 위에 적힌 코드를 수행한다.

m = maj(X8, Y10, Z10) 연산을 시행한다.

└ maj는 더 많은 수를 반환하는 함수, Ex) maj(0, 1, 0) = 0, maj(1, 1, 0) = 1

그 후 maj에서 비교한 인자들을 m과 확인하여 각 연산을 수행한다.

최종적으로 S(키 스트림)은 각 레지스터의 최우측 비트의 XOR 연산 결과이다.

이를 그림으로 보면 위와 같다

X8의 bit는 1, Y10의 bit는 0, Z10의 bit는 1이다. maj(1, 0, 1)은 1이므로 m은 1이다.

m과 X8, Z10이 각각 같기 때문에, X와 Z에서 시프트 연산이 일어나게 되고

결국 X, Y, Z의 최우측 비트는 각각 0, 1, 0이 된다.

S = X18 ^ Y21 ^ Z22 = 0 ^ 1 ^ 0 = 1이므로 키 스트림 비트는 1이다.

이렇게 N번 반복하여 길이가 N인 키 스트림을 완성한다.

키 스트림과 평문을 XOR 연산하면 암호문이 생성된다.

이런 시프트 레지스터 기반 암호는 하드웨어에서 효율적이다. (소프트웨어 구현은 어렵다.)

과거에는 자주 사용했지만, 현재는 SW로도 구현 가능하면서도 점차 사용하지 않는 추세이다.

└ 특정 분야에서는 아직 사용한다.

RC4

A5/1는 1bit씩 생성했지만, RC4는 1Byte씩 생성한다.

└ 이는 곧 A5/1는 하드웨어에서, RC4는 소프트웨어에서 효율적이라는 뜻과 같다.

RC4는 각 단계에서 Lookup 테이블 요소를 교환하고 테이블에서 키 스트림 Byte를 선정한다.

이 Lookup 테이블은 항상 0, 1, ..., 255의 어떤 순열을 포함하고, 키를 이용해 이 순열을 초기화한다.

# 초기화 단계(KSA : Key-Scheduling Algorithm)
key = input()

S = [ i for i in range(256) ]	# 0 ~ 255까지 초기화
K = [] # 입력받은 key로 초기화, key 길이가 256 이상이면 잘라서 그대로 넣고 짧다면 key를 반복

j = 0
for i in range(N):
    j = (j + S[i] + K[i]) mod 256
    swap(S[i], S[j])

위에서 언급한 RC4 초기화를 코드로 분석해보자.

S(state vector의 앞글자를 딴 S이다) 배열을 0부터 255까지 초기화한다.

입력받은 key를 기준으로 K 배열을 초기화한다.

└ 예를 들어 key가 "keystream"이라면 길이가 256이 될 때까지 keystreamkeystream... 반복적으로 넣어 K를 초기화한다.

그 후 반복문에 따라 S의 위치를 바꾸어 초기화 해준다.

# 키 스트림 생성 단계(PRGA : Pseudo-Random Generation Algorithm)
i, j = 0, 0
Plaintext = input()

while (P := len(Plaintext)) > 0:
    i = (i + 1) mod 256
    j = (j + S[i]) mod 256
    
    swap(S[i], S[j])
    
    t = (S[i] + S[j]) mod 256
    keystreamByte = S[t]
    
    P -= 1

평문을 입력받아 평문의 길이만큼 반복해준다.

반복하는 과정에서 keystreamByte에 1Byte씩 추가될 것이다. 반복문이 끝나면 키 스트림 바이트가 생성된다.

생성한 키 스트림 바이트를 일회성 키처럼 사용할 수 있다.

이때 초기화 해준 256Byte의 S 배열은 폐기해야 한다. 공격자가 키를 복구하는 것에 대비함이다.

동작 과정이 이해가 되지 않는다면 이 영상을 참고하자 https://www.youtube.com/watch?v=kfdvlaOD1ig&t=172s

3. 블록 암호

특징과 표기

1bit 혹은 1Byte씩 암호화하는 스트림암호와 달리, 블록 암호는 고정 크기 블록(정해진 길이)으로 암호화한다.

평문과 암호문 모두 고정 크기 블록으로 구성한다.

P = 평문 블록(Plain block)

C = 암호문 블록(Cipher block)

C = E(P, K) : 암호문 C를 얻기 위해 키 K로 P를 암호화

P = D(C, K) : 평문 P를 얻기 위해 키 K로 C를 복호화

P = D(E(P, K), K), C = E(D(C, K), K)

Feistel

Feistel(페이스텔) 암호는 특정 암호 체계가 아닌, 아래에서 설명하는 블록 암호 설계의 한 형태이다.

암호화 과정

1. 평문을 좌우 반으로 나눔 : 평문 = (L₀, R₀)

2. 각 회전(1, 2, ..., N)에서 다음을 계산한다.

ㆍ L_i = R_i-1

ㆍ R_i = L_i-1 ⊕ F(R_i-1, K_i) // F는 회전 함수, K는 보조키

3. 암호문 (L_N, R_N)을 얻음

복호화 과정

1. 각 회전(i = N, N-1, ..., 1)에서 다음을 계산한다.

ㆍ R_i-1 = L_i

ㆍ L_i-1 = R_i ⊕ F(R_i-1, K_i) // F는 회전 함수, K는 보조키

2. 평문 (L₀, R₀)를 얻음

페이스텔 특징

1. 공식은 어떤 함수 F에 대해서도 성립한다.

2. 그러나 특정 함수 F에 대해서만 안전하다.

DES

DES는 Data Encryption Standard의 준말로, 1970년대 개발한 암호화 알고리즘이다.

IBM Lucifer 암호를 기반으로 미 정부 표준으로 국가안보국(National Security Agency)에서 비밀리에 개발했다.

설계과정은 비공개이지만, 키의 길이가 줄어든 것 때문에 논쟁이 있었다.

DES는 Feistel 암호이다.

64bit 블록, 56bit 키, 16Rounds(회전), 각 회전에서 48bit 보조키를 사용한다.

각 회전은 단순한 알고리즘이기에, 안전성은 주로 S-box에 의존한다.

└ 8개의 S-box를 사용하고, 각 S-box는 6bit를 4bit로 압축한다.

DES Round는 확장 E 박스, 압축 S 박스, 치환 P 박스 3단계 구조로 이루어진다.

Expansion 박스에서는 32bit 입력을 48bit 출력으로 확장시키고,

Substitution 박스에서는 6bit 입력을 4bit 출력으로 매핑시키고,

Permutation 박스에서는 32bit 입력을 32bit 출력으로 위치를 바꿔준다.

Substitution은 6bit짜리 8개 박스로 나누어 압축을 실행한다.

E-Box 위치(왼쪽), S-Box 위치(가운데), P-Box 위치(오른쪽)

E-Box는 정해진 인덱스에 따라 bit를 중복하여 확장한다.

S-Box는 6bit 중 첫 번째와 마지막 bit를 합쳐 행으로, 나머지 4bit를 열 번호로 하여 주어진 표에 해당하는 수를 선택한다.

P-Box는 정해진 인덱스에 따라 bit 위치를 변경한다.

보조키는 위의 과정에 따라 생성된다.

Key(bits)	가능한 키의 수	실행 시간(1 decypt/us)	실행 시간(10^6 decypt/us)
32	2^32 = 4.3 * 10^9	2^31us = 35.8min	2.15ms
56	2^56 = 7.2 * 10^16	2^55us = 1142yrs	10.01hrs
128	2^128 = 4.3 * 10^38	2^127us = 5.4 * 10^24yr	5.4 * 10^18yrs
168	2^168 = 4.3 * 10^50	2^167us = 5.9 * 10^36yr	5.9 * 10^30yr

DES의 안전성은 다수의 S-Box에 의존한다.

30년간 분석으로 백도어 공격은 없는 것으로 알려졌고, 오늘날 가능한 공격은 전수키 조사 뿐이다.

3DES

현재 DES의 56bit 키는 안전하지 않기에 중첩하여 사용한다.

삼중 DES(3DES)로 112bit 키를 사용한다.

C = E(D(E(P, K1), K2), K1)

P = D(E(D(C, K1), K2), K1)

Q. 2개의 키로 암호화-복호화-암호화(EDE)하는 이유

A. 이런 구조가 DES와 호환되기 때문이다. E(D(E(P, K), K), K) = E(P, K)

Q. 왜 C = E(E(P, K), K)가 아닌가

A. 여전히 56bit의 키로 보안성이 증가하지 않았다.

Q. 왜 C = E(E(P, K1), K2)가 아닌가

A. 선택적 평문 공격을 받을 가능성이 있기 때문이다.

AES

AES는 Advanced Encryption Standard의 준말로, DES를 대체할 발전된 암호 알고리즘이다.

DES는 전수키 조사에 안전하지 않고, 3DES는 3번의 DES 연산으로 속도가 느리다.

효율과 안전을 위해서는 더 큰 블록이 필요하다.

1997년 NIST(National Institute of Standards and Technology)는 공식적으로 알고리즘 응모를 진행하였다.

응모하는 AES의 요구사항은 다음과 같다.

ㆍ 저작권 없이 전세계에서 사용할 수 있도록 비밀 없는(Unclassified) 암호 알고리즘

ㆍ 대칭키 방식이어야 함

ㆍ 블록 암호 방식과 블록 크기는 최소한 128bit여야 함

ㆍ 키 길이는 128bit, 192bit, 256bit여야 함

1998년 NIST 15개의 AES 후보 알고리즘을 발표했다.

ㆍ 결과적으로 라인댈(Rijndael) 알고리즘이 선정됐다.

ㆍ Rain Doll 또는 Rhine Doll로 발음한다.

ㆍ 반복되는 블록 암호 (DES와 동일하다)

ㆍ 페이스텔 암호가 아님 (DES와 상이하다)

AES 한 라운드 동작 과정(왼쪽), AES 키 확장 Round Constant(오른쪽)

블록 크기 : 128bit, 192bit, 256bit (공식 AES의 블록 크기는 128bit)

키 길이 : 128bit, 192bit, 256bit (블록 크기와는 독립적)

반복 횟수는 가변적이다

└ Round 10 : B = K = 128bit

└ Round 12 : B = K = 192bit and the other ≤ 192bit

└ Round 14 : B = K = 256bit

각 회전에서 4개의 함수를 사용한다.

└ ByteSub : 비선형 계층, 치환

└ ShiftRow : 선형 혼합 계층, 순열

└ MixColumn : 비선형 계층, 치환

└ AddRoundKey : 키 추가 계층, 치환

AES는 복호화를 위해서 진행 과정은 반드시 역산이 가능해야만 한다.

└ ByteSub : 역산 가능 > 역산은 Lookup 테이블로 구축

└ ShiftRow : 역산 가능 > Cyclic Shift의 반대 방향으로 진행

└ MixColumn : 역산 가능 > 역산은 Lookup 테이블로 구축

└ AddRoundKey : 역산 가능 > ⊕ 연산 자체가 역산

4. 그 밖의 블록 암호

IDEA

ㆍ IDEA : International Data Encryption Algorithm

ㆍ Xuejia Lai와 James Massey가 발명한 알고리즘

ㆍ 64bit 블록, 128bit 키

ㆍ 혼합 모드 연산(여러 수학 연산의 결합)

Blowfish

ㆍ Bruce Schneier(브루스 슈나이어)가 발명한 알고리즘

ㆍ 64bit 블록, 448bit까지 변화 가능한 키

ㆍ 페이스텔 암호 형태

└ R_i = L_i-1 ⊕ K_i

└ L_i = R_i-1 ⊕ F(L_i-1 ⊕ K_i)

ㆍ 회전 함수 F는 4개의 S-Box를 사용

ㆍ 각 S-Box는 8bit를 32bit로 매핑

ㆍ 키에 의존하는 S-Box(키에 의해 S-Box들이 결정)

RC6

ㆍ Ron Rivest, Matt Robshaw, Ray Sidney, Yiqun Lisa Yin가 AES 공모에 맞추어 발명

ㆍ 다양한 파라미터 지원 : 블록 크기, 키 크기, 회전 수

ㆍ AES 경쟁 시 마지막까지 검토된 후보 암호

ㆍ 회전(rotation)이 데이터에 의존

└ 알고리즘의 한 부분이 자료에 의존하는 것이 타 알고리즘과의 차이점

TEA

ㆍ Tiny Encryption Algorithm

ㆍ 64bit 블록, 128bit 키

ㆍ 32bit 연산 컴퓨터를 가정한 알고리즘

ㆍ 회전 수는 가변적 (32회 정도면 안전하다고 취급)

ㆍ 간단한 회전 함수 사용으로 상대적으로 많은 회전이 필요

ㆍ 페이스텔 암호화 유사한 형태(XOR 대신 +와 - 연산)

ㆍ 구축이 쉬우며, 빠르고 작은 메모리 요구

ㆍ 관련 키 공격이 가능한 알고리즘

ㆍ 확장된 TEA(XTEA)는 관련 키 공격을 제거할 수 있지만, 더 복잡한 알고리즘이다.

ㆍ 단순한 TEA(STEA)는 암호 분석의 예제로 사용하는 안전하지는 않은 버전

운용 모드

블록 암호는 고정 길이 N비트 블록을 암호화하는 알고리즘이다.

임의 길이의 평문을 암호화 하기 위해서는 평문을 특정 길이로 분할하여 블록 암호에 입력해야 한다.

이럴 때 사용하는 방식으로 '운용 모드'를 정의하였다.

5가지(ECB, CBC, CFB, OFB, CTR)의 모드가 있지만 여기서는 3가지만 설명을 한다.

운용 모드 - ECB

ECB : Electronic Code Book

표기 방법 : C = E(P, K)

주어진 평문 : P0, P1, ..., Pm

암호화	복호화
C0 = E(P0, K)	P0 = D(C0, K)
C1 = E(P1, K)	P1 = D(C1, K)
...	...
Cn = E(Pn, K)	Pn = D(Cn, K)

코드북의 형태처럼 블록 암호를 사용하는 확실한 방법 (코드북 암호의 전자적 버전)

고정키 K에 대해 각 블록을 독립적으로 암호화한다.

ECB 모드 : 복사-붙여넣기 공격

1. 평문 "Alice digs Bob. Trudy digs Tom."

2. 평문을 블록으로 쪼갬 P0 = "Alice di" / P1 = "gs Bob." / P2 = "Trudy di" / P3 = "gs Tom."

3. 각 평문을 암호화 함 C0, C1, C2, C3

4. 이때 Trudy가 C1과 C3를 복사-붙여넣기 공격 시행

5. 복호화한 결과 "Alice digs Tom. Trudy digs Bob."

Trudy가 Ci = Cj임을 알았다면, Pi = Pj임을 안다. (두 블록의 평문이 같다)

Pi나 Pj를 모른다고 하더라도 평문의 일부라는 사실은 알 수 있다.

> 정보가 누출될 가능성이 있고, 한 블록의 정보로 다른 블록의 정보를 알 수도 있음

앨리스의 원본 이미지와 ECB모드(TEA)로 암호화한 그림이다.

같은 평문 블록에 대해서 같은 암호문을 뱉기 때문에 위와 같은 형태가 된다.

운용 모드 - CBC

CBC : Cipher Block Chaining

블록을 체인처럼 연결하는 방식

임의의 초기화 벡터(IV; Initialization Vector)가 모드 초기화를 위해 필요

초기화 벡터(IV)는 난수이지만 비밀일 필요는 없음

ECB 모드보다 안전, 실질적으로 추가 작업 없음

암호화	복호화
C0 = E(IV ⊕ P0, K)	P0 = IV ⊕ D(C0, K)
C1 = E(C0 ⊕ P1, K)	P1 = C0 ⊕ D(C1, K)
...	...
Cn = E(Cn-1 ⊕ Pn, K)	Pn = Cn-1 ⊕ D(Cn, K)

특징

ㆍ 암호화가 순차적으로 이루어짐 > 병렬화 불가능

ㆍ 메시지는 블록 크기에 맞춰야 함 > 크기가 많지 않을 경우 Padding 필요

ㆍ 같은 평문 블록도 다른 암호문 블록 생성

ㆍ 복사-붙여넣기 공격이 가능은 하나 복잡한 과정이 필요

ㆍ 오류의 영향이 있음 > 한 bit의 오류가 두 블록에 영향을 끼침

앨리스의 원본 이미지와 CBC모드(TEA)로 암호화한 그림이다.

같은 평문 블록에 대해서 다른 암호문을 뱉기 때문에 위와 같은 형태가 된다.

운용 모드 - CTR

CTR - Counter

임의 접근을 해야 할 때 대중적으로 사용

스트림 암호처럼 작동

암호화	복호화
C0 = P0 ⊕ E(IV, K)	P0 = C0 ⊕ E(IV, K)
C1 = P1 ⊕ E(IV+1, K)	P1 = C1 ⊕ E(IV+1, K)
...	...
Cn = Pn ⊕ E(IV+2, K)	Pn = Cn ⊕ E(IV+2, K)

5. 데이터 무결성

기밀성과 무결성

기밀성 : 정보를 오직 인가받은 사람에게만 공개하는 것

무결성 : 인가받지(허락받지) 않은 데이터의 수정을 방지하거나 탐지하는 행위

암호화 자체만으로는 기밀성을 제공하나, 무결성을 확신할 수 없다

한 번의 암호화로 기밀성과 무결성을 제공하는 것이 도전과제이다.

메시지 인증 코드(MAC : Message Authentication Code)

데이터의 무결성을 위해 사용하는 방법

CBC의 나머지로 계산하는 방법

CBC 암호화를 계산하여 암호문 블록의 마지막을 저장

MAC 계산

C0 = E(IV ⊕ P0, K)

C1 = E(C0 ⊕ P1, K)

C2 = E(C1 ⊕ P2, K)

...C_N-1 = E(C_N-2 ⊕ P_N-1, K) = MAC

이렇게 나온 MAC은 평문과 함께 전송한다.

수신자는 같은 방법으로 계산하여 결과가 수신받은 MAC과 같은지 여부를 점검한다.

└ 당연히 수신자도 키(K)를 알고 있어야 한다.

이때 동일하다면 무결성 입증에 성공한 것이다.

MAC 예시

1. Alice가 4개의 평문 블록을 가지고 있다.

2. Alice가 다음을 계산한다.

ㆍ C0 = E(IV ⊕ P0, K), C1 = E(C0 ⊕ P1, K), C2 = E(C1 ⊕ P2, K)

ㆍ MAC = C3 = E(C2 ⊕ P3, K)

3. Alice가 Bob에게 IV, P0, P1, P2, P3, MAC을 전송한다.

4. Trudy가 P1을 T로 변경했다.

5. Bob은 다음을 계산한다.

ㆍ C0 = E(IV ⊕ P0, K), C1 = E(C0 ⊕ T, K), C2 = E(C1 ⊕ P2, K)

ㆍ MAC = C3 = E(C2 ⊕ P3, K)

ㆍ Alice의 MAC ≠ Bob의 MAC

6. 오류가 MAC까지 이어진다(전파).

└ Key를 알지 못하는 한 Trudy는 MAC을 변경하는 건 불가능하다.

'학교 공부 > 스마트 콘텐츠 보안' 카테고리의 다른 글

05 해시 함수 (0)	2023.03.30
04 공개키 (0)	2023.03.30
03_1 SDES (0)	2023.03.30
02 암호 기초 (0)	2023.03.27
01 정보 보안의 개요_____교재 : 정보 보안 이론과 실제 (0)	2023.03.26

정리하며 삽시다