A5/1

Da Wikipedia, l'enciclopedia libera.
A5/1
A5-1 GSM cipher.svg
Struttura dell'A5/1 con i suoi 3 registri a scorrimento LFSR
Generale
Prima pubblicazione 1987
Successori A5/2
Dettagli
Dimensione chiave 64 bit
Dim. vettore di inizializazione 22 bit
Struttura registri a scorrimento a retroazione lineare
Numero di passaggi 64
Migliore crittanalisi
il cifrario è stato reingegnerizzato nel 1999

In crittografia l'A5/1 è un cifrario a flusso utilizzato per cifrare le comunicazioni effettuate con i telefoni cellulari GSM in Europa e Stati Uniti. L'algoritmo ha gravi vulnerabilità ed è stato più volte dimostrato come sia facile violarne la sicurezza. Inizialmente tenuto segreto, è stato reingegnerizzato nel 1999 da Marc Briceno lavorando su un telefonino GSM.

Storia e utilizzo[modifica | modifica wikitesto]

L'A5/1 fu sviluppato alla fine degli anni ottanta per proteggere le comunicazioni vocali della nascente telefonia mobile. Fu sviluppato nel 1987 e destinato inizialmente all'uso nella sola Europa; in seguito fu poi adottato anche negli USA. Nel 1989 ne fu sviluppata una versione deliberatamente più insicura denominata A5/2 e destinata all'uso in alcuni Paesi asiatici ritenuti pericolosi (un esempio è l'Iraq dove governava Saddam Hussein)[1]. Nel 1994 la struttura generale degli algoritmi divenne di pubblico dominio mentre nel 1999 gli algoritmi furono completamente reingegnerizzati da Marc Briceno tramite l'uso di un telefono GSM. Nel 2000 si stimava che circa 130 milioni di clienti GSM facevano affidamento sull'A5/1 per proteggere la confidenzialità delle loro comunicazioni vocali.

Il ricercatore sulla sicurezza Ross Anderson dichiarò nel 1994 che "ci fu una forte diatriba fra le SIGINT (le agenzie di intelligence preposte all'intercettazione dei segnali) di diversi Paesi della NATO alla metà degli anni '80 circa il fatto che la cifratura GSM dovesse essere forte o meno. Quelle tedesche affermavano di sì, dato che confinavano con diversi Paesi del Patto di Varsavia, ma molti altri Paesi non condividevano questa idea. Vinse quest'ultima linea di pensiero e fu adottato per l'algoritmo un progetto francese"[2]

Descrizione[modifica | modifica wikitesto]

Il cifrario a flusso A5/1 utilizza 3 registri LFSR. Un registro è sincronizzato se il suo bit di sincronizzazione (in arancio) coincide con il bit di sincronizzazione di maggioranza di tutti e tre i registri

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. I tre registri sono specificati come segue::

Reg.
LFSR
Lunghezza
in bit
Polinomio
caratteristico
Bit di
sincronizzazione
Bit
usati
1 19 x^{19} + x^{18} + x^{17} + x^{14} + 1 8 13, 16, 17, 18
2 22 x^{22} + x^{21} + 1 10 20, 21
3 23 x^{23} + x^{22} + x^{21} + x^{8} + 1 10 7, 20, 21, 22

I bit sono indicizzati con il bit meno significativo (least significant bit, o LSB) assunto essere lo 0.

I registri sono sincronizzati in una specie di "avvio/arresto" basato su una regola della maggioranza. Ogni registro ha un proprio bit di sincronizzazione: ad ogni ciclo il bit di sincronizzazione di tutti e tre i registri viene esaminato e viene determinato un bit di maggioranza. Un registro è sincronizzato se il suo bit di sincronizzazione coincide con il bit di maggioranza. Quindi ad ogni passaggio due o tre registri sono sincronizzazione, ed ogni registro avanza con una probabilità di 3/4.

Inizializzazione[modifica | modifica wikitesto]

Inizialmente i registri sono impostati a zero. Poi, per 64 passaggi, i 64 bit della chiave segreta sono mescolati secondo lo schema seguente: nel ciclo 0\leq{i}<64, l'i-esimo bit della chiave è aggiunto al bit meno significativo di ogni registro utilizzando uno XOR.

R[0] = R[0] \oplus K[i].

