HPC - Brute-force password cracking

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-10-13

Il programma omp-brute-force.c contiene un messaggio cifrato lungo 64 byte memorizzato nell'array enc[]. È stato usato l'algoritmo crittografico XOR, che consiste nell'applicare l'operatore logico "or esclusivo" (xor) tra il testo in chiaro e la chiave. Questo algoritmo in generale non è sicuro, tranne in casi particolari, ma risulta adeguato per i nostri scopi.

La chiave di cifratura è una sequenza di 8 caratteri ASCII che rappresentano cifre numeriche; è quindi compresa tra "00000000" e "99999999". Nel programma è fornita una funzione xorcrypt(in, out, n, key, keylen) per decifrare un messaggio cifrato data la chiave:

L'algoritmo di cifratura produce sempre un messaggio decifrato data una chiave qualsiasi; se la chiave non è quella corretta, il messaggio decifrato conterrà caratteri senza senso. Nel nostro caso, il messaggio in chiaro è una stringa di caratteri zero-terminata (quindi stampabile da printf()), i cui primi dieci caratteri sono "0123456789".

Scrivere un programma per realizzare un attacco di tipo brute force allo spazio delle chiavi sfruttando il parallelismo OpenMP. Il programma deve tentare tutte le possibili chiavi da "00000000" a "99999999", fino a quando ottiene un messaggio decifrato che inizia con "0123456789"; trovata la chiave, il programma deve stampare il messaggio decifrato, che è una citazione da un vecchio film.

Si usi un costrutto omp parallel (non parallel for) inserendo all'interno del quale codice che assegna a ciascun thread un opportuno sottoinsieme dello spazio delle chiavi. Ricordare che il costrutto omp parallel si applica a structured blocks, ossia a blocchi con un unico punto di ingresso e un unico punto di uscita. Quindi, il thread che trova la chiave corretta non può uscire dal blocco con return, break o goto (l'uso di simili istruzioni in un blocco parallelo dovrebbe causare un errore in fase di compilazione); d'altra parte non vogliamo aspettare che tutti i thread abbiano esplorato l'intero spazio delle chiavi per terminare. Serve quindi un meccanismo per terminare la computazione in modo "pulito" non appena uno dei thread abbia trovato la chiave. Non sono consentite soluzioni brutali come exit() o abort().

Compilare con:

    gcc -std=c99 -Wall -Wpedantic -fopenmp omp-brute-force.c -o omp-brute-force

Eseguire con:

    OMP_NUM_THREADS=2 ./omp-brute-force

Nota: il tempo di esecuzione del programma parallelo potrebbe cambiare in modo irregolare al variare del numero \(P\) di thread OpenMP. Perché?

File

Per trasferire in modo semplice i file direttamente sul server è possibile usare il comando wget (già installato sul server). Ad esempio:

    wget https://www.moreno.marzolla.name/teaching/HPC/handouts/omp-brute-force.c