Analyzing Forgery Security of LeMac: Tight Bounds and Impact of Padding

LeMac-0, proposed in ToSC 2024, is currently the fastest message authentication code, designed based on an AES-based universal hash function. After the proposal, a mistake was discovered in the evaluation code, leading the designers to rename the candidate from the original paper as LeMac-0 and the corrected version as LeMac. However, the evaluation of the MAC against forgery attacks remains inadequate, as the designers provide only rough bounds for specific forgery attacks. In this paper, we present a comprehensive evaluation of LeMac-0 and LeMac against forgery attacks using three methods. To efficiently derive bounds on differential probability, we employ a hybrid approach that combines byte-wise and bit-wise search with state-of-the-art Boolean satisfiability problem (SAT) tools. This approach tightens the upper and lower bounds of the differential probability for forgery attacks, considering three distinct attack methods under the nonce-misuse setting. Furthermore, we examine the security implications of zero-padding rounds, which are central to resisting forgery attacks on messages in LeMac-0 and LeMac. Our analysis reveals that omitting these rounds or reducing them to a single round compromises 128-bit security and makes forgery attacks feasible. These findings demonstrate that message padding must be applied carefully to ensure the security of LeMac-like structures.