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

skin by 이글루스
"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)
트랙백 주소 : http://sonnet.egloos.com/tb/4346979
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Commented by 로리 at 2010/02/26 17:33
보안이건 소프트웨어는 결국 최고보다는 언제나 최선을 다하는 것이.. 훨씬 좋은 듯 하더군요.
Commented by sonnet at 2010/02/28 15:34
하하. 프로토타이핑을 빨리 하고, 알파와 베타 테스트도 빨리 시작하는 게 영원히 안 나오는 것보다 훨씬 나은 것 같습니다. 최종 제품의 완성도는 완벽을 추구하면 나올 수가 없는 것이니까요.
Commented by uriel at 2010/02/26 17:56
앞으로도 영원히 불가능 한 것은 아닌게 모든 소프트웨어를 formal model (아마 automata면 충분?)로 만들어서 모델링한다면 불가능한것은 아니긴 하죠. 실제로 OS의 security 기준 중에 저게 포함되어 있긴 하고요.

단지 모델링의 경우 주로 deadlock이 있는지 등등이 주요 criteria였는데, 안전한지라는 performance index를 좀 더 세분화 할 필요가 있죠.

물론 가능한것과 현실적인 것은 안드로메다 만큼의 차이가 있긴 하니까요. 이걸 가지고 논문을 쓰면 100년은 써야지 제대로 된 OS가 나올 듯 하네요.
Commented by sonnet at 2010/02/26 18:06
TCSEC에 그런 개념이 있었지만, 사실 아무도 할 생각을 하지 않았고 이젠 잊혀진게 아닌가 싶은데요.
Commented by object at 2010/02/26 18:01
먼저, 저는 보안/암호학에 문외한입니다. Probably secure가 아니라 증명가능한, provably secure가 아닌가요? b/v 차이로 뜻이 완전히 바뀌니깐 헷갈리네요.
http://en.wikipedia.org/wiki/Rabin_cryptosystem
Commented by sonnet at 2010/02/26 18:04
헛, 저의 덜떨어진 실수입니다. 수정해 놓지요.
Commented by 누렁별 at 2010/02/26 20:10
안전성 검증 문제는 소프트웨어만 아니라 자동차도 마찬가지 일텐데요. 불완전한 사람이 과학으로 할 수 있는 일은 "취약점이 없다"가 아니라 "취약점이 있다"만 보일 수 있겠죠.
Commented by Alias at 2010/02/26 20:52
칼 포퍼의 "반증가능성" 이야기와 좀 닮아 있네요...잘 읽었습니다.
Commented by 漁夫 at 2010/02/26 21:04
아무래도 괴델의 '불완전성 정리'를 연상시키는군요 ^^;;
Commented by sonnet at 2010/02/28 15:31
실제로 괴델과 튜링의 연구가 직접적인 관계가 있습니다.
Commented by 유치찬란 at 2010/02/26 21:15
어차피 안정성 자체에 대한 증명이 모호하다면, 그냥 전세계 해커들에게 상금 얼마 선포하고 제일 빨리 깨지는 OS부터 순서내서 안정성 정하는것도 괜찮을지도 모르겠어요.ㅋㅋㅋ 가장 싸고 현실적으로 당장 취약성을 찾을 수 있는 보안 안정성 구별법. 순위 매기기도 편할테고, 돈도적게 먹히고, 취약점도 빨리 찾고, 취약점을 알면 보안법도 빨리 찾고...ㅋㅋㅋㅋㅋㅋㅋ
Commented by sonnet at 2010/02/28 15:32
윗부분에 링크된 글이 순위매기기가 별 의미가 없다는 점을 설명해 주고 있는데, 그걸 제외하면 사실 말씀하신 게 현재 이루어지고 있는 방법과 비슷합니다.
Commented by hama at 2010/02/27 01:30
halting problem을 못 푸는 것은 computability의 근본적인 한계이고, 인수분해, DL 등의 조건을 안 달고 안전성을 증명 못 하는 것은 어려운 문제를 엄밀하게 조건 없이 어렵다고 보이지 못하고 있는 (예를 들어 NP-complete 문제가 P가 아니라는) 현재 전산 이론의 기술적인 (그러나 앞이 잘 안 보이는) 한계입니다만, 이런 글자 그대로 '거대한' 장벽들이 소프트웨어 엔지니어링에 대한 논의에 얼마나 적용 가능한지는 잘 모르겠습니다.

halting problem은 어떤 프로그램이 무한루프를 도는지 '일반적으로는' 알 수 없다라는 것입니다만 여기서 핵심 키워드는 '일반적으로는'이죠. 약한 계산 모델 하에서는, 혹은 특정 프로그램에 대해서는 halting problem도 잘 풀고 사람들도 '종종' 버그들을 눈으로 봐서 잡아내니까요. 아마도 일상적으로 IT 업계에서 프로그래밍에 사용되는 이디옴들이 halting problem을 거론해야 할 정도로 '일반적일' 것 같지는 않습니다.

