Titolo

La guerra alla crittografia - alcune questioni tecniche

8 commenti (espandi tutti)

Buongiorno, Ho letto l'articolo, e direi che c'è parecchio da eccepire anche dal punto di vista tecnico, contrariamente a quanto reputa la redazione di NfA. Probabilmente ciò che segue potranno sembrare dettagli di poco conto. D'altro canto, credo che se non si divulgano bene i principi alla base di una disciplina scientifica, inevitabilmente si finisce per distorcere il dibattito etico che deriva dalle sue applicazioni e dal suo impatto nel mondo reale (e se al posto di "crittografia" sostituiamo "economia", penso che la maggior parte dei frequentatori e autori di questo blog si troverà d'accordo).

Andando per punti:

- Punto 2: «[La crittografia simmetrica] Si basa su algoritmi di sostituzione progressiva che sono tanto complessi quanto più è complessa la chiave».

Sebbene esistano algoritmi di cifratura che rendono vera questa affermazione, il principio non vale in generale: la complessità di un algoritmo di cifratura (intesa come numero di operazioni per trasformare il messaggio in chiaro in messaggio cifrato) e la complessità della chiave (intesa come lunghezza) sono parametri non strettamente collegati tra loro. Per fare un esempio, l'algoritmo di cifratura Rijndael che è stato adottato come standard AES segue questo principio. In particolare, il numero di operazioni per cifrare un singolo messaggio dipende dal numero di round adottati, che a loro volta in Rijndael dipendono dalla lunghezza della chiave, come di seguito:

#chiave #round

128 bit 10

192 bit 12

256 bit 14

D'altronde, come si può leggere in [2], la decisione di aggiungere 1 round ogni 32 bit aggiuntivi di chiave è un margine precauzionale, ma non ha una giustificazione completamente rigorosa. Infatti, allo stato attuale delle nostre conoscenze si conoscono attacchi pratici per rompere AES solo con un numero di round minore di quelli citati sopra. È inoltre interessante notare che in uno degli attacchi più recenti [1] viene dimostrato che AES con chiavi lunghe 256 bit e 11 round consente un attacco (non attuabile in pratica, va precisato) che invece non può essere applicato su AES con chiavi a 128 bit e 10 round. Questo per evidenziare che l'intuizione

"Chiavi più lunghe/complesse -> Maggior numero di operazioni di cifratura -> Maggior sicurezza"

non è vera in generale. Oltre a ciò, come menzionavo in precedenza, esistono poi algoritmi di cifratura simmetrica in cui il numero di round è fisso e indipendente dalla lunghezza della chiave. Per esempio Twofish [5], anch'esso finalista alla competizione di AES, usa sempre 16 round di cifratura.

- Punto 2: «Il sistema a chiave pubblica è molto ingegnoso ed affascinante perché si basa su moltiplicazioni di numeri primi molto grandi e su concetti anarchici di "web of trust"».

Trascurando la connotazione politica data al web of trust (che è completamente gratuita), i sistemi di cifratura a chiave pubblica non si basano solo su moltiplicazioni di numeri primi. È vero che RSA è uno degli algoritmi a chiave pubblica più diffusi e utilizzati in Internet e sfrutta esattamente questo principio, ma esistono una pletora di altri sistemi basati su assunzioni matematiche diverse. Per esempio, il primo protocollo per lo scambio delle chiavi ideato da Diffie e Hellman [3], che gli è valso il premio Turing di quest'anno, si basa sul logaritmo discreto. Tra l'altro, questo paper viene considerato come quello che ha dato inizio alla ricerca sulla crittografia a chiave pubblica, ed è del 1976. Quindi anche l'affermazione secondo cui «la crittografia a chiave pubblica [...] è stata inventata negli anni 60» è inesatta dal punto di vista storico. Inoltre, il concetto di "Web of Trust" è una conseguenza applicativa della crittografia a chiave pubblica, non uno dei principi su cui essa si basa.

