Desafío criptográfico: cómo acertar la contraseña en un teclado manipulado

La empresa EscapaEsp, que diseña retos para salas de escape, ha recibido un encargo de un canal de YouTube: un concurso en el que equipos de 10 personas se enfrenten a varias pruebas. La encargada del canal, una famosa youtuber, quiere ofrecer un premio suculento para los ganadores, pero para ello quiere estar completamente segura de que, a lo sumo, solo van a ganar tres de cada diez equipos. Además, le gustaría dar la impresión de que el juego es difícil de ganar.

Julia y Juan, encargados de diseñar los retos en EscapaEsp, intercambian ideas hasta alcanzar una propuesta. Cada equipo deberá enfrentarse a diferentes pruebas para ir encontrando los diez caracteres de una contraseña. Al final de las pruebas, todos los equipos pasarán a una fase final en la que los miembros del grupo competidor entrarán de uno en uno en una sala en la que solo hay un teclado y una pantalla. Cada uno escribirá un carácter de la contraseña. Para ganar, han de conseguir que la pantalla del ordenador muestre los diez caracteres de la contraseña en el orden correcto.

La prueba, desde luego, no será sencilla; ni siquiera para los equipos que conocen la contraseña al completo: el teclado está manipulado, de forma que lo escrito en el teclado no se corresponde con lo mostrado en pantalla. En concreto, Julia y Juan han propuesto las siguientes reglas:

1) La contraseña no tiene ningún carácter repetido, y los caracteres solo pueden estar entre los 40 siguientes: las 27 letras del abecedario español (con la “ñ”), el punto, el guion, la coma y los diez dígitos (0- 9).

2) El teclado tiene únicamente los 40 caracteres anteriores. Además, se han manipulado los cables aleatoriamente, de forma que, al pulsar una tecla, lo más probable es que no aparezca en la pantalla el carácter pulsado. Es decir, al pulsar la tecla “m” quizás se muestre el carácter “8″. No obstante, esta manipulación se mantiene igual a lo largo de todo el juego (si la tecla “m” hace aparecer “8″, lo hará para todos los jugadores del mismo equipo). Además, no hay dos teclas que hagan aparecer en pantalla el mismo carácter.

3) · Los jugadores que han entrado en la sala del teclado deberán salir por una puerta diferente de la entrada, y no podrán comunicarse con los jugadores que aún esperan su turno. Del mismo modo, aunque se pueda mostrar a los espectadores lo que ocurre en la sala del teclado, los jugadores que no han entrado no deben saber nada. Es decir, cada jugador del equipo que entre en la sala del teclado debe tener la misma información que el primero que se enfrentó al teclado.

4) · Los caracteres de la contraseña se deben introducir en orden: el primer jugador que entre en la sala deberá introducir el primer carácter, el segundo introducirá el segundo carácter y así con todos.

5) · Cuando un jugador se enfrenta al teclado, podrá probar hasta un máximo de 20 teclas distintas para hacer aparecer su carácter. En el momento en el que el carácter correcto aparezca, una luz verde se encenderá y podrá pasar el siguiente jugador, independientemente de si el jugador conocía o no el carácter correcto antes de entrar. Si tras la pulsación 20 algún jugador no logra obtener la luz verde, todo el equipo habrá perdido.

6) · Los diez jugadores pueden diseñar cooperativamente una estrategia antes de enfrentarse al juego.

La youtuber hace un cálculo rápido y determina que la probabilidad de éxito de cada miembro del equipo es ½ . Como todos tienen la misma información al entrar, al ser 10 jugadores en el equipo, su probabilidad de éxito es de ½ * ½ * … * ½ (10 veces) , aproximadamente 0,001. Esto le choca por dos motivos. En primer lugar, parece que la probabilidad de ganar es independiente de si la contraseña es conocida o no, ya que el ordenador automáticamente valida la clave cuando se introduce el carácter correcto. Y eso le parece injusto: el equipo que conozca toda la contraseña debe tener una ventaja. En segundo lugar, esta probabilidad le parece demasiado escasa. Que haya equipos que ganen hace que más gente se interese por el programa. Y también que más equipos quieran participar.

Sin embargo, Julia y Juan explican que existe una estrategia que garantiza que la probabilidad de éxito del equipo, si conocen la contraseña al completo, es de 0,32. Si únicamente conocen algunas partes de la contraseña, la probabilidad de ganar se reduce: por ejemplo, si conocen 7 caracteres, no han podido dar con una estrategia que ofrezca un éxito con probabilidad superior a 0,04.

¿Puede el lector encontrar cuál es esta estrategia que deberían seguir los concursantes para ganar aproximadamente tres de cada diez veces si conocen toda la contraseña? ¿Por qué es tan importante conocer la contraseña para maximizar las opciones de ganar?

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.

Diego Castejón Molina y David Balbás Gutiérrez son investigadores predoctorales en el Instituto IMDEA Software de Madrid. Su trabajo se centra en el diseño y análisis de protocolos criptográficos y aplicaciones.

SOLUCIÓN AL DESAFÍO ANTERIOR

Esta quincena hemos recibido multitud de respuestas, ¡gracias a todos por sus comentarios!

