The Daily Click ::. Forums ::. Klik Coding Help ::. 600 DC points! Hash Colision testing.
 

Post Reply  Post Oekaki 
 

Posted By Message

UrbanMonk

BRING BACK MITCH

Registered
  07/07/2008
Points
  49610

Has Donated, Thank You!Little Pirate!ARGH SignKliktober Special Award TagPicture Me This Round 33 Winner!The Outlaw!VIP MemberHasslevania 2!I am an April FoolKitty
Picture Me This Round 32 Winner!Picture Me This Round 42 Winner!Picture Me This Round 44 Winner!Picture Me This Round 53 Winner!
2nd October, 2009 at 04:25:05 -

600 DC points up for grabs!

I've made a hashing algorithm from within mmf2. It's obviously a lot slower than the MD5 hashing of the quick hash object, but the point is to be able to create a unlock key generator for Klik games.

Anyways I need help with collision testing. Try out random strings and see if you get repeating patterns or matching hashes for 2 or more inputs. The point is to has as many possible solutions as the computer can compute without the hash being reversible.

The idea behind this is that if your hashing algorithm isn't widely used then it'll take longer to hack and be almost foolproof against brute-forcing because the attacker doesn't have the original algorithm. Also the programmer can invent his or her own key format (ex: xxx-xxx-xxx or xxxxxx-xx-xxxxxx)

The keys can be generated based on their username and doesn't require a database.


So to the point! If anyone can crack this or reverse engineer the algorithm without having the source I'll give you 600 DC points and the source code.

http://www.jsoftgames.com/jhash.zip

Some example hashes (Try these out in the program above!)

ZSKsFgwsTa5wQrC5S8FuLBr6ollzwQ -> "cat"
rmbQr6Br6BZ2LNmyJ9PdCEosTa5SVJ -> "Cat"
uxg#D8@NyZ2xWg3FVKttd6oQrmTa53 -> "CAT"

I'll give hints to how the algorithm works if no one can crack it right away.

UPDATE: Found a major flaw in the algorithm, fixed it.

Edited by UrbanMonk

 
n/a

Codemonkey

Always Serious

Registered
  06/11/2007
Points
  164

Code MonkeyKlikCast StarVIP MemberAttention GetterWii Owner360 OwnerThe Cake is a LieCardboard BoxHero of TimeI'm a Storm Trooper
I'm on a BoatIt's-a me, Mario!PS3 OwnerSonic SpeedGOTM - SEPTEMBER 2009 - WINNER!Evil klikerPokemon Ball!I am an April Fool
2nd October, 2009 at 22:06:12 -

Sounds fun.

 
You can log off any time you like, but you can't ever leave.

OMC

What a goofball

Registered
  21/05/2007
Points
  3539

KlikCast Musician! Guy with a HatSomewhat CrazyARGH SignLikes TDCHas Donated, Thank You!Retired Admin
2nd October, 2009 at 22:12:45 -

I uh... I killed the program. ._.

 

  		
  		

UrbanMonk

BRING BACK MITCH

Registered
  07/07/2008
Points
  49610

Has Donated, Thank You!Little Pirate!ARGH SignKliktober Special Award TagPicture Me This Round 33 Winner!The Outlaw!VIP MemberHasslevania 2!I am an April FoolKitty
Picture Me This Round 32 Winner!Picture Me This Round 42 Winner!Picture Me This Round 44 Winner!Picture Me This Round 53 Winner!
2nd October, 2009 at 22:20:40 -

Input too much text?

Well it's really only meant for small inputs, like username. It's meant to generate keys for games and whatnot.
I already found a bunch of collisions though, and after another revision I got it to hash up to 3 characters at a time until It hit another collision.

Something like

aba = !ag or something.

I guess offering 600 DC point to reverse engineer it is kinda silly though because if you are smart enough to do that then you wouldn't need the source.

Hint: I had to use the int64 object to do the math because the numbers wouldn't fit in a 32bit int.

Edited by UrbanMonk

 
n/a

UrbanMonk

BRING BACK MITCH

Registered
  07/07/2008
Points
  49610

