From: Steven L Baur <steve@miranova.com>
Date: Wed, 2 Oct 1996 11:56:15 +0800
To: cypherpunks@toad.com
Subject: Re: Anonymous: Re: Phoenix News
In-Reply-To: <199610010137.VAA23410@jekyll.piermont.com>
Message-ID: <m2raniutwl.fsf@deanna.miranova.com>
MIME-Version: 1.0
Content-Type: text/plain


>>>>> "Ralph" == Donald ``Ralph'' Wood writes to Perry Metzger:

Ralph> I do not object to criticism,  when I am wrong, but I do
Ralph> object to using just highly subjective opinions to attack me,
Ralph> or anyone for that matter.

The same Ralph of IPG who offered an unbreakable system or they would
sell the company for $1?

		     [Repost from March 19, 1996]
Return-Path: owner-cypherpunks@toad.com
Received: from relay3.UU.NET (relay3.UU.NET [192.48.96.8]) by deanna.miranova.com (8.7.3/8.6.9) with ESMTP id TAA01777 for <steve@miranova.com>; Tue, 19 Mar 1996 19:52:42 -0800
Received: from toad.com by relay3.UU.NET with SMTP 
	id QQahuk09205; Tue, 19 Mar 1996 22:31:17 -0500 (EST)
Received: by toad.com id AA29880; Tue, 19 Mar 96 09:32:18 PST
Received: from pangaea.hypereality.co.uk by toad.com id AA29874; Tue, 19 Mar 96 09:32:09 PST
Received: (from remail@localhost) by pangaea.hypereality.co.uk (8.6.9/8.6.9)
	id RAA17262 for cypherpunks@toad.com; Tue, 19 Mar 1996 17:32:47 GMT
	Hypereality Systems : <WWW: http://www.hypereality.co.uk/>
Date: Tue, 19 Mar 1996 17:32:47 GMT
Message-Id: <199603191732.RAA17262@pangaea.hypereality.co.uk>
To: cypherpunks@toad.com
From: cpunk@remail.ecafe.org (ECafe Anonymous Remailer)
Subject: IPG cracked with known plaintext
Remailed-By: ECafe Anonymous Remailer
Complaints-To: complaints@remail.ecafe.org
X-Www: http://www.ecafe.org/~remail/
X-Notice: The contents of this message are neither appoved or
X-Notice: condoned by ecafe.org or our host Hypereality Systems.
X-Notice: We bear no liability for misuse of this system.
X-Warn: *** This message was remailed through an anonymous remailer ***
X-Warn:  *** Replying to it will not send your reply to the sender ***
Sender: owner-cypherpunks@toad.com
Precedence: bulk
Lines: 77
Xref: deanna.miranova.com cypherpunks:199

This information is preliminary and is based on an attempt to
understand the IPG algorithm information.  That description is not
clear in some areas, however, hence this analysis is tentative at this
time.

First let us describe the IPG system in more conventional C:

a[0] to a[63] are initialized to random 8-bit values.  (The
description is unclear and almost makes it sound like they are
initialized to a random 8-bit value anded with 0x3500, which would of
course be zero.  The attack below will assume that this bizarre step
is not done, but will still apply even if it is.)

b[0] to b[63] are initialized to random primes selected from some
pool.  c[0] to c[63] are also initialized to random primes selected
from a different pool.

d is initialized to a random 8 bit value.

The algorithm is:

    for ( ; ; ) {
	for (i=0; i<63; i++) {
	    a[i] = (a[i] + b[i]) % c[i];
	    d = (d + a[i]) & 255;
	    *data++ ^= d;		/* xor with data */
	}
    }


Note first that with a known plaintext attack, the value of d can be
calculated for each iteration, simply by xor'ing the plaintext and
ciphertext.  So we can easily recover a series of d values under this
assumption.  Known plaintext is a plausible cryptographic assumption
in many contexts.

Note second that we can assume that b[i] is less than c[i].  It
appears from the description that this will be true, although it is a
little unclear.  If b[i] is greater than c[i] then simply do
b[i] = b[i] % c[i] before beginning the loop.  This will produce the
same results since (a + (b mod c)) mod c is equal to (a + b) mod c.

Note third that when a[i] and b[i], both less than c[i], are added mod
c[i], the result will be equal to one of two things: a[i]+b[i], or
a[i]+b[i]-c[i].  The reason is that the sum a[i]+b[i] must be less
than 2*c[i] so the "mod" operation will be at most a single
subtraction of c[i].  In general, half the time it will be necessary
to subtract c[i], and half the time it will not.

Now, as mentioned above, with known plaintext we can deduce the series
of d values.  Since each d differs from its predecessor by adding
a[i], this allows us to calculate the low 8 bits of a[i] simply by
taking the difference between successive d's.

Every 64 bytes, i repeats.  We know the low byte of a[i] from the
previous iteration, and we know it for this iteration.  Half of the
time (on average) a[i] will change simply by adding b[i], in which
case the low 8 bits will change by exactly the low 8 bits of b[i].  So
if we take the difference between a[i] values spaced 64 bytes apart,
half of the time these values will be a constant which is equal to the
low byte of b[i].

The other half the time, the low 8 bits will change by adding b[i] and
subtracting c[i].  So the low 8 bits of (b[i]-c[i]) is the other
possible constant value which will be seen when you take the
difference of a[i] every 64 bytes.

So with a few multiples of 64 bytes of known plaintext, you will
quickly find all the possible b[i] and b[i]-c[i] low bytes. By itself
this should significantly narrow down the possibilities for b[i] and
c[i], in many cases to a single prime.  Even without this the
algorithm can now be run forward or backward with only two possible
known changes to a[i] at each step, and the entire message can be
easily deduced.

So this algorithm is easily broken with known plaintext.