내가 이해한 Dual_EC_DRBG 백도어

본 블로그에서 이미 언급한 바 있지만 Dual_EC_DRBG가 뭔지 좀 찾아봤다. 여기에 대충 설명해보겠다. 일전에 Dual_EC_DRBG 백도어의 작동원리에서 소개한 포스트와 위키피디아, 그리고 여러가지 암호학 관련 서적을 약간씩 참조하였다. 그러나 본인은 이를 전공하지 않았으므로 이 포스트에는 오류가 있을 수 있다.

 


Diffie–Hellman 키 교환이나 RSA 암호와 같은 것들의 과정은 익히 들어 알고 있을 터이라 생각한다. 고전 암호의 경우 해독 정보를 보내고 받는 양쪽이 공유하고 있어야 하는데, 이를 전달하는 과정에서 필연적으로 보안에 취약해진다. Diffie–Hellman의 경우 이러한 정보교환 없이 공통 키를 가지게 되는 장점이 있다. 마찬가지로 RSA의 경우도, private key 없이 public key 만으로 보내는 쪽에서 암호화해서 전송가능하다는 장점이 있다.

Diffie–Hellman의 경우는 Discrete logarithm을 계산하기 어렵다는 성질을 이용하고 있고, RSA는 소인수 분해가 어렵다는 것을 이용하고 있다.

여하간 어느 쪽이든 암호화 과정 중간에 숫자를 잘 고르는 부분이 들어 있는데, 여기서 무작위적인 수를 생성할 필요가 있다. 이 값이 예측당하면 알고리즘이 취약해지므로, 예측하기 어려운 random number를 만들 필요가 있다.

근데 컴퓨터라는 물건이 입력값이 정해지면 출력값도 결정이 되는 물건이라 random number를 만들기 매우 어렵다는 문제가 있다. 하드웨어적으로 random number를 만드는 수도 있지만, 보통은 pseudo-random number generator(PRNG)를 이용한다. deterministic random bit generator(DRBG)와 같은 말이다. 이것은 주기가 있는 수열이므로 random은 아니지만, 주기를 매우 길게 만들면 대충-_- random으로 간주할 만하다. 이렇게 어느정도 안전한 가짜 랜덤 생성기를 Cryptographically secure pseudorandom number generator(CSPRNG)이라 한다.

그래서 컴퓨터에 쓰이는 random number가 진짜 랜덤이 아니기 때문에 이를 공격하는 기법도 있는 모양이다. 위키피디아에 따르면 넷스케이프 초기 버전은 허술하게도 당일 날짜, 프로세스 ID, 부모 프로세스 ID를 random number로 쓴 모양이라 예측이 꽤나 쉬웠던 모양이다. ㅋ

여하간 그래서 나온게 타원곡선(EC)을 활용하는 랜덤 생성 기법이다. 애석하게도 타원 곡선에 ‘타원’은 한 개도 안 나오는데-_- 타원의 곡선 길이를 계산하다가 나온 게 타원 적분이고, 그 타원 적분식과 관련된 곡선이라 이런 말도 안 되는 이름이 붙었다. ㅋ

여하간 곡선 y^2 = x^3 +ax +b 위의 점집합에 대해, 한 직선위에 있는 세 점(with multiplicity)들의 합이 영이라는 연산을 아래 그림과 같이 주고 identity를 만들기 위해 point at infinity를 하나 추가하면, abelian이 된다.(why? ㅋㅋㅋ)
500px-ECClines.svg
물론 실수나 유리수 전체를 컴퓨터에서 다루기는 불편하므로, 점들의 coordinate에 실수 대신 finite field를 쓴다. 근데 이 때는 유클리드 기하학적 직선을 그을 수 없기 때문에, 실수에서 한 직선위의 점을 찾는 대수적 계산과정을 그대로 카피해 온다. 물론 컴퓨터는 계산을 해야 하니까 finite field는 \mathbb{Z}/p\mathbb{Z} 를 쓰는 것 같다.

자연수 n과 elliptic curve위의 한 점 P에 대해, P를 반복적으로 더하는 것을 nP로 표현하면, abelian은 자연수와의 scalar multiplication도 정의가능하다. 그러면 여기서 elliptic curve discrete logarithm problem이 등장한다. 즉, 두 점 P, Q가 주어져 있을 때 Q = nP가 성립하는 자연수 n 을 찾는 문제이다. 아직 이 문제를 효율적으로 푸는 방법이 알려져 있지 않다고 한다.

여하간 미국 국립표준기술 연구소(NIST)에서는 이를 위해 기술 표준을 정할 필요가 있으므로, 알고리즘에 사용할 특정한 타원곡선을 지정해줄 필요가 있다. NIST SP 800-90A라는 문서에 그 알고리즘을 설명하고 있다. 이 문서는 공개 문서로 여기에 pdf포맷으로 열람 가능하다. NIST는 곡선 세 개를 선택했는데, NIST-p256, NIST-p384, NIST-p521라 부르는 듯.

