SequenceHash: 다양한 해시 함수로 안전하게 여러 입력 해싱하기

AI 요약

여러 값을 하나의 해시로 묶는 멀티해싱(multihashing)은 입력을 단순히 이어 붙여 해시하면 경계가 사라져 보안 문제가 생길 수 있습니다. 예를 들어 (A, BC)와 (AB, C)가 같은 바이트열이 되면, 해시 결과만으로 원래 입력 구성을 구분할 수 없습니다. Trail of Bits는 이런 혼동을 줄이기 위해 SequenceHash와 키 기반 변형 SequenceMAC을 만들고, 명세를 Community Cryptography Specification Project(C2SP)에 공개했습니다.

멀티해싱에서 생기는 위험

암호 프로토콜은 여러 값으로 인증자나 커밋먼트를 만들 때 각 입력의 경계를 정확히 보존해야 합니다. 경계가 모호하면 입력을 다른 조합으로 해석하거나 커밋먼트를 여러 방식으로 여는 문제가 생길 수 있습니다. 영지식 증명에서 Fiat-Shamir 변환을 잘못 구현하면 위조 위험으로 이어질 수 있으며, 암호화폐 프로토콜에서도 손실이 클 수 있습니다.

개발자들은 구분자 문자를 넣거나 입력 길이를 기록하는 등 여러 방식으로 문제를 해결해 왔지만, 구분자가 입력에도 등장할 수 있고 인코딩이 복잡해지면 구현 오류나 타이밍 위험이 생길 수 있습니다. 일부 방식은 특정 입력에만 길이를 붙이기도 합니다. NIST SP 800-185의 TupleHash는 길이 접두 인코딩으로 이 문제를 해결하는 널리 알려진 선택지입니다. 다만 Keccak 기반으로만 정의되어 있어 SHA-2나 BLAKE 같은 다른 해시 함수와 함께 쓰려면 대안이 필요합니다.

SequenceHash의 인코딩과 보안 기능

SequenceHash도 길이 인코딩으로 입력을 구분하지만, 각 입력의 바이트 길이를 128비트 고정 길이 값으로 표현하고 길이 정보를 입력 뒤에 붙입니다. 고정 길이 인코딩은 32비트와 64비트 시스템에서 구현하기 쉽고, 길이 접미 방식은 입력 전체 길이를 미리 모르는 상황에서도 스트리밍 API를 구성하기 편합니다. 표현할 수 있는 입력 길이는 바이트 기준 최대 2¹²⁸−1입니다. SHA-256과 SHA-512 자체의 입력 길이 한계는 각각 2⁶¹바이트와 2¹²⁵바이트이므로, 이 한도는 일반적인 사용 범위를 넘어섭니다.

이 구성은 입력 경계를 명확히 해 서로 다른 값의 조합이 같은 해시 입력으로 이어지지 않도록 합니다. 또 HMAC과 비슷한 이중 해시 구조를 써서 SHA-256이나 SHA-512처럼 길이 확장 공격에 취약한 해시 함수를 사용할 때 그 공격을 막습니다. 사용자 정의 문자열(customization string)을 지원해 해시 결과를 프로토콜 단계나 특정 용도에 묶을 수 있습니다. 이 문자열은 바깥쪽 해시 단계에만 들어가므로 같은 입력을 여러 사용자 정의 문자열로 해싱할 때 안쪽 해시를 다시 계산하지 않아도 됩니다.

SequenceHash는 해시 함수에 종속되지 않습니다. SHA-256·SHA-384·SHA-512, BLAKE, RIPEMD 등 보안성이 적절한 해시 함수와 함께 쓸 수 있습니다. 다만 이 구성만으로 약한 해시 함수가 안전해지는 것은 아닙니다. 예를 들어 MD4나 SHA-0을 선택하면 그 취약성이 그대로 남습니다.

SequenceMAC과 키 처리

SequenceMAC은 SequenceHash의 키 기반 모드이며, 최소 32바이트 키를 요구합니다. 저자들은 256비트 키와 적절한 256비트 해시 함수를 함께 쓸 때 위조 공격에 대한 보안 수준이 약 128비트라고 설명합니다. 키 길이와 사용자 정의 문자열도 해시 메타데이터에 반영합니다.

HMAC에서는 해시 블록 크기보다 긴 키를 먼저 해싱하므로 긴 키와 그 해시값이 같은 결과를 낼 수 있습니다. 키 끝에 0을 덧붙여도 같은 키로 처리되는 경우도 있습니다. SequenceMAC은 키 길이를 헤더에 넣어 이런 키 의사충돌(key pseudocollision)을 찾기 어렵게 하고, 끝에 0을 붙인 키도 별개의 키로 취급합니다. 키를 길게 만든다고 보안 수준이 계속 높아지는 것은 아닙니다. 실제 보안 한계는 선택한 해시 함수와 키 전처리 방식에 좌우되며, 출력 길이보다 훨씬 긴 키를 쓰는 것은 대체로 권장하지 않습니다.

구현과 사용 시 주의점

Trail of Bits는 Rust·Go·Python 구현과 여러 해시 함수에 대한 테스트 벡터를 공개했습니다. 벡터에는 최종 출력뿐 아니라 중간 값도 포함해 구현을 점검하고 오류를 찾도록 돕습니다. API에서는 객체에 값을 쓸 때마다 그 값을 독립된 길이 인코딩 입력으로 처리합니다. 따라서 두 번 나눠 쓴 값은 두 값을 이어 붙여 한 번에 쓴 경우와 다른 해시 결과를 냅니다. 이는 Go의 hash.Hash나 Python의 update처럼 연속된 쓰기를 단순한 바이트열 연결로 처리하는 일반 해시 API와 사용 방식이 다릅니다.

SequenceXOF 명세는 아직 나오지 않았습니다. 확장 출력 함수(XOF)의 활용 사례와 API가 충분히 자리 잡지 않았으므로 관련 요구를 검토하고 있다고 설명합니다. SequenceHash를 쓰더라도 입력 직렬화 형식을 일관되게 정하고, 프로토콜에 필요한 값을 빠짐없이 포함해야 합니다. JSON이나 XML은 필드 순서가 항상 보장되지 않을 수 있으며 문자열 인코딩도 통일해야 합니다. Fiat-Shamir 변환에서는 군 정보와 생성원 같은 매개변수를 빠뜨리지 말아야 하고, 해시 출력을 모듈러 정수로 바꿀 때는 모듈러 편향도 고려해야 합니다.

Lobsters 반응

• @orib — 글보다 명세를 살펴보겠습니다. 제 생각에는 명세가 훨씬 이해하기 쉽습니다. https://c2sp.org/sequencehash

원문: Trail of Bits / 번역·요약: Trawling