여섯 번째 발걸음파일이 바뀌었는지는 해시로 비교한다

친구가 보낸 과제 파일을 내려받았습니다. 파일 이름은 같지만 내용도 같은지 알고 싶습니다. 파일 전체를 한 글자씩 대조할 수도 있지만, 정해진 해시 함수로 파일의 바이트를 짧은 결과값에 대응시켜 비교하면 대용량 자료도 일정한 길이의 기준값으로 다룰 수 있습니다. 암호학적 해시 함수의 결과를 해시값 또는 다이제스트라고 합니다. SHA-256은 입력 길이와 관계없이 256비트 결과를 만듭니다. 이를 16진수 문자로 표시하면 한 문자에 4비트를 담으므로 64문자가 됩니다.

같은 바이트 열에 같은 함수를 적용하면 같은 결과가 나옵니다. 사람이 보기에는 같은 문장이어도 줄바꿈 방식, 공백, 문자 인코딩, 파일 메타데이터가 달라지면 파일 바이트가 달라질 수 있습니다. 해시값 불일치는 계산 대상의 바이트가 다르다는 근거이지, 누가 악의로 바꾸었다는 결론까지는 아닙니다. 반대로 해시값 일치는 서로 다른 파일이 절대로 없다는 수학적 보증은 아닙니다. 가능한 입력 수가 유한한 출력 수보다 많으므로 충돌은 존재합니다. 필요한 것은 유용한 충돌을 현실적인 자원으로 찾기 어렵다는 성질입니다.

세 가지 요구를 나누어 보겠습니다. 주어진 해시값에서 그 값을 만드는 입력 하나를 찾기 어려워야 하는 성질이 역상 저항성입니다. 특정 파일을 이미 정해 놓았을 때 같은 해시를 만드는 다른 파일을 찾기 어려운 것은 제2역상 저항성입니다. 두 파일을 모두 공격자가 고를 수 있어도 같은 해시를 갖는 한 쌍을 찾기 어려운 것은 충돌 저항성입니다. “해시는 되돌릴 수 없다”는 표현은 이러한 계산상의 어려움을 줄여 말한 것입니다. 가능한 평문이 네 자리 숫자뿐이면 후보를 전부 해시해 비교할 수 있으므로 해시만으로 작은 비밀이 강해지지는 않습니다.

import hashlib
original = b'answer=42\n'
copied = b'answer=42\n'
changed = b'answer=43\n'
digest = hashlib.sha256(original).hexdigest()
print(len(digest))  # 64
print(hashlib.sha256(copied).hexdigest() == digest)   # True
print(hashlib.sha256(changed).hexdigest() == digest)  # False
print(digest[:32])
print(digest[32:])

해시 내부도 여러 구조가 있습니다. SHA-256이 속한 SHA-2 계열은 입력에 길이 등을 반영한 패딩을 붙이고 블록을 순서대로 압축 함수에 넣어 내부 상태를 갱신합니다. SHA-3는 Keccak의 스펀지 구조를 사용합니다. 입력을 흡수하며 상태를 섞은 뒤 필요한 출력을 짜내는 구조이며 SHA-2의 단순한 긴 버전이 아닙니다. 이 차이는 구현과 보안 분석의 기반을 이해하는 데 필요합니다. 비밀 키와 메시지를 단순 연결해 해시하는 독자적인 MAC을 만들지 말고, 그 목적을 위해 분석된 HMAC 같은 구성을 사용합니다.

이상적인 n비트 해시에서 일반적인 역상 찾기는 대략 2ⁿ 규모의 시도를 생각하지만, 아무 충돌이나 찾는 데는 생일 역설 때문에 대략 2^(n/2) 규모가 기준이 됩니다. 방 안 두 사람의 생일이 같을 가능성은 특정 한 사람과 같은 생일일 가능성보다 빠르게 커진다는 관계입니다. 따라서 SHA-256의 충돌 탐색 기준을 단순히 2²⁵⁶이라고 쓰면 안 됩니다. 이는 이상적인 경우의 대략적인 작업량 설명이며 모든 실제 공격 비용을 보장하는 계산은 아닙니다. MD5와 SHA-1은 충돌 저항성이 중요한 새 서명·검증 설계의 선택지로 삼지 않습니다. 과거 로그나 파일 식별자에서 이름을 보더라도 사용 목적과 위협을 함께 판단합니다.

참고　[136] · [137] · [138]