Thanatos

Implementazione di un attacco a Forza Bruta sul Crittosistema D.E.S.tramite un’infrastruttura di calcolo distribuito e parallelo

In ordine Alfabetico:

Francesco PietralungaIdriss RiouakRenato GaravagliaTommaso Campari

Corso di Laurea in Informatica

SOMMARIO• Strumenti utilizzati• Scopo del progetto• DES - Implementazione in C• Introduzione CUDA–C • Architettura CUDA• Implementazione DES su CUDA -C

Strumenti Utilizzati

Editorditestoeproject manager.Unostrumentotecnologicamentesofisticatoeall’avanguardiaconlacompilazionestaticael’integrazionediunosoftwarediversionamento.

Strumenti UtilizzatiCompilatoreSviluppatodaApple.PossiedealcuniprogettidisviluppodiwrapperperMPIcomempicc.

Strumenti Utilizzati

Repository esoftwarediversionamento.

Strumenti Utilizzati

APIUtilizzatenelleapplicazionipersistemiamemoriadistribuitaperilCalcoloParallelo

Strumenti Utilizzati

E’unopackageditools perlaverifica,ilprofiling eildebugging diprogrammi.Valgrind è ingradodirilevareautomaticamentelapresenzadimemory leak.

Strumenti Utilizzati

API multipiattaforma per la creazione di applicazioni parallele su sistemi a memoria condivisa

Strumenti Utilizzati

Strumenti Utilizzati

Scopo del Progetto

Lo scopo del nostro lavoro è quello non tanto di mettere in evidenza le già note vulnerabilità del crittosistema DES, ma piuttosto quello di fare un confronto tra due approcci distinti di attacco al crittosistema che utilizzano la medesima modalità ma con strumenti differenti, in particolare verranno utilizzate nella prima parte dei test le CPU presenti sui nodi della rete, mentre nella seconda parte verranno utilizzate le GPU.

Il DES (Data Encryption standard ) è un Crittosistema scelto come standard dal Federal Information Processing Standard (FIPS) per il governo degli Stati Uniti d’America nel 1976. Si basa su chiavi a 64 bit (di cui 8 sono di controllo, quindi lo spazio dei valori si riduce a 56 bit) e per questo si presta a un attacco a Forza Bruta. Seppur 256 chiavi siano poche, un singolo processore impiegherebbe anni a testarle tutte, per questo già nel 1998 gli EFF’s DES cracker (Deep Crack) ruppero il DES in appena 56 ore grazie a un supercomputer equipaggiato con 1856 chip.

DES -Implementazione in C

DEMO PRATICA

IlCèunlinguaggiodiprogrammazionedibassolivello,perquestoèspessovistocomeunodeilinguaggipiù́performantiincircolazione.InoltrehasvariatelibreriechepermettonodisvolgerefunzionialtrimenticomplicatecomeiltrasferimentodellechiavidalmasteraivariWorkerconOpenMPIol’esecuzioneconmultithreadinggrazieaOpenMP.

Introduzione CUDA-C

PerchéCUDA-C? Noiabbiamoscelto CUDA-Cinquantosiprestavaparticolarmenteainostrifini:fornisceinfattisupportoaOpenMPI eOpenMP elepartiCPUsipresentanocomunqueefficientiinquantoC ètrailinguaggipiùperformanti.

Cos’èCUDA-C?LeschedegraficheconsupportoaCUDA (ComputeUnifiedDeviceArchitecture)sonountipodiHardwarecreatodaNVIDIAperpermetterel’esecuzionedicalcoloparallelosuGPU.Ilinguaggidiprogrammazionedisponibilinell’ambientedisviluppoperCUDA,sonoestensionideilinguaggipiùdiffusiperscrivereprogrammi.IlprincipaleèCUDA-C(CconestensioniNVIDIA),altrisonoestensionidiPython,Fortran,JavaeMATLAB.

Architettura CUDA

CUDA basa il suo funzionamento sul concetto di esecuzione parallela,questo è possibile grazie a particolari funzioni marcate con la keywordglobal che sono anche definite come funzioni kernel.Una funzione kernel si presenta esattamente come una funzione C nella suadefinizione, le differenze si mostranoinfatti al momento della chiamata che è strutturata come:

kernel<<<NumBlocks,NumThreads>>>(Arguments);

Implementazioni DES su CUDA-C

1° ImplementazioneCUDA-C

2° ImplementazioneCUDA-C

PROFILING• Profiling DES su CUDA-C• ZeroCopyMemory• Profiling Jetson TX1

NVIDIA teslak40ccon1GPUxKeplerGK110Beprestazioni1.66TFlops(clockdiGPUBoost)

Scheda Grafica K40c

Profiling DES su CUDA-C

Profilingdeitempid’esecuzioneconnvprof.

Profiling generate_all_subkeys. (1)

Kernel Performance

Profiling generate_all_subkeys. (2)

Function Unit Utilization

Profiling try_all. (1)

Kernel Performance

Profiling try_all. (2)

Function Unit Utilization

Profiling try_all. (3)

Stall Reasons: Ragioni di Stallo.

Jetson TX1

