До обидного тихо и незаметно произошло одно очень интересное и важное событие. Президент России Владимир Путин встретился и беседовал с одним из руководителей государственной службы, имя которого нечасто попадает в прессу. Нет, этот человек - не тайный агент, хотя по роду деятельности он имеет доступ к секретной информации, и даже может считаться своеобразным «бойцом невидимого фронта». В общем, Путин общался с главой Федерального архивного агентства Андреем Артизовым.

Разговор главы государства с главой агентства носил деловой характер, возможные последствия которого способны кое-где вызвать эффект разорвавшейся бомбы, а кое у кого и детонацию персонального сопла.

Президент сделал негромкое заявление, что им принято решение о рассекречивании множества архивных документов, причём, указ будет подписан в тот же день. Кроме того, Путин сообщил о передаче Росархива в прямое подчинение президенту России, поскольку многие материалы ведомства «представляют особую ценность и имеют мировое значение».

Глава агентства в свою очередь информировал президента, что архивный фонд России хранит 500 миллионов дел, и что «никогда за последние десятилетия плановая, организованная работа по рассекречиванию не проводилась так, как она проводится сейчас».

Ключевой момент – сразу после рассекречивания архивные документы будут доступны на официальном сайте Росархива, для чего уже создана специальная база данных.

Среди уже рассекреченных архивов – материалы, на которые давно облизывались отечественные и зарубежные историки: 1400 уникальных директив Сталина, распоряжений Ставки, фронтовых приказов, оперативных карт, постановлений и фотографий того времени, еще недавно хранившихся в архивах под грифом «совершенно секретно».

Можно только искренне порадоваться за историков, пожелать им свежих и интересных трудов, в основе которых будут лежать вышеупомянутые документы, но только рассекречивание коснётся не единой военно-исторической тематики.

Источник, близкий к Росархиву, сообщает любопытные подробности: «Речь, насколько я знаю по информации из архивного ведомства, идет о периоде с 1930 по 1989 года. Там есть дела, простите, стукачей – как и невинно репрессированных, с очень интересными фамилиями. Там будут данные о космических и военных разработках, которые уже можно сообщить. Кроме того, рассекречиваются данные о ходе сражений, приказах и полученной развединформации во время Великой Отечественной войны, так же, как и о межгосударственных отношениях в период войны холодной».

И очень веско добавляет: «Некоторые документы общество удивят. Собственную историю нужно знать, какой бы она ни была».

Архивы имеют долгую память и несут в себе потенциальный заряд не хуже водородной бомбы. Не случайно в нашей стране до сих пор продолжают оставаться засекреченными «дело маршалов» и «дело врачей», длительное время создающих почву для всевозможных спекуляций. Не так давно в Великобритании специальная комиссия разбиралась с архивными документами, чей срок секретности подходил к концу, но на данные о предвоенных контактах британской разведки с гитлеровской СД было решено продлить режим секретности ещё на 50 лет.

Оговорка про «некоторые документы общество удивят» сделана не случайно. В конце 1980-х, как в России, так и в республиках бывшего СССР, на волне «демократизации» к власти пришли самые разные люди.

Многие проявляют поразительную политическую живучесть, несмотря на явное отсутствие управленческих талантов и склонность учить народ демократии со своей кочки зрения.

В ближайшем зарубежье бывшие лидеры «народных фронтов», сменившие мировоззрение с антисоветского на антироссийское, крепко прикипели к власти и проводят недружественную политику в отношении России со своей территории – от организации съездов всяческих лишенцев из «Открытой России» до обучения профашистских боевиков и оказания военной помощи бандеровцам.

Европейскому сообществу, как и гражданам этих лимитрофов, будет интересно узнать из рассекреченных документов Росархива – кто из записных «евродемократов» состоял в осведомителях КГБ. Слухами о том, что в пору туманной юности в КГБ «стучали» бывший лидер НФ Литвы Ландсбергис и нынешняя мадам президент Даля Грибаускайте - земля полнится. Теперь об этой стороне их биографии, полагаю, можно будет узнать из первоисточника.

Судачить о том, что «это было давно, и неправда», «быльём поросло», можно сколько угодно, но не стоит недооценивать убойной силы подобных разоблачений.

Можно вспомнить, как в прошлом году эффектно рванул в польской прессе пакет документов, раскопанный Институтом национальной памяти, о сотрудничестве Леха Валенсы (под оперативным погонялом «Болек») в разгар его деятельности на Гданьской судоверфи. Информационный взрыв не оставил камня на камне от имиджа иконы, «поляка № 1», лидера «Солидарности», лауреата Нобелевской премии мира и первого президента антисоветской Польши. Отныне и навеки Валенса – просто усатый жирный старик, руина ушедшей эпохи, чей позор можно увидеть собственными глазами в виде выставленных всё в том же Институте национальной памяти 17 расписок в получении денег за переданную спецслужбам стук-стук-информацию.

