forums.ps2dev.org

[adresd]

Much congrats to djhuevo on the faster SHA1 algorithm for the search.

I have combined this with a more cache friendly searchtable, the result is here:

[Drakonite]

I just did a bit of performance testing on the new version to work out the best optimization flags.

If it matters, tests were performed on a athlon XP running at 2Ghz with virtually zero cpu usage in the background, compiled with gcc 3.3.5 (except for the icc test which was compiled with icc 7.1) Extra debug output was added to aid timing which ultimately causes a lower speed.

All tests with any optimization level set were around 2 million checks/sec. The difference between the worst (gcc -Os) and best (icc -O2) was about 200,000 checks/sec.

-march=athlon-xp and -fomit-frame-pointers both made large impacts in all cases.
-fomit-frame-pointer increased speed by over 45,500 checks/sec
-march=athlon-xp increased speed by around 10,000 checks/sec

-O2 was faster than -O3 in almost all tests by around 15,000 to 25,000 checks/sec though there was a lot of variance between tests. Possibly an anomoly but worth noting, though -O2 was typically faster, in one of the longer tests -O3 outperformed -O2 by around 10,000 check/sec.

Judging from the high variance in difference between -O2 and -O3 it seems numerous factors, including background processes and dictionary contents, have a noticable impact on the effectiveness of the optimization levels.

adresd reported a 13% decrease in running time on his test case while using -O2 as opposed to -O3 which leads me to believe the extra debug output I added was destroying part of -O2's cache advantage, which means the one case -O3 was faster could likely have been caused by the debug output.

Even without knowing much about it's optimization options icc beat out the best gcc scores by over 100,000 checks/sec.

So in summary, unless you have a binary compiled with icc, 'gcc -O2 -fomit-frame-pointer -march=athlon-xp' (replace athlon-xp with your cpu) should give significantly faster results, at least in most cases.
_________________
Shoot Pixels Not People!
Makeshift Development

[mrbrown]

You can use gprof to give you accurate function-level profiling. Compile nidattack with "gcc -pg <optimizations>" without -fomit-frame-pointer. After your test run has completed, run "gprof -b -Q <path to nidattack executable>" to get the timing results.

In my tests, the fastSHA1() code takes up ~93% of execution time, so it's still the biggest bottleneck.

[Guest]

This added part of fastSHA1 appears (to the eyes) to be destructive:

[loser]

yeh i noticed that in 'release config' in msvc++ it didnt work correctly, but in 'debug config' it did. after adding the memsets to buffer and buffer2 at the top it seemed to work. that was more of a quick fix tho; this part you point out is prolly what really needs fixing

[Warren]

In response to Gorim: that part is in fact a part of the SHA1 spec and is usally done in SHA1_Final. fastSHA1 as a whole looks really weird as it's all of the usual SHA1_* funcs mashed into one func and optimised for 62 char or less buffers. I found that out looking at integrating openSSL's assembly implementation of SHA1 into nidAttack.

[Guest]

Ahh understood now. Thanks! :)

[djhuevo]

[Guest]

Which brings up another thing...

We are doing lots of optimizing mods. It would be good to build in a "test" string analysis so that the program can automatically verify for itself that it will produce correct results.

As I am currently doing some other mods I will take a look at this, but don't let that hold back anyone who wants to do it sooner. :)

[ooPo]

pspdev: the search for a better password cracker

Sheesh. :)

[Guest]

Ok I still have one concern.

The latest code in CVS still produces different results than the code Adresd posted at the beginning of this topic. (as of last night's cvs version).

Basically, given the same test dictionary of 40-50 words, hashlist, and prefix, run against both programs, they find completely different hits.

Could someone else please check if they can see the same thing I am ? I am concerned about this inconsistancy...

[adresd]

I have been concerned by recent events. So started digging.

The result is here is a new version to try.

Added:
-Sanity check to SHA1 algos on startup, runtime, to make sure the return values are valid.
-Added a seperate dictionary for the 'firstword' of each string.
-nidstatus.tmp file, to track progress through firstword dictionary. Delete this file to restart a run.
-Resume function tied to above, starts at the word after the last fully completed word in the firstword dictionary.
-Splitting of results into seperate files for each firstword.
-Optional check, on #define to skip already present results files, to re-run one, simply remove or rename the file, then rerun.
-Now uses the opted SHA1 for strings under 55 chars (pointed out by djhuevo), and the reference one for strings over that length.

Commandline params are now:
<hash_list> <dictionaryfirst> <dictionarymain> [prefix]

prefix being optional.

dictionaryfirst is the firstword dictionary, and dictionarymain is the dictionary used for the later words in the string..
This dramatically cuts down the searchspace and time, and given most prefixes are amongst a small list, should aid the effort somewhat.

If run with no params, it will run the sanity check and display the result.

Thanks go to Drakonite for helping with debugging/testing.

[Guest]

Ok. I think the cause of my problem are endian issues. As always, I seem to be the first to try stuff on big-endian boxes. ;)

I will get back with y'all after the seek and destroy mission. Plus I hope to merge some more optimizations back in...

