[컴퓨터보안]Key management & Other PKC

용어

tampering - 변조

forgery - 위조

private key == secret key 비밀 키

distribution - 배포

nonce - 인증 등을 목적으로 일시적으로 사용하는 값

discrete logarithms - 이산 로그(이산대수)

Key management

공개키 암호 방식은 키 분배 문제를 해결해준다.

2종류로 나눠보면 아래와 같다.

 1. 공개키 분배

 2. 공개키 암호를 이용한 비밀키 분배 

공개키 분배

---

공개키 분배는 4가지 사용측면으로 고려된다.

public announcement(게시판 같은곳에 공개 키 올림)

publicly available directory(공적으로 이용가능한 디렉토리에 올리는 방법)

public-key authority(권위가 있는 기관(믿을만한) 에서 관리)

public-key certificates(공개 키에 대한 인증서==공인인증서)

Public Announcement

주된 약점은 위조가 가능하다는 것이다.

아무나 위조가 가능하기 때문에 누군가 A에게 보내려고 한 메시지를 중간에 다른 사람이 위조를 통해 가로챌 수 있다는 문제점이 발생한다.

Publicly Available Directory

신뢰성 있는 속성을 가진 공개 디렉토리에 공개키를 등록하는 방법이다.

디렉토리는 {name,public-key}  같은 속성들을 포함하고 있다.

하지만 여전히 변조와 위조에 취약하다.

Public-Key Authority

보안성을 증가시키기 위해 디렉토리에서 공개 키 배포에 대한 통제를 한다.--> 기능이 추가된 디렉토리라서 기관으로 취급

사용자는 디렉토리의 공개 키를 알아야하며 디렉토리와 실시간으로 상호작용 할 수 있어야한다.

아래와 예시와 같이 7개의 메시지가 필요하다.

(1) A는 기관에 B의 공개키 요구함(with Time stamp)

(2) PRauth (기관의 개인키) 로 암호화해서 A로 전송. A는 기관의 공개키로 복호화해서 해당 정보 얻음 

(3)얻은 B의  공개키 PUb로 B에게 보내는 정보 암호화

(4,5) 기관으로부터 A의 공개키 PUa를 얻음

(6) 얻은 A의 공개키 PUa로 암호화해서 보냄(N1은 B만이 PRb로 풀 수 있었기 때문에, N1을 A로 다시 보냄으로서 A의 통신대상자가 B임을 확인시켜줌)

(7) B가 보낸 nonce 값 N2를 A가 자신의 비밀키 PRa로 풀어서 이를 PUb로 암호화해서 B로 보냄. B의 통신 상대자가 A임을 확인시켜줌

*취약점 :  1. 기관에 bottleneck 현상(병목현상) 이 발생할 수 있다는 약점이 있다.(실시간 상호작용 때문?)

2. 기관이 관리하는 이름과 공개 키의 디렉토리는 여전히 tempering에 취약하다.

Public-Key Certificates

우리가 잘 알고 자주 사용하는 공인인증서가 이 예시이다.

Public-Key Authority 방식은 bottleneck 현상(병목현상) 이 발생할 수 있다는 약점이 있다.

또한, 기관이 관리하는 {이름, 공개키}의 디렉토리는 여전히 tempering에 취약하다.

인증서 방식을 사용하면 기관에 대한 실시간 접근 없이도 키 교환이 가능하게 된다. 또한 기관은 인증서에 공개키와 함께 ID를 바인딩한다.

각 가입자 A,B는 인증기관에 자신의 공개키를 제공하면서 인증서(C_A,C_B) 발급 요청 

A는 다른 가입자에게 인증서 제공 ->해당 가입자는 기관의 공개키 PU_auth로 복호 가능 -> Time, ID_A, PU_a 정보 얻음

PKC(공개 키 암호화) 를 이용한 비밀 키 분배

---

공개키가 배포되었거나 액세스 가능해지면 도청, 변조 또는 둘 다를 저지하는 보안 통신이 가능하다.

