충돌공격

Collision attack

암호학에서, 암호 해시에 대한 충돌 공격은 동일한 해시 값, 즉 해시 충돌을 생성하는 두 개의 입력을 찾으려고 시도합니다.이는 특정 대상 해시 값이 지정되는 역이미지 공격과는 대조적입니다.

충돌 공격에는 크게 두 가지 유형이 있습니다.

고전적 충돌 공격
해시(m) = 해시(m)와 같은 두 개의 다른 메시지 m과 m을 찾습니다.

일반적으로:

선택 프리픽스 충돌 공격
두 개의 서로 다른 접두사 p와 p가 주어졌을 때, 두 개의 접미사와 s를 찾아 해시(p ∥s) = hash(p ∥s)를 나타내고, 여기서 ∥는 연결 연산을 나타냅니다.

고전적 충돌 공격

대칭키 암호가 무차별 대입 공격에 취약한 것처럼 모든 암호 해시 함수는 생일 공격을 이용한 충돌에 본질적으로 취약합니다.생일 문제로 인해 이러한 공격은 단순한 무력보다 훨씬 빠릅니다.n비트의 해시는 2개의n/2 시간 단계(해시 함수의 평가)로 분해할 수 있습니다.

수학적으로 표현하자면, 충돌 공격은 해시(m1) = 해시(m2)와 같은 두 개의 다른 메시지 m1과 m2를 찾습니다.고전적인 충돌 공격에서 공격자는 두 메시지의 내용에 대한 제어권이 없지만 알고리즘에 의해 임의로 선택됩니다.

특정 해시 함수에 암호 분석을 사용함으로써 보다 효율적인 공격이 가능합니다.충돌 공격이 발견되고 생일 공격보다 더 빠른 것으로 확인되면 해시 함수는 종종 "부러진"으로 비난됩니다.NIST 해시 함수 경쟁은 매우 일반적으로 사용되는 두 개의 해시 함수 MD5[1] 및 SHA-1에 대한 공개된 충돌 공격에 의해 크게 유도되었습니다.MD5에 대한 충돌 공격이 매우 개선되어 2007년 현재 일반 컴퓨터에서는 불과 몇 초밖에 걸리지 않습니다.[2]이러한 방식으로 생성된 해시 충돌은 일반적으로 일정한 길이이며 대부분 구조화되지 않은 상태이므로 광범위한 문서 형식이나 프로토콜을 공격하는 데 직접 적용할 수 없습니다.

그러나 여러 형식으로 존재하는 동적 구성 요소를 사용하여 해결할 수 있습니다.이런 방식으로, 동일한 해시 값을 갖기 위해 가능한 한 유사한 두 개의 문서가 생성됩니다.하나의 문서는 서명된 기관에 표시되고, 서명은 다른 파일에 복사될 수 있습니다.이러한 악의적인 문서는 동일한 문서에 두 개의 다른 메시지를 포함하지만 파일을 약간 변경하여 조건부로 표시합니다.

  • 포스트스크립트나 마이크로소프트 워드의 매크로 같은 문서 형식에는 조건부 구성이 있습니다.[3][4]표시되는 내용을 제어하기 위해 파일의 위치에 하나 또는 다른 값이 있는지 여부를 테스트할 수 있는 (if-then-else).
  • TIFF 파일에는 잘라낸 이미지가 포함될 수 있으며, 해시 값에 영향을 주지 않고 이미지의 다른 부분이 표시됩니다.[4]
  • PDF 파일은 색상 값(한 메시지의 텍스트는 배경에 혼합된 흰색으로 표시되고 다른 메시지의 텍스트는 어두운 색으로 표시됨)을 사용하여 충돌 공격에 취약하며, 이를 변경하여 서명된 문서의 내용을 변경할 수 있습니다.[4]

선택 프리픽스 충돌 공격

충돌 공격의 확장은 Merkle-Damgård 해시 함수에 특화된 선택-프리픽스 충돌 공격입니다.이 경우 공격자는 임의로 다른 두 개의 문서를 선택한 다음 계산된 값을 추가하여 전체 문서가 동일한 해시 값을 가질 수 있습니다.이 공격은 일반적으로 더 단단하며, n비트의 해시는 2번의(n/2)+1 시간 단계로 깨질 수 있지만, 고전적인 충돌 공격보다 훨씬 더 강력합니다.

수학적으로 표현하자면, 두 개의 서로 다른 접두사 p, p가 주어졌을 때, 공격은 해시(p ∥s) = 해시(p ∥s)(여기서 ∥는 연결 연산)와 같은 두 개의 접미사와 s를 찾습니다.

특정 해시 함수에 암호 분석을 사용함으로써 보다 효율적인 공격이 가능합니다.2007년에 MD5에 대한 선택된 프리픽스 충돌 공격이 발견되었으며, MD5 기능에 대한 약 2번의50 평가가 필요했습니다.이 논문은 또한 충돌하는 해시 값을 가진 서로 다른 도메인 이름에 대한 두 개의 X.509 인증서를 보여줍니다.즉, 한 도메인에 대한 인증서에 서명하도록 인증 기관에 요청한 다음 해당 인증서(특히 해당 서명)를 사용하여 다른 도메인을 가장하는 새 로그 인증서를 만들 수 있습니다.[5]

