楕円曲線のみのハッシュ

楕円曲線のみのハッシュ (ECOH)アルゴリズムは、 NIST ハッシュ関数コンペティションで SHA-3 の候補として提出されました。しかし、コンペティションの開始時に2 番目のプリイメージ攻撃が見つかったため、却下されました。

ECOH は、まだ攻撃に成功したことのないMuHASHハッシュ アルゴリズムに基づいています。しかし、MuHASH は実用には効率が悪すぎるため、変更する必要がありました。主な違いは、MuHASH がランダム オラクル^{[説明が必要]}を適用するのに対し、ECOH はパディング関数を適用することです。ランダム オラクルを想定すると、MuHASH で衝突を見つけることは、離散対数問題を解決することを意味します。したがって、MuHASH は証明可能なほど安全なハッシュです。つまり、衝突を見つけることは、既知の難しい数学的問題と 同じくらい難しいことがわかっています。

ECOH はランダムオラクルを使用せず、そのセキュリティは離散対数問題と厳密には直接関係ありませんが、それでも数学関数に基づいています。ECOH は、バイナリ体上の和多項式方程式の低次解を見つけるセマエフの問題に関連しており、和多項式問題と呼ばれます。この問題を解く効率的なアルゴリズムは今のところ示されていません。この問題がNP 困難であることは証明されていませんが、そのようなアルゴリズムは存在しないものと想定されています。特定の仮定の下では、ECOH での衝突を見つけることは、サブセット和問題の例と見なすこともできます。和多項式問題を解決することに加えて、2 番目の原像、つまり衝突を見つける別の方法、ワグナーの一般化誕生日攻撃が存在します。

ECOH は、ハッシュを取得するためにビットをアドホックに混合する従来の方法ではなく、 数学関数 (証明可能なセキュリティアプローチを使用) に基づいたハッシュ関数の良い例です。

が与えられた場合、ECOH はメッセージをブロックに分割します。最後のブロックが不完全な場合は、1 が 1 つ埋め込まれ、その後適切な数の 0 が埋め込まれます。さらに、メッセージ ブロックと整数を楕円曲線点にマッピングする関数を とします。次に、マッピング を使用して、各ブロックは楕円曲線点に変換され、これらの点がさらに 2 つの点と加算されます。1 つの追加点には埋め込みが含まれ、メッセージ長のみに依存します。2 つ目の追加点は、メッセージ長とすべてのメッセージ ブロックの XOR に依存します。結果はハッシュ を取得するために切り捨てられます。 ${\displaystyle n}$${\displaystyle M}$${\displaystyle n}$${\displaystyle M_{0},\ldots ,M_{n-1}}$${\displaystyle P}$${\displaystyle P}$${\displaystyle P_{i}}$${\displaystyle X_{1}}$${\displaystyle X_{2}}$${\displaystyle H}$

