A3 (rejtjel)

Az A3 a GSM mobil cellás kommunikáció globális digitális szabványának hitelesítési folyamatában  használt algoritmus . Az A3 tehát a GSM hívásvédelmi rendszer eleme az A5 és A8 algoritmusokkal együtt . Az algoritmus feladata, hogy választ generáljon ( SRES-Signed Response ) egy véletlenszerű jelszóra ( RAND-Random ), amelyet egy mobiltelefon ( MS-Mobile Station ) kapott az MSC kapcsolóközponttól ( MSC-Mobile Switching Center ) hitelesítési eljárás. Az A3 az előfizető SIM kártyájában van megvalósítva.

Hitelesítési folyamat

A GSM -ben a hitelesítés lényege,  hogy elkerüljük a felhasználó mobiltelefonjának klónozását. A titkos kulcs egy 128 bites Ki kulcs, amely mind az előfizető, mind a hitelesítési központ ( AuC  - Authentication Center) tulajdonában van. A Ki a SIM-kártyán van tárolva , akárcsak az A3-as algoritmus. A hitelesítésben részt vesz a Home Location Registry ( HLR  - Home Location Registry) és a Switching Center ( MSC  - Mobile Switching Center) is.

Amikor egy MS hozzáférést kér egy GSM hálózathoz (pl. bekapcsoláskor), az MSC-nek hitelesítenie kell az MS-t. Ennek érdekében az MSC elküldi a HLR-nek egy egyedi nemzetközi mobil-előfizetői azonosítót ( IMSI  ) és egy speciális hármaskészletre vonatkozó kérést. Amikor a HLR kap egy IMSI-kérést a tripletekre, először ellenőrzi az adatbázisát , hogy megbizonyosodjon arról, hogy az IMSI-vel rendelkező MS valóban a hálózathoz tartozik. Ha az ellenőrzés sikeres, akkor a HLR elküldi az IMSI-t és egy hitelesítési kérelmet az AuC-nek.

Az AuC az IMSI segítségével keresi meg az adott IMSI-nek megfelelő Ki-t. Az AuC véletlenszerű 128 bites RAND számot is generál. Ezt követően az AuC kiszámít egy 32 bites SRES választ (SRES - Signed Response) az A3 algoritmus segítségével: SRES = A3(RAND, Ki). Ezenkívül az AUC kiszámít egy 64 bites Kc munkamenet kulcsot az A8 algoritmus segítségével : Kc = A8(RAND, Ki). A Kc-t az A5 algoritmusban is használják az adatok titkosítására és visszafejtésére.

A RAND, SRES és Kc csak azokat a hármasokat alkotják, amelyeket az MSC kért a HLR-től. Az AuC öt hármast generál és elküldi a HLR-nek, majd a HLR elküldi ezt a készletet az MSC-nek. Ez az a hármashalmaz, amelyet azért állítanak elő, hogy csökkentsék a jelzést a GSM maghálózatban , amely minden alkalommal előfordulna, amikor az MS hozzáférést kér a hálózathoz, és az MSC-nek hitelesítenie kell az MS-t. Meg kell jegyezni, hogy a hármasok egy készlete egyedi az IMSI-ben, és nem használható semmilyen más IMSI-hez.

Az MSC elmenti a Kc-t és az SRES-t, és RAND kérést küld az előfizető MS mobilállomásának. A RAND kérés vételekor az MS az A3 algoritmus és a Ki titkos kulcs segítségével kiszámítja a választ az SRES kérésre: SRES = A3(RAND, Ki), és elküldi az MSC-nek. Ha a fogadott SRES megegyezik az MSC-ben tárolt SRES-sel, akkor a hitelesítés sikeresnek minősül.

Öt hitelesítési munkamenet után az MSC új hármaskészletet kér a HLR-től (RAND, SRES, Kc)

Az algoritmus leírása

Általános rendelkezések

Az A3 algoritmus bemeneti és kimeneti adatformátumát, valamint a teljes hitelesítési folyamatot szigorúan a 3GPP konzorcium határozza meg . Érdemes megjegyezni, hogy minden egyes operátor választja ki az A3 algoritmus működési elvét. Tehát az A3 nem szabványos, hanem az operátor határozza meg. Ha azonban az operátor nem akar saját A3-as algoritmussal előállni, használhatja az algoritmus szabványos implementációját.

Jelenleg az A3 algoritmus RAND, Ki, SRES bemeneti és kimeneti adatainak következő formátuma elfogadott: Ki hossza - 128 bit RAND hosszúság - 128 bit SRES hossz - 32 bit

Az A3 algoritmus végrehajtási idejének 500 ezredmásodpercnél rövidebbnek kell lennie. [egy]