Остаётся только сожалеть, что архивная «бомба» не рванула под днищем агента «Болека» в 1980-х, когда он и его «Солидарность», спевшиеся с западными спецслужбами, расшатывали социалистическую Польшу.

Масса интересных неожиданностей может подстерегать и записных отечественных либеральчиков. Их извилистый жизненный путь во многом схож с путём Валенсы к вершинам власти. К глубокому сожалению, в КГБ не спешили с разоблачением перековавшихся информаторов по многим причинам, среди которых этические были не на последнем месте. Ведь если раскроешь агента, особенно добровольного, то кто пойдёт на сотрудничество? На агентуре, пойманной при совершении неблаговидных поступков и на этой почве завербованных, далеко не уедешь.

В СМИ прорывается неофициальная информация о том, что «видные деятели либерально-демократического движения России» шли на сотрудничество с советскими спецслужбами добровольно, из шкурных побуждений: интересные командировки, продвижение по карьерной лестнице, престижная работа и т.п.

Можно только представить, какими стукаческими гадюшниками были различные творческие объединения писателей, театральных деятелей и кинематографистов.

У многих критиков СССР и советского строя родители были не просто видными партийными или хозяйственными деятелями, но и служили в органах НКВД-МГБ-КГБ, и даже принимали личное участие в репрессиях.

Конечно, дети за отцов не отвечают, но на душе становится гадко, когда разоблачать и срывать покровы принимаются перекрасившиеся отпрыски, не желающие вспоминать прошлое своих родителей, но когда-то без всяких угрызений совести воспользовавшиеся их высоким положением, как трамплином в персональное светлое будущее.

Рассекреченные архивы способны повлиять на расстановку сил и в обандеренной Украине. Можно вспомнить, как ряд документов, опубликованных в соцсетях Мирославой Бердник ещё до майданного путча, касавшихся сотрудничества главарей ОУН с МГБ и МВД, вызывали приступы корчи и фонтаны горловой диареи у поклонников бандеровских умертвий. Свидомиты сыпали проклятия, обзывали фотокопии документов «эфэсбэшными фальшивками», но аргументированно возразить ничего не могли.

Почему это важно? Украинский радикальный национализм – зло без всяких оговорок. Но его исповедуют самые разные люди. Среди современных оуновцев есть свои идеалисты, которые желают очистить украинский национализм от наиболее одиозных фигур Бандеры и Шухевича, поскольку они давно и безвозвратно скомпрометировали себя как гитлеровские марионетки и каратели. Как бы там ни было, но послевоенная советская разведка неплохо разобралась в чувствах немецких националистов, чётко отделявших себя от гитлеровцев и сторонников генерала Гелена, лёгших под американцев. Немецкие националисты, считавшие своим кумиром Бисмарка, пережив ужасы войны и видя то, как американцы толкают ФРГ в новую войну с СССР, предпочли работать на советскую и восточногерманскую разведки. Этот момент непременно стоит учесть.

С другой стороны, на Украине полно ярых и не страдающих избытком брезгливости необандеровцев, которых не страшат никакие документальные свидетельства сотрудничества их кумиров с гитлеровскими спецслужбами. А если будут опубликованы рассекреченные документы, говорящие, что их идолы, вроде Василя Кука, сливали МГБ информацию на «побратимов», сидящих по схронам?

Если внезапно окажется, что всякие там «правозатычники» и «незалежники» позднесоветского периода постукивали КГБ для смягчения режима отсидки, за дополнительную посылку сала из дома или пачку махорки из лагерного ларька? Выдержит ли подобное испытание на прочность убеждений бандеровская «спильнота», видящая повсюду длинную руку Москвы, ФСБ и лично Путина?

Информация подобного рода может вызвать мощнейший выброс термоядерной плазмы из свидомых дуп, владельцы которых кичатся «национальной чистотой» и «свидомостью». Кого-то разоблачения кумиров могут заставить отшатнуться и одуматься.

Было бы небезынтересно узнать и про двойную жизнь главарей самозванного «меджлиса», как и прочих мерзопакостных деятелей, изнемогающих под самочинно взятым на себя бременем «совести нации».

Так под чьим персональным задом рванёт первая архивная «бомба»? Кто пойдёт «паровозом», разматывающим длинную цепь разоблачений?

Что за штука такая - ZIP-бомба?

Как выяснилось, сжатие ZIP великолепно справляется с повторяющимися данными, так что если у вас имеется гигантский текстовый файл, заполненный повторяющимися данными вроде всех нулей, он очень хорошо сожмётся. В смысле, ОЧЕНЬ хорошо.

Как показал 42.zip , можно сжать 4,5 петабайта (4 500 000 гигабайт) в 42 килобайта. Когда вы попытаетесь посмотреть содержимое архива (извлечь или разархивировать его), то у вас, вероятно, израсходуется всё дисковое пространство или оперативная память.

Как сделать ZIP-бомбу?

