Elementi di crittografia
 registri a scorrimento
Realizzata da
Andrea Artuso, Maria Rita Guardiano, Fabio mperioli
Introduzione
Maria Rita Guardiano







Generatori casuali e pseudocasuali
Registri a scorrimento
Registri a scorrimento(con feedback function)
Registri a scorrimento con feedback lineare
Creazione della chiave
Crittoanalisi dei registri a scorrimento lineare
Conclusioni
Generatori casuali e pseudocasuali
Cifrari perfetti:
i bits della chiave devono essere generati
casualmente
(es. one-time pad)
Svantaggi one-time pad:
- Troppo dispendioso dal punto di vista
economico e
di impiego di risorse
- Chiave segreta da trasmettere troppo lunga
Generatori casuali e pseudocasuali
SOLUZIONE AL PROBLEMA
• Sostituzione della sequenza completamente casuale con
una pseudocasuale
• Vantaggi: la sequenza appare come se fosse casuale ma non lo
è e in più è molto più corta
• Cifratura : analoga alla cifratura con le sequenze casuali ovvero il
generatore pseudocasuale crea la chiave, la somma bit a bit tra la
chiave e il testo in chiaro mi da la cifratura del testo
• Esempio:
Generatori casuali e pseudocasuali
RISULTATI
• Problema scambio della chiave anche se ridotto, resta
• Purtroppo questo sistema non risulta perfettamente
sicuro come invece lo era quello basato sulle sequenze
casuali
• Occorrerebbe trovare un compromesso tra livello di
sicurezza e la quantità di dati da trasmettere
Registri a scorrimento
Le chiavi pseudocasuali sono generate dai registri
a scorrimento per due principali motivi:
− Sono realizzati in maniera efficace in hardware
− La teoria matematica nei registri risulta
abbastanza chiara
Registri a scorrimento
Sono controllati da un clock quindi ad un tempo
fissato il contenuto di ogni cella passa nella
cella successiva
Struttura troppo semplice per i nostri scopi
- l contenuto della prima cella oltre ad andare in
output è inviato allultima cella
- Struttura ancora troppo semplice dopo il quarto
shift il registro ritorna allo stato iniziale
output
Registri a scorrimento con feedback
Esempio:
- primo shift
- secondo shift
Registri a scorrimento con feedback
Dopo il secondo shift si ripresenta lo stato iniziale:
Quindi ancora la struttura è troppo semplice per i nostri scopi…
Registri a scorrimento lineare
In quest’altra struttura l’ultima cella riceve in input la somma
dello stato corrente della prima cella e della terza
Le celle che non danno contributo alla funzione di retroazione si
limitano a prendere al tempo “i+1” il contenuto della cella
precedente al tempo “i”
Vediamo come un registro ti questo tipo genera una sequenza…
Creazione di una chiave
Supponiamo che il registro abbia questo stato iniziale:
Eseguiamo gli shift fino a che lo stato iniziale non si ripresenta…
Creazione di una chiave
Stato iniziale
Dopo il primo shift
Dopo il secondo shift
Dopo il quarto shift
Dopo il sesto shift si ripresenta lo stato iniziale
Dopo il terzo shift
Dopo il quinto shift
Creazione della chiave
Celle
C4
C3
C2
C1 (output)
Stato iniziale
0
0
0
1
1° shift
1
0
0
0
2° shift
0
1
0
0
3° shift
1
0
1
0
4° shift
0
1
0
1
5° shift
0
0
1
0
Stato iniziale
0
0
0
1
Creazione della chiave
• Le righe della tabella sono i vari stati che cambiano ad ogni
shift
• L’ultima colonna rappresenta la chiave generata
• Le sequenze sono periodiche (dopo 6 shift si ripresenta lo stato
iniziale quindi il registro in esame ha periodo 6)
• Il massimo periodo di un registro a scorrimento è 2n-1
Crittoanalisi dei registri a scorrimento
Finora abbiamo visto che facendo la somma bit a bit tra:
– il testo in chiaro e la chiave ottengo il testo cifrato
– il testo cifrato e la chiave riottengo il testo in chiaro
– il testo in chiaro e il testo cifrato ottengo la chiave
Ora dimostreremo che è possibile risalire alla chiave conoscendo lo stato
iniziale del registro e la funzione di retroazione
– Consideriamo una sequenza di 6 bits ( 1 0 1 0 0 1 ) ovvero la chiave e
pensiamo di sapere che sia generata da un registro di lunghezza 3
– Il nostro scopo sarà quello di trovare i coefficienti della funzione della
retroazione
Crittoanalisi dei registri a scorrimento
La prima cosa da fare è individuare lo stato iniziale del registro ( e cioè i primi
bits della chiave):
La seconda cosa da fare è calcolare quello che stiamo cercando
Dobbiamo quindi conoscere gli stati del registro nelle varie unità di tempo
Crittoanalisi dei registri a scorrimento
PROCEDIMENTO
All’inizio supponiamo che tutte le celle partecipino alla funzione di retroazione:
Utilizzando le regole di addizione e moltiplicazione dei numeri binari, per cui:
1 · 1 = 1,
1 · 0 = 0,
0 · 1 = 0,
0·0=0
E che:
x · x = 0,
x·x=x
Operiamo come segue…
, per ogni x=0 e x=1
Crittoanalisi dei registri a scorrimento
Considero le celle con 1,
quindi avrò:
C1 · 1
C3 ·1 = C1
Quindi dopo il primo shift avrò:
C3
Crittoanalisi dei registri a scorrimento
Quindi:
• Il contenuto dell’ultima cella sarà il risultato del feedback.
• Per le altre celle il risultato sarà determinato dal
semplice shift a destra
Crittoanalisi dei registri a scorrimento
Dopo il secondo shift si avrà:
C2 · 1
C3 (C1 C3) = C2
C3 · C 1
Ovvero…
C3 · C3= C2
C3
C3 · C1
Crittoanalisi dei registri a scorrimento
Nel terzo e ultimo scorrimento si avrà:
C1 · 1
C2 (C1
C3)
C3 (C2 C3
C1
C2 · C1
C2 · C3
C3 · C2
C1
C2 · C1
0
C3 · C1 =
C1 C3
C2 · C1
C3
C3 · C1
C3 · C1) =
C3 · C3
C3 · C3 · C1 =
Partendo da…
Crittoanalisi dei registri a scorrimento
Terzo shift
Abbiamo così ottenuto i rimanenti 3 bit della chiave gia conosciuta…
Crittoanalisi dei registri a scorrimento
Possiamo scrivere le tre uguaglianze:
C1 C3 = 0
C2 C3 C1 C3 = 0
C1 C3 C2 · C1 C3 · C1 =
1
Da cui otteniamo che:
C1
C1 = 0
C2
C1 C1
C1
C1
C1 = 0
C2 · C1
C1 · C1 = 1
Quindi: C2 = 0 perché x · x = 0 e x x = 0
Crittoanalisi dei registri a scorrimento
Quindi:
C1 = 1 , C2 = 0 , C3 = 1
Allora la struttura del registro che ha generato la
chiave ( 1 0 1 0 0 1) si può rappresentare così:
Conclusioni
• E’ possibile forzare un registro a scorrimento lineare di
lunghezza n se si conosce:
–
–
una sequenza d 2n bits successivi di testo in chiaro
i corrispondenti bit del testo cifrato
• Quindi una sequenza che si ripete dopo 1000000 di bits quindi
con un periodo di 220-1 può essere ricostruita conoscendo solo
40 suoi bits
• Quindi i registri a scorrimento sono crittograficamente fragili
• Per risolvere questo problema sono stati introdotti i registri a
scorrimento non lineari
Conclusioni
• Questi hanno una funzione di retroazione più complicata (non lineare)
• Oltre alla somma viene utilizzata anche la moltiplicazione tra bits
• Spesso i registri a scorrimento non lineari vengono realizzati combinando
in modo non lineare registri a scorrimento lineari
• Nonostante i registri a scorrimento non lineari siano migliori non
garantiscono sicurezza perfetta
CLOCK
Fabio Imperioli
• Registri a scorrimento (nel dettaglio)
-diverse strutture di registri
-Clock controller
-tipologie di attacchi
Diverse strutture dei registri
• Esistono diverse implementazioni hardware dei registri a scorrimento:
– S.I.S.O. (Serial Input Serial Output): l'ingresso
e l'uscita dei dati avviene in modo seriale
quella più utilizzata nell'ambito della crittografia è la tipologia S.I.S.O.
Diverse strutture dei registri
• S.I.P.O (Serial Input Parallel Output): l'ingresso dei dati
avviene in modo seriale, mentre l'uscita avviene in modo
parallelo (tutti i bits contemporaneamente dopo un numero di
shift adeguati)
Diverse strutture dei registri
• P.I.S.O (Parallel Input Serial Output): l'ingresso dei dati
avviene in modo parallelo, mentre l'uscita avviene in modo
seriale
Diverse strutture dei registri
• P.I.P.O. (Parallel Input Parallel Output): l'ingresso e l'uscita dei
dati avviene in modo parallelo.
Clock controller
• Un registro a scorrimento è formato da due parti, il registro e
la feedback function
• Il registro è formato da una sequenza di bit , che vengono
shiftati di una posizione ad ogni intervallo di tempo grazie ad
un controllore
• Il controllore scandisce il tempo per lo shift, e ci consente di
utilizzare i registri non lineari, in quanto usando un clock
irregolare si riduce il pericolo di attacchi.
Clock controller
Le componenti fondamentali sono:
• Un registro di controllo che genera una sequenza di
interi non negativi a = {ai}i≥0 e cicla con periodo ∏.
• Un registro di generazione controllato da clock,
che ha un polinomio irriducibile nella funzione
retroattiva, di grado m>1 e di ordine M.
• Il clock opera con la funzione di retroazione, che
consiste in un polinomio
Clock controller
• Se indichiamo con b = (b(i)) i ≥ 0 la sequenza di output
prodotta da un registro quando viene cloccato regolarmente, si
ha:
• il primo elemento della sequenza è in posizione b(0) ed è pari
al primo elemento dello stato corrente del registro puntato dal
valore a0 (prodotto dal registro di controllo), mentre l’ultimo
prima dello shift è b(t-1) (con t lunghezza totale sequenza); il
registro di controllo specifica un nuovo intero non negativo at ,
il registro cloccato viene scalato at volte e produce l’output
successivo, poi il registro di controllo scala di uno per la
successiva iterazione.
• Questa tecnica(basata sul clock) viene definita forward clock
control.
Clock controller
• L'elenco dei bit che fanno parte del polinomio di retroazione
viene chiamato tap sequence.
• Ad un registro a scorrimento di lunghezza n si associa come
funzione di retroazione il polinomio f(x) = a0 + a1x + ::: +
an¡1xn¡1 + xn (4) cioè un polinomio di grado n (pari alla
lunghezza del registro stesso), avente come coefficienti i
coefficienti della funzione di retroazione. Tale polinomio è
detto polinomio del registro.
Possibili attacchi
• Edit distance correlation attack
• Embedding correlation attack
• Attacco correlato
Edit distance correlation attack
• Un pregio dei registri è l’immunità da correlazione cioè la
probabilità che sussista una relazione privilegiata tra l'uscita
del generatore di sequenze pseudocasuali e l'uscita di uno dei
suoi LFSR interni. L'immunità da correlazione è importante
perché, studiando il comportamento otteniamo informazioni
circa le sequenze interne. Usando queste informazioni ed altre
relazioni, riusciamo a forzare il generatore.
Edit distance correlation attack
• La base dell’attacco di tipo edit distance, si basa sulla misura
della distanza tra due sequenze di lunghezza diversa, definita
in modo da riflettere la trasformazione della sequenza di
output prodotta dal registro di generazione in un output che
chiamiamo u in base al modello statistico scelto.
• Questa misura permette di fare una scelta statistica tra le varie
possibilità, ed una ipotesi è accettata se, definendo Un un
segmento di lunghezza n preso in modalità random dalla
sequenza di output reale e Xm un segmento della sequenza
generata di lunghezza m supponendo un possibile stato iniziale
del registro, la distanza tra Un ed Xm è maggiore della soglia
stimata sulla base del ragionamento scelto.
• Ovviamente, questo ragionamento, si basa solo sulla edit
distance che è troppo generica, per cui l’algoritmo risulta poco
praticabile.
Attacco di tipo Embedding
• Nell’attacco di tipo Embedding l'obiettivo è quello di trovare
tutti i possibili stati iniziali del generatore, così che per alcuni
m ≥ n un segmento dato possa essere incluso nella sequenza di
output di lunghezza m del generatore prodotta sotto un clock
regolare ma l'attacco ha successo se ci sono solo pochi di
questi stati iniziali.
• Per verificare se l'inclusione sia possibile, si può usare un
algoritmo di corrispondenza diretta (direct matching
algorithm) per l'inclusione forzata o si possono usare algoritmi
per calcolare la distanza. L'inclusione è possibile se e solo se la
distanza è uguale a m – n.
• E' ovvio che embedding attacks generalmente non sono
ottimali dal momento che non fanno uso
• della distribuzione probabilistica della sequenza di controllo.
Algoritmi
Andrea Artuso
I principali algoritmi che vengono applicati ai registri a scorrimento
sono:
•
•
•
•
•
•
A5
Huges XPD/KPD
Nanoteq
Rambutan
Gifford
PKZip
A5
•
Utilizzo:
–
•
Cifrario a flusso utilizzato nella telefonia mobile (GSM) per criptare la fase in
cui si stabilisce il contatto del terminale con la base (ripetitore)
Caratteristiche:
–
–
Composto da 3 registri 19, 22 e 23 bit
Utilizza polinomi di feedback sparsi
x19 + x5 + x2 + x + 1
x22 + x + 1
x23 + x15 + x2 + x + 1
–
–
–
•
L’output è il risultato dello XOR dei tre registri
La gestione del clock per ogni registro è diversificata
Molto efficiente (passati tutti i test statistici)
Attacchi:
–
L’attacco più prevedibile richiede 240 tentativi.
Huges XPD/KPD
•
Storia:
–
–
–
•
Progettato dalla Huges Aircraft Corporation (1968)
Viene applicato su apparecchiature militari
KPD (dispositivo cinetico di protezione)
Caratteristiche:
–
–
–
•
Utilizza un registro a 61 bit con 210 polinomi primitivi
Ha 8 differenti filtri non lineari, che producono 6 TAP
Ogni TAP produce un bit che si combina con gli altri per formare
un byte utilizzato per criptare un flusso di dati
Chiave:
–
La chiave seleziona un polinomio allocato nella memoria
Nanoteq
•
Storia:
–
–
•
E’ il nome di una compagnia elettronica Sud Africana
Utilizzato dalla polizia locale per cifrare le trasmissioni fax
Caratteristiche:
–
–
–
–
•
Utilizza un registro a 127 bit con un polinomio fisso
Ciascuna cella ha 5 input ed un solo output
Ciascun input è messo a XOR con alcuni bit della chiave
Esiste una permutazione segreta, disponibile solo l’hardware
Chiave:
–
•
La chiave è lo stato iniziale del registro
Attacchi:
–
Ross Anderson ha fatto i primi passi per analizzarlo
Rambutan
•
Storia:
–
–
–
•
E di origine britannica, progettato dalla GCHQ
Approvata per la protezione di materiale confidenziale
Algoritmo segreto, chip non disponibile
Caratteristiche:
–
–
–
–
–
•
Può operare in 3 diversi modi: ECB, CBC, CFB
Probabilmente è un registro con cifrario a flusso
E’ composto da 5 registri di 80 bit
I polinomi nella retroazione ottengono solo 10 tap ognuno
Ogni registro fornisce 4 input a una funzione non lineare
Chiave:
–
La chiave è di 112 bit
Gifford
•
Storia:
–
–
•
Cifrario a flusso ideato da David Gifford
Usato per criptare notizie nelle linee di Boston (1984-1988)
Caratteristiche:
–
–
Utilizza un singolo registro a 8 byte(b0 b1b 2…b7)
Lavora in OFB(Output feedback)
Gifford
•
Algoritmo:
Per generare un byte della chiave(Ki):
– Concatenare b0 b2 e b4 b7 ed effettuarne il
prodotto per ottenere un numero a 32 bit.
– Il terzo byte dalla sinistra è Ki
Per aggiornare il registro:
–
–
–
–
•
prendere b1 e shiftarlo di un bit a destra
prendere b7 e shiftarlo di un bit a sinistra
Prendere lo XOR di b1 modificato, b7 modificato, b0
Shiftare il registro originale di un byte a destra e posizionarlo a
sinistra al posto di b0
Attacchi:
– Rotto nel 1994
Gifford
• Come trovare un byte della chiave:
Gifford
• Aggiornare il registro(1):
Gifford
• Aggiornare il registro (2):
PKZIP
• Storia:
– Progettato da Roger Schlafly come algoritmo per il
programma di compressione PKZIP
• Caratteristiche:
– Utilizza un cifrario a flusso che cripta un byte alla volta
– Usa 3 variabili da 32 bit inizializzati così:
K0 = 305419896
K1 = 591751049
K2 = 878082192
inoltre ha una chiave a 8 bit, K3 derivata da K2
PKZIP
• Sicurezza:
– Un attacco richiede da 40 a 200 byte per sapere il testo in
chiaro ed ha complessità 227.
\Registri a scorrimento non lineare
• È facile immaginare un feedback più complicato di quello
usato nei registri lineari
• Il problema è che non c’è nessuna teoria matematica che li può
analizzare
• In particolare i problemi dei non lineari sono i seguenti:
– Ci possono essere più uno che zeri oppure meno run di quanti ci si
aspetti
– Il massimo periodo della sequenza può essere molto minore di quanto
ci si aspetti
– Il periodo della sequenza potrebbe essere diverso per diversi valori di
partenza
– La sequenza potrebbe apparire casuale per un po’ per poi terminare in
un singolo valore
– La funzione di feedback potrebbe essere in una qualsiasi forma