- Punto 3: «La password, invece, dovrebbe essere salvata crittata, con un algoritmo così detto di "hashing". L'hashing è quella che in inglese si chiama trapdoor function, cioé una funzione matematica asimettrica che permette di andare facilmente da A -> B ma molto difficilmente da B -> A.»

Qui l'autore confonde due concetti matematici differenti. Una funzione di hash non è una trapdoor, ma è una funzione che associa un insieme di messaggi di lunghezza arbitraria ad un insieme di messaggi di lunghezza fissa (detti, appunto, gli hash). Considerando il significato di hash in inglese ("polpettone"), una funzione di hash può essere vista metaforicamente come un'operazione che "tritura" o "sminuzza" un messaggio di partenza per ottenere come risultato un'"impronta" più piccola (fingerprint), che sia in qualche modo rappresentativa del messaggio di partenza. Dato che l'insieme di tutti i possibili hash di lunghezza fissa è più piccolo dell'insieme di tutti i possibili messaggi di lunghezza arbitraria, vorrà dire che più messaggi avranno associato lo stesso hash (principio della piccionaia: se rappresentiamo l'insieme dei possibili hash come una piccionaia con m feritoie e l'insieme di messaggi con n piccioni, dove n>m, inevitabilmente almeno due piccioni dovranno condividere la stessa feritoia). Ciò vuol dire che una funzione di hash non è in generale invertibile, ovvero partendo da un hash non è possibile risalire al messaggio originale che l'ha prodotto. Nella pratica, può darsi il caso in cui una funzione di hash sia invertibile per alcuni valori di hash. Per questo motivo, in crittografia si cerca di utilizzare funzioni di hash che siano "One-way", ovvero come dice l'autore dell'articolo facili da calcolare ma difficili da invertire.

Una funzione trapdoor, d'altro canto, è una funzione one-way che è possibile invertire facilmente disponendo di un'informazione aggiuntiva detta trapdoor, o botola, mentre rimane difficile da invertire se non si conosce la trapdoor. Per fare un esempio, nel linguaggio della crittografia a chiave pubblica la trapdoor è la chiave privata con cui si decifra il messaggio. La cosa importante da osservare è che una funzione trapdoor deve essere una permutazione, cioè ad ogni valore di output della funzione deve corrispondendere uno e un solo valore di input. Ciò è necessario per garantire un'invertibilità univoca, e corrisponde al caso della piccionaia in cui abbiamo n piccioni ed n feritoie.

