SHA-1

1. 개요

SHA-1은 매사추세츠 공과대학교의 로날드 리베스트가 설계한 메시지 다이제스트 알고리즘으로, MD2, MD4, MD5의 원리를 기반으로 하지만 160비트의 더 큰 해시 값을 생성한다. 1993년 미국 정부 표준 기관인 NIST에 의해 SHA-0으로 처음 발표되었으나, NSA에 의해 수정되어 SHA-1으로 1995년에 재발표되었다. 2000년대 중반부터 SHA-1에 대한 다양한 공격 방법이 발표되면서 보안 취약성에 대한 우려가 커졌으며, 2010년까지 SHA-2로의 전환이 권고되었다. 2017년에는 실제 SHA-1 충돌을 일으키는 공격이 발표되었고, 주요 IT 기업들은 SHA-1 지원을 중단했다. 현재는 SHA-2와 SHA-3가 SHA-1을 대체하여 사용되고 있으며, SHA-1 사양은 2030년 12월 31일에 폐지될 예정이다. SHA-1은 TLS/SSL, PGP, SSH 등 다양한 보안 애플리케이션에 사용되었으며, Git과 같은 분산 버전 관리 시스템에서도 활용되었다.

2. 역사

SHA-1은 매사추세츠 공과대학교의 로널드 리베스트가 MD4나 MD5와 같은 이전 해시 함수들의 설계를 바탕으로 만들었지만, 더 보수적인 설계를 채택했다.

1993년 NIST는 최초의 SHA-1 규격인 FIPS 180 "Secure Hash Standard"를 발표했으며, 이를 SHA-0이라고도 한다. 그러나 SHA-0은 발표 직후 NSA에 의해 철회되었고, 1995년 FIPS PUB 180-1로 개정된 버전이 발표되었다. 이것이 바로 SHA-1이며, SHA-0과 비교했을 때 압축 함수에서 비트 연산 중 하나인 회전(rotate) 연산이 추가된 것이 특징이다. NSA는 이 변경이 SHA-0의 보안 취약점을 개선했다고 발표했지만, 구체적인 증거나 추가 설명은 제공하지 않았다. 이후 SHA-0과 SHA-1 모두에서 보안 취약점이 지속적으로 보고되었다.

2.1. 개발 배경

SHA-1은 MIT의 로날드 리베스트가 MD2, MD4, MD5 해시 함수의 원리를 기반으로 설계되었지만, 더 큰 해시 값(160비트)을 생성한다.

SHA-1은 미국 정부의 Capstone 프로젝트의 일환으로 개발되었다. 1993년 미국 정부 표준 기관인 NIST(국립표준기술연구소)는 알고리즘의 원본 사양을 보안 해시 표준, FIPS PUB 180으로 발표했다. 이 초기 버전을 SHA-0이라고 부르기도 한다. SHA-0은 발표 직후 NSA에 의해 철회되었고, 1995년 FIPS PUB 180-1로 수정된 버전이 발표되었는데, 이것이 SHA-1이다. SHA-1은 SHA-0의 압축 함수에서 단일 비트 단위 회전을 추가하여 암호화 보안을 강화했다. NSA는 이것이 원래 알고리즘의 결함을 수정한 것이라고 밝혔지만, 자세한 설명은 제공하지 않았다.

2.2. SHA-1 폐지와 전환

2005년에 SHA-1에 대한 공격법이 발견되면서, 미래 사용에 대한 안전성 문제가 제기되었다. 미국 국립표준기술연구소(NIST)는 2010년까지 미국 정부 조직에 SHA-1에서 SHA-2로 전환할 것을 요청했다. SHA-2는 아직 유효한 공격이 보고되지 않았지만, SHA-1과 구조가 유사하다. 2012년에는 Keccak 알고리즘이 SHA-3으로 선정되었다.

2013년 11월, 마이크로소프트는 2017년까지 Microsoft Windows의 TLS/SSL에서 SHA-1 인증서를 허용하지 않겠다고 발표했다. 2014년 9월, 구글도 2017년까지 구글 크롬에서 SHA-1 인증서를 허용하지 않겠다고 발표했다. 모질라 역시 2017년까지 SHA-1 인증서 허용 중단을 검토했다.

