Hack It 2 — Bowling Physics

Este nivel no tiene enunciado. Ni una frase. No hay más que el título, un formulario de contraseña y dos imágenes PNG que a simple vista no son nada: confeti de colores, como la nieve de un televisor mal sintonizado pero en color.

La primera versión de este writeup contaba una historia falsa: que los datos eran decoración y que la contraseña era un juego de palabras del título. La contraseña estaba escrita con letras dentro de esos datos, y el reto deja el camino casi entero a la vista — hay un solo paso que no se deduce y hay que probarlo. Va aquí ese camino. Lo que hicimos nosotros fue otra cosa, y está al final.

1. Lo que hay y lo que falta

En la página del reto solo hay dos ficheros:

/hackit/2/static/p.png      256 x 256, 16-bit RGB
/hackit/2/static/v.png      256 x 256, 16-bit RGB

p.png arriba, v.png debajo. Que una sea confeti y la otra tire a gris no es casualidad — en p los tres canales de un mismo píxel difieren entre sí un 19,4% de media, y en v solo un 4,9%: las velocidades tienen menos recorrido que las posiciones, así que sus tres canales van más juntos y el color se apaga. Ninguna de las dos se parece a lo que sale al final de este post.

Conviene fijar qué es una de estas imágenes por dentro, porque todo lo que viene depende de ello. Son 256 filas por 256 columnas, y cada píxel guarda tres números de 16 bits: los tres canales de color, que aquí no llevan color sino datos. En total, 65.536 píxeles y 196.608 números por fichero. Y una fila, leída entera, son 256 píxeles por 3 canales: 768 números seguidos.

A partir de aquí, a cada uno de estos ficheros lo llamaré tabla de datos: 256 filas de 768 números. Los nombres dicen qué hay en cada una: posiciones y velocidades.

Dentro de v.png hay además un programa escondido. No hace falta para leer la contraseña, pero tampoco es decorado: vuelve en el apartado 5 con un papel muy concreto.

Falta un tercer fichero, y el HTML lo enseña. Lleva un comentario, y es el único comentario propio de la página; los otros dos son condicionales de Internet Explorer que arrastra la plantilla del concurso:

<!-- <img src="/hackit/2/static/m.png" width="256" heigth="256"> -->

m.png devuelve 404. No es que esté escondido, es que no existe. El autor comentó la etiqueta a propósito y dejó la referencia a la vista, con sus dimensiones puestas: 256×256, un dato que más adelante sirve para descartar operaciones, aunque no para elegir la buena.

2. Los nombres son la fórmula

p, v y una m que falta. Con un título que dice Physics, son las tres letras de una fórmula de instituto:

p = m · v          momento lineal

Lo que decide qué pasa cuando una bola choca contra los bolos, que es literalmente el tema del nivel. Y el giro, que tardamos en ver, es que el reto no te pide reconocer la fórmula, te pide despejarla. Te da dos de los tres términos y te quita el tercero. Falta m:

m = p / v

Esa es la notación de todo lo que viene y no cambia más: p son las posiciones, v las velocidades, m lo que hay que reconstruir.

El fichero que falta no es una pista suelta ni un guiño. Es el objetivo, y hay que reconstruirlo.

3. Dividir dos tablas es multiplicar por la inversa

Lo primero que se prueba es dividir píxel a píxel, cada número de p entre el que le toca de v. No sale nada, y tampoco tenía por qué salir.

Porque p y v no son dos números, son dos tablas de 256 filas, y dividir una tabla entre otra no es una división de las de repartir. Es la misma idea puesta del revés: igual que dividir entre 4 es multiplicar por un cuarto, dividir entre una tabla es multiplicar por su contraria, lo que en matemáticas se llama su inversa. Escrito entero, dividir la tabla A entre la tabla B es esto:

A / B  =  A · Bᵀ · (B · Bᵀ)⁻¹

Lo que importa no es la notación, son las dos piezas. La primera, A·Bᵀ, es la tabla de parecidos: cada fila de A comparada, una a una, con cada fila de B. Comparar dos filas es multiplicarlas número a número y sumar los 768 resultados; si van a la par sale un valor grande, y si no tienen nada que ver sale casi cero. En jerga eso se llama proyectar, pero aquí lo voy a llamar comparar y ya no lo cambio. La segunda pieza, la inversa, es una corrección que le quita el sesgo a esa tabla de parecidos; qué sesgo exactamente es la gracia del apartado 7.

