**Algebraic Cryptanalysis of Curry and Flurry using Correlated Messages**

*Jean-Charles Faugère and Ludovic Perret*

**Abstract: **In \cite{BPW}, Buchmann, Pyshkin and Weinmann have described two families of
Feistel and SPN block ciphers called Flurry and Curry
respectively. These two families of ciphers are fully parametrizable and have
a sound design strategy against basic statistical attacks; i.e. linear and
differential attacks. The encryption process can be easily described by a set
of algebraic equations. These ciphers are then targets of choices for
algebraic attacks. In particular, the key recovery problem has been reduced to
changing the order of a Groebner basis \cite{BPW,BPWext}. This attack -
although being more efficient than linear and differential attacks - remains
quite limited. The purpose of this paper is to overcome this limitation by
using a small number of suitably chosen pairs of message/ciphertext for
improving algebraic attacks. It turns out that this approach permits to go one
step further in the (algebraic) cryptanalysis of Flurry and
\textbf{Curry}. To explain the behavior of our attack, we have established an
interesting connection between algebraic attacks and high order differential
cryptanalysis \cite{Lai}. From extensive experiments, we estimate that our
approach, that we can call an ``algebraic-high order
differential" cryptanalysis, is polynomial when the Sbox is a power function.
As a proof of concept, we have been able to break Flurry -- up to
$8$ rounds -- in few hours.

**Category / Keywords: **secret-key cryptography / algebraic cryptanalysis, block ciphers, Groebner bases, F5 algorithm

**Date: **received 21 Sep 2008

**Contact author: **ludovic perret at lip6 fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20080924:032751 (All versions of this report)

**Short URL: **ia.cr/2008/402

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]