Как получить приватный ключ от Bitcoin Cash кошелька Роджера Вера

0
ПОДЕЛИТЬСЯ

Как получить приватный ключ от Bitcoin Cash кошелька Роджера Вера

Вместо предисловия к этой статье я хочу заявить, что не знаком лично ни с самим Роджером Вером, ни с журналистами, записавшими это интервью. Каждый, у кого был доступ к видео, мог узнать приватный ключ. Я мог бы назвать этот пост просто «Какие классные все эти QR-коды и как мне удалось восстановить QR-код из мелкого фрагмента». Но гораздо интереснее, когда QR-код является ключом к Bitcoin Cash кошельку с BCH на $1 000.

Биткойн, Эфир, Litecoin, Dash, Neo… Криптовалюты пришли в нашу жизнь и продолжают быстро в ней обосновываться. Я слежу за биткойном с 2013 (следить не значит покупать). Я три раза прочитал Mastering Bitcoin чтобы понять как всё это работает и быть в состоянии популярно объяснить это кому угодно. Но тем не менее, рынок развивается так стремительно, что я не успеваю за всем следить. Новые криптовалюты, новые форки, новые ICO… Все это происходит буквально везде и всюду, каждый день.

Начать пользоваться криптовалютами просто – достаточно найти онлайн-инструкцию и следовать ей. Загрузите любое приложение-кошелек, сгенерируйте пару произвольных ключей, купите крипту на первой попавшейся бирже… Но настоящий опыт с сфере криптовалют невозможно получить так быстро, он стоит очень дорого.

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

 

Первое правило Крипто-клуба: никому не давай свой приватный ключ.

 

Самая ценная вещь для держателя криптовалют – его приватный ключ. Все просто: потерял ключ — потерял деньги. Кто-то узнал твой приватный ключ – ты тоже теряешь деньги.

В своей статье я расскажу и пошагово покажу как я сумел восстановить приватный ключ от кошелька с криптовалютой на $1000. Это кошелек был создан Роджером Вером специально для французской телепрограммы “Complément d’enquête”, но его номер был показан в «заблюренном» виде.

Еще одна прелюдия

Не так давно канал France 2 показал документальный фильм про биткойн. Для фильма они взяли интервью у @rogerkver, который решил подарить $1 000 телезрителю, который быстрее всех сможет добраться до кошелька. Но QR-код и приватный ключ от него были «заблюрены» сотрудниками France 2 при монтаже видео.

Вот та часть документального фильма, где Роджер Вер дает адрес кошелька.

№1 «Заблюренный» QR-код и ниже строка с приватным ключом

Я видел несколько возмущенных комментариев по этому поводу в Twitter. Некоторые даже обвиняли France 2 в том, что они решили оставить деньги себе. Это не так. France 2 пришлось «заблюрить» ключ не потому, что они захотели присвоить 1 000 долларов, а потому, что следовали букве закона.

Можно попытаться считать и раскодировать QR-код из видео, но он «заблюрен» так, что вам не удастся это сделать ни одним из доступных приложений. На этом история о $1 000 могла бы закончиться. Деньги пропали бы навсегда, поскольку Роджер вряд ли сохранил копию приватного ключа (разумеется их еще могли забрать себе записавшие интервью журналисты).

Но ближе к самому концу интервью на экране был четко виден один маленький кусочек QR-кода. Показали ли они его специально, зная, что иначе $1 000 пропадут? Или это просто одна из тех ошибок, которые может допустить неопытный пользователь криптовалют?

№2 Четко видимая часть QR кода. Ниже – «заблюренный» приватный ключ.

Скриншот этого QR кода мне прислал мой друг @clementstorck. Мы решили немного «поколдовать» над ним, чтобы понять сможем ли мы подобрать приватный ключ к кошельку, имея в своем распоряжении столь малый объем информации.

Честно говоря, шансы подобрать ключ перебором (brute force) были близки к нулю. Мы знали, что QR-коды хорошо защищены от повреждений. Нашей целью было найти как можно больше информации, чтобы максимально сократить количество неизвестных параметров. После описанных ниже шагов, нам осталось подобрать искомую комбинацию из всего 2 097 152 возможных вариантов.

