ビットコインの盗難を防ぐ暗号技術について、サトシらが議論

ビットコインの盗難を防ぐ暗号技術について、サトシらが議論

ビットコインを発明し、未だその正体が分かっていないサトシ・ナカモト。そんなサトシが残した約2年間の文章を、小宮自由氏の解説と共に紹介する連載「サトシ・ナカモトが残した言葉〜ビットコインの歴史をたどる旅」の第47回。

まずサトシのメールの前に、本連載の元になっている書籍『ビットコイン バイブル：サトシナカモトとは何者か？』の著者フィル・シャンパーニュ氏の解説も掲載する。

フィル・シャンパーニュ氏の解説

前に述べたように、ビットコインでは、ビットコイン送金の受取と認証 のメカニズムに、公開鍵と秘密鍵のペアによる非対称暗号化が用いられている。しかし、サトシがビットコインアドレスに使うと決めたのは、公開鍵そのものではなく、公開鍵のハッシュであった。これはサトシには二つの理由があった。一つは取引のサイズの縮小で、ハッシュの長さはわずか160ビットである。第二の利点は、ビットコインで用いる非対称暗号化アルゴリズムに将来、「バックドア」の欠陥やセキュリティの欠陥が見つかったときに備えて、もう一段のセキュリティを加えるのに便利だからだった。ハッカーがビットコインを送金するには、まず、ハッシュから公開鍵を導き出し、続いて、その公開鍵から秘密鍵を導き出すことが必要になる*1。ビットコイン・マガジンはこのテーマで秀逸な記事を掲載していた。

このスレッドでは、多大な計算パワーを持つ攻撃者がビットコインアドレス内のビットコインを使えるかどうかが議論されている。ビットコインのブロックチェーンは公開の元帳なので、これを見れば、多額の収支を含むビットコインアドレスを特定することもできるため、この種のアドレスに攻撃者は的を絞るかもしれない。

サトシの投稿全てを含め、スレッドの重要箇所をここに再現している。

【訳注】

*1 ビットコインにおいては、アドレスから出金するまではアドレスの元となった公開鍵は公開されない。従って一度も出金したことの無いアドレスからお金を盗むためには、アドレス（ハッシュ）-(復号)-> 公開鍵 -(復号)-> 秘密鍵という２段階の暗号解読を行う必要があり、これには１段階よりさらに莫大な計算時間が必要とされる（そのため、暗号が破られにくくセキュリティが高い）。このような性質があるため、ビットコインウォレットアプリにおいては、出金したアドレスの再利用を防ぐ仕組みが実装されていることがある。例えば、アドレスAからBにビットコインを送るとき、Bに送った後のAの残高すべてをCに送ってしまい、以降はCを新しいアドレスとして使う（Aは放棄する）というやり方がある。

*2 現在こちらの記事は表示できない

サトシ・ナカモトの投稿

それではサトシの投稿をみていこう。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

コインの盗難

投稿：Red　2010年07月25日　午後05時08分03秒

（注：斜体部分は、サトシ以外の者の質問を指す）

現在、実装されているビットコインにはかなり重大な暗号面の欠陥があると思います。いますぐ悪用可能かは分かりませんが（私は本物の暗号ハッカーではありません）、近い将来には十分ありえる話です。

その欠陥によって、任意のビットコインアドレスから匿名でコインの盗難が可能です。しかし、これは、既存の暗号システムの安全性を保護する難題の解決を含むものではありません。これは実装における「潜在的な」、修正可能な論理的欠陥にすぎません。

私はビットコインの成功を願っているので、欠陥について公開の場で遠慮会釈なしに騒ぎ立てたくはないです。この種の問題を議論するのに適切な場所はありますか？

Re：コインの盗難

投稿：サトシ　2010年07月25日　午後05時45分22秒

先に修正できるよう、プライベートに伝えてくれるのがベストです。

そちらのEメールにこちらのEメールアドレスを送りました（または、ここのプライベートメッセージでも結構です）。

Re：コインの盗難

