Cryptography-Digest Digest #401, Volume #11 Thu, 23 Mar 00 13:13:01 EST
Contents:
Re: Hashes! (newbie question) (Boris Kazak)
Re: ecc equation (Bob Silverman)
Re: Prime numbers? (newbie alert) ([EMAIL PROTECTED])
Maybe he has a solution ([EMAIL PROTECTED])
Re: ecc equation (Mike Rosing)
----------------------------------------------------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Hashes! (newbie question)
Date: Thu, 23 Mar 2000 17:38:54 GMT
Mark Wooding wrote:
>
> Runu Knips <[EMAIL PROTECTED]> wrote:
>
> > AFAIK SHA-1 and RIPE MD160 are the algorithms which are
> > considered secure at the moment. RIPE MD160 has been called
> > "secure for the next 10 years" by its inventors in the
> > original paper from April 1996, therefore we have time
> > until the end of 2005 :-) then we need something better.
>
> Indeed. Both can provide at most 80-bits-worth of security against an
> adversary attempting to find collisions. For SHA, this is fine, since
> 80 bits fits in nicely with the 80-bit strength of other similar
> algorithms designed by the NSA for government use, such as Skipjack and
> DSA[1].
>
> I suspect that we need good fast hash functions with at least 256-bit
> outputs right now, to go with the good 128-bit block ciphers we already
> have and the public-key algorithms we use. I don't think there can be
> much argument that the hash is the weak bit in most digital signature
> algorithms at the moment. Even Eli Biham and Ross Anderson's Tiger, at
> 192 bits, doesn't seem to offer commensurate security.
>
> Is it that attention hasn't been focussed on designing sufficiently
> large hashes, or are they actually really difficult? Or am I way off
> here and worrying about nothing?
> *****************
> -- [mdw]
=============================
Try this, it is scalable, 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. The size of the hash and
segments is #defined by the HASHBLOCKSIZE constant and can
be altered according to need. For example, if the final hash
will be 160 bit, the segments will be 320 bit each.
This proposed function is based on multiplication
(mod 2^32+1) with some "twists". The function uses one single
modular multiplier which in the program is #defined as
"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.
In all subsequent description I shall refer to the
M-transformation, which is now going to be described.
All multiplications are assumed to be (mod 2^32+1).
The specifics of the M-transformation 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 2*HASHBLOCKSIZE.
For each block, there are three rounds of multiplicative
M-transformation (for those paranoid among us, there is a
#define, where one can change the ROUNDS constant to whatever
desired).
Graphically a round of M-transformation can be visualized
in the following sketch:
( the index is circular mod 2*HASHBLOCKSIZE )
___________________________________________________________
1-st multiplication
XXXXxxxxxxxxxxxxxxxxxxxxxxxxxxxx
( XXXX - 32-bit number to multiply)
___________________________________________________________
2-nd multiplication
ppPPXXxxxxxxxxxxxxxxxxxxxxxxxxxx
(ppPP - product of the first multiplication,
PPXX - 32-bit number to multiply)
___________________________________________________________
3-d multiplication
ppppPPXXxxxxxxxxxxxxxxxxxxxxxxxx
( PPXX - 32-bit number to multiply)
...........................................................
Last multiplication
XXppppppppppppppppppppppppppppPP
( The index is cyclically wrapped over -
PPXX - 32-bit number to multiply)
___________________________________________________________
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.
The following improvements were introduced later, after
Paul Onions pointed out that it is possible to easily produce
collisions if each subsequent text block is simply XOR-ed
into the text buffer without any further precautions.
In all the discussion below I shall assume the 320-bit
block and 160-bit hash, just for example.
In order to discourage attacks based on reverse computation
of the intermediate results of the multiplicative M-transformation
these intermediate results are now not left alone in the text
buffer, but accumulated (via XOR-ing) in a dedicated 320-bit
container "accumulator".
Now the attack against the intermediate result does not work,
because one must obtain 3 numbers 320-bit each which must be:
1) the 3 consecutive results of M-transformation and
2) at the same time must XOR together to some predetermined number.
In case of 2 numbers it is academically possible to satisfy these
requirements with ~2^160 effort (birthday paradox), in case of 3
numbers the problem seems unfeasible.
However, even with this arrangement more subtle attacks are
possible, exploiting the fact that results of XOR-ing are
independent of the order in which the subsequent numbers arrive
into the accumulator.
Essentially stops against the block-swapping exist
at two levels - at the level of text buffer and at the level of
accumulator.
As it happens, there is a 32-bit unsigned integer
variable "message_length", where the count of all bytes read
from the message file is kept. Since at any moment it is the
current count, its value is N = (k+1)*2*HASHBLOCKSIZE, and
it is possible to use this variable in the hash computation.
The improved procedure boils down to XOR-ing the current
count into the text buffer before each consecutive
M-transformation, this strongly discourages any attempts to
swap the blocks in the message. The avalanche
properties of 3 consecutive M-transforms are at 100%, so
any 1-bit difference in the count or in the blocks will
produce changes all over the text buffer and accumulator.
The second line of defense goes in the accumulator
itself. After the 3 consecutive XOR-ings from the text
buffer the accumulator is subjected to 1 pass of
multiplicative M-transformation. Since M and XOR do not
commute, this amendment also prohibits swapping the blocks
or changing the order of their arrival into accumulator.
With this arrangement it became possible not to add
a special "message_length" block at the end of program.
The correct length of the message is automatically XOR-ed
into the last processed block (3 times!).
Finally, it is the accumulator whose halves are XOR-ed
together to obtain the final hash.
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 (160 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 content of the text buffer
obtained in 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 (the paddng 0-s are NOT included into the
total byte count of the message). The final operation XOR-s the
two halves of the accumulator, producing the output hash value.
Initially the text 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 text 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 /* minimum is 4, recommended 10 and above */
#define ROUNDS 3
#define SEED 0x6A09E667UL /* Modular Multiplier seed */
/* First 8 hex digits of SQRT(2), less initial 1 */
/* variables */
word32 message_length; /* size of input file */
int end_of_file;
byte inbuffer[2*HASHBLOCKSIZE], outbuffer[HASHBLOCKSIZE];
byte text[2*HASHBLOCKSIZE], accumulator[2*HASHBLOCKSIZE];
/*file handling functions*/
char read_char_from_file(FILE *fp);
void write_char_to_file(char data,FILE *fp);
void hash_file(FILE *in);
/******************************************************/
/* 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 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 M_transform (byte *buffer) /* This subroutine makes 1 pass of */
/* Modular Multiplication transform */
/* over the "buffer" */
{
int k;
word32 temp1, temp2;
for (k=0; k<2*HASHBLOCKSIZE; k+= 2)
{
/* Build a 32-bit multiplicand */
/* We want this to produce same results on big-endian
*/
/* and little-endian machines alike */
temp2 = *(buffer+(k % (2*HASHBLOCKSIZE))) ; /* Essentially this
procedure */
temp1 = (temp2 << 24) ; /* is identical to MakeH2
function */
temp2 = *(buffer+((k+1) % (2*HASHBLOCKSIZE))) ; /* However, it is
impossible to use */
temp1 += (temp2 << 16) ; /* MakeH2 function
directly, because */
temp2 = *(buffer+((k+2) % (2*HASHBLOCKSIZE))) ; /* the loop index
must be wrapped */
temp1 += (temp2 << 8) ; /* mod 2*HASHBLOCKSIZE */
temp1 += *(buffer+((k+3) % (2*HASHBLOCKSIZE))) ;
/* Get the modular product into "temp1" */
MUL(temp1, SEED);
/* Return the bytes where they belong */
*(buffer+(k % (2*HASHBLOCKSIZE))) = (byte)((temp1 & 0xff000000UL)
>> 24) ;
*(buffer+((k+1) % (2*HASHBLOCKSIZE))) = (byte)((temp1 & 0x00ff0000UL)
>> 16) ;
*(buffer+((k+2) % (2*HASHBLOCKSIZE))) = (byte)((temp1 & 0x0000ff00UL)
>> 8) ;
*(buffer+((k+3) % (2*HASHBLOCKSIZE))) = (byte) (temp1 & 0x000000ffUL)
;
}
} /* M_transform */
/******************************************************/
void Scramble (void) /* This subroutine scrambles the "text" block */
/* It uses the global variables */
/* text[], accumulator[] and inbuffer[] */
{
int m,n;
/* XOR-ing the input into the text array */
for (m=0; m < 2*HASHBLOCKSIZE; m++) text[m] ^= inbuffer[m];
/* Building the current byte count - to prevent block swaps */
for (m=0; m<8; m++) inbuffer[m]=0;
DissH1(message_length, (inbuffer+4));
for (m=8; m<2*HASHBLOCKSIZE; m++) inbuffer[m]=0;
/* Now we can start squashing the block */
for (n=0; n<ROUNDS; n++) /* ROUNDS -for one-wayness */
{
/* XOR-ing the byte count into the text array, then */
/* squashing text and XOR-ing intermediate results into accumulator */
for (m=0; m < 2*HASHBLOCKSIZE; m++) text[m] ^= inbuffer[m];
M_transform (text);
for (m=0; m < 2*HASHBLOCKSIZE; m++) accumulator[m] ^= text[m];
}
M_transform (accumulator); /* squashing accumulator */
} /* 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);
/* Clearing text buffer, accumulator, outbuffer, message_length */
for (k=0; k<2*HASHBLOCKSIZE; k++)
{
text[k]=0;
accumulator[k]=0 ;
}
for (k=0; k<HASHBLOCKSIZE; k++) outbuffer[k]=0;
message_length = 0;
/* Reading and squashing the input file */
while(end_of_file != 1)
{
read_block_from_file(in);
Scramble();
}
/* Building and writing the final hash */
for (k=0; k<HASHBLOCKSIZE; k++)
outbuffer[k] = accumulator[k]^accumulator[k+HASHBLOCKSIZE];
for (k=0; k<HASHBLOCKSIZE; k++)
{
write_char_to_file(outbuffer[k],out);
}
fclose(in); fclose(out);
}
/************** Best wishes BNK *********/
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: ecc equation
Date: Thu, 23 Mar 2000 17:42:50 GMT
In article <8bdju7$6mo$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
> In article <HXnC4.63163$[EMAIL PROTECTED]>,
> "Tom St Denis" <[EMAIL PROTECTED]> wrote:
> >
> > Joseph Ashwood <[EMAIL PROTECTED]> wrote in message
> > news:e8ZJ7yJl$GA.154@cpmsnbbsa02...
> > > > Hmmm.... I wonder what elliptic curves over the complex
> > > plain could
> > > > do for crypto :-)
> > > Since there are multiple planes that could be called complex
> > > (my knowledge of the specific terminology in the realm is
> > > not even shaky, so pardon if this is mistake).
>
> May I suggest that if you don't have the knowledge to answer the
> question that you not try to answer???
>
> A Weirstrass curve over C would be (essentially) useless.
> Why? Because if you extend the field over which you are working
> to ALL of C, then the field in which you work contains all the roots
> of the right hand side of the curve.
>
> OTOH, it is possible to use elliptic curves over a FINITE extension of
> Q (rather than its full closure) if the finite extension does NOT
> contain roots of the cubic.
Allow me to expand this explanation a bit.
A group is generally useful for cypto purposes only when it is finite.
If you take an EC over a field containing a root of the cubic you
get an infinite Mordell group (unless the group has rank 0, but then
it will be too small to be cryptographically useful; the torsion part
of the Mordell group is quite small). This is also true for *any*
global field. EC's over Q are not terribly useful for cryptography
because the Mordell group is infinite (if rank != 0)
You can however, start with a curve defined over (say) Q(alpha) where
alpha is the root of some integer, and *then* restrict that curve to
lie over a finite field, provided that the root of the integer lies
in the Mordell group. This essentially means that if one uses
Q(d^1/h) where h is an integer then d^1/h must exist in the group.
This restricts h to divide the order of the group. Thus, all one is
really doing when one starts with Q(alpha) then localizes the curve
over a finite field is to place a restriction on the order of group.
I'm not sure why one would want to do this.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Prime numbers? (newbie alert)
Date: Thu, 23 Mar 2000 17:40:20 GMT
In article <
[EMAIL PROTECTED]>,
proton <[EMAIL PROTECTED]> wrote:
>
> Would a prime number instead of an ordinary number
> be better for creating randomness?
>
> Would they be better to use for keys/seeds when XOR'ing
> streams?
>
> I've also understood how the RSA algorithm works
> as its explained in the crypto faq. But I still dont
> understand *why* it works, and if prime numbers are
> required for it to work...
>
> And to those who immediately thinks I should go buy
> a book: I cant afford books at the the moment..
>
> Heh, one final warning too. My math skills arent all
> that good. I barely understood the short RSA description
> in the crypto faq and managed to verify it on my own
> (with alittle bit of help from `bc' =))
>
> /proton
>
Here is an easy and good intro to the RSA
algorithm and its basis (modular arithmetic).
This paper explains what you need to know and
is intended for those with no previous
knowledge of the subject:
http://arxiv.org/abs/cs/9903001
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Maybe he has a solution
Date: Thu, 23 Mar 2000 17:42:03 GMT
> sounds rediculous to everyone here, but if you contact me, I need
help to
> develop the technology. You can decide then if I am a quack!
> Email me at [EMAIL PROTECTED] for more information. A non-disclosure
> agreement will be required of any parties involved in the project.
I've just read Richard's solution.
To stop all the bad feelings in this list, I can say that his
proposed solutions is quite elegant.
I will not discuss the inner workings here (Richard, I will discuss
this in private with you, just send me a strong PGP public key), but he
is right when he says that he cannot write down the algorithm. You will
know why after reading it.
I'm a professional programmer, graduated in Computer Science,
working at a data security company and I really know what I'm talking
about. So, I can say openly in this list that before anyone start
laughing at Mr. Hein (I don't have any affiliation with him and didn't
heard of him before yesterday), it should be better to know of what he
is talking about.
Mr. Hein's proposed solution is not magic, is not an untold
revolution. It is a very inventive and creative solution for the
problem. This guy, who thought about it, maybe isn't the discoverer of
the wonderful factoring algorithm that humankind is waiting. But he is
indeed sincere, far from the labels that people in this list put him,
and he deserves respect.
Now I'm standing for his defense because some day I or anyone here
could be in his position. So let's stop unproductive talk.
Daniel.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: ecc equation
Date: Thu, 23 Mar 2000 12:00:32 -0600
Bob Silverman wrote:
> A Weirstrass curve over C would be (essentially) useless.
> Why? Because if you extend the field over which you are working
> to ALL of C, then the field in which you work contains all the roots
> of the right hand side of the curve.
How does access to all the roots of the cubic make solving the
log problem easier?
> OTOH, it is possible to use elliptic curves over a FINITE extension of
> Q (rather than its full closure) if the finite extension does NOT
> contain roots of the cubic.
For the rest of you guys, Q is the symbol for rational numbers,
which means any number which can be written as a fraction of 2
integers. An extension is a set of polynomials, and finite means
the maximum power is limited. And then I'm back to the first question.
Patience, persistence, truth,
Dr. mike
------------------------------
** 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
******************************
