El hombre que ganó el desafió del millón de James Randi (segunda parte)

Por Arturo Quirantes, el 12 noviembre, 2014. Categoría(s): Criptografia
JREF11milliondollarcheck2.indd
Y decían que las matemáticas no sirven en la vida real

[Extracto del libro Cuando la Criptografía Falla]

(primera parte) … El truco de Alicia es una variante de lo que se conoce como cifrado negable (deniable encryption), una técnica que permite negar la existencia de un mensaje cifrado. Tiene dos variantes. En una de ellas, un mensaje cifrado adopta una forma que impide reconocerlo como tal, de manera que no se puede demostrar la existencia del mensaje sin la clave adecuada; en otra, un mensaje cifrado se puede descifrar con dos claves distintas, arrojando dos textos llanos distintos.

Imagínese el lector, por ejemplo, un mensaje enviado por una multinacional a su filial en España. Cuando los directores regionales reciben el mensaje, lo descifran con la clave A y leen “están ustedes haciendo un gran trabajo.” Eso tranquiliza a la plantilla. El consejo de dirección, sin embargo, utiliza la clave B y obtienen el mensaje “hay que hacer recortes, cierren las delegaciones de Málaga, Zaragoza y Valencia.” Dos públicos reciben, a partir del mismo texto cifrado, mensajes muy distintos.

En el caso de Alicia y Benito, el protocolo puede mejorarse. La forma de hacerlo es hacer que Alicia no cifre solamente el bit b, sino una combinación R+b, donde R es una cadena de bits aleatorios. Para hacer trampas, Alicia tendría que encontrar dos claves k, k’ tales que Ek(R+1)=Ek’(R+0), algo inviable si R es aleatorio y de tamaño suficiente. Cuando Alicia descifre el mensaje cifrado, Benito podrá leer “R+b,” lo que le revelará la elección de Alicia al tiempo que le permite reconocer su propia R.

El dilema de Alicia bolsista y Benito inversor puede también verse como ejemplo de una serie de problemas llamados “de conocimiento cero.” En este tipo de problemas, Alicia tiene que convencer a Benito de que conoce un secreto. La forma evidente de hacerlo es contárselo, pero en el momento que lo haga dejará de ser un secreto. Un campo de aplicación es el de las contraseñas. Vivimos en un mundo donde la forma de demostrar nuestra identidad es mediante contraseñas: en el cajero automático, en el móvil, en el acceso al trabajo. El usuario no suele pensar que los verificadores pueden no ser quienes afirman ser. Una web bancaria puede ser falsificada, o un cajero trucado, y en esos casos, el cliente estará facilitando su contraseña a terceros no autorizados. Los verificadores legítimos (bancos, empresas de telefonía) concentran sus esfuerzos en “generar confianza,” pero el hecho es que al cliente le puede quedar siempre la duda: ¿será esta gente quien realmente afirma ser?

Las pruebas de conocimiento cero (ZKP) pueden ayudar en estos casos. Vamos a ver un ejemplo de cómo una persona puede demostrar la existencia de un secreto sin revelarlo en absoluto. El artículo original, publicado en 1990, está escrito en forma de cuento de las Mil y Una Noches. Si no les importa, voy a actualizarlo levemente.

Éranse una vez dos arqueólogos, Indy y Lara, que buscaban el secreto de la Sala Oculta. En las profundidades de la selva, el Monte Perdido tiene una entrada (A), que tras un largo pasillo conduce a un vestíbulo (B). De allí arrancan dos pasadizos (C y D), que aparentemente acaban en una pared. Para un observador casual son vías sin salida, pero quien se plante al final de uno de los pasadizos y grite las palabras mágicas se encontrará con que la Sala Oculta aparece de la nada, conectando ambos pasadizos.

Indy conocía las palabras mágicas que revelaban la existencia de la Sala. Lara deseaba conocer ese secreto, así que hizo un trato con Indy: le financiaría su próxima expedición a cambio del secreto. Indy aceptó el trato, pero conforme se acercaban a la Sala empezó a dudar. ¿Y si él cumplía su parte pero Lara se echaba atrás? Por su parte, Lara no estaba dispuesta a soltar el cheque hasta comprobar que las palabras mágicas funcionaban; que Indy era perro viejo y tal vez guardase un as en la manga.

