PDA

View Full Version : Blowfish Bruteforce 48 bits


Lbolt99
July 25th, 2002, 16:59
I have come back around to working on the CacheX project (out of 5-10 different things I am working on, lol). I am going to give it a go at brute forcing the 64 bit constant.

I found a strange weakness, or at least what I think is a weakness, in the implementation: seems the 64 bits are reduced to 48 bits. So that reduces the complexity by two orders of magnitude.

Problem: Find XX XX XX XX YY YY XX XX so that Z1 set of 30h bytes "blowfishes" into Z2 set of 30h bytes.

XX = random 8 bits
YY = constant data
Z1= preset data
Z2= "target" data

The algorithm DISCARDS 16 of the bits in the 64 bit constant! Example from [already solved] CacheX for Opera:

64 bits used for final decrypting:

9D 91 93 1E 00 80 74 FD

Original 64 bit constant:

85 09 1E 93 91 9D FD 74

The 85 09 are discarded, and the program writes in a 00 80 in its place. If the proper value is obtained by brute forcing (48 bits), one still has to work backwards to arrive at the values that the 00 80 overwrote. I think that's just a 16 bit brute force, tho.

cyberheg
July 25th, 2002, 18:57
Once you will implement this you will find out soon after that with a single computer you won't be able to solve it without having a great bit of luck (the needle in a haystack problem) because the keyspace is still too big. For full 64 bit you might aswell leave it alone since you won't be able to find a key and for 48 bits you should think about how many computers your friends got that they will want to use on your project.
Without knowing the exact computing time it could take several months even if you have like 100 modern pc's.

This ofcourse raises the problem about multitasking across network and key distribution since I am sure your friends wouldn't want to type in keys manually to test.
A key test client and server is ofcourse the best solution to this (like rc5 contest or seti@home).

All in all you should try to find out how many machines you could get hold of for this. Personally I wouldn't even bother start on it if I couldn't get 50 p3's atleast.

Lbolt99
July 26th, 2002, 14:33
Well, thanks for the reply, I guess it's pretty much unfeasible unless distributed, which really isn't worth it for a $20 program.

Thanks to everyone who contributed/participated in the Blowfish/SHA-1 analysis on CacheX project. In conclusion, the best approach is a hard patch, with the P box and S box (1040 bits of the subkey table) pasted into the program, after it is finished modifying itself 100s of times, instead of dumping and pasting all the different encrypted segments. Basically let the program do all the hard work instead.

It all boiled down to an obscured 64 bit constant, making the keygen impossible unless one has a valid license (as of yet, still unable to find).

My next analysis project will be on GetDataBack for NTFS: see new thread "RSA-65 analysis on GDB-NTFS" in a similar fashion as the CacheX project was done.