Has Donated, Thank You!Little Pirate!ARGH SignKliktober Special Award TagPicture Me This Round 33 Winner!The Outlaw!VIP MemberHasslevania 2!I am an April FoolKitty
Picture Me This Round 32 Winner!Picture Me This Round 42 Winner!Picture Me This Round 44 Winner!Picture Me This Round 53 Winner!
3rd October, 2009 at 06:15:47 -

OK, new version. This version has bruteforce collision testing.

I've already found a few collisions in a test group of 248,516 Hashes!
Out of that many hashes I've found 219 collisions. That's pretty good for a homegrown hashing algorithm.
I've only tested up to 3 character combination's.

The only 2 character collisions I found are as follows:

!7=d6
09=m8
Z$=m#
5&=i$
{(=G*
0)=U(
#,=o*

All of these generate the same hash for different inputs.

For the complete list download the file below, I've included them in the archive.

I also want to make it clear that I didn't use any code from any other algorithm, and the only extensions I used were the int64 object and the string parser(converting characters to Ascii)

I've also changed the algorithm quite abit from the original version, so it should be faster now. It also now only uses only capital letters and numbers in the output hash.

Here's the new version. I also included the log file from my tests.

http://www.jsoftgames.com/jhash.zip

Here's a few example hashes from the new algorithm:

UrbanMonk -> 4PYGL3OMT6T6TACZTUWZAZ53CPNKJJEJ
OldManClayton -> CZ53YSSHXEGLRRRF5FU7U7KQPNJ6JAJC
Codemonkey -> UWOJWOJWOWZACZTU7ULRRRFACPJJYJEJ
Cat -> KEG76TAOWDQ1KQ1VN6TU76TAZ53CPCPY
CAT -> KQPYGLGLR2XESHMHBN6HBNKQPNVX2X2M
ATC -> Y3YSHXEGVBYS41VBN6HBBBY3CZ5RR2JW

These look like perfect product keys!

 
n/a

aphant



Registered
  18/05/2008
Points
  1242
3rd October, 2009 at 11:18:06 -

Patterns I'm seeing just in the new examples:

UrbanMonk -> 4PYGL3OMT6T6TACZTUWZAZ53CPNKJJEJ
T6 T6 or 6T 6T
Bonus: J.J end pattern

OldManClayton -> CZ53YSSHXEGLRRRF5FU7U7KQPNJ6JAJC
U7 U7
Bonus: 3YSSHXEG, LRRRF, KQPN, and J.J end pattern

Codemonkey -> UWOJWOJWOWZACZTU7ULRRRFACPJJYJEJ
WOJ WOJ, WO. WO. WO., or JW JW
Bonus: U7, LRRRF, and J.J end pattern

Cat -> KEG76TAOWDQ1KQ1VN6TU76TAZ53CPCPY
Q1 Q1 and CP CP
Bonus: 6T 6T and U7

CAT -> KQPYGLGLR2XESHMHBN6HBNKQPNVX2X2M
GL GL, HBN.HBN., and X2 X2
Bonus: KQPN

ATC -> Y3YSHXEGVBYS41VBN6HBBBY3CZ5RR2JW
Y3 Y3 and YS YS
Bonus: 3YSHXEG


EDIT:
Just hashed 'cat'. Compare to:
KEG76TAOWDQ1KQ1VN6TU76TAZ53CPCPY
7K17641VNK17K1VBYSSHM53CPCZAZTAC

(EDIT: whoops, you didn't do 'cat', you did 'Cat'... but there are still patterns between the two.)

Pattern at same place in string
Pattern found in other string

Then I did 'bat' and 'cas'
bat
XEGLRRF5R2MTACPNK17U7ULR2M5F53YS
cas
GVBBN6T6HXQPNVN6TAZ53Y3OWD2JLR2J

Edited by aphant

 

UrbanMonk

BRING BACK MITCH

Registered
  07/07/2008
Points
  49610

Has Donated, Thank You!Little Pirate!ARGH SignKliktober Special Award TagPicture Me This Round 33 Winner!The Outlaw!VIP MemberHasslevania 2!I am an April FoolKitty
Picture Me This Round 32 Winner!Picture Me This Round 42 Winner!Picture Me This Round 44 Winner!Picture Me This Round 53 Winner!
3rd October, 2009 at 16:12:19 -

Yes I've already noticed those patterns, but yet I'm not generating many collisions.
Those patterns are the result of multiplying and dividing prime numbers.
I chose prime numbers to make sure that the it never lands the same pattern in the same spot.
However my algorithm doesn't have a very good avalanch effect either which causes only small changes in the hash when small changes to the input are made. http://en.wikipedia.org/wiki/Avalanche_effect

But I guess perhaps my sudo-random number generator based on the seed that the original string provides is a bit shaky. However as soon as I fix it other problems arise.

I used a variation on this: http://en.wikipedia.org/wiki/Linear_congruential_generator

After the number is generated it is then used to select a character from a character map I created for it.

I'm offering 600 points if you can recreate my engine. aka make a keygen. I'm sure someone like Pixelthief could do it.

Also you'll notice that all of the collisions generated involve either symbols, or previous collisions.

If I can break the smaller collisions I'll be able to break the larger ones.



Also check this hash I found:

sKj -> OMHX2JJJJJJJJJJJJWDFU7KQ1KQPNK17

What are the chances?

 
n/a

aphant



Registered
  18/05/2008
Points
  1242
3rd October, 2009 at 17:51:36 -

PNK1KQPNK1VNK1KJ5JHMJCJVXJJLJJGJ

I'm sure you have a way to decrypt a hash, right?

 

UrbanMonk

BRING BACK MITCH

Registered
  07/07/2008
Points
  49610

Has Donated, Thank You!Little Pirate!ARGH SignKliktober Special Award TagPicture Me This Round 33 Winner!The Outlaw!VIP MemberHasslevania 2!I am an April FoolKitty
Picture Me This Round 32 Winner!Picture Me This Round 42 Winner!Picture Me This Round 44 Winner!Picture Me This Round 53 Winner!
3rd October, 2009 at 18:48:04 -

Hash/Checksum: A mathematical one-way, irreversable algorithm generating a string with fixed-length from another string of any length.

The only way to crack it is to bruteforce it.

Tell me how long the input is and I'll see if I can crack it.

EDIT: also tell me if you used lowercase letters, uppercase letter, numbers, and/or symbols in your input.

EDIT2: http://en.wikipedia.org/wiki/Hash_%28computing%29

Edited by UrbanMonk

 
n/a

aphant



Registered
  18/05/2008
Points
  1242
3rd October, 2009 at 19:06:08 -

If it's supposed to be irreversible, then why use it? What is the end application for a Klik game?

BTW, 5320 characters, uses all of those things.

 

UrbanMonk

BRING BACK MITCH

Registered
  07/07/2008
Points
  49610

Has Donated, Thank You!Little Pirate!ARGH SignKliktober Special Award TagPicture Me This Round 33 Winner!The Outlaw!VIP MemberHasslevania 2!I am an April FoolKitty
Picture Me This Round 32 Winner!Picture Me This Round 42 Winner!Picture Me This Round 44 Winner!Picture Me This Round 53 Winner!
3rd October, 2009 at 19:19:14 -


Originally Posted by Adam Phant
BTW, 5320 characters, uses all of those things.



I'd never be able to crack it.


Originally Posted by Adam Phant
If it's supposed to be irreversible, then why use it? What is the end application for a Klik game?



It's not used "in game" it's used for making unlock-keys and whatnot.

If there is only 1 hash for 1 input then the unlock key will change for each user. Therefore if someone were to buy your game and then distribute the unlock key it wouldn't work for anyone else. Another example could be a time locked key. The hash changes based on the date, so the key would only work for a space of time before it no longer matches.

To make each hash/unlockkey computer specific you could do this:

Username + harddrive serial # -> Hashed key.

The other users would need the same username and harddrive for it to work. This is a bit extream however and isn't used very often.

It's kinda hard to explain, but here is the basic idea.

Data -> Hash

The Hash is much smaller than the Data, so it's easier to store.
If the Data is changed any then the Hash changes, so then you know the Data can't be the same.

Most websites use hashes to store passwords.

1.User enters password
2.Password is hashed and sent to the server
3.If the hash matches the one in the database then the user has entered the correct password

 
n/a

UrbanMonk

BRING BACK MITCH

Registered
  07/07/2008
Points
  49610

Has Donated, Thank You!Little Pirate!ARGH SignKliktober Special Award TagPicture Me This Round 33 Winner!The Outlaw!VIP MemberHasslevania 2!I am an April FoolKitty
Picture Me This Round 32 Winner!Picture Me This Round 42 Winner!Picture Me This Round 44 Winner!Picture Me This Round 53 Winner!
4th October, 2009 at 21:52:34 -

Another new version. The character distribution has been improved. Also I'm down to only one collision in 2 character combination's.

UrbanMonk -> XSLYHW4RA3WBPLBBGY3TMRPZSZ6OWAD1
OldManClayton -> KB4PG4DXE6UXWWC4OEWGXUBVCJ1E6XGY
Codemonkey -> ZF14PQXPBJDBOVJAJR7CKJS4TDZZXVMZ
Adam Phant -> 3Z2YL4C52J37EXEPWC3KX3NYZG3VZMES
cat -> S1G3HUQF5X17DSUC2WE36GG5NVSGWEWM
Cat -> QGLMUVO1OMSUKV7NZNG2OMZO1G3KAXAP
CAT -> R47EVSSXQMVKOQK77ANXSSWKE5AJ5B31

(they are all the same length the font just messes them up)

I discovered the reason the randomness was bad last time as well. It appears that the int64 object doesn't handle floats! As a work around I just multiplied it by 1000 did my "other math" and divided it by 1000!

Does anyone else find this useful except me?

link- http://www.jsoftgames.com/jhash.zip

I'm actually developing this for a friend, but I hope it interests at least one other person. If anyone can spot any problems let me know.

Edited by UrbanMonk

 
n/a

MrMcFlurry



Registered
  03/08/2009
Points
  89

360 Owner
5th October, 2009 at 05:39:07 -

certainly useful for people interested in selling their games

 
n/a

~Matt Esch~

Stone Goose

Registered
  30/12/2006
Points
  870

VIP Member
7th October, 2009 at 09:51:55 -

UrbanMonkey, although it's nice that you've written your own hashing function, it's no use for anything other than academic purposes. Unless you can prove that the collision rate is equal or less than that of an MD5 hash I wouldn't use it. There are 2 schools of thought that I simply don't agree with

1) MD5 being freely available means it's easier to crack the hashes

Since it's a 1 way hashing function, knowing the algorithm means nothing, other than you can hash things for yourself. If someone wanted your hashing function they would just have to use a debugger and watch what happens in memory (if they can get past the MMF bloat). Ok, so there are MD5 hash databases online that people can use to find matching key values for a given hash, but if you modify your string in a specific way, or rehash your hash n times, then these databases are useless.

2) Using my own (or even an MD5) hashing algorithm makes the copy protection more secure

People don't attack the hashing algorithms, they attack the comparison method. Just modify the code that compares the 2 hashes and trick the code into thinking it's always right.

 
http://create-games.com/project.asp?id=1875 Image


UrbanMonk

BRING BACK MITCH

Registered
  07/07/2008
Points
  49610

Has Donated, Thank You!Little Pirate!ARGH SignKliktober Special Award TagPicture Me This Round 33 Winner!The Outlaw!VIP MemberHasslevania 2!I am an April FoolKitty
Picture Me This Round 32 Winner!Picture Me This Round 42 Winner!Picture Me This Round 44 Winner!Picture Me This Round 53 Winner!
7th October, 2009 at 14:43:54 -

You are absolutely right. I was just having some fun. I'm not seriously thinking that my function is better than md5, nor do I want you to use it.

Just an experiment. It's also very slow due to the way mmf2 works, so it obviously wouldn't be suitable for anything that requires larger values.

But let me ask you a question. Do you really think that someone would go to all the trouble of hacking an mmf2 app. Especially in this community. Also you seem to know what your talking about, so could give me an example. Checking through memory to discover how something works is a lot easier said than done.

Also using rainbow tables you can double hash something or triple hash something while bruteforcing to bypass that protection. I don't think that invalidates md5 though simply because a specific md5 hash still cannot be targeted and created from viable data; that is data that's actually useful.

As for password cracking.
http://www.codinghorror.com/blog/archives/000949.html

 
n/a
   

Post Reply



 



Advertisement

Worth A Click