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

아마추어 암호 설계자에 대한 메모
(Bruce Schneier)
원문은 여기

축하한다. 당신은 방금 대단한 새 암호를 발명했다. 그래서 그걸 갖고 뭔가 해보려고 한다. 당신은 이 분야에 있어 신참이기 때문에 아무도 당신의 이름을 들어본 적이 없고 암호분석가(cryptanalyst)로서 아무런 자격도 없다. 따라서 당신은 잘 알려진 암호학자들이 당신의 작품을 봐주기를 원한다. 그러기 위해서는 무엇을 할 수 있을까?

불행하게도 당신 앞에는 험난한 길이 가로놓여 있다. 내 경우 아마추어 암호설계자가 보내오는 새로운 암호 설계를 매주 두건 정도는 받아보고 있다. 그 암호들이 안전할 확률은 희박하다. 그중 하나라도 안전하면서도 효율적인 것이 있을 가능성은 무시할 수 있을 정도이다. 그중 하나라도 실제로 돈값을 할 가능성은 존재하지 않는다고 해도 과언이 아니다.

가장 무능한 아마추어로부터 최고의 암호학자에 이르기까지 누구라도 자신이 깰 수 없는 알고리즘을 만들 수 있다. 그것은 어렵지도 않다. 진짜 어려운 것은 여러 해 동안의 연구에도 불구하고 다른 사람이 아무도 깰 수 없는 알고리즘을 만드는 것이다.
그리고 그것을 증명하는 유일한 방법은 그 알고리즘을 일류 암호학자들에 의한 다년간의 분석의 대상이 되게 하는 것이다.

“세계의 일류 암호학자”들은 여러 암호들을 깨왔다. 학계의 문헌 곳곳에는 그들의 분석에 의해 해독된 암호들의 잔해들이 널브러져 있다. 하지만 그들은 바쁜 사람들이다. 그들은 모든 것을 깨부술 시간이 없다. 그들은 무엇을 살펴볼 것인지 어떻게 결정하는가?

이론적으로 말하면 암호학자들은 안전할 가능성을 충분히 가진 암호들만을 살펴보아야 한다. 그런데 누구나 자신이 생각하기에는 안전한 것 같은 암호를 만들 수 있는 이상, 이는 경청할만한 실력을 가진 사람들에 의해 만들어진 암호만을 살펴보아야 한다는 것을 의미한다.
누군가 임의의 사람이 자신이 해독할 수 없는 암호를 만들었다고 해도 아무도 주목하지 않는다. 하지만 세계 최고의 암호학자들 중 한명이 자신이 깰 수 없는 암호를 만들었다고 선언하면 이제 그것은 주목할 가치가 있는 것이 된다.

현실 세계는 그렇게 깔끔하지 않다. 암호학자들은 흥미롭거나 논문을 쓸 수 있을 정도의 결과를 얻을 수 있을 법한 알고리즘을 살펴본다. 이는 그 사람들이 저명한 암호학자가 만든 것, 현실세계에서 널리 쓰이고 있는 것(휴대폰, 유료케이블TV 디코더, 마이크로소프트 제품 같은), 학술지에 실렸던 것들을 살펴본다는 것을 의미한다. 모르는 사람이 인터넷 게시판에 올린 알고리즘 같은 것은 눈길 한번 주지 않는다. 특허출원 되었으나 미공표된 알고리즘이나 잘 알려지지 않은 제품에 내장된 “소유권이 존재하는”(proprietary) 알고리즘도 마찬가지다.

암호학적 알고리즘이 발표되기란 어렵다. 대부분의 학회나 워크샵은 방대한 분석이 첨부되지 않은 이상 모르는 사람이 투고한 디자인을 받아주지 않는다. 이것은 공정하지 않은 것처럼 보일지도 모른다. 무명의 암호설계자는 “그들이 무명이기 때문”에 자신의 암호를 발표할 수 없다. 그리고 그렇기 때문에 아무도 그들의 작업을 볼 수 없을 것이다.
현실에서 그들이 한 “유일한 일”이 암호를 설계한 것이라면 그것은 아마도 발표될 가치가 없을 것이다. 무명은 기존의 암호들을 해독한 내용을 발표함으로서 유명이 될 수 있다. 대부분의 학회들은 이러한 논문을 받아준다.

내가 『응용 암호학(Applied Cryptography)』이란 책을 쓰기 시작했을 때, 나는 기존의 암호설계들을 분석하는데 오랫동안 노력해온 사람들만이 좋은 암호 알고리즘 설계자가 될 수 있다는 격언을 들었다. 그 격언은 합당한 것처럼 느껴졌고 나는 그것을 믿었다. 세월이 흐르고 내가 암호 분석과 설계에 더 오랜 시간을 보냄에 따라 그 격언의 진실성은 더욱 더 강해져 갔다. Twofish 설계를 위해 일하면서 나는 이것을 더욱 더 절감했다.
암호의 강도는 그것의 설계에 있지 않다. 그따위 것은 누구나 설계할 수 있다. 진정한 힘은 그것의 분석에 있다. 우리는 Twofish를 분석하는데 1000인시 이상의 시간을 소모했고, 단순화된 버전들과 변형들을 깨보고, 수정사항들을 연구했다. 그렇지 않다면 우리는 그 분석을 해낼 수 없었을 것이고, 분석에 확신을 가질 수도 없었을 것이며, 전원이 많은 다른 알고리즘 설계들을 해독해 온 경험을 지닌 설계팀을 가질 수도 없었을 것이다.

