•  
  • Archivi per Crittografia (9)

Appunti avanzati di Criptografia – Parte 8 – Crittografia a chiave pubblica

Commenti: Nessun Commento
Pubblicato il: 11 aprile 2011

RSA

La criptografia a chiave pubblica è una delle principali rivoluzioni nel mondo della sicurezza delle comunicazioni.

Per centinaia di anni si è dato per scontato che due interlocutori, per comunicare a distanza in modo sicuro, dovessero avere in comune una chiave di lettura di un testo che sarebbe sembrato incomprensibile a tutti gli altri. Cambiarono le modalità di criptazione, la lunghezza e la forma di queste chiavi, ma il principio rimaneva lo stesso. Tale modalità di comunicazione venne chiamata Criptografia a chiave privata.

Adesso esiste ANCHE un’altra tipologia di criptografia, la criptografia a chiave pubblica. Tale trasmissione sicura prevede l’utilizzo non di una ma di due chiavi. Una di esse può essere resa in linea di principio nota a tutti, mentre la seconda no.

La criptografia a chiave pubblica nasce per risolvere alcuni problemi intrinseci della criptografia a chiave privata, ovvero la distribuzione delle chiavi e la firma digitale.

Per avere una buona criptografia a chiave pubblica bisogna avere a disposizione un operazione matematica che sia semplice da farsi in una direzione e che sia estremamente complessa da invertire. Tali funzioni in matematica esistono e la più comune è proprio quella che che ci viene sbattuta in faccia da bambini, la moltiplicazione.

Vi starete chiedendo cosa ci sia di complesso nell’invertire la moltiplicazione, ma la risposta è semplice. L’inverso della moltiplicazione è la scomposizione in fattori primi, e dimostreremo tra poco che la scomposizione in fattori primi può diventare estremamente complessa se i numeri in gioco sono veramente grandi.

La fattorizzazione non è l’unica funzione one way, ce ne sono altre, come ad esempio i logaritmi discreti.

La criptazione a chiave pubblica è estremamente lenta rispetto ad un corrispettivo a chiave privata, ragion per cui si utilizza molto spesso come mezzo per scambiare in modo sicuro una chiave di sessione da utilizzare con gli algoritmi a chiave privata, questa operazione viene chiamata KEY EXCHANGE e non tutti gli algoritmi a chiave pubblica consentono di farlo.

Esistono ovviamente anche la criptazione totale e la firma digitale che sono operazioni fattibili con un sottoinsieme degli algoritmi a chiave pubblica.

Uno dei più importanti e longevi algoritmi a chiave pubblica è il cifrario RSA.

E’ un cifrario a blocco che funziona tramite l’esponenziazione di numeri interi modulo un primo in un campo di galois. Per maggiori informazioni sul funzionamento di RSA, si può leggere qualcosa qui.

Esistono quattro tipi di attacchi all’algoritmo RSA:

  • Brute Force: è un attacco che è sempre fattibile ogni volta che esista una qualsiasi chiave.
  • Attacco matematico: Difficile perchè basato su una operazione complessa quale la fattorizzazione.
  • Timing Attacks: Basati sul tempo di decriptazione e facilmente invalidabili usando costanti temporali e pause casuali
  • Attacchi a testo cifrato scelto

Appunti avanzati di Criptografia – Parte 7 – Cenni di teoria dei numeri

Commenti: Nessun Commento
Pubblicato il: 11 aprile 2011

La teoria dei numeri studia le caratteristiche dei numeri interi e ne valuta le peculiarità nei vari ambiti dello scibile.

In particolare, l’argomento principe riguarda i numeri primi.

Un numero primo è un numero che non ha divisori, eccetto se stesso ed il numero 1. Si può facilmente dimostrare che i numeri primi sono infiniti, per farlo basta considerare che se essi fossero infiniti, potremmo elencarli in una successione p_i con i che va da uno a MAX.

Dando per scontato il fatto che gli interi sono un’infinità numerabile, si può verificare che il numero X dato dal prodotto di tutti i p_i + 1, è un numero che non ammette nessun divisore a parte se stesso ed uno, ed è quindi primo. Ma se è primo abbiamo negato la tesi e quindi è vero il fatto che i numeri primi sono infiniti.

Questa dimostrazione non l’ho certo fatta io ma l’ha fatta un certo Eulero.

Dei numeri primi si ignorano moltissime cose, tra cui una efficiente descrizione della loro distribuzione tra i numeri interi.

Due numeri A e B si considerano coprimi tra loro se non hanno divisori in comune eccetto 1.

Un concetto importante in criptografia è il concetto di numero primo forte, che è vincolato da queste regole:

1) il numero, detto p deve essere composto da un numero alto di cifre.
2)  p = a_{1}q_{1}+1 con q_1 grande.
3)  q_1 = a_{2}q_{2}+1 con q_2 grande.
4)  p = a_{3}q_{3}-1 con q_3 grande.

In crittografia è importante fattorizzare velocemente un numero molto grande, ma questa è un operazione estremamente onerosa conoscendo soltanto il numero e nessun altra informazione, mentre il suo inverso (moltiplicazione dei fattori) è un’operazione molto semplice. Viene appunto detta funzione one way, anche se non è l’unica ad avere questa caratteristica di funzione facile da computare da un lato e difficile dall’altro.

Riconoscere se un numero è primo o composito è un’operazione genericamente più semplice rispetto alla fattorizzazione. Esistono parecchi modi per verificare, deterministicamente o probabilmente, se un numero è primo oppure no.

Il primo metodo è il più banale, si divide per tutti i numeri da 1 a sqrt{x}, ma è un metodo altamente inefficiente.

Definiamo la funzione toziente di un numero n detta phi. come la somma di tutti i numeri minori di n che siano coprimi ad n stesso. Tale funzione è moltiplicativa, ovvero la funzione del prodotto di due numeri è data dal prodotto delle funzioni dei numeri presi singolarmente.

Ovviamente, se n è primo, il toziente sarà pari ad n-1, ma in genere non è così.

Ritornando agli algoritmi di primalità, considereremo soltanto quelli probabilistici in quanto molto più veloci rispetto a quelli deterministici, anche se matematicamente non danno certezza del risultato.

