Математика из предыдущего урока никогда не подводила. Что подводит, с удручающей регулярностью, так это случайный выбор третьей строки — и когда он подводит, частный ключ выводится в четырех строках алгебры, которые может понять любой старшеклассник.
Предположим, что две подписи сделаны с одним и тем же ключом и одним и тем же nonce k, но для разных сообщений. Поскольку r — это координата x точки k, умноженной на G, а k одинаково, то r у обеих подписей идентично — и это видно в блокчейне бесплатно для любого, кто смотрит.
Запишите обе: s1 — это обратное k, умноженное на сумму z1 и r, умноженное на d; s2 — это обратное k, умноженное на сумму z2 и r, умноженное на d. Вычтите одно из другого. Члены с r, умноженные на d, сокращаются, потому что они идентичны, и остается, что s1 минус s2 — это обратное k, умноженное на z1 минус z2. Изолируйте: k равно z1 минус z2, деленное на s1 минус s2. Имея k в руках, вернитесь к первому уравнению и изолируйте d, которое равно s1, умноженное на k минус z1, деленное на r.
Готово. Два вычитания, два деления, и частный ключ на экране. Нет грубой силы, нет таблицы, нет специального оборудования — и нет защиты после факта, потому что обе подписи уже опубликованы, и никто их не удалит.
Первый известный случай произошел не в Bitcoin. 27 декабря 2010 года на конгрессе Chaos Computer Club в Берлине группа fail0verflow показала, что Sony подписывала программное обеспечение PlayStation 3, всегда используя одно и то же k — постоянное значение, записанное в коде. Двух любых подписей было достаточно. Ключ, который авторизовал всё программное обеспечение консоли, был выведен публично, на сцене.
В Bitcoin эквивалентная катастрофа произошла в августе 2013 года. Ошибка в генераторе случайных чисел Android заставляла приложения получать одно и то же начальное значение случайности, и кошельки, подписывающие более одной транзакции, повторяли nonces без каких-либо признаков проблемы. 11 августа сайт bitcoin.org опубликовал предупреждение. Те, кто сканировал блокчейн в поисках повторяющихся значений r, уже опустошили затронутые адреса.
И проблема не является исторической. Исследователи, которые проходят весь блокчейн в поисках повторяющихся r, продолжают находить случаи, почти всегда связанные с самодельными кошельками и импровизированными программами.
Защита элегантна и является стандартом с 2013 года: прекратить случайный выбор. Стандарт RFC 6979 описывает, как выводить k детерминированным образом, применяя HMAC к частному ключу и хешу сообщения. k остается непредсказуемым для внешних наблюдателей, потому что зависит от частного ключа, но больше не зависит от качества генератора случайных чисел машины. Один и тот же ключ, подписывающий одно и то же сообщение, всегда производит одинаковую подпись — что, помимо безопасности, удобно для тестирования.
Существует еще более тонкая версия той же проблемы, и она достаточно красива, чтобы заслужить последний абзац. Не нужно повторять весь nonce. Достаточно, чтобы он немного утек — например, чтобы первые биты были предсказуемы, потому что генератор смещен. Каждая подпись тогда выдает кусочек информации. Собрав несколько сотен таких кусочков, техника уменьшения решеток восстанавливает весь частный ключ из этих кусочков, даже если ни один nonce никогда не повторялся.
Обратите внимание на то, что объединяет все эти взломы: ни один из них не атаковал кривую. secp256k1 остается нетронутой, дискретный логарифм остается нерешенным, и всегда падал плохо написанный кусок кода или дефектный генератор.
Существует, однако, целая семья атак, которые идут прямо к математике — не потому, что считают ее слабой, а потому, что выбирают интервалы, в которых квадратный корень пространства перестает быть пугающим. Это делает вызовы блокчейна возможными, и это тема следующего модуля.