Рекурсивный zip-архив

http://research.swtch.com/2010/03/zip-files-all-way-down.html
  • Перевод
Многие хабрапользователи наверняка знакомы с квайнами — программами, выводящими собственный исходный код. Сегодня я хочу показать как сделать интересный вариант квайна — ZIP-архив, который распаковывается сам в себя.



Алгоритм Lempel-Ziv



Алгоритм, используемый в ZIP-файлах (Lempel-Ziv) на самом деле довольно прост. В нём есть два вида инструкций: literal(n), за которым следует поток данных который надо вывести как есть, и repeat(d, n), который возращается назад на d байт и выводит n байт с этой позиции.

Соответственно, наша задача такова: используя этот алгоритм написать программу, которая выводит свой код при запуске. Другими словами, написать сжатый поток данных который разворачивается сам в себя. Программа-максимум: написать поток который разворачивается сам в себя с произвольными данными в начале и конце (чтобы его можно было использовать как настоящий zip- или gzip-файл, с заголовком и другими необходимыми данными).

Давайте договоримся использовать Ln и Rn в качестве сокращений для literal(n) и repeat(n, n), и программа предполагает что каждый код это один байт. L0, соответственно, это аналог NOP в Lempel-Ziv, L5 hello выведет hello; то же самое выведет L3 hel R1 L1 o.

Простой квайн будет выглядеть так:

Код Вывод
no-op L0
no-op L0
no-op L0
вывести 4 байта L4 L0 L0 L0 L4 L0 L0 L0 L4
повторить 4 последних байта R4 L0 L0 L0 L4
вывести 4 байта L4 R4 L4 R4 L4 R4 L4 R4 L4
повторить 4 последних байта R4 R4 L4 R4 L4
вывести 4 байта L4 L0 L0 L0 L0 L0 L0 L0 L0


(Видно что содержимое столбцов «Код» и «Вывод» одинаково)

Интересная часть программы — последовательность из 6 байт L4 R4 L4 R4 L4 R4, которая выводит 8 байт: R4 L4 R4 L4 R4 L4 R4. То есть, выводит саму себя с одним байтом до и одним после.

Если мы пишем квайн на Питоне, обычно проблемой является то что оператор print всегда длиннее того что он выводит. Мы решаем эту проблему с помощью рекурсии, подставляя строку для печати в саму себя. Здесь мы можем использовать другой подход. Программа на Lempel-Ziv частично повторяется, таким образом что повторяемая подстрока содержит весь изначальный фрагмент. Рекурсия здесь в самом представлении программы, а не в выполнении. В любом случае, этот фрагмент критически важен. До финального R4 вывод программы отстаёт от ввода. После выполнения, вывод на один байт опережает ввод.

Операторы-пустышки L0 можно использовать и в более общем варианте программы, который может дополнять себя произвольными трёхбайтовыми префиксом и суффиксом:

Код Вывод
вывести 4 байта L4 aa bb cc L4 aa bb cc L4
повторить 4 последних байта R4 aa bb cc L4
вывести 4 байта L4 R4 L4 R4 L4 R4 L4 R4 L4
повторить 4 последних байта R4 R4 L4 R4 L4
вывести 4 байта L4 R4 xx yy zz R4 xx yy zz
повторить 4 последних байта R4 R4 xx yy zz


(Вывод равен коду плюс aa bb cc добавленные в начало и xx yy zz , добавленные в конец)

Мне пришлось потратить большую часть воскресенья чтобы добраться до этой точки, но когда у меня получилось, я уже знал что победил. Из своих экспериментов я выяснил, что довольно легко создать программу которая выводит саму себя без нескольких инструкций или даже такую которая выводит себя с префиксом, минус несколько инструкций. Дополнительные байты aa bb cc в выводе позволяют добавить к программе нужный фрагмент. Так же несложно написать код, который выводит себя плюс дополнительные три байта xx yy zz. Эти два приёма можно использовать чтобы добавить к архиву заголовок и дополнительные данные в конце.

Вот так выглядит программа с произвольными префиксом и суффиксом:

Код Вывод
выводим префикс [P] P
выводим p+1 байт Lp+1 [P] Lp+1 [P] Lp+1
повторяем последние p+1 байт Rp+1 [P] Lp+1
выводим 1 байт L1 Rp+1 Rp+1
выводим 1 байт L1 L1 L1
выводим 4 байта L4 Rp+1 L1 L1 L4 Rp+1 L1 L1 L4
повторяем 4 последних байта R4 Rp+1 L1 L1 L4
выводим 4 байта L4 R4 L4 R4 L4 R4 L4 R4 L4
повторяем 4 последних байта R4 R4 L4 R4 L4
выводим 4 байта L4 R4 L0 L0 Ls+1 R4 L0 L0 Ls+1
повторяем 4 последних байта R4 R4 L0 L0 Ls+1
no-op L0
no-op L0
выводим s+1 байт Ls+1 Rs+1 [S] Rs+1 [S]
повторяем последние s+1 байт Rs+1 Rs+1 [S]
выводим суффикс [S] S


(Вывод это P, потом байты из колонки «Код», потом S.)

ZIP-файл, распаковывающийся в себя



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

Первая проблема: перевести наш квайн, записанный в упрощённых опкодах, в реальные опкоды Lempel-Ziv. RFC 1951 определяет формат DEFLATE, используемый в gzip и zip; последовательность блоков, каждый из которых содержит последовательность опкодов закодированных кодированием Хаффмана. Кодирование Хаффмана назначает строки разной длины разным опкодам, что не совпадает с нашим предположением о том что у опкодов одинаковая длина. Но постойте! Мы можем, если постараемся, найти кодирование с фиксированной длиной, которое можно будет использовать.

В DEFLATE существуют блоки литералов и блоки опкодов. Заголовок блока литералов это 5 байт:



Если наши опкоды L занимают по 5 байт каждый, опкоды R тоже должны занимать по 5 байт, и каждый байт выше будет повторён пять раз (например, аргумент для L4 теперь занимает 20 байт, и R4 повторяет последние 20 байт вывода). Блок опкодов с одним repeat(20,20) занимает несколько меньше 5 байт:



К счастью, блок опкодов содержащий две инструкции repeat(20,10) делает то же самое и занимает ровно 5 байт:



Кодирование repeat с другой длиной аргументов требует несколько более сложных трюков, но похоже что мы можем разработать 5-байтовые коды которые повторяют строку длиной от 9 до 64 байт. Например, вот блоки повторяющие 10 и 40 байт:





Блок, повторяющий последние 10 байт на 2 бита меньше чем нужно, но за каждым блоком повтора следует блок литералов, который начинается с трёх нулевых битов и добивки до границы ближайшего байта. Если блок повтора заканчивается за 2 бита до границы и за ним следует блок литералов, добивка вставит недостающие два бита. Точно так же блок повторяющий 40 байт выходит за границу на 5 бит, но эти биты нулевые. Начиная блок на 5 бит позже мы отнимаем эти биты у добивки. Оба этих трюка работают потому что последние 7 бит любого блока повтора — нулевые, и биты в первом байте блока литералов тоже нулевые, так что граница не видна. Если бы блок литералов начинался с одного бита, этот хитрый приём бы не сработал.

Второе препятствие состоит в том что zip-архивы (и gzip тоже) хранят контрольную сумму несжатых данных. Так как несжатые данные представляют собой тот же самый zip-архив, контрольная сумма тоже участвует в расчёте. Стало быть, нам надо найти такое значение x, при котором контрольная сумма станет равна x. Рекурсия наносит ответный удар.

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

Если Вы захотите повторить всё это самостоятельно, Вас ждёт ещё парочка несложных проблем, например сделать так чтобы длина tar-файла делилась без остатка на 512 и сжатие заголовка zip до 59 байт чтобы Rs+1 было не больше R64. Но это просто вопрос программирования.

Итак, у меня получились файлы r.gz (gzip-архив), r.tar.gz (tar-файл, сжатый gzip), и r.zip (zip-архив). Жаль, но я не смог найти программу, которая бы рекурсивно распаковывала эти файлы до бесконечности. Было бы забавно понаблюдать, но похоже намного менее сложные zip-бомбы уже испортили нам всё веселье.

