Skip to content

Instantly share code, notes, and snippets.

@vhqtvn vhqtvn/pyhashbreaker.cpp Secret
Last active Aug 29, 2015

Embed
What would you like to do?
#include <iostream>
#include <unistd.h>
#include <signal.h>
#include <vector>
#include <set>
#include <unordered_set>
#include <algorithm>
using namespace std;
struct Sample{
const char* inp;
int len;
long hash;
Sample(const char* inp, int len, long hash){
this->inp = inp;
this->len = len;
this->hash = hash;
}
};
/*Hash value of "\x00" * i */
long hashArr[]={0l,
7848190082587965582,
-3458030773997347889,
-4582483746743215612,
4410049638523290193,
6253908765636887514,
7892342918428438971,
4812826225314830288,
-3580448393237491763,
-3802863708583786458,
7877484284146754215,
};
Sample sample[] = {
Sample("testing",7,-6690661205054787548),
Sample("vanhoa",6,4054411468809426790),
Sample("ldfsjl",6,-1154596901575536268),
Sample("2cm834mc803c23-",15,-3744132313005259935),
};
int sampleLen = sizeof(sample)/sizeof(sample[0]);
int hashArrLen = sizeof(hashArr)/sizeof(hashArr[0])-1;
const char* targetStr = "you_want_it_LOLOLOL?";
int targetStrLen = strlen(targetStr);
long pythonHash(const char* p_, long len, long a, long b){
register long x, l = len;
const unsigned char* p = (const unsigned char*)p_;
x = a;
x ^= *p << 7;
while (--l >= 0)
x = (1000003*x) ^ *p++;
x ^= len ^ b;
if(x==-1) x=-2;
return x;
}
long pythonHashDump(const char* p_, long len, long a, long b){
long x, l = len;
const unsigned char* p = (const unsigned char*)p_;
x = a;
x ^= *p << 7;
printf("** %016lx | %02x\n",x,*p);
while (--l >= 0){
x = (1000003*x) ^ (*p++);
printf("** %016lx | %02x\n",x,*p);
}
x ^= len ^ b;
printf("** %016lx\n",x);
if(x==-1) x=-2;
return x;
}
long pythonHashLeft(const char* p, long len, long a, long b){
register long x, l = len;
x = a;
x ^= *p << 7;
while (--l >= 0)
x = (1000003*x) ^ *p++;
return x;
}
long subCut = 3;
void pythonHashGenLeft(vector<long>& r, long len, long sublen, long target, long a, long b, int autoChar){
long x, l = sublen;
x = a;
vector<long> curr;
for(int i=0;i<256;i++){
x = a ^ (i << 7);
curr.push_back((1000003*x) ^ i);
}
for(int ll = 1, lle = min(sublen,subCut); ll<lle; ll++){
//printf("GenLeft %d %ld\n",ll+1,curr.size());
vector<long> curr2;
for(auto it = curr.begin(); it!=curr.end(); it++){
x = (1000003 * *it);
for(int i=0;i<256;i++) curr2.push_back(x ^ i);
}
curr.clear();
curr = curr2;
}
for(int ll = subCut; ll < sublen; ll++){
//printf("GenLeft- %d %ld\n",ll+1,curr.size());
for(int i=0, ie=curr.size();i<ie;i++){
curr[i] = (1000003 * curr[i]) ^ (autoChar);
}
}
r = curr;
}
void pythonHashSolveLeft(char s[], long need, long len, long sublen, long target, long a, long b, int autoChar){
long x, l = sublen;
x = a;
vector<pair<long,long> > curr;
for(int i=0;i<256;i++){
x = a ^ (i << 7);
curr.push_back(make_pair((1000003*x) ^ i,i));
}
for(int ll = 1, lle = min(sublen,subCut); ll<lle; ll++){
printf("SolveLeft %d %ld\n",ll+1,curr.size());
vector<pair<long,long> > curr2;
for(auto it = curr.begin(); it!=curr.end(); it++){
x = (1000003 * it->first);
for(int i=0;i<256;i++) curr2.push_back(make_pair(x ^ i,it->second * 256 + i));
}
curr.clear();
curr = curr2;
}
for(int ll = subCut; ll < sublen; ll++){
printf("SolveLeft- %d %ld\n",ll+1,curr.size());
for(int i=0, ie=curr.size();i<ie;i++){
long hh0 = (1000003 * curr[i].first) ^ (autoChar);
long hh = 1000003 * hh0;
if(((hh ^ need) & ~0xFFl) == 0){
printf("SOLVE LEFT RESULT: %08x %016lx %016lx %016lx\n",curr[i].second,hh,hh0,curr[i].first);
s[0] = (curr[i].second>>16) & 0xFF;
s[1] = (curr[i].second>>8 ) & 0xFF;
s[2] = (curr[i].second ) & 0xFF;
s[3] = autoChar;
s[4] = hh & 0xFF;
}
}
}
}
long pythonHashGenRight(vector<long>& r, long len, long sublen, long target, long a, long b, int autoChar){
long x, l = sublen;
x = target ^ b ^ len;
vector<long> curr;
curr.push_back(x);
for(int ll = 0, lle = min(subCut,sublen); ll<lle; ll++){
//printf("GenRight %d %ld\n",ll+1,curr.size());
vector<long> curr2;
for(auto it = curr.begin(); it!=curr.end(); it++){
for(int i=0;i<256;i++) x=16109806864799210091 * ((*it) ^ i), curr2.push_back(x);
}
curr = curr2;
}
for(int ll = subCut; ll<sublen; ll++){
//printf("GenRight- %d %ld\n",ll+1,curr.size());
for(int i=0, ie=curr.size();i<ie;i++){
curr[i] = 16109806864799210091 * (curr[i] ^ (autoChar));
}
}
r = curr;
}
long pythonHashSolveRight(char s[], long need, long len, long sublen, long target, long a, long b, int autoChar){
long x, l = sublen;
x = target ^ b ^ len;
vector<pair<long,long> > curr;
curr.push_back(make_pair(x,0));
for(int ll = 0, lle = min(subCut,sublen); ll<lle; ll++){
printf("SolveRight %d %ld\n",ll+1,curr.size());
vector<pair<long,long> > curr2;
for(auto it = curr.begin(); it!=curr.end(); it++){
for(int i=0;i<256;i++) x=16109806864799210091 * ((it->first) ^ i), curr2.push_back(make_pair(x,it->second * 256 + i));
}
curr = curr2;
}
for(int i=0, ie=curr.size();i<ie;i++){
long hh = curr[i].first;
if(((hh ^ need) & ~0xFFl) == 0){
printf("SOLVE RIGHT RESULT: %08x %016lx\n",curr[i].second,hh);
s[4] ^= hh & 0xFF;
s[5] = curr[i].second & 0xFF;
s[6] = (curr[i].second>>8 ) & 0xFF;
s[7] = (curr[i].second>>16) & 0xFF;
}
}
}
pair<long,long> solveP(int hashMax, long M){
vector<long> possP;
possP.push_back(0);
for(int b=1;b<=8;b++){
vector<long> possP2;
for(long i=0;i<256;i++){
for(int k=0;k<possP.size();k++){
long pp = possP[k] + (i<<(8*(b-1)));
//printf("%02x: %08x\n",i,((i * M) ^ (i * M * M) ^ hashArr[1] ^ 1 ^ hashArr[2] ^ 2));
int valid12 = (((M * pp) ^ 1 ^ (M * M * pp) ^ 2 ^ hashArr[1] ^ hashArr[2]) & ((1ll<<(8*b))-1))==0;
int valid23 = (((M * M * pp) ^ 2 ^ (M * M * M * pp) ^ 3 ^ hashArr[2] ^ hashArr[3]) & ((1ll<<(8*b))-1))==0;
int valid34 = (((M * M * M * pp) ^ 3 ^ (M * M * M * M * pp) ^ 4 ^ hashArr[3] ^ hashArr[4]) & ((1ll<<(8*b))-1))==0;
if(valid12 && valid23 && valid34){
possP2.push_back(pp);
//printf("%d: %08x\n",b,pp);
}
}
}
possP = possP2;
}
vector<pair<long,long> > r;
for(int k=0;k<possP.size();k++){
long p = possP[k];
long q = (p * M) ^ 1 ^ hashArr[1];
long x = p;
bool valid = true;
for(int len=1;valid && len<=hashMax;len++){
x = (1000003*x);
if((x^len^q) != hashArr[len]) valid = false;
}
for(int i=0;i<sampleLen;i++){
if(pythonHash(sample[i].inp,sample[i].len,p,q)!=sample[i].hash) valid = false;
}
if(valid){
r.push_back(make_pair(p, q));
}
}
if(r.size()==0){
printf("Not found\n");
exit(-1);
}
printf("RSIZE = %d\n",r.size());
return r[0];
}
void solveSub(pair<long,long> pq, long hh, int ACFirst, int ACStep){
vector<long> sl, sr;
int leftlen, len = 8;leftlen = (len)/2+1;
bool firstS = true;
for(int autoChar=ACFirst;autoChar>=0 && autoChar<=0xFF;autoChar+=ACStep){
for(len = 8; len<=8;len++){
leftlen = (len)/2+1;
printf("[%02d] **** Solving len=%d | %02x\n",ACFirst,len,autoChar);
pythonHashGenLeft(sl, len, leftlen-1, hh, pq.first, pq.second,autoChar);
for(int i=0, ie = sl.size(); i < ie; i++){
sl[i] = (1000003 * sl[i]) & ~0xFFl;
}
sort(sl.begin(),sl.end());
if(firstS){
firstS = false;
sl.resize(distance(sl.begin(),unique(sl.begin(),sl.end())));
pythonHashGenRight(sr, len, len-leftlen, hh, pq.first, pq.second,autoChar);
for(int i=0, ie = sr.size(); i < ie; i++){
sr[i] &= ~0xFFl;
}
sort(sr.begin(),sr.end());
sr.resize(distance(sr.begin(),unique(sr.begin(),sr.end())));
}
vector<long> l(sl.begin(), sl.end());
vector<long> r(sr.begin(), sr.end());
vector<long> v(100);
auto it = set_intersection(l.begin(),l.end(),r.begin(),r.end(),v.begin());
v.resize(it-v.begin());
if(v.size()>0){
printf("[%02x] Result %02x : %d\n",ACFirst,autoChar,v.size());
for (it=v.begin(); it!=v.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
char sr[10];
pythonHashSolveLeft(sr,*v.begin(), len, leftlen-1, hh, pq.first, pq.second,autoChar);
pythonHashSolveRight(sr,*v.begin(), len, len-leftlen, hh, pq.first, pq.second,autoChar);
printf("Result: ");
for(int i=0;i<8;i++){
printf("\\x%02x",(unsigned char)sr[i]);
}
printf("\n");
kill(0, SIGKILL);
return;
}
}
}
}
int main(int argc, char *argv[]) {
pair<long,long> pq = solveP(hashArrLen, 1000003);
printf("Found A = 0x%016lx; B= 0x%016lx\n",pq.first,pq.second);
long hh = pythonHash(targetStr,targetStrLen,pq.first,pq.second);//pythonHash("12345",5,pq.first, pq.second);
int nProcess = 8;
for(int i=0;i<nProcess;i++){
pid_t pid = fork();
if (pid == 0){
solveSub(pq,hh,i,nProcess);
return 0;
}else if(pid<0){
printf("fork failed\n");
exit(-1);
}
}
while (true) {
int status;
pid_t done = wait(&status);
if (done == -1) {
if (errno == ECHILD) break;
} else if (!WIFEXITED(status) || WEXITSTATUS(status) != 0) exit(1);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.