[시스템 보안] 대칭 키 암호

대칭키 암호는 스트림 암호, 블록 암호 2가지 흐름이 존재한다.

1. 스트림 암호

• 일회성 암호와 동일하지만 (차이점) 증명된 안전성을 희생하면서 다루기 쉽도록 상대적으로 작은 키 사용
• 키는 긴 비트열로 "늘려져" 일회성 암호에서 사용되는 방법과 동일
• 일회성 암호처럼 Confusion 원칙만 적용
• A5/1 : 하드웨어를 기본으로 하는 큰 규모의 스트림암호 분야
• RC4 : SSL을 포함해 여러곳에서 사용, 소프트웨어에서 효율적으로 구현

2. 블록암호

• 코드북 개념에 기초
• Confusion & Difusion 원칙이 모두 적용된다.
• DES : 상대적으로 단순할 뿐만아니라 다른 암호에게도 자연스러운 비교 대상
• AES : Advanced Encryption STD
• IEDA (International Data Encryption Alg)
• Blowfish
• RC6
• Tiny Encyption Algorithm
• 다양한 운영모드 존재

Stream Ciphers

- 길이가 n인 키 K를 가지고, 이 키를 긴 키스트림으로 늘린다.

- 키스트림은 평문 P와 XOR연산을 통해 암호문 C를 만드는데 사용된다.

- 따라서 키스트림을 사용하는 방법은 일회성 암호에서 키를 사용하는 방법과 동일하다.

- 스트림 암호를 복호화하기 위해서는 암호화에 사용된 똑같은 키스트림을 생성하고 다시 암호문과 XOR연산을 하게되면 평문이 만들어지게 된다.

- 키스트림 생성함수
StreamCipher(K) = S
- 암호화 수식
C0 = P0 ⊕ S0, C1 = P1 ⊕ S1, C2 = P2 ⊕ S2 ...
- 복호화 수식
P0 = C0 ⊕ S0, P1 = C1 ⊕ S1, P2 = C2 ⊕ S2 ...

- Sender and Receiver have same stream cipher alorithm and both know the key K

- 송신자와 수신자 모두 같은 스트림암호 알고리즘과 키 K를 사용하기 때문에 시스템은 일회성 암호를 실용적으로 일반화 한것으로 볼 수 있다.

- 하지만 일회성 암호만큼 충분한 안전성은 확보되지 않을 수 있다.

 

A5/1

- A5/1은 선형 피트백 시프트 레지스터(LFSR)를 사용한다.

- 레지스터 X(x0, x1 ... x18) 는 19 비트로 구성된다. 레지스터 Y(y0, y1 ... x21) 는 22비트로, 레지스터 Z(z0, z1 ... z22) 는 23 비트로 구성된다.

- 즉 LFSR 3개를 모두 합치면 64 비트가 되도록 설계되었다.

- 키 값 = 64bits

- X 레지스터 단계에서는 다음과 같은 연산이 이루어진다.

t = x13 ⊕ x16 ⊕ x17 ⊕ x18

xi = xi-1, 여기서 i = 18, 17, 16 ... 1

x0 = t

​

- Y 레지스터 단계에서는 다음과 같은 연산이 이루어진다.

t = y20 ⊕ y21

yi = yi-1, 여기서 i = 21, 20, 19 ... 1

y0 = t

​

- Z 레지스터 단계에서는 다음과 같은 연산이 이루어진다.

t = z7 ⊕ z20 ⊕ z21 ⊕ z22

zi = zi-1, 여기서 i = 22, 21, 20 ... 1

z0 = t

 

- Each value is a single bit

- 주어진 3비트 x,y,z에서 maj(x,y,z)를 '다수결'기능을 수행하는 함수로 정의

- 즉, 과반수 이상이 0이면 0을 , 1이면 1을 반환한다.

- 색칠되어 있는 x8, y10, z10 이 세 가지의 값이 시프트의 기준 -> Clocking bit라고 한다.

- 세 개 값의 다수결 함수를 통해 기준 설정 => m = maj(x8, y10, z10)

