Los falsificadores de entradas

¨D?Carlos, Carlos! ?Espera un momento!¨D grit¨® Paula a trav¨¦s de la ventana del primer piso del instituto ¨DNotici¨®n: nos vamos al concierto de SUPERSTAR.

Carlos mir¨® a Paula con escepticismo.

¨DPaula, perdona, el concierto se suspendi¨®. Algo de entradas duplicadas, o se pasaron con el aforo¡­ no s¨¦.

¨D?Exacto!¨D grit¨® Paula¨D. 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.

¨DEl 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.

¨DMe est¨¢ empezando a dar pereza¡­¨D protest¨® Carlos. ¨D?Qu¨¦ es eso de funci¨®n resumen?

Paula prosigui¨®, implacable. ¨DUna 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.

¨DY eso no es bueno¡­¨D interrumpi¨® Carlos.

¨DNo. 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.

¨DPues menudo l¨ªo montar¨ªan¡ª salt¨® Carlos - porque seguro que hay varios que tenemos esos dos d¨ªgitos iguales.

¨D?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.

¨D?Y por qu¨¦ justo el 1.024?

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

¨DNo veo el problema¡ª dijo Carlos - lo ten¨ªan todo muy bien pensado.

¨DBueno¡­ 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.

¨DMadre m¨ªa, qu¨¦ desastre¡ª Carlos parec¨ªa preocupado ¨C y, ?tardaron mucho en darse cuenta?

¨D 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?

¨D Venga, lo pienso. Pero, si no tardaron tanto en darse cuenta, podr¨ªan haber celebrado el concierto un poco m¨¢s tarde ?no?

¨DIntentaron 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!

¨DPues, ?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.