Paper 2025/1203

Analyze the Security of the AEAD Scheme HiAE by Algebraic Techniques

Abstract

HiAE is a well-designed AEAD scheme using AES round functions, delivering outstanding performance on both ARM and x86 processors. Some existing AEAD schemes such as Rocca (ToSC 2021) have been shown to be vulnerable when attackers can repeatedly query the decryption oracle with forged ciphertexts and random tags until a valid tag is accepted. Motivated by this, we use algebraic techniques to analyze the security of HiAE under the same setting. Firstly, we employ the meet-in-the-middle technique and guess-and-determine technique to recover the state and derive a key-related equation resulting from two layers of AES round functions. Secondly, by adopting an algebraic approach to study the properties of the round function, we decompose the equation into byte-level equations for divide-and-conquer. Finally, we utilize the guess-and-determine technique to recover the key. Collectively, these techniques enable us to present the full key-recovery attack on HiAE. Our attack achieves a data complexity of $2^{130}$ and a time complexity of approximately $2^{209}$, leveraging both encryption and decryption oracles with a success probability of 1. We emphasize that our attack considers a stronger scenario than HiAE's original security model, and thus does not invalidate its original security claims.