[암호공학] 15장. Key Management

Key word : key-distribution center, session key, symmetric-key agreement protocol

 

1. Key management

큰 메시지를 암호화할때는 대칭키 방식이 비대칭키 방식보다 더 효율적이다. 하지만 대칭키 암호화 방식의 경우 shared secret key가 필요한데, 이는 key 분배에 대해 다른 문제를 야기한다.

 

1) Key-Distribution Center : KDC

가장 실용적인 해결법은 trusted third party(여기서는 KDC)를 이용하는 것이다.  key의 개수를 줄이기 위해서, 각각의 사람들이 KDC로부터 shared key를 이용한다.

 Alice는 KDC의 secret key를 가지고있고, (K_alice), Bob도 KDC의 secret key(K_bob)를 가지고... 이런 식이다.

그럼 이제 문제는 어떻게 Alice가 Bob에게 confidential message를 보내는가 하는 것이다.

1. Alice는 KDC에게 Alice와 Bob 사이에 session(temporary) secret key가 필요하다는 요청을 보낸다.

2. KDC는 BOB에게 Alice의 요청에 대해 알린다.

3. 만약 Bob이 agree한다면, session key가 둘 사이에 생성된다.

이렇게 생성된 둘 사이의 secret key는 Alice와 Bob을 KDc에게 authenticate하는데에 이용된다. 

 

2) Flat Multiple KDCs

KDC를 이용하는 사용자가 많아지면 시스템은 관리하기가 힘들어진다. 이 문제를 해결하기 위해 여러개의 KDC를 둔다. 이제 Alice가 confidential message를 bob에게 전송하고자 한다. Alice는 그녀의 KDC와 contact하고, Bob domain의  KDC가 Bob에게 contact한다. 두 KDC는 secret key를 만들어낸다.

 

3) Hierarchical Multiple MDCs

위의 flat multiple KDC 개념은 extended될 수 있는데 그게 위의 예시이다. local KDC, national KDC, International KDC가 존재할 수 있고, national KDC는 international KDC로부터의 연결을 중개한다. 이는 Bob의 domain에 도달할때까지 릴레이된다.

 

2. Session Keys

KDC는 각 멤버에 대한 secret key를 생성한다. 이 secret key는 그 둘 사이에서 이용될 수 없고 오직 KDC의 중개를 통해서만 쓸 수 있다. 만약 Alice가 Bob에게 비밀스럽게 communicate하고 싶다면, 그녀는 그녀와 Bob사이의 secret key를 필요로 할 것이다. 

KDC는 Alice와 Bob 사이에 session key라는걸 만들어 주고, 이 Session symmetric key between two parties는 단 한번 만 이용된다.

 

1) A Simple Protocol Using a KDC

위 그림은 KDC를 이용한 간단한 프로토콜에 대한 설명이다. 어떻게 KDC가 session key K_AB를 생성해서 Alice와 Bob에게 주는지 살펴보자.

1. Alice는 Bob과 그녀 사이에 symmetric session key를 얻기 위해 plaintext message를 KDC에게 전송한다. 이 메시지는 그녀의 registered identity와 Bob의 identity가 담겨있다. 이 message는 암호화되지 않았으며, public하다. KDC는 신경쓰지 않는다.

2. KDC는 메시지를 받고 ticket이라는 것을 생성한다. 이 ticket은 Bob의 key (K_b)를 이용해서 암호화된다. ticket은 Alice와 Bob과 session key K_AB에 대한 identity를 포함한다. 이 ticket과 session key를 복사한것을 Alice에게 전송한다. Alice는 이 message를 받고, 복호화하여, session key를 추출해낸다. 그녀는 bob의 ticket은 복호화할 수 없다. 이 message는 double encrypted되었다는 사실을 기억하라. 오직 Alice만이 whole message를 열어볼 수 있기 때문에 KDC에게 authenticate 되었다.

3. Alice는 Bob에게 ticket을 전송하고 Bob은 ticket을 열어 Alice가 K_AB를 이용해서 그에게 message를 전송하고 싶다는 사실을 알게된다. 이제 Bob이 복호화를 해서 session key를 알아내면 Bob은 KDC에게 authenticate된 셈이다. 그러면 aLice는 Bob에게, Bob은 Alice에게 authenticate된다.

하지만 이 간단한 protocol은 결함이 있다. Eve가 replay attack을 반복할 수 있다. 

eve가 step 3에서 메시지를 save한 뒤 replay할 수 있다는 것이다.

 

2) Needham-Schroeder Protocol 

위 프로토콜은 다섯가지 step으로 동작한다.

1. Alice는 KDC에게 message와 그녀의 nonce(Ra), Alice와 Bob의 identity를 전송한다.

2. KDC는 Alice에게 Alice의 nonce와 Bob의 identity, session key, encrypted tickert for Bob을 전송한다. 이 whole message는 Alice의 key를 통해 암호화된다.

3. Alice는 이를 복호화하고 Bob의 ticket을 전송한다.

4. Bob은 Bob의 challenge(Rb)를 Alice에게 전송한다.

5. Alice는 Bob의 challenge에 반응하여, R_B - 1 을 전송한다.

 

3) Otway-Rees Protocol