投稿：サトシ　2010年07月25日　午後07時06分23秒

彼の話の要点は、ビットコインアドレス宛ての送金は、ハッシュ関数と同レベルのセキュリティしかないということです。ビットコインアドレスを短くする上で、公開鍵そのものではなく公開鍵のハッシュを使います。攻撃者はECDSAではなくハッシュ関数を破れば済むことになります。

Re：コインの盗難

投稿：Red　2010年07月25日　午後07時09分43秒

ありがとう、サトシ。

これが先にサトシに送った内容です。

———–

公開鍵の暗号化は、大きな素数は因数分解が困難である、という事実に依存します。それは誰もが知っています。ビットコイン送金がしっかり作られた公開鍵に向けられ、紐付けされた秘密鍵が将来の送金に必要ならば、ビットコインの暗号送金は完璧に安全だと認めます。

ですが、ビットコインの送金の仕組みはそうではないようです（私の読み方では）。取引においては、コインの金額を特定の「ビットコインアドレス」に送ります。このアドレスは公開鍵のハッシュです。

取引の有効化には、ノードが署名から公開鍵を取得し、実際の署名の検証に使います。署名が有効なら、ノードは公開鍵をハッシュ化し、直前の取引で割り当てられたビットコインアドレスに一致することを確認します。両者が一致すれば、取引は良好となります。

この潜在的な弱点は、署名内の公開鍵をビットコインアドレスに紐付けする点です。

公開鍵とハッシュの間には多数対一の関係があります。いま、安全な公開鍵／秘密鍵のペア（このうち公開鍵は特定のビットコインアドレスへハッシュされます）を作成する素数のペアを見つけるのが、難しそうに見えるならば、たぶん難しいのでしょう。

でも、それは要りません。

ハッシュすると著名な高額のビットコインアカウントに衝突するような公開鍵があれば済みます。素数に基づく安全な鍵ペアである必要はありません。一度だけ成功して盗難金を別のアカウントに送れれば良いわけです。これなら潜在的にはずっと簡単です。

他のハッシュよりも衝突が起きにくいハッシュもあります。ビットコインで使われるハッシュの強さは私にはよく分かりません。ですが、ハッシュされる元の内容を気にする必要がなければ、ハッシュを衝突させる方がずっと簡単です。

公開鍵はその性質上、ランダムなデータに見えます。私の理解では、公開鍵が安全な数学に基づいているかどうかは、因数分解に成功しなければ知りえません。ですので、クライアントはトライしようとはしません。普通は、署名の有効化を実行し、公開鍵が正常に機能していれば、それは安全な手法で生成されたものなのだ、と見なすのみです。

注意。次の分析は本物の暗号ハッカーによる二重チェックが必要です。私は暗号ハッカーではありません（IANACR:I Am Not A Cryptohacker）。

なので、ハッシュに依存すると、最新のハッシュ衝突アルゴリズムを用いれば、衝突するデータブロック（これは公開鍵を表します）を生成できます。それから、公開鍵／秘密鍵の計算を逆転させると、紐付けされた（全く安全ではない）秘密鍵を生成できます。この秘密鍵から有効な署名を生成できます。

それから、簡単に因数分解できて安全ではない鍵ペアを取得し、ターゲットのビットコインアドレスに一致する署名入り取引を生成します。

コインの送金先のフルの公開鍵は取引ログでは有効化できないので、これは提示された公開鍵に違いないと、取引ログは見なします。

送金先のフルの公開鍵をブロックリストに記録すれば、目的通りの強さを取り戻せます。ですが、34文字のアドレスを回覧する可能性は失われます。

私が完全に間違っていたら、時間をとらせたことをお詫びします。

ありがとうございました！

Red

Re：コインの盗難

投稿：Red　2010年07月25日　午後07時22分14秒

サトシから、私のシナリオではさらにハッシュ関数の突破も必要だと指摘されました。それは確かですが、突破に成功した人がいると知って驚きました。MD-4とMD-5は明らかな例ですが、SHA-1や派生形のSHA-256の衝突はまだ試行の段階です。

