Category: Web
Points: 250
Description:
A web scale key value store, for your enjoyment!
Should be working
Running at 52.6.62.188 port 9009
64-bit collision approach
I didn’t solve this problem within the contest time, but it’s here finally 🙂
First, let’s take a quick look on provided script:
It’s a web service which provide key-value storage functions via JSON requests, keys are stored using its masked hash value using python’s built in hash function. So I decided it a collision-finding problem. At first, looking at this line:
assert (hash('PPP') != 2149279368079130035)
Which made me thought that python is running using version 3.4 with new SIPHASH24 hash algorithm and SPENT A DAY TO CRACK SIPHASH without success… (poor me :(). When i could manage to talk with w~ about this problem, i realized that it’s only the old hash function with randomized secret keys.
A quick search on python source code gave me the implementation of its string hashing:
static long
string_hash(PyStringObject *a)
{
register Py_ssize_t len;
register unsigned char *p;
register long x;
#ifdef Py_DEBUG
assert(_Py_HashSecret_Initialized);
#endif
if (a->ob_shash != -1)
return a->ob_shash;
len = Py_SIZE(a);
/*
We make the hash of the empty string be 0, rather than using
(prefix ^ suffix), since this slightly obfuscates the hash secret
*/
if (len == 0) {
a->ob_shash = 0;
return 0;
}
p = (unsigned char *) a->ob_sval;
x = _Py_HashSecret.prefix;
x ^= *p << 7; while (--len >= 0)
x = (1000003*x) ^ *p++;
x ^= Py_SIZE(a);
x ^= _Py_HashSecret.suffix;
if (x == -1)
x = -2;
a->ob_shash = x;
return x;
}
Quite simple huh, start with an const, mul and or rounds, and ending by xor with its length and another const. Problem was that we dont know the value of _Py_HashSecret.prefix and _Py_HashSecret.suffix, let’s call them A and B from now on. As the calculation is based on simple operations only, we can use tools like z3 to solve the SMT model, but due to laggy internet, I decided to leave that path. Let’s calculate some simple hashes:
- Hash value of “\x00” * 1 : (1000003 * A) xor 1 xor B
- Hash value of “\x00” * 2 : (1000003 * 1000003 * A) xor 2 xor B
- Hash value of “\x00” * 3 : (1000003 * 1000003 * 1000003 * A) xor 3 xor B
From above formulas, I can reduce B by xor the hash of 2 strings, make it a formula with only A:
- (Hash value of “\x00” * 1) xor (Hash value of “\x00” * 2) = (1000003 * A) xor 1 xor (1000003 * 1000003 * A) xor 2
- (Hash value of “\x00” * 2) xor (Hash value of “\x00” * 3) = (1000003 * 1000003 * A) xor 2 xor (1000003 * 1000003 * 1000003 * A) xor 3
Now how can we sove that for A? As its type is long on 64 bits machine, we can’t do a full bruteforce search.
There’s an interesting feature of multiplication and xor is that the suffix of result if equal to operation result of suffixes of its operants. i.e. 0x12130x3456 = 0x3B1EE62 while 0x130x56 = 0x662, both share the same byte suffix. Using this we can solve for its value byte-byte-byte.
First, let’s calculate the hash value of some strings first:
/*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),
};
Using these values, we can generate all possible values for A and B using:
vector<long> possP;
possP.push_back(0);
for(int b=1;b<=8;b++){
vector possP2;
for(long i=0;i<256;i++){
for(int k=0;k<possP.size();k++){
long pp = possP[k] + (i<<(8*(b-1)));
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);
}
}
}
possP = possP2;
}
And then verify the results with provided samples:
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));
}
}
Using this method, i can (always) obtain 2 possible values pair for A and B, so i decided to use only the first one.
From this point, A and B are known, so we can simulate the hashing function locally. Now we must find collision for string “you_want_it_LOLOLOL?”.
The hashing value is 64 bits, so we have to search on a 64-bit space to obtain the collision, after some simple test on small strings, i think this hashing is nearly unique for them, which lead me to consider only in 8-byte strings. Thinking the hash function as a finity state graph, starting at A, we can go to next hash number using current character of input string. A full BFS rooting from A will require 2^64 nodes to be visited, which is impossible for our normal computer. We can try BFS from both side: the source node and the target node, and check if they can visit a common node, but this approach is for 128GB computer only – as we have to save hash (8 byte each) of 2^32 values, which require approx. 34GB RAM.
My last step to solve this problem is optimizing this: BFS only 3 bytes from each node, and try to do something for the remain 2 bytes (8-3*2 bytes). The first approach should be 256^2 loop:
for char1 in range(256):
for char2 in range(256):
TWO_WAY_BFS()
which should require some hours to finish. Looking more deeply on the hashing algorithm bring me an idea:
the assigment x = (1000003*x) ^ *p++; which our controlled p can assign any value to the LSByte of x!
So a byte can be obmitted from the search because it can be calculated using next and previous values, which reduce the searching space to 7 bytes, the obmitted byte will be the glue of 2 BFSs.
Finally making it run 8 processes in parallel and we got the flag flag{wh0_n3edz22Z22zZ_p3p456}.
RSIZE = 2 Found A = 0x1d0e2c73d04d2feb; B= 0xb01eedc54b35180e [22] Result 22 : 1 -7368800807082251008 SolveLeft 2 256 SolveLeft 3 65536 SolveLeft- 4 16777216 SOLVE LEFT RESULT: 00ba9057 99bcc2b521402d3a ac0276917b41cb3e 426e84fc91cabcb4 SolveRight 1 1 SolveRight 2 256 SolveRight 3 65536 SOLVE RIGHT RESULT: 009b5da9 99bcc2b521402de5 Result: \xba\x90\x57\x22\xdf\xa9\x5d\x9b Killed: 9
For the session with given A and B, the collision string for you_want_it_LOLOLOL? was \xba\x90\x57\x22\xdf\xa9\x5d\x9b with the same hash value 0x2fdd3e3f58ce3f70.
32-bit collision approach
Here’s python collision finding using z3:
#!/usr/bin/python
from z3 import *
x = BitVecs('x1 x2 x3 x4 x5 x6 x7 x8',8)
A = 0x1d0e2c73d04d2feb
B = 0xb01eedc54b35180e
def xhash(a, A, B):
l = len(a)
x = A
x = x ^ (ZeroExt(56,a[0]) << 7) l -= 1 i = 0 while l >= 0:
x = (x * 1000003) ^ ZeroExt(56,a[i])
i += 1
l -= 1
x = x ^ len(a)
x = x ^ B
return x
s = Solver()
s.add(xhash(x, A, B) & 0xFFFFFFFF == 0x39e0776e)
print s
print 'start!'
print 'sat:',s.check()
m = s.model()
print m
This program can run under 1 minute on my machine.
[(((((((((2093659752701439979 ^ ... << ...)*1000003 ^
ZeroExt(56, x1))*
1000003 ^
ZeroExt(56, x2))*
1000003 ^
ZeroExt(56, x3))*
1000003 ^
ZeroExt(56, x4))*
1000003 ^
ZeroExt(56, x5))*
1000003 ^
ZeroExt(56, x6))*
1000003 ^
ZeroExt(56, x7))*
1000003 ^
ZeroExt(56, x8) ^
8 ^
12690842231602747406) &
4294967295 ==
971011950]
start!
sat: sat
[x8 = 163,
x3 = 28,
x2 = 162,
x1 = 0,
x4 = 175,
x5 = 217,
x6 = 114,
x7 = 100]