formal verification이나 proof 같은 방법론들은 연구도 오래 된 얘기인 것으로 알고있습니다. '그럼에도 불구하고 왜 이런 방법들이 현재 소프트웨어들의 버그를 해결 못하고 있는가'에 대한 원인은 뭔가 다른 데에서 찾아야 하지 않을까 싶습니다. 잘은 모르겠습니다만 복잡한 시스템에 대한 formal modeling 자체의 어려움이라든가 (이건 modeling 후의 computability와는 다른 문제죠), 그것도 아니라면 그냥 비용 대 효율의 현실적인 문제라든가, 이쪽 기술의 아직 미성숙 때문이라든가.

말씀드리고 싶은 것은 현재 기술의 미성숙함과 halting problem, P vs NP와 같은 근본적인 장벽은 좀 다른 문제이고, 현재 기술의 미성숙함이 꼭 그런 거대 장벽 때문이라고 단정하기에는 좀 증거가 충분치 않지 않은가 싶을 수도 없다하지 않기 어렵다는 것이죠.
Commented by sonnet at 2010/02/27 13:20
"이런 글자 그대로 '거대한' 장벽들이 소프트웨어 엔지니어링에 대한 논의에 얼마나 적용 가능한지 … 현재 기술의 미성숙함이 꼭 그런 거대 장벽 때문이라고 단정하기에는 좀 증거가 충분치 않지 않은가"

==> 동의합니다. 단칼에 데꿀멍이죠.
Commented by getabeam at 2010/02/27 01:36
더어려운건 A라는 모듈과 B라는 모듈이 각각에 대해서 어떻게는 안전함을 보장한다고 하더라도 A+B로 이루어진 시스템이 안전함을 보장할수는 없습니다.

Commented by sonnet at 2010/02/27 11:24
예. 그건 그냥 편의상 제외했습니다.
Commented by hama at 2010/02/27 02:17
암호 쪽의 reduction proof 이야기는 '보안'이라는 키워드 하에서는 관련이 있긴 합니다만 buffer overflow 같은 종류의 '보안'과 아주 잘 맞아들어가는 주제는 아닌 것 같습니다. 어쨌든,

http://portal.acm.org/citation.cfm?id=1480881.1480894

이런 것도 있더군요. Bellare & Rogaway가 code-based game-hopping technique을 언급하니까 Halevi가 '이거 어떻게 좀 자동화 못 하냐'라고 물었고, 거기에 대한 부분적인 답으로 나온 이야기입니다. 아직은 실제로 쓸 수 있는 도구라고 보기는 어려워 보입니다만 방향 자체는 근사합니다.

이런 것을 보면, 원칙적으로 '증명이 추가된' 프로그래밍을 하지 말라는 법은 없어 보입니다. 예를 들어, 프로그래머 자신은 자기가 짠 프로그램이 이러이러한 이유로 제대로 동작한다는 믿음이 있기 마련이죠 (halting problem과는 다른 상황입니다). 그 '제대로 동작하는 이유'를 논증하되, 논증 자체를 컴퓨터가 처리할 수 있는 formal language로 기술합니다. 보통 언어에서 compile time과 runtime이 있다면, 이 프레임웍에는 proof verification time, compile time, runtime이 있습니다. 각 프로그램의 입출력에 대한 contract 역시 formal하게 기술되고, 언어 자체의 표현력도 실제적인 문제를 다루는 데 충분한 정도의 표현력을 갖습니다. 암호 모듈이 필요하고 reduction proof가 필요합니까? 문제 없습니다. 이 프레임워크는 기반 가정을 추가하고 그로의 reduction을 허용합니다.

이런 프레임워크를 실현하는 것은 실용적으로 쉽지 않겠습니다만, 이론적인 거대 장벽이 있어보이지는 않습니다. '컴파일러'가 실행하는 작업은 증명을 찾는 것이 아니라 검증하는 것에 불과하고, 이는 P vs NP 문제를 건드리지 않죠. 정직한 프로그래머라면 자신의 프로그램이 잘 동작한다고 생각하는 이유가 있어야 하겠고, 그것을 잘 설명할 수 있어야 합니다. 잘 설명하는 것이 좀 지나치다 보면 포말하게 증명할 수도 있어야 하겠죠. :) 따라서 halting problem도 문제되지 않습니다. reduction이 기반하는 가정의 안전성을 논할 수는 있겠습니다만 그건 이 모델과는 별개의 문제입니다.

