Как Sony потеряла главный ключ PS3: одно «случайное» число на все подписи
Если коротко: в 2010 году Sony потеряла главный ключ, которым подписывала программы для PlayStation 3, — и шифр тут ни при чём. Алгоритм подписи ECDSA требует для каждой подписи брать новое секретное случайное число. Sony использовала одно и то же число во всех подписях. Из двух таких подписей ключ вычисляется школьной алгеброй, без суперкомпьютеров и перебора. После этого любой мог подписать свою программу так, что приставка принимала её как родную.
Это канал «Всё про ИИ и Роботов». Сегодня у нас не нейросети, а история о том, как одна строчка кода обрушила защиту консоли, которую купили десятки миллионов человек. Поводом стал один из заметных материалов недели на Хабре: автор подробно пересказал, как Sony отобрала у PS3 Linux и через год лишилась ключей. Там вся хроника с судами и скандалами. Я же разберу саму механику: почему повторённое «случайное» число выдаёт ключ целиком и почему ту же ошибку потом совершали снова.
Предыстория: приставка, которая обещала стать компьютером
У первых PS3 в меню был пункт Other OS: на приставку можно было поставить Linux. Sony подавала это как достоинство, и на это купились не только энтузиасты. Процессор Cell неплохо справлялся с вычислениями, поэтому университеты собирали из приставок недорогие кластеры. Для компании у этого была обратная сторона. По версии автора Хабра, консоли продавались в убыток, а деньги отбивались на играх. Покупатель, который брал PS3 ради Linux, игр почти не покупал.
В сентябре 2009 года вышла облегчённая PS3 Slim, и пункта Other OS в ней уже не было. А в марте 2010-го Sony объявила, что уберёт его и со старых моделей. В официальном анонсе прошивки 3.21 в блоге PlayStation сказано прямо: обновление выходит 1 апреля 2010 года и отключает «Install Other OS» «из соображений безопасности». Формально прошивку можно было не ставить, но тогда приставка теряла вход в PlayStation Network, онлайн-игры и запуск новых дисков, которым нужна свежая система. То есть выбирать приходилось между Linux и всем остальным, за что человек заплатил.
Поводом стало то, что хакер Джордж Хотц (geohot) пробрался к гипервизору приставки как раз через режим Other OS. Sony закрыла дверь, убрав функцию, а дыру в самой системе латать не стала. Самыми обиженными оказались люди, которые умеют читать машинный код. Это и предопределило, что было дальше.
Зачем приставке цифровая подпись
Чтобы понять, что именно сломалось, нужно разобраться, как консоль отличает «свою» программу от чужой. Внутри работает асимметричная криптография. У Sony есть приватный ключ: это секретное число, которое хранится только у компании. В каждой приставке зашит соответствующий ему публичный ключ, которым можно проверить подпись, но нельзя её создать.
Каждую игру, обновление и системный модуль Sony подписывает приватным ключом. Перед запуском приставка проверяет подпись публичным ключом. Если подпись сходится, файл выпустила Sony и его никто не менял. Если нет, файл не запустится. Вся защита держится на одном допущении: приватный ключ знает только Sony. Если ключ утёк, любой может подписать что угодно, и приставка не отличит это от официальной прошивки.
Если идея пары ключей «закрытый у меня, открытый у всех» для вас новая, её же на бытовом примере мы разбирали в статье про SSH-ключи: устроено так же, только там вместо приставки сервер.
Как устроена подпись ECDSA и где у неё слабое место
Sony подписывала файлы алгоритмом ECDSA на эллиптических кривых. Формулы тут не нужны, хватит общей картины. Чтобы получить подпись, алгоритм берёт три вещи:
Приватный ключ → тот самый секрет Sony, одинаковый для всех подписей
Хеш файла → короткий «отпечаток» подписываемых данных, его знают все
Секретное число k → одноразовое случайное число, новое для каждой подписи
На выходе получается пара чисел, которую обычно называют r и s. Число r зависит только от k. Число s получается из k, хеша и приватного ключа. Публичный ключ позволяет проверить, что всё сходится, но вытащить из подписи секреты не даёт.
Главное здесь в числе k. Американский стандарт цифровой подписи NIST FIPS 186-5 требует генерировать новое секретное k перед каждой подписью и беречь его так же, как сам приватный ключ. Это не пожелание, а условие, без которого схема не работает.
Почему повтор k смертелен
Представьте, что подпись — это уравнение, в котором два неизвестных: ключ и k. Одна подпись — одно уравнение с двумя неизвестными. Решить его нельзя, вариантов бесконечно много. Если k каждый раз новое, вторая подпись добавляет ещё одно уравнение, но и ещё одно неизвестное. Неизвестных по-прежнему больше, чем уравнений, и ключ остаётся в безопасности.
А теперь возьмём одно и то же k в двух подписях. Получаем два уравнения и всего два неизвестных: ключ и k. Такую систему решит восьмиклассник. Вычитаем одно уравнение из другого, ключ сокращается, и остаётся k. Подставляем k обратно и получаем приватный ключ. Повтор к тому же сразу заметен со стороны: раз r зависит только от k, у двух подписей с одним k совпадёт первая половина. Атакующему даже не нужно гадать, повезло ли ему.
Ага-момент: «случайное» число, которое не менялось
29 декабря 2010 года на 27-м Chaos Communication Congress в Берлине группа fail0verflow выступила с докладом Console Hacking 2010. Его подзаголовок на слайдах — «PS3 Epic Fail». В записи доклада и на слайдах хакеры сначала объясняют ту же логику, что выше: «Случайное m обязательно для каждой подписи: из пары подписей с одинаковым m можно вычислить и m, и ключ» (в их обозначениях секретное число называется m, а приватный ключ — k).
Потом идёт слайд с подписью «Sony's ECDSA code» и примером того, как выглядит правильная генерация: прочитать 30 байт из системного источника случайности. Смысл шутки в том, что у Sony вместо этого стояла константа. Число, которое по стандарту обязано быть свежим и случайным для каждой подписи, у них было одним на все файлы. Зал вспомнил известный комикс xkcd, где функция «получить случайное число» всегда возвращает 4, «выбранное честным броском кубика».
Важно, что fail0verflow сам ключ не опубликовали, только показали метод. Но метод занимает пару строк. По хронологии из оригинальной статьи на Хабре, в начале января 2011 года Хотц выложил вычисленный ключ у себя на сайте и для наглядности приложил подписанную им программу Hello world. После этого приставки на тогдашних прошивках запускали любой подписанный код как официальный.
Миф: «хакеры взломали шифр Sony»
Так эту историю часто пересказывают, и это неверно. Математику ECDSA никто не ломал. Она так же надёжна, как и в 2010 году, и сегодня на подписях этого семейства работают HTTPS-сертификаты сайтов, подписи приложений и криптовалюты. Сломалась реализация. Инженеры выполнили все сложные шаги и пропустили простой — получение нового случайного числа.
Это типичный сценарий для криптографии. Стойкий алгоритм почти никогда не взламывают «в лоб», за перебор ключа длиной в сотни бит никто не берётся. Взламывают то, что вокруг: генератор случайных чисел, хранение ключа, проверку длины, порядок операций. Похожий сюжет был у Intel с Pentium: идеальная на бумаге схема деления и пять незаполненных ячеек в таблице.
Почему ключ нельзя было просто поменять
Казалось бы, ключ утёк — выпусти новый. Беда в том, что публичный ключ для проверки уже был зашит в десятки миллионов проданных приставок, а программы, подписанные старым ключом, разошлись по всему миру. Sony выпускала новые прошивки с другой схемой, но консоли на старых версиях оставались открытыми. По словам автора Хабра, в 2012 году утекли ещё и ключи самого нижнего загрузчика, который проверяет прошивку в железе и обновлением не меняется. После этого уже выпущенные PS3 остались открытыми навсегда.
Та же ошибка, другие жертвы
Если бы повтор k был единичным промахом одной компании, о нём бы давно забыли. Но через три года история повторилась с деньгами. В августе 2013-го Bitcoin.org предупредил владельцев кошельков на Android: компонент Android, отвечающий за генерацию безопасных случайных чисел, содержал критические недостатки, из-за которых все кошельки, созданные на Android, оказались уязвимы для кражи. Механика та же: если генератор выдаёт повторяющиеся или предсказуемые значения, одинаковое k в двух транзакциях раскрывает ключ, а блокчейн публичен, и подписи видны всем. Разработчики кошельков выпустили обновления и попросили пользователей перевести средства на новые адреса.
Вывод из этого неприятный: случайность трудно проверить. Тест может убедиться, что подпись верна, но не может убедиться, что число k было по-настоящему случайным. Программа с константой вместо k выдаёт корректные подписи, проходит все проверки и годами работает без жалоб, пока кто-нибудь не сравнит две подписи.
Как это исправили: k без генератора случайных чисел
Индустрия сделала вывод: раз генератор случайных чисел — слабое звено, нужно сделать так, чтобы подпись от него не зависела. В том же 2013 году вышел документ RFC 6979 «Детерминированные DSA и ECDSA». В его введении прямо сказано, что DSA и ECDSA требуют для каждой подписи свежее случайное k, что даже небольшой перекос в его выборе превращается в атаку и что качество случайности автоматическими тестами не проверить.
Решение элегантное. Число k не берут из генератора, а вычисляют из приватного ключа и хеша подписываемого файла криптографической функцией. Для разных файлов k получается разным, для одного и того же файла — одинаковым, и это безопасно: подпись тоже выходит одинаковой, новых уравнений не появляется. Без приватного ключа предсказать k невозможно. Современный стандарт NIST FIPS 186-5 тоже разрешает такой детерминированный способ наравне со случайным. Ошибку Sony теперь просто нельзя совершить, если пользоваться нормальной библиотекой, а не писать криптографию самому.
Чем всё закончилось для Sony и владельцев
Дальше начались суды и скандалы. Sony подала иск против Хотца и участников fail0verflow, весной 2011 года стороны заключили мировое соглашение. Примерно тогда же произошло вторжение в PlayStation Network: Sony отключила сеть целиком, а личные данные пользователей оказались у взломщиков. Прямой связи с делом о ключах официально не установили. Коллективный иск владельцев PS3 из-за удалённого Other OS, по данным автора Хабра, тянулся до 2018 года и закончился выплатами примерно по 10 долларов на человека.
Есть и урок поважнее криптографии. Покупатель заплатил за приставку, которая умела запускать Linux, а через несколько лет одно обновление эту возможность отключило. Именно это превратило горстку недовольных программистов в людей, которые разобрали защиту до винтика. О том, как устроено «купил не вещь, а доступ к ней», у нас есть отдельный разбор.
Коротко
— Sony потеряла главный ключ подписи PS3 не из-за слабого шифра, а потому что использовала одно и то же «случайное» число k во всех подписях ECDSA.
— Одна подпись — уравнение с двумя неизвестными. Две подписи с одинаковым k — система из двух уравнений, из которой ключ вычисляется за пару строк.
— Повтор виден снаружи: у таких подписей совпадает половина r.
— Метод показали fail0verflow на 27C3 в декабре 2010 года, ключ появился в сети в январе 2011-го.
— В 2013 году та же ошибка ударила по Android-кошелькам биткоина.
— Сегодня от неё защищает детерминированная подпись по RFC 6979: k вычисляется из ключа и файла, и генератор случайных чисел подвести уже не может.
Пока нет комментариев