Prev: Volume on Advanced Linear Cryptanalysis -- Contributions sollicited
Next: OAEP vs. PSS in PKCS#1
From: Scott Fluhrer on 16 Mar 2010 09:51

"Maaartin" <grajcar1(a)seznam.cz> wrote in message
news:0e2af2b5-5650-4733-86ec-ce6cc23ce97f(a)r1g2000yqj.googlegroups.com...
On Mar 16, 1:58 am, "J.D." <degolyer...(a)yahoo.com> wrote:
> > Permutation cycles, as I discovered today, are one of the many gaps in
> > my knowledge. I am still grappling with how a permutation with an odd
> > number of disjoint orbits can be "even" (for instance, the AES s-box
> > has 5 disjoint orbits).
> >
> Right. But the sbox works on 1 byte and leaves 15 bytes alone. Taken
> as a function of the whole state it has 5 * 2**(15*8) orbits, right?

Yes, however more to the point, if a single sbox can be implemented in N
transpositions of 1 byte elements, the effect a single sbox on the entire
128 bit element can be performed in N * 2**120 tranpositions (as Martin has
pointed out). This is even, hence the effect of a single sbox on the entire
cipher is even, whether or not N is even.

> Actually, all the sboxes (may) work in parallel, but thinking about
> them as being applied in row makes it clearer here.

Either in a row or serially.

> > I take it that this has to do with the number
> > of transpositions/swaps that a permutation can be decomposed into.
> > But it would seem to raise the possibility that AES under a particular
> > key might well constitute a permutation with an odd number of disjoint
> > orbits (for example "one grand loop") despite being decomposable into
> > an _even_ number of transpositions. So evidently I am missing
> > something...
>
> Yes, but it's simple, too: A permutation decomposable into an even
> number of transpositions is by definition an even permutation. Is a
> "grand loop" an even permutation? Only in case of a set having an odd
> number of elements. Is 2**128 odd?
>
> For the "grand loop" just make an example, consider the set {0,1,2,3},
> wlog. let x -> (x+1) mod 4 be the permutation, you can decompose it
> into 3 swaps:
> 0 <-> 1
> 1 <-> 2
> 2 <-> 3

Well, a grand loop permutation (or single cycle permutation) on N elements
can be implemented in N-1 transpositions (as, in your case, you created a
single cycle permutation on 4 elements with 3 transpositions). Hence, a
single cycle permutation on an even number of elements is odd, while a
single cycle permutation on an odd number of elements is even.

In the case of AES, we have 2**128 elements, this is even, and hence a
single cycle permutation would be odd.

--
poncho


From: J.D. on 16 Mar 2010 10:33
On Mar 16, 9:51 am, "Scott Fluhrer" <sfluh...(a)ix.netcom.com> wrote:
> "Maaartin" <grajc...(a)seznam.cz> wrote in message
>
> news:0e2af2b5-5650-4733-86ec-ce6cc23ce97f(a)r1g2000yqj.googlegroups.com...
> On Mar 16, 1:58 am, "J.D." <degolyer...(a)yahoo.com> wrote:
>
> > > Permutation cycles, as I discovered today, are one of the many gaps in
> > > my knowledge. I am still grappling with how a permutation with an odd
> > > number of disjoint orbits can be "even" (for instance, the AES s-box
> > > has 5 disjoint orbits).
>
> > Right. But the sbox works on 1 byte and leaves 15 bytes alone. Taken
> > as a function of the whole state it has 5 * 2**(15*8) orbits, right?
>
> Yes, however more to the point, if a single sbox can be implemented in N
> transpositions of 1 byte elements, the effect a single sbox on the entire
> 128 bit element can be performed in N * 2**120 tranpositions (as Martin has
> pointed out).  This is even, hence the effect of a single sbox on the entire
> cipher is even, whether or not N is even.
>
> > Actually, all the sboxes (may) work in parallel, but thinking about
> > them as being applied in row makes it clearer here.
>
> Either in a row or serially.
>
>
>
> > > I take it that this has to do with the number
> > > of transpositions/swaps that a permutation can be decomposed into.
> > > But it would seem to raise the possibility that AES under a particular
> > > key might well constitute a permutation with an odd number of disjoint
> > > orbits (for example "one grand loop") despite being decomposable into
> > > an _even_ number of transpositions. So evidently I am missing
> > > something...
>
> > Yes, but it's simple, too: A permutation decomposable into an even
> > number of transpositions is by definition an even permutation. Is a
> > "grand loop" an even permutation? Only in case of a set having an odd
> > number of elements. Is 2**128 odd?
>
> > For the "grand loop" just make an example, consider the set {0,1,2,3},
> > wlog. let x -> (x+1) mod 4 be the permutation, you can decompose it
> > into 3 swaps:
> > 0 <-> 1
> > 1 <-> 2
> > 2 <-> 3
>
> Well, a grand loop permutation (or single cycle permutation) on N elements
> can be implemented in N-1 transpositions (as, in your case, you created a
> single cycle permutation on 4 elements with 3 transpositions).  Hence, a
> single cycle permutation on an even number of elements is odd, while a
> single cycle permutation on an odd number of elements is even.
>
> In the case of AES, we have 2**128 elements, this is even, and hence a
> single cycle permutation would be odd.
>
> --
> poncho