- 0,0,1 이면 0이 기준이되고, 1,0,1이면 1이 기준이 된다.

- X,Y,Z 레지스터는 다음 규칙에 따라 시프트

• 만약, x8 = m 이면 X 는 시프트
• 만약, y10 = m 이면 Y 는 시프트
• 만약, z8 = m 이면 Z 는 시프트

- 기준과 다른 값이면 연산을 진행하지 않고, 기준과 같은 값이면 연산을 진행한다.

• X의 경우, x13, x16, x17, x18 의 각 값을 XOR
• Y의 경우, y20, y21 의 각 값을 XOR
• Z의 경우, z7, z20, z21, z22 의 각 값을 XOR

- 계산 값을 저장한 후에 Shift-Right 연산을 진행하고, 저장했던 값을 시프트연산 중에 비게 된 0번째 인덱스에 넣는다.

- 시프트 연산을 통해 손실되는 데이터의 정보를 담고 있기 때문에 중요한 요소가 된다.

- 시프트 연산을 완료하면  -> 마지막 인덱스인 x18, y21, z22 의 값을 XOR

- 연산한 값이 키 스트림의 한 비트

- 위의 예제에서 Clocking bit의 값은 1,0,1 이 되고, m은 1이 되게 된다.

- y 만 시프트연산을 수행하지 않아도 된다.

- 키 스트림 비트는 0 ⊕ 1 ⊕ 0 = 1

 

RC4

- 소프트웨어로 구현하도록 설계 & 각 단계에서 키스트림 한 바이트를 생성  (차이점) A5/1은 하드웨어로 구현되도록 설계 , 키 스트림 한 비트 생성

- RC4는 기본적으로 256 바이트 값의 배열이 들어있는 검색표

- RC4는 바이트 단위로 실행

- RC4 암호 체계의 구성

• 키 스트림이 만들어지기 위한 재료로서 임의의 배열 선언
• 배열을 안에 각 인덱스를 값으로 넣음 ( S[] = {0,1,2,3,4,5,6,7,8, ... } )
• 키값을 통해 배열의 값을 섞는다
• 정해진 규칙으로 배열을 이용해 키 스트림 생성
• XOR 을 통한 암호문 생성

- 키의 길이가 0 부터 256 까지 모두 가능하다는 것이다.

- 키의 용도는 단지 순열 S를 초기화는 것

- 키가 배열을 구성하고, 배열이 키스트림을 구성하고, 키스트림이 암호문 만들어냄

- 키 스트림 바이트 생성

i := 0
j := 0
while GeneratingOutput:
i := (i + 1) mod 256
j := (j + S[i]) mod 256
swap values of S[i] and S[j]
K := S[(S[i] + S[j]) mod 256]
output K
endwhile

- 출력된 키스트림은 암호문을 위해 평문과 XOR 연산을 하거나 복호하를 이해 암호문과 XOR연산을 하게 된다.

- Use keystream bytes like a one-time pad

- 처음 생성하는 256바이트의 키스트림을 버리면 공격이 불가능하다.

 

Block Ciphers

- 블록 암호는 평문을 일정한 크기의 블록으로 나누고 고정된 크기를 가지는 블록 단위의 암호문을 생산한다.

- 여러번의 회전(round)에 거쳐 함수 F를 반복 수행하는 과정을 거쳐 평문으로부터 암호문이 생성된다.

- 함수 F는 이전 회전의 출력과 키 K에 값에 의해 정해지는데, 각 회전마다 반복적으로 적용되기 때문에 회전함수라고 불린다.

- 블록 암호의 설계 목표 : 비밀성 & 효율성

 

Feistel Cipher

- 페이스텔 암호는 특정 암호체계 지칭 X, 암호의 일반적인 설계 원리 의미- 평문 P 가 왼쪽과 오른쪽으로 반반씩 나뉘어 구성된다.

P = (L0, R0)

- 회전을 통해 새로운 왼쪽 반과 오른쪽 반은 아래와 같은 규칙에 따라 계산된다.

Li = Ri-1
Ri = Li-1 ⊕ F(Ri-1, Ki)

