В сентябре 2022 года я решил создать себе новый hot wallet для ежедневного использования. Хотелось сгенерировать себе что-то легко узнаваемое, например 0x0000...aced. Мой друг Алекс сказал мне, что он использовал для таких целей Profanity, инструмент для создания Ethereum кошельков с красивыми адресами. Когда я открыл их GitHub репозиторий, то я увидел в README файле, что была найдена критическая ошибка. Кроме того, в тот же день была опубликована статья в блоге 1inch с некоторыми идеями по её использованию.

У меня было свободное время, поэтому я решил погрузиться в тему и самостоятельно реализовать взлом. В этой статье я объясню, как можно взломать адреса, сгенерированные с помощью Profanity, и как я смог подобрать приватный ключ к кошельку моего друга на MacBook M1 Pro (16 Гб) за 26 минут. Погнали!

Как получить публичный ключ?

Если у вас есть закрытый ключ k (случайное число длиной 256 бит), то вам нужно немного "пошаманить" с криптографией на эллиптической кривой, чтобы получить ваш открытый ключ. Более конкретно, ваш открытый ключ K = k * G , где G - точка генератор на эллиптической кривой. Затем вы берете 5 младших байт хеша keccak256 от открытого ключа, чтобы получить адрес, на который вам обычно и кидают эфиры. Как можно догадаться, вы не можете обратить этот процесс. Таким образом, единственный способ получить адрес с множеством ведущих нулей - это перебрать много различных приватных ключей.

Как работает Profanity?

Profanity использует OpenCL ядра для параллельного запуска большого количества GPU потоков, которые генерируют миллионы адресов в секунду с помощью простого алгоритма:

1. Profanity генерирует случайный сид S, который используется при генерации закрытого ключа k.

2. Затем он создает примерно 4 миллиона воркеров, где i-й воркер принимает K[i, 0] = (k + i * 2^192) * G в качестве начального открытого ключа.

3. После этого каждый воркер увеличивает свой открытый ключ на G, пока адрес, полученный из него, не будет соответствовать требованиям пользователя. Когда он будет найден, вы можете легко вычислить закрытый ключ, зная номер воркера, который его нашел, и сколько итераций он совершил.

Что здесь не так?

Описанный метод прост и эффективен, но в его реализации есть небольшая проблема, которая имеет значительные последствия. Случайный сид S, который используется для генерации закрытого ключа k, является 32-разрядным числом вместо 64-разрядного. Обратите внимание, что если вы знаете S, который Profanity использовал в процессе генерации, вы знаете все закрытые ключи, которые он генерировал.

Мы собираемся использовать тот факт, что количество всех сидов всего 2^32.

И как хакнуть-то?

Идея алгоритма

Если у вас есть адрес, который был сгенерирован с помощью Profanity, вы можете найти соответствующий закрытый ключ, выполнив обратный процесс генерации:

1. Сначала вам нужно восстановить открытый ключ K_t соответствующий адресу. Вы можете это сделать, если есть любая транзакция подписанная жертвой. Например, вы можете попробовать найти её на Etherscan.

2. Если открытый ключ K_t был сгенерирован из начального открытого ключа K при помощи добавления необходимого количества G (+2^192 * G для каждой строки и +G для каждого столбца), то можно инициализировать воркеров таким образом, чтобы i-й воркер начинал с открытого ключа K_t - i * 2^192 * G, а затем уменьшал его на G на каждой итерации, пока K не будет найден кем-либо из них.

3. Если вы знаете, какой закрытый ключ соответствует K, вы можете вычислить и закрытый ключ жертвы (опять же, потому что вы знаете строку и столбец, где его нашли).

Вроде бы все просто! Но есть один нюанс! Мы не знаем начальный открытый ключ K.

Уязвимость

Да, мы не знаем, какой начальный открытый ключ K был использован при генерации кошелька жертвы. Но мы знаем, что он был получен из одного из 2^32 сидов (примерно 4 миллиарда). Таким образом, мы можем проитерироваться через все и предварительно вычислить все соответствующие закрытые и открытые ключи.

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

Если бы сид имел 64 бит, то мы были бы должны предварительно вычислить 2^64 открытых ключей. Это очень много! В 4 миллиарда раз больше!

Задача поиска

Эта часть алгоритма самая нетривиальная.

Еще разок. Мы должны уметь проверять элемент на принадлежность множеству из 2^32 открытых ключей. В идеале бы, чтобы каждый воркер выполнял эту проверку на GPU, чтобы CPU не был бы узким горлышком.

У нас есть 2^32 открытых ключей. На самом деле это не выглядит огромным количеством для современных компьютеров. Но каждый открытый ключ занимает 32 байта в сжатом виде. Поэтому, если вы решите хранить их все на диске, то потребуется 128Gb памяти. Более того, скорее всего ваш компьютер не имеет 128Gb RAM для загрузки их в память.

Проще говоря, 128Gb это слишком много. Если мы используем только 12 байт для каждого открытого ключа, то потребуется 48GB памяти для их хранения, и вероятность коллизий будет низкой. Так и поступим. Когда я использовал только 8 байт, то коллизии происходили.

Разделение

Если у вас есть видеокарта с 48Gb и более, то вы можете загрузить все ключи в память, чтобы каждый воркер мог искать их с помощью двоичного поиска или используя какую-то другую структуры данных.

Я хотел взломать Алекса с помощью моего MacBook Pro M1 с 16Gb памяти, поэтому я выбрал 8Gb в качестве ограничения и попробовал несколько разных подходов.

Бинарный поиск

Я поделил множество всех открытых ключей на 4 части по 2^30 ключей в каждой. Затем взял только 8 байт от каждого открытого ключа, отсортировал их и загрузил в память. Это ровно 8Gb памяти видеокарты.

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

Как вы помните, я уже упомянул, что коллизии случаются, если использовались только 8 байт. Но это не большая проблема, потому что они случаются редко, и когда это происходит, я сравниваю эти открытые ключи на CPU используя 12 байт.

Хеш-таблица

Двоичный поиск - отличный алгоритм, но есть ли способ найти элемент еще быстрее? Конечно. Мы можем использовать хеш-таблицу. Однако есть одно ограничение. Все слоты использовать нельзя. Как правило, большинство реализаций хеш-таблиц с открытой адресацией имеют коэффициенты загрузки 50%. Таким образом, если у нас выделено 8Gb для хеш-таблицы, то мы можем хранить только 2^29 открытых ключей (8 байт каждый). Поэтому нам нужно разбить наш набор на 8 частей, а не на 4.

Стоит ли это того? С одной стороны, чем больше у нас частей, тем больше мы тратим вычислительных ресурсов на повторное прохождение по одним и тем же ключам. С другой стороны, проверка элемента на принадлежность в хеш-таблице работает за O(1) вместо O(log N) для двоичного поиска.

Сравнение

Реализации с хеш-таблицей потребовалось 64 минуты для выполнения 10 000 итераций, а двоичному поиску - почти 4 часа. Даже несмотря на повторные вычисления для 8 частей, вместо 4, первый подход работает гораздо быстрее.

Хак

Вот и самая вкусная часть! Я потратил 7,5 часов на предподсчет открытых ключей на своем Macbook Pro, а также 26 минут на сам взлом закрытого ключа Алекса. Это просто безумие!

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

Что тут сказать? Будьте осторожны, всегда проверяйте свой код и подписывайтесь на мой аккаунт в Twitter и блог в Telegram ????

Disclaimer

Этот пост был подготовлен исключительно в образовательных и развлекательных целях.