A3 (chiffer)

A3  är algoritmen som används i autentiseringsprocessen i den globala digitala standarden för mobil GSM -kommunikation . A3 är således en del av GSM -samtalsintegritetssystemet tillsammans med algoritmerna A5 och A8 . Algoritmens uppgift är att generera ett svar ( SRES-signed Response ) på ett slumpmässigt lösenord ( RAND-Random ) som tas emot av en mobiltelefon ( MS-Mobile Station ) från MSC-växeln ( MSC-Mobile Switching Center ) i autentiseringsprocedur. A3 är implementerad i abonnentens SIM-kort .

Autentiseringsprocess

Kärnan i autentisering i GSM  är att undvika kloning av användarens mobiltelefon. Den hemliga nyckeln är en 128-bitars nyckel Ki, som ägs av både abonnenten och Authentication Center ( AuC  - Authentication Center). Ki lagras i SIM-kortet , liksom A3-algoritmen. Även inblandade i autentiseringen är Home Location Registry ( HLR  - Home Location Registry) och Switching Center ( MSC  - Mobile Switching Center)

När en MS begär åtkomst till ett GSM-nätverk (t.ex. vid uppstart), måste MSC:n autentisera MS. För att göra detta sänder MSC till HLR en unik International Mobile Subscriber Identity ( IMSI  ) och en begäran om en uppsättning speciella tripletter. När HLR tar emot en IMSI-begäran om tripletter, kontrollerar den först sin databas för att säkerställa att MS med den IMSI faktiskt tillhör nätverket. Om verifieringen är framgångsrik, skickar HLR:n IMSI och en autentiseringsbegäran till AuC.

AuC använder IMSI för att hitta Ki som motsvarar den IMSI. AuC genererar också ett slumpmässigt 128-bitars RAND-nummer. Efter det beräknar AuC ett 32-bitars SRES-svar (SRES - Signed Response) med hjälp av A3-algoritmen: SRES = A3(RAND, Ki). Dessutom beräknar AUC en 64-bitars sessionsnyckel Kc med användning av A8 -algoritmen : Kc = A8(RAND, Ki). Kc används vidare i A5- algoritmen för att kryptera och dekryptera data.

RAND, SRES och Kc bildar bara de tripletter som MSC begärde från HLR. AuC genererar fem av dessa tripletter och skickar dem till HLR, sedan skickar HLR denna uppsättning till MSC. Det är uppsättningen av tripletter som genereras för att minska signaleringen i GSM-kärnnätet som skulle inträffa varje gång MS skulle begära åtkomst till nätet och MSC skulle behöva autentisera MS. Det bör noteras att en uppsättning tripletter är unik för en IMSI och inte kan användas för någon annan IMSI.

MSC:n sparar Kc och SRES och sänder en RAND-begäran till abonnentens mobilstation MS. Vid mottagande av RAND-begäran, beräknar MS svaret på SRES-begäran med användning av A3-algoritmen och den hemliga nyckeln Ki: SRES = A3(RAND, Ki), och skickar det till MSC. Om det mottagna SRES-värdet matchar SRES som är lagrat i MSC:n, anses autentiseringen vara framgångsrik.

Efter fem autentiseringssessioner ber MSC:n HLR om en ny uppsättning tripletter (RAND, SRES, Kc)

Beskrivning av algoritmen

Allmänna bestämmelser

In- och utdataformatet för A3-algoritmen, såväl som hela autentiseringsprocessen, är strikt definierade av 3GPP- konsortiet . Det är värt att notera att varje enskild operatör väljer funktionsprincipen för A3-algoritmen. Så A3 är inte standardiserat utan definieras av operatören. Men om operatören inte vill komma med sin egen A3-algoritm kan han använda standardimplementeringen av algoritmen.

För närvarande accepteras följande format för in- och utdata RAND, Ki, SRES för A3-algoritmen: Ki-längd - 128 bitar RAND-längd - 128 bitar SRES-längd - 32 bitar

Exekveringstiden för A3-algoritmen måste vara mindre än 500 millisekunder. [ett]

Följande standardimplementationer av A3-algoritmen är för närvarande kända:

