← 2026-06-16 の一覧へ戻るホーム
多項式を用いた「短袖」RSA鍵の因数分解

2026/06/12 21:52

多項式を用いた「短袖」RSA鍵の因数分解

RSS: https://news.ycombinator.com/rss

元のHacker News記事へ ↗
要約▶

Japanese Translation:

研究者らは、旧バージョンの CompleteFTP に深刻なセキュリティ脆弱性を発見した。キー生成プロセスにおけるバグにより、何百ものユニークで弱い RSA と DSA のキーが作成されていたことが判明した。この脆弱性の原因は、

Array.Copy
エラーによって 8 ビットのランダム数を 32 ビットの limbs として誤ってキャストし、“短スリーブ” (short-sleeve) キーを生成したことにある。これによりゼロビットの予測可能なパターン（例えば、いくつかのビットごとにゼロ）が形成された。これらの数学的な弱点は、多項式因数分解技法を用いて攻撃者が私人鍵を素早く解読することを可能にする。Yahoo、Verizon、NetApp など主要組織のログへの検証により、研究者 Hanno Böck とその協力者によって回収された 603 の RSA キーおよび 74 の DSA キーを含む、インターネット上に存在する 600 件以上の脆弱なキーが確認された。影響を受けるバージョン（RSA では 10.0.0～12.0.0、DSA では 10.0.0～12.0.0 およびそれ以下のもの）はリスク下に置かれているが、新しいバージョン（RSA では v12.1.0 以降、DSA では v23.1.0 以降）は標準的な暗号化 API を使用しており、この問題を回避している。これに対応して、EnterpriseDT は 2026 年 5 月 8 日にバージョン 26.1.0 をリリースし、管理者が悪用される前に侵害されたキーを特定および再生成するのを支援するための自動検出ツールを含めている。また、badkeys ウェブサイトおよびスタンドアローンツールは、これらの特定の“短スリーブ”脆弱性の検出をサポートするようになっている。

本文

RSA ショートスリーブキー：多項式構造を利用した素因数分解

序論

RSA 私鍵のビット生成がランダムではない場合、**0 ビットに強い偏り（バイアス）**が生じます。この特性は公開鍵にも表れるため、現実世界での誤生成検出が可能です。badkeys プロジェクトでは数百個のユニークなキーを発見し、それらを素因数分解可能であることを示しました。さらに、バグの原因を特定し、0 のビットパターンを悪用した強力な暗号解析技術を開発しました。

現実世界で観測されたパターン

連続した 0 ビットブロックを持つ RSA 合成数は、「ショートスリーブ（Short-sleeve）」と呼ばれます（整数の limbs を完全に覆っていないため）。主に以下の 2 つのパターンが観測されました。

パターン 1：原因未明

  • 発見場所: Yahoo や Verizon などの大企業証明書、NetApp ソフトウェアの実行デバイスなど。
  • 現状: 幸いにもすべての証明書は期限切れ済み。発見事実を企業に共有したが、具体的な製品情報の回答は得られなかった。

パターン 2: CompleteFTP のバグ（要因）

  • 原因: EnterpriseDT社の「CompleteFTP」の古いバージョンにおける大整数コードの不整合（タイプミスマッチ）。
  • 影響:
    • RSA 私鍵：パターンを持ちます。
    • DSA キー：脆弱なショートスリーブ型のキーも多数生成されました。
  • ステータス: 設定期間 (2016 年 12 月〜2023 年 12 月) のキーに対して、EnterpriseDT のツールで再発行必要性を確認可能です。

回復された脆弱なキーの総数:

  • RSA 私鍵：603 個ユニーク
  • DSA キー：74 個

脆弱なキーを発見した方法

badkeys プロジェクトは、公開鍵の脆弱性検出に特化したオープンソースサービスです。Certificate Transparency ログやインターネットスキャンから膨大なデータを収集し、極めて疎（まばら）な RSA 合成数を探求しました。その結果、上記の「ショートスリーブ」パターンを持つ多数のキーを特定しました。

パターンの特徴と期間

いずれの場合も、「疑似的にランダムなデータ」と規則的に間隔を置いた「0 のブロック」が複数存在します。

  1. パターン 1: Yahoo/Verizon/NetApp関連（既に期限切れ）。
  2. パターン 2 (CompleteFTP):
    • SSH ホストで観察され、根本的な脆弱性は以下のバージョンに影響します。
    • RSA キー: バージョン 10.0.0 〜 12.0.0（2016 年 12 月〜2019 年 3 月）
    • DSA キー: バージョン 10.0.0 〜 23.0.4（2016 年 12 月〜2023 年 12 月）

