Arctic Code Vault

Hoy me he enterado de que el código de algunos de mis proyectos está impreso en una película fotográfica y enterrado en el ártico. Y si has contribuido a proyectos públicos de Github, seguramente el tuyo también.

Rollo de película del Artic Code Vault

Nuestros sistemas de almacenamiento son mucho menos duraderos de lo que solemos creer. Los CDs tienen una vida útil de unos 10 años, mientras que los discos duros convencionales aguantan 8 años de media, o algo menos en el caso de los SSD. Y si tienes algún disquete por casa, seguramente ya esté desmagnetizado.

Existen formatos más duraderos como el Blu-ray M-DISC, que según aseguran sus creadores tiene una durabilidad de 1000 años. Aunque si ya resulta difícil encontrar sitios donde revelar carretes de fotos, nadie nos asegura que para entonces siga habiendo lectores de CDs.

Por eso Github ha lanzado la iniciativa Artic Code Vault, que tiene como objetivo preservar el mayor repositorio de código de la humanidad en el Artic World Archive. Esta instalación está enterrada en una montaña del ártico a 250 metros de profundidad, suficiente para evitar los daños provocados por armas nucleares o pulsos EM.

Entrada al Arctic World Archive

El objetivo de este búnker es preservar la información necesaria para reconstruir la humanidad en caso de colapso global. La isla en la que se sitúa es parte de Svalbard, un archipiélago al norte de Noruega que está considerado zona desmilitarizada por 42 países.

La información se almacena en carretes transparentes usando una tinta magnética legible con una lupa, que se espera que aguante entre 500 y 1000 años. Y en caso de apagón, el propio frío de la montaña mantendría la temperatura y humedad en un rango razonable durante décadas.

El 2 de febrero de este año, Github hizo un snapshot de los proyectos públicos para convertirlos a este formato. Un total de 21TB de código que representa algunas de las contribuciones más importantes de los últimos años, desde lenguajes de programación a sistemas operativos completos.

Para saber si tu código también está en este búnker, sólo tienes que irte a tu perfil de Github y buscar el badge Arctic Code Vault Contributor.

1 comentario

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!

1 comentario

Tuenti Challenge 10

Del 27 al 4 de mayo se ha celebrado la décima edición del reto para programadores que organiza Tuenti todos los años. Suelo participar siempre porque se sale de los esquemas habituales de los concursos de programación y eso lo hace muy divertido.

Logo del Tuenti Challenge 10

En este mega-post describo cómo he resuelto los primeros 18 problemas, así que lo he convertido en una serie de sub-secciones que podéis comprimir y expandir a voluntad. Podéis encontrar mi solución a todos los problemas en su repo de Github.

Introducción

Estos concursos suelen seguir la estructura que inventó ICPC, que consiste en resolviendo problemas algorítmicos a partir de una descripción y un archivo de entrada. Este archivo contiene muchos casos de prueba que hay que interpretar para generar otro archivo de salida. Otros concursos de este tipo son Google Code Jam o Facebook Hacker Cup.

Otros siguen la estructura CTF, que consiste en encontrar una clave escondida tras un archivo o la IP de un servidor. Al no tener enunciado, es necesario aplicar el pensamiento lateral y tener ciertos conocimientos sobre un tema. Hay muchos CTF sobre seguridad informática al año.

Tuenti Challenge destaca por la variedad de problemas de ambos tipos. En esta edición ha habido niveles tales como una escape room via SSH a un servidor que sólo funciona con emojis, calcular el CRC32 de archivos de 200GB ultra-comprimidos o construir el mayor castillo de papel higiénico posible con los rollos de un supermercado.

Nivel 1: Rock, Paper, Scissors

El primer problema suele ser algo simple para ir calentando, así que voy a aprovechar para explicar cómo proceso la entrada y genero la salida. Suelo resolver todos los problemas usando Python por su cercanía al pseudocódigo que hace tan fácil probar nuevas ideas rápidamente.

Diagrama de piedra, papel o tijera

El problema consiste en averiguar qué figura ganaría en un juego de piedra, papel o tijera. Al ser un problema en formato ICPC, la entrada es un archivo de texto cuya primera línea es el número de casos N (partidas de piedra, papel o tijera) y cada una de las N siguientes líneas se corresponde a un caso.

4
R S
R P
P P
S P

Con una entrada como la anterior, debemos generar un archivo de salida en el que cada línea sea el resultado de uno de los casos siguiendo el formato Case #n: result. Para nuestro ejemplo, la salida esperada es la figura ganadora, o - en caso de empate.

Case #1: R
Case #2: P
Case #3: -
Case #4: S

Primero debemos procesar un archivo de prueba llamado testInput.txt que contiene unos pocos casos pequeños. Cuando lo resolvemos, obtenemos el archivo submitInput.txt en el mismo formato y con muchos más —y casi siempre más complejos— casos de prueba. La idea es usar el test para comprobar que nuestro algoritmo funciona bien, y el submit para que puedan evaluar nuestra solución.

FNAME = 'test'

def load_input():
    with open('%sInput.txt' % FNAME, 'r', encoding='utf-8') as fp:
        problems = int(fp.readline())
        for p in range(problems):
            yield sorted(fp.readline().strip().split(' '))

Esta es la forma en la que suelo cargar el archivo de entrada en estos problemas. Ir iterando línea a línea y usar un generador mediante la sentencia yield hace que estos problemas se procesen de una forma muy natural. En ninguno de ellos he tenido que dedicar demasiado tiempo a adaptar la entrada y eso me permite centrarme en el problema. El único tuning que ha sufrido en este caso es la función sorted, que me asegura que las figuras de la partida lleguen en orden alfabético.

def main():
    output = ''
    for p, problem in enumerate(load_input(), 1):
        print('Solving case #%d' % p)
        output += 'Case #%d: %s\n' % (p, solve(*problem))
    with open('%sOutput.txt' % FNAME, 'w', encoding='utf-8') as fp:
        fp.write(output)

La función main es el punto de entrada de este script, y va leyendo los problemas uno a uno para obtener su solución llamando a la función solve. Al usar el operador * como argumento de solve, esta función recibe como entrada los mismos parámetros que devuelve el generador.

def solve(p1, p2):
    if p1 == 'R' and p2 == 'S':
        return 'R'  # rock beats scissors
    elif p1 == 'P' and p2 == 'R':
        return 'P'  # paper beats rock
    elif p1 == 'P' and p2 == 'S':
        return 'S'  # scissors beats paper
    else:
        return '-'  # it's a draw

Sabiendo que las figuras de ambos jugadores llegan ordenadas, la solución se obtiene de forma muy sencilla. Y con esto podemos resolver el problema de test, descargar el archivo submit y cambiar FNAME para procesarlo de la misma forma.

Nivel 2: The Lucky One

Este nivel en formato ICPC nos da como entrada una lista de partidas de ping-pong y tenemos que averiguar cuál es el mejor jugador. Como el problema asegura que la solución es única y que no es posible el empate, podemos deducir que hay un jugador que nunca ha perdido una partida.

def solve(matches):
    players = set()
    losers = set()
    for p0, p1, p1_loser in matches:
        players.update((p0, p1))
        losers.add(p1 if p1_loser else p0)
    return max(players.difference(losers))

Así, podemos ir recorriendo la lista de partidas creando un conjunto de jugadores que hemos visto y otro de jugadores que han perdido alguna vez. Tras iterar sobre todas las partidas, el mejor jugador es el único del conjunto de jugadores que no aparece en el de perdedores.

Nivel 3: Fortunata and Jacinta

Este nivel es un homenaje al novelista Pérez Galdós en el centenario de su muerte. Dada una versión en txt de su novela magna, tenemos que convertir a minúsculas todo el documento, identificar las palabras como un conjunto de tres o más letras del alfabeto español y ordenarlas por frecuencia siguiendo el orden unicode en caso de empate.

from collections import Counter  # frequency counter
from regex import compile  # unicode-aware regex library

REMOVE_INVALID = compile(r'[^abcdefghijklmnñopqrstuvwxyzáéíóúü]+').sub
SPACE_SPLIT = compile(r'\s+').split

_ctx_by_word = {}
_ctx_by_rank = {}
def load_context():
    global _ctx_by_word, _ctx_by_rank
    text = SPACE_SPLIT(REMOVE_INVALID(' ', text).strip())
    text = [word for word in sorted(text) if len(word) >= 3]
    text = Counter(text).most_common()
    for rank, (word, frequency) in enumerate(text, 1):
        _ctx_by_word[word] = '%d #%d' % (frequency, rank)
        _ctx_by_rank[rank] = '%s %d' % (word, frequency)

Para crear este ranking he usado una expresión regular para reemplazar por espacios todos los caracteres no deseados y otra para separar las palabras. Después, la librería built-in collections nos permite crear un ranking por frecuencia sin esfuerzo, y con él construir los dos rankings que necesitamos para este problema:

def solve(line):
    if line.isnumeric():
        return _ctx_by_rank[int(line)]
    else:
        return _ctx_by_word[line]

Habiendo construido estos rankings al empezar, la resolución del problema es así de simple. Sólo tenemos que ver si la entrada es un número para devolver una salida u otra.

Nivel 4: My Favorite Video Game

Aquí empiezan los problemas que se salen de lo habitual. Este nivel de tipo CTF nos habla de una compañía de videojuegos llamada Steam-Origin (como si Valve y EA no fueran suficientemente grandes por sí solas), que tiene una API para obtener claves de sus juegos.

$ curl steam-origin.contest.tuenti.net:9876/games/free_shoot/get_key
{"game":"Free Shoot","key":"9999-9999-9999"}

La compañía es conocida por sus fallos de seguridad, y la semana que viene va a publicar su nuevo juego, Cat Fight, que quieres conseguir a toda costa. Recientemente han publicado una presentación técnica en Prezi que revela información clave para conseguir el juego antes que nadie.

Prezi con información sobre los entornos de producción y pre-producción

Sus entornos de pre- y producción comparten la base de datos y un balanceador de carga externo, pero al de preproducción sólo se puede acceder desde su VPN en la dirección pre.steam-origin.contest.tuenti.net. Este balanceador de carga no está muy fino:

from requests import get

URL = 'http://steam-origin.contest.tuenti.net:9876/games/cat_fight/get_key'
HEADERS = {'Host': 'pre.steam-origin.contest.tuenti.net:9876'}

data = get(URL, headers=HEADERS).json()
with open('key.txt', 'w') as fp:
    fp.write(data['key'])

La cabecera Host ayuda al servidor a identificar a qué dominio se está enviando cierta petición de entre los alojados en un servidor. Esta cabecera es suficiente para confundir al balanceador de carga, hacerle creer que estamos dentro de la VPN y obtener sin restricciones una clave del juego.

Nivel 5: Tuentistic Numbers

Se define un número "tuentístico" como aquel que pronunciado en inglés contiene la palabra twenty. Por ejemplo, 20, 21 o 120000 son números tuentísticos. Dado un número entre 1 y 262, debemos averiguar cuál es la mayor suma de números tuentísticos que lo representa.

Este es el primer problema en el que los límites empiezan a ser relevantes. Con números tan grandes como 262 no nos podemos plantear probar todas las sumas posibles. En su lugar, debemos buscar una simplificación que nos permita hacer este cálculo rápidamente.

Una posibilidad es usar sólo los números tuentísticos más pequeños; aquellos entre 20 y 29. De esta forma, la menor cantidad de números a sumar será siempre n / 29 y la mayor cantidad será n / 20, redondeando hacia abajo.

def solve(n):
    mn = n // 29 + (1 if n % 29 else 0)
    mx = n // 20
    if mn > mx:
        return 'IMPOSSIBLE'
    else:
        return mx

Y esto es todo lo que debemos hacer, considerando un par de excepciones: si el número no es divisible entre 29, tendremos que añadir un término más a la suma, y si la menor cantidad de números a sumar es mayor que la mayor cantidad, este problema es imposible.

Nivel 6: Knight Labyrinth

De nuevo un nivel de tipo CTF, que me resultó especialmente divertido. Dada una IP para acceder a un laberinto en formato texto que sólo nos muestra las casillas de nuestro alrededor, debemos movernos por ellas mediante el salto del caballo de ajedrez para rescatar a una princesa.

Posiciones del tablero de ajedrez

En esta ocasión he intentado llegar a la solución más rápida posible haciendo algunas optimizaciones:

Representación del laberinto completo

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!

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.

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.

Nivel 18: Matters with Formatters

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).

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 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

Haciendo scraping en paralelo

Todo el que haya hecho un poco de Web scraping en algunos lenguajes como Python, se habrá topado con un problema muy habitual: las peticiones de red bloqueantes.

Aunque el scraper tarde unos pocos milisegundos en procesar el HTML, tener que descargarse 10 páginas de forma secuencial hace que el tiempo de ejecución crezca considerablemente. Para sortear este problema, hay muchas alternativas. Veamos algunas de ellas con un ejemplo.

Supongamos que queremos descargarnos los primeros 1000 cómics de XKCD. Un script sencillo sería el siguiente:

from requests import get

URL = "https://xkcd.com/%s/"

pages = []
for n in range(1, 1001):
  print("Downloading page %s" % n)
  pages.append(get(URL % n))

El módulo threading

Con este módulo podemos crear varias threads, y hacer muchas peticiones de forma simultánea:

from requests import get
from threading import Thread

URL = "https://xkcd.com/%s/"
pages = []

def down(n):
  print("Downloading page %s" % n)
    pages.append(get(URL % n))

threads = [Thread(target = down, args = (n,)) for n in range(1, 1001)]
[t.start() for t in threads]  # start all threads
[t.join() for t in threads]  # block until all threads finish

