충돌 공격

**충돌 공격**(Collision attack)은 암호학적 해시 함수의 공격 방식으로, 해시 충돌이 일어나는 두 입력값을 찾는 공격이다. 충돌 공격은 다음의 두 가지로 구분된다.url-status=dead * **충돌 공격**(Collision attack) * **선정 접두어 충돌 공격**(Chosen-prefix collision attack) 역상 공격은 충돌 공격과는 달리 해시 함수의 출력값이 고정되어 있고, 해시 함수의 출력값이 같은 새로운 입력값을 찾는 공격이다. 따라서 충돌 공격은 역상 공격에 비해 더 쉬운 것으로 알려져 있다.
# 고전적인 충돌 공격
대칭 키 암호가 무차별 대입 공격에 취약한 것과 마찬가지로, 모든 암호화 해시 함수는 생일 공격을 사용하여 본질적으로 충돌에 취약하다. 생일 문제 때문에 이러한 공격은 무차별 대입 공격보다 훨씬 빠르다. n비트 해시는 2n/2번의 시간 단계(해시 함수 평가)로 깨질 수 있다. 수학적으로 말하면, 충돌 공격은 hash(m_1) = hash(m_2)가 되도록 서로 다른 두 메시지 m_1와 m_2를 찾는다. 고전적인 충돌 공격에서 공격자는 두 메시지의 내용에 대한 통제권이 없지만, 알고리즘에 의해 임의로 선택된다. 특정 해시 함수에 암호 해독을 적용하여 더 효율적인 공격이 가능하다. 충돌 공격이 발견되어 생일 공격보다 빠르다는 것이 밝혀지면, 해시 함수는 종종 "깨졌다"고 비난받는다. NIST 해시 함수 경쟁은 두 가지 매우 일반적으로 사용되는 해시 함수인 MD5Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, Cryptology ePrint Archive Report 2004/199, 16 Aug 2004, revised 17 Aug 2004. Retrieved July 27, 2008.와 SHA-1에 대한 공개된 충돌 공격으로 인해 크게 유발되었다. MD5에 대한 충돌 공격은 2007년 기준으로 일반 컴퓨터에서 불과 몇 초밖에 걸리지 않을 정도로 개선되었다.publisher=Eindhoven University of Technology 이런 방식으로 생성된 해시 충돌은 일반적으로 길이가 고정되어 있고 대부분 구조화되지 않아, 널리 사용되는 문서 형식이나 프로토콜을 직접 공격하는 데 적용할 수 없다. 그러나 많은 형식에 존재하는 동적 구성을 악용하여 해결책을 찾을 수 있다. 이런 방식으로, 동일한 해시 값을 갖도록 가능한 한 유사한 두 문서를 만들 수 있다. 한 문서는 서명을 위해 당국에 보여주고, 그 서명을 다른 파일에 복사할 수 있다. 이러한 악성 문서는 동일한 문서에 두 가지 다른 메시지를 포함하지만, 파일의 미묘한 변경을 통해 둘 중 하나를 조건부로 표시한다. * 포스트스크립트와 같은 일부 문서 형식이나 마이크로소프트 워드의 매크로에는 조건부 구성archive-date=2010-03-27 (if-then-else)이 있어 파일 내의 특정 위치가 어떤 값을 가지는지 테스트하여 표시되는 내용을 제어할 수 있다. *TIFF 파일은 해시 값에 영향을 주지 않고 이미지의 다른 부분이 표시되는 잘라낸 이미지를 포함할 수 있다. *PDF 파일은 색상 값을 사용하여 (한 메시지의 텍스트는 배경과 어울리는 흰색으로 표시되고 다른 메시지의 텍스트는 어두운 색상으로 표시되어) 충돌 공격에 취약하며, 이는 서명된 문서의 내용을 변경하기 위해 수정될 수 있다.
# 선택 접두어 충돌 공격
충돌 공격의 확장으로는 머클-담가드 해시 함수에 특정한 선택 접두어 충돌 공격이 있다. 이 경우 공격자는 임의로 다른 두 문서를 선택하고, 전체 문서가 동일한 해시 값을 갖도록 다른 계산된 값을 추가할 수 있다. 이 공격은 일반적으로 더 어려워 n비트 해시는 2(n/2)+1번의 시간 단계로 깨질 수 있지만, 고전적인 충돌 공격보다 훨씬 강력하다. 수학적으로 말하면, 서로 다른 두 접두어 p1, p2가 주어졌을 때, 이 공격은 hash(p1 ∥ s1) = hash(p2 ∥ s2)가 되도록 두 접미어 s1과 s2를 찾는다(여기서 ∥는 문자열 연결 연산이다). 특정 해시 함수에 암호 해독을 적용하여 더 효율적인 공격도 가능하다. 2007년에 MD5에 대한 선택 접두어 충돌 공격이 발견되었는데, MD5 함수를 약 250번 평가해야 한다. 이 논문은 또한 충돌하는 해시 값을 가진 다른 도메인 이름에 대한 두 개의 X.509 인증서를 시연한다. 이는 인증 기관에 한 도메인에 대한 인증서 서명을 요청한 다음, 해당 인증서(특히 서명)를 사용하여 다른 도메인을 가장하는 새로운 불량 인증서를 만들 수 있음을 의미한다.doi-access=free 실제 충돌 공격은 2008년 12월에 보안 연구원 그룹이 MD5 해시 함수에 대한 접두어 충돌 공격을 이용하여 인증 기관을 가장하는 데 사용될 수 있는 위조된 X.509 서명 인증서를 발표하면서 공개되었다. 이는 공격자가 SSL로 보호되는 모든 웹사이트를 중간자로 가장하여 전자 상거래를 보호하기 위해 모든 웹 브라우저에 내장된 인증서 유효성 검사를 무력화할 수 있음을 의미했다. 불량 인증서는 실제 기관에 의해 취소될 수 없으며, 임의로 위조된 만료 시간을 가질 수도 있었다. MD5가 2004년에 매우 약하다는 것이 알려졌음에도 불구하고, 인증 기관들은 2008년 12월에도 MD5로 검증된 인증서에 서명할 의향이 있었고,url-status=dead 적어도 하나의 마이크로소프트 코드 서명 인증서는 2012년 5월에도 여전히 MD5를 사용하고 있었다. 플레임 악성 소프트웨어는 선택 접두어 충돌 공격의 새로운 변형을 성공적으로 사용하여 손상된 MD5 알고리즘을 여전히 사용하던 마이크로소프트 루트 인증서에 의한 구성 요소의 코드 서명을 스푸핑했다.url-status=deadaccess-date=9 June 2012 2019년에 연구원들은 SHA-1에 대한 선택 접두어 충돌 공격을 발견했는데, 계산 복잡도는 266.9에서 269.4 사이였고 비용은 10만 달러 미만이었다. date = 2019-05-13 date = 2019-05-06 2020년에 연구원들은 SHA-1에 대한 선택 접두어 충돌 공격의 복잡도를 263.4로 줄였다.date = 2020-01-05
# 공격 시나리오
암호화 해시 함수의 많은 응용 프로그램은 충돌 저항에 의존하지 않으므로 충돌 공격은 보안에 영향을 미치지 않는다. 예를 들어, HMAC는 취약하지 않다.archive-date = 2008-07-17 공격이 유용하려면 공격자가 해시 함수의 입력에 대한 통제권을 가지고 있어야 한다.
## 디지털 서명
디지털 서명 알고리즘은 많은 양의 데이터를 효율적으로 서명할 수 없으므로, 대부분의 구현은 해시 함수를 사용하여 서명해야 하는 데이터 양을 일정한 크기로 줄인다("압축"). 디지털 서명 체계는 기본 해시 함수가 실제로 깨지자마자 해시 충돌에 취약해지는 경우가 많다. 무작위화된(솔트된) 해싱과 같은 기술은 더 어려운 역상 공격을 요구함으로써 추가 시간을 벌 수 있다.Shai Halevi and Hugo Krawczyk, Randomized Hashing and Digital Signatures date=2009-06-20 일반적인 공격 시나리오는 다음과 같다. # 맬러리는 동일한 해시 값을 가진 두 개의 서로 다른 문서 A와 B(즉, 충돌)를 생성한다. 맬러리는 밥이 앨리스로부터 온 것처럼 보이는 문서 B를 수락하도록 속이려 한다. # 맬러리는 **문서 A를 앨리스에게 보낸다**. 앨리스는 문서 내용에 동의하고, 해당 해시에 서명한 다음, 서명을 맬러리에게 보낸다. # 맬러리는 문서 A의 서명을 문서 B에 첨부한다. # 맬러리는 **서명과 문서 B를 밥에게 보낸다**, 앨리스가 B에 서명했다고 주장하면서. 디지털 서명이 문서 B의 해시와 일치하므로 밥의 소프트웨어는 대체 사실을 감지할 수 없다. 2008년, 연구원들은 이 시나리오를 사용하여 MD5에 대한 선택 접두어 충돌 공격을 통해 불량 인증 기관 인증서를 생성했다. 그들은 TLS 공개 키 인증서의 두 가지 버전을 만들었는데, 그중 하나는 합법적으로 보였고 RapidSSL 인증 기관에 서명을 위해 제출되었다. 동일한 MD5 해시를 가진 두 번째 버전에는 웹 브라우저가 이를 임의의 다른 인증서를 발급하는 합법적인 기관으로 받아들이도록 신호하는 플래그가 포함되어 있었다.conference=Chaos Communication Congress 2008
## 해시 플러딩
**해시 플러딩**(HashDoSs2cid=17805370라고도 함)은 해시 테이블 조회 시 최악의 경우(선형 조사) 런타임을 악용하기 위해 해시 충돌을 사용하는 서비스 거부 공격이다.website=v8.dev 이는 원래 2003년에 알고리즘 복잡도 공격의 한 예로 설명되었다.Scott A. Crosby and Dan S. Wallach. 2003. Denial of service via algorithmic complexity attacks. In Proceedings of the 12th conference on USENIX Security Symposium - Volume 12 (SSYM'03), Vol. 12. USENIX Association, Berkeley, CA, USA, 3-3. 이러한 공격을 실행하기 위해 공격자는 동일한 값으로 해싱되는 여러 데이터를 서버에 보내고 서버가 느린 조회를 수행하도록 시도한다. 해시 테이블에 사용되는 해시 함수의 주요 초점이 보안보다는 속도였기 때문에 대부분의 주요 프로그래밍 언어가 영향을 받았으며, 원래 발표 후 10년이 지나서도 이 클래스의 새로운 취약점이 계속 나타나고 있다. 해시 함수를 과도하게 복잡하게 만들지 않고 해시 플러딩을 방지하기 위해 새로운 키드 해시 함수가 도입되었으며, 키가 알려지지 않은 한 충돌을 찾기 어렵다는 보안 목표를 가지고 있다. 이전 해시보다 느릴 수 있지만 암호화 해시보다 계산하기는 여전히 훨씬 쉽다. 2021년 현재, 장-필립 오마송과 대니얼 J. 번스타인의 SipHash (2012)는 이 클래스에서 가장 널리 사용되는 해시 함수이다.date=2012-09-18 (응용 프로그램의 해시 테이블이 외부에서 제어할 수 없는 한 키가 없는 "단순" 해시는 계속 안전하게 사용할 수 있다.) (부분적인) 역상 공격을 사용하여 블룸 필터를 채우는 유사한 공격을 수행할 수 있다.type=report