В Штатах ГОСТы тоже так себе. Фатальная уязвимость в YubiKey FIPS, которую можно было избежать

Привет, %username%!

13 июня 2019 года компания Yubico, производитель устройств для двухфакторной аутентификации, выпустила уведомление о безопасности в котором говорится о критической уязвимости некоторых устройств Yubikey FIPS. Давайте посмотрим что это за уязвимость и как её можно было предотвратить.

Предисловие

В Штатах тоже есть свои ГОСТы, называются FIPS — Federal Information Processing Standard. Оборудование и программное обеспечение, с которым работают гос. структуры обязаны соответствовать FIPS.

По словам коллег, с которыми мы познакомились на EuroCrypt 2019, сертификация FIPS — сущий ад, вплоть до того, что специалисты FIPS приходят к вам, запускают ваш софт в debug режиме, меняют значения в памяти и проверяют, упадёт ли там, где задумано.

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

ECDSA

Внутри usb токена Yubico есть хранилище для ключей и движок, реализующий в т.ч. ECDSA. На сервер при регистрации передаётся и сохраняется публичный ключ из токена.

А при логине сервер отправляет клиенту случайную строку, которую тот подписывает вместе с метаинформацией, такой, например, как домен.

В двух словах о том как работает ECDSA или цифровая подпись на эллиптических кривых. Некоторые детали опущены для простоты изложения:

1. Считаем хеш от сообщения и переводим его в число. $$.
2. Генерируем криптографически стойкое случайное число k.
3. Вычисляем точку $$ где G — базовая точка кривой, называемая генератором(константа)
4. Вычисляем $$, где n — порядок базовой точки (константа)
5. Вычисляем $$, где d — приватный ключ
6. Цифровая подпись состоит из пары чисел r, s

Критически важно, чтобы число k было не только секретным, но и всегда разным. Иначе становится возможным вычислить закрытый ключ.

К примеру, у нас есть две подписи (r, s) и (r1, s1), которые получены для разных сообщений m и m1, но с помощью одного и того же секретного k. Давайте вычислим приватный ключ.

• Атакующий вычисляет e и e1.
• Поскольку $$, то можно узнать k. $$
• Поскольку $$, то можно вычислить d. $$
• d — приватный ключ

Если числа k разные, но не совсем, то тоже можно вычислить приватный ключ, просто надо будет немного побрутфорсить. Кстати, В 2013 году я уже писал как ломался коряво реализованный (EC)DSA в PlayStation и других продуктах, крайне рекомендую к прочтению.

Yubico

Так вот, в ряде продуктов Yubico FIPS был баг, при котором числа k сразу после включения токена генерировались не совсем случайные. И была реальная возможность вычислить приватный ключ, зашитый внутри. Поэтому они отозвали уязвимые устройства и выпустили уведомление.

Что можно было сделать?

Вообще говоря, проблема давно решена. С 2013 года существует RFC 6979, который описывает детерминированную ECDSA, получаемой из обычной путём нескольких несложных модификаций. Более того, в 2014 году при разработке стандарта U2F именно из-за потенциальных проблем с ГСЧ FIPS открытым текстом предлагали перейти на Deterministic ECDSA, но предложение было отклонено. Это одна из причин, по которой FIPS расшифровывают как F*cked-up, Insecure, Persnickety Standards.

Yubico могла формально соответствовать требованиям FIPS на случайность числа k, но использовать workaround, генерируя k детерминировано, а потом XOR-я его с тем, что выдал ГСЧ (или прогнав всё через KDF). Однако, этого сделано не было.

А что у нас?

А у нас всё то же самое. ГОСТ Р 34.10-2012 — по сути тот же самый ECDSA, просто с другими кривыми. Требования к генерации числа k остаются такими же, как в традиционном ECDSA. Делает ли кто-нибудь из производителей наших токенов описанный выше workaround? Использует ли детерминированную версию ECDSA? Сомневаюсь.

Если тут есть представители разработчиков, было бы интересно послушать их мнение на этот счет. Или по крайней мере, чтобы они имели это ввиду.

Спасибо за внимание.