A3 (chiffer)

A3  er den algoritme, der bruges i godkendelsesprocessen i den globale digitale standard for GSM mobil cellulær kommunikation . A3 er således et element i GSM -opkaldsbeskyttelsessystemet sammen med algoritmerne A5 og A8 . Algoritmens opgave er at generere et svar ( SRES-Signet Response ) på et tilfældigt kodeord ( RAND-Random ) modtaget af en mobiltelefon ( MS-Mobile Station ) fra MSC-omstillingscenteret ( MSC-Mobile Omstillingscenter ) i autentificeringsprocedure. A3 er implementeret i abonnentens SIM-kort .

Godkendelsesproces

Essensen af ​​autentificering i GSM  er at undgå kloning af brugerens mobiltelefon. Den hemmelige nøgle er en 128-bit nøgle Ki, som ejes af både abonnenten og Authentication Center ( AuC  - Authentication Center). Ki er gemt på SIM-kortet , ligesom A3-algoritmen. Også involveret i autentificering er Home Location Registry ( HLR  - Home Location Registry) og Switching Center ( MSC  - Mobile Switching Center)

Når en MS anmoder om adgang til et GSM-netværk (f.eks. ved opstart), skal MSC'en autentificere MS'en. For at gøre dette sender MSC'en til HLR en unik International Mobile Subscriber Identity ( IMSI  ) og en anmodning om et sæt specielle tripletter. Når HLR modtager en IMSI-anmodning om tripletter, tjekker den først sin database for at sikre, at MS'en med den IMSI faktisk tilhører netværket. Hvis verifikationen er vellykket, sender HLR'en IMSI'en og en autentificeringsanmodning til AuC'en.

AuC'en bruger IMSI'en til at finde den Ki, der svarer til den IMSI. AuC genererer også et tilfældigt 128-bit RAND-nummer. Derefter beregner AuC et 32-bit SRES-svar (SRES - Signed Response) ved hjælp af A3-algoritmen: SRES = A3(RAND, Ki). Derudover beregner AUC en 64-bit sessionsnøgle Kc ved hjælp af A8 -algoritmen : Kc = A8(RAND, Ki). Kc bruges yderligere i A5 -algoritmen til at kryptere og dekryptere data.

RAND, SRES og Kc danner bare de tripletter, som MSC anmodede om fra HLR. AuC'en genererer fem af disse tripletter og sender dem til HLR'en, derefter sender HLR'en dette sæt til MSC'en. Det er det sæt af tripletter, der genereres for at reducere signaleringen i GSM-kernenetværket, som ville forekomme, hver gang MS ville anmode om adgang til netværket, og MSC'en skulle autentificere MS'en. Det skal bemærkes, at et sæt tripletter er unikt for én IMSI og ikke kan bruges til nogen anden IMSI.

MSC'en gemmer Kc og SRES og sender en RAND-anmodning til abonnentens mobilstation MS. Ved modtagelse af RAND-anmodningen beregner MS svaret på SRES-anmodningen ved at anvende A3-algoritmen og den hemmelige nøgle Ki: SRES = A3(RAND, Ki), og sender det til MSC'en. Hvis det modtagne SRES matcher det SRES, der er lagret i MSC'en, anses godkendelsen for at være vellykket.

Efter fem autentificeringssessioner beder MSC'en HLR om et nyt sæt tripletter (RAND, SRES, Kc)

Beskrivelse af algoritmen

Generelle bestemmelser

Input- og outputdataformatet for A3-algoritmen samt hele autentificeringsprocessen er strengt defineret af 3GPP- konsortiet . Det er værd at bemærke, at hver enkelt operatør vælger A3-algoritmens funktionsprincip. Så A3 er ikke standardiseret, men er defineret af operatøren. Men hvis operatøren ikke ønsker at komme med sin egen A3-algoritme, kan han bruge standardimplementeringen af ​​algoritmen.

I øjeblikket accepteres følgende format for input- og outputdata RAND, Ki, SRES af A3-algoritmen: Ki-længde - 128 bit RAND-længde - 128 bit SRES-længde - 32 bit

Udførelsestiden for A3-algoritmen skal være mindre end 500 millisekunder. [en]

Følgende standardimplementeringer af A3-algoritmen er i øjeblikket kendt:

