Sicurezza nel GSM e Smart Card
A cura di Marco Canu Marco Cascianelli
Luca de Angelis
Emanuele Garuglieri
Paola Ranaldi
Storia e panoramica sull’architettura GSM
A cura di
Marco Cascianelli
Cronologia
1921 – il Dipartimento di Polizia di Detroit sperimenta comunicazione one-way centrale-volanti
1935 – E.H.Armstrong inventa la Frequency Modulation (la modulazione varia proporzionalmente al segnale
analogico da trasmettere, segnale modulante, come
frequenza di un segnale sinusoidale ausiliario). Già tra la
fine degli anni 40 fu evidente la mancanza di un numero
sufficiente di canali radio per soddisfare le richieste di
tutti i settori
Cronologia
Fine anni 40 – singolo trasmettirore FM, copertura ristretta, commutazione manuale delle chiamate nella stazione radio. Banda di 120 KHz
Anni 60 – riduzione della banda necessaria a 60KHz
Anni 70 – riduzione della banda a 25 KHz
Passaggio ai sistemi trunked
z
I primi sistemi utilizzavano più trasmettitori indipendenti, con una frequenza fissa per ogni utente.
z
In seguito vennero introdotti i sistemi trunked, con selezione dinamica dei canali liberi –
inizialmente manuale ed in seguito
automatizzata
Sistemi a celle
z
Concepiti negli anni 40, sperimentati negli anni 60, commercializzati negli anni 80
z
invece di usare trasmettitori ad elevatra
potenza per coprire vaste ma limitate aree, servendo un numero ristretto di utenze,
usano stazioni distribuite su celle geografiche limitate
z
Ogni cella usa frequenze diverse da quelle
usate nelle celle adiacenti
Sistemi a celle
z
I trasmettitori necessitano di minore potenza per coprire una cella senza interferire con
quelle non adiacenti operanti alle stesse frequenze
z
I terminali mobili devono essere in grado di sintonizzarsi sulle frequenze relative alla cella
z
Il passaggio dalle frequenze di una cella a quelle della cella adiacente si chiama
handover
Collocazione delle celle
z
È importante trovare il giusto equilibrio tra grandezza delle celle e numero di
suddivisioni della banda.
z
Uno studio attento garantisce un numero non eccessivo di handover e basso rischio di
interferenza tra celle a fronte di una banda
necessaria limitata
Collocazione delle celle
z
Il territorio viene suddiviso in aree (celle) adiacenti, che
utilizzano un numero ridotto di frequenze.
z
La grandezza delle celle può variare per esigenze relative al servizio richiesto o alla
conformazione del territorio
TACS
z
Acronimo di Total Access Communication System 1979 – AMPS negli USA (Advanced Mobile Phone
Standard)
1981 – NMT nei paesi scandinavi (Nordic Mobile Telephone)
1985 – TACS in Gran Bretagna
z
1000 canali; 890-960 MHz
z
ETACS: 1320 canali; 872-950 MHz
1990 – in Italia viene adottato l’ETACS a seguito della
saturazione del sistema RTMS
TACS – limiti
z
Standard diversi incompatibili in vari paesi
z
Roaming internazionale limitato per sicurezza e incompatiblità
z
Sfruttamento inefficiente della banda, limite di utenze gestibili per zona (segnale analogico)
z
Bassa qualità del segnale dovuta alla sensibilità al rumore
z
Grande numero di ricetrasmettitori necessari, per l’alto numero di canali
z
Costi alti dei terminali, per l’impossibilità di politiche commerciali di scala (standard incompatibili)
z
Impossibile autenticare un terminale
z
Impossibile criptare il segnale, e trasmettere dati
GSM
1982 – La CEPT crea il Group Special Mobile 1985 – Il GSM sceglie definitivamente la via del
digitale
z
TDM – Time Divisione Multiplexing
z
Bassa sensibilità al rumore (=> celle più piccole=>più utenze possibili)
z
Cifratura dei messaggi
z
Identificazione con chiave segreta degli apparati
z
Trasmissione dati
z
980-915 MHz, 935-960 MHz
GSM
1987 – Memorandum of Understanding, per apertura del servizio nel 1991
1989 – GSM passa all’ETSI, viene rettificato il
significato dell’acronimo: Global System for Mobile Communications
1990 – phase 1: prime specifiche
1993 – phase 2: integrazione servizi supplementari
z
36 reti GSM in 22 paesi
z
Con DCS1800 e PCS1900 80 paesi attualmente usano
GSM
Architettura GSM
Mobile Station
Base Station Subsystem
(gestione della copertura radio)
Base
Transceiver Station
Base Station Controller
Operation Support Subsystem
Network Service
Management Centre
Operation and
Manintenance Centre
Network Subystem
Home Location Register
Equipment Identity Register
Rete GSM
Autentication Centre
Mobile service
Switching Centre Visitor Location Register
Unico canale protetto
Architettura GSM
SS7
Um
HLR
MSCVLR
BTS
BSC
BTS
Abis Abis
BTS
BSC
BTS
Abis Abis
MSCVLR
BTS
BSC
BTS
Abis Abis
BTS
BSC
BTS
Abis Abis A
A
AuC
A A
Um
Um: cifrata Abis: non cifrata
SS7 SS7 : rete di segnalazione
SS7
Procedura di chiamata
z
Verso MS:
z
Utente PSTN compone MSISDN
z
Il GMSC richiede all’HLR la posizione dell’abbonato
z
L’HLR ottiene dal VLR l’MSRN
z
Il GMSC usa l’MSRN per l’instradamento verso l’MSC da cui dipende l’utente mobile
z
L’MSC ottiene dal VLR il LAI che identifica le BSS a cui inviare la “paging request”
z
La MS risponde alla ricerca inviando alla BSS una “channel request”
z
La MS usa il canale ottenuto per inviare una “paging
response”
Procedura di chiamata
z
La BSS invia la “paging response” al VLR tramite l’MSC associato
z
L’MSC riceve dal VLR una “complete call” che rimanda alla MS tramite BSS
z
L’MS invia al MSC una “call confirmation”
z
L’MSC, tramite il GMSC, fa arrivare alla PSTN il tono di chiamata
z
L’MSC assegna un canale di chiamata alla BSS, che a sua volta ne assegna uno alla MS
z
La MS squilla; appena l’utente risponde l’MS invia una
“connect” all’MSC che invia una “answer” al PSTN tramite GMSC
z
MSC e GMSC interconnettono il canale GSM e il circuito
PSTN e la chiamata ha corso
Procedura di chiamata
z
Da una MS (ala rete telefonica)
z
La MS trasmette alla BTS una “channel request”
z
La BSS manda una “request for service” alla MSC
z
L’MSC ottiene dal VLR info sull’abbonato
z
L’MS manda una “setup” con le informazioni necessarie alla MSC
z
L’MSC ottiene dal VLR in risposta alla “setup” una
“complete call”, e comunica alla MS una “call
proceeding”
Procedura di chiamata
z
L’MSC assegna un canale alla BSS, che ne assegna uno a sua volta alla MS
z
L’MSC contatta la PSTN, e al “address complete message” fa giungere il tono di chiamata
all’utente mobile
z
Quando dalla PSTN giunge una “answer” l’MSC
connette il canale GSM al circuito PSTN, e la
chiamata ha corso
Procedura di handover
L’handover è gestito dalle BSC con i dati
continuamente inviati dalla MS sulla qualità del segnale e sulla posizione della MS stessa Gli algoritmi di handover producono sempre
una lista di celle candidate a partire dalla
migliore
Procedura di handover
Tra celle sotto lo stesso BSC:
z
La BSC invia una “handover command” con le informazioni sul nuovo canale
z
La MS cambia canale e invia una “handover
completed”
Procedura di handover
Tra BSC sotto lo stesso MSC
z
La BSC invia una “handover required” alla MSC
z
L’MSC invia l’”handover request” all’altra BSC, la quale predispone un canale per la MS
z
L’MSC invia tramite la BSC d’origine un
“handover command” alla MS
Procedura di handover
Tra BSC sotto MSC differenti
z
Il BSC di partenza invia un “handover required”
all’MSC
z
L’MSC contatta l’altro MSC, il quale ottiene dal VLR un numero di istradamento per la connessione tra MSC
z
Il secondo MSC fa predisporre la BSC necessaria e manda le info all’MSC di partenza
z
L’MSC di partenza attiva la connessione i istruisce
la MS per il passaggio di canale
Canali radio
z
890-915 MHz (25 MHz) per uplink
z
935-960 MHz (25 MHz) per downlink
z
Le portanti uplink e downlink sono scelte a 45Mhz di distanza
z
Tra due canali radio adiacenti ci devono essere 200 KHz
z
Totale di 124 canali in entrambe le direzioni
Canali logici
MS Broadcast channels BTS
Common control channels
Dedicated control channels
bcch bcch
fcch sch
pgh rach agch
sacch facch sdcch
GSM Burst
Il burst è un quanto di trasmissione GSM
z
Normal burst: traffico e controllo
z
57 bit information
z
26 bit training sequence
z
0.031 ms guard period
z
6 bit tail bit
GSM Burst
z
Frequency correction burst: fcch
z
142 fixed bit
z
Synchronization burst: sch
z
64 bit sync sequence
z
39 bit coded information: frame tdma e id BTS
z
6 bit tail bit
z
8,25 bit guard period
GSM Burst
z
Access burst: racch, primo accesso alla BTS
z
41 bit training sequence
z
36 bit coded information
z
8 e 3 bit head bit e tail bit
z
68,25 guard period
z
Dummy burst
z
Burst privo di informazioni usato nel bcch
Problemi dell’interfaccia aerea
z
Perdite da spazio libero: attenuazione
funzione del quadrato della distanza e del quadrato della frequenza
z
Perdite da ostruzione
z
Propagazione multipercorso (Rayleigh
fading)
Ottimizzazione dell’interfaccia aerea
Codifica del canale: frame da 260 bit (20ms di conversazione)
z
50 bit più importanti: classe 1a, 3 bit di parità
z
132 bit media importanza: classe 1b, 4 bit di coda
z
78 bit meno importanti: classe 2a
Dopo la codifica di canale dei bit di classe 1, i 189 bit
vengono convoluti con r=1/2; i 378 bit ottenuti, con i
78 di classe 2, formano il frame di 456 bit
Ottimizzazione dell’interfaccia aerea
Interleaving: suddivisione del frame da 456 bit in 8 blocchi da 57 bit con distribuzione
uniforme; i primi 4 blocchi vengono spediti in
prima posizione nei primi 4 burst. I successivi
4 vengono spediti in seconda posizione dei
successivi 4 burst
Ottimizzazione dell’interfaccia aerea
Equalizzazione: sulla base della sequenza di training viene per quanto possibile dedotta la distorsione da Rayleigh fading
Time advance: i tre time slot di compensazione tra trasmissione e ricezione possono essere ridotti di massimo 63 bit per compensare
eventuali ritardi di trasmissione (tramite
sacch 2 volte al secondo)
Ottimizzazione dell’interfaccia aerea
Frequency hopping: ad ogni time slot viene scelta la frequenza con miglior campo
Modulazione GMSK: ad ogni bit di trasmissione le frequenze di 0 e 1 vengono “shiftate” di
esattamente 180°; inoltre un filtro gaussiano
viene applicato a monte dello sfasamento per
ridurre le componenti fuori banda, di disturbo
per i canali adiacenti
Le Sim Card e MD5
A cura di
Emanuele Garuglieri
Sim Card
Acronimo di Subscriber Identity Module.
Funzioni:
z Identificare l’utente del servizio GSM
z Contenere dati
z Crittare la conversazione
In quanto evoluzione nel campo della telefonia delle Smart Card non ha solo funzioni di storage ma anche funzioni computazionali
Punto di Forza:
z Autosufficienza
Sim Card:
Struttura fisica
Composta da tre elementi:
z Supporto plastico
z Circuito stampato
z Circuito integrato
Comunicazione con l’esterno tramite appositi pin
I requisiti di resistenza sono definiti nel documento ISO7816.
Sim Card:
Il Chip
La capacità di una qualsiasi smart card (la sim in questo
contesto) deriva dal suo
circuito integrato, solitamente composto da:
z Microprocessore
z Rom (contiene l’OS)
z Ram (utilizzata come in tutti i calcolatori)
z Eeprom (con funzioni di storage)
Sim Card:
Interfaccia SIM-Mobile Station
Scambio di dati a 9600 bit/s tramite una linea seriale bidirezionale utilizzata in modalità half duplex.
Questo pemette di evitate attacchi massici alla carta.
Sim Card:
Chiavi
Dentro ad ogni sim card c’è un area di sistema che può
contenere differenti chiavi di sicurezza, e per ciò segrete.
Ciclo di vita e chiavi correlate:
z Nella fase di fabbricazione viene aggiunto un chiave di fabbricazione KF, unica, che deriva da una master key (MK) del produttore.
z Nella fase di pre-personalizzazione la chiave di fabbricazione viene
rimpiazzata da una chiave personalizzata, KP, dopodichè verrà attivato un blocco delle personalizzazioni(Vper), inoltre vengono disabilitate le istruzioni di accesso fisico alla memoria.
z Nella fase di personalizzazione vengono scritti i dati e le applicazioni sulla card e vengono inseriti i codici PIN e PUK e viene scritto un blocco Vutil.
z Nella fase di utilizzo è possibile modificare il codice PIN ma non il PUK e le politiche di sicurezza sono gestite dall’applicazione.
Sim Card:
Invalidazione
Per invalidare una sim card ci sono due modi:
z
L’applicazione scrive un blocco di invalidazione sul file principale
z
Il sistema di controllo blocca irreversibilmente l’accesso,
il PIN e il PUK sono stati inseriti errati.
Sim Card
Struttura logica
File organizzati in maniera gerarchica per mezzo di directory:
z Master File (MF) è la “root” del file system, ed è selezionato
automaticamente al reset.
z Elementary File (EF) sono I
“repository” dei dati.
z Dedicated File (DF) sono le
“directory” del file system e
possono contenere sia DF che “EF”.
Esse consentono di installare più di un’applicazione all’interno della
Smart Card.
MF
DF 0 EF 00
EF 0n EF 0
EF n
DF n
EF n0
EF nn
DF n0 EF n00
EF n0n
Sim Card
Controllo degli Accessi
Il principio fondamentale di controllo di accesso è basato sulla corretta presentazione dei PIN e sulla loro gestione.
Ad ogni file è associato una intestazione che
indica le condizioni o i requisiti di accesso e
lo stato corrente.
Sim Card
Livelli di accesso
Esistono vari livelli di accesso:
z
Always: nessuna restrizione
z
Never: l’accesso al file è proibito
z
Card Holder Verification 1: CHV1 regola l’accesso, il PIN1 è stato inserito
z
Card Holder Verification 2: CHV2 regola l’accesso, il PIN2 è stato inserito
z
Administrative: l’allocazione dei livelli e i relativi requisiti
sono sotto la responsabilità di una appropriata autorità
amministrativa
Sim Card PIN e PUK
Personal Identifier Number: serve per accedere alle funzionalità e ai dati della smart card.
Se inserito in maniera scorretta un numero n di volte necessita di un’altro codice di sblocco (PUK).
Se anche quest’ultimo viene inserito errato un numero n di volte, successive, provoca il Blocco Irreversibile,
eventualmente invalidando permanentemente la carta.
Sim Card
Capacità Crittografiche
Utilizzo del DES e del tripleDES
Punto debole :Ampiezza di banda dell’ interfaccia seriale
Soluzione:nessuna, codifica simmetrica lenta.
Sim Card
Capacità Crittografiche
Utilizzo del RSA con chiave tra 512,768 e 1024 bit.
Punto debole: Capacità computazionali elevate
Soluzione:Teorema cinese del resto
La chiave è memorizzata nell’Eeprom e non è accessibile dall’esterno.
Oltre al RSA vengono utilizzati anche i DSA che si
basano su algoritmo MD5 che è una evoluzione del
MD4
Sim Card
Capacità Crittografiche –MD5
Message Digest (MD5) – Ron Rivest
Funzione hash che dato un messaggio in input genera una sequenza (fingerprinter) di lunghezza fissa (128 bit).
MD5 è una funzione hash one-way, cioè:
z dato un qualsiasi M, deve essere computazionalmente semplice calcolare H(M);
z dato un qualsiasi h, deve essere computazionalmente impraticabile calcolare un M tale che h = H(M);
Corollario:
Funzione hash senza collisioni
Una funzione di hash sicura deve essere senza collisioni (collision-resistant):
z dato un qualsiasi M, deve essere computazionalmente impraticabile trovare un M’≠ M tale che H(M’) = H(M) (funzione debolmente senza collisioni);
z deve essere computazionalmente impraticabile trovare una coppia (M, M’), con M’≠ M, tale che
H(M) = H(M’) (funzione fortemente senza collisioni).
L’idea è che, anche se necessariamente esistono
messaggi diversi che producono lo stesso hash, non
è praticabile trovarli .
Corollario:
Attacco ad una funzione hash
Le due proprietà sull’assenza di collisioni (debole e forte), corrispondono a due diversi tipi di attacchi a forza bruta:
z attacco a forza bruta “semplice”: trovare un messaggio che produca un dato hash (cioè un hash uguale a quello di un
messaggio dato);
z attacco del compleanno (birthday attack): trovare due messaggi che producano lo stesso hash, indipendentemente dal valore di questo hash.
La complessità dei due attacchi è molto diversa!
z se l’hash è lungo m bit, la complessità del primo è 2m, quella del secondo è 2m/2.
Sim Card
Capacità Crittografiche –MD5
MD5 è una funzione hash sicura
Sim Card
Capacità Crittografiche –MD5
Algoritmo di preprocessamento:
1- Il messaggio N viene riempito (padding) con altri bit in modo da diventare N=64 mod 512. Il padding è un 1 seguito da 0 fino a soddisfare la regola enunciata precedentemente. Se la misura originale è già corretta si aggiungono comunque 512 bit.
2- Viene aggiunto una sequenza di 64 bit che rappresenta la
lunghezza del messaggio in input prima dello svolgersi del punto 1.
3- Dividiamo il messaggio in blocchi di 512 bit ed ogni blocco in 16 sottoblocchi mj da 32 bit.
In questo modo otteniamo dei blocchi di 512 bit che andranno
processati singolarmente tramite la funzione hash e il cui risultato sarà l’input della iterazione successiva. Con questo preprocesso ci assicuriamo che due messaggi (diversi) non vengono rappresentati nello stesso modo.
Sim Card
Capacità Crittografiche –MD5
Algoritmo:
1- 4 registri da 32 bit che rappresentano il digest vengono inizializzati con le seguenti 4 sequenze:
A = 0x01234567 B = 0x89abcdef C = 0xfedcba98 D = 0x76543210
Dette Variabili di concatenamento (chaining variables). Ad ogni passo si fornisce il digest al passo successivo come input.
2- Copia il contento dei registri in 4 variabili a,b,c,d
3- Applica una funzione fp scelta tra 4 (F,G,H,I) a 3 registri scelti tra a,b,c,d
4- Aggiungi al quarto registro il risultato ottenuto nel passo 3
5- Somma il sotto-blocco di testo del messaggio, mj, al risultato ottenuto nel punto 4
Sim Card
Capacità Crittografiche –MD5
6- Somma un valore costante Ti al risultato del punto precedente 7- Effettua una rotazione Sk verso destra, considerando il registro
come circolare.
8- Sommo al risultato del passo 7 una delle altre tre variabili (in mod 232) e pongo il risultato al posto di quest’ultima, sostituisco il
contenuto di ognuna delle altre tre con quella alla sua sinistra
9- ripeti 16 volte dal passo 3 al 8 con la stessa funzione scelta la prima volta e variando j e i
10- ripeti 4 volte dal passo 3 al 9 con una funzione hash diversa da quella o quelle utilizzate precedentemente, azzerando j e variando i e k.
11- somma i contenuti delle variabili a,b,c e d ai rispettivi registri A,B,C e D.
12- ripeti per ogni blocco di 512 bit dal passo 2 al 11.
13- concateno i registri A,B,C,D e ottengo il message digest.
Sim Card
Capacità Crittografiche –MD5
La funzione fp è scelta tra le seguenti:
z
F(x,y,z) = (x and y) or (not x and z)
z
G(x,y,z) = (x and z) or (y and not z)
z
H(x,y,z) = x xor y xor z
z
I(x,y,z) = y xor (x or not z).
Sim Card
Capacità Crittografiche –MD5
mj Tk
Sim Card
Capacità Crittografiche –MD5
Punti di forza del MD5:
z Sicurezza: E’ computazionalmente difficile trovare due messaggi che danno lo stesso valore di hash.
z Sicurezza Diretta: MD5 non è basato su nessuna assunzione, come la difficoltà della fattorizzazione.
z Velocità: MD5 è integrabile per software ad alta velocità.E’ basata su semplici manipolazioni sui bit.
z Semplicità e Compattezza: MD5 è semplice, senza strutture dati e programmi complicati.
MD5 è stato attaccato con parziale successo da den Boer and Bosselaers.
Idea: Evoluzione SHA.
DSS e Teorema Cinese del Resto
A cura di
Luca de Angelis
Teorema Cinese del Resto (1)
Def: Siano m ed n due naturali primi tra loro; siano a,b ∈ ℤ. Allora il sistema di congruenze seguente, ha una soluzione in ℤ.
Inoltre, se x0 ∈ ℤ è una soluzione, le soluzioni del sistema sono tutti e soli gli interi x con:
⎩ ⎨
⎧
≡
≡
) (mod
) (mod
m b
x
n a
x
)
0
(mod mn
x
x ≡
Teorema Cinese del Resto (2)
z
Dimostrazione (prima parte):
1) Soluzioni intere del tipo x=b+km, con k numero intero, se e solo se b+km è congruo a(mod n);
2) Poiché m ed n sono primi tra loro, segue che m ha inverso in
ℤ
n;3) Si calcola il numero k0:= m-1(a-b) e si moltiplica tutto per m;
4) Quindi si ha mk0=(a-b), cioè congruo ad (a-b)(mod n);
5) Segue che b+ mk0 è congruo ad a(mod n);
6) Da qui si trova x0 := b+ mk0 è una soluzione del sistema.
Teorema Cinese del Resto (3)
z
Dimostrazione (seconda parte):
7) Sia x0 la soluzione precedente.
8) Un intero x è soluzione del sistema se e solo se è congruo ad x0 (mod n) e ad x0 (mod m);
9) Cioè se e solo se (x - x0) = m e (x - x0) = n;
10) Essendo m ed n primi tra loro questo si verifica se e solo se (x - x0) = mn = mn
11) Ossia se e solo se x è congruo ad x0 (mod mn). Cvd.
Teorema Cinese del Resto (4)
Def: Siano dati r numeri naturali n1, n2, …., nr a due a due primi tra loro;
sia n = n1n2…nr. Siano inoltre a1, a2, …, arr numeri interi. Allora il sistema di congruenze lineari
ha una soluzione in ℤ. Se l’intero x0è una soluzione, allora le altre soluzioni del sistema sono tutti e soli gli interi x con:
r i
n a
x ≡
i(mod
i), 1 ≤ ≤
) ...
(mod
1 20
n n n
rx
x ≡
Digital Signature Standard (DSS)
z
E’ uno standard per l’autenticazione e la firma digitale proposto dal NIST in collaborazione con l’NSA
z
Il DSS non è un algoritmo, ma specifica una serie di algoritmi da utilizzare per implementarlo:
z DSA (raccomandato dal NIST)
z RSA
z ECDSA
z
Viene anche specificata quale funzione hash utilizzare per comprimere il messaggio e per generare la firma:
z SHA-1 (specificata nel relativo standard: SHS)
Digital Signature Alghoritm (DSA) (1)
z
Parametri:
z
p = numero primo, tale che 2
L-1<p<2
Lcon 2
1023≤L≤2
1024;
z
q = numero primo, divisore di p-1 con 2
159<q<2
160;
z
g = h
(p-1)/qmod p, dove h è un intero e 1<h<p-1 tale che h
(p-1)/qmod p>1;
z
x = intero casuale o pseudocasuale con 0<x<q
z
y = g
xmod p
z
k = intero casuale o pseudocasuale con 0<k<q
Digital Signature Algorithm (DSA) (2)
z
I parametri p, q e g sono pubblici e possono essere condivisi con un gruppo di utenti
z
x e y sono rispettivamente la chiave privata e la chiave pubblica
z
k e x sono usati per generare la firma. Anche k deve essere segreto e viene rigenerato
ogni volta
Generazione della firma
z
La firma è la coppia di valori (r,s) così definiti:
z
r = (g
kmod p)mod q;
z
s = (k
-1(SHA-1(M)+xr)mod q.
z
SHA-1(M) è una stringa di 160 bit che è l’output della funzione hash;
z
k
-1è l’inverso moltiplicativo
di k, mod q;
Verifica della firma (1)
z
Il destinatario conosce p, q, g e la chiave pubblica del mittente e riceve M’, r’, s’:
z
Se non è 0<r’<q e 0<s’<q allora la firma è violata;
z
w = (s’)
-1mod q;
z
u
1= ((SHA-1(M’))w)mod q;
z
u
2= (r’w) mod q;
z
v = ((g
u1y
u2mod p) mod q.
z
Se v=r’ la firma è corretta!
Verifica della firma (2)
Teo: Se nella firma ricevuta M’=M, r’=r e s’=s allora v=r’
Dimostrazione:
z
Si ha che:
1. w = (s’)-1mod q = s-1mod q e s = (k-1(SHA-1(M)+xr)mod q segue che:
(SHA-1(M)+xr)w mod q = k mod q;
2. u1 = ((SHA-1(M’))w)mod q = (SHA-1(M)w)mod q;
3. u2 = (r’w) mod q = rw mod q;
z Essendo y = g
xmod p:
4. v = ((gu1yu2mod p) mod q = (g(SHA-1(M)+xr)wmod p) mod q = (gk mod p) mod q = r = r’. Cdd.
Critiche a DSA
z
Non può essere usato per la crittazione e la distribuzione di chiavi Æ Vero
z
E’ stato sviluppato dall’NSA, quindi ci potrebbe essere una trapdoor Æ Forse
z
E’ più lento di RSA Æ Sì e No
z
RSA è uno standard de facto Æ Vero
z
Può essere coperto da licenze Æ Vero
z
La chiave è troppo corta Æ Era Vero
Confronto DSA-RSA
10 sec 1.5 sec
16 sec
Verifica della firma
0.03 sec 15 sec
0.03 sec
Generazione della firma
4 sec N/A
14 sec
Precalcolo
4 sec Secret
14 sec
Generazione della chiave
DSA con p, q, g in comune RSA
DSA
Secure Hash Standard (SHS)
z
Questo standard specifica 4 algoritmi hash sicuri, da utilizzare negli standard di firma digitale:
z
SHA-1;
z
SHA-256;
z
SHA-384;
z
SHA-512.
z
Sono sicuri perché sono unilaterali, e sono sia debolmente che fortemente senza
collisioni
Secure Hash Alghoritms
z
Ognuno dei 4 algoritmi può essere descritto in due passi:
z
Preprocessamento;
z
Calcolo dell’hash.
z
Gli algoritmi si differenziano principalmente per:
z
Lunghezza del messaggio di input;
z
Lunghezza del message digest;
z
Lunghezza dei blocchi e delle word utilizzati dalle funzioni interne;
z
Sicurezza rispetto all’attacco del compleanno.
SHA - Proprietà
256 512
64 1024
<2128 SHA-512
192 384
64 1024
<2128 SHA-384
128 256
32 512
<264 SHA-256
80 160
32 512
<264 SHA-1
Security (bit) MD Size
(bit) Word
Size (bit) Block
Size (bit) Message
Size (bit)
SHA-1 Preprocessamento
z
Il preprocessamento deve essere eseguito prima del calcolo della funzione hash
z
Si può dividere in tre sotto-passi:
1. Padding del messaggio M;
2. Parsing del risultato in blocchi;
3. Setting dei valori iniziali.
SHA-1 Padding
z
Lo scopo di questa operazione è far sì che la lunghezza del messaggio ottenuto sia un
multiplo di 512 bits
z
Se la lunghezza del messaggio M è di l bits, si aggiunge un “1” seguito da k zeri, con:
l + 1 + k = 448 mod 512
z
Rimangono 64 bit che servono ad esprime la
lunghezza del messaggio iniziale.
SHA-1 Parsing
z
Lo scopo di questa operazione è dividere il messaggio ottenuto precedentemente in N blocchi di m bits
z
In questo caso si divide in N blocchi da 512 bit: M
(1), M
(2), …, M
(N)z
Ogni blocco è diviso in 16 word da 32 bit.
Quindi l’i-esimo blocco si può esprimere in:
M
0(i), M
1(i), …, M
15(i)SHA-1 Settings
z
Lo scopo di questa operazione è di settare il valore iniziale H
(0)dell’hash
z
In questo caso si hanno 5 word da 32 bit:
H
0(0)= 0x67452301
H
1(0)= 0xefcdab89
H
2(0)= 0x98badcfe
H
3(0)= 0x10325476
H
4(0)= 0xc3d2e1f0
SHA-1 Calcolo dell’hash
z
E’ un algoritmo iterativo: l’hash di un passo dipende dall’hash del passo precedente; ogni iterazione calcola dei valori di A,B,C,D,E che vengono sommati ai successivi
z
Ogni passo è composto da 4 round con 20 operazioni ciascuno;
z
Ogni operazione è fatta da una funzione su tre variabili,
scorrimenti ed addizioni simili ad MD5
SHA-1 Funzioni e Costanti
z Ognuna delle 4 funzioni vale solo per 1 round e sono così definite (in ordine):
z Sono usate 4 costanti. Una diversa per ogni round di un passo:
⎪ ⎪
⎩
⎪⎪ ⎨
⎧
⊕
⊕
=
∧
⊕
∧
⊕
∧
=
⊕
⊕
=
∧
¬
⊕
∧
=
=
z y
x z
y x Parity
z y z)
(x y)
(x z
y x Maj
z y
x z
y x Parity
z) x
( y) (x
Ch(x,y,z) z
y x f
t) , , (
) (
) , , (
) , , ) (
, , (
⎪⎪
⎪⎪
⎪
⎩
⎪⎪
⎪⎪
⎪
⎨
⎧
=
•
=
•
=
•
=
•
=
6 1 62 4 2
10
1 8 4 2
5
1 9
6 4 2
3
827999 5
4 2 2
32 32 32 32
d c ca
bbcdc f
eba ed
a
K t
SHA-1 Schema Operazione
SHA-1 Algoritmo (1)
1.
Si entra ne ciclo principale (FOR i=1 to N). Il blocco i-esimo M
(i)è esteso fino a 80 word da 32 bit W
0, W
1, …, W
79in
questo modo:
1. Wt = Mt, con t = 0…15
2. Wt= (Wt-3⊕Wt-8 ⊕Wt-14 ⊕Wt-16)<<<1, con t = 16…79
2.
Si inizializzano 5 variabili a, b, c, d, e con i rispettivi valori dell’hash precedente
3.
Si entra nel ciclo interno:
FOR t=0 to 79
TEMP = (a<<<5)+ft(b,c,d)+e+Wt+Kt e = d
d = c
c = b<<<30 b = a
a = TEMP
SHA-1 Algoritmo (2)
4. Si calcola l’i-esimo hash intermedio H
(i):
H0(i) = a + H0(i-1) H1(i) = b + H1(i-1) H2(i) = c + H2(i-1) H3(i) = d + H3(i-1) H4(i) = e + H4(i-1)
5. Alla fine il Message Digest viene calcolato
concatenando i valori riportati dal passo n-esimo:
H0(N) || H1(N) || H2(N) || H3(N) || H4(N)
z Il risultato finale è una stringa di 160 bit
SHA-1 Sicurezza
z
Finora non si conoscono attacchi contro SHA-1
z
Poiché produce un Message Digest di 160 bit, è più sicuro agli attacchi brute force degli algoritmi che producono MD a 128 bit (in
primis MD4 e MD5)
SHA-1 vs MD5
Il modello di sicurezza nel GSM
A cura di
Paola Ranaldi
Introduzione
Tutto l'intero costrutto per la sicurezza si fonda su criteri inerenti
l'identificazione dell'abbonato, introdotti specificamente con il sistema GSM.
L'abbonato è identificato univocamente dal codice IMSI che, unitamente alla chiave personale di autenticazione Ki, costituiscono le credenziali di
identificazione. L'innovazione particolare è che le procedure di
autenticazione e crittografia al fine di garantire maggiore sicurezza e
protezione nel sistema si esplicano in modo che queste informazioni non vengano trasmesse sul canale radio.
Precisamente, per l'autenticazione si utilizza un meccanismo di tipo
challenge-response, mentre per la crittografia dei dati trasmessi si adotta una chiave di sessione Kc, ed anch'essa non viene mai trasmessa sul
canale radio.
Mobile Station (MS)
z Mobile Equipment(ME):
Dispositivo mobile fisico Identificatori:
IMEI – International Mobile Equipment Identity z Subscribe Identity Module(SIM)
Smart Card che contiene le chiavi, gli identificatori e gli algoritmi Idenificatori:
Ki– chiave di identificazione del sottoscrittore
IMSI – International Mobile Subscriber Identity
TMSI – Temporary Mobile Subscriber Identity
MSISDN – Mobile Station International Service Digital Network
PIN – Personal Identity Number protecting a SIM
LAI – location area identity
¾ Il modello di sicurezza del GSM è basato su un segreto condiviso tra l’HLR della rete di appartenenza del sottoscrittore e la carta SIM del sottoscrittore: Ki
Gli algoritmi
z
Algoritmo di autenticazione della MS (A3)
z
Algoritmo di generazione della chiave di sessione (A8)
z
Algoritmo di autenticazione e generazione della chiave di sessione (COMP128)
z
Algoritmo di cifratura (A5)
Autenticazione della MS (A3)
e generazione di Kc di sessione (A8)
z Quando la MS vuole comunicare con la rete GSM,entrando nell’area di una MSC invia una richiesta di accesso alla BTS che la inoltra alla MSC
z Alla richiesta di identificazione della MS alla rete, l’HLR fornisce alla MSC cinque tuple contenenti:
RAND, un numero casuale a 128 bit
SRES, calcolata su RAND e sulla chiave Ki , utilizzando l’algoritmo A3
Kc, la chiave di sessione. Essa viene calcolata mediante l’algoritmo A8 che prende in input RAND e ki
z L’MSC invia la RAND della prima tupla alla MS
RETE GSM
SIM RICHIESTA D’ACCESSO
GEN. RANDOM
RAND
ki
A3
RAND
SRES
Ki
A3
A8 A8
KC IMSI / TMSI
TRATTA RADIO
Autenticazione della MS (A3)
e generazione di Kc di sessione (A8)
z La MS calcola una SRES con l’algoritmo A3 utilizzando la RAND ricevuta dalla MSC, e la chiave Ki che risiede nella SIM
z La MS invia la SRES alla MSC
z La MSC confronta la SRES inviatagli dalla MS con quella contenuta nella tripla del HLR
z La MS calcola la chiave di sessione Kc mediante l’algoritmo A8 che prende in input RAND e ki
RETE GSM
SIM RICHIESTA D’ACCESSO
GEN. RANDOM
RAND
ki
A3
RAND
SRES
Ki
A3
A8 A8
SRES
SRES?= SRES
KC KC
TRATTA RADIO IMSI/TMSI
A8 A8
A5 A5
ki ki
kc kc
Fn Fn
XOR XOR
Data Data
RAND
La chiave di sessione kc viene usata per la codifica sul canale via etere.
La stessa kcviene utilizzata fin quando l’MSC non identifica nuovamente la MS, nel qual caso ne viene generata una nuova
Crittografia dei dati trasmessi ( A5)
RAND
Ciphertext
SIM OPERATORE
ME GSM
Elementi del sistema GSM
SIM: A3, A8;
IMSI\TMSI Ki
MS: A5 BTS: A5; Kc NS (Network Subsystem)
MSC AuC Æ VLR; HLR; EIR;
A3, A8
IMSI\TMSI, LAI, Ki
gen. Num. pseudocasuali
Sicurezza della rete
z La scelta di generare un numero casuale (RAND) è dovuta al fatto che se tale stringa non fosse generata, il valore SRES trasmesso dalla MS alla BTS sarebbe sempre lo stesso: si potrebbe dunque effettuare un attacco a ripetizione
z Sia l’A3 che l’A8 sono memorizzati nella SIM. Questo significa che l’operatore può decidere quali algoritmi utilizzare indipendentemente dai produttori di
hardware e dagli altri operatori. Infatti, l’autenticazione funziona anche negli altri paesi, poiché le reti locali chiedono le 5 triple all’HLR della rete di appartenenza
dell’abbonato. Così la rete locale non deve sapere niente riguardo gli algoritmi A3 ed A8 utilizzati.
z L’abbonato è identificato univocamente dal codice IMSI e dalla chiave personale di autenticazione ki
z Per la crittografia dei dati trasmessi si adotta una chiave di sessione Kc
Î per garantire maggiore sicurezza e protezione del sistema le procedure di
autenticazione e crittografia si esplicano in modo che IMSI, Ki e kc non vengano mai trasmesse sul canale radio
.
L’anonimato
z Quando una MS entra in un’area MSC diversa e accende il segnale radio utilizzando per la prima volta la SIM, obbligatoriamente viene usata la sua vera identità IMSI.
z Per proteggere l’IMSI di un utente suLl’interfaccia aerea L’IMSI, non appena conclusa con successo l’autenticazione, viene sostituita con un’identificazione provvisoria
TMSI, ed è proprio questa ad essere resa pubblica nella rete e ad essere utilizzata in tutte le comunicazioni successive
z Appena si conclude con successo l’autenticazione, la rete assegna alla SIM un TMSI e lo trasmette in forma cifrata alla MS dove poi viene decifrato
z L’MS risponde confermando l’avvenuta ricezione e memorizza Il TMSI nella SIM.
z Da questo momento, per tutte le comunicazioni successive, il codice TMSI è utilizzato al posto del codice IMSI
z Il codice TMSI è valido solo nella Location Area (LA) in cui è stato rilasciato. Per comunicazioni al di fuori della LA è necessario l’utilizzo del LAI in aggiunta al TMSI
z Ogni volta che si compie una Location Updating il VLR assegna una nuova TMSI alla MS e la invia insieme al messaggio che comunica l’esatto aggiornamento della
localizzazione (Location Updating Accept)
z Il codice TMSI, quando il processo di crittografia è stato attivato può essere riallocato anche in caso di altri accessi alla rete (TMSI ReallocationRequest-TMSI Reallocation Confirmation)
Comp128
Invece di utilizzare due algoritmi distinti, A3 ed A8, la maggior parte degli operatori GSM utilizza un unico algoritmo, chiamato
COMP128.
A3 A8
Ki (128 bit) , RAND (128 bit) Ki (128 bit) , RAND (128 bit)
SRES (32 bit) Kc (64 bit)
ALGORITMO DI
AUTENTICAZIONE
ALGORITMO DI GENERAZIONE
DELLA CHIAVE DI SESSIONE KC
Comp128
Invece di utilizzare due algoritmi distinti, A3 ed A8, la maggior parte degli operatori GSM utilizza un unico algoritmo, chiamato
COMP128.
Comp128
Ki (128 bit) , RAND (128 bit)
SRES (32 bit) , Kc (54 bit)
Comp128
1. Vengono creati:
z
Un array x[ ] formato da 32 byte
z
Un array bit[ ] formato da 128 byte
Negli ultimi 16 byte di x[ ] viene immesso RAND
presente in input
Comp128
2. Viene creata un’iterazione per cui per 8 volte vengono eseguiti
i seguenti passi:
Comp128
3. Viene creato l’array simoutput[ ] di 96 bit dei quali:
z
I primi 32 rappresentano SRES
z
Gli altri 64 ( di cui gli ultimi 10 sono sempre posti
uguali a zero) rappresentano la chiave kc
Comp128
z Il COMP128 e' considerato un algoritmo debole In generale anche gli altri algoritmi utilizzati dal GSM lo sono. Infatti:
z gli ultimi 10 bit della chiave di sessione kc sono posti uguali a zero.
Lo spazio delle chiavi si riduce da 264 a 254
.
Si è riscontrato che questo avviene in tutte le implementazioni di A3/A8, incluse quelle che non usano COMP128 per la generazione della chiave e sembra sia una caratteristica voluta.
z In realta' vi e' il forte e fondato sospetto che siano utilizzati proprio per questo. Durante il processo di standarizzazione del protocollo piu' volte diversi governi si espressero a favore di algoritmi deboli per rendere possibile l'intercettazione ed il controllo delle chiamate.
Algoritmo di cifratura A5
z L’algoritmo A5 è lo stream cipher utilizzato per cifrare i frame che vengono inviati via etere
z Ciascun frame contiene 114 bit e rappresenta una parte della comunicazione tra MS e BTS e viceversa.
z I cifratori di tipo stream cipher operano bit a bit producendo per ogni bit di testo in chiaro un singolo bit cifrato in uscita.
A5 A5
Kc (64 bit) Kc (64 bit)
Fn (22 bit) Fn (22 bit)
XOR XOR
Data(114 bit) Ciphertext (114 bit) Data (114 bit)
OPERATORE MS GSM
114 bit 114 bit
Algoritmo di cifratura A5
z Uno stream cipher è tipicamente implementato come un exclusive-or(XOR) tra il flusso dei dati ed una opportuna sequenza di bit chiave (keystream).
z L’efficacia in termini di sicurezza dipende quindi dalle proprietà della Keystream:
una keystream completamente casuale è certamente più efficace di una deterministica a breve periodo
A5 A5
Kc(64 bit) Kc (64 bit)
Fn (22 bit) Fn(22 bit)
XOR XOR
Data(114 bit) Ciphertext (114 bit) Data (114 bit)
OPERATORE MS GSM
keystream (114 bit) keystream (114 bit)
Algoritmo di cifratura A5
z Fn è il numero del frame da cifrare
z Kc viene utilizzata per tutta la sessione, durante la quale il numero del frame cambia
Î Viene generata un’unica keystream per ciascun frame
z Una telefonata può essere decifrata qualora l’attaccante conosca Kc in quanto il numero di frame viene trasmesso in chiaro
A5 A5
Kc(64 bit) Kc (64 bit)
Fn (22 bit) Fn(22 bit)
XOR XOR
Data(114 bit) Ciphertext (114 bit) Data (114 bit)
OPERATORE MS GSM
keystream (114 bit) keystream (114 bit)
Algoritmo di cifratura A5 I tre LFSR
z Il generatore delle keystream è costituito da 3 LFSR di lunghezze differenti.
Organizzati in modo non lineare, che corrispondono ai tre polinomi delle connessioni:
z X19 + x5 + x2 + x + 1
z x22 + x + 1
z x23 + x15 + x2 + x + 1
z Tali polinomi sono stati scelti primitivi in modo che i corrispondenti registri abbiano periodo massimale: il periodo massimo di un registro a K bit è 2k -1
Algoritmo di cifratura A5 I tre LFSR
z La lunghezza totale dei tre LFSR è di 64 bit.
Gli LFSR sono lunghi rispettivamente 19, 22 e 23 bit e le funzioni utilizzate sono polinomi di feedback sparsi.
z Tutti e tre i registri sono temporizzati in base al valore del loro bit centrale
Algoritmo di cifratura A5 I tre LFSR
z Ad ogni passo ciascun registro viene shiftato se il suo bit centrale concorda con il valore di maggioranza dei bit centrali dei tre registri. Per esempio, se i bit
centrali dei tre registri sono rispettivamente 0,1 e 1, gli ultimi due registri vengono shiftati, invece se i bit centrali sono rispettivamente 0, 1 e 0, allora vengono shiftati il primo ed il terzo registro. Così, ad ogni round, vengono shiftati almeno due registri.
Lo XOR dei bit meno significativi dei tre registri rappresenta un bit della keystream.
Algoritmo di cifratura A5 I tre LFSR: inizializzazione
z I tre LFSR vengono inizializzati con una combinazione non lineare della chiave di sessione Kc ed il numero di frame .
z I 64 bit di Kc vengono inizialmente caricati nei tre registri r1, r2 ed r3 bit a bit, in modo sequenziale. Durante il caricamento dei bit della chiave, la regola di shift dei registri che contengono i bit di maggioranza è disabilitata. Il caricamento dei bit viene mostrato nel seguente esempio:
