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倍）かかるだろう。
この関数でハッシュされているものは何か？ <— これをxと呼ぶことにする
xの可能な総数がSHA256が提供する256ビット空間より小さければ、攻撃はすべてのsha256(x)値のテーブルという形になる。
-
その計算は可逆コンピューティングの進歩をまったく考慮していない。これらの技術は、従来のコンピューターでは不可能なアルゴリズムを活用することで、探索空間を半分にできる可能性がある。
-
その計算はアルゴリズムが完全に安全であることを前提としている。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 に弱点が徐々に見えてきた場合、特定のブロック番号以降に新しいハッシュ関数に移行できる。全員がそのブロック番号までにソフトウェアをアップグレードする必要がある。新しいソフトウェアはすべての古いブロックの新しいハッシュを保持し、同じ古いハッシュを持つ別のブロックに置き換えられないようにする。