Calcolare la complessità di un algoritmo
L'elemento principale per valutare la resistenza di un algoritmo di crittografia all'analisi crittografica è il tempo necessario per svolgere l'attacco. In generale non si può essere certi di aver trovat l'algoritmo di attacco più efficiente. Tutt'al più si può dire che, per un determinato algoritmo, il livello di impegno per un attacco è di un determinato ordine di grandezza. Quindi si può confrontare tale ordine di grandezza con la velocità dei microprocessori disponibili, per determinare il livello di sicurezza di un dato algoritmo.
Una misura comune dell'efficienza di un algoritmo è la sua complessità temporale. Si definisce complessità temporale di un algoritmo la funzione f(n) tale che, per tutti gli input di lunghezza n, l'esecuzione dell'algoritmo richiede al più f(n) passi. Pertanto, per determinate dimensioni di input e determinate velocità del microporcessore, la complessità temporale è un limite superiore del tempo di esecuzione.
La definizione contiene numerose ambiguità. Innanzitutto, la definizione di passo non è precisa. Un passo potrebbe essere un'unica operaazione di una macchina di Turning, un'istruzione del microprocessore, un'istruzione in un linguaggio di alto livello e così via. Tuttavia, queste differenti definizioni di "passo" dovrebbero essere tutte correlate con semplici costanti moltiplicative. Per valore molto estesi di n, queste costanti non sono importanti. Ciò che è importante è la velocità con cui il tempo di esecuzione relative cresce. Per esempio se ci si chjiede se il problema di utilizzare chiavi a 50 cifre (n=10 alla 50) o a 100 cifre (n= 10 alla 100) per RSA, non è necessario (né realmente possibile) conoscere esattamente quanto tempo sarebbe necessario per violare le chiavi di ciascuna dimensione. Piuttosto si è interssati ai valori generici del livello di impegno e a conoscere qual è l'impegno relativo necessario per chiavi di dimensioni sempre più grandi.
Il secondo problema è che, in generale, non si può stabilire una formula esatta per f(n) ma solo una forma approssimata. Anche in questo caso si è principalmente interessati alla velocità di variazione di f(n) all'aumentare di n.
DES: critiche, NSA e S-Box. Come nasce un algoritmo vincente
Lo schema di crittografia più utilizzato si basa sullo standard DES (Data Encryption Standard) adottato nel 1977 dal National Bureau of Standards, oggi NIST (National Institute of Standards and Technology), come FIPS PUB 46 (Federal Information Processing Standard 46). L'algoritmo è però chiamato DEA (Data Encryption Algorithm). In DES i dati vengono crittografati in blocchi di 64bit utilizzando una chiave di 56bit. L'algoritmo in una serie di passi di 64 bit in un output di 64bit.
Gli stessi passi, con la stessa chiave consentono invece di invertire la crittografia.
L'algoritmo DES è ampiamente utilizzato ed è stato il soggetto di molte controversie riguardanti la sua sicurezza. Per comprendere la natura di queste controversie, è opportuno introdurre brevemente la storia di DES. Alla fine degli anni 60, IBM diede origine a un progetto di ricerca nel campo della crittografia condotto da Horst Feistel. Il progetto porta nel 1971 allo sviluppo di un algoritmo chiamato LUCIFER, che venne venduto ai Lloyd di Londra per l'utilizzo nei sistemi di prelievo di costante, anch'essi sviluppati da IBM. LUCIFER è una cifratura a blocchi di Feistel che opera su blocchi di 64bit utilizzando chiavi di 128bit. Dati i risultati promettenti prodotti dal progetto LUCIFER, IBM pensò di sviluppare un prodotto di crittografia commerciale che potesse essere implementato su un chip. Questa operazione venne diretta da Walter Tuchman e Carl Meyer e coinvolse non solo i ricercatori IBM ma anche consulenti esterni e il personale tecnico della NSA. Il risultato di questo tentativo fu una versione raffinata di LUCIFER che era più resistente all'analisi crittografica ma utilizzava chiavi di 56bit per poter entrare in un chip.
Nel 1973, l'NBS (National Bureau of Standards) emise un bando di gara per proporre uno standard di cifratura a livello nazionale. IBM inviò i risultati del progetto Tuchman-Meyer. Questo era di gran lunga il migliore algoritmo proposto e nel 1977 fu adottato con il nome di Data Encryption Standard.
Prima della sua adozione come standard, la proposta di DES fu soggetta ad ampie critiche che non si sono ancora spente. Due elementi in particolare fecero sorgere molte critiche. Innanzitutto la lunghezza della chiave nell'algoritmo LUCIFER originale di IBM era di 128bit mentre quella del sistema proposto era di soli 56bit con una riduzione (enorme) pari a 72(!!!)bit. La seconda area problematica era il fatto che i criteri progettuali della struttura interna di DES, ovvero le S-box, erano segreti. Pertanto gli utenti non potevano sapere se la struttura interna di DES fosse esente da punti deboli nascosti che potessero consentire alla NSA di decifrare i messaggi senza utilizzare la chiave. I successivi eventi, in particolare i recenti lavori di analisi crittografica differenziale, sembrano indicare che DES ha una struttura interna molto resistente. Inoltre, secondo IBM, le sole modifiche apportate alla proposta riguardavano le S-box; tali modifiche, suggerite dalla NSA, hanno eliminato i punti deboli identificati nel corso del processo di valutazione.
In ogni caso, DES si è molto sviluppato ed è ampiamente utilizzato specialmente nella applicazioni finanziarie. Nel 1994, il NIST confermò DES per l'utilizzo a livello Federale per altri cinque anni sebben non per applicazioni relative alla protezione di informazioni militare segrete. Nel 1999, NIST emise una nuova versione dello standard che indicava che DES doveva essere utilizzato solo per i sistemi preesistenti e che venisse invece adottata la versione triple DES. TripleDES non è altro che DES applicato 3 volte sul testo in chiaro con due o tre chiavi differenti.
[Security 35] .NET | Firme Digitali (Introduzione)
Le firme digitali vengono utilizzate per "firmare" un messaggio aggiungendo uno strato di dati denominato firma. Utilizzando le firma digitali, il destinatario può verificare l'integrità del messaggio utilizzando specifiche funzioni di verifica. Gli algoritmi che supportano le firme digitali sono definiti "Algoritmi a Firma Digitale". Una firma digitale è specifica per ogni messaggio / documento.
Quale è il vantaggio di utilizzare le firme digitali? Beh la risposta a questa domanda è abbastanza semplice. Se il mittente utilizza le firme digitali per inviare informazioni, il destinatario può essere sicuro che il contenuto del messaggio non sia stato alterato da terze parti durante il suo viaggio.
La figura che segue ne illustra il funzionamento
Al momento della creazione del messaggio, il mittente (colui che crea il messaggio), crea una coppia chiavi. Il processo di firma del messaggio crea a tutti gli effetti un insieme di dati che verranno spediti insieme al messaggio al destinatario Bob.
Al fine di accellerare il processo, Alice (mittente) non firma l'intero messaggio ma :
- Crea il messaggio
- Genera il codice Hash del messaggio
- Firma il codice Hash ottenuto
Un altro vantaggio derivato dall'utilizzo delle firme digitali è la possibilità di avere differenti firme di più persone. Come una sorta di contratto n persone possono firmare una informazione al fine di approvare il contenuto dello stesso. Questo è possibile attraverso una serie di step che riporto qui di seguito
- Alice e Bob accettano e firmano il messaggio (contratto)
- Alice crea l hash code del messaggio e lo firma con la sua chiave privata
- Bob crea l hash code del messaggio e lo firma con la sua chiave privata
- Alice controlla se Bob ha usato il codice di hash corretto e verifica la firma utilizzando la chiave pubblica di Bob.
- BoB controlla se Alice ha usato il codice di hash corretto e verifica la firma utilizzando la chiave pubblica di Alice.
Seguire questi step può rivelarsi incredibilmente utile perchè permette ad entità di terze parti di verificare le firme delle parti interessate utilizzando le loro chiavi pubbliche.
La sicurezza delle firme digitali
Le firme digitali hanno due obbiettivi:
- Sicurezza Crittografica
- Devono avere "security features" pari o superiori alle firme per come tutti le conosciamo. (documenti su carta)
Perchè le firme digitali possono essere considerate relativamente sicure?
- Nel caso in cui il messaggio venga intercettato - (Sniffing) – colui che intercetta il messaggio non deve poter modificare il messaggio. Questa task può essere completata nel caso in cui l'attaccante sia in grado di replicare la firma del mittente.
- Nessuno dovrebbe essere capace di utilizzare la firma del mittente in nessun altro messaggio.
- Colui che ha intercettato il messaggio non può modificare il contenuto del messaggio originale. Questa sicurezza è data dal fatto che : modificando il messaggio originale, la firma originale non corrisponderà al messaggio stesso.
- Il mittente non può firmare e successivamente negare il fatto di aver firmato il messaggio originale. Solo il mittente può utilizzare la sua chiave privata. A rigor di logica nessun altro può aver firmato.
Follow Up : [Security 36] .NET | Firme Digitali (Creazione)
Steganografia, tra passato e presente.
Prima d'iniziare a trattare la cifratura a blocchi DES vorrei concludere la sezione tecniche codifica di base con la Steganofragia.
Eliminiamo subito ogni dubbio, la steganografia non è crittografia. Di fatto un messaggio in chiaro può essere nascosto in due modi. I metodi della steganografia nascondono l'esistenza stessa del messaggio, a differenza dei metodi di crittografia che rendono il messaggio illeggibile da parte di estranei grazie a varie trasformazioni applicate al testo.
Una forma di steganografia semplice prevede la disposizione delle parole o delle lettere all'interno di un testo apparentemente innocuo. Per esempio, il messaggio nascosto può essere definito dalla sequenza delle prime tre lettere di ciascuna parola di un messaggio.
Storicamente sono state utilizzate varie altre tecniche fra cui le seguenti:
1) Contrassegno dei caratteri : alcune lettere del testo scritto o stampato vengono sovra scritte a matita. I segni non sono normalmente visibili a meno che la carta non venga mantenuta a una certa angolazione rispetto ad una intesta sorgente luminosa.
2) Inchiostro invisibile : varie sostanze consentono di scrivere senza lasciare alcuna traccia visibile se non applicando calore o una sostanza chimica.
3) Piccoli fori : piccoli fori sulle lettere prescelte che non risultano visibili se non ponendo il foglio di carta davanti a una sorgente luminosa.
4) Nastro correttore per macchine da scrivere : usato per scrivere il messaggio segreto fra le righe scritte con inchiostro in nero, lo rende visibile solo con una forte sorgente luminosa.
Queste tecniche, sebbene possano sembrare arcaiche, hanno degli equivalenti contemporanei. La lettura [WAYN93] propone di nascondere un messaggio nei bit meno significativi dei frame di un CD. Per esempio, la massima risoluzione del formato Kodak Photo-CD è di 2048 per 3072 pixel, ogni pixel contiene 24 bit di informazioni per i colori RGB. Il bit meno significativo di ciascun pixel può essere modificato senza alterare significativamente la qualità dell'immagine. In questo modo è possibile nascondere 2,3MB di messaggio in un'unica fotografia digitale.
Per esempio, è possibile recuperare una immagine di un gatto da una di un discreto paesaggio.
"Steganografia < Crittografia"
La steganografia presenta numerosi difetti rispetto alla crittografia. Richiede un grosso impegno anche per nascondere un numero relativamente limitato di bit di informazioni. Inoltre il sistema, una volta scoperto, diviene praticamente inutile. Anche questo problema può però essere risolto se il metodo di inserimento dipende da un certo tipo di chiave. Alternativamente un messaggio può essere prima crittografato e poi nascosto utilizzando la steganografia.
"Steganografia > Crittografia"
Il vantaggio della steganografia è che può essere impiegata da parti che non vogliono far sapere che sono in comunicazione. La crittografia invece segnala essa stessa che il traffico è importante o comunque che il mittente e il destinatario stanno avendo una conversazione privata.
Fasi Multiple di crittografia : Macchine a Rotazione
Prima dell'introduzione di DES, l'applicazione più importante del principio delle fasi multiple di crittografia era una classe di sistemi nota con il nome di macchine a rotazione.
Il principio di queste macchine è abbastanza complesso. La macchina consiste in un insieme di cilindri rotanti indipendenti attraverso i quali possono passare degli impulsi elettrici. Ogni cilindro ha 26 terminali d'ingresso e 26 terminali di uscita con cablaggi interni che connettono ciascun terminale di ingresso a un solo terminale di uscita.
Se si associa a ciascun terminale di ingresso e di uscita una lettera dell'alfabeto, allora un cilindro definisce una sostituzione mono alfabetica. Si consideri una macchina con un unico cilindro. Dopo la pressione di ciascun tasto di input, il cilindro ruota di una posizione e dunque le connessioni interne vengono ruotate di conseguenza. Pertanto verrà impiegata un'altra sostituzione cifrata mono alfabetica. Dopo 26 lettere di testo in chiaro, il cilindro torna alla posizione iniziale: si ha dunque un algoritmo di sostituzione poli alfabetica con un periodo pari a 26.
Un sistema con un unico cilindro è molto semplice e non rappresenta un problema per l'analisi crittografica. La potenza della macchina a rotazione è costituita dalla presenza di più cilindri dove le uscite di un cilindro sono connesse agli ingressi del cilindro successivo. Quando si usano più cilindri, quello più vicino all'input dell'operatore ruota di una posizione a ogni input. Per ogni rotazione completa del cilindro interno, il cilindro intermedio ruota di una posizione. Infine, per ogni rotazione completa del cilindro centrale, il cilindro più esterno ruota di una posizione (esempio a tre cilindri). In pratica questo sistema si comporta come il contachilometri di un'automobile. Il risultato è che vi sono 26 x 26 x 26 = 17576 diversi alfabeti di sostituzione prima che il sistema si ripeta. L'aggiunta di un quarto e di un quinto rotore porta rispettivamente a runa ripetizione con un periodo di 456976 e 11881376. Per capire l'elevata complessità di questo sistema possiamo usare una citazione di David Kahn il quale ha riferito in modo eloquente riguardo alla macchina a rotazione con 5 rotori quanto segue:
Un periodo di questa lunghezza impedisce qualsiasi possibilità pratica di soluzione sulla base della frequenza delle lettere. Per ottenere una soluzione generale sarebbero necessarie circa 50 lettere per alfabeto cifrato, ovvero i cinque rotori dovrebbero svolgere il loro ciclo per 50 volte. Il testo cifrato dovrebbe essere lungo quanto tutti i discorsi tenuti al senato e alla casa dei rappresentati in tre sessioni successive del congresso. Nessun analista crittografico sarebbe in grado di catturare un tale tesoro in tutta la sua vita; perfino i diplomatici, che possono essere prolissi quanto i politici, raramente raggiungono questi livelli di loquacità
La macchina a rotazione è importante in quanto apre la strada alla cifratura attualmente più utilizzata: l'algoritmo DES (Data Encryption Standard).
Curiosità : Macchine basate sul principio del rotore sono state utilizzate sia da Germania (Enigma) sia in Giappone (Purple) durante la Seconda Guerra Mondiale. La violazione di questi due codici da parte degli alleati ha contribuito significativamente al risultato della guerra.
Tecniche di trasposizione
La maggior parte delle tecniche di crittografia classica si basa sul concetto della sostituzione di un simbolo di testo cifrato con un simbolo di testo in chiaro. Ma è interessante sapere che si può ottenere un mapping molto differente eseguendo una permutazione delle lettere del testo in chiaro. Questa tecnica è chiamata cifratura a trasposizione.
La tecnica puù semplice è chiamata Rail Fence (staccionata) in cui il testo in chiaro viene scritto come una squenza di diagonali e poi letta come una sequenza di righe. Per esempio, la staccionata del messaggio "ciao a tutti" sarà:
c a a u t i o t t i
andando ad avere un messaggio cifrato pari a:
caautiotti
Questo tipo di tecnica è estramemente facile da analizzare. Uno schema più complesso consiste nello scrivere il messaggio in un rettangolo, riga per riga e poi leggerlo colonna per colonna permutando l'ordine delle colonne. L'ordine delle colonne diviene quindi la chiave dell'algoritmo. Ecco un esempio:
plaintext: "messaggio segreto"
chiave : 3 2 1 5 4
m e s s a
g g i o s
e g r e t
o
cipher: sireggmgeoastsoe
Una cifratura a trasposizione pura è facile da riconoscere poichè presenta la stessa frequenza delle lettere del testo in chiaro originario. Per il tipo di trasposizione a colonne appena illustrato, l'analisi crittografica è piuttosto semplice e prevede la disposizione del testo cifrato in una matrice, giocando poi sulla posizione delle colonne. Può essere utile anche impiegare tabelle di frequenze di diagrammi e trigrammi.
La cifratura a trasposizione può essere resa significativamente più sicura eseguendo la trasposizione in più fasi. Il risultato è una permutazione più complessa che risulta difficile da ricostruire. Pertanto, se il messaggio precedente viene ri-crittografato utilizzando lo stesso algoritmo si avrà:
chiave : 3 2 1 5 4
S I R E G
G M G E O
A S T S O
Ecipher: rgtimssgaegooees
Per visualizzare il risultato di questa trasposizione, si designano le lettere del messaggio in chiaro originario con i numeri che indicano la loro posizione. Pertanto, con un messaggio di 16 lettere, la sequenza di lettere originaria sarà
01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
Dopo la prima trasposizione si avrà
03 08 13 02 07 12 01 06
11 16 05 10 15 04 09 14
il quale presenta una struttura ancora troppo regolare. Ma dopo la seconda trasposizione si avrà una struttura molto meno strutturata e di conseguenza sarà più difficile da analizzare/attaccare.
Cifratura PlayFair
Una delle cifrature più note è chiamata PlayFair e tratta i diagrammi del testo in chiaro come singole unità traducendoli in diagrammi cifrati. L'algoritmo PlayFair si basa sull'uso di una matrice 5x5 costruita utilizzando una parola chiave.
M O N A R
C H Y B D
E F G I/J K
L P Q S T
U V W X Z
In questo caso la parola chiave è monarchy. La matrice è costruita introducendo le lettere della parola chiave (esclusi i duplicati) da sinistra a destra e dell'alto al basso e poi completando la parte rimanente della matrice con le altre lettere specificate in ordine alfabetico. Le lettere I e J contano come una sola lettera. Il testo in chiaro viene crittografato due lettere alla volta, in base alle seguenti regole.
La cifratura PlayFair rappresenta già un notevole miglioramento rispetto alla semplice cifratura monoalfabetica. Per esempio, mentre vi sono solo 26 lettere, vi sono 26 x 26 = 676 diagrammi e dunque l'identificazione dei singoli diagrammi è più difficoltosa. Inoltre le frequenze relative delle singole lettere hanno un intervallo molto più ampio di quello dei diagrammi, complicando lulteriormente l'analisi della frequenza. Per questi motivi, la cifratura PlayFair è stata considerata per lungo tempo inviolabile. In particolare è stata utilizzata come sistema di comunicazione sul campo dall'esercito inglese nella prima guerra mondiale ed era ancora diffusamente utilizzata dall'esercito americano e dalle forze alleate durante la seconda guerra mondiale.
Nonostante questo livello di fiducia nella sua sicurezza, la cifratura PlayFair risulta comunque relativamente facile da violare perché conserva ancora molta della struttura del linguaggio in chiaro. In generale bastano poche centinaia di lettere di testo cifrato per poterla violare.
Curiosità : Questa cifratura è stata in realtà inventata dallo scienziato inglese Sir Charles Wheatstone nel 1854 ma porta il nome del suo amico Playfair Barone di St. Andrews, che ha depositato la cifratura al Foreign Office Britannico.
Su Internet : A questo link del Liceo Foscarini è possibile testare e provare (tramite questo script Javascript) l'algoritmo appena descritto.
