해시

두꺼운 계약서 두 부가 있고 상대방이 한 글자를 몰래 고쳤다고 가정해 보겠습니다. 원본과 사본을 처음부터 끝까지 한 글자씩 대조하면 바뀐 곳을 찾을 수 있지만, 문서가 길어질수록 시간이 많이 걸립니다. 해시는 이런 내용을 짧은 지문으로 바꾸어 비교하는 방법입니다.

해시란 무엇인가

해시는 입력 데이터를 정해진 절차로 계산해 일정한 길이의 출력값으로 바꾸는 계산입니다. 입력은 글자 한 개일 수도 있고, 사진이나 두 시간짜리 영화 파일, 천 쪽짜리 장부일 수도 있습니다. 무엇을 넣든 해당 해시 함수가 정한 길이의 지문이 나옵니다.

사람의 지문은 손가락 끝의 작은 무늬이지만 한 사람을 가리키는 표식으로 사용됩니다. 해시는 문서나 사진, 장부 같은 데이터에 디지털 지문을 만들어 줍니다. 원본 전체를 매번 비교하는 대신 지문을 비교하면 데이터가 같은지 빠르게 확인할 수 있습니다.

같은 입력을 같은 해시 함수에 넣으면 어디에서 계산해도 같은 출력이 나옵니다. 출력이 다르면 입력의 어딘가가 달라졌다는 사실을 알 수 있습니다. 다만 해시가 같다는 것만으로 서로 다른 입력이 절대로 존재하지 않는다고 단정하는 것은 정확하지 않습니다. 출력 길이는 정해져 있고 입력의 종류는 무한히 많기 때문에, 이론적으로는 같은 출력이 나오는 충돌이 존재할 수 있습니다.

해시의 세 가지 성질

일방향성

데이터에서 해시를 계산하는 일은 빠르지만, 해시만 보고 원래 데이터를 찾는 일은 적절한 조건에서 계산적으로 어렵도록 설계되어 있습니다. 다만 입력 후보가 짧거나 흔하다면 후보를 추측해 해시를 계산하고 비교하는 공격이 가능합니다. 따라서 비밀번호는 단순한 해시값만 저장하지 않고, 전용 비밀번호 해싱 함수와 솔트 같은 별도 보호 수단을 사용해야 합니다. 해시 함수의 역상 저항성과 충돌 저항은 서로 다른 성질입니다(NIST 해시 함수 참고).

이 성질은 믹서에 간 과일 주스에 비유할 수 있습니다. 사과와 당근을 갈아 주스 한 잔을 만들고 나면, 주스를 들여다보는 것만으로 갈기 전 사과의 모양을 그대로 되살리기 어렵습니다. 다만 원래 재료의 후보가 몇 가지뿐이라면 추측과 비교로 후보를 좁힐 수 있습니다.

눈사태 효과

입력에 아주 작은 변화만 생겨도 출력 전체가 크게 달라지는 성질을 눈사태 효과라고 합니다. ‘안녕하세요’와 여기에 마침표 하나를 붙인 문장을 각각 해시하면 두 결과는 크게 달라집니다.

산꼭대기에서 굴러 내려온 작은 눈덩이가 산 아래에서 거대한 눈사태가 되는 모습과 비슷해서 붙은 이름입니다. 장부의 숫자 하나만 고쳐도 지문 전체가 달라지므로, 일부만 수정해 원래 지문과 비슷하게 유지하려는 방법이 통하지 않습니다.

충돌 저항

서로 다른 두 데이터가 같은 해시값을 갖는 일을 충돌이라고 합니다. 좋은 해시 함수는 이런 짝을 찾기 어렵게 설계됩니다. 핵심은 충돌이 논리적으로 절대 존재하지 않는다는 뜻이 아니라, 실제로 찾아내기 매우 어렵다는 뜻입니다.

지문의 길이는 정해져 있지만 입력 데이터의 종류는 끝이 없습니다. 따라서 이론적으로 충돌은 존재할 수밖에 없습니다. 그러나 충돌을 실제로 찾아내기 어려워야 해시가 검증 도구로 기능할 수 있습니다. 도장이 모두 똑같다면 다른 사람이 내 도장을 복제해 계약서에 찍을 수 있지만, 서로 다른 문서가 같은 지문을 만들기 어려워야 지문이 위조를 드러내는 표식이 됩니다.

비트코인에서 해시가 쓰이는 곳

비트코인의 전체장부는 블록들이 사슬처럼 이어진 구조입니다. 각 블록은 앞 블록의 지문을 품고 있습니다. 누군가 과거 블록의 거래를 고치면 거래 목록에서 계산한 머클 루트가 달라지고, 그 결과 블록 헤더의 해시도 달라집니다. 이후 블록의 참조를 맞추려면 뒤따르는 블록의 헤더와 작업증명을 다시 계산해야 하므로, 과거 기록을 바꾸는 비용이 커집니다. 블록 헤더와 머클 루트의 관계는 Bitcoin Developer Guide에서 확인할 수 있습니다.

일방향성은 지문을 미리 계산해 장부를 짜 맞추는 길을 어렵게 만들고, 충돌 저항은 지문이 같은 가짜 블록을 끼워 넣는 방법을 어렵게 만듭니다. 해시는 비트코인에서 블록을 이어 붙이고, 장부가 바뀌었는지 확인하며, 채굴의 계산 문제를 만드는 데 활용됩니다.

해시는 배포 파일의 지문을 공개해 받은 파일이 바뀌었는지 확인하는 데에도 사용할 수 있습니다. 또한 스팸을 어렵게 만들기 위해 메시지에 계산 결과를 요구하는 작업증명 방식에도 활용되어 왔습니다. 이런 활용은 해시가 데이터 비교뿐 아니라 계산 비용을 부과하는 도구로도 쓰일 수 있음을 보여 줍니다.

해시는 주소를 만드는 과정에도 사용되지만, 주소 형식에 따라 적용되는 해시와 절차는 다를 수 있습니다. 주소 생성은 해시만으로 이루어지는 하나의 동일한 과정으로 이해해서는 안 됩니다.

해시는 암호화가 아니다

암호화는 나중에 다시 읽기 위해 내용을 잠그는 기술입니다. 따라서 적절한 열쇠가 있으면 원문으로 되돌리는 길이 처음부터 마련되어 있습니다.

해시는 목적이 다릅니다. 원본을 숨겼다가 다시 여는 것이 아니라, 원본이 그대로인지 확인할 수 있는 지문을 만드는 것이 목적입니다. 그래서 해시에는 암호화처럼 열쇠로 여는 문이 없습니다. 다만 입력 후보를 추측해 해시와 대조하는 방식으로 원문을 알아낼 수 있는 경우는 있으므로, ‘해독할 수 없다’고 절대적으로 말해서는 안 됩니다.

정리

• 해시는 어떤 입력이든 정해진 길이의 지문으로 바꾸는 계산입니다.
• 같은 입력은 같은 해시를 만들고, 입력이 달라지면 해시도 달라지는 것이 이상적입니다.
• 일방향성은 적절한 조건에서 해시로부터 원본을 찾는 일을 계산적으로 어렵게 합니다.
• 눈사태 효과는 입력의 작은 변화가 출력 전반에 큰 변화를 일으키게 합니다.
• 충돌 저항은 서로 다른 입력에서 같은 해시를 찾기 어렵게 합니다.
• 비트코인은 해시로 블록을 연결하고 장부의 변경과 채굴 계산을 검증합니다.