From: Michael Johnson <mpjohnso@nyx.cs.du.edu>
Date: Mon, 27 Sep 93 10:41:14 PDT
To: cypherpunks@toad.com
Subject: Challenge: break the MPJ Encryption Algorithm
Message-ID: <Pine.3.05.9309271122.A29490-d100000@nyx>
MIME-Version: 1.0
Content-Type: text/plain



I would like as many of you as are interested to take a serious look at a
private key block encryption algorithm that I invented and let me know if
there is any weakness in it that you can discover.

No, I will not insult you with a block of random data as a challenge text.  I
have published the full algorithm, including source code, in my Master's
Thesis.  It is available to callers in the USA only on my BBS at 303-938-9654
(local to the Denver/Boulder calling area) as CRYPTMPJ.ZIP and MPJ_PS.ZIP. 
CRYPTMPJ.ZIP contains a plain ASCII text version of my thesis, full Pascal
source code, and an executable program CRYPTMPJ.EXE that was used to test
it.  MPJ_PS.ZIP contains a PostScript version of my Thesis so that you can
print out the pictures and see the equations more normally.  Other sources: 
CompuServe, IBMSYS forum, as CRYPTM.ZIP; anonymous ftp to soda.berkeley.edu;
and on the disks bound in the back of the book "Network Security Secrets" by
David Stang and Sylvia Moon (ISBN1-56884-021-7; published by IDG Books
Worldwide, Inc.).

Here is a short description of the algorithm:

1.  Using a convoluted key expansion process, expand a 128 bit (16 byte) key
into 160 different, reversible 256 byte substitution boxes.

2.  Execute ten rounds of encryption, where each round consists of (1) alter
each byte of the input by replacing it with the value obtained by using the
input byte as an index into the corresponding substitution box, then (2)
perform a fixed "wire crossing" bit selection such that each output byte is
a function of one bit from each of 8 different input bytes.

Each substitution box is used only once in encrypting a block.  Block size is
16 bytes (128 bits).

Attacks I have considered:

1.  Brute force (both exhaustive key search and precomputation).  Good luck.

2.  Analytical solution for the contents of the substitition arrays with a
chosen plain text attack.  With 10 or more rounds, the complexity of the
matrix of boolean equations required and the quantity of known or chosen
plain text required seems to make this impractical, but I may be missing
something.

3.  Differential cryptanalysis.  Since the structure of the cipher algorithm
has no simpler subkeys than the arrays themselves, this can't be done in the
same sense as Biham and Shamir have discussed for DES, IDEA, etc.  There may
be a related attack, but I haven't thought of one yet (hardly a proof of
nonexistance!)

4.  Attack of the key expansion algorithm to simplify an analytical attack of
the contents of the substitution arrays.  This seems to me to be worse than a
frontal attack on the arrays, given the complexity of the key scheduling
algorithm.  Then again, I suffer inventor's blindness in this area.

The only complaints anyone has made so far are not fatal, in my humble
opinion:

1.  The key is fixed length.  OK, the key expansion could be done differently
to make this variable, but 128 bits is enough to preclude exhaustive key
search within the budgets of anyone I anticipate worrying about for the next
10 years, at least.  That assumes growth in computing power of a few orders
of magnitude, too.

2.  It is a symetric key algorithm, not a public key algorithm.  Guilty as
charged.  On the other hand, you don't have to pay royalties to PKP (or
anyone, including me) to use the algorithm in your own code or hardware.

3.  The user interface to CRYPTMPJ.EXE is confusing, archaic, and not as
simple as it should be.  True.  I plan to fix this some day, but it is still
not a problem with the algorithm.

4.  The source code is in Pascal, not C.  Easily fixed by porting.  If anyone
does this before I do, please send me a copy.

I wish I had the resources to offer a cash reward, but I don't.  On the other
hand,

If you break the MPJ encryption algorithm and post your solution, then you
will have the satisfaction of having beaten me in an intellectual game.

If no one succeeds in breaking the MPJ encryption algorithm after reasonable
effort has been applied, then there will be a secure, royalty free,
unpatented block cipher available for use in the USA.  (Where else would math
be patented?)

                                             -- Mike Johnson (mpj@csn.org)

This message contains speech and writings protected by the First Amendment of
the Constitution of the United States of America.