История про то, как секретный ключ для Bitcoin’a в виде QR-кода восстановили из размазанной картинки
Мы могли бы просто назвать этот пост «Насколько хорош QR-код и как мы его восстановили практически из ничего». Но гораздо интереснее, когда QR-код является ключом к кошельку на сумму $1000 в битках.
Где обращаются деньги — там особо строгие требования к безопасности.
Мы в компании EDISON часто занимаемся разработкой систем электронных платежей. У нас были и службы такси и услуги ЖКХ и мобильные операторы и интернет-провайдеры и онлайн-лотереи. И, конечно, несть числа внедрённым системам оплаты на продающих сайтах.
Для обеспечения безопасности при разработке и интеграции систем платежей наши программисты используют различные продвинутые алгоритмы шифрования.
Часть документального фильма, где Roger Ver рассказывает про кошельки Биткойн.
Прежде чем мы начнем я отвечу: мы не знаем журналистов, которые записали интервью, и мы не знаем Роджера Вер. Любой, кто имел доступ к этому видео, мог получить секретный ключ.
Bitcoin, Ethereum, Litecoin, Dash, Neo…
Криптовалюты повсюду и быстро развиваются. Что касается меня, я наблюдаю за биткойном с 2013 (но не значит, что покупаю). Пришлось прочитать 3 раза «Mastering Bitcoin», чтобы понять, как действительно функционирует каждая его часть и иметь возможность объяснить это другим. Все же я не могу идти в ногу с современным рынком, новые криптовалюты, алгоритмы, новые ICO-повсюды и появляются каждый день.
Легко начать использовать криптовалюту, следуя учебным пособиям в сети Интернет. Вы просто загружаете любое приложение-кошелек, создаете пару ключей и покупаете криптовалюту на одном из обменников, но в то же время кривая изучения криптовалют довольно сложная.
И если вы не до конца понимаете как функционирует каждая часть в этом механизме вам следует избегать работы с криптовалютой, в противном случае вы рискуете потерять свои деньги, попав в одну из многочисленных ловушек. Одна из них, сохранение своего секретного ключа в безопасности, что является темой этого поста.
Основное правило «Криптографического клуба»: не делиться своим секретным ключом с другими.
Самое важное, что у вас есть при работе с криптовалютой — это ваш секретный ключ безопасности. Если вы его потеряли, можно сказать вы потеряли свои деньги. Если кто-то получит доступ к вашему ключу безопасности, вы также потеряете свои деньги. Все просто.
На реальном примере мы покажем вам как шаг за шагом мы восстановили секретный ключ 1000$ биткойн-кошелька созданного @rogerkver для французскоко телешоу “Complément d’enquête”, хотя он был замазан.
Введение
На прошлой неделе Франция 2 транслировала документальный фильм о биткойне. Они взяли интервью у @rogerkver, который решил предложить 1000 долларов в Биткойнах для самого быстрого зрителя. К сожалению, QR-код и секретный ключ были замазаны Францией 2.
Рис 1. Трудноразличимый QR код и секретный ключ.
Я видел, как несколько человек жаловались на это в Twitter, а некоторые даже оставляли твиты, утверждающие, что “Франция 2” решила сохранить Биткойны себе. Это ошибочное предположение, “Франция 2” закрыла QR код не по тому, что хотела зажать Биткойны, а потому что была юридически обязана.
Вы можете попробовать просканировать QR код столькими приложениями, сколькими сможете но у вас не получится его расшифровать из за сильной размытости.
История могла закончится на этом моменте, 1000$ были бы утеряны безвозвратно, поскольку я не думаю, что Роджер Верт держал копию секретного ключа. Только журналисты, записывающие интервью, смогли бы выкупить биткойны.
Но, в самом конце интервью, они показали небольшую часть QR-кода. Делали ли они это специально, зная, что 1000 долларов будут потеряны, если никто не сможет найти секретный ключ? Или это была одна из ошибок, которую вы можете допустить, начиная использовать криптовалюту?
Рис 2. Открытая часть QR кода и замазанная строка с ключом ниже.
Я собирался написать моему другу @clementstorck когда я получил скриншот QR кода, который он взял. Мы решили работать, с целью узнать, можно ли получить секретный ключ, имея такой маленький объем информации.
Будем честны, шансы найти секретный ключ с помощью только грубого перебора были близки к нулю. Мы знали свойства QR-кодов и их устойчивость к повреждениям. Наша цель состояла в том, чтобы собрать как можно больше информации, насколько это возможно, дабы сократить количество неизвестных параметров до минимума. Мы знали, что на каком то шагу, прибегнем к перебору. После всех шагов, приведенных ниже, нам нужно было перебрать всего 2 097 152 комбинации =).
Итак, с чего мы начнем? Ниже, все шаги, которые мы сделали, чтобы получить секретный ключ.
- Сбор информации
- Давайте пошаманим. Обработка изображений.
- Стандарт QR кода, часть 1
- Реконструкция QR-кода
- Стандарт QR кода, часть 2
- Декодирование QR-кода
- Код коррекции ошибок
- Брут на Python
1.Сбор информации
Первым шагом было собрать как можно больше информации из интервью. Мы наблюдали за воспроизведением покадрово и получили несколько снимков, таких как:
Открытый ключ, который ведет нас к (почти) пустому кошельку BTC. Роджер Вер лгал? Многие люди говорили об этом в Twitter. Он не лгал, в его твиттере размещена запись, где он говорил о распродаже. Нам пришлось искать BCH кошелек.
Рис 3. Публичный ключ и QR-код: 17Qgadvc7pm51mV9r9zUAs4xU1XXwDRr8o
Размытая часть строки с ключом доступа. Мы будем использовать ее на этапе анализа изображения, чтобы получить первые 6 букв. Шаг с кодом коррекции ошибок даст нам следующие 7 букв.
Рис 4. Замазанная часть строки с секретным ключом. Вы можете разглядеть несколько слов но в основном картинка не четкая.
Последняя буква секретного ключа, так же будет полезна для для разблокировки 8ми крайних символов ключа.
Рис 5. Последняя буква хорошо различима V.
Скрины плохого качества сверху и снизу QR кода. Они также будут полезны, чтобы получить (немного) больше данных и заполнить QR-код на этапе восстановления.
Рис 6. Верхняя часть QR-кода, первая строка может быть использована.
Рис 7. Чё, серьезно?? Левая часть QR-кода, первые два столбца, также могут быть (частично) использованы.
Инструментом, который он использовал для создания публичного и секретного ключей, является инструмент Single Wallet на Bitcoin.com. Это дало нам информацию о данных внутри QR-кода: 32 сивольный ключ биткойн кошелька аналогичный этому.
KwjiU4CVAmdyxyDbvkbx2XbSoU1nxZgyXz7usqAemvsd4RdGHoPF
Следующий шаг — это воссоздать QR-код.
2. Пошаманим. Обработка изображений
Хорошо, на данном этапе мы имеем менее 1/3 QR-кода, мы все еще далеки от секретного ключа. Что мы можем узнать из добытых скриншотов?
Мы решили сосредоточиться на 2 скриншотах, первый — это размытый QR-код секретного ключа, мы хотели знать, смогут ли приложения QR-кода читать его после обработки.
Второй скриншот, над которым мы хотели работать имел небольшую часть секретного ключа. Мы знали, что нам нужно иметь хотя бы небольшой объем данных, если мы хотим, чтобы код ECC (Error Correction Code) работал.
Мы решили отправить скриншоты нашим экспертам. С большим количеством результатов :)
Вот что мы получили после частичного снятия эффекта размытия.
Версия QR-кода после обработки, так же не была декодирована ни одним из приложений для чтения QR кода. Мы решили попробовать, потому что этот парень провел некоторые тесты на QR-кодах, и в комментариях подтвердил что они сканируемые
Рис 8. Мы ничего не нашли на этой фотографии. Только подтверждение последней буквы.
Две неразмытые версии строки секретного ключа. Первый дает нам первые четыре буквы (мы явно не видим «К»), а второй — первые шесть букв (мы не видим «z»).
Рис 9. Фотография не четкая, но вы можете видеть “yUz”.
Рис 10. Можно прочитать первые 6 символов “KyU?sR”
Оставим эту информацию на потом. Она поможет нам восполнить несколько бит позднее.
3.Стандарт QR кода, часть 1
Было важно понять, как работают QR-коды и ограничения их возможностей ECC в восстановлении поврежденного QR-кода.
Википедия — хорошее начало, но все, что нам нужно, было в стандарте ISO / IEC 18004 (есть бесплатная версия первого издания на Swisseduc). Мы также нашли это сокровище онлайн.
Рис 11. Error Correction Level и Маску QR-кода можно извлечь из этого скриншота.
Прежде чем мы начнем реконструировать QR-код, давайте посмотрим, что мы можем извлечь из этого изображения, используя стандарт ISO и структуру QR-кода.
Рис 12.
Интересной для нас была синий столбик (x: 8, y: 22-28).
Это часть информационной строки формата (15-битная последовательность, 5 бит данных и 10 бит исправления ошибок BCH). Биты, расположенные в (x: 8, y: 22-28), являются битами 8-14 строки. У нас было всего 7 бит из 15, но этого было достаточно, чтобы найти нужную нам информацию.
Строка информации формата кодирует уровень коррекции ошибок (EC) и шаблон маски, применяемый к QR-коду. Существует 4 возможных уровня EC (L, M, Q, H) и 8 возможных шаблонов маски => 32 возможных информационных формата информации.
Подробности о том, как создать информационную строку, можно найти на стр. 76 стандарта (Приложение C — Информация о формате). Список из 32 вариантов можно найти здесь.
Рис 13.
Сверху вниз. Мы имеем биты от 8 до 14 информационной строки. Бит 14 является самым значимым. На скриншоте № 11 мы можем его прочитать.
0011001XXXXXXXX
Быстрый поиск в таблице строк информации формата. Единственная комбинация, которая соответствует той, которая соответствует уровню ECC: И имеет маску: 3
Рис 14.
Нам также необходимо было найти формат кодирования QR-кода. Существует пять различных форматов кодирования (каждый из них использует свой метод для преобразования текста в биты):
- Числовой (0-9)
- Буквенно-цифровой (0-9; A-Z; девять других символов: пробел $% * + -. /:)
- 8-разрядный байт (набор символов JIS 8 бит. JIS X 0201 японская версия os ISO 646)
- Кандзи (символ JIS Shift, может кодировать каждый символ кандзи на 2 байта)
- ECI (Extended Channel Interpretation, если вам нужна специальная / пользовательская кодировка)
Формат кодирования QR-кода — это 8-разрядное число типа Byte, числовой и буквенно-числовой тип не поддерживаются алфавитом секретного ключа (без букв в нижнем регистре), Кандзи кодирует по 2 байта (нам нужно только один), а ECI — это перебор.
Мы были почти готовы начать реконструкцию QR-кода, последнее, что нам нужно было знать размер QR-кода.
Есть 40 разновидностей размеров QR-кода (называемые версиями). Они могут начинаться от 21x21 пикселей (версия 1) до 177x177 пикселей (версия 40). Они растут на 4x4 пикселей каждый раз, когда увеличивают свой номер версии. Каждая версия имеет максимальную емкость, основанную на формате кодирования и уровне исправления ошибок.
Емкость каждого QR-кода зависит от его версии и уровня исправления ошибок (error correction level). Подробности можно найти на странице 28 стандарта ISO.
Мы знали, что QR-код должен был хранить 52 символа (416 бит) с уровнем коррекции ошибок H.
Рис 15. V6 — самый маленький размер, который может удерживать 416-битный ключ с уровнем коррекции ошибок H. V5 слишком мал, V7 слишком большой.
Размер QR кода 6й версии 41x41px.
Теперь у нас была вся информация, необходимая для начала реконструкции QR-кода.
4. Реконструкция QR кода
Мы знаем, что нам пришлось восстановить QR-код размером 41x41 пиксель. Мы решили работать над электронной таблицей Google (где легко рисовать и применять такие функции, как маскирование QR-кода).
Мы выполнили следующие шаги:
- Нарисуйте каждый шаблон, который является частью стандарта (шаблон позиционирования, шаблон выравнивания (только один — из 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. Битовый поток, содержащий в кодовые слова данных.
Кодовые слова ECC (error-correcting code) добавляются в последовательность кодовых слов данных для обнаружения и исправления кодовых слов данных в случае ошибок или стираний. Это коды Reed-Solomon, созданные из кодовых слов данных. Мы поговорим немного подробнее о них на шаге 7.
Количество кодов данных и кодов коррекции ошибок (ECC) зависит от версии и уровня коррекции ошибок. Они разбиваются на группы (1 или 2) и на блоки (от 1 до 67) в зависимости от версии и уровня коррекции ошибок.
Рис. 20. Характеристики коррекции ошибок для версии 6 (стр. 35 стандарта ISO)
В нашем случае (версия 6, уровня H) у нас будет 15 кодовых слов данных и 28 кодовых слов ECC для каждого блока. QR-код будет содержать 1 группу из 4 блоков для всего 172 кодовых слов.
Рис. 21. Блоки кодов данных. Каждый Codeword имеет длину 8 бит. Они несут часть битового потока из рис 19.
Рис 22. Блоки ECC Codewords. Они представляют собой 8-битные коды Рида-Соломона, полученные из блоков данных.
6. Декодирование QR-кода
Следующий шаг состоял в том, чтобы прочитать QR-код и заполнить как можно больше таблицы кодовых слов данных и ECC с шага 5.
Первым шагом было демаскирировать(unmask) QR-код. Мы использовали электронную таблицу Google для создания маски и использовали функцию BITXOR для ее применения.
Рис 23. При применении к QR-коду каждый зеленый модуль маски инвертирует цвет модуля.
Результатом процесса маскирования является читаемый QR-код. Как читать QR-код и с чего начать? Стандарт ISO объясняет, как кодовые слова отображаются на QR-код и как их читать (стр. 46: Размещение кодового слова в матрице).
Давайте наложим кодовые слова на QR-код.
Рис 24. Позиция кодовых слов данных и кодов корректировки ошибок. Можно увидеть регулярные и нерегулярные символы.
Теперь давайте прочитаем каждый из них. Каждый символ должен считываться по-разному в зависимости от его формы и направления считывания, как показано ниже, и как описано на стр. 47 стандарта ISO.
Рис 25.
Ниже побитово прочитаный QR код, где каждый X-это неизвестный бит.
Рис 26. Декодирование вручную, один бит за раз. Выглядит забавно, правда?
Затем мы прочитали и заполнили таблицы данных и ECC с шага 4.
Рис 27. Кодовые слова данных после того, как мы прочитали QR-код, заполнили биты протокола и те, которые мы получили с помощью анализа изображений.
Кодовые слова №1 и №2 известны, поскольку они являются частью протокола (индикатор режима + индикатор количества символов).
Кодовые слова 3, 4, 6 и 7 известны на основе анализа изображений, которые мы сделали на шаге 2 («KyUzsR»)
Кодовые слова № 54 до № 60 также известны, поскольку они являются частью протокола (Terminator + Padding bits).
Каждый открытый «Х» увеличивает наши шансы на успех в ECC-фазе и разделяет на 2 количество возможностей, которые нам придется преодолевать в будущем.
Возможно, вам интересно, почему весь 5-й бит всех кодовых слов, несущих сообщение / данные, установлен на «0». Это потому, что мы знаем алфавит частного ключа (Base58Check), и все символы в этом алфавите начинаются с «0» при кодировании на 8 бит. (5-й бит в каждом кодовом слове — это первый бит каждой буквы сообщения из-за сдвига, введенного битами первого 12-го протокола).
Рис 28. таблица кодовых слов ECC после того, как мы прочитали QR-код. Здесь мы ничего не можем сделать, поскольку все они определяются декодером Reed-Solomon.
Давайте теперь воспользуемся магией кода исправления ошибок, чтобы восстановить как можно больше данных.
7. Код исправления ошибок
На этом этапе мы все еще были далеки от полного значения ключа, но вскоре мы смогли узнать, собрали ли мы достаточно данных для восстановления ключа, используя ECC.
ECC (Error Correction Code) — это технология, которая обеспечивает надежную связь по ненадежным каналам. Она может восстанавливать исходные данные, обнаруживая и исправляя ошибки и стирания.
QR-коды реализуют коды Рида-Соломона (подтип кода BCH, который мы видели при декодировании строки информации формата на шаге 3).
Мы не будем подробно объяснять, как кодировать или декодировать коды Рида-Соломона. В Интернете много хороших ресурсов, но если коротко:
Устройство кодирования Рида-Соломона создает кодовые слова ECC. Они являются остатком деления между многочленом, представляющим сообщение, и неприводимым генераторным многочленом.
Рис 29. Неприводимый генераторный многочлен для 28 кодовых слов EC
Декодер Рида-Соломона немного сложнее, потому что существует множество способов декодирования сообщения. Для этой задачи существуют различные алгоритмы декодирования, эта страница очень полезна для понимания процесса декодирования.
Декодер Рида-Соломона способен одновременно декодировать стирания и ошибки. К сожалению, существует предел, называемый Singleton Bound.
Риск, который у нас был, должен был превысить этот предел. Рид-Соломон является оптимальным FEC и «уязвим» к эффекту скалы (cliff effect). Это означает, что если вы превысили лимит, вы не можете получить ничего из кодов ЕС, и это то, где нам нужно было прибегнуть к брутфорсу.
Предел (количества исправлений и корректировки ошибок) определяется формулой ниже, как определено на стр. 33 стандарта ISO:
e + 2*t ≤ d — p
Где:
- e: количество исправлений
- t: количество ошибок
- d: количество кодовых слов с исправлением ошибок
- p: количество кодовых слов защиты от неправильного кодирования (0 в нашем случае: 6-H)
Эта формула означает, что вы можете исправить до 14 ошибок или 28 стираний на блок (или их сочетание, если сумма не превышает 28). Мы использовали тот факт, что мы знали, где были стирания на QR-коде, чтобы иметь самый высокий уровень исправления ошибок (28 кодовых слов на блок).
Давайте проверим каждый блок, если мы находимся ниже или выше предела:
- Блок 1: данные содержат 6 стираний, ECC содержит 22 стирания
- Блок 2: данные содержат 12 стираний, ECC содержит 21 стирание
- Блок 3: данные содержат 10 стираний, ECC содержит 18 стираний
- Блок 4: данные содержат 6 стираний, ECC содержит 21 стирание
С 28 стираниями блок 3 и блок 1 находятся на пределе, и может быть восстановлен на 100%. То же самое для блока 4, всего 27 стираний.
С 33 стираниями блок 2 находится выше предела, и нам придется прибегнуть к брутфорсу. К счастью, брутфорс будет сделан на небольшом количестве комбинаций.
8. Python и брутфорс
Мы решили использовать кодек Reed-Solomon на Python для декодирования сообщения.
Мы будем использовать сочетание кода Python и псевдокода, чтобы описать шаги, которые мы сделали, чтобы найти конечный результат.
Начнем с наилучшего сценария, когда мы ниже предела и декодируем блок 3, 4 и 1.
Рис 30. Блок декодирования 3 с использованием декодера Рида-Соломона.
Результат декодирования 3-го блока:
[115, 22, 181, 6, 151, 103, 118, 229, 22, 133, 167, 39, 101, 164, 87]
Тот же процесс для блока 4, просто измените значение переменных mess, ecc и error_pos. Результат:
[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 и EC-кодовое слово 50.
21 неизвестных бит в сумме дают 2²¹ (2 097 152) комбинаций. Не так много. Ниже псевдокод брутфорса.
Рис 31. Брутфорс второго блока дает нам последние необходимые биты.
Мой процессор i5-6600K смог вычислить около 30 000 ключей в минуту на одном ядре. Потребовалось 30 минут и 838 849 проб, чтобы найти первое решение, которое было подходящим для восстановления секретного ключа (из этих 2 097 152 комбинаций было всего 2 решения, которые соответствовали фильтрам).
Рис 32. Брутфорс блока 2.
Результат для второго блока:
[85, 99, 35, 131, 19, 84, 181, 99, 148, 87, 165, 38, 99, 116, 84]
Теперь у нас есть все кодовые слова, последний шаг — преобразовать все эти кодовые слова в двоичные, заполнить таблицу 27, обрезать первые 12 бит, последние 52 бита, декодировать и вуаля!
Конечным результатом является секретный ключ:
KyUzsRudpNkLKeV2815KV9EzRf7EG1kPivwnQhZrvZEwhKrbF7CV
Само собой разумеется, что вы не должны использовать этот секретный ключ, поскольку он больше не является актуальным!
QR код секретного ключа восстановлен.
Роджер, спасибо тебе за распродажу. Процесс выкупа BCH был не таким простым, как сканирование QR-кода на ТВ, но это было сложно и весело.
Перевод: Вячеслав Букатов