教訓

独立した暗号実装同士が同様の失敗パターンを示すことは、他の実装にも同様のバグが存在する可能性を強く示唆します。このタイプの失敗を対象とした解析アルゴリズムの開発は極めて重要です。

数学的基盤：整数から多項式へ

暗号アルゴリズムの「大整数」は、小さなマシンサイズ値の配列（limbs）で表現されます。ショートスリーブキーの場合、基数（base）は limb サイズに相当し、余分な 0 ビットにより極めて小さな係数を持つ多項式が生成されます。

整数と多項式の互変換

  • 原理: 通常の基底 $B=10$ では $10^i$ を $x^i$ に置き換えます。ショートスリーブキーでは**基数 $B=2^w$（limb サイズ）**を使用します。
  • 式: 整数 $a = \sum_i a_i B^i$ は、多項式 $f_a(x) = \sum_i a_i x^i$ と対応し、評価 $a = f_a(B)$ で整数に戻ります。

攻撃の核心

  1. ショートスリーブ RSA 合成数 $n$ に対して、基底 $2^w$ の表現を用いて多項式 $f_n(x)$ を求めます。
  2. もし因子 $f_p(x)$ と $f_q(x)$ も同様に極めて小さな係数を持つ場合： $$f_n(x) = f_p(x) * f_q(x)$$ が成立します。
  3. 通常の RSA では $f_p(x)$ および $f_q(x)$ は $w$ ビット分の係数を持ちますが、ショートスリーブキーではその必要がありません。

攻撃手順

  1. 多項式評価の性質を利用: 乗算の前か後かは関係なく、積の評価 $f_a(B) * f_c(B)$ は $(f_a*f_c)(B)$ に等しくなります。
  2. 多項式因数分解: 多項式の因数分解は容易なため、$f_n(x)$ を $f_p(x)$ と $f_q(x)$ に分解可能。
  3. 整数への変換: 得られた多項式を実際の値 $2^w$ で評価することで、素因数 $p$ と $q$ を獲得できます。

重要: この手法は「小さな係数を持つ特殊な多項式」のみに対して機能するため、一般論としては RSA は破綻しません。

CompleteFTP 脆弱性のリバースエンジニアリング

Hanno氏が適用した結果、私鍵因子がショートスリーブ化されていることが判明しました。CompleteFTP の SSH バナーからソフトウェアの存在を確認し、トライアル版をリバースエンジニアリングすることでバグを発見しました。

脆弱なコード構造 (
genRandomBits
)

RSA キー生成時にランダムビットを埋め込む役割を果たす関数ですが、以下のロジックに致命的な不整合があります。

public void genRandomBits(int bits) {
    // Limb の数を計算 (1 limb = 32 bit)
    int numLimbs = bits / 32; 
    // RNG オプットの保存領域を割り当てる (各 limb が 8 バイトの byte[] として扱われる点に注意)
    byte[] array = new byte[numLimbs];
    // システム RNG を呼び出す
    rngProvider.GetNonZeroBytes(array);
    // ランダムデータを大整数の limb にコピーする
    Array.Copy(array, 0, bignumLimbs, 0, numLimbs); 
    // トップビットをセットして適切なビット長を確保する
    bignumLimbs[numLimbs - 1] |= 0x80000000;
    // 長さを保存する
    dataLength = numLimbs;
}

バグの特定：サイズの不整合

  • 問題点: 
    genRandomBits
    は、各 limb に 32 ビット のランダムデータを必要としていますが、コードは暗黙的に 8 ビット（1 Byte）要素 を大整数 limb へコピーしています。
  • 結果: コピーされるデータ量が不足し、0 ビットが重複して埋め込まれます。これがショートスリーブキーの反復構造を生成する直接の原因です。

バグの修正経緯

  • 最新のバージョンでは関数が実行不可（コンパイル済み）にされ、動的テストで破損キーが生成されなかった理由です。
  • 旧バージョンは独自コードを使用し、この脆弱な関数を呼び出していましたが、後に標準的な .NET クリプト API に書き換えられました。
  • この変更により、RSA キー生成に 
    RSACryptoServiceProvider
    、DSA キー生成に 
    DSA.Create
    API が採用され、脆弱性の発生源が完全に排除されました。

脆弱性の拡散と封じ込め

