ed25519-unsafe-libs

Атака Oracle на функцию подписи с двойным открытым ключом в Ed25519

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

Большинство репозиториев из нашего анализа перечислены в IANIX :: Что использует Ed25519.

Количество затронутых библиотек: 45
Количество библиотек, исправивших проблему после объявления: 8
последнее обновление: 4 мая 2023 г.

Реализации Proof of Concept, демонстрирующие эту потенциальную уязвимость:

• Rust: ed25519-chalkias-exploit
• Python: Уязвимость Ed25519 в Python, Buchanan, William J (2022). Уязвимость Ed25519 в Python (восстановление закрытого ключа). Asecuritysite.com.

Доклады:

• Приглашённый доклад в Криптографическом читательском клубе Национального института стандартов и технологий США (NIST): слайды — Укрощение множества EdDSA (стр. 28–39), Konstantinos Chalkias, François Garillot, Valeria Nikolaenko (2023). Укрощение множества EdDSA и атаки на подписи Ed25519.

Освещение этой атаки в новостях и социальных сетях

• Криптографический читательский клуб NIST «Укрощение множества EdDSA» (8 марта 2023 г.)
• The Daily Swig «Десятки криптографических библиотек уязвимы к краже закрытых ключей» (28 июня 2022 г.)
• Risky Biz News «Новая криптоуязвимость: десятки криптографических библиотек неправильно реализовали алгоритм цифровой подписи Ed25519» (28 июня 2022 г.)
• Пост в блоге SafeHeron «Анализ рисков использования Ed25519: закрытый ключ вашего кошелька может быть украден» (17 июня 2022 г.)
• kryptera.se «Уязвимость в большинстве библиотек ed25519» (на шведском языке) (29 июня 2022 г.)
• Difesa e Sicurezza & Yoroi «Librerie crittografiche ed25519 potenzialmente non sicure» (на итальянском языке) (1 июля и 29 июня 2022 г.)
• Пост на Medium от профессора Билла Бьюкенена OBE «Ed25519 отличный, но ...» (1 июля 2022 г.)
• Reddit r/crypto (лучший пост месяца — 18 июня 2022 г.)
• Reddit r/cryptography (17 июня 2022 г.)
• Интересные твиты:
  • твит 1 (автор: Kostas Kryptos — «Первоначальные 26 уязвимых библиотек»)
  • твит 2 (автор: Kostas Kryptos — «Последствия для 40 уязвимых библиотек»)

В чём суть проблемы?

Обратите внимание, что в обычном случае, согласно соответствующему rfc8032, подписи EdDSA детерминированы, и, таким образом, для одного и того же входного сообщения возвращается уникальный результат подписи, включающий два элемента: точку на кривой R и скаляр S.

Алгоритмическая деталь состоит в том, что открытый ключ подписывающего участвует в детерминированном вычислении только части S подписи, но не значения R. Последнее означает, что если бы злоумышленник каким-либо образом смог использовать функцию подписи как Oracle (принимающий произвольные открытые ключи на вход), то для одного и того же сообщения можно было бы получить две подписи с одинаковым R, различающиеся только частью S. К сожалению, когда это происходит, закрытый ключ можно легко извлечь; этот пост на StackOverflow объясняет, почему это возможно.

Тем не менее, публичные API НЕ должны допускать передачу раздельной пары закрытый/открытый ключ в качестве входных данных для подписи. Чтобы обойти это, многие реализации хранят открытый ключ вместе с закрытым ключом (или сидом) и считают всю пару ключей секретом ЛИБО всегда повторно вычисляют открытый ключ внутри функции подписи. К сожалению, большое количество существующих библиотек не решают эту проблему, допуская передачу произвольных открытых ключей на вход без проверки соответствия входного открытого ключа входному закрытому ключу.

Конечно, это не означает, что все приложения, зависящие от этих библиотек, подвержены атакам с раскрытием ключей; на самом деле большинство из них, вероятно, безопасны, поскольку обычно не предоставляют затронутый API своим пользователям и связывают пару открытый/закрытый ключ непосредственно перед вызовом sign. С другой стороны, даже когда эти API не открыты, существуют приложения с разными стратегиями модели угроз TCB в отношении того, как управляются и хранятся закрытые и открытые ключи. Тем не менее, чтобы предотвратить эту атаку, разработчикам следует также обеспечить протокол защиты целостности и для открытых ключей.