Per riassumere, sia le funzioni di hash sia le funzioni trapdoor sono entrambi esempi di funzioni one-way, ma non sono la stessa cosa: le prime associano qualcosa di più grande a qualcosa di più piccolo (e dovrebbero essere per esempio usate, come scritto giustamente dall'autore, per cifrare le password nei database dei siti web), mentre le seconde associano un oggetto A di una certa dimensione ad un oggetto B della medesima dimensione, con l'obiettivo di recuperare A partendo da B disponendo di una chiave segreta.

- Punti 4 e 5: non credo di aver capito cosa intenda l'autore per "unicità" di una chiave/password, e soprattutto quale sia la sua relazione con l'entropia della stessa e con la facilità di attuare un attacco a forza bruta. Se una chiave ha entropia bassa, allora si possono adottare delle strategie come attacchi basati su dizionario per indovinarla. Ma questi non sono attacchi a forza bruta: per definizione, negli attacchi a forza bruta si provano tutte le possibili combinazioni di una chiave indipendentemente dal fatto che essa possegga una struttura/regolarità o meno.

- Punto 5: «Qui giace un concetto della crittografia molto importante da capire: indovinare una password con brute force non è MAI matematicamente impossibile. È però matematicamente inattuabile.»

No, esiste un particolare algoritmo di cifratura per cui l'attacco a forza bruta è anche impossibile dal punto di vista matematico, ed è la one-time pad [6]. La proprietà di "sicurezza perfetta" di questo algoritmo deriva dal fatto che si utilizza una chiave lunga almeno quanto il messaggio che si vuole cifrare. Se questa chiave è scelta in modo casuale (più tecnicamente, scelta con probabilità uniforme) e viene utilizzata solo una volta, allora un attaccante si ritroverà nella situazione in cui il messaggio cifrato può corrispondere a qualsiasi messaggio in chiaro, e quindi anche passandosi per forza bruta tutte le possibili chiavi non potrà mai sapere qual è il messaggio originale (proprio perché ogni possibile messaggio originale è ugualmente probabile). Ovviamente, questo algoritmo è poco pratico per la lunghezza delle chiavi, anche se trova applicazioni limitate in alcuni algoritmi di crittografia quantistica.

- Punto 5: la parte sui limiti fisici degli attacchi a forza bruta basati sul principio di Landauer è molto interessante e suggestiva, però quando si prendono idee/stralci di testo da altri autori (nel caso specifico, l'"Applied Cryptography" di Bruce Schneier [4]), occorrerebbe citare le fonti.

Per quanto riguarda i punti rimanenti (6-7-8), mi trovo sostanzialmente d'accordo con l'autore, ma l'argomentazione portata a supporto è abbastanza limitata e sproporzionata rispetto alla parte tecnica introduttiva, e andrebbe elaborata meglio. Dato che al momento ho già eretto un wall-of-text sulla parte tecnica (mi scuso per la prolissità), cercherò di tornare sulla parte etica/politica con un altro intervento.

 

Bibliografia

[1] A. Biryukov, O. Dunkelman, N. Keller, D. Khovratovich, A. Shamir: Key Recovery Attacks of Practical Complexity on AES-256 Variants with up to 10 Rounds. In: EUROCRYPT 2010. LNCS, vol. 6110, pp. 299-319. Springer (2010)

[2] J. Daemen, V. Rijmen. The Design of Rijndael. Springer (2002)

[3] W. Diffie, M. Hellman. New directions in cryptography. IEEE Trans. Information Theory 22(6): 644-654 (1976)

[4] B. Schneier. Applied Cryptography. John Wiley & Sons (2007)

[5] B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall, N. Ferguson. Twofish: A 128-Bit Block Cipher. https://www.schneier.com/cryptography/paperfiles/paper-twofish-paper.pdf

[6] C. Shannon. Communication Theory of Secrecy Systems. Bell Syst. Tech. J. 28 (4): 656–715 (1949)

 

EDIT: formattazione

Scusa Luca, non so se ti rendi conto dello scopo dell'articolo e del pubblico a cui e' indirizzato. Probabilmente no, perche' altrimenti non avresti impiegato tutto questo tempo a precisare che questo capello non vale in questa eccezione e questo in quest'altra. Lo scopo dell'articolo e' dare un'infarinatura profonda abbastanza da capire le valenze socio-politiche, non di discutere le alternative a AES o cosa e' un raibow table.

Giorgio, grazie per la risposta.

Ho capito benissimo lo scopo dell'articolo e il pubblico a cui è rivolto. Proprio per questo motivo, a me sembra che hai dato un'introduzione tecnica all'argomento eccessivamente sbilanciata, rispetto alla parte socio-politica. L'intera questione "privacy/sicurezza" può essere divulgata senza scendere troppo nei dettagli, e anzi dovrebbe essere divulgata in questo modo proprio per permettere una partecipazione anche ai non addetti ai lavori.

Premesso quanto sopra:

- A che pro menzionare la questione dei numeri primi, quando la crittografia a chiave pubblica può essere spiegata astraendo completamente dal substrato matematico, con ottimi esempi pedagogici (vedi il libro di Simon Singh "Codici e Segreti", dove viene spiegata in termini di chiavi e lucchetti)?

- Critichi la mia tendenza a scadere in tecnicismi che sono oscuri al pubblico generico. La cosa probabilmente è anche vera (vedere punto successivo), però mi viene da domandarti: credi che quella tirata sul principio di Landauer, sfere di Dyson, ecc. siano argomentazioni apprezzabili dal pubblico generico? Non sono tecnicismi inutili anch'essi, che potevano essere riassunti in modo molto più sintetico, senza tirare in ballo necessariamente la termodinamica? Noto peraltro che hai glissato completamente sulla mia osservazione che hai riproposto in modo non originale un'argomentazione di un altro autore senza dargli credito. Allo stesso modo, è davvero necessario mettersi a parlare di entropia di una password, senza dare una chiara idea di cosa si tratti?

- Come ho già detto in conclusione del mio precedente commento, mi scuso per la prolissità e la pignoleria del mio intervento. Il problema divulgativo del tuo articolo, per come la vedo io, si può considerare in due modi:

a) O si tiene la parte tecnica al livello più superficiale possibile, e si fa uno sforzo di comunicare i principi alla base della crittografia (senza tirare in ballo entropia, termodinamica, ecc.), concentrandosi di più sulla parte socio-politica che è inevitabilmente più interessante per il pubblico di questo blog;

b) Oppure, se si vuole entrare maggiormente nei dettagli tecnici, lo si fa correttamente evitando di scrivere inesattezze come hai fatto tu in questo articolo, e su cui tra l'altro non hai speso una parola per rispondere a un singolo punto di quelli che ho sollevato. Noto tra l'altro che tipicamente occorre versare molto più inchiostro per correggere un'inesattezza che non a scriverla. Ciò spiega, almeno in parte, il fatto che il mio intervento è stato molto lungo: dire le cose esattamente come stanno è già un lavoro tedioso e lungo di per sé. Se poi bisogna anche correggere errori, il lavoro si allunga ulteriormente perché occorre argomentare con esempi, controesempi ecc. Poi, sicuramente, gioca una parte rilevante anche la mia pignoleria personale :)