물론, 이게 현실적, 실제적, 실용적, 경제적으로 말이 되는 이야기인가는 좀 다른 이야기입니다. 하지만 제 논지는, 네, 이것은 이론적 거대 장벽과는 '좀 다른' 이야기라는 것입니다.
Commented by sonnet at 2010/02/27 12:15
"암호 쪽의 reduction proof 이야기는 '보안'이라는 키워드 하에서는 관련이 있긴 합니다만 buffer overflow 같은 종류의 '보안'과 아주 잘 맞아들어가는 주제는 아닌 것 같습니다."
==> 네, 동의합니다. 이 글이 원래 이야기[암묵적으로 상정되는 해킹 관련 문제]와 벗어난 쪽으로 움직였다고 지적하면 변명의 여지가...


"자신의 프로그램이 잘 동작한다고 생각하는 이유가 있어야 하겠고, 그것을 잘 설명할 수 있어야 합니다. 잘 설명하는 것이 좀 지나치다 보면 포말하게 증명할 수도 있어야 하겠죠."

==> 별로 생각해 본 적이 없긴 한데 잠깐 생각하기엔 이건 단순히 증명의 부담을 프로그래머에게 떠넘긴 게 아닌가 싶은 생각이 듭니다.

현재의 프로그래머는 원칙적으로는 증명과 검증을 자기 머리속에서 해야 하지만 실제로는 대충(satisficing) 하고 넘기는 방식으로 일하는데, 말씀하신 방식은 검증은 컴퓨터가 해 주지만, 이제 프로그래머는 작성하려는 모든 프로그램에 대해 "'제대로 동작하는 이유'를 논증하되, 논증 자체를 컴퓨터가 처리할 수 있는 formal language로 기술"하는 작업을 강제로 해야 하기 때문에 일이 훨씬 힘들어질 것 같습니다.


한편 저는 계산량 문제에 대해서는 장기적으로 보면 PCP(probablistic checkable proof) 같은 수법이 다양하게 등장해서 새로운 전기를 열어줄 수 있지 않을까 기대하는 편입니다.
Commented by sonnet at 2010/02/27 14:11
전형적인 계산의뢰 문제를 예로 들어볼까 합니다.

1) 컴퓨팅 파워가 떨어지는 클라이언트(예를 들어 스마트 카드)가 복잡한 암호학적 계산을 스스로 할 수 없어 서버(카드 리더)에게 컴퓨팅 파워를 빌리고자 합니다.
2) 클라이언트는 계산식과 parameter를 그대로 주면 모든 기밀이 노출되니까 풀고자 하는 문제와 parameter를 변형 혹은 다수의 함수로 분해해서 서버에게 맡깁니다.
3) 클라이언트는 서버가 돌려준 계산값들을 (서버에게 알려주지 않은 재조합과 관련된 정보를 이용해) 자신이 풀고자 하는 계산값을 얻습니다.
4) 서버는 클라이언트가 준 자료를 바탕으로 클라이언트의 비밀을 복원해 낼 수 없어야 하며, 서버가 클라이언트에게 chosen parameter들을 돌려주어 공격하는 것에도 안전해야 합니다.

2), 3)항이 가능한 프로그래밍 방법은 많겠지만, 4)가 보장됨을 증명하기는 그보다 어렵습니다. 그런데 4)가 보장되지 않으면 사실 전혀 안전하지 않죠.

제 생각에 이런 상황을 주면 프로그래머들은 그냥 컴퓨터에게는 2), 3)만 requirement라고 말하고, 4)는 생략한 채로 프로그램을 짤 것 같습니다. 아마 거의 모든 프로그래머는 이런 종류의 과제를 증명할 능력이 없을 겁니다. 또한 4)같은 property를 가질 것이라고 예상되는 방법이 떠오르긴 한데, 증명할 수 없는 경우도 흔히 존재하겠지요.
Commented by 암호암호 at 2010/02/27 15:32
4) 에서 클라이언트가 '안전'하라는 것은 불가능한 요구입니다. 서버가 엉터리 값을 넘겨주더라도 클라이언트가 올바른 결과를 도출할 수 있다면 서버따위 필요없겠지요. -_-a

하지만 최소한 클라이언트 측에서 서버가 올바른 값을 넘겨주는지를 검사는 할 수 있어야 합니다. 100%는 아니라도 최소한 높은 확률로 서버의 농간을 파악할 수 있어야 한다는 뜻입니다. 현재의 암호학에서는 일반적인 요구사항이라고 할 수 있습니다.