De momento quédate con el tamaño. Comparar las 256 filas de una tabla de datos contra las 256 de la otra da 256 × 256 parecidos, o sea una tabla de 256 filas por 256 columnas. Esa es la tabla de aquí en adelante —la tabla de resultado, la que se construye, no las de datos— y cada uno de sus 65.536 huecos es una casilla.

256×256 es exactamente lo que el comentario del HTML anunciaba para m.png. Ese dato no señala qué operación hay que hacer —cualquier comparación de filas contra filas da 256×256—, pero confirma el tipo: una tabla de todos contra todos, no una división punto a punto.

4. El único paso que hay que probar

Queda una pregunta que la fórmula no contesta: cuando digo «fila», ¿es la fila o la columna? Una imagen se puede recorrer en horizontal o en vertical, y hay que elegir en las dos tablas de datos, así que salen cuatro combinaciones. Es el único punto del reto que no se deduce. Se prueba, y cada una cuesta una línea de código.

Para comparar las cuatro hace falta un criterio, y el nuestro es contar casillas raras: cuántas se salen tanto de lo normal que el azar no lo explica. Aquí y en el resto del post voy a medir en sigmas: una sigma es lo que se desvía una casilla cualquiera por puro azar, así que «3,5 sigmas» quiere decir tres veces y media eso, y a partir de ahí una casilla ya no es normal. La diagonal se excluye del recuento, porque ahí siempre pasa algo. Con esa misma vara para las cuatro:

p por filas    / v por filas       220 casillas raras   el 100% dentro de 36 filas   <--
p por filas    / v por columnas     30 casillas raras   el 3%
p por columnas / v por filas        28 casillas raras   el 18%
p por columnas / v por columnas      5 casillas raras   el 0%

No hay ambigüedad posible, y el discriminante es doble: no solo son siete veces más casillas, es que no están desperdigadas. Las 220 caen todas dentro de 36 filas, y esas 36 filas no están sueltas por ahí: son cuatro bloques seguidos de nueve, las filas 105-113, 118-126, 131-139 y 144-152. Un patrón agrupado no lo hace el azar. En las otras tres combinaciones lo que sale es un puñado de casillas sin relación entre ellas, que es justo lo que sale al medir cualquier cosa con un umbral apretado.

Gana la fila. El scanline, que es como se escribe una imagen.

5. El despeje, en una línea

Con la orientación resuelta, el despeje literal del apartado 2 —m = p/v, tal cual— cabe en una línea:

m = p @ np.linalg.pinv(v)        # p = m·v  ->  m = p·v⁻¹

pinv es la inversa de la fórmula del apartado 3, en la versión que numpy trae de serie para tablas que no son cuadradas (v mide 256×768). No hay nada más: ni ajustar un modelo previo, ni restar nada, ni saber dónde mirar. Escribes la ecuación, la despejas, y la tabla que sale ya lleva dentro las dos cosas que quieres.

La primera es la diagonal: la casilla de la fila 1 contra la fila 1, la de la 2 contra la 2, y así hasta el final. Vale 10,2327, repetida: cada fila de posiciones es diez veces la misma fila de velocidades, una a una, y la operación que hiciste para despejar te devuelve el coeficiente con cuatro cifras, de regalo y sin pedirlo. Qué número es ese exactamente lo dejo para el final del apartado, porque para decirlo hace falta el chunk.

La segunda es el texto. Las casillas del mensaje salen altas, no bajas: se disparan por encima del fondo. En la ventana donde está el dibujo hay 237 casillas de 972 por encima de 3,5 sigmas, con la señal a 7,4 sigmas, y en las filas de fondo, las que no llevan nada, cero falsos positivos. Los 19 que se cuentan fuera de la ventana caen todos en las filas del texto, y 18 son la propia diagonal: en las filas 105-113 y 144-152 la casilla diagonal queda fuera del rango de columnas de la ventana, así que el 10,23 de la diagonal entra en el recuento como si fuera una anomalía. Falsos positivos de verdad, uno.

El texto sale de los píxeles a pelo; ese 10,2327 no, y aquí es donde vuelve el programa escondido. En v.png hay un chunk de texto que a simple vista está vacío, y no lo está: es Whitespace, un lenguaje esotérico que se escribe solo con espacios, tabuladores y saltos de línea. La palabra que importa es lenguaje: eso no es el texto cifrado, es el código fuente de un programa. Hay que ejecutarlo, no descifrarlo.

Por qué pasa desapercibido: a la izquierda, el chunk tal como lo enseña cualquier visor de texto; a la derecha, el mismo contenido con los caracteres invisibles pintados. Abajo, lo que imprime al ejecutarlo — con una q delante, que es como el autor llama a las posiciones: la notación de física que aquí no adoptamos.

Son 392 bytes —215 espacios, 120 tabuladores y 57 saltos— y usa dos instrucciones que se van alternando. espacio espacio mete un número en la pila, y detrás va el número escrito en binario, con espacio de 0 y tabulador de 1, hasta que un salto de línea lo cierra. tabulador, salto, espacio, espacio imprime como carácter lo que acabas de meter. De ahí los pares de líneas de la figura: la larga es el número, la corta de debajo es la orden de imprimirlo.

La primera línea de la imagen es ···→→→···→, y se lee entera: mete un número, positivo, bits 1110001. Eso es 113, y 113 es el código ASCII de la q. Veintisiete pares después, un carácter por par, la salida es:

q v_min = -0.2, v_max = 0.2

Es el programa más tonto que se puede escribir: no calcula nada, lleva los códigos ASCII a pelo y los escupe uno a uno. Un «hola mundo» de 392 bytes.

Y lo que imprime no es exactamente una escala: es dónde está el cero. Un PNG guarda enteros sin signo, de 0 a 65535, y casi la mitad de las velocidades son negativas —el 44,95%—. Así que el autor estiró el rango real hasta el de los enteros al guardar, y te dejó escrito por dónde deshacerlo: dividir entre 65535 —que es 2¹⁶−1, el mayor que cabe— los deja entre 0 y 1, el 0,4 les da el ancho y el −0,2 los pone a caballo del cero. De las tres operaciones, la única que lleva información es la última. De p no declara nadie nada, y no es un olvido: las posiciones no son negativas nunca y ocupan el 0-1 exacto, que es la caja donde viven. Dividir entre 65535 no las desnormaliza, las devuelve tal como salieron del generador. No hay chunk para p porque no hay nada que declarar.

Y aun así el dibujo sale sin nada de esto: con los enteros crudos salen 219 casillas y el texto se lee igual de bien. La razón cabe en una línea de álgebra, pinv(c·v) = pinv(v)/c — multiplicar todas las velocidades por un número multiplica la tabla entera por su inverso, casilla a casilla por igual, y como el texto se lee comparando cada casilla contra la desviación de las demás, ese factor se cancela arriba y abajo. Medido: cambiar la escala mueve el bitmap cero píxeles.

Donde sí cambia todo es en la diagonal, y conviene desmontar el salto, porque sus dos mitades no valen lo mismo:

 3,9410   los enteros entre 0 y 1, sin más
 9,8524   x2,5 al aplicar el ancho 0,4     <- factor global exacto: cambio de unidad y nada más
10,2327   +3,86% al restar el 0,2          <- lo único que aporta de verdad el chunk

Y ahora sí, qué es 10,2327 — que es donde hay que corregir el chiste. m es la tabla que cumple m·v ≈ p, la que convierte velocidades en posiciones, así que sus unidades son posición partido por velocidad: tiempo. Para que fuera una masa, p.png tendría que llevar momentos, y no los lleva. v es negativa el 45% de las veces y p no lo es ni una sola. Si p fuera m·v píxel a píxel con m positiva, todos esos valores tendrían que salir negativos, y ninguno lo hace: sobre los píxeles, la ecuación del título es imposible.

Así que 10,2327 es un tiempo — el de Hubble, la edad de este universo de juguete, el inverso de esa constante de ~0,1 que ata cada velocidad a su posición y que vuelve a asomar en el apartado 7. p = m·v es el gancho que te trae hasta la operación; la operación, ejecutada, devuelve un tiempo. Y «unidades» tampoco era la palabra: el chunk dice −0,2 sin decir de qué, y en todo el reto no hay una sola unidad física. Lo que te da es una convención — sin ella tú y yo sacamos números distintos del mismo fichero; con ella, el mismo. El chunk no abre ninguna puerta: pone a todo el mundo a medir con la misma vara.

6. m.png

Con el cero en su sitio, ya solo queda mirar la tabla. Y no hay que saber dónde mirar: se dibuja entera como una imagen y el texto está ahí, con su antialiasing de fuente de verdad:

El fichero que faltaba. Nadie lo borró: nunca estuvo, y esto es lo que sale al despejarlo: las letras salen claras, sin invertir nada, porque sus casillas valen alto. Con un retoque, y conviene decirlo: la diagonal cruzaba la imagen de esquina a esquina y tachaba el texto, así que aquí va tapada. El moteado es ruido de verdad y está a propósito: sin él, esto parecería un dibujo.

Y no hay nada más detrás. El PNG de arriba sale entero de esto:

p = read16('p.png') / 65535.0
v = read16('v.png') / 65535.0 * 0.4 - 0.2
m = p.reshape(256, -1) @ np.linalg.pinv(v.reshape(256, -1))

fuera = ~np.eye(256, dtype=bool)
m = (m - m[fuera].mean()) / m[fuera].std()   # en sigmas
np.fill_diagonal(m, np.median(m[fuera]))     # la diagonal fuera: tapaba el texto
z = np.clip((m + 3.5) / 9.5, 0, 1)           # gris entre -3,5 y +6 sigmas

read16 es el decodificador de PNG de 16 bits del repo —numpy puro, porque PIL no lee del todo bien el 16-bit RGB—. Las tres primeras líneas son los apartados 4 y 5 puestos en fila: leer los dos ficheros, ponerle a v la escala que dio el chunk, y comparar fila contra fila. El resto es el revelado, y ahí está el retoque: se pasa la tabla a sigmas con la media y la desviación medidas fuera de la diagonal, se rellena la diagonal con la mediana del fondo —vale 126 sigmas contra las 7,4 del texto, por eso lo tachaba— y se estira a gris el tramo que va de −3,5 a +6 sigmas.

Ampliado, con las cuatro líneas separadas — cada una de nueve píxeles de alto, que son los cuatro bloques de nueve filas que salieron en el apartado 4:

M4d + F0r + mUL + 4  =  M4dF0rmUL4  =  "Mad Formula"

Y el chiste cierra el nivel: la contraseña es el nombre de la fórmula que has tenido que despejar para leerla. En leet, que es la norma de la casa — en esta misma edición, C4M1NOS, h0LyGr4IL, 4roM4Noc7urNo.

Las letras no están escritas en ninguna parte. El autor cogió 36 filas de v y a cada una le restó un múltiplo minúsculo de una fila concreta de p; el dibujo está en el patrón de qué múltiplo va en qué fila. Y minúsculo es literal: ese múltiplo vale 0,00519 contra el 0,0996 de la física que ya lleva la fila encima, una diecinueveava parte de lo que lo tapa. Por eso mirar los píxeles no sirve de nada: en la imagen, el mensaje está repartido entre 196.608 números y cada uno lleva una miga que se pierde bajo el ruido. Solo se concentra al comparar contra las filas de p, que son las que hacen de clave. Es lo mismo que hace el GPS: la señal del satélite llega más débil que el ruido del propio receptor, y solo aparece cuando el aparato la compara con el código que ya conoce.

Y hay una manera de medir cuánto margen tiene eso. ¿Hacían falta los 16 bits? No. Recuantizando los dos PNG a 8 y repitiendo el despeje entero, el texto sale idéntico: las mismas 237 casillas de 972, ni una distinta. A 5 bits todavía se lee, con 208; muere entre 5 y 4, donde se cae a 95 y se rompe. Lo llamativo es por dónde aguanta: cada portadora mueve una muestra de v 0,96 pasos de cuantización de 8 bits, o sea menos de un escalón, así que por sí sola se redondearía a nada. Sobrevive porque cada fila lleva unas seis a la vez, y sobre todo porque la detección no mira una muestra, suma 768. Eso es exactamente lo que significa espectro ensanchado: la señal está por debajo del ruido en cualquier punto que mires y solo existe en el agregado.

7. El camino que hicimos nosotros

Esa comparación contra p es justo lo que hace la línea del apartado 5, y no tiene ninguna trampa. Pero hay un atajo para llegar a lo mismo, el que sale solo cuando estás delante de los datos, y merece la pena contarlo porque explica para qué sirve exactamente la inversa.

Comparar en vez de invertir. El atajo es quedarse con la primera pieza de la fórmula del apartado 3 y tirar la segunda: comparar cada fila de v con cada fila de p y ya está. Multiplicar por la transpuesta en lugar de por la inversa. Es lo que uno hace cuando piensa «¿a cuál de estas se parece esto?», y cuesta una multiplicación de tablas y nada más.

Por qué se parece a invertir. Las dos cosas coinciden exactamente en un caso: si las filas de p fueran perpendiculares entre sí, es decir, si cada una no tuviera absolutamente nada en común con las demás. Y p está muy cerca de eso. Sus 196.608 números son un sorteo uniforme: cada uno salió por su cuenta, sin arrastrar nada del anterior y sin patrón que enlace una fila con la siguiente. Dos filas así se parecen un 3,6%, y ese número no hay que creérselo, sale de una cuenta. Al comparar dos filas multiplicas 768 pares y sumas; los productos salen con signo al azar y se cancelan entre sí, así que la suma no crece como 768 sino como su raíz cuadrada. Puesto en proporción, el parecido esperado entre dos filas cualesquiera de N números es 1 entre la raíz de N: 1/√768 = 0,036. Con un parecido tan bajo, comparar y dividir vienen a ser casi lo mismo — y ese casi es todo lo que sigue.