일본 CRYPTREC는 2003년 초판에서 SHA-1을 권장 목록에 포함했으나, 2013년 개정에서 운용 감시 목록으로 변경했다. 총무성 및 법무성은 정부 인증 기반 및 전자 인증 등기소에서 SHA-1 전자 증명서 검증을 2015년까지(특별한 경우 2019년까지) 종료하기로 했다.

이에 따라 SHA-1을 사용하는 웹사이트는 SHA-2로 전환해야 하며, SHA-2를 지원하지 않는 소프트웨어나 기기는 접속이 불가능해진다. 특히 2009년 이전 휴대 전화는 일부를 제외하고 소프트웨어 업데이트가 없어 하드웨어 교체가 필요하다.

NIST는 2030년 12월 31일에 SHA-1 사양을 폐지할 예정이며, 이후 미국 정부는 SHA-1 사용 제품을 구매하지 않을 것이다.

3. 응용 분야

SHA-1은 TLS 및 SSL, PGP, SSH, S/MIME, IPsec 등 다양한 보안 애플리케이션 및 프로토콜에서 사용되었다. 이러한 응용 프로그램들은 MD5도 사용할 수 있었으며, MD5와 SHA-1은 모두 MD4에서 파생되었다.

SHA-1과 SHA-2는 기밀 해제된 중요 정보 보호를 위해 다른 암호화 알고리즘 및 프로토콜 내에서 사용을 포함하여 특정 미국 정부 응용 프로그램에서 법적으로 사용이 요구되는 해시 알고리즘이었다. FIPS PUB 180-1은 민간 및 상업 조직에서도 SHA-1의 채택 및 사용을 권장했다. 그러나 SHA-1은 대부분의 정부 사용에서 폐지되고 있으며, 미국 국립표준기술연구소는 "연방 기관은 충돌 저항이 필요한 응용 프로그램에 대해 가능한 한 빨리 SHA-1 사용을 중단해야 하며, 2010년 이후 이러한 응용 프로그램에 대해 SHA-2 제품군의 해시 함수를 사용해야 한다"고 밝혔다.

SHA 해시 함수는 SHACAL 블록 암호의 기반으로 사용되었다.

2005년에는 SHA-1에 대한 공격법이 발견되어 미래 사용에 충분한 안전성을 가지고 있지 않음이 시사되었다. 미국 국립표준기술연구소(NIST)는 미국 정부 조직에 대해 2010년까지 SHA-1에서 SHA-2로 이전할 것을 요청했다. 2013년 11월, 마이크로소프트는 2017년까지 Microsoft Windows의 TLS/SSL에서 SHA-1을 사용한 인증서를 더 이상 허용하지 않겠다고 발표했다. 2014년 9월, 구글도 2017년까지 구글 크롬에서 SHA-1에 의한 인증서를 허용하지 않겠다고 발표했다. 모질라 역시 2017년까지 SHA-1에 의한 인증서를 허용하지 않는 것을 검토하고 있다.

일본에서도 CRYPTREC가 2003년 초판에서는 권장 목록에 SHA-1을 포함했으나, 2013년 개정에서 호환성 유지를 위한 사용으로 제한한 운용 감시 목록으로 변경했다. 총무성 및 법무성에서는 정부 인증 기반 및 전자 인증 등기소(상업 등기 인증국)에서 SHA-1을 사용한 전자 증명서의 검증을 2015년도까지(특별한 사정이 있는 경우는 2019년도까지) 종료하기로 했다.

SHA-1 해시는 Git, Mercurial, Monotone과 같은 분산 버전 관리 시스템에서도 버전 관리와 데이터의 손상 및 변조 감지에 사용되고 있다. 닌텐도의 Wii에서는 기동 시 SHA-1에 의한 서명을 검증하지만, 이를 회피하는 수법도 개발되어 있다.

4. 암호 해독 및 유효성 검사

해시 함수에서 주어진 메시지 다이제스트(해시값)에 해당하는 원본 메시지를 찾는 것은 대략 2^L번의 평가를 통해 무차별 대입 공격으로 가능하다. 이를 원상 공격이라고 부르며, L(메시지 다이제스트의 비트 수)과 컴퓨팅 환경에 따라 현실적으로 가능할 수도, 불가능할 수도 있다.

생일 공격을 이용하면 평균적으로 1.2 x 2^L/2 번의 평가만으로 동일한 메시지 다이제스트를 생성하는 두 개의 다른 메시지, 즉 충돌을 찾을 수 있다. 따라서 해시 함수의 보안 수준은 일반적으로 메시지 다이제스트 길이의 절반인 대칭 암호와 비교된다. SHA-1은 160비트 메시지 다이제스트를 가지므로, 원래 80비트 강도를 갖는 것으로 여겨졌다.

