コインの窃盗
現在の実装のビットコインには、かなり重大な暗号学上の欠陥があると思います。今すぐ悪用可能かどうかはわかりません（私は本物の暗号ハッカーではありません）が、近い将来に悪用される可能性は十分にあります。
この欠陥により、任意のビットコインアドレスからコインを匿名で窃盗することが可能になります。なお、既存の暗号システムを安全に保つ困難な問題を解くことは含まれていません。これは単に実装における潜在的な修正可能な論理的欠陥です。
ビットコインの成功を望んでいるので、公の場で欠陥について大声で騒ぎ立てたくはありません。このような問題を議論するための適切な場はありますか？
修正されるか、動作しないと証明されたら、詳細をここに投稿してもらえないか？とても気になる。=)
Red、先に非公開で教えてくれてありがとう！投稿してくれ（そして皆のサスペンスを解消してくれ！）
彼のポイントは、ビットコインアドレスに支払われたトランザクションはハッシュ関数と同程度の安全性しかないということだ。ビットコインアドレスを短くするために、公開鍵そのものではなく公開鍵のハッシュになっている。攻撃者はECDSAではなくハッシュ関数を破るだけで済む。
サトシは私のシナリオでもハッシュ関数が破られることが前提だと指摘した。それは正しいが、それに成功した事例があることを知って驚いた。MD4やMD5は明らかな例だ。しかし、SHA-1やSHA-256のような同系統のアルゴリズムの衝突攻撃の研究も進んでいる。
Bitcoinのこの部分ではどのハッシュが使われているのか？
彼はまた、生成された鍵ペア以外のものを使えるかについて懐疑的だ。
この点については、単純な数学の問題だとかなり確信している。文書の「ブラインド署名」について学ぶまで、十分に注意を払っていなかった。
実は、文書を乱数で掛け算し、その混ぜ合わされたファイルに誰かに署名してもらい、最後にその署名から乱数を割って取り除くと、結果は元の文書に対する有効な署名のままだ。まさかそれがうまくいくとは！
とにかく、鍵ペアが素数のペアに基づいている場合にのみ安全だとすれば、数が素数でなくても数学自体は何も変わらない。ただ因数分解がはるかに容易になるだけだ。
暗号の専門家に私が馬鹿だと証明してもらえたら本望だ。同じ関連に依拠した以前のプロジェクトのいくつかの機能にも影響する。その時もこれには気づかなかった。
素晴らしい。オープンソースが好きなもう1つの理由
私の理解では、間違っていれば訂正してほしい：
公開鍵のハッシュは実際の公開鍵自体より小さいので、ハッシュに一致する衝突を見つけるだけでよく、その衝突が見つかれば公開鍵/秘密鍵のペアが分かる。そして既知のペアを使ってコインを使えば、他のクライアントはハッシュが被害者のハッシュと一致していることだけを確認するので、有効な転送だと考える。そしてそのトランザクションは永久に記録される。
現在ハッシュは35文字の英数字だ。 26（大文字）+26（小文字）+10（数字）= 1文字あたり62通り つまり541,638,008,296,341,754,635,824,011,376,225,346,986,572,413,939,634,062,667,808,768通りの組み合わせがある。
つまり、本来の秘密鍵/公開鍵に対するブルートフォースと比べて約半分の作業量だ。将来への備えは損にならない Wink
Quote from: Red on July 25, 2010, 07:22:14 PM
サトシは私のシナリオでもハッシュ関数が破られることが前提だと指摘した。それは正しいが、それに成功した事例があることを知って驚いた。MD4やMD5は明らかな例だ。しかし、SHA-1やSHA-256のような同系統のアルゴリズムの衝突攻撃の研究も進んでいる。
Bitcoinのこの部分ではどのハッシュが使われているのか？
彼はまた、生成された鍵ペア以外のものを使えるかについて懐疑的だ。
この点については、単純な数学の問題だとかなり確信している。文書の「ブラインド署名」について学ぶまで、十分に注意を払っていなかった。
実は、文書を乱数で掛け算し、その混ぜ合わされたファイルに誰かに署名してもらい、最後にその署名から乱数を割って取り除くと、結果は元の文書に対する有効な署名のままだ。まさかそれがうまくいくとは！
とにかく、鍵ペアが素数のペアに基づいている場合にのみ安全だとすれば、数が素数でなくても数学自体は何も変わらない。ただ因数分解がはるかに容易になるだけだ。
暗号の専門家に私が馬鹿だと証明してもらえたら本望だ。同じ関連に依拠した以前のプロジェクトのいくつかの機能にも影響する。その時もこれには気づかなかった。
彼らがあまり言及しないのは、衝突生成にはまだ大量のCPU時間がかかるということだ。
公開鍵123456がハッシュABCDを生成し、 公開鍵654321もハッシュABCDを生成すると分かっても、 秘密鍵はまだ持っていない。
しかしあなたの言うことからすると、公開鍵654321さえあれば、公開鍵123456のふりをしてコインを使えるということか。
聞いたところでは、bitcoinはビットコインアドレスの生成に160ビットハッシュの1つを使っている。
SHA-1ファミリーのハッシュアルゴリズムは最も広く使われているものの1つだ。SHA-1は160ビットハッシュだ。
2^52の暗号操作でSHA-1の衝突を見つけられるという論文がある。最適に安全なハッシュなら2^80の操作が必要だ。2^52の時間はまだ大きいが、クラスターやボットネットの射程圏内に入りつつある。
http://www.ictlex.net/wp-content/iacrhash.pdf
MD5ハッシュはすでにラップトップで数秒でクラッシュ（衝突）できる。これが証明書ベースの署名から廃止された理由だ。
そして、私の理解では、公開鍵は数学的に結合された2つの秘密の数と考えることができ、秘密鍵はそれらの2つの数を別々に保持したものだ。システムを安全にするためには、2つの秘密の数が本当に大きな素数である必要がある。
しかし、本当に大きな非素数であっても結合の数学はまだ動く。ただ、アルゴリズムを破るのがはるかに速くなるだけだ。
もう少し調べて、自分の主張を裏付けられるか見てみる。誰かが即座に否定してくれることを期待していたのだが。
Quote from: knightmb on July 25, 2010, 07:44:02 PM
Quote from: Red on July 25, 2010, 07:22:14 PM
サトシは私のシナリオでもハッシュ関数が破られることが前提だと指摘した。それは正しいが、それに成功した事例があることを知って驚いた。MD4やMD5は明らかな例だ。しかし、SHA-1やSHA-256のような同系統のアルゴリズムの衝突攻撃の研究も進んでいる。
Bitcoinのこの部分ではどのハッシュが使われているのか？
彼はまた、生成された鍵ペア以外のものを使えるかについて懐疑的だ。
この点については、単純な数学の問題だとかなり確信している。文書の「ブラインド署名」について学ぶまで、十分に注意を払っていなかった。
実は、文書を乱数で掛け算し、その混ぜ合わされたファイルに誰かに署名してもらい、最後にその署名から乱数を割って取り除くと、結果は元の文書に対する有効な署名のままだ。まさかそれがうまくいくとは！
とにかく、鍵ペアが素数のペアに基づいている場合にのみ安全だとすれば、数が素数でなくても数学自体は何も変わらない。ただ因数分解がはるかに容易になるだけだ。
暗号の専門家に私が馬鹿だと証明してもらえたら本望だ。同じ関連に依拠した以前のプロジェクトのいくつかの機能にも影響する。その時もこれには気づかなかった。
彼らがあまり言及しないのは、衝突生成にはまだ大量のCPU時間がかかるということだ。
公開鍵123456がハッシュABCDを生成し、 公開鍵654321もハッシュABCDを生成すると分かっても、 秘密鍵はまだ持っていない。
しかしあなたの言うことからすると、公開鍵654321さえあれば、公開鍵123456のふりをしてコインを使えるということか。
かつ 公開鍵654321もハッシュABCDを生成するとわかったとしても、 秘密鍵は依然としてわからない。
しかしあなたの言うことでは、公開鍵654321さえあれば、公開鍵123456のふりをしてコインを使えるということだ。 それでも公開鍵654321で署名する必要がある。秘密鍵を知っている公開鍵を使って衝突を見つける必要がある。
ビットコインアドレスのトランザクションを要求する際、ハッシュに一致する公開鍵を提示し、その鍵で署名する必要がある。
Redのポイントは、安全でない公開鍵を素早く大量に生成することは簡単で、衝突を見つけた後にそれを破って秘密鍵を見つけることができるということだ。
彼は、公開鍵が安全なものである必要がある場合、つまり素数を見つけるために相当な作業が必要なものである場合、ハッシュ関数単独よりも強度が増すと指摘している。ブルートフォースを試みる人は、各試行ごとに鍵を生成するのに時間をかける必要がある。
Quote from: satoshi on July 25, 2010, 08:01:40 PM
Quote from: knightmb on July 25, 2010, 07:44:02 PM
公開鍵123456がハッシュABCDを生成すると分かったとして
かつ 公開鍵654321もハッシュABCDを生成するとわかったとしても、 秘密鍵は依然としてわからない。
しかしあなたの言うことでは、公開鍵654321さえあれば、公開鍵123456のふりをしてコインを使えるということだ。 それでも公開鍵654321で署名する必要がある。秘密鍵を知っている公開鍵を使って衝突を見つける必要がある。
ビットコインアドレスのトランザクションを要求する際、ハッシュに一致する公開鍵を提示し、その鍵で署名する必要がある。
Redのポイントは、安全でない公開鍵を素早く大量に生成することは簡単で、衝突を見つけた後にそれを破って秘密鍵を見つけることができるということだ。
彼は、公開鍵が安全なものである必要がある場合、つまり素数を見つけるために相当な作業が必要なものである場合、ハッシュ関数単独よりも強度が増すと指摘している。ブルートフォースを試みる人は、各試行ごとに鍵を生成するのに時間をかける必要がある。
そうだ、秘密鍵が絡む必要があると思った。ただ、別のランダム性を追加するわけで、別の公開鍵と衝突するハッシュを見つけるだけでなく、同時にその秘密鍵が破れるほど弱くなければならない。不可能とは言わないが、2つの変数が逆衝突探索に導入される。
基本的には、弱い秘密鍵のレインボーテーブルを構築し、それらを公開ハッシュと比較し、たまたまその攻撃に含まれるハッシュを持つ人がいることを祈る必要がある。もちろん不可能ではないが、コンピュータが10年で100倍速くなったとしても、どの程度実現可能だろうか？
[編集] OK、もう一度読み直した。公開鍵は秘密鍵から生成されるもので、独立ではない。つまり弱い公開鍵を見つけることだけが問題だ。
引用「SHA-1の衝突を2^52回の暗号操作で見つけられると主張する論文があります。最適に安全なハッシュでは2^80回の操作が必要です。2^52回の時間はまだ大きいですが、クラスターやボットネットの範囲に入ってきています。」 2^80は誕生日攻撃を使える場合だ。この場合は誕生日攻撃を使えないため、難易度は完全な2^160ビットだ。ただし、100万件（2^20件）のトランザクションのうちどれか1つを破ろうとしている場合、部分的な誕生日攻撃で2^160/2^20 = 2^140にできる。
ビットコインアドレスは160ビットハッシュが使用される唯一の場所だ。その他すべてはSHA-256だ。計算方法は以下の通りだ:
bitcoinaddress = RIPEMD-160(SHA-256(publickey))
間違っていたら訂正してほしい（喜んで謝るので）が、この場合RIPEMD-160に対する解析的攻撃を使うのは難しいと思う。解析的攻撃は、衝突を見つける確率を大幅に高める特定の範囲やパターンの入力を試すように規定している。ここでは、RIPEMD-160への入力はSHA-256の出力であるため、そのような制御ができない。解析的攻撃によってRIPEMD-160の衝突を生み出す入力を見つけたとして、それで何をするのか？SHA-256にその値を出力させる必要があるため、SHA-256も破る必要がある。
ブルートフォースの場合、RIPEMD-160(SHA-256(x))はRIPEMD-160単独と比べて強くはない。しかし解析的攻撃の場合、RIPEMD-160とSHA-256の両方を解析的に攻撃する必要があるようだ。もし間違っていれば、強度はRIPEMD-160と同じであり、SHA-256は1回分の鍵強化として機能するだけだ。
Quote from: satoshi on July 25, 2010, 08:48:01 PM
引用「SHA-1の衝突を2^52回の暗号操作で見つけられると主張する論文があります。最適に安全なハッシュでは2^80回の操作が必要です。2^52回の時間はまだ大きいですが、クラスターやボットネットの範囲に入ってきています。」 2^80は誕生日攻撃を使える場合だ。この場合は誕生日攻撃を使えないため、難易度は完全な2^160ビットだ。ただし、100万件（2^20件）のトランザクションのうちどれか1つを破ろうとしている場合、部分的な誕生日攻撃で2^160/2^20 = 2^140にできる。
ビットコインアドレスは160ビットハッシュが使用される唯一の場所だ。その他すべてはSHA-256だ。計算方法は以下の通りだ:
bitcoinaddress = RIPEMD-160(SHA-256(publickey))
間違っていたら訂正してほしい（喜んで謝るので）が、この場合RIPEMD-160に対する解析的攻撃を使うのは難しいと思う。解析的攻撃は、衝突を見つける確率を大幅に高める特定の範囲やパターンの入力を試すように規定している。ここでは、RIPEMD-160への入力はSHA-256の出力であるため、そのような制御ができない。解析的攻撃によってRIPEMD-160の衝突を生み出す入力を見つけたとして、それで何をするのか？SHA-256にその値を出力させる必要があるため、SHA-256も破る必要がある。
ブルートフォースの場合、RIPEMD-160(SHA-256(x))はRIPEMD-160単独と比べて強くはない。しかし解析的攻撃の場合、RIPEMD-160とSHA-256の両方を解析的に攻撃する必要があるようだ。もし間違っていれば、強度はRIPEMD-160と同じであり、SHA-256は1回分の鍵強化として機能するだけだ。
分析的攻撃については正しいと思う。少なくとも、それを分析している数学的天才について私が最低限理解する範囲では。
心配していたのは、もっと単純な：
bitcoinaddress = RIPEMD-160(publickey)
だった場合だ。
私が読む限りでは、
2つの数pとqがある。RSAではこれらは大きな素数であるべきだ。
n = p*q
公開鍵は2つのフィールド (n, e) だ。eは公開指数と呼ばれ、一般的な値のセットから選ばれるようだ。 秘密鍵も2つのフィールド (n, d) だ。dは秘密指数と呼ばれ、e、p-1、q-1を知ることで導出される。
トリックは、nをpとqに因数分解するのが本当に難しいこと。したがってp-1とq-1を見つけるのも同様に難しい。
私の仮説は、nが任意で、eが一般的な値の1つなら、動くp, qのペアはたくさんあるということだ。数が素数でないほどpとqを見つけやすく、したがってp-1とq-1も見つけやすい。そして大きな任意のデータブロックがあれば、ハッシュの衝突を試みる際に多くの柔軟性が得られる。
（ここが完全に的外れかもしれないところだ。暗号の専門家が私より詳しければ、本当に知りたい。）
鍵生成アルゴリズムはpとqを「ほぼ確実に素数」として生成するが、確実に知るには計算コストが高すぎるという記述を読んだ。これは非素数が明らかな失敗を引き起こさないことを示唆している。間違っているかもしれないが。