Symmetric Crypto (대칭키 암호)

Symmetric crypto는 대칭키 암호로써, 암호화와 복호화를 할 때 같은 키를 사용하는 암호이다.

Symmetric crypto는 크게 Stream Cipher와 Block Cipher 두 가지로 나뉜다.

Stream Cipher는 one-time-pad(일회성 암호)와 거의 동일하다.

one-time-pad와 다른 점은 key의 size가 상대적으로 작고, 작은 key를 길게 늘려서 one-time-pad와 같이 사용한다.

Block Cipher는 codebook(코드북)의 개념과 거의 동일하다.

블록 암호 키는 codebook에 의해 결정된다. 각각의 키는 다른 코드북을 생성한다.

Stream Cipher

Stream Cipher의 예시로 A5/1, RC4를 설명한다. A5/1은 hardware 기반이고, RC4는 software 기반이다.

Block Cipher는 DES, Tripple DES, AES를 설명한다.

Stream Cipher는 Key K를 평문 P에 맞게 긴 Key stream으로 늘린 후 K와 P의 XOR 연산을 통해 암호문 C를 얻는다.

암호문 C를 복호화하여 평문 P를 얻기 위해 다시 K를 이용한 Key stream을 이용해 C와 K의 XOR 연산을 통해 평문 P를 얻는다.

암호화와 복호화를 위해 같은 Key를 사용하고, 송신자, 수신자 또한 동일한 stream algorithm과 key를 사용한다.

A5/1

A5/1은 hardware 기반에서 작동하는 stream cipher이다.

A5/1을 수행하기 위해 X,Y,Z의 이름을 가진 선형 피드백 시프트 레지스터(LFSR)을 사용한다.

레지스터 X는 x0, x1, .... x18 까지 19 bit이다.

레지스터 Y는 y0, y1, .... y21 까지 22 bit이다.

레지스터 Z는 z0, z1, .... z22 까지 23 bit이다.

X+Y+Z는 64-bit이다. 따라서 A5/1의 Key size는 64 bit이다.

각각의 반복(iteration) or 클럭(clock)마다 각각의 레지스터(X,Y,Z)는 아래의 계산을 한다.

X 단계

Y 단계

Z 단계

A5/1은 hardware에서 작동하는 알고리즘이기 때문에 clock마다 결과값이 나온다.

매 clock 마다 아래와 같은 식에 의해 m 값이 나온다.

m 값을 가지고 각각의 레지스터는 아래의 규칙을 따라 

만일 x8 = m이면 X단계 실행

만일 y10 = m이면 Y단계 실행

만일 z10 = m이면 Z단계 실행

maj(x, y, z) 함수는 가장 많은 것을 출력하는 함수로 만일 maj(1, 1, 0)이면 X단계, Y단계를 실행하고 1을 return 한다.

maj(0, 1, 0)이면 Y단계를 실행하고 0을 return하는 함수이다.

또한 Key Stream은 각각의 X, Y, Z의 마지막 bit를 뽑아 아래와 같이 만든다.

이러한 key stream을 평문 P만큼 뽑아 평문과 xor 연산을 통해 암호문 C를 만들고

암호문 C를 key stream과 xor 연산을 하여 평문 P를 얻는다.

한 클럭마다 결과값이 생기기 때문에 클럭의 속도에 비례해 key stream이 생성된다.

RC4

RC4은 software 기반에서 작동하는 stream cipher이다.

RC4 알고리즘은 lookup table을 항상 가지고 있는데 256 byte의 순열이 들어있다. {0, 1, 2, ... , 255}

각 단계에서 key stream 한 바이트를 생성하는데 한 바이트가 생성 될 때마다 lookup table이 새롭게 수정된다.

RC4는 크게 2단계로 이루어진다. 키를 사용해 lookup table을 초기화한다. 알고리즘에 따라 key stream byte를 생성한다.

위에서 보듯이 key는 lookup table을 초기화 하는데만 사용하기 때문에 0~255까지 key size가 가능하다.

key[i], i =0, 1, 2, ... , N-1은 key의 바이트이다.

RC4의 초기화 단계는 아래와 같은 의사코드로 진행된다.

for i = 0 to 255
    S[i] = i
    K[i] = key[i mod N]
next i
j = 0
for i = 0 to 255
    j = (j + S[i] + K[i]) mod 256                                                
    swap(S[i], S[j])
next i
i = j = 0

RC4의 key stream 생성 단계는 아래와 같은 의사코드로 진행된다.

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]

이렇게 생성된 key stream Byte를 평문 P만큼 뽑아 평문과 xor 연산을 통해 암호문 C를 만들고

암호문 C를 key stream Byte과 xor 연산을 하여 평문 P를 얻는다.

RC4 알고리즘은 취약점이 발견되었는데, 첫 256 key stream byte를 버리면 보완 가능하다고 한다.

