해시 함수 해설

소프트웨어를 내려받아 체크섬을 비교할 때, 비밀번호로 로그인할 때, 문서에 서명할 때, 비트코인에 블록을 추가할 때 해시 함수가 작동하고 있습니다. 해시 함수는 양에 관계없이 어떤 데이터든 해시값(다이제스트)이라는 고정된 크기의 짧은 지문으로 바꾸며, 이 과정은 되돌릴 수도 위조할 수도 없습니다. 아이디어는 단순하지만 좋은 해시 함수에 대한 요구 조건은 엄격하며, 가장 널리 쓰인 두 해시 함수인 MD5와 SHA-1은 그 조건을 견뎌 내지 못했습니다.

글자 하나만 다른 두 메시지가 해시 함수에 들어가 완전히 다른 두 SHA-256 해시값으로 나오고, 뒤집힌 비트가 격자에 표시된 모습
글자 하나만 다른 두 메시지가 해시 함수에 들어가 완전히 다른 두 SHA-256 해시값으로 나오고, 뒤집힌 비트가 격자에 표시된 모습

데이터의 지문

해시 함수는 길이에 관계없이 입력을 받아 고정된 길이의 해시값을 돌려줍니다. SHA-256은 256비트이며, 16진수 64자리로 씁니다. 같은 입력은 언제나 같은 해시값을 내므로 해시값이 데이터를 대표할 수 있습니다. 두 파일의 SHA-256 해시값이 같다면 두 파일이 똑같다고 확신할 수 있고, 내려받은 파일의 비트 하나라도 손상되었다면 그 해시값은 배포자가 공개한 값과 더 이상 일치하지 않습니다. 가능한 입력이 가능한 해시값보다 훨씬 많으므로, 해시값 하나마다 많은 입력이 대응할 수밖에 없습니다. 좋은 해시 함수는 단지 그중 어느 것도 찾을 수 없게 만들 뿐입니다.

세 가지 약속

암호학적 해시 함수는 세 가지를 약속합니다. 역상 저항성: 해시값이 주어져도 그 해시값을 만드는 입력을 찾을 수 없습니다. 제2 역상 저항성: 입력이 주어져도 같은 해시값을 가진 다른 입력을 찾을 수 없습니다. 충돌 저항성: 같은 해시값을 가진 두 입력을 어떤 것이든 찾을 수 없습니다. n비트의 이상적인 해시 함수에 대한 최선의 공격은 추측이며, 역상에는 약 2ⁿ번, 충돌에는 약 2ⁿᐟ²번의 시도가 필요합니다. 누군가 이보다 훨씬 빠른 방법을 찾아내면 그 해시 함수는 깨졌다고 합니다.

눈사태 효과

입력의 비트 하나를 바꾸면 해시값의 각 비트는 다른 비트와 독립적으로 2분의 1 확률로 뒤집혀야 합니다. 그러면 메시지의 작은 변화가 전혀 관계없어 보이는 해시값을 만들어 내고, 해시값은 입력의 어느 부분이 바뀌었는지 전혀 드러내지 않습니다. SHA-256은 32비트 워드 여덟 개를 회전하고 더하고 조합하는 라운드를 64번 실행해 이를 달성하며, 몇 라운드 안에 모든 입력 비트가 모든 워드에 영향을 미칩니다. 반면 단순한 바이트 합은 입력이 바뀐 양만큼 정확히 바뀌므로 모든 것을 드러내 버립니다.

SHA-256의 내부

SHA-256은 먼저 메시지를 패딩합니다. 1비트 하나, 0 여러 개, 그리고 메시지의 길이를 덧붙여 전체 길이를 512비트의 배수로 만듭니다. 그런 다음 메시지를 512비트씩 처리합니다. 각 블록은 64개의 워드로 늘어난 뒤, 32비트 워드 여덟 개로 이루어진 상태에 섞여 들어갑니다. 상태의 초깃값은 고정되어 있으며, 처음 여덟 소수의 제곱근에서 가져온 값입니다. 마지막 블록을 처리한 뒤의 상태가 해시값입니다. Ralph Merkle과 Ivan Damgård의 이름을 딴 이 연쇄 구조는 MD5, SHA-1, SHA-512도 공유합니다. 2015년에 표준화된 더 새로운 SHA-3은 스펀지라고 부르는 다른 구성을 사용합니다.

2007년 싱귤래리티 서밋에서의 랄프 머클. SHA-256이 쓰는 연쇄 구조는 그와 이반 담고르의 이름을 땄다.
2007년 싱귤래리티 서밋에서의 랄프 머클. SHA-256이 쓰는 연쇄 구조는 그와 이반 담고르의 이름을 땄다.

생일 공격

