Между человеком и его криптовалютой стояло несколько квинтиллионов вариантов ключей расшифровки

В октябре Майкл Стэй получил с LinkedIn странное сообщение. Некий незнакомец потерял доступ к приватным ключам своей криптовалюты и попросил у Стэя помощь в возвращении доступа к его $300 000.

Было не так уж и удивительно, что «Чувак», как называет его Стэй, нашёл бывшего специалиста по безопасности из компании Google. Девятнадцать лет назад Стэй опубликовал работу с детальным описанием технологии взлома зашифрованных ZIP-файлов. Чувак купил в январе 2016 года биткоинов на сумму порядка $10 000, задолго до бума криптовалют. Он зашифровал приватные ключи в ZIP-файле и забыл пароль. И теперь он надеялся, что Стэй может помочь ему взломать его.

На прошедшей недавно конференции Defcon Стэй описал свои эпичные попытки сделать это.

ZIP – популярный формат файлов, используемый для сжатия больших файлов без потерь – как небольшой чехол с тесьмой может вместить ваш спальный мешок. Известно, что многие варианты реализации формата ZIP имеют проблемы с безопасностью – до того, что прошлым летом даже один американский сенатор обратился в Национальный институт стандартов и технологий с целью исследования этого вопроса. «Если мы успешно отыщем этот пароль, я вас отблагодарю», — написал Чувак со смайликом в конце. Проведя первичный анализ, Стэй оценил что взлом файла обойдётся в $100 000. Чувак принял предложение – всё-таки прибыль должна получиться большой.

«Давно я так не развлекался. Каждое утро я с радостью шёл на работу и боролся с этой проблемой», — говорит Стэй, в настоящее время работающий техническим директором фирмы Pyrofex, занимающейся технологиями блокчейна. «Шифрование ZIP несколько десятилетий назад разработал криптограф-непрофессионал – поэтому то, что оно так долго продержалось, довольно примечательно». Однако если некоторые ZIP-файлы можно взломать при помощи готовых утилит, то Чуваку удача не улыбнулась.

В частности поэтому за работу попросили так много. Новые поколения программ ZIP используют авторитетный и надёжный криптостандарт AES, а старые версии, одну из которых использовал Чувак — Zip 2.0 Legacy, который часто можно взломать. Степень сложности, однако, зависит от его реализации. «Одно дело – сказать, что стандарт поломанный, но реально его взломать – это совершенно другой вопрос», — говорит криптограф Мэтью Грин из университета Джонса Хопкинса.

Помочь Стэю с его подходом могло лишь небольшое количество подсказок. У Чувака до сих пор был ноутбук, который он использовал для создания зашифрованного ZIP – что подтверждало его право на владение этими биткоинами, а также давало Стэю информацию о том, какую именно программу ZIP и какой версии использовали для шифрования. Ему также было известно время создания файла, которое ПО Info-ZIP использует для своей криптографической схемы. Огромное количество возможных паролей и ключей шифрования Стэй смог уменьшить до нескольких квинтиллионов.

Для проведения атаки такого масштаба нужно было арендовать облачные мощности для обработки графики. Стэй обратился к Нэшу Фостеру, директору Pyrofex, чтобы тот написал код для криптоанализа и запустил его на GPU общего назначения от Nvidia Tesla. По мере углубления в проект Стэй сумел уточнить атаку и уменьшить время работы программы, требовавшееся для достижения результата.

«Изначально мы предполагали, что пару месяцев будем разрабатывать программу, а потом она будет работать ещё несколько месяцев, — рассказал Фостер журналу Wired. – В итоге Майк сумел более эффективно провести криптоанализ, и мы больше времени потратили на разработку атаки, а на работу у программы ушла всего неделя. Это сэкономило Чуваку уйму денег на аренде инфраструктуры. Лет десять назад это было бы невозможно сделать без сборки специального оборудования, а стоимость проекта, вероятно, превысила бы стоимость его биткоинов».

Однако вопрос того, сработает ли это перемалывание цифр на GPU, всё ещё оставался открытым. После нескольких месяцев труда над этой задачей Стэн, наконец, был готов попробовать. Чувак не предоставил Стэю и Фостеру весь файл целиком – он, вероятно, не доверял им, считая, что они могут украсть его криптовалюту, взломав ключи. Благодаря особенностям реализации шифрования в ZIP он мог предоставить Стэю и Фостеру только зашифрованные заголовки – информационные записи, касающиеся содержимого файла – не передавая его основное содержимое. К февралю, через 4 месяца после первого сообщения с LinkedIn, они подготовили программу и начали атаку.

Она проработала 10 дней и не справилась. Позднее Стэй писал, что «был убит горем».

«До этого мы встречались с разными багами, но на всех тестах, что я прогонял у себя на ноутбуке, всё работало отлично, — говорит он. – Если это и была ошибка, она должна была быть какой-то очень уж хитрой, и я беспокоился, что на её поиски у нас уйдёт много времени. Не помогал и тот факт, что в феврале стоимость биткоинов начала падать, а вместе с ней – и стоимость файла. Чувак очень беспокоился.

Стэй прошерстил всю программу, беспокоясь о наличии в ней какого-либо неверного предположения или скрытых ошибок. Но затем ему в голову пришла новая идея о том, с какого случайного начального значения [seed] можно начать работу генератора случайных чисел, используемого в их программе. Чувак тоже просмотрел тестовые данные и заметил ошибку, которая возникала, если GPU не обрабатывал правильный пароль при первом проходе. Стэй и Фостер исправили ошибку. Сделав два этих исправления в программе, они были готовы начать заново.

»Бах! И из файла выскочила куча биткоинов", — говорит Фостер. «Мы вздохнули с облегчением», — добавляет Стэй.

В итоге стоимость аренды инфраструктуры составила $6000 — $7000 вместо изначально предполагавшихся $100 000, говорит Фостер. Чувак заплатил вчетверо меньше, чем ожидал.

«Сделка для него получилась отличной, — говорит Фостер. – Такого рода проекты встречаются редко. Если бы у него была немного другая ситуация, если бы он использовал более свежую версию ZIP, это было бы невозможно сделать. Но в данном конкретном случае мы могли что-то сделать».

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

И всё же факт распространённости ZIP говорит о том, что у исследования Стэя и Фостера есть далеко идущие последствия.

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

Всем бы нам так везло.