Los falsificadores de entradas

―¡Carlos, Carlos! ¡Espera un momento!― gritó Paula a través de la ventana del primer piso del instituto ―Notición: nos vamos al concierto de SUPERSTAR.

Carlos miró a Paula con escepticismo.

―Paula, perdona, el concierto se suspendió. Algo de entradas duplicadas, o se pasaron con el aforo… no sé.

―¡Exacto!― gritó Paula―. Lo han aplazado hasta la semana que viene. Y en el Aula de Tecnología han puesto en marcha un concurso. Hay que contestar tres preguntas y ¡el premio son dos entradas!

A Carlos le encantaba SUPERSTAR, así que se sentó pacientemente mientras Paula soltaba emocionada un torrente de información.

―El concierto se suspendió porque tuvieron varios problemas con la validación de entradas. Verás, cada entrada tiene un número, y para validarlas más rápido, ese número se resumía a través de una transformación que se llama función hash o función resumen. En la puerta del estadio tenían un lector que comparaba el resumen de cada entrada con la lista de resúmenes válidos, para autorizar o no el paso.

―Me está empezando a dar pereza…― protestó Carlos. ―¿Qué es eso de función resumen?

Paula prosiguió, implacable. ―Una función resumen es una función matemática que toma un valor, por ejemplo una ristra de números de cualquier longitud, como el número de una entrada, y te devuelve un resumen, es decir, una secuencia de números corta. Este proceso es irreversible, es decir, si te dan el resumen no puedes volver atrás y recuperar la secuencia de partida. Por otro lado, con la misma entrada, la función te devuelve siempre la misma salida. Paula pintaba dos círculos con puntos y unas flechas en la tierra del paseo, representando lo que estaba explicando.

Estos resúmenes se usan para muchas cosas. Por ejemplo, para detectar y corregir errores al transcribir un número grande; justo ese es el papel de la letra de nuestro DNI, que es un resumen de los dígitos que la preceden. También sirven para detectar si alguien añade un virus a un programa que te bajas de internet: puedes comprobar si el resumen del código que te has bajado coincide con el que está publicado en la web de quien te ofrece el programa. Si no es así, alguien ha modificado el archivo mientras viajaba por la red.

―Y eso no es bueno…― interrumpió Carlos.

―No. Mala señal. Otras veces, se usan los resúmenes para, por ejemplo, acelerar procesos, imagínate que en lugar de llamarnos en el instituto usando nuestro número entero de matrícula, usaran sólo los dos últimos dígitos.

―Pues menudo lío montarían— saltó Carlos - porque seguro que hay varios que tenemos esos dos dígitos iguales.

―¡Eso es!— dijo Paula— ¡Si la función resumen es mala, hay coincidencias, que se llaman colisiones, y no deben usarse… justo eso les ha pasado a los del concierto! Te lo explico, es bastante sencillo. Cada entrada tenía un número identificativo, cuyo resumen se determinaba usando la función CUTREHASH, que divide el número original por 1.024 y toma como resumen el resto de esa división.

―¿Y por qué justo el 1.024?

―Ummm. Eso no es relevante para resolver el problema, pero interesará a quienes recuerden las secuencias binarias. Como validar las entradas ha de ser rápido, ambos números se representan en binario (con unos y ceros), para que puedan leerse fácilmente con un lector óptico. Como 1.024 es 2 elevado a 10, así nos aseguramos que el número resumen va a poder representarse como mucho con 10 cifras (10 bits).

―No veo el problema— dijo Carlos - lo tenían todo muy bien pensado.

―Bueno… no del todo… —sonrío Paula— para empezar, el aforo del estadio era de 10.900 personas, con lo que los identificadores correctos de partida deberían ser números entre 1 y 10.900. Pero con la fórmula elegida hay muchos menos resúmenes que números de entradas, entonces ¡no podía haber un resumen diferente para cada identificador! ¿Recuerdas el Principio del Palomar que vimos en clase? Si tienes más palomas que palomares, algunas han de compartir cama…y justo eso les pasó. En un momento dado, empezaron a llegar personas con entradas válidas y resúmenes que ya habían sido validados por el lector de la puerta, con lo que les denegaron el acceso.

―Madre mía, qué desastre— Carlos parecía preocupado – y, ¿tardaron mucho en darse cuenta?

― En realidad no, Carlos, piénsalo… Esa es la primera pregunta del concurso. ¿Cuánta gente como máximo y como mínimo había entrado en el estadio cuando llegó la primera persona con un resumen repetido?

― Venga, lo pienso. Pero, si no tardaron tanto en darse cuenta, podrían haber celebrado el concierto un poco más tarde ¿no?

