Rozděl a panuj: hrubou sílou na MS-CHAPv2 klíče

Ondrej Mikle 13. 8. 2012

Když v březnu Marsh Ray zmínil v mailinglistu starší výsledek Bruce Schneiera z 1999 ohledně derivace klíčů v MS-CHAP v1/v2 protokolu, nikdo pravděpodobně nečekal, že bude následovat bruteforce implementace útoku na MS-CHAP. Na DEFCONu 20 ovšem čekalo překvapení v podobě „louskacího“ zařízení.

Co je to MS-CHAP?

MS-CHAP je autentizační challenge-response protokol. Běžně se vyskytuje jako součást protokolů VPN PPTP, 802.1×, PPPoA, a PPPoE.

Bruce Schneier, Mudge a David Wagner již v 1999 napsali analýzu (PDF) MS-CHAPv2, kde dokládají, že MS-CHAPv2 je „proti první verzi zlepšení odstraňující hlavní zranitelnosti, ale jeho bezpečnost stále závisí na síle zvoleného hesla“. To zřejmě vedlo poskytovatele VPN k názoru, že MS-CHAPv2 s dostatečně silným heslem je dobrým způsobem autentizace, ale již si neuvědomili, že zároveň poskytuje maximálně ekvivalent 57 bitů bezpečnosti (strana 6 v Schneierově PDF).

Uvedených 57 bitů odpovídá celkem dvěma průchodům přes celý prostor možných 256 DES operací. Nejnáročnější interní operací je tedy jedno DES šifrování. Moxie Marlinspike ve spolupráci s Marshem Rayem provedli drobnou ale podstatnou optimalizaci vhledem, že výpočet lze provést i jedinou iterací přes všechny DES klíče. Navíc na stejné stránce vede odkaz na službu Cloudcracker, která poskytuje lámání (nejen) MS-CHAPv2 handshake jako komerční službu. Samotné louskání DES klíčů pomocí této služby trvá nejdéle 23 hodin, průměrně pak asi pouhých 12 hodin.

Redukce MS-CHAPv2 na složitost počítání jednoho DES klíče

MS-CHAPv2 vypadá na prvý pohled (zbytečně) složitě, což je napsáno i v původním článku z roku 1999. Prvním krokem pro pochopení útoku je proto vyházet všechny nepodstatné kroky a ponechat pouze části, které jsou pro provedení útoku podstatné. Podrobně je MS-CHAPv2 popsán v RFC 2759, ale jako všechna RFC se i toto nečte moc příjemně (dost „nelineárního“ skákání po referencích). Mnohem lépe je princip fungování vidět na následujícím obrázku z Moxieho zápisku:

Obrázek 1: Kroky MS-CHAPv2 protokolu: známé hodnoty jsou zeleně, tajné/hledané červeně.

Všechny hodnoty v MS-CHAPv2 protokolu označené zeleně útočník buď zná přímo – odposlechem sítě, protože jsou v plaintextu, nebo si je jednoduše může odvodit. První důležité pozorování: útočník nemusí znát původní heslo a ani nemusí zpětně rozlamovat MD4 hash – pro provedení úspěšného útoku nemusíte odhalit heslo, ale stačí vám pouze tři DES klíče. Hodnotu ChallengeHash, která se šifruje známe, stejně jako známe to, co má byt výsledkem šifrování – ChallengeResponse. Obě hodnoty putují po drátě v nešifrované podobě a útočník je může jednoduše odposlechnout.

Získání nejslabšího DES klíče – 216 pokusů

Druhé důležité pozorování: Spočítaný NTHash se „rozsekne“ po 7 bytech na tři DES klíče. Jenže NTHash má jenom 16 bytů a tři DES klíče potřebují 21 bytů! Zbývající byty jsou z definice protokolu vyplněny nulami. Jinými slovy – první DES klíč je prvních 7 bytů NTHash-e, druhý klíč je dalších 7 bytů NTHash-e, a pak nám zůstanou jenom 2 byty, které se doplní 5 nulami. Z toho vyplývá, že celkový prostor všech možností pro poslední klíč je „velký“ jenom 216.

Obrázek 2: Rozdělení NTHash na tři DES klíče

Získání ostatních dvou DES klíčů

Tato část vyžaduje skutečnou hrubou výpočetní sílu. Triviální algoritmus na lousknutí těchto dvou klíčů hrubou sílou by vypadal jako dvě iterace přes celý prostor DES klíčů:

key1 = NULL;
key2 = NULL;

