Re: IPG - newest release of the ABC Encryption Algorithms (fwd)

>IPG Sales wrote:
>> Obviously, you meet our requirements for the release of the IPG ABC
>> Encryption algorithms. We need no further information from you. though we
>> would appreciate your telephone num and snail mail address.
>

At 08:01 AM 3/19/96 -0600, Mike McNally wrote in reply:
>On the other hand, the "algorithm" as presented is so hopelessly 
>obfuscated by the strange terminology and loose descriptions used
>to present it that there's no way I (or anybody else) could seriously
>evaluate it.  Either publish an algorithm in some accepted format
>(a real C program, or even Knuth notation) or cut back your expectations
>for public analysis.
>

IMPORTANT: I have nothing to do with IPG and I don't endorse their stuff,
I got the same mail and produced the code below to help me figure out
what they are doing. 
                        John

Here is my take on a C version of their code - note that a[] b[] c[] and the
initial d are filled in from the 'one time pad'.  The size of a,b,c is not
specified it could be 8 16 or 32 bits from the text ...  However the initial
values of a,b & c are set using 8 bits of the 'random' key.

int a[64]  /* Random & 0x3500 */
int b[64]  /* Randomly selected primes */
int c[64]  /* randomly selected primes*/
char d;     /* random start value */
int i;

/* the arrays b,c are filled in from tables of smallish primes supplied
by IPG using 'random' numbers supplied by IPG to select the primes (and the
order of same).  since all the values are > 8 bits I've assumed a,b,c = int. 
a[] is filled with 13568 + an 8 bit 'random' number.  (13568 = 0x3500 which
gets ANDed with the seed value)
*/

while(1)
{
        for(i=0; i<64;i++)
        {
                a[i] = (a[i] + b[i]) % c[i];
                d = (d+a[i]) & 0xFF;
                /* output d as next byte in stream */
                /* XOR with plaintext */
        }
}

I would not trust it without spending more time than I have
right now to look at it.  It arrived with the following text:

>The algorithms detailed below are copyrighted 1995 and 1996 by Internet 
>Privacy Guaranteed, Seymour, TX. All rights are reserved. You may not
>provide them to any other party, or parties, by any means or 
>any media, without the expressed written permission of Internet Privacy 
>Guaranteed.

I have not agreed to this, further I strongly suggest IPG add studying trade
secret and copyright law to their todo list.

I do not endorse the above code or algorithm and make no comment on it's
strength or otherwise.

On Tue, 19 Mar 1996, John Pettitt wrote:

my first gut reaction is that there looks like the scheme falls 
trivially to 64 bytes of known plaintext, but I didn't look at it closely.

Simon

---
They say in  online country             So which side are you on boys
There is no middle way                  Which side are you on
You'll either be a Usenet man           Which side are you on boys
Or a thug for the CDA                   Which side are you on?
  National Union of Computer Operatives; Hackers, local 37   APL-CPIO

John Pettitt wrote:
> /* the arrays b,c are filled in from tables of smallish primes supplied
> by IPG using 'random' numbers supplied by IPG to select the primes (and the
> order of same).  since all the values are > 8 bits I've assumed a,b,c = int.
> a[] is filled with 13568 + an 8 bit 'random' number.  (13568 = 0x3500 which
> gets ANDed with the seed value)
> */

One tangerine-flavord Starburst to the first cypherpunk who can give
a rough estimate for the results of the sub-expression:

	(random() & 0xff) & 0x3500


______c_____________________________________________________________________
Mike M Nally * Tiv^H^H^H IBM * Austin TX    * pain is inevitable  
       m5@tivoli.com * m101@io.com          *
      <URL:http://www.io.com/~m101>         * suffering is optional

Chris McAuliffe (cmca@alpha.c2.org) wrote:

: >One tangerine-flavord Starburst to the first cypherpunk who can give
: >a rough estimate for the results of the sub-expression:
: >	(random() & 0xff) & 0x3500
: 
: Well, actually, it depends on whether the bytes are treated as signed or
: unsigned, and we don't know for sure that IPG wanted them treated as
: unsigned. This means IPG either:
: 
: a) can't write portable code, or
: b) really are as stupid as we are giving them credit for.

a) is obvious, since they explicitly say that they coded it in 80x86 
assembler, but I wouldn't discount the possibility of b) being true also.

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

[To: Mike McNally <m5@tivoli.com>]
[cc: cypherpunks@toad.com]
[Subject: Re: IPG - newest release of the ABC Encryption Algorithms (fwd) ]
[In-reply-to: Your message of Tue, 19 Mar 96 13:40:33 CST.]
             <314F0DB1.61FE@tivoli.com> 