キー生成コードを標準ライブラリへ書き換える判断は、影響範囲の拡大を大幅に抑制しました。歴史的なスキャンデータとの照合結果は以下の通りです。

  • 2016 年 12 月: 脆弱性発覚、増加開始。
  • 2019 年 3 月: 再構築された RSA コードがリリースされ、増大が一気に止まりました。
  • 傾向: 以降はホスト数は減少しつつも、影響を受けるキーの割合は安定しています（顧客側での一時的な更新によるパターン）。

封じ込め対策

EnterpriseDT チームは迅速に対応し、2026 年 5 月 8 日にバージョン 26.1.0 をリリースしました。

  • システムが脆弱なキーを使用しているか自動検出。
  • ユーザーに対してキー再発行が必要な場合を警告。
  • badkeys ウェブサイトおよび個別ツールでも、脆弱なショートスリーブ RSA キーの検出をサポートするようになりました。

回復実績

合計で以下の数の私鍵回復に成功しました（RSA SSH キーに偏っているため実際の普及度は過小評価されている可能性があります）。

  • 完全な復旧: CompleteFTP 脆弱バージョンによる 603 個の RSA、74 個の DSA。
  • 部分復旧: ショートスリーブパターンを持つ 26 個の RSA キー（製品未特定分）。

ショートスリーブキーさらなる探索への取り組み

現時点ではパターン 1 の追加情報は得られておらず、脆弱性がか他のキータイプにも広がっているかは不明です。しかし、以下の点は重要です。

  • 新構造の利用: 規則的な間隔を持つビットブロックを利用する既存アルゴリズムに加え、新しい構造を活用する強力な変種が存在する可能性があります。
  • フィードバックループ: この種の脆弱性の研究は、「暗号実装がどのように失敗するか」を理解し、「システムがどう壊れるか」を観察することでのみ学習できます。

付録：実装詳細と課題（探索的なガイド）

攻撃の実装や有効性を証明するためのコード検討用の資料です。以下の課題質問に答え、独自の実験を試みてみてください。

試行データ（合成生成）

以下の $n_1, n_2$ は実際に生成されたものではなく、現実世界のキーと同じパターンに従って作成されたものです。$n_2$ の因子は 

genRandomBits(1024)
をループして素数になるまで生成しています。

n_1 = 0xc889f7ef523b08e400000000000000014d2ee8284c7a03c000000000000000012c16eeaeab96ddc8000000000000000201036d671407a06600000000000000022f743377005a840d0000000000000001e8e3c0efdd8054ba000000000000000306ee98c677dfdf190000000000000002de525d2b1011ceae0000000000000424455c59eec3a0654500000000000003f8d762d68bcbe8cc3a00000000000000d31291f9aaa7e9a7d60000000000000337a82a59342aadff570000000000000295c495b3690a69b66c00000000000000d9c5e55654e9b14cba000000000000040f0f0f7d3bfdce03d6000000000000026b89ac77db000000000000000000036a77

n_2 = 0x40000049000014ac8000900e00010ec58000b17b8001e0720001be890002169f80029cd5000349190003cd4480037c8c000397660003b28300041021000418cb00058a210004c2708004924980053b8780051cbd8005ebe80006bb27800765e6800651478007f62300073949800860950008614d800863988008d103800884c100099a260009a6d90009578f0007e84300080db800072e59000724f10007c0ec0006ec6600062231000605930005ca4c000566cc0005da92000574dd00040bf1000457dc0004cfbe0004c5640003fe6d0003ada60002de110002cbb30002d5a6000243840001cdf40001a8a9000151be000113f4000101070000acdf000029e5

課題質問（考察）

  1. $B=2^{32}$ を用いて $f_{n_2}(x)$ を計算すると、一部の係数が大きくなります。なぜでしょうか？$f_p(x)$ および $f_q(x)$ のすべての係数が小さいことは事実ですか？
  2. $p \ll i$ というビットシフトによって $f_{2^i p}(x)$ が小さな係数を持つものになりますか？これは、任意のショートスリーブ値を多項式へ変換するための重要なトリックです。
  3. $f_{2^i p}(x)$ と $f_{2^j q}(x)$ が小さな係数を持つ場合、公開情報から積 $f_{2^i p}(x) \cdot f_{2^j q}(x)$ を計算可能でしょうか？それを通じて $p$ と $q$ を回復可能ですか？
  4. この手法があらゆる $p, q$ に機能するなら RSA が破綻します。**なぜショートスリーブ性が重要であり、なぜこの因数分解方法は一般論では機能しないのでしょうか？**限界は何か？
  5. ショートスリーブ性は積の構築を可能にしますが、多項式が既約でない場合、因数分解によりさらに項に分割する可能性があります。多項式因数分解から常に効率的に $p$ と $q$ を回復する方法が存在することを証明してください。

