Cryptography-Digest Digest #310, Volume #12 Sat, 29 Jul 00 04:13:01 EDT
Contents:
Hash function? (tweaked) (Boris Kazak)
Re: Proving continued possession of a file ([EMAIL PROTECTED])
Re: IDEA Encryption (Boris Kazak)
Re: Elliptic Curves encryption (Greg)
Re: Elliptic Curves encryption (Greg)
Re: Elliptic Curves encryption (Greg)
Re: A naive question (Boris Kazak)
Bluetooth security source code (Tome')
Re: generating S-boxes (Terry Ritter)
----------------------------------------------------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Hash function? (tweaked)
Date: Sat, 29 Jul 2000 06:46:51 GMT
Boris Kazak wrote:
>
> those who know me have no need of my name wrote:
> > are you really a worldnet customer? if so you can have a web site, if
> > you wish -- see http://home.att.net/ for more information.
> > --
> > okay, have a sig then
> ----------------------------
> No particular reasons, just plain laziness from my part
> (and I can write HTML and Javascript... it would be easy).
>
> I hope to awaken some day. BNK
==================================
To the judgement of sci.crypt posters and readers...
Here is the proposal for a very simple hash function -
scalable, fast, byte-oriented.
(name = "Karagash", see Note 3 below)
Everything starts with an array of bytes. The size of array
is equal to the size of future hash, and is named _buffer_.
Array is initialized either with user's key, or, barring
that, with consecutive bytes 1,2,3...
There is a _magic_ 16-bit constant called SEED, equal to
0xB7E1 hex, which happens to be first 4 hex digits of e,
less initial 2.
Core procedure.
A byte is read from the hashed message (file) into some
temporary variable.
Then follow 3 rounds of a rather simple procedure:
{
The said byte is XORed into the 0-th element of _buffer_.
Thereafter the 16-bit number, built from the 0-th and
1-st elements of _buffer_, is multiplied by SEED,
yielding a 32-bit product.
The 4 bytes of the product are XORed into the first 4
elements of _buffer_ (Big-endian architecture assumed).
Thereafter _buffer_ is rotated left 1 byte.
}
Following that, a new byte is read from the file,
and the 3-round hashing procedure is performed with the
newly acquired byte.
After the EOF there are 8 more bytes to be hashed - the
length of the file as 64-bit number. These 8 bytes are
also hashed exactly the same way as the main body of the
file - 3 rounds each one.
Finally, the buffer undergoes one more full cycle of
multiplications-rotates, in order for the full avalanche
to happen. The final hash is in the _buffer_.
Hash function Pseudocode:
/********************/
// variables
unsigned int32 product;
unsigned int16 SEED = 0xB7E1; //first 4 hex digits of e, less initial 2
unsigned int16 multiplicand,i;
unsigned byte BUFFER[HASHSIZE]; // whatever the HASHSIZE is #defined
unsigned byte temp, prod[4];
// BUFFER initialize
for (0 to HASHSIZE-1)
BUFFER(i) = i+1; // writing in there consecutive numbers.
// Alternatively, BUFFER can be initialized with user's key
// Hashing
//Before EOF
WHILE (temp = (READBYTE(InputFile)) != EndOfFile)
{
FOR(1 to 3) // 3 rounds
{
BUFFER[0] = BUFFER[0]^temp; // XORing the byte
multiplicand = 256*BUFFER[0]+BUFFER[1]; //16-bit
product = multiplicand*SEED; //32-bit
split _product_ into 4 bytes from prod[0] to prod[3];
FOR (k = 0 to 3) BUFFER[k] ^= prod[k]
//Assume big-endian architecture.
Rotate BUFFER to the left 1 position;
//This implies BUFFER[HASHSIZE-1]=BUFFER[0],
//BUFFER[0]=BUFFER[1], BUFFER[1]=BUFFER[2], etc.
NEXT round
}
Read new byte; Repeat;
} // Total number of rounds here = 3*HASHSIZE
//After EOF
//File length must be determined in
//process of reading, the above procedure is
//repeated 8 more times, hashing in the consecutive
//bytes of file length (64-bit number assumed,
//big-endian architecture assumed)
//Total number of rounds here = 24
//Thereafter, the final squashing
FOR (0 to HASHSIZE-1)
{
multiplicand = 256*BUFFER[0]+BUFFER[1];
product = multiplicand*SEED;
split product into 4 bytes from prod[0] to prod[3];
XOR product bytes into BUFFER according to indices;
Rotate BUFFER to the left 1 position;
NEXT multiplication
}
//This is the same procedure as above, without
//reading new bytes, repeated for 1 full cycle
//in order to provide full avalanche.
//Final hash is contained in the BUFFER.
*******************************
Note 1. The previous version of this program was defeated by
Scott Fluhrer in an elegant attack. He succeeded in finding
2 files which were hashing to the same value.
His attack was based on finding pairs of bytes which
produced the same MSB after multiplication, and used the fact
that each byte of the message was XORed into the buffer
and multiplied exactly once.
Repeating the XOR and multiplication 3 times
defeats this attack, because it is highly improbable that
one can find a pair of bytes yielding the same MSB after
multiplication with 3 different random numbers. In fact,
the probability of such an event can be estimated as being
close to 1/512. Practically this means that any effort to
maintain difference = 0 in the buffer will fail immediately.
Note 2. Following this text there is a C program which can be
compiled by any ANSI C compiler and will be able to run under
DOS. The program takes its input from a file and writes the
resulting hash to another file. The program is heavily loaded
with printouts, actually this is a debugging version.
There was an option not to do any physical _rotates_ of the
buffer in memory, sliding instead the indexes cyclically
(mod HASHSIZE). I decided against this option, mainly because
it obscures the program machinery without giving any sizeable
speed or code benefits.
Note 3. Scott Fluhrer named the first version of the program
"Kazakhash", just because he felt that it should have some
name. Going along with this reasonong, I would like this
program in future be called "Karagash", which is just a crude
alliteration of words "character" and "hash". In my view,
it fits the byte-oriented nature of the program.
Any feedback will be appreciated.
Best wishes BNK
/********************** Karagash.c ***************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef unsigned char byte;
typedef unsigned int word16;
typedef unsigned long word32;
#define HASHSIZE 16
#define SEED 0xB7E1 // 4 hex digits of e
/* variables */
word32 message_length; /* size of input file */
int end_of_file;
byte outbuffer[HASHSIZE];
/*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 */
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 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 (void)
{
byte read_byte, temp, prod[4];
byte buffer[HASHSIZE];
byte msg[8]; // here will be the 64-bit message_length
word16 i, j, k, n, multiplicand;
word32 product;
FILE *in,*out;
char infile[100], outfile[100], *dot;
/* 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++='s'; /* Changing file extension */
*dot++='h'; *dot='\0'; /* to .hsh */
if ((out=fopen(outfile,"w+b"))==NULL)
{
printf("\nError opening output file: %s\n",outfile);
exit(-1);
}
printf("\nOutput file is: %s\n",outfile);
message_length = 0;
i=0;
/* Clearing buffer */
for (n=0; n<HASHSIZE; n++) buffer[n]=(byte)(n+1); //initialize buffer
/********************************************/
/* Here begins the main procedure */
/********************************************/
while(1) /* exit this loop on End of File */
{
read_byte = (byte)read_char_from_file(in);
if (end_of_file == 1) break;
for (j=0; j<3; j++) // 3 rounds
{
buffer[0] ^= read_byte;
multiplicand=256*(word16)buffer[0]+(word16)buffer[1];
product=(word32)multiplicand*(word32)SEED;
printf("\n Prod = %08lX ",product);
prod[3]= (byte)( product &0x000000FF);
prod[2]= (byte)((product >> 8)&0x000000FF);
prod[1]= (byte)((product >> 16)&0x000000FF);
prod[0]= (byte)((product >> 24)&0x000000FF);
printf (" Buf = ");
for (k=0; k<HASHSIZE; k++) printf ("%02x ",buffer[k]);
for (k=0; k<4; k++) buffer[k] ^= prod[k];
temp = buffer[0];
for (k=1; k<HASHSIZE; k++) buffer[k-1] =buffer[k];
buffer[HASHSIZE-1] = temp;
}
}
printf ("\n Hashing in length");
msg[0]=0; msg[1]=0; msg[2]=0; msg[3]=0;
msg[4]=0; msg[5]=0; msg[6]=0; msg[7]=45; //length of message
for (i=0; i<8; i++) //length loop
{
for (j=0; j<3; j++) // 3 rounds
{
buffer[0] ^= msg[i];
multiplicand=256*(word16)buffer[0]+(word16)buffer[1];
product=(word32)multiplicand*(word32)SEED;
printf("\n Prod = %08lX ",product);
prod[3]= (byte)( product &0x000000FF);
prod[2]= (byte)((product >> 8)&0x000000FF);
prod[1]= (byte)((product >> 16)&0x000000FF);
prod[0]= (byte)((product >> 24)&0x000000FF);
printf (" Buf = ");
for (k=0; k<HASHSIZE; k++) printf ("%02x ",buffer[k]);
for (k=0; k<4; k++) buffer[k] ^= prod[k];
temp = buffer[0];
for (k=1; k<HASHSIZE; k++) buffer[k-1] =buffer[k];
buffer[HASHSIZE-1] = temp;
}
}
printf ("\n Final round");
for (i=0; i<HASHSIZE; i++) //final round
{
// buffer[0] ^= msg[i]; // This is not needed here
multiplicand=256*(word16)buffer[0]+(word16)buffer[1];
product=(word32)multiplicand*(word32)SEED;
printf("\n Prod = %08lX ",product);
prod[3]= (byte)( product &0x000000FF);
prod[2]= (byte)((product >> 8)&0x000000FF);
prod[1]= (byte)((product >> 16)&0x000000FF);
prod[0]= (byte)((product >> 24)&0x000000FF);
printf (" Buf = ");
for (k=0; k<HASHSIZE; k++) printf ("%02x ",buffer[k]);
for (k=0; k<4; k++) buffer[k] ^= prod[k];
temp = buffer[0];
for (k=1; k<HASHSIZE; k++) buffer[k-1] =buffer[k];
buffer[HASHSIZE-1] = temp;
}
/*******************************************/
/* Hash is ready, write output buffer */
/*******************************************/
for (k=0; k<HASHSIZE; k++) outbuffer[k] = buffer[(3*i+k)%HASHSIZE];
printf("\n\n HASH = ");
for (k=0; k<HASHSIZE; k++) printf ("%02x ",outbuffer[k]);
/***********************/
/* Write output file */
/***********************/
for (k=0; k<HASHSIZE; k++) write_char_to_file(outbuffer[k],out);
fclose(in); fclose(out);
}
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Proving continued possession of a file
Date: Sat, 29 Jul 2000 06:51:06 GMT
I've found an algorithm that lets Bob post non-interactive
proofs that he has a certain message M. For example,
Alice and Bob might sign a contract that required Bob to
hold a backup file for her. He would have to prove to the
world once a day that he still had M. The proof should be
short and non-interactive, even if the message M is terabytes
long. Anyone should be able to read the proof, and verify
that Bob isn't cheating, but still has the file. The
algorithm here is too slow, but it may be secure.
Initially Alice has the file M, and generates:
s = 10 (use higher numbers for more security)
p, q = randomly chosen primes
n = p * q
a = M^(-s) mod (p-1)(q-1)
Alice publishes a signed file containing:
s, n, a
Alice and Bob's names, and the filename for M
Alice can then forget everything, including M.
Now, each day Bob must post a short file that can be
combined with Alice's published file to prove he still
has M. On any given day, Bob generates:
r = secure hash of the concatenation of last night's
closing prices for the first 10 stocks
listed alphabetically on the New York Stock
Exchange.
Bob then publishes the date and the single
number b:
b = r^(M^s) mod n
= (...(((r^M)^M)^M)...^M) mod n
If Victor wants to verify Bob's claim today, he
first calculates r for the published date, then
he verifies that:
(b ^ a mod n) == r
If they are equal, then Bob must have had a copy
of the file M sometime between market close on the
listed date and the present.
The work that Bob must do is proportional to s.
The work that Alice and Victor must do is very
small, and is independent of s. If s is too
small, then Bob will be able to cheat. s=10
should be safe.
LCB
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: IDEA Encryption
Date: Sat, 29 Jul 2000 07:13:26 GMT
Joseph Ashwood wrote:
>
> I will go on record right now as stating that IDEA is not
> the strongest cipher, that crown belongs to One Time Pad
> (which don't even bother attacking it offers absolute data
> confidentiality).
>
> As to where to find out about IDEA:
> (from http://www.r3.ch/o_files/products/idea/)
> Patents
>
> The international patent application is published with
> number WO 91/18459 dated Nov. 28, 1991. The US patent number
> is 5 214 703 with date of May 25, 1993. The European patent
> number is EP 0 482 154 B1 with date of June 30, 1993. The
> Japanese patent is pending.
>
> And you can get the source code from:
> http://www.r3.ch/o_files/products/idea/download.html
>
> As to what I'd consider more difficult to cryptanalyse, the
> short list is:
> MARS, RC5, RC6, Twofish, Rijndael, 3DES, Serpent,
> Blowfish......
>
> Enjoy, if you make significant headway against any of them
> (with the exception of 3DES, where you will have to reduce
> it below about 2^112) you will gain instant recognition in
> the crypto community. Of course I'd say that almost everyone
> on this group is looking at at least one of the list
> thinking that maybe, just maybe, they can find an attack (I
> personally chose RC5, and RC6).
> Joe
>
> "George" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > I'm new to this group, but I have read Applied Crypt. by
> Mr. Schneier. I was
> > wanting to if there was a site I could go to that has a
> good cryptanalisysm
> > of IDEA encryption. I have been told it is the strongest
> cipher to break,
> > and I have been wanting to give it a shot myself. Please
> let me know where I
> > can find some information. I look forward to contributing
> my new ideas here
> > and interacting with other users that take an interest in
> the field of
> > crypto. :)
> > --
> > -George
> > [EMAIL PROTECTED]
> >
=======================
Try <http://rpini.com> and browse their Crypto CD online.
There you will find many source codes of encryption
programs (IDEA included). May be you will end up ordering
a copy for yourself.
Best wishes BNK
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Elliptic Curves encryption
Date: Sat, 29 Jul 2000 07:09:32 GMT
In article <8kjgu6$g8g$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
> Nicol So <[EMAIL PROTECTED]> wrote:
> > Does applying for access automatically sign you up for their mailing
> > list?
>
> I think the thing is that one way of obtaining the password is to
> sign up for the mailing list. Then they send it to you in
> the confirmation message.
>
> It was a cute password, too. at least last time I looked.
MarsRoks or something like that and it is case sensitive.
--
Craig: Well what will you do?
William: I will invade England and defeat the English on their own
ground.
Craig: Invade? That's impossible.
William: Why? Why is that impossible? You're so concerned with
squabbling for the scraps from Longshank's table that
you've missed your God-given right to something better.
There is a difference between us.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Elliptic Curves encryption
Date: Sat, 29 Jul 2000 07:13:42 GMT
> Well, there are plenty of ideas, but a remarkable lack of proof.
But it does make you feel all fuzzy warm all over, doesn't it?
I sort of believe in the open system that allows everyone who is
interested in ECC to look at ways of breaking it. I think there
are plenty of math experts out there who would try too.
But I think that you could prove for any symmetric key cipher
that there is no math proof of invulnerability. In fact, if
I am correct (please tell me if you think I am not), only the
TOTP has a proof of invulnerability. While that may not be
true for the practical OTP, no other cipher can say that about
its theoritical counter part.
--
Craig: Well what will you do?
William: I will invade England and defeat the English on their own
ground.
Craig: Invade? That's impossible.
William: Why? Why is that impossible? You're so concerned with
squabbling for the scraps from Longshank's table that
you've missed your God-given right to something better.
There is a difference between us.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Elliptic Curves encryption
Date: Sat, 29 Jul 2000 07:16:45 GMT
> >I was expecting a comment from you on this. <G>
>
> Thank you. It's a shame more people are not so vigilant. This ever
> creeping belief of strength is more dangerous to cryptography than
> actual bad ciphers.
No, bad implementations on an OS platform are far worse
than any cipher can be. A strong cipher is no good on Windows NT
when using CryptAPI because a virus can easily insert itself
between the cipher and the app and see and transmit the plain
text (for example).
At that point, you only have to ask yourself, Why bother with a strong
anything?
--
Craig: Well what will you do?
William: I will invade England and defeat the English on their own
ground.
Craig: Invade? That's impossible.
William: Why? Why is that impossible? You're so concerned with
squabbling for the scraps from Longshank's table that
you've missed your God-given right to something better.
There is a difference between us.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: A naive question
Date: Sat, 29 Jul 2000 07:32:09 GMT
"Carl L. Distefano" wrote:
>
*************
> Ascii charset.
>
> Reaching back to high-school math, I calculated the number of possible
> encodings as a permutation of 256 chars taken 64 at a time, using the
> standard
> formula P(n,r) = n!/(n - r)! My calculator tells me that this amounts to
> some
> 2.416e+150 possible permutations, or 50 orders of magnitude more than a
> googol.
> --------------
> Carl Distefano
> [EMAIL PROTECTED]
> http://www.serve.com/xywwweb/
=================================
To give you an easily understandable analogy, why this calculation
does not work.
Imagine that you have 6 locks and 6 keys: one key for each lock.
The number of permutations is 6! = 720.
However, you find the first key in 5 tries,
the second key in 4 tries (from remaining)
the third key in 3 tries
the fourth kry in 2 tries
the fifth key in 1 try
the sixth key without any tries
Total: 15 tries maximum!!
You tell me, are keys and letters so different?
Best wishes BNK
------------------------------
From: [EMAIL PROTECTED] (Tome')
Subject: Bluetooth security source code
Date: Sat, 29 Jul 2000 07:38:27 GMT
I'm looking for source code of Bluetooth. In particular i'm interested
in encryption algorithm and authentication algorithm.
Can someone help me ?
Tome'
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: generating S-boxes
Date: Sat, 29 Jul 2000 07:45:37 GMT
On Sat, 29 Jul 2000 17:02:58 +0100, in
<[EMAIL PROTECTED]>, in sci.crypt David Hopwood
<[EMAIL PROTECTED]> wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>Tom Anderson wrote:
>> On 28 Jul 2000, Mack wrote:
>> > >i was wondering about how one generates S-boxes.
>[...]
>> > The three usual criteria are the SAC,
>>
>> if a and b differ by 1 bit, S(a) and S(b) differ by, on average, half
>> their bits. do we care more about the actual average (ie 3.9 bits is good,
>> 2.4 is bad) or the deviation from the average (3.9+/-2.1 is bad, 2.4+/-0.2
>> is good)? or both? should this be weighted with some nonlinear function,
>> so that 2.4 is more better than 2.3 than 3.9 is better than 3.8?
>
>What we want is that the distribution of differences between S(a) and S(b)
>is as expected for a random function. IIRC it should be a binomial
>distribution - Terry Ritter's site has some information on this.
>
>Perhaps you could define a metric for the "goodness" (or more precisely
>"badness") of an S-box with respect to the SAC, based on the results of a
>statistical test of whether the output differences are consistent with the
>expected distribution, for some set of small input differences.
What I have done for SAC is to first construct a key value at random,
then a data block value also at random, encipher the block, and save
the resulting ciphertext block. Then I change each plaintext bit, one
at a time, enciphering each time, and then count the number of bits
different from the saved block. For each possible number of bit
differences, I accumulate a count.
I collect data for a number of different blocks for each key, and for
a number of different keys.
Now I have a distribution of occurrences over bit-difference counts.
This should be binomial, and we can compare the experimental
distribution to the expected distribution. I will always collect the
data multiple times.
We certainly can get a pristine and precise (for what that is worth)
percentile value by using a statistical distribution comparison like
chi-square, but I am a great believer in the human eye actually seeing
the distribution. I think we should avoid trying to compress the
experimental data unduly, because the distribution speaks to us. By
producing a single statistic value, we may muffle the very data we
wish to understand. The result, often, is a single Boolean value
{good, bad} which, of course, also has a distribution, but one that
may take huge numbers of trials to resolve. Even a chi-square
percentage result has a distribution that should be resolved before
experimentation is finished. Just looking at the data is often
better.
I should say, though, that I rarely find problems with this sort of
bit-change testing. The Boolean function nonlinearity test seems to
be far more rigorous.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
** 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
******************************
