La
crittografia come modifica volontaria del testo esisteva già al tempo degli
egiziani nel 1900 a.C. (tomba del faraone Knumotete II). La
parola crittografia ha origine greca e significa "nascosto". Un'altra
parola
correlata è steganografia che significa scrittura nascosta. Un esempio
legato all'antichità è di scrivere messaggi segreti non sull'argilla
che ricopriva le tavolette, ma sulle stesse tavolette che venivano
poi ricoperte d'argilla e sembravano non usate. Gli
Spartani per crittare un messaggio segreto di tipo militare usavano 2500
anni fa una striscia di papiro avvolta a spirale attorno ad un bastone (che
costituirà la chiave di decodifica). Una volta scritto il messaggio in verticale
sul papiro questo veniva consegnato al destinatario che, con un bastone
dello stesso diametro poteva leggere il messaggio in chiaro. Questo metodo
è di trasposizione perché il messaggio è in chiaro ma l'ordine delle
lettere è da scoprire. Un
altro metodo, questa volta di sostituzione, è stato inventato da Giulio Cesare:
la chiave è un numero n stabilito e si sostituisce ogni lettera del messaggio
con l'ennesima seguente. Esempio:
pippo con chiave 3 diventa snssr. Questo
metodo è facilmente attaccabile perché basta confrontare la frequenza
delle lettere nella lingua italiana con la frequenza dei simboli usati
nel messaggio cifrato. Bisogna inoltre considerare che le chiavi possibili
sono solo 26, quindi al limite con un brute force si potrebbe scovare
la chiave. Data la bassa complessità [tanto bassa non è, numero di combinazioni
possibili: 26!=4*(10^26)] del metodo usato da Cesare è chiaro che
non fosse infallibile, ma dati i risultati militari è stato efficace! Il
metodo di Cesare ha ispirato un sistema usato ancora oggi, il ROT-13 dove
la chiave è appunto 13, quindi A->N, B->O, etc. Il
metodo che usavano gli ebrei è detto ATBASH. La sostituzione avviene utilizzando
questa tabella dove le lettere della seconda riga sono scritte
in
ordine decrescente:
a
b c d e f g h i j k l m n o p q r s t u v w x y z
z
y x w v u t s r q p o n m l k j i h g f e d c b a
Messaggio:Il Libro di Geremia
Testo
Cifrato: Ro Oryil wr Tvivnrz. Lo
storico greco Polibio inventò una tecnica di codifica legando le lettere
a
una coppia di numeri che ne indicava la posizione in una tabella. La coppia
di numeri era comunicata nella notte attraverso delle torce. Ecco un
esempio
di tabella:
1 2 3 45
1
a b c de
2
f g h ij k
3
l m n op
4
q r s tu
5
v w x yz
pippo
diventa (3,5) (2,4) (3,5) (3,5) (3,4)
Se
la disposizione delle lettere nella tabella non seguono l'ordine alfabetico
si capisce la difficoltà di trovare la chiave che in questo caso è
la tabella. L'imperatore
romano Augusto usava invece un altro interessante metodo di sostituzione
usando come chiave un'altra parola o frase. La chiave e il testo
avevano un corrispettivo numerico, il testo cifrato risultava una sfilza
di numeri ottenuti come somma fra testo e chiave. Esempio (testo:
spippolatori,
chiave: decifralo):
Se
la somma (valore cifrato) eccede 21 si ricomincia dalla a; ciò equivale a
fare una somma modulo 21. La
decifrazione è una semplice sottrazione. La
criptoanalisi di questo metodo non beneficia della frequenza delle lettere
della lingua usata. Questo metodo può essere attaccato con un brute force
utilizzando un dizionario di parole. Ovviamente ci si può difendere non
usando come chiave parole di senso compiuto, ma un insieme di lettere generate
in maniera casuale. E,
se ogni volta si cambia la chiave generandola casualmente, stiamo usando un
metodo chiamato One-Time Pad, che è difficile da superare senza conoscere
la chiave e generando in maniera "davvero" casuale la chiave (e
non
è facile perché si può ottenere solo osservando fenomeni casuali naturali).
Occorre notare che non bisogna usare questo metodo per due diversi
messaggi con la stessa chiave perché la differenza tra testo cifrato
e testo in chiaro è uguale e, in unione a un bruteforce, aiuta di parecchio
la criptoanalisi di questo metodo. Infatti, trascurando il discorso
della somma modulo 21 per semplificare il discorso risulta che:
Altri
metodi usatissimi per centinaia di anni prevedevano la sostituzione
delle
singole parole con altre che costituivano la chiave. Spesso si
usavano
più metodi insieme.
Siamo
nel quindicesimo secolo quando nasce la crittografia moderna con Leon Battista
Alberti, artista rinascimentale poliedrico, amico di un funzionario
pontificio che gli chiese di inventare un metodo di crittografia.
L'idea
partì dall'osservazione che un criptoanalista può essere aiutato dalle
caratteristiche di una lingua come le frequenza delle lettere, le sillabe
impossibili o più frequenti, le sequenze di lettere caratteristiche come
le desinenze. Per rendere più difficile il lavoro del criptoanalista altro
non c'era da fare se non cambiare durante il procedimento l'alfabeto da
cui pescare la lettera cifrata: questo è il sistema polialfabetico. Altro
esempio di cifratura con il sistema del polialfabeto è quello inventato
da un tedesco contemporaneo dell'Alberti: Johannes Trithemius. Il sistema
fa uso di una tabella che si chiama tabula recta, formata da 26 righe
(tante quante le lettere dell'alfabeto inglese) riportanti ognuna un alfabeto
scalato di una posizione rispetto a quello precedente. La tabella si
usa così: la prima lettera da cifrare rimane la stessa, la seconda si cifra
con il secondo alfabeto, la terza lettera userà il terzo alfabeto e così
via fino a ricominciare dal primo alfabeto dopo la ventiseiesima lettera.
Per rendere difficile il lavoro dei criptoanalisti si può usare un alfabeto
disordinato o, meglio ancora (è più facile da ricordare e comunicare
al destinatario del messaggio) una frase chiave. L'uso
della criptografia continua intensificandosi sempre di più e migliorandosi
con il tempo fino ad avere importanza tale da cambiare il corso
della storia durante le due guerre mondiali quando appaiono le prime macchine
elettriche per cifrare i messaggi ma, soprattutto, per la criptoanalisi.
I
tedeschi usarono per tutta la seconda guerra mondiale una macchia chiamata
Enigma che avrebbe dovuto cifrare i messaggi in maniera sicura. Così
non successe, perché inglesi e polacchi unendo le loro forze furono in grado
di decifrare quasi tutti i messaggi intercettati. L'Enigma
era una macchina elettromeccanica con contatti, lampadine, rotori e
una tastiera. Ogni lettera veniva cifrata con un alfabeto diverso dando luogo
ad un numero sproposito di combinazioni che rendevano la decodifica teoricamente
impossibile per l'epoca. Ma ciò non fermò gli inglesi che trassero
grande beneficio dai messaggi decodificati. Per
anni la regola generale è stata di creare algoritmi semplici e di impiegare
chiave molto lunghe per rendere difficile la vita al criptoanalista.
Oggi l'orientamento è opposto data la potenza di calcolo di cui
si può disporre per fare un bruteforce, quindi si creano algoritmi complicatissimi
da decifrare in modo che anche se il nostro avversario avesse
parecchio materiale su cui condurre un'analisi, gli sarebbe pressoché
inutile. Oggi
la crittografia serve per il commercio elettronico, l'autenticazione, la
riservatezza delle informazioni, etc. Uno dei presupposti fondamentali è
che
si suppone che il criptoanalista di turno conosca in generale il nostro metodo
di crittografia, questo perché è davvero un disastro cambiare ogni volta
metodo di crittografia ogni qual volta si ha il sospetto che qualcuno sia
riuscito a infrangerlo. Da questo presupposto segue che i metodi si basano
sulle chiavi di codifica e decodifica. Se
la chiave è la stessa sia per la codifica che per la decodifica ricadiamo
nel caso delle crittografia classica: questi sono i metodi a chiave
simmetrica o segreta. Gli algoritmi a chiave asimmetrica o pubblica che
(risalgono agli anni '70) utilizzano coppie di chiavi complementari. Una
delle due chiavi è pubblica e conosciuta da tutti e serve per cifrare i messaggi,
mentre l'altra è segreta e riservata al destinatario dei messaggi che
la utilizzerà per decifrarli. Le chiavi vanno a coppie e quindi solo una
chiave può decifrare il messaggio generato utilizzando la chiave a lei complementare.
In questo modo possiamo trasmettere tranquillamente la nostra
chiave pubblica senza paura che venga intercettata. Spesso
ci si orienta per metodi ibridi simmetrici-asimmetrici (come succede nel
famoso PGP) perchè il solo metodo asimmetrico non è efficiente (è
lento!)
per grandi moli di dati e, se dovessimo inviare lo stesso messaggio a
più persone, dovremmo cifrarlo ogni volta con la giusta chiave. PGP
(Pretty Good Privacy) è un pacchetto freeware (http://www.pgpi.com) che realizza
la crittografia a chiave pubblica; permette l'interscambio di documenti
elettronici realizzando segretezza, autenticità, integrità dei dati
su un canale insicuro. PGP è principalmente pensato per lo scambio di documenti
via Internet, ma può essere usato su un qualsiasi canale insicuro;
è indubbiamente un prodotto di qualità, e non c'è da dubitare dell'integrità
morale del suo autore (che potrebbe come sempre aver lasciato
delle trap-door), Philip Zimmerman. Egli infatti lo ha sviluppato con
il chiaro intento di permettere la privacy nell'interscambio di posta elettronica
su Internet, con un approccio fortemente critico verso la politica
di NSA e del Congresso Americano di progettare un monopolio dei sistemi
di crittografia; P. Zimmerman è stato sotto inchiesta per due anni e
mezzo, accusato di esportazione non autorizzata di materiale crittografico,
ed è recente la notizia che le autorità federali statunitensi
hanno deciso di non perseguirlo penalmente. Standard
federale ancora oggi ufficiale (nella versione triplo-des) per gli USA,
è nato nel 1977 per implementazioni per lo più hardware come derivazione
di Lucifer, un algoritmo di IBM nato nel '70, su insistenza del National
Bureau of Standard per difendere dati riservati ma non segreti militari.
Il
DES brevettato nel 1976 da IBM è royalty-free dal 1993. Il
DES è un codice cifrato a blocchi (si dice che un codice è cifrato a blocchi
quando si applica un codice cifrato a un bit, byte, parola o gruppi di
parole alla volta). Il blocco che si usa per crittografare è di 64 bits (8
sottoblocchi da 8 bits). Dato che l'ultimo bit di ogni sottoblocco è di controllo,
i bit utili sono 56. Per
cifrare il testo si divide in blocchi da 64 bits che sono cifrati in successione.
Se un messaggio non riempie i 64 bits si può completare in diversi
modi: si possono aggiungere zeri, si possono aggiungere bit random specificando
nell'ultimo quanti se ne aggiungono, etc. Il
DES è molto usato in ambito commerciale perché nonostante consti di numerosi
passaggi, questi sono tutti relativamenti semplici come XOR, sostituzioni
e permutazioni. Occorre
ricordare che il DES cambia solo la chiave; questo porta vantaggi economici
immediati, ma appena verrà scoperto il modo per forzarlo (senza bruteforce)
occorrerà cambiare radicalmente tutto. Un altro difetto fondamentale
è lo spazio limitato delle chiavi pari a 2^56. Per ovviare al problema
si tenta di allungare le chiavi o di applicare più volte il DES (triplo-DES
o TDES). Il
progetto originale dell' IMB per il DES prevedeva una chiave più lunga dei
56 bits usati di default. Probabilmente il progetto originario fu influenzato
dall'NSA che impose all'IBM una chiave sicura, ma comunque alla portata
dei loro potenti mezzi. Nel
gennaio 1998 la RSA Laboratories lanciò il "DES challenge II" coordinato
e risolto da distributed.net in 39 days. Record
presto battuto, nel 17 luglio 1998. L'EFF,
Electronic Frontier Foundation's, costruì una macchina (DES Cracker macchine)
per distruggere il DES e ha scritto un libro (maggio 1998) dove è spiegato
nei minimi dettagli come si è proceduto. La
macchina del costo di 210.000 $ (80.000 per lo sviluppo e il rimanente per
i materiali impiegati, il software è stato scritto da volontari in 2 settimane)
forza un DES-56 bits in meno di 3 giorni. Il progetto è stato completato
in 18 mesi. Hanno
così dimostrato ai loro "stolti" (così li definiscono nel libro)
governanti
che il DES può essere forzato con una macchina dedicata. Qualche giorno
prima un funzionario del dipartimento di giustizia, Robert Litt, si affannava
a dire che non era possibile che l'FBI possesse macchine per craccare
il DES. 6
mesi dopo, 19/01/1999, Distributed.Net lavorando con un network mondiale in
Internet di 100.000 pc e con il DES Cracker della EFF, vinse l'RSA Data Security's
DES Challenge III con il tempo record di 22 ore e 15 minuti! Dal
novembre 1998 il DES non è più l'algoritmo standard federale; è sostituito
dal triplo-DES finchè il nuovo AES non sarà pronto. IDEA,
International Data Encryption Algorithm Creato
nel 1991 da Xuejja Lai e James L. Massey, è, come il DES, codice cifrato
a blocchi di 64 bits con chiave, però, di 128 bits. Anche IDEA usa calcoli
semplici basati su operazioni (addizioni e moltiplicazioni) modulari,
scambi e concatenamenti. Le sottochiavi usate nel procedimento sono
tutte diversi e a 16 bits. Con
questo tipo di crittografia è stato risolto il problema della gestione delle
chiavi che non occorre più trasmettere al destinatario del messaggio per
la decodifica. Il concetto di crittografia simmetrica è stato introdotto
nel 1976 da Whitfield Diffie e Martin Hellman e si basa sul concetto
fondamentale che un messaggio codificato con una precisa chiave pubblica
può essere decodificato SOLO dalla corrispondente chiave privata che
è unica ed associata strettamente a quella pubblica; ciò si basa anche su
un dato matematico per cui, impiegando 1024 bits, per ottenere la (unica)
chiave segreta da quella pubblica occorrerebbe una potenza di calcolo
pari a una rete di milioni di computer al lavoro per 1000 anni! Gli
algoritmi a chiave pubblica, per la loro lentezza, sono usati spesso per
cifrare la chiave di sessione con cui verrà codificato il messaggio usando
la crittografia simmetrica. Nel
1976 due crittologi americani, Diffie ed Hellmann, pubblicarono un fondamentale
lavoro teorico nel quale, ipotizzando di poter disporre di un cifrario
"asimmetrico", dimostravano la fattibilità di sistemi crittografici
di nuovo tipo, adatti alla crittografia di massa mediante il concetto
delle "chiavi pubbliche". Questo
algoritmo è stato sotto brevetto fino al 29/4/97. Basa la sua difficoltà
di decodifica sui problemi logaritmici. E' considerato sicuro con
chiavi lunghe e generatori adatti. Nato
a due anni dal Diffie-Hellman (e brevettato il 29/9/1983 , scadenza nel
2000 in USA, libero nel resto del mondo), questo algoritmo è ancora oggi
molto usato (dato in licensa a 350 compagnie, conta un numero di motori
di codifica installati pari a circa 300 milioni). L'acronimo individua
le iniziali degli inventori, i tre ricercatori del MIT Ron Rivest,
Adi Shamir e Leonard Adleman. La sua potenza si basa sull'estrema difficoltà
di ricreare la chiave segreta da quella pubblica basandosi su funzioni
unidirezioni e quindi invertibili ma tali che la funzione diretta sia
banale, ma quella inversa sia estremamente difficoltosa. Ecco un esempio
che dovrebbe chiarire e che è appunto l'idea su cui si basa l'RSA: è
facilissimo trovare il prodotto di due numeri molto grandi, ma dato il prodotto
sarà estremamente difficoltoso trovarne i 2 fattori primi. Illustriamo
i passaggi e l'esempio (che sarà fatto con numeri piccoli per non
complicare):
1)
Prendiamo due numeri primi p(=3) e q(=11) molto grandi ed n(=33) sia il
loro
prodotto.
2)
Prendiamo e(=3) che deve essere: minore di n, dispari e primo con
(p-1)(q-1).
[ (p-1)(q-1)=(3-1)(11-1)=2*10=20 ]
3)
Calcolare d(=7) in modo che: d*e=1 MODULO (p-1)(q-1). Significa che d*e
diviso
(divisione intera) (p-1)(q-1) dà come risultato 1. Infatti
d*e=3*7=21/20=1.
4)
Cifriamo il testo con c=(t^e) MODULO p*q.
t,
intero positivo, è il testo in chiaro. il risultato c è il testo
cifrato.
La
chiave pubblica conterrà n ed e(esponente pubblico), quella privata n e d(esponente
privato). Se
t sono i numeri da 0 ad 8, li cifreremo elevandoli alla terza e facendo il
risultato modulo 33.
La
chiave per l'RSA è il modulo n. Più è grande la chiave, più sarà sicura
(ma
lenta) la cifratura. Con 1024 bits si è abbastanza (molto?) sicuri. Per
craccare un RSA a 256 bits basta un potente home computer; andando a 384
bits servirebbe un'organizzazione universitaria o una grande azienda; la
crittografia a 512 bits può essere superata da agenzie statali. Solo chiavi
a 2048 bits possono ritenersi sicure per qualche anno a ogni livello (e
chissà...). Se
volessimo usare un sistema ibrido si potrebbero usare RSA e DES. Con il DES
produciamo una chiave casuale (che cifreremo con l'RSA) che servirà per crittare
il messaggio in maniera simmetrica. Spedisco poi il messaggio e la chiave
DES cifrata con la chiave pubblica RSA al suo proprietario che con la
sua chiave segreta decritterà prima la chiave che impiegherà per decodificare
il messaggio. Questo
si fa perché DES è da due (a livello software) a 4/5 ordini (a livello
hardware) di grandezza più veloce dell'RSA. Nel
marzo 1994, usando 1600 computer connessi a Internet, Atkins e altri fattorizzarono
un numero di 129 cifre (426 bits) in 8 mesi di lavoro. Una
studio del 1997 stimava in un milione di dollari il costo per forzare un
RSA con chiave a 512 bits. Curiosità:
il numero di numeri primi minori o uguali a n è asintotico a n/ln
n. Quindi il numero di numeri primi di lunghezza minore o uguale a 512 bits
è di circa 10^150, cioè più grande del numero degli atomi dell'universo
conosciuto. Questo la dice lunga sull'enorme disponibilità di chiavi
diverse. Notizia
del marzo 1999 apparsa sul mensile Crypto-Gram: è stato fattorizzato
un RSA-140. Un nuovo record è stato stabilito da Herman Riele e
il suo gruppo ad Amsterdam avendo fattorizzato un numero di 140 cifre (456
bit). Questo numero è stato una delle sfide dell'RSA, era il prodotto di
due numeri primi molto grandi, proprio il tipo di numeri usati nel criptosistema
RSA. La
mole di lavoro è stata stimata in 2000 anni-mips (mips=milioni di istruzioni
al secondo, un anno-mips corrisponde alla potenza di calcolo di una
macchina che macina per un anno un milione di istruzioni al secondo. Un DEC
11/780 è una macchina mips. Un Pentium II di fascia alta è una macchina
da
200 mips. Il supercomputer per simulare esplosioni nucleari installato al
Sandia National Laboratory è una macchina da 1.8 milioni di mips). Per
l'impresa è stato usato un algoritmo detto "a setaccio di numeri", lo
stesso
usato per fattorizzare un RSA-130 impiegherebbe 1000 mips-anni, per un
RSA-150 1500 mips-anni. L'algoritmo non scala come ci si aspetterebbe, ma
le tecniche di fattorizzazione diventano sempre più efficienti e veloci perché
i computer diventano sempre più veloci, le macchine possono lavorare in
rete, gli algoritmi migliorano continuamente di pari passo alle ricerche di
matematica. E'
stato già avviato un progetto per fattorizzare un RSA-155 (512 bit) che sarà
pronto per fine 1999. Sono
stati un pò più veloci della fine d'anno promessa e così è il 22 agosto
quando il solito Herman Riele annuncia l'impresa compiuta ad Amsterdam
su un numero da 155 cifre (512 bit) del tipo degli stessi usati per
l'RSA in quanto prodotto di due fattori primi da 78 cifre. 300 macchine tra
workstation SGI e PC Pentium hanno lavorato alacremente per sette mesi durante
la notte e i weekend. Usando il solito algoritmo a setaccio si sono impiegati
8000 anni-mips in 3.7 mesi per la fase cosiddetta "di setaccio" e
224
ore-CPU e 3.2 Gigabytes di memoria per la seconda fase di riduzione matriciale
su un Cray C916. Lo
sforzo è stato 50 volte più facile che craccare il DES. Fattorizzare le
chiavi
usate per il commercio elettronico è sempre più facile e lo sarà ancor
di più in futuro. Questa impresa deve mettere in allarme perchè la maggior
parte dei protocolli sicuri usati in Internet usano RSA a 512 bits. Grosse
e medie società come Compaq e Microsoft usano ancora per i loro magazzini
on-line l'RSA a 512 bit. Occorre inoltre riflettere sul fatto che è
probabile che qualche organizzazione in segreto già forzi abitualmente comunicazioni
private e/o segrete. All'Eurocrypt
'99, Adi Shamir (la S dell'acronimo RSA) presenta l'idea per una
macchina che potrebbe incrementare la velocità di fattorizzazione attuale
di 100-1000 volte. Chiamata TWINKLE (The Weizmann INstitute Key Locating
Engine), fattorizza chiavi di 512 bits. La
macchina opera essenziamente in due passi: il primo fa da setaccio e attua
una massiccia ricerca parallela di equazioni con una certa relazione. Appena
un certo numero di relazioni è trovato, c'è una massiccia operazione matriciale
per risolvere un'equazione lineare e produrre i fattori primi. Shamir
ha teorizzato l'uso di tecniche elettro-ottiche per la prima fase di setaccio,
idea peraltro non nuova perchè si rifà a quella di D.H. Lehmer che
pensò nel 1930 di usare tecniche meccanico-ottiche. La macchina sembra non
sia ancora stata costruita.E' da
notare che questa nuova macchina non risolve
il problema di prestazione del secondo passaggio che riguarda operazioni
sulla matrici. La complessità del secondo passaggio esplode nella
fattorizzazione di numeri enormi: con un numero a 1024 bit, per esempio,
il secondo passaggio richiederebbe 10 terabytes di memoria (non di memoria
di immagazzinamento ma di vera memoria per il computer). Questa
macchina non introduce nessun concetto matematico innovativo, ma semplicemente
esegue operazioni già conosciute più velocemente. L'idea
è semplice: così come si entra in Hotmail e si spediscono e ricevono messaggi,
allo stesso modo lo si può fare, utilizzando però email criptate senza
dover scaricare nessun software.
HushMail
http://www.hushmail.com, basato su PGP e S/MIME-like, sfrutta java.Il mittente entra in HushMail e, attraverso un'applet java, può
mandare
un'email criptata. Anche il destinatario deve avere un account su HushMail.
Gli account possono essere anonimi. Gli algoritmi sono ElGamal a 1024
bit e Blowfish. La chiave privata personale è immagazzinata sul server di
HushMail e l'unica cosa che la protegge da accessi più o meno illegali al
server è una passphrase. L'altra debolezza è costituita dall'applet java
che
non si può mai sapere se è quella corretta o un cavallo di Troia. Anche
certificando
l'applet ci sarebbero dei problemi. L'ultimo problema è legato alla
collocazione fisica del server, che nonstante la compagnia che lo gestisce
sia di Antigua, è collocato in Canada, che notoriamente è molto più
suscettibile ad azioni legali. Nonostante
tutto HushMail sembra una ragionevole implementazione dell'idea.
Esistono
altri servizi come http://www.ziplip.com, http://www.ynnmail.com,
http://www.zixmail.com
che sono molto meno sicuri fornendo una protezione davvero
blanda e facilmente attaccabile.
Insomma,
le email web-based criptate sono più sicure di una email non criptata,
ma meno sicure di una email criptata con PGP per molti motivi: i server
sono obiettivi di attacchi, le connessioni anche se SSL non sono immuni da
spoofing.
Apparso sul n°
10 di NetRunners, la e-zine
degli Spippolatori
