about the algorithm used

Moderator: BarsMonster

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 3:04 pm

neinbrucke wrote:
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... :/
Damn, why didn't you have born in Russia? :-)

Also Visual C++ Express does not support 64-bit code AFAIK
Intel C++ have evaluation, and it's free for open source things under linux AFAIK

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 4:59 pm

well, i'll release source code anyway, so if anyone feels like compiling with intel c++, he's free to do so...
i think i'm done with optimizing it now, i'll just make it a real brute forcer instead of a benchmark... and it should be done :)

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 16, 2009 1:46 pm

well, I think it's done now...

So I present SHAbr: using SSE2 and it's multi threaded. As far as I know, it's currently the fastest CPU brute forcer for SHA-1. Now close to 60 Mhashes/ using 4 threads. Feel free to make it REALLY fast, probably possible to do things more efficient :)

http://blog.distracted.nl/

(oh, and i seem to have a blog since a few days ;))

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 » Fri Jan 16, 2009 4:48 pm

neinbrucke wrote:well, I think it's done now...

So I present SHAbr: using SSE2 and it's multi threaded. As far as I know, it's currently the fastest CPU brute forcer for SHA-1. Now close to 60 Mhashes/ using 4 threads. Feel free to make it REALLY fast, probably possible to do things more efficient :)

http://blog.distracted.nl/

(oh, and i seem to have a blog since a few days ;))
Damn, pthreads :-)
Have you considered using other cross-platform libs like Boost or POCO which does not require some "magic" actions to make it work in 64-bit mode?
(pthreads have 64-bit support in very last version, but it is not-precompiled, and one need to have cvs installed to get it...)

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 16, 2009 6:33 pm

i used threads for the first time when i build rcracki_mt (rainbowtables stuff)... i first did it using windows threads... that's not portable at all :P
then when i was looking for something else, i found pthreads, and a little later boost... what i remember was something about pthreads being a little lower level, boost easier (not sure if that is correct though :P)... and pthreads is by default supported under linux... anyway, i choose to use that :)

when i ported from windows threads to pthreads, it wasn't that much work actually... so i guess it won't be that much work to port it to boost... never heart of POCO :)
i didn't know that pthreads sucks for 64-bit support... maybe i'll give boost a try next time if have some spare time on my hands... (that is not for the upcoming couple of weeks :))

Bitweasil
Posts: 110
Joined: Fri Nov 07, 2008 6:50 am
[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 Bitweasil » Fri Jan 16, 2009 6:39 pm

Hm, I'll look at porting that to CUDA here shortly. Thanks!

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 » Fri Jan 16, 2009 7:12 pm

neinbrucke wrote:when i ported from windows threads to pthreads, it wasn't that much work actually... so i guess it won't be that much work to port it to boost... never heart of POCO :)
i didn't know that pthreads sucks for 64-bit support... maybe i'll give boost a try next time if have some spare time on my hands... (that is not for the upcoming couple of weeks :))
Well, the problem of Boost is that there is no thread priority there :-)
POCO have portable thread priority thing.

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 16, 2009 7:58 pm

Bitweasil wrote:Hm, I'll look at porting that to CUDA here shortly. Thanks!
good luck :) it might not be necessary to reverse the steps i did, it's probably enough to just reverse the value that is A (preCheck) before step SSE_ROTATE4(76)... don't think the code behind that check gets executed that often.
i might give it a try some time as well... have to learn CUDA some day or another :)

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 19, 2009 7:34 am

Just tried 2xSSE2, and extrapolated to 2xSSE2 + 1xMMX:
2xSSE2 = 55Mhash, so even if we would get free MMX, it would give us 68.7Mhash, while 3xSSE2 gives 72MHash :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 » Mon Jan 19, 2009 9:22 am

those speeds are probably on your own system? what do you get without your own modifications?

what do you mean by 2x SSE2? You mean 8 plaintexts being hashed at the same time?

anyway, i'm off for a vacation now... cya in 4 weeks :P

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 19, 2009 3:47 pm

neinbrucke wrote:those speeds are probably on your own system? what do you get without your own modifications?

what do you mean by 2x SSE2? You mean 8 plaintexts being hashed at the same time?

anyway, i'm off for a vacation now... cya in 4 weeks :P
yes 2xSSE2 mean 8 plaintexts. What do you mean "modifications" :-) Just 4Ghz C2D :-)

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 Feb 16, 2009 8:52 am

BarsMonster wrote:
yes 2xSSE2 mean 8 plaintexts. What do you mean "modifications" :-) Just 4Ghz C2D :-)
*back from vacation :P*

with "modifications" i meant changes in code, as you said "2xSSE2 = 55Mhash", i have no clue what your speed was with just 1xSSE2 :P

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 » Wed Feb 18, 2009 7:23 pm

aargh...
to do 2x SSE2 and such... is that a special trick? or am i too stupid to understand how you let 1 instruction apply to 2 variables at the same time?
Or do i really need to use intel compiler for it to work at all?

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 » Wed Feb 18, 2009 10:12 pm

Well, if you do a=b+c and a2=b2+c2 they both most likely be done in 1 clock :-)
With Intel C++ it just happens more often :-)

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

