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

skin by 이글루스
태그 : 해쉬
2007/03/20   우리 업계의 원칙 [3]
2006/08/27   중국 연구팀이 SHA-1 해독에 새로운 진전을 이룩(2005년 버전) [9]
우리 업계의 원칙
일 관계로 뭐 좀 읽다가 돈 럼스펠드가 생각나 피식 웃고 만 구절

The standard approach to security evaluation is to look for attacks on a candidate MAC construction. When practical attacks can be found, their effect is certainly conclusive: the construction must be dropped. The difficulty is when attacks are not yet found. Should one adopt the construction? Not clear, because attacks might be found in the future.

The maxim that guided the HMAC construction was that an absence of attacks today does not imply security for the future. A better way must be found to justify the security of a construction before adopting it.

번역

보안성 평가를 위한 표준적인 접근법은 제안된 MAC설계(알고리즘)에 대한 공격을 살펴보는 것이다. 실질적인 공격법을 찾아낼 수 있을 경우, 그 효과는 확실히 결정적이다. 즉 그 제안은 버려야 한다. 진짜 어려운 것은 공격을 아직 찾아내지 못했을 경우다. 우리는 그 제안을 채택해야 하나? 분명치 않다. 왜냐면 공격은 미래에 발견될 수도 있기 때문이다.

(우리가) HMAC설계를 할 때 지침으로 삼은 원칙은 오늘까지 공격법을 찾아내지 못했다는 것이 미래에도 안전하다는 것을 함축하지는 않는다라는 것이다. 그 설계를 적용하기 전에 설계의 안전성을 정당화할 더 나은 방법을 반드시 찾아내야만 한다.


M. Bellare, R. Canetti, H. Krawczyk, Message Authentication using Hash Functions: The HMAC Construction, CryptoBytes, Vol. 2 No.1, Spring 1996

이것은 사실 이쪽 일을 할 때는 너무 당연한 이야기인데, 전에 많이 논의되었듯이 입증의 책임은 제안자에게 있다. 그런데 중요한 것은 내가 아직 모르는(영원히 모를 수도 있는) 미지의 어떤 것에 대한 입증을 어떤 기법으로 하느냐이다.

기술적 분석

MAC은 인기가 없는 분야여서 연구자가 적고, 연구나 공격 모두 성과가 부족하다. (그러면 연구가 적으니 실용화가 안되고 실용화가 안되니 인기가 없고 인기가 없으니 연구가 위축되는 악순환이 시작된다) 그런데 MAC의 사촌 격인 MDC는 그보다는 훨씬 연구가 많이 되는 장르여서 사람들은 둘이 거의 비슷하니까 MDC를 조금 고쳐서 MAC를 만들어 쓰자는 생각을 많이 했다. 그러나 알고리즘이란 원래 미묘한 것이라 아주 사소한 수정 혹은 설계자가 의도하지 않은 방식으로 사용할 경우 보안성이 완전히 망가질 수 있다.

따라서 MDC를 갖고 만든 MAC는 전용 MAC을 새로 만든 것과 마찬가지로 공격기법 분석을 처음부터 새로 해야 되는 문제를 안고 있다. 원래 MDC를 이용해 MAC을 만들자는 발상은 MDC연구의 성과를 그대로 이용하면 좋지 않느냐는 것인데 이러면 그 의미가 사라져 버리게 된다.

위에 인용한 설계자들은 자신들이 (MDC를 두번 겹쳐서) 만든 MAC을 공격하는데 성공하려면 (그 전에) 하부에 사용된 MDC의 보안성을 파괴하는 결과가 될 가능성이 높음을 증명하였다. 따라서 이들의 증명을 깨지 못한다면 MAC이 깨지기 전에 하부의 MDC를 깼다는 사람이 먼저 나오게 될 테고, 따라서 보안성 증명의 모든 책임을 MAC 대신 하부의 MDC로 떠넘길 수 있게 된다.
즉 MAC연구자들은 사실 내 것이 더 안전해 진 것은 아니지만 온갖 잡다한 증명으로부터 해방될 수 있는 것이다.