Para calcular el orden correcto orden utilizamos el mecanismo enunciado, que, aunque de manera simplificada, es el que sigue la criptomoneda Bitcoin, propuesta en 2008 bajo el pseudónimo de Satoshi Nakamoto. Principalmente, nos fijamos en el valor BA, que es un puntero al bloque anterior. En concreto, BA indica el resto de calcular la división entera del bloque anterior por 541. Así, por ejemplo, el segundo bloque lo encontramos al calcular la división entera de 53244 entre 541. El resto, 226, nos indica cuál es el segundo bloque (aquel que tiene 226 como BA). Por el mismo procedimiento podemos encontrar el tercer bloque. Al calcular la división entera de 22623138 por 541, el resto, 141, nos anuncia el tercer bloque. Para calcular el cuarto bloque primero se tendrá que calcular el valor de B del tercer bloque. Recordad que se trata de encontrar un valor tal que 141112XXXXX (donde las X son dígitos diferentes, y la longitud no es fija) tal que al calcular la división entera de 141112XXXX^3 y 541, el resto acabe con dos ceros. Se trata de ir probando valores (una sugerencia es programarlo, usando un comando del estilo Table[H[141112*10 + k], {k, 0, 9}] ―si suponemos que encontraremos la solución añadiendo un solo dígito― o Table[H[141112*10^2 + k], {k, 0, 99}] ―para probar con dos dígitos― etc,). Con esa técnica, se obtiene que 39 lo cumple. Así, podemos calcular el valor BA del cuarto bloque, que será el resto de calcular la división entera entre 14111239 y 541. El resultado, 336, nos anuncia el cuarto bloque. El restante, por lo tanto, será el último de los bloques.

Nota: Para los que sepan aritmética modular, las operaciones que estamos haciendo al calcular las divisiones enteras y quedarnos con el resto, es el cálculo del dividendo módulo el divisor.

Una vez tenemos los bloques ordenados, podemos mirar qué dinero tienen los hermanos. Recogemos el resultado en la siguiente tabla, donde la última columna es el resultado final.

Aunque, como varios habéis señalado, si no hay bloques inválidos las transacciones propuestas en el reto “conmutarían”, y mirando el saldo final la solución es la misma, si los bloques no se ordenan bien no podemos dar la solución por correcta. La razón (muy importante en el mundo real) es que ordenando los bloques de cualquier manera a menudo aparecen transacciones intermedias inválidas: es decir, alguien tiene que transferir más de lo que tiene en ese momento.

Nota: Aparte de la simplificación en los contenidos, hay que tener en cuenta la importancia de los formatos, que aquí se han simplificado también para focalizar la explicación en el mecanismo. Puede que a algunos les sea familiar la noción de función resumen (o hash) y que se utilizan en numerosos escenarios de la vida cotidiana, desde las firmas digitales hasta cuando guardamos una contraseña. Lo que hace un minero al minar, no es calcular el cubo de ciertos valores, sino que calculará convenientemente una función hash, en particular una de las más utilizadas en la actualidad, la función SHA-256. Por simplicidad, también hemos omitido la (muy importante) parte en la que se autentican los mensajes, las firmas digitales son de gran ayuda en este contexto.

PS: Tal y como prometimos la semana pasada, incluimos también la solución al desafío criptográfico-musical que nos envió nuestro lector Salva Fuster.

- ¿Qué melodía actúa como clave (hay que tener en cuenta que en la clave, las F realmente son F#)?

La primera suite de Bach para violonchelo BWV 1007.

- ¿Cuál es la palabra oculta?

ENHORABUENA

- ¿Cuál es el sistema que permite cifrar/descifrar el mensaje?

Para cifrar un mensaje, únicamente lo convertimos en binario, como en el desafío Un mensaje en clave napolitana oculto entre unos y ceros y, a partir de una determinada melodía escogida previamente (que actúa como clave), creamos una nueva de tal manera que sea disonante con la melodía clave para obtener un 0, y consonante para obtener un 1. En particular, se ha elegido una alternancia de notas musicales inferiores y superiores a las de la clave para las disonancias, y una cuarta justa (o quinta justa) para las consonancias, aunque se hubiera podido complicar un poco más eligiendo aleatoriamente otros tipos de disonancias y consonancias.

Para descifrarlo, únicamente cabría hacer lo mismo, pero en sentido inverso, es decir, identificar las disonancias y consonancias de la melodía recibida respecto a la melodía que actúa como clave para convertirlas en las correspondientes cifras 0 y 1, y, posteriormente, transformar el código binario obtenido en el mensaje en claro.

Otro infatigable lector, Xuacu Álvarez, ha dado con la solución correcta (ENHORABUENA, nunca mejor dicho, también para él por acertar).

Fe de errores: En una primera versión de este artículo incluíamos las dudas sobre la solución que nos había transmitido Xuacu Álvarez. Pero en un segundo correo (al que incluso contestamos, ¡ay qué cabeza la nuestra!), nos confirmaba que sus dudas habían quedado aclaradas. Nuestras disculpas y, de nuevo, nuestro agradecimiento a él y a Salva.

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