A3 (šifra)

A3  je algoritmus používaný v procesu ověřování v globálním digitálním standardu pro mobilní celulární komunikaci GSM . A3 je tedy prvkem systému utajení hovorů GSM spolu s algoritmy A5 a A8 . Úkolem algoritmu je vygenerovat odpověď ( SRES - Signed Response ) na náhodné heslo ( RAND - Random ) přijaté mobilním telefonem ( MS - Mobile Station ) z ústředny MSC ( MSC - Mobile Switching Center ) v autentizační procedura. A3 je implementován v SIM kartě účastníka .

Proces autentizace

Podstatou autentizace v GSM  je vyhnout se klonování mobilního telefonu uživatele. Tajným klíčem je 128bitový klíč Ki, který vlastní jak předplatitel, tak autentizační centrum ( AuC  - Authentication Center). Ki je uložena na SIM kartě , stejně jako algoritmus A3. Na autentizaci se podílí také Home Location Registry ( HLR  - Home Location Registry) a Switching Center ( MSC  - Mobile Switching Center)

Když MS požaduje přístup do GSM sítě (např. při zapnutí), MSC musí autentizovat MS. Za tímto účelem odešle MSC do HLR jedinečnou mezinárodní identitu mobilního předplatitele ( IMSI  ) a požadavek na sadu speciálních trojic. Když HLR obdrží požadavek IMSI na triplety, nejprve zkontroluje svou databázi , aby se ujistil, že MS s touto IMSI skutečně patří do sítě. Pokud je ověření úspěšné, pak HLR odešle IMSI a požadavek na ověření do AuC.

AuC používá IMSI k nalezení Ki odpovídající této IMSI. AuC také generuje náhodné 128bitové číslo RAND. Poté AuC vypočítá 32bitovou odpověď SRES (SRES - Signed Response) pomocí algoritmu A3: SRES = A3(RAND, Ki). Navíc AUC vypočítává 64bitový klíč relace Kc pomocí algoritmu A8 : Kc = A8(RAND, Ki). Kc se dále používá v algoritmu A5 k šifrování a dešifrování dat.

RAND, SRES a Kc právě tvoří triplety, které MSC požadoval od HLR. AuC vygeneruje pět těchto tripletů a odešle je do HLR, poté HLR odešle tuto sadu do MSC. Je to sada trojic, která je generována pro snížení signalizace v jádrové síti GSM , která by nastala pokaždé, když by MS požadovala přístup do sítě a MSC by musela autentizovat MS. Je třeba poznamenat, že sada trojic je jedinečná pro jednu IMSI a nelze ji použít pro žádnou jinou IMSI.

MSC uloží Kc a SRES a odešle požadavek RAND do mobilní stanice MS účastníka. Po přijetí požadavku RAND vypočítá MS odpověď na požadavek SRES pomocí algoritmu A3 a tajného klíče Ki: SRES = A3(RAND, Ki) a odešle ji do MSC. Pokud přijatý SRES odpovídá SRES uloženým v MSC, pak se autentizace považuje za úspěšnou.

Po pěti autentizačních relacích MSC požádá HLR o novou sadu trojic (RAND, SRES, Kc)

Popis algoritmu

Obecná ustanovení

Formát vstupních a výstupních dat pro algoritmus A3, stejně jako celý proces autentizace, jsou striktně definovány konsorciem 3GPP . Stojí za zmínku, že každý jednotlivý operátor volí princip fungování algoritmu A3. Takže A3 není standardizováno, ale je definováno operátorem. Pokud však operátor nechce přijít s vlastním algoritmem A3, může použít standardní implementaci algoritmu.

V současné době je akceptován následující formát vstupních a výstupních dat RAND, Ki, SRES algoritmu A3: Délka Ki - 128 bitů Délka RAND - 128 bitů Délka SRES - 32 bitů

Doba provádění algoritmu A3 musí být kratší než 500 milisekund. [jeden]

V současné době jsou známy následující standardní implementace algoritmu A3:

