В сентябре 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 потоков, которые генерируют миллионы адресов в секунду с помощью простого алгоритма:
Profanity генерирует случайный сид
S
, который используется при генерации закрытого ключаk
.Затем он создает примерно 4 миллиона воркеров, где i-й воркер принимает
K[i, 0] = (k + i * 2^192) * G
в качестве начального открытого ключа.После этого каждый воркер увеличивает свой открытый ключ на
G
, пока адрес, полученный из него, не будет соответствовать требованиям пользователя. Когда он будет найден, вы можете легко вычислить закрытый ключ, зная номер воркера, который его нашел, и сколько итераций он совершил.
Что здесь не так?
Описанный метод прост и эффективен, но в его реализации есть небольшая проблема, которая имеет значительные последствия. Случайный сид S
, который используется для генерации закрытого ключа k
, является 32-разрядным числом вместо 64-разрядного. Обратите внимание, что если вы знаете S
, который Profanity использовал в процессе генерации, вы знаете все закрытые ключи, которые он генерировал.
Мы собираемся использовать тот факт, что количество всех сидов всего 2^32
.
И как хакнуть-то?
Идея алгоритма
Если у вас есть адрес, который был сгенерирован с помощью Profanity, вы можете найти соответствующий закрытый ключ, выполнив обратный процесс генерации:
Сначала вам нужно восстановить открытый ключ
K_t
соответствующий адресу. Вы можете это сделать, если есть любая транзакция подписанная жертвой. Например, вы можете попробовать найти её на Etherscan.Если открытый ключ
K_t
был сгенерирован из начального открытого ключаK
при помощи добавления необходимого количестваG
(+2^192 * G
для каждой строки и+G
для каждого столбца), то можно инициализировать воркеров таким образом, чтобы i-й воркер начинал с открытого ключаK_t - i * 2^192 * G
, а затем уменьшал его наG
на каждой итерации, покаK
не будет найден кем-либо из них.Если вы знаете, какой закрытый ключ соответствует
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
Этот пост был подготовлен исключительно в образовательных и развлекательных целях.
vassabi
... мне кажется - или это не уязвимость, а просто стало можно делать такие переборы на ноутбуке?
0serg
Ограничение в 2^32 ключей — это однозначная уязвимость. Это по стойкости где-то как 6-символьный пароль что примерно в 1000 раз слабже минимально рекомендовавшегося еще 20 лет назад 8-символьного.
Прикинул что 8 символов из-за прогресса GPU теперь стало маловато, а у меня многие пароли остались с тех самых 20-летней давности времен как раз примерно такими, взгрустнул. Из плюсов — то что по сути вычислительный прогресс каждых 10 лет можно свести к необходимости 1 дополнительного символа в пароле
usego
Первое что нужно сделать - это хранить пароли в keepassе или подобном и пофиг, какой они длины.
vassabi
и еще не забыть пароль от keepass сделать длинным
maeris
И ещё не забыть про бекдоры и потенциальный слив всех паролей из пассворд менеджера.
me21
Ну когда база паролей не заливается в облако, слить её несколько сложнее. Каждого пользователя надо отдельно ломать.
DaneSoul
Это если менеджер паролей на офф-лайн машине, а так еще есть вариант, что зловреда внедрят в сам парольный менеджер и он в тихую сольет базу.
ilyapirogov
И еще не забыть, что огромное количество сайтов устанавливают бестолковые ограничения на длину пароля и допустимые символы.
Hungryee
А еще не забыть про то, что каждый день вас может сбить фура, и вообще не выходить на улицу
Что больше всего умиляет в подобных адептах секьюрити - они считают, что их жизнь и их секреты кому-то интересны и важны.
Не забудьте шапочки надеть
vassabi
не, у меня 6 букв в пароле - только от мусорных аккаунтов :)
но действительно, прогресс не стоит на месте - раньше брутфорс 32 бит считались помедленнее %)
MoscowBrownBear
Товарищи, просветите, пожалуйста, вот все говорят о брутфорсе коротких паролей, но не уж то в ПО которое даёт доступ по паролю не делают, что то вроде ограничения на частоту ввода пароля, типа не чаще чем один раз в 2 секунды?
Sazonov
Если получилось стырить зашифрованные таким паролем данные - то всё будет разруливаться именно брутфорсом
vassabi
вы же понимаете, что это ограничение ПО, а не ограничение формулы?
Если вы не пытаетесь взломать удаленный чужой сервер, то никаких ограничений, чтобы взять исходные данные и вычислять формулу самостоятельно и параллельно - перед вами нет (ибо все нужные библиотеки доступны вместе с исходниками)
MoscowBrownBear
Нет, не понимал, теперь понял (я думал речь про подбор пароля путем его ввода, теперь понял что речь про вычисление формулы имея начальные значения и конечные). Спасибо!
lovermann
Ломается обычно не напрямую, стучась на сервер, а имея у себя, например, хеш пароля, который потом ломается на локалке.
anwender95
Я перешел на генерацию паролей по советам xkcd:
https://xkpasswd.net/s/
Выучил пароль из 6 слов с разделителем в виде дефиса и не забывается.
ssj100
Аналогично, Сестра долго смеялась когда надо было дать доступ к моей почте
Elmot
сорок тысяч обезьян?
Odinokij_Kot
и волшебный банан =)
ssj100
Ot_topotа_3_kobil_pili_po_poliu_letit
тоесть при придумывании не забудьте: цифру и заглавные буквы. Чтоб успокоить валидатор
baldr
We are sorry, but this password is already used on another website by user vasya95. Please make up another password.
ssj100
Меня больше бесит:
Ot_topotа_3_kobil_pili_po_poliu_letit
Password incorect
Ot_topotа_3_kobil_pili_po_poliu_letit
Password incorect
Ot_topotа_3_kobil_pili_po_poliu_letit
Password incorect
Change password
Enter new password need more 8 symbols, digit and uppercase
Ot_topotа_3_kobil_pili_po_poliu_letit
Новый пароль не может совпадать с текущим
O_o аааааааа
MaximRV
https://3dnews.ru/1075932/publikatsiya-1075932
Rebryk Автор
Должно все-таки было быть 2^64.
+ все-таки это все надо на видюхе делать, иначе будет долго