COMP128 är den allra första versionen av A3-algoritmen. Till en början hölls COMP128-algoritmen hemlig. Utvecklarna av den första versionen av A3 förlitade sig på säkerhet på bekostnad av dunkel, vilket innebär att algoritmer är svårare att knäcka om de inte är offentligt tillgängliga. COMP-128 komprometterades dock av kryptoanalytikerna Marc Briceno, David Wagner och Ian Goldberg från säkerhetsforskningsgruppen ISAAC. Efter att COMP128-sårbarheterna publicerats utvecklades korrigerade versioner av COMP128-2 och COMP128-3.

COMP128

1998 läckte en beskrivning av COMP128-algoritmen till Internet. Även om beskrivningen inte var fullständig har koden återställts helt genom omvänd teknik och är nu tillgänglig för allmänheten .

I grund och botten är COMP128 en 128-bitars hashfunktion. Argumentets bredd är 256 bitar eller 32 byte (128 bitar Ki + 128 bitar RAND). De 32 mest signifikanta bitarna av det beräknade värdet tas som SRES, och de 64 minst signifikanta bitarna tas som sessionsnyckeln Kc. Låt X [0..32] vara 32-byte-ingången för algoritmen, där X [0..15] = Ki och X [16..31] = RAND. T0 [0..511], T1 [0..255], T2 [0..127], T3 [0..63] och T4 [0..31] är hemliga bytesubstitutionstabeller. Algoritmen består av 8 omgångar, varje omgång har 5 iterationer. Varje iteration består av att slå upp motsvarande tabell (T0 för den första iterationen, T1 för den andra, etc.) och bytesubstitution. I slutet av varje omgång, förutom den sista, permuteras de resulterande 128 bitarna av resultatet, och efter permutationen används dessa 128 bitar i nästa omgång. Beskrivning av en omgång i pseudokod:

(ersättningar) för i = 0 till 4 gör: för j = 0 till 2^i - 1 gör: för k = 0 till 2^(4-i) - 1 gör: { 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] } (bildning av bitar från bytes) för j = 0 till 31 gör: för k = 0 till 7 gör: { bit[4*j+k] = den (8-k):e biten i byte j } (permutation) om (i < 8) då för j = 0 till 15 gör: för k = 0 till 7 gör: { nästa bit = (8 xj + k) x 17 mod 128 Bit k av X[j + 16] = bit[next_bit] }

Vid varje iteration beror utdatabyten på de två inmatade byten. De två inmatningsbytena används för att identifiera ett element i uppslagstabellen. Detta element kommer att uppdatera utdatabyten. Uppslagstabellen för den i-te iterationen innehåller 2^(9 - i) element med storlek (8 - i) bitar. Det är

tabell antal element storleken på ett element T0 512 8 bitar T1 256 7 bitar T2 128 6 bitar T3 64 5 bitar T4 32 4 bitar

Faktum är att var och en av de 32 utmatade byten från den sista iterationen av omgången har endast 4 signifikanta bitar. Därför, i slutet av iterationen, omvandlas dessa 32 byte genom permutation till 16 byte, varav alla bitar är signifikanta. Dessa 16 bytes skrivs till X [16 .. 31], och nästa omgång av algoritmen startas (i X [0 .. 15] ändras inte värdet på Ki på något sätt).

David Wagner kallade denna struktur av algoritmen fjärilsstruktur, vilket betyder "i form av en fjäril"

COMP128-2 och COMP128-3

Även om det nu är klart att principen "säkerhet genom obscurity" inte fungerar, hålls versionerna COMP128-2 och COMP128-3 hemliga.

Milenage

Algoritmerna för Milenage-autentisering och generering av sessionsnyckel har utvecklats av 3GPP- konsortiet tillsammans med 3GPP-medlemsorganisationer. Det finns inga ytterligare krav eller behörigheter som krävs för att använda dessa algoritmer. Ett exempel på hur man använder Milenage som A3 visas i 3GPP TS 55.205 "Specifikation av GSM-MILENAGE Algorithms: En exempelalgoritm för GSM-autentiserings- och nyckelgenereringsfunktionerna A3 och A8" . Den fullständiga Milenage-specifikationen finns tillgänglig på 3GPP-konsortiets webbplats.

Milenage är immun mot alla kända attacker. [2]

Möjliga attacker