Итак, с чего начать? Вот предпринятые нами шаги:

  • Сбор информации
  • Увеличиваем! Анализ изображения
  • Стандарт оформления QR-кода. Часть 1
  • Реконструкция QR-кода
  • Стандарт оформления QR-кода. Часть 2
  • Раскодирование QR-кода
  • Код с коррекцией ошибок
  • Python & подбор перебором (brute force)

1 — Сбор информации

На первом этапе мы попытались «выжать» из видео как можно больше информации. Мы просмотрели интервью кадр за кадром и сделали несколько скриншотов:

Открытый ключ, который привел нас к (почти) пустому BTC кошельку. Неужели Роджер Вер соврал? Именно так решили многие пользователи Twitter. Он не врал. Вот его твит. Нужно было искать BCH кошелек.

№3 Открытый ключ и QR код: 17Qgadvc7pm51mV9r9zUAs4xU1XXwDRr8o

«Заблюренная» часть приватного ключа. Мы исследуем её на этапе Анализа изображения, чтобы получить первые 6 символов. Код с коррекцией ошибок даст нам следующие 7.

№4 «Заблюренная» часть приватного ключа. Можно прочитать некоторые символы, но все нечётко.

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

№5 Последняя буква приватного ключа. Четкая “V”

Скриншоты верхней и левой части QR-кода также пригодятся. Не смотря на плохое качество, они дадут довольно много полезной информации на стадии завершения реконструкции QR-кода.

№6 Можно расшифровать верхний первый ряд QR-кода.
№ 7 Серьезно? Левая сторона QR-кода, первые две колонки можно (частично) расшифровать.

Инструмент, которым Вер пользовался для создания открытого и приватного ключа – Single Wallet на Bitcoin.com. Это дает нам кое-какую информацию о данных, зашифрованных в QR-коде: ключ длиной в 52 символа формата Wallet Import, похожий на этот:

KwjiU4CVAmdyxyDbvkbx2XbSoU1nxZgyXz7usqAemvsd4RdGHoPF

Следующий шаг – воссоздание QR-кода.

2 — Давайте увеличим! Анализ изображения

Ok, у нас есть меньше 1/3 QR-кода и мы по-прежнему очень далеки от расшифровки приватного ключа. Но что ещё можно узнать из полученных скриншотов?

Мы решили хорошенько рассмотреть 2 скриншота. На первом из них «заблюренный» QR-код приватного ключа. Мы решили узнать смогут ли приложения для чтения QR-кодов прочитать его после небольшой обработки.

Второй скриншот, над которым мы решили поработать – тот, на котором был приватный ключ. Чтобы сработал код с исправлением ошибок, нужно было получить хотя бы небольшую часть информации.

Мы решили послать скриншоты нашим экспертам. И получили хорошие результаты 🙂

Так и не смог решить, какая из реплик моя самая любимая.

А Вот что у нас получилось после небольшого «разблюривания».

«Разблюренная» версия QR-кода по-прежнему не читалась приложениями. Мы решили всё же попытаться его прочитать, потому что этот чувак проводил ряд крэш-тестов с QR-кодами и, судя по комментариям, все они оказались сканируемыми.

№8 Но у нас не получилось ничего кроме этой картинки. Только подтверждение последней буквы.

Две версии «разблюренного» приватного ключа. Первая дает нам первые четыре символа (мы не можем четко увидеть “K”), а вторая – первые шесть символов (мы не можем четко увидеть “z”).

№ 9 Нечетко, но можно различить “?yUz”
№10 Немного четче. Можно прочитать до 6 символа “KyU?sR”.

Эта информация пригодится нам на следующих этапах. Пока забудем про нее и сосредоточимся на QR-коде.

3 — Стандарт оформления QR-кода. Часть 1

Важной задачей было разобраться в том, как работают QR-коды и насколько можно восстановить поврежденный QR-код с помощью кода с коррекцией ошибок.

