20.08.2013

Случайности третьего сорта: как плохая рандомизация опустошила кошельки пользователей Android

Неделю назад Bitcoin-сообщество было растревожено серией наглых краж. Стало известно, что из нескольких кошельков, заведённых и используемых их владельцами на Android-устройствах, увели суммарно около полусотни BTC. В общем-то мелочь, ибо в переводе на доллары это примерно пять тысяч — ерунда на фоне многомиллионных ограблений, которыми нынче забавляются чёрные хакеры. Шум, однако, поднялся такой, что вмешаться в происходящее сочла необходимым даже Google. Причин тому несколько. Во-первых, мелкое воровство вскрыло фундаментальную недоработку в Android, поставившую под удар всех пользователей Bitcoin на этой платформе. Во-вторых, когда пыль улеглась, стало ясно, что пострадать могут и пользователи множества других Android-приложений, включая криптографические. Наконец, в-третьих, проблема не решена по сей день и в ближайшие годы будет висеть дамокловым мечом над андроидовской экосистемой.

Впрочем, давайте по порядку. Формальным началом этой истории стало появившееся 11 августа на сайте Bitcoin.org предупреждение: биткойновые кошельки, сгенерированные с помощью Android-приложений, небезопасны. Чтобы понять причину, не нужно быть специалистом по виртуальным деньгам: достаточно вспомнить основы так называемого асимметричного шифрования, называемого также шифрованием с открытым ключом. Основано оно на использовании двух длинных чисел, одно из которых («открытый ключ») доступно всем (с его помощью можно, например, зашифровать сообщение, отправляемое владельцу ключа), другое («секретный ключ») хранится в тайне, поскольку нужно для расшифровки, постановки цифровой подписи и прочих операций, право выполнять которые имеет только владелец ключа.

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

Тут-то и кроется проблема. Генераторы случайных чисел (ГСЧ), реализованные программно, на самом деле, конечно, выдают псевдослучайные последовательности: числа в таком ряду друг от друга не зависят, но сам ряд всегда одинаков. Чтобы каждый раз после включения компьютера не начинать с одного и того же места, приступая к работе, следует «крутануть рулетку» (инициализировать начальное состояние генератора, передав ему полученное каким-либо образом одно истинно случайное число). Так вот: оказалось, что ГСЧ в Android (конкретно — соответствующий компонент Java-машины) «рулетку» не крутил. И — хоть и не всегда — мог выдать одинаковые числа.

Так что злоумышленнику достаточно просмотреть все транзакции, сделанные владельцем конкретного кошелька, и, обнаружив хотя бы две с одинаковыми «случайными» подписями, вычислить секретный ключ. Если вас интересует математика, весь процесс (с опорой на open source-пакет Sage) подробно, ещё зимой, описал в своём блоге некто Нильс Шнайдер. Остаётся загадкой, почему Bitcoin-сообществу потребовалось полгода, чтобы оценить важность его открытия.

Ответ, впрочем, очевиден. Публика в массе своей имеет весьма смутные представления о стойкой криптографии и брезгует или боится заглядывать глубже пользовательского интерфейса. Вот и сейчас от внимания многих популярных ресурсов, написавших о происшествии, ускользнул важный нюанс: под угрозой опустошения находятся не только кошельки, сгенерированные Android-приложениями, но все биткойн-кошельки, которыми пользовались на Android-устройствах. (Ведь слабость не в ключах, а в подписях транзакций!) Так что если вы пересылали биткойны через Android, задумайтесь над обновлением софта и переводом средств в новый кошелёк.

Что касается таинственного вора, воспользовавшегося находкой Шнайдера (а может быть, обнаружившего проблему самостоятельно), он продолжает красть: последняя операция по его кошельку датирована вчерашним днём. И вообще говоря, пока в кошельках, скомпрометированных Android-транзакциями, остаются какие-то средства, кражи будут продолжаться, ведь в системе Bitcoin абсолютно все транзакции открыты. А вернуть деньги законным владельцам, естественно, не удастся, потому что откат транзакций в Bitcoin невозможен принципиально.

Но довольно о Bitcoin. Я предлагаю поменять действующих лиц. Вместо программ, работающих с биткойн-кошельками, пусть на сцену выйдут программы асимметричного шифрования документов — скажем, GPG или PGP. Вместо биткойн-транзакций будут текстовые сообщения, передаваемые от пользователя А к пользователю Б. Конечно, схема шифрования и подписи будет отличаться от реализованной в Bitcoin, но принцип останется тем же: мелкая недоработка в генераторе случайных чисел приведёт к катастрофическим последствиям для стойкости шифра (посторонний наблюдатель сможет восстановить секретный ключ и читать либо подделывать часть корреспонденции). И тут самое время вспомнить о подозрениях, высказанных недавно в связи с шумихой вокруг Эдварда Сноудена. Помните, как пару недель назад эксперты предположили, что в микропроцессорах Intel и AMD по инициативе АНБ организованы искусственные «слабые места»? Глядя на происходящее с Bitcoin на мобильных устройствах, легко представить, чем такие мелочи могут аукнуться.

Но и для Android история не завершена. Google отреагировала оперативно и уже разослала производителям устройств соответствующий патч для операционной системы. Так что в ближайшие недели и месяцы владельцы поддерживаемых Android-устройств, вероятно, его получат. Однако сотни миллионов пользователей сидят на мобильных устройствах, которые уже не поддерживаются и прошивки которых никогда не будут обновлены. Для них уязвимость ГСЧ останется навсегда. И хорошо, если разработчики прикладных программ, использующих ГСЧ, знают об уязвимости и самостоятельно позаботились о том, чтобы её обойти (как сделали авторы всех популярных мобильных Bitcoin-приложений). Но ведь останутся тысячи программ, создатели которых о проблеме и не подозревают.

Сотрудники Symantec не поленились оценить численность армии приложений, пользующихся ущербным ГСЧ в андроидовской Java. Это 360 тысяч программ, из которых только каждая девятая, обращаясь к ГСЧ, не ленится принудительно рандомизировать стартовую точку генератора, тогда как остальные надеются, что ГСЧ позаботится об этом сам. И хорошо, если программа, которой понадобились случайные числа, использует их, скажем, для расстановки виртуальных врагов на игровом поле. Вот только игрушек в списке Symantec всего 10 процентов...

Евгений Золотов

Источники:

1. computerra.ru