about the algorithm used

Moderator: BarsMonster

brunolap
Posts: 11
Joined: Fri Jan 09, 2009 7:51 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

about the algorithm used

Post by brunolap » Fri Jan 09, 2009 8:03 pm

hi,

I've just started using barswf and it made me wonder: How you crack it so fast??
I've made a program to bruteforce MD5 and maneged to get about 1 200 000 Hashes/s and your program is still much faster, even with "just" 90 000 Hashes/sec.

How do you do that???

My bruteforce program is going sequentially: starts with a, than b, than c ... than aa, than ab, and so on. This must be the diference.

I would love to know your algorithm, imagine if i manege to get 1 200 000 hashes/s with the efficiency of your program.

thanks in avance

By the way: i get 1 200 000 Hashes/s with just 1 core and 90 000 hashes/s with your program using 2 cores(Core 2 Duo 2Ghz) + GPU (8400M GS)

neinbrucke
Posts: 82
Joined: Sun Nov 02, 2008 8:53 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by neinbrucke » Fri Jan 09, 2009 9:20 pm

your program probably doesn't have SSE2 optimizations... and you probably don't reverse your hashes to a certain level :)
brunolap, how fast is your bruteforcer when you check only one hash at the same time? does it scale well? the comparison part can also be a big hold up.

but i am somewhat curious about the input generation as well, bars, you doing anything special there? :)

brunolap
Posts: 11
Joined: Fri Jan 09, 2009 7:51 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by brunolap » Fri Jan 09, 2009 9:47 pm

actually, I'am checking just one hash at a time. I have one thread doing all the work.
it dosen't scale well. with more than one thread the program it's very unreliable. sometimes it goes over the right hash and don't notice and sometimes it gives the next key as the right one (for example, the right is abcde and it says it is abcdf)

you are right....i'm not using SSE2 optimizations neighter reverse the hash (i just found out about it)

Do you think it might be this the reason??

another stupid question that just poped my head: on barswf Mhash/s is 10^3 Hash/s or 10^6 hash/s ?? that would explain...hehe

neinbrucke
Posts: 82
Joined: Sun Nov 02, 2008 8:53 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by neinbrucke » Fri Jan 09, 2009 10:14 pm

not sure where your slow down is, probably at multiple places... my sha-1 brute forcer already does 5M hashes/s (well, that is a 3.2 ghz core, but still), while sha-1 is slower then md5... and it seems like you can't reverse as much as with MD5.

oh btw, if i just use openssl's MD5, i already get more then 5M hashes/s (3.6 when calling it the slow way) on one of my cores... so try that implementation first and see if that speeds things up... then you know if it's in your MD5 code or the brute force and comparison part...

o and the M is for 10^6

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by BarsMonster » Sat Jan 10, 2009 5:16 pm

Yes, it is millions, so it is 70 times faster :crazy:
The key is using SSE2, using Intel C++ and reversing last steps.
But duing steps 1 & 2 will push you somewhere to 60 mil if everything else is implemented right.
If your program tends to miss keys in multithreaded mode, I guess you are not using mutexes for key generation.

neinbrucke
Posts: 82
Joined: Sun Nov 02, 2008 8:53 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by neinbrucke » Sat Jan 10, 2009 9:54 pm

i've been toying around with sha1 and sse2 (first time i use sse :P), and i'm sort of learning it (already do 4 hashes at the same time, not optimized at all, but still like 50% faster overall)... do you use sse2 for generating plaintexts as well?

also, is it me, or is there no PTEST like function in SSE2, such as in SSE4.1 (for example _mm_testz_si128). So i'm left with using something like _mm_cmpeq_epi32 for comparing hashes, but then i have to check the contents of the resulting __m128i... that seems to be unnecessarily slower to me :crazy:

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by BarsMonster » Sat Jan 10, 2009 10:37 pm

neinbrucke wrote:i've been toying around with sha1 and sse2 (first time i use sse :P), and i'm sort of learning it (already do 4 hashes at the same time, not optimized at all, but still like 50% faster overall)... do you use sse2 for generating plaintexts as well?

also, is it me, or is there no PTEST like function in SSE2, such as in SSE4.1 (for example _mm_testz_si128). So i'm left with using something like _mm_cmpeq_epi32 for comparing hashes, but then i have to check the contents of the resulting __m128i... that seems to be unnecessarily slower to me :crazy:
Personally I do it like that:

