암호화 해시 함수

이 강의에서는 빠른 검증과 인증에 광범위하게 사용되는 암호화 해시 함수를 살펴봅니다.

강의가 끝나면 다음 내용을 다루게 됩니다:

• 암호화 해시 함수란 무엇인가
• 해시 함수 사용을 보여 주는 Python 코드 예제
• 암호화 해싱의 응용 분야
• 암호화 해싱의 보안
• 고전 컴퓨터와 양자 컴퓨터 양쪽으로부터의 위협

암호화 해싱 소개

해시 함수는 기밀성을 유지하면서 검증을 가능하게 해 주는 유용한 암호화 구성 요소입니다. 이러한 특성 덕분에 해시 함수는 해시 기반 메시지 인증 코드(HMAC) 및 디지털 서명과 같은 데이터 인증 및 무결성 메커니즘의 중요한 구성 요소를 이룹니다. 이 글에서는 암호화 해시 함수의 기본 개념과 보안 고려 사항을 설명하고, 양자 컴퓨팅의 등장으로 인한 잠재적 취약점을 살펴봅니다.

해시 함수의 기본 원리와 설계

인증과 무결성 검증을 저비용으로, 그리고 검증을 수행하는 당사자에게 개인 정보를 노출하지 않고 수행해야 하는 상황이 많습니다.

예를 들어, 원격 서버에서 소프트웨어를 다운로드할 때는 다운로드된 소프트웨어가 원래 개발자가 만든 이후 수정되지 않았는지 효율적으로 확인하는 메커니즘이 필요합니다. 마찬가지로, 웹 애플리케이션의 사용자를 인증할 때는 실제 비밀번호를 물리적으로 저장하거나 전송하지 않아도 되는 메커니즘이 바람직합니다. 비밀번호를 직접 다루면 기밀성이 침해될 수 있기 때문입니다.

암호화 해시 함수(CHF)는 이러한 요구를 효율적이고 안전하게 충족시킵니다.

근본적으로, 암호화 해시 함수는 임의 길이의 입력(또는 메시지)을 받아 n비트의 고정 크기 문자열을 출력으로 반환합니다. CHF의 출력은 *다이제스트(digest)*라고도 합니다. 유용한 CHF는 다음과 같은 몇 가지 핵심 속성을 만족해야 합니다:

1. 균일성(Uniformity): CHF가 생성하는 다이제스트는 균일하게 분포되어 있어야 하며 무작위처럼 보여야 합니다. 이는 출력이 입력에 관한 정보를 누설하지 않도록 하기 위함입니다.
2. 결정성(Determinism): 주어진 입력에 대해 CHF는 항상 동일한 다이제스트를 생성해야 합니다. 즉, 결정적이어야 합니다.
3. 비가역성(Irreversibility): CHF는 일방향 함수로, 다이제스트가 주어졌을 때 해싱을 역산하여 입력을 얻는 것이 불가능해야 합니다.
4. 근사 단사성(Approximate injectivity): CHF는 다대일 함수이지만, 일대일 함수처럼 보여야 합니다. 이는 엄청난 출력 공간 크기와 함께 입력의 미세한 변화가 전혀 다른 다이제스트를 만들어 내는 눈사태 효과(avalanche effect)를 결합함으로써 달성됩니다. 이 특성을 근사 단사성이라고 합니다.

이를 바탕으로, 데이터의 다이제스트를 원본의 다이제스트와 비교하여 해당 데이터가 원본과 동일한지 검증할 수 있습니다.

• 두 다이제스트가 일치하면, 데이터가 원본과 동일하다는 것을 높은 확률로 확신할 수 있습니다.
• 다이제스트가 다르면, 데이터가 변조되었거나 진본이 아님을 확실히 알 수 있습니다.

CHF 다이제스트 자체는 데이터의 실제 내용이나 원본을 드러내지 않으므로, 개인 정보를 보호하면서도 검증을 가능하게 합니다.

수학적 설명

해시 함수 $H$는 다음과 같이 정의할 수 있습니다:

$H : Σ^* \rightarrow \{0,1\}^n$