ビットコインのこの部分にはどのハッシュが使われていますか？

生成された鍵ペア以外を使えるのではないかと彼は疑いも抱いています。

この点では、これが単に数学の問題にすきないと、かなり自信があります。文書の「ブラインド署名」のことを知るまでこのことにはあまり注目していませんでした。

受け取った文書にランダムの数字を掛け算することが可能なことが分かります。それから、ごちゃまぜにしたファイルを誰かに署名させます。最後に署名からランダム数字を割ると、結果は元の文書の有効な署名のままです。そんなことが可能だとは誰が想像できるでしょう。

ともかく、素数のペアに基づくときのみ鍵ペアが安全なのなら、数字が素数でないときは計算は何も変わりません。因数分解はずっと簡単です。

私が愚かだと証明してくれる暗号の専門家がいたら完璧に嬉しいです。これは、私が作成した以前のプロジェクトで、同じ紐付けに依存するいくつかの機能にも影響してきます。このことは考えていませんでした。

Re：コインの盗難

投稿：knightmb　2010年07月25日　午後07時34分42秒

とても良いことですね。*私がオープンソースを愛するもう一つの理由ですよ*

私が理解しているのは次の通りです。間違っていたら訂正して下さい。

公開鍵のハッシュは実際の公開鍵そのものより小さいので、ハッシュに一致する衝突のみを見つければよく、その衝突が見つかったら公開鍵／秘密鍵のコンビが判明します。そうしたら、判明した鍵でコインを使用すれば、他のクライアントには、あなたのハッシュが被害者のハッシュに一致することと、この取引を永久に記録することだけが問題なので、有効な送金だと判断します。

現行のハッシュは35文字の長さで、アルファベット26文字（大文字）＋26文字（小文字）＋10文字（数字）＝62文字が使えます。

ですので、可能な組み合わせは 541,638,008,296,341,754,635,824,011,376,225,346,986,572,413,939,634,062,667,808,768 通りです。

ですので、必要な作業は、メインとなる本丸の秘密鍵／公開鍵への総当たり攻撃に比べて半分程度だと思います。将来に向けて計画しても構わないでしょう: – )

Re：コインの盗難

投稿：knightmb　2010年07月25日　午後07時44分02秒

引用：Red　2010年07月25日　午後07時22分14秒

サトシから、私のシナリオではさらにハッシュ関数の突破も必要だと指摘されました。それは確かですが、突破に成功した人がいると知って驚きました。MD-4とMD-5は明らかな例ですが、SHA-1や派生形のSHA-256の衝突はまだ試行の段階です。

あまり言及されないのは、*衝突の生成*にはCPU時間を多くとられる点です。

公開鍵123456からハッシュABCDが生成され、公開鍵654321からもハッシュABCDが生成されるとしても、私はなお秘密鍵を持たない状態です。

でも、あなたの発言に基づけば、必要なのは公開鍵654321だけで、公開鍵123456に偽装すればコインを送金できることとなります。

Re：コインの盗難

投稿：Red　2010年07月25日　午後07時52分23秒

指摘されたように、ビットコインではビットコインアドレスの生成に160ビットのハッシュが使われています。

最も広く使われているのはハッシュアルゴリズムのSHA-1の系統です。SHA-1は160ビットのハッシュです。

SHA-1の衝突を2^52 の暗号操作で発見したと主張する論文がこれです。最高に安全なハッシュなら2^80 の操作が必要です。2^52回はまだ多い方ですけど、クラスターやボットネットの射程に入りつつあります。

http://www.ictlex.net/wp-content/iacrhash.pdf

MD-5のハッシュはラップトップPCでも数秒で破壊できます。そのため、認証ベースの署名としては役目を終えました。

そして、そう、私が言っているのは、二つの秘密の数字を数学的に組み合わせたものが公開鍵だと考えることができるということです。その二つの数字を別々に保存するのが秘密鍵です。システムの安全性を保つには、その二つの秘密の数字が非常に大きな素数であることが求められます。

