Category Archives: Problem Solving

CTF OverTheWire: Natas8

After a break we continue with the CTF Natas series, now is the turn for natas8

Natas Level 7 → Level 8
Username: natas8
URL:      http://natas8.natas.labs.overthewire.org

Using the flag obtained in the previous challenge, we go to the URL showed in the description and we will see the following screen.

It’s just a simple web page with a basic input form, if we type nonsense we get an error message displaying Wrong secret, we proceed to click the the View sourcecode

<html>
<head>
<!-- This stuff in the header has nothing to do with the level -->
<link rel="stylesheet" type="text/css" href="http://natas.labs.overthewire.org/css/level.css">
<link rel="stylesheet" href="http://natas.labs.overthewire.org/css/jquery-ui.css" />
<link rel="stylesheet" href="http://natas.labs.overthewire.org/css/wechall.css" />
<script src="http://natas.labs.overthewire.org/js/jquery-1.9.1.js"></script>
<script src="http://natas.labs.overthewire.org/js/jquery-ui.js"></script>
<script src=http://natas.labs.overthewire.org/js/wechall-data.js></script><script src="http://natas.labs.overthewire.org/js/wechall.js"></script>
<script>var wechallinfo = { "level": "natas8", "pass": "<censored>" };</script></head>
<body>
<h1>natas8</h1>
<div id="content">

<?

$encodedSecret = "3d3d516343746d4d6d6c315669563362";

function encodeSecret($secret) {
    return bin2hex(strrev(base64_encode($secret)));
}

if(array_key_exists("submit", $_POST)) {
    if(encodeSecret($_POST['secret']) == $encodedSecret) {
    print "Access granted. The password for natas9 is <censored>";
    } else {
    print "Wrong secret";
    }
}
?>

<form method=post>
Input secret: <input name=secret><br>
<input type=submit name=submit>
</form>

<div id="viewsource"><a href="index-source.html">View sourcecode</a></div>
</div>
</body>
</html>

This is supposed to be the backend code of the HTML page we just saw, the important part of this challenge is in the PHP code functions, taking a quick look the data flow looks like this:

  • Check if submit key exists on $_POST
  • Pass $_POST[‘secret’] to encodeSecret function
  • encodeSecret function will apply some transformation to the secret and return it
  • The transformed secret must be equal to 3d3d516343746d4d6d6c315669563362, otherwise we are getting the Wrong secret error we saw already

As I say before, the important part is happening inside the encodeSecret function, the code is basically doing this:

secret -> base64_encode -> strrev -> bin2hex -> 3d3d516343746d4d6d6c315669563362

So we need to perform exactly the same operations but in reverse order to obtain the original secret, ie: the old bin2hex should be hex2bin, I don’t know if we should call this reverse engineering, anyway ¯\_(ツ)_/¯

3d3d516343746d4d6d6c315669563362 -> hex2bin -> strrev -> base64_encode -> secret

We can use PHP from the command line and do this:

$ php -r "echo base64_decode(strrev(hex2bin('3d3d516343746d4d6d6c315669563362')));"
oubWYf2kBq
$

We get the secret: oubWYf2kBq, we try it on the input form.

The flag for the next level, natas9, is: W0mMhUcRRnG8dcghE4qvk3JA9lGt8nDl

In this challenge we take advantage of a security vulnerability called Source code disclosure and then we did basic reverse engineering on the PHP code.

Happy hacking 🙂

#DailyCodingProblem: El producto de todos los elementos en el arreglo menos el elemento actual

https://www.dailycodingproblem.com/

Good morning! Here’s your coding interview problem for today.

This problem was asked by Uber.

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can’t use division?

Si ignoramos la restricción este problema es muy sencillo de resolver.

  • Iteramos el arreglo y calculamos el producto total de todos los elementos: 1 x 2 x 3 x 4 x 5 = 120
  • Iteramos nuevamente dividiendo el total entre cada uno de los elementos y guardamos esos resultados en nuevo arreglo: 120/1, 120/2, 120/3, 120/4, 120/5

La complejidad de esta solución seria O(2n) o simplemente O(n), pero debido a que el problema dice que no podemos usar la división las cosas se complican un poco mas.

Solución cuadrática

Sin usar la división la solución mas obvia es una solución cuadrática, iteramos el arreglo y por cada elemento vamos a ir acumulando el producto de esos valores menos el elemento i actual.

    int[] calculateProduct(int[] numbers) {
        int[] result = new int[numbers.length];
        // ...
        // ... logica para inicializar todos los valores de result en 1
        // ...
        for (int i = 0; i < numbers.length; i += 1) {
            for (int j = 0; j < numbers.length; j += 1) {
                if (i != j) {
                    result[j] *= numbers[i];
                }
            }
        }
        return result;
    }

