Stop using SHA-1

SHA-1 함수는 SHA(Secure Hash Algorithm)이라 불리는 SHA 함수 중 하나이며, 많은 곳에서 쓰이고 있다.

SHA-1의 해시값 크기는 160bit이며 16진수로 40개의 문자로 표현된다.

간단하게 "do9dark" 값과 .(점)을 찍은 "do9dark." 값의 SHA-1 해시값을 비교하면 눈사태 효과(쇄도 효과)에 의해서 출력값에 상당한 변화가 발생된다.

SHA1("do9dark") = c82e31303466b765eabdab1eb367f6e0fcb221fa

SHA1("do9dark.") = 16e9f7ac968899b5d94eff21fe4918a651e75fde

이러한 특징 때문에 파일, 인증서 등에 위변조 판단 여부로도 많이 사용되고 있다.

공백은 da39a3ee5e6b4b0d3255bfef95601890afd80709

하지만, SHA-1의 보안적인 문제라 할 수 있는 해시 충돌에 대한 이론은 이미 공개되었고, 실제로 서로 다른 두 파일을 동일한 해시값이 출력되도록 위변조가 가능하다는 것을 2017년 2월 23일, Google Security Blog를 통해서 "Announcing the first SHA1 collision"을 공개하였다.

파일의 내용은 다르지만 SHA-1 해시 함수로 검증하였을 때 동일한 PDF 파일을 만드는 데 성공하였고, 해당 파일도 같이 공개하였다.

두 개의 PDF 파일의 헥사값을 비교해보면 위와 같이 Collision blocks의 내용이 다르지만 SHA-1 해시값은 동일한 것을 알 수 있다.

(좌) shattered-1.pdf                                                                           (우) shattered-2.pdf

https://shattered.io/ 페이지에 접속해보면 PDF 파일의 SHA-1 해시값 충돌에 대하여 확인할 수 있는 기능도 제공하고 있다.

그리고 제공된 두 개의 PDF 파일을 분석해보면 파일 헤더에 Collision blocks을 제외한 나머지 값은 같다는 것을 알 수 있고, 나머지 부분을 분석해보면 하나의 PDF에 양쪽에서 사용되는 내용이 모두 포함되어 있다는 것을 알 수 있다. 

조금 더 명확하게 확인하기 위해서 서로 다른 이미지 2개를 준비하였다.

그리고 http://alf.nu/SHA1 페이지에 접속해보면 서로 다른 2개의 이미지를 이용하여 SHA-1 해시 충돌이 발생하는 PDF 파일을 만들어주는 기능을 이용할 수 있다.

생성된 PDF 파일을 열어서 확인해보면 내용이 서로 다른 것을 확인할 수 있다.

간단하게 두 파일의 SHA-1 해시값을 확인해보면 동일한 것을 확인할 수 있다.

비교한 2개의 PDF 파일의 헥사값을 확인해보면 shattered-1.pdf, shattered-2.pdf에서 사용한 값을 이용한 것을 볼 수 있다.

shattered-1.pdf = b.pdf

shattered-2.pdf = a.pdf

<shattered-1.pdf 파일과 b.pdf 파일 비교>

2개의 파일에서 사용된 부분만 비교를 해봐도 SHA-1 해시값이 같은 것을 알 수 있다. 

(해당 값 뒤에 임의로 값을 동일하게 추가하거나 변경하더라도 동일한 SHA-1 해시값이 출력됨.)

즉, 2개의 파일에서 사용된 0x000 ~ 0x13F 값이 SHA-1 해시 충돌에 직접적으로 연관을 주는 것을 알 수 있고 PDF 파일 구조의 트릭을 이용해서 두 내용을 각각의 PDF 파일에 모두 삽입한 다음, 서로 다른 내용을 보여주도록 되어있는 것을 추측할 수 있다.

a.pdf의 0x000 ~ 0x13F 값과 b.pdf의 0x000 ~ 0x13F 값을 바꿔보면 내용이 서로 바뀌는 것을 볼 수 있으며, 아래와 같이 1.jpg의 FF D8을 제외한 부분을 a.pdf 파일에서 찾을 수 있고, 2.jpg의 FF D8을 제외한 부분도 a.pdf에서 찾을 수 있다.

<a.pdf 파일에서 1.jpg 부분>

<a.pdf 파일에서 2.jpg 부분>

https://github.com/nneonneo/sha1collider 페이지에 접속해보면 2개의 PDF 파일을 입력하였을 때, 동일한 SHA-1 해시값을 가지는 PDF로 변환해주는 파이썬 코드를 볼 수 있다.

코드 분석을 전부 해보지는 않았지만, PDF 파일에 이미지 정보를 가져와서 SHA-1 해시 충돌이 발생하는 헤더값으로 다시 PDF를 생성해주는 코드로 보인다.

코드 테스트는 리눅스(Ubuntu 16.04 64bits)에서 하였고, Python3, Pillow, libjpeg-progs(cjpeg, djpeg)를 추가로 설치하였다.

# apt-get install python3-pip

# pip3 install pillow

# apt-get install libjpeg-progs

# python3 collide.py a.pdf b.pdf

그리고, Boston Key Party CTF 2017에서도 SHA-1 해시 충돌을 이용해서 문제가 출제되었다.

- Prudentialv2

<?php
require 'flag.php';
 
if (isset($_GET['name']) and isset($_GET['password'])) {
    $name = (string)$_GET['name'];
    $password = (string)$_GET['password'];
 
    if ($name == $password) {
        print 'Your password can not be your name.';
    } else if (sha1($name) === sha1($password)) {
      die('Flag: '.$flag);
    } else {
        print '<p class="alert">Invalid password.</p>';
    }
}
 
?>

Boston Key Party CTF 2015에서 나왔던 문제를 수정한 문제이기도 하다.

- Prudential 

<?php
require 'flag.php';
 
if (isset($_GET['name']) and isset($_GET['password'])) {
    if ($_GET['name'] == $_GET['password'])
        print 'Your password can not be your name.';
    else if (sha1($_GET['name']) === sha1($_GET['password']))
      die('Flag: '.$flag);
    else
        print '<p class="alert">Invalid password.</p>';
}
 
?>

Prudential 문제는 === 로 비교 시, GET으로 배열 형태로 입력해주면 쉽게 우회할 수 있었다.

http://do9.kr/?name[]=a&password[]=b

Prudentialv2 문제는 (string)으로 타입을 지정하는 방법으로 조치를 해놓은 문제로 배열 형태로 입력해도 우회가 불가능하다.

하지만, sha1() 함수로 해시값을 비교하고 있기 때문에 PDF 파일에서 사용된 값을 이용해서 통과할 수 있다.