Por fortuna, ambos eran personas razonables, y cuando llegaron a la entrada del Monte Perdido ya habían diseñado una prueba de Conocimiento Cero. El primero en entrar fue Indy. Con paso firme, llegó al vestíbulo y escogió uno de los pasillos. Después entró Lara, quien se quedó en el vestíbulo. Desde allí gritó con voz alta y clara “Indy, vuelve por el pasillo C.” Indy así lo hizo. A continuación, repitieron el proceso de nuevo, escogiendo el mismo pasillo o bien otro distinto (a capricho de Lara). Luego otra vez. Y otra más. Recordando la historia de Alí Babá y los cuarenta ladrones, hicieron este proceso un total de cuarenta veces. Finalmente, Lara se convenció de que Indy conocía el secreto que llevaba a la Sala Oculta.

La clave del protocolo consiste en que ni Lara sabe qué pasillo ha tomado Indy, ni Indy sabe qué pasillo de vuelta le va a indicar Lara. Si las elecciones se toman al azar, hay un 50% de probabilidades de que Indy vuelva por el mismo pasillo por el que entró, lo que ciertamente no prueba nada; pero también hay un 50% de probabilidades de que tenga que salir por un pasillo distinto, y eso no podría hacerlo más que diciendo las palabras mágicas y atravesando la Sala Oculta.

Un Indy tramposo podría haberse arriesgado y confiar en la suerte. Lara lo sabía y no se hubiera quedado satisfecha con la prueba. Pero si Indy repitiese con éxito el proceso un total de 40 veces, la probabilidad de haber “tenido suerte” hubiera sido de una entre un billón. Demasiado suerte incluso para él. Lara concluyó que Indy realmente conocía el secreto de la Sala Oscura y cumplió su parte del trato.

Algún tiempo después, tuve la oportunidad de cenar con ambos arqueólogos (recuerden, esto es un cuento). Tras un magnífico Oporto, me contaron toda la historia. Yo, que cuando he pillado el punto suelo volverme algo malicioso, les dije: “Entiendo por qué ese proceso tan complicado funciona, pero hay algo que aún se me escapa. Lara, ¿por qué no te limitaste a enviar a Indy por un pasillo y esperar a que apareciese por el otro?” Debí haber grabado la cara que pusieron los pobrecitos. Realmente, se hubieran ahorrado una buena caminata por el interior del Monte Perdido.

En su defensa, debo decir que ellos no son criptógrafos profesionales y se limitaron a copiar la idea de un experto y aplicarla a su caso particular. En general, las pruebas de conocimiento cero del tipo que hemos visto requiere una serie de desafíos por parte de la persona que quiere verificar un secreto, seguidos por una elección hecha por el poseedor del secreto. Cada paso del proceso solamente puede hacerse con seguridad si realmente se posee el secreto, en tanto que un timador solamente tiene una probabilidad de acierto debido al azar.

James Randi tampoco es criptólogo profesional, y seguro que no pensó que tendría que enfrentarse a uno. Afortunadamente, en esta ocasión no tuvo por qué preocuparse. Caballero ante todo, Blaze mostró su apoyo al trabajo de la fundación Randi. ¿Y saben lo mejor? En un arrebato de generosidad, renunció al premio. «Por esta vez,» dijo. Si hubiese sido un vidente de esos que salen en la tele, podría haberlo «revelado» en un programa de máxima audiencia para hacerse mundialmente famoso. Sin embargo, no sólo no hizo tal cosa, sino que renunció al premio de un millón de dólares. Hasta la fecha, sigue sin reclamarlo.

Para su sorpresa, el caso acabó en los tribunales. No, bueno, quiero decir de modo simulado. El asunto Randi-Blaze fue aprovechado por un profesor de la Facultad de Leyes de la Universidad Stetson, en Florida, quien tuvo la genial ocurrencia de explicarlo a los alumnos, aderezarlo un poco y utilizarlo como cuestión en un examen. Los alumnos debían explicar quién puede demandar a quién, por qué motivos, y quién ganaría.

Por su parte, Randi se lo tomó con humor. Según contó en su revista electrónica, cambió el contenido del archivador, y ahora nos da la siguiente pista:

BSQN ISIO QWOD QPIE

Que yo sepa, nadie ha descifrado este reto ni reclamado el millón de pavos. ¿Se atreve usted a intentarlo? Le deseo suerte. Y, por supuesto, en caso de éxito espero mi porcentaje.



Deja un comentario

Por Arturo Quirantes, publicado el 12 noviembre, 2014
Categoría(s): Criptografia
Etiqueta(s): ,