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):

"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ů:

Diablo I Beta
  Setup.exe Kompletní 06.11.04 - Christopher, Mystery
  Diabdat.mpq Kompletní 09.05.05 - Ojan, Ladik, Christopher, Mystery
Diablo I
  Autorun.exe Kompletní 09.05.03 - Ladik, StarcraftFreak
  Battle.snp Kompletní 04.05.03 - Ladik, StarcraftFreak
  Diabdat.mpq Kompletní 13.06.03 - Ladik, Thalick, StarcraftFreak
  Patch 1.09b.exe Kompletní 04.05.03 - Ladik, StarcraftFreak
  Patch_rt.mpq Kompletní 04.05.03 - Ladik, StarcraftFreak
  Spawn.mpq Kompletní 13.06.03 - Ladik, Thalick, StarcraftFreak
  single_*.sv, multi_*.sv Kompletní 17.05.03 - Thalick, Ladik
  d1221a.mpq Kompletní 09.06.03 - Thalick
Hellfire
  Hellfire.mpq Kompletní 04.07.03 - Ladik, StarcraftFreak
  Hfmonk.mpq Kompletní 28.05.03 - Ladik, StarcraftFreak
  Hfmusic.mpq Kompletní 04.05.03 - Ladik, StarcraftFreak
  Hfvoice.mpq Kompletní 04.05.03 - Ladik, StarcraftFreak
Lords of Magic
  Demoverze Kompletní 22.08.03 - Thalick, Ladik
  gs.mpq Kompletní 12.09.03 - Ladik
  imp.mpq Kompletní 10.09.03 - Ladik
  pic.mpq 1 Neznámý 16.09.03 - Ladik
  sndfx.mpq Kompletní 27.03.05 - DW, Ladik
  special.mpq Kompletní 16.09.03 - Ladik
StarCraft
  Battle.snp Kompletní 04.05.03 - StarcraftFreak
  Install.exe (v 1.0.0.5) 2 neznámé 27.03.05 - DW, Ojan, Ladik, Thalick, StarcraftFreak
  SC-1152.exe Kompletní 25.04.08 - Ojan, Ladik, StarcraftFreak
  Patch_rt.mpq Kompletní 04.05.03 - StarcraftFreak
  Standard.snp Kompletní 04.05.03 - StarcraftFreak
  StarDat.mpq 4 neznámé 11.07.03 - Thalick, Ladik, StarcraftFreak
StarCraft
Brood War
  Battle.snp Kompletní 04.05.03 - StarcraftFreak
  BrooDat.mpq Kompletní 09.05.03 - Ladik, StarcraftFreak
  Install.exe (1.0.0.5) 2 neznámých 27.03.05 - DW, Ojan, Ladik, StarcraftFreak
  BW-1152.exe Kompletní 16.08.08 - Ojan, Ladik, StarcraftFreak
  Patch_rt.mpq Kompletní 04.05.03 - StarcraftFreak
  Standard.snp Kompletní 04.05.03 - StarcraftFreak
Warcraft II
Battle.net Edition
  Battle.snp Kompletní 04.05.03 - StarcraftFreak
  Install.exe (UK) 2 neznámé 20.07.03 - Thalick, Ladik, StarcraftFreak
  War2Patch_202.exe Kompletní 04.05.03 - StarcraftFreak
  Patch_W2.mpq Kompletní 04.05.03 - StarcraftFreak
  War2Dat.mpq (UK) 1 neznámý 20.08.03 - Thalick, Ladik, StarcraftFreak
Diablo II
  D2data.mpq Kompletní 04.05.03 - StarcraftFreak
  D2char.mpq Kompletní 04.05.03 - StarcraftFreak
  D2music.mpq Kompletní 04.05.03 - StarcraftFreak
  D2sfx.mpq Kompletní 09.06.03 - Thalick, StarcraftFreak
  D2speech.mpq Kompletní 04.05.03 - StarcraftFreak
  D2video.mpq Kompletní 09.05.03 - Ladik, StarcraftFreak
  D2Patch_111b.exe Kompletní 16.08.08 - Ojan
  Patch_D2.mpq Kompletní 09.05.03 - Ladik, StarcraftFreak
  Setup.mpq Kompletní 03.07.03 - Thalick, Ladik, StarcraftFreak
Diablo II
Lord of Destruction
  D2xmusic.mpq Kompletní 04.05.03 - StarcraftFreak
  D2xtalk.mpq Kompletní 09.05.03 - Ladik, StarcraftFreak
  D2xvideo.mpq Kompletní 09.05.03 - Ladik, StarcraftFreak
  D2Patch_111b.exe Kompletní 16.08.08 - Ojan
  Patch_D2.mpq (1.10) Kompletní 16.01.04 - Uzume, Ladik, StarcraftFreak
  Setup.mpq Kompletní 03.07.03 - Ladik, Thalick, StarcraftFreak
Warcraft III
Reign of Chaos
  Patch 1.13.exe Kompletní 27.12.03 - Ladik, StarcraftFreak
  Patch_War3.mpq (1.13) Kompletní 27.12.03 - Ladik
  Patch_War3_Low.mpq Kompletní 03.08.03 - Ladik
  Patch_War3_Med.mpq Kompletní 03.08.03 - Ladik
  Setup.mpq Kompletní 27.03.05 - Ojan, Ladik
  War3.mpq Kompletní (Vč. vnořených MPQ) 09.05.03 - Ladik, StarcraftFreak
  War3patch.mpq Kompletní 09.05.03 - Ladik, StarcraftFreak
Warcraft III
The Frozen Throne
  Patch 1.13.exe Kompletní 27.12.03 - Ladik
  Setup.mpq Kompletní 03.07.03 - Ladik
  War3.mpq Kompletní (Vč. vnořených MPQ) 27.03.05 - Ojan, Ladik
  War3Patch.mpq (1.23) Kompletní 22.12.13 - Ladik
  War3x.mpq Kompletní (Vč. vnořených MPQ) 03.07.03 - Ladik
  War3xLocal.mpq Kompletní 03.07.03 - Ladik
  War3x_low.mpq Kompletní 16.07.03 - Ladik
  War3x_med.mpq Kompletní 16.07.03 - Ladik

World of Warcraft

Interní seznamy jsou kompletní

Starcraft II

Interní seznamy jsou kompletní