Algebraic Precomputations in Differential Cryptanalysis

Algebraic cryptanalysis is a general tool which permits one to assess the security of a wide range of cryptographic schemes. Algebraic techniques have been successfully applied against a number of multivariate schemes and stream ciphers. Yet, their feasibility against block ciphers remains the source of much speculation. At FSE 2009 Albrecht and Cid proposed to combine differential cryptanalysis with algebraic attacks against block ciphers. The proposed attacks required Grobner basis computations during the online phase of the attack. In this work we take a different approach and only perform Grobner basis computations in a pre-computation (or offline) phase. In other words, we study how we can improve “classical” differential cryptanalysis using algebraic tools. We apply our techniques against the block ciphers Present and Ktantan32.