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
Modifica dati su Wikidata · Manuale

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.

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]

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	${\displaystyle x^{19}+x^{18}+x^{17}+x^{14}+1}$	8	13, 16, 17, 18
2	22	${\displaystyle x^{22}+x^{21}+1}$	10	20, 21
3	23	${\displaystyle 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.

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 ${\displaystyle 0\leq {i}<64}$, l'i-esimo bit della chiave è aggiunto al bit meno significativo di ogni registro utilizzando uno XOR.

${\displaystyle 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.

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.

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^[3]; questo lavoro era basato su un precedente scritto di Jovan Golic^[4]. 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.^[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].

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]:

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.

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

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

• Wikimedia Commons contiene immagini o altri file sull'A5/1

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

Portale Crittografia

Portale Sicurezza informatica