Symmetry Distinguishers

Team

About the project:

Theoretical cryptanalysis has always leveraged non-randomness as one of the primary indicators of underlying weakness of a cryptographic primitive. In this regard symmetry has always been a cheap source of non-randomness and a property that is foremost on the list of properties to be eliminated by any cryptosystem designer. In \fse 2017~\cite{DBLP:journals/tosc/SahaKC17} and later in \afc 2020~\cite{DBLP:conf/africacrypt/SuryawanshiSS20}, it was shown how internal symmetry (alternatively, the \emph{translation invariance} property) of some sub-functions of \sha~\cite{sha3} (the latest cryptographic hash function standard) can be linked to its algebraic degree. And the same property was used to devise the \emph{most effective} distinguishers on \sha. The primary idea was to compute higher order vectorial derivatives (Refer Definition~$\text{???}$) on self-symmetric inputs. The fact that non-linear operation of \sha precedes the round-constant addition allowed the $(d-1)^{th}$ order derivative to produce a \emph{deterministically} symmetric output. This was named as the \emph{Symmetric-Sum} or \sym. It can be noted the the generic ZeroSum requires the $(d+1)^{th}$ order derivative to be computed thereby conceding to \sym an advantage of factor 2. However, the degrees of freedom of \sym is half of that of ZeroSum since \sym relies on higher order vectorial derivatives of partition size 2.

This project attempts to investigate new properties of higher order boolean derivatives to detect non-randomness in cryptographic hash functions. The primary targets are international hash standard \sha and \nist Lightweight Cryptography competition finalist \xood~\cite{DBLP:journals/tosc/DaemenHPAK20}. The basic idea is to improve the limitations of \sym distinguisher.