でも、非常に大きな非素数なら、組合せ数学はまだ機能します。アルゴリズムを破るスピードが速まるだけです。

もう少しグーグルを探してみて自分の主張を立証できるか、試みてみます。私は自分の主張を誰かが即座に却下してくれるのを望んでいましたけれど。

Re：コインの盗難

投稿：サトシ　2010年07月25日　午後08時01分40秒

引用：knightmb　2010年07月25日　午後07時44分02秒

公開鍵123456からハッシュABCDが生成され、公開鍵654321からもハッシュABCDが生成されるのは理解できるとしても、

私はなお秘密鍵を持たない状態です。

でも、あなたの発言に基づけば、必要なのは公開鍵654321だけで、公開鍵123456に偽装すればコインを送金できることとなります。

さらに、公開鍵654321で署名しなければなりません。公開鍵に対応する秘密鍵を知っている必要があり、その公開鍵を用いて衝突を発見する必要があります。

ビットコインアドレスの送金を要求するときは、ハッシュに一致する公開鍵を与え、その鍵で署名しなければなりません。

Redの要点は、突破可能な安全でない公開鍵をすばやく生成し、衝突の発見後に秘密鍵を見つけるのはたやすいということです。

彼の指摘は、素数の発見に多大な作業を要するぐらい公開鍵が安全でなければならないなら、その強さはハッシュ関数のみでの強さを上回るだろうということです。総当たり攻撃を試みれば、毎回、鍵の生成に時間をとられるでしょう。

Re：コインの盗難

投稿：knightmb　2010年07月25日　午後08時20分41秒

引用：サトシ　2010年07月25日　午後08時01分40秒

さらに、公開鍵654321で署名しなければなりません。公開鍵に対応する秘密鍵を知っている必要があり、その公開鍵を用いて衝突を発見する必要があります。

ビットコインアドレスの送金を要求するときは、ハッシュに一致する公開鍵を与え、その鍵で署名しなければなりません。

Redの要点は、突破可能な安全でない公開鍵をすばやく生成し、衝突の発見後に秘密鍵を見つけるのはたやすいということです。

彼の指摘は、素数の発見に多大な作業を要するぐらい公開鍵が安全でなければならないなら、その強さはハッシュ関数のみでの強さを上回るだろうということです。総当たり攻撃を試みれば、毎回、鍵の生成に時間をとられるでしょう。

はい、秘密鍵はどこかに含まれる必要があると考えていました。そうすれば別のランダムさが少々追加されます。別の公開鍵と衝突するハッシュを見つけなければならず、それと同時に、秘密鍵は突破が容易なぐらい脆弱でなければなりません。不可能だとは言っていませんが、二つの変数が逆衝突探索*1 に導入されます。

基本的に、弱い秘密鍵のレインボーテーブルを作り、これを公開ハッシュに照合し、誰かが持つハッシュがたまたまその攻撃の一部になるのを期待しないといけません。もちろん不可能ではないですけど、たとえ十年後にコンピューターが百倍速くなったとしても、どのくらいありうるでしょう？

［編集済］OKです。あなたの文章を読み返しました。公開鍵は秘密鍵から生成されます。独立して、ではありません。ですので、弱い公開鍵の発見だけが問題になります。

Re：コインの盗難

投稿：サトシ　2010年07月25日　午後08時48分01秒

引用：

SHA-1の衝突を2^52 の暗号操作で発見したと主張する論文がこれです。最高に安全なハッシュなら2^80 の操作が必要です。2^52回はまだ多い方ですけど、クラスターやボットネットの射程に入りつつあります。

2^80回は誕生日攻撃が使えるときです。これには誕生日攻撃は使えないので*2、難易度はフルの2^160ビットです。でも、百万（2^20）取引のうちから一つの破壊を試すなら、部分的な誕生日攻撃、2^160÷2^20＝2^140が可能です。

160ビットハッシュが用いられているのはビットコインアドレスだけです。他は全てSHA-256です。その計算は

bitcoinaddress = RIPEMD-160(SHA-256(publickey))*3 です。