result_mask = _mm_movemask_epi8(
_mm_and_si128(_mm_cmpeq_epi32(as1,tas1),
_mm_and_si128(_mm_cmpeq_epi32(bs1,tbs1),
_mm_and_si128(_mm_cmpeq_epi32(cs1,tcs1),_mm_cmpeq_epi32(ds1,tds1)))));

Surely you can use PTEST too, this would be a little faster and will limit number of processors supported :-)

neinbrucke
Posts: 82
Joined: Sun Nov 02, 2008 8:53 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by neinbrucke » Sun Jan 11, 2009 12:58 pm

oh, nice solution :)
i doubt it will be faster to do a PTEST actually...

btw wouldn't it be faster to only compare as1 and tas1? and only on success start comparing the other variables?

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by BarsMonster » Sun Jan 11, 2009 5:58 pm

neinbrucke wrote:oh, nice solution :)
i doubt it will be faster to do a PTEST actually...

btw wouldn't it be faster to only compare as1 and tas1? and only on success start comparing the other variables?
Well, actually this code gets executed quite rare, because you can skip last steps after checking D value when it's finalized few steps earlier :-)

neinbrucke
Posts: 82
Joined: Sun Nov 02, 2008 8:53 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by neinbrucke » Sun Jan 11, 2009 8:30 pm

ah ok, that would be for a reversed md5 i think?

i'm doing sha1... doesn't seem to reverse that well :) (data is being 'expanded' after step 16)

just curious, did you start on an optimized sha1 cracker already?

brunolap
Posts: 11
Joined: Fri Jan 09, 2009 7:51 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by brunolap » Sun Jan 11, 2009 9:02 pm

can I do this SSE2 optmizations using visual studio 2008 or I must use the intel c++??

And i'm still confused about this "reverse the last step"...which is the last step?? is it the last of the 64 steps or the whole last round (the 4th one)??...can you point me somewhere i can find more about it?? I saw the topic abot algorith optmization but I still dont understand it weel enough to implement

Another reason why my program is slower is that i'm using c# calling a DLL writen in C that perform the hash....
I can't even generate that much strings that fast!!..haha....I might have to write all the work intensive part in c/c++ and use c# just as a user interface...what do you thing about it??

thanks

neinbrucke
Posts: 82
Joined: Sun Nov 02, 2008 8:53 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by neinbrucke » Sun Jan 11, 2009 9:19 pm

oh lol... and probably you are generating strings as input... not even an array of characters... strings are slooooow.
i'm doing sse2 in vc++ 2008, i should give the intel compiler a try :P

with my sha1 brute forcer i'm now from 5M hashes/s without SSE2 to 10M hashes/s with SSE2... should still be able to do things faster... but i've just learned SSE2 since a few days :)
anyone got some tips on getting input bytes (like "unsigned char * pData") into __m128i registers, in groups of 32 bits (first 4 bytes in first register, then 2nd 4 bytes into next register)? i'm now doing some ugly union with an array of unsigned chars and an array of uint32's. then memcpy data to this union, then set_epi32 the uint32's into the __m128 variables (and doing some stuff in between).

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by BarsMonster » Sun Jan 11, 2009 9:48 pm

You can do VC 2008 with no problems, intel C++ just "packs" instructions better, so that it works like 10% faster (But compilation time is 5-10 times slower, so I tend to develop on VC, and only release build are under Intel C++).

I do _mm_set_epi32 out of int* pointer, no need to copy to union.

brunolap, it should be fine to use C# for UI only, like setting parameters/starting C++ threads, but no computations should be done in C#.

brunolap
Posts: 11
Joined: Fri Jan 09, 2009 7:51 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by brunolap » Mon Jan 12, 2009 12:17 am

I'm generating a array of bytes (the byte value of chars, so I can increment the value easily).

i'll try to implement the "string" generation in c together with the hash soh my thread in c# just call a loop in c.

another question: how are you deviding the task between the multiple cores? are you assining a space to try for each thread? like thread 1 from a to zzzzz, thread to from aaaaaa to zzzzzz... and so on
or are you using a single function that gives a string to each thread at each loop sequencialy?

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by BarsMonster » Mon Jan 12, 2009 1:40 am