Статья в Википедии дала базовую информацию, но реально полезным оказался стандарт ISO/IEC 18004  (бесплатная версия его первого издания есть на Swisseduc). Мы также нашли в сети вот это сокровище.

№11  Область коррекции и маска для QR-кода были взяты с этого скриншота.

Прежде чем начать реконструировать QR-код давайте посмотрим что удастся узнать из этой картинки с помощью стандарта ISO и описания структуры QR-кода.

 

№12 Картинка из Wikimedia Commons

Нас интересовала синяя колонка (x:8, y:22–28).

Это часть строки данных форматирования (15-битовая последовательность. 5 бит данных и 10 бит коррекционного кода БЧХ). Биты расположенные в координатах (x:8, y:22–28) — это биты строки с 8 по 14. У нас было всего 7 из 15 битов, но их оказалось достаточно чтобы найти нужную информацию.

В строке данных форматирования закодированы уровень коррекции и узор маски, примененной в QR-коде. Есть 4 возможных уровня корректировки ошибок (L, M, Q, H) и 8 возможных узоров маски => 32 возможных строк сведений о форматировании.

Более детально о создании строк сведений можно прочитать на стр 76 стандарта (Приложение C — Информация о формате). Список 32 возможных вариантов можно найти здесь.

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

№13 Картинка из Wikimedia Commons

Сверху вниз у нас имеется биты с 8 по 14 строки сведений. Бит 14 самый важный. С его помощью мы можем теперь прочитать скриншот №11.

0011001XXXXXXXX

Заглянем в таблицу строк данных форматирования. Единственная совпадающая комбинация – с кодом уровня коррекци: H и узором маски: 3

№14 —  Картинка из Wikimedia Commons

Нам также было нужно найти формат кодировки QR-кода. Существует 5 видов форматов кодировки (в каждом используется особый метод конвертации текста в биты):

  • Цифровой (0–9)
  • Буквенно-цифровой (0–9; A-Z; девять других символов: пробел $ % * +- . / : )
  • 8-битный байт (JIS [японский промышленный стандарт] 8-битный набор символов. JIS X 0201 японская версия стандарта ISO 646)
  • Кандзи (символы Shift JIS [японская кодировка] могут кодировать каждый символ Кандзи на 2 байтах)
  • ECI (Интерпретация расширенного канала [Extended Channel Interpretation], когда вам требуется специальное/персонализированное кодирование)

Формат кодирования для нашего QR-кода 8-битный байт. Цифровой и буквенно-цифровой форматы не поддерживают буквы нижнего регистра, используемые в приватных ключах. Кандзи кодирует на 2 байтах (нам нужен всего один), а такой сложный формат как ECI в нашем случае явный перебор.

Мы почти готовы начинать реконструкцию QR-кода. Последнее что нам требуется узнать – его размер.

Существует 40 вариантов размера QR-кода (они называются версиями). Они варьируются в размере от 21×21 пикселей (Версия 1) до 177 x 177 пикселей (Версия 40). По мере возрастания порядкового номера версии размер кода вырастает на 4×4 пикселя. Каждая версия имеет максимальную емкость, зависящую от формата кодирования и уровня коррекции ошибок. Более детально см. стр. 28 стандарта ISO.

Мы знали, что наш QR-код должен содержать 52 символа (416 бит) с уровнем коррекции ошибок H.

№°15 — V6 самая маленькая версия, способная вмещать ключ размером 416 бит с уровнем коррекции H. V5 — слишком мала, V7 – слишком велика

Размер Версии 6 QR-кода 41×41 пикселей. Теперь у нас есть вся нужная информация для реконструкции QR-кода.

4 —реконструкция  QR-кода

Понятно, что нам предстоит восстановить QR-код размером 41×41 пикселей. Мы решили воспользоваться таблицей Google (в ней легко рисовать, выделять цветом и накладывать маску на QR-код).

