Solving Systems of Differential Equations of Addition and Cryptanalysis of the Helix Cipher

Souradyuti Paul; Bart Preneel

Paper 2004/294

Solving Systems of Differential Equations of Addition and Cryptanalysis of the Helix Cipher

Souradyuti Paul and Bart Preneel

Abstract

Mixing addition modulo 2^n (+) and exclusive-or has a host of applications in symmetric cryptography as the operations are fast and nonlinear over GF(2). We deal with a frequently encountered equation (x+y)XOR((x XOR a)+(y XOR b))=c $. T h e d i f f i c u l t y o f s o l v i n g a n a r b i t r a r y s y s t e m o f s u c h e q u a t i o n s - - n a m e d d i f f e r e n t i a l e q u a t i o n s o f a d d i t i o n (D E A) - - i s a n i m p o r t a n t c o n s i d e r a t i o n i n t h e e v a l u a t i o n o f t h e s e c u r i t y o f m a n y c i p h e r s a g a i n s t d i f f e r e n t i a l a t t a c k s . T h i s p a p e r s h o w s t h a t t h e s a t i s f i a b i l i t y o f a n a r b i t r a r y s e t o f D E A - - w h i c h h a s s o f a r b e e n a s s u m e d \emph h a r d f o r l a r g e$ n $- - i s i n t h e c o m p l e x i t y c l a s s P . W e a l s o d e s i g n a n e f f i c i e n t a l g o r i t h m t o o b t a i n a l l s o l u t i o n s t o a n a r b i t r a r y s y s t e m o f D E A w i t h r u n n i n g t i m e l i n e a r i n t h e n u m b e r o f s o l u t i o n s . O u r s e c o n d c o n t r i b u t i o n i s s o l v i n g D E A i n a n a d a p t i v e q u e r y m o d e l w h e r e a n e q u a t i o n i s f o r m e d b y a q u e r y (a, b) a n d o r a c l e o u t p u t c . T h e c h a l l e n g e i s t o o p t i m i z e t h e n u m b e r o f q u e r i e s t o s o l v e (x + y) X O R ((x X O R a) + (y X O R b)) = c . O u r a l g o r i t h m s o l v e s t h i s e q u a t i o n w i t h o n l y 3 q u e r i e s i n t h e w o r s t c a s e . A n o t h e r a l g o r i t h m s o l v e s t h e e q u a t i o n (x + y) X O R (x + (y X O R b)) = c$ with (n-t-1) queries in the worst case (t is the position of the least significant `1' of x), and thus, outperforms the previous best known algorithm by Muller -- presented at FSE~'04 -- which required 3(n-1) queries. Most importantly, we show that the upper bounds, for our algorithms, on the number of queries match worst case lower bounds. This, essentially, closes further research in this direction as our lower bounds are optimal. We used our results to cryptanalyze a recently proposed cipher Helix, which was a candidate for consideration in the 802.11i standard. We are successful in reducing the data complexity of a DC attack on the cipher by a factor of 3 in the worst case (a factor of 46.5 in the best case).

Note: A proper subset of the results of this report under the title "Optimal Lower Bounds on the Number of Queries for Solving Differential Equations of Addition" had resided here till April 20, 2005.

Metadata

Available format(s): PDF PS
Publication info: Published elsewhere. An Extended Abstract of this Paper will be published in the proceedings of ACISP 2005
Keywords: Differential Cryptanalysis Helix cipher P NP
Contact author(s): Souradyuti Paul @ esat kuleuven ac be
History: 2012-11-07: last of 17 revisions; 2004-11-12: received; See all versions
Short URL: https://ia.cr/2004/294
License: CC BY

BibTeX

@misc{cryptoeprint:2004/294,
      author = {Souradyuti Paul and Bart Preneel},
      title = {Solving Systems of Differential Equations of Addition and Cryptanalysis of the Helix Cipher},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/294},
      year = {2004},
      url = {https://eprint.iacr.org/2004/294}
}