Cocktails y otros cifrados para compartir – Elige la vida

Buenos días a todos. Disculpen la demora, me he encontrado algo de tráfico camino de aquí y me ha costado llegar. Desde Agosto en ese maldito atasco.

Ya saben como se ponen las carreteras a estas alturas de temporada.

No les voy a engañar. Soy complicado de narices. Escribir en este blog ha sido como volver al instituto, los profesores sabían que siempre estaba castigado en los recreos, ocupado por las tardes mandando 17.000 toques a amigos y amigas tratando de interpretar los suyos y aún así querían que aprobase con nota. Cuando yo siempre he sido de cincos.

Malos hábitos.

Manos a la obra. Hoy quería presentarles un tipo de cifrado que me llamó mucho la atención hace unos días. Se lo presentaré en el contexto donde yo mismo lo conocí. El siguiente reto fue planteado en el evento de seguridad Qurtuba 2017 durante la competición «Captura la bandera»  donde estuvimos muy bien representados. Fue una pena no poder asistir este año.  Espero que Edu y Miguel Ángel sepan perdonarme. Prometo no faltar a la siguiente edición y con una participación activa.

Por cierto, estos tres bichos de arriba fueron campeones. Un año más. Esta edición ni me han esperado. No les culpo. Felicidades por todo lo que estáis consiguiendo, especialmente a la fiel defensora de Simeone. Aún recuerdo los primeros días con Diego. Tratando de hackear alguna que otra persona acabamos, como no podía ser de otra manera, hackeados. Pero salimos a flote. Los villanos siempre vuelven, como en las películas de superhéroes.

Pues bien, el villano de Diego me hizo llegar este reto (a sabiendas de mi gusto por las matemáticas y la criptografía) el lunes pasado pese a darme aviso durante el fin de semana mientras disfrutaban del sol cordobés, dejándome sin caramelo durante unos días. Os dije que era de los malos.

Se trataba de un reto de criptografía que hace uso del algoritmo de cifrado SSSS.  Shamir’s Secret Sharing Scheme. Antes de que me lo pidáis voy a presentaros a Shamir. Adi Shamir es un criptógrafo Israelí, co-inventor del algoritmo RSA junto a Ron Rivest y Len Adleman, entre otras cosas. Ha recibido varios premios por su trabajo como el «Turing Award» en 2002 por sus investigaciones y contribuciones al mundo de la criptografía. Aquí tenéis un listado de sus publicaciones, por si estáis interesados.

El enunciado del reto era el siguiente:

Dividir para vencer (175 puntos)

Hemos encontrado estos mensajes en unas transmisiones. ¿Puedes ayudarnos a descifrarlos?

1-232a6ade20749098101a13f41a0f92d56c9f01833ea4b0b8
2-cb87dcfbeea3e521ac88bac9425042d0a22be917358ecb9c
3-82d12c7c9a69cab7cc97ce4ab6f1744545592f4075c75b51
4-6298f0848387e14e6eda3d4e93f1a72570c9c073d3a1c05d
5-aa26185ec1b90277356d46ed3d40a4c7cc4f96f5680056ab
6-415b9ec16287ee90feaff190d13f1e2cb5125fc294fa217e

Tras jugar con las diferentes cadenas durante un buen rato probando diferentes combinaciones (como eliminar los números de las cadenas para quedarnos únicamente con las letras) . Nada parecía tener demasiado sentido hasta que apareció la idea del «Shamir Secret Sharing». Vamos a introducir este tipo de técnica para luego pasar a ver el algoritmo concreto.

Secret Sharing

---

La técnica de «Secret Sharing» se basa en cifrar una clave en diferentes cadenas. Imaginemos por un momento que queremos cifrar un mensaje confidencial de forma que podamos enviar una pequeña parte de dicho mensaje cifrado a una serie de personas de manera que ninguna de ellas podría obtener el mensaje confidencial únicamente utilizando su clave. Necesitaría la de los demás.

Yo siempre lo he comparado con un buen Cocktail, lo ideal sería formarlo con todos los ingredientes al completo, pero según va avanzando la noche todo se olvida y uno acaba tomándose un Old Fashioned sin esa amarga Angostura. Lo que viene siendo un whisky con hielos, vamos.

Por tanto, estamos dividiendo un mensaje cifrado en diferentes claves (pongamos, por ejemplo, 7 partes o cadenas) con la intención de que se necesiten un mínimo de ellas para reconstruir de nuevo el mensaje original.

Un ejemplo muy sencillo de entender es el siguiente, vamos a ponernos en situación: 4 de Mayo de 1992. Una fecha bastante cercana a mi persona, por cierto. Time Magazine publica un artículo en el cual se da a entender que el control de las armas nucleares en Rusia está en manos de tres partes. Como si fuera un botón rojo que tienen que pulsar en grupito. Lo curioso es que es un esquema dos-de-tres. Es decir, es necesario que al menos dos de las tres partes cooperen o estén de acuerdo en lanzar los misiles nucleares. No se necesitan las tres partes.