Il primo è il test di fermat, si sfrutta il piccolo teorema di fermat e si controlla se la congruenza è vera per molti numeri di base di esponenziazione. Anche se venissero verificati tutti, ci sono i numeri di carmichael che pur essendo compositi verificano la congruenza.

Un altro algoritmo è il test di Miller Rabin.

Il test di miller Rabin è un test probabilistico, che non da la certezza che un numero sia primo o composito, ma è possibile, iterando tale algoritmo fare in modo che la probabilità che un numero dato per primo sia in realtà composito sia piccola a piacere.

Supposto n il numero primo del quale verificare la primalità.

Per il numero n-1 possiamo sicuramente dire che:

 n - 1 = 2^kq, ammesso che q sia dispari e j appartenga ai naturali.

A questo punto scegliamo un valore a compreso tra 1 e n-1.

Valutiamo l’espressione a^q equiv 1 ; (mod ;n)

Se tale espressione è vera, per quel numero a, n ha passato il test. Esiste una probabilità su 4 che un test di questo tipo restituisca un numero composito se verificato. A causa dell’indipendenza dei singoli test, la probabilità congiunta è il prodotto delle probabilità marginali, per cui possiamo, iterando il test, far decrescere la probabilità come frac {1}{4^t}

Un problema estremamente importante nella criptografia è quello del calcolo dei logaritmi discreti.

L’operazione di esponenziazione discreta (in un campo finito) è relativamente semplice, al pari della moltiplicazione tra interi. Non è invece altrettanto semplice ricavare la potenza di una base dato il risultato dell’esponenziazione. Esistono diversi algoritmi che tentano risolvono tale operazione, ma nessuno di essi ha complessità polinomiale.

Motivo per cui, i logaritmi discreti sono anch’essa una funzione trappola (o one way) al pari della fattorizzazione, e sono usati in algoritmi come El Gamal, Diffie Hellman e DSA

Appunti avanzati di Criptografia – Parte 6 – Numeri casuali e Cifrari a flusso

Commenti: Nessun Commento
Pubblicato il: 31 marzo 2011

I numeri casuali sono un pò il pane quotidiano della crittografia. Vengono utilizzati per mille motivi tra cui le chiavi di sessione, le generazioni delle chiavi pubbliche o dei keystream.

Tali numeri casuali devono essere quanto più casuali possibili, e questo in informatica, è molto complesso.

Il miglior modo è quello di “campionare” fenomeni della vita reale.

Esistono diversi algoritmi che creano numeri pseudocasuali, che però possono superare vincoli ristretti quanto si vuole, uno di questi è il Linear Congruential Generator.

X_{n+1} = (aX_n + c) mod ; m

dove X è il numero in questione, m è il modulo, c un incremento e a è un moltiplicatore…

Una sequenza di numeri casuali di questo tipo può essere ricostruita anche con pochi valori carpiti, per cui non è eccessivamente sicura.

Un altro algoritmo è il Blum Blum Shub che si basa sulla difficoltà di fattorizzare grandi numeri, ma ovviamente risulta essere un processo molto lento.

Quali sono le caratteristiche che dovrebbe avere una sequenza di numeri pseudocasuali?

1) Non deve essere alta la probabilità di avere elementi consecutivi identici
2) Deve essere indistinguibile da una sequenza di numeri casuali veri secondo dei test
3) A partire da una sottosequenza o da uno stato del generatore non deve essere possibile trovare l’intera sequenza
4) Non deve essere possibile trovare numeri precedenti della sequenza partendo da un punto qualsiasi.

I cifrari a flusso cifra il plaintext un bit o un byte alla volta, utilizzando un keystream che si combina con lo stesso plaintext. Il cifrario di vernam è una tipologia di cifrario a flusso con keystream di lunghezza infinita.

I cifrari a flusso, se hanno un keystream valido e casuale, sono più semplici e veloci dei cifrari a blocco e danno la stessa sicurezza.

Esistono varie tipologie di cifrari a flusso, la prima salomonica divisione è in cifrari sincroni ed autosincronizzanti.

I cifrari sincroni sono più performanti dal punto di vista del recupero d’errore, ma sono maggiormente soggetti agli attacchi attivi in quanto un errore volutamente prodotto in input da luogo ad un cambiamento prevedibile in output.



Cifrario sincrono, criptazione

Se la funzione h è uno XOR, si tratta di cifrario a flusso additivo binario.

Nel caso dei cifrari autosincronizzanti, il keystream è funzione della chiave e di un numero definito di bit precedenti del ciphertext.

sigma_i = (c_{i -t},c_{i - t + 1},c_{i - t + 2})
z_i = g(sigma_i,k)
c_i = h(z_i,m_i)

Consentono una diffusione delle statistiche del plaintext e sono meno soggetti ad attacchi attivi ma possono dovere richiedere maggiori ritrasmissioni in caso di errori anche singoli.

Uno dei più famosi, semplici ed efficienti algoritmi BASC (BInary Additive Stream Cipher) è l’ RC4. Tale algoritmo viene utilizzato ampiamente in protocolli quali l’SSL ed il WEP.

L’RC4 genera un flusso di bit pseudo casuali (keystream): tale flusso è combinato mediante un’operazione di XOR con il testo in chiaro per ottenere il testo cifrato. L’operazione di decifratura avviene nella stessa maniera, passando in input il testo cifrato ed ottenendo in output il testo in chiaro (questo perché lo XOR è un’operazione simmetrica).
Per generare il keystream, l’algoritmo utilizza una S-box di 256 byte e 2 indici da 8 bit, generalmente identificati con le lettere “i” e “j”. La chiave di cifratura fornita dall’utente è generalmente lunga da 40 a 256 bit (da 5 a 32 caratteri) ed è utilizzata per inizializzare l’S-box mediante la funzione KSA, acronimo di Key-Scheduling Algorithm (algoritmo di gestione della chiave).

L’RC4 è tanto semplice quanto insicuro, in quanto si nota una certa correlazione nei primi 256 byte cifrati che vengono spesso generati a vuoto, come in una sorta di transitorio.

WEP è stato dimostrato essere craccabile in poco tempo, ma questo non sembra dipendere dal cuore di RC4.