Ad ogni registro viene poi dato un colpo di clock. Similarmente, i 22 bit del numero di sessione sono aggiunti durante 22 cicli. Dopodiché per 100 cicli il clock viene gestito dalla funzione di maggioranza, alla fine dei quali i dati generati vengono scartati. Dopo questa operazione il cifrario è pronto per produrre in uscita 2 sequenze da 114 bit di keystream: i primi 114 bit sono utilizzati per le trasmissioni in ingresso, gli altri 114 per le trasmissioni in uscita.

Sicurezza[modifica | modifica wikitesto]

Il messaggio sul video di un telefonino che avverte dell'assenza di cifratura nelle trasmissioni

Sono stati pubblicati diversi attacchi all'A5/1. Alcuni di essi richiedono un processo iniziale altamente oneroso in termini di risorse ma dopo di esso il cifrario può essere attaccato in minuti o secondi. Fino a poco tempo fa le debolezze note erano state trovate utilizzando attacchi con testo in chiaro noto ma nel 2003 sono state scoperte delle vulnerabilità più serie che possono essere violate con attacchi con solo testo cifrato. Nel 2006 Elad Barkan, Eli Biham e Nathan Keller hanno mostrato una serie di attacchi agli algoritmi della serie A5 (A5/1 ed A5/3), ma anche del GPRS, che permettono agli attaccanti di captare le conversazioni dei telefoni GSM e decifrarle sia in tempo reale che in un secondo tempo.

Attacchi con testo in chiaro noto[modifica | modifica wikitesto]

Nel 1997 Jovan Golic presentò un attacco basato sulla risoluzione di un sistema di equazioni lineari che ha una complessità temporale di 240,16 (le unità sono in termini di numero di soluzioni di un sistema di equazioni lineari).

Nel 2000 Alex Biryukov, Adi Shamir e David Wagner mostrarono che L'A5/1 può essere crittanalizzato in tempo reale usando un attacco basato sul compromesso tempo-memoria[3]; questo lavoro era basato su un precedente scritto di Jovan Golic[4]. Il compromesso permette all'attaccante di ricostruire le chiave in 1 secondo nel caso si abbiano a disposizione 2 minuti di testo in chiaro noto oppure in pochi minuti se si hanno solo 2 secondi di testo in chiaro noto: in ogni caso, l'attaccante devo prima completare un processo molto complesso che richiede 248 passaggi e che genera circa 300 GB di dati. Sono comunque possibili diversi compromessi in questo processo iniziale fra i requisiti dei dati, il tempo di attacco ed impegno di memoria.

Lo stesso anno anche Eli Biham e Orr Dunkelman pubblicarono un attacco all'A5/1 con una complessità totale di 239,91 sincronizzazioni dell'algoritmo dati 220,8 bit of testo in chiaro noto. L'attacco richiede un processo iniziale con complessità 238 al termine del quale sono generati 32 GB di dati.[5].

Ekdahl e Johannson pubblicarono un attacco alla procedura di inizializzazione dell'algoritmo che viola l'A5/1 in pochi minuti usando da 2 a 5 minuti di conversazione trascritta[6]; questo attacco non richiede un processo iniziale. Nel 2004 un gruppo capitanato da Maximov migliorò questo risultato con un attacco che richiedeva meno di 1 minuto di calcoli e pochi secondi di conversazione trascritta; l'attacco fu ulteriormente affinato da Elad Barkan e Eli Biham nel 2005[7].

Attacchi all'A5/1 implementato nel GSM[modifica | modifica wikitesto]

Nel 2003 Elad Barkan, Eli Biham e Nathan Keller pubblicarono diversi attacchi alla cifratura GSM[8]. Il primo è un attacco attivo: i telefoni GSM possono essere indotti ad utilizzare il meno robusto algoritmo A5/2, che può essere violato molto più facilmente, dato che utilizza la stessa chiave del più robusto A5/1. Il secondo attacco all'A5/1 è del tipo con solo testo cifrato basato sul compromesso tempo-memoria: è solo a livello teorico, però, dato che il processo iniziale porta alla generazione di un'enorme quantità di dati precomputati.

Nel 2006 Elad Barkan, Eli Biham e Nathan Keller hanno pubblicato la versione integrale dei loro scritti del 2003, con attacchi a tutti gli algoritmi della serie A5/X. Gli autori hanno dichiarato[9]:

