5. Conventional Cryptography Systems

Confusion : 메시지를 완전히 다른 문자로 대체(substituting) 해 암호화 하는 방식

Diffusion : 원래 문자열의 배열만 섞어 암호화 하는 방식

 

 

Unconditionally Secure

공격자에 관계없이 절때로 깰 수 없는 보안이다.

조건

1. key 사이즈는 적어도 message 사이즈 이상이여야 한다. H(M) <= H(K)

2. 키는 한번 사용하고 폐기되야 한다. One-Time Pads(OTP)

 

One-time Pads 의 문제점

매번 원타임 패드에서 완전히 랜덤한 값이 요구된다.

원타임 패드의 안전한 생성과 교환이 요구된다.

이는 숨겨져 있어야 하며 안전하게 폐기되어야 한다.

 

Computationally Secure

유용한 암호화 시스템으로, 제한된 암호화 생명주기를 가진다. 

key 가 한정된 길이에 반복 사용되기 때문이다.

또한, ciphertext 의 강도와 size 에는 tradeoff 가 성립된다.

보안을 위해 size 를 키우면 메모리 사용이 늘어나 비효율적이고,

size 를 줄인다면 메모리 사용은 줄지만 보안이 떨어지게 된다.

-> RSA : 효율적 알고리즘은 아니지만, 한계가 없는 컴퓨터적 능력에 의해 지금도 여전히 사용된다.

 

 

Kerckhoff's Principle

crypto system 은 key 를 제외한 모든 내용이 알려지더라도, 보안상 안전해야 한다.

 

Shannon's Maxim

공격자는 시스템에 대해 알고 있다.

 

 

Security through Obscurity(모호함)

시스템의 내부 작업은 기밀로 유지되어야 한다. (군대, 개인 회사,,)

그러나, 시스템은 짧은 시간 안에는 안전할 수 있지만, 장기적으로는 공개되고 분석된 시스템만 신뢰해야 한다.

 

 

Classifications of Attacks

1. Ciphertext only

공격자가 암호화된 문자열만 가지고 있는 경우, 공격자는 ciphertext로 메시지를 예측해야 한다.

one-way secure : C는 E,K 에 따라 1개로 고정된다.

 

2. Known-Plaintext

1개 이상의 M과 C 쌍을 알고 있다.

공격자는 몇몇 쌍을 통해 key 혹은 다른 Ciphertext 를 찾아야 한다.

 

3. Chosen-Plaintext (안전하지 않음)

공격자는 C에 대하여 임의의 M을 선택하여 비교할 수 있는 상태이다.

즉, C = Enc(M0) 인지 C = Enc(M1) 인지 판단하여 정보를 획득해야 한다. 

 

 

Types of Ciphers

1. Block Cipher

메시지를 고정된 일정 길이의 size 로 나누고, 각 block 을 같은 key 로 암호화 한다.

예) DES 는 56bit 의 key 로 64bit block 을 암호화한다.

 

메시지를 m = b1b2 로 나눴을 때, bi 는 고정된 길이여야 한다.

Block Cipher 은 Ek(m) = Ek(b1)Ek(b2) 로 정의할 수 있다.

 

- 특징

- 메시지와 key 에 대해 Confusion 을 더해야 한다.

- 좋은 Diffusion 특성을 가져야 한다. (Avalanche Effect)

• input plaintext 의 1bit 를 바꾸면 output bits 의 50% 가 변한다.
• key 의 1bit 를 바꾸면 output bits 의 50% 가 변한다.

 

- 사용방법

- 블록은 고정된 길이로 encrypt 되야한다.

- 임의의 길이의 메시지를 encrypt 할 방법

• NIST
• ECB (Electronic Code Book)
• CBC (Cipher Block Chaining)

 

- 준비단계

- Message Padding

• plaintext 메시지는 고정된 크기의 블록으로 나뉜다. P1, P2, P3 ...
• 마지막 블록의 크기가 블록 크기보다 작다면, padding 을 추가해 크기를 맞춘다.

 

Electroninc Code Book Mode

cipher 들이 정해진 key 에 의해 단순한 블록 치환으로 작동된다.

빠르고 단순하지만, 동일 메시지 블록이 들어간 경우 똑같은 Cipher 블록이 생성된다.

즉, replay 공격에 취약하다.

따라서 공격자는 <Cn guessed Mn>과 같이 코드북을 만들 수가 있다.

즉, 이는 짧은 정보 전송에 활용된다. (임시적인 encryption key)

 

Cipher Block Chaining (CBC) Mode

이전 단계에서 결과로 출력된 ciphertext blok 을 이용하는 방식이다.

즉, 최초의 key 를 위한 initialize vector 을 제외하고,

각 plaintext 들은 이전 단계에서 결과로 출력된 암호문 블록과 XOR 을 취하게 된다.

따라서 block 의 encryption 은 현재 블록과 이전단계들의 모든 블록에 영향을 받는다.