...암호'학'에서는 그렇지요. 사실 이게 아주 곤란한 문제입니다. 여러 조각으로 나눠서 암호화한 후에 '검사가 가능한' 크기의 연산을 의뢰하고, 결과를 받아서 다시 암호를 풀고, 결과를 검사하고... 이러다 보면 클라이언트 측에서도 상당히 많은 연산을 하게 되는데, 서버와의 통신이 차지하는 bandwidth까지 고려하면 수지를 맞추기가 쉽지 않지요. 아마 지금 실제로 구현하라고 하면 차라리 검사나 증명은 대충 생략할 수 있는 믿을 만한 서버하고만 통신하는 쪽이 효율적일 것 같습니다. -_-;;
Commented by sonnet at 2010/02/27 16:15
암호암호/ 계산능력이 부족한 것이 전제니까 아마 확률적 검사를 이용할 수밖에 없겠지요. 문제가 발견되면 통신을 끊으면 요구사항을 만족하는 것이고. 말씀하신 대로 위탁에 따른 효율성 목표를 맞추면서도 안전성을 담보하려면 너무 크게 쪼개도, 너무 작게 쪼개도, 또한 너무 많은 시간을 들여 검사해도 안 될 겁니다. trade-off가 아주 예민한 그런 경우지요.
Commented by hama at 2010/02/27 03:41
> Rabin은 다른 공격법(chosen ciphertext)에 취약하다는 것이 금방 밝혀져 실용화되지 못한 반면, RSA는 그렇지 않았기 때문이다.

사소한 이야기지만, RSA 역시 Rabin과 별로 다를 것이 없습니다. m^e (mod N)은 homomorphic하고 deterministic하기 때문에 Rabin과 마찬가지로 온갖 문제점들이 있고, 따라서 그 자체로 쓰일 수는 없습니다. RSA-OAEP와 같이 그런 문제를 한 레벨 뭔가 덮어씌워서 해결해야만 하죠. 그런 입장에서는 Rabin cryptosystem과 마찬가지 상황입니다.

그냥 underlying primitive로 RSA가 Rabin보다 더 많이 쓰이는 이유는, chosen ciphertext attack 문제라기보다는 (RSA도 정확히 마찬가지이기 때문에) 그냥 먼저 발견되고 먼저 대중화된 기술이 살아남은 경우라고 보는 것이 더 적절할 것 같습니다.
Commented by sonnet at 2010/02/27 10:44
무슨 말씀인지는 알겠는데, 시점 문제를 좀 부연하고자 합니다.

70년대 후반에서 80년대 전반 사이에 상대의 체제가 취약함을 입증함으로서 어떤 PKC가 더 우수한지를 보여주려는 경쟁이 있었던 것은 잘 아시리라고 생각합니다. 대표적인게 knapsack 계열을 겨냥한 RSA 측의 집요한 공격이었구요. Rabin의 경우에는 chosen plaintext에 대한 증명이 바로 chosen ciphertext에 대한 insecure 증명이 되는 격이어서 문제가 일찍 지적되었고, 또한 가장 일찍 배제된 부류에 속했던 것으로 압니다. (사람들은 이걸 스스로 약점을 증명해서 자살한 사례라고 받아들인 것 같은데, 이런 시각은 Stinson 같은 흔히 쓰는 교과서에서 쉽게 찾아볼 수 있습니다. 딱 잘라서 completely insecure하다고 기술하니까요.)

RSA의 경우는 좀 다른데, PKCS#1이 박살나기 전까지는 사람들이 RSA의 chosen ciphertext 문제에 대해 Rabin과 본질적으로 다를 것이 없다고 생각하진 않았던 것 같습니다. 그 당시 관련 회의에 가면 다들 PKCS#1 이야기로 꽃을 피웠기 때문에, 꽤 여러 사람이 그런 관점을 갖고 있었다고 기억합니다.

정리하면 두 번째 시기(90년대 후반)는 이미 RSA가 강력한 installed base를 가지고 있을 때고, 말씀하신 이유가 적절한 설명이라고 생각합니다. 그러나 첫번째 시기(70년대 말~80년대 전반)는 그런 기득권 문제는 아닌 것 같습니다.
Commented by .... at 2010/02/27 07:48
양자 컴퓨터를 들면서 소인수 분해 쉽다는 건 좀 너무하군요;;

인수분해는 NP문제니까, NP와 P는 다르다라는 것이 증명되면 양자 컴퓨터 수준의 초월적인 오버테크놀로지가 아니면 분명히 어려운 문제라고 할 수 있죠. 적어도 인간 뇌나 일반 컴퓨터에게는 말이죠.
Commented by sonnet at 2010/02/27 12:19
쉽다고 말한 것은 아닌데요. 오해를 만들었다면 죄송합니다.

그리고 한 가지 덧붙이자면 이런 응용을 위해 trapdoor를 넣어가며 변형된 문제를 만들었을 때 원래 출발점이 된 문제처럼 충분한 어려움을 주는지는 불분명한 경우가 많습니다. knapsack과 Merkle-Hellman 의 관계가 좋은 예가 되겠지요.
Commented by 암호암호 at 2010/02/27 14:45
조금 오해의 여지가 있는 것 같습니다. 몇 가지 말씀드리자면

