Hash()関数は安全ではない
やあ、
util.hのHash()関数はBitcoinの暗号化の大部分の基盤となっている：
template<typename T1>
inline uint256 Hash(const T1 pbegin, const T1 pend)
{
uint256 hash1;
SHA256((unsigned char*)&pbegin[0], (pend - pbegin) * sizeof(pbegin[0]), (unsigned char*)&hash1);
uint256 hash2;
SHA256((unsigned char*)&hash1, sizeof(hash1), (unsigned char*)&hash2);
return hash2;
}ご覧の通り、これは2回ハッシュすることでより安全にしようとしている。しかし、これは実際にはセキュリティを低下させる。純粋なSHA256を破るには、攻撃者は既知のdに対してSHA256(d’) == SHA256(d)となるd’を見つける必要がある。これはHash()を破るのにも十分だ。しかし攻撃者はハッシュの外側の層を攻撃することもでき、SHA256(d’) != SHA256(d)であってもSHA256(SHA256(d’)) == SHA256(SHA256(d))となるd’を見つけることができる。このように、二重ハッシュはハッシュを破ることを_より容易に_している！
より良い解決策は以下のようなものだろう：
template<typename T1>
inline vector<unsigned char> HashV(const T1 pbegin, const T1 pend)
{
uint256 sharesult;
uint160 riperesult;
SHA256((unsigned char*)&pbegin[0], (pend - pbegin) * sizeof(pbegin[0]), (unsigned char *)&sharesult);
RIPEMD160((unsigned char*)&pbegin[0], (pend - pbegin) * sizeof(pbegin[0]), (unsigned char *)&riperesult);
vector<unsigned char> ret;
ret.insert(ret.end(), (unsigned char *)(&sharesult), (unsigned char *)(&sharesult + 1));
ret.insert(ret.end(), (unsigned char *)(&riperesult), (unsigned char *)(&riperesult + 1));
return ret;
}鍵は、ハッシュを混ぜ合わせるのではなく、並べてつなぐことだ。これにより攻撃者は両方のハッシュを破る必要がある - 最悪の場合でも、単一のハッシュよりも安全性が低くなることはない。
残念ながら、ハッシュを変更するとチェーンが壊れてしまうが……
この関数でハッシュされているものは何か？ <— これを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倍）かかるだろう。
…
2^255上記の鍵値を見つけるための試行回数
-
その計算は可逆コンピューティングの進歩をまったく考慮していない。これらの技術は、従来のコンピューターでは不可能なアルゴリズムを活用することで、探索空間を半分にできる可能性がある。
-
その計算はアルゴリズムが完全に安全であることを前提としている。NISTがSHA-3の開発にかなり積極的であることを考えると、その分析にはあまり確信が持てない。
-
攻撃者はシステムを侵害するために特定の鍵を見つける必要はなく、誰かのウォレットの鍵を見つけるだけでよい。これを地球の人口と企業アカウントにとって実用的な通貨にしたいなら、探索空間は10^10から10^12減少する。
2^256の探索空間は、今世紀末までに2^110の範囲まで削られる可能性がある。完全性に対する重大な攻撃が存在しないと仮定してだが。
正直なところ、このプログラムの技術的健全性にはあまり納得していない。なぜSHA256を使い、WhirlpoolやSHA512ではないのか？
正直なところ、このプログラムの技術的健全性にはあまり納得していない。なぜSHA256を使い、WhirlpoolやSHA512ではないのか？
SHA1024やSHA2048やSHA4048やSHA1000000000000000000000000000000000を使わなかったのと同じ理由だ。
理論上の攻撃はたくさんあるが、あるプログラムや新しい数学的証明が解読にかかる時間を半分にできたとして、暗号の解読に1000億年かかるところが、この新しい攻撃（数学、攻撃、欠陥を適宜挿入）でたった10億年になることを本当に心配するのか？ 100万年ならどうだ？ 10万年でも？
SHA256が10分以内に解読できるようになったら心配するが、それまでは時間は味方だ。
SHA1024やSHA2048やSHA4048やSHA1000000000000000000000000000000000を使わなかったのと同じ理由だ。
違う。SHA512とWhirlpoolは存在し、明確に定義され、十分にサポートされ、十分に分析されており、存在する理由がある。
可逆計算技術はエントロピー限界を「かいくぐる」。つまり、現在のコンピューターで可能なものをはるかに超える実効速度に達することができる。事実上、非決定論的な演算が可能になるのだ。
基本的に、AESで行われたように有効ビット長を半減させる手段を誰も開発しないことに経済全体（Bitcoinが成功すると信じるなら）を賭けていることになる。
軽率だ。
SHA256にわずかな欠陥しかないと仮定して、10年だ。
もし重大な欠陥があれば（SHA-3への推進を見よ）、はるかに深刻な問題になる。基本アルゴリズムの侵害に対処する明確なメカニズムが存在しないようであり、あるべきだ。
可逆計算技術はエントロピー限界を「かいくぐる」。つまり、現在のコンピューターで可能なものをはるかに超える実効速度に達することができる。事実上、非決定論的な演算が可能になるのだ。
ちょっと待って？ 可逆計算は消費エネルギーが少ないだけだと思っていた。非決定性はどこから来るの？
それと、ハッシュの安全性について：WikipediaによるとSHA-256への攻撃にはまだ2^250程度の操作が必要だ。それに、ここで大きな思い違いをしていなければ、ハッシュターゲットは約10分ごとに変わるのではないか？ それは攻撃者を混乱させないだろうか？ SHAをより速く破ることが可能になったとしても、システムが難易度を上げることで調整するのではないか？
ちょっと待って？ 可逆計算は消費エネルギーが少ないだけだと思っていた。非決定性はどこから来るの？
それはどこまでできるかの理論的限界だ。ブルートフォース検索を行う際、以前の任意の状態に戻って新しい状態を試すことができる。
すべてのコインが鋳造される前にSHA2がそこまで破られることはおそらくない。問題は、誰かの銀行口座を乗っ取るのにいくらかかるかということになる。
SHA256は128ビットから160ビットへのステップとは違う。
アナロジーを使うと、32ビットから64ビットのアドレス空間へのステップに近い。16ビットコンピューターではすぐにアドレス空間を使い果たし、32ビットコンピューターでは4GBでアドレス空間を使い果たしたが、だからといって64ビットですぐに使い果たすということにはならない。
SHA256は私たちの生涯においてムーアの法則による計算能力の向上では破られない。もし破られるとすれば、何らかの画期的な解読手法によるものだろう。SHA256を計算可能な範囲にまで完全に打ち負かすような攻撃は、SHA512も同様に破壊する可能性が高い。
SHA256に弱点が徐々に見えてきた場合、特定のブロック番号以降に新しいハッシュ関数に移行できる。全員がそのブロック番号までにソフトウェアをアップグレードする必要がある。新しいソフトウェアはすべての古いブロックの新しいハッシュを保持し、同じ古いハッシュを持つ別のブロックに置き換えられないようにする。