Mike McNally <m5@tivoli.com> Scribed:
>John Pettitt wrote:
>> /* the arrays b,c are filled in from tables of smallish primes supplied
>> by IPG using 'random' numbers supplied by IPG to select the primes (and the
>> order of same).  since all the values are > 8 bits I've assumed a,b,c = int
 .
>> a[] is filled with 13568 + an 8 bit 'random' number.  (13568 = 0x3500 which
>> gets ANDed with the seed value)
>> */

>One tangerine-flavord Starburst to the first cypherpunk who can give
>a rough estimate for the results of the sub-expression:
>	(random() & 0xff) & 0x3500

Well, actually, it depends on whether the bytes are treated as signed or
unsigned, and we don't know for sure that IPG wanted them treated as
unsigned. This means IPG either:

a) can't write portable code, or
b) really are as stupid as we are giving them credit for.

(I'm miffed at being left out of the game... sniff...)

Chris

Chris McAuliffe <cmca@alpha.c2.org> (No, not that one.)

-----BEGIN PGP SIGNATURE-----
Version: 2.6

iQCVAwUBMU86OoHskC9sh/+lAQExRQQAs97CBv/HdJwqarKVIZeVOr49xqLjeqbT
RHaaFb1otqh0iH0twRcyqXoaDfTeSyZZZK/pPCWHqiWmPME8NoVzQY9hW86GxKKO
8bxfDjKL6VH2By08fpGxNqBVLUuqNX19rNpreZtcDTxU5ttD8Rz9vA/654opjPDt
2UToOsmNMcw=
=t1pT
-----END PGP SIGNATURE-----

> >IPG Sales wrote:
> >> Obviously, you meet our requirements for the release of the IPG ABC ...

> At 08:01 AM 3/19/96 -0600, Mike McNally wrote in reply:
> >On the other hand, the "algorithm" as presented is so hopelessly 
> >obfuscated by the strange terminology and loose descriptions used ...

John Pettitt presents us with C code possibily matching the algorithm
(see the end of this email).

I imagine that John Pettitt may have written:

> I do not endorse the above code or algorithm and make no comment on it's
> strength or otherwise.

Well I spent 30 seconds on it. Do we get to start with known plain text?
This is the usual assumption these days. It so hopeless I imagine more
experienced cryptographers won't even bother replying.

DON'T USE THIS CODE.

It has a long cycle: (the product of all the c[i]) * 64

It can be broken into 64 parts and each part attacked separately.
Each part is the outputs with offset i modulo 64. Part i has a cycle
of c[i]. (Its irrelevant that the b[i] are prime, helps if they are
coprime to c[i].) There is no feedback between parts.

Each part looks like a LCM PRNG to me. The cryptanalysis of these was
done decades ago by Knuth. From memory the key can be deduced in a
known plain text attack with knownledge of about the same amount of
plain text as there is unknown key (initial state). (under 1K bytes).

Even without known plain text I suspect it would not survive past the
maximum c[i] (given some redundancy in the input).

I imagine that John Pettitt may have written:

> Here is my take on a C version of their code - note that a[] b[] c[] and the
> initial d are filled in from the 'one time pad'.  The size of a,b,c is not
> specified it could be 8 16 or 32 bits from the text ...  However the initial
> values of a,b & c are set using 8 bits of the 'random' key.
> 
> int a[64]  /* Random & 0x3500 */
> int b[64]  /* Randomly selected primes */
> int c[64]  /* randomly selected primes*/
> char d;     /* random start value */
> int i;
> 
> /* the arrays b,c are filled in from tables of smallish primes supplied
> by IPG using 'random' numbers supplied by IPG to select the primes (and the
> order of same).  since all the values are > 8 bits I've assumed a,b,c = int. 
> a[] is filled with 13568 + an 8 bit 'random' number.  (13568 = 0x3500 which
> gets ANDed with the seed value)
> */
> 
> while(1)
> {
>         for(i=0; i<64;i++)
>         {
>                 a[i] = (a[i] + b[i]) % c[i];
>                 d = (d+a[i]) & 0xFF;
>                 /* output d as next byte in stream */
>                 /* XOR with plaintext */
>         }
> }

-- 
Munro Saunders    Often seen at Gracelands, but ...     P.O. Box 192,
munro@ci.com.au   I am not an official spokesperson     ERSKINEVILLE 2043
61 2 564 6368     for Elvis, IBM, M$ or Corinthian.     AUSTRALIA