그러나 통신을 위해 공개키 암호화만을 독점적으로 사용하는 경우는 거의 없다. 그 이유는 공개키 암호 알고리즘이 느리기 때문이다.

따라서, 공개키 암호화는 기존 암호화에 사용되는 비밀 키의 분배(배포)를 제공한다.

Simple Secret Key Distribution

A 는 임시 공개키 쌍인{PUa, PRa} 를 생성한다.

A는 B에게 공개키와 A의 identity 를 보낸다.

B는 세션키 Ks 를 생성한 후 그것을 A에게서 받은 공개 키로 암호화하여 보낸다.(원서에 세션키라 나와있지만 이 용어는 그렇게 중요한 것이 아님.)

A는 세션키를 복호화 한 후 그것을 사용한다.

이 프로토콜은 메시지를 가로 채고 차단 된 메시지를 중계하거나 다른 메시지를 대체 할 수있는 상대방에 대해 안전하지 않다.(Man-in-the-middle Attack 에 취약)

Man-in-the-middle Attack

1. A가 공개 키/비밀 키 쌍인 {PUa, PRa} 를 생성 후 B에게 A의 공개 키와 identity(ID_A) 를 보낸다.

2. 하지만 중간에 E 가 해당 정보를 가로채어 A의 공개 키 대신 E의 공개 키로 바꾸어 B에게 보낸다.

3. B는 자신이 받은 공개 키인 PUe 로 Ks 를 암호화 하여 A에게 보낸다. 

4. 다시 중간에서 E가 해당 정보를 먼저 받아서 복호화 하여 확인하고 그것을 A의 공개 키로 다시 암호화여 A에게 보낸다.

결과적으로 A,B 는 E가 메시지 내용을 도청한다는 것을 모르는 상태로 계속 통신할것이다.

Secret Key Distribution with Confidentiality and Authentication (기밀성과 인증을 고려한 방식)

N1 : A에 의해 생성된 nonce

N2 : B에 의해 생성된 nonce

K_s :  secret key

(1) A는 B에게 N1과 ID_A를 B의 public key 로 암호화 시켜 전송

(2) B는 PR_b(private key_B) 가지고 있으므로 N1을 추출할 수 있고 추출 후 N2와 함께 A에게 다시 보낸다. 이 때 A의 공개키로 암호화 해서 보낸다. 이 때의 N1 은 A의 통신상대가 B 라는 것을 보장하는 것이다.

(3) A는 복호화를 통해 N2를 얻고 다시 B에게 돌려준다. B의 통신상대가 A라는 것을 보장하는 것이다.

