commutative property of algorithms
in [Cryptography]
|
Prev: Volume on Advanced Linear Cryptanalysis -- Contributions sollicited
Next: OAEP vs. PSS in PKCS#1
From: unruh on 15 Mar 2010 11:32 On 2010-03-15, WTShaw <lurens1(a)gmail.com> wrote: > On Mar 9, 9:12?pm, unruh <un...(a)wormhole.physics.ubc.ca> wrote: > >> >> almost all modern block cyphers are probably not a group and certainly >> are not commutative. Stream cyphers often are commutative, but almost >> certainly are not a group, although the OTP IS both commutative and >> forms a group ( and is the only provably unbreakable cypher). >> >> ... > Even while concerned with other matters, I've been thinking of the > best way to use simple logic to address this issue. > > Concerning AES, for example since I am somewhat rusty on it these > days.: > > 1. Are all combinations of bits allowed as input data? Yes. > > 2. Are all combinations of bits allowed as output data? Yes. > > 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? Unknown, but there probably are loops of length less than 2^128 and the distribution of loop lengths probably depends on the key. > > I am well aware of how these matter with different base number > systems. And, that my research results with different bases were very > strange, not what I expected at all. C > > Changing the boxes in AES might affect #3. Another questions would > be: > > 4. What do we know about NSA's recommended changes to these boxes, > why, and how would any specific desired effects be confirmed? > >
From: unruh on 15 Mar 2010 11:37 On 2010-03-15, Greg Rose <ggr(a)nope.ucsd.edu> wrote: > In article <5d1bc45d-11fe-4fa8-bc49-d46ce4e271d1(a)g26g2000yqn.googlegroups.com>, > WTShaw <lurens1(a)gmail.com> wrote: >>On Mar 9, 9:12?pm, unruh <un...(a)wormhole.physics.ubc.ca> wrote: >> >>> >>> almost all modern block cyphers are probably not a group and certainly >>> are not commutative. Stream cyphers often are commutative, but almost >>> certainly are not a group, although the OTP IS both commutative and >>> forms a group ( and is the only provably unbreakable cypher). > > I don't know what you (unruh) mean about stream > ciphers and OTP forming a group. What is the > operation in this context? If you mean XOR to > combine keystream with plaintext, it is a group, > for both OTP and any additive stream cipher. If > that isn't what you mean I don't understand. C(k1,C(k2,M))=C(k3,M) for all k1,k2 and there exists a k' for every k such that C(k',(C(k,M))=M This is clearly true for the OTP. The first is probably untrue for other stream cyphers. > >>> ... >>Even while concerned with other matters, I've been thinking of the >>best way to use simple logic to address this issue. >> >>Concerning AES, for example since I am somewhat rusty on it these >>days.: >> >>1. Are all combinations of bits allowed as input data? > > Yes. > >>2. Are all combinations of bits allowed as output data? > > Yes. > >>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. > >>I am well aware of how these matter with different base number >>systems. And, that my research results with different bases were very >>strange, not what I expected at all. C > > I don't know what this means either. AES is > defined on 128-bit blocks. Number systems don't > come into it. > >>Changing the boxes in AES might affect #3. Another questions would >>be: >> >>4. What do we know about NSA's recommended changes to these boxes, >>why, and how would any specific desired effects be confirmed? > > I don't think NSA recommended any changes > to the AES S-box. I think you're confusing it > with DES. And the effect of their changes is > well understood, in that case, to strengthen > DES against differential cryptanalysis. > > Greg.
From: Scott Fluhrer on 15 Mar 2010 13:50 "Greg Rose" <ggr(a)nope.ucsd.edu> wrote in message news:hnkipa$8g5$1(a)ihnp4.ucsd.edu... > In article > <5d1bc45d-11fe-4fa8-bc49-d46ce4e271d1(a)g26g2000yqn.googlegroups.com>, > WTShaw <lurens1(a)gmail.com> wrote: >>On Mar 9, 9:12 pm, unruh <un...(a)wormhole.physics.ubc.ca> wrote: >> >>> >>> almost all modern block cyphers are probably not a group and certainly >>> are not commutative. Stream cyphers often are commutative, but almost >>> certainly are not a group, although the OTP IS both commutative and >>> forms a group ( and is the only provably unbreakable cypher). > > I don't know what you (unruh) mean about stream > ciphers and OTP forming a group. What is the > operation in this context? If you mean XOR to > combine keystream with plaintext, it is a group, > for both OTP and any additive stream cipher. If > that isn't what you mean I don't understand. > >>> ... >>Even while concerned with other matters, I've been thinking of the >>best way to use simple logic to address this issue. >> >>Concerning AES, for example since I am somewhat rusty on it these >>days.: >> >>1. Are all combinations of bits allowed as input data? > > Yes. > >>2. Are all combinations of bits allowed as output data? > > Yes. > >>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. That also answers the question about changing the sboxes: no, changing the sboxes doesn't affect this, because the Rijndael structure always implements an even permutation, independent of what the sboxes are. > >>I am well aware of how these matter with different base number >>systems. And, that my research results with different bases were very >>strange, not what I expected at all. C > > I don't know what this means either. AES is > defined on 128-bit blocks. Number systems don't > come into it. > >>Changing the boxes in AES might affect #3. Another questions would >>be: >> >>4. What do we know about NSA's recommended changes to these boxes, >>why, and how would any specific desired effects be confirmed? > > I don't think NSA recommended any changes > to the AES S-box. I think you're confusing it > with DES. And the effect of their changes is > well understood, in that case, to strengthen > DES against differential cryptanalysis. That is correct; the sbox used in AES is the one proposed in the original Rijndael proposal. NSA may have proposed their own set of sboxes for their own use. I haven't heard of such, though, and I'd be skeptical that would have occurred. But, even if it did, it wouldn't affect the standard AES implementation. > > Greg. > --
From: J.D. on 15 Mar 2010 14:33 > >>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. For example, take the permutation (in the sense of a bijective function from the set S to itself) f : {A, B, C, D} --> {A, B, C, D} such that: f(A)=B f(B)=C f(C)=D f(D)=A The domain/codomain of f has an even number of elements, but the elements form a single loop from A to B to C to D and then back to A (in the manner I think WTShaw was describing). Contrast this with the permutation g : {A, B, C, D} --> {A, B, C, D} such that: g(A)=A g(B)=C g(C)=D g(D)=B Here the permutation has two separate loops of different size (if mapping A onto itself can be called a 'loop'). If anyone is curious, the AES s-box forms 5 separate loops in this fashion, all of different sizes. I doubt that the AES family of permutations is any more prone to forming a particular number of loops (whether one "grand loop" or any higher number of smaller loops) than a random permutation. 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.
From: J.D. on 15 Mar 2010 15:44
> I doubt that the AES family of permutations is any more prone to > forming a particular number of loops (whether one "grand loop" or any > higher number of smaller loops) than a random permutation. 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. However, if instead of AES we are talking about a classic Feistel cipher with a particular kind of key schedule then we might be able to use this looping quality in an attack. For example, let us say that the key schedule is such that --due to the self-inverting nature of the Feistel structure-- the decryption function under one key is identical to the encryption function under another key. i.e. for all plaintexts x and for all keys k0, there exists a key k1 such that if Ek0(x)=y then Ek1(y)=x -- where Ei(j) means the encryption of j under key i. For such a pair of keys (a "good pair"), the composite function, Ek1(Ek0(.)), is essentially the identity function, and the identity function over a set with n elements always forms n different 'loops' of the sort described above. Such a pattern is easily detectable: and so with enough adaptive chosen related key plaintexts, an attacker should be able to find a good pair. With a good pair, the first round key under one key will be identical to the last round key under the other, and the same for the second and penultimate round keys, and so on. Given this fact and the known relation between the keys, it should be possible to deduce the keys (though this will depend on how complicated the key-schedule is). For example, the xor-difference between the first round keys of a good pair must be identical to the xor-difference of the last round keys of the same pair. So if we know the xor-difference between the two user- keys then we can follow that difference through the key schedule and then filter out possibilities that do not meet the above condition; and once we have filtered out enough we can easily guess the actual values of the keys. |