Archivy MPQ

Detekce jmen

Co je detekce jmen ?

Odkaz přímo na tabulku seznamů souborů

Archivy MPQ obecně neobsahují jména souborů, které jsou v nich uloženy. Soubory jsou uloženy podle hashové hodnoty jejich jména. Výpočet hashové hodnoty je jednosměrný, není tedy možné z hashové hodnoty zpětně zjistit jméno souboru uloženého v archivu. Určitou možnost poskytuje odchytávání volání funkce SFileOpenFileEx z knihovny Storm.dll a logování nalezených jmen. Většina her obsahuje ale také soubory, které nejsou ve hře nikde použity. Jména těchto souborů není možné nikde najít (pokud byste nevykradli vývojový server Blizzardu :-). Jak tedy získat kompletní seznam souborů (filelist), který je jedinou možností, jak z archivu extrahovat všechny soubory ?

Detekce jmen je metoda, která hledá jména souborů uložených v archivu použitím hrubé síly (brute force attack), tedy generování všech možných kombinací a jejich následné zkoušení, zda soubor v archivu existuje.

Kde je potřeba detekce jmen k získání kompletního seznamu souborů ?

Počínaje hrou StarCraft, vývojáři společnosti Blizzard začali vkládat do archivů MPQ vlastní seznamy souborů. Soubor se jmenuje "(listfile)". Na první pohled je vyhráno, co může být lepší než seznam souborů přímo od jejich autorů ? Když ale zkusíte tento vnitřní soubor použít, zjistíte, že obsahuje méně než 10% všech souborů v MPQ archivu. K čemu takový seznam souborů ? Když prozkoumáte archivy MPQ z Diabla II, zjistíte, že zde jsou seznamy souborů kompletní. Také Warcraft III obsahuje kompletní seznamy souborů. Ve hrách Diablo, StarCraft, Brood War a Warcraft II BNE seznamy tedy buďto chybí, nebo nejsou kompletní. Na internetu se dají seznamy souborů lehce najít, ale kompletní také nejsou.

Úskalí detekce jmen (Špatné zprávy)

Jméno souboru v archivu MPQ obsahuje obvykle adresář, jméno souboru (maximálně 8 znaků) a příponu. Uvažujme případ, kdy známe adresář a příponu souboru, a hledáme pouze samotné jméno. To se může skládat z číslic (10 možností), velkých písmen bez diakritiky (26 možností) a znaku "podtržítko". Pokud by délka jména souboru byla 1 písmeno, dostáváme 10+26+1 = 37 možností jména souboru. Při dvouznakové délce jména souboru je to již tedy 37^2 (37*37) = 1369 kombinací. Při maximální délce jména 8 znaků dostáváme 37^8 + 37^7 + 37^6 + 37^5 + 37^4 + 37^3 + 37^2 + 37 = 3,61 * 10^12 (přes tři biliony) kombinací. je jasné, že i když bude ověření jednoho jména trvat 1 mikrosekundu, celková doba na ověření všech kombinací je přes 1000 hodin (41 dní). A to nemluvě o různých příponách a různých adresářích ve jméně archivovaného souboru. Ke kompletní detekci všech jmen není navíc možné použít slovník, protože jména souborů jsou velice často různě zkrácená. Naštěstí většina jmen souborů (u her, kde je detekce potřebná) má délku maximálně 8 znaků. U novějších her (Warcraft III) toto pravidlo neplatí, Délka jmen souborů je zde běžně přes 20-30 znaků. Takové jméno není vůbec možné metodou hrubé síly v geologicky krátkém čase najít.

Optimalizace detekce jmen (Dobré zprávy)

Pro hledání jmen souborů je možné použít několik optimalizací, které ulehčují hledání jmen souborů

1. Před hledáním jmen je dobré seřadit souboru v archivu MPQ podle jejich ordinálního čísla v archivu. Vzhledem k tomu, že archivy jsou většinou z lokálních souborů budovány najednou, soubory ze stejného adresáře (a soubory stejného typu) se většinou se nacházejí vedle sebe.
2. Některá jména souborů se liší pouze indexem (flame1.cel, flame2.cel, ...). Toho lze využít k rychlému hádání jmen souborů "zkusím štěstí".
3. Leccos také napoví velikost souboru, která se dá zjistit bez dešifrování.
4. Díky slabině v šifrování archivovaných souborů je možné snadno najít dešifrovací klíč k souborům, které jsou zkomprimované. Takových je v archivech MPQ většina (kromě nativně komprimovaných typů souborů, jako SMK, MP3). Je tedy možné soubor extrahovat a prozkoumat jeho strukturu. To nám umožní uhodnout typ souboru a tím pádem jeho příponu.
5. Podobně jako adresáře na disku, adresáře v archivech MPQ většinou sdružují soubory určitého typu, jestli např. mají známé soubory v adresáři příponu WAV, ty ostatní ji budou mít nejspíš taky.
6. Při ověřování jmen souborů je možné "předvypočítat" hashové hodnoty odpovídající adresářům. "Dovypočítání" hashových hodnot používá těchto předvypočítaných hodnot, což ušetří čas procesoru.
7. Pokud se zdá, že určitá skupina souborů začíná stejným prefixem (např. 2 znaky), je možné tento prefix zahrnout do adresáře a hledat pouze posledních 6 znaků. Tato finta zkrátí prohledání velkého množství jmen na několik minut.

Implementace detekce jmen - Name Breaker

Name Breaker je součástí programu Ladikův MPQ Editor. Umožňuje prohlížení souborů před detekcí jejich jména, ukládání rozdělané práce a podporuje automatickou detekci typů souborů, využívající slabiny v šifrování archivů MPQ. Detekce jmen běží s nižší prioritou na pozadí, takže během něj můžete pracovat nebo hrát hry a Name Breaker využije zbývající čas procesoru. Pro rychlé spuštění Name Breakeru spusťte MPQ Editor s těmito parametry:

MPQEditor.exe /namebreaker mpqfile listfile

Jak dlouho trvá detekce jmen

Doba potřebná na prohledání celého intervalu jmen souborů záleží na délce hledaného jména. Zde jsou orientační hodnoty, které jsem zjistil na počítači s procesorem Intel Pentium IV, 2,4 GHz s 533 MHz FSB a DDRAM 333 MHz (512 MB):

• Hledání 5tiznakového jména trvá 8 sekund
• Hledání 6tiznakového jména trvá 5 minut
• Hledání 7miznakového jména trvá 3 hodiny
• Hledání 8miznakového jména trvá 114 hodin (4 dní 18 hodin)

"MPQ@Home"

Cílem této stránky je vytvořit projekt detekce jmen (Obdoba známého projektu "seti@home") Zde budou k dispozici ke stažení nejnovější verze seznamů souborů pro hry používající archivy MPQ. Pokud byste se chtěli zapojit do detekce jmen, napište mi nebo si stáhněte MPQ Editor a některý ze seznamu souborů a zkuste detekovat jména souborů. Navštivte také stránky StarcraftFreaka, který se také zabývá kompletováním seznamů souborů pro MPQ archivy.

Seznamy souborů

Následující tabulka obsahuje přehled počtů neznámých souborů v MPQ archivech. Poslední verzi seznamů souborů si můžete stáhnout v sekci Download. Moje poděkování patří těm, kteří pomáhali se sestavením seznamů souborů:

• Thalick (Zvláštní poděkování za spoustu práce !!!)
• StarcraftFreak
• Uzume
• Christopher Ott
• Mystery
• Valery Anisimovsky
• DW and Ojan Pojan

Copyright (c) Ladislav Zezula 2003 - 2013