어떤 암호학자 친구가 자신이 발명한 암호를 갖고 그를 귀찮게 한 아마추어에 대한 이야기를 해준 적이 있다. 이 친구는 그 암호를 해독했다, 그러자 아마추어는 그것을 “고친” 수정판을 내놓았고 이 친구는 그것을 다시 깨야 했다. 이 왔다갔다는 이 친구가 넌덜머리를 내며 두 손 들 때까지 몇 차례나 반복되었다. 아마추어가 이 친구의 견해를 듣기 위해 그를 방문했을 때, 암호학자는 테이블 위에 세 개의 봉투를 내놓았다.
“각각의 봉투에는 당신 암호에 대한 해독법이 들어 있소. 하나를 골라서 읽어 보시오. 그리고 당신이 나머지 두 공격을 스스로 알아낼 때까지 다시 나를 찾아오지 마시오.”
아마추어는 그 뒤로 다시는 나타나지 않았다고 한다.

나는 전적으로 부정적인 이야기를 하려는 것이 아니다. 사람들은 이따금씩 강한 암호들을 설계하기도 한다. 아마추어 암호학자조차도 강한 암호들을 만들 수 있다. 그러나 당신이 암호학계에 알려져 있지 않고, 다른 암호학자들이 당신의 작업을 봐주길 원한다면 다음과 같은 일을 해야 한다.

1. 당신의 암호를 표준적인 표기법(standard notation)을 사용해 기술하라. 이는 C 코드를 의미하지 않는다. 이 바닥에는 학술문헌에서 사용되는 확립된 전문용어와 기호들이 있다. 그것을 배워 사용하라. 당신만의 특수한 표기법을 배우려고 할 사람은 아무도 없다.

2. 다른 설계들과 당신의 암호를 비교하라. 십중팔구 그것은 예전에 발표된 몇몇 개념들을 사용하고 있을 것이다. 그것들을 참조(reference)하라. 이는 다른 사람들이 당신의 작업을 이해하기 쉽도록 만들어 줄 것이고, 다른 한편으로 당신이 학술문헌을 이해하고 있음을 보여줄 것이다.

3. 왜 당신의 암호가 문헌에 언급된 주요한 공격기법 각각으로부터 면역성을 갖고 있는지를 설명하라. 단순이 “이것은 안전합니다.”라고만 말하는 것은 좋지 않다. 당신은 왜 이것이 그러한 공격들로부터 안전한지 보여줘야만 한다. 이것은 당연한 이야기지만 당신이 단순히 문헌을 읽어봤을 뿐만 아니라 그것을 이해하고 있을 것을 요구한다. 이 과정에 여러 달이 걸리고 방대한 수학적 문서가 나올 것임을 각오하라.
그리고 기억해 둬라. 통계적 테스트는 그다지 의미가 없다.

4. 왜 당신의 암호가 기존의 대안들보다 나은지를 설명하라. 기존의 것들보다 명백한 이점이 없는 한 뭔가 새로운 것을 살펴보아야 할 이유가 없다. 그것은 펜티엄에서 더 빠른가? 하드웨어로 만들었을 때 더 작은가? 어떤가? 나는 종종 이런 이야길 한다, 충분히 많은 라운드가 있다면 웬만한 것은 다 안전하다고. 당신의 설계는 괄목할 만한 성능상의 장점이 필요하다. 그리고 “이것은 깰 수 없습니다”는 장점이 아니다. 그것은 필수조건이다.

5. 암호를 공표하라. 경험적으로 볼 때 공표되지 않은 암호들은 대부분 매우 취약하다. 암호를 비밀로 하는 것은 일단 암호가 널리 사용되기 시작하면 보안성을 증가시켜주지 못한다. 그리고 당신의 암호가 안전하기 위해 비밀이 유지될 필요가 있다면 그것은 어쨌든 쓸모가 없다.

6. 암호에 특허를 걸지 마라. 당신은 암호를 팔아서 돈을 벌 수 없다. 이 세상에는 단순히 너무 많은 우수한 공짜 암호들이 널려 있다. AES에 암호를 제출한 모든 사람들은 그것을 기꺼이 포기했다. 제안된 것들 중 많은 것은 이미 공개 암호였다. 만약 당신이 당신의 설계에 특허를 낸다면 모든 사람들은 단순히 다른 것을 쓰고 말 것이다. 그리고 (당신이 돈 주고 그 일을 시키지 않는 이상) 아무도 당신을 위해 그것을 분석해 주지 않을 것이다. 왜 그들이 당신을 위해 공짜로 그 일을 해야 하나?

7. 참을성을 가져라. 현재 당장 살펴보아야 할 많은 암호들이 있다. AES 경쟁은 암호학자들에게 분석해야 할 15개의 새로운 설계들을 내놓았다. 그리고 우리는 2000년 봄까지 승자를 가려내야만 한다. 여유시간이 있는 훌륭한 암호학자라면 이들 설계들을 캐고 있을 것이다.

당신이 알고리즘을 설계하고 싶다면, 거기 있는 것들 중 하나를 깨는 것으로부터 시작하라. 이미 깨어진 알고리즘을 (답을 들춰보지 말고) 깨는 연습을 하는 것부터 시작하라. 다른 사람이 깬 적이 없는 어떤 것을 깨보라. 또 다른 것을 깨보라. 당신의 해독결과를 공표하라. 자신이 기존의 알고리즘을 깰 수 있는 사람임을 입증했을 때, 당신은 새 알고리즘을 설계하기 시작할 수 있다. 그 전에는, 아무도 당신을 심각하게 상대해주지 않을 것이다.

암호를 만드는 것은 쉽다. 그것을 분석하는 것은 어렵다.