길이를 고를 수 있는 해시 — SHAKE와 그 이웃들

SHA-256의 출력은 32바이트입니다. 항상 그렇습니다. 48바이트가 필요하면 SHA-384로 바꾸거나, 두 번 돌려 이어 붙이거나, 파생 함수를 씁니다.

SHA-3 계열에는 그 제약이 없는 함수가 있습니다.

SHAKE는 원하는 만큼 뽑는다

  8바이트  325ea50b0911cedb
 16바이트  325ea50b0911cedbd77872fdfb66fee5
 32바이트  325ea50b0911cedbd77872fdfb66fee5e6bcc592be002b79839e5c2d59493ee8
 64바이트  325ea50b0911cedbd77872fdfb66fee5e6bcc592be002b79839e5c2d59493ee8
           6fe97fcaba11f1cce75cc1404a92099e2322bc8b378fc75d97b2a58484ae49a6

같은 입력 onuel에 길이만 바꿔 넣은 결과입니다. 이런 함수를 XOF(extendable-output function, 확장 출력 함수)라고 합니다.

눈에 띄는 성질이 하나 있습니다. 짧은 출력이 긴 출력의 접두사입니다. 8바이트 결과가 64바이트 결과의 앞 8바이트와 정확히 같습니다.

Keccak의 스펀지 구조 때문입니다. 입력을 상태에 흡수한 뒤 상태에서 바이트를 짜내는데, 짜내는 것을 멈추는 시점이 곧 출력 길이입니다. 상태는 같으므로 앞부분도 같습니다.

이 성질은 편하기도 하고 위험하기도 합니다. 16바이트 출력을 공개해 놓고 32바이트 출력을 비밀로 유지할 수는 없습니다. 앞 절반이 이미 나가 있습니다.

SHAKE128과 SHAKE256의 숫자는 출력 길이가 아니라 보안 강도입니다. SHAKE128에서 64바이트를 뽑아도 강도는 128비트입니다.

cSHAKE는 용도를 구분한다

한 시스템 안에서 같은 함수를 두 군데에 쓰면 문제가 생길 수 있습니다. 키 유도에 SHAKE를 쓰고 파일 지문에도 SHAKE를 쓰면, 어떤 입력이 우연히 같을 때 두 값이 같아집니다.

cSHAKE는 커스터마이제이션 문자열을 받습니다. "key-derivation"과 "file-fingerprint"를 각각 넣으면 두 용도는 서로 절대 충돌하지 않습니다. 같은 입력이라도 다른 값이 나옵니다.

도메인 분리(domain separation)라고 부르는 장치이고, 직접 만들려면 접두사를 붙이는 방식으로 흉내 낼 수 있습니다. 다만 흉내에는 함정이 있습니다.

이어 붙이기는 모호하다

["ab", "c"]  →  "abc"  →  ba7816bf8f01cfea414140de5dae2223…
["a", "bc"]  →  "abc"  →  ba7816bf8f01cfea414140de5dae2223…
                          같은 값

서로 다른 두 입력이 같은 해시를 냅니다. 충돌을 찾은 것이 아니라, 이어 붙이는 순간 두 입력이 같은 바이트가 된 것입니다.

서명 대상을 만들 때 이 일이 일어납니다. 사용자명과 권한을 이어 붙여 서명하면, ("admi", "n")과 ("admin", "")이 같은 값으로 서명됩니다.

길이를 함께 넣으면 갈라집니다.

["ab","c"] → "2:ab1:c" → 430fb1b4ac43316eca81fab27a1930ab…
["a","bc"] → "1:a2:bc" → 5310a58788781ab25d5ad7c3f8503582…

TupleHash가 표준으로 하는 일이 이것입니다. NIST SP 800-185는 left_encode라는 인코딩을 정의합니다 — 값 앞에 그 값의 바이트 수를 붙입니다.

left_encode(    0) = 0100
left_encode(    1) = 0101
left_encode(  255) = 01ff
left_encode(  256) = 020100
left_encode(65536) = 03010000

첫 바이트가 뒤따르는 길이 바이트의 개수이고, 그다음이 값입니다. 이 인코딩으로 각 조각을 감싸면 조각의 경계가 복원 가능해집니다.

KMAC은 HMAC이 필요 없다

HMAC은 해시를 두 번 겹쳐 씁니다.

HMAC(k, m) = H((k ⊕ opad) || H((k ⊕ ipad) || m))

이 구조는 SHA-1·SHA-2 같은 머클-담고르 해시의 길이 확장 공격을 막기 위한 것입니다. H(key || message)를 그냥 쓰면 키를 모르고도 메시지를 이어 붙일 수 있기 때문에, 안쪽 해시를 한 번 더 감쌉니다.

Keccak에는 길이 확장이 없습니다. 스펀지 구조라 내부 상태 전체가 출력되지 않습니다. 그래서 겹칠 이유도 없습니다.

KMAC은 cSHAKE 위에 키를 얹은 MAC입니다. 해시 호출이 한 번이고, 출력 길이를 고를 수 있으며, 커스터마이제이션 문자열도 그대로 받습니다.

어디에 쓰이는가

XOF는 결정론적으로 임의 길이 바이트가 필요한 자리에 들어갑니다. 후양자 서명 알고리즘 SPHINCS+와 ML-KEM(Kyber)이 내부에서 SHAKE를 씁니다 — 시드에서 필요한 만큼의 의사난수를 뽑는 용도입니다.

확인 순서

해시 출력을 잘라 쓰고 있다면 XOF로 바꿔 원하는 길이를 직접 뽑습니다
여러 조각을 이어 붙여 해시하거나 서명한다면 조각 길이를 함께 넣습니다. 구분자 하나로는 부족합니다 — 구분자가 데이터에 들어갈 수 있습니다
한 시스템에서 같은 해시를 여러 용도로 쓴다면 용도별 문자열로 갈라 놓습니다
XOF의 짧은 출력은 긴 출력의 앞부분입니다. 앞부분을 공개했다면 뒷부분만으로 비밀을 유지할 수 없습니다
SHAKE128의 128은 출력 길이가 아니라 보안 강도입니다

tools.onuel.dev의 SHAKE에서 SHAKE128·SHAKE256의 출력 길이를 바꿔 가며 접두사 성질을 직접 확인할 수 있습니다. cSHAKE는 커스터마이제이션 문자열을, KMAC은 키를 받고, TupleHash에 ["ab","c"]와 ["a","bc"]를 넣으면 위와 달리 서로 다른 값이 나옵니다. 고정 길이 쪽과 비교하려면 SHA3-256이 같은 Keccak 계열입니다.