21

環境

OpenSSLの機能 BN_consttime_swapは美しいものです。このスニペットでは、またはconditionとして計算されています。0(BN_ULONG)-1

#define BN_CONSTTIME_SWAP(ind) \
    do { \
            t = (a->d[ind] ^ b->d[ind]) & condition; \
            a->d[ind] ^= t; \
            b->d[ind] ^= t; \
    } while (0)
…
    BN_CONSTTIME_SWAP(9);
…
    BN_CONSTTIME_SWAP(8);
…
    BN_CONSTTIME_SWAP(7);

高レベルの bignum 操作に一定の時間がかかるようにするために、この関数は 2 つの bignum を交換するか、一定の時間内にそのままにしておくことが意図されています。それらをそのままにしておくと、実際に各 bignum の各単語を読み取り、古い単語と同一の新しい単語を計算し、その結果を元の場所に書き戻します。

これには、bignum が効果的に交換された場合と同じ時間がかかることが意図されています。

この質問では、Agner Fog が最適化マニュアルで説明しているような最新の広範なアーキテクチャを想定しています。C コードからアセンブリへの直接的な変換 (C コンパイラーがプログラマーの努力を台無しにすることなく) も想定されています。

質問

上記の構成が「ベスト エフォート」型の一定時間実行として特徴付けられるのか、それとも完全な一定時間実行として特徴付けられるのかを理解しようとしています。

a特に、関数が呼び出されたときに bignum がすでに L1 データ キャッシュにあり、BN_consttime_swap関数が返された直後のコードがすぐに bignum で作業を開始するというシナリオが懸念されaます。最新のプロセッサでは、bignumaが使用されたときにコピーが技術的に終了しないように、同時に十分な数の命令を実行できます。BN_consttime_swapへの呼び出しの後の命令が動作するようにするメカニズムaは、メモリ依存スペキュレーションです。議論のために単純なメモリ依存の推測を仮定しましょう。

質問が要約すると、これは次のとおりです。

BN_consttime_swapメモリから読み取られた後、投機に反して関数内に書き込まれたコードをプロセッサが最終的に検出した場合、プロセッサはアドレスが書き込まれたことを検出するとすぐに投機的実行をキャンセルしますか、それともそれ自体を許可しますか?書き込まれた値が既に存在していた値と同じであることを検出したときにそれを保持するには?

最初のケースでは、BN_consttime_swap完全な定数時間を実装しているように見えます。2 番目のケースでは、ベストエフォートの定数時間のみです。bignum がスワップされていない場合、への呼び出しの後に来るコードの実行は、スワップBN_consttime_swapされている場合よりもかなり高速になります。

2 番目のケースでも、これは、2 つの bignum のそれぞれの単語ごとに、2 つの可能な final とは異なる値を書き込むことによって、近い将来 (プロセッサが十分に素朴である限り) 修正できるように見えるものです。古い値または新しい値を再度書き込む前に値を変更します。通常のvolatileコンパイラがシーケンスを過度に最適化するのを防ぐために、ある時点で型修飾子を含める必要があるかもしれませんが、それでも可能に思えます。

注:ストア転送については知っていますが、ストア転送はショートカットにすぎません。後に来るはずの書き込みの前に読み取りが実行されることを防ぎません。そして、状況によっては失敗しますが、この場合は期待できません。

4

3 に答える 3

17

C コードからアセンブリへの直接的な変換 (C コンパイラーがプログラマーの努力を台無しにすることなく) も想定されています。

それがあなたの質問の核心ではないことは知っていますし、あなたがこれを知っていることも知っていますが、少し怒鳴る必要があります. これは、一定時間の実行を提供するための「ベスト エフォート」の試みとは言えません。コンパイラは の値をチェックするライセンスを取得しており、がゼロconditionの場合はすべてをスキップします。conditionの設定を難読化するとcondition、これが発生する可能性は低くなりますが、保証はされません。

「一定時間」のコードは、C で書くべきではないと言われています。今日が一定の時間であっても、テストするコンパイラーでは、よりスマートなコンパイラーがやって来て、あなたを打ち負かします. あなたのユーザーの 1 人は、あなたより先にこのコンパイラを使用しますが、あなたがさらしたリスクに気付かないでしょう。私が認識している定数時間を実現する方法は、正確に 3 つあります。それは、専用ハードウェア、アセンブリ、またはマシン コードを生成する DSL と定数時間実行の証明です。