Un altro algoritmo interessante è A5, con tutte le sue derivazioni. Tale classe di algoritmi viene utilizzata spesso nelle comunicazioni GSM americane.

Una trasmissione GSM è composta da pacchetti di dati definiti burst. Su un normale canale ed in ogni direzione viene spedito un burst ogni 4,615 millisecondi: questo burst viene generato dall’A5/1. L’algoritmo produce 114 bit di dati cifrati tramite un’operazione di XOR tra 114 bit di dati in chiaro ed altrettanti bit di keystream.

L’A5/1 viene inizializzato utilizzando una chiave a 64 bit combinata con un numero di sessione a 22 bit pubblicamente noto. Nelle implementazioni dei campi GSM 10 bit della chiave sono fissati a 0 (zero) per cui l’effettiva lunghezza della chiave è di 54 bit.

L’A5/1 si basa su una combinazione di tre registri a scorrimento a retroazione lineare (LFSR) con sincronizzazioni irregolari.

Gli algoritmi A5 sono considerati abbastanza insicuri, in quanto suscettibili ad attacchi anche del tipo testo in chiaro noto.

L’ultimo algoritmo considerato è il SEAL, che è un algoritmo ottimizzato per architetture a 32 bit, utilizzato per l’encrypting degli hard disk, utilizza chiavi a 160 bit.

Fa parte della tipologia di algoritmi che mappano sequenze di bit in altre sequenze più grandi (in generale), chiamate lenght increasing pseudo random functions.

Queste funzioni consentono di non dovere partire necessariamente dall’inizio ma di potere generare la pseudo random string a partire da qualsiasi punto del testo.

Appunti avanzati di Criptografia – Parte 5 – Cifrari simmetrici contemporanei

Commenti: Nessun Commento
Pubblicato il: 27 marzo 2011

Il Data Encryption Standard si è subito scoperto essere suscettibile al brute force.

Per questo motivo occorse scegliere un altro cifrario. Si potè scegliere tra un cifrario completamente nuovo come l’AES e alcuni sistemi di criptazione multipla, utilizzando algoritmi già disponibili.

Il più semplice cifrario multiplo è il DOUBLE DES.

Le formula caratteristiche del double des sono le seguenti:

C = E[K_2,; E(K_1,P)]
P = D[K_1,; D(K_2,C)]

Ovviamente il double-des, dato che può produrre un mapping che nel single-des non si avrebbe, è più sicuro, ma quanto?

Per poterlo appurare, dobbiamo fare delle considerazioni. Supponiamo di conoscere una coppia Plaintext-CipherText, possiamo subito vedere che:

  X = E[K_1,P] = D[K_2,C]

Se si ottiene un matching, la coppia {K1, K2} può essere una coppia papabile, a questo punto si verifica con altri Plaintext e ciphertext. Il numero di falsi allarmi è abbastanza elevato, ma ripetendo l’operazione più volte diventa semplice craccare il cifrario.

Questo attacco viene chiamato meet in the middle.

Per scongiurare attacchi MITM, la metodologia migliore è quella di passare dal double des al TRIPLE DES.

Il triple des è la triplice ripetizione del cifrario DES, che quindi può utilizzare due, o tre chiavi.

Nel caso di tre chiavi i test che dovrebbe fare un ipotetico attacco MITM sarebbero ben 2^{118} che sono troppi per essere fattibile.

Anche il triple des con due chiavi risulta essere resistente all’attacco MITM, ma è suscettibile ad altri attacchi simili al MITM se si è in possesso di dati intermedi, come la criptazione del plaintext al primo dei tre stadi.

Questo algoritmo è tra i più utilizzati nell’ambito delle applicazioni Internet, compreso PGP e s/MIME.

Esistono diverse modalità di funzionamento dei cifrari simmetrici, che ovviamente, sono da considerarsi quando le quantità di dati da criptare superano la grandezza di un singolo blocco.

Esse sono:

  • Electronic CodeBook
  • Cipher Block Chaining
  • Cipher Feedback
  • Output Feedback
  • Counter

ECB è la modalità più ovvia dove ciascun blocco viene criptato come se esistesse solo lui.

CBC è invece una modalità in cui l’output di ogni blocco viene xorato con la chiave del successivo per creare una chiave nuova che quindi varia ad ogni blocco.

CFB è una modalità che si utilizza per i cifrari a flusso, che è più facile vedere che descrivere:



OFB è anch’esso descrivibile tramite un immagine:



Counter è simile ad OFB ma non cripta i valori di Feedback ma lo fa con i valori di un counter.

L’ultima forma di Encryption, usata per i dischi è la XTS-AES



Appunti avanzati di Criptografia – Parte 4 – Advanced Encryption Standard

Commenti: Nessun Commento
Pubblicato il: 26 marzo 2011

Si è notato quasi subito dopo avere realizzato il Data Encryption Standard che esso era soggetto ad attacchi di vario tipo, dal brute force alla criptanalisi lineare e differenziale.

Si suppose di iterare il processo DES, facendo nascere il double e triple des, ma i blocchi continuavano a restare piccoli ed era molto lento, per cui si decise di creare un nuovo cifrario.

Il NIST nel 1997 emise un bando per un nuovo cifrario, con caratteristiche di sicurezza in partenza migliori rispetto a DES. Nell’ottobre del 2000 venne scelto il RijnDael come AES.

Le richieste del bando erano le seguenti:

  1. Cifrario Simmetrico a blocco
  2. Blocco da 128 bit con chiave da 128/192/256 bit
  3. Più veloce e robusto del triple-des
  4. Computazionalmente efficente
  5. 20/30 anni di vita stimata
  6. Licenza free
  7. Specifiche complete e dettagliate
  8. Implementazioni C e Java

Questi criteri mutarono durante la selezione stessa, arrivando ad essere molto più stringenti.

Rijndael venne scelto superando tutti gli altri pretendenti, esso ha come caratteristica peculiare il fatto di non essere una rete di Feistel ma un cifrario iterativo e quindi di operare su tutto il blocco di dati in ogni stadio.