Jelenleg az A3 algoritmus következő szabványos megvalósításai ismertek:

A COMP128 az A3-as algoritmus legelső változata. Kezdetben a COMP128 algoritmust titokban tartották. Az A3 első verziójának fejlesztői a biztonságra hagyatkoztak az ismeretlenség rovására, vagyis az algoritmusokat nehezebb feltörni, ha nem nyilvánosak. A COMP-128-at azonban feltörték Marc Briceno, David Wagner és Ian Goldberg, az ISAAC biztonsági kutatócsoportjának kriptoanalitikusai. A COMP128 sebezhetőségek közzététele után a COMP128-2 és a COMP128-3 javított verzióit fejlesztették ki.

COMP128

1998-ban a COMP128 algoritmus leírása kiszivárgott az internetre. Bár a leírás nem volt teljes, a kódot visszafejtéssel teljesen visszaállították, és most már elérhető a nyilvánosság számára .

Alapvetően a COMP128 egy 128 bites hash függvény. Az argumentum szélessége 256 bit vagy 32 bájt (128 bit Ki + 128 bit RAND). A számított érték 32 legjelentősebb bitjét SRES-nek vesszük, a 64 legkevésbé jelentős bitet pedig Kc munkamenetkulcsnak. Legyen X [0..32] az algoritmus 32 bájtos bemenete, ahol X [0..15] = Ki és X [16..31] = RAND. T0 [0..511], T1 [0..255], T2 [0..127], T3 [0..63] és T4 [0..31] titkos bájthelyettesítési táblák. Az algoritmus 8 körből áll, minden körben 5 iteráció van. Minden iteráció a megfelelő tábla megkereséséből áll (T0 az első iterációhoz, T1 a másodikhoz stb.) és bájthelyettesítésből. Minden kör végén, az utolsó kivételével, az eredmény 128 bitjét permutáljuk, majd a permutáció után ezt a 128 bitet használjuk fel a következő körben. Egy kör leírása pszeudokódban:

(helyettesítések) ha i = 0-tól 4-ig, tegye: ha j = 0 és 2^i - 1, tegye: ha k = 0-tól 2-ig^(4-i) - 1 tegye: { 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] } (bitek előállítása bájtokból) j = 0 és 31 között tegye a következőket: k = 0 és 7 között tegye a következőket: { bit[4*j+k] = a j bájt (8-k)-ik bitje } (permutáció) ha (i < 8) akkor j = 0 és 15 között tegye a következőket: k = 0 és 7 között tegye a következőket: { következő bit = (8 xj + k) x 17 mod 128 X[j + 16] k bitje = bit[következő_bit] }

Minden iterációnál a kimeneti bájt a két bemeneti bájttól függ. A két bemeneti bájt egy elem azonosítására szolgál a keresési táblázatban. Ez az elem frissíti a kimeneti bájtot. Az i-edik iteráció keresőtáblája 2^(9 - i) (8 - i) bites méretű elemet tartalmaz. Azaz

táblázat elemek száma egy elem mérete T0 512 8 bites T1 256 7 bites T2 128 6 bites T3 64 5 bites T4 32 4 bites

Valójában a forduló utolsó iterációjának 32 kimeneti bájtja csak 4 jelentős bittel rendelkezik. Ezért az iteráció végén ezt a 32 bájtot permutációval 16 bájtokká alakítják, amelyeknek minden bitje szignifikáns. Ezt a 16 bájtot X-be írjuk [16 .. 31], és elindul az algoritmus következő köre (X [0 .. 15]-ben a Ki értéke semmilyen módon nem változik).

David Wagner az algoritmus ezt a struktúráját pillangó szerkezetnek nevezte, ami azt jelenti, hogy „pillangó alakú”.

COMP128-2 és COMP128-3

Bár ma már világos, hogy a "biztonság az ismeretlenség által" elv nem működik, a COMP128-2 és COMP128-3 változatokat titokban tartják.

Milenage

A Milenage hitelesítési és munkamenetkulcs-generáló algoritmusokat a 3GPP konzorcium fejlesztette ki a 3GPP tagszervezetek közös erőfeszítésével. Nincsenek további követelmények vagy engedélyek ezeknek az algoritmusoknak a használatához. Példa a Milenage használatára A3-ként a 3GPP TS 55.205 "GSM-MILENAGE algoritmusok specifikációja: példaalgoritmuskészlet az A3 és A8 GSM hitelesítési és kulcsgenerálási funkciókhoz" című dokumentumban látható . A teljes Milenage specifikáció elérhető a 3GPP konzorcium honlapján.

A Milenage immunis minden ismert támadásra. [2]

Lehetséges támadások

Támadások a COMP128 ellen

BGW Attack

