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).
Utilizamos la bandera obtenida en el reto anterior y accedemos a la URL indicada en las instrucciones del reto, veremos una pantalla como la siguiente.
Es solo un formulario donde nos piden ingresar una contraseña o secreto, al introducir cualquier cosa obtenemos un mensaje de error.
En la misma pagina hay un enlace que dice view sourcecode (ver código fuente), damos clic y veremos lo siguiente.
La parte importa es:
<?
include "includes/secret.inc";
if(array_key_exists("submit", $_POST)) {
if($secret == $_POST['secret']) {
print "Access granted. The password for natas7 is <censored>";
} else {
print "Wrong secret";
}
}
?>
Es un código php muy sencillo, podemos ver que obtiene un parámetro via POST (el que enviamos mediante el formulario) y lo compara con la variable $secret, ademas hace include de un archivo interesante includes/secret.inc
Accedemos a ese archivo usando el navegador.
Y utilizamos el secret que acabamos de descubrir en el formulario inicial.
La bandera para acceder a natas7 es 7z3hEENjQtflzgnT29q7wAvMNfZdh0i9
En este reto aprovechamos un fallo de seguridad llamado Source code disclosure, en donde tenemos acceso a código que solo debería ser consumido del lado del servidor.
Para este reto nos daban un archivo comprimido zion.tar.gz, procedemos a descomprimirlo y obtenemos otro archivo llamado YouKnow.
El archivo no tiene extension pero utilizamos el comando file para ver que tipo de archivo es.
Parece un archivo de Microsoft Word Office y sabemos que los archivos docx en realidad son archivos en formato zip.
Procedemos a descomprimir YouKnow
Obtenemos varios archivos y carpetas, comenzamos a analizarlos de uno por uno, sin embargo no encontramos nada que haga referencia a la bandera del reto. (analice la imagen del conejo con un par de herramientas de esteganografía pero no había nada)
Damos un paso atrás y abrimos el archivo YouKnow en un editor hexadecimal de su elección, you utilice Sublime
Observamos la cabecera estándar PK del formato ZIP
Al ir analizando el archivo, hacia el final, algo salta inmediatamente a la vista.
Parece que hay otro archivo Zip concatenado al primero pero los bytes están en orden inverso (observen como el archivo termina en KP, y vemos algunos strings como lmx que seria xml).
Podemos utilizar python para invertir los bytes del archivo fácilmente.
Obtenemos el archivo con los bytes invertidos y procedemos a descomprimirlo.
Obtenemos nuevamente varios archivos y carpetas.
Y en donde estaba la imagen anterior del conejo rojo ahora encontramos otra imagen, esta vez de un conejo azul que nos muestra la bandera del reto 🙂
La bandera del reto es sctf{m41nfr4m3_4cc3ss_c0d3_1337_4lw4s}
Bonus
Programe una pequeña herramienta en python llamada reverse bytes para invertir los bytes de un archivo utilizando una cli mas amigable.
usage: rbytes.py [-h] [-o OUTFILE] infile
A simple python script for reverse the bytes of a file.
Author: Lenin Alevski Huerta Arias
Year: 2018
positional arguments:
infile Input file
optional arguments:
-h, --help show this help message and exit
-o OUTFILE, --outfile OUTFILE
Output file
Hola, como muchos saben, este blog esta registrado como comunidad tecnológica en Campus Party, cada año gente del estado de Michoacán nos organizamos para asistir al evento, jugar, divertirnos, aprender y sobre todo pasar un buen rato 🙂
Ser comunidad de CPMX tiene algunas ventajas por ejemplo obtener códigos de descuento y entradas gratuitas para rifar entre los miembros de la comunidad pero este año realice una dinámica diferente, hace mas o menos 1 semana anuncie en redes sociales (Facebook y Twitter) un pequeño reto CTF en donde poder ganar una entrada no fuera cuestión de suerte. Muchas gracias a todos los que participaron y felicidades a los ganadores.
A continuación dejo la solución de cada uno de los retos por si hay gente que se quedo con dudas 🙂
0x01 – 8.8.8.8 or 1.1.1.1?
A Dan Kaminsky le gusta ( ͡° ͜ ʖ ͡°) www.alevsk.com
Este reto es bastante sencillo si sabes un poco de cultura general de como funciona Internet. 8.8.8.8, 1.1.1.1 y Dan Kaminsky son claras referencias al sistema DNS.
En este tipo de retos es muy común que la información se encuentre escondida en el record TXT, pero también existen muchos otros tipos de DNS records. Vamos a utilizar la herramienta nslookup y con los siguientes comandos podemos listar los records TXT de cualquier dominio.
$ nslookup
> set q=TXT
> alevsk.com
La bandera de este reto es: ctf_flag{3550dd06-aec9-4841-96cb-dbfb093c6991}
0x02 – Cipher
Cipher es probablemente el reto mas complicado de este CTF, las instrucciones del reto nos muestran el siguiente texto cifrado.
Podemos intentar resolver esto con alguna herramienta automática como Rot13 Online o Caesar Cipher pero no hay resultados. No queda otra cosa mas que empezar a hacer un analisis del texto y aplicar distintos ataques criptograficos 🙂
Utilizamos uno de mis lenguajes de programación favoritos, python, para comenzar a recolectar estadísticas interesantes del texto.
Comenzamos separando el texto cifrado por espacios y contando el numero de veces que se repiten las palabras
La palabra que se repite mas veces es l2e (6 veces), pero también vemos l2e0 (2 veces) que es una variación de la palabra anterior, algo similar ocurre con h8g y h8g0g y algunas otras más.
La complejidad de este reto disminuye notoriamente ya que sabemos lo que estamos buscando en el texto, la bandera 🙂 y sabemos cual es el formato que deben seguir las mismas.
ctf_flag{xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx}
En una cadena de texto lo suficientemente larga debemos encontrar un símbolo que se repita siguiendo el mismo patrón que el de la bandera si no estuviera encriptada, es decir:
La palabra mas larga que arrojo nuestro análisis es whcjc4om{dzz9bk}v_pbdi_i}v3_op33_c3p39d.owvwpu, probamos “alineando” el formato de la bandera en esa palabra para ver si cumple con el patrón:
Tenemos una coincidencia 🙂 acomodamos el resto de la bandera y comenzamos a crear un diccionario con los caracteres a sustituir en el texto y podremos empezar a romper el cifrado (encontrar el alfabeto que fue usado para la sustitución)
Todavía tenemos otras 2 palabras, l2e y h8g, que se repiten bastante en el texto, si encontramos cual es su equivalente nuestro texto sera todavía mas legible. Investigando un poco encontré un articulo bastante interesante The Most Common Three Letter Words (Las palabras mas comunes de 3 letras)
Hacia al final del texto podemos leer algo que dice:
t8g flag s, ctf_flag{dzz9bk}v-pbdi-i}v3-ap33-f3p39d.acvcp}
si t8g puede ser the (que se encuentra en la lista de palabras populares) y s, es is la frase final seria
the flag is ctf_flag{dzz9bk}v-pbdi-i}v3-ap33-f3p39d.acvcp}
Parece que nos vamos acercando, probamos agregando estas letras a nuestro diccionario.
this is l2e0 last charcex afte0 thisn the0e is r2 te0rirg .acyx l2e taye the .lee 5ill – the st20l erzsn l2e !aye e5 ir l2e0 .ez arz .elie1e !hate1e0 l2e !art t2 .elie1ex l2e taye the 0ez 5ill – l2e stal ir !2rze0larz arz i sh2! l2e h2! zee5 the 0a..it-h2le g2esx the flag is ctf_flag{dzz9bk}v-pbdi-i}v3-ap33-f3p39d.acvcp}
Mas palabras salen a la luz:
afte0 … 0 es r
l2e0 se vuelve l2er, por lo tanto en la frase this is l2er last charcex, l2er es remplazado por your y el texto tiene aun mas sentido 🙂 !!!
charce … r es n (chance)
this is your last chancex after thisn there is no turning
Tenemos suficiente texto legible para realizar una búsqueda en google y darnos cuenta que el texto es una frase famosa de la película The Matrix
Completamos el resto del diccionario con las letras que nos hacen falta.
Nota: en este punto de la solución me di cuenta que cometí un error al momento de diseñar el reto y no se puede avanzar mas, gracias a @unmanarc por reportar el problema
Por lo tanto la bandera de este reto es ctf_flag{ddd9bk}v-pbdi-i}v3-ap33-f3p39dbacvcp}
0x03 – A new security policy standard
Si encuentras una vulnerabilidad en www.alevsk.com deberías reportarla utilizando los canales adecuados 🙂
Tanto el nombre del reto como la descripción nos da una pista acerca de que debemos investigar sobre nuevos estándares en políticas de seguridad, algunas personas se confundieron en este reto pues creían que tenían que encontrar vulnerabilidades en esta pagina, pero la solución es mas sencilla que eso.
security.txt es un estándar propuesto (similar a robots.txt) para que los sitios web puedan anunciar sus políticas de seguridad y consiste en publicar un archivo de texto en el directorio .well-known donde comuniquemos información importante como por ejemplo la direccion de contacto en la que los hackers pueden reportar las vulnerabilidades encontradas de nuestro sitio web, en este caso https://www.alevsk.com/.well-known/security.txt
# If you would like to report a security issue
# you may report it to me on www.alevsk.com
# ctf_flag{1999251d-df25-4d4a-846b-d4267f471b23}
Contact: [email protected]
Encryption: https://pgp.mit.edu/pks/lookup?op=get&search=0xFF4F600D674B6DED
La bandera de este reto es: ctf_flag{1999251d-df25-4d4a-846b-d4267f471b23}
0x04 – Foogle
Neo: Why do my eyes hurt? Morpheus: You’ve never used them before.
Este reto involucra esteganografía y es muy fácil de resolver, descargamos la imagen que nos indican las instrucciones y comenzamos a realizar el análisis, lo mas sencillo y lo primero que intentamos es ver si la imagen contiene en sus bytes alguna cadena de caracteres que tenga sentido.
Podemos utilizar la herramienta hexdump para hacer esto.
Al final del archivo hay una cadena de caracteres muy peculiar, parece que es un mensaje codificado en base64, tomamos el string y lo decodificamos con alguna herramienta como https://www.base64decode.org/
La bandera de este reto es ctf_flag{b309e05c-f224-4437-acd9-adae996142ed}
0x05 – Information leak
Información critica ha sido leakeada en los archivos de este repositorio x.x
Como la descripción nos indica, tenemos que revisar los archivos del repositorio donde esta hospedado el CTF, y no solo eso, tambien tenemos que revisar el historial de commits, vemos que en uno de los commits un archivo llamado 0x05_secret.txt fue publicado en el repositorio.
La bandera de este reto es ctf_flag{163f0835-8fc0-4fd0-b96b-dcd724cbe200}
0x06 – We can fix it!
Otro participante trato de robar la bandera de este reto pero sin querer la daño, ¿Puedes repararla? Descargar imagen
Este reto nos presentaba un codigo QR “dañado” (los bordes de la imagen han sido recortados), por lo que si tratamos de leerlo nos dará un error
Pero nada que un poco de photoshop no pueda arreglar 🙂
La bandera de este reto es ctf_flag{d55bd4f6-bff1-45b4-836e-7df1839e7d70}
Espero se hayan divertido mucho y aprendido algo nuevo al participar en este reto.
Utilizamos la bandera obtenida en el reto anterior y accedemos a la URL indicada en las instrucciones del reto, veremos una pantalla como la siguiente.
Como lo hemos hecho anteriormente, revisamos el codigo fuente pero no encontramos nada interesante, tampoco hay archivo robots.txt
Nos concentramos en el mensaje que aparece en la pantalla: Access disallowed. You are visiting from “” while authorized users should come only from “http://natas5.natas.labs.overthewire.org/”
Acceso deshabilitado. Nos estas visitando de “” mientras que los usuarios autorizados deberian de venir desde “http://natas5.natas.labs.overthewire.org/”
El mensaje anterior sugiere algún tipo de validación del lado del servidor en donde se revisa el origen de la petición, damos click en el link de refresh, inspeccionamos las cabeceras del request utilizando google developer toolbars y observamos que el mensaje de la pagina cambio.
Observamos una cabecera interesante llamada referer cuyo valor actual es http://natas4.natas.labs.overthewire.org/, veamos si es posible definir nuestro propio valor utilizando cURL.
Abrimos una consola y escribimos
$ curl --help
Usage: curl [options...] <url>
Options: (H) means HTTP/HTTPS only, (F) means FTP only
....
-r, --range RANGE Retrieve only the bytes within RANGE
--raw Do HTTP "raw"; no transfer decoding (H)
-e, --referer Referer URL (H)
-J, --remote-header-name Use the header-provided filename (H)
....
Genial, con el parámetro -e / –referer podemos definir nuestra propia URL.
○ → curl --user natas4:Z9tkRkWmpt9Qr7XrR5jWRkgOU901swEZ --referer http://natas5.natas.labs.overthewire.org/ http://natas4.natas.labs.overthewire.org/
<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": "natas4", "pass": "Z9tkRkWmpt9Qr7XrR5jWRkgOU901swEZ" };</script></head>
<body>
<h1>natas4</h1>
<div id="content">
Access granted. The password for natas5 is iX6IOfmpN7AYOQGPwtn3fXpbaJVJcHfq
<br/>
<div id="viewsource"><a href="index.php">Refresh page</a></div>
</div>
</body>
</html>
La bandera para acceder a natas5 es iX6IOfmpN7AYOQGPwtn3fXpbaJVJcHfq
