Hubert Hackin''

To the batcave! | Web | Nsec24

In this challenge, we’re presented with a map and controls to go through that map. It’s simple enough. With each request, you move forward in two possible directions; left or right. You must hit no wall and follow the trail of X. I prefer to see it as this famous game successful worldwide called: “The floor is lava”.

Is that all?

Alright, that’s easy! As Dijkstra taught me, let’s get our A* search algorithm going!

You can parse the map, copy-paste that Rosetta Code implementation of the A* search algorithm, import the requests library and send your path one request at a time.

ggwp, you’ve got the flag!

To be more exhaustive in our approach however, let’s look at the code we’re being provided.

import random
import numpy

def getAnswer(d,g):
    lv = float(g)
    rv = float(d)
    if lv > 1 or lv < 0:
        raise InvalidValue
    if rv > 1 or rv < 0:
        raise InvalidValue
    if (rv + lv) < 0:
        raise TotalTooSmall
    if (rv + lv) > 1:
        raise TotalTooBig

    la = [lv]
    ra = [rv]

    v = round(random.uniform(0,2),1)
    la.append(v)
    print('Utricule voted left a value of ' + str(v) + ' and a right value of ' + str(2-v))
    ra.append(2-v)

    v = round(random.uniform(0,2),1)
    la.append(v)
    print('Saccule voted left a value of ' + str(v) + ' and a right value of ' + str(2-v))
    ra.append(2-v)

    v = round(random.uniform(0,10),1)
    la.append(v)
    print('Vestibulocochlear nerve voted left a value of ' + str(v) + ' and a right value of ' + str(10-v))
    ra.append(10-v)


    v = round(random.uniform(0,1),1)
    la.append(v)
    print('Ampula voted left a value of ' + str(v) + ' and a right value of ' + str(1-v))
    ra.append(1-v)

    v = round(random.uniform(0,1),1)
    la.append(v)
    print('Cupula voted left a value of ' + str(v) + ' and a right value of ' + str(1-v))
    ra.append(1-v)


    print('Average left ' + str(numpy.mean(la)))
    print('Average right' + str(numpy.mean(ra)))

    if max(numpy.mean(la),numpy.mean(ra)) == numpy.mean(la):
        return 'Left'
    else:
        return 'Right'

First, we see our input d and g (for “droite” and “gauche” in French) are parsed as floats. I’m not going to mention how the reversed left and right make my OCD spike like an 90s microphone on teamspeak…

Then, it is validated to make sure they are both between 0 and 1 and that their sum is also between 0 and 1.

Finally, a few elements of the vestibular system are debating whether they should go left or right. To do so, they are using the random.uniform() function and calculate the average of weights to go left or right (including our feather weight). I assume they are doing all of this randomly because they are as tilted as me by getAnswer(d,g)… No wonder I always get vertigo on Friday nights…

Speaking of Randomness

There’s a nice warning in the Python documentation saying:

Warning The pseudo-random generators of this module should not be used for security purposes. For security or cryptographic uses, see the secrets module.

As we can see in the code, we’re given the value for each random.uniform() execution. The random module uses a Mersenne Twister construct for its PRNG (which is unsafe and can be reversed to then compute the rest of the sequence).

This means that with the values we’re given, it would be theoretically possible to reconstruct the Mersenne Twister’s state, compute the following sequence and realize that we cannot alter the average calculation by more than a tiny 1/len(all_random_values_list)…

Anyway, we don’t seem to be in a context where this random module is instantiated only once (such as in an eternally running Flask application).

Great! No Need to Analyze Python Implementation

I can’t say I haven’t…

Let’s look again at how our input is treated.

def getAnswer(d,g): # Never forgive, never forget
    lv = float(g)
    rv = float(d)
    if lv > 1 or lv < 0:
        raise InvalidValue
    if rv > 1 or rv < 0:
        raise InvalidValue
    if (rv + lv) < 0:
        raise TotalTooSmall
    if (rv + lv) > 1:
        raise TotalTooBig

    la = [lv]
    ra = [rv]

# ...

The validations look good to me and after that, there’s not much to be done.

Whatever FLOATs Your Boat

What about float()? Let’s look at Python documentation once again.

sign        ::=  "+" | "-"
infinity    ::=  "Infinity" | "inf"
nan         ::=  "nan"
digit       ::=  <a Unicode decimal digit, i.e. characters in Unicode general category Nd>
digitpart   ::=  digit (["_"] digit)*
number      ::=  [digitpart] "." digitpart | digitpart ["."]
exponent    ::=  ("e" | "E") ["+" | "-"] digitpart
floatnumber ::=  number [exponent]
floatvalue  ::=  [sign] (floatnumber | infinity | nan)

This seems to contain interesting stuff that looks interesting, but I have another resource that looks interestinger.

I have to be honest here, I really like being dumb when I look at a challenge and this is why I went looking at the Python WTF GitHub repo instead of Python doc. But, this is writeup time and appearing smart is our duty.

Almost every possible inputs to float() should respect the validations.

NAN NAN NAN NAN NAN NAN NAN NAN NAN NAN NAN NAN NAN NAN NAN NAN BATNAN!

I hope you’ve guessed what I’m getting to by now…

>>> float('nan') < 1
False
>>> float('nan') > 1
False
>>> float('nan') < 0
False
>>> float('nan') > 0
False
>>>
>>> # Logically, the following is also false
>>>
>>> float('nan') + float('nan') < 0
False
>>> float('nan') + float('nan') > 1
False

This means that we can send a NaN in either right or left (see what I did there?) and it will be valid.

Are We There Yet?

What about numpy.mean()?

>>> l = [float('nan'), 1]
>>> numpy.mean(l)
nan
>>> numpy.mean(l) == numpy.mean(l)
False
>>>
>>> # This last bit is interesting. wtf...
>>>
>>> max(1, numpy.mean(l))
1
>>> max(numpy.mean(l), 1)
nan

That looks promising! The decision between left and right and left and right and … is done with:

    if max(numpy.mean(la),numpy.mean(ra)) == numpy.mean(la):
        return 'Left'
    else:
        return 'Right'

So, if we want to go left, we input nan for right and a valid float for left. Otherwise to go right, we input nan for left and whatever for right (a valid float though…)

From there, you take out your A* search algorithm again, compute the correct trajectory and you get the flag!

FLAG-cpprx7maynsnlevgqbilrjwvxk5ipixk