1. 대부분의 공개키 암호계는 안전하다는 것이 수학적으로 증명되어 있습니다.
2. 그런데 수학적으로 안전하다고 증명된 암호계도 꼭 안전하지는 않습니다. -_-a
3. 양자컴퓨터는 강력하지만 만능은 아닙니다.

우선 1번 내용에 대해 말씀드리자면, 현대에 대부분의 암호계는 증명 없이는 인정받지 못합니다. 최소한 공개키 암호계에서는 그렇습니다. 대칭키 암호계 쪽은 사정이 상당히 다르지만 말입니다.

증명 없이도 새로운 공개키 암호계가 인정받을 수 있었던 것은 대체로 20세기에 있었던 일입니다. 90년대까지만 해도 암호학의 여러 개념들이 잘 구현되지 않아서 증명 없이 '안전할 가능성이 높아 보이는' 수준의 체계도 주목을 받을 수 있었지만, 21세기에 암호학은 gap diffie-hellman group 이라는 강력한 도구에 힘입어서 눈부신 발전을 거듭했습니다. 2002년 정도에 나온 논문들도 벌써 고전 취급을 받을 정도입니다. (아직 읽는 사람이 있는 논문들은 그렇습니다.) 이미 공개키 암호계 쪽에 증명이 붙어있는 암호계가 제시되지 않는 분야는 거의 없고, 또 그런 상황에서 아무리 완전히 새로운 분야라고 해도 증명 없는 체계는 인정받기도 어렵습니다.

소인수분해 문제와 RSA 문제에 대해서도 좀 해명이 필요할 것 같습니다. 우선 RSA 문제와 소인수분해 문제는 다릅니다. 그리고 많은 RSA 기반 체계들은 RSA 문제와 동등하다는 것이 수학적으로 증명되어 있습니다. (혹은 '강한' RSA 문제와 같은 다른 문제를 이용해서 증명하기도 합니다.) 즉 그러한 암호계를 '무시할 수 없는 확률로' 깰 수 있다면 RSA 문제도 '무시할 수 없는 확률로' 풀 수 있다는 것이 증명되어 있습니다.

('무시할 수 없는 확률'이라는 표현이 다소 거슬릴 수도 있겠습니다만, 모든 암호계는 0보다는 큰 확률로 깰 수 있습니다. 무작위로 아무 숫자나 선택했을 때, 그 숫자가 우연히도 비밀키와 같을 확률을 생각하면 적어도 0보다는 크지 않겠습니까? '무시할 수 있을 정도로 작은' 크기겠지만 말입니다.)

소인수분해 문제를 풀 수 있다면 RSA 문제도 풀 수 있지만, 그 역은 증명되어 있지 않습니다. 따라서 소인수분해 문제를 풀 수 없다고 해서 RSA 기반 암호계들을 깰 수 없다는 증명이 존재하지 않는다는 말씀은 맞습니다. 하지만 그렇다고 각각의 암호계가 "대충 이 정도면 어렵겠지" 하는 식으로 만들어진다는 듯이 말씀하시는 것은 오해의 소지가 너무 많습니다.

...막상 증명따위 안 붙어 있는 PKCS 계열도 여전히 많이 쓰이고 있기는 합니다만... -_-a

다 그런 건 아니지만 상당수의 새로운 암호계들은 더 탄탄한 수학적 증명도 붙어있고, 실행속도나 크기 면에서도 옛날에 개발된 암호계들보다 못할 게 없는데도 원래의 암호계를 대체하지 못하는 경우가 많습니다. 특별히 문제가 있다기보다, 시스템을 교체하는 건 돈이 들기 때문에 특별히 문제가 생겨서 '굳이 돈을 들일 이유'가 있는 게 아닌 한 계속 사용디는 것 같습니다. 그래도 완전히 새로 만드는 시스템에서는 새로운 암호계도 많이 도입되는 것 같습니다. 결국은 시간 문제겠지요.
Commented by sonnet at 2010/02/27 17:11
상세한 부연 감사합니다.

"각각의 암호계가 "대충 이 정도면 어렵겠지" 하는 식으로 만들어진다는 듯이 말씀하시는 것은 오해의 소지가 너무 많습니다."
==> 다른 것보다 이 글이 진짜 그런 인상을 줍니까? 저는 그게 제일 궁금합니다. 만약 그렇다면 이 글은 오해를 확산시키는 것을 막기 위해 날려버리는 게 좋을지도 모르겠습니다.

실질적으로는 크게 다르지 않은 의견인데 설명하는 방법이 이질적이라는 느낌이 듭니다. 제가 그렇게 느끼니까 반대편에서도 동일하게 느끼시지 않았나 싶은 생각이 들기도 하고. 우선 앞부분 조금만 놓고 제가 왜 그렇게 느끼는지 말씀드리고자 합니다.