COMP128 er den allerførste version af A3-algoritmen. Oprindeligt blev COMP128-algoritmen holdt hemmelig. Udviklerne af den første version af A3 stolede på sikkerhed på bekostning af uklarhed, hvilket betyder, at algoritmer er sværere at knække, hvis de ikke er offentligt tilgængelige. COMP-128 blev imidlertid kompromitteret af kryptoanalytikerne Marc Briceno, David Wagner og Ian Goldberg fra ISAAC-sikkerhedsforskningsgruppen. Efter at COMP128-sårbarhederne blev offentliggjort, blev patchede versioner af COMP128-2 og COMP128-3 udviklet.

COMP128

I 1998 blev en beskrivelse af COMP128-algoritmen lækket til internettet. Selvom beskrivelsen ikke var fuldstændig, er koden blevet fuldstændig gendannet gennem reverse engineering og er nu tilgængelig for offentligheden .

Grundlæggende er COMP128 en 128-bit hash-funktion. Argumentets bredde er 256 bit eller 32 bytes (128 bit Ki + 128 bit RAND). De 32 mest signifikante bit af den beregnede værdi tages som SRES, og de 64 mindst signifikante bit tages som sessionsnøglen Kc. Lad X [0..32] være algoritmens 32-byte input, hvor X [0..15] = Ki og X [16..31] = RAND. T0 [0..511], T1 [0..255], T2 [0..127], T3 [0..63] og T4 [0..31] er hemmelige byte-substitutionstabeller. Algoritmen består af 8 runder, hver runde har 5 iterationer. Hver iteration består af at slå den tilsvarende tabel op (T0 for den første iteration, T1 for den anden osv.) og bytesubstitution. I slutningen af ​​hver runde, bortset fra den sidste, permuteres de resulterende 128 bits af resultatet, og efter permutationen bruges disse 128 bits i næste runde. Beskrivelse af en runde i pseudokode:

(udskiftninger) for i = 0 til 4 gør: for j = 0 til 2^i - 1 do: for k = 0 til 2^(4-i) - 1 do: { s = k + j*2^(5 - i) t = s + 2^(4-i) x = (X[s] + 2X[t]) mod (2^(9 - i)) y = (2X[s] + X[t]) mod (2^(9 - i)) X[s]=Ti[x] X[t]=Ti[y] } (dannelse af bits fra bytes) for j = 0 til 31 gør: for k = 0 til 7 gør: { bit[4*j+k] = den (8-k) bit af byte j } (permutation) hvis (i < 8) så for j = 0 til 15 gør: for k = 0 til 7 gør: { næste bit = (8 xj + k) x 17 mod 128 Bit k af X[j + 16] = bit[næste_bit] }

Ved hver iteration afhænger outputbyten af ​​de to inputbytes. De to inputbytes bruges til at identificere et element i opslagstabellen. Dette element vil opdatere outputbyten. Opslagstabellen for den i-te iteration indeholder 2^(9 - i) elementer med størrelse (8 - i) bits. Det er

tabel antal elementer størrelsen af ​​et element T0 512 8 bit T1 256 7 bit T2 128 6 bit T3 64 5 bit T4 32 4 bit

Faktisk har hver af de 32 outputbytes i den sidste iteration af runden kun 4 signifikante bits. Derfor, ved slutningen af ​​iterationen, konverteres disse 32 bytes ved permutation til 16 bytes, hvoraf alle bits er signifikante. Disse 16 bytes skrives til X [16 .. 31], og næste runde af algoritmen startes (i X [0 .. 15] ændres værdien af ​​Ki ikke på nogen måde).

David Wagner kaldte denne struktur af algoritmen sommerfuglestruktur, hvilket betyder "i form af en sommerfugl"

COMP128-2 og COMP128-3

Selvom det nu er klart, at "sikkerhed ved obscurity"-princippet ikke virker, holdes COMP128-2 og COMP128-3 versionerne hemmelige.

Milenage

Milenage-godkendelses- og sessionsnøglegenereringsalgoritmerne blev udviklet af 3GPP -konsortiet med en kombineret indsats fra 3GPP-medlemsorganisationer. Der kræves ingen yderligere krav eller tilladelser for at bruge disse algoritmer. Et eksempel på brug af Milenage som A3 er vist i 3GPP TS 55.205 "Specifikation af GSM-MILENAGE Algorithms: Et eksempel på algoritmesæt til GSM Authentication and Key Generation-funktionerne A3 og A8" . Den komplette Milenage-specifikation er tilgængelig på 3GPP-konsortiets hjemmeside.

