Cryptography-Digest Digest #662, Volume #9 Sat, 5 Jun 99 01:13:04 EDT
Contents:
Re: Challenge to SCOTT19U.ZIP_GUY (SCOTT19U.ZIP_GUY)
Re: what cipher? (better description) (fungus)
Re: DES Effective Security Q (Nicol So)
Re: random numbers in ml ([EMAIL PROTECTED])
Re: random numbers in ml ("Douglas A. Gwyn")
Re: Finding a 192 bit hash (Was: Using symmetric encryption for hashing) (Boris
Kazak)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: Sat, 05 Jun 1999 03:03:00 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tim
Redburn) wrote:
>On Fri, 04 Jun 1999 20:24:05 GMT, [EMAIL PROTECTED]
>(SCOTT19U.ZIP_GUY) wrote:
>
>
>>
>> I have worked on many aircraft simulations and OFP;s one of the main
>>problems that seems to occur over and over is that other people keep
>>missing the obvious errors in the code becasue most people inheirently
>>put faith on the comments and this leads to major maistakes that take
>>years to find and fix.
>
>Quite the opposite. Comments tell you what the programmer intended.
>It is then easier then to verify that the code actually works
>as intended. If you don't know what the code was meant to do, how can
>you debug it ?
>
>
>- Tim.
Tim the newserver here has died several times. I think that when you
type a long message and I upload a long anwser it dies so if I don't
respond to one after a few days re send it back
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: what cipher? (better description)
Date: Sat, 05 Jun 1999 01:29:31 -0100
Particle wrote:
>
> > RC4 seem to an effective algorithm here, if high integrity is not needed
> > (RCA allows encrypted data to be undeterministicly modified at bit/byte
> > level without requiring decryption)
>
> Just read about RC4...
>
> ie: instead of having 256 values in the
> array, each from 0-256, I'll have 0xFFFF values each from
> 0-256... (seems to make it much stronger...)
>
Why "stronger"? Bigger isn't always better - a big table means that
values will sit still for much longer then with a small table - less
chaos.
> btw: how important to security that swap of values in the array,
> it would be nice if I could avoid it...
Very, very, very important.
> (that would mean I can
> seek to specific locations in the file without looping for a while
> to synch the array with the counter)
>
Nope. No can do.
Also, never, ever use the same key twice with RC4. If you want
to use the same password to encrypt several files then add some
random bytes to the end of it.
These don't have to be very random in the strict sense of the word.
The only reason you are doing this is to make the password unique
for each file.
eg. Use the time of day (four bytes) and the filename (some more
bytes) - this is almost certain to never come up twice the same.
See http://www.ciphersaber.com/ for more discussion of RC4.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: DES Effective Security Q
Date: Fri, 04 Jun 1999 23:15:28 -0400
Jim Gillogly wrote:
>
> karl malbrain wrote:
> >
> > DJohn37050 <[EMAIL PROTECTED]> wrote in message:
> > > I think it has been shown that using independent keys does NOT help, at
> > > least not much.
> >
> > This is completely counter-intuitive for a brute-force exposition of the
> > key. Can you provide a reference for this analysis??? Karl M
>
> Biham & Shamir (Differential Cryptanalysis of DES, Springer-Verlag 1993)
> show it's vulnerable to differential cryptanalysis with 2^61 chosen
> plaintexts. Not a very practical attack, but not the level of difficulty
> you want from a 56*16-bit key. See Schneier 2nd, p.295.
While I don't have any problem with the result of Biham and Shamir (that
independent subkeys increase the amount of chosen plaintexts needed for
differential cryptanalysis only by a very modest amount), I would not
interpet it as saying that independent subkeys don't help much.
In my opinion, differential cryptanalysis is not a practical attack
against DES, as the conditions necessary for its applicability seldom
occur in practice, if ever. To date, exhaustive search with fast,
parallel hardware seems to remain the most practical attack. Is there
an attack against DES that requires only a handful of known
plaintext-ciphertext pairs and 2^32 trial encryptions? I don't know. I
haven't heard of one but I can't rule out its existence either. Without
reliable knowledge of the best practical attack against DES there is, it
would be difficult or impossible to know the security implications of
independent subkeys.
(For the sake of argument, assume that the attack postulated above does
exist and it is the best practical attack there is. Further assume that
independent subkeys increase its complexity to 2^80 trial encryptions.
Under such assumptions, independent subkeys help *a lot*.)
Nicol
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.sys.cbm
Subject: Re: random numbers in ml
Date: 5 Jun 1999 03:21:45 GMT
Reply-To: [EMAIL PROTECTED] (Matthew Montchalin)
David Holz wrote:
>> but the case that we have here is when we're trying to convey an
>> algorithm that takes advantage of the carry states of the 6502. Can't
>> really do that in C, because the language has no concept of the carry
>> flag, unless you use another variable for it.
Jerry Coffin wrote:
>True, but at least when/if you do that, the rest of the people on
>sci.crypt can understand what's going on if they try.
Unless they prefer assembly language. Naturally, there are bound to be
some 'C' aficionados around, and a fair number of assembly language
aficionados around, too. Unless we exhaustively analyze the entire set of
readers of sci.crypt, how are we to conclude that 'C' is the preferred
language for talking about random number generators? (My vote is that we
supply additional source code for other microprocessors, too.)
>Ultimately, cross-posting between the two groups is probably not the best
>way to go;
Unless there are more people conversant with assembly language than you
think there are.
>there's probably no way to express the algorithm so it's particularly
>transparent to most participants in both newsgroups.
There are probably lots of ways to express the algorithm, regardless of
the choice of microprocessors. However, performance may vary between
microprocessors, and between implementations, too.
--
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: comp.sys.cbm
Subject: Re: random numbers in ml
Date: Sat, 05 Jun 1999 03:55:51 GMT
"White Flame (aka David Holz)" wrote:
> but the case that we have here is when we're trying to convey an algorithm that
> takes advantage of the carry states of the 6502. Can't really do that in C,
> because the language has no concept of the carry flag, unless you use another
> variable for it.
It is true that C does not entirely replace assembly language, and
its lack of access to the carry bit is a good example of that.
However, in many cases, reasonable results can be obtained by using
a wider type (so that the "carry" remains within the accessible
representation) and suitable bit operations.
I.e. the algorithm can be coded in C, but it may use methods that
are different from those that you would use in assembly language.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: Finding a 192 bit hash (Was: Using symmetric encryption for hashing)
Date: Fri, 04 Jun 1999 21:07:26 -0400
Reply-To: [EMAIL PROTECTED]
Thomas J. Boschloo wrote:
> (********)
> The experts in this group seem awefully silent, so I guess my questions
> are just too boring for them to reply to :-( But I did a websearch on
> '192' and 'hash' and found out that HAVAL can be run in 192 and 256
> mode! I guess that this answers my question if I ever get in the mood
> for writing a "K.I.S.S." public key crypto product (which uses and
> reveals as less info as possible).
>
> Regards & so long everybody,
> Thomas
> Email: boschloo_at_multiweb_dot_nl
========================
Try this, it reads a file, writes a file...
The program takes the filename from the simple dialog
and writes the hash into a new file with the name of the
original file and extension "h32".
Original message is divided into segments of the size
twice that of the final hash, e.g. if the final hash will
be 160 bit, the segments will be 320 bit each. The size of
the hash and segments is #defined by the HASHBLOCKSIZE
constant and can be altered according to need.
This proposed function is based on multiplication
(mod 2^32+1) with two "twists". First, however, some
background information.
The function uses 256 different modular multipliers
derived from one initial number "SEED". This number is
0x6A09E667, which happens to be the first 8 hex digits of
SQRT(2), less initial 1. The use of this number should
dispel any suspicions about a "trap door" built into SEED.
The multipliers themselves are simply the powers of SEED,
so that Mult[k] = SEED^(k+1), this way SEED^0 = 1 is
avoided, we don't want any trivial multipliers. Also, this
number produces a 33,502,080 long cycle of its powers
until it comes back to 1, so there are no duplicate
multipliers in the array.
The multiplier array can be precomputed in advance or
can be filled at the program start. The latter case saves
some code (no need for a big data table), but implies a
time penalty of 255 modular multiplications.
Now about the "twists". The first twist boils down to
the plaintext-dependent choice of the multiplier. If a
certain 4-byte number is going to be hashed, the
corresponding multiplier is chosen from the table with the
index I = XOR(all 4 bytes of the number).
Second twist regards the progression along the block.
After the multiplication, when the bytes of the product
are returned to their places and it is time to proceed
with the subsequent multiplication, the two LS bytes of
the previous product become the two MS bytes of the new
number to be multiplied, and two adjacent bytes of
the plaintext are appended to them in order to make this
new 32-bit number. When the end of the block is reached,
the index wraps cyclically over the BlockLength.
For each block, there are three rounds (for those
paranoid among us, there is a #define, where one can
change the ROUNDS constant to whatever desired).
Graphically a round can be visualized in the
following sketch:
( the index is circular mod "BlockLength" )
___________________________________________________________
1-st multiplication
XXXXxxxxxxxxxxxxxxxxxxxxxxxxxxxx
( XXXX - 32-bit number to multiply, multiplier
index is computed as X^X^X^X)
___________________________________________________________
2-nd multiplication
ppPPXXxxxxxxxxxxxxxxxxxxxxxxxxxx
(ppPP - product of the first multiplication,
PPXX - 32-bit number to multiply, multiplier
index is computed as P^P^X^X)
___________________________________________________________
3-d multiplication
ppppPPXXxxxxxxxxxxxxxxxxxxxxxxxx
( PPXX - 32-bit number to multiply, multiplier
index is computed as P^P^X^X)
...........................................................
Last multiplication
XXppppppppppppppppppppppppppppPP
( The index is cyclically wrapped over -
PPXX - 32-bit number to multiply, multiplier
index is computed as P^P^X^X)
___________________________________________________________
This arrangement allows an ultra-rapid propagation
of all changes across the entire block - there is complete
avalanche after the 2-nd round and then after each
subsequent round.
It should be also noted that this arrangement
effectively molds the entire hash into an inseparable
entity, where the junctions between the adjacent bytes and
words don't exist any more, they are all blurred by
overlapping and by cyclical wrapover of the index. This
strongly discourages any attacks based on different
behavior of the distinct bytes and words during hashing.
In this function the entire hash is just a circular
sequence of bits without beginning or end, without the
junctions between bytes or words, without any realistic
possibility to trace the output changes back to the changes
in any particular word or byte. The cryptanalyst would
either be forced to attack the hash as a whole (128 or
even 256 bits), or just give up, which I hope will
precisely happen.
After 3 rounds, the new subsequent block is read from
the message and XOR-ed with the hash obtained in the previous
cycles. Then the hashing procedure repeats again for 3
rounds, and so on until the last message block is read.
If the last message block is shorter than needed, it is
padded with 0-s. Thereafter one more block is added to the
hash, containing the full message length as a 64-bit binary
number padded with 0-s. The final operation XOR-s the two
halves of the hash buffer, producing the output hash value.
Since in each multiplication step the multiplicand is
replaced with the product, there is no practical way of
reconstructing the multiplier index (other than computing
multiplicative inverses for all 256 multipliers and testing
the product to find out the match for the index used,
however, the final XOR-ing defeats this option).
Initially the hash buffer contains either 0's or an
appropriate IV. No hashing is done on this value, the first
message block is just XOR-ed into the hash buffer.
If the secret key will be used as the IV, the function
will produce a MAC.
The source code was compiled under Borland C++ 4.52
and should compile under any ANSI-compliant C compiler.
The routines for breaking and making the 32-bit integers
from 4 bytes should assure identical results on both big-
endian and little-endian platforms (not tested).
No attempt has been made in order to optimize the
program in any way. After all, it is supposed to be just
a working model, not a racing car. One simple possible
optimization might reverse the direction of scanning
over the "text" block for little-endian Intel processors.
Any comments would be appreciated.
/********************* Start of code ************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define byte unsigned char
#define word16 unsigned int
#define word32 unsigned long int
#define LO 0x0000FFFFUL
#define HI 0xFFFF0000UL
#define HASHBLOCKSIZE 16
#define ROUNDS 3
#define SEED 0x6A09E667UL /* Modular Multiplier seed */
/* First 8 hex digits of SQRT(2), less initial 1 */
/* variables */
word32 mult[256]; /* multiplier array */
word32 message_length; /* size of input file */
int end_of_file;
byte inbuffer[2*HASHBLOCKSIZE], outbuffer[HASHBLOCKSIZE];
byte text[2*HASHBLOCKSIZE]; /* the working array */
/*file handling functions*/
char read_char_from_file(FILE *fp);
void read_block_from_file(FILE *fp);
void write_char_to_file(char data,FILE *fp);
/* Functions */
word32 Mul (word32 x, word32 y) /* Returns (x * y) mod
(2^32+1) */
/* For the purposes of this algorithm 0 =
2^32 */
/* Modular Multiplication "CORRECT BUT SLOW" (mod 2^32+1)
If your compiler does not handle the "double long"
integers (64 bit), you have to split the 32-bit words
into 16-bit halves, multiply them, then juggle the
intermediate products until you get the correct result.
*/
{
word32 t[4]; word16 u[2], v[2];
if (x == 0) return (1 - y);
if (y == 0) return (1 - x);
u[0] = (word16)(x & LO);
v[0] = (word16)(y & LO);
u[1] = (word16)((x >> 16) & LO);
v[1] = (word16)((y >> 16) & LO);
t[0] = (word32) u[0] * (word32) v[0] ;
t[1] = (word32) u[1] * (word32) v[0] ;
t[2] = (word32) u[0] * (word32) v[1] ;
t[3] = (word32) u[1] * (word32) v[1] ;
/* intermediate 32-bit products */
t[3] = t[3] + ((t[1] >> 16) & LO)
+ ((t[2] >> 16) & LO);
/* no overflow possible here */
t[1] = (t[1] & LO) + (t[2] & LO)
+ ((t[0] >> 16) & LO);
/* collect them all in t[1]. Overflow into the
17-th bit possible here */
t[0] = (t[0] & LO) + ((t[1] << 16) & HI);
t[3] = t[3] + ((t[1] >> 16) & LO); /* add eventual overflow */
return (t[0] - t[3] + (t[3] > t[0]));
} /* Mul */
#define MUL(x,y) (x=Mul(x,y))
void MultSetup (word32 *mul)
{
int k;
*mul = SEED; /* Initialize multiplier array */
for (k = 1; k < 256; k++)
{
*(mul+k) = *(mul+k-1); /* Copy next <- previous */
MUL (*(mul+k),SEED); /* Subsequent power */
}
} /* MultSetup */
void DissH1( word32 H, byte *D )
/*
Disassemble the given word32 into 4 bytes.
We want it to work on all kinds of machines,
Little-Endian or Big-Endian.
*/
{
word32 T ;
T = H ;
*D++ = (byte)((T & 0xff000000UL) >> 24) ;
*D++ = (byte)((T & 0x00ff0000UL) >> 16) ;
*D++ = (byte)((T & 0x0000ff00UL) >> 8) ;
*D = (byte) (T & 0x000000ffUL) ;
} /* DissH1 */
word32 MakeH1( byte *B )
/*
Assemble a word32 from the four bytes provided.
We want it to work on all kinds of machines,
Little-Endian or Big-Endian.
*/
{
word32 RetVal, temp ;
temp = *B++ ;
RetVal = (temp << 24) ;
temp = *B++ ;
RetVal += (temp << 16) ;
temp = *B++ ;
RetVal += (temp << 8) ;
RetVal += *B ;
return RetVal ;
} /* MakeH1 */
void Scramble (void) /* This subroutine scrambles the "text" block */
/* It uses the global variables */
/* mult[], text[] and inbuffer[] */
{
int i,k,m;
word32 temp1, temp2;
/* XOR-ing the input into the text array */
for (m=0; m < 2*HASHBLOCKSIZE; m++) text[m] ^= inbuffer[m];
/* Now we can start squashing the block */
for (m=0; m<ROUNDS; m++)
{
for (k=0; k<2*HASHBLOCKSIZE; k+= 2)
{
/* Build a 32-bit multiplicand and multiplier index */
/* We want this to produce same results on big-endian
*/
/* and little-endian machines alike */
temp2 = text[k % (2*HASHBLOCKSIZE)] ; /* Essentially this
procedure */
i = (int)temp2; /* is identical to MakeH2
function */
temp1 = (temp2 << 24) ; /* However, it is
impossible to use */
temp2 = text[(k+1)%(2*HASHBLOCKSIZE)] ; /* MakeH2 function
directly, because */
i ^= (int)temp2; /* the loop index must be
wrapped */
temp1 += (temp2 << 16) ; /* mod 2*HASHBLOCKSIZE, and
also the */
temp2 = text[(k+2) % (2*HASHBLOCKSIZE)] ; /* multiplier index is
computed, */
i ^= (int)temp2; /* which is not provided in
MakeH2 */
temp1 += (temp2 << 8) ;
temp1 += text[(k+3) % (2*HASHBLOCKSIZE)] ;
i ^= (int)temp2;
/* Get the modular product into "temp1" */
MUL(temp1, mult[i]);
/* Return the bytes where they belong */
text[k % (2*HASHBLOCKSIZE)] = (byte)((temp1 & 0xff000000UL) >>
24) ;
text[(k+1) % (2*HASHBLOCKSIZE)] = (byte)((temp1 & 0x00ff0000UL) >>
16) ;
text[(k+2) % (2*HASHBLOCKSIZE)] = (byte)((temp1 & 0x0000ff00UL) >>
8) ;
text[(k+3) % (2*HASHBLOCKSIZE)] = (byte) (temp1 & 0x000000ffUL) ;
}
}
} /* Scramble */
char read_char_from_file(FILE *fp)
{
char temp=0;
message_length++;
if ((fread(&temp,sizeof(char),1,fp))!=1)
{
end_of_file=1;
message_length--;
}
return (temp);
} /* read_char_from_file */
void read_block_from_file(FILE *fp)
{
int i;
for (i=0; i<2*HASHBLOCKSIZE; i++)
{
inbuffer[i]=read_char_from_file(fp);
}
} /* read_block_from_file */
void write_char_to_file(char data,FILE *fp)
{
if ((fwrite(&data,sizeof(char),1,fp))!=1)
{
printf("Fatal Error writing output file!!!\n");
exit(-1);
}
} /* write_char_to_file */
void main()
{
FILE *in,*out;
char infile[100], outfile[100], *dot;
int k;
/* Opening files */
printf("\nEnter input filename:");
gets(infile);
if ((in=fopen(infile,"r+b"))==NULL)
{
printf("\nError opening input file: %s\n",infile);
exit (-1);
}
strcpy(outfile,infile);
dot=strrchr(outfile,'.'); dot++;
*dot++='h'; *dot++='3'; /* Changing file extension */
*dot++='2'; *dot='\0'; /* to .h32 */
if ((out=fopen(outfile,"w+b"))==NULL)
{
printf("\nError opening output file: %s\n",outfile);
exit(-1);
}
printf("\nOutput file is: %s\n",outfile);
/* Setting up the multipliers */
MultSetup(mult);
/* Clearing the text buffer */
for (k=0; k<2*HASHBLOCKSIZE; k++) text[k]=0;
/* Reading and squashing the input file */
while(end_of_file != 1)
{
read_block_from_file(in);
Scramble();
}
/* Building up and squashing the final block */
for (k=0; k<4; k++) inbuffer[k]=0;
DissH1(message_length, (inbuffer+4));
for (k=8; k<2*HASHBLOCKSIZE; k++) inbuffer[k]=0;
Scramble();
/* Building and writing the final hash */
for (k=0; k<HASHBLOCKSIZE; k++)
outbuffer[k] = text[k]^text[k+HASHBLOCKSIZE];
for (k=0; k<HASHBLOCKSIZE; k++)
{
write_char_to_file(outbuffer[k],out);
}
fclose(in); fclose(out);
}
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
