シャバル

シャバルは、フランスが資金提供している研究プロジェクトSaphirがNISTのハッシュ関数に関する国際コンペティションに提出した暗号ハッシュ関数です

Saphirのパートナー

Saphirの研究パートナー（LIENSを除く）はShabalの構想を開始し、後に研究プロジェクトSaphir2のパートナーが加わり、Shabalの最終設計に積極的に貢献しました。Saphir（ハッシュプリミティブのセキュリティと分析）は、ハッシュ関数に関するANR資金提供プロジェクトです。Saphirは2006年3月に3年間のプロジェクトとして開始され、Cryptolog International、DCSSI、France Telecom（リーダー）、Gemalto、LIENSの5つのパートナーが参加しました。Saphir2のパートナーは産業界と学界の両方から来ており、Saphirのパートナーに加えて、EADS SN、INRIA、Sagem Sécurité、UVSQの4つの新しいパートナーがプロジェクトに加わり、貢献しました。^{[ 1 ]}

歴史

シャバルはNISTハッシュ関数コンペティションにエントリーされ、第2ラウンドまで進みましたが、決勝ラウンドには進出できませんでした。シャバルが決勝に選ばれなかったのは、主にセキュリティ上の懸念によるものです。ハッシュアルゴリズム全体のセキュリティは損なわれませんでしたが、低い時間計算量で非ランダム性の特性が発見されたことで、NISTの暗号学者の間では、将来的にさらに強力な攻撃が行われる可能性に対する懸念が生じました。^{[ 2 ]}

このアルゴリズムの名前はセバスチャン・シャバルに敬意を表して選ばれた。^{[ 1 ]}

説明

Shabalは、ワイドパイプのMerkle-Damgårdハッシュ構造の変種と見なせる演算モードを使用します。Shabalの内部状態は、A、B、Cで示される3つの部分で構成されます。Shabalの鍵付き順列は、相互に作用する非線形フィードバックシフトレジスタを使用してAとBを更新します。順列のメインループは、3と5のモジュラー乗算、モジュラー加算、XOR、補数演算、およびAND演算を使用します

シャバルの連鎖モードは次のように機能します: (A, B) ← PM,C

(A, B, C) ← (A, C – M, B)、

（A⊕W、B+M）、

ここで、Mはメッセージブロック、Wはカウンタである。すべてのメッセージブロックを処理した後、メッセージブロックとカウンタの値が固定される3回のファイナライズラウンドが適用される。Shabalには2つの調整可能なパラメータ(p, r)が定義されている。ここで、pはキー順列内で実行されるループの数、rはAのサイズである。(p, r)のデフォルト値は(3, 12)である。さらに、pとrは16p ≡ 0 mod rを満たす必要がある。Shabalのすべての出力サイズに対して、同じ内部関数が使用される。^{[ 2 ]}

シャバルの出力サイズ

ダイジェストの長さに基づいた Shabal の出力サイズは次のとおりです。

シャバル-192
シャバル-224
シャバル-256
シャバル-384
シャバル-512 ^{[ 1 ]}

シャバルの出力

シャバルハッシュの例：

シャバル-192: CB6E700F CE4DCF97 D2BBBF00 0C5364FB B40C8732 0D733948
シャバル-224: 14A6DD99 E8D207F9 F7187681 326F6930 8BCAAE00 25F4855F 3120BA43
シャバル-256: C0088FDA 9ABA672A 79D0BD56 07AE488E 095E2114 06855B3B 1877A349 A2543F99
シャバル-384: 3312DE9D DA850D91 03785C3A C611B112 5D1BCAFC 033755D2 3B8EE05E 15251E4E 636A724F F0A8E584 4AABEAAF 122FC0C4
シャバル-512: C6168015 0A3F1FC8 688DD952 8E9E2FED 23EF9578 BCE2A7CB A5D80961 E6C9E632 9701A5A6 F037B89F 20C6C44E DC7931E7 2BB5AB82 B3ADCD32 9CE25056 22305E98 ^{[ 1 ]}

セキュリティ

