프리이미지 공격

Preimage attack

암호학에서 암호 해시함수에 대한 프리이미지 공격은 특정 해시 값을 갖는 메시지를 찾으려고 한다. 암호해시함수는 그 프리이미지(가능한 입력의 집합)에 대한 공격에 저항해야 한다.

공격의 맥락에서 두 가지 유형의 프리이미지 저항이 있다.

  • 사전 이미지 저항: 기본적으로 사전 지정된 모든 출력에 대해 해당 출력에 해시되는 입력을 찾는 것은 계산상 불가능하며, 예를 들어 y를 고려할 때 h(x) = y와 같은 x를 찾는 것은 어렵다.[1]
  • 두 번째 프리이미지 저항: 특정 입력에 대해 동일한 출력을 생성하는 다른 입력을 찾는 것은 계산상 불가능하다. 즉, x가 주어지면 h(x) = h(x) = h(x)[1]인 두 번째 프리이미지 x ≠ x를 찾는 것은 어렵다.

이것들은 충돌 저항과 비교할 수 있는데, 어떤 두 개의 뚜렷한 입력 x, 즉 같은 출력에 대한 해시 x를 찾는 것이 계산상 불가능하다는 것이다. 즉, h(x) = h(x)[1]와 같은 것이다.

충돌 저항은 2차 사전 이미지 저항을 의미하지만 사전 이미지 저항을 보장하지는 않는다.[1] 반대로 두 번째 프리이미지 공격은 충돌 공격을 내포하고 있다(x′ 외에 x는 이미 처음부터 바로 알려져 있기 때문에).

적용된 프리이미지 공격

정의에 따르면 이상적인 해시함수는 첫 번째 또는 두 번째 프리이미지를 계산하는 가장 빠른 방법이 흉포한 공격을 통해서이다. n비트 해시의 경우, 이 공격은 시간 복잡성 2를n 가지는데, 이는 n = 128비트의 일반적인 출력 크기에 비해 너무 높은 것으로 간주된다. 만약 그러한 복잡성이 적에 의해 달성될 수 있는 최선의 것이라면, 해시함수는 프리이미지 내성으로 간주된다. 그러나 양자 컴퓨터가 computers2n = 2에서n/2 구조화된 프리이미지 공격을 한다는 일반적인 결과가 있는데, 이것은 또한 두 번째 프리이미지[2] 공격과 따라서 충돌 공격을 함축하기도 한다.

더 빠른 프리이미지 공격은 특정 해시함수를 암호화함으로써 찾을 수 있으며, 그 함수에 특유하다. 일부 유의미한 프리이미지 공격은 이미 발견되었지만, 아직 실용적이지 않다. 만약 실제적인 사전 이미지 공격이 발견된다면, 그것은 많은 인터넷 프로토콜에 큰 영향을 미칠 것이다. 이 경우 "실용적"은 합리적인 양의 자원을 가지고 공격자에 의해 실행될 수 있다는 것을 의미한다. 예를 들어, 수조 달러의 비용이 들고 원하는 해시 값 하나 또는 메시지 하나를 미리 이미지화하는 데 수십 년이 걸리는 사전 이미징 공격은 실용적이지 않다. 수천 달러가 들고 몇 주가 걸리는 공격은 매우 실용적일 수 있다.

MD5와 SHA-1에 대해 현재 알려진 모든 실제 또는 거의 실제적인 공격은[3][4][5] 충돌 공격이다[citation needed]. 일반적으로 충돌 공격은 어떤 설정값(충돌에 두 값을 사용할 수 있음)에 의해 제한되지 않기 때문에 프리이미지 공격보다 탑재하기가 쉽다. 프리이미지 공격과는 대조적으로, 흉포력 충돌 공격의 시간 복잡성은 2에n/2 불과하다.

제한된 프리이미지 공간 공격

이상적인 해시함수에 대한 첫 번째 프리이미지 공격의 계산적 불가능성은 가능한 해시 입력의 집합이 무차별적인 힘 검색에 비해 너무 크다고 가정한다. 그러나 주어진 해시 값이 상대적으로 작거나 어떤 식으로든 우도에 의해 정렬된 입력 집합에서 생성된 것으로 알려진 경우, 무차별적인 힘 검색이 효과적일 수 있다. 실용성은 입력 세트 크기와 해시함수의 계산 속도나 비용에 따라 달라진다.

일반적인 예로는 해시를 사용하여 암호 유효성 검사 데이터를 인증에 저장하는 것이 있다. 사용자 암호의 일반 텍스트를 저장하는 대신, 접근 제어 시스템은 암호의 해시를 저장한다. 사용자가 액세스를 요청하면 제출하는 암호가 해시되어 저장된 값과 비교된다. 저장된 유효성 검사 데이터를 도난당하면 도둑은 암호가 아닌 해시 값만 갖게 된다. 그러나 대부분의 사용자는 예측 가능한 방법으로 비밀번호를 선택하고 많은 비밀번호는 프리이미지 공격에 대해 해시가 보안 등급이라 하더라도 빠른 해시를 사용하면 가능한 모든 조합을 테스트할 수 있을 정도로 충분히 짧다.[6] 검색 속도를 늦추기 위해 키 파생 함수라고 불리는 특별한 해시가 만들어졌다. 암호 크래킹을 참조하십시오.

참고 항목

  • 생일 공격
  • 암호해시함수
  • 해시함수 보안 요약
  • 레인보우 테이블
  • 랜덤 오라클
  • RFC4270: 인터넷 프로토콜의 암호해시 공격

참조

  1. ^ a b c d Rogaway, P.; Shrimpton, T. (2004). "Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance" (PDF). Fast Software Encryption. Lecture Notes in Computer Science. Springer-Verlag. 3017: 371–388. doi:10.1007/978-3-540-25937-4_24. ISBN 978-3-540-22171-5. Retrieved 17 November 2012.
  2. ^ Daniel J. Bernstein (2010-11-12). "Quantum attacks against Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD, and Skein" (PDF). University of Illinois at Chicago. Retrieved 2020-03-29.
  3. ^ Bruce Morton, Clayton Smith (2014-01-30). "Why We Need to Move to SHA-2". Certificate Authority Security Council.{{cite web}}: CS1 maint: 작성자 매개변수 사용(링크)
  4. ^ "MD5 and Perspectives". 2009-01-01.
  5. ^ "Google Online Security Blog: Announcing the first SHA1 collision". Retrieved 2017-02-23.
  6. ^ Goodin, Dan (2012-12-10). "25-GPU cluster cracks every standard Windows password in <6 hours". Ars Technica. Retrieved 2020-11-23.