"현대에 대부분의 암호계는 증명 없이는 인정받지 못합니다."

이건 이미 많은 것들이 있는 상태에서 새로 발표하려면이라는 해설이 따라야 한다고 봅니다. 후발주자 입장에서 기존의 것보다 무엇이 나은가를 자신있게 주장할 수 없다면 먹히지 않는 건 당연한 것 아니겠습니까?

물론 어떤 권위를 업을 수 있을 때는 전혀 다를 수 있습니다. 예를 들어 과거 학계에서 skipjack을 어떻게 다루었는가를 생각해 보면, 그들이 이번에 아무 설명없이 공개키 시스템을 하나 떡 하니 던져 놔도 아무도 무시하지 못할 거라고 생각합니다. coppersmith가 DC에 대해 알면서도 함구했듯이, 아마 그들은 design criteria에 대해 정확히 말하지 않을 겁니다. 또 DSS 때 그랬듯이 다소의 설명을 해도 그게 다가 아니라고 의심할테니 어차피 말해 주어도 또 큰 의미가 없을지도 모르지만요.

시대구분도 좀 마음에 걸리는 부분입니다. 2차대전 이전의 고전암호들과 대비해 70년대 DES와 DH를 시초로 해서 그 이후는 현대암호학으로 묶는게 보통이잖습니까? 그리고 또 20세기에 만들어진 것 중 현역이고 앞으로도 한참 현역일 가능성이 높은 게 무수하게 있는데, 그걸 20세기와 현대가 대조되는 것처럼 구분하는 게 좀 찜찜합니다.

"다 그런 건 아니지만 상당수의 새로운 암호계들은 더 탄탄한 수학적 증명도 붙어있고, 실행속도나 크기 면에서도 옛날에 개발된 암호계들보다 못할 게 없는데도 원래의 암호계를 대체하지 못하는 경우가 많습니다. 특별히 문제가 있다기보다, 시스템을 교체하는 건 돈이 들기 때문에 특별히 문제가 생겨서 '굳이 돈을 들일 이유'가 있는 게 아닌 한 계속 사용디는 것 같습니다. 그래도 완전히 새로 만드는 시스템에서는 새로운 암호계도 많이 도입되는 것 같습니다. 결국은 시간 문제겠지요."

네, 동의합니다. 기본적으로 말해서 기존 체제들이 물러나야 할 이유가 분명히 있다고 판단될 때 바뀌겠지요. 단순히 새 암호가 좋아서가 아니고 기존 암호를 버려야할 이유가 있을 때 말입니다. 여기까진 같은 생각인데, 저는 그렇기 때문에 "2002년 정도에 나온 논문들도 벌써 고전" 같은 설명은 좀 불편하게 느꼈습니다. 20세기 마지막 30년 동안 만들어지고 현재 대부분의 어플리케이션을 점유하고 있는 것들이 이미 obsolesce되었다는 느낌을 주는 것 같아서요.

하지만 이런 측면을 뒤집어 생각하면, 제가 주로 70년대 말~80년대 초의 상황을 묘사한 것이 마음에 걸리셨는지도 모르겠다는 생각이 듭니다.
Commented by 암호암호 at 2010/02/28 02:42
70~80년대의 상황을 묘사하신 것이었군요. 불편하다거나 하는 종류의 문제가 아니라, 그 때의 상황은 제가 단편적으로밖에 모르기 때문에 뭐라고 말씀드릴 수가 없습니다. (죄송합니다.) 그냥 현재의 상황도 그렇다는 듯한 느낌을 받았기 때문에 조금 장황하게 말씀을 드렸습니다.

제가 sonnet님의 글이 그런 인상을 준다고 말씀드린 부분은

> 그런데 좀 더 깊게 들어가서 말하면, RSA 암호를 해독하는 어려움이 합성수 n을 소인수분해하는 것과 동등하다(equivalent)는 것을 보여주는 수학적 증명은 없다. 그건 다만 RSA를 만든 세 사람이 제시한 특정한 방법을 따라 암호문을 평문으로 바꿀 때 그럴 뿐이다.

로 시작되는 단락 부분입니다. 소인수분해 문제와 동등하다는 것을 보여주는 수학적 증명은 없지만 다른 문제인 RSA 문제와 동등하다는 것을 보여주는 증명은 있기 때문입니다. (RSA 기반 체계들이 RSA 문제와 동등하다고 하면 뭔가 말장난하는 기분이 들지만, 문제의 이름이 그렇게 붙어버렸으니까요. -_-a )

그 부분은 본문에서도 설명하고 계시기는 합니다만, 예제로 드신 사례 때문에 그런 '수학적 증명이 붙은 암호계'를 제대로 만들기가 어려워서 안 쓰고 있다는 듯한 느낌이 들어서 조금 이런저런 말을 붙였습니다. 예전에는 만드는데 실제로 애를 먹었던 것 같지만, 2010년 현재를 기준으로 보면 이미 그런 단계는 지났으니까요.

