Nohls arbejde er en videreførelse af arbejdet i "The Hackers Choice" gruppen i 2008. "The Hackers Choice" har vist, at man principielt kan dekryptere opsamlet radiokommunikation, hvis man kan lave en rainbow-table med den midlertidige nøgle.
Det er vurderingen, at angrebet fra "The Hackers Choice" må betragtes som realistisk, men også praktisk meget vanskeligt at gennemføre.
Omvendt skal man som mobilbruger være klar over, at GSM-mobiltelefoni som udgangspunkt ikke er egnet til at føre dybt fortrolige samtaler.
Har man dette behov, bør man anvende særligt sikrede telefoner med punkt til punkt kryptering.
Min kollega,
civilingeniør Henry Galle Stech fra Teknisk kontor i IT- og Telestyrelsen, har følgende beskrivelse af det konkrete angreb som Nohl har meldt ud:
Det koncept til hackning af GSM A5/1-krypteringen, som Karsten Nohl præsenterede på CCC-konferencen den 27-30. december 2009 virker ikke. Forklaringen er meget enkel. Den opstillede tabel (incl. de underliggende kæder) er alt for lille.
På CCC-konferencen den 27-30. december 2009 fremgår det af Karsten Nohl's præsentation, at den endelige tabel består af 380 undertabeller, og at hver af disse undertabeller har en højde på 2^28,5 elementer (ca. 380 millioner elementer). Hvert af de pågældende 380 millioner elementer i en vilkårlig af de 380 undertabeller er slutningen af en kæde på 32 x 2^15 mulige krypteringsnøgler altså i alt 2^20 mulige krypteringsnøgler (ca. 1 million krypteringsnøgler).
Med en sådan tabel kan man maksimalt afdække et samlet nøglerum for krypteringsalgoritmen, der er lig med: 380 x 2^28,5 x 2^20 dvs. lig med 2^57,1 (idet 380 tilnærmelsesvis er lig med 2^8,6). Men alle disse værdier kan ikke benyttes i et givet angreb på algoritmen. Der vil nemlig være en hel del dubletter.
På trods af brugen af både Rainbow-tables og DP (: Distinguished Points) har projektgruppen bag det angivelige hack måtte konstatere, at der i én given tabel med blot 400 millioner kæder vil være 151,3 millioner dubletter (konvergerede kæder) og dermed alene 248,7 millioner unikke kæder. Altså vil det reelle antal kæder blot være 62 % af det beregnede antal kæder. Oplysningerne kan blandt andet findes via denne link:
http://reflextor.com/ (...) Idet 62 % (= 0,62) er lig med 2^-0,69 vil det samlede nøglerum (der kan dækkes med tabellen) maksimalt kunne være: 2^57,1 x 2^-0,69 dvs. 2^56,4
Bemærk at denne reduktion i det maksimale nøgletal (som Karsten Nohl's tabel kan dække) er alene en konsekvens af dubletterne (altså kædesammenfald) indenfor én og den samme undertabel. Der vil desuden være et helt tilsvarende kædesammenfald mellem kæder i forskellige undertabeller. Altså at 38 % af alle kæder i en vilkårlig valgt undertabel (blandt de 380) vil være dubleret med kæder i en vilkårlig anden undertabel. Hvis projektgruppens oplysninger om kædesammenfaldet er korrekt, så vil der derfor være ekstremt få unikke kæder i den samlede tabel. Men lad os antage (til hackergruppens helt klare fordel) at kædesammenfaldet totalt kun er 38 %, og Karsten Nohl's tabel derfor kan dække et samlet nøglerum på 2^56,4.
Nu har vi beregnet, hvor det maksimale antal nøgler, som vi (angiveligt) kan finde med den pågældende tabel. Et helt centralt spørgsmål er derefter: Hvor stort er det effektive nøglerum for GSM's A5/1 krypteringsalgoritme? Én ting er, at den benyttede sessionsnøgle i GSM's A5/1 krypteringsalgoritme (kaldet Kc) er på 64 bit. Men det er jo langt fra givet, at hele nøglerummet svarende til 64 bits kompleksitet også bliver udnyttet i A5/1.
Dette helt centrale forhold er heldigvis allerede blevet nøje gennemanalyseret af J.D. Golic og præsenteret i 1997 på EuroCrypt 97. Golic's artikel kan læses her:
http://dsns.csie.nctu.edu.tw/ (...) . Som det fremgår af dette udmærkede dokument, så er A5/1 algoritmen meget effektiv med hensyn til udnyttelse af nøglerummet. I krypteringsmæssig sammenhæng er A5/1's effektive nøglestørrelse omkring 63,32 bit (altså meget tæt på det optimale tal 64 bit).
Så nu kan vi sætte et øvre loft på sandsynligheden for at finde den midlertidige krypteringsnøgle Kc ved hjælp af den pågældende tabel. Det er simpelthen antal dækkede nøgler i tabellen i forhold til antal mulige nøgler - eller mere præcist: 2^56,4 / 2^63,32 eller 2^-6,92. dvs. lig med 0,0083 eller i mere forståelige termer: 0,83 %
Lad mig lige sammenfatte dette resultat. Med den pågældende tabel (eller rettere tabel-dimension/struktur) vil man altså i den bedst mulige situation højst kunne finde den benyttede midlertidige GSM-nøgle Kc i 0,8 % af tilfældene. Og her stopper festen egentlig, men for hackergruppen er denne showstopper ikke det værste problem.
Aha, (tænker den kritiske læser) men kan hackeren da ikke bare lave parallelprocessering med flere parallelle klartekstangreb (hvor hvert angreb har en successandsynlighed på 0,8 %). Svaret er NEJ. Det hjælper ikke noget. Den øvre grænse på de 0,8 % er sandsynligheden for, at den benyttede midlertidige A5/1-krypteringsnøgle i det hele taget befinder sig i en af de specifikke kæder, der hører til den opstillede tabel.
Hvordan kan det så være, at hackergruppen (og Kasten Nohl i sin præsentation) angiver en mere acceptabel succesrate? På hackergruppens Wiki-site for projektet anfører Karsten Nohl således, at den forventede succesrate er omkring 80 %. På selve præsentationen ved CCC 2009 den 29. december 2009 er succesraten sågar steget til 99 %. Svaret er lige så enkelt som det er sigende. Hacker-gruppens faglige viden om og forståelse af GSM (og i særdeles omkring GSM's sikkerhedsmæssige aspekter) er meget rudimentær - for at sige det dannet. De antager helt fejlagtigt, at den effektive størrelse på GSM's midlertidige A5/1-krypteringsnøgle Kc stadigvæk er begrænset til 56 bit (altså at de første 8 bit af nøglens i alt 64 bit af eksportmæssige årsager stadigvæk er sat til nuller). Men det er ikke tilfældet. Denne begrænsning er forsvundet for adskillige år siden i Europa og GSM's A5/1-krypteringsalgoritme benytter i dag alle 64 bit.
Men jeg antyder i det forudgående, at hackergruppen har flere problemer (end den førnævnte showstopper, nemlig at den øvre succesgrænse er 0,83 %). For at forstå hvad jeg vil beskrive, skal man nok kende lidt mere til selve metoden, som Karsten Nohl benytter (forkert !!!). Metoden er ikke ny. Den er første gang blevet beskrevet i litteraturen i 1980 (nej det er ikke en skrivefejl) i 1980, før GSM eksisterede i sit allerede første spæde, spæde udkast i CEPT's særlige arbejdsgruppe: Groupe Special Mobile.
Idéen (som Karsten Nohl forsøger at benytte) blev beskrevet af Martin Hellman en af de helt store koryfæer i krypteringssammenhæng i hans artikel "A Cryptanalytic Time-Memory Trade-Off" i IEEE Transactions on Information Theory, Volumen IT-26, No. 4, 4 juli 1980, side 401-406.
Martin Hellman's metode kan ikke benyttes til 'knække' en algoritme. Hans metode går alene ud på at reducere omkostningerne i tid og computerhukommelse, når man foretager et såkaldt 'Brute Force' angreb på krypteret indhold. Martin Hellman starter i sin artikel med at betragte de to ekstreme 'Brute Force' måder til at angribe krypteret indhold, hvor man kender en tilstrækkelig lille bid af det (ukrypterede) indhold og selve krypteringsalgoritmen. Disse to metoder er (1) det tids-belastende angreb og (2) det hukommelses-belastende angreb.
I det tidsbelastende angreb (1) opsamler hackeren det krypterede indhold hvor en passende og bestemt bid af indholdet er kendt. Dette kaldes "Known Plaintext" angreb. Hvis den kendte tekst enten kan kontrolleres af hackeren eller med sikkerhed vil være tilgængelige et bestemt sted og tid, så er der tradition for at kalde det "Chosen Plaintext" angreb. Når hackerne har fået adgang til disse ting, så begynder hackeren at kryptere det kendt indhold med den benyttede krypteringsalgoritme, idet hacker støt roligt forsøger med alle mulige krypteringsnøgler. På et eller tidspunkt vil der være bid. Men der kan gå ret så lang tid. Måske længere tid end universets alder. Ved dette angreb lærer hackeren ikke noget om algoritmen (det er jo Brute Force), men får alene adgang til benyttede krypteringsnøgle. Man kan ikke sige, at hackeren derved har brudt algoritmen, men hvis hackeren kan finde nøglen indenfor en kritisk tid, så har hackeren derimod demonstreret, at nøglestørrrelsen er for lille (: der er for få nøgler).
I det hukommelsesmæssige angreb (2) laver hackeren en total oplagstabel, der rummer alle mulige krypteringsnøgler sammen med tilsvarende kryptering af den kendte 'Plaintext' ud for den respektive nøgle. Når hackeren derefter opsamler det krypterede indhold (hvor den kendte 'Known Plaintext' indgår), så er det et "simpelt" tabelopslag at finde den benyttede nøgle. Denne tilgang er normalt heller ikke realistisk, idet tabelstørrelsen for en rimeligt fornuftigt konstrueret kryptering vil være så gigantisk stor, at tabellen reelt set ikke kan opstilles. Et kort eksempel: hvis man valgte denne strategi for GSM's A5/1-kryptering og valgte at gemme tabellen på 2 TeraByte harddiske, så skulle hver dansker (alle 5.5 millioner af os) har 25 af sådan harddiske stående for at gemme denne tabel.
Det der er Martin Hellman's lysende indfald er, at han indså, at man kan lave kombineret strategi, hvor der laves et optimalt trade-off mellem den tidsmæssig belastning og kravet til computerhukommelse. Ved at benytte hans strategi vil tabellen være håndterbar og de beregningsmæssige omkostninger vil også kunne være acceptable. Det er det, der beskrevet i hans artikel fra 1980. Der er desværre en alvorlig skønhedsfejl i hans metode. Eftersom krypteringsblokken typisk vil være større end nøglestørrelsen så benytter Martin Hellman en såkaldt 'reduktionsfunktion' efter hvert krypteringtrin i kæderne. Det betyder, at man kan få forskellige kæder til at frembringe de samme forslag til mulige krypteringsnøgler. Sådan kollisioner vil føre til dubletter i den endelige tabel. Beregningskæderne vil især ved de store tabeller kollidere (og derved føre til dubletter). Hvorved den effektive tabelstørrelse bliver meget mindre. Det lyder bekendt ikke?
Kollisionproblemet blev i 1982 foreslået løst af et andet stort koryfæ i krypteringsverdenen: Ron Rivest, nemlig at man kunne finde kollisionerne meget hurtigt (og droppe de uegnede kæder) ved at bruge såkaldte 'Distinguished Point' ved gennemregningen af de forskellige kæder. En udmærket beskrivelse af princippet er givet af J. Bost, B. Preneel og J. Vandewall i 1998 i deres bidrag "A Time-Memory Tradeoff Using Distinguished Points" fra 1998, Technical Report ESAT-COSIC Report 98-1.
Nogen rigtigt tilfredsstillende løsning var det ikke. Problemet blev først egentligt tilfredsstillende adresseret med Philippe Oechlins ide: Rainbow table. Der kort fortalt blot betyder, at hvert trin i kæder har sin egen reduktionsfunktion. I Martin Hellman's idé bruger man den samme reduktionsfunktion på alle trin i alle tabellens kæder. Hvis to kæder (på forskellige trin) rammer den samme værdi, så de to kæder i en Rainbow tabel yderst sjældent kollidere, idet man takket være de forskellige reduktionsfunktioner (på de forskellige trin) får forskellige værdier på de to steder.
Rainbowtabel-koncept bliver generelt tilskrevet Philippe Oechslin, der første gang beskrev det i artiklen "Making a Faster Cryptanalytic Time-Memory Trade-Off". Artiklen kan (gratis) læses på hans universitets hjemmeside her:
http://lasecwww.epfl.ch/ (...) Martin Hellman oprindelige tanke er løbende blevet analyseret og forsøgt optimeret over årene. Men som det bliver fastslået med syv tommer søm i Elad Barkan, Eli Biham og Adi Shamir's bidrag "Rigorous Bounds on Cryptanalytic Time/Memory Tradoffs", CRYPTO 2006, 26th Annual Internatonal Cryptology Conference, Santa Barbara, Califormnia, USA, August 20-24 2006, så er den optimale udnyttelse af Martin Hellman's metode at benytte Rain Tables (og ikke Distinguished Points)
Med hele denne teoretiske bagage på plads, så er det på tide at vende til bage til Karsten Nohl's særlige udgave af Martin Hellman's TMTO (Time-Memory Trade-Off) strategi. Hvad er det nye, som Karsten har gjort. Jo, han har i modsætning til budskabet fra de egentlige koryfæers på området kombineret Distinguished Points og Rainbow Tables, og tilmed på en sådan klodset måde, at han ikke har kunnet udnyttet nogen af fordele ved de to strategier. Dette har blandt andet ført til det meget høje antal af kollisioner i undertabellerne.
Jeg har for god orden skyld beregnet sandsynligheden for, at Karsten Nohl's konkrete tabel vil fremskaffe A5/1's midlertidige krypteringsnøgle Kc (ikke ud fra den tidligere dækningssandsynlighed) med ved at benytte metoden i Martin Hellman's artikel, det og giver mig svaret: 0,84 % - altså praktisk talt samme sandsynlighed som før. Hvilket også helst skulle være tilfældet. Forskellen skyldes alene afrunding.
Ved at kigge lidt tilbage i teksten kan man se, at Karsten Nohl har underestimeret opgaver med 8 bit. Hver bit svarer i denne opgave til en fordobling af "besværet" (enten i tid eller i hukommelse). Moore's lov fortæller os, at vi populært sagt får en fordobling i vores basale IT-styrke "foræret" for hver 18 måneder (nogen siger 24 måneder). Lad os være venlige og holde fast i de 18 måneder. Det betyder, at Karsten Nohl's koncept ville rykket i virkelighedens verden (for den sammen omkostning om 8 x 18 måneder) - altså om 12 år. På det tidspunkt har GSM A5/1 nok forladt os.
Men problemerne for Karsten Nohl slutter ikke her. Hvis vi antager, ar man kunne få fat i A5/1's krypteringsnøgle Kc, så er Kc jo alene den midlertidige sessionsnøgle og ikke den egentlige kronjuvel, nemlig den hemmelige nøgle Ki på SIM-kortet. Og ved næste samtale, SMS, location update etc etc, skifter GSM-systemet ved autentifikationskontrollen sandsynligvis Kc. Dette er heldigvis udenfor brugerens kontrol.
Og lidt mere, og langt mere alvorligt for hele konceptet, så forudsætter Karsten Nohl's koncept, at hackeren kan få fat i noget krypteret indhold (tilhørende brugeren) sammen med 'plaintext'en', der svarer til indholdet. Der har været mange vidtløftige teorier i tidens løb om hvordan hackeren får fat i dette indhold. Der har i de snart 29 år GSM har været luften kun været præsenteret en virkende metode til få fat i sådan indhold. Nemlig ved at hackeren benytter sig af en falsk basestation og gennem denne får mobiltelefonen at afsende en bekræftelse af, at mobiltelefonen nu kører krypteret (Cipher Command Complete). Denne meddelelse er oftest (men ikke altid) blot den minimale (og kendte) besked, nemlig at mobiltelefonen gentager blot basestations oprindelige Cipher Command, men som krypteret. I denne (og alene i denne situation) kan hackeren opsamle 4 bursts (dvs. 456 bit) på en bestemt kontrolkanal, hvor indholdet er kendt og den tilhørende kryptering er kendt. Men hvis GSM-systemet instruerer mobiltelefonen om at tilføje IMEISV (der er mobiltelefonens elektroniske serienummer med udvidet oplysning om softwareversion) i sit Cipher Command Complete svar, så vil der så mange ukendt bits i de fire burst, at svaret ikke længere kan benyttes i et 'Plain Text' angreb.. Kan mobilselskaberne benytte denne feature? Ja, det har været en del af GSM-specifikationerne lige fra dag ét. Koster det noget for selskaberne at benytte denne feature? Nej. Bruger de den? Det ved jeg ikke. Men det vil være ganske naturligt.
Dette er den anden showstopper for Karsten Nohl's koncept.Og dette problem er faktisk langt værre for hans koncept, fordi dette problem vil tiden (dvs. Moore's lov) ikke løse for hackeren.
Det værste hindring for Karsten Nohl og hans gruppe er, at den reelle nøglestørrelse for GSM's A5/1-kryptering er ikke blot de tidligere oplyste 64 bit (nemlig den midlertidige nøgle Kc). Næh, A5/1 bliver også kodet og initialiseret med burstnummeret (kaldet Frame Number). Dette tal er på 22 bit og bliver af krypteringsfolk (udenfor GSM-verdenen) helt fejlagtigt betragtet som værende en betydningsløs del af krypteringen, eftersom dette tal (1) bliver jo udsendt løbende i klartekst på radiokanalen og (2) ikke udvider det effektive nøglerum. Så krypteringsverdenen betragter tilføjelsen af Frame Number nærmest som en slags initialiseringsvektor (: IV) som man eksempelvis kender det fra WEP i WiFi.
Men det er ikke korrekt. Først bliver A5/1 skifteregistrene kodet op og initialiseret med Kc, derefter bliver skifteregistrene kodet op og initialiseret med Frame Number for det burst hvor data skal afsendes og modtages. Når denne initialisering er foretaget, genereres der 100 bit med A5/1 (der kasseres) før der genereres de egentlige 228 bit stream cipher bit, der benyttes til kryptering/dekryptering af de 114 bit i frame til uplink og downlink burst.
A5/1's opbygning er dybt genialt (det synes ikke umiddelbart, når man kigger lidt på de tre skifteregistre som A5/1 består af), men på grund af den særlige opsætning med selektiv klokning af tre skifteregistre på baggrund af en majority voting mellem tre skifteregisterpositioner, så er det ekstremt vanskeligt ('praktisk umuligt' er vurderingen, der er nemlig endnu ingen i den cryptotekniske verden der har kunnet anvise en brugbar metode) at køre A5/1 baglæns ud fra en kendt streamcipher sekvens for derved komme tilbage til den vigtige situation hvor Kc netop er blevet klokket ind i A5/1 registrene (altså før Frame Number bliver klokket ind) - altså den vigtige udgangs-state på 64 bit for indholdet af de tre skifteregistre, der alene og éntydigt afhænger af Kc..
Og det er denne præcise A5/1 tilstand, som vi skal hen, før at man kan benytte Karsten Nohl's koncept. Karsten Nohl's koncept angriber således ikke signalet fra radiostrækningen, men tager sit udgangspunkt i initialiseringstilstanden for de tre skifteregistre i A5/1, når Kc er blevet klokket ind i A5/1 og initialiseret.
Reelt set er der en løsning på problemet, Nemlig at sige som det er, at den reelle nøglestørrelse er 64 bit + 22 bit altså 86 bit, og så angribe problemet med en rigtig Rainbow table mod de 86 bit. Sandsynligvis delt, med et Rainbow tabel angreb først mod de kendte 22 Frame Number bit, og derefter et egentligt Rainbow tabel angreb mod de 64 bit i Kc. Men det betyder under alle omstændigheder, at Karsten Nohl ikke blot mangler 8 bit, men derimod 30 bit i sin kompleksitetsvurdering - og det betyder, at hacket på baggrund af Moore's lov vil nok først være realistisk om 45 år - altså under forudsætning at mobilselskaber ikke instruerer mobiltelefonen om at tilføje IMEISV til Cipher Command Complet.
Det er på baggrund af alle disse oplysninger, at man skal forstå GSM Associations udmelding den 30 december 2009, om at pågældende hack af GSM A5/1 ikke er praktisk anvendeligt.
Log ind
Publiceret d. 21. januar 2010 kl. 21.00
| 