Первым делом создадим 10-гигибайтный файл ZIP, заполненный нулями. Можно сделать много вложенных сжатий, но начнём с простого.

В линуксе можно сделать очень просто, командой dd:

Dd if=/dev/zero bs=1M count=10240 >> 10

Получим файлик с именем "10" и 10-ть гигов...:)

Zip -r 10.zip 10

Получим файлик с именем "10.zip", у меня он весит всего пять мегабайт! :)

Как сбросить ZIP-бомбу на жертву?

Ну можно просто дать ему такой файлик на распаковку! :)

Но давайте рассмотрим более прикольный способ:

К сожалению, веб-браузеры не понимают ZIP, но зато они понимают GZIP.

Так что первым делом создадим 10-гигибайтный файл GZIP, заполненный нулями.

Dd if=/dev/zero bs=1M count=10240 | gzip > 10G.gzip

Создание бомбы и проверка её размера

Как видите, её размер 10 МБ. Можно было сжать и получше, но пока хватит.

Теперь установим PHP-скрипт, который доставит её клиенту.

Всё браузер прочитает такой файлик и сдохнет! :)

Можно использовать для борьбы с хакерами и сканерами на уязвимости, пример:

Данный скрипт проверяет заголовки популярных сканеров на уязвимости и выдаёт этот файлик на чтение вместо самого сайта! :)

Итак… Что будет, если запустить этот скрипт?

IE 11 - Память расходуется, IE падает.
Chrome - Память расходуется, демонстрируется ошибка.
Edge - Память расходуется, утекает, грузится вечно.
Nikto - Как будто нормально сканирует, но не выдаёт результат.
SQLmap - Большой расход памяти, затем падает.
Safari - Большой расход памяти, затем падает и перезагружается, затем опять большой расход памяти и так далее...
Chrome (Android) - Память расходуется, демонстрируется ошибка.

*Есть две версии 42.zip: старая 42 374 байт, и более новая на 42 838 байт. Разница в том, что новая требует пароль перед распаковкой. Мы сравниваем только со старой версией. Вот копия файла, если он вам нужен: 42.zip .

Zip-бомбы должны преодолеть тот факт, что наиболее часто поддерживаемый парсерами алгоритм сжатия DEFLATE не может превысить степень сжатия 1032 к 1. По этой причине zip-бомбы обычно полагаются на рекурсивную декомпрессию, вкладывая zip-файлы в zip-файлы, чтобы получить дополнительный коэффициент 1032 с каждым слоем. Но трюк работает только в реализациях, которые распаковывают рекурсивно, а большинство этого не делают. Самая известная бомба 42.zip расширяется до грозных 4,5 ПБ, если все шесть слоёв рекурсивно распаковать, но на верхнем слое у неё пустяковые 0,6 МБ. Zip-квайны, как у Кокса и Эллингсена , выдают копию самих себя и, таким образом, расширяются бесконечно при рекурсивной распаковке. Но они тоже совершенно безопасны при распаковке один раз.

В этой статье показано, как создать нерекурсивную zip-бомбу, степень сжатия которой превышает предел DEFLATE в 1032. Она работает путём перекрытия файлов внутри zip-контейнера, чтобы ссылаться на «ядро» сильно сжатых данных в нескольких файлах, не делая несколько копий. Выходной размер zip-бомбы растёт квадратично от входного размера; т. е. степень сжатия улучшается при увеличении размера бомбы. Конструкция зависит от особенностей zip и DEFLATE: она не переносится напрямую на другие форматы файлов или алгоритмы сжатия. Бомба совместима с большинством zip-парсеров, кроме «потоковых», которые анализируют файлы в один проход, не проверяя центральный каталог zip-файла. Мы стараемся сбалансировать две противоречивые цели:

• Увеличить степень сжатия. Мы определяем степень сжатия как сумму размеров всех файлов в архиве, делённому на размер самого файла zip. Здесь не учитываются имена файлов или другие метаданные файловой системы, а только содержимое.
• Сохранить совместимость. Zip - это сложный формат, и парсеры отличаются, особенно в пограничных ситуациях и дополнительными функциями. Не использовать приёмы, которые работают только с определёнными парсерами. Мы отметим некоторые способы повышения эффективности zip-бомбы при определённой потере совместимости.

Структура zip-файла

Zip-файл состоит из центрального каталога ссылок на файлы .

Центральный каталог находится в конце файла zip. Это список заголовков центрального каталога . Каждый заголовок центрального каталога содержит метаданные одного файла, такие как имя файла и контрольная сумма CRC-32, а также обратный указатель на заголовок локального файла. У заголовка центрального каталога длина 46 байт плюс длина имени файла.

Файл состоит из заголовка локального файла, за которым следуют сжатые данные файла. Длина заголовка локального файла - 30 байт плюс длина имени файла. Он содержит избыточную копию метаданных из заголовка центрального каталога, а также размеров сжатого и несжатого файлов данных за ним. Zip - это формат контейнера, а не алгоритм сжатия. Данные каждого файла сжимаются с помощью алгоритма, указанного в метаданных, - обычно DEFLATE .