따라서, Mi = Mk 인 plaintext 들은 같은 ouput code 를 출력하지 않을 것이다.

 

입력 :

출력 :

 

Stream Ciphers

대칭 키 암호 구조의 하나로, pseudorandom number 을 연속적으로 생성하여 암호화하려는 자료와 결합한다.

1비트 단위로 생성된 공유 비밀키 Key-stream 은 Message-stream 과 XOR 결합되어, Cipher-stream 을 얻을 수 있다.

그러나 한계가 존재한다.

Confusion(치환) 만 가능하다는 것이다.

또한, sender 와 receiver 사이에 손실이 있다. -> resync

따라서 cryptosync 가 lost 되었으면, 다시 동기화 하여 전송한다.

-> Self-synchronous Stream Cipher

 

Key-Stream을 절때 재사용하면 안된다.

만약 M1 이 알려지면, M2 도 당연히 노출되기 때문에 재사용 하면 굉장히 위험하다.

 

 

 

Simple Conventional Systems

Transposition : 위치 변경

행을 섞어서 위치를 변경한다.

Substituion Ciphers : 문자가 one-to-one 으로 다른 문자에 매핑된다.

Cryptanalysis 를 하기 위해선 26! 만큼의 경우의 수를 시도해야 한다.

이는 Letter Frequency 를 통해 알아챌 수 있다. 즉, 빈번하게 사용하는 알파벳과 상대 위치로 추론할 수 있다.

 

Shifted Alphabet : 문자를 몇 칸 shift 한 것이 암호가 된다.

f(x) = (x+k) mod 26

여기서 alphabet 을 k 만큼 shift 하고 alphabet 사이즈 n 만큼 modulo 한다.

 

 - Caesar Cipher

 

 

 

Vigenere Cipher

반복된 Key Word 를 사용하여 encrypt 하는 방식이다.

각 알파벳이 각각 shift 값을 가지고 있으면, 키가 반복되면서 각 key 의 spell 과 매칭되는 알파벳이 shift 하여

결론적으로 plaintext 가 switch 된다.

  - Kasiski Method

  같은 문자열의 반복 사이의 distance 를 알아낼 수 있어 key 의 length 를 알아낼 수 있다.

  

Strict Avalanche Condition

1비트당 암호화된 문자의 변경은 output bits 의 거의 1/2 가 변경되게 된다.

정확히 output bits 의 1/2 만큼의 변하게 된다.

 

 

Product Cipher

각각 치환하거나 다른 곳으로 배치하는 것은 보안성이 강하지 않다.

그러나,  confusion(치환) 과 diffusion(배치) 를 통한 여러 round 를 통해서 반복적으로 암호화 한다면

강한 cipher 을 생성할 수 있다.

 

 

Fiestel Cipher

Fiestel Cipher 의 round 는 다음과 같은 과정으로 진행된다.

1. F를 라운드 함수로 하고 K0, K1, ... , Kn을 각 라운드 0, 1, ..., n의 하위 키로 한다.
2. 평문 블록을 두 개의 동일한 조각으로 분할(L0, R0)
3. 각 라운드의 경우 i = 0, 1, ..., n,
4. Compute Li+1 = Ri, Ri+1 = Li = ⊕ F(Ri,Ki)
5. 암호 텍스트는 (Rn+1, Ln+1)

 

R0L0 이 plaintext 인 메세지가 되며, Rn+1 Ln+1 이 cipher text 가 된다.

그리고, R0~Rn+1 의 라운드 별로 key 가 모두 다르다.

원형 함수 F 는 역함수를 취할 필요가 없다.

즉, 암호화와 암호해독의 유일한 차이는 subkey 순서이다.

 

 

DES

DES 는 데이터 암호화 표준으로, 세계에서 가장 널리 사용되는 블록 암호로 Feistel 암호 구조에 기초한다.

DES 는 높은 수준의 diffusion 과 confusion 을 달성하기 위해 만들어졌다.

 

Block 은 64bit, key 은 56bit 인 구조이다.

 

과정

 

1. Initial, Final permutation

처음 64비트 평문이 들어왔을 때와 마지막 64비트 암호문이 생성되기 직전에 수행되는 Permutation과정이다.

즉, P-box 를 사용한다. 이때 initial P-box 와 final P-box 는 역관계이다.

Initial Permutation(IP) / Final Permutation(IP^-1)

initial permutation

 

2. Feostel (F) Function, 라운드 함수

처음 Initial Permutation 을 진행하고 난 뒤에, 16번의 라운드 함수를 거치게 된다.

 

과정

1) Expansion (E- box)

쪼개진 R bits (32bits) 들을 Expansion E-box 에 넣어서 48 bit 로 만든다.

 

2) XOR

key-straem 을 통해 만들어진 라운드 키(48 bits) 와 XOR 연산을 한다.

 

 

3) Substitution (S-Box)

비선형 치환 테이블을 말하며, 각각의 비트가 맵핑되어, 공간을 줄일 수 있다.

