martedì 10 giugno 2014

E ci risiamo (was: crittografia e steganografia)

A quanto pare, e' stato scoperto un altro baco grave nella crittografia di OpenSSL. Del resto, con l'adozione massiva da parte di giganti come Google, le librerie stanno venendo passate al setaccio, e siccome i giganti IT americani stanno perdendo soldi a gogo per via della questione di Snowden (1), vogliono far vedere che loro alla sicurezza ci badano. Ma questo mi fa arrivare diverse domande nella casella di posta elettronica.



La domanda principale che mi arriva e' "ma esiste un modo per trasformare la steganografia in uno standard sicuro, ovvero in qualcosa che non spera che il mio nemico non trovi il contenuto, ma in qualcosa che e' CERTO che senza una data chiave non si trovi nulla?".

Altri mi chiedono se non ci sia uno standard ancora piu' sicuro di RSA, e se non esistano metodi ancora piu' sicuri del Pad casuale.

La risposta e' si, ma questa sicurezza ha un prezzo. Vediamo perche'.

Avevo spiegato nel post "Steganografia" come costruire un algoritmo che nasconda un messaggio di testo all'interno di un file di immagine, onde renderlo introvabile. http://www.keinpfusch.net/2014/06/steganografia.html

Sebbene il LSB sia praticamente rumore bianco, e sebbene sia possibile criptare il contenuto prima di metterlo nel file, la domanda e': e se volessimo andare oltre? E se volessimo qualcosa di cosi' mostruoso che nemmeno usando tutte le particelle subatomiche dell'universo per tutto il tempo dell'universo potessimo decrittare il messaggio? Esiste qualcosa che potrebbe dare dei problemi di budget a Dio?

Si, esiste. Ci viene in aiuto il meraviglioso mondo dell'algebra  ed in particolare delle permutazioni.

Adesso astraiamo il concetto. Nella steganografia dell'esempio del mio post, mettevamo il bit N-esimo nel pixel N-esimo, realizzando una trasformazione monotona da N -> N. 

Insomma, se in un vettore N mettevamo i bit da criptare e in un vettore M il file ove criptare, allora 

N[1] veniva criptato in M[1]
N[3] veniva criptato in M[2]
N[4] veniva criptato in M[3]
---
N[n] veniva criptato in M[n]


Adesso proviamo a rompere l'assunzione di monotonia. E diciamo chiaramente che da qualche parte salviamo una "chiave", ovvero una tabella per cui 

 

N[1] veniva criptato in M[a]
N[3] veniva criptato in M[b]
N[4] veniva criptato in M[c]
---
N[n] veniva criptato in M[d]
e la nostra tabella contiene le corrispondenze tra 1 ed il valore di a, 2 ed il valore di b, eccetera. Chiameremo "chiave" questa tabella.

Allora, il nostro programma scritto in pseudocodice si scrive cosi':

per ogni  bit[i] da criptare
estrai un numero x a casaccio compreso tra 1 e la dimensione del file "nascondiglio".
se il numero estratto non esiste gia' nella chiave.
 nascondi il bit nel pixel x-esimo dell'immagine.
 salva la coppia  {i,x} nella chiave
                salva la chiave.
salva la chiave

ora, la domanda che vi pongo e': se i e' il numero di bit da nascondere e x e' il numero di pixel a disposizione, in quanti modi possiamo distribuire i it in x pixels, se x >> i?

La risposta e' che si tratta di un fattoriale particolare, ma senza stressarvi troppo con la teoria, possiamo andare a chiederci: se salvo diciamo 80 KB (640.000 b) in una fotografia diciamo 8 Milioni di Pixel, in quanti modi posso salvare 640.000 elementi in una scelta di 8 milioni di caselle?

Beh, lasciate perdere. Lasciate perdere perche' il numero sarebbe cosi' gigantesco che non importa davvero. Non importa davvero perche' chi volesse anche provarci con un attacco brute-force dovrebbe comunque ricordare ogni tentativo fatto, al fine di non ripeterlo.

