MD5 collision speed increase

[spektormax]

ok. first of all specs back in the house... so heres my idea, for those of you that don't know the MD5 algarithum front and back go to wikipedia, theres a great aretical, alternitavly you could go look at the rfc for MD5 but its not pritty AT ALL.

So, those of you that are well firmiluare with MD5, you know that esencialy you are reducing a 512 bit (well 448) block to a 128 bit block thru 4 rounds of 16. In the MD5 algarithum you take the password and cut it up into 512 bit chuncks. THen, add a 1 and pad with NULLS till the length is 448%512. THen you add a 64-bit big edine to the end of the Block. Then you break it up into 16 32-bit little eddines. You then perform functions f,g,h, and i on ABCD and then rotate.(im over simplifing it but if you know what im talking about this is enough).

Now, the MD5 algarithum was invented for more of an integready check algarithum for large files (greater than 1 MEG) that have alot of Blocks. Now the problem is that if you just do 512bit to 128 bit (forget about all the padding), thats a 4-1 reduction. Thats a 2^4 or 16 collisions (not that many, that means you ahve to go thru a full 2^128 passwords to theoreticly get 1 probable colision. If you do 2 Blocks, a 1KB file, its 2^4^2 or 256 collisions, that means that treated as a 1kb pass you have to do only 2^64th passwords to get a probbable colion because of 16-1 reduction. At 4KB you get 65535 collions and, at 8 its 2^32... now granted that these passwords are longer, and therefore ar equal in the number of crack cycles since a 1meg file=a 512 bit file in crackign puprosed (we are tallking megabits and kilabits). This causes the algarithum to work worse the bigger the Block number is. If you have a say 100meg file you have a HUGE number of collision, now granted that you still have the same number of crack sycles to get a collions, evnetialy the collions reach infinity, and the probablty of getting a collisoin of the nth attempt aprochase 100%.

This makes shorter password thoereticly harder to crack. Asuming the averge password is under 14 char, you get 8bits*14char, or 112 non zero bits. That leaves 336 bits of zeros, next you have an automatic 1 at the 448th bit, so thasts 337 bits you know, Next, 7 bits of the 64-bits of the big eddine are used to give the bit length of a 14 char password (112<128). So that means taht you have 57 more known bits + the 337 gives you 394 known bits, and 118 that you have to calculate. Now asmuning that you have the 7 that are random, you have those 112 that can be attacked burte forcefully, and the other 7 can jsut be compiled thru the bruteforce. So we got back to 256^14 combinations thats alot, Lets start haking away at the ascii table, throw away all ther extended ascii since its not on the keyboard and most places that use MD5 (web forums likehak5( don't allow them. THats only 128^14, take out the first 32 numbers because you cant have say a new line char in your password. Thats 96^14, take away sybles tahts only 64^14 now thats still a CRAP load of collisons, but far better than 2^512 possibities. And its only 1/4 of that since probaility sates that tis a 4-1 reduction so there are 4 512 blocks for ever 128 bit hash.

Now MD5 beats DES any day since DES is first of all all upercase so its only 2^36^7*2, so its VERY easy to crack.

So in short MD5 collisons are MUCH faster to callculate then say MDCRACK can becasue of this fact, you take a chance on a ,001% of passwords but hey 1 hour vs 12 years for 99.9% of passwords any day.

[cooper]

ok. first of all specs back in the house...

Snip an only slightly comprehensible story that has so much spelling errors, it's damn near impossible to figure out just what points you're trying to make.

Now MD5 beats DES any day since DES is first of all all upercase so its only 2^36^7*2, so its VERY easy to crack.

Oh FFS, READ and UNDERSTAND the stuff you talk about before you start dissing it.

NTLM uses DES, but DES is not NTLM.

So in short MD5 collisons are MUCH faster to callculate then say MDCRACK can becasue of this fact, you take a chance on a ,001% of passwords but hey 1 hour vs 12 years for 99.9% of passwords any day.

Here's an MD5 of a password:

c95c101901924a7e55bb6c68e77b2147

Your time starts NOW!

[VaKo]

Mate, you seem kinda smart but I can't read a word of that. We've been here before, you babble on about your right to be incomprehensible and any good ideas you have sink to the bottom. Please, if you have a big post like this, use a god damn spell check function.

[Darren Kitchen]

I read it. I auto corrected the spelling errors in my head (Like CRC but better). I thought about it. I read the replies of others. And rather than go on about your spelling I figured I'd post something meaningful. Except for the fact that I have neither the understanding nor the immediate time necessary to grok the finer points of the MD5 algorithm. So in short, your ideas are interesting to me, and I would like to subscribe to your newsletter. If you don't get it, read more slashdot.

[spektormax]

sorry about my spelling, yeh thats why anyone that knows me from IRC more personaly knows that I like to skype people instead becasue then I can make alot more sence, as for DES and NTLM, DES IS the base for LM, the upercase portion is LM, as for NTML, version 1 the LM is DES version 2 theres no DES part, the password is stored as MD4, and then HMAC MD5ed with nt time and other stuff (its not fully documented but has been reverse engineered). As for c95c101901924a7e55bb6c68e77b2147 if that is a hash from 1 512 block, then you can possibly assume a A-Za-z0-9 character set and a length of less than or equal to 14, if thats an MD5 of more than one block that was xored, then you cannot asume anything, so since I have no sentex to that hash, the speed increse doesn't exist. Note that any hash function that uses non semi-random padding has these problems, that means that so does MD4, I don't know the MD2 or RIPMD-160 algarithums off the top of my head.

[cooper]

As for c95c101901924a7e55bb6c68e77b2147 if that is a hash from 1 512 block, then you can possibly assume a A-Za-z0-9 character set and a length of less than or equal to 14, if thats an MD5 of more than one block that was xored, then you cannot asume anything, so since I have no sentex to that hash, the speed increse doesn't exist.

Here's an MD5 of a password

Let me make it easier by admitting that yes, it IS limited to [a-zA-Z0-9] and less than 14 characters long.

The clock has been reset. GO!

[Deveant]

T_T Cooper u just had to use Caps didnt ya :P my RT's only a 99% alpha_Numeric, would be cool to have a all RT Md5 but umm kinda pointless... damn u salt...

[cooper]

Well, I tried to read and comprehend SpectorMax's story, and yes I even did make it to the end. The whole idea SpectorMax is going on about is not so much to provide us with the exact same password/passphrase, but instead give us a character combination that yields the exact same hash - the collision.

Back in march '06 Vlastimil Klima published an algorithm that is claimed to yield a sequence that will provide an identical MD5 hash in under 30 seconds on a generic underpowered laptop. I've tried to go over the paper and the code. The paper was well beyond my mathematical capabilities, and the published source code was windows-only, and spat out only the times in which a collision was supposedly found... without providing the actual collision. I'm sure it's in there somewhere, but the variable names are presumably checkoslovakian, or polish or some language I don't understand. Like any good piece of proof-of-concept code, it's very light on comments, but I would presume that if you're clever enough to figure out the paper the code can be this terse.

So, long story short, there's a paper out there that claims to describe a way to quickly find a byte sequence that will result in the same MD5. No rainbow tables, just some solid math. As I can't get the program to produce the colliding MD5 (oh, and this colliding MD5 does of course need to be keyboard-producable. I highly doubt this program checks for that) I can't personally verify the validity of the claims. But SpectorMax apparently can. And thus by all means, kind sir, provide me with a byte sequence that you can enter via the keyboard which will match the above-provided MD5 sequence. It's the product of a plain php md5("text") call, so it's not like I've made it especially hard or anything.

GO!

[SomeoneE1se]

If this is true then MD5 is broken because you're not matching passwords you're matching the hash. So if you can get the same hash it's over, right?

[cooper]

If the described method of finding a collision works, it means that the encryption MD5 is supposed to add is flawed. You're not entirely fucked as you need access to whatever location that holds these keys, but other than that, yes you're right.

So if you've got the choice between algorithms, it would seem SHA-1 is the safer bet.

But until an actual collision of my key is provided, I'm sceptical.

[majk]

And also as far as I know the best techniques can only find arbitrary collisions. It can't find collisions for a specific hash.