SymSum_Sim - Beating ZeroSum

Published in Designs, Codes and Cryptography, 2025.

Team

Sahiba Suryawanshi
Shibam Ghosh
Dhiman Saha
Prathamesh Ram

Abstract

Higher order differential properties are powerful tools for algebraic cryptanalysis. In FSE 2017, Saha et al. introduced $\textsf {SymSum}_\textsf {Vec}$, a distinguisher based on higher order vectorial Boolean derivatives, which proved effective against SHA-3. However, its maximum attainable derivative (MAD) was limited compared to the ZeroSum distinguisher due to its reliance on vectorial derivatives.

In this work, we overcome this limitation by developing the theory for computing $\textsf {SymSum}\textsf {Vec}$ using simple derivatives, achieving a near $100\%$ improvement in MAD. We introduce $\textsf {SymSum}\textsf {Sim}$, a new variant that outperforms ZeroSum by a factor of $2^{257}$ for 10-round SHA3-384 and $2^{129}$ for 9-round SHA3-512, while matching its MAD. Additionally, we report the best 15-round and 16-round distinguishers for Keccak-p, the best full-round distinguisher for Xoodoo, and the first third-party distinguishers for Bash. $\textsf {SymSum}_\textsf {Sim}$ breaks the MAD barrier, establishing itself as a superior alternative to ZeroSum.

Key Contributions

SymSum_Sim: Development of a new variant of the SymSum distinguisher based on k-fold simple derivatives, overcoming the MAD limitation of the vectorial version.
Outperforming ZeroSum: The new distinguisher outperforms ZeroSum by significant factors for SHA3-384 and SHA3-512 while maintaining the same MAD.
Keccak-p Results: Reports the best 15-round distinguisher ($2^{256}$) and the first better than birthday-bound 16-round distinguisher ($2^{512}$) for Keccak-p.
Xoodoo & Bash: Devises the best full-round distinguisher on the Xoodoo internal permutation and furnishes the first third-party distinguishers on Bash.

Read the full paper