SHA-256
고친 사람 github-actions[bot]
SHA-256 은 데이터를 받아 그 데이터를 대신하는 짧은 값 하나를 만들어 줍니다. 무엇을 넣든 나오는 값은 언제나 256비트입니다. 데이터가 조금만 달라져도 값은 거의 확실히 달라집니다. 그래서 데이터가 바뀌었는지 가려내는 데 씁니다.
쉽고 빠른 이해
SHA-256 은 어떤 데이터든 받아 64글자짜리 16진수 문자열 하나로 바꿔 줍니다. 세 글자 abc 를 넣으면 ba7816bf 로 시작하는 64글자가 나옵니다.
이게 없으면 큰 파일 둘이 같은지 보려고 처음부터 끝까지 맞대 봐야 합니다. 한쪽의 짧은 값을 미리 적어 두면, 다른 쪽은 짧은 값끼리만 비교하면 끝납니다. 같은 값이 나오는 다른 데이터를 일부러 만들기는 계산으로 불가능에 가깝습니다. 그래서 값이 맞으면 내용이 안 바뀌었다고 믿습니다.
어떻게 도나:
- 데이터 끝에 비트 몇 개와 원래 길이를 붙여 512비트 단위로 맞춥니다
- 256비트 값 하나를 512비트 블록마다 한 번씩 고칩니다
- 마지막 블록까지 고친 그 값이 결과입니다
대가는 둘입니다. 계산을 일부러 비싸게 만드는 손잡이가 없어서 비밀번호를 저장하는 데는 혼자 못 씁니다. 비밀 값을 앞에 붙여 위조를 막는 용도에도 혼자 못 씁니다. 결과값에서 계산을 이어 갈 수 있기 때문입니다.
상세
SHA-256 은 Secure Hash Algorithm 256 의 줄임말입니다. 메시지를 받아 256비트 값 하나를 내는 계산 절차입니다. 메시지는 입력 데이터 전체를 가리킵니다. 길이가 2의 64제곱 비트보다 짧으면 무엇이든 받습니다.
세 글자 문자열 abc 를 넣으면 이 값이 나옵니다.
ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
256비트는 32바이트입니다. 16진수로 적으면 한 바이트가 두 글자라서 64글자가 됩니다. 이 결과가 해시값입니다. 메시지 다이제스트나 다이제스트도 같은 것을 가리키는 이름입니다.
이름의 Secure
이름의 Secure(안전한)는 두 가지 일이 계산으로 불가능하다(computationally infeasible)는 뜻입니다. 하나는 주어진 해시값을 내는 메시지를 찾는 일입니다. 다른 하나는 같은 해시값을 내는 서로 다른 두 메시지를 찾는 일입니다. 앞의 성질이 역상 저항성, 뒤의 성질이 충돌 저항성입니다.
이 성질 덕분에 해시값이 메시지를 대신할 수 있습니다. 메시지가 조금이라도 바뀌면 아주 높은 확률로 해시값도 달라집니다. 해시값만 비교해도 내용이 바뀌었는지 아는 까닭입니다.
이 성질에 기대는 것이 전자 서명과 메시지 인증 코드입니다. 메시지 인증 코드는 비밀 값을 나눠 가진 쪽끼리 메시지가 안 바뀌었음을 확인하는 값입니다. 둘 다 해시 함수와 함께 쓰면, 메시지가 바뀌었을 때 검증이 실패합니다.
전처리와 해시 계산
계산은 두 단계로 나뉩니다. 첫 단계는 전처리입니다. 메시지 끝에 비트를 덧붙여 길이를 512비트의 배수로 맞춥니다. 이 덧붙이기를 패딩이라고 합니다.
전처리는 패딩한 메시지를 512비트씩 자릅니다. 이 한 덩어리가 블록입니다. 그리고 계산을 시작할 256비트 값을 놓습니다. 이 값이 초기 해시값입니다.
둘째 단계는 해시 계산입니다. 블록을 처음부터 하나씩 받아 256비트 값을 고쳐 나갑니다. 블록 하나를 처리할 때마다 나오는 값을 중간 해시값이라고 합니다. 마지막 블록을 처리한 중간 해시값이 곧 해시값입니다.
SHA-2 가족
SHA-256 은 SHA-2(Secure Hash Algorithm 2) 가족의 하나입니다. 가족은 같은 두 단계 틀을 씁니다.
가족끼리 가장 크게 갈리는 것은 보안 강도입니다. 보안 강도는 해시를 깨는 데 드는 일의 양을 비트 수로 적은 값입니다. 128비트면 2의 128제곱만큼의 일이 든다는 뜻입니다. SHA-256 의 강도는 보장과 가정 절이 다룹니다.
표에 적힌 값으로는 받는 메시지 길이, 블록 크기, 워드 크기, 출력 길이가 갈립니다. 워드는 계산이 한 번에 다루는 비트 묶음입니다.
| 알고리즘 | 메시지 길이 | 블록 | 워드 | 출력 |
|---|---|---|---|---|
| SHA-224 | 2의 64제곱 비트 미만 | 512비트 | 32비트 | 224비트 |
| SHA-256 | 2의 64제곱 비트 미만 | 512비트 | 32비트 | 256비트 |
| SHA-384 | 2의 128제곱 비트 미만 | 1024비트 | 64비트 | 384비트 |
| SHA-512 | 2의 128제곱 비트 미만 | 1024비트 | 64비트 | 512비트 |
| SHA-512/224 | 2의 128제곱 비트 미만 | 1024비트 | 64비트 | 224비트 |
| SHA-512/256 | 2의 128제곱 비트 미만 | 1024비트 | 64비트 | 256비트 |
표는 두 갈래로 나뉩니다. SHA-224 와 SHA-256 은 512비트 블록과 32비트 워드를 씁니다. 나머지 넷은 1024비트 블록과 64비트 워드를 씁니다.
SHA-224 와 SHA-256 은 블록을 처리하는 계산이 똑같습니다. 다른 것은 초기 해시값과 마지막에 내보내는 길이뿐입니다. SHA-512/256 은 출력 길이만 SHA-256 과 같습니다. 계산은 1024비트 블록 갈래를 따릅니다.
복잡도
SHA-256 의 계산 시간은 메시지 길이에 비례합니다. 더 쓰는 메모리는 메시지 길이와 상관없이 일정합니다. 입력 값에 따라 갈리는 분기가 없어서 평균과 가장 오래 걸리는 경우가 같습니다.
비용을 정하는 것은 블록 수입니다. 블록 하나마다 같은 일을 같은 횟수만큼 하기 때문입니다. 메시지 길이를 L, 블록 수를 N 이라고 두면 N 은 L 에서 바로 나옵니다. L 은 바이트가 아니라 비트로 셉니다.
패딩은 메시지 뒤에 적어도 65비트를 붙입니다. 비트 1 하나와 원래 길이를 적는 64비트입니다. 따라서 N 은 L + 65 를 512 로 나눠 올림한 값입니다.
| 메시지 | 길이 L | L + 65 | 블록 수 N |
|---|---|---|---|
abc |
24비트 | 89비트 | 1 |
abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq (56글자) |
448비트 | 513비트 | 2 |
둘째 줄은 메시지가 448비트만 돼도 블록이 둘로 늘어나는 것을 보입니다. 첫 블록에는 길이 64비트가 들어갈 공간이 안 남습니다. 그래서 0 을 511개 채운 뒤 길이를 둘째 블록 끝에 적습니다.
block-beta columns 3 a["블록 1 · 메시지 448비트"] b["비트 1"] c["0 · 63비트"] d["블록 2 · 0 · 448비트"]:2 e["길이 448 · 64비트"]
블록 하나를 처리하는 일은 같은 계산 단계를 64번 되풀이하는 것입니다. 이 한 번을 라운드라고 합니다. 라운드를 도는 동안 32비트 워드 네 묶음을 들고 있습니다.
| 값 | 워드 수 | 무엇인가 |
|---|---|---|
| 중간 해시값 | 8 | 앞 블록이 남긴 256비트 값. 다음 블록으로 넘어간다 |
| 작업 변수 | 8 | 블록 하나를 처리하는 동안 라운드마다 고쳐지는 값 |
| 메시지 스케줄 | 64 | 라운드마다 하나씩 쓰는 워드 표. 처음 16워드는 블록에서 가져온다. 나머지 48워드는 새로 계산한다 |
| 임시 워드 | 2 | 라운드 하나 안에서만 쓰는 값 |
이 값들로 비용을 세면 이렇습니다.
| 항목 | 비용 | 왜 |
|---|---|---|
| 블록 하나 | 라운드 64번 · 워드 48개 새로 계산 | 라운드 수와 워드 수가 입력과 상관없이 고정이다 |
| 전체 시간 | O(L) | 블록 수 N 은 L 에 비례한다. 블록당 비용은 고정이다 |
| 추가 공간 | O(1) · 32비트 워드 82개 | 위 표의 8 + 8 + 64 + 2 |
| 평균과 가장 오래 걸리는 경우 | 같다 | 반복 횟수가 입력 값에 따라 안 바뀐다 |
추가 공간이 일정한 까닭은 블록 처리 순서에 있습니다. 블록은 순서대로 처리됩니다. 각 블록은 직전 중간 해시값만 씁니다. 덕분에 메시지 전체를 메모리에 올릴 필요가 없습니다. 블록이 들어오는 대로 흘려 넣으며 계산할 수 있습니다.
예시
SHA-256 이 들어간 실물 셋을 듭니다. Git 과 OCI(Open Container Initiative) 이미지는 SHA-256 을 씁니다. 비트코인은 작업 증명에 쓸 해시 함수로 SHA-256 을 예로 듭니다.
셋에서 해시값이 맡는 일이 다릅니다. Git 은 내용에 이름을 붙입니다. OCI 이미지는 받은 내용을 검증합니다. 비트코인은 계산에 든 비용을 증거로 씁니다.
Git
Git 은 버전 관리 시스템입니다. 그 바탕은 내용으로 주소를 매기는 파일 시스템입니다. 파일·디렉터리·리비전을 일련번호가 아니라 내용의 해시값으로 부릅니다.
이름이 곧 해시값이라 손상을 찾기 쉽습니다. 내용에서 비트 하나가 뒤집혀도 다시 계산한 해시값이 이름과 안 맞습니다.
Git 은 오래 SHA-1(Secure Hash Algorithm 1)로 이름을 지었습니다. SHA-1 은 출력이 160비트인, SHA-2 보다 앞선 해시 함수입니다. Git 은 이것을 더 강한 해시로 옮기는 중입니다. 2018년 말에 후임으로 SHA-256 을 골랐습니다. 후보는 SHA-256 과 SHA-512/256 을 비롯해 다섯이었습니다.
고른 기준은 SHA-1 보다 강하고 적어도 10년은 믿고 쓸 수 있는 해시였습니다. 함께 본 성질은 출력이 256비트일 것, 품질 높은 구현이 널리 있을 것, 성질이 Git 에 맞을 것입니다. 계산이 금방 끝나는지는 나머지가 비길 때 가르는 기준이었습니다.
Git 에 필요한 성질은 충돌 저항성과 제2 역상 저항성입니다. 제2 역상 저항성은 주어진 입력과 해시값이 같은 다른 입력을 찾기 어렵다는 성질입니다. 길이 확장 공격에 버티는 성질은 필요 없다고 봤습니다. 길이 확장 공격은 해시값에서 계산을 이어 가 더 긴 메시지의 해시값을 만드는 공격입니다.
저장소를 만들 때 객체 이름에 쓸 해시를 고릅니다.
git init --object-format=sha256
고를 수 있는 값은 sha1 과 sha256 둘입니다. sha256 에는 그 기능이 켜져 있어야 한다는 조건이 붙습니다. 무엇으로 켜는지는 자료에 없습니다(미확인). 기본값은 sha1 입니다.
지금은 SHA-256 저장소와 SHA-1 저장소 사이에 서로 오가는 길이 없습니다. 객체 이름은 16진수로 SHA-1 에서 40글자, SHA-256 에서 64글자입니다.
OCI 이미지
OCI 이미지 형식은 컨테이너 이미지를 이루는 조각을 다이제스트로 가리킵니다. 이 형식에서 다이제스트는 해시값 앞에 알고리즘 이름과 콜론을 붙인 문자열 전체를 가리킵니다.
sha256:6c3c624b58dbbcd3c0dd82b4c53f04194d1247c6eebdaab7c610cf7d66709b3b
이 문자열은 내용을 가리키는 이름이면서 검증 수단입니다. 받은 바이트의 SHA-256 을 직접 다시 계산해서 적힌 값과 견줍니다. 다이제스트를 안전한 길로 받았다면, 내용은 믿을 수 없는 곳에서 받아도 바뀌지 않았음을 확인할 수 있습니다.
OCI 형식이 다이제스트에 거는 규칙은 다섯입니다.
| 규칙 | 강도 |
|---|---|
| 믿을 수 없는 곳에서 받은 내용은 쓰기 전에 다이제스트와 맞춰 본다 | 권장(SHOULD) |
| 다이제스트를 계산하기 전에 내용 크기부터 맞춰 봐서 충돌을 노릴 여지를 줄인다 | 권장(SHOULD) |
| 다이제스트 알고리즘으로 SHA-256 을 쓴다 | 권장(SHOULD) |
| 구현은 SHA-256 다이제스트 검증을 갖춘다 | 필수(MUST) |
sha256 다음의 값은 소문자 16진수 64글자이고 대문자를 쓰지 않는다 |
필수(MUST) · 금지(MUST NOT) |
SHA-256 을 고른 까닭은 충돌 저항성, 어디서나 쓸 수 있다는 점, 알맞은 길이, 안전한 성질이었습니다.
비트코인
비트코인은 계산에 든 비용을 증거로 씁니다. 이것을 작업 증명이라고 합니다. 여기서 블록은 거래를 묶은 비트코인의 블록입니다. SHA-256 의 512비트 블록과 다른 것입니다.
작업 증명은 블록 안의 논스(nonce, 한 번 쓰고 마는 수)를 하나씩 올려 가며 값을 찾는 일입니다. 블록을 SHA-256 같은 해시 함수에 넣었을 때 해시값이 정해진 개수의 0 비트로 시작해야 합니다. 찾는 데 드는 평균 일은 요구하는 0 비트 수에 지수로 늘어납니다. 확인은 해시 한 번이면 끝납니다.
일단 찾으면 그 블록은 일을 다시 하지 않고는 못 바꿉니다. 뒤에 이어진 블록이 있으면 그 블록들의 일까지 다시 해야 합니다.
동작
이 절은 메시지 abc 하나가 해시값이 되기까지의 단계를 따라갑니다. 단계마다 무엇이 바뀌는지 적습니다.
줄이면 세 단계입니다. 메시지를 512비트 블록으로 맞춥니다. 블록마다 중간 해시값을 한 번씩 고칩니다. 마지막 중간 해시값을 내보냅니다.
패딩
메시지 길이를 L 비트라고 합니다. 메시지 끝에 비트 1 을 하나 붙입니다. 그 뒤에 0 을 여러 개 붙입니다. 마지막으로 L 을 64비트 이진수로 붙입니다.
0 의 개수는 메시지와 비트 1 과 0 을 합친 길이를 512 로 나눈 나머지가 448 이 되게 하는 가장 작은 수입니다. 448 에 마지막 64비트를 더하면 512 가 됩니다. 그래서 패딩이 끝난 메시지는 길이가 512의 배수입니다.
abc 는 한 글자가 8비트라서 L = 24 입니다. 비트 1 하나를 붙입니다. 이어서 0 을 448 − 25 = 423개 붙입니다. 마지막으로 길이 24 를 64비트로 붙입니다. 합치면 512비트 블록 하나입니다.
block-beta columns 2 a["메시지 abc · 24비트"] b["비트 1 · 1비트"] c["0 · 423비트"] d["길이 24 · 64비트"] t["합계 512비트 · 블록 하나"]:2
블록 나누기
패딩한 메시지를 512비트 블록 N 개로 자릅니다. 블록 하나는 32비트 워드 16개로 읽습니다. abc 는 블록이 하나라서 N = 1 입니다.
초기 해시값
계산은 32비트 워드 8개로 된 초기 해시값에서 시작합니다. 이 값은 첫 소수 여덟 개(2, 3, 5, 7, 11, 13, 17, 19)의 제곱근에서 소수부의 앞 32비트를 딴 것입니다.
6a09e667 bb67ae85 3c6ef372 a54ff53a 510e527f 9b05688c 1f83d9ab 5be0cd19
블록 하나의 계산
블록 하나는 네 단계로 처리합니다. 결과는 새 중간 해시값 하나입니다.
flowchart TD
B["블록 · 워드 16개"] --> W["메시지 스케줄 · 워드 64개로 늘린다"]
H0["직전 중간 해시값 · 워드 8개"] --> V["작업 변수 a~h 에 옮긴다"]
W --> R["라운드 64번"]
V --> R
R --> N["작업 변수를 직전 중간 해시값에 더한다"]
N --> H1["새 중간 해시값"]
첫째, 메시지 스케줄을 만듭니다. 블록의 워드 16개를 64워드로 늘린 표입니다. 처음 16워드는 블록의 워드를 손대지 않고 씁니다. 나머지 48워드는 앞서 만든 워드 넷을 비트 회전·시프트·덧셈으로 섞어 만듭니다. t 번째 워드라면 t−2 · t−7 · t−15 · t−16 번째 워드가 그 넷입니다.
둘째, 작업 변수 여덟 개 a·b·c·d·e·f·g·h 를 놓습니다. 작업 변수는 블록 하나를 처리하는 동안 고쳐지는 32비트 값입니다. 처음에는 직전 중간 해시값의 여덟 워드를 손대지 않고 옮겨 담습니다.
셋째, 라운드를 64번 돕니다. 라운드 t 마다 상수 Kt 하나와 메시지 스케줄 워드 Wt 하나를 넣습니다. 한 라운드는 이렇게 생겼습니다.
T1 = h + BSIG1(e) + CH(e,f,g) + Kt + Wt
T2 = BSIG0(a) + MAJ(a,b,c)
h = g g = f f = e e = d + T1
d = c c = b b = a a = T1 + T2
T1 과 T2 가 임시 워드입니다. 그 라운드 안에서만 쓰는 값입니다. 아래 두 줄에서 변수 여덟 개가 한 칸씩 밀립니다. 새로 들어오는 a 와 e 에만 섞은 값이 들어갑니다.
CH 는 e 의 비트를 보고 f 와 g 가운데 한쪽 비트를 고릅니다. MAJ 는 a·b·c 세 비트 가운데 다수를 따릅니다. BSIG0 과 BSIG1 은 한 워드를 세 번 다르게 회전해 비트마다 섞습니다.
상수 Kt 는 64개입니다. 첫 소수 64개의 세제곱근에서 소수부의 앞 32비트를 딴 값입니다. 첫 값은 428a2f98 입니다. 덧셈은 전부 2의 32제곱으로 나눈 나머지만 남깁니다. 32비트를 넘친 부분은 버린다는 뜻입니다.
넷째, 작업 변수를 직전 중간 해시값에 워드끼리 더합니다. 그 결과가 새 중간 해시값입니다. abc 의 64라운드가 끝났을 때 a 는 506e3058 입니다. 이것을 초기 해시값의 첫 워드에 더하면 6a09e667 + 506e3058 = ba7816bf 입니다. 상세 절에서 본 해시값의 첫 여덟 글자입니다.
출력
마지막 블록까지 처리한 중간 해시값의 여덟 워드를 순서대로 이어 붙인 것이 해시값입니다. 32비트 여덟 개라서 256비트입니다.
블록 사이의 사슬
블록 하나의 결과는 다음 블록 계산의 출발점이 됩니다. 블록마다 처음부터 다시 시작하지 않습니다. 앞 블록이 남긴 중간 해시값 위에서 이어 갑니다.
flowchart TD
H0["초기 해시값"] --> C1["블록 1 계산"]
C1 --> H1["중간 해시값 1"]
H1 --> C2["블록 2 계산"]
C2 --> H2["중간 해시값 2"]
H2 --> CN["블록 N 까지 같은 계산"]
CN --> OUT["마지막 중간 해시값 = 해시값 · 256비트"]
블록 하나를 처리하는 계산을 압축 함수라고 합니다. 압축 함수를 블록마다 되풀이해 앞 결과를 이어 가는 얼개가 머클-담고르 구조입니다. 그림에서 볼 것은 해시값이 마지막 중간 해시값 그 자체라는 점입니다. 보장과 가정 절의 길이 확장 공격이 이 점에서 나옵니다.
보장과 가정
이 절은 SHA-256 의 약속과 그 약속이 서 있는 바탕을 다룹니다. 결론은 셋입니다. 보장은 출력 길이에서 나오는 기대 강도입니다. 그 강도는 지름길 공격이 없다는 가정에 기댑니다. 길이 확장과 비밀번호 저장은 처음부터 약속 밖입니다.
세 가지 저항성
약속은 세 가지입니다. 각각 어떤 일을 계산으로 불가능하게(computationally infeasible) 만드는지가 다릅니다. 강도 128비트는 그 일을 높은 확률로 해내는 데 2의 128제곱만큼의 일이 든다는 뜻입니다.
| 성질 | 어려워야 하는 일 | SHA-256 의 기대 강도 |
|---|---|---|
| 충돌 저항성 | 해시값이 같은 서로 다른 두 입력을 찾는다 | 128비트 |
| 역상 저항성 | 무작위로 고른 해시값을 내는 입력을 찾는다 | 256비트 |
| 제2 역상 저항성 | 주어진 입력과 해시값이 같은 다른 입력을 찾는다 | 201~256비트 |
역상 저항성은 일방향 성질이라고도 부릅니다. 제2 역상 저항성은 메시지 길이에 따라 갈립니다. 입력이 허용 길이의 끝까지 길면 201비트 쪽입니다. 비교적 짧으면 256비트 쪽입니다.
한 쓰임이 성질 여럿을 필요로 하면 그중 가장 약한 성질이 그 쓰임의 강도입니다. 서명처럼 충돌이 문제가 되는 쓰임에서 SHA-256 의 강도는 128비트입니다.
충돌 강도가 출력 길이의 절반인 까닭
해시값이 2의 256제곱 가지라도 충돌을 찾는 데 그만큼의 일이 들지는 않습니다. 입력을 무작위로 골라 해시값을 모아 가면, 2의 128제곱 개 안팎에서 서로 겹치는 쌍이 나올 확률이 무시 못 할 만큼 커집니다.
한 반에 스물세 명만 있어도 생일이 같은 두 사람이 있을 확률이 절반을 넘습니다. 이 현상을 생일 문제라고 합니다. 스물세 명이면 서로 견줄 두 사람 쌍이 253개나 됩니다. 쌍의 수는 사람 수의 제곱에 맞춰 늘어납니다.
그래서 겹침은 가짓수 전체가 아니라 가짓수의 제곱근 근처에서 흔해집니다. 365 의 제곱근은 19 남짓입니다. 해시값에 대면 2의 256제곱 가지의 제곱근이 2의 128제곱입니다. 지수가 절반이 되므로 기대 충돌 강도는 출력 길이의 절반인 128비트입니다.
지름길 공격이 없다는 가정
위 강도는 무차별 대입보다 빠른 공격 방법이 없을 때의 값입니다. NIST(National Institute of Standards and Technology, 미국 국립표준기술연구소)가 승인한 해시 함수는 SHA-1 을 빼면 모두 충돌 강도가 출력 길이의 절반이라고 2012년 기준으로 믿어집니다. 역상을 찾는 지름길도 그때까지 알려진 것이 없었습니다.
이 가정은 같은 얼개의 이전 함수에서 실제로 깨졌습니다. SHA-1 은 SHA-256 과 같은 패딩, 같은 512비트 블록, 같은 32비트 워드를 씁니다. 출력이 160비트라서 기대 충돌 강도는 그 절반인 80비트입니다. 그런데 2005년에 SHA-1 의 충돌 저항성을 겨눈 심각한 공격이 발표됐습니다. 2012년 기준으로 SHA-1 의 충돌 강도는 80비트보다 크게 낮을 수 있다고 봅니다.
서명 밖의 쓰임을 겨눈 SHA-1 공격도 2022년 공지 기준으로 최근 몇 년 사이 점점 심해졌습니다. 그 결과 NIST 는 2030년 12월 31일까지 모든 쓰임에서 SHA-1 을 걷어 내기로 했습니다.
MD5(Message-Digest Algorithm 5)에서도 충돌 저항성 가정이 깨졌습니다. 2004년에 서로 다른 메시지 두 쌍의 충돌이 처음 발표됐습니다. 2006년에는 노트북 한 대로 1분 안팎에 충돌을 찾는 공격이 나왔습니다. MD5 는 전자 서명처럼 충돌 저항성이 필요한 곳에서 더는 받아들여지지 않습니다.
가정이 깨지면 그 가정에 기댄 보장부터 무너집니다. 충돌 저항성은 전자 서명이 기대는 성질입니다. 두 함수 모두 서명 쓰임에서 먼저 물러난 까닭입니다.
비밀을 앞에 붙인 인증과 길이 확장
메시지 인증 코드는 비밀 값을 나눠 가진 쪽끼리 메시지가 안 바뀌었음을 확인하는 값입니다. 이 값을 가장 단순하게 만드는 방법은 비밀 값 k 를 메시지 x 앞에 붙여 해시하는 것입니다. 보내는 쪽은 그 해시값을 메시지와 함께 보냅니다. 받는 쪽은 같은 k 로 같은 계산을 해서 값을 견줍니다.
이 구성은 길이 확장 공격에 뚫립니다. 조건은 x 가 블록 정수 개로 딱 떨어지는 것입니다. 동작 절에서 본 대로 해시값은 마지막 중간 해시값 그 자체입니다. 공격자는 그 해시값을 중간 해시값으로 놓고 계산을 이어 갑니다. 그러면 k 를 모르는 채로, x 를 앞부분으로 품은 더 긴 메시지의 값을 만들어 냅니다.
flowchart TD
A["비밀 값 k + 메시지 x"] --> B["블록 계산을 되풀이한다"]
B --> C["해시값 · 마지막 중간 해시값"]
C --> D["정상 검증 · k 를 아는 쪽이 처음부터 다시 계산한다"]
C --> E["공격자 · 해시값을 중간 해시값으로 놓고 덧붙인 블록을 계산한다"]
E --> F["더 긴 메시지에 맞는 해시값"]
공격자는 k 를 알 필요가 없습니다. k 를 직접 공격하지도 않습니다.
SHA-2 는 이 길이 확장 성질을 지닙니다. NIST 가 공모로 SHA-3(Secure Hash Algorithm 3)를 뽑을 때는 후보가 이 성질에 버텨야 했습니다. 그 공모 전에 만든 해시 함수에는 요건이 아니었습니다.
이런 쓰임에는 HMAC(Hash-based Message Authentication Code, 해시 기반 메시지 인증 코드)을 씁니다. HMAC 은 안쪽 해시 결과를 바깥에서 한 번 더 해시합니다. 그래서 안쪽 사슬의 중간 해시값이 겉으로 드러나지 않습니다. 인터넷 프로토콜은 거의 모두 길이 확장 성질이 있는 해시 함수를 써도 안전하게 설계돼 있습니다. HMAC 을 쓰는 프로토콜이 특히 그렇습니다.
비밀번호 저장과 역상 저항성
역상 저항성은 무작위로 고른 해시값에 대한 약속입니다. 비밀번호처럼 후보가 적은 입력은 그 약속이 다루지 않습니다. 공격자는 후보를 하나씩 해시해 털린 해시값과 견주면 됩니다. 계산이 금방 끝날수록 후보를 더 많이 견줘 봅니다.
SHA-256 이 받는 입력은 메시지 하나뿐입니다. 사용자마다 다르게 섞는 값도, 계산을 일부러 비싸게 만드는 손잡이도 없습니다. 앞의 것을 솔트, 뒤의 것을 비용 인자라고 합니다.
비밀번호 해싱 방식은 비밀번호·솔트·비용 인자를 받아 해시값을 냅니다. 목적은 해시 파일을 손에 넣은 공격자가 추측 한 번을 할 때마다 드는 비용을 키우는 것입니다. 그러면 추측 공격 전체의 비용이 감당 못 할 만큼 커집니다.
비밀번호를 저장하는 규칙은 이렇습니다.
| 규칙 | 강도 |
|---|---|
| 비밀번호는 오프라인 공격에 버티는 꼴로 저장한다 | 필수(SHALL) |
| 비밀번호에 솔트를 섞고 알맞은 비밀번호 해싱 방식으로 해시한다 | 필수(SHALL) |
| 솔트는 32비트 이상이고, 저장된 해시끼리 솔트가 겹치는 일이 최소가 되게 고른다 | 필수(SHALL) |
| 솔트와 결과 해시값을 비밀번호마다 함께 저장한다 | 필수(SHALL) |
| 비용 인자는 검증하는 쪽 성능을 해치지 않는 선에서 되도록 높게 잡는다 | 권장(SHOULD) |
| 비용 인자는 컴퓨터가 빨라지는 만큼 시간이 지나며 올린다 | 권장(SHOULD) |
관련 항목
SHA-256 이 속하는 상위 분류
해시 함수 · 암호학적 해시 함수 · 해시값 · 다이제스트 · SHA-2
SHA-256 과 함께 SHA-2 를 이루는 형제 알고리즘
SHA-224 · SHA-384 · SHA-512
SHA-256 을 대신할 수 있는 다른 해시 함수
SHA-1 · MD5 · SHA-3 · BLAKE2 · xxHash
SHA-256 이 지키는 성질
충돌 저항성 · 역상 저항성 · 제2 역상 저항성 · 눈사태 효과 · 생일 문제
SHA-256 을 이루는 계산 얼개
머클-담고르 구조 · 압축 함수 · 패딩 · 메시지 스케줄 · 초기 해시값 · 비트 연산 · 모듈러 연산
SHA-256 을 노리는 공격
길이 확장 공격 · 충돌 공격 · 생일 공격 · 무차별 대입 공격 · 레인보우 테이블
SHA-256 을 무결성 확인과 이름표에 쓰는 도구
Git · 컨테이너 이미지 · 머클 트리 · 체크섬 · 콘텐츠 주소 저장소 · 무결성
SHA-256 을 계산 비용의 증거로 쓰는 체계
작업 증명 · 비트코인 · 블록체인 · Hashcash · 논스
SHA-256 을 안에 품는 보안 규격
HMAC · 메시지 인증 코드 · 전자 서명 · HKDF · 인증서 · TLS · JWT
비밀번호 저장에서 SHA-256 을 대신하는 방식과 재료
비밀번호 해싱 · 키 유도 함수 · 솔트 · 비용 인자 · bcrypt · Argon2 · PBKDF2 · scrypt
SHA-256 을 정의하는 표준 문서
FIPS 180-4 · RFC 6234 · NIST SP 800-107 · NIST
다른 이름: SHA256 · Secure Hash Algorithm 256