Soy un investigador en la ETSI Informática de la Universidad de Sevilla, dedicado a la extracción de información web y la ciencia de los datos en general. Anteriormente trabajé en el Information Sciences Institute de la University of Southern California y actualmente estoy desarrollando una startup llamada Stargazr.

Cuando no estoy confinado dedico mi tiempo libre a patinar, el diseño e impresión 3D, la música, el remo y hacer juegos indie, entre otros. Puedes encontrarme en LinkedIn, Github, Twitter, Thingiverse o enviarme un mail a juancarlos@sevilla.es.

Picture of me raiding a fallen trunk in Hawaii

Como es costumbre entre cualquier persona con un mínimo de conocimientos de diseño web, pierdo más tiempo rediseñando mi web una y otra vez que escribiendo contenido interesante. Puedes ver la versión antigua de esta web, y la versión muy antigua.

Algunos blogs que sigo: Microsiervos, Kirai, Fogonazos, DataGenetics, XKCD, SMBC.Esto es un pequeño experimento: zanáculo zanáculos

Puedes hacer scroll para ir al blog.

El problema del User Agent

Hace casi 25 años, un popular navegador web llamado Mosaic tuvo una idea: incluir una cabecera en sus peticiones con la versión del navegador. Así, cada vez que un servidor recibiera una petición, podría saber con exactitud qué versión del navegador se estaba usando al otro lado.

User-Agent: NCSA_Mosaic/2.0 (Windows 3.1)

Al principio no se le dio mucho uso. Sin embargo, otro navegador llamado Netscape la popularizó poco después. Como las funcionalidades de ambos navegadores eran distintas, algunos servidores empezaron a usar esta cabecera para determinar qué respuesta enviar a los usuarios.

User-Agent: Mozilla/1.0N (Windows)

En vez de usar su propio nombre, este predecesor de Firefox usó el nombre de su mascota: Mozilla, abreviatura de Mosaic-killer. Pero esto sólo era el principio de la confusión. Otros navegadores como Internet Explorer usaron el nombre de Mozilla para indicar que eran compatibles con él.

User-Agent: Mozilla/2.0 (compatible; MSIE 3.02; Windows 95)

Y esto sólo fue a más. Algunos navegadores como Opera le dieron al usuario la opción de elegir a qué navegador querían suplantar mediante un menú desplegable. Los servidores estaban cada vez más confusos y saber quién había al otro lado se estaba volviendo muy difícil.

User-Agent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; en)
User-Agent: Mozilla/5.0 (Windows NT 6.0; U; en; rv:1.8.1) Gecko/20061208 Firefox/2.0.0
User-Agent: Opera/9.51 (Windows NT 5.1; U; en)

Actualmente, los navegadores utilizan un User-Agent que poco tiene que ver con su nombre. Algunos servidores usan gigantescas bases de datos para detectar el navegador actual a partir de esta cabecera y así servir la versión de la página más compatible. Por ejemplo, tu User-Agent es:

Desconocido

Es por esto que las herramientas modernas para asegurar la compatibilidad como Modernizr o Polyfill.io ya no confían en el User-Agent. En su lugar, hacen pequeñas pruebas en el propio navegador para saber qué es capaz de hacer. Esta técnica se conoce como feature detection.

La existencia de millones de User-Agent distintos también ha facilitado el browser fingerprinting: un conjunto de métodos que usan esta cabecera y otros datos de tu navegador para identificarte de forma única pese a que te conectes tras un proxy, en incógnito y con un bigote postizo.

Aunque esta cabecera nació con un buen propósito, el paso del tiempo la ha convertido en algo distinto. Por eso, Chrome ha anunciado que va a dejar de usarla y otros navegadores como Firefox han apoyado esta decisión. Pero ¿qué implica actualmente dejar de usarla por completo?

Hace una semana me instalé un plugin para Chrome llamado User-Agent Switcher and Manager y dejé esta cabecera vacía, para ver cómo respondían las webs que suelo visitar. Os dejo algunos de los resultados que resumen esta experiencia:

Como veis, aun no estamos preparados para un cambio en esta dirección, y seguramente muchas webs nunca lleguen a estarlo. Por suerte Chrome va a aplicar este cambio de forma gradual, empezando por no volver a actualizar el valor de esta cabecera. Adiós, User Agent!

No hay comentarios

Tuenti Challenge 10: nivel 18