COMP128 je úplně první verze algoritmu A3. Zpočátku byl algoritmus COMP128 držen v tajnosti. Vývojáři první verze A3 se spoléhali na bezpečnost na úkor nejasností, což znamená, že algoritmy je těžší prolomit, pokud nejsou veřejně dostupné. Nicméně, COMP-128 byl kompromitován kryptoanalytiky Marcem Bricenem, Davidem Wagnerem a Ianem Goldbergem z bezpečnostní výzkumné skupiny ISAAC Po zveřejnění zranitelností COMP128 byly vyvinuty opravené verze COMP128-2 a COMP128-3.

COMP128

V roce 1998 unikl na internet popis algoritmu COMP128. Přestože popis nebyl úplný, kód byl plně obnoven pomocí reverzního inženýrství a je nyní k dispozici veřejnosti .

COMP128 je v podstatě 128bitová hašovací funkce. Šířka argumentu je 256 bitů nebo 32 bajtů (128 bitů Ki + 128 bitů RAND). 32 nejvýznamnějších bitů vypočtené hodnoty se bere jako SRES a 64 nejnižších bitů se bere jako klíč relace Kc. Nechť X [0..32] je 32bajtový vstup algoritmu, kde X [0..15] = Ki a X [16..31] = RAND. T0 [0..511], T1 [0..255], T2 [0..127], T3 [0..63] a T4 [0..31] jsou tajné bajtové substituční tabulky. Algoritmus se skládá z 8 kol, každé kolo má 5 iterací. Každá iterace se skládá z vyhledání odpovídající tabulky (T0 pro první iteraci, T1 pro druhou atd.) a substituce bajtů. Na konci každého kola, kromě posledního, je permutováno výsledných 128 bitů výsledku a po permutaci je těchto 128 bitů použito v dalším kole. Popis jednoho kola v pseudokódu:

(náhrady) pro i = 0 až 4 udělejte: pro j = 0 až 2^i - 1 udělat: pro k = 0 až 2^(4-i) - 1 udělat: { 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] } (tvorba bitů z bajtů) pro j = 0 až 31 proveďte: pro k = 0 až 7 udělejte: { bit[4*j+k] = (8-k)-tý bit bajtu j } (permutace) if (i < 8) pak pro j = 0 až 15 proveďte: pro k = 0 až 7 udělejte: { další bit = (8 xj + k) x 17 mod 128 Bit k z X[j + 16] = bit[další_bit] }

Při každé iteraci závisí výstupní bajt na dvou vstupních bytech. Dva vstupní bajty se používají k identifikaci prvku ve vyhledávací tabulce. Tento prvek aktualizuje výstupní bajt. Vyhledávací tabulka pro i-tou iteraci obsahuje 2^(9 - i) prvky velikosti (8 - i) bitů. To znamená

tabulka počet prvků velikost jednoho prvku T0 512 8 bit T1 256 7 bit T2 128 6 bit T3 64 5 bit T4 32 4 bitů

Ve skutečnosti má každý z 32 výstupních bajtů poslední iterace kola pouze 4 platné bity. Proto se na konci iterace těchto 32 bajtů převede permutací na 16 bajtů, z nichž všechny bity jsou významné. Těchto 16 bajtů se zapíše do X [16 .. 31] a spustí se další kolo algoritmu (v X [0 .. 15] se hodnota Ki nijak nemění).

David Wagner nazval tuto strukturu algoritmu motýlí strukturou, což znamená „ve tvaru motýla“

COMP128-2 a COMP128-3

I když je nyní jasné, že princip „zabezpečení utajením“ nefunguje, verze COMP128-2 a COMP128-3 jsou drženy v tajnosti.

Milenage

Algoritmy pro autentizaci Milenage a generování klíčů relace byly vyvinuty konsorciem 3GPP ve spojení s úsilím členských organizací 3GPP. Pro použití těchto algoritmů nejsou vyžadovány žádné další požadavky ani oprávnění. Příklad použití Milenage jako A3 je uveden v 3GPP TS 55.205 "Specifikace algoritmů GSM-MILENAGE: Příklad sady algoritmů pro funkce GSM Authentication a Key Generation A3 a A8" . Kompletní specifikace Milenage je k dispozici na webu konsorcia 3GPP.

Milenage je imunní vůči jakýmkoli známým útokům. [2]

