commutative property of algorithms
in [Cryptography]
|
Prev: Volume on Advanced Linear Cryptanalysis -- Contributions sollicited
Next: OAEP vs. PSS in PKCS#1
From: Scott Fluhrer on 15 Mar 2010 17:49 "J.D." <degolyer181(a)yahoo.com> wrote in message news:3dd24543-c302-4073-a341-51f621e3a403(a)q15g2000yqj.googlegroups.com... >> >>3. if using a single key and repeatedly encrypting with it while >> >>moving output bits to input bits, do you pass through all combinations >> >>of data, a single grand loop, or do you circuit through lesser >> >>combinations with the same key or different numbers of combinations in >> >>the loops with different keys? >> >> > It is extremely unlikely that AES forms a single >> > cycle for any key, let alone in general. But I >> > don't think anyone knows for sure. A random >> > permutation wouldn't, in general, and AES seems to >> > model a random permutation. >> >> Actually, we do know the answer to question 3: "No" (unsurprisingly). >> This >> is because AES always implements an even permutation, and a single-cycle >> permutaion (on an even number of elements) is an odd permutation. > > I am not sure WTShaw was asking about permutation cycles in the sense > you are talking about. WTShaw might not have intended to ask about permutation cycles; however, that does appear to be the answer to his question. When he says "repeatedly encrypting with it while moving output bits to input bits", it sounds like he is talking about the sequence X, E(X), E(E(X)), ..., E^n(X) When he then ask whether "you pass through all combinations of data", it sounds like whether, for a fixed key and X, whether all possible 2^128 values can be represented by E^n(X), for some n. This is precisely the single-cycle permuation criteria. And, as AES is known not to be a single cycle permutation for any key, we know that the answer to his question is "No". > And if it > is more prone to forming a particular number of loops, I greatly doubt > that this will help in any key-recovery attack. Yes, it doesn't help a key-recovery attack... -- poncho
From: J.D. on 15 Mar 2010 18:24 @Scott Fluhrer > WTShaw might not have intended to ask about permutation cycles; however, > that does appear to be the answer to his question. When he says "repeatedly > encrypting with it while moving output bits to input bits", it sounds like > he is talking about the sequence X, E(X), E(E(X)), ..., E^n(X) > > When he then ask whether "you pass through all combinations of data", it > sounds like whether, for a fixed key and X, whether all possible 2^128 > values can be represented by E^n(X), for some n. This is precisely the > single-cycle permuation criteria. > > And, as AES is known not to be a single cycle permutation for any key, we > know that the answer to his question is "No". You appear to be correct about whether WTShaw was talking about permutation cycles. However I cannot understand your argument for why AES can never be a single cycle for any key. I suppose I will have to read more about permutation parity...do you have any suggestions?
From: Scott Fluhrer on 15 Mar 2010 18:46 "J.D." <degolyer181(a)yahoo.com> wrote in message news:8f9796ea-dfc8-4d31-8ef3-2d7dee0e1694(a)30g2000yqi.googlegroups.com... > You appear to be correct about whether WTShaw was talking about > permutation cycles. However I cannot understand your argument for why > AES can never be a single cycle for any key. I suppose I will have to > read more about permutation parity...do you have any suggestions? http://en.wikipedia.org/wiki/Even_and_odd_permutations As for AES always implementing an even permutation, this can be deduced from the facts that: - AES can be implemented via the composition of a number of invertable operations on subsets of bits; for each suboperation, there is always at least 1 bit that does not participate. - Any operation on a subset of bits (which happen independently of the values of the bits not in the subset) always performs an even permutation on the entire value. - The composition of even permutations is always an even permutation.
From: J.D. on 15 Mar 2010 19:08 On Mar 15, 6:46 pm, "Scott Fluhrer" <sfluh...(a)ix.netcom.com> wrote: > "J.D." <degolyer...(a)yahoo.com> wrote in message > > news:8f9796ea-dfc8-4d31-8ef3-2d7dee0e1694(a)30g2000yqi.googlegroups.com... > > > You appear to be correct about whether WTShaw was talking about > > permutation cycles. However I cannot understand your argument for why > > AES can never be a single cycle for any key. I suppose I will have to > > read more about permutation parity...do you have any suggestions? > > http://en.wikipedia.org/wiki/Even_and_odd_permutations > > As for AES always implementing an even permutation, this can be deduced from > the facts that: > > - AES can be implemented via the composition of a number of invertable > operations on subsets of bits; for each suboperation, there is always at > least 1 bit that does not participate. > > - Any operation on a subset of bits (which happen independently of the > values of the bits not in the subset) always performs an even permutation on > the entire value. > > - The composition of even permutations is always an even permutation. Thanks. That certainly helps, though I am going to have to do a lot more reading before I can understand enough to fully follow your argument.
From: Maaartin on 15 Mar 2010 19:59
On Mar 16, 12:08 am, "J.D." <degolyer...(a)yahoo.com> wrote: > On Mar 15, 6:46 pm, "Scott Fluhrer" <sfluh...(a)ix.netcom.com> wrote: > Thanks. That certainly helps, though I am going to have to do a lot > more reading before I can understand enough to fully follow your > argument. I don't think so, it's easy, the 1st and 3rd parts follows directly from the definition. The second can be clarified by an example: Consider the set of 4-bit numbers (written in hex), habe a function complementing the first bit. This function looks like follows: 0 -> 1 1 -> 0 2 -> 3 3 -> 2 .... E -> F F -> E so it's composition of 8 swaps: 0 <-> 1, 2 <-> 3, ..., E <-> F, so it's even per definition. Obviously the same argument holds for "any operation on a subset of bits (which happen independently of the values of the bits not in the subset)". In fact, the number of swaps is always a multiple of 2**n where n is the number of the bits not in the subset. |