brunolap wrote:I'm generating a array of bytes (the byte value of chars, so I can increment the value easily).

another question: how are you deviding the task between the multiple cores? are you assining a space to try for each thread? like thread 1 from a to zzzzz, thread to from aaaaaa to zzzzzz... and so on
or are you using a single function that gives a string to each thread at each loop sequencialy?
Each thread has it's own keyspace

neinbrucke
Posts: 82
Joined: Sun Nov 02, 2008 8:53 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by neinbrucke » Mon Jan 12, 2009 7:24 am

i use part of the rainbow tables reduction function to calculate the starting points for each keyspace.
Last edited by neinbrucke on Mon Jan 12, 2009 7:41 am, edited 1 time in total.

neinbrucke
Posts: 82
Joined: Sun Nov 02, 2008 8:53 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by neinbrucke » Mon Jan 12, 2009 7:29 am

BarsMonster wrote: I do _mm_set_epi32 out of int* pointer, no need to copy to union.
oh, now i remember why i used the union... i used it to set padding byte at array_of_chars[length]... but since i'm now doing a brute forcer, i can just fixate that one in my input generator :)

btw, just an idea, not tested yet; using 4* _mm_set_epi32 with int* pointer, you do 4 loads from memory per set_epi32, that would be at least 4*4 operations in total right?
if you load 4*16 input bytes at once into 4* an m128i, then matrix transpose the 4 m128i's, you'd have it alright.
you then have 4 loads and there is this shuffle macro for floats (_MM_TRANSPOSE4_PS) using 8 shuffle operations,you have a total of 12 operations... wouldn't that be faster?

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by BarsMonster » Mon Jan 12, 2009 12:30 pm

Why need for shuffle?

neinbrucke
Posts: 82
Joined: Sun Nov 02, 2008 8:53 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by neinbrucke » Mon Jan 12, 2009 10:10 pm

http://msdn.microsoft.com/en-us/library ... S.71).aspx

this transpose does the following:

Code: Select all

#define _MM_TRANSPOSE4_PS(row0, row1, row2, row3) {                 \
            __m128 tmp3, tmp2, tmp1, tmp0;                          \
                                                                    \
            tmp0   = _mm_shuffle_ps((row0), (row1), 0x44);          \
            tmp2   = _mm_shuffle_ps((row0), (row1), 0xEE);          \
            tmp1   = _mm_shuffle_ps((row2), (row3), 0x44);          \
            tmp3   = _mm_shuffle_ps((row2), (row3), 0xEE);          \
                                                                    \
            (row0) = _mm_shuffle_ps(tmp0, tmp1, 0x88);              \
            (row1) = _mm_shuffle_ps(tmp0, tmp1, 0xDD);              \
            (row2) = _mm_shuffle_ps(tmp2, tmp3, 0x88);              \
            (row3) = _mm_shuffle_ps(tmp2, tmp3, 0xDD);              \
        }
i guess they made this macro because it's fast to transpose a matrix this way... or just for lazy people :P
anyway, it doesn't work... there is no such macro for integers... nor such a shuffle operation...

so now i do it this way:

Code: Select all

	__m128i plain1 = _mm_load_si128 ((__m128i *)pData);
	__m128i plain2 = _mm_load_si128 ((__m128i *)pData2);
	__m128i plain3 = _mm_load_si128 ((__m128i *)pData3);
	__m128i plain4 = _mm_load_si128 ((__m128i *)pData4);

	sse_W[0] = _mm_set_epi32(plain1.m128i_i32[0], plain2.m128i_i32[0], plain3.m128i_i32[0], plain4.m128i_i32[0]);
	sse_W[1] = _mm_set_epi32(plain1.m128i_i32[1], plain2.m128i_i32[1], plain3.m128i_i32[1], plain4.m128i_i32[1]);
	sse_W[2] = _mm_set_epi32(plain1.m128i_i32[2], plain2.m128i_i32[2], plain3.m128i_i32[2], plain4.m128i_i32[2]);
	sse_W[3] = _mm_set_epi32(plain1.m128i_i32[3], plain2.m128i_i32[3], plain3.m128i_i32[3], plain4.m128i_i32[3]);
actually works already a lot faster then what i did previously, was close to 10% faster :)
reversed last 3 steps, written out the first 4 steps... now i'm at 11.6 Mhashes/s :)

