Paper 2008/402

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
algebraic cryptanalysisblock ciphersGroebner basesF5 algorithm
Contact author(s)
ludovic perret @ lip6 fr
History
2008-09-24: received
Short URL
https://ia.cr/2008/402
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/402,
      author = {Jean-Charles Faugère and Ludovic Perret},
      title = {Algebraic Cryptanalysis of Curry and Flurry using Correlated Messages},
      howpublished = {Cryptology ePrint Archive, Paper 2008/402},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/402}},
      url = {https://eprint.iacr.org/2008/402}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.