Útok Fluhrera, Mantina a Šamira

Útok Fluhrera, Mantina a Šamira (anglicky Fluhrer, Mantin and Shamir attack) je v informatice název kryptografického útoku na běžně používanou proudovou šifru RC4. Útok umožňuje z velkého množství zachycené šifrované komunikace pomocí kryptoanalýzy získat symetrický klíč šifry RC4, což útočníkovi umožňuje šifrovanou komunikaci nejen odposlouchávat, ale i měnit.

Útok Fluhrera, Mantina a Šamira působí na určité metody odvozování klíče, ale nepůsobí na SSL (TLS) založené na RC4, protože SSL generuje dekódovací klíče pro RC4 pomoc hashovaní, což znamená, že rozdílné SSL session mají nesouvisející klíče.

Pozadí

Útok Fluhrera, Mantina a Šamira (FMS) publikovaný v roce 2001 v Weaknesses in the Key Scheduling Algorithm of RC4 zneužívá slabost v algoritmu ke generování klíče RC4 šifry k rekonstrukci klíče z několik zachycených zakódovaných zpráv. FMS útok získal popularitu v nástrojích jako AirSnort, weplab a aircrack-ng, které mohou být použity na WEP zakódovanou síť.

Příklad algoritmu pro generování RC4 klíče:

begin ksa(with int keylength, with byte key[keylength])
    for i from 0 to 255
        S[i] := i
    endfor
    j := 0
    for i from 0 to 255
        j := (j + S[i] + key[i mod keylength]) mod 256
        swap(S[i],S[j])
    endfor
end

Následující generátor pseudonáhodných čísel bude také použit:

begin prga(with byte S[256])
    i := 0
    j := 0
    while GeneratingOutput:
        i := (i + 1) mod 256
        j := (j + S[i]) mod 256
        swap(S[i],S[j])
        output S[(S[i] + S[j]) mod 256]
    endwhile
end

Útok

Základ FMS útoku je v použití slabých inicializačních vektorů (IV) použitých s RC4. RC4 rozkódovává byte po byte s keystreamem z prga(). RC4 používá klíč k inicializaci konečného automatu přes ksa() a poté průběžně úpravuje stav a generuje nové byte keystreamu z nového stavu. Teoreticky keystream funguje jako náhodná Vernamova šifra, protože generátor pseudonáhodných čísel kontroluje výstup každého kroku.

S určitými IV může útočník, který zná první byte keystreamu a prvních m bytů klíče odvodit (m + 1) byte klíče. To je možné z důvodu slabosti v generátoru pseudonáhodných čísel použitém k vytvoření keystreamu. Vzhledem k tomu, že první byte plaintextu pochází z WEP SNAP hlavičky, může útočník předpokládat, že lze odvodit první byte keystreamu z B ⊕ 0xAA. Poté pouze potřebuje IV ve formě (a + 3, n − 1, x) pro index klíče a se začátkem v 0, místo pro hodnotu prvku n (256 protože byte tvoří 8 bitů) a nějaké X. Pro začátek útoku útočník potřebuje jen IV ve tvaru (3, 255, x). WEP používá 24bit klíče, což dělá každou hodnotu jeden byte dlouhou.

Na začátku útočník využívá IV jako první tři prvky K[ ]. Naplní S-box S[ ] sekvencí hodnot od 0 do n jako to dělá RC4 při inicializaci S[ ] ze známého K[ ]. Poté provede první tři opakování ksa() k začátku inicializace S-boxu.

Po třetím kroku útočník možná může (ovšem ne definitivně) odvodit čtvrtý byte klíč použitím výstup keystreamu O a spočítáním (O − j − S[i]) mod n = K[i], s hodnotou i = 3 v prvním kroku.

V tuto chvíli útočník ještě nemá čtvrtý byte klíče. Tento algoritmus negeneruje další byte klíče, generuje možnou hodnotu klíče. Sbíráním několika zpráv, například WEP paketů, a opakováním těchto kroků vygeneruje útočník několik možných hodnot. Správná hodnota se objeví znatelně vícekrát než jiné. Útočník může hodnotu klíče rozhodnout rozpoznáním této hodnoty a použít jí jako další byte. V tuto chvíli může začít útok znovu pro pátý byte klíče.

Přestože útočník nemůže zaútočit na slova klíče mimo pořadí, může zprávy ukládat pro pozdější sekvenční útok na pozdější slova, jakmile zná slova předcházející. Znovu potřebuje pouze zprávy se slabým IV a může zahodit ostatní. Skrz tento proces může nashromáždit velké množství zpráv pro útok na celý klíč. Ve skutečnosti může ukládat jen krátkou část začátku těchto zpráv, právě tolik k pokračování útoku.

Reference

• Weaknesses in the Key Scheduling Algorithm of RC4 paper