🔒 Locked

Checksum algorithm.

Started by Nice Coder Apr 11, 2005 at 12:55 AM 17 replies 2.8k views

Original Post

101

Apr 11, 2005 at 12:55 AM

Ok, after looking at a few checksum algorithms, i had a look at making my own. j = binary 010101010..... and is 64 bits long and is unsigned. k = ~j and is 64 bits long and is unsigned m = 0110..... and is 64 bits long. Every iteration, you get one 32 bit chunk of the variable. (if there isn't 32 bits left, you just get what you have, then pad it with zero's). Call this i. Now, you get j, and you barrelshift it right by 16 bits. (making the two least significant bytes the two most significant bytes, and moving everything else down). You get k, and you ballelshift it left by 16 bits. (making the two most significant bytes, the two least significant bytes). You then set j as (j xor i) plus 1 And k as (k xor i) minus 1 you set m as m xor (j + k) then you do the same for the next iteration, ect. When your outputting, you output (k concatinated with l, multiplied by m) moduo 2^128 Which is a nice output function. How does it look? Do you see any major weaknesses. (please note that this is a non-cryptographic hash function, but i'm trying to make it as hard as possible to exploit the hash.) From, Nice coder

Author

101

Apr 11, 2005 at 1:59 AM

Problem with short strings: The major problem with single byte strings, is that the hash is very similar to its starting position.

To help, please change the following:
j = 4DC2EDDD015295B8 instead of 01010101010
k = D63792157DB78628 instead of 10101010101
m = 082211754618C8E8

Also, do the xor before the barrellshifts.

Edit: barrelshift by 19, instead of 16. It scrambles bits across nibble borders better.

From,
Nice coder

[Edited by - Nice Coder on April 11, 2005 3:59:35 AM]

216

Apr 11, 2005 at 2:47 AM

http://www.toolmaker.nl/downloads/md5.zip

Or use my pre-built MD5 function. Download that package, and then use this:

#include "MD5.h"string MD5(const string& PlainText){    MD5_CTX       Context;    unsigned char Digest[16];    char          HashValue[33];    HashValue[32] = 0;    MD5Init(&Context);    MD5Update(&Context, (unsigned char *)PlainText.c_str(), (unsigned int)PlainText.length());    MD5Final((unsigned char *) Digest, &Context);    // Copy the digest into the string    int Pos = 0;    for (int i = 0; i < 16; ++i)    {        sprintf(&HashValue[Pos], "%02x", Digest);        Pos += 2;    }    return (HashValue);}

You shouldn't have trouble porting it to char*.

Toolmaker

Author

101

Apr 11, 2005 at 3:07 AM

1. I like my hash function. (its probably secure. But i don't know yet.)

2. I already know of md5, and how to use it.

3. Can you find a nice flaw in my algorithm?

From,
Nice coder

Author

101

Apr 11, 2005 at 3:19 AM

codish code

int j = 4DC2EDDD015295B8 int k = D63792157DB78628 int m = 082211754618C8E8for(int i = 0; i < n; input = inputarr[i++];) {j ^= input;k ^= input;j = (j >> 8) | (j << 45); //Barrelshift jk = (k << 8) | (k >> 45); //Barrelshift km ^= (int64)(j + k) //Make m}Return (int128)(((k << 64) | j) * m); //Output is 192 bits long. Truncate to 128 bits

From,
Nice coder

[Edited by - Nice Coder on April 11, 2005 4:19:38 AM]

Author

101

Apr 11, 2005 at 4:34 AM

ok. if we've got 192 bits, and we need 128....

we get the top 64 bits, and xor them with the bottom 64 bits.
We then use the xored bits, as the output.

So:
o = (((k << 64) | j) * m);
return (o & 680564733841876926889855726716117319680) | ((o >> 128) ^ (o & 36893488147419103231))

680564733841876926889855726716117319680 is all one bits, from 128 to 65. and zero from 64 down.

36893488147419103231 = all one bits, from 0-64.

From,
Nice coder

182

Apr 11, 2005 at 4:35 AM

That looks similiar to TEA.

Author

101

Apr 11, 2005 at 4:51 AM

Nah.

Theres a few similarities. (there both small), but theres a few differences.

Like, mine uses a barrelshift. (which i did with or's and ands. Imalc, you know a few bithacks, is there a better way?).
TEA doesn't.

//Teavoid code(long* v, long* k)  {              unsigned long y=v[0],z=v[1], sum=0,   /* set up */ delta=0x9e3779b9, n=32 ;             /* a key schedule constant */while (n-->0) {                       /* basic cycle start */  sum += delta ;    y += (z<<4)+k[0] ^ z+sum ^ (z>>5)+k[1] ;    z += (y<<4)+k[2] ^ y+sum ^ (y>>5)+k[3] ;   /* end cycle */              } v[0]=y ; v[1]=z ; }

Theres a bit of a difference.

Mine actually uses two barrelshifts, going in different directions.
I also use a really arbetrary number. (its random actually. I'm looking for a better one now...) rather then delta.

Tho it does seem a bit similar tho.....

From,
Nice coder

Author

101

Apr 11, 2005 at 4:57 AM

int128 hash(int* input, int n) {uint64 j = 4DC2EDDD015295B8 uint64 k = D63792157DB78628 uint64 m = 082211754618C8E8n = &input + nfor(;&input < n; input++;) { //Is this hack ok?j ^= *input;k ^= *input;j = (j >> 8) | (j << 45); //Barrelshift jk = (k << 8) | (k >> 45); //Barrelshift km ^= (int64)(j + k) //Make m}uint256 o = (((k << 64) | j) * m);return (o & 680564733841876926889855726716117319680) | ((o >> 128) ^ (o & 36893488147419103231)); }

Current code.

Wow, thats complex. (see the pointer hack, that gets rid of the counter?)

From,
Nice coder

121

Apr 11, 2005 at 5:47 AM

Quote:
Original post by Nice Coder
Wow, thats complex. (see the pointer hack, that gets rid of the counter?)

Intel, for example (there are other papers, too - just was the first I stumbled across) advises against using pointer arithmetic on modern CPUs. I think your pointer hack is useless and might even degrade performance.

BTW. Have you compiled the code? It would be interesting to see whether the compiler is smart enough to translate your rotation code ((j >> c) | (j << d)) into a single rol assembly instruction, which is available on most platforms [smile].

The algorithm looks nice so far. Have you done any tests yet (collisions, best input length ranges, ...)?

Regards,
Pat

EDIT: I only see a problem with your bit-ops on these large bit-fields. I don't think 256 bit integers are commonly available...

Author

101

Apr 11, 2005 at 6:13 AM

Quote:
Original post by darookie
Quote:
Original post by Nice Coder
Wow, thats complex. (see the pointer hack, that gets rid of the counter?)

Intel, for example (there are other papers, too - just was the first I stumbled across) advises against using pointer arithmetic on modern CPUs. I think your pointer hack is useless and might even degrade performance.

BTW. Have you compiled the code? It would be interesting to see whether the compiler is smart enough to translate your rotation code ((j >> c) | (j << d)) into a single rol assembly instruction, which is available on most platforms [smile].

The algorithm looks nice so far. Have you done any tests yet (collisions, best input length ranges, ...)?

Regards,
Pat

EDIT: I only see a problem with your bit-ops on these large bit-fields. I don't think 256 bit integers are commonly available...

Yes. i need a roll, but c doesn't have one. (and neither does vb).
Hopefuly the compiler will change it. (if it doesn't then its a little silly)

ok, i'll get rid of that pointer arithmatic.

Ok, but now i need one register for j, k and m, one for the counter, and one for the data! (as well as for the pointer, and the exit variable).

i can't test now, but from what i've done (pencil and paper sims, w/ idle as a calculator. Unfortunatly i don't know enough python to actually program the sim on it tho...), it seems to be mixing things up a LOT.

From,
Nice coder

121

Apr 11, 2005 at 8:36 AM

Quote:
Original post by Nice Coder
Ok, but now i need one register for j, k and m, one for the counter, and one for the data! (as well as for the pointer, and the exit variable).

That's micro-optimisation. Don't even think about that, that's what compilers are for unless you want to optimise for a specific architecture whose exact specifications and properties are well known to you.

EDIT: You should seriously consider to learn some Python. You can test ad verify your ideas much more quickly (and more reliable) than using a pen-and-paper method. Python isn't hard so give it a go - takes less effort than you might think and a sample implementation helps others to actually take your ideas seriously.

Author

101

Apr 11, 2005 at 7:20 PM

ok. I'll try.....

from,
Nice coder

Author

101

Apr 11, 2005 at 9:42 PM

ok. This is harder then it looks. (j keeps getting l0onger, k gets shorter, and m turns into a midget).

[bawling]

And thats just the main part. (ie, not the output!)

From,
Nice coder

Author

101

Apr 11, 2005 at 9:53 PM

def hash():	j = 0x4DC2EDDD015295B8 	k = 0xD63792157DB78628 	m = 0x082211754618C8E8	j = j ^ 203	k = k ^ 203	j = (j >> 8) | (j << 45)	k = (k << 8) | (k >> 45)	m = m ^ ((j + k) % pow(2, 64))	o = (((k << 64) | j) * m)	return (o & 680564733841876926889855726716117319680) | ((o >> 128) ^ (o & 36893488147419103231))

Heres the code i'm trying so far.

Currently, the output i get (in decimal) is 326373747148640747218235787710117895513

Thats hashing 203.

or if you want it in hex:
0xF5894C19DB579F6E4CE238CCD802DD59

And change the last line to

	return hex((o & 680564733841876926889855726716117319680) | ((o >> 128) ^ (o & 36893488147419103231)))

Can somebody check it against their implementation?

From,
Nice coder

Author

101

Apr 12, 2005 at 12:17 AM

After a few python lessons, i got this

def Hash(x):	j = 0x4DC2EDDD015295B8 	k = 0xD63792157DB78628 	m = 0x082211754618C8E8	for i in x:		j = j ^ i		k = k ^ i		j = ((j >> 19) | (j << 45)) % pow(2, 64)		k = ((k << 19) | (k >> 45)) % pow(2, 64)		m = m ^ ((j + k) % pow(2, 64))	o = (((k << 64) | j) * m)	return (o & 680564733841876926889855726716117319680) | ((o >> 128) ^ (o & 36893488147419103231))

You have to send it the ascii codes (as an array. like [200, 310]). Mainly because i can't find anything that will do that.

But at least it works :) (assuming the earlier ones did. This one agrees with them).

Edit: Need the mods, otherwise the barrelshift doesn't work. Silly me [lol]!
Edit: Be sure to put in teh 32 bit integers. Also changed the barrelshift params they work now.

From,
nice coder

[Edited by - Nice Coder on April 12, 2005 12:17:36 AM]

Author

101

Apr 12, 2005 at 5:46 AM

Does the code look ok to you?

From,
Nice coder

Author

101

Apr 12, 2005 at 7:02 AM

After some testing, it seems great.

Hash for 32767 in hex 0x2995A861BCD2DAB653700331160C6180
Hash for 32768 in hex 0x1641377F1B62D7F2053D4ABEE3DF72E7D
Hash for 32766 in hex 0x90F1229E904D0BF9D8CC0F019B16C6D2

Now, these are only one digit apart, but look at how different the hashes are!

For eg.
Hash(range(1, 100)) = 0x1F303516BC165C922E52F3049626CC978
But if you change the last value, from 99 to 100, you end up with

                      0x38D918E07EC2DB84A9559BB192DEF765

Which is pretty different.

The hash from all integers from 1-(2^16-1) is 0xD91A8B1E27351C11F302A07DAA56587E

Takes awhile tho. (maybe i should start on a quicker python verson? using ands instead of mods by pow's ?)

This is using the current implementation, of cource.

As well, this is pretty fast for a checksum (esp one thats pretty strong), only three xors, two rolls and an add! (not counting loop). (assuming you use C/C++ and not python or VB).

I've also thought about making it a keyed hash function.

For eg.

int j = [number] ^ key[0]
int k = [number] ^ key[1]
int m = [number] ^ key[2]

For 192bit key.

How does that sound?

From,
Nice coder

Author

101

Apr 12, 2005 at 7:13 AM

New hash function, with ands instead of the mods by pows.

def Hash(x):	j = 0x4DC2EDDD015295B8 	k = 0xD63792157DB78628 	m = 0x082211754618C8E8	for i in x:		j = j ^ i		k = k ^ i		j = ((j >> 19) | (j << 45)) & 18446744073709551615		k = ((k << 19) | (k >> 45)) & 18446744073709551615		m = m ^ ((j + k) & 18446744073709551615)	o = (((k << 64) | j) * m)	return hex((o & 680564733841876926889855726716117319680) | ((o >> 128) ^ (o & 36893488147419103231)))

From,
Nice coder

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.