암호화 해시를 사용하는 일부 응용 프로그램(예: 비밀번호 저장)은 충돌 공격에 큰 영향을 받지 않는다. 공격자가 특정 계정의 비밀번호를 알아내려면 사전 공격이 필요하며, 이 공격은 원본 비밀번호의 해시값에 접근해야 가능하다. 하지만 안전한 비밀번호 해시라도 약한 비밀번호에 대한 무차별 대입 공격은 막을 수 없다.

문서 서명의 경우, 공격자는 기존 문서의 서명을 위조할 수 없다. 대신 무해한 문서와 유해한 문서 한 쌍을 생성하고, 개인 키 소유자가 무해한 문서에 서명하도록 유도해야 한다. 2008년에는 MD5 충돌을 이용하여 위조된 SSL 인증서를 생성하는 것이 가능했다.

모든 SHA 함수(SHA-3 제외)는 알고리즘의 블록 및 반복 구조와 추가적인 최종 단계가 없기 때문에 길이 연장 공격 및 부분 메시지 충돌 공격에 취약하다.

4.1. 암호 해독 공격

SHA-1은 길이 확장 공격 및 부분 메시지 충돌 공격에 취약하다. 이러한 공격으로 인해 키를 알지 못하고도 메시지를 확장하고 해시를 다시 계산하여 메시지를 변조할 수 있다.

SHA-0 공격

* CRYPTO 98에서 프랑스 연구원 플로랑 샤보와 앙투안 주는 SHA-0에 대한 공격을 발표했는데, 충돌을 2⁶¹의 복잡도로 찾을 수 있었다.
* 2004년, 비함과 첸은 SHA-0에 대한 근접 충돌을 발견했다.
* 2004년 8월, Joux, Carribault, Lemuet 및 Jalby에 의해 전체 SHA-0 알고리즘에 대한 충돌이 발표되었다. 충돌을 찾는 복잡성은 2⁵¹이었다.
* 2005년 2월, 샤오윤 왕, 이윤 리사 인, 그리고 홍보 유에 의한 공격은 SHA-0에서 2³⁹ 연산으로 충돌을 찾을 수 있었다.

SHA-1 공격

* 2005년 초, 빈센트 레이먼과 엘리자베스 오스왈드는 SHA-1의 축소 버전(53라운드)에 대한 공격을 발표하여 2⁸⁰ 미만의 연산으로 충돌을 찾았다.
* 2005년 2월, 샤오윤 왕, 이퀸 리사 인, 훙보 유의 공격은 SHA-1 전체 버전에서 2⁶⁹ 미만의 연산으로 충돌을 찾을 수 있다고 발표했다.
* 2005년 8월, 샤오윈 왕, 앤드루 야오, 프란시스 야오는 SHA-1에서 충돌을 찾는 데 필요한 복잡성을 2⁶³으로 낮춘 공격을 발표했다.
* 2017년 2월 23일, CWI와 구글은 SHAttered 공격을 발표했는데, 약 2^63.1번의 SHA-1 평가를 거쳐 동일한 SHA-1 해시를 가진 두 개의 서로 다른 PDF 파일을 생성했다.
* 2019년, 가에탕 르렌트와 토마 페린은 선택 접두사 충돌 공격에 대한 개선 사항을 발표하여 약 2⁶⁸번의 SHA-1 평가로 선택 접두사 충돌을 찾을 수 있게 되었다.
* 2020년 1월, "shambles"라고 불리는 개선된 공격이 발표되었으며, 2^63.4의 복잡성을 가진 선택 접두사 충돌 공격을 시연했다.

4.2. 공식 유효성 검사

모든 FIPS 승인 보안 기능의 구현은 국립표준기술연구소(NIST)와 통신보안청(CSE)이 공동으로 운영하는 암호 모듈 유효성 검사 프로그램(CMVP)을 통해 공식적으로 유효성을 검사받을 수 있다. 비공식적인 확인을 위해, NIST 사이트에서 다수의 테스트 벡터를 생성하는 패키지를 다운로드할 수 있지만, 이 결과는 법적으로 요구되는 공식 CMVP 유효성 검사를 대체하지 않는다. 2013년 12월 기준으로, SHA-1의 유효성 검사를 받은 구현은 2000개가 넘으며, 그 중 14개는 비트 단위 메시지 길이가 8의 배수가 아닌 경우에도 처리할 수 있다.