23명으로 이루어진 집단에서 생일이 같은 두 사람이 있을 확률은 1년이 365일인데도 2분의 1을 조금 넘습니다. 중요한 것은 짝의 수이고, 짝의 수는 집단 크기의 제곱에 비례해 늘어나기 때문입니다. 해시 함수의 충돌도 같은 규칙을 따릅니다. 가능한 해시값이 2ᵏ가지일 때, 약 √(π/2 · 2ᵏ)개의 무작위 입력이면 충돌이 하나 나올 것으로 예상됩니다. 32비트라면 약 8만 2,000개의 입력으로, 순식간에 끝납니다. 128비트라면 약 2⁶⁴로, 대규모 계산 프로젝트라면 손이 닿는 수준입니다. 그래서 MD5의 128비트는 결코 넉넉한 적이 없었고, SHA-256은 길이를 두 배로 늘려 128비트의 보안을 제공합니다.

MD5와 SHA-1: 깨진 해시 함수

Ron Rivest가 1991년에 MD5를 설계했고, NSA가 설계한 SHA-1은 1995년에 발표되었습니다. 2004년 Xiaoyun Wang과 동료들은 MD5 충돌을 빠르게 만드는 방법을 보여 주었고, 2008년에는 연구자들이 이를 이용해 웹 브라우저가 신뢰하는 인증서를 위조했습니다. 2012년의 스파이 소프트웨어 Flame은 MD5 충돌을 이용해 Microsoft 업데이트로 위장했습니다. SHA-1은 2017년에 무너졌습니다. Google과 CWI Amsterdam이 약 2⁶³번의 계산 끝에 SHA-1 해시값이 같은 서로 다른 PDF 파일 두 개를 공개한 것입니다. 둘 다 우연한 오류를 찾는 데는 여전히 괜찮지만, 공격자가 노릴 수 있는 용도에는 쓸 수 없습니다.

해시 함수가 쓰이는 곳

디지털 서명은 문서 자체가 아니라 문서의 해시값에 서명합니다. Git은 모든 파일과 커밋에 해시값으로 이름을 붙이고, 비트코인 채굴자들은 SHA-256을 두 번 적용한 해시값이 긴 0의 연속으로 시작하는 블록 헤더를 찾습니다. 웹사이트는 비밀번호를 절대 그대로 저장해서는 안 되며 그 해시값만 저장해야 합니다. 하지만 사람들은 짧은 비밀번호를 고르기 때문에, 그 해시는 bcrypt, scrypt, Argon2 같은 방법으로 느리게, 솔트를 적용해 만들어 추측에 많은 비용이 들게 해야 합니다. ZIP 파일, PNG 이미지, Ethernet에서 쓰이는 CRC-32 같은 체크섬도 해시이지만, 공격자가 아니라 잡음을 잡아내도록 만들어졌습니다.

직접 탐구해 보세요

해시 함수 실험실을 열고 SHA-256, SHA-512, SHA-1, MD5, CRC-32, 장난감 바이트 합으로 직접 쓴 텍스트를 해시해 보세요. ‘한 글자 바꾸기’를 눌러 뒤집힌 비트를 세어 보고, ‘테스트 실행’으로 1비트 변경 1,000번에 걸친 눈사태 테스트를 해서 해시값의 절반을 중심으로 한 종 모양 곡선을 확인하고, ‘충돌 찾기’로 해시값의 앞 8~32비트에서 실제 충돌을 찾아 생일 공격이 작동하는 모습을 지켜보세요.

자주 묻는 질문

해싱은 암호화와 같은 것인가요?

아니요. 암호화는 키를 가진 사람이 되돌릴 수 있도록 만든 것이고, 해싱에는 키가 없어 누구도 되돌릴 수 없습니다. 암호화는 메시지를 비밀로 지키는 반면, 해시는 이미 가지고 있는 메시지를 확인할 수 있게 해 주는 지문을 줄 뿐입니다.

SHA-256 충돌을 찾는 데 얼마나 걸리나요?

생일 공격으로는 약 2¹²⁸번의 해시 계산이 필요하며, 이는 39자리 수입니다. 지구상의 모든 컴퓨터가 다른 일은 전혀 하지 않고 이 일만 해도 우주의 나이보다 훨씬 오래 걸립니다. 알려진 지름길은 없습니다.

같은 텍스트의 해시값이 왜 절대 달라지지 않나요?

해시 함수는 결정적입니다. 무작위성도 키도 없으므로 같은 바이트는 언제나 같은 해시값을 냅니다. 하지만 끝에 붙은 공백, 다른 줄바꿈 문자, 악센트가 붙은 글자의 다른 유니코드 형태처럼 눈에 보이지 않는 작은 차이는 실제로 다른 해시값을 만듭니다.

솔트란 무엇인가요?

비밀번호 해시 옆에 저장되어 해시에 함께 섞이는 무작위 값입니다. 그러면 같은 비밀번호를 쓰는 두 사용자도 서로 다른 해시값을 얻게 되고, 공격자는 흔한 비밀번호를 미리 계산해 둔 표 하나를 모든 계정에 쓸 수 없습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

해시 함수 실험실 열기