Ma quanto spazio occorre per ricordare un attacco brute-force del genere? 


Beh, dobbiamo chiederci in quanti modi possiamo "rimescolare" 640.000 bit in 8.000.000 di posizioni diverse. In generale, per le combinazioni semplici vale:


Nel caso di n=8.000.000 e di k=640.000 , il numero che otteniamo e' "grandino", di uno di quei "grandini" che e' difficile da capire. Si tratta del prodotto degli ultimi  640.000 numeri che precedono 8.000.000 , diviso per i primi 640.000. 

Per la precisione: 5.18 moltiplicato per 10 elevato alla 968540 

 
Un "numerillo" che ha quasi un milione di zeri.

Si tratta di un problema  che per i numeri di cui parliamo, si esprime in questo modo: "anche usando come memoria ogni particella subatomica dell'universo, per tutto il tempo dell'universo, sfruttando la piu' veloce trasformazione che una particella possa effettuare,  non si potrebbe  fare questo calcolo per mancanza di risorse macchina".

Insomma, anche Dio avrebbe qualche problema di budget.

Adesso facciamo un passo indietro: ma con numeri di queste dimensioni, abbiamo davvero bisogno di usare una foto?

La risposta e' no. Cosi' possiamo usare il cosiddetto "xor con pad", e potenziarlo un attimo. 

Nello xor con pad, quello che si fa e' di avere una sequenza di numeri casuali grande quanto il messaggio da criptare, e di criptare usando uno xor il nostro messaggio. A costituire la "chiave" e' il pad, cioe' la sequenza casuale che stiamo usando. Idealmente, se due fonti casuali avessero la stessa sequenza, sarebbe "impossibile" se non usando un attacco brute-force, risalire al pad. 

Questa tecnica rende ogni combinazione di lettere e caratteri ugualmente probabile, ma lasciando le cose al loro posto, e' ancora del tipo "monotono", cioe' se il bit i viene prima di n, anche nel messaggio criptato il bit I viene prima del bit N.

Proviamo allora a ricalcolare il tutto, usando quanto detto. Bob e Jane vogliono criptare usando un pad. Ma non si scambiano il pad. Bob genera rumore bianco, (il pad) ed esegue un algoritmo di questo genere, e ha come dicevo sopra una chiave che esprime delle permutazioni:

per ogni bit i del messaggio da criptare
estrai un numero x a caso da 0 alla dimensione del pad.
verifica che la x non si trovi gia' nella chiave.
se non si trova nella chiave
infila il bit numero i dentro il LSB del byte x-esimo del pad
salva la coppia i,x nella chiave 
        
a questo punto il pad - rumore bianco - e' pronto per essere inviato da bob a Jane, che possiede la chiave.

Chi si trova in mezzo vede passare bit a casaccio. Chiaramente SA che dentro c'e' qualcosa di criptato, ma non ha alcun modo per tirarlo fuori da li'. Anche se Jane non ha un randomizzatore identico a portata di mano, il punto e' che solo Jane sa quali LSB leggere dal quel rumore bianco.

Supponiamo di usare sempre la stessa chiave: supponiamo di criptare sempre 640.000 bit in 8.000.000 di bytes usando sempre la stessa chiave.  Certo, e' un overhead mostruoso, perche' spediamo 8Mb ogni 80K da inviare. Ma se vi chiedete quante risorse servano per decodificare questo codice, beh: forget it. Non si puo'.

Adesso la vostra obiezione sara' che Bob e Jane devono scambiarsi la chiave in maniera sicura, e qui entra in campo il problema che molti esprimono dicendo "se un canale e' sicuro per la chiave lo e' anche per il contenuto". Ma non e' del tutto vero, perche' al momento dello scambio delle chiavi magari il messaggio non esiste ancora.

