충돌 저항

Collision resistance

암호학에서, 충돌 저항은 암호 해시함수의 속성이다: 해시함수 H는 동일한 출력에 해시함수 2개를 찾기 어렵다면, 즉, b b 그러나 H(a) = H(b)인 a와 b의 입력 2개를 찾기 어렵다면 충돌에 강하다.[1]: 136 비둘기구멍 원리는 출력보다 입력이 많은 해시함수는 반드시 그러한 충돌을 갖는다는 것을 의미한다.[1]: 136 해시함수를 찾기가 어려울수록 암호화된 방식으로 더 안전하다.

"생일의 역설"은 충돌 저항에 상한을 둔다. 해시함수가 N비트의 출력을 생성하는 경우, 무작위 입력에서 해시 연산을 2비트N/2(또는 만 계산하는 공격자는 일치하는 출력 두 개를 찾을 가능성이 있다. 만약 이 흉포한 공격보다 쉬운 방법이 있다면, 일반적으로 해시함수의 결함으로 간주된다.[2]

암호 해시함수는 보통 충돌 내성을 갖도록 설계된다. 그러나 한때 충돌 내성이 있다고 여겨졌던 해시함수는 나중에 많이 깨졌다. 특히 MD5와 SHA-1은 충돌 발견을 위한 짐승 같은 힘보다 더 효율적인 기법을 발표했다.[3][4] 그러나 일부 해시함수는 적어도 어떤 어려운 수학 문제(정수 인자화 또는 이산 로그 등)만큼 충돌을 찾는 것이 어렵다는 증거를 가지고 있다. 그 기능들은 확실히 안전하다고 불린다.[2]

정의

함수 {hk : {0, 1}m(k) → {0, 1} → {0, 1}l(k)은(는) 어떤 k에 대해서도k m(k) > l(k)가 입력 문자열을 압축하고, 모든k h는 주어진 k에 대해 다항식 시간 내에 계산할 수 있지만, 확률론적 다항식 알고리즘 A에 대해서는 충돌 방지 해시함수의 계열이다.

Pr [k ← G(1n), (x12, x) ← A(k, 1n) s.t. x x1 x 그러나2 hk(x1) = hk(x2)] < negl(n), (유리)

여기서 negl(·)은 일부 무시해도 될 함수를 나타내며 n은 보안 매개변수다.[5]

이론적 근거

충돌 저항은 여러 가지 이유로 바람직하다.

  • 일부 디지털 서명 시스템에서는 당사자가 문서의 해시에 공개 키 서명을 게시하여 문서를 증명한다. 만약 같은 해쉬로 두 개의 문서를 만들 수 있다면, 공격자는 한 사람에게 증명할 당사자를 얻은 다음 다른 사람에게 증명했다고 주장할 수 있다.
  • 일부 분산 콘텐츠 시스템에서는, 당사자들이 동일한 버전을 가지고 있는지 확인하기 위해 파일의 암호 해시를 비교한다. 같은 해쉬로 두 개의 파일을 만들 수 있는 공격자는 사용자가 실제로 그렇지 않은 경우 동일한 버전의 파일을 가지고 있다고 믿도록 사용자를 속일 수 있다.

참고 항목

참조

  1. ^ a b Goldwasser, S. and Bellare, M. "Cryptography on Cryptography". MIT, 1996-2001년 암호학 여름 강좌
  2. ^ a b 패스, R. "렉처 21: 충돌방지 해시함수와 일반 디지털 서명 방식" 코넬 대학교 암호학 강좌, 2009
  3. ^ Xiaoyun Wang; Hongbo Yu. "How to Break MD5 and Other Hash Functions" (PDF). Archived from the original (PDF) on 2009-05-21. Retrieved 2009-12-21.
  4. ^ Xiaoyun Wang; Yiqun Lisa Yin; Hongobo Yu. "Finding Collisions in the Full SHA-1" (PDF). {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
  5. ^ Dodis, Yevgeniy. "Lecture 12 of Introduction to Cryptography" (PDF). Retrieved 3 January 2016., def 1.