1

10^11の数値をハッシュできる完璧なハッシュ/一方向性関数を探すように頼まれました。ただし、組み込みデバイスを使用するため、関連するバケットを格納するためのメモリがないため、バケットなしで適切な(最小限の)完全なハッシュを作成できるかどうか疑問に思いました。

計画では、デバイスを使用して数値をハッシュし、ハッシュをオフセットとして使用するレインボーテーブルまたはファイルを使用します。

乾杯

編集:

私はいくつかのより多くの情報を提供しようとします:)

1)10^11は実際には10^10になっているため、簡単になります。この数値は可能な組み合わせです。したがって、0000000001から10000000000(10 ^ 10)までの数値を取得できます。

2)計画は、番号を安全にする一方向性関数の一部として、安全でない方法で送信できるようにすることです。次に、レインボーテーブルを使用してもう一方の端で元の番号を検索します。問題は、デバイスが一般的に使用するメモリが512k-4Megであるということです。

3)それは完璧でなければなりません-私たちは100%衝突することはできません。

Edit2:

4)暗号化はデバイスでは実際には不可能であると言われているため、暗号化を使用することはできません。可能であれば、キー管理は悪夢になります。

Edit3:

これは賢明ではないので、今は純粋に学術的な質問です(私は約束します)

4

2 に答える 2

7

さて、あなたはあなたが何をしようとしているのかを明確にしたので、私は私の答えを書き直しました。

要約すると、実際の暗号化アルゴリズムを使用します。

まず、ハッシュシステムが悪い考えである理由を説明します。

とにかく、あなたのハッシュシステムは何ですか?

私が理解しているように、提案されたシステムは次のようなものです。

組み込みシステム(これをCと呼びます)は、値スペースが10^11のある種のデータを送信しています。このデータは、ある種のサーバー(私はSと呼びます)に転送する際に機密を保持する必要があります。

あなたの提案は、値hash(salt + data)をSに送信することです。Sはレインボーテーブルを使用してこのハッシュを逆にし、データを回復します。saltCとSの両方に知られている共有値です。

これは暗号化アルゴリズムです

暗号化アルゴリズムは、要約すると、機密性を提供するアルゴリズムです。あなたの目標は守秘義務であるため、あなたの目標を満たすアルゴリズムは、これを含む暗号化アルゴリズムです。

これは非常に貧弱な暗号化アルゴリズムです

まず、やむを得ず衝突する可能性があります。さらに、衝突する値のセットは毎日異なります。

第2に、正規のサーバーSであっても、復号化はCPUとメモリを非常に多く消費します。ソルトの変更はさらにコストがかかります。

第三に、あなたが述べた目標は鍵管理を回避することですが、あなたの塩は鍵です!あなたは鍵管理をまったく解決していません。塩を持っている人なら誰でも、あなたと同じようにメッセージを解読することができます。

第4に、CからSまでしか使用できません。組み込みシステムCには、ハッシュを逆にするのに十分な計算リソースがなく、データを送信することしかできません。

これは、組み込みデバイスの実際の暗号化アルゴリズムよりも高速ではありません

最も安全なハッシュアルゴリズムは、悪くはないにしても、妥当なブロック暗号と同じくらい計算コストがかかります。たとえば、SHA-1では、512ビットブロックごとに次のことを行う必要があります。

  • 12個の32ビット変数を割り当てます。
  • 拡張メッセージに80個の32ビットワードを割り当てます
  • 64回:3つの配列ルックアップ、3つの32ビットXOR、およびローテーション操作を実行します
  • 80回:最大5つの32ビット二項演算を実行します(xor、and、or、not、andの組み合わせ、およびラウンドによって異なります)。次に、ローテーション、配列ルックアップ、4つの追加、別のローテーション、およびいくつかのメモリのロード/ストア。
  • 5つの32ビット2を実行します-補数の追加

メッセージの512ビットごとに1つのチャンクがあり、最後に余分なチャンクが存在する可能性があります。これは、チャンクあたり1136の二項演算(メモリ演算は含まない)、またはバイトあたり約16の演算です。

比較のために、RC4暗号化アルゴリズムでは、バイトごとに4つの操作(3つの追加とメッセージのxor)に加えて、2つの配列読み取りと2つの配列書き込みが必要です。また、SHA-1のピークが368バイトであるのに対し、必要な作業メモリーは258バイトのみです。

キー管理は基本です

機密保持システムでは、何らかの秘密が必要です。シークレットがない場合は、他の誰もが同じデコードアルゴリズムを実装でき、データは世界に公開されます。

したがって、秘密をどこに置くかについては2つの選択肢があります。1つのオプションは、暗号化/解読アルゴリズムを秘密にすることです。ただし、アルゴリズムのコード(またはバイナリ)がリークされた場合、失うことになります。そのようなアルゴリズムを置き換えることは非常に困難です。

したがって、シークレットは一般的に簡単に置き換えることができます。これがキーと呼ばれるものです。

提案されているハッシュアルゴリズムの使用にはソルトが必要です。これはシステム内の唯一の秘密であり、したがって重要です。好むと好まざるとにかかわらず、このキーは慎重に管理する必要があります。また、他のキーよりもリークされた場合、交換するのは非常に困難です。変更するたびに新しいレインボーテーブルを生成するために多くのCPU時間を費やす必要があります。

あなたは何をするべきか?

実際の暗号化アルゴリズムを使用し、実際に鍵管理について考えることに時間を費やしてください。これらの問題は以前に解決されています。

まず、実際の暗号化アルゴリズムを使用します。AESは、高性能および低RAM要件向けに設計されています。前に述べたように、RC4のようなストリーム暗号を使用することもできます。ただし、RC4で注意する必要があるのは、暗号からの出力の最初の4キロバイト程度を破棄する必要があることです。そうしないと、同じものに対して脆弱になります。 WEPを悩ませた攻撃。

次に、キー管理について考えます。1つのオプションは、各クライアントにキーを書き込むだけで、クライアントが危険にさらされた場合は、物理的に外に出て交換することです。すべてのクライアントに簡単に物理的にアクセスできる場合、これは合理的です。

それ以外の場合、中間者攻撃を気にしない場合は、Diffie-Hellman鍵交換を使用して、SとCの間で共有鍵をネゴシエートできます。MitMが心配な場合は、次のことを行う必要があります。ECDSAまたはDH交換から取得した鍵を認証するための何かを検討し始めます。ただし、その道を進み始めると、問題が発生しやすいことに注意してください。その時点でTLSを実装することをお勧めします。組み込みシステムの機能を超えているわけではありません。実際、すでに多数 の組み込み 商用(およびオープンソース) ライブラリが 利用可能です。TLSを実装しない場合は、少なくとも専門の暗号技術者にアルゴリズムを調べてから実装してもらいます。

于 2011-02-03T11:23:11.740 に答える
1

少なくとも入力と同じ数のハッシュバケットがない限り、「完璧な」ハッシュのようなものは明らかにありません。そうしないと、必然的に2つの入力が同じハッシュバケットを共有する可能性があります。

ただし、 0から10^11までのすべての数値を格納することはほとんどありません。それで、パターンは何ですか?パターンがある場合は、実際のデータセットに最適なハッシュ関数がある可能性があります。

ただし、とにかく「完璧な」ハッシュ関数を見つけることはそれほど重要ではありません。ハッシュテーブルは非常に高速です。衝突率が非常に低い関数(整数をハッシュする場合、つまりモジュラスなどのほぼすべての単純な関数)は問題なく、O(1)の平均パフォーマンスが得られます。

于 2011-02-03T10:33:49.413 に答える