충돌 공격

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 충돌 공격
3. 공격 시나리오
- 3.1. 디지털 서명
- 3.2. 기타 공격
4. 대응 방안
참조

1. 개요

충돌 공격은 동일한 해시 값을 갖는 두 개의 다른 메시지를 찾는 것을 목표로 하는 암호 공격의 한 종류이다. 이는 대칭키 암호와 해시 함수에 취약하며, 생일 공격을 통해 무차별 대입 공격보다 빠르게 수행될 수 있다. 충돌 공격에는 고전적인 충돌 공격, 선택 접두사 충돌 공격, 해시 플러딩 공격이 있으며, MD5, SHA-1과 같은 널리 사용되는 해시 함수에 대한 공격이 발견되었다. 이러한 공격은 디지털 서명, 인증서 위조 등 다양한 방식으로 악용될 수 있으며, 키 해시 함수와 같은 대응 방안이 제시되고 있다.

더 읽어볼만한 페이지

암호 공격 - 재전송 공격
재전송 공격은 유효한 데이터 전송을 가로채 재사용하여 권한 없는 접근을 시도하는 사이버 공격으로, 세션 ID, 일회용 비밀번호, 타임스탬핑 등을 통해 방지할 수 있으며, IoT 장치와 같은 시스템에서 보안 위험을 초래할 수 있다.
암호 공격 - 랜섬웨어
랜섬웨어는 컴퓨터 시스템 접근을 제한하고 금전을 요구하는 악성 소프트웨어이며, 암호화 기술을 활용하여 파일 접근을 막고, 비트코인 등장 이후 피해가 급증했으며, 이중 갈취 및 서비스형 랜섬웨어 형태로 진화하여 기업과 기관을 대상으로 공격하고, 파일 암호화, 시스템 잠금, 데이터 유출 등의 피해를 발생시킨다.

충돌 공격
암호학적 공격
분류
특징
목표	두 개의 구별되는 입력값이 동일한 해시 값을 생성하도록 하는 것. 임의의 입력값과 동일한 해시 값을 생성하는 다른 입력값을 찾는 것.
공격 성공 조건	공격자가 충돌을 생성할 수 있는 계산 능력을 갖추어야 함.
유형
생일 공격	해시 함수의 출력 공간 크기에 의존하는 일반적인 공격.
중간자 공격	암호화된 통신을 가로채고 수정하는 공격.
길이 확장 공격	해시 함수의 내부 상태를 이용하여 메시지 해시를 확장하는 공격.
차분 공격	입력값의 작은 변화가 출력값에 미치는 영향을 분석하는 공격.
부채널 공격	암호 시스템의 물리적 구현에서 발생하는 정보 누출을 이용하는 공격.
SHA-1 충돌 공격
발견	2017년 구글과 CWI 암스테르담 연구팀에 의해 발견됨.
원리	"선택된 접두사 충돌 공격"을 통해 두 개의 다른 메시지가 동일한 SHA-1 해시 값을 갖도록 함. 계산 복잡도는 2^63.1 SHA-1 연산에 해당하며, 이는 생일 공격보다 효율적임.
의미있는 충돌	두 개의 다른 PDF 문서가 동일한 SHA-1 해시 값을 가짐. 의미있는 충돌 공격 시나리오

2. 충돌 공격

대칭키 암호는 무차별 대입 공격에 취약하며, 모든 암호화 해시 함수는 생일 공격을 사용하여 충돌에 취약하다. 생일 문제로 인해 이러한 공격은 무차별 대입보다 훨씬 빠르다. ''n'' 비트의 해시는 2^''n''/2 시간 단계(해시 함수 평가)로 깰 수 있다.

디지털 서명 알고리즘은 대량의 데이터를 효율적으로 서명할 수 없기 때문에, 대부분의 구현은 해시 함수를 사용하여 서명해야 하는 데이터의 양을 고정된 크기로 줄인다("압축"). 디지털 서명 방식은 기본 해시 함수가 실질적으로 깨지면 해시 충돌에 취약해진다. 무작위(소금) 해싱과 같은 기술은 더 어려운 사전 이미지 공격을 요구함으로써 추가적인 시간을 벌 수 있다.^[13]

일반적인 공격 시나리오는 다음과 같다.

# 맬러리는 동일한 해시 값을 가진 두 개의 다른 문서 A와 B를 생성한다. 즉, 충돌이 발생한다. 맬러리는 앨리스가 보낸 것처럼 위장하여 문서 B를 수락하도록 밥을 속이려고 한다.

