ed25519-unsafe-libs

Ed25519 に対する二重公開鍵署名関数オラクル攻撃

署名関数の入力として秘密鍵と公開鍵を独立して受け取る公開APIを備えた、潜在的に安全でない ed25519 署名ライブラリのリストです。これらの公開APIを誤用すると、秘密鍵が漏えいする可能性があります。

私たちの分析で対象となったリポジトリのほとんどは、IANIX :: Things that use Ed25519 に掲載されています。

影響を受けるライブラリの数: 45
アナウンス後に問題を修正したライブラリの数: 8
最終更新日: 2023年5月4日

この潜在的なエクスプロイトを実証する Proof of Concept 実装:

• Rust: ed25519-chalkias-exploit
• Python: Ed25519 Vulnerability in Python, Buchanan, William J (2022). Ed25519 Vulnerability in Python (Recovering Private Key). Asecuritysite.com.

講演:

• 米国国立標準技術研究所 (NIST) Crypto Reading Club への招待講演: slides - Taming the Many EdDSAs (28〜39ページ), Konstantinos Chalkias, François Garillot, Valeria Nikolaenko (2023). Taming the Many EdDSAs & Ed25519 Signing Attacks.

この攻撃に関するニュースおよびソーシャルネットワークでの報道

• NIST Crypto Reading Club「Taming the Many EdDSAs」 (2023年3月8日)
• The Daily Swig「Dozens of cryptography libraries vulnerable to private key theft」 (2022年6月28日)
• Risky Biz News「New crypto vulnerability: Tens of cryptography libraries have misimplemented the Ed25519 digital signature algorithm」 (2022年6月28日)
• SafeHeron blogpost「Analysis on Ed25519 Use Risks: Your Wallet Private Key Can Be Stolen」 (2022年6月17日)
• kryptera.se「Vulnerability in most ed25519 libraries」(スウェーデン語) (2022年6月29日)
• Difesa e Sicurezza & Yoroi「Librerie crittografiche ed25519 potenzialmente non sicure」(イタリア語) (2022年7月1日および6月29日)
• Prof Bill Buchanan OBE による Medium 投稿「Ed25519 is Great, But ...」 (2022年7月1日)
• Reddit r/crypto (今月のベスト投稿 - 2022年6月18日)
• Reddit r/cryptography (2022年6月17日)
• 注目のツイート:
  • tweet 1 (Kostas Kryptos 氏 -「The original 26 vulnerable libs」)
  • tweet 2 (Kostas Kryptos 氏 -「Aftermath of the 40 vulnerable libs」)
  • tweet 3 (Catalin Cimpanu 氏 -「40 cryptography libraries are impacted by same Ed25519 misimplementation」)
  • tweet 4 (Kenny Paterson 氏 -「Potential for widespread EdDSA private key recovery, cf. http://kopenpgp.com where same vector exploited in OpenPGP libs」)
  • tweet 5 (Steven Galbraith 氏 -「A hazard for deterministic signatures: better check it is the correct public key!」)
  • tweet 6 (Riyaz Faizullabhoy 氏 -「If you're using EdDSA in prod please take a look」)
  • tweet 7 (Bart Preneel 氏 -「Reminder that implementing cryptographic algorithms securely and correctly is hard」)。
• この攻撃を題材にした CTF (capture the flag) チャレンジ:
  • ImaginaryCTF - JWT25519 (200pts) (2022年6月30日)

問題は何か?

通常、関連する rfc8032 に従えば、EdDSA 署名は決定論的であり、同じ入力メッセージに対しては、曲線上の点 R とスカラー S の2つの要素を含む一意の署名出力が返されます。

アルゴリズム上の詳細として、署名者の公開鍵は署名の S 部分の決定論的計算にのみ関与し、R 値には関与しません。これは、攻撃者が何らかの方法で署名関数をオラクル(任意の公開鍵を入力として受け付けるもの)として利用できた場合、同じメッセージに対して、同じ R を共有し S 部分のみが異なる2つの署名を取得できる可能性があることを意味します。残念ながら、これが発生すると、秘密鍵を簡単に抽出できてしまいます。この StackOverflow の投稿 が、これが可能である理由を説明しています。

つまり、公開APIは、分離された秘密鍵/公開鍵のペアを署名入力として許可すべきではありません。これを回避するために、多くの実装では公開鍵を秘密鍵(またはシード)とともに保存し、鍵ペア全体を秘密として扱うか、あるいは常に署名関数内で公開鍵を再導出しています。残念ながら、既存のライブラリの多くは、入力された公開鍵が入力された秘密鍵に対応するかどうかを確認せずに任意の公開鍵を入力として許可することで、この問題に対処できていません。

もちろん、これはこれらのライブラリに依存するすべてのアプリケーションが鍵漏えい攻撃の危険にさらされていることを意味するわけではありません。実際、ほとんどのアプリケーションは、影響を受けるAPIをユーザーに公開しておらず、sign 呼び出しの直前に公開鍵と秘密鍵のペアを結合しているため、おそらく安全です。一方で、これらのAPIが公開されていない場合でも、秘密鍵と公開鍵の管理・保存方法に関して異なる TCB 脅威モデル戦略を採用しているアプリケーションが存在します。この攻撃を防ぐためには、開発者は公開鍵に対しても完全性保護プロトコルを適用する必要があります。

ここでは、影響を受けるいくつかのライブラリと関連するコード参照を列挙します。

図1. ed25519-dalek Rust クレートにおける API 誤用の例。

影響を受けるライブラリ

• 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

• Dart: riclava_ed25519 (riclava)
  https://github.com/riclava/ed25519/blob/master/lib/ed25519.dart#L125