¿Cómo descifrar el texto cuando faltan cuatro primeras letras de la clave en el concurso CTF de Facebook?

Question

¿Cómo descifrar el texto cuando faltan cuatro primeras letras de la clave en el concurso CTF de Facebook?

#1 de Polynomial (4 votos)
#2 de S.C. (2 votos)

3

Soy principiante en seguridad cibernética. Ahora estoy participando en Facebook del concurso Catch the Flag. Tengo que resolver la siguiente tarea:

Hay una clave. Pero faltan los primeros cuatro caracteres de la clave:

_ _ _ _ U3xn3Gk9y

Este es el algoritmo:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    FILE *fi, *fo, *fk;
    int i, r;
    char key[20], text[100];

    fi = fopen("flag.txt", "r");
    fo = fopen("encrypted.txt", "w");
    fk = fopen("key.txt", "r");

    fscanf(fi, "%s", text);
    fscanf(fk, "%s", key);



    srand(key[0] * key[1] * key[2] * key[3]);
    for(i = 0; i < strlen(text); ++i)
    {
        r = rand();
        putc(r ^ key[(r % strlen(key))] ^ text[i], fo);
    }

    fclose(fi);
    fclose(fo);
    fclose(fk);
    return 0;
}

Texto cifrado:

P

Necesito descifrar el texto ecrypted.

En primer lugar, no estoy pidiendo una solución o respuesta. Estoy pidiendo algunos consejos:

¿Desde dónde debo comenzar a resolver: para encontrar los primeros 4 caracteres de un número clave o aleatorio?
¿Cómo funciona el algoritmo rand() ?
Si r ^ key[(r % strlen(key))] ^ text[i] = encrypted[i] es verdadero, ¿cuál será la fórmula para text[i]= ?
¿Hay alguna forma matemática para resolver este problema? Si existe, ¿podrías nombrarlo?
¿Podría dar alguna sugerencia (no solución) para resolver este problema?

encryption ctf c

pregunta Joe Rakhimov 12.06.2016 - 18:20

fuente

2 respuestas

Lea otras preguntas en las etiquetas encryption ctf c

EFI: encripta ESP ¿Las solicitudes sin encabezado UserAgent son un riesgo?

score 4 · Answer 1

4

Algunos consejos:

Es probable que las letras en la clave estén dentro del rango de impresión ASCII.
Es probable que el texto decodificado se encuentre dentro del rango de impresión ASCII.
No es muy difícil imponer un número de 32 bits, incluso menos si puedes reducir el espacio de la clave hacia abajo.

respondido por el Polynomial 12.06.2016 - 21:05

fuente

score 2 · Answer 2

Sí, puedes usar esta fuerza bruta con bastante rapidez, pero en caso de que sientas curiosidad, no necesitas forzar esta solución completa. Hay un enfoque matemático. Puede que incluso requiera partes de esto, ya que parece ser un algoritmo de hash y no un algoritmo de cifrado (es decir, no es reversible de manera confiable).

¿Le da curiosidad que un algoritmo de cifrado repetible utilice la generación de números aleatorios? Eso solo puede funcionar cuando la semilla aleatoria (buscar srand ) se establece de manera consistente para la misma entrada, lo que significa que las llamadas consecutivas a rand() devolverán la misma secuencia ordenada de resultados.

Q. ¿Cómo se establece la semilla aleatoria en este caso?

A. Por el producto de los códigos de caracteres de los primeros cuatro caracteres, los que faltan.

Sabemos por el código que el texto cifrado resultante tendrá la misma longitud que la entrada de texto sin formato. También sabemos que cada carácter de salida cifrado es generado por el carácter original en su índice de esta manera: %código%.

A partir de eso, puede derivar una fórmula matemática simple para encontrar (random number generated from the seed at the n'th pass where n is the current index + 1) ^ (that same random number mod the key length of 13 in your example) ^ (the character code at the current index) en un paso dado a través del cifrado basado en un código de carácter de salida e índice.

No pude encontrar una fuente oficial de forma gratuita, pero varios lugares como aquí muestran cómo el c% Se implementa la función r :

static unsigned long int next = 1;

int rand(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

void srand(unsigned int seed)
{
    next = seed;
}

Observe que la semilla se ajusta cada vez que se genera un número. Puede crear otra fórmula basada en la implementación rand para encontrar qué valores posibles rand puede cuando next devuelve el código de carácter asociado con el quinto carácter de la salida (el primero asociado con un carácter clave que usted conoce) . Tome cada una de esas posibilidades y filtre hacia abajo ejecutando pases subsiguientes a través de rand según el código anterior y el código de encriptación que usa la salida rand como el valor rand y compare los resultados con los siguientes caracteres de la salida hasta solo te queda una única opción válida válida para r en la quinta pasada.

Una vez que sepa eso, invierta esa vez para que cada uno de los caracteres anteriores obtenga los primeros 4 valores de next . Una vez que haya resuelto para esos valores de r , todo lo que queda es revertir r para resolver para output[i] = r ^ key[(r % strlen(key))] ^ text[i] . Será útil recordar que la inversa de text[i] es y = a ^ x . Conecte los valores y = log base a (x) que resolvió anteriormente en el orden correcto para obtener los códigos de caracteres asociados con el paso a través del cifrado. Agregue esos al principio de la clave y verifique su trabajo invirtiendo el algoritmo de cifrado y pasando su nueva clave con el texto cifrado y observando si la salida tiene sentido. Si lo hace, has completado el desafío sin fuerza bruta (excepto quizás en tu filtro).

Por supuesto, ya que el espacio clave es lo suficientemente pequeño como para fuerza bruta, siempre puedes hacerlo.