От Ильича до Ильича
by sonnet 2006 이글루스 TOP 100 2007 이글루스 TOP 100 2008 이글루스 TOP 100 2009 이글루스 TOP 100 2010 이글루스 TOP 100 2011 이글루스 TOP 100
rss

skin by 이글루스
태그 : 소인수분해
2010/02/26   "provably secure" [35]
"provably secure"
OS별 취약점 통계에 대한 짧은 생각 (헐랭이)

내 생각엔 위 글의 본문이 아주 잘 설명이 되어 있는 것 같은데, 덧글에 다소 순진한 질문이 붙었다. '보안취약점이 없는 clean OS'를 만들 수 없는가? 여기에 대해서도 이미 일반인도 쉽게 이해할 수 있는 수준으로 쉽게 답변이 된 것 같은데 쉽게 납득하지 못하시는 듯 하다.

내 생각에 알만한 사람들에겐 당연한 이야기이지만, 이 분이 잘 납득하지 못하는 것은 "안전하다" 혹은 "취약점이 없다"는 것을 입증할 방법이 마땅치 않다는 점인 것 같다. 그래서 신중하게 작성하고 잘 테스트하면 취약점이 없는 프로그램을 만들 수 있다고 간주하는 것 같은데, 그건 그렇지가 않다. 우리는 누군가가 작성한 프로그램에 취약점이 없다는 것을 입증할 수 없다.

엄격하게 말하면 현재로서는, 그리고 내가 보기에는 아마 앞으로도 영원히.

그런데 이미 이 정도 설명은 제시되었는데도 납득을 못하는 분이 계시는 만큼, 이 글에서는 설명 방법을 바꿔 볼까 한다.

우리가 흔히 생각하는 windows XP나 linux 같은 기존 OS는 아주 거대한 프로그램이기 때문에 여기저기에 취약점이 있을 수 있다. 그러므로 훨씬 더 견고한(robust) 방법론을 취해 보자. 일단 프로그램을 다 만들어 놓고 거기 취약점이 있는지 살피는 것이 아니라. "안전하다" 혹은 "취약점이 없다"란 것이 입증된 모듈만 포함시키는 방식으로 OS를 개발했다고 가정하는 것이다.

그럼 이제 "안전한" 모듈들을 만들어야 되는데, 편의상 문제를 최소한으로 정의하도록 하자. 이 OS는 단 1개의 암호 알고리즘을 구현한 작은 모듈 1개로 이루어져 있으며 그 구현은 완벽하다고 가정한다. 이러면 OS의 안전성=암호 알고리즘의 안전성이 된다.

이렇게까지 문제를 축소해도 여전히 문제가 남는다. 쉽게 말해서 지금껏 알려지지 않은 새로운 암호해독법이 개발되면 암호 알고리즘의 안전성은 파괴될 수 있다. 이는 방어하는 입장에서 보면 지금껏 알려지지 않은(zero-day) 취약점이 새로 발견되는 것과 비슷한 문제를 야기한다. 그런데 코딩 실수 정도는 눈으로 보면서 찾을 수 있다고 쳐도, 아직 개발되지도 않은 암호해독법을 어떻게 미리 예상하고 찾아내 막겠는가? 학문과 기술의 발전 가능성이 계속되는 한 취약점은 숨겨져 있다가 나중에 드러나게 될 가능성이 있는 셈이다.


… 이렇게 뻔한 이야기를 하려고 길게 이야기를 끄는 건 다소 어리석은 듯 하니까, 안전하다는 것을 증명하는 문제에 대해 좀 더 살펴보도록 하자.


공개키암호의 대표 격인 RSA 알고리즘을 예로 들면, 보통 일반인들(여기에는 평범한 프로그래머 대부분이 포함됨)에게 설명할 때 RSA는 커다란 소수 두 개를 곱해 만든 합성수 n을 인수분해하는 게 어렵다는 수학문제에 입각한 알고리즘이라고 말한다. 인수분해야 중학교 때 배우는 것이니까 RSA에 대해 몰라도 대충 어렵겠거니 하는 느낌은 전해지길 기대하고 하는 말이다.