${\displaystyle {\begin{aligned}P_{i}&{}:=P(M_{i},i)\\X_{1}&{}:=P'(n)\\X_{2}&{}:=P^{*}(M_{i},n)\\Q&{}:=\sum _{i=0}^{n-1}P_{i}+X_{1}+X_{2}\\R&{}:=f(Q)\end{aligned}}}$

2 つの追加ポイントは、およびによって計算されます。は、すべての楕円曲線ポイントと 2 つの追加ポイントを加算します。 最後に、結果は出力変換関数 f に渡され、ハッシュ結果 が得られます。 このアルゴリズムの詳細については、「ECOH: 楕円曲線のみのハッシュ」を参照してください。 ${\displaystyle P'}$${\displaystyle P^{*}}$${\displaystyle Q}$${\displaystyle R}$

ECOH アルゴリズムとして、ECOH-224、ECOH-256、ECOH-384、ECOH-512 の 4 つが提案されています。数字はメッセージ ダイジェストのサイズを表します。これらは、パラメータの長さ、ブロック サイズ、使用する楕円曲線が異なります。最初の 2 つは楕円曲線 B-283: を使用し、パラメータは ( 128, 64, 64) です。ECOH-384 は曲線 B-409: を使用し、パラメータは (192, 64, 64)です。ECOH-512 は曲線 B-571: を使用し、パラメータは (256, 128, 128) です。最大 ビット長のメッセージをハッシュできます。 ${\displaystyle X^{283}+X^{12}+X^{7}+X^{5}+1}$${\displaystyle X^{409}+X^{87}+1}$${\displaystyle X^{571}+X^{10}+X^{5}+X^{2}+1}$${\displaystyle 2^{128}}$

• 増分性: メッセージに小さな変更があり、ECOH 計算に中間値がある場合、メッセージの ECOH を迅速に更新できます。
• 並列化可能性: これは、計算が並列システム上で実行できることを意味します。${\displaystyle P_{i}'s}$
• 速度: ECOH アルゴリズムはSHA-1より約 1000 倍遅いです。ただし、デスクトップ ハードウェアの並列化とキャリーレス乗算の進歩を考えると、数年後には長いメッセージの場合、ECOH は SHA-1 と同等の速度になる可能性があります。短いメッセージの場合、大規模なテーブルを使用しない限り、ECOH は比較的低速です。

ECOH ハッシュ関数は具体的な数学関数に基づいています。衝突を見つけるという問題が、既知の困難な数学問題 (部分集合和問題) に還元できるように設計されています。つまり、衝突を見つけることができれば、困難で多項式時間では解決できないと想定されている根本的な数学問題を解くことができます。これらの特性を持つ関数は証明可能に安全であることが知られており、他のハッシュ関数の中でも非常にユニークです。しかし、証明で与えられた仮定が強すぎたため、後に 2 番目の原像 (つまり衝突) が見つかりました。

衝突または第 2 原像を見つける 1 つの方法は、セマエフ総和多項式を解くことです。与えられた楕円曲線 E に対して、変数に関して対称で、 内の和が 0 になる点の横座標で評価したときにちょうどゼロになる多項式が存在します。今のところ、この問題を解く効率的なアルゴリズムは存在せず、困難であると考えられています (ただし、NP 困難であることは証明されていません)。 ${\displaystyle f_{n}}$${\displaystyle n}$${\displaystyle E}$

より正式には、を有限体、を に係数を持つワイエルシュトラス方程式を持つ楕円曲線、を無限大点とします。となる< が存在する場合のみ、多変数多項式が存在することが知られています。 この多項式は各変数に次数を持ちます。 問題は、この多項式を見つけることです。 ${\displaystyle \mathbf {F} }$${\displaystyle E}$${\displaystyle \mathbf {F} }$${\displaystyle O}$${\displaystyle f_{n}(X_{1},\ldots,X_{N})}$${\displaystyle y_{1},\ldots ,y_{n}}$${\displaystyle (x_{1},y_{1})+\ldots +(x_{n},y_{n})=O}$${\displaystyle 2^{n-2}}$

ECOH における衝突を見つける問題は、サブセット和問題に似ています。サブセット和問題を解くのは、離散対数問題とほぼ同じくらい難しいです。これは多項式時間では実行できないと一般に考えられています。ただし、かなり緩いヒューリスティックを想定する必要があります。より具体的には、計算に含まれるパラメータの 1 つは必ずしもランダムではなく、特定の構造を持っています。この緩いヒューリスティックを採用すると、内部 ECOH 衝突を見つけることは、サブセット和問題の例と見なすことができます。

2 番目の原像攻撃は、一般化誕生日攻撃の形で存在します。

攻撃の説明: これは、ワグナーの一般化誕生日攻撃です。ECOH -224 と ECOH-256 では2 ^{143時間、ECOH-384 では 2 206}時間、ECOH-512 では 2 ²⁸⁷時間かかります。この攻撃では、チェックサム ブロックを固定値に設定し、楕円曲線ポイントの衝突検索を使用します。この攻撃では、メッセージMがあり、同じメッセージにハッシュされるM'を見つけようとします。最初に、メッセージ長を 6 つのブロックに分割します。つまり、です。K を自然数とします。に対してK個の異なる数値を選択し、で定義します。K個の対応する楕円曲線ポイントを計算してリストに格納します。次に、 に対してK個の異なるランダム値を選択し、 を定義し、 を計算して、2 番目のリストに格納します。ターゲットQ は既知であることに注意してください。 は、固定したメッセージの長さにのみ依存します。は、すべてのメッセージ ブロックの長さと XOR に依存しますが、これが常にゼロになるようにメッセージ ブロックを選択します。したがって、はすべての試行で固定されます。 ${\displaystyle M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})}$${\displaystyle (M_{0},M_{1})}$${\displaystyle M_{2}}$${\displaystyle M_{2}:=M_{0}+M_{1}}$${\displaystyle P(M_{0},0)+P(M_{1},1)+P(M_{2},2)}$${\displaystyle (M_{3},M_{4})}$${\displaystyle M_{5}:=M_{3}+M_{4}}$${\displaystyle Q-X_{1}-X_{2}-P(M_{3},3)-P(M_{4},4)-P(M_{5},5)}$${\displaystyle X_{1}}$${\displaystyle X_{2}}$${\displaystyle X_{2}}$

K が楕円曲線上の点の数の平方根より大きい場合、 2 つのリストの間に1 つの衝突が予想されます。これにより、 次のメッセージが表示されます。 これは、このメッセージがターゲット値Qにつながり、2 番目のプリイメージ (これが問題) につながることを意味します。ここで実行する必要がある作業量は、K の部分ハッシュ計算の 2 倍です。詳細については、「楕円曲線のみのハッシュ (ECOH) に対する 2 番目のプリイメージ攻撃」を参照してください。 ${\displaystyle (M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})}$${\displaystyle Q=\sum _{i=0}^{5}P(M_{i},i)+X_{1}+X_{2}}$

実際のパラメータ:

• ECOH-224 と ECOH-256 は、曲線上に約 個の点がある楕円曲線 B-283 を使用します。 を選択して、複雑度 の攻撃を取得します。${\displaystyle 2^{283}}$${\displaystyle K=2^{142}}$${\displaystyle 2^{143}}$
• ECOH-384は、曲線上に約点を持つ楕円曲線B-409を使用します。選択すると、複雑な攻撃が可能になります。${\displaystyle 2^{409}}$${\displaystyle K=2^{205}}$${\displaystyle 2^{206}.}$
• ECOH-512は、曲線上に約点を持つ楕円曲線B-571を使用します。選択すると、複雑な攻撃が可能になります。${\displaystyle 2^{571}}$${\displaystyle K=2^{286}}$${\displaystyle 2^{287}.}$

ECOH に関する公式コメントには、ECOH2 と呼ばれる提案が含まれていました。これは、Halcrow-Ferguson の第二原像攻撃を阻止するために楕円曲線のサイズを 2 倍にし、パフォーマンスの向上または同様のパフォーマンスが予測されるものです。

• Daniel RL Brown、Matt Campagna、Rene Struik (2008)。「ECOH: 楕円曲線のみのハッシュ」。
• Michael A. Halcrow、Niels Ferguson (2009)。「楕円曲線のみのハッシュ (ECOH) に対する 2 番目のプリイメージ攻撃」。