SHA1 Attack Program

adresd · Post by **adresd** » Wed Jun 01, 2005 4:22 am

Have been playing around with the SHA1 attack program and optimisation of the searching.

Currently using a hashlist of 2354 and dic size of 2322 (as an example).

Main changes are:
Removal of duplicates from dictionary on load.
Searchtable for the hash checking, cutting down searchspace time.
Moving SHA1 calc to minimise time spent doing it.

Thanks to gorim for helping with performance checking of the code.

Here is the result: attack.c [Updated]
------------------------------------------------------

Code: Select all

Edited - see below for newer version of code

------------------------------------------------------
This code also outputs all found function names into an xml file, this is for collecting them and easy collision checking later.

currently testing using following script:
------------------------------------------------------
#!/bin/bash
echo ------BUILDING--------
gcc attack.c -O3 -o attack
echo ------PROCESSING------
./attack sce hashlist.hsh dictionary.dic
------------------------------------------------------
which searches using prefix 'sce' ie kernel etc as words in dic file.

one final note: add a '0x00000000' and '0xffffffff' entries to your hash file. This solves a segfault some people reported.

tested on cygwin here.

Hope some can have some fun with this :))

Any comments/suggestions/inprovements welcome.

Next step for me is looking at optimising the dictionaries for each step.

Guest · Post by **Guest** » Wed Jun 01, 2005 4:47 am

Ok, here is a time comparison with the original.

Using a dictionary of 25 words, and a hash/nid list of 2355, here is the comparison:

original: 298.4 sec
optimized: 3.2 sec

basically, the original is 100 times slower than the one posted here.

It is worth noting, that nearly all of speedup came from optimizing checking the computed hash against the list of 2500 or so nids. That function alone consumed almost 90% of the execution time. Now its virtually non-existant in time.

Post by **mrbrown** » Wed Jun 01, 2005 4:50 am

Great stuff, adresd and gorim. Also, I've been looking a bit into doing a BOINC server/client for this, and this seems like a good base to start from.

adresd · Post by **adresd** » Wed Jun 01, 2005 4:53 am

Thanks for the performance comparison gorim.

Its meant to give people a bit more of a good start, so we arent just wasting time.

Guest · Post by **Guest** » Wed Jun 01, 2005 4:59 am

Is a distributed system really necessary any more ? ;) One fast Pentium 3.0ghz running for a day or much quicker should knock it all out. ;)

Post by **mrbrown** » Wed Jun 01, 2005 5:08 am

Really? Hmm, if that's the case then I'll not worry about it :P. Also it seems the SHA1 algo itself could use some platform-specific optimization, no?

I'd still like to improve this program for stuff like state saving/restoring, multithreading, and perhaps custom rules? It would be nice to have a list of verbs or smaller words to try as prefixes and then the rest of "normal" words.

Post by **mrbrown** » Wed Jun 01, 2005 5:10 am

Also, what optimization flags are you guys using? Drakonite said he got the best results using '-O2 -fomit-frame-pointer', so I use '-O2 -fomit-frame-pointer -march=pentium4' at work. Is -O3 (which turns on aggresive function inlining) worse than -O2 here?

Guest · Post by **Guest** » Wed Jun 01, 2005 5:17 am

Well, I tested with -02 -fno-frame-pointer as well as -03.

At this state, there is virtually no difference brought about by optimization flags... at most there is 0.1-0.2 secs difference.

The best I could get from optimization was turning on the Mac PPC specific flags of -fast -mcpu=7450 which gave 0.5 sec improvement. Which isn't bad... .5 out of 3.2 is still 16% or so. It would add up on a large dictionary.

Drak probably saw an improvement on the original code because it was so slow that anything the compiler did for optimization would help. ;)

Guest · Post by **Guest** » Wed Jun 01, 2005 12:16 pm

gorim wrote:Using a dictionary of 25 words, and a hash/nid list of 2355, here is the comparison:

original: 298.4 sec
optimized: 3.2 sec

basically, the original is 100 times slower than the one posted here.

I forgot to mention this test was ran on a 1.0 Ghz Apple Powerbook and the timings were quite consistant with each run.

