ビットコイン・インスティテュート

Re: Hash()関数は​安全ではない

人物: mcdett
mcdett 2010年7月15日15:56 UTC

この関数でハッシュされているものは何か? <— これをxと呼ぶことにする

xの可能な総数がSHA256が提供する256ビット空間より小さければ、攻撃はすべてのsha256(x)値のテーブルという形になる。

xの可能な組み合わせがすべて256ビット空間より大きければ、以下の計算を参照してほしい(攻撃は既知のsha256(x)のテーブルではなく、ハッシュ値そのものに対するものになる):

以下はwww.atmel.com/dyn/resources/prod_documents/doc8668.pdfからの引用だ。

鍵が256ビットの場合、2^255回の試行後に攻撃者が正しい鍵を見つける確率は50%であり、2^256回の試行後にはすべての可能な鍵を試し終え、鍵の発見が保証される。

以下は大きな数の推定値だ:

2^66地球上の砂粒の数2^76宇宙の星の数2^79アボガドロ数。石炭12グラム中の炭素原子の数。2^96水1立方メートル中の原子の数2^190太陽の原子の数2^255上記の鍵値を見つけるための試行回数

では、米国国家安全保障局(NSA)のような潤沢な資金を持つ組織はどうか? 256ビットの鍵を解読するマシンを作れるだろうか? 理論的なナノコンピューターが毎秒10^13命令を実行でき(原子振動の概算速度)、一辺5.43nmの立方体の空間に収まると仮定する(これは幅10原子のシリコン格子、または1000個のシリコン原子を含む結晶の概算サイズだ)。1回の試行を10サイクルで計算できると仮定する。地球サイズのそのコンピューターでさえ、256ビットアルゴリズムに対する総当り攻撃には10^13年以上(地球の推定年齢の約58倍)かかるだろう。