Здесь мы перечисляем некоторые затронутые библиотеки вместе с соответствующими ссылками на код.

Рис. 1. Пример неправильного использования API в Rust-крейте ed25519-dalek.

Затронутые библиотеки

• C: OpenGNB
  https://github.com/gnbdev/opengnb/blob/master/libs/ed25519/sign.c#L7

• C: GNU Nettle
  https://github.com/gnutls/nettle/blob/fe7ae87d1b837e82f7c7968b068bca7d853a4cec/ed25519-sha512-sign.c#L43

• ASM/C: iroha-ed25519 (Hyperledger Project)
  https://github.com/hyperledger/iroha-ed25519/blob/main/lib/ed25519/ref10/ed25519.c#L27 и https://github.com/hyperledger/iroha-ed25519/blob/main/lib/ed25519/amd64-64-24k-pic/ed25519.c#L30

• C: ed25519-donna (Andrew Moon)
  https://github.com/floodyberry/ed25519-donna/blob/master/ed25519.c#L59

• C: ed25519 (Orson Peters)
  https://github.com/orlp/ed25519/blob/master/src/sign.c#L7

• C: libbrine (Kevin Smith)
  https://github.com/kevsmith/libbrine/blob/master/src/ed25519/sign.c#L7

• C++: Ed25519 (ArduinoLibs)
  https://rweather.github.io/arduinolibs/classEd25519.html#a36ecf67b4c5d2d39a31888f56af1f8a5

• C#: ed25519 (Hans Wolff)
  https://github.com/hanswolff/ed25519/blob/master/Ed25519/Ed25519.cs#L146

• C#: Ed25519 (CryptoManiac)
  https://github.com/CryptoManiac/Ed25519/blob/972829ac688847895d5105f19ca1e5777131b421/Chaos.NaCl/Internal/Ed25519Ref10/keypair.cs#L7

• Dart: ed25519_dart (Oleksii Semeshchuk)
  https://github.com/semolex/ed25519_dart/blob/master/lib/src/ed25519_dart_base.dart#L200

Исправленные библиотеки

• C: Trezor firmware
  Исправлено в этом PR: https://github.com/trezor/trezor-firmware/pull/2349 (Исправление внесено 27 июня 2022 г.)

• Java: ed25519-elisabeth (Jack Grigg)
  Исправлено в этом коммите: https://github.com/cryptography-cafe/ed25519-elisabeth/commit/49545ce47d550fed807522dff86546c812ccbbac (Исправление внесено 19 июня 2022 г.)

• C: Harbour (Viktor Szakats)
  Исправлено в этом коммите: https://github.com/vszakats/hb/commit/bae610b63d35c6c1793d94a3bf9467c3b1eded18 (Исправление внесено 30 июня 2022 г.)

• Rust/Wasm: polkadot-js/wasm
  Исправлено в этом PR: https://github.com/polkadot-js/wasm/pull/381/files (Исправление внесено 3 июля 2022 г.)

• C: horse25519 (Yawning Angel)
  Исправлено в этом PR: https://github.com/Yawning/horse25519/pull/3 (Исправление внесено 15 августа 2022 г.)

• Erlang: erlang-libdecaf
  Исправлено в этом коммите: https://github.com/potatosalad/erlang-libdecaf/commit/16ba07ea122660e95f6cfa9107e28ed58bada713. Логика рассмотрена в этом issue: ed25519-unsafe-libs/issues/7 (Исправление внесено 28 августа 2022 г.)

• Rust: ed25519-dalek (Isis Agora Lovecruft)
  Исправлено в этом PR: https://github.com/dalek-cryptography/ed25519-dalek/pull/205 (Исправление внесено 22 октября 2022 г.)

• C: Monocypher (Loup Vaillant)
  Исправлено в этом коммите: https://github.com/LoupVaillant/Monocypher/commit/da7b5407d20329f21a53ea993f516fb55e2f5e26 (Исправление внесено 27 февраля 2023 г.)

Ложные срабатывания (вероятно, безопасны)

Библиотеки, изначально указанные как уязвимые, но исключённые из списка на основе отзывов сообщества.

• Go: threshold-ed25519 — пороговые подписи с использованием Ed25519
  https://gitlab.com/unit410/threshold-ed25519/-/blob/main/pkg/ed25519.go#L161 -> см. отчёт https://github.com/MystenLabs/ed25519-unsafe-libs/pull/9 (сообщено 27 октября 2022 г. пользователем nitronit)