さておき、実際のアーキテクチャの問題について: ばかばかしいほど単純なコンパイラを想定すると、このコードは、問題を評価するのに十分なほど精通している µarches で一定の​​時間です。パワー。保存されている値がすでに存在する値と一致するかどうかをストア キューまたはキャッシュでチェックし、条件付きでストアを短絡するか、すべてのストアでキャッシュ ラインのダーティ化を回避することは、まれに発生する場合に節約されるよりも多くのエネルギーを消費することを期待しています。仕事を避けるために。ただし、私は CPU 設計者ではなく、彼らの代わりに話すつもりもないので、これを大さじ数杯の塩と一緒に取り、これが真実であると仮定する前に相談してください。

于 2015-03-19T16:18:29.647 に答える
3

このブログ投稿、およびこの質問の主題に関する著者のヘンリーによるコメントは、誰もが期待できるように、信頼できるものと見なす必要があります。アーカイブのためにここで後者を再現します。

同じ値でメモリの場所を上書きする場合は実用的ではないと思いました。その答えは、現在のプロセッサでは、ストアの価値は関係なく、住所だけが重要であるということだと思います。

ここ学界では、メモリの曖昧さを解消するための 2 つのアプローチについて聞いたことがあります。アドレスベースまたは値ベースです。私の知る限り、現在のプロセッサはすべてアドレスベースの曖昧さ回避を行っています。

現在のマイクロベンチマークには、値が関連していないという証拠があると思います。多くの場合、同じ値を同じ場所に繰り返し格納する必要があります (特にオフセット = 0 の場合)。これらは異常に高速ではありませんでした。

アドレス ベースのスキームでは、ストア キューとロード キューを使用して未処理のメモリ操作を追跡します。ロードはストア キューをチェックしてアドレスの一致を確認し (このロードはキャッシュから読み取る代わりにストアからロードへの転送を行うべきか?)、ストアはロード キューをチェックします (このストアは後で実行を許可したロードの場所を破壊しましたか?)早い？）。これらのチェックは、完全にアドレス (ストアとロードが衝突した場所) に基づいています。このスキームの利点の 1 つは、ストア キュー検索もそこで使用されるため、ストアからロードへの転送に加えて、かなり単純な拡張であることです。

値ベースのスキームは、連想検索を取り除きます (つまり、高速、低電力など) が、ストアからロードへの転送を行うには、より優れた予測子が必要です (検索ではなく、転送するかどうか、どこに転送するかを推測する必要があります。 SQ)。これらのスキームは、コミット時にロードを再実行し、それらの値が正しいかどうかをチェックすることで、順序付け違反 (および不正な転送) をチェックします。これらのスキームでは、競合するストアがある (またはその他の間違いを犯した) 場合でも正しい結果値が得られた場合、順序違反として検出されません。

将来のプロセッサは価値ベースのスキームに移行できますか? 私は彼らがそうかもしれないと思います。これらは、メモリ実行ハードウェアの複雑さを軽減するために、2000 年代半ば (?) に提案されました。

于 2015-04-29T16:50:34.533 に答える
1

一定時間の実装の背後にある考え方は、実際にはすべてを一定時間で実行することではありません。これは、順不同のアーキテクチャでは決して起こりません。要件は、タイミング分析によって機密情報が明らかにならないことです。これを防ぐには、基本的に次の 2 つの要件があります。

a) ループの停止条件として、または分岐の述語として秘密を使用しないでください。そうしないと、分岐予測攻撃を受けやすくなりますhttps://eprint.iacr.org/2006/351.pdf

b) メモリ アクセスのインデックスとして秘密のものを使用しないでください。これは、キャッシュ タイミング攻撃につながります http://www.daemonology.net/papers/htt.pdf

あなたのコードに関して:あなたの秘密が「条件」であり、おそらくaとbの内容であると仮定すると、その実行はa、b、および条件の実際の内容に依存しないという意味で、コードは完全に一定時間です。もちろん、メモリ内の a と b の局所性はループの実行時間に影響しますが、シークレットである CONTENTS には影響しません。もちろん、条件が一定時間で計算されたと仮定しています。C の最適化に関して: コンパイラは、既知の情報に基づいてコードを最適化することしかできません。「条件」が本当に秘密の場合、コンパイラはその内容を識別して最適化することはできません。コードから差し引ける場合、コンパイラは 0 ケースの最適化を行う可能性が高くなります。

于 2015-04-03T16:38:49.323 に答える