Path: illuminati.io.com!uunet!news.sprintlink.net!nwnexus!news.halcyon.com!
+     coho!ken
From: ken@coho.halcyon.com (Ken Pizzini)
Newsgroups: sci.crypt

Subject: Re: Algorithms
Date: 16 Nov 1994 20:16:32 GMT
Organization: What, me?
Lines: 61
Message-ID: <3adpb0$q9@news.halcyon.com>
References: <199411152009.OAA09390@pentagon.io.com>
NNTP-Posting-Host: coho.halcyon.com

In article <199411152009.OAA09390@pentagon.io.com>,
Terry Ritter  wrote:
> In <3a396u$f50@news.halcyon.com> ken@chinook.halcyon.com
> (Ken Pizzini) writes:
>
>>In article <199411120422.WAA04049@pentagon.io.com>,
>>Terry Ritter  wrote:
>>> We commonly assume that the keysize of Triple DES is at least twice
>>> as long (has 2**56 times as many keys) as ordinary DES, and that may
>>> be.  But consider the simple newspaper amusement ciphers, which are
>>> also Simple Substitution:  Clearly, even three sequential cipherings
>>> through different alphabet permutations will be no harder to solve
>>> than one.  (In this case we do not solve for each of the keys
>>> independently, but this probably does not matter.)
>>
>>Monoalphabetic substition ciphers form a group.  DES does not.
>
> Since this is irrelevant in context, I am at a loss.

Sigh.

> Block ciphers are relatively simple machines which attempt to
> emulate an immense Simple Substitution table.  Such tables all have
> the same entries (the same substitution elements); the thing that
> distinguishes one table from another is the order of the entries.
> For a 64-bit data block, such a table would have 2**64 entries, and
> (2**64)! possible permutations, or "keys."

The best (known) attacks on DES are attacks on the keyspace.
Since the keyspace is less than 2**56 this gives a big boost
to searching through the entirety of the block permutation
space.

> Now, suppose we confine each of the newspaper ciphers to a subset
> of their 26! possible permutations:  Does this prevent us from
> solving the overall permutation of several sequential ciphers?
> No, it does not (unless we insist on solving for each key).  The
> fact that the overall permutation may not be producible from a
> single key is beside the point if we just want to find the hidden
> information.

The best attacks on monoalphabetic substitutions are direct recovery
of plaintext from ciphertext with the aid of various statistical
tools and a model of the underlying plaintext language.  Since the
keyspace is ignored in the general case it doesn't make any difference
to the attack how much you restrict the actual keyspace used.  Of
course if the keyspace is known to be restricted this may be
taken advantage of -- for example if the mapping is known to be
a Caesar cipher you can quickly run-down the 26 alphabets, regardless
of how many times the text is reenciphered.

Now, if a new attack on DES is discovered that is both more efficient
than a keyspace attack and doesn't care about the key used, then
yes, I agree that the groupness of DES is irrelevant.  But since
the best attacks known are attacks on the keyspace it is relevant
whether the keyspace is enlarged by composition.  And the proof
that DES is not a group tells us that the keyspace of DES does
get enlarged by composition.


                --Ken Pizzini