# 맬러리는 '''앨리스에게 문서 A를 보낸다'''. 앨리스는 문서의 내용에 동의하고, 해당 해시를 서명한 후, 해당 서명을 맬러리에게 보낸다.

# 맬러리는 문서 A의 서명을 문서 B에 첨부한다.

# 맬러리는 그런 다음 '''서명과 문서 B를 밥에게 보낸다'''. 앨리스가 B에 서명했다고 주장하면서 말이다. 디지털 서명이 문서 B의 해시와 일치하기 때문에 밥의 소프트웨어는 대체를 감지할 수 없다.

2008년, 연구자들은 이 시나리오를 사용하여 MD5에 대한 선택 접두사 충돌 공격으로 악성 인증 기관 인증서를 생성했다. 그들은 두 버전의 TLS 공개 키 인증서를 생성했는데, 그 중 하나는 합법적으로 보였고 RapidSSL 인증 기관에 서명을 위해 제출되었다. 동일한 MD5 해시를 가진 두 번째 버전에는 웹 브라우저가 임의의 다른 인증서를 발급하기 위한 합법적인 기관으로 받아들이도록 신호를 보내는 플래그가 포함되어 있었다.^[14]

2. 1. 고전적인 충돌 공격

수학적으로, 충돌 공격은 ''hash(m1)'' = ''hash(m2)''를 만족하는 서로 다른 두 메시지 ''m1''과 ''m2''를 찾는 것이다. 고전적인 충돌 공격에서 공격자는 두 메시지의 내용에 대해 아무런 제어 권한이 없지만, 알고리즘에 의해 임의로 선택된다.

암호 분석을 특정 해시 함수에 적용하면 더 효율적인 공격이 가능하다. 생일 공격보다 빠른 충돌 공격이 발견되면, 해당 해시 함수는 "깨졌다"고 평가받는다. NIST 해시 함수 경쟁은 널리 사용되는 두 해시 함수인 MD5^[1]와 SHA-1에 대한 공개된 충돌 공격 때문에 시작되었다. 2007년 기준으로, MD5에 대한 충돌 공격은 일반 컴퓨터에서 단 몇 초 만에 완료될 정도로 크게 개선되었다.^[2] 그러나 이렇게 생성된 해시 충돌은 일반적으로 고정된 길이를 가지며 구조화되지 않아, 널리 사용되는 문서 형식이나 프로토콜을 공격하는 데 직접 적용하기는 어렵다.

하지만, 많은 형식에 존재하는 동적 구성을 악용하면 해결할 수 있다. 동일한 해시 값을 갖도록 가능한 한 유사한 두 개의 문서를 만드는 것이다. 하나의 문서는 서명을 위해 권한자에게 보여주고, 그 서명을 다른 파일에 복사할 수 있다. 이러한 악성 문서는 동일한 문서에 두 개의 다른 메시지를 포함하지만, 파일에 대한 미묘한 변경을 통해 조건부로 하나를 표시한다.

PostScript나 Microsoft Word의 매크로와 같은 일부 문서 형식에는 파일의 위치에 다른 값이 있는지 확인하여 표시할 내용을 제어할 수 있는 조건 구성(if-then-else)이 있다.^[3]^[4]
TIFF 파일은 해시 값에 영향을 주지 않으면서 이미지의 다른 부분이 표시되도록 잘린 이미지를 포함할 수 있다.^[4]
PDF 파일은 색상 값을 사용하여 충돌 공격에 취약하다. 한 메시지의 텍스트는 배경과 혼합되는 흰색으로, 다른 메시지의 텍스트는 어두운 색상으로 표시하여 서명된 문서의 내용을 변경할 수 있다.^[4]

2. 2. 선택 접두사 충돌 공격

메르클-담고르드 해시 함수에 특정한 선택 접두사 충돌 공격은 충돌 공격의 확장된 형태이다. 공격자는 임의로 다른 두 개의 문서를 선택하고, 전체 문서가 동일한 해시 값을 갖도록 서로 다른 계산된 값을 추가할 수 있다. 이 공격은 일반적으로 더 어렵고, n 비트의 해시는 2^(n/2)+1 단계 내에 깨질 수 있지만, 고전적인 충돌 공격보다 훨씬 강력하다.

수학적으로 표현하면, 서로 다른 두 개의 접두사 ''p''₁, ''p''₂가 주어졌을 때, 공격은 ''hash''(''p''₁ ∥ ''s''₁) = ''hash''(''p''₂ ∥ ''s''₂) (여기서 ∥는 결합 연산)을 만족하는 두 개의 접미사 ''s''₁과 ''s''₂를 찾는다.

