はじめにこれはPGPのためのパスフレーズFAQである。パスワードや種々の鍵長といったことがらをカバーするような雑事について、alt.security.pgpで尋ねられたことのある質問をすべて含めようとした。大学の代数学以上のものを学んでいる人は数学についてくることができるだろう。8.2節の用語解説をチェックして、いくつかの用語とその使われ方についての助けとしてほしい。MD5とIDEAは128ビットブロックに基づいている。56ビットDES鍵や他の大きさの鍵に変えることは些細なことだろう。パスワードがパスフレーズと違うのは、その長さである。パスワードでもパスフレーズでも、解析するには同じ考えを使う。このFAQは工事中である(みんなそうじゃないか?)。それらについてわかったり、それを生み出したり、時間があったりしたら変更するだろう。適用された暗号使用法[1]は、この分野で出版された研究はそれほど多くなかったと信じさせてくれる。パスワード・クラックはカバーされているが、パスフレーズについてはほとんどない。数学関係の一部は、私が通常かかわっている分野ではない。私は訓練を積んだエレクトリニクス・エンジニアである。暗号使用は単なる趣味だ。些細な見落としがあっても許してほしい。わたしはこれをほとんど頭の中で考えて作った。返事は期待しないでほしい。どこにパスフレーズFAQはあるのか?これはお約束の質問。これを読んでいるということは見つけているのである。見つけていなければ、この節は実質的に役に立たない。今のところ、パスフレーズFAQのある公式な場所は3つしかない。ウェブサイトに感謝する。FAQのPGP署名済みコピーも、毎月中ごろにalt.security.pgpに投稿される(ほとんどのばあい)。この文書ではどのように物事が扱われるのか?最初のことは、この文書で使われる数字である。ポケット計算機と、私のPCの立証のためのいくつかのプログラムで実行された。有効数字の桁数はわずかに制限されている。40桁もの数列はほとんど必要ではなく、実のところ、ほとんど理解を超えているからだ。ここで使われた巨大な数字の正確な値は、6.0節を参照のこと。3.4E38=3.4*10^38=2^128という表記法を使っている。これは入力しやすく、場所もとらない。10)もここで使うので注意。e)を使うことを心配しなくてもよい。セキュリティに影響するところで概数にするには、安全を期して切り上げにしている。他の数字は四捨五入している。ほとんどの場合、これについてはっきりテキストに書いてあるはずだ。下位参照は小文字をつけてある。ほかのことがらについては、それをたどってほしい。乱数を得る方法は?乱数はひじょうに生成しづらい。危機や回路のランダムさをもたらすのは、ランダムでない出来事だったりする。1からNまでのマーカーを作って、優れたミキサーに置くところを考えてほしい。コインをはじいてみてもいいが、誰かを実験すれば、コインをはじくのも長期的に見れば充分に偏るという結果が出るだろう。宝くじで使っているようなボール法はよい乱数源だが、宝くじからの数字をつかってはならない。宝くじの番号はあまりにも少なく、簡単に試せてしまう。ビリヤードゲームは、1セットのボールを入れ物にいれておいて、同時に取り出せるのは1つだけということにできる。これは、安価な乱数源となる。16個のボールから取り出すという作業を特定のアプリケーションで使えるようにする方法については、読者にゆだねた。「ダンジョン&ドラゴン」などのロールプレイング・ゲームに親しんでいる人なら、いろいろな面数のあるサイコロのセットを持っていることだろう。一つ注意しなければならないことは、サイコロの目を足すこと(たとえば2つの6面体サイコロ)は、中間の数字を多く(7は1/6の確率で出る)、両極の数字は起こりにくく(2と12の確率は1/36)してしまい、乱数性が薄れるということだ。ランダムなサイコロを持っているとしよう。その品質はあまりよくないことがあり、ランダムではない結果を導くかもしれない。疑似乱数生成PGNG(疑似乱数生成)を使うのは、たいていの場合、乱数をつくるのによくない。PRNGの問題は、数字が機械的に作られることである。rand()、その他の言語での乱数機能も同じことである。プログラマーはこの単純で比較的高速な方法をプログラムやゲームで長い間使ってきた。その理由は、PRNGの働き方にある。いうようなコードを使う。Cには、ふつう、素数が使われる。ほとんどの言語は、PRNGを呼び出す前にR1の基本値を設定するが、必ずというわけではなく、PRNGのなかには付加的な定数Bに煩わされないものもあるかもしれない。PRNGが破りやすくなっているのは、その値を蓄えるのに16ビットしか使っていないためである。それはつまり、使用された疑似乱数要素の数をNとすると、16ビットPRNG鍵スペースを無理やり解くには、65536*N回の試みで破ることができるということだ。PRNG鍵スペースは1日で検索できるだろう。どれほど幸運で最善のPRNGを持っていたとしても、平均的な家庭用コンピューターで最悪1週間以内に検索することはできるし、検索スペースはせいぜい2^32であろう。NSAが40ビット鍵など気にしていないように、40ビット鍵も個人がコンピューターを全力で使って1週間内外で総当たりすることができることに注意。ハードウェア乱数生成ハードウェア生成は、さまざまな半導体PN接合点からのノイズを使って作る。このよい例は、zenerダイオードから単純に導かれるノイズである。他のノイズ源は、高価なレジスターや、ノイズを発生させるためにさまざまな技術を使っている商用チップの数々である。ランダムな情報のハードウェアソースへの注意としては、ランダムではないノイズや他の信号に影響されうるということである。多くの場所では、コンピューター、テレビ、ラジオその他の電磁気機によって、電源からの50Hzや60Hzのノイズ、時計信号、その他のデジタルノイズにさらされる。安全のために、ハードウェアソースの出力を暗号化したり改作してもいいだろう。よい改作機能または暗号化は、どんな未発見のパターンも隠れる。安価なランダムビットソースは、10米ドルで[7]、大量生産は5米ドル以下で作られる。IDEA鍵をクラックするのはどれくらい困難か?PGPは、従来の暗号としてIDEAを使う。IDEAのための鍵は128ビットである。総当たりでの鍵スペースは、2^128=3.4E38と計算できる。すべての鍵の可能性を調べるために、1秒あたり10億(1E9)の鍵を試すことができるIDEAのための鍵クラッカー用特別ハードウェアでも、1.08E22年かかる。ほとんどの鍵を得ることができるだろうと思われる半分の時間でも5.39E21年である。太陽は1E9年で新星と化すとされている。アルゴリズムは安全であるから、暗号分析家はRSAのような別のものやあなたのパスフレーズを狙う。IDEA鍵を総当たりでクラックするには、われわれの技術力を越えている。RSAをクラックするのはどれほど難しいか?素因数分解は、鍵スペースの総当たり検索よりも簡単な問題である。ふるい分け(MPQS)とその変形、そして数フィールドふるいわけ(NFS)である。何らかの特殊な例を除いて、130桁/429ビットより大きな数を素因数分解するにはどれほどかかるか、だれもわからないのではないかと思う。数についてのネット参考文献は、素因数分解されたのはRSA129と384ビットブランクネット鍵だという。129桁/426ビット鍵を素因数分解するよりも、116桁/384ビット鍵を素因数分解するほうが時間もコンピューターの能力もかからないことに注意すべきだ。NFSは、RSA129が素因数分解されるよりも速く、130桁/430ビット鍵のRSA130を素因数分解してしまった。RSAはおそらく、PGPでも最も弱いリンクであるが、現在、155桁/512ビット以上の数を素因数分解するのに、特別な機械を作らずにやる方法はだれもわからない。MD5とは?MD5はあなたのパスフレーズを撮ってそれをIDEA鍵に変換するものである。理論的に、MD5はあなたの鍵スペースが2^128以上である限り、毎回違ったビットの組合わせを出力するものである。MD5がすべての2^128出力を、2^128に等しい与えられた鍵スペースから作るであろうということを証明するのは、実質上不可能である。これは、IDEA鍵への総当たり検索とほぼ同じである。興味深い問題は、理論的に、2^128以上の与えられた鍵スペースを検索することによって、同じパスフレーズを作り出すことができるということだ。MD5に対する攻撃を考慮して、待って、観察しよう。弱点が発見されてから、審査委員会では未修整のMD5を使わないようにしている。SHAその他の変換機能への移行が、将来のPGPにあるかもしれない。パスフレーズはどのくらいの長さがいいか?経験からいえば、必要とする鍵の1ビットあたり1文字を使うことだ。実際には、鍵のために英文文字ごとに約1.2ビット[1c]ということになる。鍵の長さは128÷1.2=106.667≒107文字が必要ということだ。これは、パスフレーズのための小文字とスペースだけの通常の英語構文を想定しており、計算のためにパスフレーズ中のスペースはすべて無視している[1a]。PGPを使うたびに1行半もの文字を喜んで入力する人は少ない。セキュリティが破られ、弱いパスフレーズを使ってしまうのだ。別の言語を使ったら?あなたの母国語を使うということはもちろん選択肢の一つとしてあっていい。このFAQを通じて、データと統計は英文によるものだ。他の言語または複合言語を使うなら、その数字は少々変わるだろう。それは、あなたのパスフレーズをわかりにくくするわけではない。異なった言語や複数の言語を攻撃するのは、やはり同じことだ。検索スペースは大ざっぱに、言語のサイズか、追加される言語の語彙の平均サイズが追加されると言うことになる。別の言語の辞書攻撃は、英語の辞書攻撃と同じ方法で作用するだろう。一般的なフレーズ(句)や引用文を使ったら?一般的なフレーズの短いものは使ってはならない。一冊の本の引用だったら、4万くらいの引用ができるだろう[5]。XTをセットして、特別なハードウェアなしに比較的短い時間で一般的なフレーズをチェックすることだってできる。単純なフレーズは真っ先にチェックされるだろう。あなたがスタートレック・ファンなら、「喜べ、スコット」はよくないフレーズだ。公刊書籍にフレーズを見つけたら、それは使ってはいけない。背景を探るだけで、音楽、本、テレビショー、映画、ゲーム趣味、その他あなたが使いたがるようなものはすぐにわかる。すべての一般的フレーズは鍵検索の最初の過程で試されるだろう。40000の引用でも、未改造PGPで約2.4日のあいだに試すことができる。2.7.1節参照のこと。フレーズや無意味なフレーズを組み合わせたら?フレーズを組み合わせることで、フレーズ検索はちょっと大変になる。無意味なフレーズは、総当たり検索の速度を落とすだろう[4]。その他の文の構成要素の順序は、自然な順序で試されるだろう。よい無意味なフレーズは、総当たり検索に対する限りランダムに見えるがほんとうはランダムではないというものだ。CaPitaliZatTiOn"というようにすることで、検索を1語あたり100万まで増やせる[1b]。パスフレーズのための数字を修正することは、きちんとしたパスフレーズの800万倍以上(1語あたり100万倍)を手に入れることになる。ランダムな大文字化は語の長さによって順列組合わせが変わってくる。語に0〜9の数字を一つ付け加えるなら、辞書サイズを10倍にする。これは小さなプラスだが、いくつかの場合では煩雑にできるかもしれない。3をEのかわりに、1をIのかわりに、5をSのかわりに、2をZのかわりに使うなら、0〜9までの数字を追加してアルファベットを36文字にすることができる。文字の入れ替え、文字の循環、文字ずらし、その他の語撹乱はランダムさの役には立たないが、総当たり検索を遅くしてくれる。この方法でパスフレーズをランダムなものに近づけることができる。約74000語の単語がある。128ビット鍵サイズに必要なのは、log(2^128)/log(74000)=7.91のランダムな辞書からの単語ということになる。切り上げれば、IDEA鍵より難しいパスフレーズにはランダムな8語が必要だということになる。総当たり辞書攻撃は、IDEA鍵への総当たり攻撃よりわずかに長くかかる。これは覚えておくのが難しいようなパスフレーズを作り出す方法だ。それでもこれは多少タイプしやすい。鍵生成辞書を使ってもいいか?小さな辞書ほど速く検索できる。だれかの周囲にあるものは、一般の検索のかわりに始める手がかりとして充分であろう。鍵生成システムはほんとうにランダムだと思っていい。プログラムは、貧弱に作られていたり、監視されていても解決できる。よいランダム・パスフレーズ生成システムとして、ダイスウェア[8]を試してほしい。辞書が語の構造を一層ランダムにするようなトリックを持っているなら意味はない。最後に、検索スペースを数えてみよう。乱数のもとがランダムでなければ、検索の手間を減らしてしまう。このため、鍵生成器がほんとうにランダムかどうか確認する必要がある。違ったサイズの辞書がどれくらいの効果を持つかを示した。1万語辞書を使うと(2.7節より)、平均6か月以上かからせるにはlog(3.16E13)÷log(10000)=3.37≒約4語が必要。同じ辞書でIDEAの同等のパスフレーズを作るには、log(2^128)÷log(10000)=9.63≒約10語が必要。2万5000語辞書では、lot(2^128)÷log(25000)=8.76≒9語。5万語辞書だと、log(2^128)÷log(50000)=8.20≒9語。完全にランダムな文字を使ったら?標準アルファベットは26文字ある。数学的にいえば、log(2^128)÷log(26)=27.23個のランダム文字が必要だ。切り上げれば、IDEA鍵より難しいものを作るのに28文字が必要だということである。28ランダム文字を記憶するのは難しいが、不可能ではない。入力するにもそう悪くはない。すべてのランダムな記号を使ったら?印字可能なすべてのASCII文字を使うなら、95の文字・記号を使うことができる。log(2^128)÷log(95)=19.48のランダムな文字がこの方法に必要だということになる。切り上げれば、この方法でIDEA鍵より難しくするには20のランダムな文字が必要ということだ。20のランダムな文字を記憶するのはまだむずかしいことであり、また入力も簡単ではない。パスフレーズ攻撃にどれくらいかかるか?鍵クラッカーは1秒あたり100万鍵を試せると仮定しよう。1クロックサイクルあたり約1回の指示を実行する。200Mhzペンティアムと最小の指示を使えば、小さいプログラムは1秒間に100万回動作するということになる。6x86は同じクロック速度でももっと速く、RISCチップはもっと速い。鍵を1年で試すことができるということだ。ランダムな語でできた1つの鍵は、6か月平均で終わらせるならlog(3.16E13)÷log(74000)=2.77≒3語の長さであるということになる。ところで、私たちが本当に試そうとしているのは、沈黙のコンピューター攻撃をやめさせることである。コンピューターが賢くなるにつれて、コンピューターが得るものはゆっくりになっていく。私たちはいつでもハードウェアを注文して組み立て、監視統制だけのためにコンピューターを使うこともできるのである。PGP2621つ、その他の必要なファイルをロードしたものでの実験がある。キャッシュ可能、その他の設定も高速になるようにしてあった。5と6.xで使われるようになった)で、有効なパスフレーズ環境を使って新しいパスフレーズをPGPに送ってエラーコードを調べるという形でパスフレーズを試した。この方法を使って、毎秒2つ(正確には1.8125)のパスフレーズが試され、PGPはエラーが検出されたときにはビープ音を鳴らして遅くなるが、それは最小限になるように修正された。本気でパスフレーズを攻撃するためには、PGPを改良して遅延をのぞき、加速する必要があるだろう。教訓として、小さな辞書からの一つのランダムな語は約1時間で得られる。最大の辞書なら検索に1日かからない。この攻撃に必要なツールはすべて持っているとしよう。この作業をするのに必要なプログラムと設定は、高校生ハッカーでも充分に可能なのである。強いパスフレーズの作り方は?その答えは、あなたのパスフレーズがどのくらいの安全性を必要としているかによる。一般のフレーズで始めて、それをわずかにランダムにさせて、ゆがめるといい。単語を変えて、無意味なフレーズを作ろう。ランダムなやり方で分校蔵を変えるのも忘れてはならない。いくつかのランダムなタンゴや文字を加えて、安全性を確保しよう。最後に、IDEA鍵への攻撃より時間のかかるように、覚えやすいものを作ろう。beat"(私の破られないスーパー・パスフレーズは打つことができない)というのは、それ自体は弱い。beets"(マイルブレーキない意識朦朧過去凍結は露営できる蜜蜂ビート)ならずっといいし、攻撃に備えて同音異字辞書を使うのはいいことだ。一方で、一つのパス中に、文構造と違う無意味なフレーズや論理的に全くつながりのない語を入れてもいい。総当たり攻撃以外では想像もできないがあなたにはわかるようなランダムな文字を加えてもいい。フレーズはかなり覚えやすい。一般のフレーズをもとに使ったからだ。実際のフレーズを忘れても、再構成できるだろう。人間として、わたしたちは物事を同じように予測できるやり方でする傾向がある。さらなる安全性のために、あなたは完全にランダムなフレーズや文字列を生成してもいい。これは時間がかかり、覚えにくい。あなたのセキュリティ・レベルは、鍵の長さを変えることで簡単に変更できる。確実な方法はダイスウェアだ[8]。私のパスフレーズはどのくらい強いか?わたしたちは知っているパスフレーズのなかでも絶対的最小と最大のものを使って、与えられたパスフレーズがどれだけ安全かを計算するちょっとした公式を作ってみよう。ここで、ランダムとは真のランダムを意味する。rnd()や線形合同生成器のような疑似ランダム法はここでは勘定にいれない。この公式は使うときに必要に応じて変更してもいい。