Luca, non esiste una ricetta unica per scrivere un articolo divulgativo. Ognuno ha il proprio stile. Il mio stile e' quello di dare una infarinatura tecnica comprensibile ai piu', facendo un compromesso tra semplificazioni e onesta' intellettuale e poi, si' spiegare, ma soprattutto instaurare un grado di fascinazione verso l'argomento che promuova una ricerca spontanea nel lettore: se al 10% di chi legge e' venuta la curiosita' di googlare cos'e' una sfera di dyson o una trapdoor function o come i numeri primi sono coinvolti con crittografia, io ho raggiunto un buon obiettivo. A me premeva far capire che ci sono tre strategie per decrittare un messaggio e che maths is not the weakest ring in the chain. Se a te il mio stile non piace, me ne faro' una ragione.

Non ti ho risposto punto per punto perche' francamente non ne vedo la necessita'. Cosa vuoi che ti dica? Che si' e' vero che ci sono algoritmi meno noti di RSA che non si basano su numeri primi? O forse dobbiamo metterci a fare una discussione su hybrid attacks e l'intersezione tra dictionary attacks, brute force and rainbow table? 

Evidentemente abbiamo approcci alla divulgazione differenti. Ciononostante, rimango dell'idea che se si vuole dare un'infarinatura tecnica ad un qualsiasi argomento scientifico, va bene sì semplificare ed affascinare il pubblico, ma senza scadere in errori marchiani. Francamente, non so che idea possa farsi una persona di quel 10% che googlando "trapdoor function" legge che in realtà si tratta di una cosa diversa da quella che hai scritto tu. Nella migliore delle ipotesi, secondo me, resterà confuso. Nella peggiore, penserà di avere capito qualcosa, e probabilmente sarà anche la cosa sbagliata. Poi magari sono io che sottovaluto la maturità intellettuale del layman.

Notare inoltre che per falsificare la mia affermazione "non hai risposto a un singolo punto di quelli che ho sollevato" non è necessario rispondermi punto per punto, ma ne basta uno. In particolare, mi accontenterei se potessi rispondere almeno a queste tre domande sparse nel mio primo intervento:

- Quale pensi che sia la relazione tra web of trust e crittografia a chiave pubblica?

- Cosa intendi per "unicità" di una chiave/password?

- Dove ti sei documentato per la parte sui limiti termodinamici degli attacchi brute-force?

