Algoritmi di crittografia

G G

000 111

101

G2(k) G2 : K --->K^8

Modi operativi (One Time Key) 08/04/2020

L’input di un cifrario a blocchi consiste di una chiave ed un blocco, l’output è un altro blocco. È bene

ora considerare le modalità di utilizzo di un cifrario a blocchi, dal momento che, generalmente, i

messaggi sono più lunghi del blocco standard.

L’obbiettivo dei modi operativi è proprio quello di spiegare l’utilizzo dei cifrari a blocchi per

messaggi di lunghezza superiore a quella del blocco processato dal cifrario. Abbiamo due scenari

differenti: One Time Key (una chiave non può essere utilizzata per cifrare messaggi differenti) e

Many Time Key (il riutilizzo è concesso).

Un esempio di utilizzo di One Time Key è quello della cifratura delle email: ne viene utilizzata una

per ogni messaggio; è bene considerare che, però, la chiave sarà la stessa nella cifratura dei vari

blocchi del messaggio.

Si assume che i cifrari possano essere considerati come delle semplici black box (o procedure) e che

siano delle PRP sicure.

L’obbiettivo è costruire un algoritmo sicuro per la cifratura di un messaggio di lunghezza arbitraria

a partire da una PRP sicura; ancora una volta, si fa riferimento alla confidenzialità. Il potere

dell’avversario consiste nell’intercettare un testo cifrato (avversario passivo); il suo obbiettivo è

risalire al testo in chiaro (anche in parte) a partire dal testo cifrato. Dal momento che la chiave è

differente per ogni messaggio, non ci si espone a pericoli legati alla correlazione.

Electronic Code Book (ECB) Un primo modo operativo potrebbe essere quello

di dividere il testo in chiaro in più blocchi e

applicare ad ognuno di essi il cifrario a blocchi; la

cifratura dei vari blocchi avverrà con la stessa

chiave. La lunghezza dei blocchetti dipende dal

cifrario a blocchi che si sta adottando. ECB è insicuro: potrebbe verificarsi che due blocchi del testo

in chiaro siano uguali e, dunque, verranno generati due blocchi di testo cifrato identici, visto che uno

stesso cifrario viene richiamato con lo stesso input (m₁ = m₂ c₁ = c₂); non è detto che l’avversario

riesca a capire il testo in chiaro, ma comunque deduce che alcuni blocchi saranno identici: anche

questo è un leaking di informazioni che non dovrebbe accadere. Possiamo vederlo con degli esempi:

Come si nota, è possibile notare che il testo cifrato ottenuto con ECB non è affatto confidenziale: nel

caso di Linux, le parti relative a porzioni di immagini con lo stesso colore sono assimilabili a blocchi

identici e, quindi, verranno cifrati alla stessa maniera. Due blocchi in chiaro uguali generano due

blocchi cifrati uguali.

Anche se si parte da un cifrario a blocchi sicuro si ottiene un testo cifrato insicuro se si usa un modo

operativo insicuro. Anche in questo caso ricorriamo alla definizione di

sicurezza semantica.

sicuro in termini di riservatezza se la adv è piccolo tende a 0

per ogni avversario efficiente deve essere trascurabile il

vantaggio.

[A, CIPHER]

Ci aspettiamo che ECB non abbia sicurezza semantica. Per dimostrarlo bisogna verificare l’esistenza

di un avversario efficiente con vantaggio non trascurabile; il messaggio, ovviamente, deve essere

costituito da almeno due blocchi. Consideriamo un messaggio m₀ costituito da due

blocchi “Hello” e “world”, quindi due blocchi

diversi; m₁ è invece costituito da due blocchi

identici “Hello”. L’avversario manda i due

messaggi al challenger, estrae una chiave, effettua

la cifratura c di uno dei messaggi e la restituisce

all’avversario. Quest’ultimo può individuare

1 certamente quale dei due messaggi ha generato c:

se i due blocchetti sono uguali, c è la cifratura di m₁, diversamente è quella di m₀. Il vantaggio è 1, il

massimo: quando l’avversario riceve la cifratura di m₀ non risponderà mai 1; viceversa, quando

riceve la cifratura di m₁ risponderà sempre 1. Questo basta per stabilire che ECB non è sicuro

semanticamente.

Deterministic Counter Mode CI si accontenta di una PRF non richiede una PRP, è chiaro che se abbiamo una PRP questa è anche una PRF anche se abbiamo una

PRF che non è una PRP →

Supponiamo di avere una PRF F: K × {0, 1}ⁿ {0, 1}ⁿ, ovvero un cifrario per blocchi di n bit. Il modo

operativo DETCTR suddivide il messaggio in L + 1

blocchi di lunghezza n bit ciascuno.

F(k, i) richiama il cifrario a blocchi con chiave k sul

blocco che rappresenta il numero i.

G(k)-------------> Si ottiene una sequenza di lunghezza pari a quella

del messaggio in chiaro; le due sequenze vengono

messe in XOR in modo tale da ottenere una sequenza che rappresenta l’output finale della cifratura.

Abbiamo costruito un cifrario a flusso a partire da un cifrario a blocchi. È un modo operativo con

sicurezza semantica. È interessante notare che il cifrario a blocchi non viene richiamato direttamente

sul testo in chiaro ma sui blocchi che codificano i numeri da 0 a L. Per decifrare, semplicemente si

calcola la sequenza e questa verrà messa in XOR con il testo cifrato. F non deve essere invertita per decifrare quindi per

questo va bene una PRF, infatti si usa sempre F(k,i) in