2008년 12월 보안 연구자 그룹이 MD5 해시 함수에 대한 접두사 충돌 공격을 이용하여 인증 기관을 사칭하는 데 사용될 수 있는 위조된 X.509 서명 인증서를 발표하면서 실제 충돌 공격이 발표되었습니다.이는 공격자가 SSL 보안 웹 사이트를 중간자로 가장하여 모든 웹 브라우저에 구축된 인증서 유효성 검사를 전복하여 전자 상거래를 보호할 수 있음을 의미했습니다.악성 인증서는 실제 사용자가 취소할 수 없으며 임의로 위조된 만료 시간을 가질 수도 있습니다.2004년 MD5가 매우 취약한 것으로 알려졌지만,[1] 2008년 12월에도 인증 당국은 여전히 MD5 인증 인증서에 서명할 의사가 있었고,[6] 2012년 5월에도 적어도 하나의 Microsoft 코드 서명 인증서가 여전히 MD5를 사용하고 있었습니다.

Flame 멀웨어는 선택된 프리픽스 충돌 공격의 새로운 변형을 성공적으로 사용하여 여전히 손상된 MD5 알고리즘을 사용하는 마이크로소프트 루트 인증서를 통해 구성 요소의 코드 서명을 스푸핑했습니다.[7][8]

2019년, 연구원들은 SHA-1에 대한 선택된 프리픽스 충돌 공격을 발견했는데, 이 공격은 계산 복잡도가66.969.4 2에서 2 사이이며 비용이 10만 달러 미만입니다.[9][10] 2020년, 연구원들은 SHA-1에 대한 선택된 프리픽스 충돌 공격의 복잡성을 2로63.4 줄였습니다.

공격 시나리오

암호화 해시 함수의 많은 응용 프로그램은 충돌 저항성에 의존하지 않으므로 충돌 공격은 보안에 영향을 미치지 않습니다.예를 들어 HMAC는 취약하지 않습니다.[12]공격이 유용하려면 공격자가 해시 함수에 대한 입력을 제어하고 있어야 합니다.

디지털 서명

디지털 서명 알고리즘은 많은 양의 데이터에 효율적으로 서명할 수 없기 때문에 대부분의 구현에서는 서명해야 하는 데이터의 양을 일정한 크기로 줄이기 위해 해시 함수를 사용합니다.디지털 서명 체계는 기본 해시 함수가 실질적으로 고장 나자마자 해시 충돌에 취약해지는 경우가 많습니다. 랜덤화(염화) 해싱과 같은 기술은 더 강력한 역상 공격을 요구함으로써 추가 시간을 벌 수 있습니다.[13]

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

  1. Mallory는 동일한 해시 값, 즉 충돌을 갖는 두 개의 다른 문서 A와 B를 만듭니다.맬로리는 표면적으로 앨리스가 보낸 서류 B를 받아들이도록 밥을 속이려고 합니다.
  2. 맬로리는 문서 A를 앨리스에게 보내고 앨리스는 문서가 말하는 것에 동의하고 해시에 서명한 후 맬로리에게 서명을 보냅니다.
  3. 맬로리는 A 문서에서 B 문서에 서명을 첨부합니다.
  4. 그 후 맬로리는 앨리스가 B에 서명했다고 주장하는 서명과 서류 B를 밥에게 보냅니다.디지털 서명이 문서 B의 해시와 일치하기 때문에 Bob의 소프트웨어는 대체를 감지할 수 없습니다.[citation needed]

2008년에 연구원들은 이 시나리오를 사용하여 MD5에 대한 선택된 프리픽스 충돌 공격을 사용하여 악성 인증 기관 인증서를 만들었습니다.그들은 두 가지 버전의 TLS 공개 키 인증서를 만들었고, 그 중 하나는 합법적으로 보였고 Rapid에 의해 서명을 위해 제출되었습니다.SSL 인증 기관.같은 MD5 해시를 가진 두 번째 버전은 웹 브라우저가 임의의 다른 인증서를 발급하는 합법적인 권한으로 받아들이도록 신호하는 플래그를 포함하고 있었습니다.[14]

해시 플러딩

해시 플러딩(HashDoS라고도[15] 함)은 해시 충돌을 사용하여 해시 테이블 룩업의 최악의 경우(선형 프로브) 런타임을 이용하는 서비스 거부 공격입니다.[16]그것은 원래 2003년에 묘사되었습니다.공격자는 이러한 공격을 실행하기 위해 동일한 값으로 해시된 여러 데이터를 서버에 전송한 다음 서버가 느린 조회를 수행하도록 시도합니다.해시 테이블에 사용된 해시 함수의 주요 초점이 보안 대신 속도였기 때문에 대부분의 주요 프로그래밍 언어가 영향을 받았으며,[17] 이 클래스의 새로운 취약점은 원래 프레젠테이션 이후 10년이 지난 후에도 여전히 나타났습니다.[16]

해시 함수를 지나치게 복잡하게 만들지 않고 해시 플러딩을 방지하기 위해 키를 알 수 없는 한 충돌을 찾기 어렵다는 보안 목표와 함께 새로운 키를 가진 해시 함수가 도입되었습니다.이전 해시보다 속도가 느릴 수 있지만 암호화 해시보다 계산이 훨씬 쉽습니다.2021년 현재 Daniel J. Bernstein의 SipHash(2012)는 이 클래스에서 가장 널리 사용되는 해시 함수입니다.[18](프로그램의 해시 테이블이 외부에서 제어할 수 없는 한 키가 없는 "단순" 해시는 안전하게 사용할 수 있습니다.)

(부분) 역상 공격을 사용하여 Bloom 필터를 채우는 유사한 공격을 수행할 수 있습니다.[19]

참고문헌

  1. ^ a b Xiaoyun Wang, Dengguo Feng, Shuejia Lai, Hongbo Yu: 해시 함수 MD4, MD5, HAVAL-128 및 RIPEMD, Cryptology ePrint Archive Report 2004/199, 2004년 8월 17일 개정.2008년 7월 27일 회수.
  2. ^ M.M.J. Stevens (June 2007). "On Collisions for MD5" (PDF). [...] we are able to find collisions for MD5 in about 224.1 compressions for recommended IHVs which takes approx. 6 seconds on a 2.6GHz Pentium 4. {{cite journal}}:저널 요구사항 인용 journal=(도움말)
  3. ^ Magnus Daum; Stefan Lucks. "Hash Collisions (The Poisoned Message Attack)". Eurocrypt 2005 rump session. Archived from the original on 2010-03-27.
  4. ^ a b c Max Gebhardt; Georg Illies; Werner Schindler (4 January 2017). "A Note on the Practical Value of Single Hash Collisions for Special File Formats" (PDF). {{cite journal}}:저널 요구사항 인용 journal=(도움말)
  5. ^ Marc Stevens; Arjen Lenstra; Benne de Weger (2007-11-30). "Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities". Advances in Cryptology - EUROCRYPT 2007. Lecture Notes in Computer Science. Vol. 4515. p. 1. Bibcode:2007LNCS.4515....1S. doi:10.1007/978-3-540-72540-4_1. ISBN 978-3-540-72539-8.
  6. ^ Alexander Sotirov; et al. (2008-12-30). "Creating a rogue CA certificate". Archived from the original on 2012-04-18. Retrieved 2009-10-07.
  7. ^ "Microsoft releases Security Advisory 2718704". Microsoft. 3 June 2012. Archived from the original on 7 June 2012. Retrieved 4 June 2012.
  8. ^ Marc Stevens (7 June 2012). "CWI Cryptanalist Discovers New Cryptographic Attack Variant in Flame Spy Malware". Centrum Wiskunde & Informatica. Retrieved 9 June 2012.
  9. ^ Catalin Cimpanu (2019-05-13). "SHA-1 collision attacks are now actually practical and a looming danger". ZDNet.
  10. ^ Gaëtan Leurent; Thomas Peyrin (2019-05-06). "From Collisions to Chosen-Prefix Collisions Application to Full SHA-1" (PDF).
  11. ^ Gaëtan Leurent; Thomas Peyrin (2020-01-05). "SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust" (PDF).
  12. ^ "Hash Collision Q&A". Cryptography Research Inc. 2005-02-15. Archived from the original on 2008-07-17. Because of the way hash functions are used in the HMAC construction, the techniques used in these recent attacks do not apply
  13. ^ Shai Halevi and Hugo Krawczyk, 무작위 해시 및 디지털 서명
  14. ^ Alexander Sotirov; Marc Stevens; Jacob Appelbaum; Arjen Lenstra; David Molnar; Dag Arne Osvik; Benne de Weger (30 December 2008). MD5 considered harmful today. Chaos Communication Congress 2008.
  15. ^ Falkenberg, Andreas; Mainka, Christian; Somorovsky, Juraj; Schwenk, Jörg (2013). "A New Approach towards DoS Penetration Testing on Web Services". 2013 IEEE 20th International Conference on Web Services. pp. 491–498. doi:10.1109/ICWS.2013.72. ISBN 978-0-7695-5025-1. S2CID 17805370.
  16. ^ a b "About that hash flooding vulnerability in Node.js... · V8". v8.dev.
  17. ^ 스콧 A.크로스비와 댄 S. 왈락.2003. 알고리즘 복잡도 공격을 통한 서비스 거부USENIX 보안 심포지엄 제12회 회의록 - 12권(SSYM'03), 12권USENIX 협회, 버클리, 캘리포니아, 미국, 3-3
  18. ^ Jean-Philippe Aumasson & Daniel J. Bernstein (2012-09-18). "SipHash: a fast short-input PRF" (PDF).
  19. ^ Gerbet, Thomas; Kumar, Amrit; Lauradoux, Cédric (12 November 2014). The Power of Evil Choices in Bloom Filters (report). INRIA Grenoble.

외부 링크