🚀 go-pugleaf

 In <1992Aug13.153842.24060@mintaka.lcs.mit.edu>
 knight@hal.gnu.ai.mit.edu (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 <1992Aug11.001118.28760@mintaka.lcs.mit.edu>:

   >     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   ritter@cactus.org

 My thanks to those who remind me that each byte has eight bits.
 The values should be 95^1024 keys, controlling 2^8192 possible
 cipherings.  But I'm not sure it matters much.

 Now that I think about it, Mass Encryption is odd in that the
 User Key is so closely connected to the internal key.  Of course,
 any cipher can be insecure with a short key, but the difference
 here is that the User Key is so directly related to the ciphering
 process itself.  Whereas a short key in other ciphers may select
 in a well-distributed fashion from a small number of choices
 hidden among all the possible cipherings (and even this is weak),
 in this cipher a short key means that only a small portion of the
 cipher is really unique.  The rest of the cipher is functionally
 derived from the unique portion which is exposed to attack.

 Whereas in other ciphers a User Key selects a particular
 ciphering as a unit, in this cipher *each character* in the User
 Key *independently* selects a portion of the cipher, a known
 particular byte.  This means that individual characters of the
 User Key can be isolated and attacked separately.  This is unusual
 and very weak.

 Indeed, each User Key character may control *several* particular
 bytes, due to the key expansion formulas; such bytes could be
 anagrammed in an attempt to find a single solution for the
 associated key character, independent of the rest of the key.

 When selections are poorly distributed, the number of possible
 cipherings tells the wrong story.  For example, Simple Substitution
 on 26 letters should select from 26! (that's about 2^88) possible
 cipherings.  Nevertheless, people somehow manage to solve these
 ciphers virtually by examination.  Trial-and-error occurs, but it
 is not a *random* sort of trial-and-error; it is instead directed
 by probable words and probable adjacent characters.  For solution
 purposes, each letter of the substitution key can be worked on
 separately, most of the time.

 Evaluating the number of possible cipherings is useful only to the
 extent that other attacks have been eliminated, and brute force
 remains as the only available attack.  But that is not the case in
 Simple Substitution, and that is not the case in Mass Encryption
 either.

 ---
 Terry Ritter   ritter@cactus.org