[Перевод] Прикладная криптография. Как мы восстановили биткоины на 300 тысяч долларов
Поделюсь с вами одной историей. Около двадцати лет назад я получил степень по физике, но занимался реверс-инжинирингом и криптоанализом. Наша компания AccessData работала в конце 90-х и начале 2000-х. Тогда правительство США постепенно снимало ограничения на экспорт криптографии, однако парольная защита в большинстве программ по-прежнему оставалась довольно бесполезной. Мы брали офисные программы, я проводил реверс-инжиниринг и выяснял алгоритм шифрования, а потом ломал криптозащиту.
Это был нескончаемый поток интересных, но не особенно сложных математических головоломок. За всё время я написал около сорока взломщиков паролей. Мы продавали их домашним пользователям, системным администраторам, местным и федеральным правоохранительным органам. Мне пришлось несколько раз съездить в федеральный центр подготовки сотрудников правоохранительных органов в Глинко, чтобы объяснить ребятам из Секретной службы, ФБР и АТФ основы криптографии и как использовать наши продукты.
Особенно ярко мне запомнились два проекта. Первым был Microsoft Word 97. До его появления файлы шифровались с помощью XOR байтов открытого текста и 16-байтовой строки, которая выводилась из пароля. Самыми распространёнными байтами в файле Word обычно были 0×00, 0xFF или 0×20 (пробел), поэтому мы просто выбирали самый распространённый символ в каждом столбце и проверяли 316 вариантов. Восстановление ключа обычно происходило мгновенно, но чтобы людям не казалось, что они зря потратили деньги, мы вставили небольшую анимацию, похожую на голливудскую хакерскую сцену с множеством случайных символов, из которых постепенно проявляется правильный пароль.
Microsoft Word 97 всё изменил. Возможно, в MSDN и раскрывали формат шифрования, но наша маленькая фирма не могла позволить себе подписку. И не факт, что нам бы разрешили написать программу для взлома после получения информации. Чтобы разобраться, в SoftICE я поставил точку останова сразу после ввода пароля, а затем медленно продвигался вверх по стеку, пока не нашёл алгоритм. Это было ещё до выхода IDA Pro, поэтому у меня на стене были приклеены десятки страниц распечаток с ассемблерным кодом, исчерченным красным маркером. Я был очень доволен, когда наконец во всём разобрался. В то время Microsoft было разрешено экспортировать только 40-битную криптографию, поэтому компания послушно реализовала строго разрешённую криптографию: они многократно хэшировали пароль в MD5 с помощью «соли» (случайно выбранных байтов из файла), чтобы получить 40-битный ключ, затем добавляли к нему соль и снова хэшировали. Проверка пароля на компьютерах того времени занимала примерно полсекунды. Нам пришлось задействовать атаку по словарю, потому что взломать пароль брутфорсом было практически невозможно. В итоге мы написали взломщик паролей для крупных компаний и агентств. Программа выполняла брутфорс 40-битного ключевого пространства, используя эти причудливые инструкции MMX на Pentium. Я слышал, что однажды она работала девять месяцев, прежде чем подобрала пароль.
Другой действительно забавный проект — это zip-архивы. Фил Кац, создатель PKZIP, принял необычное для того времени решение задокументировать свой формат файла и включить эту документацию в комплект программного обеспечения, что сделало ZIP любимым форматом у разработчиков. Роджер Шлафли разработал потоковый шифр для шифрования архивов. Стандарт zip быстро стал самым популярным под Windows, а многие другие форматы, такие как java-файлы .jar и документы OpenOffice, на самом деле представляли собой zip-файлы с определённой структурой каталогов внутри. Опенсорсная версия программы называлась InfoZIP, она лежала в основе практически всех фирменных zip-архиваторов, таких как WinZip. Когда я приступил к взлому WinZip, он занимал 95% рынка.
Эли Бихам и Пол Кохер опубликовали описание атаки с известным открытым текстом (текст перед шифрованием), но в нашем случае известный открытый текст был заархивирован. Чтобы получить коды Хаффмана в начале сжатого файла, вам по сути нужен весь файл. Атака была практически бесполезной для правоохранительных органов.
Шифр zip содержит 96 бит внутреннего состояния, разделённых на три 32-разрядных блока, которые называются key0, key1 и key2. Первый и третий — это внутреннее состояние двух копий CRC32, регистра линейного сдвига с обратной связью (простая математическая модель, позволяющая создавать псевдослучайные последовательности). Если вкратце, чтобы обновить состояние с новым байтом данных, вы сдвигаете всё вниз на один байт (отбрасывая нижний байт), а затем делаете XOR c константой из таблицы преобразования, проиндексированной по байту данных после XOR’а с нижним байтом. key1 — это внутреннее состояние усечённого линейного конгруэнтного генератора (TLCG). Чтобы обновить его внутреннее состояние, мы добавляем байт данных, умножаем на константу, которую назовём c, и добавляем единицу. Шифр работает следующим образом: вводите байт данных в первый CRC32, затем берёте нижний байт и вводите его в TLCG, затем берёте верхний байт оттуда и вводите его во второй CRC32, затем берёте состояние и возводите в квадрат (примерно), а потом выдаёте второй байт результата в поток байтов. Чтобы инициализировать 96 бит внутреннего состояния, вы начинаете с известного состояния и шифруете пароль, а затем шифруете десять байт соли.
PKZIP получает свои байты соли, выделяя память без её инициализации, так что там содержатся биты материалов из других запущенных программ или изображения, или документы, что угодно. Это прекрасно работало в Windows, но во многих системах Unix память инициализируется автоматически при выделении. InfoZIP выбирал байты соли с помощью функции rand языка Си. Он инициализировал состояние генератора случайных чисел, делая XOR временной метки на идентификаторе процесса, а затем генерировал десять байт на файл. В таком случае, зная временную метку и идентификатор процесса, можно было, теоретически, восстановить байты заголовка, что, в свою очередь, позволяло провести атаку Бихама и Кохера. Похоже, авторы InfoZIP знали об этой атаке, потому что пошли на шаг дальше — и зашифровали заголовок, используя пароль. Таким образом, у злоумышленника был только дважды зашифрованный открытый текст, и атака не сработала бы.
Я заметил это, поскольку пароль одинаковый в обоих проходах, первый байт потока одинаковый в каждом из них. Точно так же, как при двойном переключении выключателя света он остается там, где был в начале, при повторном XOR’е байта с одним и тем же байтом потока он остается нетронутым. Это позволило мне разработать очень мощную атаку только на шифротекст: получив пять зашифрованных файлов в архиве, я мог вывести внутреннее состояние функции rand без необходимости смотреть на метку времени или знать идентификатор процесса. Дальше я мог сгенерировать оригинальные незашифрованные заголовки. Поскольку всего несколько бит в каждой части шифра влияют на следующую часть, я также мог угадать несколько бит состояния и проверить, даёт ли расшифровка следующих байтов дважды тот ответ, который я ожидал. По мере продвижения вперёд мне приходилось угадывать всё меньше и меньше кусочков ключа. Каждый дополнительный файл также позволял исключить больше потенциальных материалов ключа; в то время это занимало несколько часов на одном десктопе. Я опубликовал статью об этом и получил возможность представить её в Японии на конференции Fast Software Encryption 2001.
Вскоре я ушёл из компании AccessData, в течение года работал в стартапе по нейросетям, провёл три года в обучении на степень магистра компьютерных наук в университете Окленда с Крисом Калудом, начал обучение на докторскую с математическим физиком Джоном Баэзом в Калифорнийском университете Риверсайда, шесть лет работал в команде по прикладной безопасности Google, закончил докторскую, а ещё через несколько лет стал техническим директором нового стартапа.
Примерно полгода назад я совершенно неожиданно получил сообщение в LinkedIn от одного русского парня. Он прочитал ту статью, которую я написал 19 лет назад, и хотел знать, будет ли атака работать на архиве, который содержит только два файла. Быстрый анализ показал, что это требует огромного количества вычислительных мощностей и денег. Поскольку есть только два файла, на каждом этапе подбора возникает гораздо больше ложных срабатываний. В конечном итоге получается 273 возможных ключей для тестирования, почти 10 секстиллионов. Я подсчитал, что большой кластер на GPU будет работать год, а его стоимость составит порядка 100 тысяч долларов. Он поразил меня, сказав, что согласен потратить столько денег, чтобы восстановить ключ.
Дело в том, что ещё в январе 2016 года он купил биткоинов примерно на $10–15 тыс. и поместил ключи в зашифрованный zip-файл. Теперь они стоили больше $300 тыс., и он не мог вспомнить пароль. К счастью, у него все еще был оригинальный ноутбук, и он точно знал время шифрования. Поскольку InfoZip выводит энтропию на основе временной метки, это обещало значительно сократить количество возможных вариантов ключа «всего» до 10 квинтиллионов — и делало атаку вполне осуществимой за пару месяцев на средней ферме GPU. Мы заключили контракт, и я приступил к работе.
Я потратил некоторое время, восстанавливая атаку, описанную в статье. К моему огорчению, там были некоторые хитрые детали, которые я упустил в статье, но я снова их проработал. А потом я обнаружил, что совершил ужасную ошибку, оценивая объём вычислений!
В моей оригинальной атаке я угадывал старшие байты ключей key1·c, key1·c2, key1·c3 и key1·c4. К тому времени, когда я угадал этот четвёртый байт, я знал полное состояние остальной части шифра; мне просто нужно было преобразовать эти четыре байта в исходный key1, и на этом всё. Я бы пробежался по 32-битному пространству состояний для key1 и проверил каждый из них, чтобы увидеть, даёт ли он правильные старшие байты. Однако, здесь пришлось бы проверить квинтиллионы ключей; если нужно сделать 232 теста на каждом, это заняло бы несколько сотен тысяч лет.
Я смутно помнил, что была проделана некоторая работа по криптоанализу TLCG через редукцию базиса решётки, поэтому откопал оригинальную статью. Так и было! Нужно было просто определить решётку с базисными векторами, заданными 232 и степенью константы из TLCG, а затем сделать редукцию базиса решетки. На уменьшенном базисе я мог бы восстановить исходное состояние из старших байтов простым перемножением матриц.
По крайней мере, такова идея. Нужно было пять байт, чтобы дойти до единственно правильного результата, и на тот момент атаки у меня было только четыре. Описанный в статье процесс редко давал правильный ответ. Однако я знал, что ответ должен быть близок к правильному, поэтому мог пробежаться по всем возможным значениям key1 и проверить разницу между реальным ответом и истинным. Разница всегда составляла один из 36 векторов! С помощью этой оптимизации я могу свести перебор всего к 36 вариантам вместо четырёх миллиардов. Мы всё ещё в деле.
Дальше мы столкнулись с проблемой передачи данных между машинами с GPU. Мой партнёр по бизнесу Нэш Фостер занимался реализацией в GPU. Он консультировал меня, насколько быстро выполняются различные операции, и писал большую часть вспомогательных структур для приложения с моим кодом для криптовзлома. Как получить эти петабайты ключей-кандидатов для тестирования на GPU? Они будут почти всё время простаивать, ворочая своими ядрами в ожидании работы. Мне пришло в голову, что на каждом этапе моей атаки проверяется много бит, а затем сохраняется только один из примерно 65 тыс. кандидатов. Если бы найти какой-то способ выводить эти биты на основе имеющейся информации, а не просто брутфорсить их, я бы сэкономил много работы и, что более важно, много сетевого трафика. Проблема здесь была в слишком сложных алгоритмах, представляющих смесь конечных полей с кольцами целых чисел, а они не очень хорошо сочетаются друг с другом.
Я подумал о других криптоаналитических атаках, которые мне известны. Одной из них была атака «встреча в середине» (meet-in-the-middle). Она казалась многообещающим кандидатом. Атака применяется к блочному шифру, когда он использует одну часть материала ключа для выполнения первой половины шифрования, а другую часть — для второй. Это относилось к шифру zip, но материал ключа намного перевешивал количество битов в середине. Затем мне пришло в голову, а что, если использовать линейность CRC32: если выполнить операцию XOR на двух выходах последнего CRC32, то результат будет независим от key2! Вместо того, чтобы вычислять промежуточное состояние шифра и хранить его в таблице, я бы вычислял XOR двух промежуточных состояний и хранил его вместо этого.
Я написал дифференциальную атаку «встреча в середине» и запустил её на своем ноутбуке. Этап, который раньше занимал несколько часов, теперь завершился всего за несколько секунд. Следующий этап, который мог занять неделю на GPU-ферме, завершился за несколько часов на одном мощном CPU. У меня не получалось оптимизировать третий этап атаки достаточно, чтобы это отразилось на общей скорости, но полностью отпала необходимость перемещать данные: мы просто вычисляли кандидатов для каждого GPU на компьютере с этими картами. Нэш написал код GPU, который работал с невероятной скоростью.
Атака продолжалась десять дней и закончилась неудачей.
Мое сердце было разбито. Неужели мы упустили один из возможных ключей? Мы вернулись назад и посмотрели на максимальный идентификатор процесса на его ноутбуке и обнаружили, что он был на несколько бит больше, чем мы ожидали, и поэтому было немного больше возможных исходных сидов для rand. Я также перепроверил весь наш код. Может, мы что-то упустили? Может, версия на CPU работала как-то иначе, чем на GPU? Наконец, я обнаружил, что версия на GPU не могла найти правильный ключ, когда он был вторым в списке кандидатов, а только первым. Покопавшись в коде, мы обнаружили, что перепутали индекс блока с индексом потока при вычислении смещения в структуре данных.
Мы исправили ошибку, повторно запустили код и нашли правильный ключ в течение дня. Наш клиент был очень доволен и дал нам большой бонус за то, что мы так быстро нашли ключ и сэкономили ему столько денег сверх нашей первоначальной оценки.
Теперь я ищу работу. Если у вас есть интересные проблемы по техническому анализу или оптимизации, дайте знать.