이들의 페이퍼는 96년에 발표되었으나 10여 년이 흐른 지금도 깨지지 않은 채 잘 버티고 있고, 실용화되어 MAC을 필요로 하는 많은 분야에 이용되고 있다. 이들이 만든 MAC은 하부의 MDC를 아무거나 바꿔 끼울 수 있도록 만들었기 때문에, 언제든지 최신의 가장 강력한 MDC를 갖다 꽂으면 업그레이드가 된다. 따라서 이들의 증명을 깨지 못하는 이상 MAC 자체에 대한 연구는 별 의미가 없어져 버린 셈이다.
결국 이들 덕분에 MAC에 대한 연구는 더더욱 침체로 빠져든 셈이다.

몇 년 전 ISO 일을 할 때 지나가면서 의례적으로 9797(MAC에 대한 국제표준이 ISO/IEC 9797임)은 좀 어떻습니까라고 물으니 해당 문서 follow-up을 맡은 사람이 "9797에 무슨 새로운게 있겠습니까!!"라고 나에게 분노의 표정을 지어 보이던 기억이 아직도 난다. ISO 표준은 매 5년마다 갱신 검토를 한다. 5년이 지나도 할게 wording밖에 없다면 짜증도 나긴 하겠지.


이들은 자신들이 말했듯이 설계의 안전성을 정당화할 더 좋은 방법을 찾아냈다.