> 후발주자 입장에서 기존의 것보다 무엇이 나은가를 자신있게 주장할 수 없다면 먹히지 않는 건 당연한 것 아니겠습니까?

그 관련 문제에 대해서는 특별히 이견이 있다기보다 단지 강조점이 좀 다른 것입니다. '기존의 것'에는 현재 많이 사용되고 있는 것들 뿐만 아니라, '실용적으로 많이 사용되는 건 아니지만 이미 발표되어 있는' 것들이 포함되니까요. 저는 최근에 암호학의 발전 속도가 빨라지면서 '많이 사용되는 것들'과 '발표된 것들'의 차이가 다소 벌어진 상태라고 생각하기 때문에, 새로운 암호계에 대해 생각할 때 '기존에 사용되는 것들'은 적절한 비교기준이 되지 않는다고 생각하는 편입니다. 그래서 '발표된 것들' 쪽을 좀 더 강조하려는 것이지요.

20세기와 21세기의 구분은 그냥 제 느낌을 기준으로 한 것이니까 신경쓰지 않으셔도 됩니다. ^_^ 그냥 그 때는 그랬더라, 그런데 요즘은 이렇다는 정도의 이야기일 뿐이었거든요.
Commented by sonnet at 2010/02/28 15:25
예. 말씀 잘 들었습니다. 쉽게 설명한다고 하면서 misleading하게 글을 쓰는 것은 제가 아주 싫어하는 일인데, 이번에 제가 실수를 한 것 같습니다. 보충해 주셔서 감사합니다.

여담이지만 저는 개인적으로 암호학이 이제 성숙기에 접어들어 연구의 평균적인 질이나 양은 풍부해졌지만, 옛날처럼 무주공산에서 혁신적인 무엇이 펑펑 튀어나오던 시대(영웅의 시대라고나 할까요)는 이제 지나간 것이 아닌가 하는 인상을 갖고 있습니다. 그러니까 발전이 예전같이 빠르지는 않다는 것인데, 이런 생각의 차이가 글에 반영되는 것 같습니다.

예를 들어 MD4가 있는데, MD4는 나오마마자 (특별히 보안취약점이 없는 것들까지 포함해) 기존의 모든 알고리즘을 몽땅 폐물로 만들었고, 지금 사용되는 모든 해쉬는 사실상 이것의 아류라고 할 수 있지 않습니까. cryptanalysis에서 DC도 비슷한 위상을 가지고 있고. 하지만 이번에 SHA-3 콘테스트를 보면 다들 독특한 아이디어를 보여주고 있지만, MD4처럼 군계일학같은 차이를 보이는 것은 없다고 생각됩니다.

저는 이 생각이 여전히 옳지 않나 하지만, 제가 최근의 흐름을 제대로 따라가고 있지 못해 잘못된 인상을 갖고 있을 가능성도 있다는 생각을 해보게 되었습니다. 많은 자극이 되었습니다. ;-)
Commented by 암호암호 at 2010/02/27 15:03
다음으로 2번 내용을 말씀드리자면, 암호계의 안전성이 수학적으로 증명되었다고 해도, 그것은 특정한 조건하에서 증명되는 것이므로 그 조건이 무너지면 안전성도 깨질 수 있습니다.

예컨대 RSA 기반 암호계에서는 N = pq 인 N 만 공개되고, N의 소인수인 p와 q 등은 비밀이어야 합니다. 만약 p와 q가 공개된다면 당연히 깨질 수밖에 없습니다. 그런데 만약 외부의 공격자가 암호를 해독하는 연산의 내용을 추적할 수 있다면 p나 q, 혹은 비밀키 등을 알아내거나 최소한 polynomial time 에 추측할 수 있는 단서를 찾아낼 수 있을 것이고, ㄸ라서 '수학적으로 안전하다고 증명된' 암호계를 깨는 것도 가능할 것입니다.

이러한 종류의 공격을 side channel attack 이라고 하는데, 이런 공격 전체에 대해서 대응할 수 있는 방법은 없습니다. 다만 각각의 알려진 공격방식에 대해서 방어수단을 고안할 따름입니다. 이렇게 볼 때 절대적으로 안전하다고 증명할 방법이 없다는 말씀은 맞다고 할 수 있습니다.


다음으로 양자컴퓨터에 대해서 말씀드리자면, 현재 양자컴퓨터로 소인수분해 문제와 이산 로그 문제를 풀 수 있는 알고리즘은 고안되어 있습니다. 정작 양자컴퓨터 자체를 만들 방법은 아직 못 찾고 있는 셈입니다만. -_-a