곡선이 정의되려면 먼저 coordinate를 이루는 field \mathbb{Z}/p\mathbb{Z}에서 소수 p가 필요하고, 삼차식의 두 계수 a, b가 필요하고, 마지막으로 계산을 출발하는 곡선위의 두 점 P(x, y), Q(x, y)가 필요하다. 다음 곡선 정보는 NIST SP 800-90A의 appendix A에서 볼 수 있다.

곡선 p-256 (괄호안은 hexadecimal)
p = 2256 − 2224 + 2192 + 296 − 1
= 115792089210356248762697446949407573530/
086143415290314195533631308867097853951
(ffffffff 00000001 00000000 00000000 00000000 ffffffff ffffffff ffffffff)
a = -3
b = 4105836372515214212932612978004726840/
9114441015993725554835256314039467401291
(5ac635d8 aa3a93e7 b3ebbd55 769886bc 651d06b0 cc53b0f6 3bce3c3e 27d2604b)
Px = 4843956129390645175905258525279791420/
2762949526041747995844080717082404635286
(6b17d1f2 e12c4247 f8bce6e5 63a440f2 77037d81 2deb33a0 f4a13945 d898c296)
Py = 3613425095674979579858512791958788195/
6611106672985015071877198253568414405109
(4fe342e2 fe1a7f9b 8ee7eb4a 7c0f9e16 2bce3357 6b315ece cbb64068 37bf51f5)
Qx = c97445f4 5cdef9f0 d3e05e1e 585fc297 235b82b5 be8ff3ef
ca67c598 52018192
Qy = b28ef557 ba31dfcb dd21ac46 e2a91e3c 304f44cb 87058ada
2cb81515 1e610046
나머지 두 곡선은 생략-_- p-256과 유사한 특성을 지니고 있다고 한다.

NIST가 제시한 알고리즘은 다음과 같다. 먼저 처음 random seed 역할을 하는 자연수 s_0를 주면 주어진 점 P와 스칼라 곱을 한 후, 그 x 좌표에서 16개 비트를 버린다. 이 값이 다음 random seed 역할을 하게 된다. 즉, 다음과 같은 점화식으로 수열을 얻는다.

s_i = \varphi ( x ( s_{i-1} P)),\; (i \ge 1)

함수 x()는 x 좌표만 따내는 projection이고, 함수 \varphi 는 16개의 비트를 truncate하는 함수이다. 그리고 실제로 사용하는 랜덤 값 r_n은 이 수열에서 추가적으로 옆으로 빠져 나와서 얻는다.

r_i = \varphi ( x ( s_i Q)),\; (i \ge 1)

자 그러면 백도어를 어떻게 심어놓을까?

먼저 위 결과물들은 모두 어떤 점들의 x 좌표의 일부라는 사실을 관찰해보자. 곡선위의 모든 점은 알려져 있으므로 bruteforce 공격을 통해 잃어버린 16개의 비트를 복원할 수 있다. x 좌표를 가지고 y 좌표도 계산해서 복원한다. (사실 이차방정식이라 y좌표가 두 개 나오므로 이 모든 과정을 두 번 시험해봐야 한다) 그리하여 첫번째 결과물 r_1로 부터 점 s_1 Q 를 복원할 수 있다. 여기까지는 문제없다.

그런데 만약 최초에 주어진 두 점 P, Q 사이에 교묘한 관계(!)가 있다는 것을 숨기고 있다고 하자. 즉, 백도어 역할을 하는 자연수 d가 존재해서 P = dQ 가 존재한다는 사실을 누군가 알고 있다. 그러면 다음과 같이 이 값에 d를 곱하여 s_1 P를 복원할 수 있다.

\displaystyle d(s_1 Q) = s_1 (dQ) = s_1 P

그러면 점화식 때문에 연쇄적으로 s_n P를 전부 복원할 수 있다.

게다가 이러한 백도어가 있는지의 여부를 찾는 것 자체가 elliptic curve discrete logarithm problem을 푸는 일이기 때문에 쉽지 않다. 그러나 실제로 이러한 d 값을 NSA에서 알고 있는지의 여부는 불분명하다.

여하간 일전에도 이야기 했지만, 이쪽 분야에서 NIST의 영향력이 상당히 커서 이 친구들이 표준으로 결정하면 대부분 따라간다고 한다. 그러나 사태가 이 지경이 된 만큼 세상이 좀 달라질 듯 하다. ㅋ

 


2014.4.20

본인이 위에서 한 설명과 거의 동일한 내용이다.

 


2014.4.23
해커뉴스를 보니 이런 놀라운 사실이!
NIST Removes Cryptography Algorithm from Random Number Generator Recommendations in NIST

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중