[mrbrown]

Note to those scrambling to find function names:

In case you missed it a NID is a 32-bit SHA1 hash value used to dynamically link functions and variables into a program. The majority of the time this hash value corresponds to the function name it belongs to, so sceUtilityGameSharingUpdate == 0x7853182D.

Because a NID is just a unique identifer within a library, it can be any value whatsoever, as long as the program refers to that function with the same NID. This means that NIDs do not have to correspond 1:1 with the real world function name. Sony can randomly generate NIDs and attach any function they want, and we'll never be able to figure out the real function name.

Just a heads up in case folks get stuck. I have yet to crack any of the NIDs found in the VSH modules. Has anyone else?

[loser]

wow newest version of sha1 attack goes really fast!
good work guys

sometimes i just want to check what the Nid would be for a function name without doing whole dictionary search things. i put up a html page to do this quickly and easily. this page calculates the Nid in javascript, so you should be able to save it locally to run it from your computer.

http://www.internalreality.com/nid.html

[PspPet]

> while ((hash[hashpos3++]&0xffffff00) < searchval);
BUG: no range checking on the 'hash' array. Applies to all 3 searches, and all versions.
May or may not bite you (depends on system memory management and luck and what garbage memory is past the end of the array)

Fix/Workaround (keeping the searches fast).
Change:
< hash = (unsigned int*)malloc(hash_count * sizeof(unsigned int));
To:
> hash = (unsigned int*)malloc((hash_count+1) * sizeof(unsigned int));
> hash[hash_count] = 0xFFFFFFFF; // end marker

[Inopia]

Hmm, has anyone of you guys even seen this?

http://www.antsight.com/zsl/rainbowcrack/

It's a generic method of reversing hashing algorithms such as sha1 and md5 by creating a huge-ass table. It can crack md5, as mr-t would put it, 'helluva fast'. You need to create a 300mb table first though, takes only a couple of hours :) It can be used to crack large quantities of hashes however.
Minor drawback is that the algorithm cannot guarantee a 100% succes rate on every hash because of the way the table is built.
Anyway, there's sourcecode that includes sha1, md5 and the thing can be extended to work with other algorithms if you please. The site also includes a paper on how it all works.

Perhaps you guys can use it :)
_________________
what is love, beep beep

[adresd]

Here is the latest version of the attack program.

Main change is: Big endian issues sorted, and now passing all sanity checks on both big and little endian.

for msvc and icc , change '__inline__' to '__inline'.
Thanks to loser and warren for this.

Thanks also to gorim for big endian testing.

[florinsasu]

...a bit late to add this to this thread :)

[PspPet]

> Here is the latest version of the attack program.
Please incorporate the hash[] array bug fix mentioned above (or something similar) . The latest version still has this problem (crashes on me 100% of the time without it -- VC6 -Ot)

For people still having problems with the VC debug/release options, apply the fix yourself and your problem will hopefully go away.

The current version may not crash for you depending on memory randomness. Even if it doesn't crash, it may make the algorithm run slower than it should (in unpredicatable ways)

[PspPet]

mrbrown wrote:
>I have yet to crack any of the NIDs found in the VSH modules. Has anyone else?

Just started looking into the VSH modules. Lots of good stuff there.
Found a few NIDs -- searching for more now (fortunately it appears they use the same technique)
The trick, as always is finding the prefix they use. "sceSystem" appears to be used for the shared utilities.

eg: "sceSystemFileLoadAll" in module sceVshCommonUtil (and a bunch of other "sceSystemFile*" helpers)
More to come when I get a more complete list. I guess the database will have to be expanded for these modules too.

[mrbrown]

Yeah, I have the sceSystem ones found when looking at a plaintext vsh module. I also have vsh* from vshbridge, which match the same names with an sce prefix, i.e. vshKernelLoadModule for sceKernelLoadModule.

Guess we'll have to crack the whip to get our big NID list out the door. There's way too much duplication going on :).

Now if you have some names from scePaf, we need to talk :). I've even thought about setting up a bounty for those.

[PspPet]

> Guess we'll have to crack the whip to get our big NID list out the door. There's way too much duplication going on :).

How about placing them in the public database ? http://pspdev.ofcode.com/api.php
(or at least post them on the "Library function list" thread and someone will move them over)

FWIW: that's what I've been doing lately, and then automatically grab all the entries from the web and reformat it to a simple text file (for disassembler use).

[mrbrown]

We have a huge XML file that we use to keep track of NIDs. Without an automated script it would take too long to add those NIDs using a web interface.

[PspPet]

FWIW: There is an automated way of adding hundreds of entries at once (you need a login ID). Checks the SHA1 values and reports if the names are new or old
[those reports "neofar" posts in the other top sticky thread]

I just did that myself (converting my discovered entries from disassembler format to the trivial web input format for posting)
FWIW2: My name dictionary is pretty small and I came up with about 200 new names, which tells me the public database is far from complete. ie. still some low hanging fruit.
Now with VSH NIDs and others to look for there is more work to do!