Re: about the algorithm used

Post by Sc00bz » Thu Feb 19, 2009 1:03 pm

2x SSE2 just means to interlace (doing your algorithm twice):

algo:
a += b;
b ^= c;
c &= d;
b += d;

"2x" algo interlaced:
a1 += b1;
a2 += b2;

b1 ^= c1;
b2 ^= c2;

c1 &= d1;
c2 &= d2;

b1 += d1;
b2 += d2;

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 » Thu Feb 19, 2009 5:18 pm

tnx both of you... apparently i was already close, but not close enough :p
i'll try and order things a little closer, so instead of (for example):
SSE_EXPAND_3(t); SSE_ROTATE2_F( sse_A, sse_B, sse_C, sse_D, sse_E, sse_W[t] );
and then another such line for the second one.
i'll try to have the two lines per actual instruction.

Maratyszcza
Posts: 3
Joined: Mon Dec 22, 2008 9:33 pm
Location: Moscow, Russia
Contact:

Re: about the algorithm used

Post by Maratyszcza » Thu Feb 19, 2009 6:02 pm

neinbrucke wrote:aargh...
to do 2x SSE2 and such... is that a special trick? or am i too stupid to understand how you let 1 instruction apply to 2 variables at the same time?
Or do i really need to use intel compiler for it to work at all?
Every instruction is decomposed to microoperations. For integer SSE instructions usually 1 instructions comes to 1 microoperation. Core2 processors have 6 ports to execute microoperations: ports 0, 1 and 5 are for arithmetic microoperations, port 2 is for read-from-memory microoperations, ports 3 and 4 are for write-to-memory microoperations. Each clock cycle processor can execute one microoperation on every port. Many integer SSE microoperations can execute on several ports; so far, processor can execute multiple microoperations in 1 clock cycle. For example

Code: Select all

paddd xmm1, xmm7 ; paddd can execute on ports 0 or 5
pand xmm0, xmm7 ; pand can execute on ports 0, 1, 5
pslld xmm2, 27 ; pslld can execute on port 0 only
On the same clock cycle processor can execute paddd on port 5, pslld on port 0 and pand on port 1.

At http://www.agner.org you can find tables with execution ports for each instruction

bias_resistor
Posts: 18
Joined: Fri Oct 03, 2008 10:07 am
[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 bias_resistor » Mon Feb 23, 2009 2:49 pm

neinbrucke, will you add support for salting?
good options would be prepend/append of salt, either binary or ascii format.
also, since some passwords are created using unicode, that would be good feature too.

great tool

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 Feb 23, 2009 3:05 pm

not sure if i have time (or want to make time) to further work on it in the near future... but i'll keep it in mind :)
(i just have some random periods that i actually find joy in programming :P)

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 May 04, 2009 8:29 pm

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.
let's revive another old topic... but ehm, i'm currently playing around with my NTLM brute forcer, and i have something strange with interlacing SSE2 more and more :P

my system: Q9450 @ 3.2Ghz, 4 threads:
1x SSE2 : 110 Mhashes/s
2x SSE2 : 150 Mhashes/s
3x SSE2 : 175 Mhashes/s
4x SSE2 : 200 Mhashes/s
(5x gets slower, like 170)

shouldn't it just stop getting faster at like 2 or 3xSSE2 ??

or is this just a way to get VC++ 2008 express to arrange instructions efficient enough to have 2 or 3 simultaneously executed? :)

[edit]with my MD5 brute forcer it doesn't do this, that goes from like 77 to 100 to 114 back to 105 Mhashes/s when doing 1x, 2x, 3x, 4x SSE2)

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

Re: about the algorithm used

Post by Sc00bz » Tue May 05, 2009 12:38 am

If it's 64 bit it should start slowing down after interlacing it three times since you need 5 registers to do MD4 or MD5 and you have 16 registers to work with. It might be faster interlacing it four times but it depends on your cache.

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 May 05, 2009 7:54 am

i run 32 bit, and i think my cpu has a large cache... so that explains MD4... probably MD5 not going faster with 4 times interlacing because of the larger code then.

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 May 05, 2009 8:21 pm

neinbrucke wrote:i run 32 bit, and i think my cpu has a large cache... so that explains MD4... probably MD5 not going faster with 4 times interlacing because of the larger code then.
I bet your L1 code/data cache is not that huge ;-).
There should be no benefit for more than 3 SSE2 "threads" in current generation CPUs (Core2Duo/Nahalem), because they only can execute 3 instructions per cycle.
I would suggest you download trial version of Intel C++, and try again. You should get maximum speed at 3 threads.

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 May 05, 2009 8:30 pm

hmm, 64KB indeed... i so have 3MB L2 cache per core though :p

maybe i'll try and get me an evaluation version for VC pro as well...

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 May 05, 2009 11:49 pm

neinbrucke wrote:hmm, 64KB indeed... i so have 3MB L2 cache per core though :p

maybe i'll try and get me an evaluation version for VC pro as well...
It's not 64kb, it's 32kb for data and 32kb for code (decoded operations, which takes more space).
L2 does not matter, it is sloooooooooow....... (compared to registers & L1)

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