특정 해시 함수에 암호 분석을 적용하여 더욱 효율적인 공격이 가능하다. 2007년에는 MD5에 대한 선택된 접두사 충돌 공격이 발견되었으며, 이는 MD5 함수를 약 2⁵⁰번 평가해야 한다.^[5] 또한 이 논문에서는 충돌하는 해시 값을 가진 서로 다른 도메인 이름에 대한 두 개의 X.509 인증서를 시연했다. 이는 인증 기관이 한 도메인에 대한 인증서에 서명하도록 요청받을 수 있으며, 해당 인증서(특히 서명)를 사용하여 다른 도메인을 사칭하는 새로운 불량 인증서를 만들 수 있음을 의미한다.^[5]

2008년 12월, 일련의 보안 연구자들이 MD5 해시 함수에 대한 접두사 충돌 공격을 이용하여 인증 기관을 사칭하는 데 사용할 수 있는 위조된 X.509 서명 인증서를 발표했을 때 실제 충돌 공격이 발표되었다. 이는 공격자가 SSL로 보호되는 모든 웹사이트를 중간자 공격으로 사칭하여 모든 웹 브라우저에 내장된 인증서 검증 기능을 무력화하여 전자 상거래를 보호할 수 있음을 의미했다. 불량 인증서는 실제 기관에 의해 철회될 수 없으며, 임의의 위조된 만료 시간을 가질 수도 있다. MD5가 2004년에 매우 취약한 것으로 알려졌음에도 불구하고,^[1] 인증 기관은 2008년 12월에도 MD5로 검증된 인증서에 기꺼이 서명했으며,^[6] 2012년 5월에도 최소한 하나의 마이크로소프트 코드 서명 인증서가 여전히 MD5를 사용하고 있었다.

플레임 멀웨어는 손상된 MD5 알고리즘을 여전히 사용하고 있는 마이크로소프트 루트 인증서에 의해 구성 요소의 코드 서명을 스푸핑하기 위해 선택된 접두사 충돌 공격의 새로운 변형을 성공적으로 사용했다.^[7]^[8]

2019년, 연구자들은 컴퓨팅 복잡도가 2^66.9에서 2^69.4 사이이고 비용이 10만달러 미만인 SHA-1에 대한 선택된 접두사 충돌 공격을 발견했다.^[9]^[10] 2020년, 연구자들은 SHA-1에 대한 선택된 접두사 충돌 공격의 복잡성을 2^63.4로 줄였다.^[11]

2. 3. 해시 플러딩 공격

서비스 거부 공격의 일종인 '''해시 플러딩'''(Hash flooding, 일명 '''HashDoS'''^[15])은 해시 테이블 조회 시 최악의 경우(선형 탐사) 실행 시간을 악용하기 위해 해시 충돌을 사용한다.^[16] 이 공격은 2003년에 처음 설명되었다. 공격자는 서버에 동일한 값으로 해싱되는 여러 데이터 조각을 보내어 서버가 느린 조회를 수행하도록 시도한다. 해시 테이블에 사용되는 해시 함수의 주요 초점이 보안보다는 속도였기 때문에, 대부분의 주요 프로그래밍 언어가 영향을 받았다.^[17] 원래 발표된 지 10년이 지난 후에도 이 부류의 새로운 취약점이 계속 나타나고 있다.^[16]

해시 함수를 지나치게 복잡하게 만들지 않으면서 해시 플러딩을 방지하기 위해, 키가 알려지지 않는 한 충돌을 찾기 어렵다는 보안 목표를 가진 새로운 키 해시 함수가 도입되었다. 이전 해시보다 느릴 수 있지만, 암호화 해시보다 훨씬 쉽게 계산할 수 있다. 2021년 현재, 장-필립 오마송(Jean-Philippe Aumasson)과 다니엘 J. 번스타인(Daniel J. Bernstein)의 SipHash(2012)가 이 부류에서 가장 널리 사용되는 해시 함수이다.^[18] (응용 프로그램의 해시 테이블이 외부에서 제어할 수 없는 한, 키가 없는 "단순한" 해시는 안전하게 사용할 수 있다.)

블룸 필터를 채우는 유사한 공격을 (부분) 프리이미지 공격을 사용하여 수행할 수 있다.^[19]

3. 공격 시나리오