Прошли следующие шаги:

  • Нарисовали каждый узор, входящий в стандарт (поисковые узоры, выравнивающий узор (в Версии 6 он всего один), полосы синхронизации и отступы (рамка) как показано на рис. №12)
  • Добавили биты из строки сведений о форматировании, найденные на предыдущем этапе.
  • Заполнили остальные блоки QR-кода по нашему скриншоту (рис. №11).

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

№16 —Тут мы собрали еще немного  битов из верхних рядов

 

№17 — Делаем то же самое с левой стороной QR-кода (повернуто на 90°)

Внизу QR-код, который удалось реконструировать. Следующий шаг – определить последовательность битов и выделить кодовые комбинации и кодовые комбинации коррекции ошибок.

№18 — Пошаговая реконструкция QR-кода

5 — Стандарт оформления QR-кода. Часть 2

Чтобы добыть из нашего QR-кода еще немного бит, нужно было научиться его читать.

Любой QR-код состоит из (кодовых слов) блоков данных и блоков коррекции. Каждый блок имеет размер 8 бит и представлен в виде модуля (черного или белого квадратика). Просто глядя на QR-код вы не сможете определить, означает ли какой-либо белый квадрат “0” или “1”, потому что, как мы увидим позже, маска накладывается на QR-код до того, как он проходит рендеринг (визуализацию).

  • Кодовые слова блоков данных несут в себе сообщение/данные, инкапсулированные в простой протокол, как показано ниже (более подробно на стр. 17 стандарта ISO):
  • Указатель режима: 4-битный индикатор, указывающий в каком режиме закодировано сообщение/последовательность данных.
  • Указатель числа символов: последовательность битов, указывающая длину сообщения. Варьируется в зависимости от режима кодирования и версии QR-кода.
  • Поток битов сообщения/данных (приватный ключ; 8 битов на символ)
  • Терминатор (символ конца строки): 4 бита, обозначающие конец строки битов, представляющих сообщение.
  • Биты-заполнители: используются для заполнения пустых мест в последовательности битов.
№19 — Последовательность битов содержала кодовые слова блока данных

Кодовые слова блока коррекции добавляются к последовательности кодовых слов блоков данных чтобы определить и скорректировать данные в случае ошибки (ошибок) или стирания. Это коды Рида-Соломона, генерируемые из кодовых слов блоков данных. Мы поговорим о них подробнее на этапе №7.

Число кодовых слов блоков данных и блоков коррекции варьируется в зависимости от версии и уровня коррекции. Они делятся на две группы (1 или 2) и на блоки (от 1 до 67) в зависимости от версии и уровня коррекции.

№20 — Характеристики коррекции ошибок для версии 6 (стр. 35 стандарта ISO)

В нашем случае (Версия 6, Уровень коррекции H), получается 15 кодовых слов блока данных и 28 кодовых слов блока коррекции на блок. QR-код будет содержать в себе 1 группу из 4 блоков для 172 кодовых слов.

№21 —  блоки кодовых слов данных. Каждое кодовое слово имеет длину в 8 битов. Они содержат часть потока битов с рис. № 19

 

№ 22 — блоки кодовых слов коррекции. Каждое кодовое слово из 8 битов кода Рида-Соломона взятых из блоков данных

6 — Раскодирование QR-кода

Следующий этап – чтение QR-кода и заполнение его как можно большим объемом кодовых слов данных и коррекции из таблицы, показанной на этапе №5.

Первый шаг – снятие маски с QR-кода. Мы пользовались таблицей Google для создания маски и функцией BITXOR для её нанесения.

№°23 — Когда маска накладывается на QR-код, каждый зеленый модуль маски меняет цвет модуля на противоположный

Результат наложения маски – читаемый QR-код. С чего начать чтение QR-кода и как его читать? В стандарте ISO объяснено как кодовые слова отображаются на QR-коде и приведены правила их чтения (стр. 46: Codeword placement in the matrix).

Давайте перенесем кодовые слова на наш QR-код.

№24 —Позиции кодовых слов данных и коррекции. Видны символы правильной и неправильной формы

Давайте их прочитаем. Каждый символ должен читаться по-разному в зависимости от его формы и направления написания, как показано ниже и как объясняется на стр. 47 стандарта ISO.

