역상 저항성

역상 저항성(pre-image resistance)은 암호학에서 해시 함수가 만족해야 할 기본적인 보안 성질 중 하나로, 주어진 해시값 h에 대해 이를 출력하는 입력값 x를 찾는 것이 계산적으로 불가능해야 한다는 특성을 의미한다.

개요

해시 함수는 임의의 길이의 입력을 고정된 길이의 해시값으로 압축하는 함수이며, 암호학적으로 안전한 해시 함수는 특정 보안 조건들을 만족해야 한다. 그 중 하나가 역상 저항성이며, 이는 다음과 같은 조건을 만족해야 함을 뜻한다:

• 주어진 해시값 h에 대해 H(x) = h를 만족하는 x를 찾는 것이 실질적으로 불가능해야 한다.

즉, 해시 함수의 출력값만 보고 입력값을 역으로 추론하거나 계산하는 것이 매우 어렵도록 설계되어야 한다.

수학적 정의

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

• 역상 문제: y = H(x)일 때, x를 구하라.

이 문제의 해결이 어렵다는 것을 기반으로 해시 함수는 다양한 암호 프로토콜에서 사용된다.

관련 개념

암호학적 해시 함수는 보통 다음 세 가지 보안 성질을 요구한다:

• 역상 저항성 (pre-image resistance)
• 제2 역상 저항성 (second pre-image resistance): 주어진 입력 x에 대해 H(x) = H(x′)이면서 x ≠ x′인 x′를 찾는 것이 어렵다.
• 충돌 저항성 (collision resistance): 서로 다른 두 입력 x ≠ x′에 대해 H(x) = H(x′)가 되도록 하는 쌍을 찾는 것이 어렵다.

역상 저항성은 가장 기본적인 성질로, 다른 두 성질의 전제가 된다.

응용

역상 저항성은 다음과 같은 보안 응용에서 핵심적인 역할을 한다.

• 비밀번호 저장: 사용자 입력 비밀번호를 해시값으로 저장하여 원본 유출을 방지
• 디지털 서명: 서명 대상 메시지의 해시값만을 서명함으로써 위변조 방지
• 블록체인: 작업 증명(PoW)에서 특정 해시값에 해당하는 입력을 찾는 문제로 활용됨
• 인증 및 무결성 검증: 메시지 인증 코드(MAC), 해시 기반 전자서명

파이썬 예시

import hashlib

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

h = hash_value("openai")
print("해시값:", h)

• 위 예제에서 출력된 해시값만으로 원래 입력 문자열("openai")을 알아내는 것은 현실적으로 불가능해야 하며, 이것이 역상 저항성이다.

같이 보기

• 암호학적 해시 함수
• 충돌 저항성
• 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.