Those of you who have 3.0Ghz x86 boxes should have no need of a distributed system. :)

Optimization flags may still matter. As I said, I could get a 16% improvement using them on top of the base optimized code, though its harder to expect more (and actually 16% is damned good) at this point because the code is already about as optmized as it can get. But one needs to play around much more than just -O2/-O3 which are now indistinguishable from each other.

As I implied before, I am thinking the next best improvement can come from some possible vectorization in SHA1Transform() [focused on the ROL() routine which is executed 3-4 times for each R()], which now consumes the highest execution profile in the code. The current implementation is about as optimized as one can get without resorting to vectorization, and even then it doesn't lend well to such.

Currently dictionaries and hash/nid lists should fit comfortably in L1 cache. For systems where they do not, some prefetching may be in order so as to keep the CPU busy.

At best, I reckon another 30%, if lucky, in overall program execution time. Compared to the amount of time it might take to write, test, debug, and profile such code, it may not be a worthwhile time investment.

Those of you who do have 3.0Ghz systems at your disposal, try things out and let us know. 100 times speedup may be plenty. ;)

MrSiir[S] · Post by **MrSiir[S]** » Thu Jun 02, 2005 1:55 am

I am proving the program with the dictionary of the original program of djhuevo and it always fails to me, I have compiled it in a Linux with GCC 3.4.1, here this the result:

Code: Select all

./attack sceHttp sceHttp.hsh sceHttp.dic 
SHA1 hash dictionary attack v1.0 by adresd
based on the original by djhuevo
Reading hash file 'sceHttp.hsh'
Reading dictionary file 'sceHttp.dic'

prefix          &#58; 'sceHttp'
hash count      &#58; 46
dictionary words&#58; 145

Sorting Hashlist
Building Search Tree
Segmentation fault &#40;core dumped&#41;

P.D.: Sorry for my poor english :-)

Post by **mrbrown** » Thu Jun 02, 2005 2:56 am

There's currently a bug in fillsearchtable() as it's building the sorted hash table.

Add 0x00000000 to the top of your hash list, then add 0xffffffff to the bottom of your hash list to fix it.

Post by **Drakonite** » Thu Jun 02, 2005 6:18 am

gorim wrote:Is a distributed system really necessary any more ? ;) One fast Pentium 3.0ghz running for a day or much quicker should knock it all out. ;)

Er... I swear I figured out that the dictionary I had from mrb (for net stuff) would take over a hundred years with the old attack.c, so even if the new attack.c is over a hundred times faster, we'd still be looking at over a year to exaust that word space. Increase the dictionary size by making it a decent attack against all the possible function names and we are again at a huge amount of time and a distributed attack is the only real way to go IMO.

Post by **mrbrown** » Thu Jun 02, 2005 7:07 am

If the SHA1 algorithm is CPU optimized and the search parallelized (for folks with mutiple-CPU boxes) I'm sure we can shave a lot more time off of that.

Guest · Post by **Guest** » Thu Jun 02, 2005 12:56 pm

Drakonite wrote:Er... I swear I figured out that the dictionary I had from mrb (for net stuff) would take over a hundred years with the old attack.c, so even if the new attack.c is over a hundred times faster, we'd still be looking at over a year to exaust that word space.

I was under the impression that the new attack code could go through the dictionary in 12 hours or so on a 1Ghz box, based on adresd's statement he stopped his at 80% completion after 8-9 hours.

Does anyone else have any actual numbers on current runtimes with specific dictionary sizes on specific systems ?

Increase the dictionary size by making it a decent attack against all the possible function names and we are again at a huge amount of time and a distributed attack is the only real way to go IMO.

Well, the key thing is finding the smart way to do it in a distributed manner.

Guest · Post by **Guest** » Thu Jun 02, 2005 12:58 pm

mrbrown wrote:If the SHA1 algorithm is CPU optimized and the search parallelized (for folks with mutiple-CPU boxes) I'm sure we can shave a lot more time off of that.

I found sound SHA1 code that looks a bit more optimized, including some hand-tuned assembly for PPC. I will be testing that out tonight.