cifratura e decifratura

Teorema

L > 0, se F è una PRF sicura, allora DETCTR è un cifrario semanticamente sicuro. In particolare,

∀ ∀A

avversario di DETCTR, B avversario efficiente della PRF:

∃ Ma se la F è sicura, a destra dell’uguale avremo

una quantità trascurabile (anche se raddoppiata);

allora lo sarà anche quella a sinistra, ovvero il

vantaggio di A su DETCTR. Ciò vuol dire che

DETCTR è semanticamente sicuro.

Ci si accontenta di una PRF perché non è necessario invertire F: per decifrare si inverte solo il

processo, non F. Modi operativi (Many Time Key)

In questo caso, si permette di cifrare più messaggi con la stessa chiave: è il caso della cifratura di file

o in IPsec. Per analizzarne la sicurezza, bisogna considerare che un avversario passivo può

intercettare più testi cifrati generati con la stessa chiave. L’avversario può ora effettuare anche un

chosen plaintetxt attack (CPA), ovvero ottenere la cifratura di un messaggio a sua scelta.

In questo caso, si deve considerare una definizione

adattata di sicurezza semantica.

Il procedimento è identico; la differenza è che

l’avversario può effettuare una seconda volta

l’esperimento; il challenger cifrerà sempre il primo

(o il secondo) elemento di ogni coppia.

L’esperimento può essere iterato ulteriormente,

per un totale di q coppie e q testi cifrati ricevuti dall’avversario, a sua disposizione. Dovrà poi

stabilire se è stato cifrato sempre il primo o sempre il secondo messaggio di una coppia. Ci

potrebbero essere dei round in cui l’avversario decide di inviare una coppia di messaggi identici: in

questo modo, l’avversario ottiene la cifratura di un messaggio scelto da lui. Per il resto, rimangono le

stesse definizioni viste in precedenza relativamente al vantaggio.

Un cifrario che, richiamato più volte con la stessa

chiave e lo stesso testo in chiaro, produce sempre

lo stesso testo cifrato, non soddisfa questa

definizione di sicurezza semantica.

In questo caso, infatti, mandando prima una

coppia di messaggi identici e poi una coppia in cui almeno uno dei due messaggi è quello inviato

prima, l’avversario individua con probabilità 1 il testo in chiaro che ha prodotto c.

Per far fronte a questo problema si adottano due soluzioni:

1. Si rende l’algoritmo randomizzato;

2. Si utilizzano dei nonce. 15/04/2020

Supponiamo che E, richiamato con la stessa chiave

e lo stesso testo in chiaro, restituisca lo stesso testo

cifrato. Il cifrario non soddisfa la definizione di

sicurezza semantica. Nel contesto MTK, vorremmo

poter utilizzare la stessa chiave per tutti gli n

messaggi; basta che due di questi siano uguali per

ottenere due testi cifrati uguali: si ha lo stesso problema visto con ECB. È necessario che la proprietà

caratteristica di E non sia soddisfatta.

Una prima soluzione è ricorrere ad un algoritmo randomizzato:

Un algoritmo E randomizzato è tale che,

richiamato più volte con la stessa chiave e con lo

stesso messaggio m₀, si dovrebbero ottenere testi

cifrati differenti, con alta probabilità.

Chiaramente, la decifratura dei due testi cifrati

differenti deve invece portare allo stesso

messaggio m₀.

Il testo cifrato ottenuto, tuttavia, sarà più lungo del testo in chiaro, per via di una sequenza di bit

randomica.

Un secondo approccio è quello dell’utilizzo dei nonce:

In figura si nota il classico scenario di crittografia

simmetrica, con una differenza: la presenza del

nonce, che viene inviato a Bob insieme al testo

cifrato stesso. Da ciò si ricava che non è richiesto

che il nonce sia segreto, infatti viene inviato in

chiaro. Infine si nota che l’algoritmo di cifratura prende in input anche il nonce, per un totale di tre

diversi parametri. Lo stesso ragionamento, ovviamente, si applica anche all’algoritmo di decifratura.

Il nonce non deve necessariamente essere segreto; la stessa coppia ‹chiave, nonce› non può essere

utilizzata più volte: la chiave è fissata, ma si fa variare il nonce; infine, non deve necessariamente

essere una valore casuale, può anche essere un semplice contatore; ad ogni modo, se è scelto in

maniera casuale da un insieme N, è bene che N sia molto grande. Il vantaggio legato all’utilizzo di

un nonce che rappresenta un contatore è dovuto al fatto che, se mittente e destinatario sono

sincronizzati, non è necessario inviarlo. Ciò è possibile solo se è certo che venga mantenuto l’ordine

di invio dei messaggi.

Quando si utilizzano i nonce, bisogna adattare la definizione di sicurezza CPA:

In questo caso, l’avversario invia al challenger, per

q volte, una tripla costituita dai due messaggi e dal

nonce; il resto del procedimento rimane invariato.

È bene specificare, però, che ognuno dei q nonce

deve essere differente.

Un cifrario Q basato sul Nonce è semanticamente sicuro, se per ogni A avversario efficiente ha un

vantaggio trascurabile

Adv nCPQ [A,Q] =| Pr[EXP(0)=1] - Pr[EXP(1)=1] | è trascurabile

Novità :

1) challenger usa il Nonce scelti dall'avversario( Nonce sempre diversi)

3) stessa chiave Nonce deve essere sempre diverso per ogni round

Cipher Block Chaining (CBC)

È un modo operativo MTK sicuro sotto determinate condizioni.

Costr