Hemos construido un nuevo servicio, y debido a la falta de coordinación entre dos equipos, cada uno necesita recibir ciertos datos en un formato distinto: Elements Separated by Commas (ESC) y List-Oriented Language with Multiple Advanced Options (LOLMAO).

Matters with Formatters, fue el último del Tuenti Challenge 10 al que llegué. Como la solución optimizada para el caso de submit se me quedó en el tintero, me propuse terminarla y aquí va el resultado. Puedes encontrar en mi repositorio de Github del concurso mi solución completa.

Dada una cadena válida en uno de los dos formatos, debemos calcular el número mínimo de cambios necesarios para hacerla válida en el otro. No nos importa lo que represente esta cadena, lo único que queremos es que la cadena resultante sea válida en ambos formatos.

Para que una cadena sea válida en formato ESC nos basta con que cada línea del texto contenga al menos dos elementos separados por una coma.

alfa,beta,gamma
,,
foo,bar
test,a[5],asdf

El formato LOLMAO es algo más restrictivo:

[[],foo,[[[,],[1,2],5,,],some0literal
with3multiple
lines]]

La cadena de entrada del problema puede ser un texto de hasta 400 caracteres en formato LOLMAO que debemos convertir a ESC, o un texto de hasta 4000 caracteres en formato ESC que debemos convertir a LOLMAO.

En caso de que no sea posible generar una cadena válida en ambos, debemos devolver IMPOSSIBLE. Viendo estas reglas es fácil deducir que toda cadena en ESC debe contener al menos una lista de dos elementos, y por tanto una coma. Para que una cadena con una coma sea válida en LOLMAO, deberá estar rodeada de corchetes. Así, la cadena más pequeña que es válida en ambos formatos es [,] y cualquier cadena menor será imposible.

Ejemplo de exploración de solución

El resto de casos debemos resolverlos explorando cambios en la cadena de entrada. Nos enfrentamos a un problema de programación dinámica, en el que partiendo de un estado inicial —la cadena de entrada— debemos alcanzar un estado final —la cadena válida— en el mínimo número de pasos.

A fin de simplificar las cadenas de entrada, voy a reemplazar cualquier símbolo de la siguiente forma:

def standarize(text):
    res = ''
    for char in text:
        if char in '[],':
            res += char
        elif char == '\n':
            res += 'N'
        else:
            res += 'O'
    return res

A continuación, podríamos representar los estados como cadenas modificadas pero esto permitiría que pudiéramos explorar estados inválidos. Una de las máximas para optimizar la exploración es escoger una representación de estados que permita representar el mínimo número de estados inválidos.

