SHA-1 충돌

해시함수는 입력된 임의의 자연수 값에 대해 고정된 값 이하의 자연수를 출력하는 함수인데, 출력된 정수를 보고 처음에 어떤 값을 넣었는지 추론하기 어려울 수록 좋다. 주로 비밀번호의 저장과 같은 보안성이 필요한 경우에 사용된다. 어떤 사람이 SHA-1의 알고리즘을 step by step으로 예시를 통해 상세히 설명하는 사이트[1]가 있는데, 설명이 아주 훌륭하니 일독을 권한다.

그런데 정의역인 자연수 집합은 무한집합이고 해시함수의 치역은 유한집합이므로, 반드시 함수 값이 같은 서로 다른 두 자연수가 존재한다. 따라서 해시함수로만 비밀번호를 저장한다는 가정하에, 반드시 사이트에 로그인을 할 수 있는 또 다른 문자 집합이 존재하게 된다. 같은 함수값(해시값)을 갖지 않는 다른 입력값을 찾기 어려워야 좋은 해시함수가 되는 것이다. 이렇게 입력이 다르지만 해시값이 같은 값이 발견될 때, ‘충돌’이라 부른다.

SHA1의 충돌은 이미 십년 전부터 이야기 되어 오던 것이라 새삼스러울 것은 없는데, 슈나이어 선생의 2005년 포스트[2]를 참고하기 바란다. sonnet씨가 슈나이어 선생의 글을 번역한 것[3]이 참고할만하다.

근래 구글에서 아예 SHA1의 해시값이 똑같게 나오는 두 pdf 파일을 예시로 보여준 모양[4]인데, 이게 화제[5,6]가 되고 있는지 여러 사이트에서 반복적으로 언급되고 있다. 비교적 효과적으로 SHA1의 충돌을 만드는 어떤 방법을 찾은 것 같다. 아예 관련 사이트[7]도 만들었는 듯. CPUU씨가 구글 보안 블로그의 글[4]을 번역한 포스팅[8]을 고맙게도 해 놓았다. 일전에 SyntaxNet에 관한 구글의 글을 번역[9]하신 그 분이다. ㅋ

해커뉴스[10]에서는 아예 SHA1 충돌이 일어나도록 생성해주는 충돌 생성기[11]도 만든 걸 소개하던데, 꽤 신통방통한건지 화제가 되고 있다. 본인이 직접 해 보니 너무 큰 이미지를 업로드하면 안 되고, 512 x 512 이하의 작은 이미지 두 개를 업로드하면 SHA1 해시 함수값이 같은 두 개의 업로드한 이미지를 삽입한 pdf 파일을 압축해서 다운로드 하도록 만들어 준다. 해시 체커로 확인해보면 분명 다른 파일인데 SHA1 해시함수 값이 똑같다. 오오!! ㅋㅋㅋ 구글측에서는 충돌 pdf를 만들기 위해 연산량이 상당했던 것 같은데[4], 충돌생성기[11]는 상당히 순식간에 되는게 꽤 신통방통하구만.

국내 인터넷 뱅킹에 SHA1을 꽤 많이 쓰는 걸로 알고 있는데[12], 컴퓨팅 파워가 무어의 법칙을 따라 지속적으로 증가해 오면서 2015년 부터 지속적으로 SHA1을 쓰지 말고 업그레이드 된 SHA-256이상을 쓰라고 경고가 있어 온 걸로 알고 있다.[13] 뭐 은행이 알아서 잘 해주겠지 ㅋㅋㅋ

 


2017.2.26

 


2017.2.27
지디넷 SHA1 깬 구글 “깃(Git) 시스템도 불안하다” 2017.02.27.13:57

 


2017.3.8
보안뉴스 SHA-1 충돌 코드 공개까지 약 90일, 구글의 역할은? 2017-03-08 16:27

 


2017.3.21
https://news.ycombinator.com/item?id=13917990

 


[1] How Hash Algorithms Work
[2] Cryptanalysis of SHA-1 by Bruce Schneier
[3] 중국 연구팀이 SHA-1 해독에 새로운 진전을 이룩(2005년 버전) by sonnet
[4] Announcing the first SHA1 collision in Google Security Blog
[5] 지디넷 구글, 구형 암호기술 ‘SHA1’ 허점 입증했다 2017.02.24.15:52
[6] SHATTERED — SHA-1 IS BROKEN IN in Hack a Day
[7] https://shattered.it/
[8] Google, SHA-1 해쉬함수 충돌쌍 공격 발표 by CPUU
[9] 내 백과사전 구글의 자연어 처리 오픈소스 SyntaxNet 2016년 5월 14일
[10] https://news.ycombinator.com/item?id=13723892
[11] https://alf.nu/SHA1
[12] 지디넷 인터넷뱅킹에도 쓰는 암호화 기술 보안 ‘우려’ 2015.10.26.11:22
[13] 보안뉴스 각종 인증서 기본이 되는 SHA-1에 충돌 공격 비상 2015-10-13 14:32

Advertisements

2 thoughts on “SHA-1 충돌

  1. 리누스의 반응에 대해서는 HN에 찬반 양론이 대립하고 있습니다. [1] 개인적으로는 이번 SHA-1 공격의 본질은 2^63 공격이 알고리즘만 제대로 잡으면 적절한 비용(1억 정도를 추산하더군요)으로 가능해졌다는 것이 중요하지 SHA-1 충돌이 나온 게 중요한 건 아니라고 봅니다—2^60 공격이 이미 있었던 걸로 기억하고, 슈나이어도 시간 문제[2]라고 지적했죠(슈나이어가 요즘 암호학에 딱히 유의미한 사람은 아니긴 합니다만;). 리누스는 옛날에도 커널에서 보안 버그와 일반 버그는 딱히 차이가 안 난다[3]고 주장했던 사람이라 놀랍진 않은데, 매우 실용주의적인 입장이긴 합니다만 다른 개발자들이 보안 버그를 보는 시각과는 확실한 온도 차이가 있습니다. Git의 현재 및 근미래 계획은 리누스한테는 충분할지 몰라도 다른 사람한테는 충분하지 않을 수 있겠지요.

    [1] https://news.ycombinator.com/item?id=13733481
    [2] https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html
    [3] http://yarchive.net/comp/linux/security_bugs.html

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중