Thanks (to both of you). It all makes sense now.
From: WTShaw on 17 Mar 2010 01:18
On Mar 15, 1:06 am, g...(a)nope.ucsd.edu (Greg Rose) wrote:
> In article <5d1bc45d-11fe-4fa8-bc49-d46ce4e27...(a)g26g2000yqn.googlegroups..com>,
>
> WTShaw  <lure...(a)gmail.com> wrote:

>
> >1. Are all combinations of bits allowed as input data?
>
> Yes.
>
> >2. Are all combinations of bits allowed as output data?
>
> Yes.
>
I figured that if everything was allowed, the first two questions
would be 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.

One way to find out is to try it. Given the information we have, if a
given block encrypted with a picked key gives a particular output,
then if the cycle is short enough to be done, solution would be
available by progressive encryptions to the end of the loop.

If certain ciphertexts were able to be seen as children from a key or
range of keys, this would simplify a search.
>
> >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.

This is the important crux of what I am saying, all numbers are used
within a number system, AES, DES, etc., are constrained by binary as a
family of number systems and more specifically by which one, 64, 128,
256, because even these have different characteristics.
>
> >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.
>
No, I think that mention of slight modifications did occur or were
considered. It seemed strange to me at the time, almost as a footnote
and with arguments over numbers of rounds and how many it takes to
boggle so many minds and techniques.

The big question is that by knowing as much as NSA is supposed to
know, why did they ask civilians even of different countries to solve
their problem. For one or more reasons probably, NSA had failed with
DES and did not want to again, various people hoped that a deficient
system would be picked so might be routinely broken, it needed to be
produced for various political reasons, government wanted to pick the
brains of contributers, and others.


> --

From: WTShaw on 17 Mar 2010 01:21
On Mar 15, 7:43 am, Phoenix <ribeiroa...(a)gmail.com> wrote:
> On 9 Mar, 23:00, WTShaw <lure...(a)gmail.com> wrote:
>
> >An immediate question could be whether two or more keys used with a
> >distinct algorithm could be simplified to perhaps a single key and
> >single use, or new sets of  multiple keys might give the same result
> >as those used before.  If so, multiple encryptions might have no real
> >advantage at all for that algorithm; it's commutative.
>
> I absolutly agree with "no real advantage" in encryption.
>
> See:
> Encrypt a commutative algorithm with i.e 3 keys:
>
> K1,K2,K3
>
> We can decrypt with
>
> K1,K2,K3  The original
> K1,K3,K2
> K2,K1,K3
> K2,K3,K1
> K3,K1,K2
> K3,K2,K1
>
> With a total 6 possible permutations (3!), and all are not simple (at
> least in size)
>
> Making a key attack based in this principle (commutative weackness),
> are no advantage.
> At the end, we still need to now K1, K2 and K3.
>
> Commutativity on encryption, don't means weakness.

If there was no such commutatuve effect, all combinations would need
to be searched, thus indicating increased strength.
From: WTShaw on 17 Mar 2010 01:31
On Mar 15, 10:32 am, unruh <un...(a)wormhole.physics.ubc.ca> wrote:
> On 2010-03-15, WTShaw <lure...(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.
>
This is important, even building a map of such variations. Again from
research in different number systems, 1) present what appears as one
loop; 2) quantities of equal but shorter loops, 3) a large loop and a
smaller loop, base 10; 4) populations of various sized loops but many
in each category; and surely more depending on the several
parameters.

Knowing this type of information is important be assigned keys might
be easier or harder to search, I suppose on who might benefit by
knowing about it.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6
Prev: Volume on Advanced Linear Cryptanalysis -- Contributions sollicited
Next: OAEP vs. PSS in PKCS#1