Instantly share code, notes, and snippets.

@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