1

Cで記述されたゲームのコードの脆弱性に関して、簡単な概念実証を実証しようとしています。

文字ログインを検証したいとしましょう。ログインは、ユーザーがグラフィカルメニューから項目を選択することによって処理されますn（今のところは仮定します）。n=5アイテムはすべて中世をテーマにしています：

例えば：

 _______________________________
|           |           |       |
| Bow       | Sword     | Staff |
|-----------|-----------|-------|
| Shield    | Potion    | Gold  |
|___________|___________|_______|

ユーザーは各アイテムをクリックしてから、各アイテムの番号を選択する必要があります。

次に、検証アルゴリズムは次のことを行います。

  1. 選択されたアイテムを決定します
  2. 各文字列を小文字にドロップします（つまり、次のようにBowなりますbow）
  3. 各文字列の単純な文字列ハッシュを計算します（つまり、 `bow => b = 2、o = 15、w = 23、sum =（2 + 15 + 23 = 40）
  4. ハッシュに、ユーザーが対応するアイテムに対して選択した値を掛けます。この新しい値は、key
  5. keys選択した各アイテムのを合計します。これが最終的な検証ハッシュです
  6. 重要：バリデーターは、ゼロ以外の倍数とともにこのハッシュを受け入れます（つまり、最終的なハッシュが1111に等しい場合、2222、3333、8888なども有効です）。

したがって、たとえば、次のように選択するとします。

Bow (1)
Sword (2)
Staff (10)
Shield (1)
Potion (6)

アルゴリズムは、これらの各文字列を小文字に落とし、文字列のハッシュを計算し、そのハッシュに各文字列に対して選択された数を掛けてから、これらのキーを合計します。

例えば：

Final_Validation_Hash = 1*HASH(Bow) + 2*HASH(Sword) + 10*HASH(Staff) + 1*HASH(Shield) + 6*HASH(Potion)

オイラー法を適用することにより、これらのハッシュが一意ではないことを実証する予定であり、それを証明するための簡単なアプリケーションを考案したいと思います。

私の場合、5つのアイテムについて、基本的に次のように計算しようとしています。

(B)(y) = (A_1)(x_1) + (A_2)(x_2) + (A_3)(x_3) + (A_4)(x_4) + (A_5)(x_5)

どこ：

B is arbitrary
A_j are the selected coefficients/values for each string/category
x_j are the hash values for each string/category
y is the final validation hash (eg: 1111 above)
B,y,A_j,x_j are all discrete-valued, positive, and non-zero (ie: natural numbers)

誰かがこの問題を解決するのを手伝ってくれるか、同様の例（つまり、コード、方程式を解くなど）を教えてもらえますか？最後のステップを解決する必要があります（つまり、（B）（Y）= ...）。

n最後に、レベルを深くしてから、残りのすべての可能な組み合わせのインクリメント、テストなどを処理する再帰アルゴリズムを作成しました。あまり効率的ではありませんが、機能します。リクエストに応じて提供できます（大きすぎてここに投稿できません）。

4

5 に答える 5

1

ほとんどのユーザーは、各アイテムにかなり小さい数を選択するように思われます（結局、「2」は「438483」よりも覚えやすいです）。

その制約を考えると、ブルートフォースはおそらく実際には合理的です。

5つのシンボルのすべての可能な入力値に加えて、1..99の範囲の数値を生成し、結果のハッシュを計算し、特定のハッシュを生成する個別の組み合わせの数を数える（たとえば、辞書を使用する）だけで、経験的な結果が得られます。最も可能性の高い入力値のハッシュ分布の理解。

そこから、実際に生成された個別のハッシュ値の数（ハッシュがInt32の場合は2 ^ 32の可能なハッシュ値から）を調べ、特定の頻度で生成されたハッシュ値（高い辞書で数えます）。

于 2012-06-12T16:18:36.187 に答える
1

x_jメニューの項目、係数A_j、検証ハッシュy、および選択した項目の数に応じて、一意である場合とそうでない場合がありますn。

たとえば、検証ハッシュがである場合はどうなります1か？次に、すべてが検証されます。

一方、nアイテムの総数がある場合、一意になる可能性のあるハッシュは1つだけです。

もちろん、これらは極端な例ですが、要点を示しています。それはあなたのパラメータに依存します。ブルートフォースを除いて、ハッシュが一意であるかどうかを検出するための単純な一般的な方法はありません。

于 2012-06-12T16:21:18.500 に答える
1

アルゴリズムはゼロ以外の倍数を受け入れるため、これは非常に簡単です。すべての入力に2を掛けると、競合が発生します。

Bow (1)
Sword (2)
Staff (10)
Shield (1)
Potion (6)

y = (A_1)(x_1) + (A_2)(x_2) + (A_3)(x_3) + (A_4)(x_4) + (A_5)(x_5)

次に、それらに2を掛けます。

Bow (2)
Sword (4)
Staff (20)
Shield (2)
Potion (12)

2(A_1)(x_1) + 2(A_2)(x_2) + 2(A_3)(x_3) + 2(A_4)(x_4) + 2(A_5)(x_5)
= 2((A_1)(x_1) + (A_2)(x_2) + (A_3)(x_3) + (A_4)(x_4) + (A_5)(x_5))
= 2y
于 2012-06-12T16:22:05.537 に答える
1

正式な証明ではありませんが、私には考えがあります。

異なる文字列のハッシュを、、h_1...h_2とするとh_n、線形和は次のようになります。

y = h_1 + h_2 + ... + h_n

一度取得すると、シリーズ内のとのペアで少なくともそのような、、、...をy常に見つけることができます。h_1'h_2'h_n'ij h_i != h_j'

したがって、最終的な合計を取得するために重複するh値を持つことができます。

繰り返しますが、各h値はいくつかの整数（文字の代表値）の線形合計から生成されるため、特定のh値は、異なる線形合計、つまり異なる文字列によって実現できます。

乗数の値は調整できます。また、乗数の値が一定である場合、つまり重複ハッシュジェネレータがそれを選択できない場合でも、乗数hを掛けた値は、掛けられたキーの合計が一定のままになるように変更できます。

したがって、多くの文字列から1つのハッシュを生成できます。

于 2012-06-12T16:23:00.247 に答える
1

最後の係数を除くすべてを1に設定すると、An * xn = r（mod y）の形式になり、拡張ユークリッドアルゴリズムを使用して解を見つけることができます。ウィキペディアを参照してください。

于 2012-06-12T16:37:53.220 に答える