Visualizza wikitesto di A5/1

{{Metodo crittografico
|fullName = A5/1
|image = A5-1 GSM cipher.svg
|caption = Struttura dell'A5/1 con i suoi 3 [[Registro a scorrimento a retroazione lineare|registri a scorrimento LFSR]]
|designers = 
|yearPublished = [[1987]]
|derivedFrom = 
|derivedTo = [[A5/2]]
|keySize = 64 bit
|IvSize = 22 bit
|cipherStructure = [[Registro a scorrimento a retroazione lineare|registri a scorrimento a retroazione lineare]]
|rounds = 64
|cryptanalysis = il cifrario è stato [[reingegnerizzazione|reingegnerizzato]] nel [[1999]]
}}

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

== Storia e utilizzo ==
L'A5/1 fu sviluppato alla fine degli [[Anni 1980|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 [[Stati Uniti d'America|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]])<ref>{{cita web|urlarchivio=https://web.archive.org/web/20040712061808/http://www.ausmobile.com/downloads/technical/Security+in+the+GSM+system+01052004.pdf|titolo=Security in the GSM system|autore= Jeremy Quirke |data=1 maggio 2004|url=http://www.ausmobile.com/downloads/technical/Security+in+the+GSM+system+01052004.pdf}} </ref>. Nel [[1994]] la struttura generale degli algoritmi divenne di [[pubblico dominio]] mentre nel [[1999]] gli algoritmi furono completamente [[Reingegnerizzazione|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"''<ref>{{cita testo|url=https://groups.google.com/group/uk.telecom/msg/ba76615fef32ba32|titolo=Ross Anderson sul newsgroup uk.telecom}}</ref>

== Descrizione ==
[[File:A5-1 GSM cipher.svg|thumb|upright=1.6|Il cifrario a flusso A5/1 utilizza 3 registri [[registro a scorrimento a retroazione lineare|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 (informatica)|bit]] di dati cifrati tramite un'operazione di [[disgiunzione esclusiva|XOR]] tra 114 bit di dati in chiaro ed altrettanti bit di [[keystream]]. L'A5/1 viene inizializzato utilizzando una [[chiave crittografica|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 [[dimensione chiave|lunghezza della chiave]] è di 54 bit.

L'A5/1 si basa su una combinazione di tre [[registro a scorrimento a retroazione lineare|registri a scorrimento a retroazione lineare]] (LFSR) con sincronizzazioni irregolari. I tre registri sono specificati come segue:
{| class="wikitable"
!Reg.<br />LFSR
!Lunghezza<br />in bit
!Polinomio<br />caratteristico
!Bit di<br />sincronizzazione
!Bit<br />usati
|-
|1 || 19 || <math>x^{19} + x^{18} + x^{17} + x^{14} + 1</math> || 8 || 13, 16, 17, 18
|-
|2 || 22 || <math>x^{22} + x^{21} + 1</math> || 10 || 20, 21
|-
|3 || 23 || <math>x^{23} + x^{22} + x^{21} + x^{8} + 1</math> || 10 || 7, 20, 21, 22
|}
I bit sono indicizzati con il [[ordine dei bit|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 <math>0\leq{i}<64</math>, l'''i''-esimo bit della chiave è aggiunto al bit meno significativo di ogni registro utilizzando uno XOR.

:<math>R[0] = R[0] \oplus K[i].</math>

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 ==
[[File:CipheringNotProvided.jpg|thumb|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 [[attacco con testo in chiaro noto|attacchi con testo in chiaro noto]] ma nel [[2003]] sono state scoperte delle vulnerabilità più serie che possono essere violate con [[attacco con solo testo cifrato|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<sup>40,16</sup> (le unità sono in termini di numero di soluzioni di un sistema di equazioni lineari).

Nel [[2000]] [[Alex Biryukov]], [[Adi Shamir]] e [[David A. Wagner|David Wagner]] mostrarono che L'A5/1 può essere [[crittanalisi|crittanalizzato]] in tempo reale usando un attacco basato sul [[compromesso tempo-memoria]]<ref>Alex Biryukov, Adi Shamir, David Wagner: {{cita testo|titolo=Real Time Cryptanalysis of A5/1 on a PC|url=http://cryptome.info/0001/a51-bsw/a51-bsw.htm|urlarchivio=https://web.archive.org/web/20140110184154/http://cryptome.info/0001/a51-bsw/a51-bsw.htm}} - [[Fast Software Encryption]] 2000</ref>; questo lavoro era basato su un precedente scritto di Jovan Golic<ref>Jovan Golic: {{cita testo|titolo=Cryptanalysis of Alleged A5 Stream Cipher|url=http://jya.com/a5-hack.htm|urlarchivio=https://web.archive.org/web/20080920120527/http://jya.com/a5-hack.htm}} - [[EUROCRYPT]] 1997</ref>. 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<sup>48</sup> 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<sup>39,91</sup> sincronizzazioni dell'algoritmo dati 2<sup>20,8</sup> bit of testo in chiaro noto. L'attacco richiede un processo iniziale con complessità 2<sup>38</sup> al termine del quale sono generati 32 GB di dati.<ref>Eli Biham, Orr Dunkelman: Cryptanalysis of the A5/1 GSM Stream Cipher - [[Indocrypt]] 2000</ref>.

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<ref>Patrik Ekdahl, Thomas Johansson: Another attack on A5/1 - IEEE Transactions on Information Theory (2003), vol. 49 - pagg. 284–289</ref>; 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<ref>Elad Barkan, Eli Biham: Conditional Estimators: An Effective Attack on A5/1 - Selected Areas in Cryptography 2005</ref>.

=== Attacchi all'A5/1 implementato nel GSM ===
Nel [[2003]] Elad Barkan, Eli Biham e Nathan Keller pubblicarono diversi attacchi alla cifratura GSM<ref>Elad Barkan, Eli Biham, Nathan Keller: {{cita testo|url=http://cryptome.org/gsm-crack-bbk.pdf|titolo=Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication}} - [[Crypto]] 2003</ref>. 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 [[attacco con solo testo cifrato|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<ref>Elad Barkan, Eli Biham, Nathan Keller: {{cita testo|url=http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2006/CS/CS-2006-07.pdf|titolo=Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version)|accesso=9 dicembre 2008|dataarchivio=13 maggio 2012|urlarchivio=https://web.archive.org/web/20120513130253/http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2006/CS/CS-2006-07.pdf|urlmorto=sì}}</ref>:
{{Citazione|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 [[Field programmable gate array|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 [[crittografia ellittica|curve ellittiche]]<ref>Tim Gueneysu, Timo Kasper, Martin Novotniy, Christof Paar, Andy Ruppe: {{cita testo|url=http://www.copacobana.org/paper/TC_COPACOBANA.pdf|titolo=Cryptanalysis with COPACOBANA}} - Transactions on Computers, Nov. 2008, Volume 57, Pagg. 1498–1513</ref>.

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 [[Lookup table|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 ==
<references/>

== Bibliografia ==
* {{Cita web | nome = Greg | cognome = Rose | titolo = A precis of the new attacks on GSM encryption | editore = [[Qualcomm]] Australia | data = 10 settembre 2003 | url = http://www.qualcomm.com.au/PublicationsDocs/GSM_Attacks.pdf | accesso = 9 dicembre 2008 | urlarchivio = https://web.archive.org/web/20110927122703/http://www.qualcomm.com.au/PublicationsDocs/GSM_Attacks.pdf | urlmorto = sì }}
* {{Cita pubblicazione| nome = Alexander | cognome =  Maximov | coautori = Thomas Johansson; Steve Babbage| titolo = An Improved Correlation Attack on A5/1| rivista = [[Selected Areas in Cryptography]] 2004 | anno = 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 ==
{{interprogetto|preposizione=sull'}}

== Collegamenti esterni ==
* {{Cita web | nome = Marc | cognome = Briceno | coautori = Ian Goldberg; David Wagner | data = 23 ottobre 1999 | url = http://www.mirrors.wiretapped.net/security/cryptography/algorithms/gsm/a5-1-2.c | titolo = A pedagogical implementation of the GSM A5/1 and A5/2 "voice privacy" encryption algorithms | urlmorto = sì | urlarchivio = https://web.archive.org/web/20081010152347/http://www.mirrors.wiretapped.net/security/cryptography/algorithms/gsm/a5-1-2.c }}
* {{Cita news | url = http://www.cs.technion.ac.il/%7Ebarkan/GSM-Media/HaaretzInternetEnglish.pdf | titolo = Technion team cracks GSM cellular phone encryption | pubblicazione = [[Haaretz]] | nome = Hadar | cognome = Horesh | data = 3 settembre 2003 | accesso = 9 dicembre 2008 | urlarchivio = https://web.archive.org/web/20070326142136/http://www.cs.technion.ac.il/%7Ebarkan/GSM-Media/HaaretzInternetEnglish.pdf | urlmorto = sì }}
* {{Cita web|url = http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?2006/CS/CS-2006-07|titolo = Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication (Technical Report CS-2006-07)|nome = Elad|cognome = Barkan|coautori = Eli Biham; Nathan Keller|mese         = luglio|anno = 2006|accesso = 29 febbraio 2020|urlarchivio = https://web.archive.org/web/20160303191021/http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?2006%2FCS%2FCS-2006-07|urlmorto = sì}}
* {{Cita web| url = http://www.ma.huji.ac.il/~nkeller| titolo = Nathan Keller's Homepage| urlmorto = sì| urlarchivio = https://web.archive.org/web/20080604000934/http://www.ma.huji.ac.il/~nkeller/}}
* {{Cita news|lingua =|autore = D. Le|url = http://www.ilsole24ore.com/art/SoleOnLine4/Mondo/2009/12/hacker-codice-gsm.shtml?uuid=8e09be06-f519-11de-ac8b-164065c89034|titolo = L'hacker svela il codice del Gsm|pubblicazione = il Sole 24 Ore|giorno = 30|mese=dicembre|anno = 2009|p=|accesso = 31 dicembre 2009|cid =}}

{{Cifratura a flusso}}
{{Portale|crittografia|sicurezza informatica}}

[[Categoria:Cifrari a flusso]]