Introducing dynamics into block encryptions
in [Cryptography]
|
Prev: Generic Crypto APIs ?
Next: in ElGamal, could you hardcode the generator for a public key and not lose security?
From: Mok-Kong Shen on 6 Mar 2010 09:50 Phoenix wrote: > Mok-Kong Shen > > Do you mean some think like this: [snip] Please excuse me that I don't understand your post, because owing to my poor knowledge I can't read in the programming language that you used. I have hitherto used (because of not knowing better words) two terms of my own to designate two different kinds of modifications to any arbitrary (already existing and assumed sufficiently good) encryption algorithm, such that, through doing something "additional" that are "apparently" (see however below) not harmful to security and that are likely to render the analysis much harder, one can achieve higher security. This has the particular intention of rendering it possible to continue to satisfactorily and safely use in some near future the currently existing good algorithms despite the continuing and raapid advances in analysis techniques and hardware performances (i.e. without having to take the trouble of developing new encryption algorithms to keep pace with the scientific and technological progress). The one I designated as "inner" dynamics, because it modifies the inside (the actual content) of the encryption algorithm. My example is to let the four components of a round in AES to be dynamically (i.e. at runtime) permuted, dependent on some (variable) value obtained during the processing of a preceding block. This means that the modifications (of the algorithm) that actually take place for the processing of any particular block is a "random" variable that has a certain range in combinatorics. Thus the work that the analyst has to do is evidently way harder than before. The other I designated as "outer" dynamics, because it doesn't touch anything at all of the algorithm as such. It consists in employing different keys for different blocks (one key for one block or for a small number of blocks (that number can also be dynamically, thus randomly, determined) ). One uses namely a master key and employs e.g. a block cipher in counter mode to generate the said different keys to do the proper encryption of the given plaintext. (The cipher for key generation and for proper encryption could be the same.) The benefit of this is that the workload of the analysts is evidently multiplied by a factor which is of an order equal to the number of blocks that the plaintext has. For those analysis techniques that rely on the availability of "huge" amounts of materials encrypted with the "same" key (the majority of currently existing highly promissing analysis techniques are in this category, if I don't err), the impact of "outer" dynamics is devastating in my view, for obviously "nothing" of them works any more. As far as I am aware, recently active research activities are done in algebraic analysis, with which some researchers seem to entertain the hope to be able to crack a good block cipher even with as little material as that from one single block. However, even if this scientific breakthrough comes, with the said "outer" dynamics the analyst has to work on each block "individually" to get its key, which is albeit useless for cracking the remaining blocks, since these have completely different keys. In other words, for the algebraic analysis, getting the keys is actually futile in our scenario from the very beginning. But, of course, the above represent merely my humble viewpoints and experts of the group may well have quite different opinions and I don't even exclude from the outset the possibility that some experts would "fundamentally" refute my viewpoints. That's why I have in a recent post in this thread sincerely and explcitly call for a "thorough" discussion on the "inner" and "outer" dynamics. Thanks. M. K. Shen
From: Maaartin on 7 Mar 2010 11:03 On Mar 2, 4:46 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Consider, for instance, AES, where each round (excepting the last) > consists of the four components SubBytes, ShiftRows, MixColumns and > AddRoungkey in this order. Would it really matter very much, if the > order of these components is changed? As layman I guess it wouldn't. I guess, it would in most cases. Look at http://groups.google.com/group/sci.crypt/browse_thread/thread/6f443d0ff1ec3d9a and think what happens when you permute the rounds. Moreover, obviously some operation sequences make no sense at all (it's easy to find examples).
From: Mok-Kong Shen on 7 Mar 2010 14:13 Maaartin wrote: > Mok-Kong Shen wrote: >> Consider, for instance, AES, where each round (excepting the last) >> consists of the four components SubBytes, ShiftRows, MixColumns and >> AddRoungkey in this order. Would it really matter very much, if the >> order of these components is changed? As layman I guess it wouldn't. > > I guess, it would in most cases. Look at > http://groups.google.com/group/sci.crypt/browse_thread/thread/6f443d0ff1ec3d9a > and think what happens when you permute the rounds. Moreover, > obviously some operation sequences make no sense at all (it's easy to > find examples). Could you kindly tell why e.g. the steps ShiftRows and MixColumns of AES couldn't be exchanged? Thanks, M. K. Shen
From: Mok-Kong Shen on 8 Mar 2010 11:58 In order to solicit further thorough discussions, I am taking the liberty to summerize what I posted before and to include some additional points. The main idea is to let a given block cipher behave dynamically, i.e. changing its behaviour after processing each block (or a dynamically determined variable number of blocks). This evidently has the potential to foil from the outset the chance of success of those known analysis techniques that rely on the availability of materials from processing a huge number of blocks with a fixed (unmodified) algorithm and with one and the same key. For other techniques, notably the algebraic analysis, that eventually could reduce this huge number possibly to 1, the work of recovering the key of a block becomes senseless in our dynamic scenario, since the recovered key cannot be used to decipher the other blocks. Thus introducing dynamics into block encryptions turns out to be sort of a catch-all for defending against analysis techniques hitherto known. In using "inner" dynamics, one dynamically modifies a given algorithm at runtime in some "mild" and hence apparently not harmful ways, depending on certain (variable) values taken from the processing of a preceding block. One example is to permute the four components of the round function of AES, which are in a sense "orthogonal" to one another. Another example is to permute the round keys, i.e. employing them in a sequence different from the original algorithm description. A third example is to permute and/or cyclicly bit-shift the four 32-bit computer words of the input and/or output of a cipher of 128 block length. With such "inner" dynamics, the modifications of the processing of any particular block consitute a "random" variable that has a certain range in combinatorics. Thus the work that the analyst (who has no knowledge of that random variable) has to do is evidently way harder than before. In using "outer" dynamics, one employs different keys for different blocks (one key for one block or for a small dynamically determined variable number of blocks). One uses namely a master key and employs e.g. a block cipher in counter mode to generate the said different keys to do the proper encryption of the given plaintext. (The cipher for key generation and for proper encryption can be the same.) The benefit of this is that the workload of the analyst, independent of the method he employs, is evidently multiplied by a factor which is of an order equal to the number of blocks that the plaintext has. Evidently all measures described above could be combined and simultaneously used, if one likes. Note that, if block chaining is used, the effects of the dynamical behaviour of the individual blocks would get coupled in a complex way and thus manifest themselves to an even higher total intensity. (See for chaining also a proposal of mine in the recent thread "Using a kind of running accumulation of ciphertext as chaining value of encryption".) My suggestion above of exploiting dynamics in block encryptions has the particular intention of rendering it possible to continue to satisfactorily and safely use in some near future the currently existing good algorithms despite the continuing and rapid advances in analysis techniques and hardware performances, i.e. without having to take the trouble of developing new encryption algorithms to keep pace with the scientific and technological progress. (Efforts of scientists could prehaps be much more advantageously spent in developing novel encraption algorithms that would be needed in the (maybe very soon) coming quantum computing age, in my humble view.) It must certainly be mentioned that a different, well-known, way of getting higher security is to do multiple encryptions, thus after 3-DES one could do 3-AES etc. Further, since it is beneficial in general to have larger block lengths, one could use a large cipher. (See in this connection the thread "Composing large block cipher from smaller ones", note though the revised code there.) Thanks, M. K. Shen
From: Maaartin on 8 Mar 2010 12:31
On Mar 7, 8:13 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Maaartin wrote: > > Mok-Kong Shen wrote: > >> Consider, for instance, AES, where each round (excepting the last) > >> consists of the four components SubBytes, ShiftRows, MixColumns and > >> AddRoungkey in this order. Would it really matter very much, if the > >> order of these components is changed? As layman I guess it wouldn't. > > > I guess, it would in most cases. Look at > >http://groups.google.com/group/sci.crypt/browse_thread/thread/6f443d0... > > and think what happens when you permute the rounds. Moreover, > > obviously some operation sequences make no sense at all (it's easy to > > find examples). > > Could you kindly tell why e.g. the steps ShiftRows and MixColumns > of AES couldn't be exchanged? Said simply: You need to mix the whole state as much as you can. If you exchange two steps in one round, than you get something like ShiftRows ... ShiftRows ... MixColumns ... MixColumns What should be shifting rows twice in a row good for? As already said, you should try harder to find out such simple things, this is no rocket science. |