1998. április 13-án Marc Briceno, Ian Goldberg és David Wagner publikált egy cikket , amelyben leírtak egy módszert a Ki titkos kulcs megszerzésére úgy, hogy körülbelül 150 000 kérést küldenek a SIM-kártyára. A támadás az algoritmus szűk keresztmetszetét használja ki.

Az első kör második iterációja után az X[i], X[i+8], X[i+16], X[i+24] bájtok csak az azonos indexű bemeneti bájtoktól függenek. Az X[i] és X[i+8] bájtok kulcsbájtok, azaz X[i] = Ki[i] és X[i+8] = Ki[i+8] (mindegyik i-hez 0 és 7 között), az X[i+16] és X[i+24] bájtok pedig a bázisállomás RAND kérési bájtjai, azaz X[i+16] = RAND[i+16] és X[i+24] = RAND[ i+24] (minden i-hez 0-tól 7-ig).

Most megváltoztatjuk a COMP128 algoritmus bemenetének i+16, i+24 bájtjait (vagyis a RAND lekérdezés i, i+8 bájtjait), a fennmaradó bemeneti bájtokat állandóan hagyva. Mivel egy iteráció nem egy az egyhez, a második iteráció után az i, i+8,i+16,i+24 kimeneti bájtok ütközésére számíthatunk. A " születésnapi paradoxon " biztosítja, hogy az ütközés meglehetősen gyorsan megtörténjen (mivel a szűk keresztmetszet 4 bájtra korlátozódik). A szűk keresztmetszetben lévő ütközések észlelhetők, mivel ezek a COMP128 algoritmus kimenetei ütközését okozzák (vagyis két azonos SRES választ kapunk), és minden ütközésből az i, i + kulcs két bájtja nyerhető. 8 (figyelembe véve az első két iteráció csekély feldolgozását – vagyis a 2R támadást a differenciális kriptográfiai elemzés szempontjából).

Ehhez néhány COMP128 bemeneti lekérdezésre lenne szükség a kulcs két bájtjának megtalálásához (mivel a második iteráció utáni négy kimeneti bájt mindegyike lényegében 7 jelentős bittel rendelkezik). Most egy 2R támadást hajtunk végre minden kulcsbájtpárra (minden i-re 0-tól 7-ig). Így a teljes 128 bites Ki kulcs beszerzéséhez kérésekre lesz szükség.

Érdemes megjegyezni, hogy a támadáshoz fizikai hozzáférés szükséges a SIM-kártyához, egy kártyaolvasóhoz és egy számítógéphez. A támadás végrehajtásához körülbelül 150 000 kérést kell küldeni a SIM-kártyára. Az ISAAC csapata által használt kártyaolvasó másodpercenként 6,25 kérést teljesített, így a teljes támadás 8 órát vett igénybe. A SIM-kártyáról érkező válaszok elemzése sokkal kevesebb időt vesz igénybe, mint a kérések elküldése.

BGW on-the-air támadás

Marc Briceno, Ian Goldberg és David Wagner is úgy gondolja, hogy a BGW-támadás távolról is végrehajtható a SIM-kártya fizikai hozzáférése nélkül. Sajnos nem végezték el a kísérletet, mivel az sértené az Egyesült Államok törvényeit. Az ISAAC kutatói által megkeresett GSM-szakértők azonban megerősítették, hogy a támadás a gyakorlatban is megvalósítható. A GSM protokollok tulajdonságai lehetővé teszik a BGW támadás végrehajtását, ha hamis BS létrehozható. A hamis BS-nek nem kell a teljes GSM protokollt támogatnia, hanem csak funkcióinak egy részét. Az éteren keresztüli BGW támadás azon a tényen alapul, hogy az MS mobilállomásnak válaszolnia kell a GSM hálózat minden kérésére. Ha a hamis BS jele felülírja a legitim BS jelét, a támadó kéréseket küldhet a cél MS-nek, és újra létrehozhatja a Ki-t az MS-től kapott válaszokból. Érdemes megjegyezni, hogy az MS-nek a támadó rendelkezésére kell állnia a támadás teljes időtartama alatt. Nem ismert, hogy mennyi ideig tart egy BGW légi támadás. Becslések szerint nyolc-tizenhárom óra.

A támadás a metróban hajtható végre, amikor a legális BS jele nem érhető el, és a telefon be van kapcsolva. A felhasználó nem is fog tudni a folyamatban lévő támadásról, csak az riaszthatja, hogy a telefon akkumulátora a szokásosnál gyorsabban merül le. A támadás szakaszosan is végrehajtható: nyolcórás támadás helyett a támadó minden nap rövidebb időszakokra küldhet kéréseket, például amikor a felhasználó munkába áll.

