From: "Mike Johnson" <exabyte!smtplink!mikej@uunet.UU.NET>
Date: Fri, 1 Oct 93 16:43:40 PDT
To: cypherpunks@toad.com
Subject: MPJ Encryption Algorithm
Message-ID: <9309017495.AA749522149@smtplink.exabyte.com>
MIME-Version: 1.0
Content-Type: text/plain



Bill Stewart writes:
> Sounds interesting; do you have any comparisons between it and IDEA
> about either encryption strength, speed, or design philosophy?

The full design philosophy for MPJ is in my thesis.  Since then, I learned
about differential cryptanalysis and was relieved to see that MPJ is fairly
resistant to that.  Here is a short summary:

Algorithm Key size Block size Rounds    Strength*  SW Speed   HW Speed

DES        56 bits  64 bits   16/2       22-55     slow       fast
3DES      112 bits  64 bits   (16*3)/2   24-58     slower     fast
IDEA      128 bits 128 bits   16         65-110    fast       fast
Skipjack   80 bits 128 bits   32            79     ?          ?
MPJ       128 bits 128 bits   10         70-120    medium     very fast
MPJ2     >=64 bits 128 bits   >=10       50-128    <=medium   <=very fast

*Strength is a GUESS at log base 2 of the complexity of breaking it.

Algorithm Legal status       Back door?  Origin

DES       Public Domain      No          IBM/NBS->NIST/NSA
3DES      Public Domain      No          IBM
IDEA      Patented           No          Switzerland
Skipjack  Classified         LEAF        NSA
MPJ       Public Domain      No          USA - University of Colorado at
                                               Colorado Springs (UCCS)
MPJ2      Not yet released   No          USA

DES Design philosophy:
(1) Fit in small chip

(2) Use involution for reversibility (only half of block changes with each
round)

(3) Use polyalphabetic nonlinear s-boxes of limited size (requires great care
to avoid differential cryptanalysis)

(4) Some design criteria still classified.

3DES Design philosophy:

(1) Cascade existing known algorithm

(2) Avoid weak key situations

(3) Try not to require too much more key than the strength of the algorithm
justifies (i.e. just 2 instead of 3 keys are used).

(4) Apply a bandaid.  Making one compound block cipher would have been more
secure, but not all the s-box design criteria are known.

IDEA Design philosophy:

(1) Use unrelated arithmetic operations on different fields.

(2) Use only 32 bit arithmetic operations for speed on a computer.

(3) Arrange the structure of the algorithm to do proper confusion/diffusion.

(4) Very small code and memory space used in computer.

Skipjack design philosophy (guessed):

(1) Similar to DES, but with a block size of 128 bytes.

(2) No attack known to the NSA will be more than a bit or two better than
exhaustive key search.

(3) Learn from the mistakes of DES (i.e. avoid weak keys and complementation
symmetries DES suffers from).

(4) Restrict knowledge of the algorithm as much as possible.

MPJ Design philosopy:  

(1) Relax some of the size limits of DES & IDEA to gain security, but make
sure it fits on a PC.  

(2) Avoid fragile fixed s-box & subkey design of DES, but copy its product
cipher structure.  

(3) Change the whole block with each round instead of just half (i.e. 10 MPJ
rounds is as effective as 20 DES-type rounds).  

(4) Make every output bit a strong function of every bit of the input and
every bit of the key within 3 rounds.

(5) Use such simple operations in a complex and nonlinear fashion that
mathematical breakthroughs are not a threat (as with RSA).  

(6) Make the substitution steps reversible through a very clever construction
of reversible substitution arrays directly from the key.  

(7) Make key scheduling slow (to discourage exhaustive search for keys), but
make the algorithm very fast, especially in dedicated hardware.  

(8) Make creative use of nonlinearity, bit twiddling, and rounds to thwart an
analytical attack using massive quantities of known or chosen plain text.

MPJ2 Design philosophy:

(1) Generalize the key scheduling to accommodate variable length keys.

(2) Generalize to n rounds.

(3) Attempt to do key scheduling on the fly in cases where the memory
required for precomputed internal keys take up too much RAM.

Common elements:  All of these block cipher algorithms use repeating rounds
of "confusion and diffusion" or "substitution and permutation" weaker ciphers
to form a stronger product cipher.  All of them are secure, even if the
cipher becomes known.  Skipjack is classified more to prevent knowledge of
design criteria and cryptanalysis secrets, and to allow the forced insertion
of a back door (LEAF) than for the security of the algorithm (just ask Dr.
Denning).  DES and 3DES can raise the price of unauthorized disclosure of
secrets above the average individual's means.  The others have the potential
of raising the price of eavesdropping by breaking crypto algorithms to above
the budgets of organized crime, hostile governments, and terrorists.  None of
them prevent other technological solutions to spying, such as placing bugs
closer to the target individual, office, or computer system.

General rules of the game in CRYPTOGRAPHY and CRYPTANALYSIS:

1.  There is always a way to crack any practical cryptosystem.

2.  Your opponent will not tell you if she has broken your cryptosystem and
is reading your mail.

3.  The longer any one cryptosystem is in use, and the more widely it is
used, the more likely it is that someone has broken it, or at least
discovered a weakness in it and not told anyone about it.

4.  The more widely used a cryptosystem is, the more profitable it is to try
to break it (for either noble or ignoble purposes).

5.  Exclusive control of the ability to communicate securely is a powerful
force that can easily be corrupted.

6.  Putting all your eggs in one basket is unwise.  Use more than one
cryptosystem, and change keys regularly -- even if you don't suspect
compromise.

7.  Insecure cryptosystems often appear on the surface to be secure.  They
are often sold for good money.

DISCLAIMERS:

DISCUSSIONS ABOVE ARE FROM MEMORY AND MAY NOT BE ACCURATE.  ALL DATA CLAIMING
TO BE GUESSWORK IS.  PROVING ANY CRYPTOSYSTEM SECURE IS USUALLY IMPOSSIBLE. 
INVENTERS OF CRYPTO ALGORITHMS ARE NOT QUALIFIED TO JUDGE THEM.

                                         Mike Johson
                                         mpj@csn.org

This message contains writings protected under the First Amendment of the
Constitution of the United States of America.  Censorship is forbidden.