Paper 2025/2038

Breaking and Fixing MacaKey

Abstract

The sponge construction underpins many modern symmetric primitives, enabling efficient hashing and authenticated encryption. While full-state absorption is known to be secure in keyed sponges, the security of full-state squeezing has remained unclear. Recently, Lefevre and Marhuenda-Beltrán introduced MacaKey, which applies ideas from the summation-truncation hybrid technique of constructing PRFs to the full-state sponge. The authors claimed that MacaKey is provably secure up to the birthday bound in capacity, even when the adversary is allowed to request variable-length outputs. In this work, we revisit this claim and show that MacaKey is insecure as a PRF. We demonstrate a simple four-query distinguishing attack that violates its claimed bound, exploiting the exposure of the full internal state and the resulting loss of secrecy in the capacity portion during squeezing. We then propose a simple modification that restores security with negligible overhead. The modified construction, KeyMacaKey, re-randomizes the internal state after absorption by incorporating a keyed finalization step without requiring an extra permutation call. Further, we show that KeyMacaKey achieves the stronger security of birthday-bound in the full state size than what was claimed for MacaKey.

Note: Updated to published version at ToSC and updated author list.