Это описание формата zip опускает много деталей, которые не нужны для понимания zip-бомбы. Для получения полной информации см. раздел 4.3 APPNOTE.TXT или «Структуру файла PKZip» Флориана Бухгольца, или см. .

Значительная избыточность и много двусмысленностей в формате zip открывают возможности для озорства разных видов. Zip-бомба - это лишь верхушка айсберга. Ссылки для дальнейшего чтения:

$ python3 -m zipfile -e overlap.zip . Traceback (most recent call last): ... __main__.BadZipFile: File name in directory "B" and header b"A" differ.
Далее мы рассмотрим, как изменить конструкцию для согласованности имён файлов, сохранив при этом большинство преимуществ перекрывающихся файлов.

Второе открытие: цитирование заголовков локальных файлов

Нам нужно разделить заголовки локальных файлов для каждого файла, при этом повторно использовать одно ядро. Простое объединение всех заголовков не работает, потому что парсер zip найдёт тот заголовок локального файла, где он ожидает начало потока DEFLATE. Но идея будет работать, с небольшими изменениями. Будем использовать функцию DEFLATE несжатых блоков, чтобы «цитировать» заголовки локальных файлов, чтобы они казались частью того же потока DEFLATE, который заканчивается в ядре. Каждый заголовок локального файла (кроме первого) будет интерпретироваться двумя способами: как код (часть структуры zip-файла) и как данные (часть содержимого файла).

Поток DEFLATE представляет собой последовательность блоков , где каждый блок может быть сжатым или несжатым. Мы обычно думаем только о сжатых блоках, например, ядро - это один большой сжатый блок. Но есть и несжатые, которые начинаются с 5-байтового заголовка с полем длины, что означает просто: «выведите следующие n байтов дословно». Распаковка несжатого блока означает только удаление 5-байтового заголовка. Сжатые и несжатые блоки могут свободно смешиваться в потоке DEFLATE. На выходе получается конкатенация результатов распаковки всех блоков по порядку. Понятие «несжатый» имеет значение только на уровне DEFLATE; данные файла по-прежнему считаются «сжатыми» на уровне zip, независимо от того, какие блоки используются.

Проще всего представить эту конструкцию как внутреннее перекрытие, от последнего файла к первому. Начинаем со вставки ядра, которое будет формировать конец файла данных для каждого файла. Добавляем заголовок локального файла LFH N и заголовок центрального каталога CDH N , который указывает на него. Устанавливаем поле метаданных «сжатый размер» в LFH N и CDH N на сжатый размер ядра. Теперь добавляем 5-байтовый заголовок несжатого блока (зелёным цветом на диаграмме), поле длины которого равно размеру LFH N . Добавляем второй заголовок локального файла LFH N −1 и заголовок центрального каталога CDH N −1 , который указывает на него. Устанавливаем поле метаданных «сжатый размер» как новый заголовок сжатого размера ядра плюс размер несжатого заголовка блока (5 байт) плюс размер LFH N .

На данный момент zip-файл содержит два файла с именами Y и Z. Давайте пройдёмся, что увидит парсер при разборе. Предположим, что сжатый размер ядра 1000 байт, а размер LFH N - 31 байт. Начинаем с CDH N −1 и следуем указателю на LFH N −1 . Имя первого файла Y, а сжатый размер его файла данных 1036 байт. Интерпретируя следующие 1036 байт как поток DEFLATE, мы сначала сталкиваемся с 5-байтовым заголовком несжатого блока, который говорит скопировать следующие 31 байт. Записываем следующие 31 байт, которые являются LFH N , которые мы распаковываем и добавляем в файл Y. Двигаясь дальше в потоке DEFLATE, находим сжатый блок (ядро), который распаковываем в файл Y. Теперь мы достигли конца сжатых данных и закончили с файлом Y.

Переходя к следующему файлу, мы следуем указателю от CDH N к LFH N и находим файл с именем Z, сжатый размер которого составляет 1000 байт. Интерпретируя эти 1000 байт как поток DEFLATE, мы сразу же сталкиваемся со сжатым блоком (снова ядро) и распаковываем его в файл Z. Теперь мы достигли конца финального файла и закончили. Выходной файл Z содержит распакованное ядро; выходной файл Y тот же, но дополнительно с префиксом 31 байт LFH N .

Завершаем конструкцию, повторяя процедуру цитирования, пока zip-архив не будет включать нужное количество файлов. Каждый новый файл добавляет заголовок центрального каталога, заголовок локального файла и несжатый блок для цитирования непосредственно следующего заголовка локального файла. Сжатые файловые данные, как правило, представляют собой цепочку несжатых блоков DEFLATE (процитированных заголовков локальных файлов), за которыми следует сжатое ядро. Каждый байт в ядре вносит около 1032N в выходной размер, потому что каждый байт является частью всех N файлов. Выходные файлы тоже разного размера: более ранние больше, чем более поздние, потому что больше цитируют заголовки локальных файлов. Содержимое выходных файлов не имеет особого смысла, но никто не говорил, что оно должно иметь смысл.