Možné útoky

Útoky na COMP128

BGW Attack

Marc Briceno, Ian Goldberg a David Wagner publikovali 13. dubna 1998 článek , ve kterém popsali způsob získání tajného klíče Ki odesláním asi 150 000 požadavků na SIM kartu. Útok využívá úzké místo v algoritmu.

Po druhé iteraci prvního kola jsou bajty X[i], X[i+8], X[i+16], X[i+24] závislé pouze na vstupních bytech se stejnými indexy. Bajty X[i] a X[i+8] jsou klíčové bajty, tj. X[i] = Ki[i] a X[i+8] = Ki[i+8] (pro každé i od 0 do 7), a X[i+16] a X[i+24] bajty jsou bajty požadavku RAND ze základnové stanice, tj. X[i+16] = RAND[i+16] a X[i+24] = RAND[ i+24] (pro každé i od 0 do 7).

Nyní změníme bajty i+16, i+24 vstupu algoritmu COMP128 (tj. bajty i, i+8 dotazu RAND), přičemž zbývající vstupní bajty ponecháme konstantní. Vzhledem k tomu, že jedna iterace není jedna ku jedné, lze očekávat kolizi výstupních bytů očíslovaných i, i+8,i+16,i+24 po druhé iteraci. " Narozeninový paradox " zajišťuje, že ke kolizi dojde poměrně rychle (protože úzké místo je omezeno na 4 bajty). Kolize na úzkém místě mohou být detekovány, protože způsobí kolizi výstupů algoritmu COMP128 (to znamená, že dostaneme dvě identické odpovědi SRES), a každou kolizi lze použít k získání dvou bajtů klíče i, i + 8 (s přihlédnutím k malému zpracování prvních dvou iterací — to znamená použití 2R útoku z hlediska diferenciální kryptoanalýzy).

To by vyžadovalo nějaké vstupní dotazy COMP128 k nalezení dvou bajtů klíče (protože každý ze čtyř výstupních bajtů po druhé iteraci má v podstatě 7 platných bitů). Nyní provedeme útok 2R pro každý klíčový bajtový pár (pro každé i od 0 do 7). K získání celého 128bitového klíče Ki tedy budou vyžadovány požadavky.

Za zmínku stojí, že útok vyžaduje fyzický přístup k SIM kartě, čtečce karet a počítači. K provedení útoku bude nutné odeslat na SIM kartu asi 150 000 požadavků. Čtečka karet, kterou používal tým ISAAC, provedla 6,25 požadavků za sekundu a celý útok tak trval 8 hodin. Analýza odpovědí ze SIM karty trvá mnohem méně času než odesílání požadavků.

BGW útok vzduchem

Marc Briceno, Ian Goldberg a David Wagner také věří, že útok BGW lze provést na dálku bez fyzického přístupu k SIM kartě. Bohužel experiment neprovedli, protože by to bylo v rozporu s americkými zákony. Odborníci na GSM, které kontaktovali výzkumníci ISAAC, však potvrdili, že útok lze v praxi realizovat. Vlastnosti GSM protokolů umožňují provést BGW útok, pokud lze vytvořit falešnou BS. Falešná BS nemusí podporovat celý GSM protokol, ale pouze část jeho funkcí. Bezdrátový útok BGW je založen na skutečnosti, že mobilní stanice MS musí reagovat na každý požadavek GSM sítě. Pokud signál z falešné BS přepíše signál z legitimní BS, útočník může posílat požadavky do cílové MS a znovu vytvořit Ki z odpovědí přijatých z MS. Za zmínku stojí, že MS musí být útočníkovi k dispozici po celou dobu, po kterou bude útok prováděn. Není známo, jak dlouho trvá útok BGW vzduchem. Odhadem osm až třináct hodin.

Útok lze provést v metru, když není dostupný signál legální BS a telefon je zapnutý. Uživatel se o probíhajícím útoku ani nedozví, upozornit ho může pouze fakt, že se baterie telefonu vybíjí rychleji než obvykle. Útok lze provádět i po částech: namísto osmihodinového útoku může útočník každý den posílat požadavky na kratší časové úseky, například když uživatel chodí do práce.