그런데 좀 더 깊게 들어가서 말하면, RSA 암호를 해독하는 어려움이 합성수 n을 소인수분해하는 것과 동등하다(equivalent)는 것을 보여주는 수학적 증명은 없다. 그건 다만 RSA를 만든 세 사람이 제시한 특정한 방법을 따라 암호문을 평문으로 바꿀 때 그럴 뿐이다. 그런데 그 '특정한 방법'이 유일하거나 최선의 방법인지는 아직까지 알려진 바 없다. 혹시 큰 합성수 n을 소인수분해하는 것보다 쉬운 방법으로 이 문제를 우회하는 해법이 있을지도 모른다. 다만 지난 30여 년간 그런 방법이 발견되지 않았고, 많은 관련자들이 RSA 암호를 해독하는 어려움이 합성수 n을 인수분해하는 것과 같지 않을까하고 막연하게 추측하고 있을 뿐이다.

그래서 그 이후의 다른 연구자들은 새 알고리즘을 만들 일이 있으면, 가능하면 처음부터 앞서 거론된 합성수 n의 소인수분해처럼 계산이 어렵다고 잘 알려진 어떤 문제와 equivalent하다는 것을 직접적으로 보여줄 수 있는 방식으로 설계하려고 시도하게 되었다.

이런 접근법을 처음 시도한 사람이 Michael O. Rabin이다.

M.O. Rabin, “Digitalized Signatures and Public-Key Functions as Intractable as Factorization,” MIT, 1979.

두 암호는 모두 동일한 소인수분해 문제에 기반한 것인데, RSA는 최대 큰 합성수 n을 소인수분해하는 것만큼 해독하기 어렵고, Rabin은 큰 합성수 n을 소인수분해하는 것과 같은 만큼 해독하기 어려운 만큼, 다른 조건이 동일하다면 Rabin이 아마도 더 강한 암호라고 말할 수 있을 것이다.

그러나 위 설명이 여전히 깨지지 않았음에도 불구하고, 실제로는 30여 년이 지난 오늘날에도 Rabin 대신 RSA가 널리 사용된다. Rabin은 다른 공격법(chosen ciphertext)에 취약하다는 것이 금방 밝혀져 실용화되지 못한 반면, RSA는 그렇지 않았기 때문이다. 이는 어떤 수학적 방법으로 안전도 증명을 제공한다 하더라도 그 증명이 보장하는 범위는 매우 좁음을 잘 보여준다.

게다가 정공법, 즉 기반이 되는 어려운 문제(이 경우 소인수분해)를 획기적으로 빨리 풀 수 있는 방법이 발견되면 이런 증명이 몇 개가 있다 한들 소용이 없다. 한 방에 모두 무너지는 것이다. 예를 들어 "어떤 조건을 만족하는 양자컴퓨터가 있다면" 소인수분해를 P-time(polynomial)에 풀 수 있다는 것을 보여준 연구는 이미 있다.

이보다 현저하게 더 질이 떨어지는 것으로는 확률적 검증이 있다. 암호는 기본적으로 쉬운 해독을 막기 위해 엄청나게 긴 자리수를 가진 숫자들을 사용하고 있기 때문에 확률적 검증이 무의미한 경우가 많다. 알 만한 사람들은 확률적 검증을 너무 강조하는 암호는 야바위꾼이 만들었을 가능성이 높으니 조심하라는 경고를 할 정도이다.

고로 어떤 안전성에 대한 (formal한) 증명은 1)만들기는 까다로운 반면, 2)있다면 까다로운 전제 때문에 보장되는 범위가 매우 좁으며, 3)제작자의 지적 능력을 엿보는데는 좋을지 몰라도 실질적으로 별로 믿을 것이 못 된다는 문제를 갖고 있으며, 여기서 벗어나는 경우란 거의 없다.

여기서는 암호 알고리즘의 예를 들었지만 다른 것들, 예를 들어 특정한 통신 프로토콜이 안전하냐의 문제도 잘 생각해보면 입증하기 쉽지 않은 문제라는 것을 금방 깨달을 수 있을 것이다.



附記: formal verification에 대해서는 hama, 암호학에 관해서는 암호암호 두 분이 좋은 코멘트를 주셨으니 관심있는 분들은 읽어주시기를 바란다. 본문을 고칠까도 생각해 보았는데, 왜 저런 코멘트가 나왔는지를 이해하는데 오히려 방해를 주는 것 같아서 놔두기로 한다. 지적 대부분은 받아들이며, 개인적으로는 서툰 글을 썼다고 다소 후회하고 있다.
by sonnet | 2010/02/26 17:27 | 과학기술 | 트랙백 | 덧글(35)
<< 이전 다음 >>