У этой конструкции цитирования с перехлёстом лучше совместимость, чем у конструкции полного перекрытия из предыдущего раздела, но совместимость достигается за счёт степени сжатия. Там каждый добавленный файл стоил только заголовка центрального каталога, здесь он стоит заголовка центрального каталога, заголовка локального файла и ещё 5 байт для заголовка цитирования.

Оптимизация

Получив базовую конструкцию zip-бомбы, постараемся сделать её максимально эффективной. Мы хотим ответить на два вопроса:

• Какова максимальная степень сжатия для данного размера zip-файла?
• Какова максимальная степень сжатия, учитывая ограничения формата zip?

Сжатие ядра

Нам выгодно максимально сжать ядро, ведь каждый распакованный байт умножается на N . С этой целью используем кастомный компрессор DEFLATE под названием bulk_deflate, специализированный на сжатии строки повторяющихся байтов.

Все приличные архиваторы DEFLATE приближаются к степени сжатия 1032 на бесконечном потоке повторяющихся байтов, но нас волнует конкретный размер. В наш размер архива bulk_deflate вмещает больше данных, чем архиваторы общего назначения: примерно на 26 КБ больше, чем zlib и Info-ZIP, и примерно на 15 КБ больше, чем Zopfli , который жертвует скоростью ради качества сжатия.

Цена высокой степени сжатия bulk_deflate - отсутствие универсальности. Он может сжимать только строки из повторяющихся байт и только определённой длины, а именно 517 + 258 k для целого числа k ≥ 0. Кроме хорошего сжатия, bulk_deflate работает быстро, выполняя работу практически за одно и то же время независимо от размера входных данных, не считая работу по фактической записи сжатой строки.

Имена файлов

Для наших целей имена файлов - практически мёртвый груз. Хотя они вносят вклад в выходной размер, будучи частью цитируемых заголовков локальных файлов, но байт в имени файла вносит гораздо меньше, чем байт в ядре. Мы хотим, чтобы имена файлов были как можно короче, при этом разными, не забывая про совместимость.

Каждый байт, потраченный на имя файла, означает два байта, не потраченных на ядро (два, потому что каждое имя файла появляется дважды: в заголовке центрального каталога и в заголовке локального файла). Байт имени файла приводит в среднем только к (N + 1) / 4 байта вывода, в то время как байт в ядре считается как 1032 N . Примеры: , , .

Первым соображением совместимости является кодировка. В спецификации формата zip указано, что имена файлов должны интерпретироваться как CP 437 или UTF-8 , если установлен определённый бит флага (APPNOTE.TXT, приложение D). Это основной момент несовместимости между парсерами zip, которые могут интерпретировать имена файлов в некоторой фиксированной или специфичной для локали кодировке. Поэтому для совместимости лучше ограничиться символами с одинаковой кодировкой как в CP 437, так и в UTF-8. А именно, это 95 печатаемых символов US-ASCII.

Мы также связаны ограничениями именования файловой системы. Некоторые файловые системы нечувствительны к регистру, поэтому "a" и "А" не считаются разными именами. Распространённые файловые системы, такие как FAT32, запрещают определённые символы , такие как "*" и "?".

В качестве безопасного, но не обязательно оптимального компромисса, наша zip-бомба будет использовать имена файлов из 36-символьного алфавита, который не включает специальные символы и символы разного регистра:

0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Имена файлов генерируются очевидным образом, все позиции по очереди, с добавлением позиции в конце цикла:

"0", "1", "2", …, "Z", "00", "01", "02", …, "0Z", …, "Z0", "Z1", "Z2", …, "ZZ", "000", "001", "002", …
Существует 36 имён файлов длиной в один символ, 36² имён длиной два символа и так далее. Четырёх байтов достаточно для 1 727 604 различных имён файлов.

Учитывая, что у имён файлов в архиве обычно будет разная длина, как их лучше упорядочить: от самого короткого к самому длинному или наоборот? Если немного подумать, то лучше ставить самые длинные имена последними. Такое упорядочение добавляет более 900 МБ вывода в zblg.zip , по сравнению с упорядочением от самого длинного к самому короткому. Впрочем, это незначительная оптимизация, потому что 900 МБ - всего 0,0003% от общего размера выдачи.

Размер ядра

Конструкция цитирования с перехлёстом позволяет разместить сжатое ядро данных, а затем дёшево скопировать его много раз. Для конкретного размера zip-файла X , сколько места оптимально выделить для хранения ядра, а сколько для создания копий?