5. 기술적 세부 사항

SHA-1은 로널드 리베스트가 MD2, MD4, MD5 등 메시지 다이제스트 알고리즘을 설계할 때 사용했던 원리와 유사하게 메시지 다이제스트를 생성한다. 다만, SHA-1은 더 큰 해시 값(128비트 대신 160비트)을 생성한다.

SHA-1 알고리즘의 의사 코드는 다음과 같다.

참고: 모든 변수는 부호 없는 32비트 양이며 계산 시 2³²를 모듈로로 감싼다. 단, ml (메시지 길이)은 64비트 양이며, hh (메시지 다이제스트)는 160비트 양이다.

변수 초기화:

```
h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0
```

전처리:
메시지에 비트 '1'을 추가하고, 0 ≤ k < 512 비트 '0'을 추가하여 비트 단위의 결과 메시지 길이가 합동 −64 ≡ 448 (mod 512)가 되도록 한다. 그리고 64비트 빅 엔디안 정수로 원본 메시지 길이인 ml을 추가한다.

메시지를 연속적인 512비트 청크로 처리:
메시지를 512비트 청크로 나누고, 각 청크를 16개의 32비트 빅 엔디안 단어 w[i](0 ≤ i ≤ 15)로 나눈다.

메시지 스케줄: 16개의 32비트 단어를 80개의 32비트 단어로 확장:
for i from 16 to 79
w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) 왼쪽 회전 1

이 청크에 대한 해시 값 초기화:
a = h0
b = h1
c = h2
d = h3
e = h4

메인 루프:
for i from 0 to 79
if 0 ≤ i ≤ 19 then
f = (b and c) or ((not b) and d)
k = 0x5A827999
else if 20 ≤ i ≤ 39
f = b xor c xor d
k = 0x6ED9EBA1
else if 40 ≤ i ≤ 59
f = (b and c) or (b and d) or (c and d)
k = 0x8F1BBCDC
else if 60 ≤ i ≤ 79
f = b xor c xor d
k = 0xCA62C1D6

temp = (a leftrotate 5) + f + e + k + w[i]
e = d
d = c
c = b leftrotate 30
b = a
a = temp

이 청크의 해시를 지금까지의 결과에 추가:
h0 = h0 + a
h1 = h1 + b
h2 = h2 + c
h3 = h3 + d
h4 = h4 + e

최종 해시 값을 160비트 숫자로 생성(빅 엔디안):
hh = (h0 leftshift 128) or (h1 leftshift 96) or (h2 leftshift 64) or (h3 leftshift 32) or h4

`hh`는 메시지 다이제스트이며, 16진수로 표현될 수 있다.

알고리즘에 사용된 상수 값은 nothing up my sleeve number로 가정되었다.

* 네 개의 라운드 상수 `k`는 2, 3, 5 및 10의 제곱근의 2³⁰배이다.
* `h0`부터 `h3`까지의 처음 네 개의 시작 값은 MD5 알고리즘과 동일하며 다섯 번째 값(`h4`의 경우)은 유사하다.

다음은 빈 문자열과 "The quick brown fox jumps over the lazy dog" 문장에 대한 SHA-1 해시 값 예시이다.

5.1. SHA-1 압축 함수

* A, B, C, D, E: 32비트 상태 워드
* F: 비선형 함수
*

_n: n만큼 왼쪽 회전
* n: 연산마다 변화
* W_t: 라운드 t에서의 확장 메시지 워드
* K_t: 라운드 t에서의 상수
* alt=⊞: modulo 2³² 덧셈

SHA-1은 MIT의 로널드 리베스트가 MD2, MD4, MD5 메시지 다이제스트 알고리즘을 설계할 때 사용했던 원리와 유사한 원리를 기반으로 메시지 다이제스트를 생성하지만, 더 큰 해시 값(128비트 대신 160비트)을 생성한다.

SHA-1 압축 함수는 5개의 32비트 워드(A, B, C, D, E)로 구성된 내부 상태를 사용하며, 80라운드에 걸쳐 연산을 수행한다. 각 라운드에서는 비선형 함수 F, 라운드 상수 K, 확장된 메시지 워드 W를 사용하여 내부 상태를 업데이트한다.