Esta solución es muy fácil de entender pero no es para nada eficiente, O(n2), en la publicación anterior ya analizábamos otra solución cuadrática y veíamos que era un problema con inputs de datos muy grandes, por ejemplo un arreglo de 1000 elementos (1 millón de operaciones).

Solución en tiempo lineal con programación dinámica

Después de pensar un rato en este problema, haciendo algunas anotaciones y viendo la relación entre los indices y el producto parcial de cada uno de ellos llegue a la siguiente solución.

La primera fila son los valores del arreglo, después como si estuviéramos iterando, el valor actual es marcado en color amarillo, si pudiéramos obtener el producto acumulado de izquierda y derecha de cada uno de los elementos entonces podríamos resolver el problema multiplicándolos entre si 🙂

Ejemplo: para el obtener el resultado del 3 tendríamos que multiplicar sus valores de la izquierda que son 2 y sus valores de la derecha que son 20 dando como resultado 40.

Vamos a recorrer el arreglo por la izquierda y por la derecha guardando el producto de sus elementos, para eso necesitaremos 2 arreglos mas, left y right, podemos hacer esos recorridos en una sola iteración, después iteramos nuevamente multiplicando los valores de izquierdo y derecho de result[i].

    public static int[] calculateProduct(int[] numbers) {
        int[] result = new int[numbers.length];
        int[] left = new int[numbers.length];
        int[] right = new int[numbers.length];
        int totalLeft = 1;
        int totalRight = 1;
        int size = numbers.length - 1;
        for (int i = 0; i <= size; i += 1) {
            totalLeft *= numbers[i];
            totalRight *= numbers[size - i];
            left[i] = totalLeft;
            right[size - i] = totalRight;

        }
        for (int i = 0; i < numbers.length; i += 1) {
            if (i == 0) {
                result[i] = right[i + 1];
            } else if (i == numbers.length - 1) {
                result[i] = left[i - 1];
            } else {
                result[i] = left[i - 1] * right[i + 1];
            }
        }
        return result;
    }

La complejidad en tiempo de esta solución es O(2n) o O(n).
La complejidad en espacio de esta solución es O(3n) o O(n), (tomando en cuenta solamente los 3 nuevos arreglos que necesitamos, todas las demás variables son espacio constante).

Happy hacking 🙂

#DailyCodingProblem: Encontrar si dos números dentro de un arreglo suman K

https://www.dailycodingproblem.com/

Good morning! Here’s your coding interview problem for today.

This problem was recently asked by Google.

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

Como el problema lo indica, debemos crear una función que reciba 2 parámetros, un arreglo de números y un numero entero k, debemos buscar dentro de ese arreglo si dos elementos sumados entre si son iguales al numero k.

La solución naive para este problema seria iterar sobre los elementos del arreglo y por cada uno de ellos iterar nuevamente para ver si la suma de numbers[i] + numbers[j] da como resultado el numero k

   for (int i = 0; i < numbers.length; i += 1) {
        for (int j = 0; j < numbers.length; j += 1) {
            // evitamos la comparación de un elemento consigo mismo
            if (i != j && (numbers[i] + numbers[j]) == k) {
                return true;
            }
        }
    }

Esta solución no es muy buena ya que por cada elemento en el arreglo vamos a iterar nuevamente los datos, resultando en una complejidad O(n2) donde n es el tamaño del arreglo, imagina un arreglo de 1000 elementos, tendríamos que realizar 1 millón de operaciones.

Solución lineal para encontrar si dos números suman K

Vamos a iterar el arreglo, pero esta vez vamos a usar un HashSet para guardar información, por cada elemento:

  • Calculamos el numero que falta para completar el total k
  • Revisamos si el numero que nos falta existe en el HashSet, si es así devolvemos true (buscar elementos en un HashSet se hace en tiempo constante)
  • Si el numero que buscamos no existe entonces registramos el numero actual como “observado” en el HashSet

Si terminamos de recorrer el arreglo significa que no hay números que sumados nos den como resultado k y por lo tanto devolvemos false.

    public static boolean findSum(int[] numbers, int k) {
        HashSet<Integer> seenNumbers = new HashSet<>();
        for (int i = 0; i < numbers.length; i += 1) {
            int missing = k - numbers[i];
            if (seenNumbers.contains(missing)) {
                return true;
            }
            seenNumbers.add(numbers[i]);
        }
        return false;
    }

La complejidad en tiempo de esta solución es O(n), ya que el numero de operaciones a realizar depende directamente del tamaño del arreglo n.

La complejidad en espacio de esta solución también es O(n), el espacio o la memoria a utilizar depende directamente de lo que reciba la función, en este caso un arreglo de n elementos, utilizamos un HashSet para almacenar máximo el mismo numero de elementos y no realizamos otras operaciones que sean significativas con la memoria.

Happy hacking 🙂