여기서 $Σ^*$는 임의 길이의 이진 문자열을 포함하는 모든 가능한 문자열의 집합입니다.

$H$의 입력 도메인 $Σ^*$의 크기는 무한한 반면 공역(co-domain) $\{0,1\}^n$의 크기는 유한하다는 사실은, $H$가 무한히 많은 입력을 임의의 n비트 문자열로 매핑하는 다대일 함수임을 의미합니다.

균일성과 결정성이라는 속성은 암호화 해싱의 랜덤 오라클 모델 안에서 잘 설명됩니다.

SHA-256을 이용한 Python 암호화 해싱 예제

이 간단한 예제는 cryptography Python 라이브러리가 제공하는 인기 있는 SHA-256 알고리즘을 사용한 암호화 해싱을 보여 줍니다. 먼저, 평문의 미세한 차이가 해시 다이제스트에 매우 큰 차이를 초래한다는 것을 보여 줍니다.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

# Begin by importing some necessary modules
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes

# Helper function that returns the number of characters different in two strings
def char_diff(str1, str2):
    return sum(str1[i] != str2[i] for i in range(len(str1)))

# Messages to be hashed
message_1 = b"Buy 10000 shares of WXYZ stock now!"
message_2 = b"Buy 10000 shares of VXYZ stock now!"

print(f"The two messages differ by { char_diff(message_1, message_2)} characters")

The two messages differ by 1 characters

두 메시지는 정확히 한 글자가 다릅니다.

다음으로, 해싱 과정을 활성화하기 위해 hash 객체를 인스턴스화합니다. 이 과정에서는 update와 finalize 두 메서드를 호출합니다.

SHA-256 CHF의 눈사태 효과로 인해, 입력 메시지에서 한 글자 차이가 매우 다른 두 다이제스트를 만들어 낸다는 것을 확인할 수 있습니다.

# Create new SHA-256 hash objects, one for each message
chf_1 = hashes.Hash(hashes.SHA256(), backend=default_backend())
chf_2 = hashes.Hash(hashes.SHA256(), backend=default_backend())

# Update each hash object with the bytes of the corresponding message
chf_1.update(message_1)
chf_2.update(message_2)

# Finalize the hash process and obtain the digests
digest_1 = chf_1.finalize()
digest_2 = chf_2.finalize()

# Convert the resulting hash to hexadecimal strings for convenient printing
digest_1_str = digest_1.hex()
digest_2_str = digest_2.hex()

# Print out the digests as strings
print(f"digest-1: {digest_1_str}")
print(f"digest-2: {digest_2_str}")

print(f"The two digests differ by { char_diff(digest_1_str, digest_2_str)} characters")

digest-1: 6e0e6261b7131bd80ffdb2a4d42f9d042636350e45e184b92fcbcc9646eaf1e7
digest-2: 6b0abb368c3a1730f935b68105e3f3ae7fd43d7e786d3ed3503dbb45c74ada46
The two digests differ by 57 characters

암호화 해싱의 응용

CHF의 고유한 특성은 다양한 응용 분야에 적합합니다:

• 데이터 무결성 검사: 해시 함수를 사용하여 데이터 집합에 대한 체크섬을 만들 수 있습니다. 의도적이든 아니든 데이터가 수정되면 다른 체크섬이 생성되어 시스템이나 사용자에게 변경 사실을 알립니다. 체크섬은 일반적으로 원본 데이터보다 훨씬 작아 체크섬 비교가 매우 빠릅니다.

그림 1. 데이터 무결성을 위한 보안 해싱

• 디지털 서명: 암호화 해시는 디지털 서명의 기능에 필수적입니다. 디지털 서명은 암호화된 해시 메시지를 비교하여 개인 정보를 보호하면서 진위성과 무결성을 확인합니다.

그림 2. 디지털 서명

• 블록체인과 암호화폐: Bitcoin과 같은 암호화폐는 특히 거래 무결성 확보와 *작업 증명(proof of work)*과 같은 합의 메커니즘 구현에 CHF를 대폭 활용합니다.

암호화 해싱의 보안

