Como os comentaba en mi anterior post, hace un par de semanas estuve intentando un par de retos del PlaidCTF. El que más me gustó de los dos fue el que ya os he explicado, pero además de ese también hice uno llamado "The Game" (que para mi gusto era más de programación que de hacking en sí) y que decía tal que así:
Robots enjoy some strange games and we just can’t quite figure this one out. Maybe you will have better luck than us.
184.73.47.70:6969
Si conectábamos a la IP y puerto que decían mediante NCat o Telnet, nos devolvía algo así:
You have gotten 0 of 75
Choice 1 = 81dc9bdbf52d04dc20a036dbd8313ed055
Choice 2 = e2f1c714c4727ee9395af324cd2e7f331f
Which one is bigger? (1 or 2)
El sistema nos da dos churros incomprensibles y nos pide que digamos cual es mayor. Después de observar unas cuentas veces no parece que el orden sea por su ordenación ASCII, ni que sean hashes de números ni nada similar, así que tendremos que asumir que lo único que podemos hacer es ir aprendiendo que "churro" es mayor que otro por medio de observación de las respuestas del servidor.
Pepelux también estuvo pegándose con el reto y lo sacó de una manera similar aunque no idéntica a la que voy a explicar yo. Podeis verlo AQUÍ.
Para explicar el concepto del algoritmo utilizado vamos a suponer que la máquina elige 5 elementos diferentes (en el original serían hashes, y muchos más en cantidad, pero como ejemplo nos vale) que a priori el cliente no sabe en que orden van, aunque el servidor sí que conozca su orden:
El orden es lo de menos en realidad, pero supongamos que el servidor conoce a estos personajes y sabe que LUKE, aunque sea prota, es un poco soso, que CHEWIE es el papel más sencillo de aprender de la historia, pero que tiene mucho carisma, que YODA es el maestro de maestros pero OBIWAN siempre me ha gustado más, y que por supuesto VADER es el más grande de todos.
La primera idea de algoritmo que tuve es una lista a la que pudiera ir cambiando el orden según los descubrimientos que fuera haciendo, pero se me ocurrió que tenía la pega de que habría que recorrerla cada vez para buscar los elementos que queremos, y eso me parecía un poco "coñazo".
Por eso, pensando en alguna forma en que las búsquedas fueran muy rápidas, decidí usar un tipo de dato diccionario de Python, en los que los índices para buscar fueran los propios hashes, lo cual me permitía buscar el hash de una forma muy rápida. Pero... ¿cómo hacía después para comparar ambos hashes? Pues asignaba un valor entero "tentativo" a cada uno, así solo tenía que acceder por el hash, recuperar sus enteros y compararlos.
Con un pequeño ejemplo ayudado de nuestros amigos de Star Wars seguro que se entiende el algoritmo mucho mejor:
Antes de empezar comentaros que tenemos una variable "step" que la inicializamos a un valor muy alto. Para nuestro ejemplo lo haremos a 100, pero para el caso real se haría a un valor mucho mayor.
1. ¿OBIWAN o CHEWIE?: Ninguno de los dos está en el diccionario, así que elegimos al segundo como mayor. El sistema nos dice que FALLAMOS, así que hacemos lo siguiente:
dic['CHEWIE'] = 0
dic['OBIWAN'] = dic['CHEWIE'] + step = 100
step = step / 2 = 50
2. ¿LUKE o VADER?: Idem que antes. Elegimos el segundo y esta vez ACERTAMOS:
dic['LUKE'] = 0
dic['VADER'] = dic['LUKE'] + step = 50
step = step / 2 = 25
3. ¿YODA o CHEWI?: Yoda no lo tenemos aún, así que lo escogemos como mayor y ACERTAMOS:
dic['YODA'] = dic['CHEWI'] + step = 25
step = step / 2 = 12
Vamos a ver como va la cosa en el diccionario y seguimos unos pocos más:
dic['CHEWIE'] = 0
dic['LUKE'] = 0
dic['YODA'] = 25
dic['VADER'] = 50
dic['OBIWAN'] = 100
4. ¿LUKE o CHEWI?: Están empatados, así que cogemos cualquiera, el primero mismo, y FALLAMOS:
dic['CHEWIE'] = dic['LUKE'] + step = 12
step = step / 2 = 6
5. ¿VADER o YODA?: Vader es 50 y Yoda es 25, así que elegimos a Vader y ACERTAMOS, con lo que no tocamos nada, dejamos el diccionario como está.
6. ¿OBIWAN o VADER?: Obiwan es 100 y Vader 50, así que elegimos a Obiwan y FALLAMOS:
dic['VADER'] = dic['OBIWAN'] + step = 106
step = step / 2 = 3
Vamos a pegar otro vistazo a como llevamos la ordenación por ahora:
dic['LUKE'] = 0
dic['CHEWIE'] = 12
dic['YODA'] = 25
dic['OBIWAN'] = 100
dic['VADER'] = 106
Parece que a partir de este punto ya tenemos valores bien asignados en el diccionario, así que a partir de aquí todo van a ser aciertos, 75 o todos los que queramos. Lo único que hay que tener en cuenta es que el parametro step debe estar dimensionado a la cantidad de pasos que pensemos que vamos a necesitar.
Si por ejemplo calculamos que vamos a necesitar N pasos para aprender, entonces tenemos que elegir un step que sea 2^N, para que al ir dividiendo entre dos no nos vayamos a decimales. Tampoco pasaría nada siempre y cuando Python permita representar suficientes decimales (que no tengo ni idea de cuantos permite).
Esta es la idea del script que hice para superar el reto, solo que con un "step" mucho más grande y empleando los hashes en lugar de a nuestros amigos de Star Wars. Podeis descargar el script de AQUÍ si tenéis curiosidad en verlo completo. Lamentablemente tardaba bastante la ejecución y tuve que irme antes de que acabara, y cuando lo volví a lanzar ya se había acabado el tiempo del CTF y el servicio no estaba disponible, pero me programé yo un servicio que realizaba lo mismo (con unos pocos elementos) y la solución funcionaba perfectamente, por lo que presumiblemente debería funcionar igual con el servicio real.
Si los PPP publican el código del servicio de este reto lo probaré con él y pondré como una actualización en resultado.
Robots enjoy some strange games and we just can’t quite figure this one out. Maybe you will have better luck than us.
184.73.47.70:6969
Si conectábamos a la IP y puerto que decían mediante NCat o Telnet, nos devolvía algo así:
You have gotten 0 of 75
Choice 1 = 81dc9bdbf52d04dc20a036dbd8313ed055
Choice 2 = e2f1c714c4727ee9395af324cd2e7f331f
Which one is bigger? (1 or 2)
El sistema nos da dos churros incomprensibles y nos pide que digamos cual es mayor. Después de observar unas cuentas veces no parece que el orden sea por su ordenación ASCII, ni que sean hashes de números ni nada similar, así que tendremos que asumir que lo único que podemos hacer es ir aprendiendo que "churro" es mayor que otro por medio de observación de las respuestas del servidor.
Pepelux también estuvo pegándose con el reto y lo sacó de una manera similar aunque no idéntica a la que voy a explicar yo. Podeis verlo AQUÍ.
Para explicar el concepto del algoritmo utilizado vamos a suponer que la máquina elige 5 elementos diferentes (en el original serían hashes, y muchos más en cantidad, pero como ejemplo nos vale) que a priori el cliente no sabe en que orden van, aunque el servidor sí que conozca su orden:
El orden es lo de menos en realidad, pero supongamos que el servidor conoce a estos personajes y sabe que LUKE, aunque sea prota, es un poco soso, que CHEWIE es el papel más sencillo de aprender de la historia, pero que tiene mucho carisma, que YODA es el maestro de maestros pero OBIWAN siempre me ha gustado más, y que por supuesto VADER es el más grande de todos.
La primera idea de algoritmo que tuve es una lista a la que pudiera ir cambiando el orden según los descubrimientos que fuera haciendo, pero se me ocurrió que tenía la pega de que habría que recorrerla cada vez para buscar los elementos que queremos, y eso me parecía un poco "coñazo".
Por eso, pensando en alguna forma en que las búsquedas fueran muy rápidas, decidí usar un tipo de dato diccionario de Python, en los que los índices para buscar fueran los propios hashes, lo cual me permitía buscar el hash de una forma muy rápida. Pero... ¿cómo hacía después para comparar ambos hashes? Pues asignaba un valor entero "tentativo" a cada uno, así solo tenía que acceder por el hash, recuperar sus enteros y compararlos.
Con un pequeño ejemplo ayudado de nuestros amigos de Star Wars seguro que se entiende el algoritmo mucho mejor:
Antes de empezar comentaros que tenemos una variable "step" que la inicializamos a un valor muy alto. Para nuestro ejemplo lo haremos a 100, pero para el caso real se haría a un valor mucho mayor.
1. ¿OBIWAN o CHEWIE?: Ninguno de los dos está en el diccionario, así que elegimos al segundo como mayor. El sistema nos dice que FALLAMOS, así que hacemos lo siguiente:
dic['CHEWIE'] = 0
dic['OBIWAN'] = dic['CHEWIE'] + step = 100
step = step / 2 = 50
2. ¿LUKE o VADER?: Idem que antes. Elegimos el segundo y esta vez ACERTAMOS:
dic['LUKE'] = 0
dic['VADER'] = dic['LUKE'] + step = 50
step = step / 2 = 25
3. ¿YODA o CHEWI?: Yoda no lo tenemos aún, así que lo escogemos como mayor y ACERTAMOS:
dic['YODA'] = dic['CHEWI'] + step = 25
step = step / 2 = 12
Vamos a ver como va la cosa en el diccionario y seguimos unos pocos más:
dic['CHEWIE'] = 0
dic['LUKE'] = 0
dic['YODA'] = 25
dic['VADER'] = 50
dic['OBIWAN'] = 100
4. ¿LUKE o CHEWI?: Están empatados, así que cogemos cualquiera, el primero mismo, y FALLAMOS:
dic['CHEWIE'] = dic['LUKE'] + step = 12
step = step / 2 = 6
5. ¿VADER o YODA?: Vader es 50 y Yoda es 25, así que elegimos a Vader y ACERTAMOS, con lo que no tocamos nada, dejamos el diccionario como está.
6. ¿OBIWAN o VADER?: Obiwan es 100 y Vader 50, así que elegimos a Obiwan y FALLAMOS:
dic['VADER'] = dic['OBIWAN'] + step = 106
step = step / 2 = 3
Vamos a pegar otro vistazo a como llevamos la ordenación por ahora:
dic['LUKE'] = 0
dic['CHEWIE'] = 12
dic['YODA'] = 25
dic['OBIWAN'] = 100
dic['VADER'] = 106
Parece que a partir de este punto ya tenemos valores bien asignados en el diccionario, así que a partir de aquí todo van a ser aciertos, 75 o todos los que queramos. Lo único que hay que tener en cuenta es que el parametro step debe estar dimensionado a la cantidad de pasos que pensemos que vamos a necesitar.
Si por ejemplo calculamos que vamos a necesitar N pasos para aprender, entonces tenemos que elegir un step que sea 2^N, para que al ir dividiendo entre dos no nos vayamos a decimales. Tampoco pasaría nada siempre y cuando Python permita representar suficientes decimales (que no tengo ni idea de cuantos permite).
Esta es la idea del script que hice para superar el reto, solo que con un "step" mucho más grande y empleando los hashes en lugar de a nuestros amigos de Star Wars. Podeis descargar el script de AQUÍ si tenéis curiosidad en verlo completo. Lamentablemente tardaba bastante la ejecución y tuve que irme antes de que acabara, y cuando lo volví a lanzar ya se había acabado el tiempo del CTF y el servicio no estaba disponible, pero me programé yo un servicio que realizaba lo mismo (con unos pocos elementos) y la solución funcionaba perfectamente, por lo que presumiblemente debería funcionar igual con el servicio real.
Si los PPP publican el código del servicio de este reto lo probaré con él y pondré como una actualización en resultado.
.png "English"){kind=small}
Entradas
6 comentarios :
La verdad es que es una solución similar a la mía. Bueno, creo que la tuya está más optimizada a la hora de realizar las búsquedas de cada caso (con una lista haces menos comprobaciones que yo, aunque el coste de las inserciones es más elevado)
Está genial. Lástima que no te diera tiempo a probarlo hasta el final!
Felicidades por la explicación, el más claro de los writeup´s que he visto (el de pepelux tbm está bien ;) ).
Yo estuve media noche y parte de la mañana intentándolo pero me quedé por el camino...mis habilidades de scripting tiene que mejorar considerablemente.
Salu2
@Pepelux: Una cosa que a mi no se me ocurrió es guardar el estado por si se cerraba o algo. Muy buena idea por tu parte :) Creo que han sacado ya los scripts de los servicios (me suena haber leido algo en el Twitter de RS). Cuando tenga un rato lo probaré a ver si hubiera funcionado "tal cual".
@DvD: Me pasa igual que a ti, no programo todos los días, y cuando lo hago voy cambiando de lenguaje, así que me lio y tengo que tirar de manual hasta para hacer un bucle :P Programar la solución es sin duda un cuello de botella para mi, pero bueno, la cosa es ponerse, al final sale. Ánimo!
Una cosita...no pensaste que podrian ser simples numeros codificados en hexadecimal? digo ninguno es superior a "F",de manera que lo natural seria que fuera una codificacion hexadecimal y tirar por lo sano de buscar el de mayor tamaño con una calculadora simple...digo pregunto si lo intentaste por ese medio
@miniminiyo: Sí, claro, pero intenté adivinar unos cuantos así y fallaba (o eso me pareció). También pensé que pudieran ser hashes de números, pero la longitud no era potencia de 2 y no encontré ningún hash que fuera así.
Así fue como primero lo intenté, pero tras unos minutos de analizar los números no detecté que fuera nada de eso, así que me fui a por la "fuerza bruta".
No he leido muchos WriteUp's de este reto, pero los que he leido lo han resuelto como yo, aunque por supuesto no te puedo asegurar que no se pudiera resolver de la manera que dices tú.
Publicar un comentario