№25 — картинка из Wikimedia Commons

На картинке ниже – поэлементная (побитная) схема читабельного QR-кода. Каждый “X” – неизвестный бит.

№26 — Декодирование QR-кода «вручную», побитно. Весело, правда?

Теперь читаем и заполняем таблицы кодов данных и коррекции из этапа №4.

№27 —К кодовым словам данных после прочтения QR-кода и заполнения битов протокола добавляем данные, которые мы извлекли при анализе скриншотов

Кодовые слова #1 и #2 известны, поскольку они часть протокола(Указатель режима + Указатель числа символов).

Кодовые слова #3, #4, #6 и #7 известны из анализа скриншотов на этапе №2 (“KyUzsR”)

Кодовые слова с #54 по #60 также известны, поскольку они часть протокола (Терминатор + Биты-заполнители).

Каждый найденный “X” увеличивает шансы на успешное завершение фазы коррекции ошибок и вдвое уменьшает число вариантов для подбора перебором, который мы применим в конце пути.

Наверное, вы уже задали себе вопрос почему каждый пятый бит кодовых слов, несущих сообщение/данные, мы установили в “0”? Это сделано потому, что мы знаем алфавит приватного ключа (Base58Check) и все символы этого алфавита начинаются с “0” если кодируются в 8-битном формате (5-й бит каждого кодового слова становятся первым битом каждой буквы сообщения в результате сдвига, произошедшего из-за битов первых 12 протоколов).

№28 — Таблица кодовых слов кодов коррекции ошибок после того, как мы прочли QR-код. Тут мы ничего не можем сделать, поскольку все они определяются кодировщиком Рида-Соломона

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

7 — Код коррекции ошибок

На этом этапе мы по-прежнему далеки от того, чтобы полностью воспроизвести приватный ключ. Но уже скоро мы выясним достаточно ли нам собранных данных, чтобы его восстановить с помощью кода коррекции ошибок (ККО).

ККО — это техника кодирования, позволяющая вести надежную коммуникацию по ненадежным каналам. С их помощью можно реконструировать исходные данные выявив и скорректировав ошибки и нечитаемые участки.

В QR-кодах применяются коды Рида-соломона (подтип кодов Боуза-Чоудхури-Хоквингема, которые мы видели, когда на этапе №3 расшифровывали цепочку данных о форматировании).

Мы не будем детально объяснять как пользоваться кодами Рида-Соломона. Об этом много и подробно написано на многих ресурсах. Если кратко, то:

Кодировщик Рида-Соломона выдает кодовые слова ККО. Они — остаток при делении многочлена, представляющего сообщение и неприводимый многочлен генератор.

№29 — неприводимый многочлен генератор для 28 коррекционных кодовых слов

Декодер Рида-Соломона устроен немного сложнее из-за того, что есть множество различных способов раскодировать сообщение. Для этого существуют различные алгоритмы раскодирования. Более подробно о процессе декодирования тут: https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders

Декодер Рида-Соломона способен одновременно исправлять нечитаемые данные и ошибки. Но его возможностям есть предел – граница Синглтона.

В нашем случае риск заключался в попадании за предел этой границы максимально возможной мощности кода. Рид-Соломон – оптимальная система прямого исправления ошибок и она «уязвима» для этого порогового эффекта. Это значит, что если вы превысили максимальную мощность кода, вы не можете применять коды коррекции. То есть пришло время подбора перебором.

Предел мощности кода (число ошибок и пропусков, которые возможно исправить) определяется представленной ниже формулой, как указано на стр 33 стандарта ISO:

e + 2*t ≤ d — p

Где:

  • e : количество пропусков (нечитаемых данных);
  • t : количество ошибок;
  • d : количество кодовых слов коррекции ошибок;
  • p : количество кодовых слов защищающих от неправильного раскодирования (0 в нашем случае: 6-H).