Esto acelera considerablemente el programa, que pasa de tardar unos 17 minutos en mi ordenador, a unos aceptables 17 segundos. Pero el problema sigue ahí: si en lugar de 1000 páginas fueran 10000, ¿sería el procesador capaz de manejar tantísimos hilos de forma óptima? ¿daría con un número máximo de threads?.

El módulo threading con workers

Una alternativa es la creación de workers: un número limitado de threads que no descargan una única página, sino que van descargando páginas hasta obtenerlas todas.

from requests import get
from threading import Thread

URL = "https://xkcd.com/%s/"
WORKERS = 20
pages = []

to_download = [URL % n for n in range(1, 1001)]

def worker():
  while len(to_download):
     url = to_download.pop()
     print("Downloading page %s" % url)
     pages.append(get(url))

workers = [Thread(target = worker) for _ in range(WORKERS)]
[w.start() for w in workers]  # start all workers
[w.join() for w in workers]  # block until all workers finish

En mi ordenador, tarda unos 21 segundos en hacer la descarga completa, pero la carga del procesador es mucho menor en este caso. Volvemos a la limitación anterior, ante un gran número de páginas a descargar, se vuelve bastante lento. Pero aun nos queda una opción.

El módulo grequests

Este módulo tiene la misma interfaz que requests, con la diferencia de que al importarlo hay que poner una G por delante. Su instalación desde pip es muy sencilla, y permite hacer las peticiones de forma asíncrona mediante la librería Gevent. Al hacer una petición de varias páginas, grequests crea y gestiona las corrutinas para descargarlas.

from grequests import get, map

URL = "https://xkcd.com/%s/"

reqs = [get(URL % n) for n in range(1, 1001)]
print("Downloading all pages")
print(map(reqs))

Este código es mucho más sencillo e intuitivo que los anteriores. Además, descarga las 1000 páginas en apenas 15 segundos sin sobrecargar el procesador en absoluto.

Cómic de XKCD

Existen otras alternativas que aun no he explorado, como requests-threads y requests-futures. Si conoces más sobre este tema, no dudes en dejar un comentario!

No hay comentarios

Diffchecker: comparando secuencias

Si alguna vez has programado alguna vez usando un repositorio, habrás usado una herramienta de diff para comparar el código antiguo y el nuevo, y detectar qué fragmentos han cambiado y qué fragmentos son comunes a ambos.

Ejemplo de diff checking

Este algoritmo parece sencillo hasta que nos paramos a pensar en su funcionamiento un rato. Por ejemplo, si queremos comparar las palabras schwarzenegger y chuarcheneger, obtenemos el siguiente resultado:

  ANTES:  s c h w a r z . e n e g g e r
DESPUES:  . c h u a r c h e n e g . e r
CAMBIOS:  - = = / = = / + = = = = - = =

En el cambio hemos eliminado 2 letras, modificado 2 letras y añadido una letra. Este análisis, que no es tan simple de realizar con nuestra inteligencia natural, tampoco tiene una solución algorítmica trivial.

Subsecuencia común más larga (LCS)

En algoritmia, este problema se conoce como LCS. El objetivo de LCS es, dadas dos secuencias, encontrar la subsecuencia más larga que ambas tienen en común.

Como las herramientas de diff sólo comparan entre sí dos cadenas, existe una solución mediante un algoritmo divide y vencerás, que va reduciendo el problema a otros problemas más pequeños. Así, se puede definir el problema de la siguiente forma:

def LCS(X, Y):
    if len(X) == 0 or len(Y) == 0:
        return []
    if X[-1] == Y[-1]:
        return LCS(X[:-1], Y[:-1]) + [X[-1]]
    else:
        return longest(LCS(X, Y[:-1]), LCS(X[:-1], Y))

Donde longest es una función que sencillamente devuelve la cadena más larga:

def longest(X, Y):
 return X if len(X) > len(Y) else Y

Teniendo el algoritmo LCS (que podéis probar en Python), es fácil averiguar qué se ha añadido, eliminado, o modificado al comparar dos cadenas. Sin embargo, es un algoritmo muy lento. Basta con que pongamos dos cadenas algo más largas (como arn. schwarzenegger y ar. chuarcheneger) para que el tiempo de ejecución se dispare.

Por eso es necesario el uso de una memoria que almacene los resultados, a fin de no tener que computarlos más de una vez. Haz la prueba:

Esta es la base de este algoritmo, aunque hay que detallar ciertos matices para que funcione correctamente; convertir el algoritmo recursivo en uno iterativo para evitar exceder el límite de recursión, utilizar estructuras de datos que permitan un cálculo más eficiente, o tokenizar las secuencias para considerar que cada elemento puede ser una fila de código o una palabra en lugar de un caracter.

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í.