NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/sci/crypt/2912

Text File | 1992-08-15 | 7.5 KB | 183 lines

Newsgroups: sci.crypt
Path: sparky!uunet!cs.utexas.edu!milano!cactus.org!ritter
From: [e-mail] (Terry Ritter)
Subject: Re: Growth of mcrypt due to packets
Message-ID: <[e-mail]>
Summary: Very Preliminary Analysis
Keywords: mcrypt
Organization: Capital Area Central Texas UNIX Society, Austin, Tx
References: <[e-mail]>
Date: Sun, 16 Aug 1992 08:19:31 GMT
Lines: 170



 In <[e-mail]>
 [e-mail] (Knight of Tossing and Turning) says:

>This is the post to the creation method of the "Encryption Grid" of
>"Mass Encryption" aka mcrypt.


>The most blunt but valid example of this would be

>(4x4 matrix, password "china")

>   1  2  3  4
>1  C  H  I  N
>2  A  *
>3
>4

>  Where * is a NON-ASCII value, computed by third letter of the
>password + 128 ($80).

 I'm afraid that I do not understand this fully.  Mass Encryption was
 earlier supposed to be a byte Simple Substitution followed by
 bit-transposition on a 1K block:


    From <[e-mail]>:

   >     The incoming packet is then reassigned bytes.  The key to this
   >is generated off of the password line.

   >     The Key Grid is then used as a template to place bits from the
   >incoming data packet into the encrypted packet.


 How does the User Key create the *two* necessary permutations?
 Or does the cipher simply re-use the *same* permutation for *both*
 the substitution and transposition stages?  But how can this be?
 The Simple Substitution on bytes needs 256 entries of 0..255; a
 complete bit-permutation for a 1K block needs 8192 entries of
 0..8191.

 I assume that the matrix structure in the example is used to
 illustrate the transposition permutation (although I would normally
 expect to see a permutation defined in terms of a linear array).
 But there is something very strange about the size of this matrix:

>   For password string "X", and distribution of "X" in a 32 * 32
>   matrix is represented by the function GENKEY, . . .

 If we are to have a 1024-byte-block and bit-transposition, we will
 need to separately position 8192 bit entries.  A 32 * 32 matrix can
 only hold 1024 entries; thus it can only hold enough data to transpose
 the *bytes* of a 1K block, not *bits* (and that takes two-byte values).
 But the substitution step needs only 256 entries.


 (MUCH LATER)

 OK, I think I see how the process works now:

 First we work on the 1's in the "reference grid"; we scan until we
 find the next 1.  Then we place the next input bit at that position
 (presumably in a different storage area, because we will have to
 scan the reference grid again for the next block).

 This continues until we are out of 1's in the "reference grid"; then
 we scan for 0's.

 This means that "255's" (ff hex) and "0's" may well place a full byte
 of data together, which is why there was some discussion of deleting
 255's and 0's from the reference grid.

 It also means that adjacent bits in the input stream are about
 50% likely to be adjacent when enciphered; 25% likely to be separated
 by one bit; 12.5% likely to be separated by two bits, etc.  This
 is in no sense a general permutation; it is better described as
 key-controlled multiplexing or "braiding" (to recall the discussion
 we had last year) without either the random control or the noise data
 channel.

 Multiplexer combiners were first openly described by Geffe [1] in
 1973 (where they were used to mix LFSR sequences).  Breaking the
 sequences produced by these combiners is the whole point of the
 Siegenthaler "correlation attack" [2] and now other correlation
 attacks as well.  Although these have always attacked LFSR combiners,
 I have no doubt that the principles can be applied to data combiners,
 perhaps even with improved results.

 In this cipher, a particular bit in the plaintext block is not
 positioned arbitrarily in the ciphertext block.  Instead, each bit is
 closely related to its original neighbors.  On average, any particular
 bit has one of its plaintext neighbors next to it in the ciphertext.
 On average, 16 bits of ciphertext contain two intermixed 8-bit
 sequences; take 32 bits of ciphertext and you are sure to get a couple
 of complete plaintext characters.  In other words, the diffusion is
 very weak, and diffusion is all that transposition does.

 Moreover, the input data separations (gaps between the runs) are
 not random, indeed, they *make sense* in the underlying reference
 grid; they are, in fact, ASCII letter bit positions.  Known-plaintext
 (after any substitution) may well recover these letters, and thus the
 actual User Key itself.  Any phrase-like structure in the User Key
 will help to fill in gaps in the cryptanalysis.

 One remaining issue is how strong the Simple Substitution is at
 preventing the information necessary for attack.  Usually Simple
 Substitution is considered very weak, and it will be much weaker
 if the same "reference grid" is used for both substitution and
 mixing.  Apparently the substitution step was not displayed in the
 "debug mode" output, so it is hard to know how this is done.


>  The rest of the grid can be generated from happenstance values
>from manipulation of characters from the password characters that
>make up X.  A few formulas would be:

>   matrix[x,y]=( ( 1 / ordinal ( X[current])) * 1000) % 256
>   matrix[x,y]=(pi * 10^ordinal(x) ) % 256
>   matrix[x,y]=(X[current-1]^(e*(1/current-2)*(X[current%length(X)])) % 256

 These formulas simply to expand the User Key.  They do not produce
 independent results; the results are completely defined by the
 User Key.  Thus, the maximum possible uniqueness is the size of the
 User Key alphabet (95) to the power of the size of the User Key
 string (1024), or 95^1024.  Of course, since only 1024 bits are
 used to encipher a block, there can be no more than 2^1024
 possibilities.  Still huge, to be sure, but note the difference
 from the claim:

>   Total permutations for the GENKEY() function = 95 ^ (1024!).

 Few users will have a 1024-character User Key, so the average
 uniqueness will be much lower.  The multiplexing will not be
 well-distributed or random, because a User Key of any size will
 probably be a language phrase, and that plaintext phrase will control
 the multiplexer directly.  The expansion formulas may well be used to
 expand any cryptanalytic "breaks" to multiple places within the block.
 The expansion formulas themselves may relate individual User Key
 characters to multiple locations in the block, yielding multiple
 attack possibilities (it may be possible to attack individual User
 Key characters this way).  For icing on the cake, the plaintext User
 Key itself will exist in a known position the "reference grid," just
 begging to be the first thing attacked.  And this is not to mention
 anagramming, the classical attack on transposition.

 But the real problem is that the underlying multiplexing step
 is so very weak.

 One might argue that the multiplexing still provides 2^1024 options
 for the data block (although I argue that correlation effects greatly
 reduce this value).  But few would disagree that each additional
 block enciphered in the same way would greatly improve the ability
 to attack the cipher.


 References

 [1]  Geffe, P.  1973.  How to protect data with ciphers that are
      really hard to break.  Electronics.  January 4.  99-101.

 [2]  Siegenthaler, T.  1985.  Decrypting a Class of Stream Ciphers
      Using Ciphertext Only.  IEEE Transactions on Computers.
      C34: 81-85.

 ---
 Terry Ritter   [e-mail]