CHF의 보안은 일반적으로 두 가지 유형의 공격, 즉 사전 이미지 공격과 충돌 공격에 대한 저항성을 기준으로 평가됩니다.

사전 이미지 저항성

*사전 이미지 저항성(Pre-image resistance)*이란, 다이제스트가 주어졌을 때 입력을 찾는 것이 불가능해야 함을 의미합니다.

이는 CHF의 일방향 속성과 관련이 있습니다.

잘 설계된 CHF는 사전 이미지 공격을 시도하는 당사자가 시간 복잡도 $2^n$의 무차별 대입(brute force) 방법 외에 더 나은 선택지가 없도록 설계됩니다.

수학적 세부 사항

CHF $H$와 다이제스트 $g$가 주어졌을 때, $H(m) = g$를 만족하는 임의의 입력 $m$을 $g$의 사전 이미지에서 찾는 것은 계산적으로 불가능해야 합니다.

충돌 저항성

*충돌 저항성(Collision resistance)*이란, 동일한 다이제스트로 해싱되는 서로 다른 두 입력을 찾기 어려워야 함을 의미합니다.

암호화 해시 충돌은 두 입력이 동일한 다이제스트로 해싱될 때 발생합니다. CHF의 다대일 특성상 충돌은 필연적으로 존재하지만, 잘 설계된 CHF는 임의로 충돌을 찾는 것을 불가능하게 만듭니다.

충돌 저항성은 디지털 서명 및 인증서와 같은 응용 분야에 매우 중요합니다. 악의적인 당사자가 동일한 값으로 해싱되는 위조품을 만들 수 있다면 치명적인 결과를 초래할 수 있기 때문입니다.

해시 충돌의 수학적 세부 사항

$H(m_1) = H(m_2)$를 만족하는 $m_1, m_2$를 찾을 수 있습니다.

해시 길이

충돌 저항성은 사전 이미지 저항성보다 더 강한 요구 사항으로, 사전 이미지 저항성에 필요한 출력 길이의 두 배가 필요합니다. 이는 해시 충돌을 찾는 데 사용할 수 있는 생일 공격(birthday attack)이라는 무차별 대입 공격의 시간 복잡도가 $2^{n/2}$이기 때문입니다.

암호 분석학적 취약점이 없는 경우, 해시 함수의 보안은 주로 해시 길이에 의해 결정됩니다. 해시가 길수록 무차별 대입 공격을 수행하기 어려워져 더 안전합니다.

일반적으로 사용되는 암호화 해시 함수

다음 표는 일반적으로 사용되는 암호화 해시 함수와 해시 길이 및 주요 응용 도메인을 나열합니다:

해시 함수	출력 길이 (비트)	주요 응용 분야
MD5	128	파일 무결성 검사, 구형 시스템, 비암호화 용도
SHA-1	160	레거시 시스템, 버전 관리용 Git
SHA-256	256	암호화폐(Bitcoin), 디지털 서명, 인증서
SHA-3	가변 (최대 512)	다양한 암호화 응용 분야, SHA-2의 후계자
Blake2	가변 (최대 512)	암호화, 일부 시스템에서 MD5/SHA-1 대체
Blake3	가변 (최대 256)	암호화, 파일 해싱, 데이터 무결성

• MD5와 SHA-1은 덜 민감한 응용 분야에서 여전히 사용되지만, 충돌 저항성 측면에서 더 이상 권장되지 않으며 새로운 시스템에는 사용하지 않는 것이 좋습니다. SHA-2 계열에 속하는 SHA-256은 널리 사용되며 현재 대부분의 응용 분야에서 안전합니다.
• SHA-3은 2015년 NIST 해시 함수 공모전의 승자로 NIST가 선정한 새로운 표준입니다. SHA-2의 드롭인 대체품으로 설계되었지만, 내부 특성이 다소 다르며 SHA-2에 효과적일 수 있는 특정 유형의 공격에도 저항력을 갖추고 있습니다.
• Blake2와 Blake3는 MD5, SHA-1, SHA-2, SHA-3보다 빠르면서도 최신 표준인 SHA-3 이상으로 안전한 암호화 해시 함수입니다. 특히 속도가 중요한 경우에 새로운 시스템에서 점점 더 많이 사용되고 있습니다.