It should be easy to code it so that multiple threads (1/cpu) can be fed strings to try...

zigzag · Post by **zigzag** » Thu Jun 02, 2005 2:49 pm

What is the goal here?

Guest · Post by **Guest** » Thu Jun 02, 2005 3:02 pm

zigzag wrote:What is the goal here?

Very simple: within PSP modules, functions are identified by a 32-bit unique identifier, known as a NID.

These NID's are actually partial values of the SHA1 hash of the character string that contains the "name" of that function.

The function name, which is often descriptive enough to understand a fair amount of what the function does, is the unknown quantity.

The task here is: reverse map the known NID to the unknown function name by using brute force dictionary word sequences on possible name strings that are then transformed by SHA1 and comped to the list of currently known NIDs.

There is one minor drawback to this: there are many false positives generated as well. So many hits require a judgement call on its true likelihood.

steddy · Post by **steddy** » Thu Jun 02, 2005 7:26 pm

Am I missing something.

I have a hash count of 13 and a dictionary of 151 words.

It takes above 5 seconds to process each word. This is going to take forever.

Compiled with cygwin and it did report some warnings:

Code: Select all

attack.c&#58;48&#58;65&#58; warning&#58; backslash and newline separated by space
attack.c&#58;53&#58;77&#58; warning&#58; backslash and newline separated by space
attack.c&#58; In function `load_dictionary'&#58;
attack.c&#58;248&#58; warning&#58; passing arg 1 of `strcmp' from incompatible pointer type
attack.c&#58;252&#58; warning&#58; passing arg 1 of `strlen' from incompatible pointer type
attack.c&#58;254&#58; warning&#58; passing arg 2 of `strcpy' from incompatible pointer type
attack.c&#58;528&#58;2&#58; warning&#58; no newline at end of file

Have I screwed up?

Steddy

Post by **pixel** » Thu Jun 02, 2005 8:09 pm

Add -mno-cygwin to compilation maybe...

steddy · Post by **steddy** » Thu Jun 02, 2005 9:09 pm

pixel wrote:Add -mno-cygwin to compilation maybe...

Thanks, but I get the same errors and same speed. How long should it take to check each word on a P4 3.2Ghz with 2Gb of memory?

I also got a false positive with such a small dataset. What is the statistical likelihood of a false find like this?

Cheers
Steddy

adresd · Post by **adresd** » Thu Jun 02, 2005 9:15 pm

False positives very much depend on your dictionary.
For that reason just throwing a BIG dictionary at it is a very bad idea.
Same with a badly picked one as well.

The run that i stopped at 80% was on a dictionary size of 394 words, running on a 1ghz machine.

I would say that about 400 words would take 12-13 hours on 1ghz, hence about 4-5 hours on 3.2ghz, 500 words is more than enough to make a big deal of inroads into the NID list.

The other point is, the word is displays as checking is a toplevel word, so it means checking everything starting with that word. Its more a progress marker than anything, so you can see how far down the dic it has reached.

steddy · Post by **steddy** » Thu Jun 02, 2005 9:21 pm

gorim wrote:Using a dictionary of 25 words, and a hash/nid list of 2355, here is the comparison:

original: 298.4 sec
optimized: 3.2 sec

3.2 seconds for a dictionary of 25 words seems orders of magnitude faster than the results you or I are getting.

I think a big improvement would be for the code to concatenate any combination of upto 3 strings on the end of the prefix. Also, to try capitalizing the words in this order automatically:-

word
Word
WORD

Steddy

adresd · Post by **adresd** » Thu Jun 02, 2005 9:25 pm

thats because the default checks 4 words, or 5 if compiled for it.

Hence
25*25*25*25 = 390,625

versus

151*151*151*151 = 519,885,601

or for me
400*400*400*400 = 25,600,000,000

thats why its orders of magnitude slower, and why dictionary size is so critical :)

steddy · Post by **steddy** » Thu Jun 02, 2005 9:49 pm

Ahhhhh.. that explains it.

Sorry for extending this thread unnecessarily with dumb statements in that case.

Steddy

adresd · Post by **adresd** » Thu Jun 02, 2005 10:29 pm

