CryptoAnalisisServer(CAS)
Reti di Calcolatori LS
progetto di Carpenè Michele, Busacca Fulvio
Servizio distribuito basato sul calcolo
parallelo per operazioni di crittanalisi
A.A. 2004/2005
PARTE I (Carpenè)
Struttura e funzionamento-bilanciamento
del carico-prima implementazione
La crittanalisi: 2 parole
• La Crittologia è la scienza che studia come
difendere l’informazione da attacchi
intenzionali
• due distinte discipline:
• Crittografia: gli algoritmi e i protocolli che
occorrono a fronteggiare gli attacchi degli
intrusi
• Crittanalisi: valuta la robustezza esaminando
come, in quanto tempo e con quali risorse è
possibile rompere le difese
Il sistema
sistema distribuito per effettuare attacchi con forza
bruta:
proviamo tutte le combinazioni possibili di chiave per
giungere comunque a una soluzione del problema,
anche in un periodo di tempo lungo.
Obiettivi:
comprendere come il calcolo parallelo sia uno
strumento efficace per risolvere problemi di calcolo in
tempi ragionevoli e cimentarci con una caso pratico
Possibili architetture (1)
server centrale con funzione di
manager
Possibili architetture (2)
manager replicato su tutti i
nodi clienti
Possibili architetture (3)
simmetrico
Architettura del Manager
Listener:
Allocazione statica
RequestManager,
Esecutor:
Allocazione
dinamica
Il bilanciamento del carico
• carico = coefficiente prestazione
macchina + numero chiavi + lunghezza
file
•Se aumentiamo i processori l’efficienza
tende a zero

Necessità di stimare un lowerbound
Caso due processori
Ipotesi:
caso peggiore
I due processi partono insieme
Caso generale di N processori :
tmono > trandevouztot + tricercalocale
tmono > trandevouztot + tmono /N
tmono *(N-1)/N > trandevouztot
tmono > N/(N-1)*trandevouztot
Dove:
trandevouztot = trandevouzcliente +tloadbalancing
+N*(trandevouzhost+tallocazioneprocessi)
Caso generale di N processori :
tcontrollofile*nchiavi > N/(N-1)*trandevouztot
nchiavi > N*trandevouztot /[(N-1)*tcontrollofile]
nchiavi = 2^L (L lunghezza chiave)

L > log2 (N*trandevouztot /[(N-1)*tcontrollofile])  Lowerbound
Attenzione!!!
gli host potrebbero essere già carichi!
È interessante notare come nel caso di un
numero elevato di processori la funzione di
lower-bound possa essere approssimata:
Infatti per N tendente a un numero elevato diventa
nchiavi > trandevouztot /tcontrollofile
e quindi:
Lowerbound  log2 (trandevouztot/tcontrollofile)
prova con un file di 16 righe cifrato con
una chiave TriploDes a 168 bit, con tre
slave attivi.

Usando valori temporali indicativi è
risultato in queste condizioni un lower
bound minimo di 375468 chiavi.

nettamente inferiore a 2^168
Ripartizione del carico
per ogni slave viene calcolato il carico
corrispondente in base al carico di cui è
già gravato e in base al carico totale.
Per ognuno di essi è:
NKey = (K/N)*(1-CaricoSlave/CaricoTotale)
Nkey=0  nessun carico assegnato
Esempio di esecuzione (1)
Esempio di Esecuzione (2)
E se il carico totale è inferiore al
lwb???
• si è previsto di assegnare ugualmente il
compito ripartendolo su un sottoinsieme
degli host attivi.
• Necessarie due procedure:
• La prima ricalcola il lwb
• La seconda determina le n macchine
meno cariche
Nel caso in cui sia presente un unico
host attivo la soluzione è semplice:
il carico viene assegnato interamente a
quell’host.
Il client e lo slave (1)
• Il processo client si occupa di fornire
una semplice interfaccia grafica che
permetta all’utente di inserire i dati
(nome del file, lunghezza della chiave e
algoritmo di codifica),
• quindi il client invia la richiesta al
processo Listener che si occuperà di
servirla e rimane in attesa del risultato.
Il client e lo slave (2)
• Lo slave invia costantemente un
messaggio di disponibilità ad effettuare
il servizio al Listener e si occupa di
istanziare un oggetto GestoreRichiesta
che fa fisicamente l’operazione di
ricerca
• Invia il nome del gestore al
ServerManger
Se non ci sono slave attivi il
sistema risponde:
Spiacente nessuno slave
presente
Impossibile effettuare
l’operazione
Il client e lo slave (3)
• Il formato del pacchetto richiesta è questo:
• mentre il pacchetto dello slave è
semplicemente questo:
La comunicazione
Il risultato
Implementazione
•
•
•
•
Implementazione in java
20 classi
Uso della libreria matematica BigInteger
Per la comunicazione inter-processo: javaRMI
Conclusioni
• Dipendenza dello speed-up dalla probabilità
di trovare la chiave subito
• La sequenza del rande-vouz limita lo speedup del sistema
Sviluppi futuri
• Prevenzione di fenomeni di congestione
• Eventuale gestione dinamica del bilanciamento
Bibliografia
• [1] R.Laschi, R.Montanari: Appunti di
Tecnologie per la sicurezza (Progetto
Leonardo Bologna).
• [2] Dispense di reti di calcolatori LA (Docente:
Antonio Corradi, università di Bologna).
• [3] Dispense di reti di calcolatori LS (Antonio
Corradi)