パスワードを忘れた？ アカウント作成
Close
13974 story

CPUの高速化技術を悪用したRSA鍵盗聴が可能か 19

ストーリー by kazekiri
大事の予感 部門より

tamo 曰く、

本家記事によると、 RSA 鍵など機密情報が CPU で使用される際にそれを盗聴する強力な方法 Simple Branch Prediction Analysisが発見されたそうです。 発見者によれば、これまでの Branch Prediction Analysis 攻撃に有効とされてきた blinding などの対策が効かないようです。
詳しくは分からないのですが、 Matasano Chargen や本家コメントなどをざっと見た感じでは、RSA アルゴリズム自体に問題があるのではなく、 CPU が分岐予想で使うキャッシュの保護に問題があるような感じです。
以前の ハイパースレッディングに深刻な脆弱性が報告される という問題と方向性は同じだと思うのですが、 今回はもっと回避が難しいようです。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

CPUの高速化技術を悪用したRSA鍵盗聴が可能か More

  • アブストラクト [iacr.org]だけ読んでの話ですが，(以下引用)

    We prove that a carefully written spy-process running simultaneously with an RSA-process, is able to collect during one \emph{single} RSA signing execution almost all of the secret key bits.

    つまり，RSAによる暗号化処理を行っているのと同じマシンで解読プロセスを走らせられることが大前提，という時点で攻撃手段はそれなりに絞られるかと．
    逆に言えば，例えば一人だけが使うPCのブラウザでRSAアルゴリズムを使ってSSL通信をやるとして，その暗号鍵がそのPC上でこの方法で破られるリスクは小さい(そもそもそのPC上でそんなやばいプロセスが動作できてしまう環境自体が問題)と考えられます．

    勿論，

    Moreover, despite sophisticated hardware-assisted partitioning methods such as memory protection, sandboxing or even virtualization, SBPA attacks empower an unprivileged process to successfully attack other processes running in parallel on the same processor.

    から推察するに，マルチユーザ環境において他人のRSA解読の様子が覗けてしまうとかいうあたりはかなり問題．
    • 私もPDFの本文を斜めで読んでの感じなんですが、
      分岐予測やパイプラインの流れに支配されるデータの動き自体がMPU SETやOS依存になりますから、盗聴者は相手のシステム(MPUだけではなくOSやミドルウェアあたりのバイナリコードも入るかな？）を確定した上で盗聴プログラムをはりつける必要がある訳で。

      そうなると、この方法に依存して、なおかつ安易に考えられる、「確実な」盗聴手段は二つになる訳で、

      1.特定ユーザの特定プロセスを「ストーキング」する盗聴プロセスを対でマシン内に用意しておく
      2.コンパイラの最適化過程で盗聴コードが混入されるように仕込んでおく

      こうなると、「どっちもどっち」と言うか、SSLなどのSecure系のShared LibやOSのコンテキストスイッチャのコードを書き換えてバックドア仕掛ける方が簡単では無いか(^_^;と言う感じがするんですけど(^_^;
      今回の「発見」の肝はバックドアの隠蔽度を非常に高められる…と言うことなんでしょうかねぇ?(^_^;
      シェア
      親コメント

      • ざっと読んでみた話ですが (スコア:3, 興味深い)

        by superfox (31908) on 2006年11月20日 22時17分 (#1061499)
        「分岐予測に使うキャッシュの保護に問題」というのは、別のユーザプロセスから間接的に分岐状態が予測出来てしまうことを指しているようです。スパイプロセスが１ビットの記録にかかる時間は暗号化／複合化の時間に比べてはるかに少なくてすむので

        １）（なんらかの方法で）暗号化／複合化プロセスと同期を取ってスタート（分岐キャッシュをクリアしておく）
        ２）自前のプログラムで分岐を行い、前方／後方のどちらが「ヒット側」だったか（と暗号化／複合化プログラムのコードから）0/1を決定して記録
        ３）次のビットによる暗号化／複合化を待つ（分岐キャッシュを汚さないように注意）

        …という感じなのだと思います。ただ、これだと同一キーで複数回結果を取って精度を上げないといけないと思いますが、今回のニュースでは「一回で良い」というのが大きいのでしょう。精度の高い同期の取り方が見つかったか、結果から精度の高いビット列予測が可能となったか、その両方か、ではないでしょうか。

        # わかりきったキーをサービスにバンバン投げておいて、違うのが見つかったらそれを記録、とかもありそう。
        シェア
        親コメント
        • あまりにもズバリ求められそうなので怖くなってきました…。

          # あくまでも同一マシン上で実行出来ることが前提ですが。
          シェア
          親コメント

        • HyperThreadの脆弱性のときも思ったんですけど (スコア:1, 興味深い)

          by Anonymous Coward on 2006年11月21日 0時19分 (#1061585)
          不勉強で各暗号系の処理がどのようになっているかは知らないんですが、結局のところ

          ループ→常に最大（最悪）の回数ループするようにする
          分岐→分岐条件に関わらず常に演算を行い、条件付代入（x86ならMOVcc）などで切り分けるようにする

          として、入力が何であれ、常に同じ命令群を実行するようにコードを書くしかなさそうな気がします。
          （条件付代入がない命令セットもありますが、ビット演算などの組み合わせで代用できますし）

          ただそうすると、タダでさえ重い処理が常にワーストな時間がかかるようになるのと、
          分岐命令を生成させないように高級言語で記述するのは面倒という問題がありそうですが。

          次はSpeedStep/Cool'n'Quiet系で盗聴かなと思ったAC
          シェア
          親コメント

          • 実際のところ (スコア:3, 参考になる)

            by superfox (31908) on 2006年11月21日 0時44分 (#1061599)
            ここの解説 [iacr.org]によれば、RSA に用いられるモンゴメリ乗算

            S = ((A*B)/R) mod N

            の最後（mod N）の条件分岐が注目されているそうで、openSSL のコードは

            openssl-0.9.8d/crypto/bn/bn_mont.c

            の int BN_from_montgomery() にあるこの部分だと思います。

                    if (BN_ucmp(ret, &(mont->N)) >= 0)
                            {
                            if (!BN_usub(ret,ret,&(mont->N))) goto err;
                            }

            > ループ→常に最大（最悪）の回数ループするようにする
            > 分岐→分岐条件に関わらず常に演算を行い、条件付代入（x86ならMOVcc）などで切り分けるようにする

            前者が blinding というものではないのでしょうか？（私も詳しくはない）。blinding と randomization techniques は totally useless [iacr.org] とあります。後者もサイクル数が違ったりすると付け込む隙があるかもですね。
            シェア
            親コメント

            • Re:実際のところ (スコア:2, 興味深い)

              by Anonymous Coward on 2006年11月21日 2時24分 (#1061629)
              > 前者が blinding というものではないのでしょうか？（私も詳しくはない）。blinding と randomization techniques は totally useless [iacr.org] とあります。

              なるほど、blindingというのですか。

              英語も不勉強なもので（笑）、確信はないのですが「SBPA Attack に対しては blinding と randomization techniques は totally useless」ということではないのですかね。

              盗聴されないための必要条件だけど、SBPA Attackに対しては無力なので十分条件にはならない…という意味に読み取れたのですが。

              > 後者もサイクル数が違ったりすると付け込む隙があるかもですね。

              今時のCPUの条件付代入は大抵1クロック命令なのでおそらく大丈夫かと思われます。

              ただ結局はCPUごと（アーキテクチャごとではなく）に安全かどうかを確認する必要があるんでしょうね。

              しかし、面倒ですね。
              CPUによっては乗算命令やシフト命令なども値によって処理にかかるクロック数が違うので使用できない可能性が。

              暗号化ライブラリコーディング規約（C言語版）はこんな感じですかね。
              （思いつきで書いているのでテキトーですが）

              1. システムコール・外部ライブラリの呼び出しは原則使用しないこと
                      （必要な場合はリーダーに申請して、理由と使用許可番号をコメントに記述すること）

              2. while/do-whiteループは原則使用しないこと
                      （可変長の入力データに対応するためなどで使用した場合はリーダーに申請して、理由と使用許可番号をコメントに記述すること）

              3. forループの初期値・増分値・終了値は定数のみとし必ず固定回数のループとすること
                      （暗号ビット長に対応するなどで可変にしたい場合はリーダーに申請して、理由と使用許可番号をコメントに記述すること）

              4. if分岐/switch分岐/三項演算子（?:）は使用しないこと
                      代わりに処理時間固定三項演算マクロを使用すること

              5. バージョン管理サーバにコミットする前にビルドを行い、対象とするCPU用の処理時間可変命令チェックツールで処理時間が可変である命令が生成されていないことを確認すること

              6. 各コードのバージョン履歴には「チェック済み対象CPU」「ビルド環境情報」を記述すること

              おそらくこれでは不足していると思いますが、これだけでも面倒ですね。

              テストも入力値によって異なった動きをしないか確認する必要があるわけですし。
              （エミュレータを作ってとりあえずの1次確認するのが楽かな？）

              こんなプロジェクトに参加したくないと思ってしまったAC

              PS
              投稿制限があるのでここに書いてしまいますが（アカウント作れよ）、#1061625 [srad.jp]のコア数の話に関して。

              コア数に対して十分なスレッドを起こしてすべてで盗聴させてその結果を統合すれば推測できそうな気がしますが、どうでしょう。
              シェア
              親コメント
        • 4 way set associativeなら、4bitまで判定可能ってこと？

          BTBでは話しが違うのかな？

  • 恥かしい分岐結果のストア禁止 (スコア:3, 参考になる)

    by Anonymous Coward on 2006年11月20日 18時56分 (#1061376)
    CPUが分岐予想で使うキャッシュの保護に問題がある

    CPU内キャッシュ(L1, L2等)とは別にある、分岐予測用キャッシュ(BTB; branch target buffer)の問題のようですね。 暗号処理のクリティカルな処理最中のコンテキストスイッチではBTBを強制的に消したり、分岐結果をストアしないモードにいれたりすることはできないのかな?
    でも常時暗号処理を行っているような環境で動的な分岐予測ができなくなったらパフォーマンスに響きそうですね。

  • コアの数 (スコア:3, すばらしい洞察)

    by ken-1 (4041) on 2006年11月21日 1時58分 (#1061625)
    リンク先を読んだわけではない上に、超素人考えなのですが、前の
    ストーリーのときに思ったのは、これはキャッシュを共有するコア
    の数が２つだけだから可能なのではないか、ということです。

    基本的に「自分の足跡以外の足跡はあいつの足跡だから、あいつが
    どこにいったか推測できる」という発想だと思うので、あいつ以外
    の足跡も残っていれば、どれがあいつの足跡かわからなくなるので
    はないだろうか。

    • Re:コアの数 (スコア:0)

      by Anonymous Coward
      HTにせよBLBにせよ、悪意を持ったコードが、暗号化ロジックとかカーネルのようなクリティカルなコードと、キャッシュだかBLBだかで同居してしまえば、悪意プロセスはクリティカルな同居人を覗き見る事ができる（可能性がある）。

      特権にはCPUレベルでのガードのみならずOSレベルでの付与もあること、悪意を持ったプロセスがシステムに侵入できる時点でかなりアウトなこと。

      これらから総合して問題の中心はOSによる保護機能の無効化≒特権昇格と見てええんでしょうか？
  • Schneierが来週のWiredでこれについて書く [schneier.com]そうなのでそっちにも期待．
    コラム記事だし，内容はコトの詳細よりもインパクトについての分析が中心になると想像．

  • じぇんじぇんシリアスじゃない (スコア:0, オフトピック)

    by Anonymous Coward on 2006年11月20日 18時47分 (#1061364)
    それよりマトモなパスワード付けてくれ

  • 要約すると (スコア:0)

    by Anonymous Coward on 2006年11月20日 23時29分 (#1061548)
    シンプルな盗聴ツールができただけ？

  • 今こそ! (スコア:0)

    by Anonymous Coward on 2006年11月21日 11時43分 (#1061739)

    みんなでC7 [mycom.co.jp]を使おう！

    # ワイヤードロジックにしてしまえばOKとかいう話ではない？

  • メニーコア (スコア:0)

    by Anonymous Coward on 2006年11月21日 17時46分 (#1061992)
    例えばCellのSPEだとコアが完全に独立している上に、isolatedモードによって外部から内部のメモリやレジスタ類が保護されます。HyperThreading/SMTのような技術を使った高速化も手ですが、完全独立の小コアを大量に用意するメニーコアというのも、一つの解法かもしれません。

    本気でisolatedモードで保護しようと思うと、256kBのLSを越えるメモリを使う時に、暗号化・サニタイズをしなければ、真の安全性が確保出来ないのが問題ではあります。

  • もう、RSAと楕円は専用ICでやれと？ (スコア:0)

    by Anonymous Coward on 2006年11月24日 13時11分 (#1063875)
    とかいわれてもね。しかし国民一人一枚スマートカードというのも悪くない。旅券（パスポート）にはIC付くんでしょ？２１世紀の安心な情報社会を実現するためには、自由情報技術党を結成して社会運動に身を投じるしかないぞと。
typodupeerror

目玉の数さえ十分あれば、どんなバグも深刻ではない -- Eric Raymond