암호화 해시 함수의 많은 응용 분야는 충돌 저항에 의존하지 않으므로 충돌 공격은 해당 보안에 영향을 미치지 않는다. 예를 들어, HMAC는 취약하지 않다.^[12] 공격이 유용하려면 공격자는 해시 함수의 입력값을 제어할 수 있어야 한다.

일반적인 공격 시나리오는 다음과 같다.

# 맬러리는 동일한 해시 값을 가진 두 개의 다른 문서 A와 B를 생성한다. 즉, 충돌이 발생한다. 맬러리는 앨리스가 보낸 것처럼 위장하여 문서 B를 수락하도록 밥을 속이려고 한다.

# 맬러리는 '''앨리스에게 문서 A를 보낸다'''. 앨리스는 문서의 내용에 동의하고, 해당 해시를 서명한 후, 해당 서명을 맬러리에게 보낸다.

# 맬러리는 문서 A의 서명을 문서 B에 첨부한다.

# 맬러리는 그런 다음 '''서명과 문서 B를 밥에게 보낸다'''. 앨리스가 B에 서명했다고 주장하면서 말이다. 디지털 서명이 문서 B의 해시와 일치하기 때문에 밥의 소프트웨어는 대체를 감지할 수 없다.

2008년, 연구자들은 이 시나리오를 사용하여 MD5에 대한 선택된 접두사 충돌 공격으로 악성 인증 기관 인증서를 생성했다. 그들은 두 버전의 TLS 공개 키 인증서를 생성했는데, 그 중 하나는 합법적으로 보였고 RapidSSL 인증 기관에 서명을 위해 제출되었다. 동일한 MD5 해시를 가진 두 번째 버전에는 웹 브라우저가 임의의 다른 인증서를 발급하기 위한 합법적인 기관으로 받아들이도록 신호를 보내는 플래그가 포함되어 있었다.^[14]

3. 1. 디지털 서명

디지털 서명 알고리즘은 대량의 데이터를 효율적으로 서명할 수 없기 때문에, 대부분의 구현은 해시 함수를 사용하여 서명해야 하는 데이터의 양을 고정된 크기로 줄인다("압축"). 디지털 서명 방식은 기본 해시 함수가 실질적으로 깨지자마자 해시 충돌에 취약해지는 경우가 많다. 무작위(소금) 해싱과 같은 기술은 더 어려운 사전 이미지 공격을 요구함으로써 추가적인 시간을 벌 수 있다.^[13]

일반적인 공격 시나리오는 다음과 같다.

# 맬러리는 동일한 해시 값을 가진 두 개의 다른 문서 A와 B를 생성한다. 즉, 충돌이 발생한다. 맬러리는 앨리스가 보낸 것처럼 위장하여 문서 B를 수락하도록 밥을 속이려고 한다.

# 맬러리는 '''앨리스에게 문서 A를 보낸다'''. 앨리스는 문서의 내용에 동의하고, 해당 해시를 서명한 후, 해당 서명을 맬러리에게 보낸다.

# 맬러리는 문서 A의 서명을 문서 B에 첨부한다.

# 맬러리는 그런 다음 '''서명과 문서 B를 밥에게 보낸다'''. 앨리스가 B에 서명했다고 주장하면서 말이다. 디지털 서명이 문서 B의 해시와 일치하기 때문에 밥의 소프트웨어는 대체를 감지할 수 없다.

2008년, 연구자들은 이 시나리오를 사용하여 MD5에 대한 선택된 접두사 충돌 공격을 사용하여 악성 인증 기관 인증서를 생성했다. 그들은 두 버전의 TLS 공개 키 인증서를 생성했는데, 그 중 하나는 합법적으로 보였고 RapidSSL 인증 기관에 서명을 위해 제출되었다. 동일한 MD5 해시를 가진 두 번째 버전에는 웹 브라우저가 임의의 다른 인증서를 발급하기 위한 합법적인 기관으로 받아들이도록 신호를 보내는 플래그가 포함되어 있었다.^[14]

3. 2. 기타 공격

서비스 거부 공격의 일종인 '''해시 플러딩'''(Hash flooding, 일명 '''HashDoS'''^[15])은 해시 테이블 조회 시 최악의 경우(선형 탐사) 실행 시간을 악용하기 위해 해시 충돌을 사용한다.^[16] 이 공격은 2003년에 처음 설명되었다. 공격자는 서버에 동일한 값으로 해싱되는 여러 데이터 조각을 보내고, 서버가 느린 조회를 수행하도록 시도한다. 해시 테이블에 사용되는 해시 함수의 주요 초점이 보안보다는 속도였기 때문에, 대부분의 주요 프로그래밍 언어가 영향을 받았으며,^[17] 원래 발표된 지 10년이 지난 후에도 이 부류의 새로운 취약점이 계속 나타나고 있다.^[16]

