7. Public Key Cryptography - Diffie Hellman Key Exchange

Diffie-Hellman Key Exchange

Key Exchange 방법

y = x^a mod p, x, p 가 주어졌을 때 a를 구하기 -> 아주 큰 소수 p일 때 매우 어렵다.

 

key exchange 원리

-> 다른 secret color 로 결론은 같은 secret 을 만들게 된다.

 

 

다음은 실제 key exchange 과정이다.

-> 둘다 common secret key 를 가지게 된다. public element 인 g,p 만으로 g^x mod p =12 에서 x또는 y를 알아내는 것이 매우 어렵기 때문에 이 알고리즘이 성립할 수 있다. 

 

 

 

Man-in-the-Middle Attack

Alice 와 Bob은 common element 를 이용해 각각 secret integer x와 y 를 만든다.

또한 x와 y로 각각 common key XA 와 XB 를 생성한다.

 

Trudy는 자신만의 private key TA,TB 와 common element 인 g,p 그리고 alice 와 bob의 XA와 XB를 가지고 있다. 

Trudy 는 가짜 key인 XTA 와  XTB 를 만든다.

이때 XTA = g^TA mod p , XTB = g^TB mod p 로, 자신의 private key 인 TA,TB를 이용한다.

 

Trudy 는 XTA와 XTB 를 Alice 와 Bob 에게 전달한다. 즉, XA와 XB 를 자신이 만든 가짜 key XTA,XTB 로 교체한 것이다.

 

Alice 와 Bob 은 XTA 와 XTB 가 서로에게서 온 것으로 착각할 것이다.

 

따라서 Alice 는 common secret key 인 KA = XTB^x mod p 를 생성하게 된다.

Bob 도 KB = XTB^y mod p 를 생성하게 된다. 

이때 KA 는 KB 와 같지 않다!!!!

왜냐하면 key 가 x,y 로 만들어진 것이 아니라 XTA,XTB 로 만들어졌기 때문이다.

 

한편, Trudy 는 KTA 를 계산할 수 있는데, KTA = (XA)^TB mod p = g^xTB mod p 이다.

마찬가지로 KTB = (XB)^TA mod p = g^xTA mod p 이다.

Trudy는 KTA,KTB 를 이용해서 각각 Alice , Bob 과 통신할 수 있다.

그러나 KA 는 KB 와 같지 않기 때문에 Alice 와 Bob 은 서로 통신할 수 없다.

 

Alice,Bob 은 key 를 확인하기 위해서 각각 ciphertext 를 생성한다.

CA = E(KA,mA) , CB = E(KB,mB)

그러나 이 Ciphertext는 Trudy 에 의해 Decrypt 될 수 있다.

CA 는 KTA 로 decrypt 될 수 있고, CB는 KTB 로 decrypt 된다.

 

Trudy 는 KTB,KTA로 가짜 ciphertext C'A, C'B 또한 만들 수 있다.

 

 

-> 이러한 middle attack 을 막는 방법

- key exchange 이전에 User authentication 하기

- Station-to-Station Protocol 

 

 

 

Basic Authenticated D-H Key Exchange

A와 B는 각자의 private integer x,y 를 가지고 있다.

A는 B에게 자신의 ID A 와 g^x 를 보낸다.

B는 ID B와 g^y, 그리고 서명인 SIGB(g^x,g^y) 를 보낸다.

A는 SIGB(g^x,g^y) 를 decrypt 하여 g^x, g^y 를 얻는다.

g^x 와 g^y 가 맞는지 비교하여 verify 할 수 있다.

또한 A는 SIGA(g^y,g^x) 를 B에게 보내, 마찬가지로 B도 decrypt 하여 verify 를 한다.

-> 이것이 과연 안전할까? 답은 NO

 

Identity-Misbinding (ID-M) Attack

A의 ID 가 A->E 로 변경되서 보내진다.

B는 B,g^y,SIG 를 A에게 보내고, A는 decrypt 한 후 자신의 SIG 도 전송한다.

그러나 이는 E에 의해 SIGE(g^y,g^) 로 변경되어 보내진다.

 

따라서 이는 Wrong identity binding 이 일어나는 공격이다.

A는 B와 share 했고, B는 A와 share 했다고 생각하지만 실은 E와 bind 한 것이다.

B는 E에서 온 것이 A라고 생각한다. 

 

예시)

B= Bank, A,E = customer 라고 가정하자.

A->B 에게 계좌에서 $2000 을 인출한다.

그러나 B는 E의 계좌에서 돈을 인출하게 된다.

 

 

-> Misbinding 을 방지하는 방법

- ISO PROTOCOL

signature 에 상대방의 ID 를 포함해서 보낸다. 

 

위와 같은 상황이 생기더라도, A는 B가 자신이 아닌 E에게 전송하는 것을 알게된다.

 

한편, E는 SIG B(g^x, g^y, B) 를 만들 순 없다. 왜냐하면 SIG 는 B만의 private key 로 만들 수 있기 때문이다.

 

 

ISO Protocol 

대부분 Secure 하지만,

Identity Protection 에는 적합하지 않다.

-> active attacker 에 맞선 protection 이 불가능하다!

복잡하다.

-> 보안적으로 강해지는 것이 아니라, 상대방의 ID를 protocol 에 더할 뿐이다.

 

 

Another Solution: STS(Station-to-Station)