International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Algebraic Cryptanalysis of Curry and Flurry using Correlated Messages

Authors:
Jean-Charles Faugère
Ludovic Perret
Download:
URL: http://eprint.iacr.org/2008/402
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-18053,
  title={Algebraic Cryptanalysis of Curry and Flurry using Correlated Messages},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / algebraic cryptanalysis, block ciphers, Groebner bases, F5 algorithm},
  url={http://eprint.iacr.org/2008/402},
  note={ ludovic.perret@lip6.fr 14143 received 21 Sep 2008},
  author={Jean-Charles Faugère and Ludovic Perret},
  year=2008
}