Todo muy rollo Wargames, ¿verdad?

Pues bien, las tres partes involucradas en este juego de niños eran el Presidente, el Ministro de Defensa y el propio Ministerio de Defensa.

Esto es básicamente un  «Secret Sharing Scheme». Vamos a presentarlo de forma más general.

Un esquema básico de este tipo de cifrado consistiría en utilizar un «repartidor» y «n jugadores», desconocidos entre sí. El repartidor cifraría el mensaje y lo dividiría en n partes o cadenas. Cada una de ellas iría a parar a un jugador. De esta manera, cuando el repartidor considerase, podría poner en contacto a dichos jugadores (no es necesario a todos, solo a los que él haya considerado como cantidad mínima de jugadores) para reconstruir dicho mensaje original.

Bajo esta idea, se suele denotar lo siguiente:

n = número de jugadores o cadenas en las que se dividirá la clave.

t = mínimo de jugadores o cadenas necesarias para reconstruir dicha clave.

De manera que (t,n) sería el esquema de cifrado «Secret Sharing» que dividiría el mensaje original cifrado en n-cadenas y necesitaría un mínimo de t-cadenas para volver a ser reconstruido.

Cuando n = t significa que es necesario todos los participantes para reconstruir la clave.

Shamir’s Secret Sharing

---

La idea del cifrado de Adi Shamir se basa en lo siguiente.

• Dos puntos son suficientes para definir una recta (Grado 1).
• Tres puntos son suficientes para definir una parábola (Grado 2).
• Cuatro puntos son suficientes para definir una función cúbica (Grado 3). 
• Un número k de puntos son suficientes para determinar un polinomio de grado k-1.

Supongamos, como ya hemos comentado, que tenemos un esquema (k,n) para nuestro mensaje secreto S. Una vez que tenemos nuestro polinomio de grado k-1, elegimos n puntos de ese polinomio o curva. Cada uno de los participantes recibirá uno de ellos. Pues bien, dados cualesquiera t elementos de esos n (puesto que t <= n), podemos encontrar los correspondientes coeficientes del polinomio usando técnicas de interpolación de Lagrange utilizando un polinomio de grado t-1 donde el primer coeficiente a₀ será el secreto S.

De manera, que la idea básica del algoritmo es dividir el mensaje secreto S en una serie de subconjuntos S₁…S_n de manera que:

• • Conocer k o más de esos elementos S_i permite recuperar el mensaje secreto S.
  • Conocer k-1 o menos de esos elementos  S_i no permite recuperar el mensaje secreto S.

Donde, como hemos dicho, k representa el número mínimo de elementos elegidos por el repartidor para que se pueda reconstruir dicho mensaje.

Por cierto, las matemáticas que hay debajo de este cifrado son preciosas. Para los más curiosos y la gente rara como yo, aquí y aquí les dejo más información al respecto con algunos ejemplos desarrollados para entenderlo mejor.

¿Aburrido? Lo entiendo. Vamos a poner rock & roll.

Prueba de concepto

---

Veamos un ejemplo más concreto:

Supongamos que queremos cifrar el siguiente mensaje y repartirlo entre nuestros 7 amigos.

Quedamos el domingo en el parque del Retiro para preparar el viaje. Nos vemos a las 12:00. No te olvides del cafe.

Por tanto, tendremos que dividir el mensaje cifrado en 7 cadenas y repartirlas a cada uno de ellos. Como son algo despistados, consideraremos que con 4 de ellos bastaría para reconstruir el mensaje original. Ya luego que se pasen el mensaje vía Telegram. O que se bajen al bar y se lo cuenten entre copa y copa.

Utilizaremos la herramienta ssss disponible en Linux:

• Archlinux: https://aur.archlinux.org/packages/ssss/
• Linux: http://point-at-infinity.org/ssss/ssss-0.4.tar.gz
• Online: http://point-at-infinity.org/ssss/demo.html

En mi caso utilizaré la versión de consola para Archlinux con el siguiente comando:

$ ssss-split -t 4 -n 7

WARNING: couldn't get memory lock (ENOMEM, try to adjust RLIMIT_MEMLOCK!).
Generating shares using a (4,7) scheme with dynamic security level.
Enter the secret, at most 128 ASCII characters: Quedamos el domingo en el parque del Retiro para preparar el viaje. Nos vemos a las 12:00. No te olvides del cafe.

Este es el resultado que obtenemos:

1-2675ef1a4632ebc4cf4b5e9b94d55e29fc803c6c3c9fb830e442146090eabaa16cc2cb9be386371816e88941e6f500b2e512e934c979017f2cbedb83f12d9e68154f0e8c1961d33848f103907f208dccb5404701e882d192e24621f70d9548ce44d58316a1be38fb795af3c107f3b226cb79
2-cdaadc0b037cb2e49d9dbcbe995316a5aacfd32789a1de2cf1e02da6f9587fa989a3277fa3eb3f1e42567939dc0165bef6677ead3b039f9e93ab8825a3f74c461f13fd26b6672fbadedcc57b5b5c968f64ffcc9b0214de1eed5cc6875c0ce2f8b58a866e925414aa689fa08c406576e79894
3-b7d322ac69fcf35a39b5db9012b72bb4030f35f3aaf3a559bac3fdcabf5f074808a2d412523c476dd4ac32b23731a662d9efad7bfe317283ff0485930a5d6706792d367eaf821dfdbd1457729a2aa757fbbb24c88843b03d3f822a2a3e1355d59639e95fa1baf0f47347b1d8a27d6dc175f8
4-24b190016304cf36d6fc857098cdd361163a17bad3d6c2272666c9bd53f64d9eff9cc075017ce7c9ea2a42a0bc200f3a5c6c2cfc1d3bda7ccce2ddb55e79da75445b52b643366bd73aa5770cacdf89c6f588e14ab03d4aa5ba1cddef911eb6f6c12ee0149813f6f1221d3bec2d278b9664bc
5-3716fc56c42b7cee05b965762f535a08bc16320e7ae4978bc316812751dd5ea194cd3920a8a9ddbac6604878fe77325dc697fa28f0e72c07f51c0f47180504c76be0df920243806ca9b933812c0253f740bc1d160504b1b1070ad847b2b28d7aa6ef8d8cd05e602ee695133a9b6262d5ff84
6-0f74eaa61a3ac102b9b489035a207a74ed805b84db1aac248a13890db0374c14a50cc1b458c051bde7be3aa7964caa26bf0467b55341842ae0aae26895723d0df2b6a0c01c64cf17de3d58628b299f66c5e3be92914f9453d781ed3d604c3e0edf548da614f2a97c49f03373744f42de40c1
7-bffadbbaff9a8fa07be5336689ad79d5473853269c3e2d7b56134406c57e916f369be03282781dcef5c99db981d7057f74346bd7b0641af0a892af5b47921ff4738cec9b2e4cba3eb0bd36d87d7a0b19c81c28172d6285fbc8d4a62258dd31b9a25e560622e942f8a465a52505783b51a772

Como ya hemos comentado, bastará con utilizar 4 de las 7 cadenas que nos han devuelto para reconstruir el mensaje. Vamos a verlo a continuación utilizando las 4 primeras:

$ssss-combine -t 4

WARNING: couldn't get memory lock (ENOMEM, try to adjust RLIMIT_MEMLOCK!).
Enter 4 shares separated by newlines:
Share [1/4]: 1-235e53567b4321dcb43ff22b39920aa5aa29c138aeeb2c5a763f08537a77517c0cf84c4c3f6a64ce8294c700d007d1374008c1acf126798fcda0925c9949fe
Share [2/4]: 2-27bb537a00ae38be842a914ba033e56fe27978bb3f91f0cb46744b087e8f1609c8c8478ec1f9257080090c8119160a898747e29bea901e9572bbfd367f56af
Share [3/4]: 3-20288c0ea90c75b1249871628bdadf68fb765ad13604e1f5d0a73949293077676d8578fe693454c3bd3303235018375ee0fdbda2d071a25a05234a91460ab8
Share [4/4]: 4-33da65802d330c5f98d2b5453b9115b7ef3bb5e57c564313db5ae7341cae65a5b3831c91048312b0f9a16124b256c764ade32e39a2d7819c54fe61b69d4d01
Resulting secret: Quedamos el domingo en el parque del Retiro para preparar el viaje. Nos vemos a las 12:00. No te olvides del cafe.

Os animo ahora a tratar de resolver el reto que nuestros amigos de Qurtuba 17 plantearon. Tenéis el enunciado al principio de la entrada. Espero dejen en los comentarios cualquier duda sobre el cifrado SSSS o, en caso de que la hayan conseguido obtener, la flag del reto.

Por mi parte, recordaros como siempre que podéis contactar conmigo vía twitter (@juanvelasc0) y si me queréis conocer algo más, podéis pillarme en los diferentes bares y restaurantes de vuestra zona (a veces hasta altas horas de la mañana) y por las diferentes CON’s y eventos que se realizan por España. Mi siguiente parada será Santander para el evento Cybercamp 2017.

No sé como van a conseguir estos conejos convencerme de ir al evento teniendo la posibilidad de secuestrar a Guille, organizar un equipo de reconocimiento y recorrernos la costa de Santander de bar en bar.

Siempre he pensado que si llego a conocer a ese caradura unos años antes ahora mismo iríamos por Madrid a lo Trainspotting.

La próxima vez vendré en transporte público, para evitar atascos y llegar a tiempo.

Recuerdos para todos,

HoldenV