Эта формула означает, что вы можете корректировать до 14 ошибок или 28 пропусков на каждый блок (или комбинацию из ошибок и пропусков общим числом не более 28). Мы воспользовались тем, что мы знали где в QR-коды были пропуски, чтобы применить самый высокий уровень коррекции (28 кодовых слов на блок).

Давайте посмотрим превышается ли предел мощности кода в каждом из блоков:

  • Блок 1: Данные содержат 6 пропусков, ККО содержит 22 пропуска;
  • Блок 2: Данные содержат 12 пропусков, ККО содержит 21 пропуск;
  • Блок 3: Данные содержат 10 пропусков, ККО содержит 18 пропусков;
  • Блок 4: Данные содержат 6 пропусков, ККО содержит 21 пропуск.

С 28-мью пропусками блоки 1 и 3 не превышают лимит мощности и будут полностью восстановлены. То же справедливо и для блока 4, где всего 27 пропусков.

Единственный блок, превышающий лимит мощности кода – блок 2 с 33 пропусками. Его нам придется подбирать с помощью перебора. К счастью, мы уже сократили до минимума количество комбинаций.

8 — Python & подбор перебором (brute force)

Для расшифровки сообщения мы решили использовать кодер/декодер Рида Соломона на Python.

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

Давайте начнем с самого оптимистичного сценария, в котором мы не превысили предел мощности и расшифровали блоки 3, 4 и 1.

№30 — Расшифровка блока 3 с помощью декодера Рида-Соломона

Результат декодировки блока 3:

[115, 22, 181, 6, 151, 103, 118, 229, 22, 133, 167, 39, 101, 164, 87]

Тот же процесс применяем для блока 4, но меняем значение непрочитанных участков, переменных ошибочных позиций и коррекционных кодовых слов. Получаем:

[118, 132, 183, 38, 36, 99, 116, 53, 96, 236, 17, 236, 17, 236, 17]

Результат декодера для блока 1:

[67, 68, 183, 149, 87, 167, 53, 39, 86, 71, 4, 230, 180, 196, 182]

Пока всё хорошо. К сожалению, если мы попробуем сделать то же с блоком 2, декодер не справится с заданием, потому что мы превысили предел мощности кода.

Единственное решение – подбор перебором. У нас имеется 5 «лишних» пропусков (33 вместо 28). Поэтому наша цель — восстановить (подобрать) 5 кодовых слов и посмотреть какой результат нам выдаст декодер.

Чтобы сократить число вариантов, ищем в таблицах №27 и №28 байты с меньшим числом неизвестных битов. Кодовые слова данных #17, #19, #20, #27 и кодовое слово коррекции ошибок #50 выглядят перспективно.

21 неизвестных битов дают в общем 2²¹ комбинаций (2 097 152). Не слишком-то и много! Ниже показан псевдокод для подбора перебором.

№31 — Подбор блока 2 дает нам последние нужные биты

Мой i5–6600K CPU показывает вычислительную мощность около 30 000 ключей в минуту на одном ядре. Подбор первой комбинации, подходящей для реконструкции приватного ключа (всего из 2 097 152 комбинаций нашим фильтрам соответствовали 2 варианта) занял 30 минут (838 849 попыток).

№32 — Подбор комбинаций для блока 2

Результат для блока 2:

[85, 99, 35, 131, 19, 84, 181, 99, 148, 87, 165, 38, 99, 116, 84]

Теперь у нас есть все кодовые слова. Следующий шаг — переводим эти слова в двоичную систему, заполняем таблицу №27, сокращаем первые 12 бит и последние 52 бита, раскодируем — и voilà!

Финальный результат – приватный ключ:

KyUzsRudpNkLKeV2815KV9EzRf7EG1kPivwnQhZrvZEwhKrbF7CV

Разумеется, вам не стоит пользоваться этим приватным ключом, просто потому что он уже не конфиденциален.

Восстановленный QR-код!

Роджер, спасибо за подарок! Процесс добычи этих «халявных» BCH оказался не так прост, как показывали по телевидению, но преодолевать трудности было весело!

 

Источник

ОСТАВЬТЕ ОТВЕТ

Please enter your comment!
Please enter your name here