もし間違っていたら訂正してください（その際は素直に誤りを認めます）。このケースで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は鍵の強化の一巡目として使うだけです。

Re：コインの盗難

投稿：Red　2010年07月25日　午後09時04分01秒

引用：サトシ　2010年07月25日　午後08時48分01秒

bitcoinaddress = RIPEMD-160(SHA-256(publickey))

間違っていたら訂正して下さい（お願いします。誤りを認める屈辱を喜んで受け入れます）。このケースでRIPEMD-160に解析的攻撃をするのは難しいと思います。

解析的攻撃については合っていると思います。少なくとも、それを解析する数学的才能が（最低限）私にあれば、です。

もっと単純なbitcoinaddress = RIPEMD-160(publickey)かと心配していました。

Re：コインの盗難

投稿：Red　2010年07月25日　午後09時19分11秒

私の読み方はこうです。

二つの数字、pとqがあります。これはRSAでは大きな素数と仮定されます。

するとn = p*qとなります。

公開鍵は二つの場(n, e)です。eは暗号化指数（public exponent）と呼ばれ、共通の値のセットから選ばれたように見えます。

秘密鍵も二つの場(n, d)です。dがeとp-1とq-1を知ることで導かれれば、dは復号化指数（private exponent）と呼ばれます。

ここでのトリックは、nをpとqに因数分解するのはとても難しいという点です。それゆえ、p-1とq-1を見つけるのも同じぐらい難しいです。

私の仮定では、nが任意の数で、eが共通の値のうちの一つなら、うまくいく異なるpとqのペアはたくさんあります。小さい素数ほどpとqの発見は易しく、ゆえに、p-1とq-1の発見も易しいです。そして、もし、ハッシュ衝突の試みに多大な柔軟性をもたらす任意のデータの大きなブロックを持っていれば*4 、です。

（この点が私が完全に間違っている可能性がある点です。暗号の専門家が私よりよく知っているなら、とても興味があります）

私は、鍵生成アルゴリズムにより、「とてもよく素数に見える」ようなpとqが作成されると読みましたが、これを確かめるにはあまりに多くの作業が必要です。このことから、私は、非素数は、明白な失敗の原因にはならないと信じるようになりました。ただ、私が間違っているかもしれません。

Re：コインの盗難

投稿：サトシ　2010年07月25日　午後10時27分36秒

すみません、実際はECDSA（楕円曲線デジタル署名アルゴリズム）で、RSAではないです。「素数」と言うべきではなかったです。ECDSAでは鍵ペアの生成に多くの時間はとられません。

Re：コインの盗難

投稿：Red　2010年07月26日　午後12時46分04秒

引用：サトシ　2010年07月25日　午後10時27分36秒

すみません、実際はECDSA（楕円曲線デジタル署名アルゴリズム）で、RSAではないです。「素数」と言うべきではなかったです。ECDSAでは鍵ペアの生成に多くの時間はとられません。

楕円曲線がどう機能するかは今日ではなく、いつか勉強してみます。大学生のときに有限数学をもっととるべきでした。何かの役に立つものだ、とは思えないものです！

ともかくこれは素晴らしいアイデアです。ビットコインの素晴らしい実装です、サトシ！ 世界の新しい可能性を開いています。信用に依存しない分散型の合意というコンセプトがとりわけ気に入っています。それが斬新なコンセプトだと思います。

また、ビットコイン採掘のアイデアも素晴らしいと思います！ ネットワークを別の方法で立ち上げできなかったものかと思っています。コインの分配は「公平な手法」だ、という話には賛成できませんが、でも、まあ、世界は公平ではないです！ そして、実際、利用者の興奮をこれ以上に誘い出す方法もなかったと思います。

ところで、私の以前の前提では、ビットコイン盗難の脅威に関するスレッドがなかったことは認めます。私の見方では、二重ハッシュが安全性を保証しているようですね。妙案です！

ところで、非素数に基づいてRSA鍵を生成したら何が起きるか、まだ知りたいです。二重ハッシュを実行しない別のシステムがあるのかなと想像しています。:-)

