From: C Matthew Curtin <cmcurtin@research.megasoft.com>
Date: Tue, 3 Sep 1996 05:53:48 +0800
To: Alex Walker <survival@aa.net>
Subject: Pseudocrypto detector is going wild (was: Re: ALPHACIPHER - An unbreakable encryption program.)
In-Reply-To: <01bb94a6.44902540$8adc9dcc@survival>
Message-ID: <864tlgivwo.fsf@goffette.research.megasoft.com>
MIME-Version: 1.0
Content-Type: text/plain


The following message is a courtesy copy of an article
that has been posted as well.

-----BEGIN PGP SIGNED MESSAGE-----


"Alex  Walker" <survival@aa.net> writes:

> The strongest encryption system available to the public will be available
> soon at:
> http://www.aa.net/cyber-survival-hq
> 
> ALPHACIPHER has been in the making for the past ten years, and has come
> into its own
> with the proliferation of Internet communications. 
> 
> A demo of this program along with a FAQ can be downloaded from
> cyber-survival-hq 1SEP.  This is an unbreakable program...

Here we go again.

I just got done surfing the site above. Assuming that all statements
regarding the unbreakability of the cipher, the lack of applicability
of the question regarding its key size, etc., are at least based on
some degree of truth, "alphacipher" is a one-time pad. Given that
anything else is not really "unbreakable," if it's not a one-time pad,
the claims about its security are bogus.

But let's assume that it is.

In exchange for the great security of one-time pads, users of such
must be willing to tolerate their drawbacks, and there are some
significant ones.

    1 The unbreakability of the one-time pad is completely thrown out
      the window if the key is not _truly_ random. A software based
      pseudorandom number generator simply won't cut it; even the best
      PRNGs will have some degree of predicability. It is possible
      that these random keys are truly random (given point 2, below),
      but I find this to be unlikely, since the overview boasts that
      the keys are generated by a "proprietary random key set
      generator." Now, we're getting into *another* issue, and that is
      of the wisdom (or, more correctly, lack thereof) in using
      proprietary algorithms. Not only does this fail to ensure any
      higher level of security when compared to that of a well-known
      algorithm, but actually increases the liklihood that an error
      has gone undiscovered, since fewer experts have had the
      opportunity scrutinize it.

    2 The pool (or "pad") of random bits from which the keys are
      generated must be distributed ahead of time. Given this
      requirement, the "random bit pad" must be distributed with the
      program itself. In fact, the two "comm key disks" seem to be
      just this. A third "vault key" disk, used for local online
      storage, seems to be another random bit pad.

    3 Keys must stay perfectly in sync. A single bit-shift either way,
      and you're hosed. Given that there is a finite number of bits in
      the pad (as there must be, since they need to be precalculated
      and distributed with the program), that they all must stay
      perfectly in sync, and that the program appears to be marketed
      for widespread (albeit low-bandwidth) use, there must be some
      mechanism by which the encrypting program can tell the
      decrypting program how far along in the bit pad to advance
      before using them for the key. Otherwise, if I send a message to
      Alice, then I send one to Bob, Bob is going to use a different
      starting point in the pad for the key assembly than I did to
      create the message, unless he also received a copy of what I
      sent Alice, and every person before that. Giving an indication
      of the byte offset to use for decryption seems the only workable
      solution to this problem.

    4 The keysize must be exactly equal to the size of the plaintext
      to be encrypted.

    5 Bits from the pad that are used for key generation must never
      be used again. Ever. Since there are only two "comm key" disks,
      which must be the same for every distribution, you can get
      probably get somewhere between two and 10 million "random" bits
      on the disks, depending on whether you're using compression, and
      if so, what compression algorithm you're using. Let's assume
      that you've got 10 million bits on there. Since the encryption
      of one bit exhausts one bit from the pad, I can exhaust the
      entire supply by sending someone a 10MB mail message. Or two
      five MB mail messages, or 10 one MB messages. In any case, it
      doesn't take long. And as soon as I'm out, if I start over again
      at the beginning, I'm blowing the security, since I'm reusing
      keys.

    6 Anyone with access to the key pad can decrypt a message sent to
      anyone else, as long as they know the proper bit offset. Because
      of what I've described in item 3, it seems likely that I'll know
      that ahead of time. Hence, the security of the "alphacipher"
      encrypted messages decreases with each additional user that
      "alphacipher" gains.

So, it seems to me that I can break *any* message that anyone encrypts
with "alphacipher" by getting a copy of the comm key disks, figure out
how "alphacipher" calculates where in the pad to begin generating the
key, and apply the appropriate key to the encrypted message. Perhaps a
bit of additional obfuscation is occuring somewhere in there, but the
basic premise is that because of what it's trying to do, this has to
be a very poor implementation of a one-time pad, and therefore
completely vulnerable to passive attack.

(This is using the "comm key"; the "vault key" has much more
potential, since it can be unique for every user, but it can still be
exhausted very quickly, and therefore have a successful cryptanalysis
made of that data, using other means: a larger amount of data will be
necessary to reconstruct the bit pad before any messages can be
broken, but once again, after it's constructed, anything encrypted
using that bit pad can be broken. And, since it seems unlikely that
we're dealing with REAL random numbers here, this probably isn't
nearly as tough as it ought to be.)

I have absolutely no knowledge of "alphacipher" beyond what is
contained in the original posting I saw on alt.security which pointed
me to the web page (http://www.aa.net/cyber-survival-hq/Alpha1.htm)
but it seems that I've made a decent (albeit trivial) analysis of its
weakness, and at least given serious raise to your ability to make
such claims about its security.

If I'm wrong, please show me how so. If not, please do us all a favor
and quit with the advertising claims.

(All I need now is someone to threaten to sue me, and I'll maintain my
record of having lawsuit threats made against me every time I
criticize something that claims to be "strong crypto.")

- -- 
C Matthew Curtin                MEGASOFT, INC                Chief Scientist
I speak only for myself.  Don't whine to anyone but me about anything I say.
Hacker Security Firewall Crypto PGP Privacy Unix Perl Java Internet Intranet
cmcurtin@research.megasoft.com http://research.megasoft.com/people/cmcurtin/

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: Have you encrypted your data today?

iQEVAwUBMisu2X6R34u/f3zNAQFKSgf/T/cB0X33sDGHoiqVfbXZcW9VEFBcbtVA
bTjFLEKrh89pEeZ8VR7FsZRkbC5C7ceuy1aoTAK+RLdaOBZN8AkOTWXvo139gVW/
9P+gv8eitZlhWzSnXfpURp45m737wjRfgsP7drgWZr3AdGCu3XOipIyy3tcJrcGY
fPBpBZXvAfdmxX5B3CiRgLFOdhVxzhyO7Cv019ybRTCYjZncPEyyXIYMzrCJkyBi
QbZzcsvgwTq+vD0Cw9/REVqxH6Av3tzJacLLgo33hO1cvti9910FcTSCIdnmR+E+
Pse2Gm0nx8Ochcfw2ZmEVtJI7hXkLbOXMq7i/i++jtMSeMVrIsfXUg==
=ZbJf
-----END PGP SIGNATURE-----