SchedaJetsonTX1conCPU64-bitARM®A57CPUs eGPU1TFLOP/s 256-corewithNVIDIA Maxwell™Architecture

Jetson TX1

L’università ci ha fornito l’accesso ad una scheda Jetson TX1 sulla quale effettuare dei test.

Questa scheda, ha un’unica memoria centrale, condivisa tra CPU e GPU.

Infatti per utilizzare questa scheda, per allocare la memoria, bisogna utilizzare il metodo d’allocazione ZeroCopy.

ZeroCopyMemory

Per l’implementazione è stato modificata la seconda implementazione in CUDA-C cfr(Slide 7)

Sostituendo le classiche cudaMalloc con le chiamate cudaHostAlloc fornitedalla libreria CUDA e le cudaMemcpy con cudaGetHostDevicePointer con le seguentiSintassi.

cudaError_t cudaHostAlloc(void** pHost, size_t size, unsigned int flags).

cudaError_t cudaHostGetDevicePointer(void ** pDevice, void * pHost, unsigned int flags).

Profiling Jetson TX1

Analisi dei tempi d’esecuzione sulla macchina Jetson TX1

Comunicazione & Distribuzione Chiavi

• Entità Server e Client• Scatter• Coda• Opzioni d’esecuzione• Gestione delle richieste

Comunicazione & Distribuzione Chiavi

OpenMPI(MessagePassing Interface): APIperlagestionedellecomunicazioni traivarinodi.

OpenMP(MultiProcessing): è un API multipiattaforma per la creazione di applicazioni parallele su sistemi a memoria condivisa.

Comunicazione & Distribuzione Chiavi

• L’entitàServer:chedistribuisceblocchidichiaviaisingoliClientenetestailrisultato.

• L’entitàClient:cheperognichiavedelbloccopassatogliprovaadecifrareilmessaggioesehasuccessoinformailServerchelachiaveè statatrovataedunqueilmessaggiomessaggiovieneridecifratodalServer emostraall’utentelachiavetrovata.

Scatter & Coda (1)

Int MPI_Scatter( const void* sendbuf, int sendCount, MPI_Datatype sendtype, void* recvbuff, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm);

Scatter & Coda (2)

256 chiavi

255 chiavi

• Supponiamo di avere K client con CPU a disposizione

Numero di Blocchi= 255

#$%&'()

L’eventuale resto viene calcolato dall’ultimo client.

Gestito tramite coda. Slide successiva

Scatter & Coda (2)

225 + 224

225

224

0

Server Client

Server comunica l’offset

Una volta comunicato l’offset viene eliminato.

Una volta ricevuto l’offset il client elabora le chiavi.

Per l’opzione -cpusono stati utilizzati offset d’ampiezza 262.144

Opzioni d’esecuzione (1)

typedef struct {longlongpossibileChiave;longlongprocessID;double tempo;int tipo;

}infoExec;

static MPI_Datatype Info_Type;

Opzioni d’esecuzione (2)

-cpu: vengono utilizzate come unica unità d’elaborazione le CPU.

-gpu: vengono utilizzate come unica unità d’elaborazione le GPU.

-zcmem: deve essere preceduta da –gpu o da -hybrid, e permette di eseguire i test utilizzando i costrutti CudaHostAlloc e CudaGetHostDevicePointer.

-hybrid: permette di utilizzare contemporaneamente sia l’unità d’elaborazione CPU che GPU, sfruttando dunque al massimo tutta la potenza computazionale a disposizione.

Gestione delle richieste

Per poter gestire i diversi messaggi che i client devono mandare al server, utilizziamo diversi tipi di TAG. cfr(OpenMPI)

• Key_found_tag (0): Utilizzando questo Tag, il client comunica al master che ha trovato la chiave per decifrare il messaggio di partenza.

• New_offset_request_tag (1): Utilizzando questo Tag, il master è in grado di capire che uno dei client ha bisogno di un nuovo blocco di chiavi da processare.

• Info_on_elaboration_tag(2): Utilizzando questo Tag, il client raccoglie il messaggio e lo elabora per ricavare l’avanzamento totale dell’attacco.

GREEN COMPUTING VS GRID COMPUTING

• TESLA VS XEON VS JETSON• ARM VS XEON• ZeroCopyMemory• Hybrid Function: 4K40 VS TX1• 1998 VS 2016

TESLA VS XEON VS JETSON

TESLA VS XEON VS JETSON

ARM VS XEON

ZeroCopyMemory Testing (1)

ZeroCopyMemory Testing (2)

HYBRID FUNCTION: 4K40 VS TX1

1998 VS 2016 (1)

Grafico delle chiavi testate per giorno da DESCHALLnel 1998.

Grafico dei Client connessi in ogni giorno di elaborazionesu DESCHALL nel 1998.

1998 VS 2016 (2)

In particolare osservando il seguente graficonotiamo come nel massimo picco di potenza dicalcolo (con all’incirca 14000 Client connessi)DESCHALL elaborasse “solo” 600 trilioni dichiavi al giorno, mentre oggi il nostro sistema conlo stesso numero di Client ne elaborerebbe2,536 Quadrilioni cfr(Slide 34), garantendo quindi unincremento delle prestazioni del 422 %