―Intentaron hacerlo. Al comprobar que usar solo el resumen era un mal método, decidieron validar las entradas de otra forma, comprobando dos cosas: que el identificador no hubiera sido utilizado antes y que su resumen estuviera bien calculado (usando así el hash para corregir posibles errores de impresión). Pero tampoco funcionó. Unos maleantes, conocedores del defectuoso sistema de validación, habían falsificado miles de entradas con sus correspondientes resúmenes, desde la que llevaba el identificador 10.901, hasta la numerada con el 99.999. ¡Y de eso solo se dieron cuenta cuando claramente los asistentes desbordaron el aforo!

Y ahora vienen el resto de preguntas del desafío. La segunda es fácil: ¿Podrías encontrar el número de una entrada válida cuyo resumen dé el mismo valor que la entrada con identificador 4.410? Y la tercera, más complicada: ¿Cuántas entradas válidas y cuántas en total, contando las falsificadas, tenían el mismo resumen que esa numerada con el 4.410? ¡Tenemos que darnos prisa, el premio son dos entradas de las buenas!

―Pues, ¡al lío!— ahora sí que Carlos estaba convencido — ¡Vamos a ir al concierto de SUPER STAR fijo!

Los desafíos criptográficos se publicarán cada 15 días. Los lectores pueden dejar sus soluciones y debatir sobre el problema en los comentarios de esta página, por lo que se recomienda a quien quiera resolverlo por sí mismo no leerlos hasta haber descifrado el enigma. También pueden enviar sus respuestas al correo desafioscriptograficos@gmail.com. En cada nuevo desafío publicaremos la solución del anterior, acompañada de un comentario con algunas ideas originales o inspiradoras que hayamos recibido.

Ana Isabel González Tablas Ferreres, @aigtf, es Doctora en Informática y profesora e Investigadora del grupo COSEC de la Universidad Carlos III de Madrid.

SOLUCIÓN AL DESAFÍO ANTERIOR

En el desafío Cómo engañar a un verificador de sudokus, lo esencial en este reto es observar lo siguiente: si en cada celda se apilan tres fichas iguales, como el sudoku no esté bien resuelto, el verificador siempre detectará el problema. La única posibilidad de engañar al verificador es pues apilar fichas con números diferentes.

El sudoku propuesto se completa así:

Por tanto, si supiéramos que el verificador comprueba primero por filas, luego por columnas y en último lugar por cajas, una de las múltiples maneras de engañarle sería:

Donde suponemos las fichas apiladas y a la izquierda aparece el número de la primera ficha (la inferior), en medio el de la segunda y a la derecha el de la capa superior. Hemos colocado tres fichas idénticas en las celdas fijas, ya que van boca arriba, mientras que con las fichas boca abajo, nos hemos limitado a colocar, correlativamente, las fichas más bajas disponibles, primero por filas, luego por columnas y finalmente por cajas (de izquierda a derecha y de arriba abajo). Algunos lectores (como Javier y Héctor) nos han señalado que dado que hay tres comprobaciones (filas, columnas y cajas) que se harán de modo secuencial y viendo que resulta trivial rellenar el sudoku de modo que no haya repeticiones en cada una de ellas, la probabilidad de proporcionar una solución que el verificador dé por válida cuando solo disponemos de propuestas que superen una prueba (la de filas, la de columnas y la de cajas) coincide con la de acertar el orden en que se hará comprobación. Dicha probabilidad es 1/6 (uno dividido entre el número de permutaciones de tres elementos).

La herramienta criptográfica que subyace a este reto son las llamadas Pruebas de Conocimiento Cero, conocidas por las siglas ZKP (del inglés Zero Knowledge Proof), que fueron introducidas en 1985 por Shafi Goldwasser, Silvio Micali y Charles Rackoff (ver The Knowledge Complexity of Interactive Proof-Systems). Informalmente, una Prueba de Conocimiento Cero es un procedimiento a través del cual un “demostrador” convence de un hecho a un “verificador” sin revelar más información que la veracidad de dicho hecho. Este tipo de protocolos son tremendamente útiles en criptografía, pues, por ejemplo, permiten demostrar la posesión de claves secretas (identificando así a los usuarios de un sistema) sin filtrar información sobre las mismas. En la actualidad, la investigación en ZKPs está en auge debido a la expansión de las criptomonedas. En este contexto las ZKPs son imprescindibles para validar transacciones de cara a evitar fraudes sin poner al descubierto los movimientos de una cuenta, protegiendo así la privacidad de los usuarios del sistema.

Nuestro ejemplo de los Sudokus está inspirado en Gradwohl, Naor, Pikas y Rothblum (2007), donde, además de proponer y revisar otras ZKPs para resolución de Sudokus, los autores analizan en detalle una variación del método propuesto en la el verificador selecciona aleatoriamente una ficha de cada casilla cada vez que dicha celda interviene en la comprobación por filas, columnas o cajas. Con este protocolo de verificación, que aparece en la solución propuesta por un lector (David), puede demostrarse que la probabilidad de engañar a un verificador con una solución errónea no puede ser superior a 1/9.

Puedes seguir a EL PAÍS TECNOLOGÍA en Facebook y Twitter o apuntarte aquí para recibir nuestra newsletter semanal.