Титла: Някой случайно да разбира от DEFLATE компресията? Публикувано от: gat3way в Jan 10, 2012, 01:31 Въпросът е малко странен и не знам защо го задавам тук, но все пак - има ли някой, който да е запознат ама добре запознат с DEFLATE алгоритъма за компресия (използван от gzip и zip)?!? Имам предвид някой, който е имал достатъчно много вземане-даване с това, примерно писал си е собствена inflate функция. Иначе що е то Хъфманово дърво и що е то LZ77 и аз знам и такива отговори за жалост няма да ми помогнат особено.
Това което на мен ми трябва е някакъв относително бърз начин да знам още от първите няколко байта от блока дали това е валиден блок или не. Първите няколко байта съдържат хедъра, както и описание на distance/code length големините. Причината да питам за това е идиотска. Тръгнах да троша ZIP файлове върху видеокарти. ZIP encryption-а условно казано има два варианта - един стар encryption алгоритъм, който е слаб, както и новия strong encryption алгоритъм, който ползва PBKDF2 подсилване на ключа и AES криптиране на данните. Колкото и да е странно, strong encryption-а не е проблема - проблемът е стария им стандарт. Ще се опитам да обясня - при стария стандарт има прост начин по който паролата се превръща в ключ. С този ключ се декриптират 12 байта от zip архива и се получава една стойност, наречена verifier. Въпросната стойност е само един байт и се сравнява с някаква стойност от ZIP хедъра - ако не съвпаднат, имаме грешна парола. Както сте се досетили, всяка грешна парола-кандидат има шанс 1/256 да мине тази проверка - откъдето следва декриптиране и декомпресиране и ако няма грешка при декомпресирането и сравняването на крайната CRC стойност, значи имаме успешно позната парола. Последните два процеса са безумна цел за реализация върху видеокарти - просто няма как да се извърши по-бързо, отколкото върху процесора - има прекалено големи изисквания към паметта, а видеопроцесорите за разлика от CPU-тата нямат такива прекрасни L1/L2 кешове от под няколко мегабайта. Не мога да декомпресирам целия файл и не мога да му смятам CRC сума върху видеокартата, поне не мога да го правя бързо. Обаче съм сигурен че има начин ако декриптирам само първите няколко байта от компресирания stream, да разбера дали това е валиден DEFLATE блок или не. Засега имам една доста генерична проверка върху GPU-тата във първия байт от декриптирания stream, която проверява типа на кодирането и ако не ползваме динамични Huffman codes, връщаме грешка - това е ефективно защото на практика всеки ZIP софтуер (WinZIP, 7z, WinRAR) ползват въпросния метод. Това вдига ситото от 1/256 на 1/1024. Но не е достатъчно. Върху видеокарта среден клас правя около 2 милиона опита в секунда, за момента процесорът ми се справя по-добре, което е странно. Също така има разни комерсиални решения със затворен код, които се хвалят с над 200-300 милиона опита/секунда върху относително калпава NVidia карта и стигам до извода че те парсват и обработват DEFLATE данните в GPU кода по някакъв начин и отсяват по-добре нещата. Та мисълта ми е - има ли някакъв начин сравнително лесно и бързо ако имам само първите няколко байта от DEFLATE stream-а да кажа: това е валиден такъв или невалиден. Истински вярвам, че има и ако си загубя няколко седмици в четене вероятно ще го открия. Ако все пак някой има идея, ще се радвам да помогне :) Титла: Re: Някой случайно да разбира от DEFLATE компресията? Публикувано от: AMD в Jan 10, 2012, 09:07 Не съм наясно с това, но намерих това -> http://www.compression.ru/download/articles/lz/mihalchik_deflate_decoding.html
Може да има отговора който търсиш но не знам можеш ли да си го преведеш. Мога да помогна с превода евентуално. Титла: Re: Някой случайно да разбира от DEFLATE компресията? Публикувано от: gat3way в Jan 10, 2012, 12:15 Проблем с четенето на руски нямам, но за съжаление това четиво няма да свърши работа - защото се отнася за статични кодове където таблицата изглежда доста различно.
Обаче намерих едно обяснение с малко примерен сорс код, което май ще свърши работа. Изглежда малко на магия, но ще помогне да намаля шанса за false positives поне няколко пъти. Титла: Re: Някой случайно да разбира от DEFLATE компресията? Публикувано от: AMD в Jan 10, 2012, 13:01 Проблем с четенето на руски нямам, но за съжаление това четиво няма да свърши работа - защото се отнася за статични кодове където таблицата изглежда доста различно. Както казах не съм навътре в това, и дадох документация която намерих. С примери в нея. Титла: Re: Някой случайно да разбира от DEFLATE компресията? Публикувано от: gat3way в Jan 11, 2012, 00:42 Май в крайна сметка наистина съм търсил в грешна насока.
Първо, оказва се че има вероятност да се ползват статични кодове все пак, което чупи тези презюмпции. От друга страна, успях да измисля няколко проверки и в двата случая - при динамичните хъфманови кодове, при дължините има очевидни грешки които могат да се хванат, при статичните е още по-лесно. Грубо около 1/65535 вероятност грешна парола да match-не, което е приемливо... Обаче ме осени една друга гениална идея - тъй като в един ZIP архив може да имаме повече от един файл и всеки файл идва с неговата 12-байтова IV стойност, която инициализира алгоритъма и съответно и неговата си 1-байтова стойност за проверка, Можем да се възползваме от това, ако парснем ZIP файла и вземем IV стойностите за няколко компресирани/криптирани файла. Така, примерно за 3 криптирани файла в архива, имаме 1/(256*256*256) == близо 1/16 милиона вероятност грешна парола да мине проверката. Което е забавно. Сега разбирам как се достигат високи скорости върху видеокарти за стария ZIP алгоритъм. Титла: Re: Някой случайно да разбира от DEFLATE компресията? Публикувано от: gat3way в Jan 14, 2012, 00:58 ОК, крайният резултат (ако на някой му е интересно):
http://www.gat3way.eu/index.php?mact=News,cntnt01,detail,0&cntnt01articleid=169&cntnt01returnid=15 Доста неща не съм споменал за жалост, нямах време... |