A5/1

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.

A5/1
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

Storia e utilizzo

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). 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"

Descrizione

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

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

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

Nel 1997 Jovan Golic presentò un attacco basato sulla risoluzione di un sistema di equazioni lineari che ha una complessità temporale di 2^40,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; questo lavoro era basato su un precedente scritto di Jovan Golic. Il compromesso permette all'attaccante di ricostruire la 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 deve prima completare un processo molto complesso che richiede 2⁴⁸ 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 2^39,91 sincronizzazioni dell'algoritmo dati 2^20,8 bit of testo in chiaro noto. L'attacco richiede un processo iniziale con complessità 2³⁸ al termine del quale sono generati 32 GB di dati..

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; 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.

Attacchi all'A5/1 implementato nel GSM

Nel 2003 Elad Barkan, Eli Biham e Nathan Keller pubblicarono diversi attacchi alla cifratura GSM. 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:

«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.

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.

Bibliografia

• Greg Rose, A precis of the new attacks on GSM encryption (PDF), su qualcomm.com.au, Qualcomm Australia, 10 settembre 2003. URL consultato il 9 dicembre 2008 (archiviato dall'url originale il 27 settembre 2011).
• Alexander Maximov, Thomas Johansson; Steve Babbage, An Improved Correlation Attack on A5/1, in Selected Areas in Cryptography 2004, 2004, pp. 1–18.

Voci correlate

• A5/2, versione più debole dell'A5/1
• Cellular Message Encryption Algorithm
• KASUMI (cifrario), noto anche come A5/3

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su A5/1

Collegamenti esterni

• Marc Briceno, Ian Goldberg; David Wagner, A pedagogical implementation of the GSM A5/1 and A5/2 "voice privacy" encryption algorithms, su mirrors.wiretapped.net, 23 ottobre 1999 (archiviato dall'url originale il 10 ottobre 2008).
• Hadar Horesh, Technion team cracks GSM cellular phone encryption (PDF), in Haaretz, 3 settembre 2003. URL consultato il 9 dicembre 2008 (archiviato dall'url originale il 26 marzo 2007).
• Elad Barkan, Eli Biham; Nathan Keller, Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication (Technical Report CS-2006-07), su cs.technion.ac.il, luglio 2006. URL consultato il 29 febbraio 2020 (archiviato dall'url originale il 3 marzo 2016).
• Nathan Keller's Homepage, su ma.huji.ac.il (archiviato dall'url originale il 4 giugno 2008).
• D. Le, L'hacker svela il codice del Gsm, in il Sole 24 Ore, 30 dicembre 2009. URL consultato il 31 dicembre 2009.