シャバルの鍵順列には様々な識別器が提案されています。キューブテスターを用いて、シャバルの鍵順列の統計的非ランダム性特性が時間計算量2300で記述されまし^た。^{[ 3 ]}
²¹⁷¹回の呼び出しを用いたシャバルの鍵付き順列に対する回転識別器が提示された。この識別器は、Pにおけるほとんどの演算が入力間の回転関係を保存するという観察に基づいている。しかし、非対称なIV、ブロックカウンタの追加、そしてファイナライズラウンドの存在のため、この攻撃をハッシュアルゴリズムに拡張することはできない。^{[ 4 ]}^{[ 5 ]}
3倍すると最上位ビットの差が確率1で保存されるという観察に基づく別の識別器が提示された。この観察を用いて、著者らは鍵付き順列の準等価鍵を見つける方法を提示した。関連鍵モデルの下では、著者らはまた、単一のクエリを用いてPとランダム順列を区別する方法も提示した。この方法は、任意のセキュリティパラメータに一般化できる。著者らはまた、ファイナライズにおける反復回数が36回ではなく24N回（N ≥ 2）であるShabalの変種において、擬似衝突と擬似2次原画像を見つける方法も提示した。しかし、この攻撃は元のShabalには通用しない。反復回数が36回の場合、差異を相殺することができないからである。^{[ 6 ]}
鍵付き順列Pには、検証が容易な非ランダム性特性がいくつか示されている。著者らは、Pの不動点を見つけるための簡便な手法を提案した。順列への入力は、順列内のループの影響を受けないように選択された。この手法は、Aのワード数やラウンド数に依存しないため、調整可能なセキュリティパラメータを任意に選択しても動作する。著者らはまた、鍵入力のみが異なる、多数の大規模な多重衝突を構築する方法を示した。^{[ 2 ]}
^223のデータ複雑度を持つ差分解析を使用して、偏った出力ビットの一部に識別子が提示されました。^{[ 7 ]}
Shabal圧縮関数に対する低重み（45ビット）擬似衝突攻撃（時間計算量2.84 ^）が提示された。セキュリティパラメータ（2, 12）を用いたShabal 5.12に対する原画像攻撃は、時間計算量^2.497 、メモリ計算量^2.400で実行された。^{[ 8 ]}
これらの識別器はいずれも、ハッシュアルゴリズムの安全性を直接脅かすものではありません。さらに、設計者は連鎖モードの非区別性安全性の証明を、理想的な暗号よりも弱い仮定を必要とするように修正しました。^{[ 2 ]}

実装

参考文献

^ ^a ^b ^c ^d Bresson, Emmanuel; Clavier, Christophe; Fuhr, Thomas; Icart, Thomas; Misarsky, Jean-Francois; Naya-Plasencia, Maria; Reinhard, Jean-Rene; Thuillet, Celine; Videau, Marion (2008-10-28). 「Shabal, a Submission to NIST's Cryptographic Hash Algorithm Competition」(PDF) : 2– 3, 20, 22, 32– 35{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
^ ^a ^b ^c ^d NIST 機関間報告書 7764 (2011年2月). 「SHA-3 暗号ハッシュアルゴリズムコンペティション第2ラウンドの現状報告」(PDF) : 20–21 .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要ですCS1 maint: 数値名: 著者リスト (リンク)
^ Aumasson, Jean-Philippe. 「Shabalの鍵付き順列の擬似乱数性について」(PDF) . 2018年11月14日閲覧。{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
^ Van Assche, Gilles (2010年3月24日). 「Shabalの鍵付き順列における回転識別器とセキュリティ証明への影響」(PDF) .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
^ Aerts, Nieke (2011年8月). 「ハッシュ関数の暗号解析 ― 特にSHA-3の候補であるShabalとBlakeについて」(PDF) : 56– 57.{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
^ Aumasson, Jean-Philippe; Mashatan, Atefeh; Meier, Willi. 「シャバルの順列についてさらに詳しく」(PDF) . 2018年11月14日閲覧。{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
^ Novotney, Peter (2010年7月20日). 「Shabalの順列関数の識別器」(PDF) .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
^磯部孝典、白井泰三. 「Shabalに対する低重み擬似衝突攻撃と縮小Shabal-512に対する原像攻撃」(PDF) . 2018年11月14日閲覧。{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です

外部リンク

[:1-1] Bresson, Emmanuel; Clavier, Christophe; Fuhr, Thomas; Icart, Thomas; Misarsky, Jean-Francois; Naya-Plasencia, Maria; Reinhard, Jean-Rene; Thuillet, Celine; Videau, Marion (2008-10-28). 「Shabal, a Submission to NIST's Cryptographic Hash Algorithm Competition」(PDF) : 2– 3, 20, 22, 32– 35{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です

[:0-2] NIST 機関間報告書 7764 (2011年2月). 「SHA-3 暗号ハッシュアルゴリズムコンペティション第2ラウンドの現状報告」(PDF) : 20–21 .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要ですCS1 maint: 数値名: 著者リスト (リンク)

[3] Aumasson, Jean-Philippe. 「Shabalの鍵付き順列の擬似乱数性について」(PDF) . 2018年11月14日閲覧。{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です

[4] Van Assche, Gilles (2010年3月24日). 「Shabalの鍵付き順列における回転識別器とセキュリティ証明への影響」(PDF) .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です

[5] Aerts, Nieke (2011年8月). 「ハッシュ関数の暗号解析 ― 特にSHA-3の候補であるShabalとBlakeについて」(PDF) : 56– 57.{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です

[6] Aumasson, Jean-Philippe; Mashatan, Atefeh; Meier, Willi. 「シャバルの順列についてさらに詳しく」(PDF) . 2018年11月14日閲覧。{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です

[7] Novotney, Peter (2010年7月20日). 「Shabalの順列関数の識別器」(PDF) .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です

[8] 磯部孝典、白井泰三. 「Shabalに対する低重み擬似衝突攻撃と縮小Shabal-512に対する原像攻撃」(PDF) . 2018年11月14日閲覧。{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]