# What is a "Group" in Block Cipher Analysis?

## A Ciphers By Ritter Page

We assume that Triple-DES is stronger than plain DES because DES is not a group. So what does that mean?

### Contents

• 1998-12-15 Patrick Juola: "...the relevant property here is that a group is 'closed' under a particular operation."
• 1998-12-15 Andrew Haley: "A group (G, *) is a set G with a binary operator * with the following properties...."
• 1998-12-15 John Savard: "If DES encryption _were_ a group... then double-DES, or triple-DES, or quintuple-DES, would just be regular DES in disguise."
• 1998-12-15 Bryan Olson: "The pure Feistel structure of DES generates only even permutations, so the group generated by DES is a subgroup of the alternating group (which has half the elements of the symmetric group)."
• 1998-12-15 keaak@tgr.arg: "A semigroup is a set S together with an associative binary operation, t : SxS---->S. Nothing is said of the existence of inverses, nor of an identity element under t...."
• 1998-12-16 John Pliam: "There are finite semigroups which are not groups." "However, there are no sub-semigroups of a finite group."
• 1998-12-26 fungus: "Imagine you encrypt some data twice with seperate keys K1 and K2 If there exists a single key K3 which can decrypt the data then the encipherment is a group."
```
Subject: Re: What is "group" means in block cipher ?
Date: 15 Dec 1998 09:26:46 -0500
From: juola@mathcs.duq.edu (Patrick Juola)
Message-ID: <755rj6\$497\$1@quine.mathcs.duq.edu>
References: <36766E0C.F0BF70B2@sec-cse.sch.ac.kr>
Newsgroups: sci.crypt
Lines: 22

In article <36766E0C.F0BF70B2@sec-cse.sch.ac.kr>,
Seung-Chul, Chae <chae@sec-cse.sch.ac.kr> wrote:
>Someone said, DES encryption generates a semigroup and other encryption
>generates a group.
>What is "group" means ? it is a set of block ?

A group is a mathematical abstraction; the relevant property here is
that a group is "closed" under a particular operation.

Which is to say, if you do the operation once (with one parameter)
and then do the operation again (with another parameter), there's some
third parameter that could do it in one step.

Just as an example, the set of whole numbers is closed under addition.

If I add three to a number X (getting X + 3), and then add five to
the result, that's exactly the same as if I had added eight directly
to the original number.  So the operation pair (adding five, adding three)
is exactly the same as the operation (adding eight).

-kitten

Subject: Re: What is "group" means in block cipher ?
Date: 15 Dec 1998 16:51:13 GMT
From: aph@cygnus.remove.co.uk (Andrew Haley)
Message-ID: <756421\$aet\$1@korai.cygnus.co.uk>
References: <36766E0C.F0BF70B2@sec-cse.sch.ac.kr>
Newsgroups: sci.crypt
Lines: 24

Seung-Chul, Chae (chae@sec-cse.sch.ac.kr) wrote:
: Someone said, DES encryption generates a semigroup and other encryption
: generates a group.
: What is "group" means ? it is a set of block ?

A group (G, *) is a set G with a binary operator * with the following
properties:

Associativity: a * (b * c) = (a * b) * c

There is an identity element I: a * I = I * a, for all a elem G.

For each a elem G there exists an inverse a ^ (-1) elem G,
a * (a^(-1)) = (a^(-1)) * a = 1

DES is not a group; that is the operation DES on a block does not have
these properties.

You ought to get a book on the mathematics behind cryptography before
proceeding any further.

Andrew.

Subject: Re: What is "group" means in block cipher ?
Date: Tue, 15 Dec 1998 17:16:54 GMT
From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard)
Message-ID: <367698cd.875397@news.prosurfr.com>
References: <36766E0C.F0BF70B2@sec-cse.sch.ac.kr>
Newsgroups: sci.crypt
Lines: 21

"Seung-Chul, Chae" <chae@sec-cse.sch.ac.kr> wrote, in part:

>Someone said, DES encryption generates a semigroup and other encryption
>generates a group.
>What is "group" means ? it is a set of block ?

If DES encryption _were_ a group - the term is taken from algebra -
which it is not,

then for any two keys x, y, there would exist a key z such that
encrypting any and all plaintext blocks, first with key x, then with
key y, exactly the same result could be obtained by just encrypting
once with key z.

If that were true, then double-DES, or triple-DES, or quintuple-DES,
would just be regular DES in disguise. Even though one would not know
what the key is that is equivalent, for someone not knowing the key,
it would be no harder to crack.

John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html

Subject: Re: What is "group" means in block cipher ?
Date: Tue, 15 Dec 1998 11:45:42 -0800
From: Bryan Olson <first.last@xuptronicsx.com>
Message-ID: <3676BC66.C851EE5C@xuptronicsx.com>
References: <36766E0C.F0BF70B2@sec-cse.sch.ac.kr>
Newsgroups: sci.crypt
Lines: 28

"Seung-Chul, Chae" wrote:
> Someone said, DES encryption generates a semigroup and other encryption
> generates a group.
> What is "group" means ? it is a set of block ?

I'm not really up on semigroups, but I understand that given a
finite set of elements, they're the same thing as groups.

DES, like all block ciphers, generates a group.  The elements of
the group are one-to-one functions from 64 bit blocks to 64 bit
blocks (equivalently, permutations of the set of 64 bit blocks).
Specifically, any permutation that can be generated as a composition
of DES encryptions (possibly with different keys) is in the set.
The group operation is function composition.

The pure Feistel structure of DES generates only even permutations,
so the group generated by DES is a subgroup of the alternating
group (which has half the elements of the symmetric group).  If DES
is any good at simulating random even permutations, it should
generate the alternating group.

A couple other posts answered the question of whether DES _is_ a
group, which is not the same as the one you asked about generating
a group.  A block cipher is a group iff each of the permutations
in the group it generates is equivalent to some single encryption.

--Bryan

Subject: Re: What is "group" means in block cipher ?
Date: Tue, 15 Dec 1998 23:06:04 GMT
From: keaak@tgr.arg
Message-ID: <756q2r\$sht\$1@news-2.news.gte.net>
References: <3676BC66.C851EE5C@xuptronicsx.com>
Newsgroups: sci.crypt
Lines: 37

On Tue, 15 Dec 1998 11:45:42 -0800, Bryan Olson
<first.last@xuptronicsx.com> wrote:

>
>"Seung-Chul, Chae" wrote:
>> Someone said, DES encryption generates a semigroup and other encryption
>> generates a group.
>> What is "group" means ? it is a set of block ?

>I'm not really up on semigroups, but I understand that given a
>finite set of elements, they're the same thing as groups.

No, they're not the same thing.  A semigroup is a set S together with
an associative binary operation, t : SxS---->S.  Nothing is said of
the existence of inverses, nor of an identity element under t
(Although the latter is included in the definition in some texts).

A trivial example:  Let S={1,s} and define a 'multiplication' in the
obvious way except define s^2=s.  This defines a semigroup, and it's
finite.  To see it's not a group, try to find the inverse of s under
this multiplication.

Mike

Decrypt keaak@tgr.arg with ROT13 for email address.

NOTICE TO BULK EMAILERS:  Pursuant to US Code,
Title 47, Chapter 5,  Subchapter II,  227, any
and all nonsolicited commercial E-mail sent to
fee in the amount of \$500 US. E-mailing denotes
acceptance of these terms.

Subject: Re: What is "group" means in block cipher ?
Date: 16 Dec 1998 02:02:48 GMT
From: John Pliam <pliam@ima.umn.edu>
Message-ID: <36771FC8.524C073F@ima.umn.edu>
References: <7571kk\$lun\$1@nntp1.uunet.ca>
<756q2r\$sht\$1@news-2.news.gte.net>
Newsgroups: sci.crypt
Lines: 61

jme@mycpu.org wrote:
> any pointer on a paper about that ? i know there is one paper about
> the proof that des is not a group, but i dont remember the title.

See refs below.

Bryan Olson <first.last@xuptronicsx.com> wrote:
> "Seung-Chul, Chae" wrote:
> > Someone said, DES encryption generates a semigroup and
> > other encryption generates a group. What is "group" means ?
> > it is a set of block ?
>
> I'm not really up on semigroups, but I understand that given a
> finite set of elements, they're the same thing as groups.

There are finite semigroups which are not groups.  (An important
family of examples comes from finite automata whose state transition
diagrams are not a Cayley graphs.  The *syntactic monoid* of such an
automaton is the semigroup of partial functions induced on the state
space by words in the regular expression.  This semigroup is not
a group.)

However, there are no sub-semigroups of a finite group.  Thus the
requirement of decryption means that no block cipher can generate a
semigroup (which is not itself a group).

> If DES is any good at simulating random even permutations, it
> should generate the alternating group.

Wernsdorf [1] showed that, in fact, the one-round functions
of DES generates the full alternating group.  It can be inferred
that the 16-round functions do as well.

> A couple other posts answered the question of whether DES _is_ a
> group, which is not the same as the one you asked about generating
> a group.  A block cipher is a group iff each of the permutations
> in the group it generates is equivalent to some single encryption.

Yeah, I think things are sufficiently confusing and the results
are sufficiently spread out that a summary could be useful to the
beginner:

o No block cipher can generate true semigroup.
o No block cipher can ``be'' a true semigroup.
o Any block cipher generates a subgroup of the symmetric group S_(2^n).
o Any Feistel cipher generates a subgroup of A_(2^n). [2]
o DES ``is'' not a group. [3]
o DES generates the full alternating group, A_(2^n). [1]

John Pliam
pliam@ima.umn.edu
http://www.ima.umn.edu/~pliam

refs:

[1] R. Wernsdorf, "The One-Round Functions of DES Generate the
Alternating Group", EUROCRYPT '92, pp. 99-112, 1993.
[2] S. Even & O. Goldreich, "DES-Like Functions can Generate the
Alternating Group, IEEE inf. theo., IT-29:6, pp. 863-865, 1983.
[3] K.W. Campbell and M.J. Wiener, "DES is not a Group",
CRYPTO '92", pp. 512-517, 1992.

Subject: Re: What is "group" means in block cipher ?
Date: Sat, 26 Dec 1998 09:04:19 -0100
From: fungus <spam@egg.chips.and.spam.com>
Message-ID: <3684B4A3.1A92ABE1@egg.chips.and.spam.com>
References: <36766E0C.F0BF70B2@sec-cse.sch.ac.kr>
Newsgroups: sci.crypt
Lines: 21

Seung-Chul, Chae wrote:
>
> Someone said, DES encryption generates a semigroup and other
> encryption generates a group.
> What is "group" means ? it is a set of block ?

Imagine you encrypt some data twice with seperate keys K1 and K2

If there exists a single key K3 which can decrypt the data then
the encipherment is a group.

In DES this is not possible. You may find one key which will decrypt
one block of data, but it would be luck. You probably won't even be
able to decrypt other blocks of the same message.

--
<\___/>
/ O O \
\_____/  FTB.

```

Terry Ritter, his current address, and his top page.

Last updated: 1999-02-20