Marc Briceno, Ian Goldberg és David Wagner kiemeli, hogy az ilyen típusú támadások bonyolultsága és költsége ellenére sem szabad figyelmen kívül hagyni a megvalósítás lehetőségét.

Partitioning Attack

2002 májusában az IBM Watson Research Center kutatóinak egy csoportja a zürichi Svájci Szövetségi Technológiai Intézet kutatóival közösen közzétett egy elosztott támadást a COMP128 ellen . Az egyszerű teljesítményelemzésen (SPA) alapul, és néhány perc alatt megadja a kulcsot. A támadás a SIM-kártya processzorának alacsony teljesítményét használja. Így a T0 táblázatot használó első helyettesítés 512 érték közül választ egyet, egy érték kiválasztásához 9 bit szükséges. A SIM processzor azonban csak 8 bites címet tud elérni. Ehhez a táblázatot két részre kell osztani. Az IBM Watson Research Center kutatói azt javasolták, hogy a táblázat két egyenlő részre oszlik. A kutatók a SIM-kártya energiafogyasztásának elemzésével különféle kérésekre (valamint az elektromágneses sugárzásra) meghatározták, hogy a T0 táblázat melyik részére címezték a kérést. A kérések címzésének és energiafogyasztásának elemzésével a RAND[0] első bájtjának megváltoztatásakor sikerült megtalálniuk K[0]-t. Hasonló elemzést végezve más RAND bájtok esetében a Ki kulcs teljesen visszaáll.

Ennek eredményeként a támadás 1000 véletlenszerű vagy 255 konkrét kérés elküldésével hajtható végre. Végül a támadást 8 önadaptáló kérésre csökkentették, ami lehetővé teszi, hogy 2 másodperc alatt megkapja a Ki-t. A támadás azonban csak a SIM-kártyához való fizikai hozzáféréssel lehetséges.

Ki beszerzése az AuC-től

Pontosan ugyanaz a támadás, hogy Ki-t kapjunk a SIM-ről, az AuC ellen is végrehajtható. Az AuC válaszol minden GSM-hálózati kérésre, és hármasokat bocsát ki az MS hitelesítéshez. Lényegében az eljárás hasonló a SIM elleni BGW-támadáshoz. Az egyetlen különbség az, hogy az AuC sokkal gyorsabban dolgozza fel a kéréseket, mint a SIM, mert sokszor több kérést kell feldolgoznia. Az AuC biztonsága nagy szerepet játszik, függetlenül attól, hogy lehetséges-e ez a fajta támadás.

Hamis bázisállomás

Fontos megjegyezni, hogy a GSM-ben a hitelesítés egyirányú: a telefont (MS) a bázisállomás (BS) hitelesíti, de a bázisállomást (BS) nem a telefon (MS) hitelesíti. Ez a tény lehetővé teszi a támadásokat, amikor egy harmadik fél legitim BS-nek adja ki magát egy vagy több MS számára. A GSM fejlesztésének egyik feltételezése az volt, hogy az ilyen típusú támadások nagyon drágák lesznek más típusú támadásokhoz képest. A BS ára azonban gyorsan csökkent, és manapság nem nehéz megtalálni a BS emulátorokat. Ezenkívül az aktuális hívás titkosítása nem automatikus - a kommunikációs munkamenet titkosítás nélkül jön létre, és csak ezután küldi el az MS parancsot, hogy titkosítsa-e a munkamenetet vagy sem. A titkosítás indító parancsát a rendszer titkosítatlanul küldi el, és semmilyen módon nem ellenőrzi a GSM hálózaton belül. Így egy hamis BS használatával létre lehet hozni olyan helyzetet, amikor az MS és a hamis BS kommunikációs munkamenete nincs titkosítva, és könnyen lehallgatható; és a hamis (legális MS-nek tűnő) BS és a legitim BS közötti kommunikáció titkosított. Ebben az esetben az ilyen típusú támadások felkutatása nem könnyű.

Lásd még

Linkek

Jegyzetek

  1. ↑ 3GPP. 3. generációs partnerségi projekt; Műszaki specifikáció csoport Szolgáltatások és rendszerszempontok; Biztonsággal kapcsolatos hálózati funkciók (9. kiadás)  (hun.)  (hivatkozás nem érhető el) 50. oldal (2009). Az eredetiből archiválva: 2012. április 10.
  2. ↑ H. Haverinen, J. Salowey. Extensible Authentication Protocol Method for Global System for Mobile Communications (GSM) és Subscriber Identity Modules (EAP-SIM)  (angol)  (hivatkozás nem elérhető) 65. o. (2006). Az eredetiből archiválva: 2012. április 10.
 Szimmetrikus titkosítási rendszerek
Rejtjelfolyam adatfolyam
Feistel hálózat
SP hálózat
Egyéb