Si nos peleamos un rato con este problema, veremos que cualquier estado se puede reducir a cuatro valores:

  1. La posición en la cadena: inicialmente será cero, y cada modificación consistirá en alterar el valor del símbolo en esta posición y generar un nuevo estado cuya posición se incremente en uno. Un estado final será aquel cuya posición sea igual a la longitud de la cadena.
  2. La profundidad: como el formato LOLMAO permite anidar listas, cada vez que encontremos un símbolo [ en la cadena la profundidad aumentará en uno, y cada vez que encontremos un símbolo ] la profundidad se reducirá en uno. Inicialmente, la profundidad es cero.
  3. El último símbolo encontrado: inicialmente no estará definido, y vez que pasemos al siguiente estado, tendrá el valor del último símbolo que hemos usado. Nos será útil para evitar combinaciones inválidas como ]O, N[ o ][.
  4. Si ha habido una coma en esta línea: este valor comenzará siendo falso, siempre que lleguemos a una coma será verdadero, y cuando alcancemos una nueva línea volverá a ser falso. Nos servirá para cumplir la restricción de ESC de tener una coma por línea.

Como esta representación está muy reducida, algunas cadenas distintas se pueden representar mediante un mismo estado. Esto quiere decir que si guardamos en memoria los resultados de nuestra exploración, se reutilizarán con bastante frecuencia.

@lru_cache(None)
def changes(pos, depth, last_char, comma_since_newline):
    # TODO compute here the alternatives "alts" as a list of symbols
    res = min(
        (alt != _text[pos]) + changes(
            pos + 1,
            depth + (alt == '[') - (alt == ']'),
            alt,
            alt != 'N' and comma_since_newline or alt == ','
        )
        for alt in alts
    )
    return res

Mientras resolvía este problema descubrí ese decorador @lru_cache(size), que se puede usar en cualquier función para almacenar en memoria su resultado, de forma que la próxima vez que se llame a esa función con los mismos argumentos, su resultado no sea calculado de nuevo.

Ya sólo nos queda saber cuándo debemos generar como alternativa cada uno de los cinco símbolos posibles:

Con esta aproximación conseguimos resolver el caso de test con facilidad. Pero al llegar al caso de submit la cosa se complica. Algunas cadenas son excesivamente largas y no logramos resolverlas mediante este método. Pero aun nos queda un as bajo la manga.

Como sabemos que las cadenas que deben ser convertidas a LOLMAO tienen como máximo 400 caracteres, cualquier cadena más larga que nos llegue deberá ser convertida a formato ESC. Si encontramos una forma rápida de hacer esta conversión sin romper el formato LOLMAO no tendremos que lanzar el algoritmo de exploración.

En este caso, el truco es el siguiente: en primer lugar, cambiar si fuera necesario el primer símbolo por [ y el último por ]. A continuación, cada vez que lleguemos a un salto de línea que no ha tenido una coma en esa línea, reemplazaremos ese salto por una coma.

De esta forma lograremos reducir el problema rápidamente y todos los casos se resolverán sin problema. El único cambio que tuve que hacer fue aumentar la profundidad máxima de la pila de llamadas debido a mi implementación recursiva de la solución.

setrecursionlimit(10000)  # we need to go deeper

Y aquí acaba la serie sobre el Tuenti Challenge 10. Todavía quedan dos niveles que no llegué a resolver, aunque igual algún día me pongo a resolverlos. Puedes consultar además los niveles anteriores:

No hay comentarios

Tuenti Challenge 10: niveles 15-17

Modificar animales genéticamente, planear la construcción de baños en un edificio gigante y encontrar el misterio escondido tras el póster de una película. Estos son los retos de este penúltimo post de la serie sobre el Tuenti Challenge 10. En mi repositorio de Github está el código de las soluciones que describo a continuación.

Nivel 15: The internsheep

En este nivel recibimos como entrada un archivo comprimido tarball de 11KB, que al ser descomprimido contiene el genoma de unos 100 animales, cada uno en un archivo de hasta 200GB. Lo primero que uno piensa al ver este archivo es que ante un ratio de compresión tan extremo tiene que haber gato encerrado, y no me refiero a su genoma.

Dediqué un precioso viernes a aprender cómo funcionaba DEFLATE, LZ2, los árboles de Huffman y hasta la vida y obra de Mark Adler, sólo para darme cuenta de que estos supuestos genomas son archivos cuyos bytes están todos a cero. No obstante, aprovecharé este conocimiento en futuros posts.

El problema nos pedía que introdujéramos ciertas modificaciones en el genoma de uno de los animales. Estas modificaciones venían definidas como un par (p, b), donde la p indica la posición en el archivo en la que debemos insertar el byte b.

Como no podemos enviar un archivo de 200GB, el problema nos pedía calcular el CRC32 del archivo resultante. El CRC32 es una cadena de control —algo así como la letra del DNI— que se calcula a partir de una secuencia de bytes como un archivo. Es muy frecuente que las descargas online vayan acompañadas de un CRC32 como medida de seguridad.

Así, una vez descargado un archivo podemos calcular su CRC32 byte a byte, y compararlo con el que nos dice la web para saber si ha habido algún error durante la descarga, ya que hasta el menor cambio en un archivo produce una alteración grande en el CRC32.

A primera vista parece un problema fácil: podemos mirar los metadatos del archivo comprimido para saber cuál es la longitud del archivo que quedemos modificar (y por tanto la secuencia de ceros que representa ese genoma), realizar las alteraciones que nos piden y calcular el CRC. Sin embargo, calcular el CRC32 de una cadena tan larga requiere semanas de cómputo en un ordenador convencional.

Por suerte, la librería zlib incluye una función llamada crc32_combine que aprovecha las propiedades de este algoritmo para calcular rápidamente el CRC32 de la concatenación de dos cadenas a partir del CRC32 de sus partes:

crc_combine(crc(A), crc(B), len(B)) = crc(concatenate(A, B))

Así, para calcular el CRC de una lista de 1024 ceros, sólo tendríamos que calcular el CRC de un único cero, usar esta función para calcular el de una secuencia de dos ceros, volverla a usar para calcular una de cuatro… y en definitiva, reducir el orden de este cálculo de forma logarítmica.

De este modo, sabiendo que todos los bytes de los archivos están a cero, podemos ver el tamaño de las secuencias genómicas en los metadatos del archivo comprimido e ir actualizando el CRC32 conforme intercalamos secuencias de ceros con los bytes que debemos insertar.

Nivel 16: The new office

Este problema nos sitúa en una oficina en un gran edificio de hasta 2000 plantas (el Burj Khalifa tiene 163) en el que trabajan muchos empleados. Hay un problema de salubridad importante: el edificio no tiene baños.

Tenemos que calcular el mínimo número de baños a construir, sabiendo que debe haber el mismo número de baños en cada planta, y que todos los empleados deben ser capaces de acceder al baño al mismo tiempo.

Los empleados están organizados en grupos: un empleado pertenece a un único grupo y cada grupo sólo tiene acceso a ciertas plantas. Dado que puede haber hasta 400 grupos de 2000 empleados en el edificio, realizar este cálculo mediante fuerza bruta no es una opción.

Siempre que veo un problema de este tipo, en el que hay muchos elementos distintos (plantas, grupos, empleados) que tienen cierta relación entre sí, algo me dice que usar grafos puede ser la solución. En este caso, el problema se puede resolver mediante grafos de flujo.

Estos grafos se usan habitualmente para modelar redes por las que un flujo recorre una serie de tuberías de una cierta capacidad, como en redes de transporte, circuitos eléctricos o sistemas de fluidos. En este problema, queremos medir el flujo de personas, asegurando que todas las personas que fluyen desde cierto grupo de empleados hacia las plantas autorizadas puedan usar los baños.

Red de flujo del problema

La imagen de arriba representa este problema. Hay tres grupos de empleados: G1, que puede ir a las plantas 2 y 3; G2, que puede ir a las plantas 0, 1 y 3; y G3, que sólo puede ir a la planta 0. Además, G1 está formado por 3 empleados, G2 por 5 y G3 por 1. Esto significa que el flujo de personas que llega a cada grupo es de 3, 5 y 1 respectivamente.

A continuación, estas personas se distribuyen lo mejor que pueden, como si de un fluido se tratase, entre los baños de cada planta; de ahí que las aristas que van de un grupo de empleados a una planta no tengan un límite en su capacidad.

Una vez modelado el problema, resolverlo se reduce a encontrar el menor número de baños posible w, que se corresponde con la capacidad de las aristas de salida en nuestro grafo.

Al diseñar este grafo con el problema original, e ir aumentando w hasta que el flujo que llega a t sea igual al número de empleados, mi ordenador tarda aproximadamente 2 horas en resolver algunos problemas. Pero todavía queda una optimización posible.

Como sabemos que w está en el rango (0, num_empleados), podemos calcular el flujo de salida en el punto medio p = num_empleados / 2. Si p es igual al número de empleados, existe la posibilidad de que podamos encontrar un w menor, por lo que w está en el rango (0, p). En caso contrario sabemos que w está en el rango (p, num_empleados).

Podemos seguir reduciendo el rango hasta encontrar una solución mucho más rápido, concretamente, en un máximo de log2(num_empleados) pasos. Este método se conoce como el método de la bisección.

Nivel 17: Zatoichi

De nuevo, este nivel no tiene más enunciado que una imagen.

Póster desordenado de Zatoichi.

Esta imagen es el póster de la película de 2003 Zatōichi, que cuenta la historia de un espadachín ciego interpretado por Takeshi Kitano. Esto nos puede dar una pista de por dónde puede ir la solución.

Además, la imagen esté desordenada y seguramente reordenarla sea el primer paso para resolver este problema. Para hacer esto tendremos que trabajar con los propios píxeles de la imagen y guardarla de nuevo, por lo que toda la meta-información que pueda estar oculta se perderá.

Teniendo esto en cuenta, es probable que no haya metainformación oculta y la clave del problema esté en los propios píxeles de la imagen. Los trucos para esconder información en un archivo se conocen como esteganografía, y una de los más conocidos consiste en esconder información en el bit menos significativo de cada canal de color.

El truco es bastante sencillo. Al representar un color en una imagen, cada pixel se suele representar como un conjunto de 3 bytes, que codifican los valores del rojo, verde y azul entre 0 y 255. Como en la práctica nadie va a notar que un pixel rojo tenga valor 136 o 137, podemos usar ese último bit de cada byte para esconder información.

Animación de imágenes creadas por cada bit del póster

Si observamos el plano que se crea al usar todos los bits en cierta posición, vemos que los que están en la posición 0 crean una imagen muy estructurada que no tiene nada que ver con la imagen original. Durante el concurso dediqué mucho tiempo a hacer pruebas con este plano: analizarlo, desplazarlo, convertirlo a texto y hasta transformar el XOR de sus tres canales de color en un pentagrama y tocarlo con el piano.

Sin embargo la respuesta era mucho más sencilla: si leemos todos esos bits de arriba a abajo y de izquierda a derecha, extraeremos una cadena que se repite muchas veces.

CONGRATULATIONS, YOU FOUND THE HIDDEN MESSAGE, WILL YOU BE ABLE TO DECODE IT?
E2A089E2A095E2A09DE2A09BE2A097E2A081E2A09EE2A0A5E2A087E2A081E2A09EE2A08AE2A095E2A09DE2A08E20E2A0BDE2A095E2A0A520E2A099E2A091E2A089E2A095E2A099E2A091E2A09920E2A09EE2A093E2A09120E2A08DE2A091E2A08EE2A08EE2A081E2A09BE2A09120E2A09EE2A093E2A09120E2A08FE2A081E2A08EE2A08EE2A0BAE2A095E2A097E2A09920E2A08AE2A08E20E2A09EE2A093E2A09120E2A08BE2A095E2A087E2A087E2A095E2A0BAE2A08AE2A09DE2A09B20E2A0BAE2A095E2A097E2A09920E2A08AE2A09D20E2A0A5E2A08FE2A08FE2A091E2A097E2A089E2A081E2A08EE2A09120E2A09EE2A081E2A085E2A091E2A08EE2A093E2A08AE2A085E2A08AE2A09EE2A081E2A09DE2A095E2A083E2A08AE2A09EE2A095E2A09EE2A081E2A085E2A091E2A08EE2A093E2A08AE2A093E2A0A5E2A08DE2A095E2A097E2A081E2A08DE2A081E2A097E2A08AE2A087E2A087E2A095E2A0BCE2A083E2A0BCE2A09AE2A0BCE2A083E2A0BCE2A09AE2A09EE2A0A5E2A091E2A09DE2A09EE2A08AE2A089E2A093E2A081E2A087E2A087E2A091E2A09DE2A09BE2A091E2A0BCE2A081E2A0BCE2A09A

Un último obstáculo antes de llegar al final. La cadena cifrada está formada por muchos códigos de seis letras que empiezan por E2A0. Una búsqueda en la web del primero de ellos nos revelará que son códigos unicode de caracteres braille.

Por ahí iba la pista de Zatōichi. Si descriframos cada uno de estos caracteres y los traducimos usando el braille inglés (sí, cada idioma usa un braille ligeramente distinto) encontraremos la solución.

Y este fue el último nivel que resolví con éxito durante el concurso. Sin embargo, he dedicado algún tiempo para conseguir resolver el submit del siguiente nivel (sólo conseguí resolver el test) y lo contaré en el próximo post.

No hay comentarios

Tuenti Challenge 10: niveles 11-14

Construir el mayor castillo de rollos de papel higiénico o introducirse en una red distribuida para alterar su funcionamiento: estos son algunos de los niveles de este cuarto post de la serie Tuenti Challenge 10.

Los primeros tres primeros niveles son bastante matemáticos. El último, echando un ojo al ranking, es uno de los más complejos de esta edición. En Github he subido todas mis soluciones a estos problemas.

Nivel 11: All the Possibilities

Este es uno de esos posts que esconden cierta complejidad bajo la simpleza de su enunciado: dado un número X entre 1 y 100 y algunos números Ni menores a este, calcular de cuántas formas se puede representar X como suma de enteros que no contengan ningún Ni. En matemáticas, una suma de enteros que da lugar a un número se denomina una partición.

def solve(X, N):
    res = [1] + [0] * X
    for i in range(1, X):  # in how many ways you can use an i...
        if i not in N:
            for j in range(i, X + 1):  # ...to obtain j
                res[j] += res[j - i]
    return res[X]

La solución también parece sencilla aunque esconde cierta complejidad. La mejor forma de entenderlo con un ejemplo: vamos a calcular cuántas formas hay de sumar 5 sin usar el número 3.

Primero, construiremos una array res en la que iremos guardando en cada posición j de cuántas formas se puede sumar dicho número. Como sólo hay una forma de sumar cero, res = [1, 0, 0, 0, 0, 0].

A continuación, iremos viendo cuántas formas hay de sumar el número en posición j usando sólo el número 1 y actualizaremos res sumándole estos valores.

Después, repetiremos la operación para el número dos. Como no podemos usar el 2 para sumar un número menor a sí mismo, empezaremos intentando sumar dos.

Como en este problema no podemos usar el número 3, nos lo saltamos y repetimos esta operación usando el número 4 para sumar 4 o 5.

Al terminar esta operación, tenemos almacenado en el último valor de la array la solución al problema.

Nivel 12: Hackerman Origins

En este problema tenemos dos mensajes en texto plano y sus versiones cifradas usando RSA. Como hemos perdido la clave pública que hemos usado para cifrarlos, debemos encontrarla a partir de ambos pares de mensajes.

Este cifrado tan seguro es la base de nuestra comunicación. La usan bancos, VPNs, navegadores y hasta comunicaciones entre gobiernos. Si pudiéramos romperlo, ¿por qué conformarse con solucionar este problema? Por suerte, no tenemos que llegar tan lejos y basta con recuperar la clave pública, cuyo propósito no es ser especialmente segura.

Una clave pública RSA es un par (e, m). Dado un mensaje sin cifrar P, su cifrado consiste en convertirlo en un entero, elevarlo al exponente e, y aplicarle el módulo m dado. El número resultante es el texto cifrado C. En otras palabras, P e = C (mod m), o lo que es lo mismo P e - C = k m, donde k es algún número entero.

Por tanto, si tenemos dos pares de textos (P1, C1) y (P2, C2) y conocemos el exponente e, podríamos hallar su módulo mediante el máximo común divisor: m = gcd(P1e - C1, P2e - C2). Para encontrar el exponente usar el más habitual: 65537.

Nivel 13: The Great Toilet Paper Fortress

Debido al reciente afán por el acopio de papel higiénico, un supermercado ha decidido construir el mayor castillo de rollos de papel para tranquilizar a los compradores, siguiendo ciertas propiedades.

Ejemplos de torre de papel higiénico

El castillo debe tener una torre central lo más alta posible, rodeada por una muralla con dos rollos menos de altura, rodeada por otra de un rollo más de altura y así sucesivamente. Este proceso termina cuando la siguiente muralla a construir tuviera que tener altura cero. Además, la torre central debe ser cuadrada o rectangular con sólo un rollo de diferencia entre ambas dimensiones.

Si asumimos que la torre central siempre tiene un único rollo en cada planta, podemos usar las propiedades de los sumatorios para calcular el número de rollos necesarios para hacer una torre de h rollos de altura.

def simple_rolls(h):
    return (16 * h**3 - 36 * h**2 - h + 24) // 3

Ahora tenemos que ver cómo añadir rollos a la planta de la torre central. Como sólo puede haber un rollo de diferencia entre ambas dimensiones, la torre central debe ser siempre de 1x1, 1x2, 2x2, 2x3, 3x3, etc. Lo que significa que la suma del ancho y el largo siempre es distinta: 2, 3, 4, 5, 6, etc.

Si de nuevo nos peleamos un poco con las propiedades de los sumatorios mirando muchos ejemplos de castillos (el Excel fue de gran ayuda), podemos escribir una función que calcule cuántos rollos extra, aparte de los calculados por simple_rolls, necesitamos para hacer una torre cuya suma de dimensiones es s.

def extra_rolls(h, s):
    if s == 0: return 0
    return (2 * s) * (h**2 - h) - h + h * (s // 2 - 1 + s % 2) * (s // 2 - 1)

Teniendo estas dos ecuaciones, el problema se vuelve muy sencillo: devolvemos IMPOSSIBLE si nos dan menos de simple_rolls(3) rollos, y en otro caso encontramos el mayor h posible con los rollos que nos dan y vamos aumentando s para encontrar el mayor la mayor torre central.

Nivel 14: Public Safety Bureau

Este fue uno de los problemas más interesantes y complejos del concurso: muchos se lo saltaron, y otros tantos abandonaron en este problema. Es un CTF en el que sólo tenemos una IP y un puerto mediante los que conectarnos a un protocolo de consenso de red conocido como Paxos inspirado en el sistema Sibyl del anime Psycho-Pass.

Sybil System logo

El objetivo de este protocolo es establecer un acuerdo sobre cierto valor v, como podría ocurrir al actualizar el valor de un atributo en una base de datos distribuida. Tenemos una serie de servidores que tienen roles definidos. Los servidores se agrupan en conjuntos llamados quorums de forma solapada. Por ejemplo, un quorum puede estar formado por los servidores 1, 2 y 4; otro por los servidores 2, 3 y 5.

El protocolo va realizando pequeñas tareas una por una, que se realizan en paralelo por todos los servidores del quorum y se ponen en común para garantizar la consistencia. Veamos este proceso paxo a paxo (mis disculpas):

  1. La petición para actualizar un valor v surge de un servidor con el rol proposer, que contacta con todos los servidores de uno de sus quorums mediante un mensaje llamado PREPARE que va acompañado de un identificador numérico n que se va incrementando.
  2. Si los servidores que reciben el mensaje, cuyo rol es acceptor, no han recibido ningún n superior significa que el servidor está al día. En este caso, responden con un mensaje llamado PROMISE, acompañado del último valor v-1 que han visto, y actualizan su valor n.
  3. Cuando el proposer ha recibido una mayoría de promises, escoge el nuevo valor de acuerdo con los v-1 que ha recibido, y se lo envía a todos los servidores mediante un mensaje ACCEPT, que debe entenderse como "acepta este nuevo valor, por favor".
  4. Si este es el mensaje más nuevo que han encontrado, los acceptors enviarán un mensaje ACCEPTED al proposer, y el valor será actualizado en todos ellos.

Tras entender el protocolo, es necesario hacer muchas, muchas pruebas hasta entender cómo funciona su sintaxis en el servidor del problema. Además, este problema tiene una pequeña vuelta de tuerca en uso de este protocolo: el valor sobre el que ponerse de acuerdo no es ningún atributo en una base de datos, es una cadena que contiene la lista de servidores que se están usando y un valor secret_owner: 1 que apunta a un servidor que contiene un secreto.

ROUND 897: 5 -> ACCEPTED {servers: [1,2,3,4,6,7,8,9], secret_owner: 1}

La modificación del secret_owner debe ser aceptada por mayoría. Cada ciclo completo de Paxos nos permite añadir o eliminar un único servidor de la lista de servidores del quorum. Podemos ir eliminando servidores uno por uno para hacernos con el control de la red, pero al llegar a 3 servidores nos encontraremos un problema.

Cluster needs to have at least 3 members alive

No podemos garantizar la mayoría siendo un único servidor. Pero si nos conectamos con 2 o más servidores al mismo tiempo, podemos alcanzar esta mayoría. Así, podemos definir la siguiente estrategia:

Y con esto recibiremos el mensaje secreto, que es una cita de Psycho-Pass. Tras indagar un poco sobre este anime para este problema, he terminado por engancharme. Son capítulos de 20 minutos y está en Netflix, así que si os gustan los futuros distópicos os recomiendo echarle un ojo.

Y esto es todo en esta entrega, nos vemos en la siguiente!

No hay comentarios

Tuenti Challenge 10: niveles 7-10

Desencriptar las comunicaciones secretas de una raza de robots alienígenas o resolver una escape room vía SSH usando sólo emojis. Estos son algunos de los challenges de los niveles 7-10 del Tuenti Challenge 10.

Esta es la continuación de la serie de posts sobre este concurso. En Github podéis encontrar todas mis soluciones a los niveles que explico a continuación, aunque es más divertido intentar superarlos. Si aún no lo habéis hecho, hay un enlace a cada nivel en el título de su solución.

Nivel 7: Encrypted lines

En este nivel aparecen dos líneas de un texto que debemos desencriptar, acompañadas de una pista de audio para que "resolvamos el problema de forma mucho más agradable". Supe de inmediato que la pista de audio es la Sinfonía del Nuevo Mundo de Antonín Dvořák, porque fue mi despertador durante un tiempo (nada recomendable para levantarse con buen humor).

yd. b., ,rpne ofmldrbf ,ao jrmlro.e xf abyrbcb ekrpatv
yd. ekrpat ocmlncuc.e t.fxrape ,ao lay.by.e xf agigoy ekrpat abe dco xpryd.p cb na, ,cnncam e.an.fv

Algunos trozos de la cadena como yd., ,ao o xf se repiten varias veces. Además, los símbolos a, . y r son bastante frecuentes. Todo esto puede hacernos sospechar que se trata de un cifrado por reemplazo, y podríamos solucionar el problema mediante análisis de frecuencia.

Sin embargo, la pista de audio nos revela algo más: Dvorak es también el nombre de una distribución de teclado famosa entre los programadores por ser especialmente ergonómica, siempre que superemos la penitencia de dejar de usar QWERTY.

Disposición del teclado DVORAK americano

Si reemplazamos cada letra del teclado Dvorak por la que ocupa la misma posición en el teclado QWERTY, desencriptaremos el texto y encontraremos la respuesta al problema.

Nivel 8: Headache

Este nivel es un CTF de los clásicos, en el que nos dan una imagen que tiene una clave escondida. Aparentemente, la imagen está en blanco, pero al subir el contraste a tope aparece esto:

Un cerebro con el texto

Esta no es la clave que buscamos. Si la abrimos con un editor hexadecimal y miramos el campo de comentarios del PNG, nos encontramos el texto "Hi challenger! No, the code is not here ;)". Pero al final del archivo hay una cadena bastante sospechosa.

++++++++++[>++++++>+++++++>++++++++>+++>+<<<<<-]>>>++++.<++.---.>>++.<<-
-.>-----.<+.+.>>.<<++++.>++++.<<--.>>>.<++++.<++++++.---.+++.---.+++.>>+

Si alguna vez habéis visto código en lenguaje esotérico Brainfuck lo habréis identificado de inmediato (sí, esto es un lenguaje de programación). Podemos pegar este texto en un intérprete online de Brainfuck y obtendremos la clave del problema.

Nivel 9: Just Another Day on Battlestar Galactica

Nos encontramos en medio de una batalla entre los robots cylons y los humanos de Battlestar Galactica, la nave de combate que protagoniza la serie homónima. Sabemos que las baterías de los cylons necesitan cierto isótopo radioactivo que se encuentra en unos pocos planetas.

Hace un año, los humanos interceptaron un mensaje cifrado de los cylons, y poco después estos aterrizaron en un planeta que albergaba el isótopo en cuestión. Conocemos las coordenadas de ese planeta.

MENSAJE: 3633363A33353B393038383C363236333635313A353336
PLANETA: 514;248;980;347;145;332

Recientemente, los humanos han interceptado otro mensaje que seguramente se corresponda a otro planeta. Además han encontrado un script bash con la función que usan para encriptar sus mensajes. ¿Podemos revertir la encriptación y descubrir las nuevas coordenadas?

Tras estudiar el script, vemos que su funcionamiento es el siguiente:

  1. Se introduce una clave secreta con la misma longitud que el mensaje.
  2. Cada símbolo del mensaje se transforma en su código ASCII.
  3. Se genera una nueva secuencia haciendo el XOR del mensaje y la clave.
  4. Se devuelve esta nueva secuencia, pasando a hexadecimal cada byte.

Como conté en el post sobre el cifrado XOR, este es un cifrado recíproco, de manera que T XOR P = C implica que C XOR P = T. Esto quiere decir que teniendo un mensaje en texto plano y su versión cifrada, podemos averiguar la clave de encripción y con ello descifrar el segundo mensaje.

Nivel 10: Villa Feristela escape room

Este me pareció el nivel más original de todo el concurso: una conexión por SSH a un servidor cuyos comandos funcionan sólo con emojis. Si no lo habéis probado no sigáis leyendo y probadlo, merece mucho la pena.

En este problema somos un detective que ha llegado a un hotel-castillo llamado Villa Feristela, y debemos resolver un misterio. La mayor parte de las interacciones con el juego se hacen mediante emojis. Como no quiero arruinarle este juego a nadie, sólo voy a mencionar las guías necesarias para superar este nivel, sin entrar en mucho detalle.

Y con esto es suficiente para resolver este problema. Para poder incluir todos estos emojis en esta entrada he tenido que cambiar el formato de algunos campos de la BD del blog a utf8mb4. Espero que os haya gustado, nos vemos en el siguiente post de esta serie!

No hay comentarios

🍪 ¿Cookies?

Esta web usa cookies para identificar qué contenido es interesante y escribir más contenido similar. Puedes obtener más información aquí.