해시 함수를 지나치게 복잡하게 만들지 않으면서 해시 플러딩을 방지하기 위해, 키가 알려지지 않는 한 충돌을 찾기 어렵다는 보안 목표를 가진 새로운 키 해시 함수가 도입되었다. 이전 해시보다 느릴 수 있지만, 암호화 해시보다 훨씬 쉽게 계산할 수 있다. 2021년 현재, 장-필립 오마송(Jean-Philippe Aumasson)과 다니엘 J. 번스타인(Daniel J. Bernstein)의 SipHash(2012)가 이 부류에서 가장 널리 사용되는 해시 함수이다.^[18] (응용 프로그램의 해시 테이블이 외부에서 제어할 수 없는 한, 키가 없는 "단순한" 해시는 안전하게 사용할 수 있다.)

(부분) 프리이미지 공격을 사용하여 블룸 필터를 채우는 유사한 공격을 수행할 수 있다.^[19]

4. 대응 방안

해시 테이블 조회 시 최악의 경우(선형 탐사) 실행 시간을 악용하기 위해 해시 충돌을 사용하는 서비스 거부 공격의 일종인 해시 플러딩(Hash flooding, 일명 '''HashDoS'''^[15])을 방지하기 위해, 키가 알려지지 않는 한 충돌을 찾기 어렵다는 보안 목표를 가진 새로운 키 해시 함수가 도입되었다. 이전 해시보다 느릴 수 있지만, 암호화 해시보다 훨씬 쉽게 계산할 수 있다. 2021년 현재, 장-필립 오마송(Jean-Philippe Aumasson)과 다니엘 J. 번스타인(Daniel J. Bernstein)의 SipHash(2012)가 이 부류에서 가장 널리 사용되는 해시 함수이다.^[18] (응용 프로그램의 해시 테이블이 외부에서 제어할 수 없는 한, 키가 없는 "단순한" 해시는 안전하게 사용할 수 있다.)

참조

_[1] 논문 Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD http://eprint.iacr.o[...] 2004-08-16
_[2] 간행물 On Collisions for MD5 http://www.win.tue.n[...] 2007-06
_[3] 웹사이트 Hash Collisions (The Poisoned Message Attack) http://th.informatik[...] 2010-03-27
_[4] 간행물 A Note on the Practical Value of Single Hash Collisions for Special File Formats http://csrc.nist.gov[...] 2017-01-04
_[5] 서적 Advances in Cryptology - EUROCRYPT 2007 2007-11-30
_[6] 웹사이트 Creating a rogue CA certificate http://www.phreedom.[...] 2009-10-07
_[7] 웹사이트 Microsoft releases Security Advisory 2718704 http://blogs.technet[...] Microsoft 2012-06-03
_[8] 웹사이트 CWI Cryptanalist Discovers New Cryptographic Attack Variant in Flame Spy Malware http://www.cwi.nl/ne[...] Centrum Wiskunde & Informatica 2012-06-09
_[9] 뉴스 SHA-1 collision attacks are now actually practical and a looming danger https://www.zdnet.co[...] 2019-05-13
_[10] 웹사이트 From Collisions to Chosen-Prefix Collisions Application to Full SHA-1 https://eprint.iacr.[...] 2019-05-06
_[11] 웹사이트 SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust https://eprint.iacr.[...] 2020-01-05
_[12] 웹사이트 Hash Collision Q&A http://www.cryptogra[...] Cryptography Research Inc. 2005-02-15
_[13] 문서 Randomized Hashing and Digital Signatures http://www.ee.techni[...]
_[14] 간행물 MD5 considered harmful today http://www.win.tue.n[...] 2008-12-30
_[15] 서적 2013 IEEE 20th International Conference on Web Services
_[16] 웹사이트 About that hash flooding vulnerability in Node.js... · V8 https://v8.dev/blog/[...]
_[17] 문서 Denial of service via algorithmic complexity attacks 2003
_[18] 웹사이트 SipHash: a fast short-input PRF https://131002.net/s[...] 2012-09-18
_[19] 학위논문 The Power of Evil Choices in Bloom Filters https://hal.inria.fr[...] INRIA Grenoble 2014-11-12
_[20] 웹인용 "Meaningful Collisions", attack scenarios for exploiting cryptographic hash collisions http://www.iaik.tugr[...] 2016-01-08

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com