Block Cipher

Block Cipher는 block 단위로 평문을 나누어 일정한 크기의 블록으로 만들고 고정된 크기를 갖는 블록 단위의 암호문을 만든다.

암호문은 평문을 반복적인 round function에 의해 얻을 수 있다.

round function의 input으로 key와 이전 round function의 output이 들어간다.

Feistel Cipher (페이스텔 암호)

Feistel Cipher는 암호의 체계를 지칭하는 것이 아니라, 암호 설계의 원리를 지칭한다.

Feistel Cipher 체계에서 평문 P를 왼쪽 반, 오른쪽 반으로 나누어 아래와 같이 구성한다.

이렇게 나눈 평문 P를 이용해 아래의 규칙에 따라 round function이 동작한다.

여기서 K는 round key로 subkey라고도 불린다. round key schedule 알고리즘에 의해 round key가 생성된다.

이러한 round function을 N번 통해서 아래의 최종 암호문 C가 얻어진다.

복화화 과정은 암호화의 역순으로 진행된다. 복호화때 사용되는 규칙은 아래와 같다.

복호화 과정을 끝낸 최종 평문 P는 아래와 같이 얻어진다.

Feistel Cipher의 동작 과정을 그려보면 아래와 같이 그릴 수 있다.

DES (Data Encryption Standard)

DES는 1970년대 후반에 개발된 block cipher이다. 

DES는 peistel 구조를 가지고 있고 스펙은 다음과 같다.

- 64 bit의 block length

- 56 bit의 key length (원래 64 bit이지만, 8bit은 parity bit이다),

- 16 round function

- 48 bit의 round key(sub key)

DES의 round function의 작업은 아래와 같다.

S-box는 6bit를 4bit로 매핑하는 box이다. 총 8개의 S-box를 사용하므로 48bit를 32bit로 매핑한다고 생각할 수 있다.

각각의 round function에서 S-box는 동일한 box를 사용한다.

DES의 block length가 64bit이기 때문에 L과 R은 각각 32bit가 된다.

S-box는 치환 박스라고 하여, 6bit를 4bit로 치환하는 code book 과 같은 box이다.

DES의 round function은 아래와 같이 정의될 수 있다.

DES의 특징은 다음과 같다.

DES는 S-box에 의해 안전성이 결정된다.

key length가 56bit이기 때문에 exhaustive key search(전수키조사)를 통해 key를 찾을 수 있다.

Tripple DES

DES의 문제점을 해결하기 위해서 나온 방안이다.

우선 왜 Double DES는 사용하지 않는지에 대해 고민할 필요가 있다.

Double DES를 두가지 방법으로 사용할 수 있는데 우선 첫 번째 경우를 보자

Key를 두 번 사용하여 마치 key length가 56bit에서 112bit로 늘어난 것으로 생각할 수 있지만

동일한 key를 두 번 사용하였으므로 결국 56bit key를 한번 사용한 DES와 똑같다.

Double DES의 두 번째 경우이다.

이번 경우는 첫 번째 경우를 보완해 112bit의 key를 갖는다.

하지만 이 경우 또한 공격자가 미리 table을 가지고 있으면 DES와 같은 확률로 key를 찾을 수 있다.

(1)번 식을 조금만 변형하면 (2)번 식을 얻을 수 있다.

만일 공격자가 E(P,K1)의 모든 값에 대해 미리 계산한 table을 가지고 있다고 가정하자.

공격자는 Encryption에 의해 생긴 암호문 C와 K2를 가지고 복호화하여, E(P,K1)의 값을 찾을 수 있다.

Table을 만드는 시간을 빼면 정확히 DES의 exhaustive key search의 확률과 동일하다.

따라서 Tripple DES를 사용하는데 아래와 같은 방식으로 사용한다.

key를 K1, K2를 사용하기 때문에 112bit의 length를 가지고, DES와 호환이 가능하다.

하지만 DES 연산을 3번 해야하기 때문에 속도가 느려, AES를 사용하고 있는 추세이다.

AES (Advanced Encryption Standard)

AES는 DES의 취약점을 보완한 block cipher이다.

DES는 key length가 56 bit로 인해 exhaustive key search(전수키조사)에 취약하다는 것을 알기 때문에 key가 DES보다 더 길어졌다.

AES의 스펙은 아래와 같다.

- 128bit의 block length

- 128, 192, 256bit의 key lenght

- 10, 12, 14의 round function

round function은 아래 4가지 function으로 이루어져 있다.

- ByteSub

- ShiftRow

- MixColumn

- AddRoundKey

간단히 각 함수를 설명하면 아래와 같다.

ByteSub는 DES의 S-box와 거의 유사하다.

ShiftRow는 단순한 left shift이다.

첫번째 행은 변화 없음

두번째 행은 lsl #1

세번째 행은 lsl #2

네번째 행은 lsl #3