// z definice protokolu:
plaintext = ChallengeHash;
ciphertext1 = ChallengeResponse[0:8];
ciphertext2 = ChallengeResponse[8:16];

for (i=0; i < 2^56; i++) {
    // i se použije jako klíč
    if (DES(i, plaintext) == ciphertext1) {
        key1 = i;
        break;
    }
}

for (i=0; i < 2^56; i++) {
    if (DES(i, plaintext) == ciphertext2) {
        key2 = i;
        break;
    }
}

Vidíme ale, že DES-em se šifruje pořád stejný plaintext, takže si nadbytečné šifrování můžeme odpustit a útok zjednodušit na jednoduchou iteraci přes prostor všech možných DES klíčů:

key1 = NULL;
key2 = NULL;

// z definice protokolu:
plaintext = ChallengeHash;
ciphertext1 = ChallengeResponse[0:8];
ciphertext2 = ChallengeResponse[8:16];

for (i=0; i < 2^56; i++) {
    // i se použije jako klíč
    result = DES(i, plaintext);

    if (result == ciphertext1) {
        key1 = i;
    }
    if (result == ciphertext2) {
        key2 = i;
    }
}

Pokud chceme útok ještě zrychlit, je možné pro výpočet 256 DES šifrování použít již zmíněné FPGA, EFF DES cracker, nebo díky dobré paralelizovatelnosti vícero běžných počítačů s GPU.

A co z toho vyplývá?

Zde bychom si vypůjčili seznam doporučení od Moxieho Marlinspikeho:

  • Všichni uživatelé a poskytovatelé PPTP VPN by měli okamžitě přejít na jiný VPN protokol. Veškerá PPTP VPN komunikace by měla být považována za nešifrovanou.
  • Firmy, které pro autentizaci WPA2 Radius používají MS-CHAPv2, by měly okamžitě přejít na něco jiného

Co se týče dostupných řešení, tak vynechte IPSEC-PSK, který je z hlediska bezpečnosti ještě horší než PPTP, a přejděte rovnou na řešení, které zahrnuje (klientské) certifikáty (například OpenVPN nebo IPSEC v módu používajícím certifikáty).

Našli jste v článku chybu?
DigiZone.cz: Jsou obchody připraveny na DVB-T2/HEVC?

Jsou obchody připraveny na DVB-T2/HEVC?

120na80.cz: Jak se zbavit nadměrného pocení?

Jak se zbavit nadměrného pocení?

DigiZone.cz: O2 Sport mění název, přejde i na Full HD

O2 Sport mění název, přejde i na Full HD

Měšec.cz: Udali ho na nelegální software a přišla Policie

Udali ho na nelegální software a přišla Policie

DigiZone.cz: Samsung uvolnil nástroj pro Tizen

Samsung uvolnil nástroj pro Tizen

DigiZone.cz: Sat novinky: Skylink skončil s kanály ČT

Sat novinky: Skylink skončil s kanály ČT

DigiZone.cz: Sázka na e-sporty stanici Prima vychází

Sázka na e-sporty stanici Prima vychází

Měšec.cz: Nový sazebník mBank radost nedělá

Nový sazebník mBank radost nedělá

Lupa.cz: eIDAS: Nepřehnali jsme to s výjimkami?

eIDAS: Nepřehnali jsme to s výjimkami?

Měšec.cz: Investice do drahých kovů - znáte základní chyby?

Investice do drahých kovů - znáte základní chyby?

Vitalia.cz: Zmrzlinu? Ani snad ne

Zmrzlinu? Ani snad ne

Vitalia.cz: Bio vejce nepoznají ani veterináři

Bio vejce nepoznají ani veterináři

Podnikatel.cz: Tahle praktika stála šmejdy přes milion

Tahle praktika stála šmejdy přes milion

Vitalia.cz: Pepsi Cola mění sirup za cukr

Pepsi Cola mění sirup za cukr

Lupa.cz: eIDAS: elektronické dokumenty platí jako papír

eIDAS: elektronické dokumenty platí jako papír

120na80.cz: SOS aneb spálená pokožka

SOS aneb spálená pokožka

Lupa.cz: Největší pitominy s logem “nyní smart a připojené”

Největší pitominy s logem “nyní smart a připojené”

Podnikatel.cz: Prodej na Alibabě? Malí hráči utřou nos

Prodej na Alibabě? Malí hráči utřou nos

Root.cz: Bitcoin začal vyplácet jen půlku odměn

Bitcoin začal vyplácet jen půlku odměn

Vitalia.cz: Cvičení tabata: na hubnutí i posilování?

Cvičení tabata: na hubnutí i posilování?