Prev: Volume on Advanced Linear Cryptanalysis -- Contributions sollicited
Next: OAEP vs. PSS in PKCS#1
From: WTShaw on 17 Mar 2010 01:33
On Mar 15, 12:50 pm, "Scott Fluhrer" <sfluh...(a)ix.netcom.com> wrote:
> "Greg Rose" <g...(a)nope.ucsd.edu> wrote in message
>
> news:hnkipa$8g5$1(a)ihnp4.ucsd.edu...
>
>
>
> > In article
> > <5d1bc45d-11fe-4fa8-bc49-d46ce4e27...(a)g26g2000yqn.googlegroups.com>,
> > 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).
>
> > 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.
> > --

Thanks Scott.
From: WTShaw on 17 Mar 2010 01:39
On Mar 15, 1:33 pm, "J.D." <degolyer...(a)yahoo.com> wrote:
> > >>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.

This fits in with the loop possibilities I spoke of before reading
your post. To dismiss any advantage is to fail to allow the
possibility of such techniques that might be found to be useful. I
figure that it's my duty to flag that area.
From: WTShaw on 17 Mar 2010 01:52
On Mar 16, 9:33 am, "J.D." <degolyer...(a)yahoo.com> wrote:
> On Mar 16, 9:51 am, "Scott Fluhrer" <sfluh...(a)ix.netcom.com> wrote:
>
>
>
> > "Maaartin" <grajc...(a)seznam.cz> wrote in message
>
>
> Thanks (to both of you).  It all makes sense now.

I appreciate the efforts here. I'd like to point out the commonality
of such problems in other number systems that have built in loop
characteristics. The issue of varying the contents of loops becomes
one of deranged sets, and picking set sizes with desired qualities,
and chosen contents for utilitarian reasons.
From: Greg Rose on 17 Mar 2010 02:16
In article <46946c82-e552-4a14-90f4-d824bf259d44(a)g28g2000yqh.googlegroups.com>,
WTShaw <lurens1(a)gmail.com> wrote:
>> 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.

Trying it out is academically possible, but not in
this real world. Almost all inputs will fall on a
very large cycle, well over 2^120, so you won't
ever finish. And the chance of finding an input
that lies on a small cycle is negligibly small. So
to do anything that would actually tell you the
answer would require about the same amount of work
as brute-forcing a 128-bit key. Not going to
happen.

>> >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.

Let me say it more forcefully then... You're
wrong. The S-Box didn't change from the first
submission to the end. It is based on a linear
transformation of the function 1/x, in GF(2^8), in
turn based on work by Kaisa Nyberg in Finland.
Now, IIRC, the MARS s-box changed. Maybe that is
what you're thinking.

>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.

Hard to argue with a conspiracy theorist.

Greg.
--
From: Phoenix on 17 Mar 2010 08:00

> If there was no such commutatuve effect, all combinations would need
> to be searched, thus indicating increased strength.

In that case, we fall in encryption with more then one.

See the tread: Is encrypting twice much more secure?
http://groups.google.pt/group/sci.crypt/browse_thread/thread/178cfcf5a045e6df/f5ca1c8b4cd3d23c

And in that tread, the most opinions are: No avantage to do more then
one encryption.



First  |  Prev  | 
Pages: 1 2 3 4 5 6
Prev: Volume on Advanced Linear Cryptanalysis -- Contributions sollicited
Next: OAEP vs. PSS in PKCS#1