同じ日のほかのニュース

一覧に戻る →

2026/06/16 5:00

LinkedIn の雇用オファーに含まれた裏口

## 日本語訳： 提供されたテキストは、読めるコンテンツではなく完全に破損したバイナリデータからなるものであり、ニュース、事実、エンティティ（製品名、日付、組織など）、または論理的構造は一切含んでいません。入力内に理解可能な単語や文が存在しないため、背景コンテキスト、将来の予測、または潜在的な影響を特定することはできません。その結果、特定の数字を抽出したり、IT 記事のための妥当な箇条書きを生成したり、意味のある要約を導き出すことは不可能であり、このデータは修復されるまで、あるいは正当なテキストで置換されるまでは静的ノイズとして機能し、分析に価値を持ちません。

2026/06/16 7:37

Wi-Fi スマート電球に内蔵された禁書図書館

## 日本語翻訳： 「Banned Book Library」プロジェクトは、安価な WiFi スマートボールを分散型で検閲耐性のある禁書アーカイブに変換し、不安定なクラウドサービスよりもローカルコントロールを重視し、Cory Doctorow の情報レジリエンス哲学と整合性を保ちます。ESP32C3 チップの限られた 4MB フラッシュストレージに対処し、外部メモリカード用の困難なハンダ付けを避けるために、開発者は Arduino IDE と ESP-IDF を用いてファームウェアをカスタマイズしました。具体的にはパーティションテーブルを変更して電子書籍用にスペースを割り当てるよう修正するとともに、Tasmota（ソースコードの複雑さから放棄された）に見られる平文で認証情報を格納するというセキュリティリスクを回避しています。本デバイスは、カスタム「safeboot」復旧メカニズムを備え、禁書理由とともに書籍リストを表示する Web インターフェースを内蔵しており、GPIO ピンを通じて LED の色温度を制御できる管理パネルも含まれています。DNS 劫奪を用いたキャプティブポータルを実装し、あらゆるデバイスからユーザーをローカルアーカイブへ誘導することで、物理的に分散されたネットワークによる情報レジリエンスを実現しています。今後のアップデートでは、AnalogWrite を用いた精密な RGB/ホワイト色制御や、ファイル共有のためのメッシュネットワーキングへの実験が含まれます。結局のところ、このプロジェクトは一般的なスマートホーム技術を堅牢なインフラストラクチャに転換し、日常のデバイスが重大なアーカイブ機能を受け持ち得ることを示すとともに、小容量というハードウェアの制約を特徴へと高め、保管者に最も重要な作品のみを選定するよう促しています。

2026/06/16 0:13

イロフ 1.0

## Japanese Translation: iroh ネットワークは、それ以前の 65 バージョンに続く初となる安定リリースとしてのバージョン 1.0 を正式にローンチし、インターネット全体で安全な localhost のように動作する革命的な「key でダイヤル」システムを導入します。このマイルストーンでは、不安定な IP アドレスをユーザーが制御するキーに置き換え、複雑なルーティングに依存せずにデバイス間での直接かつ暗号化された接続を可能にします。ネットワークは巨大なスケーラビリティを実証しており、たった 30 日で 2 億以上のエンドポイントを作成し、安全な動画ストリーミングやエージェント間の通信、大規模言語モデルのトレーニングなど、多様な用途に数百万のデバイスを支えています。IETF のドラフトや QUIC マルチパスといったオープン標準を基盤とし、ローカルフースト設計によりインターネット接続がなくても堅牢なコネクティビティを提供します。開発者にとっての大きな影響として、Python、Node.js、Swift、Kotlin への公式 FFI サポートが追加され、安定した異言語間通信が保証されています。特に、1.0 API はエンドポイント間の通信がマイナーバージョンの変更や使用されるプログラミング言語に関係なく確保されることを保証します。さらに、デバイス同士の直接転送によりクラウドホップが 95% 削減され、データエグレスコストの大幅な低下が可能となるだけでなく、Bluetooth Low-Energy など新たなトランSPORT を実装できます。前マイナーバージョンを使用しているユーザーは、2026 年 12 月 31 日（パブリックリレーサポート終了日）までにアップグレードすることを推奨され、安定性を維持するためです。問題が発生している場合は、バグレポートの前に更新して問題が持続するかを確認してください。