암호학적 해시 함수(Cryptographic Hash Function)
1. 개요
정의: 암호학적 해시 함수(Cryptographic Hash Function)는 임의 길이의 입력 메시지를 고정 길이의 요약값(해시값·다이제스트)으로 사상(mapping)하되, 역상·제2역상·충돌을 계산적으로 찾기 어렵도록 설계된 일방향 함수이다.
정보시스템에서 "데이터가 전송·저장 중에 바뀌지 않았는가", "이 사용자가 제시한 비밀번호가 등록된 것과 같은가", "이 문서가 서명 당시의 그 문서가 맞는가"라는 질문은 끊임없이 발생한다. 이 질문들은 모두 원본 전체를 다시 비교하지 않고도 짧은 지문(fingerprint) 하나로 동일성을 판정할 수 있어야 실용적이다. 암호학적 해시 함수는 바로 이 지문을 만들어 주는 기본 원초(primitive)로, 전자서명·메시지 인증·무결성 검증·비밀번호 저장·블록체인·중복제거까지 현대 보안의 거의 모든 계층에 스며들어 있다.
단순한 체크섬(CRC, 패리티)도 고정 길이 요약값을 만들지만, 이들은 우연한 오류 검출만을 목표로 하므로 공격자가 의도적으로 같은 값을 갖는 다른 데이터를 만들어 낼 수 있다. 반면 암호학적 해시는 공격자가 계산 자원을 쏟아부어도 원하는 요약값을 만족하는 입력을 찾기 어렵다는 의도적 위조 방지를 핵심 요구사항으로 삼는다. 이 차이가 "해시"라는 같은 단어 아래 전혀 다른 보증 수준을 만든다.
암호학적 해시가 중요한 이유는 그것이 신뢰의 압축을 가능하게 하기 때문이다. 수 기가바이트의 디스크 이미지, 수백만 건의 트랜잭션, 임의 길이의 인증서 체인을 256비트의 값 하나로 요약하고, 그 값만 안전한 채널로 전달하면 나머지 방대한 데이터는 신뢰할 수 없는 경로로 옮겨도 변조를 탐지할 수 있다. 예를 들어 리눅스 배포판은 수 GB ISO 파일에 대해 SHA-256 값 하나(64자리 16진수)만 공식 사이트에 게시하고, 이용자는 미러 서버에서 받은 파일을 직접 해시해 대조한다. 1,000만 건의 데이터를 비교하는 문제가 32바이트 비교 문제로 바뀌는 것이다.
등장 배경과 필요성
초기 암호학은 기밀성(암호화)에 집중했으나, 네트워크가 확산되면서 "내용을 숨기는 것"보다 "내용이 바뀌지 않았음"과 "보낸 사람이 맞음"을 증명하는 무결성·인증 수요가 폭증했다. 공개키 서명은 메시지 전체가 아니라 그 해시값에 서명함으로써 서명 비용을 상수화했고, 이로써 해시는 서명 체계의 필수 전처리 단계가 되었다.
또한 비밀번호를 평문으로 저장하면 데이터베이스 유출 시 전 계정이 즉시 탈취되므로, 비밀번호는 복원 불가능한 형태로 보관해야 한다. 일방향성을 갖는 해시는 "저장은 하되 되돌릴 수는 없는" 저장 방식을 제공해, 비밀번호 보호의 표준 수단이 되었다. 뒤에서 보겠지만 범용 해시를 그대로 쓰는 것은 위험하며 전용 패스워드 해시가 필요하다는 점이 중요한 심화 포인트다.
기술사 관점의 문제 정의
논술 답안에서는 해시 함수를 "고정 길이로 줄이는 함수"로만 기술하면 실패다. 핵심은 세 가지 보안 속성(역상·제2역상·충돌 저항성)과 각각이 깨졌을 때 무너지는 응용을 연결하고, 생일 역설에 의한 보안강도 반감, Merkle–Damgård 구조의 길이확장 취약점, 범용 해시와 패스워드 해시의 목적 차이를 구분해 설명하는 것이다. 즉 "어떤 응용에 어떤 속성이 왜 필요한가"를 축으로 삼아야 한다.
2. 핵심 보안 속성과 요구 특성
암호학적 해시 함수 H가 안전하다고 말하려면 세 가지 계산적 난해성을 만족해야 한다. 아래 구조도는 입력·처리·출력의 흐름과 각 속성이 방어하는 공격을 함께 보여 준다.
flowchart TD
M["임의 길이 메시지 M"] --> P["패딩 + 블록 분할"]
P --> C["압축/흡수 과정(라운드 반복)"]
C --> D["고정 길이 다이제스트 H(M)"]
D --> U1["무결성 검증(파일/펌웨어)"]
D --> U2["전자서명 전처리"]
D --> U3["비밀번호 저장"]
D --> U4["블록체인/머클루트"]
A1["역상 공격: H(M)->M 복원"] -. 방어 .-> C
A2["제2역상: 같은 해시의 다른 M' 찾기"] -. 방어 .-> C
A3["충돌: H(M1)=H(M2)인 임의 쌍"] -. 방어 .-> C
가. 역상 저항성(Preimage Resistance)
역상 저항성은 주어진 해시값 y에 대해 H(M)=y가 되는 입력 M을 찾기 어려워야 한다는 성질로, 흔히 일방향성(one-wayness)이라 부른다. 비밀번호 저장이 이 속성에 의존한다. 데이터베이스에 저장된 다이제스트만으로는 원래 비밀번호를 복원할 수 없어야 공격자가 유출된 해시로 로그인할 수 없다.
이상적 해시의 역상 공격 비용은 n비트 출력에 대해 약 2^n 시도다. 따라서 SHA-256은 역상 공격에 약 2^256의 비용을 요구하며, 이는 현존·근미래 연산력으로 불가능한 수준이다. 그러나 비밀번호처럼 입력 공간 자체가 작으면(사람이 쓰는 비밀번호의 엔트로피는 보통 20~40비트) 해시의 이론적 강도와 무관하게 전수조사(brute-force)로 뚫린다. 이 지점이 "강한 해시를 써도 약한 비밀번호는 못 지킨다"는 실무 교훈의 근거다.
실무에서는 역상 저항성을 과신해 민감 식별자(주민번호, 이메일)를 소금 없이 해시해 저장하는 사례가 흔한데, 값의 분포가 좁으면 사전 계산된 테이블로 역추적되므로 사실상 일방향성이 깨진다. 즉 역상 저항성은 입력 분포와 함께 평가해야 하는 조건부 속성이다.
나. 제2역상 저항성과 충돌 저항성
제2역상 저항성(Second Preimage Resistance)은 특정 메시지 M이 주어졌을 때 같은 해시를 갖는 다른 M'을 찾기 어려워야 한다는 성질이다. 반면 충돌 저항성(Collision Resistance)은 공격자가 자유롭게 H(M1)=H(M2)인 아무 쌍이나 찾기 어려워야 한다는, 더 강한 요구다.
두 속성의 차이는 공격 비용에서 극명하게 갈린다. 제2역상은 2^n에 가깝지만, 충돌은 생일 역설(birthday paradox)에 의해 약 2^(n/2)로 급감한다. 23명만 모여도 생일이 겹칠 확률이 50%를 넘는 직관처럼, 무작위 값을 약 2^(n/2)개 모으면 둘이 겹칠 가능성이 높아진다. 그래서 128비트 보안강도를 목표로 하면 해시 출력은 최소 256비트여야 한다. SHA-256이 "128비트급 충돌 저항"으로 평가되는 이유가 여기 있다.
충돌 저항성이 가장 치명적으로 요구되는 곳은 전자서명이다. 공격자가 "선의의 계약서"와 "악의의 계약서"가 같은 해시를 갖도록 만들 수 있다면, 피해자가 전자에 서명한 서명값이 후자에도 그대로 유효해진다. 실제로 2012년 Flame 악성코드는 MD5 충돌을 악용해 위조된 코드서명 인증서를 만들어 Windows Update를 통해 전파되었는데, 이는 충돌 저항성 상실이 어떻게 전 지구적 공격으로 이어지는지를 보여 준 대표 사례다.
다. 눈사태 효과와 결정성·효율성
좋은 해시는 입력이 1비트만 달라져도 출력의 약 절반 비트가 예측 불가능하게 뒤집히는 눈사태 효과(avalanche effect)를 보인다. 이는 입력과 출력 사이의 통계적 상관을 제거해, 공격자가 부분 정보를 추론하지 못하게 한다. 동시에 해시는 결정적(deterministic)이어서 같은 입력은 항상 같은 값을 내야 하며(검증 가능성의 전제), 대량 데이터에도 적용할 수 있도록 계산 효율적이어야 한다.
흥미로운 긴장 관계가 여기 있다. 무결성·서명용 해시는 빠를수록 좋지만, 비밀번호용 해시는 오히려 의도적으로 느려야 공격자의 전수조사를 어렵게 한다. 같은 "해시"라도 목적에 따라 설계 목표가 정반대인 것이다. 이 긴장을 인식하지 못하고 SHA-256으로 비밀번호를 저장하면, GPU로 초당 수십억 회 해시가 가능해 유출 시 방어력이 거의 없다.
3. 대표 알고리즘과 내부 구조
해시의 내부 구조는 크게 Merkle–Damgård(MD) 구조와 스펀지(sponge) 구조로 나뉜다. 아래 프로세스 상세도는 두 구조의 처리 흐름 차이를 나타낸다.
flowchart LR
subgraph MD["Merkle-Damgard 구조(MD5/SHA-1/SHA-2)"]
direction LR
IV["초기값 IV"] --> F1["압축함수 f(블록1)"]
F1 --> F2["압축함수 f(블록2)"]
F2 --> F3["압축함수 f(블록n)"]
F3 --> OUT1["최종 체이닝값 = 다이제스트"]
end
subgraph SP["스펀지 구조(SHA-3/Keccak)"]
direction LR
S0["상태 초기화"] --> AB["흡수(absorb): 메시지 XOR 후 순열 f"]
AB --> SQ["압출(squeeze): 상태에서 출력 추출"]
SQ --> OUT2["가변 길이 다이제스트"]
end
가. 세대별 알고리즘의 변천
해시 알고리즘은 공격 기법의 발전에 쫓기며 세대 교체를 거듭했다. MD5(128비트)와 SHA-1(160비트)은 오랫동안 사실상 표준이었으나 충돌이 실증되어 보안 용도에서 퇴출되었고, 현재는 SHA-2 계열이 주력이며 SHA-3가 구조적 다양성을 위한 대안으로 표준화되었다. 아래 표는 주요 알고리즘을 비교한다.
| 알고리즘 | 출력 길이(비트) | 내부 구조 | 충돌 저항(비트) | 상태 |
|---|---|---|---|---|
| MD5 | 128 | Merkle–Damgård | 사실상 0(수초 내 충돌) | 폐기 |
| SHA-1 | 160 | Merkle–Damgård | 깨짐(≈2^63 이하) | 폐기 |
| SHA-256 | 256 | Merkle–Damgård | 128 | 권장 |
| SHA-512 | 512 | Merkle–Damgård | 256 | 권장 |
| SHA-3-256 | 256 | 스펀지(Keccak) | 128 | 권장 |
| SHAKE128/256 | 가변 | 스펀지(XOF) | 128/256 | 권장 |
나. Merkle–Damgård 구조와 길이확장 취약점
MD 구조는 메시지를 고정 크기 블록으로 나눠 압축함수 f를 체인처럼 반복 적용하고, 이전 블록의 출력(체이닝값)을 다음 블록의 입력으로 넘긴다. 구현이 단순하고 충돌 저항성을 압축함수의 안전성으로 환원해 증명할 수 있다는 장점으로 널리 쓰였다.
그러나 이 구조에는 길이확장 공격(length-extension attack)이라는 고유 약점이 있다. 공격자가 H(secret || M) 값과 메시지 길이만 알면, 비밀값 secret을 모른 채로도 H(secret || M || padding || M')을 계산할 수 있다. 이 때문에 "해시(비밀||메시지)"를 메시지 인증에 그대로 쓰면 위조가 가능하며, 이를 막기 위해 HMAC이라는 이중 해시 구조(H(key⊕opad || H(key⊕ipad || M)))가 표준으로 자리 잡았다. SHA-512를 잘라 쓰는 SHA-512/256이나 스펀지 구조의 SHA-3는 길이확장에 면역이라는 점도 알고리즘 선택의 중요한 고려사항이다.
다. 스펀지 구조와 SHA-3의 의의
SHA-3(Keccak)는 NIST가 2007~2012년 공개 경진을 거쳐 2015년 FIPS 202로 표준화한 알고리즘으로, SHA-2와 구조 자체가 다른 점이 핵심 가치다. 만약 미래에 SHA-2의 MD 구조를 겨냥한 돌파가 나오더라도, 전혀 다른 스펀지 구조의 SHA-3가 즉시 대체재로 존재하도록 암호 민첩성(crypto-agility)의 보험을 마련한 것이다.
스펀지 구조는 큰 내부 상태에 메시지를 XOR로 흡수(absorb)한 뒤 순열을 적용하고, 필요한 만큼 출력을 뽑아내는(squeeze) 방식이라 가변 길이 출력(XOF: SHAKE128/256)을 자연스럽게 지원한다. 이 가변 출력 특성은 포스트 양자 서명(SPHINCS+)이나 키 유도 등에서 유연하게 활용된다.
4. 주요 활용과 패스워드 저장
해시의 응용은 요구 속성에 따라 분류하면 이해가 쉽다. 무결성 검증(파일·펌웨어 해시 대조)은 제2역상 저항성에, 전자서명과 인증서는 충돌 저항성에, 메시지 인증(HMAC)은 의사난수성에, 블록체인의 작업증명과 머클루트는 역상·충돌 저항성에 각각 의존한다. 데이터 중복제거(dedup)와 콘텐츠 주소 저장(content-addressable storage)도 "내용이 같으면 해시가 같다"는 성질을 주소로 삼는다.
가. 비밀번호 저장: 소금·후추·키 스트레칭
비밀번호 저장은 범용 해시를 그대로 쓰면 안 되는 대표 영역이다. 첫째, 같은 비밀번호가 같은 해시가 되면 공격자가 미리 계산한 레인보우 테이블(rainbow table)로 대량 역추적이 가능하다. 이를 막는 장치가 사용자마다 다른 무작위 소금(salt)으로, 소금을 해시 입력에 섞으면 동일 비밀번호도 서로 다른 다이제스트가 되어 사전 계산 공격이 무력화된다. 둘째, SHA-256 같은 빠른 해시는 GPU로 초당 수십억 회 시도되므로, 의도적으로 느리게 만드는 키 스트레칭(key stretching)이 필요하다.
이 요구를 충족하도록 전용 패스워드 해시가 발전했다. PBKDF2는 반복 횟수로 비용을 올리지만 GPU·ASIC에 상대적으로 취약하고, bcrypt는 Blowfish 기반으로 메모리를 약간 사용하며, scrypt와 Argon2는 메모리 하드(memory-hard) 설계로 대량 병렬 하드웨어 공격의 비용을 크게 높인다. 2015년 Password Hashing Competition에서 우승한 Argon2(특히 측면공격 저항형 Argon2id)가 현재 1순위 권장안이다. OWASP는 Argon2id를 약 19MiB 메모리·2회 반복·병렬도 1, 또는 PBKDF2-HMAC-SHA256을 약 60만 회 반복으로 설정할 것을 가이드한다. 운영 조직은 추가로 서버에만 보관하는 비밀값인 후추(pepper)를 HMAC 형태로 결합해, 데이터베이스만 유출된 경우의 방어선을 한 겹 더 둔다.
나. 전자서명·인증서에서의 해시
전자서명은 메시지 전체가 아니라 그 다이제스트에 서명하므로, 해시의 충돌 저항성이 곧 서명의 위조 불가능성으로 직결된다. 공인인증서·코드서명·TLS 인증서 체인은 모두 서명 대상 해시 알고리즘을 명시하며, 산업계가 SHA-1 서명 인증서를 2017년 전후로 일괄 폐기한 것은 앞서 본 충돌 실증에 대한 직접적 대응이었다.
5. 비교 및 공격 사례
알고리즘 선택을 "출력 길이가 길수록 좋다"로 단순화하면 실무 설계를 그르친다. 길이확장 면역 여부, 하드웨어 가속 지원, 표준·규제 적합성, 성능이 모두 변수다. 아래 표는 선택 시 고려 축과 그 이유를 정리한다.
| 고려 축 | 핵심 질문 | 실무적 함의 |
|---|---|---|
| 보안강도 | 충돌 저항 몇 비트가 필요한가 | 128비트급이면 SHA-256, 장기 보존·고가치는 SHA-384/512 |
| 구조 다양성 | 길이확장에 면역인가 | 인증엔 HMAC, 또는 SHA-3/SHA-512-256 선택 |
| 목적 적합성 | 빠를수록 좋은가 느릴수록 좋은가 | 무결성은 SHA-2, 비밀번호는 Argon2id |
| 규제 적합성 | 국내외 표준 승인 알고리즘인가 | 국내 전자서명은 SHA-256 이상, 국제는 FIPS 승인 여부 |
공격 사례는 이 선택의 근거를 생생하게 보여 준다. MD5는 2004년 왕샤오윈 연구팀이 실용적 충돌을 발표한 뒤 수초 내 충돌 생성이 가능해졌고, 2008년에는 위조 CA 인증서가 만들어졌다. SHA-1은 2017년 구글과 CWI의 SHAttered 공격으로 약 9.2×10^18(약 2^63)회 연산으로 두 개의 서로 다른 PDF가 같은 SHA-1 해시를 갖는 실증 충돌이 공개되었고, 2020년에는 선택 접두사 충돌 비용이 수만 달러 수준으로 떨어졌다. 이 수치들은 "이론적으로 깨진" 것과 "현실적으로 악용 가능한" 것 사이의 거리가 생각보다 짧다는 교훈을 준다.
6. 심화: 표준 변화와 포스트 양자 시대의 해시
암호학적 해시를 둘러싼 최신 쟁점은 양자 컴퓨팅의 위협과 그에 따른 표준의 재평가다. 공개키 암호(RSA·ECC)는 쇼어(Shor) 알고리즘으로 다항시간에 깨질 수 있어 사실상 전면 교체가 필요하지만, 대칭키·해시는 그로버(Grover) 알고리즘이 역상 탐색을 2^n에서 2^(n/2)로 제곱근 수준만 가속한다. 따라서 SHA-256의 역상 저항은 양자 환경에서 128비트급으로 낮아지는 정도여서, 충돌 저항(이미 128비트)과 합쳐 보수적으로는 SHA-384/SHA-512로의 상향이 권고된다. 즉 해시는 양자 시대에도 "폐기"가 아니라 "출력 길이 상향"으로 대응 가능한, 상대적으로 견고한 원초다.
역설적으로 해시는 포스트 양자 암호의 해결책이기도 하다. NIST가 2024년 표준화한 포스트 양자 서명 중 SPHINCS+(FIPS 205, SLH-DSA)는 격자·코드 같은 새로운 수학 가정 없이 오직 해시 함수의 안전성에만 의존하는 해시 기반 서명으로, 수학적 가정이 적어 가장 보수적으로 신뢰받는다. XMSS·LMS 같은 상태유지 해시 서명도 펌웨어 서명 등에서 채택되고 있다. 이처럼 해시는 "공격받는 대상"이자 "방어의 토대"라는 이중 지위를 갖는다.
표준 측면에서는 NIST FIPS 180-4(SHA-1/2)·FIPS 202(SHA-3)가 기반이며, 2022년 NIST는 SHA-1의 완전 사용 중단을 2030년까지 단계적으로 추진한다고 공표했다. 국내에서도 전자서명·공공시스템에서 SHA-256 이상 사용이 의무화되는 추세이며, TLS 1.3는 취약한 해시·MAC 조합을 프로토콜 수준에서 제거해 안전한 해시 사용을 강제한다.
7. 고려사항 및 시사점
- 암호 민첩성(crypto-agility) 확보: 특정 해시 알고리즘을 코드·데이터 포맷에 하드코딩하면, 미래의 돌파 발생 시 교체 비용이 폭증한다. 알고리즘 식별자를 메타데이터로 분리하고 다중 알고리즘을 병행 지원하는 설계로, MD5→SHA-1→SHA-256의 교체 역사가 반복될 것을 전제해야 한다.
- 목적별 알고리즘 분리 원칙: "하나의 좋은 해시"라는 환상을 버리고, 무결성·서명에는 빠른 SHA-2/3를, 비밀번호에는 느린 메모리 하드 Argon2id를, 인증에는 HMAC을 쓰는 용도 기반 선택을 거버넌스로 명문화해야 한다. 비밀번호를 SHA-256으로 저장하는 안티패턴이 여전히 흔하다는 점이 경고다.
- 입력 엔트로피와 소금·후추의 결합: 해시의 이론적 강도만 믿지 말고, 저엔트로피 입력(비밀번호·식별자)에는 반드시 사용자별 소금과 서버측 후추, 충분한 작업계수(work factor)를 결합해야 한다. 작업계수는 하드웨어 발전에 맞춰 주기적으로 상향하는 운영 프로세스가 필요하다.
- 트레이드오프와 장기 보존 전략: 출력 길이를 늘리면 안전하지만 저장·전송 비용과 성능이 증가한다. 장기 보존 문서·전자기록은 서명 당시 알고리즘이 수십 년 뒤 취약해질 수 있으므로, 재해싱·재서명(long-term archival signature, 예: 타임스탬프 토큰 갱신) 절차를 아키텍처에 포함해야 한다.
- 연계 기술과 전망: 해시는 머클 트리·블록체인·HMAC·전자서명·KDF·중복제거·콘텐츠 주소 저장과 촘촘히 엮여 있으므로, 단일 알고리즘 교체가 상위 프로토콜에 미치는 파급을 영향분석(impact analysis)으로 추적해야 한다. 양자 내성 관점에서는 SHA-384 이상으로의 상향과 해시 기반 서명(SPHINCS+) 도입을 중기 로드맵에 반영하는 것이 바람직하다.
참고자료
- NIST, FIPS 180-4 Secure Hash Standard(SHS), https://doi.org/10.6028/NIST.FIPS.180-4
- NIST, FIPS 202 SHA-3 Standard, https://doi.org/10.6028/NIST.FIPS.202
- NIST, FIPS 205 Stateless Hash-Based Digital Signature Standard(SLH-DSA), https://doi.org/10.6028/NIST.FIPS.205
- OWASP, Password Storage Cheat Sheet, https://cheatsheetseries.owasp.org/cheatsheets/Password_Storage_Cheat_Sheet.html
- Stevens et al., The first collision for full SHA-1(SHAttered), https://shattered.io/
- NIST, Transitioning the Use of Cryptographic Algorithms and Key Lengths(SP 800-131A), https://csrc.nist.gov/pubs/sp/800/131/a/r2/final
한 줄 요약: 암호학적 해시 함수는 역상·제2역상·충돌 저항성을 갖춘 일방향 요약 함수로, 생일 역설에 따른 보안강도 반감과 Merkle–Damgård의 길이확장 취약점을 이해해 무결성·서명·인증에는 SHA-2/3과 HMAC을, 비밀번호에는 소금·후추와 메모리 하드 Argon2id를 용도별로 적용하고, 양자 시대에는 출력 길이 상향과 해시 기반 서명으로 대응해야 하는 현대 보안의 핵심 원초다.