Milenage er immun over for alle kendte angreb. [2]

Mulige angreb

Angreb på COMP128

BGW Attack

Den 13. april 1998 publicerede Marc Briceno, Ian Goldberg og David Wagner en artikel , hvori de beskrev en metode til at opnå en hemmelig nøgle Ki ved at sende omkring 150.000 anmodninger til SIM-kortet. Angrebet udnytter en flaskehals i algoritmen.

Efter den anden iteration af første runde afhænger bytes X[i], X[i+8], X[i+16], X[i+24] kun af inputbytes med de samme indekser. Bytes X[i] og X[i+8] er nøglebytes, dvs. X[i] = Ki[i] og X[i+8] = Ki[i+8] (for hver i fra 0 til 7) , og X[i+16] og X[i+24] bytes er RAND-anmodningsbytes fra basestationen, dvs. X[i+16] = RAND[i+16] og X[i+24] = RAND[ i+24] (for hver i fra 0 til 7).

Vi ændrer nu bytes i+16, i+24 for input fra COMP128-algoritmen (det vil sige bytes i, i+8 af RAND-forespørgslen), og lader de resterende inputbytes være konstante. Da en iteration ikke er en-til-en, kan man forvente en kollision i outputbytes nummereret i, i+8,i+16,i+24 efter den anden iteration. " Fødselsdagsparadokset " sikrer, at kollisionen sker ret hurtigt (da flaskehalsen er begrænset til 4 bytes). Kollisioner ved flaskehalsen kan detekteres, fordi de vil få udgangene fra COMP128-algoritmen til at kollidere (det vil sige, vi vil få to identiske SRES-svar), og hver kollision kan bruges til at opnå to bytes af nøglen i, i + 8 (under hensyntagen til den lille behandling af de to første iterationer - det vil sige anvendelse af et 2R-angreb i form af differentiel kryptoanalyse).

Dette ville kræve nogle COMP128 inputforespørgsler for at finde nøglens to bytes (fordi hver af de fire outputbytes efter den anden iteration i det væsentlige har 7 signifikante bits). Nu udfører vi et 2R-angreb for hvert nøglebytepar (for hver i fra 0 til 7). For at opnå hele 128-bit Ki-nøglen kræves der anmodninger.

Det er værd at bemærke, at angrebet kræver fysisk adgang til SIM-kortet, en kortlæser og en computer. For at udføre angrebet vil det være nødvendigt at sende omkring 150.000 anmodninger til SIM-kortet. Kortlæseren, som blev brugt af ISAAC-teamet, udførte 6,25 anmodninger i sekundet, og hele angrebet tog således 8 timer. Det tager meget kortere tid at analysere svar fra et SIM-kort end at sende anmodninger.

BGW over-the-air angreb

Marc Briceno, Ian Goldberg og David Wagner mener også, at et BGW-angreb kan udføres eksternt uden fysisk adgang til SIM-kortet. Desværre gennemførte de ikke eksperimentet, da det ville være i strid med amerikanske love. GSM-eksperter kontaktet af ISAAC-forskere bekræftede dog, at angrebet kunne implementeres i praksis. GSM-protokollernes egenskaber gør det muligt at udføre et BGW-angreb, hvis der kan oprettes en falsk BS. Fake BS er ikke forpligtet til at understøtte hele GSM-protokollen, men kun en del af dens funktioner. BGW over-the-air-angrebet er baseret på det faktum, at mobilstationen MS skal svare på enhver anmodning fra GSM-netværket. Hvis signalet fra den falske BS tilsidesætter signalet fra den legitime BS, kan angriberen sende anmodninger til mål-MS'en og genskabe Ki'en fra svarene modtaget fra MS'en. Det er værd at bemærke, at MS skal være tilgængelig for angriberen i hele den tid, hvor angrebet vil blive udført. Det er uvist, hvor lang tid et BGW luftangreb tager. Anslået otte til tretten timer.

Angrebet kan udføres i metroen, når signalet om en lovlig BS ikke er tilgængeligt, og telefonen er tændt. Brugeren vil ikke engang vide om det igangværende angreb, kun det faktum, at telefonens batteri tømmes hurtigere end normalt, kan advare ham. Angrebet kan også udføres stykkevis: I stedet for et otte timers angreb kan angriberen sende anmodninger i mindre perioder hver dag, for eksempel når brugeren skal på arbejde.

