NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/sci/crypt/4990

Text File | 1992-11-18 | 4.1 KB | 86 lines

Newsgroups: sci.crypt
Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!zaphod.mps.ohio-state.edu!malgudi.oar.net!news.ans.net!newsgate.watson.ibm.com!yktnews!admin!wo0z!lwloen
From: [e-mail] (Larry Loen)
Subject: Re: Attack Methods
Sender: [e-mail]
Message-ID: <[e-mail]>
Date: Wed, 18 Nov 1992 20:34:13 GMT
Reply-To: [e-mail]
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
References: <[e-mail]> <[e-mail]> <[e-mail]>
Nntp-Posting-Host: wo0z.rchland.ibm.com
Organization: IBM Rochester
Lines: 71

In message <[e-mail]> Jim Dailey writes:

 [ long description of transposition system with some
   "random" pad bytes thrown in before the ordinary
   transposition step ]

Transpositions are weak because they fall to some pretty universal,
system-dependent attacks.

The technique of interest here is called "multiple anagramming".

A given message's length will be  length(prefix) + length(real text) +
                                  length(suffix)

where prefix and suffix are the padding however added.

Now, in the ordinary course of business, there will be several messages
of the same length.  There may well be unique messages that have no
one of the same length, but we start with those of the same length.
What follows will tend to work even if the length of the real texts vary;
the only issue of interest is that the overall length is the same and that
the transposition step is performed _after_ the padding.

If one knows (and, one usually does) the frequency distribution of the
real text, one can use probability theory, maybe with a little manual
inspection, to "stack" the messages vertically and solve by fragment.
Let's assume English text are the messages.

Now, the most common two words in English are "the" and "and".
Whenever both ended up at the same location, the fragment:

Msg1  t...h...e
Msg2  a...n...d  (were... represent other ciphertext in between of same length).

would stand out.  After all, there is no substitution, so the real words are
in there somewhere!  To be sure, this is a tedious process, but many who
post here can testify that it can be made to work.  And, one often has to
work with less "obvious" fragments, but if one starts with even a few of
these, it is remarkable how the pieces start to interact and build up.
The only hard part is getting the first few fragments and this is not very
hard with enough text because things like the above eventually happen.

(The anagramming, if you did not follow, is most easily seen in a trivial
example.  Suppose the transposition simply took pairs of letters and swapped
them.  Decide how to multiply anagram the following two fragments --.

Msg1  htcetanihtheta
Msg2  nabdtanohtceta   which reads "thecatinthehat" for Msg1 and
                                   "andbatonthecat" for Msg2).

Now, this will not work well for the "prefix" part of the text.  However,
for many transposition systems, recovering the real message text in
the middle will reveal the "key"; that is, the method used to transpose
the data and so the pad becomes irrelevant, because one stops and acts like
the legitimate message receiver the moment the key is produced.

Indeed, only at the very end
may the attacker even be aware of the padding, since one simply starts building
up fragments from the most likely places, which occur anywhere.

There are other ways to pad, but they have similar flaws, sooner or later.
And, yes, there are complaints by users about the extra data, especially if
it has to be 'eyeballed' to be removed.

There may well be a way to make this padding idea work, but this path
has been trodden many times and is not considered very promising; there are
much better techniques available.  It is an excellent example, however, of
how adding various sorts of "pad" bytes don't really help much.
--
   Larry W. Loen        |  My Opinions are decidedly my own, so please
                        |  do not attribute them to my employer