지금의 기술로 구현할 수 있는 양자컴퓨터는 처리할 수 있는 비트수가 너무 적습니다. 그리고 개인적은 견해로는, 양자컴퓨터 비트수를 올리는 것보다 암호계에서 사용하는 비트수를 올리는 쪽이 더 쉬울 것 같습니다. 그래서 저는 양자컴퓨터가 과연 실용적일지에 대해서 회의적입니다. 하지만 미래의 일은 모르는 것이겠지요.

모든 암호계는 본질적으로 NP 문제일 수밖에 없습니다. 따라서 모든 NP 문제를 polynomial time 에 풀 수 있는 방법이 있다면 암호학 자체가 성립할 수 없습니다. 하지만 양자컴퓨터고 모든 NP 문제를 풀 수 있는 것은 아닙니다. 단지 이산 로그 문제와 소인수분해 문제를 풀 수 있을 뿐입니다.

물론 그것만으로도 대단한 일입니다. 이산 로그 문제와 소인수분해 문제를 풀 수 있으면 현재까지 제시된 대부분의 공개키 암호계들을 깰 수 있습니다. 하지만 역시 양자컴퓨터도 만능은 아닙니다. 양자컴퓨터로 현재 사용되는 비밀키 암호계를 깰 수 있는 알고리즘은 아직 제시되지 않았습니다. DES나 AES 같은 것들은 아직은 안전하다는 것이지요. 그리고 Lattice를 기반으로 하는 암호계를 깨는 방법도 고안되어 있지 않습니다.
Commented by 암호암호 at 2010/02/27 15:21
아, DES는 양자컴퓨터로 깰 방법이 없다는 것이지, 사실은 지금은 안전하지 않습니다. 비트수가 너무 적어서 현재의 컴퓨터로도 '허용 가능한 시간 내에' 깰 수 있기 때문입니다. 하지만 DES를 확장한 구조들은 아직 안전하다고 할 수 있겠지요.

제가 계속 '암호계'라는 표현을 사용했습니다만, 이것은 암호화-복호화 과정만을 의미하는 건 아닙니다. 전자서명 등의 다른 구조도 포함합니다. 그런데 일단은 분야 자체가 이름이 '암호학'이라서 달리 표현할 말이 없군요. -_-a
Commented by .... at 2010/02/27 15:25
전 이방면에 문외한이긴 하지만..NP문제 중 하나가 풀리면 나머지도 다 풀리는 거 아니었나요?
Commented by 암호암호 at 2010/02/27 15:40
..../ 그건 NP-완전 문제입니다. NP-완전 문제는 하나만 풀리면 모든 NP 문제들이 따라서 풀리지만, P=NP가 아닌 이상 모든 NP 문제가 NP 완전 문제인 것은 아닙니다.

그리고 이산 로그 문제나 소인수분해 문제는 NP 완전 문제가 아닌 것 같습니다...아마도요. 적어도 현재까지는 이산 로그 문제나 인수분해 문제가 NP-완전 문제라고 증명되지는 않았습니다. 아니라는 증명도 없지만요.

사실 아니라는 증명이 있기는 어렵습니다. 어떤 NP 문제가 NP-완전 문제가 아니라는 것이 증명된다면, 그건 P=NP 가 아니라는 것을 의미하기 때문입니다. 쉽게 풀릴 만한 문제는 아니지요.
Commented by sonnet at 2010/02/27 18:10
이건 다른 사람들에게 설명할 때 흔히 겪는 문제인데, 잘 아시겠지만 우리가 수학적으로 안전성을 증명했다든가, 혹은 반대로 어떤 암호를 성공적으로 cryptanalysis해서 저널에 실렸다고 할 때, 그 수학적 안전성 증명이 일반인들이 생각하는 난공불락의 어떤 암호를 의미하는 것도 아니고, 반대로 대다수의 cryptanalysis(reduced round)이 오늘부터 그 평문을 읽을 수 있게 되는 것도 아니라는 점을 정확히 전달하기가 어렵습니다. 그건 학계에서 약속된 어떤 기준을 따르는 것인데 그 기준은 국외자들에게 다소 생소한 것이니까요.

말씀하신 예를 따르면 수학적으로 안전성이 증명된 암호이지만 Timing Attack에 깨졌다 이렇게 이야기해야 하는데 납득시키긴 쉽지가 않겠지요.

저는 이런 걸 적당히 설명하려 했던 것인데, 괜히 가능성이 낮은 양자컴퓨팅 같은 걸 끌어들여서 이야기를 오히려 산만하게 만들었다고 좀 후회하고 있습니다.
Commented by DresdenGreen at 2010/02/27 21:29
미국의 한 코메디언이 한 소리가 생각나는군요. "그들은 곧 안에서만 열리는 대단히 안전한 자동차를 만들어낼 것이다."

:         :

:

비공개 덧글

<< 이전 다음 >>