Attacker på COMP128

BGW Attack

Den 13 april 1998 publicerade Marc Briceno, Ian Goldberg och David Wagner en artikel där de beskrev en metod för att erhålla en hemlig nyckel Ki genom att skicka cirka 150 000 förfrågningar till SIM-kortet. Attacken utnyttjar en flaskhals i algoritmen.

Efter den andra iterationen av den första omgången beror byten X[i], X[i+8], X[i+16], X[i+24] endast på indatabytes med samma index. Byte X[i] och X[i+8] är nyckelbyte, dvs X[i] = Ki[i] och X[i+8] = Ki[i+8] (för varje i från 0 till 7) , och X[i+16] och X[i+24] byte är RAND-begäran byte från basstationen, dvs X[i+16] = RAND[i+16] och X[i+24] = RAND[ i+24] (för varje i från 0 till 7).

Vi ändrar nu byte i+16, i+24 för ingången för COMP128-algoritmen (det vill säga byte i, i+8 för RAND-frågan), och lämnar de återstående inmatningsbytena konstanta. Eftersom en iteration inte är en-till-en, kan man förvänta sig en kollision i utdatabytes numrerade i, i+8,i+16,i+24 efter den andra iterationen. " Födelsedagsparadoxen " säkerställer att kollisionen sker ganska snabbt (eftersom flaskhalsen är begränsad till 4 byte). Kollisioner vid flaskhalsen kan upptäckas eftersom de kommer att få utgångarna från COMP128-algoritmen att kollidera (det vill säga vi kommer att få två identiska SRES-svar), och varje kollision kan användas för att erhålla två byte av nyckeln i, i + 8 (med hänsyn till den lilla bearbetningen av de två första iterationerna - det vill säga att tillämpa en 2R-attack i termer av differentiell kryptoanalys).

Detta skulle kräva några COMP128-inmatningsfrågor för att hitta nyckelns två byte (eftersom var och en av de fyra utgångsbytena efter den andra iterationen i huvudsak har 7 signifikanta bitar). Nu utför vi en 2R-attack för varje nyckelbytepar (för varje i från 0 till 7). För att erhålla hela 128-bitars Ki-nyckeln kommer förfrågningar att krävas.

Värt att notera är att attacken kräver fysisk åtkomst till SIM-kortet, en kortläsare och en dator. För att genomföra attacken kommer det att vara nödvändigt att skicka cirka 150 000 förfrågningar till SIM-kortet. Kortläsaren som användes av ISAAC-teamet gjorde 6,25 förfrågningar per sekund, och hela attacken tog alltså 8 timmar. Det tar mycket mindre tid att analysera svar från ett SIM-kort än att skicka förfrågningar.

BGW over-the-air attack

Marc Briceno, Ian Goldberg och David Wagner tror också att en BGW-attack kan utföras på distans utan fysisk åtkomst till SIM-kortet. Tyvärr genomförde de inte experimentet, eftersom det skulle strida mot amerikanska lagar. GSM-experter som kontaktats av ISAAC-forskare bekräftade dock att attacken kunde genomföras i praktiken. Egenskaperna för GSM-protokollen gör att en BGW-attack kan utföras om en falsk BS kan skapas. Fake BS behöver inte stödja hela GSM-protokollet, utan bara en del av dess funktioner. BGW over-the-air-attacken är baserad på det faktum att mobilstationen MS behöver svara på varje begäran som görs av GSM-nätet. Om signalen från den falska BS:en åsidosätter signalen från den legitima BS:en, kan angriparen skicka förfrågningar till mål-MS och återskapa Ki från svaren som mottagits från MS. Det är värt att notera att MS måste vara tillgänglig för angriparen under hela tiden under vilken attacken kommer att utföras. Det är okänt hur lång tid en BGW luftattack tar. Uppskattningsvis åtta till tretton timmar.

Attacken kan utföras i tunnelbanan när signalen om en laglig BS inte är tillgänglig och telefonen är påslagen. Användaren kommer inte ens veta om den pågående attacken, bara det faktum att telefonens batteri laddas ur snabbare än vanligt kan varna honom. Attacken kan också utföras bitvis: istället för en åtta timmar lång attack kan angriparen skicka förfrågningar under kortare tidsperioder varje dag, till exempel när användaren går till jobbet.