- Ki 는 i 번째 라운드에서 사용되는 서브키이고 F 는 라운드 함수이다.

- 서브키는 키 스케줄 알고리즘에 따라 키 K 로 부터 얻어진다. 최종 암호문은 마지막 라운드의 출력이다.

    

① 라운드 입력을 L 과 R 로 나눈다.

② R 을 라운드 함수 F 로 보낸다.

③ 라운드 함수 F 는 R 과 서브키 k 를 입력으로 사용하여 랜덤하게 보이는 비트를 계산한다.

④ 얻어진 비트열과 L 을 XOR 해 다음 라운드 R 의 입력이 된다.

⑤ 현재 라운드의 R 은 다음 라운드 L 의 입력이 된다.

 

- 페이스텔 암호에서 복호화는 특정한 회전 함수 F에 무관하게 복호화 가능하다.

- 복호화는 암호화의 역순으로 식을 풀어나가면 된다.

Ri-1 = Li
Li-1 = Ri-1 ⊕ F(Li-1, Ki)

DES

- DES는 16개의 회전을 갖는 페이스텔 암호이다.

- 64비트의 블록 길이를 갖는다.

- 56비트의 키를 사용

- 각 회전은 48비트의 보조키를 사용하고, 각 보조키는 56비트 키 중에서 48비트를 사용해서 구성된다.

- Security depends on "S-Boxes"

- 각 s-박스가 6비트를 4비트로 매핑, 서로 다른 8개의 박스를 사용한다.

- S-박스를 모두 합치면 48비트를 32비트로 매핑하는 것을 의미

 

① DES 암호화

⑴ 64 비트 평문에 있는 각 비트의 위치를 바꿈(초기 치환 함수 이용).

⑵ 서로 다른 서브키 로 동일한 절차를 수행(라운드 함수 이용).

⑶ 64 비트 입력을 32 비트로 나누어서 위치를 교체

⑷ 단계 ⑶ 의 출력인 64비트의 각 비트 위치를 바꿈(최종 치환 함수 이용)

​

② DES 복호화

⑴ 64 비트 암호문에 있는 각 비트의 위치를 바꿈(초기 치환 함수 이용)

⑵ 서브키의 생성 절차는 암호화와 동일하나 암호화의 역순으로 서브키를 적용

⑶ 64 비트 입력을 32 비트로 나누어서 위치를 교체

⑷ 단계 ⑶ 의 출력인 64비트의 각 비트 위치를 바꿈(최종 치환 함수 이용)

 

Block Cipher Notation

- P : 평문 블록

- K : 키

- C : 암호문 블록

DES에서는 P와 C는 각각 64비트

K는 56비트가 된다.

P를 키 K를 이용해서 암호화 하는 표기법은  C = E(P,K) & 해당되는 복호화는 P = D(C,K)

 

Double DES

- 이중 DES를 이용해 암호화를 하게 되면 보다 더 긴 길의 키로 사용할 수 있는 것 처럼 보인다.

- C = E(E(P,K1),K2) --> 선택된 평문 공격방법으로 수행가능 = 특정한 평문 P를 선정하고 이에 해당하는 C획득 공격

- 키 K1, K2값을 찾는 것이 목표라고 했을 때, 먼저 가능한 모든 키 K값에 대해 E(P,K)와 K쌍을 포함하는 2^56 크기의 표를 미리 계산한다. 그리고 E(P,K) 값으로 표를 정렬한다. 

- 이 표와 선택한 P에 해당하는 C를 가지고, 키 K'로 표에 있는 D(C, K')를 찾을 때까지, C를 복호화 한다.

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

여기서K'와 K는 이미 알려진 값이다. 

- 112 비트의 키를 모두 찾았는지는 양쪽 변을 K'로 암호화해보면 알 수 있고 이의 결과를 식으로 나타내면

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

즉 K1 = K, K2 = K'가 된다.

- 따라서 이중 DES에 대한 공격은 는 2^56 요소의 표를 미리 계산하고 저장을 해야하는 문제가 생긴다. 

- 표를 만드는 계산은 딱 한번 수행