Prendiamo per esempio una flotta di navi in partenza: i comandanti vanno in un posto sicuro dentro l'arsenale, prendono le chiavi , le portano a bordo delle navi (che sono sempre dentro l'arsenale) e le portano a bordo. Una volta allineate le chiavi, possono salpare, e usare questa tecnica per far comunicare le navi tra loro. E il nemico non ha la piu' pallida chance di decifrare niente.

In qualsiasi organizzazione e' possibile che i caposervizio si incontrino di persona in una stanza, prendano le chiavi e le installino sui router, diciamo ogni anno. Di conseguenza, sebbene lo scambio di simili chiavi sia oneroso, non e' necessariamente infattibile , per esempio con le ambasciate (un addetto puo' occuparsi di portare personalmente le chiavi ogni anno) .

Stiamo cioe' passando da sistemi di codifica basati su problemi legati a problemi di soluzione ancora ignota (come la fattorizzazione veloce in numeri primi) a problemi di tipo combinatorio, di cui la soluzione e' assolutamente nota, ma non per questo il vostro avversario avra' vita facile.

Di fatto stiamo parlando di tecniche permutatorie, come sono DES e AES, che appartengono alla stessa famiglia, ma anziche' complicarci la vita con l'algoritmo, cioe' caricando il lavoro sulla CPU, abbiamo deciso di diventare network-intensive, inviando 8MB ogni volta che vogliamo inviare 80KB. 

Ovviamente questo non e' fattibile per sistemi client-server, perche' si tratta di sistemi che necessitano di trasmettere le chiavi lungo lo stesso canale ove passa il messaggio.

Ma se mi chiedeste come crittare un 1GB di disco rigido, preferirei questa tecnica ad AES: e' vero che avrei un costo di 99GB ogni GB criptato, spendendo 100GB per crittarne uno. Ma d'altro canto, a meno di non trovare le chiavi, non vedo proprio in che modo un attaccante potrebbe uscirne.

Alla fine, l'algoritmo diventerebbe:

leggi la chiave con le coppie
leggi 80KB di file da criptare.
alloca un buffer grande 8MB
riempi il buffer di numeri casuali
per ogni bit i del file da criptare
cerca nella tabella la posizione x dove nascondere il bit
scrivi il bit i-esimo del file da criptare nell' LSB dell' x-esimo BYTE nel buffer
salva il buffer 
se necessario, rifai con i prossimi 80K.

 
 la generazione di una chiave e' ovviamente semplice:

per i da 1 a 640.000
estrai un numero x a caso da 1 a 8.000.000
se non esiste gia' nella chiave
inserisci i,x dentro  la chiave
salva la chiave


niente di che. Ma chi trovasse i file criptati senza disporre della chiave si troverebbe con un "serio problemino" nel decrittarli.



(1) Putin si sta facendo vedere in giro con un cellulate Tizen, e Samsung dopo qualche settimana ha annunciato il lancio di un cellulare Tizen in Russia. Vedete voi come l'ha presa Google.

Discussioni & Commenti (Il Salotto Buono di KEIN PFUSCH®).

Per postare nel gruppo, semplicemente cliccate sul tasto rosso a sinistra se l'argomento e' nuovo, oppure cliccate sugli argomenti per rispondere. In caso non siate iscritti il sistema vi guidera' all'accesso. In ogni caso il vostro indirizzo email non sara' pubblicato dal forum.

So che e' seccante, ma l'aumento del traffico sul sito mi obbliga ad usare un sistema piu' adatto alle mie disponibilita' di tempo, cioe' un sistema ove la quantita' di commenti da moderare NON cresca con la quantita' di traffico. Inoltre adesso gli argomenti non sono piu' legati al post, cosi' se volete iniziare un OT non c'e' problema come prima. Inizialmente i vostri messaggi verranno moderati, poi verrete sbloccati appena sara' chiaro che non siete troll. Una volta iscritti e' possibile postare sia attraverso il web (come prima) che via email (scegliendo di ricevere i messaggi via email). Quando vi iscrivete, per favore scrivete due righe di presentazione.Altrimenti non vi iscrivo.