전통적인 암호화 해싱에 대한 양자 위협

암호화 해싱에 대한 주요 양자 위협은 무차별 대입 공격에서 비롯됩니다.

공격자는 특정 다이제스트를 가지고 동일한 다이제스트를 생성하는 입력을 찾을 때까지 무작위 입력을 시도합니다.

입력이 $n$비트이면 $2^n$개의 가능한 값이 있습니다. 따라서 공격자가 50% 이상의 성공 확률을 가지려면 약 $2^{n-1}$개의 입력을 시도해야 합니다.

Grover 알고리즘

이러한 비구조적 탐색 맥락에서, Grover 알고리즘은 양자 진폭 증폭(quantum amplitude amplification)이라는 기법을 사용하여 이차(quadratic) 속도 향상을 제공하며, 사전 이미지 공격의 시간 복잡도를 $2^{n/2}$로 줄입니다.

실질적으로, 이는 현재 고전 컴퓨터의 사전 이미지 공격에 대해 안전하다고 여겨지는 256비트 CHF가, Grover 알고리즘을 활용하는 양자 공격자에 직면했을 때 128비트 CHF와 동일한 수준의 보안을 제공한다는 것을 의미합니다.

Grover 알고리즘 자체는 고전 컴퓨터에서 수행될 수 있는 생일 공격이 설정한 한계를 넘어서는 충돌 공격에 대한 추가적인 양자 속도 향상을 제공하는 것으로 알려져 있지 않습니다. 고전적인 생일 공격은 이미 CHF가 사전 이미지 저항성에 필요한 것보다 두 배 긴 해시 길이를 사용하도록 요구하므로, Grover 탐색이 사전 이미지 공격에 대해 사실상 해시 길이를 절반으로 줄인다는 사실은 실질적인 위협이 되지 않습니다.

예를 들어, SHA-256의 경우 Grover 보조 사전 이미지 공격을 수행하기 위해 $2^{128}$ 규모의 연산을 수행하는 것은 가까운 미래에도 여전히 불가능할 것입니다.

BHT 알고리즘

생일 공격과 Grover 탐색의 측면을 결합한 양자 알고리즘이 1997년 Brassard, Høyer, Tapp(BHT)에 의해 제안되었으며, 해시 충돌을 찾기 위한 이론적 스케일링으로 $O(2^{n/3})$을 달성합니다. 그러나 이 향상된 스케일링은 현재 존재하지 않는 양자 랜덤 접근 메모리 QRAM 기술의 존재를 전제로 합니다.

QRAM 없이 실현 가능한 스케일링은 $\tilde{O}(2^{2n/5})$이며, 현재 사용 중인 해시 길이에 대해 생일 공격 대비 이 미미한 충돌 발견 능력 향상은 심각한 위협을 나타내지 않습니다.

요약

암호화 해시 함수는 디지털 정보 시스템에서 데이터 무결성과 개인 정보 보호를 보장하기 위한 필수 구성 요소로, 다양한 맥락에서 광범위하게 활용됩니다.

CHF의 보안 요구 사항은 주로 사전 이미지 및 충돌 공격에 대한 저항성의 관점에서 이해됩니다. 잘 설계된 CHF의 경우 해시 길이는 보안 수준의 좋은 지표가 됩니다.

양자 컴퓨터가 Grover 및 BHT 알고리즘을 실행하면 이론적으로 전통적인 CHF의 사전 이미지 및 충돌 저항성에 영향을 미치지만, 오늘날 이미 사용 중인 긴 해시 길이 덕분에 SHA-3과 같은 현대적인 암호화 해싱 알고리즘은 아직 알려지지 않은 암호 분석학적 공격이 발견되지 않는 한 안전하게 유지될 것으로 예상됩니다.

CHF의 중요성은 양자 저항 암호화 체계의 근본적인 구성 요소로서의 역할에 있으며, 양자 컴퓨팅 알고리즘과 기술의 잠재적인 미래 발전에 직면하더라도 디지털 정보가 안전하게 유지되도록 보장합니다.