Re：コインの盗難

投稿：Bitcoiner　2010年07月27日　午前02時01分16秒

Redのように、目を光らせる人がいて嬉しいです。このフォーラムには頭脳明晰で関心の高い人が大勢いて、ソフトウェアの動作確認をし、信頼性を高めてくれるので、このスレッドでオープンソースソフトウェアへの感謝の気持ちも生まれました。もしビットコインが閉じたソースであったとしてもこれほど成功したかどうか、定かではないです。

Re：コインの盗難

投稿：bytemaster　2010年07月28日　午後09時42分17秒

潜在的な攻撃のリスクを最小化する明らかな解決策は、潜在的な「報酬」を小さくすることだと私には思えます。ですので、一つのアドレスに保管するコインを多くしすぎないことです。「ご褒美」の経済的価値が破壊にかかるコストより低ければ、誰もトライしようとしません。しかし、こう言ってもやはり、可能な限り突破が困難なレベルを保つのがベストだと思います。

Re：コインの盗難

投稿：knightmb　2010年07月28日　午後10時45分16秒

幸運によるものでも、CPU／ストレージのパワーによるものでも、どちらにしても、確かにこれは難しいです。

衝突と秘密鍵を発見しても、アカウント利用者の 541,638,008,296,341,754,635,824,011,376,225,346,986,572,413,939,634,062,667,808,768通りの潜在的な組み合わせから一つのアカウントを特定しないといけないので、利益はありません。

ですので、これは二面的に見て下さい。私がハッシュの衝突を発見し、秘密鍵を見つけたとします。いま、私は、自分の勝つ条件はそのハッシュを使っている誰かが存在することだ、という風に期待しないといけません。潜在的なハッシュアカウントの数はこの惑星に生まれた人の数より多く、一人一人が百万のアドレスを使っているとすれば、大きな規模で見ると、攻撃は、興味深いことではあるけれど、その性質上、ほとんど実現不可能です。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【訳注】
*1 原文では「reverse collision finding」。この文脈では、通常のハッシュ衝突探索（collision finding: 異なる入力から同じハッシュ値を得ること）とは異なる特定の条件を満たす必要がある探索を指している。具体的には、ただ単にハッシュ値が衝突する（同じになる）入力を見つけるのではなく、その入力（この場合は公開鍵）が特定の条件（例えば、対応する秘密鍵が計算上破られやすいこと）を満たす必要があるという追加の条件を指している。このことをもって “reverse” と付けたと考えられるが、日本語話者にはこれを「逆」と言われてもいまいちピンと来ない。
*2 任意の二つの入力が同じハッシュ値を生成する「任意の衝突」を見つけるのではなく、特定のハッシュ値に対応する特定の入力（公開鍵）を見つける必要があるため、誕生日攻撃の利用が制限される。
*3 ビットコインアドレスを生成するプロセスを式にしたもの。公開鍵(publickey) に対してハッシュ化関数 SHA-256 を適用し、その結果に対して別のハッシュ化関数 RIPEMD-160 を適用する、という意味。この二段階のハッシュ化により、より復号化がなされにくくセキュリティが高いやり方でビットコインアドレスを生成することができる。
*4 より多くのデータがあれば、それと照らし合わせて暗号解読がより容易にできるという一般論。

解説

ビットコインのセキュリティ（どれだけ秘密鍵を攻撃者が知るのが難しいか）について語られています。他人のビットコインを奪う行為は、他人の秘密鍵に不正アクセスすることとほぼイコールです。秘密鍵があればすべてのビットコインを出金できるからです。秘密鍵は公開鍵を暗号化したもので、公開鍵はアドレスを暗号化したものです。本文をざっくりまとめると、「ビットコインアドレスを秘密鍵から導出する際には何回も暗号化がなされており、それらのどの暗号も復号が極めて難しいため、ビットコインアドレスから秘密鍵を導き出すのは事実上不可能」となります。

小宮自由

→この連載の他の記事を読む