그렇다면 WWE(Washington Wres...) 태그팀 챔피언 Unnatural Disasters라면 어떨까?
by sonnet | 2007/03/20 15:53 | 과학기술 | 트랙백 | 핑백(1) | 덧글(3)
중국 연구팀이 SHA-1 해독에 새로운 진전을 이룩(2005년 버전)
아래 글은 2005년 3월 시점에 번역했던 것이라 뉴스로서의 가치는 이미 없지만 참고삼아 올려 둔다. 해당 논문은 결국 CRYPTO'2005에 발표되었으며, 다음 주소에서 받아볼 수 있다.
(그러고보니 벌써 8월 말이니 CRYPTO'2006도 열렸겠군. ToDo List에 Proceeding 획득을 올려야.)

내 해설(2005년 3월 시점)
아래는 중국 연구팀에 의해 미국 정부의 해쉬 함수 표준인 SHA-1이 깨진 사건에 대한 해설이다.

예로부터 미국의 암호해독기관인 NSA가 만든 알고리즘들은 (빅 브라더가 만든) “외계인의 기술”이라는 평을 들어왔고, 학계가 차분공격법(diffential cryptoanalysis; DC)을 발견해내기 수십 년 전부터 NSA가 그 공격법을 알고 있으면서도 (자기들만 이용하기 위해) 함구하고 있었다는 사실이 밝혀지면서 더더욱 그들이 얼마나 앞서가고 있는지에 대한 경쟁의식이 있어 왔다.

미국의 SHA-1이나 유럽의 RIPE-MD160이 모두 MIT의 Rivest가 (즉 민간에서) 만든 MD4에 기초했다는 사실은 해쉬 분야에서는 NSA가 생각보다 많이 앞서있지는 못하다는 점을 시사하지만, 중국팀이 제일 먼저 개가를 올린 것은 놀랍다.
(대조적으로 대칭 암호 알고리즘인 Skipjack은 학계에서 만든 것들과는 구조가 정말 많이 다르고 이들이 독특한 노하우를 갖고 있음을 보여준다.)

아래 첨부파일엔 산동대 팀이 밝힌 내용인데, 사실 이 안에는 어떻게 하는지 구체적인 방법은 없고, 그들이 문제를 푼 답만 덜렁 적혀 있다. 이는 예전에 DC를 발표했던 이스라엘의 shamir와 비슷한 방식이다. 우리는 손쉽게 그들의 답이 맞는지 검산해볼 수 있기 때문에 그들이 기술을 가진 것은 알지만, 그 기술이 뭔지는 현재로서는 모르는 셈이다. 향후에 발표할 것이라고는 하지만 말이다.
이렇게 발표하는 이유는 몇가지가 있을 수 있지만, 아마도 그들의 기술이 아직 발전도상에 있어서 1등의 영예를 놓치지 않으면서도 좀 더 시간을 갖고 정리하여 완성시키고 싶어서가 아닐까 싶다.

SHA-1 깨지다.
필자: Bruce Schneier

SHA-1이 깨졌다. 단축 라운드 버전이 아니다. 간략화된 버전도 아니다. 실물이다.
Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu(주로 중국의 샨동 대학팀)은 조용히 그들의 결과를 기술한 페이퍼를 회람시켰다.

* 완전한 SHA-1을 갖고 2^69 해쉬 오퍼레이션에서 충돌 생성
* SHA-0을 갖고 2^39 오퍼레이션에서 충돌 생성
* 58라운드(로 단축시킨) SHA-1을 갖고 2^33 오퍼레이션에서 충돌 생성

이 공격법은 SHA-0과 SHA-1에 대한 이전의 공격을 발전시킨 것으로, SHA-1을 전수검색법(brute-force attack)보다 빨리 공격한다는 점에서 암호해독에 있어 중대한, 정말 중대한 성취다.

나는 지난 9월에 SHA에 대해 글을 쓰면서 이를 교체할 필요가 있다는 이야기를 한 적이 있다. 새로운 공격의 상세는 별도로 하고, 내가 말한 모든 것이 여전히 유효하다. 나는 그 글을 인용한 후 적절한 곳에 새로운 내용을 덧붙이겠다.

단방향 해쉬 함수는 많은 응용에서 사용되는 암호학적 구성물이다. 단방향 해쉬는 공개키 알고리즘과 결합해 암호화와 전자서명을 위해 사용되며, 무결성 검사나 인증에도 사용된다. 수많은 서로 다른 프로토콜 안에 온갖 종류의 응용이 있다. 암호 알고리즘 이상으로, 단방향 해쉬 함수는 현대 암호학의 핵심 요소이다.

1990년, Ron Rivest는 MD4라는 해쉬 함수를 만들었다. 1992년, 그는 MD4를 개량해 MD5라는 다른 해쉬 함수를 만들었다. 1993년에 美국가안보국(NSA)은 MD5와 매우 유사한 SHA(Secure Hash Function)이라고 불리는 해쉬 함수를 내놓았다. 그런데 1995년에 새로운 취약점이 발견되자 NSA는 SHA에 변화를 주었다. 새 알고리즘은 SHA-1이라고 불리게 되었다. 오래된 응용에 여전히 MD5가 사용되고 있지만, 오늘날 가장 널리 사용되는 해쉬 함수는 SHA-1이다.

단방향 해쉬 함수는 두 가지 속성을 갖고 있다고 가정된다.
첫째, 이들은 단방향이다. 즉 어떤 메시지를 갖고 해쉬값을 쉽게 계산할 수 있지만, 해쉬값을 갖고 원래의 메시지를 다시 만들어내는 것은 불가능하다(‘불가능’이란 합당한 시간 내에 계산할 수 없다는 의미임).
둘째, 이들은 충돌(collision)이 발생하지 않는다. 즉 같은 해쉬값을 만들어내는 두 개의 메시지를 찾아내는 것은 불가능하다.
이 두 가지 속성 뒤에 자리 잡은 암호학적 증명은 미묘한데, 관심 있는 독자는 관련 참고서를 보는 것이 좋을 것이다.

해쉬 함수를 깬다는 것은 위 두 가지 속성 중 어느 하나(혹은 둘 다)가 사실이 아님을 증명하는 것이다

지난달 세 명의 중국 암호학자가 SHA-1가 충돌 없음(Collision Free)이 아님을 증명해 보였다. 이는 그들이 전수검색법(모든 가능한 경우의 수를 대입해 보는 것)보다 빨리 충돌을 찾아내는 알고리즘을 개발했다는 이야기다.

SHA-1은 160bit 길이의 해쉬값을 만들어낸다. 이는 각각의 메시지가 160bit 길이의 숫자로 요약된다는 뜻이다. 주어진 해쉬값에 대해 무한히 많은 메시지가 있을 수 있기 때문에 가능한 충돌도 무한이 많이 존재한다.
그러나 가능한 해쉬의 수가 너무 많기 때문에 실제로 충돌을 찾아낼 확률은 무시할 수 있을 정도(2^80 분의 1)로 작다. 2^80개의 임의의 메시지를 해쉬하면 같은 해쉬값을 내는 한 쌍의 메시지를 찾을 수 있다. 이것이 충돌을 찾아내는 “전수검색법”(brute force attack)인데 이 확률은 전적으로 해쉬값의 길이에 의존한다.
해쉬 함수를 “깬다”라는 것은 그것보다 빨리 충돌을 찾아낼 수 있게 된다는 뜻이며, 중국인들이 해낸 일이 바로 이것이다.

그들은 SHA-1에서 2^69번 만에 충돌을 찾아낼 수 있었는데, 이는 전수검색법보다 2000배쯤 빠른 것이다. 당장은 현재의 기술로 실행 가능한 영역으로 막 진입한 상태이다. 두개의 비교할만한 대량 계산 사례는 그 점을 잘 보여준다.

1999년 일군의 암호학자들이 DES 해독기를 만들었다. 이는 2^56 DES 오퍼레이션을 56시간에 할 수 있었다. 이 기계는 만드는데 25만 달러가 들었으나, 추가로 제작할 경우 5만에서 7만5천 달러면 가능했다. 무어의 법칙을 사용해 이 기계를 외삽해 보면 오늘날 비슷한 기계를 만들면 56시간 안에, 2^60번의 계산을, 그리고 3년 3개월이면 2^69번의 계산을 할 수 있을 것이다. 다른 각도에서 보면 2천5백만 달러에서 3천8백만 달러짜리 기계라면 2^69번의 계산을 똑같은 56시간 안에 할 수 있을 것이다.

소프트웨어 측면에서는 2002년에 인터넷 사이트 distributed.net이 2^64의 키 검색을 해낸 적이 있다. 한 기사는 이것을 이렇게 설명했다. “경쟁기간 중, 약 331,252명의 참여자가 그들의 남는 컴퓨터 계산능력을 키 검색에 기부했다. 1757일(4.81년) 후 일본의 한 참가자가 키를 찾아냈다.” 무어의 법칙은 오늘날 그 계산은 1/4의 시간(이나 컴퓨터)면 할 수 있다고 말해준다. 따라서 오늘날 2^69번의 계산은 8배의 시간이 걸리거나 컴퓨터가 8배로 있으면 할 수 있다.

“이 결과의 심각성은 당신이 누구인가에 달렸다. 당신이 암호학자라면 이것은 대단한 결과다. 혁명적이라고까지는 할 수 없어도, 이 결과는 해당 분야에서 상당한 진보이다. 그 연구자들이 설명한 기술은 다른 응용에도 적용될 수 있을 가능성이 높으며, 결과적으로 더 안전한 시스템을 설계할 수 있게 될 것이다. 이것은 암호학이 발전해 나가는 방식이다. 우리는 다른 알고리즘을 깸으로서 새 알고리즘을 어떻게 설계해야 할지를 배우게 된다.
덧붙이자면 NSA가 내놓은 알고리즘은 일종의 외계인의 기술로 간주되어 왔다. 그것은 우월한 종족이 아무 설명 없이 내놓은 것이었다. NSA의 알고리즘을 성공적으로 암호해석했다는 것은 NSA 사람들이 거기서 얼마나 앞서가고 있는가라는 영원한 의문에 대한 흥미로운 자료를 제공한다.

평범한 인터넷 사용자에게 있어, 이 뉴스는 공황을 일으킬만한 내용은 아니다. 그 누구도 가까운 미래에 전자서명을 위조하거나, 암호화된 메시지를 읽을 수 없다. 이 연구가 발표된 후에 전자세계가 그 전보다 덜 안전해지는 것은 아니다.

그러나 NSA 내부에서 전해져 내려오는 오래된 이야기가 있다. “공격은 언제나 발전한다. 그것은 퇴보하는 법이 없다.” 이번 공격도 간략화시킨 SHA-1, SHA-0, MD4, MD5에 대한 공격법을 논한 다른 논문들을 발판으로 삼은 것이며, 다른 연구자들은 이 연구를 다시 출발점으로 삼을 것이다. SHA-1에 대한 공격은 다른 사람들이 이 내용을 읽고, 더 빠른 트릭, 최적화 등을 개발함에 따라 계속해서 발전되어 나갈 것이다. 그리고 무어의 법칙은 계속해서 진군해 나갈 것이며, 기존의 공격법을 더 빠르고 실용적으로 만들 것이다.

PGP의 CTO인 Jon Callas는 이를 잘 요약했다.
“비상구를 향해 걸어가야 할 때가 왔다. 하지만 뛸 필요는 없다. 연기는 나지 않지만 어디선가 화재경보기가 울리기 시작했다.” 이는 지난 8월에 내가 말했던 것과 대동소이하다.

다행스럽게도 현시점에 대안은 있다. 美국립기술표준국(NIST)은 더 길고 깨기 어려운 해쉬 함수 표준 -SHA-224, SHA-256, SHA-384, SHA-512- 을 제정했다. 이것은 이미 미국 정부 표준이며 사용되기 시작했다. 이는 미봉책으로서는 훌륭하다. 그러나 나는 좀 더 나은 것을 바란다.

나는 NIST가 새로운 해쉬 함수를 위한 국제 경쟁을 주관했으면 한다. 그들이 DES를 대체할 새로운 암호 알고리즘 AES을 위해 했던 것처럼 말이다. NIST는 알고리즘을 공모하고, 여러 차례의 평가회의를 개최하여 암호계가 새로운 표준을 제정하기 위해 다양한 제안을 분석하도록 해야 한다.

우리가 가진 해쉬 함수 대부분(그리고 널리 쓰이는 것 전부)은 MD4의 설계를 기반으로 것이다. 분명히 지난 10년 동안 우리는 해쉬 함수에 대해 많은 것을 배웠고, 나는 우리가 그 지식을 뭔가 한층 더 안전한 것을 만들기 위해 적용하기 시작해야 한다고 믿는다.

해쉬 함수는 가장 덜 이해되고 있는 암호학의 기본 요소이며, 해쉬 기술은 암호 기술보다 훨씬 덜 발전되었다. 따라서 해쉬 부문에서는 주기적으로 놀랄만한 암호학적 연구결과가 도출된다.

나도 John Kelsey와 공동 집필한 논문에서 SHA-1의 second preimage를 2^106번의 계산 -이는 전수검색법을 사용할 때 필요한 2^160보다 훨씬 적은 것이다- 만에 찾아내는 알고리즘을 발표한 적이 있는데, 이는 다른 대부분의 해쉬 함수에 일반화될 수 있는 기술이다. 이 공격은 완전히 이론적이며 실용적인 것과는 거리가 멀다. 하지만 우리가 여전히 해쉬에 대해 배워야 할 것이 많이 남았다는 것을 잘 보여준다.

내가 지난 9월에 썼던 것을 다시 읽어보면, 내가 이런 사태를 예측했다는 것이 명백하지만 이렇게 빨리, 그리고 이렇게 인상적인 결과가 나올 줄은 미처 몰랐다. 중국 암호학자들은 그들의 업적에 대해 커다란 영예를 받을만하며, 우리는 SHA를 교체하기 위한 작업에 착수할 필요가 있다.
shanote_1.pdf
by sonnet | 2006/08/27 14:33 | 과학기술 | 트랙백 | 핑백(1) | 덧글(9)
<< 이전 다음 >>