Marc Briceno, Ian Goldberg a David Wagner zdůrazňují skutečnost, že navzdory složitosti a ceně tohoto typu útoku by možnost jejich implementace neměla být ignorována.

Partitioning Attack

V květnu 2002 zveřejnila skupina výzkumníků z IBM Watson Research Center společně s výzkumníky ze Švýcarského federálního technologického institutu v Curychu distribuovaný útok proti COMP128 . Je založen na Simple Power Analysis (SPA) a poskytuje klíč během několika minut. Útok využívá nízký výkon procesoru SIM karty. První substituce pomocí tabulky TO tedy vybere jednu z 512 hodnot, k výběru jedné hodnoty je zapotřebí 9 bitů. Procesor SIM však může přistupovat pouze k 8bitové adrese. K tomu je třeba tabulku rozdělit na dvě části. Výzkumníci IBM Watson Research Center navrhli, aby byla tabulka rozdělena na dvě stejné části. Analýzou spotřeby energie SIM karty pro různé požadavky (a také elektromagnetického záření) vědci určili, do které části tabulky T0 byl požadavek adresován. Analýzou adresování a spotřeby energie požadavků při změně prvního bajtu RAND[0] se jim podařilo najít K[0]. Provedením podobné analýzy pro další bajty RAND je klíč Ki zcela obnoven.

Výsledkem je, že útok lze provést zasláním 1000 náhodných nebo 255 specifických požadavků. Nakonec byl útok zredukován na 8 samopřizpůsobivých požadavků, což umožňuje získat Ki za 2 sekundy. Útok je však možný pouze s fyzickým přístupem k SIM kartě.

Získání Ki z AuC

Přesně stejný útok na získání Ki ze SIM lze provést proti AuC. AuC odpovídá na všechny požadavky GSM sítě a vydává triplety používané pro MS autentizaci. V podstatě je postup podobný útoku BGW na SIM. Jediný rozdíl je v tom, že AuC zpracovává požadavky mnohem rychleji než SIM, protože potřebuje zpracovat mnohonásobně více požadavků. Bezpečnost AuC hraje velkou roli, ať už je tento typ útoku možný nebo ne.

Falešná základnová stanice

Je důležité si uvědomit, že autentizace v GSM je jednosměrná: telefon (MS) je autentizován základnovou stanicí (BS), ale základnová stanice (BS) není autentizována telefonem (MS). Tato skutečnost umožňuje útoky, když třetí strana předstírá, že je legitimní BS pro jeden nebo více MS. Jedním z předpokladů při vývoji GSM bylo, že tyto druhy útoků budou ve srovnání s jinými typy útoků velmi drahé. Náklady na BS však rychle klesly a emulátory BS v dnešní době není těžké najít. Navíc použití šifrování pro aktuální hovor není automatické - komunikační relace je navázána nešifrovaně a teprve poté je na MS odeslán příkaz, zda relaci zašifrovat či nikoliv. Příkaz spuštění šifrování je zasílán nešifrovaně a není nijak kontrolován v rámci GSM sítě. S použitím falešné BS je tedy možné vytvořit situaci, kdy komunikační relace MS s falešnou BS není šifrována a je snadno odposlouchávána; a komunikace mezi falešnou BS (vystupující jako legitimní MS) a legitimní BS je šifrována. V tomto případě není vystopování tohoto druhu útoku snadné.

Viz také

Odkazy

Poznámky

  1. ↑ 3GPP. Projekt partnerství 3. generace; Služby skupiny technických specifikací a systémové aspekty; Síťové funkce související se zabezpečením (Vydání 9)  (anglicky)  (odkaz není k dispozici) s. 50 (2009). Archivováno z originálu 10. dubna 2012.
  2. ↑ H. Haverinen, J. Salowey. Metoda protokolu Extensible Authentication Protocol pro globální systém pro mobilní komunikaci (GSM) a moduly identity předplatitele (EAP-SIM)  (anglicky)  (odkaz není k dispozici) str. 65 (2006). Archivováno z originálu 10. dubna 2012.
 Symetrické kryptosystémy
Streamové šifry
Síť Feistel
Síť SP
jiný