**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. 0x1213*0x3456 = 0x3B1EE62 while 0x13*0x56 = 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]