В статье упоминаются 9 слоев zip файлов, поэтому это не простой случай скрепления кучей нулей. Почему 9, почему 10 файлов в каждом?

Во-первых, статья Википедии в настоящее время говорит о 5 слоях по 16 файлов. Не знаете, где происходит несоответствие, но это не все, что уместно. Реальный вопрос в том, почему использование гнездования в первую очередь.

DEFLATE, единственный поддерживаемый метод сжатия для zip файлов *, имеет максимальную степень сжатия 1032. Это может быть достигнуто асимптотически для любой повторяющейся последовательности 1-3 байта. Независимо от того, что вы делаете с zip файлом, до тех пор, пока он используется только с помощью DEFLATE, размер распакованного файла будет не более чем в 1032 раза больше размера исходного zip файла.

Поэтому для достижения действительно возмутительных коэффициентов сжатия необходимо использовать вложенные zip файлы. Если у вас есть 2 слоя сжатия, максимальное отношение равно 1032 ^ 2 = 1065024. Для 3, это 1099104768 и так далее. Для 5 слоев, используемых в 42.zip, теоретическая максимальная степень сжатия составляет 1170572956434432. Как вы можете видеть, фактический размер 42.zip далек от этого уровня. Часть этого является накладными расходами формата zip, а часть его заключается в том, что им просто все равно.

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

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

P.S. Можно создать zip файл, который будет распаковывать копию самого себя (quine). Вы также можете сделать тот, который распаковывает несколько копий. Поэтому, если вы рекурсивно распаковываете файл навсегда, максимально возможный размер бесконечен. Единственное ограничение состоит в том, что он может увеличиться не более чем на 1032 на каждой итерации.

P.P.S. Значение 1032 предполагает, что данные файла в zip не пересекаются. Одна из особенностей формата zip файла состоит в том, что он имеет центральный каталог, в котором перечислены файлы в архиве и смещения данных файла. Если вы создаете несколько записей в файлах, указывающих на одни и те же данные, вы можете достичь гораздо более высоких коэффициентов сжатия даже при отсутствии вложенности, но такой zip файл, скорее всего, будет отклонен парсерами.

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

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

Внешне представляет собой обычный архив весом 42 килобайта, но если его распаковать, вы получите 4,5 петабайта информации ! Думаете это невозможно? Как бы не так. Сама по себе ZIP -бомба не более чем пустышка, но в ней зашит особый алгоритм генерирования данных. Если пользователь попытается распаковать такой архив, содержащиеся в нём слои по 16 файлов на уровень начнут разворачиваться, генерируя огромное количество бессмысленной информации. В результате «взрыва» этой ZIP -бомбы диск оказывается забитым кэшем под завязку и система полностью зависает или падает в BSOD .

Что касается выхода из строя железа компьютера, то здесь, пожалуй, имеет место преувеличение, нагрузка на комплектующие действительно резко возрастёт, но вряд ли она окажется достаточно высокой, чтобы они сгорели. Если процессор перегреется, сработает защита и компьютер перезагрузится, хотя стопроцентной гарантии, что будет именно так, дать нельзя. В хлам ПК ZIP -бомбы не превратят, уже имеющиеся на диске файлы не уничтожат, но нервы пользователю потреплют так это точно. Распознают ли антивирусы подобные угрозы? Да, антивирусные программы могут распознавать зловреды этого типа, впрочем, представлять угрозу ZIP -бомба может и для самого антивируса: при попытке распаковать архив антивирус также может забить всю память и ничего и не найти.

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

Что за штука такая - 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) - Память расходуется, демонстрируется ошибка.

Тестирование декомпрессионной бомбы

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

Скачать Bombs

Zip бомба, также известная как как zip of death или декомпрессионная бомба, является вредоносным файлом архива, разработанным для того, чтобы сбивать или удалять бесполезную программу или систему, считывающую её. Он часто используется для отключения антивирусного программного обеспечения, чтобы создать отверстие для более традиционных вирусов. Вместо того, чтобы перехватывать нормальную работу программы, zip бомба позволяет программе работать должным образом, но архив тщательно обрабатывается так, что его распаковка (например, с помощью антивирусного сканера для поиска вирусов) требует слишком много времени, дискового пространства или памяти.

Zip бомба представляет собой небольшой файл для упрощения его передачи и избегания подозрений. Однако, при попытке распаковки данного файла, его содержимое запрашивает большего, чем система может обработать. Еще одним примером zip бомбы является файл 42.zip , который представляет собой zip файл, содержащий 42 килобайта сжатых данных, содержащий пять уровней вложенных ZIP-файлов в наборах по 16, каждый архив нижнего уровня, содержащий 4,3 гигабайта (4 294 967 295 байт, ~ 3,99 GiB), в общей сложности 4,5 петабайта (4 503 599 626 321 920 байт, ~ 3,99 PiB) несжатых данных. Подобные файлы все еще можно скачать с различных вебсайтов на просторах интернета. Во многих антивирусных сканерах в архивах выполняется только несколько уровней рекурсии, чтобы предотвратить атаки, которые могли бы вызвать переполнение буфера, состояние нехватки памяти или превысить приемлемое время выполнения программы. Zip-бомбы часто (если не всегда) полагаются на повторение идентичных файлов, чтобы достичь своих предельных коэффициентов сжатия. Методы динамического программирования можно использовать для ограничения обхода таких файлов, так что на каждом уровне рекурсивно выполняется только один файл, эффективно преобразуя их экспоненциальный рост в линейный.

При тестировании всегда лучше начинать с малого и продолжать работать на повышение. Начиная работать с самым большим файлом можно серьезно навредить приложению или системе – пользуйтесь этими бомбами с большой осторожностью.

Все файлы были сжаты (bzipped), чтобы обойти ограничение загрузки файлов GitMub 50 МБ. Группы файлов были заархивированы, а затем снова сжаты (bzipped). Удалите эти дополнительные предварительные кодировки перед сканированием.

Дополнительные источники

• HTTP/2: Углубленный анализ четырех основных недостатков веб-протокола следующего поколения (HTTP/2: In-depth analysis of the top four flaws of the next generation web protocol)
• Вы не смотрите на общую картину (You’re not looking at the big picture)
• В компрессионном гнезде Hornet, исследование безопасности сжатия данных в сетевых службах (In the Compression Hornet’s Nest: A Security Study of Data Compression in Network Services)
• Дьявольская HTTP компрессия – компрессионные бомбы (

*Есть две версии 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-файл от начала до конца за один проход без предварительного чтения центрального каталога. По своей природе потоковые парсеры не допускают перекрытия файлов ни в каком виде. Скорее всего, они извлекут только первый файл. Кроме того, они могут даже выдать ошибку, как в случае с