Cryptography-Digest Digest #330, Volume #9 Fri, 2 Apr 99 22:13:03 EST
Contents:
Re: FSE information anyone? (John Savard)
A simple hash function. (Boris Kazak)
Re: Random Walk (R. Knauer)
Re: Announce - ScramDisk v2.02h ([EMAIL PROTECTED])
quick RSA key generation question (Fritz J Schneider)
Re: Announce - ScramDisk v2.02h (Boris Kazak)
Re: Announce - ScramDisk v2.02h (Rebus777)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: FSE information anyone?
Date: Thu, 01 Apr 1999 20:45:16 GMT
Thirteen <[EMAIL PROTECTED]> wrote, in part:
>First on the agenda
>is a very impressive paper by David Wagner, a student at Berkeley,
>and a participant in sci.crypt. The Boomerang attack is a new
>form of differential cryptanalysis in which work is done on half
>of the rounds. The cipher is broken in half, like a meet in the
>middle attack. David showed a 3 dimensional diagram like a cube
>cut in half with the 4 top corners being 4 plaintexts and the 4
>bottom corners being 4 ciphertexts. 2 plaintexts are found with
>differential characteristics that have "the right differences".
>The resulting ciphertexts then are used to construct 2 more
>ciphertexts with "the right differences". Then decryption
>follows the reverse path through the cube into the middle,
>where conveniently, algebraic symbols are manipulated to cancel
>out some "stuff". The key is found by trying numerous keys to
>construct the cube that has the right differences. It takes
>much less work than an exhaustive search. The Digest of Technical
>Papers does not have the cube drawing, and the Digest is not
>available to most people. I hope that this humble description
>has provided some enlightenment, and that David Wagner will
>expand upon or correct this summary.
There's some stuff at
http://www.dmi.ens.fr/users/vaudenay/dec_feedback.html
John Savard (teneerf is spelled backwards)
http://members.xoom.com/quadibloc/index.html
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: A simple hash function.
Date: Fri, 02 Apr 1999 15:49:06 -0500
Reply-To: [EMAIL PROTECTED]
One more hash function? But there are already enough
of these around, why bother?
Well, maybe just to give people a choice...
"...hash-functions have...characteristics...:
1. Given M, it is easy to compute h.
2. Given h, it is hard to compute M such
that H(M)=h.
3. Given M, it is hard to find another
message M' such that H(M)=H(M')."
(Schneier, Appl.Crypt. p.429)
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.
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.
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 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".
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.
This code is placed in the public domain.
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);
}
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Sat, 03 Apr 1999 01:33:03 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 02 Apr 1999 21:32:04 GMT, Dave Knapp <[EMAIL PROTECTED]> wrote:
> As a physicist, I am constantly
>appalled by the lack of statistical knowledge of my peers. I certainly
>don't consider myself an expert at statistics, but I seem to know it a
>lot better than most physicists.
What is YOUR model for true randomness, the one which gives you a
level of confidence that is reasonably certain to reject a TRNG
process as not truly random?
Curious minds want to know.
Bob Knauer
"First, it was not a strip bar, it was an erotic club. And second,
what can I say? I'm a night owl. Anyway the bitch set me up."
- Marion Barry, Mayor of Washington DC
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.security.pgp
Subject: Re: Announce - ScramDisk v2.02h
Date: Fri, 02 Apr 1999 21:46:15 GMT
Reply-To: [EMAIL PROTECTED]
=====BEGIN PGP SIGNED MESSAGE=====
On Fri, 02 Apr 1999 16:11:22 GMT, Liberty<[EMAIL PROTECTED]>
wrote:
>> To be honest, I sometimes wonder
>> why I bothered.....
>
>I don't know why you bothered either. I'm just
>grateful you did.
>Thanks,
Me too! And let me add my thanks.
Chris Ward.
=====BEGIN PGP SIGNATURE=====
Version: PGP 5.5.3i
iQCVAwUBNwUPDcoHR8g+vP61AQE2jAP/U5BLPAQ/BZj4I7GsSivWTQv8BXYMrGRt
SSUb2swRZDgMp58KaqJVP0vnQb6nsEIaiU2Ijfnh2uBMuSgpaXtRT1CITdlAxin8
+CA8aBTTir1TC4gcMbxPOywj2A9rKcju6bixg49IiSVOhcH9PvJVPNd/GqKJXde1
CIQTaySFSSg=
=0yUj
=====END PGP SIGNATURE=====
------------------------------
From: Fritz J Schneider <[EMAIL PROTECTED]>
Subject: quick RSA key generation question
Date: Fri, 2 Apr 1999 21:30:26 -0500
Reply-To: Fritz J Schneider <[EMAIL PROTECTED]>
After generating a random p and q, is it standard practice to set
the MSB of both p and q to 1 to ensure large values?
=-----------------------------------+-------------------------------------=
Fritz Schneider / [EMAIL PROTECTED] | For PGP Public Key finger me here:
Columbia University Engineering | "schneider,fritz"@cunix.cc.columbia.edu
=-----------------------------------+-------------------------------------=
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: Announce - ScramDisk v2.02h
Date: Fri, 02 Apr 1999 18:37:41 -0500
Reply-To: [EMAIL PROTECTED]
Terry Ritter wrote:
>
> >The point of that section of the document was that an adversary is not aware
> >of which algorithm you use....They have no method of detecting whether TEA,
> >Blowfish, IDEA, 3DES etc is used. Both PGPDisk & Bestcrypt plainly state the
> >algorithm employed.
> >
> >So, to "brute force" a ScramDisk container an adversary has to effectively
> >try all 10 ciphers, whereas to brute force other products containers they
> >only have to try 1 cipher. Is this snake oil? No.
> /...../
> 2. The big advantage of having a huge number of ciphers is the burden
> it places on any Opponent, who necessarily must keep up. Opponents
> must distinguish each cipher, obtain it, break it, then construct
> software and perhaps even hardware to automate the process. Given a
> continuous production of large numbers of new ciphers, I believe that
> "keeping up" must have a terrible cost that not even a country can
> afford.
====================
And how about a "variable" cipher? The one which philosophy will
be based on
1. a *big* number of key-derived S-boxes
2. a plaintext-dependent sequence of invocation
for these S-boxes.
In case where there will be enough plaintext-dependent variability,
no two plaintexts will be encrypted along the same sequence. This
will be essentially equivalent to adding the plaintext space and the
key space together. With all the additional effort for the attacker.
=======================
>
> 3. The risk of using a single popular cipher (no matter how
> extensively analyzed) is that a vast amount of information is
> protected by one cipher. This makes that cipher a special target -- a
> contest with a payoff far beyond the games we normally play. I think
> we want to avoid using such a cipher.
>
> 4. To make the cost of multiple ciphers real, we cannot keep using
> the same cipher, but instead must use different (new) ciphers
> periodically. We will want to use the same cipher-system, so our
> system must support "clip-in" modules for ciphers which have not yet
> been written.
========================
A long overdue problem - standard cipher-to-application interface.
========================
> 5. One of the facts of ciphering life is that we cannot prove the
> strength of any cipher. Even NIST review and group-cryptanalysis does
> not give us proven strength in a cipher, so any cipher we select might
> be already broken, and we would not know. We cannot change this, but
> we can greatly improve our odds as a user, by multi-ciphering under
> different ciphers. Doing this means an Opponent must break *all* of
> those ciphers -- not just one -- to expose our data. I like the idea
> of having three layers of different cipher, each with its own key.
>
========================
Have a little pity for the export bureaucrats! They are kind enough
to allow exporting three different ciphers, and now you want to use
their kindness to show all the world that their export regulations
can be circumvented and that they are not worth the paper they are
printed on.
> ----------------------
> Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
> Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Best wishes BNK
------------------------------
From: [EMAIL PROTECTED] (Rebus777)
Subject: Re: Announce - ScramDisk v2.02h
Date: 3 Apr 1999 03:10:46 GMT
>
>To be honest, I sometimes wonder why I bothered.....
>
>Aman.
Because everyone out here isn't a prick...
Thanks! for the great program!!!
RSC
------------------------------
** 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
******************************
