4. Meccanismi simmetrici 63. L algoritmo A5 del GSM L algoritmo RC4

Description
4. Meccanismi simmetrici Cifrari simmetrici Cifrari a flusso.64 L algoritmo A5 del GSM L algoritmo RC4 4.3 Cifrari a blocchi...67 Lunghezza della chiave Il modello di Feistel Data Encryption

Please download to get full document.

View again

of 15
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Health & Lifestyle

Publish on:

Views: 0 | Pages: 15

Extension: PDF | Download: 0

Share
Transcript
4. Meccanismi simmetrici Cifrari simmetrici Cifrari a flusso.64 L algoritmo A5 del GSM L algoritmo RC4 4.3 Cifrari a blocchi...67 Lunghezza della chiave Il modello di Feistel Data Encryption Standard (DES) Crittanalisi differenziale e lineare I successori del DES Advanced Encryption Standard (AES) Modalità di cifratura 4.4 Meccanismi per l autenticazione di un documento...72 Integrità ed origine di un testo cifrato Integrità ed origine di un testo in chiaro Integrità, origine e non ripudio di un testo in chiaro 4.5 Gestione delle chiavi.75 La chiave che cifra chiavi Il Centro di distribuzione delle chiavi Lo scambio di Diffie-Hellman 4.6 Campo GF(p)...79 Addizione in GF(p): a+b mod p Moltiplicazione in GF(p): a b mod p Esponenziazione in GF(p): y = b x mod p Logaritmo discreto Residui quadratici e Sottogruppi ciclici 4.7 Numeri primi...85 Distribuzione dei numeri primi Ricerca di numeri primi grandi 64 4. Meccanismi simmetrici 4.1 Cifrari simmetrici Il principale oggetto di studio della moderna Crittografia simmetrica è il Cifrario a chiave segreta. Gli attuali Cifrari simmetrici sono anche detti convenzionali essendo i discendenti diretti di quelli messi a punto nel periodo classico; tipicamente sono usati per la difesa della riservatezza, ma sono impiegati anche come meccanismi per la generazione di numeri pseudocasuali, per l autenticazione e per l identificazione. I Cifrari attualmente in uso sono: robusti (resistono a tutti gli attacchi di crittanalisi finora individuati), veloci (nelle realizzazioni con Hw special purpose elaborano diversi milioni di bit al secondo), efficaci (gestiscono stringhe binarie di lunghezza arbitraria), efficienti (il testo cifrato è praticamente lungo quanto il testo in chiaro). La prima cosa da mettere in luce è la consuetudine di classificarli in due categorie. Per capire su cosa si basa la classificazione, consideriamo una coppia di utenti A e B, indichiamo con AB la chiave segreta che hanno concordato di usare e supponiamo che A sia il mittente e B il destinatario di un messaggio riservato. Sia infine m la stringa di bit in chiaro cifrata da E e decifrata da D. Le attività che A e B devono svolgere sono: 1. A: calcola c = E AB (m) e trasmette c 2. B: riceve c e calcola D AB (c) = D AB (E AB (m)) = m In generale m è solo una parte del testo in chiaro M che A intende inviare a B: le attività 1. e 2. devono dunque essere ripetute per M/m volte. La dimensione di m ed il modello cui si ispira il meccanismo sono i parametri che hanno portato a distinguere due differenti tipi di Cifrario. Il Cifrario a flusso (stream cipher) si ispira a One-time pad, trasforma pochi bit alla volta (tipicamente un solo bit od un byte) e risulta particolarmente adatto quando occorre proteggere singoli dati, generati uno dopo l altro (trasmissione seriale di caratteri ASCII, comunicazione fonica digitalizzata, ecc.). Il Cifrario a blocchi (bloc cipher) si ispira al Cifrario poligrafico ed al Cifrario composto, trasforma blocchi formati da molti bit (64, o 128, o più) e risulta particolarmente adatto quando occorre proteggere strutture di dati (trasmissione di pacchetti, archiviazioni di file su hard dis, ecc.). Vedremo che la demarcazione non è poi così netta. E comunque importante prendere atto fin d ora che il cifrario a flusso è più veloce del cifrario a blocchi, il cifrario a blocchi è più sicuro del cifrario a flusso. 4.2 Cifrari a flusso I Cifrari a flusso realizzano una trasformazione variabile al progredire del testo. Discutendo il Cifrario di Vernam, è stato Il meccanismo per la sostituzione di un bit evidenziato che l hardware necessario per trasformare e ritrasformare un bit alla volta è un semplice gate EX-OR. 0 0 seed Un bit di testo (in chiaro o cifrato) ha, infatti, due sole possibili sostituzioni: PRNG Per eseguire o l una o l altra è sufficiente sommarlo modulo due con un corrispondente bit di chiave. Si ha bit di chiave dunque: bit di testo CIFRATURA: c i = m i i DECIFRAZIONE: c i i = m i i i = m i La sicurezza del metodo è concentrata nella realizzazione di una stringa di bit aleatori i lunga quanto il testo. In realtà i bit di chiave non possono che essere pseudocasuali ed è questo il fatto che non consente di ottenere una sicurezza perfetta: in trasmissione ed in ricezione occorre, infatti, impiegare due PRNG, detti generatori di flusso di chiave, per garantire la perfetta sincronizzazione dei due flussi. 4. Meccanismi simmetrici 65 Abbiamo già osservato in cap. 2 che la stringa dei bit di chiave deve avere un periodo grandissimo (almeno ). Ciò consente di suddividere la sequenza in moltissime sottosequenze e di rendere imprevedibile quella che viene di volta in volta impiegata tramite un seme casuale, concordato in segreto dai due corrispondenti. Segre tezza e variabilità di un seme vettore d inizializzazione IV Chiave testo in chiaro seed P RBG IV te sto cifrato seed Chiave PRBG testo in chiaro ESEMPIO - In figura è mostrata la soluzione adottata nel protocollo WEP (Wired Equivalent Privacy) per reti wireless. Il mittente sceglie di volta in volta un diverso vettore di inizializzazione, che concatena alla chiave segreta per determinare il seed e che trasmette in chiaro in testa al cifrato. Il destinatario estrae IV, lo concatena con la chiave segreta che condivide con il mittente ed inizializza così la generazione del flusso di chiave esattamente dallo stesso punto da cui è partito il corrispondente. La soluzione è però oggi giudicata insicura. Una volta fissata la dimensione del seed, la necessità di concatenare e IV limita la dimensione della chiave, rendendola più facilmente prevedibile. Esistono due differenti tipi di Cifrario a flusso: a flusso sincrono, con auto-sincronizzazione. A flusso sincrono seed Con auto - sincroniz. seed p i p i G (next state) Register F (output) i Shift i F Stream Ciphers c i c i seed c i seed c i G (next state) Register F (output) i Shift i F p i p i Nei Cifrari a flusso sincrono il flusso dei bit di chiave è indipendente dal flusso dei bit di testo; la chiave, il seed, può interessare o la F, o la G; la funzione interessata deve essere unidirezionale. Per un corretto funzionamento i generatori di trasmissione e di ricezione devono mantenersi al passo: quando si verifica un disallineamento, sorgente e destinazione devono far ripartire i due generatori, curando anche di scegliere un diverso punto di inizio della sequenza. Nei Cifrari a flusso con auto-sincronizzazione il flusso dei bit di chiave dipende dal flusso dei bit di testo cifrato: si noti in figura il ruolo svolto dai due registri a scorrimento. Un eventuale perdita di sincronismo non richiede alcun intervento da parte degli utenti: dopo un breve transitorio (il tempo necessario a ricaricare in modo corretto lo shift di ricezione) i due generatori si rimettono al passo da soli. La più comune causa di disallineamento è la perdita d integrità del testo cifrato, quale può essere generata o da un evento casuale o da un attacco intenzionale. Consideriamo dapprima l eventualità che sia cancellato o inserito un bit. Le stazioni di un Cifrario a flusso sincrono perdono il sincronismo e l errore si propaga su tutta la restante parte del messaggio; le stazioni del Cifrario con auto-sincronizzazione perdono il sincronismo solo temporaneamente e consentono di riprendere correttamente la decifrazione al termine del transitorio. Consideriamo ora l eventualità che sia modificato un bit. Nei Cifrari a flusso sincrono la violazione dell integrità non si propaga ai bit successivi e non è rilevabile; i Cifrari con auto-sincronizzazione decifrano invece in modo errato finché il bit modificato è presente nello shif di ricezione. I Cifrari a flusso sincrono sono più usati di quelli con auto-sincronizzazione. Molti sono stati gli studi indirizzati ad individuare PRNG veloci e di facile realizzazione. Per allargare il quadro delineato nel cap. 2, esamineremo due ulteriori soluzioni, una basata sullo scorrimento di bit e l altra sullo scambio di posizione di byte. Oggi si preferisce impiegare la funzione E di un Cifrario simmetrico a blocchi: la modalità CTR è stata discussa in 2.2.1, le modalità OFB e CFB verranno esaminate in 66 4. Meccanismi simmetrici L algoritmo A5 del GSM Lo standard GSM per i telefoni mobili impiega un Cifrario a flusso sincrono, detto algoritmo A5, per proteggere la riservatezza delle comunicazioni sulle tratte radio. Il PRN è formato da tre registri a scorrimento, ciascuno con retroazione lineare e GSM: il generatore di flusso di chiave con un comando di shift/ hold che gli indica, in ogni intervallo di cloc, se deve o non deve attuare lo scorrimento Le retroazioni calcolano l EX-OR dei bit la cui posizione nello shift compare come esponente nei seguenti polinomi primitivi: Shift / Hold Ex Or x 19 + x 5 + x 2 + x + 1 x 22 + x + 1 x 23 + x 15 + x 2 + x L uso dei polinomi primitivi attribuisce ad ogni registro un periodo di massima lunghezza: in opportuna sequenza il registro assume, infatti, tutti gli stati interni possibili ad eccezione dello stato di tutti zeri. Ad ogni passo ciascun registro è shiftato solo se il suo bit centrale concorda con il valore di maggioranza dei bit centrali dei tre registri. Il fatto che almeno due registri alla volta vengano shiftati attribuisce al loro insieme un comportamento che dipende in modo non lineare dallo stato interno e quindi dal seme di inizializzazione. La segretezza e la lunghezza della chiave (64 bit, ma in realtà, per motivi non del tutto chiari, gli ultimi 10 bit hanno sempre valore 0) dovrebbero garantire la non riproducibilità del flusso di chiave da parte di un intruso. Ross Andersen ha dimostrato che non è così (v. chem.leeds.ac.u/icasm/people/jon/a5.html). Molti altri ricercatori hanno individuato tecniche di decrittazione abbastanza efficaci (da pochi secondi a qualche minuto, secondo la quantità di dati intercettati e della memoria a disposizione per sottoporli a pre-elaborazioni). Nei videotelefoni di nuova generazione (standard UMTS) il flusso di chiave è generato in modo più sicuro dal Cifrario a blocchi Kasumi. A differenza del GSM, UMTS impiega flussi diversi in trasmissione ed in ricezione L algoritmo RC4 L algoritmo RC4 29, inventato da R. Rivest nel 1987 e tenuto segreto, è stato divulgato su Internet nel Inizialmente considerato molto robusto (ma poi la crittanalisi ha evidenziato diverse vulnerabilità), ha avuto diverse applicazioni (Lotus Notes, Oracle, Secure SQL, SSL, WEP). RC4 impiega un registro di stato interno formato da 256 celle S[i], in cui sono inizialmente sistemati, in ordine crescente, i 256 possibili valori di un byte; è poi operata Stato S: 256 byte SKA Il Cifrario a flusso RC4 Seme K: 5 K[0] K[L - 1] 32 byte S[0] PRGA S[0] byte m i S[i] S[i] byte.. S[j] S[255] S[j] S[255] byte c i una permutazione definita da un seme di lunghezza L, variabile tra 40 e 256 bit. A tale attività provvede l algoritmo SKA, che esegue scambi di contenuto (swap) tra coppie di celle: for i = 0 to 255 S[i] = i; j = 0; for i = 0 to 255 j = (j + S[i] + K[i mod L]) mod 256 scambia i valori di S[i] e S[j] Il flusso di byte pseudocasuali (sono più di ) è generato dall algoritmo PRGA, anch esso basato sul paradigma dello scambio: i = 0, j = 0 loop: i = (i +1) mod 256 j = (j + S[i]) mod 256 scambia i valori di S[i] e S[j] = S[(S[i] + S[j]) mod 256] 29 Nel sito del corso è disponibile il file RC4.zip, contenente un eseguibile ed i relativi sorgenti; l approfondimento è stato fatto da Ginevra Cicconi 4. Meccanismi simmetrici Cifrari a blocchi Mittente: Destinatario: E c 1 c 1 D m 1 Bloc cipher m 1 m 2 m N E c 2 c 2 D m 2 E c N c N D m N t Il testo da cifrare viene suddiviso in blocchi m 1, m 2,.., m N di lunghezza prefissata L. Se la lunghezza del testo in chiaro non è un multiplo intero della lunghezza del blocco, il mittente aggiunge all ultimo blocco simboli di riempimento privi di significato (padding). La regola di trasformazione dei blocchi, fissata dalla chiave, è una sostituzione monoalfabetica, ma la grossa dimensione dei blocchi (nel caso di un testo letterario codificato in ASCII un blocco include la codifica di almeno otto caratteri) la rende immune da un attacco con statistiche. Anche la decifrazione procede a blocchi ed è fissata dalla chiave. In conclusione si ha: CIFRATURA: c i = E(m i, ), per i =1,2,.. DECIFRAZIONE: D(c i, ) = m i, per i =1,2,.. Sono in uso diversi standard per consentire alla macchina del destinatario di eliminare automaticamente i bit di padding aggiunti dalla macchina del mittente. PKCS#7, ad esempio, prevede che il completamento dell ultimo blocco sia fatto da n byte di valore n, se 8 n è il numero di bit che mancano nel testo in chiaro Lunghezza della chiave n di bit n di chiavi = 7, = 3, = 3, = 6, La tabella a lato riporta una valutazione dello spazio delle chiavi (2 N ) in corrispondenza di alcuni valori della loro lunghezza N. Tutti i numeri nella seconda colonna sono oggettivamente molto grandi, ma potrebbero non spaventare un attacco con forza bruta: per condurlo basta, infatti, disporre di un testo cifrato e scrivere un programma che lo decifri provando uno dopo l altro tutti i possibili valori della chiave. Per decidere se la chiave in prova è quella giusta occorre come minimo conoscere il linguaggio impiegato nel testo in chiaro: l analisi statistica del testo decifrato fornisce già una buona indicazione se prenderla o no in considerazione. Le cose sono ancora più semplici se si conosce anche il corrispondente testo in chiaro. Il tempo necessario per rompere il Time to brea a code (10 6 decryptions/µs) Cifrario dipende naturalmente dalla potenza della macchina a disposizione dell intruso. In figura 30 si è fatta l ipotesi che l intruso non sia un hacer estemporaneo, ma un membro di una grossa Organizzazione (o criminale, o governativa) dotata di un super calcolatore in grado di eseguire decifrazioni al secondo. In media la macchina deve controllare solo la metà dello spazio delle chiavi; il tempo medio di esecuzione dell attacco è dunque: T = 2 N-1 /10 12 sec = 2 N-1 /(3, ) anni Per individuare una chiave di 56 bit una macchina di questo tipo impiega circa 10 ore; con 168 bit occorrono circa anni. ESEMPI - Nel 1998 il DES Cracer, una macchina parallela costata solo $, è riuscito ad individuare in meno di 3 giorni una chiave di 56 bit. Fino a poco tempo fa, per venire incontro alla richiesta di FBI e CIA, gli Stati Uniti hanno consentito l esportazione di algoritmi crittografici solo se dotati di una chiave non più lunga di 40 bit. 30 slide prelevata dal sito di William Stallings 68 4. Meccanismi simmetrici Il periodo di tempo in cui un informazione deve rimanere segreta può variare da poche ore a molti anni: anche questo dato deve dunque essere messo in conto quando si vuole un dimensionamento sicuro della chiave di un algoritmo simmetrico a blocchi. Nel 1996, durante un summit dei più famosi crittografi del mondo 31, è stata suggerita la seguente regola. R28: per avere sicurezza a breve termine occorre una chiave con 75 bit; per mantenere lo stesso livello di robustezza la lunghezza della chiave deve essere incrementata di 14 bit ogni vent anni. Il continuo incremento della lunghezza della chiave è un aspetto caratteristico dei Cifrari a blocchi moderni. La pericolosità di particolari attacchi con testo noto o scelto (li citeremo più avanti) ha fatto parallelamente incrementare anche la dimensione dei blocchi. ESEMPI - Diversi standard di Cifrari a blocchi si sono succeduti nel tempo: DES (56 bit di chiave e 64 bit di blocco): ha avuto un larghissimo impiego negli anni 80 e 90; TDES (112 o 168 bit di chiave e 64 bit di blocco): versione più robusta del DES usata negli anni 90; AES-Rijndael (da 128 a 256 bit di chiave con blocchi di 128,192,256 bit): il vincitore della gara citata a pag. 22, per il quale è stata prevista una vita almeno trentennale. Gli utenti devono inoltre rispettare le regole R12 (i bit della chiave devono essere generati a caso) e R24 (la chiave in uso deve essere frequentemente modificata, come peraltro aveva a suo tempo sostenuto Kerchoffs) Il modello di Feistel Quasi tutti i Cifrari adottano, con qualche variante, il modello di Feistel 32, che a sua volta discende dal modello del Cifrario composto proposto da Shannon. Ogni blocco di testo cifrato è ottenuto dal corrispondente blocco di testo in chiaro (nel seguito indicheremo con 2w la loro dimensione in bit) iterando diverse volte l esecuzione di una sostituzione e di una trasposizione. La rete di Feistel L i = R i - 1 R i =L i - 1 F( R i - 1, i ) Round 1 Round i Round n L 0 L 1 L i L n Plaintext (2w bits ) R 0 F F F Ciphertext (2w bits ) R 1 R i R n 1 i n Key Subey generation algorithm La generica i-esima iterazione, detta round, genera due vettori di w bit, (L i, R i ) a partire dai risultati del round i-1-esimo (L i-1, R i-1 ): L i = R i-1 R i = L i-1 F(R i-1, i ). La proprietà di confusione è ottenuta con la sostituzione operata dalla funzione non lineare F. Ogni round ha una sua regola di sostituzione, stabilita di volta in volta da una sottochiave i che un apposito generatore calcola a partire dalla chiave concordata dagli utenti. La proprietà di diffusione discende dal continuo scambio tra L e R. Si noti che in questo modello la trasposizione è fissa: in altre parole la P-box è priva di chiave. Una proprietà notevole del modello è che la decifrazione si esegue con lo stesso algoritmo, invertendo l ordine delle sottochiavi. Per verificarla, consideriamo soltanto l ultimo round di cifratura ed il primo di decifrazione. In ingresso alla decifrazione si ha: L 0 = R n = L n-1 F(R n-1, n ) R 0 = L n = R n-1. In uscita dal primo round si ha: L 1 = R 0 = R n-1 R 1 = L 0 F(R 0, n ) = L n-1 F(R n-1, n ) F(R n-1, n ) = L n-1. Arrivati a questo punto sono stati dunque annullati gli effetti dell ultimo round di cifratura. 31 M. Blaze, W. Diffie, R. Rivest, B. Schneier, T. Shimomura, E. Thompson, M. Wiener, Minimal Key Length for Symmetric Ciphers to Provide Adequate Commercial Security, Report,January All inizio degli anni 70 H. Feistel ha guidato il gruppo che ha progettato il Cifrario Lucifer per i calcolatori IBM-Serie 360 e ne ha poi descritto il modello sulla rivista Scientific American (maggio 1973). 4. Meccanismi simmetrici Data Encryption Standard (DES) Il capostipite dei moderni Cifrari a blocchi è stato il DES, voluto a metà degli anni 70 dal Governo Federale USA come standard per la riservatezza di dati non classificati e realizzato poi dalla IBM su invito del NIST. I round sono 16, i blocchi contengono 64 bit e la chiave è di 64 bit, o meglio di 56 perché 8 sono di parità. Si noti in figura 33 che la funzione F (uno dei punti più delicati della progettazione di tutti i Cifrari a blocchi) è stata ottenuta disponendo in cascata: una espansione&permutazione da 32 a 48 bit (effettuata da 8 E-box), la somma modulo due del risultato con altrettanti bit di sottochiave, una sostituzione&scelta (effettuata da 8 S-box) che fornisce un dato di 32 bit, una permutazione senza chiave (P-box) dei bit prima ottenuti. Si noti anche la relativamente complessa modalità di generazione delle sottochiavi (un secondo punto delicato della progettazione). Il DES è stato concepito per una realizzazione Hw (con un chip VLSI si è arrivati a cifrare 120 milioni di byte il secondo), ma ha poi trovato un impiego grandissimo con le più svariate realizzazioni Sw (le migliori cifrano 100 mila byte il secondo). Il basso numero di bit di chiave (il predecessore Lucifer ne impiegava 128) e l iniziale segretezza delle S- box avevano fatto sorgere il sospetto che il progetto contenesse punti di vulnerabilità dettati dal NIST. Dopo molti anni di polemica si arrivò alla conclusione che il sospetto era infondato. A causa del limitato spazio delle chiavi, era stato comunque previsto di dare al DES non più di dieci anni di vita, anche se poi in realtà è stato usato per più di trent anni Crittanalisi differenziale e lineare Il DES è stato un importante palest
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks