SPRi POPUP3 ENGLISH
SPRi POPUP3 ENGLISH

' 박살난’SHA-1, 퇴출 가속화되나

  • 송지환SW기반정책·인재연구실 책임연구원
날짜2017.04.28
조회수21759
글자크기
  • “SHAttered” SHA-1, does it speed up the sunsetting?
    • 최근 Google과 CWI 암스테르담 연구소는 암호학적 해시 함수인 SHA-1에 대한 충돌 공격 성공
    • 공식적으로 SHA-1 사용이 제한되었지만, 여전히 많은 응용에서 사용됨에 따라 이번 공격 성공은 SHA-1 퇴출 필요성 강조
    • SHA-1 사용을 자제하고 좀 더 안전한 SHA-2 이상의 해시 함수로의 전환 필요
    • SHA-1과 같은 암호화 알고리즘의 일몰(sunsetting) 기한을 반드시 준수하여 보안 사고가 발생하지 않도록 조치
    • Recently, Google and CWI Amsterdam Institute succeeded in a collision attack against SHA-1, the most common cryptographic hash function
    • SHA-1, officially deprecated, is still used in many applications, so the success of this attack will emphasize the necessity of sunsetting SHA-1
    • We must avoid SHA-1 usage and switch to the more secure hash functions such as SHA-2 or higher
    • We should follow the sunsetting deadline of cryptographic algorithms such as SHA-1 to prevent security incidents
  • 최근 SHA-1 해시 알고리즘에 대한 충돌 공격 성공
    • Google 연구팀과 CWI 암스테르담 연구소는 그간 발표된 SHA-1 취약점 공격 알고리즘과 Google의 고성능 컴퓨팅 인프라를 이용하여 SHA-1 충돌 공격(collision attack) 성공(2017년 2월)
    • 2005년 SHA-1에 대한 충돌 공격이 이론적으로 가능하다는 논문 발표(1) 이후 실제 충돌 공격을 성공한 첫 번째 사례
    • 연구팀은 이번 충돌 공격 성공을 ‘SHA-1을 실제 깼다’라는 의미로‘ SHAttered(박살난)’라는 표현을 사용
    • <그림 1> Google과 CWI 암스테르담 연구소는 같은 SHA-1 값을 갖는 서로 다른 PDF 문서를 생성하여 웹사이트에 공개(좌측 PDF는 파란색 배경, 반면 우측 PDF는 빨간색 배경, 그러나 SHA-1 값은 동일)
    • 연구팀은 발표 90일 후인 2017년 5월 말 SHA-1 충돌 공격에 대한 상세 알고리즘 공개 예정
    • 그간 발표된 SHA-1의 여러 취약점 공격 알고리즘을 바탕으로 고성능 분산 컴퓨팅 환경에서 수행 가능한 새로운 방법을 제안하였다고만 언급
    • 자세한 알고리즘은 SHA-1에 대한 대책이 어느 정도 강구되었다고 판단되는 시점인 5월 말 공개 예정
    • 여전히 SHA-1을 사용하는 분야가 많아 상당한 파장 예상
    • 최근 美 국립표준기술연구소(NIST)의 권고로 SHA-1 기반의 SSL/TLS 인증서 발급이 중단되었고, Google 크롬 브라우저를 비롯해 대부분의 브라우저는 SHA-1 기반 SSL/TLS 인증서를 사용하는 웹사이트 접근시 사용자에게 보안 위험 경고 표시
    • 그러나, 문서 변조 확인, 중복 파일 검사, 소스 코드 관리, 일부 SSL/TLS 인증서 등 여러 응용분야에서 여전히 사용
  • SHA-1이란?
    • SHA-1은 암호학적 해시 함수(cryptographic hash function)로서 임의의 길이(2)의 입력값을 받아 160비트의 해시값으로 매핑
    • 예를 들어,‘ 소프트웨어정책연구소’라는 한글 유니코드 메시지(3)의 SHA-1 해시값은 항상‘ 67 09 4F B8 94 0E 9F EA 83 64 A2 76 C0 96 CB FD AE E4 5B 70’(16진수)으로 매핑
    • 해시 함수와 암호학적 해시 함수
    • 소프트웨어정책연구소’라는 메시지에 대해서는 항상 같은 SHA-1 해시값을 갖지만, 이와 동일한 해시값을 갖는 다른 메시지를 임의로 만들어 내는 것은 거의 불가능
    • 해시값이 같은 서로 다른 메시지를 임의로 만들어내는 것을 충돌 공격(collision attack)이라 함
    • SHA-1에 대한 무차별 대입 탐색(brute-force search) 공격이 성공하기 위해서는 이론적으로 대략 280(=1,208,925,819,614,629,174,706,176) 정도의 계산이 필요(4)하기 때문에 최신 GPU로 1,200만 년 소요(비현실적인 방법)(5)
    • 그림 2 SHA-1 해시값에서 입력값을 알아내는 것은 불가능하며, 동일한 SHA-1 해시값을 갖는 다른 입력값을 찾아내는 것도 거의 불가능
      <그림 2> SHA-1 해시값에서 입력값을 알아내는 것은 불가능하며, 동일한 SHA-1 해시값을 갖는 다른 입력값을 찾아내는 것도 거의 불가능
    • 입력 메시지의 한 비트(bit)만 달라져도 전혀 다른 SHA-1 해시값 출력 (눈사태 효과)
    • ‘ 00000000’(2진수)의 SHA-1 값은 ‘5B A9 3C 9D B0 CF F9 3F 52 B5 21 D7 42 0E 43 F6 ED A2 78 4F’(16진수)
    • ‘ 00000001’(2진수)의 SHA-1 값은‘ BF 8B 45 30 D8 D2 46 DD 74 AC 53 A1 34 71 BB A1 79 41 DF F7’(16진수)
    • 즉, 한 비트만 다른‘ 00000000’과‘ 00000001’의 SHA-1 값은 서로 전혀 다름
    • 그림 3 원본 그림에 한 픽셀의 빨간 점 하나만 추가해도 SHA-1 값은 완전히 달라짐(눈사태 효과)
      <그림 3> 원본 그림에 한 픽셀의 빨간 점 하나만 추가해도 SHA-1 값은 완전히 달라짐(눈사태 효과)
    • SHA-1의 이러한 특성 때문에 문서 변조 방지를 위한 디지털 서명, 안전한 HTTP 통신을 위한 SSL/TLS 인증서, 백업시스템에서의 파일 변경 감지, 소스 코드 관리 시스템에서의 파일 버전 관리 등 여러분야에서 사용
  • SHA-1 탄생에서 퇴출까지
    • 암호학적 해시 함수로는 MD-SHA 패밀리가 대표적
    • 1990년 MD4의 등장으로 MD-SHA 패밀리 시작, 그러나 보안 취약점 발견으로 2년 만에 MD5로 대체
    • 그 후 MD5는 10년 이상 널리 사용되었으나, 2004년 중국의 대학 연구팀에 의해 깨져(6) 퇴출
    • MD5를 대체할‘ 안전한 해시 표준(Secure Hash Standard)’이라는 구호 아래 1993년 美 국립표준기술연구소(NIST)는 SHA-0 공개, 그러나 보안 문제 발생으로 바로 폐기하고 1995년 SHA-1 발표
    • SHA-1은 280 정도의 계산 복잡도를 갖기 때문에 쉽게 깨지지 않을 것으로 믿어왔으나, 2005년부터 SHA-1의 복잡도를 낮추어 공격하는 방법이 줄지어 발표되고 컴퓨팅 성능이 빠르게 발전함에 따라, 결국 2011년 NIST는 공식적으로 SHA-1 사용 제한(DEPRECATED)
    • 2017년 Google 연구팀과 CWI 암스테르담 연구소에 의해 SHA-1 충돌 공격 첫 성공
    • SHA-1의 취약성을 보완하여 SHA-224, SHA-256, SHA-384, SHA-512 등이 발표되고 이를 SHA- 2라 부름
    • NIST는 SHA-2보다 좀 더 안전한 SHA-3를 공모, 2012년 기존 알고리즘과는 전혀 다른‘ Keccak’이라는 알고리즘을 SHA-3의 해시 알고리즘으로 선정하였고, 2015년 SHA-3를 공식 발표(7)
    • 표 1 MD-SHA 패밀리 알고리즘 비교
      <표 1> MD-SHA 패밀리 알고리즘 비교
  • Google과 CWI 암스테르담 연구소에 의해 ‘ 박살난(SHAttered)’ SHA-1
    • 연구팀은 SHA-1 충돌 공격 성공을‘ SHAttered’라고 명명
    • ‘ SHAttered’는‘ 박살난’ 또는‘ 엄청나게 충격받은’이라는 사전적 의미를 가지는 동시에‘ SHA-’로 시작되는 단어를 선택한 재치 있는 중의적 표현
    • SHA-1 충돌 공격 성공은 기존 연구들과 Google의 고성능 분산 컴퓨팅 인프라 때문에 가능
    • 연구팀은 이론 기반의 기존 충돌 공격 연구들을 바탕으로 분산 컴퓨팅 환경에서 실제 공격을 구현하기 위해 새로운 알고리즘 제시
    • SHA-1 충돌 공격은 이론적으로는 261의 계산이 필요(9) 하지만 실제 분산컴퓨팅 환경에서 구현하기 위해 263.1의 계산 필요, 그런데도 SHAttered 방식이 무차별 대입 탐색(brute-force search) 공격 방식보다 약 10만 배 빠름
    • SHAttered 방식은 무려 9,223,372,036,854,775,808의 SHA-1 계산이 필요하므로 일반적인 컴퓨팅 환경에서 수행하기는 힘들지만, Google의 고성능 분산 컴퓨팅 환경에서는 비교적 단시일 만에 충돌 공격 성공
    • 연구팀은 효율적인 계산을 위해 알고리즘을 두 단계로 나누었고, 첫 번째 단계는 CPU 기반의 분산 컴퓨팅 환경에서 수행되었으며, 많은 컴퓨팅 성능이 필요한 두 번째 단계를 위해서는 여러 개의 고성능 GPU로 구성된 컴퓨팅 환경에서 수행
    • 연구팀은 SHA-1 충돌 공격 여부를 확인할 수 있는 서비스(10)를 제공하고 있으며, GitHub에 해당 알고리즘을 공개(11) 하여 누구나 자유롭게 사용 가능
    • 그림 4 SHAttered 방식은 110개의 GPU를 사용하여 대략 1년 안에 SHA-1을 깰 수 있지만, 무차별 대입 탐색(brute-force search) 공격의 경우 1년 안에 깨려면 1.2천만 개의 GPU 필요
      <그림 4> SHAttered 방식은 110개의 GPU를 사용하여 대략 1년 안에 SHA-1을 깰 수 있지만, 무차별 대입 탐색(brute-force search) 공격의 경우 1년 안에 깨려면 1.2천만 개의 GPU 필요
  • 시사점
    • 암호화 알고리즘의 취약점 발견과 컴퓨팅 성능의 빠른 발전으로 기존 암호화 알고리즘의 퇴출 주기가 빨라지고 있음
    • 암호화 알고리즘의 취약점 발견 즉시 수정 패치를 즉시 반영하여 피해 발생을 최소화해야 함
    • 보안에 민감한 영역에서 SHA-1 사용을 즉시 금지하고 그 이외의 사용에 대해서도 SHA-2 이상으로 전환 권장함
    • 암호화 알고리즘의 일몰(sunsetting) 기한을 반드시 준수하여 보안 사고를 미리 대비해야 함
    • (1) Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu, Finding Collisions in the Full SHA-1, CRYPTO(Victor Shoup, ed.), Lecture Notes in Computer Science, vol. 3621, Springer, 2005, pp. 17-36
    • (2) 최대 264 -1의 길이까지 입력 가능
    • (3) 소프트웨어정책연구소’의 한글 유니코드는‘FFFE 8CC1 04D5 B8D2 E8C6 B4C5 15C8 45CC F0C5 6CAD 8CC1’(16진수)
    • (4) 생일 패러독스(birthday paradox) 이론에 의하면 해시값 길이의 절반만큼만 공격하면 해시 알고리즘을 깰 수 있음, 따라서 SHA-1 해시값의 크기가 160비트이기 때문에 그 길이의 절반인 80 비트의 경우의 수인 280만큼의 공격으로 SHA-1을 깰 수 있음
    • (5) http://shattered.it/
    • (6) Xiaoyun Wang and Hongbo Yu, How to Break MD5 and Other Hash Functions, EUROCRYPT(Ronald Cramer, ed.), Lecture Notes in Computer Science, vol. 3494, Springer, 2005, pp. 19-35
    • (7) https://www.federalregister.gov/documents/2015/08/05/2015-19181/announcing-approval-of-federal-informationprocessing-standard-fips-202-sha-3-standard
    • (8) 컴퓨팅 성능에 따라 기준이 달라지지만 최근 기준으로는 112 이상이 안전하다고 봄
    • (9) Marc Stevens, New Collision Attacks on SHA-1 Based on Optimal Joint Local-Collision Analysis, EUROCRYPT (Thomas Johansson and Phong Q. Nguyen, eds.), Lecture Notes in Computer Science, vol. 7881, Springer, 2013, pp. 245-261
    • (10) https://shattered.io/ 에 파일을 올리면 SHA-1 충돌 여부를 알려줌
    • (11) https://github.com/cr-marcstevens/sha1collisiondetection
목록