No problem steddy, I am sure those questions would have come up sooner or later :)

NOTE: for other people, I have updated the code in the first post, with my latest version.. some minor changes to searchtable and rejection handling, nothing critical, but it helps :)

adresd · Post by **adresd** » Fri Jun 03, 2005 7:09 am

Simple easy way to view collisions in the results file.

Copy this:

Code: Select all

<?xml version="1.0"?>
<xsl&#58;stylesheet xmlns&#58;xsl="http&#58;//www.w3.org/TR/WD-xsl">
  <xsl&#58;template match="/">
    <TABLE STYLE="border&#58;0px solid black; width=100%">
      <TR STYLE="font-size&#58;12pt; font-family&#58;Verdana; font-weight&#58;bold; text-decoration&#58;underline">
        <TD STYLE="background-color&#58;lightgrey">Nid</TD>
        <TD>Function Name</TD>
      </TR>
      <xsl&#58;for-each select="NIDFUNCLIST/FUNC" order-by="NID">
        <TR STYLE="font-family&#58;Verdana; font-size&#58;12pt; padding&#58;5px 6px">
          <TD STYLE="background-color&#58;lightgrey"><xsl&#58;value-of select="NID"/></TD>
          <TD><xsl&#58;value-of select="NAME"/></TD>
        </TR>
      </xsl&#58;for-each>
    </TABLE>
  </xsl&#58;template>
</xsl&#58;stylesheet>

to a file called 'resultsdisplay.xsl'

Now add:

Code: Select all

<?xml version="1.0"?>
<?xml&#58;stylesheet type="text/xsl" href="resultsdisplay.xsl" ?>

to the top of the xml file, also make sure the closing element is intact if you interrupted the run, so its a valid xml.

Now open the xml file in webbrowser of your choice to view the nids found, sorted by nid.. making easy collision checking :)

Have fun

djhuevo · Post by **djhuevo** » Sat Jun 04, 2005 2:58 pm

gorim wrote:Ok, here is a time comparison with the original.
Using a dictionary of 25 words, and a hash/nid list of 2355, here is the comparison:

original: 298.4 sec
optimized: 3.2 sec

O___o

You are comparing with the first and buggy version released early in ps2reality.net forums.

That code has a horrible problem as stated in http://www.ps2reality.net/forum/viewtop ... c&start=15
and http://forums.ps2dev.org/viewtopic.php?t=1759 and fixed in
http://pspdev.ofcode.com as "Attack 0.1r2".

I have optimized Attack to be faster than actually, ripping off some parts of the SHA1 algorithm used. But it can be really faster if you tweak some things in asm, especially for little endian machines.

Code: Select all

hashes&#58; 47
dict words&#58; 86
combinations&#58; 4 words

Attack 0.1r2&#58; 100 seconds
adresd Attack&#58; 103 seconds
Attack 0.2&#58; 47 seconds

Code: Select all

hashes&#58; 47
dict words&#58; 37
combination&#58; 5 words

adresd Attack&#58; 129 seconds
Attack 0.2&#58; 58 seconds

Attack 0.2 can be found at http://pspdev.ofcode.com/index.php/attack-02

adresd · Post by **adresd** » Sat Jun 04, 2005 9:43 pm

Please note djheuvo that I was not the one who posted performance figures, I was not after the fastest, merely a lot faster than the one I had.

Congrats on getting it running faster.

Most benefits now with either be in SHA1 algo, or with dic selection imho.

Thanks for sharing your 0.2 version with the forums :)

Guest · Post by **Guest** » Sat Jun 04, 2005 9:50 pm

The competition is on!!!! Those look like some good numbers to beat! :)
*rushes back to tuning SHA1*

(I finally figured out why the ASM code I found wasn't compiling. I hope to have a library of different SHA1 modules available to for ppl to swap in and out soon...)

djhuevo · Post by **djhuevo** » Sun Jun 05, 2005 2:36 am

well, this is not a competition, this for ppl do the thing every time more fast.

talking about sharing: ppl here are talking 2000+ NID list..
anybody can be kindly to sendme it to publish in the API documentation proyect?? :P (i have only 1013)