Algebraic attacks and data word rotations
in [Cryptography]
|
Prev: Protecting 3x16 bits with 16 bits ? (Which error correcting code for mode 3?)
Next: why doesn't the decryption primitive in PKCS#1 employ RSA blinding?
From: Mok-Kong Shen on 14 Feb 2010 12:45 J.D. wrote: > So, would it be accurate to say that a block cipher like RC5, where w > (the word size parameter) is 32 or 64, should be highly resistant to > algebraic attack after a few rounds, due primarily to the high degree > of the data-dependent rotations? In fact, even if we used xor to > merge the round keys with the state rather than using addition modulo > 2^w, it should still be highly resistant (though substantially less > resistant to other sorts of attack), yes? While a design goal of ciphers is to well achieve Shannon's confusion and diffusion, I think that this is only one way of looking at the matter and that another is variability and indirectness. Data-dependent rotations render a block cipher "variable", thus giving the analyst a moving/flying instead of a stationary taget to hit. Most block algorithms popularly known are static and not variable, i.e. once a key is given, its function is entirely fixed/defined. Presumably the authors of these algorithms thought that their constructs are already strong engough without any need to incorporate "variability" into them to enhance their strength. M. K. Shen
From: J.D. on 14 Feb 2010 13:47 On Feb 14, 12:45 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > J.D. wrote: > > So, would it be accurate to say that a block cipher like RC5, where w > > (the word size parameter) is 32 or 64, should be highly resistant to > > algebraic attack after a few rounds, due primarily to the high degree > > of the data-dependent rotations? In fact, even if we used xor to > > merge the round keys with the state rather than using addition modulo > > 2^w, it should still be highly resistant (though substantially less > > resistant to other sorts of attack), yes? > > While a design goal of ciphers is to well achieve Shannon's confusion > and diffusion, I think that this is only one way of looking at the > matter and that another is variability and indirectness. Data-dependent > rotations render a block cipher "variable", thus giving the analyst > a moving/flying instead of a stationary taget to hit. Most block > algorithms popularly known are static and not variable, i.e. once a key > is given, its function is entirely fixed/defined. Presumably the > authors of these algorithms thought that their constructs are already > strong engough without any need to incorporate "variability" into them > to enhance their strength. > > M. K. Shen Data-dependent rotations are not magic. What makes a data-dependent rotation "variable" where a 'data-dependent xor' (e.g. the F-function of a Feistel cipher like DES) is "fixed"? Your terminology does not appear to be coherent.
From: Mok-Kong Shen on 14 Feb 2010 18:42 J.D. wrote: > Mok-Kong Shen wrote: >> ......... Most block >> algorithms popularly known are static and not variable, i.e. once a key >> is given, its function is entirely fixed/defined. > > Data-dependent rotations are not magic. What makes a data-dependent > rotation "variable" where a 'data-dependent xor' (e.g. the F-function > of a Feistel cipher like DES) is "fixed"? Your terminology does not > appear to be coherent. That's why I wrote "most". (But maybe you are indeed right, if more examples could be demonstrated. AES is "fixed", if I don't err.) M. K. Shen
From: J.D. on 14 Feb 2010 19:13 On Feb 14, 6:42 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > J.D. wrote: > > Mok-Kong Shen wrote: > >> ......... Most block > >> algorithms popularly known are static and not variable, i.e. once a key > >> is given, its function is entirely fixed/defined. > > > Data-dependent rotations are not magic. What makes a data-dependent > > rotation "variable" where a 'data-dependent xor' (e.g. the F-function > > of a Feistel cipher like DES) is "fixed"? Your terminology does not > > appear to be coherent. > > That's why I wrote "most". (But maybe you are indeed right, if more > examples could be demonstrated. AES is "fixed", if I don't err.) > > M. K. Shen The S-boxes of AES (and "most" other block ciphers) are 'data- dependent substitutions'. They are exactly like data dependent rotations and 'data-dependent xors', in that they are all functions where different inputs will produce different outputs. There is no meaningful difference between them that could justify your terminology. If you attempt to pin down precisely what you mean by "variable" as opposed to "fixed" in concrete terms rather than in analogies to "moving targets", then I think you will see this.
From: Mok-Kong Shen on 15 Feb 2010 03:54
J.D. wrote: > The S-boxes of AES (and "most" other block ciphers) are 'data- > dependent substitutions'. They are exactly like data dependent > rotations and 'data-dependent xors', in that they are all functions > where different inputs will produce different outputs. There is no > meaningful difference between them that could justify your > terminology. If you attempt to pin down precisely what you mean by > "variable" as opposed to "fixed" in concrete terms rather than in > analogies to "moving targets", then I think you will see this. I am afraid that you erred. S-boxs of DES are data dependent, because thier (the 4 inner input bits map to 4 output bits) selection depends on the two outer bits of the 6 input bits and therefore data dependent. But AES's ByteSub operates on a purely constant table and hence is "not" data dependent. (Or do you generally consider a substitution, e.g. the classical substitution, data dependent, simply because the outcome of the substitution, namely the output, "depends" on the data beind input? I certainly presume that's not the case.) BTW, concerning the algebraic attacks you are interested in, I remember that very long time ago there were already attempts to attack DES with algebraic methods, but later I have never heard of them. Presumably it's (among perhaps other factors) the above mentioned "variable" nature of the S-Boxes of DES that hindered progress of these projects. I always wonder why the in my view superb idea of variable S-Boxes of DES apparently has not received serious considerations that it deserves in later generation of designs of block algorithnms. Thanks, M. K. Shen |