- 표를 여러번 사용하면 표를 만들기 위한 계산은 공격 수에 따라 상쇄 가능

- 표 만드는데 사용하는 시간을 제외하면 작업은 D(C, K) 를 표에 일치하는 값 찾는데에만 사용

- 기댓값은 2^56이 되며, 이 값은 단일 DES 에서 전수키 탐색 공격과 동일하다.

 

TRIPLE DES

- 이중 DES의 공격 방법과 비슷한 중간 만남 공격은 표를 미리 만들어서 계산해 만드는 것이 쉽지 않은 문제이다.

- 표 크기를 실질적으로 만들 수 있는 크기로 줄임 -> 공격 때마다 수행해야할 작업량 多 -> 비실용적

- 논리적 접근 식

C = E( E (E(P, K1), K2) K3) 이지만 실제로는 이 방법보단.

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

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

의 방법을 더 많이 사용한다.

- 즉, 2개의 키만 사용

- WHY????

1) Backward compatible with single DES = 앞쪽의 단독 DES와의 호환성 문제로 2개의 키만 사용

2) 112비트로 충분하기 때문에

- 암호화-복호화-암호화 (EDE) 방식이 EEE방식보다 많이 사용하는 이유이다.

- K1 = K2= k를 사용하게 되면 

C = E( D (E(P, K), K) K) = E( P, K ) 즉, 3DES는 단일 DES와 동일하게 된다.

 

AES(Advanced Encryption STD

- DES는 키의 길이 56비트로 짧기 때문에 전수 키 조사에 취약하다는 단점을 가지고 있다.

- 반복되는 블록암호라는 점에서 DES와 동일하지만, AES는 페이스텔 암호가 아님

--> AES를 복호화하기 위해서는 AES의 연산과정을 거꾸로 수행가능해야한다는 것을 의미한다.

- 128비트, 192비트, 256 비트 등 3가지 블록 크기가 가능하다.

- 블록의 크기와 상관없이 세 가지 키 길이가 가능하다.

- 회전의 수는 키 길이에 따라 10~14까지 변화된다.

- 각 회전은 4개의 함수로 구성되어 있고, 각 함수는 3가지 '층' 레이어 중 하나이다.

 

3가지 추가 블록 암호

1. IDEA

- 혼합 모드 연산이다.

- 모듈로 2^16 덧셈을 사용하고 외부적으로는 비선형 성질을 위한 S-box가 불필요하다는 특징을 가진다.

2. 블로피쉬

- 키에 의존하는 S-box를 사용한다는 점이 특이

- 고정된 박스를 사용하는 것이 아니라. 키를 사용해서 박스를 생성하게 된다.

3. RC6

- 데이터에 의존하는 순환을 이용한다는 점이 특이

- 필수적인 연산 부분이 데이터 의존하는 것은 매우 이례적

 

TEA( Tiny Encryption Alogrithm)

- 64 비트 블록 길이와 128비트 키 사용

- 32비트 컴퓨터 구조를 가정하여 작성되었음 -> 모든 수학적 연산은 내부적으로 모듈이 2^32

- 매우 간단한 회전 함수 사용

- 높은 보안성을 유지하려며느 회전의 수를 상대적으로 증가시켜야함

- 페이스텔 암호가 아니기 때문에 암호화와 복호화의 처리 순서를 구분해야한다.

- XOR 연산 대신 덧셈/뺄셈을 이용한다는 것을 제외하면 "거의" 페이스텔 암호와 동일하다고 할 수 있다.

 

Block Cipher Modes (블록 암호 모드)

- 스트림 암호를 사용하는 것은 간단 => 평문의 길이와 같은 키스트림을 생성해 XOR연산을 진행하면 된다,

Ex)

평문 블록이 P0, P1 ... 2개 이상이라고 가정

키 K가 고정되어 있다면 평문과 블록간의 매핑이 고정되기 때문에 블록 암호 = 한권의 코드북으로 생각 가능

코드북 개념에 따르면, 전자 코드북(ECB 모드) 모드로 블록 암호를 사용한다고 할 수 있다.

 

1) ECB(Electronic CodeBook) 모드

