[Перевод] Ещё лучшая ZIP-бомба
В статье показано, как создать нерекурсивнуюzip-бомбу, которая обеспечивает высокую степень сжатия путём перекрытия файлов внутри zip-контейнера. «Нерекурсивная» означает, что она не зависит от рекурсивной распаковки декомпрессорами файлов, вложенных в zip-архивы: здесь всего один раунд. Выходной размер увеличивается квадратично от входного, достигая степени сжатия более 28 миллионов (10 МБ → 281 ТБ) в пределах формата zip. Ещё большее расширение возможно с помощью 64-разрядных расширений. Конструкция использует только наиболее распространённый алгоритм сжатия DEFLATE и совместима с большинством парсеров zip.
- zbsm.zip 42 kB → 5.5 GB
- zblg.zip 10 MB → 281 TB
- zbxl.zip 46 MB → 4.5 PB (Zip64, менее совместима с парсерами)
Исходный код:
git clone https://www.bamsoftware.com/git/zipbomb.git
zipbomb-20190702.zip
Данные и исходники иллюстраций:
git clone https://www.bamsoftware.com/git/zipbomb-paper.git
*Есть две версии 42.zip: старая 42 374 байт, и более новая на 42 838 байт. Разница в том, что новая требует пароль перед распаковкой. Мы сравниваем только со старой версией. Вот копия файла, если он вам нужен: 42.zip.
**Я хотел бы знать и указать автора 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. Это список заголовков центрального каталога. Каждый заголовок центрального каталога содержит метаданные одного файла, такие как имя файла и контрольная сумма CRC-32, а также обратный указатель на заголовок локального файла. У заголовка центрального каталога длина 46 байт плюс длина имени файла.
Файл состоит из заголовка локального файла, за которым следуют сжатые данные файла. Длина заголовка локального файла — 30 байт плюс длина имени файла. Он содержит избыточную копию метаданных из заголовка центрального каталога, а также размеров сжатого и несжатого файлов данных за ним. Zip — это формат контейнера, а не алгоритм сжатия. Данные каждого файла сжимаются с помощью алгоритма, указанного в метаданных, — обычно DEFLATE.
Это описание формата zip опускает много деталей, которые не нужны для понимания zip-бомбы. Для получения полной информации см. раздел 4.3 APPNOTE.TXT или «Структуру файла PKZip» Флориана Бухгольца, или см. исходный код.
Значительная избыточность и много двусмысленностей в формате zip открывают возможности для озорства разных видов. Zip-бомба — это лишь верхушка айсберга. Ссылки для дальнейшего чтения:
Сжимая длинную строку повторяющихся байтов, мы можем создать ядро сильно сжатых данных. Сама по себе степень сжатия ядра не может превышать предел DEFLATE в 1032, поэтому нам нужен способ повторного использования ядра во многих файлах, без создания его отдельной копии в каждом файле. Мы можем сделать это путём перекрытия файлов: сделать так, чтобы многие заголовки центрального каталога указывали на один файл, данные которого являются ядром.
Рассмотрим пример, как эта конструкция влияет на степень сжатия. Предположим, что ядро 1000 байт распаковывается в 1 МБ. Тогда первый мегабайт выдачи «стоит» 1078 байт входных данных:
- 31 байт для заголовка локального файла (включая 1-байтовое имя файла)
- 47 байт для заголовка центрального каталога (включая 1-байтовое имя файла)
- 1000 байт на ядро
Но каждый 1 МБ вывода после первого стоит всего 47 байт — нам не нужен ещё один заголовок локального файла или другая копия ядра, только дополнительный заголовок центрального каталога. Таким образом, в то время как первая ссылка из ядра имеет степень сжатия 1 000 000 / 1078 ≈ 928, каждая дополнительная ссылка двигает коэффициент ближе к 1 000 000 / 47 ≈ 21 277, а большое ядро поднимает потолок.
Проблема с этой идеей заключается в отсутствии совместимости. Поскольку многие заголовки центрального каталога указывают на один заголовок локального файла, то метаданные (в частности, имя файла) не могут совпадать для каждого файла. Некоторые парсеры ругаются на это. Например, Info-ZIP UnZip (стандартная программа unzip в Unix) извлекает файлы, но с предупреждениями:
$ unzip overlap.zip
inflating: A
B: mismatching "local" filename (A),
continuing with "central" filename version
inflating: B
...
Питоновский zipfile тоже выбрасывает исключение:
$ 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, независимо от того, какие блоки используются.
Проще всего представить эту конструкцию как внутреннее перекрытие, от последнего файла к первому. Начинаем со вставки ядра, которое будет формировать конец файла данных для каждого файла. Добавляем заголовок локального файла LFHN и заголовок центрального каталога CDHN, который указывает на него. Устанавливаем поле метаданных «сжатый размер» в LFHN и CDHN на сжатый размер ядра. Теперь добавляем 5-байтовый заголовок несжатого блока (зелёным цветом на диаграмме), поле длины которого равно размеру LFHN. Добавляем второй заголовок локального файла LFHN−1 и заголовок центрального каталога CDHN−1, который указывает на него. Устанавливаем поле метаданных «сжатый размер» как новый заголовок сжатого размера ядра плюс размер несжатого заголовка блока (5 байт) плюс размер LFHN.
На данный момент zip-файл содержит два файла с именами Y и Z. Давайте пройдёмся, что увидит парсер при разборе. Предположим, что сжатый размер ядра 1000 байт, а размер LFHN — 31 байт. Начинаем с CDHN−1 и следуем указателю на LFHN−1. Имя первого файла Y, а сжатый размер его файла данных 1036 байт. Интерпретируя следующие 1036 байт как поток DEFLATE, мы сначала сталкиваемся с 5-байтовым заголовком несжатого блока, который говорит скопировать следующие 31 байт. Записываем следующие 31 байт, которые являются LFHN, которые мы распаковываем и добавляем в файл Y. Двигаясь дальше в потоке DEFLATE, находим сжатый блок (ядро), который распаковываем в файл Y. Теперь мы достигли конца сжатых данных и закончили с файлом Y. Переходя к следующему файлу, мы следуем указателю от CDHN к LFHN и находим файл с именем Z, сжатый размер которого составляет 1000 байт. Интерпретируя эти 1000 байт как поток DEFLATE, мы сразу же сталкиваемся со сжатым блоком (снова ядро) и распаковываем его в файл Z. Теперь мы достигли конца финального файла и закончили. Выходной файл Z содержит распакованное ядро; выходной файл Y тот же, но дополнительно с префиксом 31 байт LFHN.
Завершаем конструкцию, повторяя процедуру цитирования, пока 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. Примеры: 1, 2, 3.
Первым соображением совместимости является кодировка. В спецификации формата 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.
zipbomb --mode=quoted_overlap --num-files=250 --compressed-size=21179 > zbsm.zip
Оптимизация привела к почти равномерному распределению пространства между ядром и заголовками файлов. Это не совпадение. Рассмотрим упрощённую модель конструкции цитирования с перехлёстом. В упрощённой модели мы игнорируем имена файлов, а также небольшое увеличение размера выходного файла из-за цитирования заголовков локальных файлов. Анализ упрощённой модели покажет, что оптимальное распределение между ядром и заголовками файлов примерно равномерное, а размер выдачи при оптимальном распределении растёт квадратично в зависимости от размера входа.
Определение некоторых констант и переменных:
Пусть H (N) — объём оверхеда на заголовки для N файлов. См. диаграмму, чтобы понять суть формулы.
Для ядра остаётся X − H (N) места. Общий распакованный размер SX (N) равен размеру N копий ядра, распакованных с соотношением C (в этой упрощённой модели мы игнорируем незначительное дополнительное расширение от упомянутых заголовков локальных файлов).
$$display$$S_X (N) = (X − H (N)) C N\\ = (X − (N ⋅ (CDH + LFH) + (N − 1) ⋅ Q)) C N\\ = −(CDH + LFH + Q) C N^2 + (X + Q) C N$$display$$
SX (N) — многочлен в части N, поэтому максимум должен находиться там, где производная S’X (N) равна нулю. Взятие производной и нахождение нуля дает нам NOPT, оптимальное количество файлов.
$$display$$S′X (N_{OPT}) = −2 (CDH + LFH + Q) C N_{OPT} + (X + Q) C\\ 0 = −2 (CDH + LFH + Q) C N_{OPT} + (X + Q) C\\ N_{OPT} = (X + Q) / (CDH + LFH + Q) / 2$$display$$
H (NOPT) даёт оптимальный объём пространства для размещения заголовков файлов. Он не зависит от CDH, LFH и C и близок к X/2.
$$display$$H (N_{OPT}) = N_{OPT} ⋅ (CDH + LFH) + (N_{OPT} − 1) ⋅ Q\\ = (X − Q) / 2$$display$$
SX (NOPT) — общий распакованный размер при оптимальном распределении. Из этого мы видим, что размер выдачи растёт квадратично при увеличении входных данных.
Увеличивая размер zip-файла, в конечном итоге мы столкнёмся с пределами формата zip: в архиве может быть не более 216−1 файлов размером не более 232−1 байт каждый. Хуже того, некоторые реализации принимают максимальные значения как индикатор наличия 64-битных расширений, поэтому наши пределы фактически 216−2 и 232−2. Бывает, что первым мы сталкиваемся с ограничением на размер несжатого файла. При размере zip-файла 8 319 377 байт наивная оптимизация даст нам количество файлов 47 837 и максимальный файл 232+311 байт.
(На самом деле всё немного сложнее, потому что точные лимиты зависят от реализации. Питоновский zipfile игнорирует количество файлов, archive/zip в Go позволяет увеличивать количество файлов до тех пор, пока у них совпадают младшие 16 бит. Но для общей совместимости мы должны придерживаться установленных лимитов).
Если мы не можем беспредельно увеличивать N или размер ядра, то хотелось бы найти максимальную степень сжатия в пределах формата zip. Необходимо сделать ядро как можно больше с максимальным количеством файлов. Несмотря на то, что мы больше не можем поддерживать примерно равномерное разделение между ядром и заголовками файлов, каждый добавленный файл всё равно увеличивает степень сжатия — просто не так быстро, как если бы мы могли продолжать увеличивать ядро. Фактически, по мере добавления файлов нам нужно будет уменьшать размер ядра, чтобы освободить место для файла максимального размера, который немного растёт с каждым добавленным файлом.
План приводит к zip-архиву с 216−2 файлов и ядру, которое распаковывается в 232−2 178 825 байт. Файлы будут больше по направлению к началу zip-архива — первый и самый большой файл распаковывается в 232−56 байт. Это так близко, как мы можем получить, используя грубые выходные параметры bulk_deflate — кодирование окончательных 54 байт будет стоить дороже, чем их размер (zip-файл в целом имеет степень сжатия 28 миллионов, а конечные 54 байта получат максимум 54 ⋅ 1032 ⋅ (216 − 2) ≈ 36?5 миллион байт, так что это только помогает, если 54 байта можно закодировать в один байт —, а я не мог закодировать меньше чем в два. Поэтому, если вы не можете закодировать 54 байта в 1 байт, это только снижает степень сжатия). Размер этой zip-бомбы на выходе: 281 395 456 244 934 байта, 99,97% из теоретического максимума (232 − 1) × (216 − 1). Любое существенное улучшение коэффициента сжатия может быть достигнуто только за счёт уменьшения размера входного сигнала, а не увеличения выходного.
zipbomb --mode=quoted_overlap --num-files=65534 --max-uncompressed-size=4292788525 > zblg.zip
Среди метаданных в заголовке центрального каталога и заголовке локального файла есть контрольная сумма несжатых данных файла — CRC-32. Это создаёт проблему, потому что объём вычислений CRC-32 для каждого файла пропорционален его размеру, который по умолчанию очень большой (в конце концов, это zip-бомба). Мы бы предпочли делать работу, которая хотя бы пропорциональна размеру архива. В нашу пользу работают два фактора: у всех файлов общее ядро, а несжатое ядро представляет собой строку повторяющихся байтов. Представим CRC-32 как матричный продукт — это позволит не только быстро вычислить контрольную сумму ядра, но и повторно использовать вычисления между файлами. Метод, описанный в этом разделе, является небольшим расширением функции crc32_combine в zlib, которую Марк Адлер объясняет здесь.
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 M0 и M1, которые вычисляют изменение состояния CRC-32, выполненное битами 0 и 1, соответственно. Векторы столбцов хранятся с наиболее значащим битом внизу: читая первый столбец снизу вверх, вы видите полиномиальную константу CRC-32 edb8832016 = 111011011011100010000011001000002. Эти две матрицы различаются только в конечном столбце, который представляет вектор трансляции в однородных координатах. В M0 трансляция равна нулю, а в M1 — edb8832016, полиномиальная константа CRC-32. Единицы сразу над диагональю представляют состояние операции state >> 1
Обе операции crc32_update_0 и crc32_update_1 можно представить матрицей перехода 33×33. Показаны матрицы M0 и M1. Преимущество матричного представления состоит в том, что матрицы можно умножать. Предположим, мы хотим увидеть изменение состояния, произведённое обработкой ASCII-символа 'a', двоичное представление которого равно 011000012. Мы можем представить совокупное изменение состояния CRC-32 этих восьми бит в одной матрице преобразования:
И мы можем представить изменение состояния строки повторяющихся 'а' путём перемножения многих копий Ма — возведение матрицы в степень. Мы можем быстро сделать это, используя алгоритм быстрого возведения в степень, который позволяет вычислить Mn всего за log2n шагов. Например, вот матрица изменения состояния строки из 9 символов 'а':
Алгоритм быстрого умножения матриц полезен для вычисления Mkernel, матрицы для несжатого ядра, поскольку ядро представляет собой строку повторяющихся байтов. Чтобы получить контрольную сумму CRC-32 из матрицы, умножьте матрицу на нулевой вектор (нулевой вектор находится в однородных координатах, то есть 32 нуля, а затем единица; здесь мы опускаем незначительное осложнение пред- и постобработки контрольной суммы для проверки на соответствие). Чтобы вычислить контрольную сумму для каждого файла, мы работаем в обратном направлении. Начинаем с инициализации M:= Mkernel. Контрольная сумма ядра также является контрольной суммой конечного файла N, поэтому умножаем M на нулевой вектор и сохраняем полученную контрольную сумму в CDHN и LFHN. Данные файла N−1 такие же, как файловые данные файла N, но с добавленным префиксом LFHN. Поэтому вычисляем 
, матрицу изменения состояния для LFHN и обновляем 
. Теперь M представляет кумулятивное изменение состояния от обработки LFHN за ядром. Вычисляем контрольную сумму для файла N−1, снова умножив M на нулевой вектор. Продолжаем процедуру, накапливая матрицы изменения состояния в M, пока все файлы не будут обработаны.
Ранее мы столкнулись с проблемой расширения из-за ограничений формата 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-файл не станет непомерно большим. Интересный порог, однако, составляет 264 байта (18 EB или 16 EiB) — столько данных не поместится в большинстве файловых систем. Двоичный поиск находит самую маленькую zip-бомбу, которая производит по крайней мере столько выходных данных: она содержит 12 миллионов файлов и сжатое ядро 1,5 ГБ. Общий размер zip-файла составляет 2,9 ГБ, и он распаковывается в 264+11 727 895 877 байт со степенью сжатия более 6,2 млрд к одному. Я не выкладывал этот файл для скачивания, но вы можете сгенерировать его самостоятельно, используя исходный код. У него файлы такого размера, что выявился даже баг в Info-ZIP UnZip 6.0.
zipbomb --mode=quoted_overlap --num-files=12056313 --compressed-size=1482284040 --zip64 > zbxxl.zip
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 с цитированием через дополнительное поле переходят из квадратичных в линейные при достижении либо максимального размера файла (232−2 байта), либо максимально разрешённого количества файлов
До сих пор мы использовали функцию DEFLATE для цитирования заголовков локальных файлов, и мы только что увидели, что этот трюк не работает в bzip2. Однако есть альтернативный способ цитирования, несколько более ограниченный, который использует только функции формата zip и не зависит от алгоритма сжатия.
В конце структуры заголовка локального файла есть дополнительное поле переменной длины для хранения информации, которая не вписывается в обычные поля заголовка (APPNOTE.TXT, раздел 4.3.7). Дополнительная информация может включать в себя, например, метку точного времени или uid/gid из Unix. Информация Zip64 тоже хранится в дополнительном поле. Дополнительное поле представлено в виде структуры length-value; если увеличить длину без добавления значения, то дополнительное поле включит то, что находится за ним в zip-файле, а именно следующий заголовок локального файла. Используя этот метод, каждый заголовок локального файла может «цитировать» следующие заголовки, заключая их в собственное дополнительное поле. По сравнению с DEFLATE здесь три преимущества:
- Цитирование через дополнительное поле требует только 4 байта, а не 5, оставляя больше места для ядра.
- Оно не увеличивает размер файлов, что означает больший размер ядра, учитывая ограничения формата zip.
- Оно обеспечивает цитирование в bzip2.
Несмотря на эти преимущества, цитирование через дополнительные поля менее гибкое. Это не цепочка, как в DEFLATE: каждый заголовок локального файла должен содержать не только непосредственно следующий заголовок, но и все последующие заголовки. Дополнительные поля увеличиваются по мере приближения к началу zip-файла. Поскольку максимальная длина поля 216−1 байт, можно цитировать только до 1808 заголовков локальных файлов (или 1170 в Zip64), предполагая, что имена назначены, как положено (в случае DEFLATE вы можете использовать дополнительное поле для цитирования первых (самых коротких) заголовков локальных файлов, а затем переключиться на цитирование DEFLATE для остальных). Другая проблема: чтобы соответствовать внутренней структуре данных дополнительного поля, необходимо выбрать 16-битный тег для типа (APPNOTE.TXT, раздел 4.5.2), предшествующий данным цитирования. Мы хотим выбрать тег типа, который заставит парсеры игнорировать данные в кавычках, а не пытаться интерпретировать их как значимые метаданные. Zip-парсеры должны игнорировать теги неизвестного типа, поэтому мы можем выбирать теги случайным образом, но есть риск, что в будущем какой-то тег нарушит совместимость конструкции.
Предыдущая диаграмма иллюстрирует возможность использования дополнительных полей в bzip2, c и без Zip64. На обоих графиках есть точка перелома, когда рост переходит от квадратичного к линейному. Без Zip64 это происходит там, где достигается макси