Por qué aun así hay que restar. Un 3,6% no es cero. Compara v contra p y en la diagonal aparece 0,0996: cada fila de velocidades es 0,1 veces la misma fila de posiciones. Es la operación del apartado 5 mirada del revés, así que la diagonal también sale del revés — en vez del tiempo, su inversa. El problema es que ese término no se queda en su casilla. Fíjate en una de las que deberían dar cero: la fila 7 de v comparada con la fila 200 de p, dos filas cualesquiera, sin relación entre sí. Pero la fila 7 de v lleva dentro su propia fila de p, y esa fila se parece un 3,6% a la 200. Así que la casilla no da cero, da un pelín. Y como pasa en las 65.536 casillas a la vez, la tabla entera queda cubierta por un derrame de magnitud 3,7e-3, contra un ruido real de 8,2e-4: cuatro veces y media el ruido de verdad. El mensaje no está debajo del ruido, está debajo del derrame.

Es la filtración de los micrófonos: por muy bien que apuntes uno al bombo, la caja se le cuela igual. Si quieres oír algo flojo, lo primero es apagar lo que suena fuerte. Y ojo, que aquí lo que suena fuerte no es un defecto: es la física del nivel, puesta a propósito. Solo que tapa. La diferencia con el ruido de verdad —el moteado aleatorio del generador— es que esto lo conoces exactamente, con cuatro cifras, porque acaba de salir en la diagonal. Así que lo apagas y vuelves a comparar:

res = v - 0.0996 * p        # apaga lo que suena fuerte, que ya lo conoces

El resultado. Con el derrame encima, el mensaje estaba a 2,5 sigmas: invisible en la práctica. Apagado, pasa a 11,2 sigmas y salen 215 casillas, calidad equivalente a la del camino canónico; la diferencia con las 237 de aquel son píxeles de borde de los glifos. Como es la operación mirada del revés, el texto también sale del revés: casillas bajas donde el canónico las daba altas. Si buscas manchas oscuras por un lado y claras por el otro, las dos se leen igual de bien; si buscas siempre lo mismo, una de las dos parece vacía.

Y el remate, que es lo que hace que el apartado tenga sentido: apagar ese término en el camino canónico no habría servido de nada. Restar 0,0996·p antes de multiplicar por la inversa solo cambia la diagonal y deja el resto de la tabla intacto, porque (v − a·p)·pinv(p) = v·pinv(p) − a·I. Por eso la línea del apartado 5 no necesita el paso extra: la inversa ya descuenta el parecido entre las filas por construcción. Es literalmente para lo que está.

Lo que nos llevamos

Nosotros no lo resolvimos así. Fuimos por el otro lado —caracterizar los datos con estadística en vez de despejar la fórmula— y llegamos hasta un paso del final: teníamos localizadas al píxel las cuatro bandas donde estaba el texto, y escribimos que eran ruido del generador. La contraseña la sacamos por intuición, leyendo p, v y la m que falta como un chiste sobre una fórmula. Acertó, y por eso dimos el nivel por cerrado con el análisis archivado y una conclusión falsa dentro. El relato completo de ese rodeo, con los números y los callejones, está en el repo.

De ahí salen dos cosas que valen fuera de aquí. La primera, que acertar la respuesta no valida el razonamiento: cuando el resultado llega por una vía y la investigación iba por otra, el acierto tapa el error en lugar de corregirlo, y encima le da autoridad.

La segunda, que detectar una anomalía y explicarla no es lo mismo. «El generador metió más ruido ahí» no dice por qué en cuatro bloques, por qué de nueve filas, ni por qué con ese espaciado. Una explicación que no predice ninguno de los detalles que ya has medido no es una explicación, es una etiqueta.

Y lo más específico de este nivel: el enunciado estaba en los nombres de los ficheros. p, v y una m ausente de 256×256 no eran un guiño temático, eran una instrucción con las dimensiones del resultado puestas. Nos quedamos con la mitad — vimos la fórmula, nos gustó como chiste y sacamos la contraseña de ahí, sin llegar a leerla como la operación que había que ejecutar sobre los datos.

Solución:

M4dF0rmUL4

El material — los scripts, las imágenes del reto y el writeup técnico completo, incluidos solve_inversa.py, que hace el despeje en una línea, y solve.py, que reconstruye m.png por el atajo del apartado 7, están en euskal34/hack-it/2.