Marc Briceno, Ian Goldberg og David Wagner fremhæver det faktum, at på trods af kompleksiteten og omkostningerne ved denne type angreb, bør muligheden for deres implementering ikke ignoreres.

Partitioneringsangreb

I maj 2002 offentliggjorde en gruppe forskere fra IBM Watson Research Center sammen med forskere fra Swiss Federal Institute of Technology Zürich et distribueret angreb mod COMP128 . Den er baseret på Simple Power Analysis (SPA) og giver en nøgle på få minutter. Angrebet bruger SIM-kortprocessorens lave ydeevne. Den første substitution ved brug af T0-tabellen vælger således en af ​​512 værdier, 9 bit er påkrævet for at vælge en værdi. SIM-processoren kan dog kun få adgang til en 8-bit adresse. For at gøre dette skal bordet opdeles i to dele. Forskere fra IBM Watson Research Center foreslog, at tabellen er opdelt i to lige store dele. Ved at analysere SIM-kortets strømforbrug for forskellige anmodninger (samt elektromagnetisk stråling) fastslog forskerne, hvilken del af T0-tabellen anmodningen var rettet til. Ved at analysere adresseringen og strømforbruget af anmodninger ved ændring af den første byte af RAND[0], lykkedes det dem at finde K[0]. Ved at udføre en lignende analyse for andre RAND-bytes bliver Ki-nøglen fuldstændig gendannet.

Som et resultat kan angrebet udføres ved at sende 1000 tilfældige eller 255 specifikke anmodninger. Til sidst blev angrebet reduceret til 8 selvtilpassende anmodninger, hvilket giver dig mulighed for at få Ki på 2 sekunder. Angrebet er dog kun muligt med fysisk adgang til SIM-kortet.

Indhentning af Ki fra AuC

Præcis det samme angreb for at få Ki fra SIM kan udføres mod AuC. AuC'en skal svare på alle GSM-netværksanmodninger og udstede tripletter, der bruges til MS-autentificering. I det væsentlige ligner proceduren BGW-angrebet på SIM. Den eneste forskel er, at AuC behandler anmodninger meget hurtigere end SIM, fordi den skal behandle mange gange flere anmodninger. AuC-sikkerhed spiller en stor rolle, uanset om denne type angreb er mulig eller ej.

Falsk basestation

Det er vigtigt at bemærke, at godkendelse i GSM er envejs: telefonen (MS) godkendes af basestationen (BS), men basestationen (BS) godkendes ikke af telefonen (MS). Dette faktum gør angreb mulige, når en tredjepart udgiver sig for at være en legitim BS for en eller flere MS'er. En af antagelserne i udviklingen af ​​GSM var, at den slags angreb ville være meget dyre sammenlignet med andre typer angreb. Men prisen på BS er faldet hurtigt, og BS-emulatorer er ikke svære at finde i disse dage. Desuden er brugen af ​​kryptering for det aktuelle opkald ikke automatisk - kommunikationssessionen etableres ukrypteret, og først derefter sendes MS en kommando om at kryptere sessionen eller ej. Krypteringsstartkommandoen sendes ukrypteret og kontrolleres ikke på nogen måde i GSM-netværket. Ved at bruge en falsk BS er det således muligt at skabe en situation, hvor MS's kommunikationssession med den falske BS ikke er krypteret og let aflyttes; og kommunikationen mellem den falske BS (der udgiver sig som en legitim MS) og den legitime BS er krypteret. I dette tilfælde er det ikke let at spore denne form for angreb.

Se også

Links

Noter

  1. ↑ 3GPP. 3. generations partnerskabsprojekt; Teknisk specifikation Gruppetjenester og systemaspekter; Sikkerhedsrelaterede netværksfunktioner (udgave 9)  (eng.)  (link utilgængeligt) s. 50 (2009). Arkiveret fra originalen den 10. april 2012.
  2. ↑ H. Haverinen, J. Salowey. Extensible Authentication Protocol Method for Global System for Mobile Communications (GSM) og Subscriber Identity Modules (EAP-SIM)  (engelsk)  (link ikke tilgængeligt) s. 65 (2006). Arkiveret fra originalen den 10. april 2012.
 Symmetriske kryptosystemer
Stream-cifre
Feistel netværk
SP netværk
Andet