Если чувствуете себя в форме, вот rgzip.go, программа на Go, генерирующая эти файлы. Интересно, получится ли у Вас создать zip-файл, содержащий gzip файл, содержащий в свою очередь оригинальный zip-файл). Кен Томпсон предложил попробовать создать zip-архив, распаковывающий свою копию но немного большего размера, чтобы при рекурсивном распакавывании размер архива рос до бесконечности (если у Вас получится то или другое, пожалуйста, оставьте комментарий).
Поделиться публикацией

Похожие публикации

Комментарии 55
    +4
    Всегда хотел создать миниатюрный архивчик в пару килобайт с терабайтом нулей и отправить заклятым друзьям по почте.
      +9
      Для этого лучше всего подойдет алгоритм RLE.
        +3
        Я слышал такую фишку: генерируем 10-Гигабайтный файл с нулями, запаковываем его в незапароленный zip и выкладываем на файлообменник вроде народа (которые проверяют файлы антивирусом). При распаковке сервером этого архива выходит небольшая своего рода DoS-атака
        Хотя, сейчас, наверное, уже пофиксили
          –1
          А не будет разве так, что размер файла слишком большой, и при распаковке он не поместится, и проверка просто игнорируется?
            +3
            Именно это я и имел ввиду под «пофиксили»
              +5
              >игнорируется
              Т.е. туда можно прятать вирусы?
                +3
                Отличная идея!
                Только вирус размером в несколько гигабайт… как-то палится
                  +9
                  Троянский СЛОН.
                  0
                  Толку то, если пользователь тоже не сможет распаковать?
                +2
                мм, каспером в режиме максимальной секурности попробуйте кто-нибудь…
                  +2
                  Палится уже года два.
                  +2
                  Все современные библиотеки проверяют при распаковке коэффициент сжатия.
                    +3
                    Это называется Zip bomb. Большинство антивирусов умеют справляться с такой напастью.
                    +8
                    Я такой архивчик даже делал. Потом когда забыл про это дело и наткнулся на него, решил посмотреть, что там внутри :)
                      +1
                      Как-то баловался с архивами. Писал в Word'е "=rand(200,99)", размножал текст на 1000 страниц, затем архивировал. Брал много таких файлов и архивировал, затем полученный архив архивировал. В итоге 60Гб записывал на дискету и ещё оставалось место. :)
                        +1
                        fsutil file createnew c:\tmp 2147483648
                        rar a c:\arc.rar c:\tmp

                        Копать отсюда. Такой файл будет проверяться антивирусом. А слишком большие файлы пропускаются. Можете закинуть пару разных архивов на вирустотал. Много антивирусов тупо кони двигают
                        +21
                        спасибо, во время написали друг меня давно просил фотки скинуть сейчас я ему отправлю пусть распаковывает.
                        • НЛО прилетело и опубликовало эту надпись здесь
                            +2
                            Я попробовал рекурсивный. Сказало, что внутри исполняемый файл и отправить его нельзя. o_O
                              +3
                              Кстати, на virustotal уже этот файлик кто-то залил. :)
                                +1
                                Думаю, это были любознательные читатели оригинальной статьи :)
                                  +1
                                  Ну вот, я такой же как все… Первая же идея была, но решил сначала проверить комментарии.
                                +2
                                о, господи
                                  +5
                                  Здесь zip-файл, содержащий картинку и сам себя.
                                  +2
                                  онлайн касперский валится Ж)
                                    +16
                                    Дал тестеру, ничего не сказав — сидит, распаковывает.
                                    • НЛО прилетело и опубликовало эту надпись здесь
                                        +2
                                          +2
                                          про www.unforgettable.dk/42.zip авира ругнулась на архивную бомбу.
                                            +1
                                            ага, ESET тоже.
                                            >> Archbomb.ZIP троянская программа
                                          +12
                                          Ха, архивчик сломал мозг антивирусу на работе :)

                                          Archive Blocked by McAfee Web Gateway
                                          You requested an archive with other nested archives included. The recursion level exceeds the defined maximum.
                                          Please contact your administrator.
                                          Url: "http://swtch.com/r.zip"
                                          File: "http://swtch.com/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip/r/r.zip"
                                            +4
                                            Это как раз нормально, превышен максимальный уровень вложенности. Продумали.
                                            +12
                                            Положил в общую с девушкой папку дропбокса, назвал именем предыдущей девушки. Жду.
                                              +2
                                              хм, может выложить на торренты и назвать Megapron.avi
                                                0
                                                Размер маловат :)
                                                  +1
                                                  На торрентах альтернатив полно. Для достижения эффекта нужно сильное желание поциента увидеть содержимое :)
                                                +2
                                                Здорово. Вообще я когда Зива-Лемпеля изучал подобные мысли приходили в голову. Вот только срезался на контрольной сумме. Не смог придумать как ее саму в себя засчитать.

                                                А еще в детстве баловались — брали diskedit.com и на флопике закольцовывали директории в FATах. А потом давали ламерам «классные игрушки в директории GAMES» :)) ну а там соответственно что-то типа games\arcade\new\games\arcade\new\… :)
                                                  +2
                                                  Я делал дискетку с одной директорией и парочкой файлов в корне. При попытке удаления директории она оставалась на месте, а файлы исчезали.
                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                                      +2
                                                      Круто ) по-тру-хеккерски )
                                                        +1
                                                        Да, такие фокусы тоже делали :) Вот только самая жесть начиналась, если попытаться удалить подобную иерархию штатными средствами ОС :)
                                                      +11
                                                      Сразу напомнило, скачать весь Интернет.
                                                        +1
                                                        Как-то раз закачали такой selfgz.gz в онлайн-проверялку на вирусы Dr. Web

                                                        Ну, он честно отработал свои, кажется, 100 вложений, потом сдался на распаковке этого.
                                                          +1
                                                          Кто-нибудь может сделать такой архив, чтобы он был поувесистей? Хотя бы метр-два?
                                                            +3
                                                            Корни этого дела сидят в фидо.

                                                            Дело в том, что сообщения в фидо между узлами передавались в zip-архивах которые автоматически распаковывались нодой (сервером) по приходу на сервер. Только ленивый не подсовывал ноде мэйл-бомбу, с архивом который распаковываясь занимал все свободное место на сервере. С целью посмотреть, что будет.

                                                            Так выглядела дос-атака 15 лет назад. :)
                                                              +3
                                                              Новое это хорошо забытое старое. Сейчас даже про ФИДО мало кто вспомнит.
                                                              Только хотел эту историю сам написать, но увидел ваш пост.
                                                              Делал подобную штуку просто исправлением пары ссылочных байтов в zip архиве через hex редактор дос навигатора.
                                                                +4
                                                                Пора создавать хабр для «пенсионеров» типа нас ;) Сейчас наверное и про дос навигатор никто не вспомнит
                                                                  +3
                                                                  Ну почему же, помним :)
                                                                    +1
                                                                    как можно забыть встроенный тетрис и пентрикс )
                                                                +1
                                                                Я еще в школе создавал огромный файл заполненый нулями и архивировал его в несколько килобайт.
                                                                Потом искал шару в сети и распаковывал ее там. Вот как без интернета было весело :)
                                                                  +1
                                                                  Почитал коменты, оказывается я не один такой «умный» :)
                                                                  +1
                                                                  Gmail утверждает, что архив содержит исполняемый файл и поэтому его нельзя отправлять. Гугл сервера настолько мощные, что могут пройти целиком бесконечную рекурсию?
                                                                    0
                                                                    >Гугл сервера настолько мощные, что могут пройти целиком бесконечную рекурсию?
                                                                    -сколько отжиманий может сделать Чак Норрис?
                                                                    -все!
                                                                    +1
                                                                    Пытался сделать нечто подобное лет пять назад, чтобы J2ME программа могла сама себя раздавать по Bluetooth)) Тогда мне не хватило умения и опыта. Возможно стоит использовать ваши разработки. Спасибо, интересно почитать.

                                                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                    Самое читаемое