SHA-1
-1( Secure Hash Algorithm 1은 데이터의 무결성을 검증, 디지털 서명, 인증서, 암호화 프로토콜 등 다양한 보안 응용 분야에서 사용되는 암호학적 해시 함수입니다. 1995년 국립표준기술연구소(NIST)와 국가안국(NSA)에 의해 개발된 SHA-1은 입력된 임의 길이의 데이터를 고정된 160비트(20바이트) 길이의 해시 값(다이제스트)으로 변환하는 기능을 수행합니다. 이 문서에서는 SHA-1의 작동 원리, 역사, 보안 취약점, 그리고 현재의 사용 현황에 대해 설명합니다.
개요
SHA-1은 메시지 다이제스트 알고리즘의 일종으로, 주어진 입력 데이터에 대해 고유한 해시 값을 생성합니다. 이 해시 값은 원본 데이터의 "지문(fingerprint)"과 유사한 역할을 하며, 입력 데이터가 조금만 변경되어도 완전히 다른 해시 값이 생성됩니다. 이러한 특성 덕분에 SHA-1은 파일 무결성 검사, 비밀번호 저장, SSL/TLS 인증서 서명 등에 널리 사용되었습니다.
하지만 2005년 이후로 SHA-1은 여러 보안 공격(특히 충돌 공격)에 취약하다는 것이 입증되었고, 현재는 사용이 권장되지 않는 알고리즘으로 분류됩니다. 대신 SHA-2 또는 SHA-3와 같은 더 안전한 해시 함수가 권장되고 있습니다.
작동 원리
입력 처리
SHA-1은 임의 길이의 메시지를 입력으로 받아 처리합니다. 입력 메시지는 다음 단계를 거칩니다:
- 패딩(Padding): 메시지 길이를 512비트의 배수로 맞추기 위해 패딩을 추가합니다.
- 우선
1 비트를 추가하고, 그 뒤에 0 비트를 연속으로 붙입니다.
-
마지막 64비트에는 원본 메시지의 길이(비트 단위)를 저장합니다.
-
블록 분할: 패딩된 메시지를 512비트 단위의 블록으로 나눕니다.
해시 연산
각 512비트 블록에 대해 다음과 같은 과정을 수행합니다:
- 블록을 16개의 32비트 단어로 분할합니다.
- 이후 80단계의 라운드 연산(round function)을 수행하며, 각 단계에서 비트 연산(AND, OR, XOR, NOT), 순환 시프트 등을 사용합니다.
- 5개의 32비트 초기 해시 값(
H0 ~ H4)을 업데이트하며 최종 다이제스트를 생성합니다.
최종적으로, 5개의 32비트 값이 결합되어 160비트의 해시 값(예: da39a3ee5e6b4b0d3255bfef95601890afd80709)이 출력됩니다.
역사와 발전
- 1993년: 최초의 SHA 알고리즘(SHA-0) 발표, 그러나 곧 취약점 발견.
- 1995년: NSA에 의해 수정된 SHA-1 발표.
- 2005년: 중국의 왕샤오윈(Xiaoyun Wang) 연구팀이 SHA-1에 대한 충돌 공격(Collision Attack)을 성공적으로 수행함. 이는 서로 다른 두 입력이 동일한 해시 값을 가질 수 있음을 의미.
- 2017년: 구글과 CWI 암스테르담 연구진이 SHAttered 공격을 발표. 두 개의 서로 다른 PDF 파일이 동일한 SHA-1 해시를 가지도록 만듦.
- 2020년 이후: 대부분의 주요 브라우저와 CA(인증 기관)가 SHA-1 기반 인증서의 발급 및 신뢰를 중단.
보안 취약점
충돌 공격 (Collision Attack)
SHA-1의 가장 큰 문제는 두 개의 서로 다른 입력이 동일한 해시를 생성할 수 있다는 점입니다. 이는 디지털 서명의 위조, 인증서 위변조 등 심각한 보안 사고로 이어질 수 있습니다.
예를 들어, 공격자가 합법적인 문서와 악성 문서를 만들어 SHA-1 해시를 동일하게 맞추면, 서명된 합법 문서처럼 위장할 수 있습니다.
전방 공격 (Pre-image Attack)
현재로서는 SHA-1에 대한 실용적인 전방 공격(주어진 해시 값에서 원본 메시지를 복원)은 알려져 있지 않으나, 충돌 공격의 존재로 인해 전반적인 신뢰도가 크게 하락했습니다.
사용 현황과 권장 사항
| 용도 |
현재 상태 |
| SSL/TLS 인증서 |
비권장, 대부분의 브라우저에서 경고 또는 차단 |
| Git 저장소 |
여전히 사용 중 (단, 보안 인증에는 사용되지 않음) |
| 비밀번호 해싱 |
절대 사용 금지, 약한 알고리즘 |
| 파일 무결성 검사 |
구형 시스템에서 일부 사용, 새 시스템은 SHA-256 권장 |
⚠️ NIST, IETF, CA/Browser Forum 등 주요 기관은 SHA-1의 사용을 2010년대 중반부터 중단할 것을 권고했으며, 2020년 이후로는 모든 보안 관련 용도에서 완전히 폐기되었습니다.
관련 알고리즘
- SHA-2: SHA-256, SHA-512 등 다양한 변종 존재. 현재 산업 표준.
- SHA-3: Keccak 알고리즘 기반, 구조적으로 SHA-1/2과 다름. 더 높은 보안성 보장.
라운드 함수 상세 구조
SHA-1의 80단계 라운드 연산은 20라운드씩 4개의 그룹으로 나뉘며, 각 그룹마다 서로 다른 논리 함수 $f$를 사용하여 비트 혼합을 수행합니다. 각 라운드에서 사용되는 논리식은 다음과 같습니다.
- 라운드 0~19: $\text{f}(t, a, b, c) = (a \land b) \lor (\neg a \land c)$
- 라운드 20~39: $\text{f}(t, a, b, c) = (a \land b) \lor (a \land c) \lor (b \land c)$
- 라운드 40~59: $\text{f}(t, a, b, c) = a \oplus b \oplus c$
- 라운드 60~79: $\text{f}(t, a, b, c) = (a \land b) \lor (\neg a \land c)$ (라운드 0~19와 동일)
여기서 $\land$는 AND, $\lor$는 OR, $\neg$는 NOT, $\oplus$는 XOR 연산을 의미합니다. 이러한 구조적 차이는 데이터의 확산(Diffusion) 효과를 극대화하여 입력값의 작은 변화가 결과값에 크게 영향을 미치도록 설계되었습니다.
충돌 공격의 수학적 배경과 SHAttered
생일 공격 (Birthday Attack)
SHA-1의 충돌 가능성은 확률론의 '생일 문제(Birthday Problem)'에 기반합니다. 이론적으로 160비트 해시 함수에서 충돌을 찾으려면 $2^{160}$번의 시도가 필요할 것 같지만, 실제로는 생일 공격을 통해 약 $2^{80}$번의 시도만으로도 충돌 쌍을 찾을 확률이 50%에 도달합니다. 이는 특정 해시 값과 일치하는 값을 찾는 '전방 공격'보다 훨씬 적은 연산량으로도 서로 다른 두 입력의 해시 값이 같아지는 지점을 찾을 수 있음을 의미합니다.
SHAttered 공격 사례
2017년 구글과 CWI 암스테르담은 SHA-1의 실질적인 충돌을 증명한 SHAttered 공격을 발표했습니다.
- 공격 방식: 특수하게 설계된 PDF 파일 두 개를 생성하여, 파일의 내용은 서로 다르지만 SHA-1 해시 값은 완전히 동일하게 만들었습니다.
- 예시 파일:
- 파일 A: 일반적인 텍스트가 포함된 PDF 문서.
- 파일 B: 파일 A와 시각적으로는 유사하나 내부 구조(메타데이터 및 바이너리 데이터)가 다른 PDF 문서.
- 결과: $\text{SHA-1}(\text{File A}) = \text{SHA-1}(\text{File B}) = \text{38763676... (동일한 160비트 값)}$
- 시사점: 이 공격은 SHA-1이 더 이상 디지털 서명의 무결성을 보장할 수 없음을 실증적으로 보여주었으며, 공격자가 정상 문서의 서명을 탈취해 악성 문서에 적용할 수 있는 위험성을 경고했습니다.
Git에서의 SHA-1 활용과 전환
내용 주소 지정 가능 저장소 (CAS)
Git은 데이터를 저장할 때 파일 이름이 아닌 파일 내용의 해시 값을 주소로 사용하는 내용 주소 지정 가능 저장소(Content-Addressable Storage) 방식을 채택하고 있습니다. SHA-1은 여기서 객체(Blob, Tree, Commit)의 고유 식별자(ID)를 생성하는 데 사용됩니다. 이는 동일한 내용의 파일이 여러 번 저장되더라도 단 하나의 해시 값으로 관리되어 저장 공간을 효율적으로 사용할 수 있게 합니다.
SHA-256으로의 전환
SHAttered 공격 이후, Git 커뮤니티는 SHA-1의 충돌 가능성이 저장소의 무결성을 해칠 수 있다고 판단하여 SHA-256으로의 전환을 추진하고 있습니다.
* 전환 메커니즘: 기존 SHA-1 기반 저장소와의 호환성을 유지하면서, 새로운 커밋부터 SHA-256을 선택적으로 사용할 수 있는 옵션을 도입하고 있습니다.
* 충돌 방지: Git은 단순 해시 비교 외에도 파일 크기나 추가적인 검증 단계를 통해 SHA-1 충돌로 인한 데이터 오염을 방지하는 보완책을 적용하고 있습니다.
SHA-1과 다른 해시 함수의 성능 비교
SHA-1은 보안성은 낮지만, 연산 구조가 단순하여 최신 알고리즘보다 처리 속도가 빠릅니다. 이는 과거 하드웨어 성능이 낮았던 시절에 큰 장점으로 작용했습니다.
| 알고리즘 |
해시 길이 |
보안 수준 |
상대적 연산 속도 |
주요 특징 |
| MD5 |
128-bit |
매우 낮음 |
매우 빠름 |
가장 빠르나 충돌 공격에 매우 취약 |
| SHA-1 |
160-bit |
낮음 |
빠름 |
속도와 보안의 타협점이었으나 현재는 취약 |
| SHA-256 |
256-bit |
높음 |
보통 |
현재 표준, SHA-1보다 연산 복잡도 높음 |
| SHA-512 |
512-bit |
매우 높음 |
보통/빠름* |
64비트 CPU 환경에서 SHA-256보다 효율적 |
*SHA-512는 64비트 아키텍처에서 32비트 기반의 SHA-256보다 처리 효율이 더 좋을 수 있습니다.
SHA-1의 설계 철학과 Merkle-Damgård 구조
SHA-1은 Merkle-Damgård 구조라는 전형적인 반복적 해시 함수 설계 방식을 따릅니다. 이 구조의 핵심은 임의 길이의 입력 메시지를 고정된 크기의 블록으로 나누어 순차적으로 처리함으로써, 최종적으로 고정된 길이의 해시 값을 생성하는 것입니다.
구조적 메커니즘
- 압축 함수(Compression Function): Merkle-Damgård 구조의 핵심 요소입니다. 이전 단계의 출력값(체이닝 변수)과 현재 처리할 메시지 블록을 입력으로 받아, 새로운 체이닝 변수를 생성합니다. SHA-1의 압축 함수는 80라운드의 비트 연산을 통해 입력 데이터의 작은 변화가 결과값 전체에 퍼지게 하는 '눈사태 효과(Avalanche Effect)'를 구현합니다.
- 반복 처리: 첫 번째 블록부터 마지막 블록까지 동일한 압축 함수를 반복 적용합니다. 이 과정에서 이전 블록의 결과가 다음 블록의 입력으로 전달되므로, 메시지의 어느 한 부분이라도 수정되면 최종 해시 값이 완전히 달라지게 됩니다.
- 최종화(Finalization): 모든 블록 처리가 끝나면 마지막 체이닝 변수가 최종 해시 값(다이제스트)으로 출력됩니다.
SHA-1과 SHA-256의 구조적 차이 비교
SHA-1과 그 후속 표준인 SHA-256은 모두 Merkle-Damgård 구조를 기반으로 하지만, 보안 강도를 높이기 위해 내부 연산 방식에서 큰 차이를 보입니다.
| 비교 항목 |
SHA-1 |
SHA-256 |
비고 |
| 출력 길이 |
160비트 |
256비트 |
출력값이 길수록 충돌 확률 급감 |
| 워드 크기 |
32비트 |
32비트 |
기본 연산 단위는 동일 |
| 라운드 수 |
80라운드 |
64라운드 |
SHA-256은 라운드 수는 적으나 각 단계가 더 복잡함 |
| 메시지 확장 |
단순 비트 회전 및 XOR |
시그마($\Sigma$) 함수를 이용한 복잡한 확장 |
SHA-256의 확장이 훨씬 비선형적임 |
| 논리 함수 |
4가지 단순 논리 함수 |
$\text{Ch}, \text{Maj}$ 및 복잡한 비트 시프트 조합 |
SHA-256이 수학적으로 더 견고함 |
| 보안 수준 |
취약 (충돌 가능) |
안전 (현재 표준) |
- |
기술적 세부 구현: 엔디언 및 초기 상수
SHA-1의 정확한 구현을 위해서는 패딩 단계의 바이트 순서와 초기 상태 값에 대한 정의가 필수적입니다.
엔디언(Endianness) 처리
SHA-1은 빅 엔디언(Big-Endian) 방식을 사용합니다.
- 메시지 블록: 512비트 블록을 32비트 단어로 나눌 때, 가장 중요한 바이트(MSB)가 먼저 옵니다.
- 길이 저장: 패딩의 마지막 64비트에 저장되는 원본 메시지 길이 역시 빅 엔디언 형식으로 기록됩니다. 만약 리틀 엔디언 시스템(x86 등)에서 구현할 경우, 바이트 순서를 뒤집는 과정이 반드시 필요합니다.
초기 해시 값 (Initial Hash Values)
알고리즘 시작 시 사용되는 5개의 32비트 초기 상수($H_0 \sim H_4$)는 다음과 같이 정의되어 있습니다. 이 값들은 임의의 상수가 아니라 설계 시 결정된 고정값입니다.
- $H_0 = \text{0x67452301}$
- $H_1 = \text{0xEFCDAB89}$
- $H_2 = \text{0x98BADCFE}$
- $H_3 = \text{0x10325476}$
- $H_4 = \text{0xC3D2E1F0}$
길이 연장 공격 (Length Extension Attack)
SHA-1은 Merkle-Damgård 구조의 특성상 길이 연장 공격에 취약합니다. 이는 공격자가 원본 메시지를 모르더라도, $\text{Hash}(\text{secret} \parallel \text{message})$ 값과 메시지의 길이만 알면 $\text{Hash}(\text{secret} \parallel \text{message} \parallel \text{padding} \parallel \text{extra\_data})$ 값을 계산할 수 있는 공격입니다.
공격 원리 및 흐름
- 상태 복구: SHA-1의 출력값은 곧 마지막 압축 함수의 결과(내부 상태)입니다. 공격자는 이 출력값을 다시 초기 해시 값($H_0 \sim H_4$)으로 설정하여 해시 함수를 재시작할 수 있습니다.
- 패딩 모사: 원본 메시지에 적용되었을 패딩을 계산하여 가짜 메시지 흐름을 만듭니다.
- 데이터 추가: 복구된 상태에서 새로운 데이터(
extra_data)를 입력하여 연산을 이어갑니다.
[길이 연장 공격 흐름도]
원본: [Secret] + [Message] $\rightarrow$ [SHA-1 상태(Hash)]
$\downarrow$
공격: [SHA-1 상태] $\rightarrow$ [추가 데이터] $\rightarrow$ [새로운 Hash]
$\downarrow$
결과: [Secret] + [Message] + [Padding] + [추가 데이터]의 해시값 생성 성공
이러한 취약점 때문에 단순한 $\text{Hash}(\text{key} \parallel \text{message})$ 방식의 MAC(메시지 인증 코드) 대신, HMAC($\text{Hash}(\text{K} \oplus \text{opad} \parallel \text{Hash}(\text{K} \oplus \text{ipad} \parallel \text{m}))$) 구조를 사용해야 합니다.
SHAttered 공격의 실제 충돌 사례
2017년 구글이 증명한 SHAttered 공격은 이론적인 충돌을 넘어 실제 파일 형태의 충돌을 보여주었습니다.
[SHAttered 충돌 PDF 예시]
- PDF 1: "Hello World"라는 텍스트가 적힌 문서 $\rightarrow$ SHA-1: 38763676...
- PDF 2: 전혀 다른 내용이나 시각적으로 유사한 문서 $\rightarrow$ SHA-1: 38763676...
- 특징: 두 파일의 바이너리 데이터는 서로 다르지만, SHA-1 알고리즘이 처리하는 내부 상태가 특정 지점에서 일치하도록 정교하게 조작되었습니다.
이 사례는 SHA-1을 이용한 파일 무결성 검사가 더 이상 신뢰될 수 없음을 시각적으로 증명한 결정적인 계기가 되었습니다.
Hardened SHA-1: Git의 충돌 방어 기제
Git은 SHA-1을 완전히 교체하기 전까지의 과도기적 조치로 Hardened SHA-1 메커니즘을 도입했습니다.
작동 방식
Hardened SHA-1은 단순히 해시 값을 계산하는 것에 그치지 않고, 연산 과정에서 충돌 공격에 사용되는 특정한 수학적 패턴이 나타나는지 실시간으로 감시합니다.
- 패턴 감지: SHAttered 공격과 같은 최신 충돌 공격들은 특정 비트 조합의 반복이나 특수한 차분(differential) 패턴을 이용합니다.
- 차단: Git의 하드닝된 구현체는 라운드 연산 중 이러한 '공격 징후'가 발견되면 즉시 연산을 중단하고 충돌 가능성 경고를 발생시켜, 악성 객체가 저장소에 삽입되는 것을 방지합니다.
현대적 관점에서의 SHA-1: 보안 vs 식별
오늘날 SHA-1은 '암호학적 보안 함수'로서는 사망 선고를 받았지만, '비암호학적 식별자'로서는 여전히 제한적으로 사용됩니다.
보안 목적 (폐기)
- 디지털 서명, SSL/TLS 인증서, 비밀번호 저장: 절대 사용 금지. 충돌 공격을 통해 위조된 인증서나 서명을 만들 수 있기 때문입니다.
식별 목적 (제한적 유효)
- 체크섬(Checksum), 캐시 키(Cache Key), 단순 ID: 의도적인 공격자가 개입하지 않는 환경(예: 네트워크 전송 중 단순 비트 오류 검출)에서는 여전히 유효합니다.
- 한계: 하지만 식별자로 사용할 때도 공격자가 의도적으로 동일한 ID를 가진 서로 다른 파일을 업로드하여 시스템 혼란을 야기하는 'ID 충돌 공격'의 위험이 항상 존재하므로, 점진적으로 SHA-256으로 전환하는 것이 권장됩니다.
참고 자료
결론
SHA-1은 과거 중요한 역할을 했던 해시 알고리즘이지만, 보안 취약성이 입증됨에 따라 현재는 사용해서는 안 되는 알고리즘입니다. 특히 보안이 중요한 시스템에서는 반드시 SHA-2(예: SHA-256) 이상의 알고리즘을 사용해야 하며, 새로운 시스템 설계 시 SHA-1은 배제되어야 합니다. 기술 발전과 함께 알고리즘의 수명 주기를 이해하고, 적절한 시기에 업그레이드하는 것이 사이버 보안의 핵심입니다.
# SHA-1
-1( Secure Hash Algorithm 1은 데이터의 무결성을 검증, 디지털 서명, 인증서, 암호화 프로토콜 등 다양한 보안 응용 분야에서 사용되는 **암호학적 해시 함수**입니다. 1995년 국립표준기술연구소(NIST)와 국가안국(NSA)에 의해 개발된 SHA-1은 입력된 임의 길이의 데이터를 고정된 160비트(20바이트) 길이의 해시 값(다이제스트)으로 변환하는 기능을 수행합니다. 이 문서에서는 SHA-1의 작동 원리, 역사, 보안 취약점, 그리고 현재의 사용 현황에 대해 설명합니다.
## 개요
SHA-1은 **메시지 다이제스트 알고리즘**의 일종으로, 주어진 입력 데이터에 대해 고유한 해시 값을 생성합니다. 이 해시 값은 원본 데이터의 "지문(fingerprint)"과 유사한 역할을 하며, 입력 데이터가 조금만 변경되어도 완전히 다른 해시 값이 생성됩니다. 이러한 특성 덕분에 SHA-1은 파일 무결성 검사, 비밀번호 저장, SSL/TLS 인증서 서명 등에 널리 사용되었습니다.
하지만 2005년 이후로 SHA-1은 여러 **보안 공격**(특히 충돌 공격)에 취약하다는 것이 입증되었고, 현재는 **사용이 권장되지 않는 알고리즘**으로 분류됩니다. 대신 SHA-2 또는 SHA-3와 같은 더 안전한 해시 함수가 권장되고 있습니다.
---
## 작동 원리
### 입력 처리
SHA-1은 임의 길이의 메시지를 입력으로 받아 처리합니다. 입력 메시지는 다음 단계를 거칩니다:
1. **패딩**(Padding): 메시지 길이를 512비트의 배수로 맞추기 위해 패딩을 추가합니다.
- 우선 `1` 비트를 추가하고, 그 뒤에 `0` 비트를 연속으로 붙입니다.
- 마지막 64비트에는 원본 메시지의 길이(비트 단위)를 저장합니다.
2. **블록 분할**: 패딩된 메시지를 512비트 단위의 블록으로 나눕니다.
### 해시 연산
각 512비트 블록에 대해 다음과 같은 과정을 수행합니다:
- 블록을 16개의 32비트 단어로 분할합니다.
- 이후 80단계의 **라운드 연산**(round function)을 수행하며, 각 단계에서 비트 연산(AND, OR, XOR, NOT), 순환 시프트 등을 사용합니다.
- 5개의 32비트 초기 해시 값(`H0` ~ `H4`)을 업데이트하며 최종 다이제스트를 생성합니다.
최종적으로, 5개의 32비트 값이 결합되어 **160비트의 해시 값**(예: `da39a3ee5e6b4b0d3255bfef95601890afd80709`)이 출력됩니다.
---
## 역사와 발전
- **1993년**: 최초의 SHA 알고리즘(SHA-0) 발표, 그러나 곧 취약점 발견.
- **1995년**: NSA에 의해 수정된 **SHA-1** 발표.
- **2005년**: 중국의 왕샤오윈(Xiaoyun Wang) 연구팀이 SHA-1에 대한 **충돌 공격**(Collision Attack)을 성공적으로 수행함. 이는 서로 다른 두 입력이 동일한 해시 값을 가질 수 있음을 의미.
- **2017년**: 구글과 CWI 암스테르담 연구진이 **SHAttered 공격**을 발표. 두 개의 서로 다른 PDF 파일이 동일한 SHA-1 해시를 가지도록 만듦.
- **2020년 이후**: 대부분의 주요 브라우저와 CA(인증 기관)가 SHA-1 기반 인증서의 발급 및 신뢰를 중단.
---
## 보안 취약점
### 충돌 공격 (Collision Attack)
SHA-1의 가장 큰 문제는 **두 개의 서로 다른 입력이 동일한 해시를 생성할 수 있다**는 점입니다. 이는 디지털 서명의 위조, 인증서 위변조 등 심각한 보안 사고로 이어질 수 있습니다.
예를 들어, 공격자가 합법적인 문서와 악성 문서를 만들어 SHA-1 해시를 동일하게 맞추면, 서명된 합법 문서처럼 위장할 수 있습니다.
### 전방 공격 (Pre-image Attack)
현재로서는 SHA-1에 대한 실용적인 전방 공격(주어진 해시 값에서 원본 메시지를 복원)은 알려져 있지 않으나, 충돌 공격의 존재로 인해 전반적인 신뢰도가 크게 하락했습니다.
---
## 사용 현황과 권장 사항
| 용도 | 현재 상태 |
|------|-----------|
| SSL/TLS 인증서 | **비권장**, 대부분의 브라우저에서 경고 또는 차단 |
| Git 저장소 | 여전히 사용 중 (단, 보안 인증에는 사용되지 않음) |
| 비밀번호 해싱 | **절대 사용 금지**, 약한 알고리즘 |
| 파일 무결성 검사 | 구형 시스템에서 일부 사용, 새 시스템은 SHA-256 권장 |
> ⚠️ **NIST, IETF, CA/Browser Forum** 등 주요 기관은 SHA-1의 사용을 2010년대 중반부터 중단할 것을 권고했으며, 2020년 이후로는 모든 보안 관련 용도에서 **완전히 폐기**되었습니다.
---
## 관련 알고리즘
- **SHA-2**: SHA-256, SHA-512 등 다양한 변종 존재. 현재 산업 표준.
- **SHA-3**: Keccak 알고리즘 기반, 구조적으로 SHA-1/2과 다름. 더 높은 보안성 보장.
---
## 라운드 함수 상세 구조
SHA-1의 80단계 라운드 연산은 20라운드씩 4개의 그룹으로 나뉘며, 각 그룹마다 서로 다른 논리 함수 $f$를 사용하여 비트 혼합을 수행합니다. 각 라운드에서 사용되는 논리식은 다음과 같습니다.
* **라운드 0~19**: $\text{f}(t, a, b, c) = (a \land b) \lor (\neg a \land c)$
* **라운드 20~39**: $\text{f}(t, a, b, c) = (a \land b) \lor (a \land c) \lor (b \land c)$
* **라운드 40~59**: $\text{f}(t, a, b, c) = a \oplus b \oplus c$
* **라운드 60~79**: $\text{f}(t, a, b, c) = (a \land b) \lor (\neg a \land c)$ (라운드 0~19와 동일)
여기서 $\land$는 AND, $\lor$는 OR, $\neg$는 NOT, $\oplus$는 XOR 연산을 의미합니다. 이러한 구조적 차이는 데이터의 확산(Diffusion) 효과를 극대화하여 입력값의 작은 변화가 결과값에 크게 영향을 미치도록 설계되었습니다.
## 충돌 공격의 수학적 배경과 SHAttered
### 생일 공격 (Birthday Attack)
SHA-1의 충돌 가능성은 확률론의 '생일 문제(Birthday Problem)'에 기반합니다. 이론적으로 160비트 해시 함수에서 충돌을 찾으려면 $2^{160}$번의 시도가 필요할 것 같지만, 실제로는 **생일 공격**을 통해 약 $2^{80}$번의 시도만으로도 충돌 쌍을 찾을 확률이 50%에 도달합니다. 이는 특정 해시 값과 일치하는 값을 찾는 '전방 공격'보다 훨씬 적은 연산량으로도 서로 다른 두 입력의 해시 값이 같아지는 지점을 찾을 수 있음을 의미합니다.
### SHAttered 공격 사례
2017년 구글과 CWI 암스테르담은 SHA-1의 실질적인 충돌을 증명한 **SHAttered** 공격을 발표했습니다.
* **공격 방식**: 특수하게 설계된 PDF 파일 두 개를 생성하여, 파일의 내용은 서로 다르지만 SHA-1 해시 값은 완전히 동일하게 만들었습니다.
* **예시 파일**:
* **파일 A**: 일반적인 텍스트가 포함된 PDF 문서.
* **파일 B**: 파일 A와 시각적으로는 유사하나 내부 구조(메타데이터 및 바이너리 데이터)가 다른 PDF 문서.
* **결과**: $\text{SHA-1}(\text{File A}) = \text{SHA-1}(\text{File B}) = \text{38763676... (동일한 160비트 값)}$
* **시사점**: 이 공격은 SHA-1이 더 이상 디지털 서명의 무결성을 보장할 수 없음을 실증적으로 보여주었으며, 공격자가 정상 문서의 서명을 탈취해 악성 문서에 적용할 수 있는 위험성을 경고했습니다.
## Git에서의 SHA-1 활용과 전환
### 내용 주소 지정 가능 저장소 (CAS)
Git은 데이터를 저장할 때 파일 이름이 아닌 파일 내용의 해시 값을 주소로 사용하는 **내용 주소 지정 가능 저장소(Content-Addressable Storage)** 방식을 채택하고 있습니다. SHA-1은 여기서 객체(Blob, Tree, Commit)의 고유 식별자(ID)를 생성하는 데 사용됩니다. 이는 동일한 내용의 파일이 여러 번 저장되더라도 단 하나의 해시 값으로 관리되어 저장 공간을 효율적으로 사용할 수 있게 합니다.
### SHA-256으로의 전환
SHAttered 공격 이후, Git 커뮤니티는 SHA-1의 충돌 가능성이 저장소의 무결성을 해칠 수 있다고 판단하여 **SHA-256**으로의 전환을 추진하고 있습니다.
* **전환 메커니즘**: 기존 SHA-1 기반 저장소와의 호환성을 유지하면서, 새로운 커밋부터 SHA-256을 선택적으로 사용할 수 있는 옵션을 도입하고 있습니다.
* **충돌 방지**: Git은 단순 해시 비교 외에도 파일 크기나 추가적인 검증 단계를 통해 SHA-1 충돌로 인한 데이터 오염을 방지하는 보완책을 적용하고 있습니다.
## SHA-1과 다른 해시 함수의 성능 비교
SHA-1은 보안성은 낮지만, 연산 구조가 단순하여 최신 알고리즘보다 처리 속도가 빠릅니다. 이는 과거 하드웨어 성능이 낮았던 시절에 큰 장점으로 작용했습니다.
| 알고리즘 | 해시 길이 | 보안 수준 | 상대적 연산 속도 | 주요 특징 |
| :--- | :---: | :---: | :---: | :--- |
| **MD5** | 128-bit | 매우 낮음 | 매우 빠름 | 가장 빠르나 충돌 공격에 매우 취약 |
| **SHA-1** | 160-bit | 낮음 | 빠름 | 속도와 보안의 타협점이었으나 현재는 취약 |
| **SHA-256** | 256-bit | 높음 | 보통 | 현재 표준, SHA-1보다 연산 복잡도 높음 |
| **SHA-512** | 512-bit | 매우 높음 | 보통/빠름* | 64비트 CPU 환경에서 SHA-256보다 효율적 |
*\*SHA-512는 64비트 아키텍처에서 32비트 기반의 SHA-256보다 처리 효율이 더 좋을 수 있습니다.*
## SHA-1의 설계 철학과 Merkle-Damgård 구조
SHA-1은 **Merkle-Damgård 구조**라는 전형적인 반복적 해시 함수 설계 방식을 따릅니다. 이 구조의 핵심은 임의 길이의 입력 메시지를 고정된 크기의 블록으로 나누어 순차적으로 처리함으로써, 최종적으로 고정된 길이의 해시 값을 생성하는 것입니다.
### 구조적 메커니즘
1. **압축 함수(Compression Function)**: Merkle-Damgård 구조의 핵심 요소입니다. 이전 단계의 출력값(체이닝 변수)과 현재 처리할 메시지 블록을 입력으로 받아, 새로운 체이닝 변수를 생성합니다. SHA-1의 압축 함수는 80라운드의 비트 연산을 통해 입력 데이터의 작은 변화가 결과값 전체에 퍼지게 하는 '눈사태 효과(Avalanche Effect)'를 구현합니다.
2. **반복 처리**: 첫 번째 블록부터 마지막 블록까지 동일한 압축 함수를 반복 적용합니다. 이 과정에서 이전 블록의 결과가 다음 블록의 입력으로 전달되므로, 메시지의 어느 한 부분이라도 수정되면 최종 해시 값이 완전히 달라지게 됩니다.
3. **최종화(Finalization)**: 모든 블록 처리가 끝나면 마지막 체이닝 변수가 최종 해시 값(다이제스트)으로 출력됩니다.
---
## SHA-1과 SHA-256의 구조적 차이 비교
SHA-1과 그 후속 표준인 SHA-256은 모두 Merkle-Damgård 구조를 기반으로 하지만, 보안 강도를 높이기 위해 내부 연산 방식에서 큰 차이를 보입니다.
| 비교 항목 | SHA-1 | SHA-256 | 비고 |
| :--- | :--- | :--- | :--- |
| **출력 길이** | 160비트 | 256비트 | 출력값이 길수록 충돌 확률 급감 |
| **워드 크기** | 32비트 | 32비트 | 기본 연산 단위는 동일 |
| **라운드 수** | 80라운드 | 64라운드 | SHA-256은 라운드 수는 적으나 각 단계가 더 복잡함 |
| **메시지 확장** | 단순 비트 회전 및 XOR | 시그마($\Sigma$) 함수를 이용한 복잡한 확장 | SHA-256의 확장이 훨씬 비선형적임 |
| **논리 함수** | 4가지 단순 논리 함수 | $\text{Ch}, \text{Maj}$ 및 복잡한 비트 시프트 조합 | SHA-256이 수학적으로 더 견고함 |
| **보안 수준** | 취약 (충돌 가능) | 안전 (현재 표준) | - |
---
## 기술적 세부 구현: 엔디언 및 초기 상수
SHA-1의 정확한 구현을 위해서는 패딩 단계의 바이트 순서와 초기 상태 값에 대한 정의가 필수적입니다.
### 엔디언(Endianness) 처리
SHA-1은 **빅 엔디언(Big-Endian)** 방식을 사용합니다.
- **메시지 블록**: 512비트 블록을 32비트 단어로 나눌 때, 가장 중요한 바이트(MSB)가 먼저 옵니다.
- **길이 저장**: 패딩의 마지막 64비트에 저장되는 원본 메시지 길이 역시 빅 엔디언 형식으로 기록됩니다. 만약 리틀 엔디언 시스템(x86 등)에서 구현할 경우, 바이트 순서를 뒤집는 과정이 반드시 필요합니다.
### 초기 해시 값 (Initial Hash Values)
알고리즘 시작 시 사용되는 5개의 32비트 초기 상수($H_0 \sim H_4$)는 다음과 같이 정의되어 있습니다. 이 값들은 임의의 상수가 아니라 설계 시 결정된 고정값입니다.
- $H_0 = \text{0x67452301}$
- $H_1 = \text{0xEFCDAB89}$
- $H_2 = \text{0x98BADCFE}$
- $H_3 = \text{0x10325476}$
- $H_4 = \text{0xC3D2E1F0}$
---
## 길이 연장 공격 (Length Extension Attack)
SHA-1은 Merkle-Damgård 구조의 특성상 **길이 연장 공격**에 취약합니다. 이는 공격자가 원본 메시지를 모르더라도, $\text{Hash}(\text{secret} \parallel \text{message})$ 값과 메시지의 길이만 알면 $\text{Hash}(\text{secret} \parallel \text{message} \parallel \text{padding} \parallel \text{extra\_data})$ 값을 계산할 수 있는 공격입니다.
### 공격 원리 및 흐름
1. **상태 복구**: SHA-1의 출력값은 곧 마지막 압축 함수의 결과(내부 상태)입니다. 공격자는 이 출력값을 다시 초기 해시 값($H_0 \sim H_4$)으로 설정하여 해시 함수를 재시작할 수 있습니다.
2. **패딩 모사**: 원본 메시지에 적용되었을 패딩을 계산하여 가짜 메시지 흐름을 만듭니다.
3. **데이터 추가**: 복구된 상태에서 새로운 데이터(`extra_data`)를 입력하여 연산을 이어갑니다.
**[길이 연장 공격 흐름도]**
`원본: [Secret] + [Message] $\rightarrow$ [SHA-1 상태(Hash)]`
$\downarrow$
`공격: [SHA-1 상태] $\rightarrow$ [추가 데이터] $\rightarrow$ [새로운 Hash]`
$\downarrow$
`결과: [Secret] + [Message] + [Padding] + [추가 데이터]의 해시값 생성 성공`
이러한 취약점 때문에 단순한 $\text{Hash}(\text{key} \parallel \text{message})$ 방식의 MAC(메시지 인증 코드) 대신, **HMAC**($\text{Hash}(\text{K} \oplus \text{opad} \parallel \text{Hash}(\text{K} \oplus \text{ipad} \parallel \text{m}))$) 구조를 사용해야 합니다.
---
## SHAttered 공격의 실제 충돌 사례
2017년 구글이 증명한 SHAttered 공격은 이론적인 충돌을 넘어 실제 파일 형태의 충돌을 보여주었습니다.
**[SHAttered 충돌 PDF 예시]**
- **PDF 1**: "Hello World"라는 텍스트가 적힌 문서 $\rightarrow$ `SHA-1: 38763676...`
- **PDF 2**: 전혀 다른 내용이나 시각적으로 유사한 문서 $\rightarrow$ `SHA-1: 38763676...`
- **특징**: 두 파일의 바이너리 데이터는 서로 다르지만, SHA-1 알고리즘이 처리하는 내부 상태가 특정 지점에서 일치하도록 정교하게 조작되었습니다.
이 사례는 SHA-1을 이용한 파일 무결성 검사가 더 이상 신뢰될 수 없음을 시각적으로 증명한 결정적인 계기가 되었습니다.
---
## Hardened SHA-1: Git의 충돌 방어 기제
Git은 SHA-1을 완전히 교체하기 전까지의 과도기적 조치로 **Hardened SHA-1** 메커니즘을 도입했습니다.
### 작동 방식
Hardened SHA-1은 단순히 해시 값을 계산하는 것에 그치지 않고, 연산 과정에서 **충돌 공격에 사용되는 특정한 수학적 패턴**이 나타나는지 실시간으로 감시합니다.
- **패턴 감지**: SHAttered 공격과 같은 최신 충돌 공격들은 특정 비트 조합의 반복이나 특수한 차분(differential) 패턴을 이용합니다.
- **차단**: Git의 하드닝된 구현체는 라운드 연산 중 이러한 '공격 징후'가 발견되면 즉시 연산을 중단하고 충돌 가능성 경고를 발생시켜, 악성 객체가 저장소에 삽입되는 것을 방지합니다.
---
## 현대적 관점에서의 SHA-1: 보안 vs 식별
오늘날 SHA-1은 **'암호학적 보안 함수'**로서는 사망 선고를 받았지만, **'비암호학적 식별자'**로서는 여전히 제한적으로 사용됩니다.
### 보안 목적 (폐기)
- **디지털 서명, SSL/TLS 인증서, 비밀번호 저장**: 절대 사용 금지. 충돌 공격을 통해 위조된 인증서나 서명을 만들 수 있기 때문입니다.
### 식별 목적 (제한적 유효)
- **체크섬(Checksum), 캐시 키(Cache Key), 단순 ID**: 의도적인 공격자가 개입하지 않는 환경(예: 네트워크 전송 중 단순 비트 오류 검출)에서는 여전히 유효합니다.
- **한계**: 하지만 식별자로 사용할 때도 공격자가 의도적으로 동일한 ID를 가진 서로 다른 파일을 업로드하여 시스템 혼란을 야기하는 'ID 충돌 공격'의 위험이 항상 존재하므로, 점진적으로 SHA-256으로 전환하는 것이 권장됩니다.
## 참고 자료
- [NIST FIPS 180-4: Secure Hash Standard](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf)
- [SHAttered: The First Practical Collision for SHA-1](https://shattered.io)
- [RFC 3174: US Secure Hash Algorithm 1 (SHA1)](https://tools.ietf.org/html/rfc3174)
---
## 결론
SHA-1은 과거 중요한 역할을 했던 해시 알고리즘이지만, **보안 취약성이 입증됨에 따라 현재는 사용해서는 안 되는 알고리즘**입니다. 특히 보안이 중요한 시스템에서는 반드시 **SHA-2**(예: SHA-256) 이상의 알고리즘을 사용해야 하며, 새로운 시스템 설계 시 SHA-1은 배제되어야 합니다. 기술 발전과 함께 알고리즘의 수명 주기를 이해하고, 적절한 시기에 업그레이드하는 것이 사이버 보안의 핵심입니다.