PHDays CTF quals 2013, Real World 500

Python service generates arbitrary amount of random numbers.
On the URL we found the Django admin page.
So, we tried and it worked: 

IF <or> exists the link will be ''%.16f'%random.random())).hexdigest())/'

Looks like modified password reset algo – 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
  • Fetch reset link
  • Restore MT state from the floats
  • Predict reset link value

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

Leave a Reply

Your email address will not be published.