Algebraic Cryptanalysis of Curry and Flurry using Correlated Messages

International audienceIn this paper, we present an algebraic attack against the Flurry and Curry block ciphers [12,13]. Usually, algebraic attacks against block ciphers only require one message/ciphertext pair to be mounted. In this paper, we investigate a different approach. Roughly, the idea is to generate an algebraic system from the knowledge of several well chosen correlated message/ciphertext pairs. Flurry and Curry are two families of ciphers which fully parametrizable and having a sound design strategy against the most common statistical attacks; i.e. linear and differential attacks. These ciphers are then targets of choices for algebraic attacks. It turns out that our new approach permits to go one step further in the (algebraic) cryptanalysis of difficult instances of Flurry and Curry. To explain the behavior of our attack, we have established an interesting connection between algebraic attacks and high order differential cryptanalysis [32]. From extensive experiments, we estimate that our approach – that we will call ”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/Curry – up to 8 rounds – in few hours. We have also investigated the more difficult (and interesting case) of the inverse function. For such function, we have not been able to bound precisely the theoretical complexity, but our experiments indicate that our approach permits to obtain a significant practical gain. We have attacked Flurry/Curry using the inverse Sbox up to 8 rounds