問題タブ [constant-time]

環境

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

高レベルの 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コンパイラがシーケンスを過度に最適化するのを防ぐために、ある時点で型修飾子を含める必要があるかもしれませんが、それでも可能に思えます。

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

リストのプロパティ:

1. サイズ N である必要があります。ここで、N は整数の量です。

2. 空のセルはありません

3. 数字は完全に連続しているとは限りません (つまり、{-23,-15,-3,1,2,6,7,8,15,100})

4. 挿入/検索は一定時間内に行う必要があります。

私の最初の本能は、ハッシュ テーブルを使用することでしたが、これでは数字がスキップされた未使用のセルが作成されます。

そのリストに数値が存在するかどうかを一定時間チェックするために、そのようなリストを構築できる方法はありますか?

私は、C/C++ 標準に違反しない一定時間のローテーションを考え出すのにかなりの時間を費やしています。

問題は、操作がアルゴリズムで呼び出され、それらのアルゴリズムを変更できないエッジ/コーナー ケースです。たとえば、次はCrypto++からのもので、 GCC ubsan (つまりg++ fsanitize=undefined)でテスト ハーネスを実行します。

そしてのコードmisc.h:637：

Intel の ICC は特に冷酷で、関数呼び出し全体を削除し、y %= sizeof(T)*8. 数年前に修正しましたが、一定時間の解決策がないため、他のエラータはそのまま残しました。

残りの 1 つの問題点があります。の場合y = 0、条件 where を取得32 - y = 32し、未定義の動作を設定します。のチェックを追加するとif(y == 0) ...、コードは一定時間の要件を満たせなくなります。

Linux カーネルから他の暗号化ライブラリまで、他の多くの実装を見てきました。それらはすべて同じ未定義の動作を含んでいるため、行き止まりのように見えます。

最小数の命令でほぼ一定の時間で回転を実行するにはどうすればよいですか?

編集：ほぼ一定の時間までに、分岐を回避することを意味するため、同じ命令が常に実行されます。CPU マイクロコードのタイミングについては心配していません。分岐予測は x86/x64 では優れているかもしれませんが、組み込みなどの他のプラットフォームではうまく機能しない可能性があります。

GCCまたはClangがほぼ一定の時間で回転を実行する組み込み関数を提供する場合、これらのトリックは必要ありません。彼らにはそれさえないので、私は「回転を実行する」ことさえ解決します。

暗号関数を C から Java に移植したいと考えています。関数は一定時間内に実行する必要があるため、条件分岐(およびx に基づくテーブル ルックアップ) は許可されません。

元の C コードは次のとおりです。

したがって、「結果」は、「x==7」の場合は 1 に設定され、それ以外の場合は 0 に設定されます。「結果」変数は、その後の計算で使用されます。

これをJavaに転置する最良の方法を探しています。Java 式では、整数ではなくブール値に評価されるため、演算子を使用して上記をシミュレートする必要があります。

私は現在使用しています

私の x は範囲 {0,...,15} にあるので、これはうまくいきます。(シフト関数は下位 5 ビットのみを使用するため、x が大きすぎる場合に誤検知が発生することに注意してください。)

式は何百万回も評価されるため、たとえば、演算子を 3 つではなく 2 つだけ使用する巧妙なソリューションがあれば、全体の計算が高速になります。

Java.Util フォームの PriorityQueue を使用せずに、カスタム プライオリティ キューを実装する必要があります。insert、remove、および clear の 3 つの基本メソッドがあります。すべての操作は、一定時間 O (log n) で実行する必要があります。どうすればこれを達成できますか? これらの操作にはどのアルゴリズムを使用すればよいですか? 最後に、ジェネリック値を保持するためにどのタイプのコンテナを使用すればよいですか?

これは私がこれまでに行ったことです...

それほど多くはありません..しかし、助けていただければ幸いです!

これは、 Nifi ExecuteScriptのインポート モジュールのフォロー アップです。

私はpythonとnifiが初めてです。ExecuteScript プロセッサで Python スクリプトを実行しようとしています。

サーバーにアクセスしたい。だから私はparamikoクライアントを使いました。しかし、プロセッサを実行すると、session.write() の行に「constant_time という名前のモジュールがありません」というエラーが表示されます。「/usr/local/lib/python2.7/dist-packages/」の下にこのconstant_time.pyがありますが

sys.path に「/usr/local/lib/python2.7/dist-packages/」というパスもあります。「Module Directory」プロパティにもこのパスを指定しました。

これは私のコードです：

どんな助けでも大歓迎です。

特定の特定の検索が実行されると、回答が特定のページにハードコードされるように、サイトに次の JavaScript があります。

JavaScript の検索ステートメントは、case ステートメントの数または一定の時間に対して線形であるかどうか疑問に思っています。線形の場合、このコードを記述するより良い方法があるので、コーディングする特殊なケースの数に関係なく一定の時間になりますか?