# PHDays CTF quals 2013, Real World 500

Python service generates arbitrary amount of random numbers.
So, we tried http://ctf.phdays.com:12391/password_reset/ and it worked:

```IF test@test.com <or userX@domain.com> exists the link will be 'http://example.com/reset/0-str(hashlib.md5(str('%.16f'%random.random())).hexdigest())/'
```

Looks like modified password reset algo – user1@phdays.com worked ok.

As we know – Python uses modified Mersenne twister for random generation, so it’s not cryptographically secure and we can predict or find some values having it’s state. Every random number gives us 2 state values of 624 total. Then algo should look like:

• Get 312 floats
• Restore MT state from the floats

But it didn’t work, and we were too tired to investigate the reason, so more stupid way was used.

```def gen_rand(a,b):
a ^= (a >> 11)
a ^= (a << 7) & 2636928640
a ^= (a << 15) & 4022730752
a ^= (a >> 18)

b ^= (b >> 11)
b ^= (b << 7) & 2636928640
b ^= (b << 15) & 4022730752
b ^= (b >> 18)

a = a >> 5
b = b >> 6

return ((a*67108864.0+b)*(1.0/9007199254740992.0))
```

Algo described was modified for using with map-reduce.
Final exploit looks like (thx @touzoku):

1. We fetch 312 random numbers (known)
2. We run password_reset for selected user (unknown)
3. Fetch 312 more random numbers (known)
Now we have 624 known numbers and need to find 313th unkown.
4. Precompute _state_2_1 and _state_2_2 (according to PoC from PT)
5. Map it to our map-reduce cluster and get candidates for a and b
6. Run reduce and generate 256 random numbers one of which is correct
7. Having correct number, we can reset users password and enter the admin interface to get the flag