MixColumn은 shift operation과 xor operation으로 구성된다.

DES의 X-box와 유사한 목적이다.

AddRoundKey는 각 round 마다 key schedule를 통해 round key를 생성하기 위한 함수이다.

4가지 function 모두 역산이 수행 가능하기 때문에 복호화가 가능하고 복호화는 암호화의 역순으로 이루어진다.

Block Cipher mode

Block Cipher를 사용할 때 임의 입력 길이의 데이터를 암호화 및 복호화 하기 위해서 운영모드(mode of operation)를 적용해야 한다.

Block Cipher mode는 ECB, CBC, CTR, CFB, GCM 등등 존재하지만 여기서 ECB, CBC, CTR mode를 설명한다.

Block Cipher를 진행할 때 다수의 block을 암호화 해야하는데 각각의 mode마다 암호화 방식이 다르다.

ECB (Electronic Codebook mode) 

각각의 block을 모두 독립적으로 암호화한다.

ECB를 사용한 암호화는 아래와 같다.

ECB를 사용한 복호화는 아래와 같다.

각각의 block을 암호화와 복호화할 때 같은 key를 여러번 사용하는것이 특징이다.

ECB mode는 각각 독립적으로 암호화 하는 특징 때문에 Cut and Paste attack에 취약하다.

만일 평문이 아래와 같다고 가정하자.

M4RC0 love Bob. Trudy love Tom.

64bit block cipher를 사용한다고 가정하면 아래와 같이 4개의 평문으로 나뉜다.

P0 = M4RC0 lo

P1 = ve Bob. 

P2 = Trudy lo

P3 = ve Tom.

각각의 평문을 암호화 하면 C0, C1, C2, C3가 얻어진다.

하지만 공격자가 C0, C3, C2, C1의 순서로 전달하고, 송신자와 수신자가 이를 알아차리지 못하면 전혀 다른 뜻이 전달 될 수 있다.

M4RC0 love Tom. Trudy love Bob

ECB mode의 또 다른 취약점은 같은 key를 반복하여 사용한다는 것이다.

같은 평문을 가지면 같은 암호문이 생긴다. 이를 이용해 공격자가 평문의 일부분을 알게 될 수 잇다.

또한 유추도 가능하다. 아래의 그림을 참고하면 쉽다.

CBC (Cipher Block Chaining)

ECB mode의 약점을 보완한 mode이다.

암호 블록 연결 모드라 불리며 각각의 block들이 의존적으로 서로 연결되어 있다. ECB mode보다 훨씬 안정적이다.

CBC를 사용한 암호화는 아래와 같다.

CBC를 사용한 복호화는 아래와 같다.

첫 번째 block을 만들기 위한 암호문 block이 없기 때문에 초기화 백터(IV, Initialization Vector)라는 것을 처음에만 사용한다.

CBC를 사용한 처음 블록 암호화는 아래와 같다.

CBC를 사용한 처음 블록 복호화는 아래와 같다.

IV값은 비밀이 아니라 공개된 값이다. 송신자가 임의로 만들어 알리면 된다.

ECB 모드를 사용하면 각 block들이 chain 처럼 순차적으로 말려 들어가 동일한 평문이 암호화 되어도 다른 암호문을 만들어낸다.

ECB의 특징으로는 error 복구 능력이 강하다는 것이다.

만일 암호문을 송신자가 수신자에게 보낼 때 블록 하나만 깨지더라도 두 개의 평문 block에만 영향을 준다.

C0, C1, C2 ... CN의 암호 block 중 C1 block이 깨졌다고 가정하면 아래와 같다.

즉 두 번째 이후 block 부터는 깨진 block에 대해 영향을 받지 않기 때문이다.

CBC mode의 예시는 아래와 같다.

CTR (Counter mode)

CTR mode는 IV를 선택해서 IV를 counter 하여 사용하는 것이다.

이전 block이 필요하지 않고 병렬화 가능해서 속도가 빠르고 효율성이 높다.

CTR를 사용한 암호화는 아래와 같다.

CTR를 사용한 복호화는 아래와 같다.

Integrity

Integrity는 무결성으로서 비인가된 사람이 data를 수정하는것을 방지하는 것이다.

block cipher에서 무결성을 확인하기 위해 MAC(Message Authentication Code)를 사용한다.

MAC은 단지 CBC 모드에서 마지막 block을 MAC으로 사용한다.

송신자는 평문과 MAC을 수신자에게 보내고 수신자는 평문을 이용해 MAC을 구해 송신자의 MAC과 수신자의 MAC을 비교해 message가 변경되었는지 확인 할 수 있다.

CBC mode는 각각의 block이 chain처럼 연결 되어있기 때문에 중간에 평문 block이 변경되면 MAC에 영향을 주어 MAC값이 수정된다. 따라서 이를 이용해 integrity를 보장할 수 있다.