Dinamite: internal differential match-in-the-end attack on eight-round PAEQ

What is it about?

We explore a cryptanalysis strategy which seems to be particularly applicable to parallelizable ciphers where the key forms a part of the internal state. The proposed technique combines internal differentials with guess and determine analysis to come up with what is referred to as the Match-in-the-end (MITE) attack. The notion of difference here deviates from the classical differential where the difference is controllable via the plaintext/ciphertext. Here we exploit the hamming distance between parallel branches to devise the differential trail. We apply the strategy on \emph{full} 8 (out of 20) rounds of parallelizable authenticated cipher \paeq to devise key recovery attacks with practical time complexities. We first show an initial attack on \texttt{paeq-64/80/128} and then devise improvements which give us the best key-recovery attacks with time complexities of $2^{33}, 2^{48}$ and $2^{64}$ respectively. While the best reported attacks on 8-round \texttt{paeq-64/80/128} have a data complexity of $2^{89}$ blocks, our result improves their time complexities by factors of $2, 2^{18}$ and $2^{34}$ while preserving the data complexity. Finally, we present a nonce-based differential attack which works on \texttt{paeq-128-t} with $2^{64}$ time complexity but uses just two single block known plaintexts making it the most practical attack on any round-reduced \paeq variant reported so far.

Featured Image