L’algoritmo prevede l’utilizzo di una matrice bidimensionale chiamata STATO, che passa attraverso le varie parti dell’algoritmo, che sono 4.

  • Substitute Bytes
  • Shift Rows
  • Mix Columns
  • Add Round Key

vediamole una per una.

  • Substitute Bytes

    E’ una matrice da 256 valori di un byte. I 4 bit più significativi rappresentano un indice di riga, mentre gli altri 4 un indice di colonna. Gli 8 bit selezionano un valore in uscita.

    Questa operazione rappresenta la S-box di Shannoniana memoria. Per ottenere una adeguata confusione, il mappaggio di ciascun byte dell’S-box avviene tramite il calcolo dell’inverso moltiplicativo nel campo GF(2^8)

    Ovvero:

      b'_i = b_i oplus b_{(i+4); mod 8} oplus b_{(i+5); mod 8} oplus b_{(i+6); mod 8} oplus b_{(i+7); mod 8} oplus c_i

    con c_i l’i-esimo bit del byte {63}.


  • Shift Rows

    Ciascuna riga dello state è shiftata ciclicamente a sinistra un numero di volte pari al suo indice riga meno uno.

    In questo modo tutti i bit si sparpagliano in tutta la matrice.


  • Mix columns

    è un prodotto matriciale nel campo di Galois GF(2^8).

    Questa operazione viene effettuata per ottenere un missaggio di buona qualità tra tutti i bytes delle diverse colonne. Dopo poche iterazioni tutti i bit in output dipendono da tutti i bit in input.


  • Add Round Key

    è l’unica operazione tra le quattro che fornisce sicurezza. Fondamentalmente si tratta di un bitwise XOR tra i 128 bit dello stato e i 128 bit della sottochiave.

    Per ottenere le sottochiavi si effettua un processo chiamato Key Expansion.

    la keyexpansion è rappresentabile mediante la formula:

     g = SW(RW(w_{i-1}) oplus Rcon(frac{i}{4})

    SubWord effettua una sostituzione usando la s-box
    RotWord compie uno shift circolare a sinistra di una word
    Rcon è una costante di round.

    La keyexpansion rappresentò, ai tempi della sua idealizzazione, il top del rapporto complessità/prezzo.


    La decriptazione AES NON è equivalente alla criptazione ma molto simile. Occorre invertire alcune operazioni della cifratura.

    AES risulta resistente alla maggior parte degli attacchi conosciuti al momento e si suppone che gli unici attacchi fattibili siano quelli di tipo SIDE CHANNEL ma che richiedono un ascolto della tempistica di calcolo estremamente precisa. Si suppone che, data la perfetta conoscenza matematica dell’algoritmo, ci possano essere attacchi matematici possibili, ma è solo un ipotesi.

  • Appunti avanzati di Criptografia – Parte 3 – Cifrari a Blocchi e DES

    Commenti: Nessun Commento
    Pubblicato il: 25 marzo 2011

    I cifrari a blocchi si occupano di criptare un testo dopo averlo diviso in parti, tipicamente maggiori di 64 bit ciascuno. Moltissimi cifrari utilizzati professionalmente al giorno d’oggi sono a blocchi, anzi, sono più diffusi di quelli a flusso.

    La maggior parte dei cifrari a blocco si basano su una singola architettura chiamata rete di Feistel.

    Prima di introdurre la rete di Feistel, conviene introdurre i concetti di S-box e P-box, che sono delle operazioni teoricamente supposte da Shannon per aumentare la diffusione e la confusione di un cifrario.

    La Diffusione consiste nel distruggere la statistica del plaintext sulla massa del ciphertext, mentre la Confusione rende la relazione tra plain e cipher il più complessa possibile.

    Un tipico blocco in cifrario di Feistel viene diviso in due parti dette L e R ed elaborate in n cicli di un algoritmo, effettuando sostanzialmente tre operazioni:

    1. Sostituzione a sinistra (L)
    2. Funzione iterata a destra + subkey (R)
    3. Swap (L – R)



    Uno dei Cipher a blocchi presi come riferimento e più conosciuti nel mondo, che risponde alla logica della rete di Feistel è il Data Encryption Standard.

    Usa blocchi da 64 bit con chiavi da 64 bit, ed esegue una serie di operazioni.



    La prima operazione effettuata dal Data Encryption Standard è l’Initial Permutation, che rimescola i bit e li divide in due metà da 32 bit ciascuna, per fare ciò, c’è una tabella di riferimento.

    Il generico ciclo DES può essere descritto, al pari di qualsiasi cifrario Feistel dalle equazioni:

    L_i = R_{i-1}
    R_i = L_{i-1} oplus F(R_{i-1},K_i)

    Ma cosa fa questa funzione F? La funzione F prende 32 bit della parte destra e i 48 bit della subkey ed esegue le operazioni seguenti:

    1. Espande la parte destra da 32 a 48 bit
    2. Effettua lo xor tra la parte destra e la subkey di round
    3. Passa attraverso 8 s-box, che restituiscono 32 bit partendo da 48
    4. Permuta i 32 bit

    Alla fine delle operazioni della funzione F, l’output della permutazione P viene xorato con la parte sinistra.

    La generica S-box altro non fa che selezionare, tramite una matrice composta da 4 righe e 16 colonne, soli 4 bit. I 6 bit di partenza scelgono l’elemento della matrice da selezionare.

    Per la generazione delle sottochiavi invece, si utilizza un’altra procedura.

    Si creano, a partire dalla chiave di 64 bit, due blocchi a 28 bit che chiameremo C0 e D0, ottenuti rimuovendo un bit ogni byte.

    Per ogni stato i due blocchi sono shiftati a sinistra di un numero di volte definito da una tabella, ottenendo una nuova coppia di C e D. Quindi le parti sono permutate dalla Permuted Choice 2 ottenendo la sottochiave di round.

    Il Des risulta attaccabile per più vie, tramite analisi lineare, differenziale e forza bruta.

    Ha perso, anche a causa della ristrettrezza della sua chiave, molto del suo charme, ed è stato soppiantato per i casi in cui la sicurezza richiesta è molto più alta, tuttavia, esso rimane ancora un cifrario degno di nota ed accademicamente parlando, rilevante.

    Appunti avanzati di Criptografia – Parte 2 – Tecniche di Criptografia classiche

    Commenti: Nessun Commento
    Pubblicato il: 24 marzo 2011

    Cominciamo definendo cosa sia la criptografia.

    Prendendo come spunto la pagina omonima di wikipedia, troviamo scritto:

    La parola criptografia deriva dall’unione di due parole greche: κρυπτὁς (kryptós) che significa “nascosto”, e γραφία (graphía) che significa “scrittura”. La crittografia tratta delle “scritture nascoste”, ovvero dei metodi per rendere un messaggio “offuscato” in modo da non essere comprensibile a persone non autorizzate a leggerlo. Un tale messaggio si chiama comunemente crittogramma.

    Una volta definita la criptografia, vediamo come attuare quanto definito, introducendo la criptografia simmetrica.

    Per criptografia simmetrica (ma anche classica, convenzionale, a chiave privata, a chiave singola) si intende una comunicazione in cui le due parti condividono una chiave ed applicano al messaggio alcune operazioni reversibili.



    Criptografia simmetrica, un esempio

    Tali operazioni reversibili sono spesso rappresentate da un algoritmo, che deve essere ovviamente robusto.

    Matematicamente definiamo:

    Y = E_k(X)
    X = D_k(Y)

    Dove Y rappresenta il testo criptato e X il plaintext.

    Ecco uno schema delle differenze che si possono avere tra le varie tipologie di crittografia simmetrica.



    Criptografia simmetrica, uno schema

    Per effettuare gli attacchi criptoanalitici, volti nella maggior parte dei casi a compromettere la sicurezza della chiave condivisa tra le parti, si possono usare vare vie, definite da questa immagine:



    Le varie metodologie criptoanalitiche

    Queste modalità di cui sopra utilizzano o sfruttano la conoscenza del plaintext, o del cipher text, di entrambi, o la possibile opportuna costruzione di uno di essi o di una coppia di entrambi.
    Esiste anche la possibilità di provare tutto lo spazio delle chiavi, tale attacco viene comunemente chiamato Brute Force Attack, e, tranne che in un solo caso, è sempre fattibile.

    Il più classico dei cifrari a sostituzione è il cifrario di cesare. Tale cifrario, esistente da diversi secoli, è effettuato spostando in avanti di tre posizioni ciascuna lettera del plaintext, ciclicamente.

    Alla lettera A, ad esempio, corrisponderà la lettera D, alla lettera B la lettera E, e così via, cicilicamente.

    Matematicamente tale cifrario può essere espresso dalle seguenti equazioni:


    C = E_k(P) = (p + k) mod quad 26
    P = D_k(C) = (c - k) mod quad 26

    Come è chiaro, esistono soltanto 25 chiavi per questo cifrario, che sono i resti distinti del campo finito GF(26), ma questo credo che Giulio Cesare non potesse saperlo, avrebbe pensato ad altro.

    Ovviamente è possibile generalizzare questo cifrario a sostituzione semplicemente ipotizzando varie lunghezze degli alfabeti di partenza e di arrivo. Tali cifrari sono detti cifrari standard diretti, e sono i più semplici da violare.

    Altri cifrari a sostituzione, ma leggermente più arzigogolati sono invece i cifrari affini.

    Sono matematicamente definiti da:


    c = (ap + b) mod quad m

    non è detto a priori che (ap + b) mod m fornisca valori distinti per ogni valore di a, p, b ed m, anzi è chiaramente facile vedere che non è così. In questo caso il cifrario sarebbe irreversibile, mentre nel caso in cui a ed m siano coprimi, si verifica che i valori sono sempre distinti per ogni p1 diverso da p2.

    I cifrari affini non sono sicuri perchè sono soggetti alla cosidetta analisi frequenziale, la quale si basa sul fenomeno naturale di non omogeneità di distribuzione delle lettere dell’alfabeto delle principali lingue mondiali.

    Questa constatazione non permette nemmeno di utilizzare cifrari monoalfabetici in cui ogni lettera è sostituita da una sua permutazione casuale nell’alfabeto che, teoricamente, amplierebbe lo spazio delle chiavi ad un numero pari a  26! simeq 4,03 cdot 10^{26}, ma che in realtà non da nessun termine di sicurezza aggiuntivo, o quasi.

    Entrano in gioco quindi i cosidetti cifrari poligrafici, uno dei più importanti dei quali è il cifrario playfair.

    Creiamo una tabella 5 x 5 e riempiamola di caratteri, impostando come primi caratteri i caratteri univoci di una frase qualsiasi, che sarà la chiave, io ho scelto il mio nome e cognome, Fabrizio Mondo, ottenendo:

    F A B R I/J
    Z O M N D
    C E G H L
    P Q S T U
    V W X Y Z

    a questo punto prendiamo il nostro plaintext e operiamo una sostituzione non più carattere per carattere, ma coppia di caratteri per coppia di caratteri.

    Si procede in questo modo:

    1) Se i caratteri sono uguali, si inserisce tra loro un filler, la X.
    2) Se le lettere sono dispari si inserisce una lettera di parità (sempre la X)
    3) Se le lettere della coppia sono nella stessa riga, si sostituisce ciascuna delle due con le lettere shiftate a destra di un posto (esempio: CG diventa EH)
    4) Se le lettere della coppia sono nella stessa colonna, si sostituiscono con le lettere che sono immediatamente sotto di esse, anche con ritorno ciclico: (esempio GX diventa SB)
    5) Altrimenti sostituire le due lettere con quelle corrispondenti alla lettera che ha la stessa riga della lettera e colonna dell’altra. (esempio: FT diventa RP)

    Anche il playfair è attaccabile dall’analisi frequenziale in quanto esiste una statistica anche per la frequenza nelle varie lingue, dei digrammi e dei trigrammi.

    Consideriamo adesso il cifrario di Vigenère, che è il più semplice cifrario polialfabetico.

    Ha come chiave una serie di n lettere distinte che vengono ripetute in sequenza e che affibbiano all’i-esima lettera l’i-esimo alfabeto da usare.

    Si potrebbe pensare che un cifrario di questo tipo possa eliminare la frequenza relativa delle lettere, dato che una stessa lettera verrebbe cifrata in modo diverso in base all’occorrenza della lettera della chiave, c’è però da dire che la lunghezza della chiave è fondamentale in un tale scenario. In base alla sua lunghezza, si possono trarre alcune informazioni, verificando ad esempio possibili ripetizioni date da multipli di lunghezza della chiave stessa.

    Definiamo per maggiore chiarezza la ROUGHNESS.

    Se le lettere fossero uniformemente distribuite nel nostro comune parlato, ciascuna di esse avrebbe una probabilità di manifestarsi pari a  frac{1}{26} simeq 0,038 ma in realtà le probabilità sono diverse, definiamo quindi roughness:


      R = sum_{i=A}^Z (p_i - frac{1}{26})^2

    La roughness spazia tra un valore minimo ed un valore massimo ed è un indice che ci consente di capire se ci troviamo nel caso di un cifrario monoalfabetico o polialfabetico.

    Per potere capire la lunghezza della chiave di un cifrario di vigenere, esiste un test probabilistico, chiamato test di friedman o kappa test che consente di calcolare una relazione tra la keyword ed un indice I, chiamato indice di coincidenza che si calcola in questo modo:


      I = frac{sum_{i=1}^{26} n_i(n_i - 1)}{n(n - 1)}

    Utilizzando una chiave lunga quanto il testo, si crea il cosidetto cifrario di Vernam, che è il più robusto tra i cifrari a sostituzione polialfabetica. Se tale chiave è ASSOLUTAMENTE CASUALE, allora il cifrario che si viene a creare viene chiamato ONE TIME PAD ed è l’unico cifrario matematicamente inattaccabile.

    Tale cifrario è matematicamente inattaccabile perchè, non essendo a conoscenza della chiave, non si ha nessuna conoscenza frequenziale e di conseguenza qualsiasi testo intellegibile avente somma dei caratteri utilizzati pari a quella del plaintext, diventa un testo plausibile.

    Esistono poi i cifrari a trasposizione, dove semplicemente si permutano secondo una determinata regola i caratteri del plaintext. L’esempio più classico è quello della scitala lacedomonica.



    Tali cifrari sono molto poco sicuri, ma ciò nonostante hanno avuto successo in quanto facilmente implementabili ad esempio in macchine a rotore o in mezzi fisici (tabelle o trellis) che davano l’impressione di una sicurezza più ampia.

    Appunti avanzati di Criptografia – Parte 1 – Introduzione

    Commenti: Nessun Commento
    Pubblicato il: 24 marzo 2011

    In questo articolo e nei successivi valuteremo alcune nozioni di criptografia che possono essere utili ad uno studente di ingegneria delle telecomunicazioni, avendo cura di essere puntuali nelle definizioni.


    Cosa vuol dire sicurezza di sistema? Si può dare una definizione istintiva, che è quella che un sistema si comporti esattamente nel modo progettato, e che non consenta un utilizzo che non sia stato precedentemente autorizzato, ma è sufficiente?

    Per dimostrare che NON lo è, possiamo intanto considerare la sicurezza di un’applicazione.

    Un applicazione viene definita sicura se e soltanto se compie il lavoro previsto per lei, non più non meno.

    Il vero problema è adesso conoscere cosa deve fare esattamente un applicativo. Se ce lo dice qualcuno avremo il problema della fiducia di questa figura (è fidata?), se ne scriviamo le specifiche avremo il problema della verifica (abbiamo controllato bene?), se abbiamo scritto il programma intervengono limiti fisici e pratici (abbiamo sbagliato qualcosa?).

    Definiamo adesso l’attacco alla sicurezza.

    Per attacco alla sicurezza si intende qualsiasi operazione che comprometta la sicurezza delle informazioni di un organizzazione. Esistono varie tipologie di questi attacchi, salomonicamente divisibili in Passivi e Attivi.

    Nel mondo dell’informatica vengono definiti i servizi di sicurezza, i cosidetti X.800:

    Nome servizio Funzionalità
    Autenticazione Assicurazione che chi comunica sia effettivamente chi dice di essere
    Controllo d’accesso Prevenzione dall’uso non autorizzato di qualcosa
    Confidenzialità dei dati Prevenzione della rivelazione non autorizzata dei dati
    Integrità dei dati Prevenzione dei dati dalle manomissioni non autorizzate.
    Non Ripudio Protezione contro il non riconoscimento di un messaggio dalla parte mittente

    Riassunti sparsi di criptografia

    Commenti: 1 commento
    Pubblicato il: 16 marzo 2011



    Ecco un elenco sparso e leggero di argomenti di criptografia, utili per avere degli schemi di massima per un esame inerente questo ambito.


    Cifrario Affine

    • Cifrario nella forma C = (aP + b) mod 26
    • C rappresenta il carattere cifrato, P rappresenta il carattere Plaintext
    • a e b sono due numeri
    • Crackabile con analisi di frequenza, reversibile solo se ab e 26 sono coprimi.

    Cifrario DES

    Il Data Encryption Standard è uno dei cifrari più utilizzati al mondo ed opera come un cifrario di Feistel. Utilizza chiavi a 64 bit, di cui solo 56 sono utili.

    Il blocco da criptare viene diviso in due parti che sono elaborate singolarmente. La parte destra passa attraverso una fase di espansione, una di xor con la sottochiave, una di sostituzione e permutazione, ed infine avviene lo xor finale con la parte sinistra. Tale risultato viene poi portato in output come sottoblocco destro del round successivo. La parte sinistra invece è la parte destra del round precedente.

    Le sottochiavi sono generate tramite una tabella chiamata permuted choice che fondamentalmente effettua uno shifting secondo un numero di passi prestabilito.

    Il DES ha il vantaggio della sua semplicità e diffusione, ma è ormai facilmente craccabile in quanto il tempo computazionale anche per abbatterlo tramite attacco brute force è minore di  2^{56}


    Cifrario AES

    L’advanced encryption standard è una naturale evoluzione del des. Venne realizzato tramite un concorso a cui parteciparono più algoritmi proposti da varie personalità ed aziende. Vinse, dopo una triplice selezione, il cifrario RjinDael che NON ha la struttura di un cifrario di Feistel.

    AES opera tramite una matrice degli stati, ed ha blocchi da 128 bit con chiavi che possono avere 128, 192 o 256 bit.

    Le operazioni fondamentali in AES sono 4:

    1. ADD ROUND KEY: Viene effettuato lo xor con una sottochiave ricavata dalla chiave di partenza
    2. SUBSTITUTE BYTES: Viene effettuato uno scambio dei byte tramite un’apposita tabella, effettuando una trasformazione inversa in GF(2^8) ed una trasformazione affine.
    3. SHIFT ROWS: Si diffondono i byte nella matrice 4 x 4 spostando a sinistra i byte di ogni riga di tanti posti quant è il suo indice, meno uno.
    4. MIX COLUMNS: Sfruttando l’aritmetica polinomiale, viene effettuata una modificadei valori della tabella degli stati operando una moltiplicazione per un polinomio di terzo grado, modulo  x^4 -1

    Modalità di funzionamento dei cifrari

    • ECB: Electronic code book, è la modalità classica in cui ogni blocco è criptato in modo indipendente
    • CBC: Chain block ciphering, è la modalità in cui l’output del round n viene xorato con la chiave del round n+1 per ottenere la sottochiave del round n+1
    • CFB: Cipher Feedback, è la modalità che converte da blocchi a flussi, ogni singolo carattere criptato viene xorato con la chiave del blocco successivo, effettuando quindi più cifrature in parallelo.
    • OFB: Output Feedback, non propaga gli errori, ma è più vulnerabile.

    Cifrario RC4

    Cifrario a flussi che viene utilizzato principalmente nelle trasmissioni a forte rumore come le comunicazioni wireless. Genera numeri pseudocasuali vincolati alla chiave e ne effettua poi uno xor con il plaintext. Per questi motivi risulta nativamente insicuro.


    A5/1 – A5/2 – Kasumi

    Cifrari a flussi utilizzati principalmente nelle comunicazioni GSM. Utilizzano 54 bit di chiave e creano un keystream xorato con il plaintext. Risulta attaccabile in meno tempo del bruteforce se viene attuata una politica di cracking a testo in chiaro noto.


    Cifrario RSA

    E’ il più conosciuto tra i cifrari a chiave asimettrica e sfrutta il principio matematico della difficoltà computazionale della fattorizzazione di numeri grandi. Si ritiene che esso utilizzi la più semplice tra le funzioni one-way, che è proprio la fattorizzazione.

    Lavorando con numeri estremamente grandi viene più spesso utilizzato per lo scambio chiavi che per la criptazione, ma è potenzialmente in grado di fare qualsiasi operazione richiesta per la sicurezza.


    Diffie-Hellman

    Algoritmo criptografico per lo scambio delle chiavi, utilizza come funzione one-way il logaritmo discreto in un campo finito. Per comunicare Alice manda a Bob una tripletta di numeri, A,G e P.

    Questi numeri sono legati tra loro dalla relazione  A = G^{a} mod P

    Dove a piccolo è un numero scelto da Alice che deve restare segreto.

    Bob risponde ad alice con un’altra tripletta, B,G,P, legati dalla relazione:

     B = G^{b} mod P

    dove b è un altro numero scelto da Bob, che deve restare segreto.

    A questo punto alice calcolerà  Ka = B^{a} mod P mentre Bob calcola  Kb = A^{b} mod P. La potenza del D-H è che Ka e Kb sono uguali, vengono calcolati e non trasmessi, e rappresentano la chiave di sessione da utilizzare come si vuole e con qualsiasi cifrario simmetrico si desideri.


    Cifrario El Gamal

    Si comporta come RSA ma utilizza i Logaritmi discreti.


    Crittografia Ellittica

    Rappresenta l’avanguardia o quasi della criptografia asimmetrica. Partendo dall’equazione  Y^2 = x^3 + ax + b confinata ad un campo finito, si modifica l’operazione di somma intendendo la somma come l’opposto del terzo punto di incontro della retta che passa per due punti R e P appartenenti alla curva con la curva stessa.

    Questa metodologia di criptazione consente di avere sicurezza maggiore a partire dallo stesso numero di bit della chiave rispetto sia alla fattorizzazione che ai logaritmi discreti ma non è ancora stata studiata a fondo e in questo momento non è considerata sufficientemente collaudata per essere utilizzata come standard internazionale.


    MAC

    Il Message Authentication Code è una sorta di impronta digitale di un messaggio, ed è sempre della stessa grandezza a prescindere dalla lunghezza del messaggio di cui fare il fingerprinting ed è fortemente dipendente da una chiave.


    Hash

    Fa le stesse operazioni del MAC ma senza utilizzare una chiave. Occorre ricordare che ne Hash ne MAC sono firme digitali e che è computazionalmente impossibile ricavare un messaggio a partire dal suo Hash ne tantomeno trovarne due uguali in tempi ragionevoli.


    DSS

    Standard di firma digitale, utilizza i logaritmi discreti esattamente come nell’algoritmo di El Gamal. Fa uso di una chiave pubblica e di una privata. La sua sicurezza è data dalla mancanza di un algoritmo per il calcolo veloce del logaritmo discreto.


    SHA

    Secure Hash Algorithm è un algoritmo per il calcolo dell’hash di un messaggio. E’ un insieme di funzioni di somma, xor e rotazioni. Le sue varie nomenclature sono dipendenti dalla grandezza del blocco in output, è uno degli standard più usati per la realizzazione dei fingerprinting.


    Whirlpool

    Algoritmo per il calcolo dell hash a 512 bit. Richiede un numero di operazioni per il cracking superiori a 2^120


    HMAC

    Il keyed-hash MAC è un meccanismo utile per avere sicurezza di integrità e autenticazione di un messaggio. Fondamentalmente è un contenitore, che non ha per standard nessuna funzione di hash in particolare, anche se spesso si utilizza SHA, nelle varie versioni.


    CBC-MAC

    Funziona come la classica modalità cbc e il MAC è rappresentato dall’ultimo blocco utile. Si rivela sicuro solo per blocchi di grandezza fissa in quanto per i blocchi a grandezza variabile risulta possibile generare un particolare mac. I problemi inerenti la grandezza del blocco vengono risolti in CMAC o OMAC.


    KERBEROS

    Kerberos è una procedura di crittografia simmetrica Client/Server. Il suo utilizzo è l’evitare che i singoli host di una subnet abbiano contatto diretto con server o applicazioni considerate non sicure. Necessita di una terza parte affidabile, ed utilizza i protocolli Needham Schroeder. E’ composto da due parti, Authentication Server e Ticket Granting System. (AS e TGS).


    X.509

    Utilizza i certificati ed è utilizzato nelle Public Key Infrastructures, che sono ovviamente dotate di una certification Authority. In soldoni è una soluzione comoda per la sicurezza delle subnet che hanno molti soldi da spendere e tante cose da nascondere o garantire.

    PGP

    Pretty good privacy è la suite di strumenti criptografici più utilizzata al mondo. E’ gratuita, ne esiste una sua implementazione opensource e utilizza la crittografia asimmetrica in funzione dello scambio chiavi per diminuire i costi computazionali.

    La sicurezza viene fornita dalla comunità e dal concetto di feedback e di web of trust. Esistono diversi key server che si sincronizzano tra loro.


    S-MIME

    Funziona come PGP ma usa una Certification Authority.


    BASE64

    Codifica che consente di inviare binari con il protocollo SMTP.


    IPSEC

    Fornisce cifratura ed autenticazione dei pacchetti IP. E’ quindi una cifratura di rete totalmente trasparente ai livelli superiori. Viene utilizzato per realizzare VPN (Virtual Private Network). Si divide in due modalità:

  • Transport (Host 2 Host)
  • Tunnel (Gateway 2 Gateway)

    Ha due modalità di utilizzo che sono utilizzabili in entrambi i casi, AH e ESP.

    AH fornisce integrità ma non confidenzialità mentre ESP fornisce confidenzialità ma non tratta l’header.


    Attacco a dizionario

    L’attacco a dizionario è una tipologia di attacco che sfrutta l’abitudine dell’utente medio di utilizzare una password non solo intellegibile, ma di senso compiuto e che sia a lui legata, per rendere il processo mnemonico più semplice. Si contrasta tale attacco in vari modi… tramite reacting way, che consiste nel verificare ogni tot che le password siano robuste, oppure proactive way, che consente nel costruire una password robusta ab ovo, tramite vincoli iniziali o tramite inserimento di un salt.

    VIRUS

    Porzione di codice che, sfruttando un altro applicativo, compie operazioni potenzialmente dannose.


    WORM

    Virus standalone, non ha bisogno di un programma da parassitare.


    DOS – DdOS

    Denial of Service, attacco che impedisce l’accesso ad un servizio pubblico di un server tramite continue richieste fasulle o allocamento di memoria non utile. Viene detto distribuito se è realizzato da più di un indirizzo ip attaccante.


    FIREWALL

    Viene chiamata una infrastruttura di rete che filtra i pacchetti in ingresso e in uscita secondo delle regole stabilite dall’amministratore di rete. Su linux si ha NETFILTER ed IPTABLES.


    DMZ

    Demilitarized Zone, è una porzione di sottorete che deve avere libero accesso all’esterno sia in entrata che in uscita ed ovviamente non deve avere alcun privilegio verso le parti sensibili della rete.


    WEP

    Wired Equivalent Privacy utilizza RC4, ma l’algoritmo di gestione della chiave risulta talmente blando da non giustificare il suo nome, per questo si è passato a WPA e WPA2.


    WPA – WPA2

    Wpa è sostanzialmente una WEP con un contatore, mentre WPA-2 ha di base un handshaking a 4 vie.


    ALGORITMI DI PRIMALITA’

    Esistono diversi algoritmi che verificano, in modo deterministico o no se un numero è primo. Tale processo è più semplice della fattorizzazione.

    Moltissimi test sono deterministici solo in alcuni casi, altri (ad esempio il metodo banale delle divisioni successive) sono troppo complessi in funzione della grandezza dell’input.

    Il metodo più utilizzato è il test di Miller Rabin. Tale test consiste nell’effettuare calcoli di minimo comune multiplo e modulazioni successive. Le operazioni vengono iterate ed ogni iterazione moltiplica la probabilità di non primalità di un fattore (1/4). Quando si arriva ad una percentuale bassa a sufficienza, tale numero viene detto primo.


    Smart Card

    Le smart card sono delle schede con dell’elettronica incorporata che svolgono delle funzioni. Sono utilizzate principalmente nella telefonia, negli acquisti online, dalle banche e per i trasporti. Hanno un naturale utilizzo come mezzi di validazione servizi. Si dividono in Memory card e microprocessor card, e poi in smart card con contattiera (Contact), smart card con antenna (Contacless smartcard) e smart card con antenna e contattiera,

    Ci sono due standard internazionali. Lo standard ISO 7816 che regola le carte di identificazione elettroniche a contatto, e lo standard ISO 14443 che regola i biglietti elettronici.


    DOUBLE-TRIPLE-DES

    Per migliorare la protezione del DES, che è oramai facilmente craccabile, si utilizza il double ed il triple DES, che sono delle concatenazioni del DES stesso. Si potrebbe pensare che un Double des abbia una complessità di cracking pari al doppio di un des normale ma non è così, basta un lieve sforzo in più rispetto al des classico per craccare anche il double des tramite attacco attivo man in the middle.

    Il triple des invece evita l’attacco meet in the middle in quanto i passaggi in cui intromettersi diventano due. Tutt’oggi il triple des a due e tre chiavi è ancora molto utilizzato.


    SSH

    Secure Shell è un protocollo per il login remoto sicuro. Si divide in tre “parti” chiamate TLP, UAP e CP, la prima autorizza il server, la seconda autorizza il client e la terza permette il multiplexing. Utilizza la porta 22 e può usare le directory o i certificati. SSH ha diverse modalità di autenticazione.

  • pagina 1 di 1
    Seguimi
    FacebookLinkedInTwitterYoutubeRSS
    I like it!
    Google and Twitter

    Benvenuto , oggi è venerdì, 18 maggio 2012