5.2. 의사 코드

SHA-1 알고리즘의 의사 코드는 다음과 같다.

참고 1: 모든 변수는 부호 없는 32비트 양이며 계산 시 2³²를 모듈로로 감쌉니다. 단,
ml (메시지 길이)은 64비트 양이며,
hh (메시지 다이제스트)는 160비트 양입니다.
참고 2: 이 의사 코드의 모든 상수는 빅 엔디안입니다.
각 단어 내에서 가장 중요한 바이트는 가장 왼쪽 바이트 위치에 저장됩니다.

변수 초기화:

```
h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0
```

ml = 비트 단위의 메시지 길이 (항상 문자 내 비트 수의 배수).

전처리:
메시지에 비트 '1'을 추가합니다(예: 메시지 길이가 8비트의 배수인 경우 0x80을 추가).
0 ≤ k < 512 비트 '0'을 추가하여 비트 단위의 결과 메시지 길이가
합동 −64 ≡ 448 (mod 512)가 되도록 합니다.
64비트 빅 엔디안 정수로 원본 메시지 길이인 ml을 추가합니다.
따라서 총 길이는 512비트의 배수입니다.

메시지를 연속적인 512비트 청크로 처리합니다:
메시지를 512비트 청크로 나눕니다.
for 각 청크
청크를 16개의 32비트 빅 엔디안 단어 w[i], 0 ≤ i ≤ 15로 나눕니다.

메시지 스케줄: 16개의 32비트 단어를 80개의 32비트 단어로 확장합니다:
for i from 16 to 79
참고 3: SHA-0은 이 왼쪽 회전이 없다는 점에서 다릅니다.
w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) 왼쪽 회전 1

이 청크에 대한 해시 값 초기화:
a = h0
b = h1
c = h2
d = h3
e = h4

메인 루프:
for i from 0 to 79
if 0 ≤ i ≤ 19 then
f = (b and c) or ((not b) and d)
k = 0x5A827999
else if 20 ≤ i ≤ 39
f = b xor c xor d
k = 0x6ED9EBA1
else if 40 ≤ i ≤ 59
f = (b and c) or (b and d) or (c and d)
k = 0x8F1BBCDC
else if 60 ≤ i ≤ 79
f = b xor c xor d
k = 0xCA62C1D6

temp = (a leftrotate 5) + f + e + k + w[i]
e = d
d = c
c = b leftrotate 30
b = a
a = temp

이 청크의 해시를 지금까지의 결과에 추가:
h0 = h0 + a
h1 = h1 + b
h2 = h2 + c
h3 = h3 + d
h4 = h4 + e

최종 해시 값을 160비트 숫자로 생성합니다(빅 엔디안):
hh = (h0 leftshift 128) or (h1 leftshift 96) or (h2 leftshift 64) or (h3 leftshift 32) or h4

`hh`라는 숫자는 메시지 다이제스트이며, 16진수(16진법)로 쓸 수 있다.

알고리즘에 사용된 선택된 상수 값은 nothing up my sleeve number로 가정되었다.

* 네 개의 라운드 상수 `k`는 2, 3, 5 및 10의 제곱근의 2³⁰배이다.
* `h0`부터 `h3`까지의 처음 네 개의 시작 값은 MD5 알고리즘과 동일하며 다섯 번째 값(`h4`의 경우)은 유사하다.

원래 FIPS PUB 180-1의 공식을 사용하는 대신, 메인 루프에서 `f`를 계산하기 위해 다음과 같은 등가 표현식을 사용할 수 있다.

c와 d 사이의 비트 단위 선택, b에 의해 제어됨.
(0 ≤ i ≤ 19): f = d xor (b and (c xor d)) (대안 1)

비트 단위 다수결 함수.
(40 ≤ i ≤ 59): f = (b and c) or (d and (b or c)) (대안 1)

5.3. 해시 값 예시

빈 문자열의 SHA-1 해시 값은 다음과 같다.

The quick brown fox jumps over the lazy dog의 SHA-1 해시 값은 다음과 같다.

6. 구현체

하드웨어 가속은 다음의 프로세서 확장에 의해 제공된다.

* 인텔 SHA 확장: 인텔 및 AMD x86 프로세서에서 이용 가능하다.
* VIA PadLock

7. SHA 함수 비교