Cryptography-Digest Digest #832, Volume #10 Mon, 3 Jan 00 16:13:01 EST
Contents:
Re: "Variable size" hash algorithm? (Boris Kazak)
Re: On documentation of algorithms (Mok-Kong Shen)
Re: meet-in-the-middle attack for triple DES (Mok-Kong Shen)
Re: Bits 1 to 3 (Re: question about primes) ("Tony T. Warnock")
----------------------------------------------------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: "Variable size" hash algorithm?
Date: Mon, 03 Jan 2000 12:18:28 -0800
Reply-To: [EMAIL PROTECTED]
"Peter K. Boucher" wrote:
>
> Why not have your program measure the entropy of the input, then use the
> input as an RC4 key, then use the RC4 PRNG to output as many bytes as
> can be justified by the entropy in the input?
=============================
This is the reply to original poster
[EMAIL PROTECTED] (Dan Day)
Organization:
Frontier GlobalCenter Inc.
*******************
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 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.
Now about the "twists". The first 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 2*HASHBLOCKSIZE.
For each block, there are three repetitions of two rounds
each (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 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 second twist was 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.
Since modular multiplication is a one-to-one transformation,
there is no way to find a different single 320-bit block which
would be transformed to the same value. A single bit change in
the original 320-bit block will produce unpredictable avalanche
changes after 2 rounds.
However, after we process the second block, there is a
possibility to take this 320-bit value, reverse transform it
via our modular multiplication with the multiplicative inverse,
take an arbitrary 320-bit value, XOR it with the buffer, again
reverse transform the result with the multiplicative inverse,
and thus obtain two bogus blocks which will together hash to
the same value as two blocks of original message. This is
really a direct way to produce collisions.
This is why I introduced the "accumulator". The intermediate
results of the multiplicative transformation are now not left
alone in the text buffer, but accumulated (via XOR-ing) in this
dedicated 320-bit container. The process goes like this:
A[k]= A[k-1]^M(t[k])^M(M(t[k]))^M(M(M(t[k])))
(2 rnds) (2 rnds) (2 rnds)
where M is the 2-round multiplicative transformation of the text
block, A[k-1] is the previous content of the accumulator (usually
A[0] = 0), A[k] is the new content, after the k-th text block is
processed.
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 multiplicative 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.
Naturally, 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 (128 or
even 256 bits), or just give up, which I hope will
precisely happen.
After 3 repetitions of 2 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 3x2 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 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
#define ROUNDS 2
#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 Scramble (void) /* This subroutine scrambles the "text" block */
/* It uses the global variables */
/* text[], accumulator[] and inbuffer[] */
{
int k,m,n;
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 (n=0; n<3; n++) /* Outer rounds -for one-wayness */
{
for (m=0; m<ROUNDS; m++) /* Inner rounds - for avalanche */
{
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 */
temp1 = (temp2 << 24) ; /* is identical to MakeH2
function */
temp2 = text[(k+1) % (2*HASHBLOCKSIZE)] ; /* However, it is
impossible to use */
temp1 += (temp2 << 16) ; /* MakeH2 function
directly, because */
temp2 = text[(k+2) % (2*HASHBLOCKSIZE)] ; /* the loop index must be
wrapped */
temp1 += (temp2 << 8) ; /* mod 2*HASHBLOCKSIZE */
temp1 += text[(k+3) % (2*HASHBLOCKSIZE)] ;
/* Get the modular product into "temp1" */
MUL(temp1, SEED);
/* 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) ;
}
}
/* XOR-ing intermediate results into accumulator */
for (m=0; m < 2*HASHBLOCKSIZE; m++) accumulator[m] ^= text[m];
}
} /* 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 and
outbuffer*/
for (k=0; k<2*HASHBLOCKSIZE; k++)
{
text[k]=0;
accumulator[k]=0 ;
}
for (k=0; k<HASHBLOCKSIZE; k++) outbuffer[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] =
outbuffer[k]^accumulator[k]^accumulator[k+HASHBLOCKSIZE];
for (k=0; k<HASHBLOCKSIZE; k++)
{
write_char_to_file(outbuffer[k],out);
}
fclose(in); fclose(out);
}
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On documentation of algorithms
Date: Mon, 03 Jan 2000 21:56:18 +0100
John E. Gwyn wrote:
>
> wtshaw wrote:
> > As Einstein said,"If you can't explain it to a child, you
> > don't understand enough yourself."
>
> That's not quite what he said, but anyway it is an oversimplification.
> Not even the most intelligent 10-year-old child is going to understand
> anything that abstracts far beyond his experience or that is
> inherently complex. Try explaining ultrafilters, C*-algebras, K
> theory, elliptic curves, etc. to a child sometime.
The citation may not be exact, in particular wrpt the word 'child',
I suppose. But certainly such sentences are to be understood analogous
to the common 'proverbs'. In fact, I think Einstein almost surely
wouldn't have expected that the majority of the adults would
be capable to well comprehend his general theory through books
written either by himself or by others.
A tiny side remark I like to add to my original post is that I
personally find it particularly frustrating in studying algorithms
(crypto or not) of others when I encounter certain 'magic'
constants, i.e. numbers whose origin/derivation/merit is nowhere
explained. On such occassions I often can't help having the same
sort of feeling as when I am looking at some ultra-modern masterpieces
of art (wonderful, but what's that??).
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: meet-in-the-middle attack for triple DES
Date: Mon, 03 Jan 2000 21:58:09 +0100
DJohn37050 wrote:
>
> There are unique keys per transaction for PIN protection keys. This idea has
> been known. A problem with it is the set up time, changing the key all the
> time means normal performance speed ups are not possible.
Many thanks for the comment. My humble opinion however is that in
most occasions of life certain tradeoffs always have to be taken.
We have to pay something for better security. My personal standpoint
on matters of performance might in fact be much biased due to my
comparatively early contact with computers. (I ran my first program in
1959 on a German made Z22.) It is perhaps understandable that I tend
to entertain certain 'doubts' about the 'necessity' of the ever more
intensive quests for higher computing speed, posing myself questions
like 'if three years ago we have lived very well with an application
on computer X, why must we unconditionally demand that the program
runs very much faster, now that X has been replaced with the more
powerful Y?'. I believe that at least for a certain wide category of
crypto applications, namely where the security requirement is fairly
high and the messages are destined for some non-instantaneous human
decision processes (e.g. highly confidential materials for top
managers as against orders to trigger military missiles), the message
transmission speed of today could well tolerate some substantial
amount of degradation without causing any negative effects. Well,
as said, this might be because I have not thrown away the 'ballast'
of the past from my own brain in order to be able to think entirely
in modern ways.
M. K. Shen
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Bits 1 to 3 (Re: question about primes)
Date: Mon, 03 Jan 2000 13:54:41 -0700
Reply-To: [EMAIL PROTECTED]
"John E. Gwyn" wrote:
> "Tony T. Warnock" wrote:
> > According to Dirichlet's theorem, the density of primes in arithmetic
> > progression is the same for all progressions with the same step size.
> > Thus the density of primes ending in 1,3,7,9 (base ten) is the same.
>
> I am unable to decipher that. "The same" as what? Surely, not as
> each other: 0,2,4,6,8 vs. 1,3,5,7,9 is a counterexample. 1,3,7,9
> final digits aren't an arithmetic progression. ???
Sorry I didn't explain better. The density of primes ending in 1 is the
same as the density ending in 3 which is the same as that of those ending
in 7 and is the same as that of those ending in 9. The arithmetic
progressions in question are 10n+1, 10n+3, 10n+7, 10n+9. The link I posted
should explain everything.
------------------------------
** 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
******************************