-> 011011 6bit input -> 4bit ouput 이 된다.

0/1101/1 에서 01 이 column, 1101 이 row information 이다.

-> 5 (0101)

-> 따라서 48bit 에서 32bit 로 치환되는 과정이다.

 

 

4) Permutation(P-BOX)

Diffusion 된다.

32 bit 의 block 을 shuffle 하는 과정이다.

 

 

Key permutation (키 생성)

DES 에서는 56bit 의 key 가 필요하고, 매 round 마다 48bit 의 round-key 가 사용된다.

즉, 56bit 를 가지고 48bit round-key 를 16개 만들어야한다. 

과정은 다음과 같다.

 

1) parity drop 을 통해 56bit 로 만든다. (8의 배수 bit 들을 선택하지 않는다)

2) 56bit 를 28bit 씩 반으로 쪼개서 각 라운드별로 shift left 한 다음,

56bit 중 48bit만 선택하는 Compree(압축) 을 진행한다.

 

 

Cryptanalysis of DES

1. 강한 avalanche effect 를 가진다는 장점이 있다.

-> 16th round 후에는 input bits 의 절반이 변하게 된다.

2. error detection 이 가능하다.

-> parity drop 을 한 bit 로 error 탐지가 가능하다.

 

 

 

Triple DES

최근 컴퓨팅의 발전으로 인해 더이상 DES 가 안전하지 않다.

이를 해결하기 위해 DES 를 세번 반복하는 Triple DES 를 사용한다.

 

 

 

AES

DES 는 더 이상 안전하지 않아 triple DES 를 사용하였다.

이에 더 강력한 암소시스템을 만들고자 NIST 에서 Rijndael 알고리즘이 채택되었고, AES 가 탄생하게 되었다.

암호화 key 로 128, 192, 256bit 를 가질 수 있다 

또한, 암호화 key 의 길이에 따라 실행하는 Round 수가 다르다. -> 9/11/13 round 

 

- Rijndael Cipher

각 round 는 세 번의 invertible 을 수행해야 한다. (DES 는 fiestel 구조라서 invertible 을 확인할 필요가 X)

• P : Linear mixing layer - 여러 round 를 거치면서 높은 diffusion
• S : Non-Linear layer - 최악의 경우 비선형 특성을 갖는 S-Box 를 사용하여 높은 confusion
• X : key 를 추가하는 layer - round key 의 XOR

 

- State

AES 에서는 State 단위로 연산되는데, 주로 4x4 2차원 배열을 사용한다.

 

- Round 구조

각 라운드마다 4가지 연산을 수행하며, 3번의 substitution 과 1번의 Permutation 을 이용한다.

1) SubBytes - Substitution

2) ShiftRows - Permutation

3) MixColumns - Substitution

4) AddRoundKey - Substitution

 

- 1) SubBytes

State 상태의 bytes 를 8bit s-box 를 이용하여 바이트 단위로 뒤섞어 주는 것이다. (Confusion)

95 -> 2A로 치환된다.

 

 

- 2) ShiftRows

각 행을 각각 0,1,2,3byte 씩 왼쪽으로 밀어주는 과정이다.

이는 바이트를 열에서 분산시키기 위해서 하는 작업이다.

 

- 3) Mixcolumns

각 열 단위로 연산을 수행한다. 열의 byte 에 새로운 상수를 곱해 새로운 값의 열을 만드는 작업이다.

이때 행렬을 곱해주는 과정을 linear transformation 이라고 한다.

 

 

- 4) AddRoundKey

4x4 의 state 에 키를 각각 XOR 연산 해주는 과정이다.

라운드 과정 중 유일하게 키를 사용한다.

이 과정은 key 확장의 복잡성을 위한 과정이다.

 

 

AES vs DES

AES 가 DES 보다 강한 이유는?

- AES 의 더 긴 암호화 key 및 block size 

- DES 는 균형잡힌 Feistel 구조를 사용하는데 half block 에만 적용된다.

  반면에 AES 는 substitution-permutation 단계를 사용하는데 전체 block 에 적용된다.

 

 

Conventional(Symmetric) Cryptosystem Issues

장점 : 고유 사용자와 data 인증을 제공해주며, 대체로 빠르다.

단점 : key 분배와 관리가 어렵다. Digital signature 을 입증하기 매우 어렵다.

 

Key Management

N 명의 사용자가 대칭키를 사용한다고 가정하자.

각 사용자는 N-1 개의 key 를 다른 사용자들과 공유할 것이다.

그렇다면 총 key 의 개수는 N(N-1) 개가 될 것이다.

각 사용자 쌍이 같은 key 를 가지고 있으므로, N(N-1)/2 => N^2/2 개의 key 가 존재하게 된다.

- Key 분배

각 사용자는 key 를 KDC와 공유한다.

사용자는 공통의 session key 를 요청하기 위해 KDC에게 접근한다.

KDC는 각 쌍에게 session key 를 보내준다.