I have combined this with a more cache friendly searchtable, the result is here:
Code: Select all
Edited - see below for newer version of code
Have fun.
SHA1 Attack Program
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:
loser pointed out that for msvc++ you may also need time.h and malloc.h, see the comments in the code.
Have fun.
I have combined this with a more cache friendly searchtable, the result is here:
Have fun.
Last edited by adresd on Tue Jun 14, 2005 12:44 am, edited 1 time in total.
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.
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
Makeshift Development
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.
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:
Since every single character of buffer[] is significant to the outcome of the SHA1 transform, this should by all rights be destructive, completely changing every character of the the resulting transform.
But supposedly people are seeing no problems with fastSHA1 as a result. Can anyone explain why this was added to the recent code ?
Code: Select all
buffer[len]=0x80;
buffer[62]=(len*8)>>8;
buffer[63]=(len*8)&0xff; But supposedly people are seeing no problems with fastSHA1 as a result. Can anyone explain why this was added to the recent code ?
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.
this fast implementation has the limitation of hash upto 55 characters.gorim wrote: But supposedly people are seeing no problems with fastSHA1 as a result. Can anyone explain why this was added to the recent code ?
buffers longer than 55 bytes are hashed wrong...
Last edited by djhuevo on Tue Jun 07, 2005 2:04 pm, edited 1 time in total.
sobreviviendo en la tierra de los trolldev
-
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. :)
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. :)
-
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...
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...
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.
Have fun.
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.
Code: Select all
Edited - see below for newer version of code
Last edited by adresd on Tue Jun 14, 2005 12:45 am, edited 1 time in total.
-
Guest
Don't overexert yourself.
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?
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?
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
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
> 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
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
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 :)
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
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.
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.
Code: Select all
/*
SHA1 dictionary attack program v5.4 (c) 2005 adresd
based on original by djhuevo
Hash searchtable and other mods by adresd
Endian independant now, with sanity checks verified on both settings
No License, public domain, do as you want, no warranties
*/
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <malloc.h>
#include <stdlib.h>
// Comment this out for BIG endian machines
#define LITTLE_ENDIANESS
// This enables using both routines, if not enabled it will use the opted one as default
#define USEBOTHSHA1ROUTINES
// These are the sanity checks at startup
#define NEW_SHA1_CHECK
#define OLD_SHA1_CHECK
// This overrides all others, and forces using the reference implementation ALWAYS
//#define FORCE_USE_SLOW
// This forces skipping over words with an existing result file
//#define SKIP_EXISTING
#ifdef FORCE_USE_SLOW
#undef NEW_SHA1_CHECK
#endif
typedef char s8;
typedef short s16;
typedef int s32;
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned int u32;
//
// This is the original REFERENCE SHA-1 Algorithm
//
typedef struct {
unsigned long state[5];
unsigned long count[2];
unsigned char buffer[64];
} SHA1_CTX;
void SHA1Transform(unsigned long state[5], unsigned char buffer[64]);
void SHA1Init(SHA1_CTX* context);
void SHA1Update(SHA1_CTX* context, unsigned char* data, unsigned int len);
void SHA1Final(unsigned char digest[20], SHA1_CTX* context);
#define rol(value, bits) (((value) << (bits)) | ((value) >> (32 - (bits))))
/* blk0() and blk() perform the initial expand. */
/* I got the idea of expanding during the round function from SSLeay */
#ifdef LITTLE_ENDIANESS
#define blk0(i) (block->l[i] = (rol(block->l[i],24)&0xFF00FF00) \
|(rol(block->l[i],8)&0x00FF00FF))
#else
#define blk0(i) block->l[i]
#endif
#define blk(i) (block->l[i&15] = rol(block->l[(i+13)&15]^block->l[(i+8)&15] \
^block->l[(i+2)&15]^block->l[i&15],1))
/* (R0+R1), R2, R3, R4 are the different operations used in SHA1 */
#define R0(v,w,x,y,z,i) z+=((w&(x^y))^y)+blk0(i)+0x5A827999+rol(v,5);w=rol(w,30);
#define R1(v,w,x,y,z,i) z+=((w&(x^y))^y)+blk(i)+0x5A827999+rol(v,5);w=rol(w,30);
#define R2(v,w,x,y,z,i) z+=(w^x^y)+blk(i)+0x6ED9EBA1+rol(v,5);w=rol(w,30);
#define R3(v,w,x,y,z,i) z+=(((w|x)&y)|(w&x))+blk(i)+0x8F1BBCDC+rol(v,5);w=rol(w,30);
#define R4(v,w,x,y,z,i) z+=(w^x^y)+blk(i)+0xCA62C1D6+rol(v,5);w=rol(w,30);
/* Hash a single 512-bit block. This is the core of the algorithm. */
__inline__ void SHA1Transform(unsigned long state[5], unsigned char buffer[64])
{
unsigned long a, b, c, d, e;
typedef union {
unsigned char c[64];
unsigned long l[16];
} CHAR64LONG16;
CHAR64LONG16* block;
#ifdef SHA1HANDSOFF
static unsigned char workspace[64];
block = (CHAR64LONG16*)workspace;
memcpy(block, buffer, 64);
#else
block = (CHAR64LONG16*)buffer;
#endif
/* Copy context->state[] to working vars */
a = state[0];
b = state[1];
c = state[2];
d = state[3];
e = state[4];
/* 4 rounds of 20 operations each. Loop unrolled. */
R0(a,b,c,d,e, 0); R0(e,a,b,c,d, 1); R0(d,e,a,b,c, 2); R0(c,d,e,a,b, 3);
R0(b,c,d,e,a, 4); R0(a,b,c,d,e, 5); R0(e,a,b,c,d, 6); R0(d,e,a,b,c, 7);
R0(c,d,e,a,b, 8); R0(b,c,d,e,a, 9); R0(a,b,c,d,e,10); R0(e,a,b,c,d,11);
R0(d,e,a,b,c,12); R0(c,d,e,a,b,13); R0(b,c,d,e,a,14); R0(a,b,c,d,e,15);
R1(e,a,b,c,d,16); R1(d,e,a,b,c,17); R1(c,d,e,a,b,18); R1(b,c,d,e,a,19);
R2(a,b,c,d,e,20); R2(e,a,b,c,d,21); R2(d,e,a,b,c,22); R2(c,d,e,a,b,23);
R2(b,c,d,e,a,24); R2(a,b,c,d,e,25); R2(e,a,b,c,d,26); R2(d,e,a,b,c,27);
R2(c,d,e,a,b,28); R2(b,c,d,e,a,29); R2(a,b,c,d,e,30); R2(e,a,b,c,d,31);
R2(d,e,a,b,c,32); R2(c,d,e,a,b,33); R2(b,c,d,e,a,34); R2(a,b,c,d,e,35);
R2(e,a,b,c,d,36); R2(d,e,a,b,c,37); R2(c,d,e,a,b,38); R2(b,c,d,e,a,39);
R3(a,b,c,d,e,40); R3(e,a,b,c,d,41); R3(d,e,a,b,c,42); R3(c,d,e,a,b,43);
R3(b,c,d,e,a,44); R3(a,b,c,d,e,45); R3(e,a,b,c,d,46); R3(d,e,a,b,c,47);
R3(c,d,e,a,b,48); R3(b,c,d,e,a,49); R3(a,b,c,d,e,50); R3(e,a,b,c,d,51);
R3(d,e,a,b,c,52); R3(c,d,e,a,b,53); R3(b,c,d,e,a,54); R3(a,b,c,d,e,55);
R3(e,a,b,c,d,56); R3(d,e,a,b,c,57); R3(c,d,e,a,b,58); R3(b,c,d,e,a,59);
R4(a,b,c,d,e,60); R4(e,a,b,c,d,61); R4(d,e,a,b,c,62); R4(c,d,e,a,b,63);
R4(b,c,d,e,a,64); R4(a,b,c,d,e,65); R4(e,a,b,c,d,66); R4(d,e,a,b,c,67);
R4(c,d,e,a,b,68); R4(b,c,d,e,a,69); R4(a,b,c,d,e,70); R4(e,a,b,c,d,71);
R4(d,e,a,b,c,72); R4(c,d,e,a,b,73); R4(b,c,d,e,a,74); R4(a,b,c,d,e,75);
R4(e,a,b,c,d,76); R4(d,e,a,b,c,77); R4(c,d,e,a,b,78); R4(b,c,d,e,a,79);
/* Add the working vars back into context.state[] */
state[0] += a;
state[1] += b;
state[2] += c;
state[3] += d;
state[4] += e;
/* Wipe variables */
a = b = c = d = e = 0;
}
/* SHA1Init - Initialize new context */
__inline__ void SHA1Init(SHA1_CTX* context)
{
/* SHA1 initialization constants */
context->state[0] = 0x67452301;
context->state[1] = 0xEFCDAB89;
context->state[2] = 0x98BADCFE;
context->state[3] = 0x10325476;
context->state[4] = 0xC3D2E1F0;
context->count[0] = context->count[1] = 0;
}
/* Run your data through this. */
__inline__ void SHA1Update(SHA1_CTX* context, unsigned char* data, unsigned int len)
{
unsigned int i, j;
j = (context->count[0] >> 3) & 63;
if ((context->count[0] += len << 3) < (len << 3)) context->count[1]++;
context->count[1] += (len >> 29);
if ((j + len) > 63) {
memcpy(&context->buffer[j], data, (i = 64-j));
SHA1Transform(context->state, context->buffer);
for ( ; i + 63 < len; i += 64) {
SHA1Transform(context->state, &data[i]);
}
j = 0;
}
else i = 0;
memcpy(&context->buffer[j], &data[i], len - i);
}
/* Add padding and return the message digest. */
__inline__ void SHA1Final(unsigned char digest[20], SHA1_CTX* context)
{
unsigned long i, j;
unsigned char finalcount[8];
for (i = 0; i < 8; i++) {
finalcount[i] = (unsigned char)((context->count[(i >= 4 ? 0 : 1)]
>> ((3-(i & 3)) * 8) ) & 255); /* Endian independent */
}
SHA1Update(context, (unsigned char *)"\200", 1);
while ((context->count[0] & 504) != 448) {
SHA1Update(context, (unsigned char *)"\0", 1);
}
SHA1Update(context, finalcount, 8); /* Should cause a SHA1Transform() */
for (i = 0; i < 20; i++) {
digest[i] = (unsigned char)
((context->state[i>>2] >> ((3-(i & 3)) * 8) ) & 255);
}
/* Wipe variables */
i = j = 0;
memset(context->buffer, 0, 64);
memset(context->state, 0, 20);
memset(context->count, 0, 8);
memset(&finalcount, 0, 8);
#ifdef SHA1HANDSOFF /* make SHA1Transform overwrite it's own static vars */
SHA1Transform(context->state, context->buffer);
#endif
}
__inline__ unsigned int hashSHA1(char *buffer, SHA1_CTX *context, int size)
{
unsigned char digest[20];
SHA1Init(context);
SHA1Update(context, buffer, size);
SHA1Final(digest, context);
#ifdef LITTLE_ENDIANESS
return *((unsigned int *)digest);
#else
{ // Swap the bytes around
unsigned int temp = *((unsigned int *)digest);
return ( ((temp&0xff000000)>>24) | ((temp&0x00ff0000)>>8) | ((temp&0x0000ff00)<<8) | ((temp&0x000000ff)<<24) );
}
#endif
}
SHA1_CTX context;
//
// This is the OPTIMISED SHA-1 Algorithm
//
/*
SHA-1 based on Steve Reid SHA1 code <steve@edmweb.com>
*/
#define o_rol(value, bits) (((value) << (bits)) | ((value) >> (32 - (bits))))
/* blk0() and blk() perform the initial expand. */
/* I got the idea of expanding during the round function from SSLeay */
#ifdef LITTLE_ENDIANESS
#define o_blk0(i) (block[i] = (o_rol(block[i],24)&0xFF00FF00) \
|(o_rol(block[i],8)&0x00FF00FF))
#else
#define o_blk0(i) block[i]
#endif
#define o_blk(i) (block[i&15] = o_rol(block[(i+13)&15]^block[(i+8)&15] \
^block[(i+2)&15]^block[i&15],1))
/* (R0+R1), R2, R3, R4 are the different operations used in SHA1 */
#define o_R0(v,w,x,y,z,i) z+=((w&(x^y))^y)+o_blk0(i)+0x5A827999+o_rol(v,5);w=o_rol(w,30);
#define o_R1(v,w,x,y,z,i) z+=((w&(x^y))^y)+o_blk(i)+0x5A827999+o_rol(v,5);w=o_rol(w,30);
#define o_R2(v,w,x,y,z,i) z+=(w^x^y)+o_blk(i)+0x6ED9EBA1+o_rol(v,5);w=o_rol(w,30);
#define o_R3(v,w,x,y,z,i) z+=(((w|x)&y)|(w&x))+o_blk(i)+0x8F1BBCDC+o_rol(v,5);w=o_rol(w,30);
#define o_R4(v,w,x,y,z,i) z+=(w^x^y)+o_blk(i)+0xCA62C1D6+o_rol(v,5);w=rol(w,30);
u32 fastSHA1(unsigned char *buffer,int len) {
u8 buf[64];
s32 i;
u32 a, b, c, d, e;
u32 *block;
int len2;
len2 = len;
if (len2 > 63) len2 = 63;
memcpy(buf, buffer, len2);
block=(u32 *)buf;
for(i=len2; i<=63; i++) {
buf[i]=0x00;
}
buf[len2]=0x80;
buf[62]=(len2*8)>>8;
buf[63]=(len2*8)&0xff;
a = 0x67452301;
b = 0xEFCDAB89;
c = 0x98BADCFE;
d = 0x10325476;
e = 0xC3D2E1F0;
/* 4 rounds of 20 operations each. Loop unrolled. */
o_R0(a,b,c,d,e, 0); o_R0(e,a,b,c,d, 1); o_R0(d,e,a,b,c, 2); o_R0(c,d,e,a,b, 3);
o_R0(b,c,d,e,a, 4); o_R0(a,b,c,d,e, 5); o_R0(e,a,b,c,d, 6); o_R0(d,e,a,b,c, 7);
o_R0(c,d,e,a,b, 8); o_R0(b,c,d,e,a, 9); o_R0(a,b,c,d,e,10); o_R0(e,a,b,c,d,11);
o_R0(d,e,a,b,c,12); o_R0(c,d,e,a,b,13); o_R0(b,c,d,e,a,14); o_R0(a,b,c,d,e,15);
o_R1(e,a,b,c,d,16); o_R1(d,e,a,b,c,17); o_R1(c,d,e,a,b,18); o_R1(b,c,d,e,a,19);
o_R2(a,b,c,d,e,20); o_R2(e,a,b,c,d,21); o_R2(d,e,a,b,c,22); o_R2(c,d,e,a,b,23);
o_R2(b,c,d,e,a,24); o_R2(a,b,c,d,e,25); o_R2(e,a,b,c,d,26); o_R2(d,e,a,b,c,27);
o_R2(c,d,e,a,b,28); o_R2(b,c,d,e,a,29); o_R2(a,b,c,d,e,30); o_R2(e,a,b,c,d,31);
o_R2(d,e,a,b,c,32); o_R2(c,d,e,a,b,33); o_R2(b,c,d,e,a,34); o_R2(a,b,c,d,e,35);
o_R2(e,a,b,c,d,36); o_R2(d,e,a,b,c,37); o_R2(c,d,e,a,b,38); o_R2(b,c,d,e,a,39);
o_R3(a,b,c,d,e,40); o_R3(e,a,b,c,d,41); o_R3(d,e,a,b,c,42); o_R3(c,d,e,a,b,43);
o_R3(b,c,d,e,a,44); o_R3(a,b,c,d,e,45); o_R3(e,a,b,c,d,46); o_R3(d,e,a,b,c,47);
o_R3(c,d,e,a,b,48); o_R3(b,c,d,e,a,49); o_R3(a,b,c,d,e,50); o_R3(e,a,b,c,d,51);
o_R3(d,e,a,b,c,52); o_R3(c,d,e,a,b,53); o_R3(b,c,d,e,a,54); o_R3(a,b,c,d,e,55);
o_R3(e,a,b,c,d,56); o_R3(d,e,a,b,c,57); o_R3(c,d,e,a,b,58); o_R3(b,c,d,e,a,59);
o_R4(a,b,c,d,e,60); o_R4(e,a,b,c,d,61); o_R4(d,e,a,b,c,62); o_R4(c,d,e,a,b,63);
o_R4(b,c,d,e,a,64); o_R4(a,b,c,d,e,65); o_R4(e,a,b,c,d,66); o_R4(d,e,a,b,c,67);
o_R4(c,d,e,a,b,68); o_R4(b,c,d,e,a,69); o_R4(a,b,c,d,e,70); o_R4(e,a,b,c,d,71);
o_R4(d,e,a,b,c,72); o_R4(c,d,e,a,b,73); o_R4(b,c,d,e,a,74); o_R4(a,b,c,d,e,75);
o_R4(e,a,b,c,d,76); o_R4(d,e,a,b,c,77); o_R4(c,d,e,a,b,78); o_R4(b,c,d,e,a,79);
a+=0x67452301;
// Swap the bytes around
return (a>>24)|((a>>8)&0xff00)|((a<<8)&0xff0000)|((a<<24));
}
typedef struct {
char **dict;
char *dict_member_length;
int dict_count;
} dictionary_struct;
dictionary_struct dicfirstword,dicmain;
unsigned int *hash;
int hash_count;
int load_hash_list(char *filename)
{
int i;
unsigned int t;
FILE *fp;
printf("Reading hash file '%s'\n", filename);
if ((fp = fopen(filename, "rt")) == NULL)
return -1;
hash_count = 0;
while (fscanf(fp, "0x%x\n", &t) == 1)
hash_count++;
printf("hash_count = %d\n", hash_count);
fseek(fp, 0, SEEK_SET);
hash = malloc(hash_count * sizeof(unsigned int));
i = 0;
while (fscanf(fp, "0x%x\n", &hash[i++]) == 1);
fclose(fp);
return 0;
}
int load_dictionary(dictionary_struct *dic,char *filename)
{
int i;
char buffer[0x200];
FILE *fp;
printf("Reading dictionary file '%s'\n", filename);
if ((fp = fopen(filename, "rt")) == NULL)
return -1;
dic->dict_count = 0;
while (fscanf(fp, "%s\n", buffer) != EOF)
dic->dict_count++;
printf("dict_count = %d\n", dic->dict_count);
fseek(fp, 0, SEEK_SET);
dic->dict = (char **) malloc(dic->dict_count * sizeof(char *));
dic->dict_member_length = malloc(dic->dict_count);
i = 0;
while (fscanf(fp, "%s\n", buffer) == 1) {
if ((buffer[0] == '-') || (buffer[0] == '/')) { // This handles comments in the dic file
} else { // Not a comment, so do duplicate check
int count;
int found = 0;
for (count = 0; count < (i - 1); count++)
if (strcmp(buffer, dic->dict[count]) == 0)
found = 1;
if (found == 0) { // If not already in dictionary, then add
dic->dict_member_length[i] = strlen(buffer);
dic->dict[i] = malloc(dic->dict_member_length[i] + 1);
strcpy(dic->dict[i], buffer);
i++;
}
}
}
dic->dict_count = i;
fclose(fp);
return 0;
}
FILE *fout;
// Hash seems to be where the program spends most of its time, so we need to speedup the
// search somehow - 32 bit value, 4 bytes
// what we do, is pre-sort the hashlist, so they are in order AABBCCDD
// Then index each byte into the list, hence cutting down the search space considerably
#define VER2_SIZE 256
// midsearch should hopefully fit in cache, so will help quite a lot with rejection testing.
int midsearch[VER2_SIZE*VER2_SIZE];
// bigsearch is really a cop out, will not fit in cache, but still quicker than checking many elements.
int bigsearch[VER2_SIZE*VER2_SIZE*VER2_SIZE];
void fillsearchtable()
{
unsigned int searchval;
int hashpos,hashpos2,hashpos3;
int count,count2,count3;
int found = 1;
// Firstly Sort the hashlist, order AABBCCDD
printf("Sorting Hashlist\n");
while (found == 1) {
found = 0;
for (count=0;count<(hash_count-1);count++) {
if (hash[count] > hash[count+1]) { // swap entries if wrong way around
unsigned int temp = hash[count+1];
hash[count+1] = hash[count];
hash[count] = temp;
found = 1;
}
}
}
// Really lazy slow clear array, but who cares only done once
printf("Clearing Search Tree\n");
for (count=0;count<(VER2_SIZE*VER2_SIZE);count++)
midsearch[count] = -1;
for (count=0;count<(VER2_SIZE*VER2_SIZE*VER2_SIZE);count++)
bigsearch[count] = -1;
// Now build the toplevel (first) byte
printf("Building Search Tree\n");
for (count=0;count<256;count++) { // Find the first firstbyte in the hashlist that matches this value
hashpos = 0;
searchval = (count<<24);
while ((hash[hashpos++]&0xff000000) < searchval);
hashpos--;
if ((hash[hashpos]&0xff000000) == searchval) { // Now Search for a twobyte combo
for (count2=0;count2<256;count2++) { // Find the first secondbyte in the hashlist from this pos
hashpos2 = hashpos;
searchval = (count<<24) | (count2<<16);
while ((hash[hashpos2++]&0xffff0000) < searchval);
hashpos2--;
if ((hash[hashpos2]&0xffff0000) == searchval) { // Add this entry
midsearch[(count<<8)+count2] = hashpos2;
// Now Search for a threebyte combo
for (count3=0;count3<256;count3++) { // Find the first thirdbyte in the hashlist from this pos
hashpos3 = hashpos2;
searchval = (count<<24) | (count2<<16) | (count3<<8);
while ((hash[hashpos3++]&0xffffff00) < searchval);
hashpos3--;
if ((hash[hashpos3]&0xffffff00) == searchval)
{ // Add this entry
bigsearch[(count<<16)+(count2<<8)+count3] = hashpos2;
} } } } } } }
int findhash(char *buffer, int size)
{
unsigned int hashvalue;
int pos;
#ifdef FORCE_USE_SLOW
hashvalue = hashSHA1(buffer,&context, size);
#else
#ifdef USEBOTHSHA1ROUTINES
if (size < 55) // If small string, use the optimised version
hashvalue = fastSHA1(buffer, size);
else // else use the standard reference implementation
hashvalue = hashSHA1(buffer,&context, size);
#else
hashvalue = fastSHA1(buffer, size);
#endif
#endif
// get twobyte position
pos = midsearch[(hashvalue &0xffff0000)>>16];
if (pos != -1) { // Get threebyte position
pos = bigsearch[(hashvalue &0xffffff00)>>8];
if (pos != -1) { // Found a position, so search from here
int h;
for(h=pos; h<hash_count; h++) {
if (hashvalue >= hash[h])
if(hashvalue == hash[h]) { // If equal, found
printf("0x%08x %s\n",hashvalue,buffer);
fprintf(fout,"<FUNC><NID>0x%08x</NID><NAME>%s</NAME></FUNC>\n",hashvalue,buffer);
return 1;
}
else // If not, reject as above
return 0;
} } }
return 0;
}
int sanity_SHA1(char *teststring, unsigned int testhash)
{
// As a first task, perform a sanity check, verify SHA1 routines
unsigned int hashvalue1;
unsigned int hashvalue2;
unsigned int size;
int failed = 0;
size= strlen(teststring);
printf("Running SHA1 Check : '%s'(%d) ",teststring,size);
#ifdef OLD_SHA1_CHECK
// Check reference version
hashvalue2 = hashSHA1(teststring,&context, size);
if (hashvalue2 != testhash) {
printf("\nReference Version Failed Sanity Check (0x%08X)\n",hashvalue2);
failed = 1;
}
#endif
#ifdef NEW_SHA1_CHECK
// Check optimized version
hashvalue1 = fastSHA1(teststring, size);
if (hashvalue1 != testhash) {
printf("\nOptimised Version Failed Sanity Check (0x%08X)\n",hashvalue1);
failed = 1;
}
#endif
#ifdef NEW_SHA1_CHECK
#ifdef OLD_SHA1_CHECK
// Both Together, so check against each other
if (hashvalue1 != hashvalue2) {
printf("\nSHA1 return values differ (0x%08X),(0x%08X)\n",hashvalue1,hashvalue2);
failed = 1;
}
#endif
#endif
if (failed == 0)
printf("- Sanity Check Passed\n");
else
printf("- Sanity Check Failed, should be 0x%08X\n",testhash);
return failed;
}
int main(int argc, char **argv)
{
int i;
int x, y, z, zz;
int firstword;
char buffer[0x200];
time_t start, end;
time_t start2, end2;
char xmlfilename[200];
char *ptr, *ptr0, *ptr1, *ptr2, *ptr3;
char *prefix = "";
int prefixlen = 0;
printf("SHA1 hash dictionary attack v5.4 by adresd\n");
printf("based on the original by djhuevo\n\n");
if (argc == 2) {
unsigned int hash;
unsigned char *ptr = argv[1];
int length = strlen(ptr);
#ifdef FORCE_USE_SLOW
hash = hashSHA1(ptr,&context, length);
#else
#ifdef USEBOTHSHA1ROUTINES
if (length > 55)
hash = hashSHA1(ptr,&context, length);
else
hash = fastSHA1(ptr, length);
#else
hash = fastSHA1(ptr, length);
#endif
#endif
printf("Input string '%s' - hash 0x%08X\n",ptr,hash);
return(0);
}
{ // Perform the sanity checks
int failed = 0; // All test hashes under 55 chars so can check both old and new vers of SHA1 algo
failed += sanity_SHA1("MyTestString",0x0CC01ABB);
failed += sanity_SHA1("abc",0x363E99A9);
failed += sanity_SHA1("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopn",0x2d96FE59);
failed += sanity_SHA1("This!is+another_test*string$zebra@~}{@!!£'$^&*()[]{}=",0x4916E3FD);
if (failed > 0)
{
printf("\n\nFAILED SANITY CHECK!!!\n\n");
exit(1);
}
printf("\n");
}
if (argc < 3) {
printf("usage:\n\t%s <hash_list> <dictionaryfirst> <dictionarymain> [prefix]\n", argv[0]);
return 1;
}
if (load_hash_list(argv[1]) < 0) {
fprintf(stderr, "can't open the hash file %s\n", argv[1]);
return 2;
}
if (load_dictionary(&dicfirstword,argv[2]) < 0) {
fprintf(stderr, "can't open the first word dictionary file %s\n", argv[2]);
return 3;
}
if (load_dictionary(&dicmain,argv[3]) < 0) {
fprintf(stderr, "can't open the main dictionary file %s\n", argv[3]);
return 3;
}
if (argc > 4) {
prefix = argv[4];
strcpy(buffer, prefix);
prefixlen = strlen(prefix);
}
if (hash_count < 1 || dicmain.dict_count < 1 || dicfirstword.dict_count < 1) {
fprintf(stderr, "error on input data.\n");
fprintf(stderr, "hash_count = %d, dict_count = %d, dict_count = %d\n", hash_count, dicmain.dict_count,dicfirstword.dict_count);
return 4;
}
#ifdef FORCE_USE_SLOW
printf("Forcing using REFERENCE SHA1 algo\n");
#endif
printf("\nprefix : '%s'\n", prefix != "" ? prefix : "<None>");
printf("hash count : %d\n", hash_count);
printf("dictionary words (firstword) : %d\n", dicfirstword.dict_count);
printf("dictionary words (main) : %d\n\n", dicmain.dict_count);
fillsearchtable();
firstword = 0;
{ // Check for resuming a run
FILE *fpt;
if ((fpt = fopen("nidstatus.tmp", "rt")) != NULL) {
char bufferstr[200];
fscanf(fpt,"%s",bufferstr);
fclose(fpt);
// Now find the string in dic
for (x = 0; x < dicfirstword.dict_count; x++) {
if (strcmp(dicfirstword.dict[x],bufferstr) == 0)
firstword = x + 1; // Match, so select next word
}
if (firstword == 0) { // means we had a status file, but the word doesnt match
printf("\nResume file contains invalid word, please remove\n");
exit(1);
}
if (firstword != 0)
printf("\nResuming from : %s\n",dicfirstword.dict[firstword]);
} }
printf("\nsearching...\n\n");
fflush(stdout);
time(&start);
ptr = buffer + prefixlen;
// First Word
for (x = firstword; x < dicfirstword.dict_count; x++) {
time(&start2);
ptr0 = ptr;
for (i = 0; i < dicfirstword.dict_member_length[x]; i++) {
*(ptr0++) = dicfirstword.dict[x][i];
}
*(ptr0) = 0;
printf("// processing word: %s\n", buffer);
sprintf(xmlfilename,"results_%s.xml",buffer);
#ifdef SKIP_EXISTING
// Open results file for this word, see if it already exists
if ((fout = fopen(xmlfilename,"rt")) > 0) { // Output file exists
printf("Skipping Word : %s - Output Exists\n",buffer);
fclose(fout);
}
else
#endif
{ // Open the results file, ready for writing
printf("// opening results file : %s\n",xmlfilename);
if ((fout = fopen(xmlfilename, "wt")) <= 0) {
printf("Failed to open output file\n");
exit(1);
}
fprintf(fout,"<NIDFUNCLIST>\n");
fflush(stdout);
// Second word
for (y = 0; y < dicmain.dict_count; y++) {
ptr1 = ptr0;
for (i = 0; i < dicmain.dict_member_length[y]; i++) {
*(ptr1++) = dicmain.dict[y][i];
}
*(ptr1) = 0;
//printf("// processing word: %s\n",buffer);
// Only do next loop if first and second dont match
if (strcmp(dicmain.dict[x], dicmain.dict[y]) != 0) {
// Third Word
for (z = 0; z < dicmain.dict_count; z++) {
ptr2 = ptr1;
for (i = 0; i < dicmain.dict_member_length[z]; i++) {
*(ptr2++) = dicmain.dict[z][i];
}
// Only do next loop if second and third dont match
if (strcmp(dicmain.dict[y], dicmain.dict[z]) != 0) {
// Fourth Word
for (zz = 0; zz < dicmain.dict_count; zz++) {
ptr3 = ptr2;
for (i = 0; i < dicmain.dict_member_length[zz]; i++) {
*(ptr3++) = dicmain.dict[zz][i];
}
#if 0
// Only do next loop if third and fourth dont match
if (strcmp(dicmain.dict[z], dicmain.dict[zz]) != 0) {
// Fifth Word
for (z2 = 0; z2 < dicmain.dict_count; z2++) {
ptr4 = ptr3;
for (i = 0; i < dicmain.dict_member_length[z2]; i++) {
*(ptr4++) = dicmain.dict[z2][i];
}
*(ptr4) = 0x00;
findhash(buffer, ptr4 - buffer);
}
}
#endif
*(ptr3) = 0x00;
findhash(buffer, ptr3 - buffer);
}
}
*(ptr2) = 0x00;
findhash(buffer, ptr2 - buffer);
}
}
*(ptr1) = 0x00;
findhash(buffer, ptr1 - buffer);
}
*(ptr0) = 0x00;
findhash(buffer, ptr0 - buffer);
// Print out end time for word
time(&end2);
printf("\n\ntime : %f minutes.\n", difftime(end2, start2)/60);
// Close results file
fprintf(fout,"</NIDFUNCLIST>\n");
fflush(fout);
fclose(fout);
}
{ // Write out toplevel word, for resuming a run from last first word
FILE *fpt;
if ((fpt = fopen("nidstatus.tmp", "wt")) != NULL) {
fprintf(fpt,"%s",buffer+prefixlen);
fclose(fpt);
}
}
}
time(&end);
printf("\n\nhash count : %d\n", hash_count);
printf("dictionary words (firstword) : %d\n", dicfirstword.dict_count);
printf("dictionary words (main) : %d\n", dicmain.dict_count);
printf("\n\ntime : %f seconds.\n\n", difftime(end, start));
return 0;
}
-
florinsasu
- Posts: 47
- Joined: Wed Dec 15, 2004 4:23 am
...a bit late to add this to this thread :)
any release from vc7 and up are messed ?!? very strange
also amd64 debug builds work and releases dont...
i also have a sha12psp attack program and it does work correctly if built with vc6 debug, vc6 release, vc7 debug, vc71 debug, vc8 debug.loser wrote: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
any release from vc7 and up are messed ?!? very strange
also amd64 debug builds work and releases dont...
> 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)
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)
(NIDs for VSH modules)
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.
>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.
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.
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.
> 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).
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).
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!
[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!