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 Ritterwrote: > 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