tnx for your hints 'n tips, or just plain directions :crazy:

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by BarsMonster » Mon Jan 12, 2009 11:28 pm

Try Intel C++ and #pragma unroll 2 or 3, also try higher numbers :-)

Sc00bz
Posts: 136
Joined: Fri Oct 03, 2008 8:28 am
Contact:

Re: about the algorithm used

Post by Sc00bz » Mon Jan 12, 2009 11:51 pm

brunolap wrote:And i'm still confused about this "reverse the last step"...which is the last step?? is it the last of the 64 steps or the whole last round (the 4th one)??...can you point me somewhere i can find more about it?? I saw the topic abot algorith optmization but I still dont understand it weel enough to implement
You only need to do the first 43 out of 64 steps and 2 half steps so it's like just doing 44 out of 64 steps for MD5. I explained basically everything here http://3.14.by/forum/viewtopic.php?f=8&t=47#p508 but you said you already saw it. I keep forgetting how much Bars reverses but I'm thinking it was just the whole last round which means he's only doing the first 45 out of 64 steps. So Bars could get like 2.27% more speed by doing it the other way. That's if I'm right on him doing 45 steps instead of 43 and 2 half steps.

Side note: I still don't understand how his 32 bit version is so fast interlacing 3 with SSE2 to me seems like it would be slower than interlacing SSE2 and MMX. Well I guess it has to do with cache (for interlacing 3 with SSE2) and/or that SSE2 and MMX have a performance hit such as with switching from floating point to integer math with SSE.

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by BarsMonster » Tue Jan 13, 2009 12:32 am

Sc00bz wrote:Side note: I still don't understand how his 32 bit version is so fast interlacing 3 with SSE2 to me seems like it would be slower than interlacing SSE2 and MMX. Well I guess it has to do with cache (for interlacing 3 with SSE2) and/or that SSE2 and MMX have a performance hit such as with switching from floating point to integer math with SSE.
Hmm, just found that windows does not restore MMX/FPU context when switching context :-) Also, MMX is just 64-bit
That is the situation where Intel C++ compiler can produce code better then average human assembler developer.
Human would just die before writing all this in assembler :-)

Well, on 32-bit version BarsWF does around 1.6-1.8 SSE2 calculations per clk, and we still have 1.4-1.2 operations in average to arrange data from L1 cache, which does not look so unrealistic (but i guess it's really boring to code by hands).

just to remind - C2D does 3 SSE2 instructions per clk with 2 clk latency, and can decode 4 instructions per clk (sometime 5, but it never happens in BarsWF)

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by BarsMonster » Tue Jan 13, 2009 12:34 am

Sc00bz wrote:You only need to do the first 43 out of 64 steps and 2 half steps so it's like just doing 44 out of 64 steps for MD5
Dude, you've got me :-)
I am doing 46, you can clearly see what I've missed :-)
Looks like we'll see 6.5%-8% speedup of SSE2 on 0.9 :crazy: :crazy: :crazy:

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by BarsMonster » Tue Jan 13, 2009 2:31 am

Sc00bz wrote:SSE2 and MMX
AFAIK MMX (as well as FPU and 3dnow) are obsolete now, so it's context is not being saved during context switch in 64-bit applications, so I would prefer to never ever use MMX :-)
Win64/x86 does not fully save the x87 state, so you cannot use the x87
registers and instructions, hence no 80-bit hardware types. Win64/IPF
*does* save the entire (82 bit) FP registers, so again, a compiler or
assembler programmer can use the extended formats (and they're quite
handy for implementing the various math functions). Note that
Win32-on-Win64 *does* support the full set of x87 functions, so a Win32
program running on Win64 can use the 80-bit registers.
ops
http://www.mombu.com/programming/amd/t- ... 82440.html

It appeared it was true only for kernel-level things, for the user-mode threads everything is backward-compatible, as usual :crazy:

neinbrucke
Posts: 82
Joined: Sun Nov 02, 2008 8:53 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: about the algorithm used

Post by neinbrucke » Tue Jan 13, 2009 1:20 pm

BarsMonster wrote:Try Intel C++ and #pragma unroll 2 or 3, also try higher numbers :-)
intel compiler isn't free and it doesn't seem to support Visual C++ Express... :/

Post Reply
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Who is online

Users browsing this forum: No registered users and 1 guest