Come decifrare il testo quando mancano quattro prime lettere del tasto nel contest di Facebook CTF?

Question

Come decifrare il testo quando mancano quattro prime lettere del tasto nel contest di Facebook CTF?

#1 da (4 voti)
#2 da (2 voti)

2

Sono un principiante nella sicurezza informatica. Ora sto partecipando al concorso Facebook Catch the Flag. Devo risolvere il seguente compito:

C'è una chiave. Ma mancano i primi quattro caratteri della chiave:

_ _ _ _ U3xn3Gk9y

Questo è l'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;
}

Testo crittografato:

РY‘ґЊЈZц‚…Jщ,PvPw#ѓЗfыbаЁ+dИ?ѕцiЃyЛSBШ“¦ЕiЈ;иb—щьХЗ*]ЋOЛ,O™µEкЧи–ББш}

Ho bisogno di decifrare il testo ecrypted.

Prima di tutto, non sto chiedendo una soluzione o una risposta. Sto chiedendo alcuni suggerimenti:

Da dove dovrei iniziare a risolvere: trovare i primi 4 caratteri di chiave o numero casuale?
Come funziona l'algoritmo rand() ?
Se r ^ key[(r % strlen(key))] ^ text[i] = encrypted[i] è true, quale sarà la formula per text[i]= ?
Esiste un modo matematico per risolvere questo problema? Se è possibile, puoi chiamarlo?
Potresti dare qualche suggerimento (non una soluzione) per risolvere questo problema?

c encryption ctf

posta Joe Rakhimov 12.06.2016 - 18:20

fonte

2 risposte

Leggi altre domande sui tag c encryption ctf

Quali informazioni puoi ottenere da una foto? È sicuro non aggiornare Windows se non si accettano connessioni in entrata?

score 4 · Answer 1

Alcuni suggerimenti:

È probabile che le lettere nella chiave siano all'interno dell'intervallo di stampa ASCII.
Il testo decodificato è probabile all'interno dell'intervallo di stampa ASCII.
Non è molto difficile bruteforce un numero a 32 bit, anche meno difficile se puoi ridurre lo spazio sulla chiave.

score 2 · Answer 2

Sì, puoi forzare questa forza piuttosto velocemente, ma se sei curioso, non hai bisogno di forzare questa intera soluzione. C'è un approccio matematico. Potresti persino richiedere parti di ciò in ogni caso poiché questo sembra essere un algoritmo di hashing e non un algoritmo di crittografia (non è reversibile in modo affidabile).

Ti fa incuriosire che un algoritmo di crittografia ripetibile usi la generazione di numeri casuali? Questo può funzionare solo quando il seme casuale (cercare srand ) è impostato in modo coerente per lo stesso input, il che significa che le chiamate consecutive a rand() restituiranno la stessa sequenza ordinata di risultati.

Q. Com'è la serie di semi casuali in questo caso?

A. Dal prodotto dei codici carattere dei primi quattro caratteri, quelli che mancano.

Sappiamo dal codice che il testo crittografato risultante avrà la stessa lunghezza dell'input in testo normale. Sappiamo anche che ogni carattere di output crittografato è generato dal carattere originale nel suo indice come questo: %codice%.

Da questo puoi ricavare una semplice formula matematica per trovare (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) in un dato passaggio attraverso la crittografia basata su un codice di carattere di output e un indice.

Non sono riuscito a trovare una fonte ufficiale gratuitamente, ma diversi luoghi come qui mostrano come il c% la funzioner è implementata:

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;
}

Si noti che il seme viene regolato ogni volta che viene generato un numero. Puoi creare un'altra formula basata sull'implementazione rand per trovare quali valori possibili rand possono quando next restituisce il codice carattere associato al quinto carattere dell'output (il primo associato a un carattere chiave che conosci) . Prendi ciascuna di queste possibilità e filtrale eseguendo passaggi successivi attraverso rand in base al codice precedente e il codice di crittografia utilizzando l'output rand come valore rand e controllando i risultati con i successivi caratteri dell'output fino a ti rimane solo una singola opzione valida valida per r al 5 ° passaggio.

Una volta che lo sai, inverti quella volta per ognuno dei personaggi precedenti per ottenere i primi 4 valori di next . Dopo aver risolto i valori di r , tutto ciò che rimane è di invertire r per risolvere output[i] = r ^ key[(r % strlen(key))] ^ text[i] . Sarà utile ricordare che l'inverso di text[i] è y = a ^ x . Inserisci i valori di y = log base a (x) che hai risolto in precedenza nell'ordine corretto per ottenere i codici di carattere associati a tale passaggio attraverso la crittografia. Aggiungi quelli all'inizio della chiave e controlla il tuo lavoro invertendo l'algoritmo di crittografia e passando la nuova chiave con il testo crittografato e verificando se l'output ha senso. Se lo fa, hai completato la sfida senza forza bruta (tranne forse nel tuo filtraggio).

Ovviamente, dato che lo spazio chiave è abbastanza piccolo per bruteforce, puoi sempre farlo.