ML-DSA는 공개키 해시 순서가 검증을 번거롭게 한다

글은 ML-DSA의 서명 검증 과정에서 공개키 해시를 메시지보다 먼저 계산하는 방식이 여러 키를 시험할 때 불편을 낳는다고 지적한다. 서명 키를 메시지 본문에서 찾아야 하는 프로토콜에서는 메시지 해시를 재사용하기 어렵다는 설명이다.

일반적인 전자서명은 크기 제한 때문에 메시지 자체가 아니라 메시지의 해시값에 서명한다. 따라서 서명자가 보지 않은 메시지라도 그 해시를 알고 있거나 해시를 담은 다른 서명이 있으면 유효한 서명을 만들 수 있는 경우가 있다. 글은 이런 문제를 막기 위해 Ed25519와 ML-DSA가 메시지와 공개키를 해시 계산에 포함한다고 설명한다. 기존 서명 방식의 사례로 RFC 8017의 PKCS #1 서명 방식, 같은 문서의 RSA-PSS, DSA, ECDSA를 든다.

여러 서명자가 있는 프로토콜에서는 서명자의 신원이 메시지 본문에 들어가는 일이 많다. 서명을 확인하기 전에 본문 전체를 신뢰해 처리하지 않으려면, 먼저 메시지를 조심스럽게 읽고 서명 키를 찾아야 한다. JWT, CWT, SAML 등에서는 키 식별자가 없거나 여러 키가 같은 식별자를 쓸 수 있어 키를 찾기 위해 여러 차례 서명 검증을 시도할 수도 있다.

전통적인 서명 방식이라면 헤더에서 알고리즘과 해시 함수를 확인한 뒤 메시지를 먼저 해시하고, 원본 메시지를 버린 다음 키를 찾아 검증할 수 있다. 이렇게 하면 메모리 사용을 줄이고, 여러 키를 시험할 때 메시지를 매번 다시 해시하지 않아도 된다. 하지만 글은 이 방식이 정의된 형태의 Ed25519와 ML-DSA에는 적용되지 않는다고 지적한다.

ML-DSA는 SHAKE-256(SHAKE-256(PubK, 64) || 0x00 || len(ctx) || ctx || m, 64)를 계산한다. 여기서 ctx는 0~255바이트 길이의 문맥 문자열이다. 글은 공개키 해시를 메시지 뒤로 옮기는 대안인 SHAKE-256(0x00 || len(ctx) || ctx || m || SHAKE-256(PubK, 64), 64)을 제안한다. 그러면 메시지 해시 상태를 보관했다가 키마다 복사해 쓸 수 있지만, 실제 표준은 이 순서를 택하지 않았다. 제안한 방식에서는 SHAKE-256 상태를 64바이트 출력값 대신 약 200바이트 넘게 보관해야 한다고 설명한다.

Ed25519의 해시 순서를 반대로 바꾸는 것도 간단하지 않다. SHA-512(M || R || PubK)로 바꾸면 SHA-512의 길이 확장 공격에 취약해질 수 있다는 설명이다. 글은 Ed25519가 발표된 2011년에 이를 피하는 방법을 마련하기는 까다로웠겠지만, 오늘날에는 SHA-3, BLAKE2, 잘라낸 SHA-2 변형 등 길이 확장 공격에 취약하지 않은 해시 함수를 사용할 수 있다고 덧붙인다. 글의 결론은 서명 크기와 비용이 커지는 상황에서 주고받는 서명 수를 줄이기를 바란다는 것이다. ML-DSA 서명 처리에 관한 추가 설명은 HashML-DSA에 대한 글에서 확인할 수 있다.