[알고리즘] 보안 알고리즘 3

디피-헬먼 키 교환법 (Diffie-Hellman protocol)

디피-헬먼 키 교환법은 키를 안전하게 교환하는 기법입니다. 두 사람이 공유할 비밀의 수를 공개된 숫자와의 연산에 섞어 넣음으로써 두 사람 사이의 대칭키를 안전하게 교환합니다. HTTPS에서도 이 DH 키를 통해서 데이터를 암호화 복호화하여 주고 받습니다.

DH 키 교환법의 개념

A와 B가 키를 교환하려는 상황에서 제 3자 X에게 키가 노출되지 않도록 교환하려고 합니다. 이때 A와 B는 두 키를 합성하는 특별한 방법을 사용하려고 합니다. P라는 키와 S라는 키를 합성하면 P와 S를 성분으로 하는 새로운 P-S키가 만들어집니다. 이 합성 방법에는 세 가지 특징이 있습니다.

DH 키의 특징

1. P와 P-S키가 있더라도 S를 추출하는 것이 불가능
2. 합성된 키도 새로운 키의 합성 요소로 사용이 가능
   P와 P-S를 합성 시 P-P-S 키가 생성
3. 키의 합성 결과는 순서와 상관 없이 키의 성분에 따름
   A-B-C 와 B-C-A 키는 동일한 키

DH 키 교환 방식

이제 합성 과정을 살펴보겠습니다.

1. X에게 알려져도 상관 없는 공개키 P를 공유합니다.
2. A와 B는 서로 비밀키 SA와 SB를 준비하여 공개키와 합성합니다.
3. A의 합성키 P-SA와 B의 합성키 P-SB을 서로 주고 받습니다.
   이때 DH키의 특징에 따라 X에게 합성키가 노출되어도 SA, SB를 추출할 수 없습니다.
4. 주고 받은 합성키를 각각 비밀키로 다시 합성합니다. (A: P-SB-SA, B: P-SA-SB)
5. DH키의 특징에 따라 키의 합성 결과는 순서와 상관 없기 때문에 P-SB-SA = P-SA-SB 입니다.
6. X는 SA, SB를 추출할 수 없기 때문에 P-SA-SB 를 만들 수 없습니다.
   X가 알 수 있는 키는 P, P-SA, P-SB 뿐이고 조합했을 때 P-SA-SB는 나오지 않습니다.

출처: 그림으로 이해하는 알고리즘

결국 DH 키 교환법의 핵심은 아래와 같습니다.

• 키의 합성 결과는 순서와 상관이 없기 때문에 공개키와 자신의 비밀키를 합성하여 A, B가 동일한 키를 생성
• 합성된 키에서 성분을 추출할 수 없기 때문에 제 3자가 키 합성의 결과인 대칭키를 생성이 불가

DH 키 교환 수식

실제로 DH 키 교환법은 소수 P, 생성자 G, 비밀값 X가 있을 때 G^X mod P에서 X를 구하는 문제인 이산대수 문제를 사용합니다. 이산대수 문제는 아직 효율적인 해법이 발견되지 않은 난제이기 때문입니다. 위에서 알아본 키 교환 방식을 실제로는 어떻게 사용하는지 수식으로 알아보겠습니다.

1. 공개키 P, G를 공유합니다. 이때 P는 아주 큰 소수이고 G는 P의 생성자(원시근) 중 하나입니다.
2. A와 B는 각각 P-2 보다 작은 비밀키를 준비합니다. X와 Y라고 하겠습니다.
3. A와 B는 각각 G^X mod P와 G^Y mod P를 계산합니다.
   mod 연산은 개념상 합성에 해당합니다.
4. A, B는 서로의 계산값(합성키)를 주고 받습니다.
5. 서로 주고 받은 숫자를 자신의 비밀값으로 제곱한 값에 mod P를 계산합니다.
   A: (G^Y mod P)^X mod P = G^XY mod P, B: (G^X mod P)^Y mod P = G^YX mod P
6. 결국 mod 연산과 지수의 특징으로 A와 B는 동일한 계산값 G^XY mod P를 얻습니다.

실제 사용 시

굳이 수식으로 원리까지 알아야하는 이유는, 어플리케이션 서버나 OpenSSL 버전에 따라 소수 P값에 대한 지원범위가 달라서 에러가 발생할 수 있기 때문입니다. 원리를 알고나면 에러가 발생했을 때 원인 파악을 더 쉽게 할 수 있을 것 입니다.

메시지 인증 코드

메시지 인증 코드는 인증과 변조 검출이라는 두 가지 기능을 제공합니다. 암호문이라도 중간에 내용이 변조되어 다른 내용으로 복호화될 수 있는데 이를 막아 주는 것이 메시지 인증 코드 (MAC; Message Authentication Code)입니다. MAC은 키와 암호문을 조합한 문자열의 해시값이라고 생각하면 됩니다. 의미를 가진 메시지는 변조를 금방 알아챌 수도 있지만 상품 번호 같은 의미 없는 문자는 변조를 알아채기 힘들고 잘못된 상품 번호가 매칭될 수도 있기 때문에 메시지 인증 코드가 필요합니다.

사용 과정

1. A가 MAC을 작성하기 위한 키를 만들어 안전한 방법(디피-헬먼 키 교환법 등)으로 B에게 전달
2. A는 전달할 메시지를 암호화하고, 암호문과 키를 조합하여 MAC을 생성
3. B에게 암호문과 MAC을 함께 전달
4. B도 A처럼 전달받은 암호문을 키와 조합하여 MAC을 생성하고 전달받은 MAC과 일치하는지 비교
5. MAC이 일치한다면 전달받은 암호문이 변조되지 않았다고 판단하고 암호문을 복호화하여 사용

제 3자가 메시지를 변조하게 되면 B가 변조된 데이터로 MAC을 생성했을 때 A에게서 받은 MAC과 일치하지 않기 때문에 변조 여부를 파악할 수 있습니다. 만약 메시지 뿐만 아니라 MAC까지 변조하여 전달하면 알 수 없겠지만, 제 3자는 키를 모르기 때문에 MAC을 변조할 수 없습니다.

결점

메시지 인증 코드는 인증과 변조 검출을 해주기 때문에 완벽한 것 같지만 아직 결점이 남아있습니다. MAC의 사용 과정을 보면 A와 B가 암호문을 이용하여 MAC을 각각 만들고 비교합니다. 결국 작성자와 검증자 모두 해당 값을 만들 수 있기 때문에 사후 부인 문제를 해결할 수 없습니다. 이 문제를 해결하는 방법이 바로 디지털 서명입니다.

[ MAC의 작성 방법 ]

• HMAC: Hash-based MAC (주로 사용)
• OMAC: One-key MAC
• CMAC: Cipher-based MAC