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: Jetelín končí. Prima ho vyřadila

Jetelín končí. Prima ho vyřadila

Měšec.cz: Investiční pasti. Děláte to, co ostatní, ale proděláváte

Investiční pasti. Děláte to, co ostatní, ale proděláváte

Podnikatel.cz: Týká se vás EET? Chtějte od berňáku posudek

Týká se vás EET? Chtějte od berňáku posudek

Měšec.cz: Do ostravské MHD bez jízdenky. Stačí karta

Do ostravské MHD bez jízdenky. Stačí karta

Podnikatel.cz: Češi to dělat nechtějí, nahradí je Ukrajinci

Češi to dělat nechtějí, nahradí je Ukrajinci

Měšec.cz: Ceny PHM v Evropě. Finty na úspory

Ceny PHM v Evropě. Finty na úspory

Měšec.cz: Se stavebkem k soudu už (většinou) nemusíte

Se stavebkem k soudu už (většinou) nemusíte

DigiZone.cz: Další rána pro piráty: 6 měsíců

Další rána pro piráty: 6 měsíců

DigiZone.cz: Test TV Samsung UE49K6372SU

Test TV Samsung UE49K6372SU

Podnikatel.cz: Pozor na vykuky, imitují služby České pošty

Pozor na vykuky, imitují služby České pošty

Lupa.cz: Olympiáda zakázala GIFy. Moc to nepomáhá

Olympiáda zakázala GIFy. Moc to nepomáhá

Měšec.cz: Platíme NFC mobilem. Konečně to funguje!

Platíme NFC mobilem. Konečně to funguje!

Lupa.cz: Kdo vykrádá LinkedIn? Zjistit to má soud

Kdo vykrádá LinkedIn? Zjistit to má soud

DigiZone.cz: Hodlá Markíza skončit v DVB-T?

Hodlá Markíza skončit v DVB-T?

Podnikatel.cz: Oznamte skutečné sídlo firmy, jinak zaplatíte

Oznamte skutečné sídlo firmy, jinak zaplatíte

Měšec.cz: Test: Výběry z bankomatů v cizině a kurzy

Test: Výběry z bankomatů v cizině a kurzy

Podnikatel.cz: Novela zákoníku práce. Řeší homeworking

Novela zákoníku práce. Řeší homeworking

Podnikatel.cz: Kauza z Vinohrad pokračuje. Policie se omlouvá

Kauza z Vinohrad pokračuje. Policie se omlouvá

Vitalia.cz: Galerie: Strouhanka ze starých rohlíků? Kdepak

Galerie: Strouhanka ze starých rohlíků? Kdepak

Podnikatel.cz: OSA zdražuje poplatky. Zaplatíte o polovinu víc

OSA zdražuje poplatky. Zaplatíte o polovinu víc