충돌 저항성

충돌 저항성(collision resistance)은 암호학에서 해시 함수가 가져야 할 중요한 보안 성질 중 하나로, 서로 다른 두 입력값 x ≠ x′에 대해 H(x) = H(x′)가 되도록 하는 쌍을 찾는 것이 계산적으로 불가능해야 한다는 특성을 의미한다.

개요

암호학적 해시 함수는 임의의 길이의 입력을 고정된 길이의 해시값으로 변환하는 함수로, 다양한 보안 응용에서 사용된다. 해시 함수는 필연적으로 무한한 입력 공간을 유한한 출력 공간으로 압축하므로 이론적으로는 반드시 충돌이 존재한다. 그러나 실용적인 보안성을 위해서는 그러한 충돌을 찾기 어렵게 만드는 것이 중요하다. 이를 충돌 저항성이라고 하며, 해시 함수의 안전성을 평가하는 핵심 요소 중 하나이다.

수학적 정의

해시 함수 H: {0,1}^* → {0,1}ⁿ가 주어졌을 때, 다음 문제의 해를 찾는 것이 계산적으로 어려워야 한다:

• 충돌 문제: H(x) = H(x′)이면서 x ≠ x′인 두 입력 x, x′를 구하라.

충돌 저항성은 역상 저항성이나 제2 역상 저항성보다 더 강력한 조건으로 간주되며, 보안 프로토콜의 설계 시 가장 높은 수준의 해시 안전성을 요구할 때 필요하다.

관련 개념

암호학적 해시 함수는 다음 세 가지 주요 보안 성질을 갖추어야 한다:

• 역상 저항성(pre-image resistance): 주어진 해시값에 대해 원래 입력을 찾는 것이 어렵다.
• 제2 역상 저항성(second pre-image resistance): 주어진 입력에 대해 같은 해시값을 가지는 다른 입력을 찾기 어렵다.
• 충돌 저항성(collision resistance): 임의의 두 서로 다른 입력 쌍이 같은 해시값을 갖도록 하는 경우를 찾기 어렵다.

충돌 저항성을 만족하는 함수는 일반적으로 다른 두 성질도 함께 만족한다.

충돌 저항성의 중요성

• 디지털 서명에서 서명자는 메시지의 해시값만을 서명하기 때문에, 악의적인 사용자가 같은 해시값을 갖는 다른 메시지를 제시하면 서명이 위조될 수 있다.
• 인증 시스템에서 충돌을 이용한 인증 우회 공격이 가능하다면, 시스템의 무결성과 신뢰성이 훼손된다.
• 충돌 저항성이 깨진 해시 함수(SHA-1 등)는 더 이상 안전하지 않은 것으로 간주되며, 최신 시스템에서는 사용이 금지되거나 SHA-2, SHA-3 계열로 교체된다.

파이썬 예시

import hashlib

def sha256_hash(data):
    return hashlib.sha256(data.encode()).hexdigest()

print("openai:", sha256_hash("openai"))
print("openai2:", sha256_hash("openai2"))

• 위와 같이 서로 다른 입력 문자열은 서로 다른 해시값을 가지며, 해시 충돌을 인위적으로 발생시키는 것은 매우 어렵다. 해시 길이가 충분히 길다면(예: 256비트), 충돌을 찾는 데 필요한 시도 횟수는 생일 역설에 따라 약 2^(n/2)회가 된다.

같이 보기

• 암호학적 해시 함수
• 역상 저항성
• SHA-1
• SHA-2
• 디지털 서명

참고 문헌

• Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press.
• William Stallings, Cryptography and Network Security, Pearson.
• Xiaoyun Wang et al., "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD", Cryptology ePrint Archive, 2004.