A scanso di equivoci, non sto insinuando alcuna disonestà intellettuale da parte tua, specialmente riguardo la terza domanda, su cui magari avevo dubbi appena letto l'articolo. Il fatto però che non mi hai risposto a riguardo mi fa pensare che effettivamente tu non conoscessi la provenienza di quell'argomentazione, e si tratta a questo punto di una curiosità personale.

- Quale pensi che sia la relazione tra web of trust e crittografia a chiave pubblica?

Come sarebbe "quale penso?". Web of Trust e' necessario per associare identita' reali a chiavi pubbliche in alternative a CAs. 

- Cosa intendi per "unicità" di una chiave/password?

intendo dictionary attacks e password reuse, come ho gia' scritto.

- Dove ti sei documentato per la parte sui limiti termodinamici degli attacchi brute-force?

Se vuoi sapere da dove vengono i numeri sono da "Applied Cryptography: Protocols, Algorithms, and Source Code in C" di Bruce Schneier. pg 157

«Come sarebbe "quale penso?". Web of Trust e' necessario per associare identita' reali a chiavi pubbliche in alternative a CAs. »

E per associare l'identità reale di A alla sua chiave pubblica ciò che si fa nel WoT è firmare con la chiave privata di qualche altro utente la chiave pubblica di A, in modo completamente decentralizzato. Quindi per realizzare il WoT occorre impiegare gli strumenti della crittografia a chiave pubblica, e non il contrario come invece si evince dal tuo articolo. Curioso tra l'altro che hai perfino citato il WoT, dato che è stato un flop totale e in pratica nel mondo reale si utilizzano le public key infrastructures per risolvere il problema di autenticazione delle chiavi, ovvero l'alternativa tramite CA che hai menzionato nel tuo commento precedente. Voglio dire, la cosa è curiosa considerando il fatto che come esempio di crittosistema a chiave pubblica hai alluso a RSA e ai numeri primi (che, come ha osservato anche agori nel commento sotto, è quello che "va per la maggiore"), mentre per il problema dell'autenticazione hai citato una soluzione di nicchia che quasi nessuno utilizza, almeno non in ambito industriale. Mi pare di capire che la tua visione sia abbastanza distorta verso le soluzioni proposte nell'ambito del free/open source software, e quindi non è molto rappresentativa dello stato dell'arte.

«intendo dictionary attacks e password reuse, come ho gia' scritto.»

Che non vuol dire assolutamente nulla, almeno cercando di collegare la tua risposta con quanto hai scritto nell'articolo. Cito:

«Ovviamente brute forcing dipende largamente dall'entropia della password ma anche dalla sua unicità. Una password ad entropia molto alta ma poco unica, è comunque abbastanza facile da indovinare»

Mi spieghi in che modo una password che viene riutilizzata da un utente in altri servizi, ma con un'entropia alta, sarebbe più facile da indovinare? Viceversa, se parliamo di dictionary attacks, allora non stiamo parlando di brute forcing, visto che per definizione si vanno a tentare tutte le password più probabili contenute in un determinato dizionario, e non tutte le password possibili indistintamente.

Un'ultima precisazione relativa alla tua discussione con Giovanni Federico: non mi risulta che i terroristi di Parigi abbiano usato ROT-13 per comunicare tra di loro, ma solo messaggi in chiaro. Probabilmente hai equivocato da questo articolo, il cui titolo era sarcastico:

Paris Terrorists Used Double ROT-13 Encryption

E' vero che la spiegazione tecnica non ha soddisfatto neppure me completamente, tuttavia le precisazioni che hai fatto sono completamente fuori luogo per l'audience dell'articolo. Ad esempio vai a fare il pignolo sull'implementazione del sistema a chiave pubblica. Ma dai, visto che ammetti che RSA va per la maggiore ci sta che si parli di numeri primi e moltiplicazioni. Invece ho trovato che spesso l'articolo sia infarcito di inutili dettagli tecnici, che poi tanto per ovvi motivi restano incomprensibili (a meno che non conosci gia' l'argomento).