« Presentiamo una crittanalisi molto pratica della cifratura delle comunicazioni GSM basata su attacchi con solo testo cifrato noto, e vari attacchi attivi ai protocolli GSM. Questi attacchi possono anche violare reti GSM che usano cifrari "inviolabili". Descriveremo per primo un attacco all'A5/2 con solo testo cifrato che richiede poche dozzine di millisecondi di conversazione cifrata registrata e che trova la chiave corretta in meno di 1 secondo su un comune PC. Estenderemo questo attacco a un (più complesso) attacco all'A5/1 con solo testo cifrato. Descriveremo poi nuovi attacchi (attivi) ai protocolli delle reti che usano l'A5/1, l'A5/3, ma anche il GPRS. Questi attacchi mostrano le falle dei protocolli GSM e sono attuabili ogni volta che il telefono mobile supporta un cifrario debole come l'A5/2. Vogliamo rimarcare che questi attacchi sono ai protocolli e che sono perciò applicabili ogni volta che il telefonino utilizza un cifrario debole: ad esempio, sono applicabili anche per attaccare le reti A5/3 utilizzando la crittanalisi dell'A5/1. A differenza dei precedenti attacchi al GSM che richiedevano informazioni irrealistiche quali lunghe conversazioni in chiaro, i nostri attacchi sono molto pratici e non richiedono alcuna conoscenza del contenuto della conversazione. Inoltre, descriviamo come rendere più robusti gli attacchi per correggere gli errori di ricezione: come risultato, i nostri attacchi permettono di captare le conversazioni e decifrarle sia in tempo reale che in un qualunque momento successivo. »

Nel 2007 le università di Bochum e Kiel hanno avviato un progetto di ricerca per creare il progetto COPACOBANA, un'apparecchiatura decifrante basata su dispositivi FPGA nota per essere la prima del genere a livello commerciale ad utilizzare tecniche basate sul compromesso tempo-memoria che possono essere utilizzate per attaccare i sistemi crittografici quali gli algoritmi A5/1 ed A5/2 ma anche il DES od i sistemi basati sulle curve ellittiche[10].

Nel 2008 il gruppo The Hackers Choice ha lanciato un progetto per sviluppare un attacco pratico all'A5/1. L'attacco richiede la costruzione di una gigantesca tabella di associazione di circa 3 terabyte. La costruzione di questa tabella si è rivelata per ora un'impresa troppo grande per chiunque ci abbia provato ma il gruppo sembra comunque intenzionato a portare avanti il progetto. Una volta che la tabella sarà costruita e con le capacità di scansione sviluppate come parte di un progetto satellite, il gruppo pensa che sarà possibile di registrare qualunque conversazione GSM o SMS cifrati con l'A5/1 e di derivarne la chiave di cifratura in circa 3-5 minuti, in modo da poter ascoltare la conversazione o leggere l'SMS in chiaro.

Note[modifica | modifica wikitesto]

  1. ^ Security in the GSM system - Jeremy Quirke (01/05/2004), archiviato dall'originale su AusMobile
  2. ^ Ross Anderson sul newsgroup uk.telecom
  3. ^ Alex Biryukov, Adi Shamir, David Wagner: Real Time Cryptanalysis of A5/1 on a PC - Fast Software Encryption 2000
  4. ^ Jovan Golic: Cryptanalysis of Alleged A5 Stream Cipher - EUROCRYPT 1997
  5. ^ Eli Biham, Orr Dunkelman: Cryptanalysis of the A5/1 GSM Stream Cipher - Indocrypt 2000
  6. ^ Patrik Ekdahl, Thomas Johansson: Another attack on A5/1 - IEEE Transactions on Information Theory (2003), vol. 49 - pagg. 284–289
  7. ^ Elad Barkan, Eli Biham: Conditional Estimators: An Effective Attack on A5/1 - Selected Areas in Cryptography 2005
  8. ^ Elad Barkan, Eli Biham, Nathan Keller: Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication - Crypto 2003
  9. ^ Elad Barkan, Eli Biham, Nathan Keller: Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version)
  10. ^ Tim Gueneysu, Timo Kasper, Martin Novotniy, Christof Paar, Andy Ruppe: Cryptanalysis with COPACOBANA - Transactions on Computers, Nov. 2008, Volume 57, Pagg. 1498–1513

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]