コインの窃盗
現在の実装のビットコインには、かなり重大な暗号学上の欠陥があると思います。今すぐ悪用可能かどうかはわかりません（私は本物の暗号ハッカーではありません）が、近い将来に悪用される可能性は十分にあります。
この欠陥により、任意のビットコインアドレスからコインを匿名で窃盗することが可能になります。なお、既存の暗号システムを安全に保つ困難な問題を解くことは含まれていません。これは単に実装における潜在的な修正可能な論理的欠陥です。
ビットコインの成功を望んでいるので、公の場で欠陥について大声で騒ぎ立てたくはありません。このような問題を議論するための適切な場はありますか？
先に私に非公開で教えていただけると、修正を先に行えるので最善だ。
メールアドレスをお送りした。（またはここで PM を送ることもできる）
修正されるか、動作しないと証明されたら、詳細をここに投稿してもらえないか？とても気になる。=)
Red、先に非公開で教えてくれてありがとう！投稿してくれ（そして皆のサスペンスを解消してくれ！）
彼のポイントは、ビットコインアドレスに支払われたトランザクションはハッシュ関数と同程度の安全性しかないということだ。ビットコインアドレスを短くするために、公開鍵そのものではなく公開鍵のハッシュになっている。攻撃者は ECDSA ではなくハッシュ関数を破るだけで済む。
サトシ、ありがとう。
これが彼に送った内容だ。
公開鍵暗号は、大きな素数を素因数分解するのが難しいという事実に依存している。それは誰もが知っている。もし bitcoin の送金がきちんと形成された公開鍵に割り当てられ、将来の送金のために対応する秘密鍵による署名が必要なら、bitcoin の暗号的送金は完全に安全だと認めるだろう。
しかし、私の読み取りでは、bitcoin のトランザクションはそのようには動いていないようだ。トランザクションはコインの金額を特定の「bitcoin アドレス」に割り当てる。そしてそのアドレスは公開鍵のハッシュだ。
トランザクションを検証するために、ノードは署名から公開鍵を取り出し、それを使って実際の署名を検証する。署名が有効なら、その公開鍵をハッシュ化して、前のトランザクションで割り当てられた bitcoin アドレスと一致するか確認する。両方が一致すれば、定義上、そのトランザクションは正当だ。
潜在的な弱点は、署名内の公開鍵を bitcoin アドレスと結びつける部分にある。
公開鍵とあるハッシュ値の間には多対一の関係がある。さて、公開鍵部分が特定の bitcoin アドレスにハッシュ化されるような、安全な公開鍵／秘密鍵ペアを作る素数の組を見つけるのは難しそうだ……たぶん難しい。
しかし、それは必要ない。
必要なのは、既知の大きな bitcoin 口座とハッシュが衝突する、公開鍵を表す「何か」だけだ。素数に基づく安全な鍵ペアである必要は全くない。1回だけ機能して、盗んだお金を別の口座に送れればそれでいい。それは潜在的にずっと簡単だ。
ハッシュによっては衝突させるのが他より難しいものもある。使われているハッシュの強度はわからない。だが、ハッシュ化される内容を気にしなくていいなら、どんなハッシュでも衝突させるのはずっと簡単になる。
公開鍵はその性質上、ランダムなデータのように見える。私が理解する限り、公開鍵が安全な数学に基づいているかどうかは、それを素因数分解できない限りわからない。したがってクライアントは試さない。普通は署名の検証だけを行い、それが通れば公開鍵は安全な方法で生成されたものだと前提する。
注：以下の分析は本物の暗号ハッカーによるダブルチェックが必要だ。私は暗号研究者ではない（IANACR）。
つまり、ハッシュ次第で、新興のハッシュ衝突アルゴリズムの一つを使って、公開鍵を表す衝突データブロックを生成できる。それから公開鍵／秘密鍵の数学を逆算して、有効な署名を生成できる、対応する（しかしまったく安全ではない）秘密鍵を生成する。
次に、その安全でない、簡単に分解できる鍵ペアを使って、対象の bitcoin アドレスに一致する署名済みトランザクションを生成する。
トランザクションログは、コインが意図された完全な公開鍵を検証できないので、提示されたものがそうだったに違いないと前提するだけだ。
送金先の完全な公開鍵をブロックリストに記録すれば、本来の強度を取り戻せる。しかしその場合、34 文字のアドレスを使い回す利便性は失われる。
もし的外れなことを言っているなら、時間を無駄にさせて申し訳ない。
ではまた！ Red
サトシは私のシナリオでもハッシュ関数が破られることが前提だと指摘した。それは正しいが、それに成功した事例があることを知って驚いた。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 通りの組み合わせがある。
つまり、本来の秘密鍵/公開鍵に対するブルートフォースと比べて約半分の作業量だ。将来への備えは損にならない 😉
サトシは私のシナリオでもハッシュ関数が破られることが前提だと指摘した。それは正しいが、それに成功した事例があることを知って驚いた。MD4 や MD5 は明らかな例だ。しかし、SHA-1 や SHA-256 のような同系統のアルゴリズムの衝突攻撃の研究も進んでいる。
彼らがあまり言及しないのは、衝突生成にはまだ大量の 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 つの秘密の数が本当に大きな素数である必要がある。
しかし、本当に大きな非素数であっても結合の数学はまだ動く。ただ、アルゴリズムを破るのがはるかに速くなるだけだ。
もう少し調べて、自分の主張を裏付けられるか見てみる。誰かが即座に否定してくれることを期待していたのだが。
公開鍵123456がハッシュABCDを生成することを突き止めたとして
かつ 公開鍵 654321 もハッシュ ABCD を生成するとわかったとしても、 秘密鍵は依然としてわからない。
しかしあなたの言うことでは、公開鍵 654321 さえあれば、公開鍵 123456 のふりをしてコインを使えるということだ。 それでも公開鍵 654321 で署名する必要がある。秘密鍵を知っている公開鍵を使って衝突を見つける必要がある。
ビットコインアドレスのトランザクションを要求する際、ハッシュに一致する公開鍵を提示し、その鍵で署名する必要がある。
Red のポイントは、安全でない公開鍵を素早く大量に生成することは簡単で、衝突を見つけた後にそれを破って秘密鍵を見つけることができるということだ。
彼は、公開鍵が安全なものである必要がある場合、つまり素数を見つけるために相当な作業が必要なものである場合、ハッシュ関数単独よりも強度が増すと指摘している。ブルートフォースを試みる人は、各試行ごとに鍵を生成するのに時間をかける必要がある。
それでも公開鍵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回分の鍵強化として機能するだけだ。
引用「SHA-1の衝突を2^52回の暗号操作で見つけられると主張する論文があります。最適に安全なハッシュでは2^80回の操作が必要です。2^52回の時間はまだ大きいですが、クラスターやボットネットの範囲に入ってきています。」 2^80は誕生日攻撃を使える場合だ。この場合は誕生日攻撃を使えないため、難易度は完全な2^160ビットだ。ただし、100万件（2^20件）のトランザクションのうちどれか1つを破ろうとしている場合、部分的な誕生日攻撃で2^160/2^20 = 2^140にできる。
分析的攻撃については正しいと思う。少なくとも、それを分析している数学的天才について私が最低限理解する範囲では。
心配していたのは、もっと単純な：
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 を「ほぼ確実に素数」として生成するが、確実に知るには計算コストが高すぎるという記述を読んだ。これは非素数が明らかな失敗を引き起こさないことを示唆している。間違っているかもしれないが。
すまない、実際には RSA ではなく ECDSA（楕円曲線デジタル署名アルゴリズム）だ。「素数」と言うべきではなかった。ECDSA は鍵ペアの生成にそれほど時間がかからない。
すまない、実際には RSA ではなく ECDSA（楕円曲線デジタル署名アルゴリズム）だ。「素数」と言うべきではなかった。ECDSA は鍵ペアの生成にそれほど時間がかからない。
楕円曲線がどう動くか、いつか勉強する。今日じゃないけどな。大学のときにもっと有限数学を取っておくべきだった。それが何かの役に立つなんて誰が思っただろう！
ところで、BitCoin のアイデアと実装は素晴らしいよ、サトシ！
まったく新しい可能性の世界を開いている。特に好きなのは、信頼に頼らない分散合意のコンセプトだ。それがブレイクスルーとなる発想だと思う。
それから、BitCoin マイニングの発想も見事だと思う！他のやり方ではネットワークをブートストラップできなかっただろう。コインを配るのが「公平な方法」だという点には同意しないが、世界はそもそも公平じゃない！それに正直、他のどんな方法でも、これほどユーザーの興奮は生み出せなかっただろう。
ところで、私の最初の仮説からは bitcoin を盗む筋道はないと認める。私の視点では、ダブルハッシュがそれを保証しているようだ。お見事！
ちなみに、それでもまだ、非素数を基にした RSA 鍵を生成したらどうなるのかは知りたい。ダブルハッシュをしていない他のシステムがあるはずだから。:-)
Red のようにあちこちで鋭く目を光らせてくれる人がいるのはありがたい！このスレッドを見ていると、オープンソースソフトウェアのありがたみも感じる。このフォーラムには賢くて関心のある人がたくさんいて、ソフトウェアを検証し、さらに信頼を上乗せできるからだ。Bitcoin がクローズドソースだったら、ここまで成功できたかどうか怪しい！
Red のようにあちこちで鋭く目を光らせてくれる人がいるのはありがたい！このスレッドを見ていると、オープンソースソフトウェアのありがたみも感じる。このフォーラムには賢くて関心のある人がたくさんいて、ソフトウェアを検証し、さらに信頼を上乗せできるからだ。Bitcoin がクローズドソースだったら、ここまで成功できたかどうか怪しい！
実は、まったく逆だ。君が読んだものは知的で筋の通った会話に見えるかもしれないし、Bitcoin への信頼や自信、興奮を感じさせてくれるかもしれない。だが、http://www.youtube.com/watch?v=lBp5ag6SJH4 のように、それはただそれっぽく聞こえるように作られた言い回しにすぎない。