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

skin by 이글루스
중국 연구팀이 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)
트랙백 주소 : http://sonnet.egloos.com/tb/2657614
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Linked at a quarantine sta.. at 2009/02/26 17:02

... )과 같은 생일을 가진 누군가를 찾으면 확률이 매우 낮은데(푸른 선), 아무나 좋으니 생일이 같은 두 사람을 찾으면 그 확률은 훨씬 높다(초록 선)는 것입니다. 이 문제는 해쉬함수 충돌같은 실용적인 응용이 있어서 많은 교재들이 빼놓지 않고 소개하곤 합니다. 그러나 이 문제는 수학과 별 관계없이 사는 사람들에게도 유용하게 활용될 수 있습니다. 어떤 ... more

Commented by 개발부장 at 2006/08/27 17:44
...우리가 모르는 곳에선 이런 일들이--;;
Commented by sonnet at 2006/08/28 15:36
개발부장/ 이쪽 일 하는 사람이 아니면 사실 잘 알기 힘든 기술적인 부분이죠.
Commented by 번동아제 at 2006/08/28 21:31
재미있는 소식 잘 읽었습니다. 한 나라가 진정한 강대국이 되기 위해선 겉으로는 잘 드러나지 않지만 반드시 갖춰야할 영역이 있죠. 중국...한국이 생존하기 위해서는 반드시 풀어야할 화두인데...쩝
Commented by sonnet at 2006/08/28 23:57
번동아제/ 말씀 감사합니다.
세계적으로 통하는 이정도 결과를 내놓는다는 건 중국이 이 분야에 이미 좋은 연구자들을 갖고 있다는 충분한 증거입니다. (물론 이들은 민간 연구자이(겠)지만, 학계가 정부를 위한 인력을 길러내는 이상, 그 나라의 학계를 보면 정부의 실력을 많은 부분 미루어 짐작할 수 있습니다)
전 개인적으로 이 분야에선 중국이 일본을 앞서 있는게 아닌가 하는 인상을 갖고 있습니다. 다만 한중일 중심의 암호학회 AsiaCrypt는 미국의 CRYPTO나 유럽의 EuroCrypt에 비해 투고논문의 질이나 편집자의 능력이 떨어지는 것이 확연히 느껴집니다.
Commented by 라피에사쥬 at 2006/08/30 03:40
2차대전 당시 SS소속의 암호 분석팀이 45년 초부터 영국본토에서 연합군점령지로 송신하는 암호를 해독한 사건이 생각나네요. 전쟁말기라 자원도 인력도 모자란 상황이었는데 전혀 의외의 결과물이라는 점에서 비슷한 점이 있을지도?..는 아니군요[..]
Commented by sonnet at 2006/08/30 15:18
라피에사쥬/ 평시나 전력이 어느 정도 비등할 때야 의미가 있겠지만...
Commented by 최종욱 at 2007/06/13 12:42
갈수록 분산 컴퓨팅이 일반화되고 무어의 법칙이 적용받으니 해쉬 충돌은 예전보다 무시무시하게 빠른 속도로 따라잡히고 있군요. 분산 컴퓨팅을 제일 많이하는 구글은 40~60만개의 인텔 CPU를 한 번에 구매했으니, 100만대(=2^20)가 있다고 생각할 수 있겠죠. MD5깨는 도구가 펜4에서 1초에 40million개 (=2^25)를 공격한답니다.

초당 2^45의 공격을 할 수 있다면, 2^56 DES 푸는 것 쯤이야 일도 아니군요. 전수 검사에 35분 걸립니다. 기대값은 절반인 17분 정도. 다만 지수가 확 올라가면 따라잡기는 아직 힘듭니다만. 무어의 법칙으로 여전히 꾸준히 따라잡고 있군요. 쿼드코어 같을 걸 쓰면 또 지수가 2개 올라가버리 말이죠.
Commented by 어부 at 2007/06/15 20:08
장거리 광자 통신이 일반화되면 양자 암호를 사용할 테니 이런 문제는 아마 근본적으로 없어질지도 모르죠.
Commented by sonnet at 2007/06/17 07:45
최종욱/ 멀티코어 CPU가 대세가 되면서 컴퓨팅 파워의 총량은 이전보다 더 빨리 늘어날 것 같습니다. 2^80도 불안해 보이고 2^128인 SHA-256정도는 되어야 하지 않겠는지요.

어부/ 그래도 end to end로 양자암호통신을 하진 않을 것 아닙니까.

:         :

:

비공개 덧글

<< 이전 다음 >>