하나의 블록에서 보내고자하는 평문을 잘라서 각각 independent 하게 블록하는 방식이다.

Notaton :

C = E(Pi, K) & P0, P1 ... 여러개의 블록으로 구성

각각 block cipher 알고리즘을 사용하게 되면 

<Encrypt>                                    <Decrypt>
C0 = E(P0, K)                              P0 = D(C0, K)
C1 = E(P1, K)                              P1 = D(C1, K)
...                                             ...

을 만족할 것이고, 키에 따라서 여러개의 일레트로닉 코드북이 존재하게 될 것이다.

 

문제점

공격자가 Ci = Cj를 알았다고 가정하면 Pi = Pj임을 알 수 있다.

Pi 또는 Pj를 모르더라도, 적어도 2개의 평문 블록이 동일하다는 것이 노출되기 때문에 문제가 생긴다.

ex)

64비트로 암호화된 블록 암호라고 가정했을 때, 각 문자는 8비트일 것이다.

암호문에 대해 Ci = E( Pi, K)라고 가정했을 때, 문장을 잘 자르고, 만약에 트루디가 문장에 대해서 사전 정보를 가지고 있다면, cut & paste공격이 가능해진다.

 

2) CBC(Cipher Block Chaining Mode) 모드

ECB 모드의 취약점이 보완 가능해진다.

한 블록에서 만들어진 암호문이 다음 블록의 평문이 되기 전에 모호하게 만드는 것이다.

따라서 동일한 평문이여도 동일한 암호문이 생성되지 않는다.

- 암호화를 할 때는 평문블록과 이전암호블록을 XOR 연산한 뒤, 키 K를 통해 암호화 를 하고

​- 복호화를 할 때는 암호블록과 키 K로 복호화를 한 뒤 이전암호블록과 XOR 연산을 한다.

- 첫 블록은 암호문 블록이 없기 때문에 초기화 벡터를 사용한다.

- 암호문이 비밀이 아니기 때문에, 초기화 벡터가 암호문 블럭 역할을 진행한다. 꼭 비밀일 필요는 없다.

즉, IV is random but need not be secret

- 오류들에 영향을 받을 수 있다.

ex) Ci에 오류가 발생했고, 오류가 발생한 암호 블럭을 G라고 하면 

암호화에 경우 = 앞이 달라지면 뒤에도 전부 영향 O

복호화에 경우 C2가 달라지면 P2가 바뀌고 P3도 달라지지만, P4부터는 C2의 영향이 가지 않기 때문에 블록에 오류가 발생하지 않게 된다.

 

3) CTR(Counter Mode) 모드

연쇄적인 CBC의 방식을 보완한 방법이다.

- CBC와의 공통점은 초기화 벡터인 IV가 쓰인다는 점이고,

​- 차이점은 CTR은 IV가 모든 블록의 암호화에 다 쓰인다는 점이다.

​- 그리고 XOR 연산의 피연산자가 다르고 이전 암호블록이 들어가지 않는 대신 카운터가 들어간다.

 

Integrity(무결성)

무결성 = unauthorized modification of data : 비인가자가 쓰는 행위(변경) 방지

- 암호화가 요구되는 보안성을 효과적으로 제공가능하다.

- 메시지 인증 코드 (MAC)은 데이터 무결성을 보장하기 위해 블록암호를 사용한다.

 

MAC(Message Authentication Code)

- 데이터의 무결성을 보장하기 위해 사용

- 데이터를 CBC모드로 암호화 -> 마지막 블럭만 남기고(MAC이 마지막 블럭) 나머지는 버린다.

• 원본 메시지 M을 비밀키 K와 병합하여 해시 수행
• 여기서 만들어진 MAC과 메시지 M을 안전하지 않은 채널로 전송
• Bob은 수신한 메시지 M과 비밀키 K로MAC'을 생성
• 수신한 MAC과 자신이 생성한 MAC'을 비교
• 동일하다면 전달받은 메시지의 무결성이 입증됨과 동시에 출원지가 Alice라 판단

 - 송 수신자가 대칭키와 IV를 공유해야하는 문제점을 가지게 된다.