Marc Briceno, Ian Goldberg och David Wagner lyfter fram det faktum att trots komplexiteten och kostnaderna för denna typ av attacker, bör möjligheten att de genomförs inte ignoreras.

Partitioneringsattack

I maj 2002 publicerade en grupp forskare från IBM Watson Research Center, tillsammans med forskare från det schweiziska federala tekniska institutet Zürich , en distribuerad attack mot COMP128 . Den är baserad på Simple Power Analysis (SPA) och ger en nyckel på några minuter. Attacken använder SIM-kortprocessorns låga prestanda. Således väljer den första substitutionen som använder TO-tabellen ett av 512 värden, 9 bitar krävs för att välja ett värde. SIM-processorn kan dock bara komma åt en 8-bitars adress. För att göra detta måste bordet delas upp i två delar. Forskare från IBM Watson Research Center föreslog att tabellen är uppdelad i två lika delar. Genom att analysera SIM-kortets strömförbrukning för olika förfrågningar (liksom elektromagnetisk strålning) bestämde forskarna till vilken del av T0-tabellen begäran riktades. Genom att analysera adresseringen och energiförbrukningen för förfrågningar när de ändrade den första byten av RAND[0], lyckades de hitta K[0]. Genom att utföra en liknande analys för andra RAND-bytes återställs Ki-nyckeln helt.

Som ett resultat kan attacken utföras genom att skicka 1000 slumpmässiga eller 255 specifika förfrågningar. Till slut reducerades attacken till 8 självanpassande förfrågningar, vilket gör att du kan få Ki på 2 sekunder. Attacken är dock endast möjlig med fysisk åtkomst till SIM-kortet.

Skaffa Ki från AuC

Exakt samma attack för att få Ki från SIM kan utföras mot AuC. AuC:n ska svara på alla GSM-nätförfrågningar och utfärda tripletter som används för MS-autentisering. I huvudsak liknar proceduren BGW-attacken på SIM. Den enda skillnaden är att AuC behandlar förfrågningar mycket snabbare än SIM, eftersom det behöver behandla många gånger fler förfrågningar. AuC-säkerhet spelar en stor roll, oavsett om denna typ av attack är möjlig eller inte.

Falsk basstation

Det är viktigt att notera att autentisering i GSM är enkelriktad: telefonen (MS) autentiseras av basstationen (BS), men basstationen (BS) autentiseras inte av telefonen (MS). Detta faktum gör attacker möjliga när en tredje part utger sig för att vara en legitim BS för en eller flera MS. Ett av antagandena i utvecklingen av GSM var att den här typen av attacker skulle bli mycket dyra jämfört med andra typer av attacker. Kostnaden för BS har dock sjunkit snabbt och BS-emulatorer är inte svåra att hitta nuförtiden. Dessutom är användningen av kryptering för det aktuella samtalet inte automatisk - kommunikationssessionen upprättas okrypterad och först då skickas MS ett kommando att kryptera sessionen eller inte. Kommandot för start av kryptering skickas okrypterat och kontrolleras inte på något sätt inom GSM-nätverket. Med användning av en falsk BS är det således möjligt att skapa en situation där MS:s kommunikationssession med den falska BS:en inte är krypterad och lätt avlyssnas; och kommunikationen mellan den falska BS (som poserar som en legitim MS) och den legitima BS är krypterad. I det här fallet är det inte lätt att spåra denna typ av attack.

Se även

Länkar

Anteckningar

  1. ↑ 3GPP. 3:e generationens partnerskapsprojekt; Teknisk specifikation Grupptjänster och systemaspekter; Säkerhetsrelaterade nätverksfunktioner (Release 9)  (eng.)  (länk ej tillgänglig) s. 50 (2009). Arkiverad från originalet den 10 april 2012.
  2. ↑ H. Haverinen, J. Salowey. Extensible Authentication Protocol Method for Global System for Mobile Communications (GSM) och Subscriber Identity Modules (EAP-SIM)  (engelska)  (länk ej tillgänglig) s. 65 (2006). Arkiverad från originalet den 10 april 2012.
 Symmetriska kryptosystem
Streama chiffer
Feistel nätverk
SP nätverk
Övrig