Чтобы найти оптимальный баланс, нужно оптимизировать только одну переменную N , количество файлов в zip-архиве. Каждое значение N требует определённого объёма накладных расходов для заголовков центрального каталога, заголовков локальных файлов, заголовков блоков цитирования и имён файлов. Всё остальное пространство будет занято ядром. Поскольку N должно быть целым числом, а вы можете поместить только определённое количество файлов, прежде чем размер ядра упадёт до нуля, достаточно проверить каждое возможное значение N и выбрать то, что даёт наибольшую выдачу.

Применение процедуры оптимизации к X = 42 374 для 42.zip находит максимум при N = 250. Эти 250 файлов требуют 21 195 байт служебных данных, оставляя 21 179 байт для ядра. Ядро такого размера распаковывается в 21 841 249 байт (соотношение 1031,3 к 1). 250 копий распакованного ядра плюс немного процитированных заголовков локальных файлов даёт общий распакованный выход 5 461 307 620 байт и степень сжатия 129 000.

CRC-32 можно смоделировать как машину состояний, обновляющую 32-разрядный регистр состояния для каждого входного бита. Основные операции обновления для битов 0 и 1 такие:

Uint32 crc32_update_0(uint32 state) { // Shift out the least significant bit. bit b = state & 1; state = state >> 1; // If the shifted-out bit was 1, XOR with the CRC-32 constant. if (b == 1) state = state ^ 0xedb88320; return state; } uint32 crc32_update_1(uint32 state) { // Do as for a 0 bit, then XOR with the CRC-32 constant. return crc32_update_0(state) ^ 0xedb88320; }
Если вы представляете регистр состояния как 32-элементный двоичный вектор и используете XOR для сложения и умножения, то crc32_update_0 является линейным отображением ; т. е. его можно представить как умножение на бинарную матрицу перехода 32×32. Чтобы понять, почему, обратите внимание, что умножение матрицы на вектор - это просто суммирование столбцов матрицы после умножения каждого столбца на соответствующий элемент вектора. Операция сдвига state >> 1 просто берёт каждый бит i вектора состояния и умножает его на вектор, который равен нулю везде, кроме бита i − 1 (нумерация битов справа налево). Условно говоря, конечное XOR state ^ 0xedb88320 происходит только тогда, когда бит b равен единице. Это можно представить как первое умножение b на 0xedb88320, а затем XORинг в данное состояние.

Кроме того, crc32_update_1 - это просто crc32_update_0 плюс (XOR) константа. Это делает crc32_update_1 аффинным преобразованием : умножение матрицы с последующим отображением (т. е., векторное сложение). Мы можем представить умножение матрицы и отображение за один шаг, если увеличим размеры матрицы преобразования до 33×33 и добавим дополнительный элемент к вектору состояния, который всегда равен 1 (такое представление называется однородными координатами).

Матрицы преобразования 33×33 M 0 и M 1 , которые вычисляют изменение состояния CRC-32, выполненное битами 0 и 1, соответственно. Векторы столбцов хранятся с наиболее значащим битом внизу: читая первый столбец снизу вверх, вы видите полиномиальную константу CRC-32 edb8832016 = 111 011 011 0111 0001 0000011 001 00000 2 . Эти две матрицы различаются только в конечном столбце, который представляет вектор трансляции в однородных координатах. В M 0 трансляция равна нулю, а в M 1 - edb88320 16 , полиномиальная константа CRC-32. Единицы сразу над диагональю представляют состояние операции state >> 1

Обе операции crc32_update_0 и crc32_update_1 можно представить матрицей перехода 33×33. Показаны матрицы M 0 и M 1 . Преимущество матричного представления состоит в том, что матрицы можно умножать. Предположим, мы хотим увидеть изменение состояния, произведённое обработкой ASCII-символа "a", двоичное представление которого равно 01100001 2 . Мы можем представить совокупное изменение состояния CRC-32 этих восьми бит в одной матрице преобразования:

И мы можем представить изменение состояния строки повторяющихся "а" путём перемножения многих копий М а - возведение матрицы в степень. Мы можем быстро сделать это, используя алгоритм быстрого возведения в степень , который позволяет вычислить M n всего за log 2 n шагов. Например, вот матрица изменения состояния строки из 9 символов "а":
Алгоритм быстрого умножения матриц полезен для вычисления M kernel , матрицы для несжатого ядра, поскольку ядро представляет собой строку повторяющихся байтов. Чтобы получить контрольную сумму CRC-32 из матрицы, умножьте матрицу на нулевой вектор (нулевой вектор находится в однородных координатах, то есть 32 нуля, а затем единица; здесь мы опускаем незначительное осложнение пред- и постобработки контрольной суммы для проверки на соответствие). Чтобы вычислить контрольную сумму для каждого файла, мы работаем в обратном направлении. Начинаем с инициализации M:= M kernel . Контрольная сумма ядра также является контрольной суммой конечного файла N , поэтому умножаем M на нулевой вектор и сохраняем полученную контрольную сумму в CDH N и LFH N . Данные файла N−1 такие же, как файловые данные файла N , но с добавленным префиксом LFH N . Поэтому вычисляем , матрицу изменения состояния для LFH N и обновляем . Теперь M представляет кумулятивное изменение состояния от обработки LFH N за ядром. Вычисляем контрольную сумму для файла N−1 , снова умножив M на нулевой вектор. Продолжаем процедуру, накапливая матрицы изменения состояния в M , пока все файлы не будут обработаны.

Расширение: Zip64

Ранее мы столкнулись с проблемой расширения из-за ограничений формата zip - невозможно было выдать более 281 ТБ, независимо от того, насколько ловко упакован zip-файл. Можно превзойти эти ограничения, используя Zip64 , расширение формата zip, которое увеличивает размер некоторых полей заголовка до 64 бит. Поддержка Zip64 отнюдь не универсальна, но это одно из наиболее часто реализуемых расширений. Что касается степени сжатия, то эффект Zip64 заключается в увеличении размера заголовка центрального каталога с 46 до 58 байт, а размера заголовка локального каталога с 30 до 50 байт. Посмотрев на формулу оптимального коэффициента расширения в упрощённой модели, мы видим, что zip-бомба в формате Zip64 по-прежнему растёт квадратично, но медленнее из-за большего знаменателя - это видно на диаграмме внизу. За счёт потери совместимости и замедления роста у нас снимаются практически любые ограничения на размер файла.

Предположим, нам нужна zip-бомба, которая расширяется до 4,5 ПБ, как 42.zip. Насколько большим должен быть архив? С помощью двоичного поиска мы находим, что минимальный размер такого файла составляет 46 МБ.

• zbxl.zip 46 MB → 4,5 PB (Zip64, менее совместимый)

zipbomb --mode=quoted_overlap --num-files=190023 --compressed-size=22982788 --zip64 > zbxl.zip
4,5 петабайта - примерно столько данных записал Телескоп горизонта событий для первого изображения чёрной дыры : стойки и стойки с жёсткими дисками в дата-центре.

С Zip64 уже практически неинтересно рассматривать максимальную степень сжатия, потому что мы можем просто продолжать увеличивать размер zip-файла и степень сжатия вместе с ним, пока даже сжатый zip-файл не станет непомерно большим. Интересный порог, однако, составляет 2 64 байта (18 EB или 16 EiB) - столько данных не поместится в большинстве файловых систем. Двоичный поиск находит самую маленькую zip-бомбу, которая производит по крайней мере столько выходных данных: она содержит 12 миллионов файлов и сжатое ядро 1,5 ГБ. Общий размер zip-файла составляет 2,9 ГБ, и он распаковывается в 2 64 +11 727 895 877 байт со степенью сжатия более 6,2 млрд к одному. Я не выкладывал этот файл для скачивания, но вы можете сгенерировать его самостоятельно, используя . У него файлы такого размера, что выявился даже баг в Info-ZIP UnZip 6.0.

Zipbomb --mode=quoted_overlap --num-files=12056313 --compressed-size=1482284040 --zip64 > zbxxl.zip

Расширение: bzip2

DEFLATE является наиболее распространенным алгоритмом сжатия для формата zip, но это только один из многих вариантов. Вероятно, вторым наиболее распространённым алгоритмом является bzip2 . Хотя он не такой совместимый, как DEFLATE. Теоретически, в bzip2 максимальная степень сжатия около 1,4 миллиона к одному, что позволяет плотнее упаковывать ядро.

Bzip2 первым делом кодирует «шаг выполнения» (run-length encoding), уменьшая длину строки повторяющихся байтов в 51 раз. Затем данные разделяются на блоки по 900 КБ и каждый блок сжимается отдельно. Теоретически, один блок может сжаться до 32 байт. 900 000 × 51 / 32 = 1 434 375.

Не обращая внимания на потери совместимости, позволяет ли bzip2 сделать более эффективную бомбу?

Да - но только для небольших файлов. Проблема в том, что в bzip2 нет ничего похожего на несжатые блоки DEFLATE, которые мы использовали для цитирования заголовков локальных файлов. Таким образом, невозможно перекрывать файлы и повторно использовать ядро - для каждого файла нужно записывать собственную копию, поэтому общая степень сжатия будет не лучше, чем коэффициент для любого отдельно взятого файла. На графике внизу мы видим, что без перекрытия bzip2 превосходит DEFLATE только для файлов размером около мегабайта.

Остаётся надежда только на альтернативное средство цитирования заголовков в bzip2, что обсуждается в следующем разделе. Кроме того, если вы знаете, что определённый zip-парсер поддерживает bzip2 и допускает несоответствие имён файлов, вы можете использовать конструкцию полного перекрытия, которая не нуждается в цитировании.

Сравнение коэффициента сжатия у разных zip-бомб. Обратите внимание на логарифмические оси. Каждая конструкция показана с и без Zip64. У конструкций без перекрытия линейная скорость роста, что видно по постоянному соотношению осей. Вертикальное смещение графика bzip2 означает, что степень сжатия bzip2 примерно в тысячу раз больше, чем у DEFLATE. У конструкций DEFLATE с цитированием квадратичная скорость роста, о чём свидетельствует наклон к осям 2:1. Вариант Zip64 немного менее эффективен, но позволяет выдавать более 281 ТБ. Графики для bzip2 с цитированием через дополнительное поле переходят из квадратичных в линейные при достижении либо максимального размера файла (2 32 −2 байта), либо максимально разрешённого количества файлов

Расширение: цитирование через дополнительное поле

До сих пор мы использовали функцию DEFLATE для цитирования заголовков локальных файлов, и мы только что увидели, что этот трюк не работает в bzip2. Однако есть альтернативный способ цитирования, несколько более ограниченный, который использует только функции формата zip и не зависит от алгоритма сжатия.

В конце структуры заголовка локального файла есть дополнительное поле переменной длины для хранения информации, которая не вписывается в обычные поля заголовка (APPNOTE.TXT, раздел 4.3.7). Дополнительная информация может включать в себя, например, метку точного времени или uid/gid из Unix. Информация Zip64 тоже хранится в дополнительном поле. Дополнительное поле представлено в виде структуры length-value; если увеличить длину без добавления значения, то дополнительное поле включит то, что находится за ним в zip-файле, а именно следующий заголовок локального файла. Используя этот метод, каждый заголовок локального файла может «цитировать» следующие заголовки, заключая их в собственное дополнительное поле. По сравнению с DEFLATE здесь три преимущества:

1. Цитирование через дополнительное поле требует только 4 байта, а не 5, оставляя больше места для ядра.
2. Оно не увеличивает размер файлов, что означает больший размер ядра, учитывая ограничения формата zip.
3. Оно обеспечивает цитирование в bzip2.

Несмотря на эти преимущества, цитирование через дополнительные поля менее гибкое. Это не цепочка, как в DEFLATE: каждый заголовок локального файла должен содержать не только непосредственно следующий заголовок, но и все последующие заголовки. Дополнительные поля увеличиваются по мере приближения к началу zip-файла. Поскольку максимальная длина поля 2 16 −1 байт, можно цитировать только до 1808 заголовков локальных файлов (или 1170 в Zip64), предполагая, что имена (в случае DEFLATE вы можете использовать дополнительное поле для цитирования первых (самых коротких) заголовков локальных файлов, а затем переключиться на цитирование DEFLATE для остальных). Другая проблема: чтобы соответствовать внутренней структуре данных дополнительного поля, необходимо выбрать 16-битный тег для типа (APPNOTE.TXT, раздел 4.5.2), предшествующий данным цитирования. Мы хотим выбрать тег типа, который заставит парсеры игнорировать данные в кавычках, а не пытаться интерпретировать их как значимые метаданные. Zip-парсеры должны игнорировать теги неизвестного типа, поэтому мы можем выбирать теги случайным образом, но есть риск, что в будущем какой-то тег нарушит совместимость конструкции.

Предыдущая диаграмма иллюстрирует возможность использования дополнительных полей в bzip2, c и без Zip64. На обоих графиках есть точка перелома, когда рост переходит от квадратичного к линейному. Без Zip64 это происходит там, где достигается максимальный размер несжатого файла (2 32 −2 байта); затем можно увеличить только количество файлов, но не их размер. График полностью заканчивается, когда количество файлов достигает 1809, тогда у нас заканчивается место в дополнительном поле для цитирования дополнительных заголовков. С Zip64 перелом происходит на 1171 файле, после чего может быть увеличен только размер файлов, но не их количество. Дополнительное поле помогает и в случае DEFLATE, но разница настолько мала, что визуально не заметна. Она увеличивает степень сжатия zbsm.zip на 1,2%; zblg.zip на 0,019%; и zbxl.zip на 0,0025%.

Обсуждение

В своей работе на эту тему Плетц с коллегами используют перехлёст файлов для создания почти самореплицирующегося zip-архива. Сам перехлёст файлов предложил ранее (слайд 47) Гинваэль Колдвинд.

Мы разработали конструкцию zip-бомбы с перехлёстом цитирования с учётом совместимости - ряда различий в реализациях, некоторые из которых показаны в таблице ниже. Полученная конструкция совместима с zip-парсерами, которые работают обычным способом, то есть сначала проверяя центральный каталог и используя его в качестве индекса файлов. Среди них уникальный zip-парсер из Nail , который автоматически генерируется из формальной грамматики. Однако конструкция несовместима с «потоковыми» парсерами, которые анализируют zip-файл от начала до конца за один проход без предварительного чтения центрального каталога. По своей природе потоковые парсеры не допускают перекрытия файлов ни в каком виде. Скорее всего, они извлекут только первый файл. Кроме того, они могут даже выдать ошибку, как в случае с