(4) A는 PU_b 로 암호화하여 B에게 메시지( M = E(PU_b, E(PR_a, K_s) ) 를 보낸다.(기밀성 보장)  .PR_a 는 해당 메시지를 A가 보냈다는 것을 인증하기 위한 목적으로 사용.

(4) 이후 B는 K_s 를 얻기 위해 D(PU_a, D(PR_b, M)) 을 계산하게 된다.

(2)(3) 을 통해 상호인증 한 것이다.

Diffie-Hellman Key Exchange(디피-헬만 키교환 알고리즘)

 discrete logarithms 기반의 키 교환 알고리즘이다.

(discrete logarithms이란 예를 들어,  y_A = a^x_A mod q 가 있다하면 a, x_A , q 를 이용해서 y_A 를 구하는 것은 쉽지만 a, y_A, q 를 이용해서 x_A 를 구하는 것은 어렵다는 것이다.)

1.임의의 소수 q와 mod q 공간의 primitive root가 되는 a를 선택한다, 이 두 숫자는 모두에게 공개되어있다. (a가 q의 primitive root :a를 통해 mod q 공간의 모든 수(1..q-1)를 generation 가능한 수)

2. A라는 사용자가 자신의 비밀 키  x_A 를 생성한다. ( x_A < q)

3. 공개 키(y_A) 를 계산한다. y_A = a^(x_A) mod q

  

K_AB = a^(x_A*x_B) mod q   (K_AB : A, B 가 공유하는 키 )

= y_A ^(x_B) mod q  (which B can compute) ->B 기준에서 A의 공개키를 B의 개인키로 복호화 하여 K_AB 를 얻음.

= y_B ^(x_A) mod q  (which A can compute) ->A 기준에서 B의 공개키를 A의 개인키로 복호화 하여 K_AB 를 얻음.

A 와 B는 서로의 공개키만 주고 받기 때문에 공격자가 중간에서 공개키를 알아낸다해도 비밀키가 없기 때문에 K_AB 값을 구할 수 없다.

A 와 B는 q와 a 값을 항상 알고 있어야 한다.

meet-in-the-middle attack, meet-in-the-middle attack 에 취약하다.

두 용어가 헷갈릴 수 있는데 자세한 설명은 이 곳에 잘 나와있다.

간단한 예제를 통해 알아보자.

q=353 (소수) , a= 3 (3^n mod 353 (n=1..352) 까지 해보면 primitive root 라는 것을 확인 가능)

1. A, B 가 임의의 비밀 키를 선택한다. x_A=97 , x_B=223 이라 하면

2. 각각의 공개 키를  계산한다

 y_A=3^97  mod 353 = 40 (A의 공개 키)

 y_B=3^233 mod 353 = 248 (B의 공개 키)

3. K_AB 값을 계산한다. 

 K_AB= y_B ^x_A mod 353 = 248^97 = 160 (A 기준에서 계산)

 K_AB= y_A ^x_B mod 353 = 40^233 = 160 (B 기준에서 계산)

 

ElGamal Cryptography(엘가말 암호)

DH(Diffie-Hellman) 와 연관된 공개 키 암호 방식이다. discrete logarithms 기반이다.

1. DH  처럼 소수 q , primitive root 인 a 를 선택한다. 

2. A가 비밀키 x_A (1 < x_A < q - 1) 을 선택하고 공개키를 계산한다. y_A = a^x_A mod q  

3. B 가 A에게 보낼 메시지 M 을 선택 한다. (0 <= M <= q - 1)

4. B 가 임의의 수 k 를 선택한다.(1 <= k <= q - 1)

5. B는 A의 공개키를 이용하여 one-time key 인 K 를 만든다. ( K = y_A ^ k mod q = a^(x_A * k) mod q )

6. B는 메시지 M 을 (C_1, C_2) 쌍으로 암호화 하여 A에게 전송한다.

 C_1 = a ^ k mod q ,  C_2 = KM mod q  (C_1 : k 값을 숨기기 위해 사용 )

7. A는 (C_1, C_2) 를 받았고 이것을 복호화 하여 메시지를 얻는다.

  K = C_1 ^ x_A mod q (= a ^( k* x_A) mod q) 

  M = C_2 K^(-1) mod q

특징 : 매 암호화 마다 K 값이 다르기 때문에 같은 메시지 M 이라도 각각 다른 암호문 이 나오기 때문에 안전하다.

간단한 예시

GF(19) 에서 q=19 , a=10 이라 하자.

A 가 비밀키 x_A = 5 로 선택하고 공개키를 계산하면 y_A = 10 ^ 5 mod 19 = 3 이 된다.

B 가 메시지 M = 17 로 선택하고 임의의 수 k = 6 으로 선택한다.

one-time key K 를 계산해보면 K = 3 ^ 6 mod 19 = 7 이고 C_1 = 10 ^ 6 mod 19 = 11, C_2 = 7*17 mod 19 = 5 가 된다.

A 가 (11, 5) 를 받았고 이것을 복호화 한다.

K = 11 ^ 5(이 5는 A의 비밀 키) mod 19 = 7 을 구할 수 있고 K 의 inverse 를 구해보면 7 ^ (-1) mod 19 = 11 이 된다.

메시지 M 을 구해보면 5 * 11 mod 19 = 17 이 나오는 것을 확인 할 수 있다.