The symmetric ciphers

[Leo Gaspard]

> The reason why the cryptanalytic community looked into whether DES forms a
> group is because the 56-bit keyspace was too short and we critically needed
> a way to compose DES into a stronger algorithm.  That's not the case with
> AES.

Disclaimer : I am not a mathematician, only a student in mathematics. I did not
learn mathematics in the English language, but have tried to check on wikipedia
the vocabulary I am about to use is the correct in english, but please pardon me
if I make a mistake. Anything I have not checked should be redefined. And this
text is not intended for people with no insight on basic group theory.


Definitions :
 * [1;n] will be the set of all integers from 1 to n, ends included.
 * M is the set of possible messages.
 * C is the set of possible ciphertexts.
 * F(M, C) is the set of encryption functions (key included), that take a
   message in M as input, and yields a ciphertext in C as output. IOW, it is the
   set of bijections from M to C.

Assumption : F(M, C) is a group for \circ, the composition, as any encrypted
message ought to be decipherable. (Well, not really a group, as the inverse
bijection would be in F(C, M), but I will write it is a group for ease of
expression. Correcting this would only be adding useless text, so feel free to
do it in you mind if you prefer.)


First, I'll assume that, when you say "ROT is a group", you mean that
(n -> ROTn) is a group morphism between (F(M, C), \circ) and (Z/26Z, +).


Let n be a positive integer.

So, now, let's assume K = [1; 2^n] is a group for some law *. Let's assume that
AES-n is a group morphism between (F(M, C), \circ) and (K, *).

In my opinion (and a bit more than that), it changes nothing to the question.
Indeed, composing two (or more) AES-n with independantly random-chosen keys is
at least as strong as one AES-n with a random-chosen key, which, IIRC, was the
heart of thhe matter.


As a proof, let's take k1 and k2 two independantly random-chosen keys in K.
Then, AES-n(k1) \circ AES-n(k2) = AES-n(k1 * k2).

Now, let's prove k1 * k2 is a randomly-chosen key in K. First, (x -> k1 * x)
is a bijection. So, if x is chosen randomly, then so is k1 * x. And k2 is chosen
randomly (independantly from k1, which is quite important here), so k1 * k2 is a
randomly-chosen key in K.

Proof of the "first" statement :
Let a, b two keys in K. Then k1 * a = k1 * b implies a = b by mere
multiplication by k1^{-1}.
So (x -> k1 * x) is an injection from K to K, and K is a finite set, so
(x -> k1 * x) is a bijection on K.
Another way of seeing this would be by exposing the inverse : (x -> k1^{-1} * x)
I know this is a well-known result, but preferred to redemonstrate it, just in
case.


So, whether AES-n is a group morphism or not does not matter for the question,
which was trying to find a resulting algorithm at least as strong as the
strongest of all.

And DES was checked for a group-like behavior because the objective was not to
create an algorithm at least as strong as the strongest component, but to create
an algorithm as strong as the sum of all components, which is substantially
harder.

BTW, the example about ROT still fits the proof : remember ROT0 could be
selected by a random key with probability 1/26. You can check ROTn \circ ROTm
(ie. ROT(n + m)) yields ROT0 with probability 1/26, when n and m are both chosen
uniformly. (Well, it's just 26 ways of making 26 from the sum of two numbers
from 0 to 25, this divided by the total possibilities of 26^2.)


As a conclusion, IMHO (and without proof here, just gut feeling, even though a
start of proof was given by Philipp earlier), stacking two algorithms with
unrelated randomly-chosen keys makes an algorithm at least as strong as the
strongest of the two algorithms, to the cost of transimitting a longer key and
spending more time on enc/decryption, which, admittedly, might be quite an
issue.


Hoping I did not make too much mistakes, both in mathematics and in the English
language,

Leo