세번째 접근법은 Otway-Rees Protocol이다. 다섯가지 step으로 구성된다.

1. Alice는 Bob에게 메시지와 common nonce R, Alice와 Bob의 identity, ticket for KDC including Alice's nonce RA(Challenge for the KDC), common nonce의 복사값 R, identity of Alice and Bob을 전송한다.

2. Bob은 동일한 종류의 ticket을 생성한다. 이번에는 RB를 이용해서 생성하고, 둘 다의 ticket을 KDC에 보낸다.

3. KDC는 R을 포함하는 메시지를 생성하고, message는 bob에게 보내진다. ticket에는 Ra와 Rb, session key KAB가 포함된다.

4. Bob은 Alice에게 Alice의 ticket을 전송한다.

5. Alice는 session key KAB로 암호화된 짧은 메시지를 보내 session key를 가지고 있음을 증명한다.

 

3. Symmetric Key Agreement

Alice와 Bob은 그들 사이에 KDC를 이용해 session key를 생성할 수 있다. 이 방법의 session-key creation을 symmetric-key agreement라 한다.

1) Diffie-Hellman Key Agreement

diffie hellman 프로토콜에서는 두 parties가 symmetric session key를 KDC 없이 생성한다. 이 대칭키를 생성하기 전에 두 parties는 p,g를 설정해야 한다. p는 large prime number on the order of 300 decimal digits(1024 bits)이고, g는 generator of order p-1 in the group<Zp*, X>이다. 이 두개는 confidential 할 필요는 없다. 과정을 살펴보자.

1. Alice는 0<=x<=p-1을 만족하는 random number x를 선택하고 R1 = g^x mod p를 계산한다.

2. Bob은 another large random number y를 선택하는데, y는 0<=y<=p-1이며, R2 = g^y mod p를 계산한다.

3. Alice는 R1을 Bob에게 보낸다. 

4. Bob은 R2를 Alice에게 보낸다.

5. Alice는 K = (R2)^x mod p를 계산한다.

6. Bob은 K = (R1)^y mod p를 계산한다.

그러면, K=(g^x mod p)^y mod p = (g^y mod p)^x mod p = g^xy mod p이므로,

Bob은 K를 K=(R1)^y mod p = (g^x mod p)^y mod p = g^xy mod p로 계산할 것이고,

Alice는 K = (R2)^x mod p = (g^y mod p)^x mod p = g^xy mod p로 계산할 것이다.

둘다 동일한 value를 얻게 된다.

 

예제를 살펴보자. g = 7, p= 23이라 생각한다.

Alice는 x=3을 선택하고, Bob은 y=6을 선택했다고 생각하자.

R1 = 7^3 mod 23 = 21

R2 = 7^6 mod 23 = 4

그럼 Alice는 Bob에게 21을 보내고, Bob은 Alice에게 4를 보낸다.

Alice는 K=4^3 mod 23 = 18을 계산하고,

Bob은 K=21^6 mod 23 = 18을 계산하게 된다.

 

이번엔 좀더 현실적인 예제를 살펴보자. 우리는 random integer of 512 bits를 생성하기 위해 프로그램을 사용하고, integer p는 159-digit number이다. 다음 g,x,y를 설정했다.

위 경우에 각각 R1,R2,K를 계산하면 다음과 같이 된다.

이 프로토콜은 약점이 존재한다.

Eve가 이 protocol을 공격할 때 value x,y를 찾을 필요가 없다. 

Man-in-the-middle Attack이다.

1. Aliced는 x를 선택하고 R1을 계산해서 Bob에게 전송한다.

2. Eve가 시스템에 침입해서 R1을 받고, z를 선택해서 R2 = g^z mod p를 계산해서 R2를 Bob와 Alice에게 전송한다.

3. Bob은 y를 이용해서 R3 = g^y mod p를 계산하고 R3를 Alice에게 전송한다. 이 R3는 Eve에게 intercept되고 Alice에게 도달하지 못한다.

4. Alice와 Eve는 K1 = g^kz mod p를 계산하고, 이는 마치 Alice와 Kve의 shared key처럼 된다. 하지만 Alice는 이 key가 Bob과 그녀간의 shared key라고 착각하게 된다.

5. Eve는 K_z = g^zy mod p를 계산해서 Eve와 Bob간의 shared key로 만들어버린다.하지만 Bob은 이 key가 Alice와의 shared key라고 착각한다.

이 문제를 해결하기 위해 새로운 방식이 고안되었다.

1.R1을 계산하고 난 후 Alice는 R1을 Bob에게 전송한다.(위 그림의 step 1,2)

2.R2와 session key를 계산하고 난 후, Bob은 Alice의 ID와 R1,R2를 concatenate시킨다. 이를 private key를 통해 sign한 후 R2, the signature, his own private-key certificate를 Alice에게 전송한다. signature은 session key로 암호화되어있다.(위 그림의 3,4,5번 과정)

3. Session key를 계산한 후, bob의 signature가 입증되면 Alice는 Bob의 ID와 R1,R2를 concatenate시킨다. 이를 Alice의 private key로 sign하고 bob에게 보낸다. 이 signature은 session key로 암호화되었다. (위 그림의 6,7,8)

4. 만약 Alice의 signature이 입증되면 Bob은 session key를 유지한다.