(57)【特許請求の範囲】
【請求項１】
遠隔パスワード認証を行うシステムであって、
クライアント・コンピュータと、
複数の認証サーバと、
クライアント・コンピュータと複数の認証サーバとを相互接続するネットワークと、
クライアント・コンピュータにパスワードを入力し、複数の認証サーバのそれぞれに一意のランダム値ｙiを記憶し、パスワードから群要素（Ｐ）を導出し、ブラインドされたパスワード値（Ｐx）を複数の認証サーバに送信し、ブラインドされた鍵のシェア（Ｐxyi）を複数の認証サーバから取り出し、マスター鍵（Ｋm）を作成するためにシェアをアンブラインドして結合し、マスター鍵（Ｋm）を使用してクライアント・コンピュータで暗号化された秘密データを解読するために共同するクライアント・コンピュータで実行されるソフトウェアと複数の認証サーバで実行されるソフトウェアとを含むシステム。
【請求項２】
クライアント・コンピュータで動作しているソフトウェアがマスター鍵（Ｋm）を検証するように動作する請求項１に記載のシステム。
【請求項３】
クライアント・コンピュータで動作しているソフトウェアがマスター鍵（Ｋm）を使用して暗号化された秘密データを解読するように動作する請求項１に記載のシステム。
【請求項４】
クライアント・コンピュータで動作しているソフトウェアが検証されたマスター鍵（Ｋm）を使用して暗号化された秘密データを解読するように動作する請求項２に記載のシステム。
【請求項５】
クライアント・コンピュータで動作しているソフトウェアが、検証されたマスター鍵（Ｋm）のプルーフと各ブラインドされたパスワード値（Ｐx）をサーバに送信するように動作する請求項２に記載のシステム。
【請求項６】
クライアント・コンピュータと、
複数の認証サーバと、
クライアント・コンピュータと複数の認証サーバを相互接続するネットワークとを含むシステムを使用する遠隔パスワード認証を行う方法であって、
クライアント・コンピュータが、入力されたパスワードから群要素（Ｐ）を導出するステップと、
クライアント・コンピュータが、ブラインドされたパスワード値（Ｐx）を複数の認証サーバに送信するステップと、
クライアント・コンピュータが、ブラインドされた鍵のシェア（Ｐxyi）を複数の認証サーバから取り出すステップと、
クライアント・コンピュータが、マスター鍵（Ｋm）を作成するためにシェアをアンブラインドして結合するステップと、
クライアント・コンピュータが、マスター鍵（Ｋm）を使用してクライアント・コンピュータで暗号化された秘密データを解読するステップとを含む方法。
【請求項７】
クライアント・コンピュータが、マスター鍵（Ｋm）を検証するステップをさらに含む請求項６に記載の方法。
【請求項８】
クライアント・コンピュータで動作しているソフトウェアがマスター鍵（Ｋm）を使用して暗号化された秘密データを解読するように動作する請求項に６記載の方法。
【請求項９】
クライアント・コンピュータが、検証されたマスター鍵（Ｋm）を使用して暗号化された秘密データを解読するステップをさらに含む請求項７に記載の方法。
【請求項１０】
クライアント・コンピュータが、検証されたマスター鍵（Ｋm）のプルーフと各ブラインドされたパスワード値（ＰX）を複数の認証サーバに送信するステップをさらに含む請求項７に記載の方法。
【請求項１１】
クライアント・コンピュータと、
複数の認証サーバであって、それぞれの一意のランダム値を含むデータ記憶領域を含む複数の認証サーバと、
クライアント・コンピュータと複数の認証サーバを相互接続するネットワークとを含む複数サーバ・システムで遠隔パスワード認証を可能にするためのコンピュータ・プログラムであって、
クライアント・コンピュータに、入力されたパスワードから群要素（Ｐ）を導出させるためのコード・セグメントと、
クライアント・コンピュータに、ブラインドされたパスワード値（Ｐx）を複数の認証サーバに送信させるためのコード・セグメントと、
クライアント・コンピュータに、ブラインドされた鍵のシェア（Ｐxyi）を複数の認証サーバから取り出させるためのコード・セグメントと、
クライアント・コンピュータに、マスター鍵（Ｋm）を作成するためにシェアをアンブラインドして結合させるためのコード・セグメントと、
クライアント・コンピュータに、マスター鍵（Ｋm）を使用してクライアント・コンピュータで暗号化された秘密データを解読させるためのコード・セグメントと
を含むコンピュータ・プログラム。
【請求項１２】
クライアント・コンピュータに、マスター鍵（Ｋm）を検証させるためのコード・セグメントをさらに含む請求項１１に記載のコンピュータ・プログラム。
【請求項１３】
クライアント・コンピュータに、マスター鍵（Ｋm）を使用して暗号化された秘密データを解読させるためのコード・セグメントをさらに含む請求項１１に記載のコンピュータ・プログラム。
【請求項１４】
クライアント・コンピュータに、検証されたマスター鍵（Ｋm）を使用して暗号化された秘密データを解読させるためのコード・セグメントをさらに含む請求項１２に記載のコンピュータ・プログラム。
【請求項１５】
クライアント・コンピュータに、検証されたマスター鍵（Ｋm）のプルーフとブラインドされたパスワード値（Ｐx）を複数の認証サーバに送信させるためのコード・セグメントをさらに含む請求項１２に記載のコンピュータ・プログラム。
【請求項１６】
ログイン試行回数、増幅数、Ｐxパスワード増幅要求値のリスト、Ｐxパスワード増幅要求値のリストに関連付けられたタイムスタンプのリストを複数の認証サーバ上に維持し、 
ブラインドされたパスワード（Ｐx）要求を受信し、 
ブラインドされたパスワードを短期リストに記録し、 
ユーザ・アカウントがロックされているかどうかを調べるためにユーザ・アカウントをチェックし、
ブラインドされた鍵のシェア（Ｐxyi）を作成し、 
クライアント・コンピュータがアンロックされている場合にはブラインドされた鍵のシェアをクライアント・コンピュータに送信するようにソフトウェアが共同する請求項１に記載のシステムであって、  
複数の認証サーバで実行されるソフトウェアが、
複数の認証サーバに、ブラインドされた鍵のシェア（Ｐxyi）が作成されるログイン試行のたびに、増幅数を増分させ、Ｐxパスワード増幅要求値のリストに、ランダムなベキ乗されるパスワードに等しいＱAの値を記録させ、
複数の認証サーバに、要求が受信された時刻を示すタイムスタンプ値を記録させ、 
複数の認証サーバに、任意のタイムスタンプ値と現在時刻の差異が特定の時間間隔よりも大きくなった場合に判定される陳腐な要求を定期的にチェックさせ、 
複数の認証サーバに、対応するパスワード増幅要求値とタイムスタンプと、増幅数とを削除させ、 
複数の認証サーバに、ログイン試行回数を増分させる
請求項１に記載のシステム。
【請求項１７】
成功裡のログインが行われたときに、クライアント・コンピュータで実行されるソフトウェアが、
クライアント・コンピュータに、ランダムなベキ乗されるパスワードに等しいＱAの値を同じログイン・セッションの以前の実行のＱAに対する任意の以前の値と共に、暗号化されたメッセージの形式で各認証サーバに送信させ、
クライアント・コンピュータに、マスター鍵Ｋmを使用してこのメッセージを認証させる、請求項１６に記載のシステム。
【請求項１８】
複数の認証サーバが、ログイン試行回数と、増幅数と、Ｐxパスワード増幅要求値のリストと、複数の認証サーバ上のパスワード増幅要求値のリストに関連付けられたタイムスタンプのリストとを維持するステップと、 
複数の認証サーバが、ブラインドされたパスワード（Ｐx）要求を受信するステップと、
複数の認証サーバが、ブラインドされたパスワードを短期リストに記録するステップと、
複数の認証サーバが、ユーザ・アカウントがロックされているかどうかを調べるためにユーザ・アカウントをチェックするステップと、
複数の認証サーバが、ブラインドされた鍵のシェア（Ｐxyi）を作成するステップと、
複数の認証サーバが、クライアント・コンピュータがアンロックされている場合にはブラインドされた鍵のシェアをクライアント・コンピュータに送信するステップとをさらに含む請求項６に記載の方法であって、
複数の認証サーバで実行されるソフトウェアが、
複数の認証サーバに、ブラインドされた鍵のシェア（Ｐxyi）が作成されるログイン試行のたびに、増幅数を増分させ、Ｐxパスワード増幅要求値のリストに、ランダムなベキ乗されるパスワードに等しいＱAの値を記録させ、
複数の認証サーバに、要求が受信された時刻を示すタイムスタンプ値を記録させ、
複数の認証サーバに、任意のタイムスタンプ値と現在時刻の差異が特定の時間間隔よりも大きくなった場合に判定される陳腐な要求を定期的にチェックさせ、
複数の認証サーバに、対応するパスワード増幅要求値とタイムスタンプと、増幅値とを削除させ、
複数の認証サーバに、ログイン試行回数を増分させる、請求項６に記載の方法。
【請求項１９】
クライアント・コンピュータが、ランダムなベキ乗されるパスワードに等しいＱAの値を同じログイン・セッションの以前の実行のＱAに対する任意の以前の値と共に、暗号化されたメッセージの形式で各認証サーバに送信するステップと、 
クライアント・コンピュータが、マスター鍵Ｋmを使用してこのメッセージを認証するステップをさらに含む請求項１８に記載の方法。
【請求項２０】
複数の認証サーバに、ログイン試行回数と、増幅数と、Ｐxパスワード増幅要求値のリストと、複数の認証サーバ上のパスワード増幅要求値のリストに関連付けられたタイムスタンプのリストとを維持させ、 
複数の認証サーバに、ブラインドされたパスワード（Ｐx）要求を受信させ、 
複数の認証サーバに、ブラインドされたパスワードを短期容疑リストに記録させ、 
複数の認証サーバに、ユーザ・アカウントがロックされているかどうかを調べるためにユーザ・アカウントをチェックさせ、 
複数の認証サーバに、アンロックされている場合にはブラインドされた鍵のシェア（Ｐxyi）を作成させ、 ブラインドされた鍵のシェアをクライアント・コンピュータに送信させ、
複数の認証サーバに、ブラインドされた鍵のシェア（Ｐxyi）が作成されるログイン試行のたびに、増幅数を増分させ、ＰXパスワード増幅要求値のリストに、ランダムなベキ乗されるパスワードに等しいＱAの値を記録させ、
複数の認証サーバに、要求が受信された時刻を示すタイムスタンプ値を記録させ、
複数の認証サーバに、任意のタイムスタンプ値と現在時刻の差異が特定の時間間隔よりも大きくなった場合に判定される陳腐な要求を定期的にチェックさせ、 
複数の認証サーバに、対応するパスワード増幅要求値とタイムスタンプと、増幅数とを削除させ、
複数の認証サーバに、ログイン試行回数を増分させる
ためのコード・セグメントをさらに含む請求項１１に記載のコンピュータ・プログラム。
【請求項２１】
クライアント・コンピュータに、ランダムなベキ乗されるパスワードに等しいＱAの値を同じログイン・セッションの以前の実行のＱAに対する任意の以前の値と共に、暗号化されたメッセージの形式で各認証サーバに送信させ、 
クライアント・コンピュータに、マスター鍵Ｋmを使用してこのメッセージを認証させる
ためのコード・セグメントをさらに含む請求項２０に記載のコンピュータ・プログラム。
【発明の詳細な説明】
【０００１】
本発明は、一般に、コンピュータ・セキュリティに関し、より詳細には、複数のサーバを使用した遠隔パスワード認証のためのシステム、方法、およびソフトウェアに関する。
【０００２】
パスワードベースの認証は、大部分の個人的な認証システムの基礎である。キャリーアラウンド・トークン、スマート・カード、およびバイオメトリックが追加されている場合でも、単純な記憶されたパスワードが、通常、コンピュータのトランザクションで人間の識別を確立するために不可欠の中心的な要因のままである。グレードの低いパスワード、すなわち人間が容易に記憶することができる種類のパスワードは、多くのそういうことがなければ安全なシステムにとって特にやっかいな問題である。グレードの低いパスワードに対処する目的で、ネットワークの脅威を解消するためにゼロ知識(zero-knowledge)パスワードが開発された。しかし、パスワード検証データが敵に対して使用可能になった場合にそのパスワード検証データへの攻撃をいかにして防止するかはいまだ未解決の問題である。
【０００３】
通常のパスワード・システムでは、サーバはパスワードのための検証データを維持しているが、それはパスワード自体のコピーである場合がある。ＵＮＩＸ（登録商標）システムでは、追加のセキュリティのために、検証データは反復されたパスワードの一方向性関数であるが、それは通常はファイルに記憶されている。特権のないユーザおよびプログラムがそれに対するアクセス権を有しないように、このファイルがさらに保護されることが多い。従来のＵＮＩＸパスワードに対する攻撃は、攻撃者がパスワード検証データのファイルに何らかの形でアクセス権を有し、かつ、可能な限り多くのパスワードを決定または「クラック」するためにそのファイルに対してパスワード・クラッキング・ツールを実行する。パスワードのクラッキングは、単に候補パスワードのリストに対して一方向性関数を適用することである。一方向性関数の出力が検証データと一致する場合、攻撃者は自分が正確なパスワードを推測したことを知る。このような攻撃は、所与の時間内にできるだけ多くのパスワードをクラックすることができるように、最も一般的なあるいは最も可能性のあるパスワードを試行するために最適化することができる。
【０００４】
目的は、可能な限り最も簡単なセキュリティ・モデルを使用して、すなわち可能な限り少ない推測を使用して、パスワードベースのクライアント／サーバ認証システムで可能な限り多くのパスワードに対するサーバベースの攻撃の脅威を低減することである。この目的は、サーバに対するまったく拘束を受けていない攻撃に直面してもなお、パスワードの露出を防止することである。現在のモデルでは、攻撃者がサーバのソフトウェアを変更し、そのサーバに対して入手可能なすべてのデータにアクセスし、サーバが合法的で疑わしくないユーザを認証している間にそのサーバの使用を制御する能力を有することを想定している。
【０００５】
この目的を達成するためには、複数のマシンを使用する必要があることは明らかである。任意の単一マシン・システムで、ユーザのパスワード検証データにアクセスすることができる、または任意のパスワードの暗号化されたデータにアクセスすることができる人物は、ユーザのアクションをシミュレーションすることによる拘束を受けていないオフラインの暴力的な攻撃を実行するために十分な情報を有している。問題は、このリスクを解消するために、複数のサーバ間でいかにしてパスワード検証データを分割するかということである。単一サーバは、オフラインの暴力的な攻撃を仕掛ける能力を有しないはずである。
【０００６】
公開鍵暗号化は、現在では安全な個人的な電子トランザクションのために必須のツールとして承認されてきている。個人のデジタル署名には広範な適用があることが予想される。しかし大きな問題は、ユーザの秘密鍵をいかにして保護し、管理するかということにある。それをおそらくはパスワードによって弱く暗号化された状態でクライアント・マシンに放置しておくことは、望ましくないセキュリティ・リスクである。セキュリティがあまりにも頻繁に管理困難に陥るクライアント・マシン上にパスワードがクラックされ得る永続的データを放置しておくことは愚かであろう。さらに、複数のユーザが単一マシンを共有するモデルでは、ユーザの信用証明書のローカルな記憶を要求することは現実的ではない。
【０００７】
いわゆる「ローミング」ユーザに対するユーザ認証の解決法の１つのクラスは、遠隔サーバに記憶されているユーザの個人的な信用証明書を保存し、それらの信用証明書を取り出すためにパスワードベースの認証を使用する。強力なゼロ知識パスワード（ＺＫＰ）プロトコルは、ネットワークベースの暴力的な攻撃を解消することによってそれらの解決法にある脅威の多くに対処するが、同時にクライアント・マシン上の他の記憶された鍵と証明書への依存性をも解消する。ＺＫＰプロトコルは、複数サーバの場合にも同様に必須である。
【０００８】
強力なモデルと弱いモデルとの複数サーバの安全なローミング・システムのための２つのモデルを議論する。どちらのモデルでも、攻撃者はパスワード検証データのコピーに対するアクセス権を入手することができると想定されており、適切に長い時間で計算を実行する能力を有する。（適切に長いとは、拘束は受けていないが計算の実現可能性の制限内であることを意味している。任意に長い計算は任意に大きな公開鍵をクラックすることができる。大部分の暗号化方法でそうであるように、潜在的な攻撃者に使用可能な時間と力に対してある種の現実的な上限を設定することができ、また鍵に対応した安全な最小限の適切なサイズを決定することができるということが想定される。）
【０００９】
弱いモデルでは、攻撃者は、サーバの永続的データのコピーに対するアクセス権を有するが、実行中のサーバのオペレーションに干渉することはできないと想定する。
【００１０】
強力なモデルでは、方法は、認証サーバのうちの１つ以外すべてに対する完全にアクティブなリークに直面してさえパスワードの安全性を維持する必要がある。攻撃者は、サーバのソフトウェアを変更し、サーバが有効なユーザを認証している間にそのサーバに入手可能なすべての情報にアクセスすることができると想定される。強力なモデルはより単純であり、したがって好ましい。これはまた、従来の安全なチャネルの存在を想定した類似のシステムに対する初期のモデルよりも強力である。
【００１１】
これらのモデルのすべてで、各サーバは、多数の許容される無効アクセスの試行に制限を課すことによって、拘束を受けていないオンラインの攻撃から自衛することができる。これらの制限は複数の通常の方法で課すことができる。本発明の好ましい一実施態様は、サーバがパスワード入力の際の合法的な誤りに対してよりよく説明することを支援する機能も含んでいる。
【００１２】
ローミング・システムの目的は、モバイル・ユーザが公開鍵暗号化オペレーションを実行するために自分の秘密鍵に安全にアクセスして使用することを可能にすることである。モビリティとは広義で使用されており、そこに鍵を記憶することを必要とせずに個人用ワークステーションおよび他の人物のワークステーションを使用すること、公衆キオスク端末を使用すること、ならびに現代的なハンドヘルド・ワイヤレス・ネットワーク・デバイスを使用することを包含している。ユーザに対してどこからでも秘密鍵に対するパスワード認証アクセスを提供しながら、同時に敵がパスワードを盗みまたはクラックし、それによってそれらの鍵を獲得する機会を最低限に抑えることが望まれる。
【００１３】
スマート・カードはローミング・ユーザに対して秘密鍵の記憶問題を解決することを約束してきたが、この解決法はカードの配置とカードリーダーの導入を必要とする。個人が便宜性のために安全性を犠牲にする傾向は、追加のハードウェアを必要とする解決法の幅広い用途に対する障壁であることは既に証明済みである。これは、ソフトウェアベースのローミング・プロトコルを求める１つの動機である。
【００１４】
本明細書で使用されるように、ローミング・プロトコルとは、１つまたは複数の信用証明書サーバからの秘密鍵の遠隔取り出しのための安全なパスワードベースのプロトコルのことである。容易に記憶されるパスワードを使用し、他の記憶されているユーザの信用証明書は一切使用しないことによって、ユーザは信用証明書サーバに対して認証し、任意のアクセス可能なクライアント・マシン上で一時的に使用するために自身の秘密鍵を取り出す。クライアントは、１つまたは複数のトランザクション用の鍵を使用し、次いでその後、その鍵と任意のローカルなパスワード関連データとを消去する。
【００１５】
本明細書で使用するように、女性のクライアントと彼女の男性のサーバに対する人称代名詞を使用して、特定のユーザに代わって動作しているクライアント・マシンはＡｌｉｃｅと称し、信用証明書サーバは一般にＢｏｂと称するか個別にＢｉと称する。
【００１６】
「ローミング」システムの概念は信用証明書サーバと密接に関係している。Ｊ．ＴａｒｄｏおよびＫ．Ａｌａｇａｐｐａｎの「ＳＰＸ：Ｇｌｏｂａｌ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｕｓｉｎｇ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｅｒｔｉｆｉｃａｔｅｓ（ＳＰＸ：公開鍵信用証明書を使用したグローバル認証）」、ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ、１９９１年の議事録１９９１年、２３２頁から２４４頁で開示されているＳＰＸ  ＬＥＡＦシステムは、検証するためにパスワードを信用証明書サーバに対して送信し、その後ユーザの秘密鍵の取り出しと解読とを実行するためにサーバ認証チャネルを使用するローミング・プロトコルを提示している。信用証明書サーバは、それ自体が検出することのできる推測による攻撃を制限することによって自衛し、プロトコルはオフラインでのパスワードの目立たない推測を防止する。
【００１７】
信用証明書（認証）サーバは、パスワードの推測が正確かどうかを判定できる場合、故障閾値を事前設定した後のさらなる交換を防止または遅延させることができる。
【００１８】
パスワードのみのプロトコルはもう１つの重要な関連分野である。Ｓ．ＢｅｌｌｏｖｉｎおよびＭ．Ｍｅｒｒｉｔｔの「Ｅｎｃｒｙｐｔｅｄ  Ｋｅｙ  Ｅｘｃｈｎａｇｅ：Ｐａｓｓｗｏｒｄ−ｂａｓｅｄ  ｐｒｏｔｏｃｏｌｓ  ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  ｄｉｃｔｉｏｎａｒｙ  ａｔｔａｃｋｓ（暗号化された鍵交換：ディクショナリ攻撃に対して安全なパスワードベースのプロトコル）」、ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｒｅｓｅａｒｃｈ  ｉｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ１９９２年５月の議事録で開示されたＥＫＥプロトコルは、事前にサーバ認証の動作を一切必要とせずに安全でないネットワークを介してパスワードを安全に認証することによる安全なパスワードのみのプロトコルの概念を紹介している。Ｌ．Ｇｏｎｇ、Ｔ．Ｍ．Ａ．Ｌｏｍａｓ、Ｒ．Ｍ．Ｎｅｅｄｈａｍ，およびＪ．Ｈ．Ｓａｌｔｚｅｒによって「Ｐｒｏｔｅｃｔｉｎｇ  Ｐｏｏｒｌｙ  Ｃｈｏｓｅｎ  Ｓｅｃｒｅｔｓ  ｆｒｏｍ  Ｇｕｅｓｓｉｎｇ  Ａｔｔａｃｋｓ（不十分に選択された秘密の予測による攻撃からの保護）」ＩＥＥＥ  Ｊｏｕｒｎａｌ  ｏｎ  Ｓｅｌｅｃｔｅｄ  Ａｒｅａｓ  ｉｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ第１１巻、ｎｏ．５、１９９３年６月の６４８頁から６５６頁と、Ｌ．Ｇｏｎｇによる「Ｉｎｃｒｅａｓｉｎｇ  Ａｖａｉｌａｂｉｌｉｔｙ  ａｎｄ  Ｓｅｃｕｒｉｔｙ  ｏｆ  ａｎ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｓｅｒｖｉｃｅ（認証サーバの使用可能性および安全性の向上）」ＩＥＥＥ、Ｊｏｕｒｎａｌ  ｏｎ  Ｓｅｌｅｃｔｅｄ  Ａｒｅａｓ  ｉｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ第１１巻ｎｏ．５、１９９３年６月の６５７頁から６６２頁とによって開示された「秘密公開鍵」方法と、Ｄ．Ｊａｂｌｏｎによって「Ｓｔｒｏｎｇ  ｐａｓｓｗａｒｄ−ｏｎｌｙ  ａｕｔｈｅｎｔｉｃａｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ（強力なパスワードのみによる認証のなされた鍵交換）」ＡＣＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｒｅｖｉｅｗ、第２６巻ｎｏ．５、１９９６年１０月の５頁から２６頁、ｈｔｔｐ：／／ｗｗｗ．ＩｎｔｅｇｒｉｔｙＳｃｉｅｎｃｅｓ．ｃｏｍ／ｌｉｎｋｓ．ｈｔｍｌ＼＃Ｊａｂ９６で議論されているＳＰＥＫＥ方法と、Ｓ．Ｌｕｃｋｓによる「Ｏｐｅｎ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ：Ｈｏｗ  ｔｏ  Ｄｅｆｅａｔ  Ｄｉｃｔｉｏｎａｒｙ  Ａｔｔａｃｋｓ  Ｗｉｔｈｏｕｔ  Ｅｎｃｒｙｐｔｉｎｇ  Ｐｕｂｌｉｃ  Ｋｅｙｓ（オープン鍵交換：公開鍵を暗号化せずにディクショナリ攻撃に打ち勝つ方法）」Ｓｅｃｕｒｉｔｙ  Ｐｒｏｔｏｃｏｌ  Ｗｏｒｋｓｈｏｐ‘９７、Ｅｃｏｌｅ  Ｎｏｒｍａｌｅ  Ｓｕｐｅｒｉｅｕｒｅ、１９９７年４月７日から９日に記載のＯＫＥ方法と、Ｔ．Ｗｕによって「Ｔｈｅ  Ｓｅｃｕｒｅ  Ｒｅｍｏｔｅ  Ｐａｓｓｗｏｒｄ  Ｐｒｏｔｏｃｏｌ（安全な遠隔パスワード・プロトコル）」、１９９８  Ｎｅｔｗｏｒｋ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍ  Ｓｅｃｕｒｅｉｔｙ  Ｓｙｍｐｏｓｉｕｍの議事録、Ｉｎｔｅｒｎｅｔ  Ｓｏｃｉｅｔｙ、１９９８年１月９７頁から１１１頁、その他に記載のＳＲＰ−３方法を含めて同様の目的のための一連の他の方法が開発されたものだが、これらは、Ｓ．ＨａｌｅｖｉおよびＨ．Ｋｒａｗｃｚ���ｋによる「Ｐｕｂｌｉｃ−ｋｅｙ  ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  ｐａｓｓｗｏｒｄ  ｐｒｏｔｏｃｏｌｓ（公開鍵の暗号化およびパスワード・プロトコル）」、ｔｈｅ  Ｆｉｆｔｈ  ＡＣＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ，１９９８年の記事録と、Ｍ．Ｋ．Ｂｏｙａｒｓｋｙによる「Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  Ｐａｓｓｗｏｒｄ  Ｐｒｏｔｏｃｏｌｓ：Ｔｈｅ  Ｍｕｌｔｉ−Ｕｓｅｒ  Ｃａｓｅ（公開鍵暗号化およびパスワード・プロトコル：複数のユーザの場合）」、６ｔｈＡＣＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ、１９９９年１１月１日から４日、シンガポールの議事録と、Ｖ．Ｂｏｙｋｏ、Ｐ．ＭａｃＫｅｎｚｉｅおよびＳ．Ｐａｔｅｌによる「Ｐｒｏｖａｂｌｙ  Ｓｅｃｕｒｅ  Ｐａｓｓｗｏｒｄ  Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ  Ｕｓｉｎｇ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎを使用した証明可能に安全なパスワード認証鍵交換）」、暗号化の発展−ＥＵＲＯＣＲＹＰＴ  ２０００、コンピュータ・サイエンスの講義録第１８０７巻、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、２０００年５月と、Ｍ．Ｂｅｌｌａｒｅ、Ｄ．ＰｏｉｎｔｃｈｅｖａｌおよびＰ．Ｒｏｇａｗａｙによる「Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ  Ｓｅｃｕｒｅ  Ａｇａｉｎｓｔ  Ｄｉｃｔｉｏｎａｒｙ  Ａｔｔａｃｋ（ディクショナリ攻撃に対して安全な認証された鍵交換）」、暗号化の発展−ＥＵＲＯＣＲＹＰＴ  ２０００、コンピュータ・サイエンスの講義録第１８０７巻１３９頁から１５５頁、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、２０００年５月によって開示されているようにパスワードのみのモデルにおける理論的な研究自体が成長しつつある中で行われた。これらの論文の大部分は、パスワードおよび関連する記憶された秘密は、暴力によってクラックされうるものか、またはせいぜい解決できないエントロピーを有するものであると保守的に想定される必要があるという点を強調しており、これによってユーザを保護するためのさらなる規準が保証される。
【００１９】
本発明の譲受人によって開発されたＳＰＥＫＥ方法は、交換の基数がパスワードによって決定される周知のＤｅｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＨ）指数鍵交換の認証された形式である。ＳＰＥＫＥの一般に使用される形式では、パスワードは、導出されたＤｉｆｆｉｅ−Ｈｅｌｌｍａｎセッション鍵の相互認証を規定する。ＳＰＥＫＥの変形態様は、係属中の米国特許出願第０８／８２３，９６１号およびＤ．ＪａｂｌｏｎによるＳｉｘｔｈ  Ｗｏｒｋｓｈｏｐｓ  ｏｎ  Ｅｎａｂｌｉｎｇ  Ｔｅｃｈｎｏｌｏｇｉｅｓ：Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ  ｆｏｒ  Ｃｏｌｌａｂｏｒａｔｉｖｅ  Ｅｎｔｅｒｐｒｉｓｅｓ（ＷＥＴ−ＩＣＥ’９７）Ｅｎｔｅｒｐｒｉｓｅ  Ｓｅｃｕｒｉｔｙ  Ｗｏｒｋｓｈｏｐ、ＩＥＥＥコンピュータ・ソサエティ、１９９７年６月１８日から２０日の議事録２４８頁から２５５頁の「Ｅｘｔｅｎｄｅｄ  Ｐａｓｓｗｏｒｄ  Ｐｒｏｔｏｃｏｌ  Ｉｍｍｕｎｅ  ｔｏ  Ｄｉｃｔｉｏｎａｒｙ  Ａｔｔａｃｋ（ディクショナリ攻撃に影響されない拡張型パスワード・プロトコル）」題する論文、およびＲ．ＰｅｒｌｍａｎおよびＣ．Ｋａｕｆｍａｎによる「Ｓｅｃｕｒｅ  Ｐａｓｓｗｏｒｄ−Ｂａｓｅｄ  Ｐｒｏｔｏｃｏｌ  ｆｏｒ  Ｄｏｗｎｌｏａｄｉｎｇ  ａ  Ｐｒｉｖａｔｅ  Ｋｅｙ（秘密鍵をダウンロードするための安全なパスワードベースのプロトコル）」、１９９９  Ｎｅｔｗｏｒｋ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍ  Ｓｅｃｕｒｉｔｙ  Ｓｙｍｐｏｓｉｕｍ、インターネット・ソサエティ、１９９９年２月３日から５日の議事録にも記載されている。
【００２０】
複数のマシン間で分割鍵を使用するＳＰＥＫＥ使用可能システムは本明細書ではＳＫ１と称するが、Ｄ．Ｊａｂｌｏｎによる１９９９年１月２１日の１９９９年ＲＳＡデータ・セキュリティ会議９９での「Ｓｅｃｒｅｔ  Ｐｕｂｌｉｃ  Ｋｅｙｓ  ａｎｄ  Ｐａｓｓｗｏｒｄｓ（秘密公開鍵とパスワード）」と題する講義で提示されたものであり、このスライドは＜ｈｔｔｐ：／／ｗｗｗ．ＩｎｔｅｇｒｉｔｙＳｃｉｅｎｃｅｓ．ｃｏｍ／ｒｓａ９９／ｉｎｄｅｘ．ｈｔｍｌ＞で公開されている。このシステムでは、Ａｌｉｃｅの秘密鍵であるＵは、パスワード導出シェアＰと、２つの大きなシェアであるＸとＹの３つのシェアに分割される。これらのシェアは、Ｕ＝Ｐ（○＋）Ｘ（○＋）Ｙとして（○＋）関数（ビット単位の排他的論理和）を使用して結合される。ＳＫ１の登録と鍵の取り出しプロセスについては以下で概説する。（訳注：明細書中（○＋）は○の中に＋が入っている排他的ＯＲ演算を現す記号の代わりである）
【００２１】
ＳＫ１登録で、Ａｌｉｃｅは３つのシェア｛Ｐ、Ｘ、Ｙ｝を選択し、それらのシェアのうちの２つを結合して機密の秘密鍵Ｓ（Ｓ＝Ｐ（○＋）Ｘとして）を作成し、Ｐを記憶し、ＡｌｉｃｅのマシンにＸを記憶する。次いで、複数の他の形式がＪａｂｌｏｎの１９９７年６月の論文に記載されているＢ−ＳＰＥＫＥプロトコルの形式を使用して、Ａｌｉｃｅはパスワード導出値｛Ｐ、Ｓ｝に対応する検証子｛ｇ、Ｖ｝を以下のように構築する。すなわち、暗号ハッシュ関数を使用したｇ＝ハッシュ（Ｓ）と、適切なグループの累乗法を使用したＶ＝Ｐである。Ａｌｉｃｅは次いでＢｏｂに｛ｇ、Ｖ、Ｙ｝を送信し、ＢｏｂはそれらをＡｌｉｃｅの秘密として記憶する。
【００２２】
ＳＫ１鍵取り出しで、Ａｌｉｃｅは（後刻）ＢｏｂからＡｌｉｃｅ自身の秘密鍵Ｕを得る。Ａｌｉｃｅは、Ｂ−ＳＰＥＫＥプロトコルを使用してＢｏｂに対してＰとＳに関するＡｌｉｃｅ自身の知識を証明し、Ｂｏｂと認証されたセッション鍵Ｋを交渉する。Ｂｏｂが｛ｇ、Ｖ｝に対するＢｏｂ自身の知識を使用してＡｌｉｃｅを検証した後、ＢｏｂはＫで対称的に暗号化されたＹをＡｌｉｃｅに送信する。Ａｌｉｃｅは次いで解読してＹを取り出し、Ｕを再構築する。このシステムにおけるパスワード導出値Ｐに対する暴力的な攻撃は、攻撃者が２つの異なるマシン上に記憶されているシェアＸとＹの両方に対するアクセス権を有することを必要とする。
Ａ：      Ｓ＝Ｐ（○＋）Ｘ
Ａ：      ｇ＝ハッシュ（Ｓ）
Ａ→Ｂ：  Ａ、ＱＡ＝ｇ２ＲＡ
Ｂ→Ａ：  ＱＢ＝ｇ２ＲＢ
Ａ：      Ｋ１＝ＱＢＲＡ
Ａ：      Ｋ２＝ＱＢＰ
Ｂ：      Ｋ１＝ＱＢＲＡ
Ｂ：      Ｋ１＝Ｖ２ＲＢ
Ａ→Ｂ：  ハッシュ（ハッシュ（Ｋ１、Ｋ２））
Ｂ→Ａ：  暗号化（Ｋ、Ｙ）
Ａ：      Ｕ＝Ｐ（○＋）Ｘ（○＋）Ｙ
ＳＫ１でＰに対する暴力的な攻撃を可能にするには、攻撃者はＸとＹの両方へのアクセス権を有する必要がある。（訳注：明細書中上付き文字Ｒの次の下付き文字Ａ、ＢはいずれもＲの下付き文字である）
【００２３】
ローミング・モデルとパスワードのみの方法は、ＥＫＥとＳＰＥＫＥの両方に基づくプロトコルを作成するためにＰｅｒｌｍａｎとＫａｕｆｍａｎの論文で結合された。これらの筆者は、信用証明書に対する安全なローミングのアクセスにはパスワードのみの方法の単純な形式で十分であることを示した。Ｇｏｎｇ，Ｌｏｍａｓ，ＮｅｅｄｈａｍおよびＳａｌｔｚｅｒの論文、Ｗｕの論文、Ｓ．ＨａｌｅｖｉおよびＨ．Ｋｒａｗｃｚｙｋの論文「Ｐｕｂｌｉｃ−ｋｅｙ  ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  ｐａｓｓｗｏｒｄ  ｐｒｏｔｏｃｏｌｓ（公開鍵およびパスワード・プロトコル）」ｔｈｅ  Ｆｉｆｔｈ  ＡＣＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ，１９９８年の議事録、およびＰ．ＭａｃＫｅｎｚｉｅおよびＲ．ＳｗａｍｉｎａｔｈａｎのＩＥＥＥＰ１３６３作業部会への提出物である論文「Ｓｅｃｕｒｅ  Ｎｅｔｗｏｒｋ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ｗｉｔｈ  Ｐａｓｓｗｏｒｄ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ（パスワード識別による安全なネットワーク認証）」ｈｔｔｐ：／／ｇｒｏｕｐｅｒ．ｉｅｅｅ．ｏｒｇ／ｇｒｏｕｐｓ／１３６３／、１９９９年７月３０日では他のローミング・プロトコルが議論されているが、これらはすべて鍵のクライアント記憶が実用的でない場合に強力なソフトウェアベースの保護を提供するためにネットワーク・メッセージに対するオフラインでの予測による攻撃を停止するように設計されている。
【００２４】
変形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎは、１９９４年８月のＣＲＹＰＴＯ‘９４のセッションで提示された「Ａｎ  ｅｎｃｒｙｐｔｅｄ  Ｋｅｙ  Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｐｒｏｔｏｃｏｌ（暗号化された鍵伝送プロトコル）」と題する論文でＥｒｉｃ  Ｈｕｇｈｅｓによって記載され、またＢ．Ｓｃｈｎｅｉｅｒ著、１９９６年Ｗｉｌｅｙ＆Ｓｏｎｓから出版の「Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｓｅｃｏｎｄ  Ｅｄｉｔｉｏｎ（応用暗号化第２版）」と題する書籍の５１５頁に記載された方法である。通常のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎでは、クライアントとサーバの両方が固定したｇを知っており、共同してＫ＝ｇｘｙを交渉する。しかし変形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎでは、クライアント（Ａｌｉｃｅ）はｇｘを送信し、ｇｘｙを受信し、サーバからＫ＝ｇｙを取り出す。Ａｌｉｃｅの秘密指数ｘはブラインディング係数として使用される。鍵は、Ｋ：＝（ｇｘｙ）１／ｘのようにサーバの値を逆転したｘ乗することによって取り出される。通常のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ方法とは異なり、Ｋに対する静的な値は、サーバがクライアントの（Ａｌｉｃｅの）ｇＸを受信する前にでさえ事前計算することができる。
【００２５】
変形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎに基づくＳＰＥＫＥの一形式は本明細書では変形ＳＰＥＫＥと称するが、これは米国特許出願第０８／８２３，９６１号に記載されている。変形ＳＰＥＫＥで、Ａｌｉｃｅは、Ｐに関するＡｌｉｃｅ自身の知識、Ａｌｉｃｅ自身のパスワードから導出された値、およびＢｏｂに知られているランダム値に基づく鍵Ｋを導出する。Ａｌｉｃｅはパスワードを秘密のランダムなベキｘ乗し、その結果生じた値（ＱＡ）をＢｏｂに送信する。ＢｏｂはＱＡをｙ乗し、その結果（ＱＡ）をＡｌｉｃｅに戻す。Ａｌｉｃｅは、Ｋ＝Ｐｙという結果になるようにＱＢをｘの反転乗することによってＫを計算する。
0004833489.tif 000002
【００２６】
Ｐは、適切な大きな有限群のジェネレータを生じるＳＨＡ１またはＭＤ５などのパスワードの暗号ハッシュ関数であることが推奨される。さらなる詳細は、米国特許出願第０８／８２３，９６１号およびＳＰＥＫＥに関する他の論文に記載されている。
【００２７】
盗まれた検証データのリスクを分散するために、データを複数のマシン間で分割することができる。複数のマシンを使用するネットワーク・プロトコルの設計には、パスワード導出データに対する攻撃の新しい手段を露呈することを防止するための注意が必要である。
【００２８】
ディクショナリ攻撃から保護しているシステムに対する別の手法は、１９９９年ＩＥＥＥＳｙｍｐｏｓｉｕｍ  ｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙの議事録のＤ．ＨｏｏｖｅｒおよびＢ．Ｋａｕｓｉｋによる「Ｓｏｆｔｗａｒｅ  Ｓｍａｒｔ  Ｃａｒｄｓ  ｖｉａ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｃａｍｏｆｌａｕｇｅ（暗号カモフラージュによるソフトウェア・スマートカード）」で議論されるように、暗号カモフラージュ（本明細書ではＣＣと称する）と称される技術である。ＣＣシステムは、サーバに記憶されている検証データの脆弱性を低減するという現段階での目的とは対照的に、クライアントに記憶されている秘密鍵の脆弱性を低減させるように導入されたものである。
【００２９】
ローミングするユーザを支援するために少なくとも１つのＣＣシステムが変更されており、それは２つのサーバのローミング解決法を提供する。次に、２つのサーバ・ローミング版を議論する前に基本的なＣＣシステムを議論するが、この基本的なＣＣシステムにはユーザと、クライアント・マシンと、ＣＣ認証サーバ（ＣＣＡＳ）が含まれる。
【００３０】
ＣＣは、公開鍵技術の原理の一部には明らかに違反するが、ＨｏｏｖｅｒおよびＫａｕｓｉｋの論文で議論された目的を達成するように設計された１組の規定による方法で公開鍵技術を使用する。「ＣＣ秘密鍵」および「ＣＣ公開鍵」という用語は、システムの２つの構成要素を示すために使用される。
【００３１】
用語「ＣＣ秘密鍵」および「ＣＣ公開鍵」の「秘密」と「公開」の用法には、用語「秘密鍵」および「公開鍵」の通常の使用法とは一致しない特別な意味があることに留意されたい。具体的には、ＣＣモデルは、ＣＣ公開鍵が公的に知られていないことを前提としている。
【００３２】
ＣＣ秘密鍵はクライアントに記憶されるが、小さな個人識別番号（ＰＩＮ）と共に隠蔽される方法で記憶される。これは、記憶されている秘密鍵を同等に信頼できる任意の予想されるＰＩＮによって解読する特別の構築を使用する。（この問題は、人間の選択対マシン生成ＰＩＮと、ＰＩＮに対する敵の部分的な知識と、関連する脅威とを考察する際に後で議論する。）
【００３３】
信頼される関係者だけがＣＣ公開鍵を知る必要がある。ＣＣ暗号化秘密鍵が盗まれた場合、ＣＣ公開鍵を所有していることによって盗用者はＰＩＮに対するディクショナリ攻撃を行う能力を得る。セキュリティの目的を満たすために、ＣＣ公開鍵はＣＣＡＳだけに知られる必要がある。実際には、クライアントは、ＣＣＡＳだけがそれを読み取ることができるようにＣＣＡＳ公開鍵の下で暗号化された形式でＣＣ公開鍵を記憶することができる。クライアントは、いつＣＣＡＳに対して認証したとしてもこの暗号化されたパッケージをＣＣＡＳに送信する。
【００３４】
同様に、ユーザのＣＣ秘密鍵によって署名された任意のデジタル署名は、ＣＣＡＳだけに可視的である必要がある。したがってメッセージはまずＣＣ秘密鍵によって署名され、次いでＣＣＡＳ公開鍵によって封印される。
【００３５】
ＨｏｏｖｅｒおよびＫａｕｓｉｋの状態は、検証可能な平文を含んでいるＣＣ秘密鍵の下で暗号化された任意のメッセージはＣＣＡＳだけに知られる必要があるというより自由な制約であることに留意されたい。実際には、検証可能な平文からは自由である有用なメッセージを作成することは非常に困難であることに留意されたい。平文は検証可能ではないという前提は、適切な検証方法を作成することが攻撃者の巧妙さに依存するシステムのセキュリティに関する問題を未解決のままとする。これらのような未解決の問題は現在のモデルでは受け入れることができず、したがってこの制約に対するより厳格な命題が使用される。以下にＣＣシステムの概要を示す。
【００３６】
ＣＣ登録では、クライアントはＰＩＮであるＰ、秘密鍵であるＥＣ、および対応する公開鍵ＤＣを選択する。ＣＣがＥＣとＤＣの構築に対して課すさらなる制約があるが、これらについてはここで考察する必要はない。クライアントは以下を記憶する。
ＣＣ（Ｐ、ＥＣ）  カモフラージュされた秘密鍵
ＤＳ              ＣＣＡＳの公開鍵
ＤＳ（ＤＣ）      ＣＣＡＳに対して封印されたクライアントの公開鍵
【００３７】
ＣＣ認証で、ユーザはＰを入力し、クライアントはＣＣ（Ｐ、ＥＣ）からＥＣを取り出す。クライアントはＣＣＡＳに、
ＤＳ（ＥＣ（メッセージ））と、
ＤＳ（ＤＣ）とを送信する。
【００３８】
ＣＣＡＳはそのメッセージを認証するためにＥＣ（メッセージ）とＤＣの両方を開封し、クライアントの署名を検証する。
【００３９】
ＤＣには、ＣＣＡＳのために鍵の有効性を証明する適切な１組の信用証明書が伴うことを想定することができよう。しかし、ＤＣがクライアントとＣＣＡＳによって共有される秘密のままでなければならないと仮定すると、第３者の信用証明書オーソリティを使用してＤＣを証明するための通常の方法は除外されるだろう。ＣＣ秘密鍵とＣＣ公開鍵に対するそれらの制約は共に、いかなる本当の公開鍵システムで使用するためにもそれらが不適切であるということを明らかにしている。
【００４０】
ＣＣでは、ＰＩＮは事実上次の２つの部分に分割される。
ＣＣ（Ｐ、ＥＣ）    クライアントにだけ知られている
ＤＣ                サーバにだけ知られている
【００４１】
一般に、ＥＣの下で署名されるかまたはＤＣの下で封印されたすべてのさらなるメッセージは、ＤＳの下でも封印される必要がある。本発明によると、これは２つのサーバによる解決法に変換することができる。
【００４２】
ＣＣシステムは、クライアントでのパスワード入力の際のタイピング・エラーを検出する機能によって特別の方法でパスワード入力エラーに対処する。クライアントは、少量のハッシュされたパスワードをクライアントにローカルに記憶された参照データと比較する。しかしこの機構は、記憶されたクライアント・データへのアクセス権を得ている敵に対してパスワードに関する情報を数ビットをリークするという大きな損失を有する。結果は、オンライン予測攻撃に対する所与のレベルのセキュリティに対して、ＣＣシステムのパスワードが若干大きくなるかまたはより複雑になる必要があり、したがって記憶することがより困難になることになる。クライアント上での早期のエラーの検出がサーバ上での不要の作業を防止するという点において、システム上での計算の困難さを軽減するために人がもう少し努力することができるという想定でＣＣエラー取り扱い機能が設計された。別の理念は、人間がしなければならない作業を軽減するためにコンピュータが使用されるべきであるというものである。システムは、ユーザに罰則を課さずにユーザの誤りに耐性を有しながら依然としてパスワード予測攻撃に対する予測し得る最高の障壁を維持するために努力すべきである。パスワードの入力における悪意のない誤りに最適に対処するシステムは、本発明の好ましい実施態様に含まれる。
【００４３】
ローミングの解決法は、公開鍵のインフラストラクチャ（ＰＫＩ）を提供する複数の企業によって、主としてスマート・カードが使用不可能な場合に「ローミング」ユーザを認証する目的で設計され開発されてきた。このようなシステムでは、ユーザは、＜ｈｔｔｐ：／／ｗｗｗ．ｉｎｔｅｇｒｉｔｙｓｃｉｅｎｃｅｓ．ｃｏｍ／ＰＫＩ５０．ｈｔｍｌ＞で入手可能なＪ．Ｋｅｒｓｔｅｔｔｅｒ著「Ｅｎｔｒｕｓｔ，ＶｅｒｉＳｉｇｎ  ｃｌｅａｒ  ｐａｔｈ  ｔｏ  ＰＫＩ」ＰＣ  Ｗｅｅｋ、１９９９年６月１４日によって議論された遠隔信用証明書サーバから記憶されているユーザ・プロファイル（通常はユーザの秘密鍵を含んでいる）を安全に取り出す。信用証明書サーバに関する他の研究は、ＰｅｒｌｍａｎおよびＫａｕｆｍａｎの論文に記載のＥＫＥおよびＳＰＥＫＥの変形態様を使用する。
【００４４】
上述の暗号カモフラージュ・システムは、単一のＣＣサーバを前提としており、またユーザの鍵情報はクライアントに記憶されていることを前提としている。クライアントに記憶されているデータをＣＣローミング・サーバ（ＣＣＲＳ）に移動し、第２のユーザのパスワードに関する追加の検証データをＣＣＲＳに提供することによって、ＣＣローミングと称される２つのサーバのローミング解決法にこの方法を変換することができる。
【００４５】
ユーザは、パスワードと、ＣＣＲＳに対してクライアントに安全に情報を戻すことができるようにする適切なパスワード認証プロトコルとを使用してＣＣＲＳに対して認証する。これは、検証子ベースの、またはいわゆる「拡張」ゼロ知識パスワード・プロトコルを使用することが好ましい。しかし、サーバ認証済みのＳＳＬ（セキュア・ソケット層）またはＴＬＳチャネルを介して検証のためにＣＣＲＳにクリア・テキストを送信することを含めた代替構築も可能である。ＳＳＬは、Ａ．Ｆｒｉｅｒ，Ｐ．ＫａｒｌｔｏｎおよびＰ．Ｋｏｃｈｅｒによる「Ｔｈｅ  ＳＳＬ  ３．０  Ｐｒｏｔｏｃｏｌ（ＳＳＬ３．０プロトコル）」１９９６年１１月１８日、Ｎｅｔｓｃａｐｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｃｏｒｐ．で議論されており、ＴＬＳは、Ｔ．ＤｉｅｒｋｓおよびＣ．Ａｌｌｅｎによる「Ｔｈｅ  ＴＬＳ  Ｐｒｏｔｏｃｏｌ  Ｖｅｒｓｉｏｎ１．０（ＴＬＳプロトコル、バージョン１．０）」１９９９年１月、ＩＥＴＦ  ＲＦＣ  ２２４６、ｈｔｔｐ：／／ｗｗｗ．ｉｅｔｆ．ｏｒｇ／ｒｆｃ／ｒｆｃ２２４６．ｔｘｔ、Ｉｎｔｅｒｎｅｔ  Ａｃｔｉｖｉｔｉｅｓ  Ｂｏａｒｄで議論されている。上述のように、完全な安全性のためには、ＣＣＡＳ  ＰＩＮおよびＣＣＲＳパスワードを完全に独立した値として選択する必要がある。これらの値が関連する場合、パスワードに対する攻撃はＰＩＮの露出に繋がる危険性がある。
【００４６】
本質的に、ＣＣローミングは、ＣＣＲＳ用の１つのパスワードとＣＣＡＳ用のもう１つのパスワード（ＰＩＮ）との２つのパスワードのシステムである。ＣＣローミングの１つの顕著な限界は、第１のサーバが第１のパスワードに対する暴力的な攻撃を仕掛ける機会を有するということである。他の２つの関連する問題は、クライアントのエントロピーを使用することの有効性と、ＰＩＮとパスワードの独立性とである。
【００４７】
ＣＣＲＳに対して認証するためにパスワードを介したＳＳＬと共にＣＣローミングを使用する場合、Ｅ．Ｆｅｌｔｏｎ，Ｄ．Ｂａｌｆａｎｚ，Ｄ．ＤｅａｎおよびＤ．Ｗａｌｌａｃｈによる「Ｗｅｂ  Ｓｐｏｏｆｉｎｇ：Ａｎ  Ｉｎｔｅｒｎｅｔ  Ｃｏｎ  Ｇａｍｅ（ウェブ・スプーフィング：インターネット詐欺）」２０ｔｈ  Ｎａｔｉｏｎａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｙｓｔｅｍｓ  Ｓｅｃｕｒｉｔｙ  Ｃｏｎｆｅｒｅｎｃｅ，１９９７年１０月７日から１０日、Ｂａｌｔｉｍｏｒｅ，Ｍａｒｙｌａｎｄと，ｈｔｔｐ：／／ｗｗｗ．ｃｓ．ｐｒｉｎｃｅｔｏｎ．ｅｄｕ／ｓｉｐ／ｐｕｂ／ｓｐｏｏｆｉｎｇ．ｈｔｍｌで議論されたサーバ・スプーフィング攻撃と、後述する関連するパスワード／ＰＩＮ攻撃との両方によるさらなるリスクがある。これらのすべてのケースでは、２つのサーバのうちの１つが攻撃された場合に２つのサーバによる手法の利点の一部が失われる危険性がある。ＣＣＲＳに対して認証するためにゼロ知識パスワード・プルーフを使用することによってサーバ・スプーフィング攻撃は解消され、関連するＰＩＮ／パスワード攻撃をより困難にすることができる。
【００４８】
ＣＣローミング・システムは、貴重かつ希少な資源であると考えられるに違いないユーザのパスワードに本来備わっているエントロピーを浪費している。パスワードによる方法の主目的は、所与のレベルのセキュリティを達成するためにユーザが記憶しなければならない情報量（上位ビット数）を最低限に抑えることであることを想起されたい。ＣＣローミング・システムはこれらのビットを浪費し、数点の脆弱性をもたらしている。第１に、ＨｏｏｖｅｒおよびＫａｕｓｉｋは、プロトコル実行前のＰＩＮの事前資格審査用にＰＩＮのいくつかのビットを使用するよう提案している。かれらは、特別に構築されたＰＩＮの小さなハッシュをクライアントに付加的に記憶することによってこれを行う。攻撃者は、候補ＰＩＮの空間を低減するためにハッシュされたＰＩＮを使用することができる。ＰＩＮのサイズが既に低減されたことを考慮すると、これは危険である。ユーザが選択したＰＩＮが許可されるということは、有効なＰＩＮの空間を危険なレベルにまで低減させることに繋がりかねない。
【００４９】
ＣＣローミング・システムは、ユーザの秘密のエントロピーを人工的に分割するＡＳ  ＰＩＮとＲＳパスワードの２つのパスワード間の関係によっても損傷を受けやすい。ＨｏｏｖｅｒおよびＫａｕｓｉｋはカモフラージュされたＡＳ  ＰＩＮが他のいかなる目的にも使用されることがあってはならないと明言している。しかしユーザがＡＳ  ＰＩＮをＲＳパスワードに誤って組み込んだ場合、またはこれらの秘密の間に攻撃者に知られ得る対応関係がある場合、ＣＣローミングの基礎をなすＣＣシステムは攻撃に対して脆弱になる。
【００５０】
関連するパスワード／ＰＩＮ攻撃は、ユーザがこれらを同じ値として選択した場合、あるいは明らかに区別可能なまたは場合によってはかろうじて区別可能な関係性をもって識別可能な値として選択した場合に可能である。本当に独立したＰＩＮとパスワードとを有するユーザが、これらの一方の場所に誤って他方をタイプした場合にも危険はある。
【００５１】
複数のユーザに対する広域的な攻撃を想定した場合、まず弱いＲＳパスワードを有するユーザをクラックすることによって目標空間を縮小し、次いでそれらクラックされたユーザの対応するＡＳ  ＰＩＮをクラックするためにそれらユーザの集合に作業を集中させることができる。このようなＲＳパスワードに関する情報のリークは、潜在的な攻撃者の全体的な作業を低減させることができる。対照的に、同じＲＳパスワードとＡＳ  ＰＩＮとを結合すると、理想的な２つのサーバによるシステム（後述する）は、パスワードとＰＩＮの両方に依存するクラッキング作業要因を有することになり、より大きな全体的な作業要因が必要となる。
【００５２】
したがって、ＣＣローミング・システムに対して秘密を２つの要因に人工的に区画することは新たな脆弱性をもたらし、モデルを弱める。好ましい実施態様の説明では、ＣＣおよびＣＣローミングに対するより簡単な代替態様は、より強力だが複雑さの点ではより低下しており、ユーザが記憶している秘密に対して少なくとも同等の保護を有するものとして記載されている。
【００５３】
すべての単一サーバのローミングによる解決法はインターネットの限界を有する。上記のローミング方法のすべてにおいて、単一の信用証明書サーバは、ユーザのパスワードに関する情報を検証するために使用することができるデータを維持する。ハッシュされたパスワードが暴力によって破壊される危険性があると仮定した場合、パスワード検証サーバは基本的にこの機密のユーザのデータに対して単一の障害点を表すことになる。次に、この問題に対処するシステムを説明する。
【００５４】
複数サーバのローミングはさらなる進歩を示す。単一サーバによるシステムはクライアントおよびネットワークからの予測攻撃は防止するが、サーバから盗まれる可能性のあるパスワード検証データに基づく予測は停止させない。複数のサーバによるローミング・システムは、このような攻撃を驚異的な程度にまで防止することができる。認証するためにｎ個の関連する信用証明書サーバを使用するという代償を払って、複数のサーバによるシステムは、信用証明書サーバのデータベースに対する保護の範囲を拡張する。これらのシステムでは、敵はｎ−１個のサーバを完全に制御し、有効なユーザの成功裡の信用証明書の取り出し中にこれらのサーバのオペレーションを監視することができるが、それでもなお、残りの損なわれていないサーバによって検出されずに誰のパスワードに対しても１つも予測を検証することはできない。
【００５５】
２０００年６月、ＶｅｒｉＳｉｇｎは、２０００年５月に「ＶｅｒｉＳｉｇｎ  Ｉｎｔｒｏｄｕｃｅｓ  Ｎｅｗ  Ｔｅｃｈｎｏｌｏｇｙ  ｔｏ  Ｅｎａｂｌｅ  Ｎｅｔｗｏｒｋ−Ｂａｓｅｄ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ，Ｄｉｇｉｔａｌ  Ｓｉｎｇｎａｔｕｒｅｓ  ａｎｄ  Ｄａｔａ  Ｐｒｉｖａｃｙ（ネットワークベースの認証、デジタル署名およびデータ・プライバシーを可能にする新しい技術をＶｅｒｉＳｉｇｎが紹介する）」という広報を発表し、高レベルでの複数のサーバによるローミング機能を説明したｈｔｔｐ：／／ｗｗｗ．ｖｅｒｉｓｉｇｎ．ｃｏｍ／ｒｓｃ／ｗｐ／ｒｏａｍｉｎｇ／ｉｎｄｅｘ．ｈｔｍｌにあるウェブページを公表した。Ｗ．ＦｏｒｄおよびＢ．Ｋａｌｉｓｋｉによる「Ｓｅｒｖｅｒ−Ａｓｓｉｓｔｅｄ  Ｇｅｎｅｒａｔｉｏｎ  ｏｆ  ａ  Ｓｔｒｏｎｇ  Ｓｅｃｒｅｔ  ｆｒｏｍ  ａ  Ｐａｓｓｗｏｒｄ（サーバ支援によるパスワードからの強力な秘密の生成）」と題する論文は２０００年６月１４日のＧａｉｔｈｅｒｓｂｕｒｇ  ＭＤでのＩＥＥＥ  Ｎｉｎｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐｓ  ｏｎ  Ｅｎａｂｌｉｎｇ  Ｔｅｃｈｎｏｌｏｇｉｅｓ：  Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ  ｆｏｒ  Ｃｏｌｌａｂｏｒａｔｉｖｅ  Ｅｎｔｅｒｐｒｉｓｅｓで提示された。この論文の改定版は、２０００年９月の議事録に発表された（Ｗ．ＦｏｒｄおよびＢ．Ｋａｌｉｓｋｉ，「Ｓｅｒｖｅｒ−Ａｓｓｉｓｔｅｄ  Ｇｅｎｅｒａｔｉｏｎ  ｏｆ  ａ  Ｓｔｒｏｎｇ  Ｓｅｃｒｅｔ  ｆｒｏｍ  ａ  Ｐａｓｓｗｏｒｄ（サーバ支援によるパスワードからの強力な秘密の生成）」９ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐｓ  ｏｎ  Ｅｎａｂｌｉｎｇ  Ｔｅｃｈｎｏｌｏｇｉｅｓ：Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ  ｆｏｒ  Ｃｏｌｌａｂｏｒａｔｉｖｅ  Ｅｎｔｅｒｐｒｉｓｅｓ、ＩＥＥＥ、２０００年９月の議事録）。これらの論文は、複数のサーバを使用したサーバベースのパスワード・クラッキング攻撃を防止する方法を説明している。２０００年６月１４日、Ｆｏｒｄ＆Ｋａｌｉｓｋｉの論文に記載の方法は従来のサーバ認証チャネルに依存することに留意されたい。パスワードの安全性に関してこのように従来の安全なチャネルに依存することは、不要かつ潜在的にリスクのある安全性の仮定をもたらす。この依存性を除去することが、本発明の利点の１つである。
【００５６】
２０００年６月１４日の論文に記載の方法のうちの１つは、本発明の好ましい実施態様で使用される上述のような変形ＳＰＥＫＥプロトコルを使用する。２０００年６月１４日の論文に記載の様々な方法では、複数のサーバがパスワード検証データの秘密を保持する義務を共有している。各サーバはユーザのために秘密を記憶する。クライアントはユーザからパスワードを獲得し、２ステップのプロセスによって各サーバと連係する。最初にクライアントは各サーバからパスワードに基づいて増幅された鍵を獲得し、次いでサーバのそれぞれに対して認証するために使用される「マスター」鍵を生成する。（本明細書では、ＦｏｒｄおよびＫａｌｉｓｋｉの用語である「強化鍵」の代わりに「増幅された鍵」という用語（ＢｅｌｌｏｖｉｎおよびＭｅｒｒｉｔｔの論文に記載）を使用していることに留意されたい。）各増幅された鍵はユーザのマスター鍵の１つのシェアを表している。クライアントは、マスター鍵を生成する目的で増幅された鍵のシェアを結合するためにハッシュ関数を使用するなどの任意の標準的な技術を使用する。
【００５７】
各増幅された鍵を獲得するために、ＦｏｒｄおよびＫａｌｉｓｋｉは２つの基本的な方法を提案する。１つは上述の変形ＳＰＥＫＥ方法であり、もう１つはＤ．Ｃｈａｕｍによる「Ｓｅｃｕｒｉｔｙ  ｗｉｔｈｏｕｔ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ：Ｔｒａｎｓａｃｔｉｏｎ  Ｓｙｓｔｅｍｓ  ｔｏ  Ｍａｋｅ  Ｂｉｇ  Ｂｒｏｔｈｅｒ  Ｏｂｓｏｌｅｔｅ（識別なしのセキュリティ：ビッグブラザーを陳腐化するトランザクション・システム）」Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ  ２８（１９８５年）１０３０から１０４４に記載のスタイルでブラインドＲＳＡデジタル署名を使用する一変形態様である。これらの方法を以下で比較する。
【００５８】
サーバは無効アクセスの試行を追跡しており、ＦｏｒｄおよびＫａｌｉｓｋｉによると、成功裡の認証に比べてパスワードの増幅に「甚だしく多くの」ステップがある場合、サーバはさらなる要求を制限またはロックアウトする動作をとる。しかしシステムは有効なユーザによってなされた誤りとパスワードに対する本当の攻撃をよりよく反映する他の事象とを区別しない。したがってこの不成功の試行に対処するためのＦｏｒｄおよびＫａｌｉｓｋｉのシステムは、一般的な人間の誤りを最適に扱っていない。単純なタイプミスや他の訂正された誤りによる不成功の増幅は、他の不成功の試行のようにみなされるべきではない。本発明はこれらのケースに対処するよりよい方法を提供する。
【００５９】
２０００年６月１４日の論文の方法は、サーバに対する既にセキュリティ保護されたサーバ認証チャネルにさらに依存している。以前の認証に対するこの依存は不要に複雑なセキュリティ・モデルを作成し、したがって攻撃のリスクは増大した。これらのリスクは、単一の障害点を解消する目的とは相容れない場合がある。
【００６０】
２０００年６月１４日の論文に記載のパスワード増幅方法のうちの１つではＲＳＡブラインド公開鍵署名が使用される。この技術は、変形ＳＰＥＫＥ方法と同様の効果を達成するが、これらはどちらももう一方の関係者に周知のランダム成分に基づいてパスワードを増幅して大きな鍵にするものである。しかしＲＳＡ方法はさらに複雑である。ＲＳＡブラインディング方法の詳細はＦｏｒｄおよびＫａｌｉｓｋｉの論文には含まれていないが、Ｃｈａｕｍブラインディングへの参照に基づく一方法は以下のように機能すると想定される。
【００６１】
単一の値ｙの代わりに、サーバは各ユーザに対して値｛ｎ，ｅ，ｙ｝を維持する。これらの値はどれもパスワードからは導出されない。値ｎは、ｐとｑをＲＳＡモジュールに適した素数とした場合にｐ・ｑに等しく、ｅはＲＳＡ公開鍵であり、ｙは対応する秘密鍵であり、したがってｅ＝１／ｄ  ｍｏｄ（ｐ−１）（ｑ−１）である。基本的に、増幅された鍵はパスワードに対するＲＳＡ署名であるＫＢである。ｘを使用すると、これは、ブラインディング係数ｘが、それが署名しているデータ（Ｐ）をサーバが知ることを防止するＣｈａｕｍの論文に記載のブラインド公開鍵署名方式となる。
【００６２】
２０００年６月１４日の論文では、クライアントに対してＫＢの認証を保証する目的でチャネルを認証するためにＳＳＬが使用されることが提案されている。この論文は、ＲＳＡのブラインディング・クライアントが、サーバを事前認証することによる他にｎとｅの値を検証する良好な（すなわち有効な）方法をまったく有しないという点で、ＲＳＡブラインディングに勝る変形ＳＰＥＫＥの利点も指摘している。
【００６３】
ＦｏｒｄおよびＫａｌｉｓｋｉは、（従来型）信用証明書サーバに対して認証するために使用される鍵Ｋ１にパスワードを増幅するために「パスワード強化サーバ」が使用される「特別なケース」のプロトコルをさらに提案している。Ｋ１の値はパスワード強化サーバの応答およびそのパスワードによって完全に決定される。第１の交換を制御する任意の攻撃者は、ユーザが計算するＫ１の値が、ユーザがＰ’に対する自身の予測に基づいて構築する候補Ｋ１’の値に等しいかどうかを判定することができるようであってはならない。したがって攻撃者はＫ１を決して見てはいけない。同様に、Ｋ１によって暗号化されたメッセージが検証可能な平文を含んでいる場合、攻撃者は同様にそこから予測を検証することができる。この脅威に対抗するために、筆者らは信用証明書サーバ通信チャネルが完全に保護されることを提案する。２０００年６月１４日の論文は明示的な方法は特定しないが、ＳＳＬの使用を提案している。（２０００年９月の論文は事前にセキュリティ保護されたチャネルの必要性を回避する方法を議論していることに留意されたい。）クライアントのルート信用証明書の共通のセットが両方のサーバを検証することができると想定される場合、１つまたは複数の単一の障害点がシステムにもたらされる。秘密鍵が常駐する各場所にルートまたは任意の副次的な信用証明書オーソリティに対して単一の故障点がある。このモデルの主目的として単一の故障点を解消することであるということが重大である。
【００６４】
前述の攻撃は、当該２つのサーバに対する一見有効そうな信用証明書チェーンを作成するための鍵を有する任意の単一のシステムを損なうことによって達成することができる。さらに前述のように、セキュリティのＳＳＬ／ウェブ・ブラウザ・モデルに対する攻撃は、ユーザを騙して悪意のあるサーバへの「有効」ＳＳＬ接続を使用させるか、またはＳＳＬを一切使用させないようにすることができる。
【００６５】
以前のサーバ認証に対する依存は重大な制約である。公衆キオスク、または異なるドメインの広範な様々なサーバに接続可能な個人向けデスクトップなどの消費者環境では、ユーザは適切なサーバの位置を特定してそこに接続する必要がある。適切なサーバに安全に接続し、パスワードの安全性を維持することをユーザに依存することによって問題が生じる。ＦｏｒｄおよびＫａｌｉｓｋｉは安全なサーバ認証チャネルを作成するためにクライアントがＳＳＬを使用できる方法を議論している。これは、クライアントがパスワードのセキュリティを維持するために（何らかの形で）サーバの識別を検証する必要があることを暗示している。また、一般的な実施態様では、サーバに対して通信チャネルを認証するためのサーバ特有状態情報をクライアントが記憶することも暗示している。サーバに対して安全なチャネルを確立するために、ＳＳＬ解決法は一般的に、クライアントにインストールされた１つまたは複数の信用証明書オーソリティに対して事前インストールしたルート鍵を有することを要求する。これはまた、指名されたサーバのルート鍵と公開鍵を関連付けるように構築した信用証明書のチェーンに対するアクセスをも要求する。クライアントは、ユーザが選択した適切な１つの（または複数の）サーバの信用証明書を検証する信用証明書検証ソフトウェアおよびポリシーの施行を含める必要がある。最後に、ユーザはサーバ・ネームのバインディングが正確であることを保証する必要がある。これは、ユーザによる多大の動作と注目とを必要とする場合がある。特にブラウザ・モデルで使用されるようなＳＳＬへの依存は不必要に危険である。ユーザは、悪意のあるサーバへの「有効」ＳＳＬ接続を使用するか、またはＳＳＬを一切使用しないように騙される危険性がある。このプロセスは、「人間の誤り」に属する可能性のあるいくつかのタイプの障害を被る。問題は、人間の参加者による非現実的な予測に基づくシステム全体の設計ミスであると考えられる。
【００６６】
パスワードの安全性に関する以前のサーバ認証チャネルに対する依存は不要である。本発明の好ましい代替方法は、複数のローミング・ユーザと複数のサーバの環境における通常の人間の挙動によりよく適合したより単純なモデルである。
【００６７】
好ましいセキュリティ・モデルは、どちらも複数のサーバを使用するという点で２０００年６月１４日の論文に類似している。しかし本発明の好ましいモデルでは、クライアントとサーバの間に事前認証された安全なチャネルが存在することは前提ではない。好ましいモデルは、パスワードの安全性を維持するためにサーバの識別を慎重に検証しなければならないという必要性からユーザを解放する。このモデルでは、ユーザは、インターネットで一般的に使用されるような任意の安全でない機構を偶然に使用して自由にサーバを配置することができる。これらの方法は、手動でタイプ（またはミスタイプ）されたＵＲＬ、安全でないＤＮＳプロトコル、信頼性のないサーチ・エンジン、知られていないソースによって収集されたコレクション中のアイテムを「クリックすること」が含まれる。これらすべての方法およびこれ以上の方法は、正確なサーバへの接続を確立するために堅固な複数の方法を提供するが、これらはどれも詐欺師に接続する機会に対しては保証する必要はない。この単純なモデルに提示された最悪の脅威はサービスの拒否の１つであるが、これはより複雑なモデルでは概して常に存在する脅威である。好ましいモデルに付加された利点は、たとえクライアントが詐欺師に接続したとしてもいかなる手段によってもパスワードが絶対に露出しないということである。
【００６８】
従来技術の大部分は、エラーのあるパスワード入力を非常に簡単に取り扱う。２０００年６月１４日の論文では、各サーバが「パスワード強化」ステップ数を追跡できること、またこの数を成功裡の認証数と照合確認することが提案されている。認証よりも「かなり多くの」強化がある場合、そのアカウントはロックアウトされる。これはパスワードベースのシステムにとっては一般的である。しかし不成功のログインも非常に一般的であることに留意されたい。パスワードはしばしばミスタイプされ、ユーザは複数あるパスワードのうちから、最終的に訂正する前に誤った選択肢を入力することがしばしばある場合がある。長期の固定された制限がそのような誤りにある場合、有効な稚拙なユーザはロックアウトされる可能性がある。一方、システムが３対１の試行対成功比に耐える場合、長期にわたる敵による時折の予測攻撃は未検出のままである場合がある。
【００６９】
このエラー取り扱い問題に対処するために、「許容」の概念が本発明に導入された。システムは、知られていないユーザによる無効アクセスの試行と同様の方法で有効なユーザによる一時的な誤りを許し、それを考慮しない。この問題は、本発明の好ましい実施態様で対処される。
【００７０】
したがって、本発明の目的は、サーバベースの攻撃の脅威を、パスワードベースのクライアント／サーバ認証システムの単純なセキュリティ・モデルで可能な限り低減することである。複数のサーバを使用した遠隔ユーザ認証を行うことも本発明の目的である。小さいパスワードのみを使用してクライアントからサーバに対して認証することも本発明の目的である。クライアント・マシン上に記憶されている鍵または信用証明書を必要としない認証を行うことも本発明の目的である。耐障害性のために複数のサーバを使用することも本発明の目的である。いかなる個別サーバに完全に動的なリークがある場合でさえも安全な遠隔パスワード認証を行うことも本発明の目的である。パスワード入力における一般的な人間のエラーによりよく対処することも本発明の目的である。
発明の概要
【００７１】
上記および他の目的を達成するために、本発明は複数のサーバを使用した遠隔パスワード認証を実施するシステム、方法およびソフトウェアを提供する。システム、方法およびソフトウェアは、複数のサーバ・システムでセキュリティを実施するために変形ＳＰＥＫＥの態様を採用する。
【００７２】
本発明によるシステムの一例は、１つまたは複数のクライアントと、ネットワークによって相互に結合されている複数の認証サーバとを含んでいる。このシステムの一例で、クライアントは、ｉを特定のサーバを指定する変数とした場合に各認証サーバから秘密マスター鍵のシェアであるＫｉを取り出すために変形ＳＰＥＫＥを使用する。クライアントはサーバのそれぞれの各シェアを結合してマスター鍵Ｋｍを作成し、このマスター鍵Ｋｍはサーバに対して認証し、そのサーバまたはどこかに安全に記憶されている機密データ（自分の秘密鍵を含めて）を取り出して解読するために使用される。
【００７３】
各認証サーバは、マスター鍵の単一シェアに対応するランダム値ｙｉを個別に知っている。各認証サーバは、クライアントからの最近のアクセス要求のリストを維持し、有効なクライアントから受信したプルーフ・メッセージを検証することによってそれらのアクセスの試行を照合確認する責任をも持つ。具体的には、各サーバは、許容に対する有効な要求を検証することができる場合、有効なユーザのパスワード入力の際の最近の過去のエラーを許す必要がある。
【００７４】
通信チャネルを制御する敵がＡｌｉｃｅを騙して不適切なマスター鍵Ｋｍを使用させることができることを防止するために、Ａｌｉｃｅは、敵に露出する可能性のあるあらゆるデータを作成する際に、使用する前にＫｍが正確であることを確認する。認証ステップは、有効なログインを認証するために、事前の最近の合法だが誤ったログイン試行に対する許容を認証し、要求すると共にＡｌｉｃｅから各サーバへの署名されたメッセージを使用する。
【００７５】
より具体的には、各ｉ番目のシェアＳｉがランダム指数ｙｉ乗されたＡｌｉｃｅのパスワードＰに応じて形成される場合、Ａｌｉｃｅは登録時にマスター対称鍵Ｋｍのｎ個のシェアを作成する。シェアの任意の正確な部分集合の知識を有する攻撃者が同じ範囲のランダム値からＫｍを区別することができないように、このシェアは関数と結合される。次いでＡｌｉｃｅは、ｉ番目のサーバによって緊密に保護された秘密として記憶されるべき各指数ｙｉを何らかの形で伝達する。Ａｌｉｃｅは、また、デジタル署名用の公開／秘密鍵対｛Ｖ、Ｕ｝も選択し、対称的に、自身の暗号化された秘密鍵Ｕｋを作成するためにＫｍから導出された鍵を使用して秘密鍵Ｕを暗号化する。最後に、ＡｌｉｃｅはパスワードをＡｌｉｃｅのマスター鍵にリンクするプルーフ値プルーフＰＫｍを作成する。Ａｌｉｃｅはｎ個のサーバのそれぞれにＶを送信し、便宜的な場所、おそらくはサーバのそれぞれにＵＫおよびプルーフＰＫｍを記憶する。登録プロトコルのフローは、Ａｌｉｃｅの識別Ａを各ｉ番目のサーバＢｉに対して認証する安全なチャネルによって実行される。
クライアント：｛登録、Ａ、Ｖ、ｙｉ｝→Ｂｉ
クライアント：｛記録、Ａ、ＵＫｍ、プルーフＰＫｍ｝→Ｂｉ
【００７６】
鍵取り出しの時点で、自身のマスター鍵を再構成して自身の秘密鍵を取り出すために、ＡｌｉｃｅはパスワードＱのランダムにブラインドされた形式を各サーバに送信する。各サーバは、ユーザのマスター鍵のブラインドされたシェアを表す秘密指数値（Ｒｉ＝Ｑｙｉ）乗されたブラインドされたパスワードを含んでいるブラインドされた応答Ｒｉに応答する。サーバの少なくとも１つはＡｌｉｃｅに対してＡｌｉｃｅの暗号化された秘密署名鍵ＵＫとプルーフＰＫｍをも送信する。
クライアント：｛要求、Ｑ｝→Ｂｉ
サーバＢｉ：｛応答、Ｑｙｉ，Ｕｋ、プルーフＰＫｍ｝→クライアント
（訳注：明細書において上付き文字ｙのあとの下付き文字はｙの下付である）
【００７７】
興味深いことには、ＡｌｉｃｅがＵＫおよびプルーフＰＫｍを取り出すチャネルはそれらの値の保全性を保証する必要はない。これは節４．４でさらに議論する。
【００７８】
Ａｌｉｃｅは、各鍵のシェアを得るために各応答をアンブラインドし、Ａｌｉｃｅのマスター鍵Ｋｍを再構築するためにそのシェアを結合する。Ａｌｉｃｅは次いで、プルーフ値プルーフＰＫｍと自身のパスワードＰとを使用してマスター鍵が正確かどうかを検証する。プルーフが不正確な場合、これは鍵のシェアの少なくとも１つが不正確であることを暗示しており、Ａｌｉｃｅはネットワークに対してＫｍまたはＰに関する任意のさらなる情報を露出せずにそのプロトコルをアボートする必要がある。そうでない場合、Ａｌｉｃｅの暗号化された秘密鍵（および任意の他のデータ）を解読するためにＫｍから導出された鍵が使用され、次いでＡｌｉｃｅは自身の識別を各サーバに提供することによってプロトコルを完了する。各サーバに最近送信された各ブラインドされたパスワードＱに対して、Ａｌｉｃｅはブラインドされたパスワードの署名されたコピーを送信する。
クライアント：｛確認、Ｑ１、署名（Ｕ、Ｑ１）｝→Ｂｉ
クライアント：｛確認、Ｑ２、署名（Ｕ、Ｑ２）｝→Ｂｉ
・・・
【００７９】
各サーバは、Ａｌｉｃｅからの署名されたＱｘ値を最近受信したブラインドされたパスワードのリストと照合し、有効な署名を伴ういかなる一致するエントリをも除去する。残りのエントリは、適切な時間内では確認されなかったとしても、悪質とラベリングされた疑わしい非合法のアクセス試行とみなされることになる。悪いアクセスの試行をカウントすることは、そのカウントが特定の閾値を超える場合にユーザのアカウントに対してさらなるブラインドされたシェアの応答を制限または遅延させるように使用することができる。
【００８０】
Ａｌｉｃｅは自身のマスター鍵を検証する必要がある。上述のように、Ａｌｉｃｅは安全でないチャネルを介して認証を実行することができる。Ａｌｉｃｅは自身の検証子プルーフＰＫｍを取り出し（通常は信用証明書サーバから）、次いでプルーフＰＫｍに対して自身のパスワードの鍵を掛けられたハッシュとそれとを比較することによって再構築されたマスター鍵の有効性を確認する。値が一致しない場合、Ａｌｉｃｅはプロトコルをアボートする。
【００８１】
本発明者らの方法の別の強化は、Ａｌｉｃｅが各サーバに対してマスター鍵の知識をどのように証明するか、また各サーバがこの情報をアクセス試行の独自の記録とどのように照合確認するかに関係している。
【００８２】
各サーバは、マスター鍵に関するＡｌｉｃｅ自身の知識のプルーフを含んでいるＡｌｉｃｅからのメッセージを探し、Ａｌｉｃｅが自身のパスワードを知っているというプルーフの含意によって不正アクセス試行を検出する。有効なプルーフがブラインドされたパスワード値に関連付けられていない場合、サーバはＡｌｉｃｅのアカウントに対して悪いアクセス事象をトリガしなければならない。現在の方法は、Ａｌｉｃｅのプルーフの構築と各サーバがパスワード入力の際のＡｌｉｃｅの誤りを許すためにどのようにプルーフを使用するかという点で従来技術と異なる。
【００８３】
安全なチャネルを使用していない場合、Ｂｉに単純にプルーフを送信することによって攻撃を再実行する方法が露出される場合がある。これを防止するために、プルーフはＡｌｉｃｅから送信されたブラインドされた要求値を組み込んでいる。さらに、Ａｌｉｃｅは時折自分のパスワードをミスタイプすることが容認されており、Ａｌｉｃｅは時期尚早のアカウントのロックアウトの原因となる可能性のある自分の不正アクセスのカウントを増分することによって罰せられることはない。Ａｌｉｃｅが最終的に正確なパスワードを入力することができたことをサーバに対して後で証明することができる場合、各サーバはＡｌｉｃｅの誤りを許すことが望ましい。
【００８４】
許容プロトコルを使用することによって、ユーザの悪意のない誤りは許される。Ａｌｉｃｅは各成功裡の認証の後で、許容に対する要求の形式で最近の以前の無効アクセス試行の証拠を送信する。この証拠を受信して検証すると、各サーバは記録から誤りを消去するか、または訂正された許容可能な誤りとしてこの事象を記録する。この方法でサーバの事象ログを微調整することによって、システム管理者は、有効なユーザが単純に失敗した時点ではなく、システムが本当に危険な時点に関するより詳細な見解を得る。
【００８５】
許容システムは、クライアントの少なくとも１つの署名生成ステップと、サーバのそれぞれに対する１つの署名検証ステップとを要求するように考えられる。計算を最低限に抑えるために（公開署名方法が使用されている場合に計算コストのために重要である場合がある）、署名ステップは、ユーザを認証し、そのユーザから要求が発せられたことを証明する結合された関数を提供する。ユーザに対する有効な認証メッセージを構築する際、クライアントはそのユーザによって発行されたすべての最近のチャレンジ・メッセージの集合を含め、その結果を適切なユーザの鍵によってデジタルに署名し、それをすべてのサーバに送信する。各サーバはユーザを認証するために署名を検証し、同時に自分の最近の許容可能な誤りの証拠を検証する。（これらの署名は、公開鍵デジタル署名システムでクライアントの秘密鍵を使用して作成することができ、クライアントの公開鍵を使用して、または代替方法として、クライアントと各サーバの間で相互に共用される別個の対称鍵によって鍵を掛けられた鍵の掛かったＭＡＣを使用して検証される。）
【００８６】
Ａｌｉｃｅの確認メッセージを受信すると、各サーバはＡｌｉｃｅのアクセス試行のプルーフをサーバの記録された最近の試行リストと照合確認することを試行する。サーバは、各Ｑ値に対するＡｌｉｃｅの署名を検証することによってこれを実行する。検証が成功すると、その要求メッセージがＡｌｉｃｅのマスター鍵を再現するために明確に使用されるかどうかには関わらず、サーバは最終的にパスワードを知っている人物によってＱ値が実際に送信されたことを知る。
【００８７】
本発明の好ましい実施態様では、どのサーバもパスワード検証子をクラックすることができないように、パスワード検証子の脆弱性はサーバ間に分配される。最高Ｎ−１個のサーバまでの任意の数のサーバに対する攻撃がユーザのパスワードまたは任意のパスワードによって保護されたデータを露出しない場合に、Ｎ個のサーバまで拡大縮小するシステムが提供される。これは、認証サーバのうちの１つ以外すべてのサーバまでの完全に動的なリークに直面してさえ、また、以前の安全でない通信チャネルに直面しても強力な保証を提供する。パスワードはこのシステムを実施する際の唯一の要因であることを理解されたい。
【００８８】
パスワードは、本発明を実施する際に要求される唯一の認証要因であることを理解されたい。パスワードのみによる認証は現在使用されている主流の方法である。本発明では、パスワード要因は可能な限り強力に作成されており、他の要因には依存しない。
【００８９】
他の追加的な鍵または信用証明書を使用することができることも理解されたい。本発明は、複数要因システムで使用することができることが想定される。明らかに、ローカル鍵を記憶することができる非ローミングの用途では、強度の付加的な層を提供するためにこれを実行することができる。例えばセキュア・ソケット層（ＳＳＬ）チャネルを使用することは本発明のシステムのパスワードの安全性に対しては必要ないが、ＳＳＬの付加的な使用は、これらのトランザクションを実行する際にユーザ名に対するプライバシー・レベルを増すなどの他の利点を提供する。パスワードの安全性に関するそのような他の要因に対する依存性を除去することによって、システム全体の強度は大幅に増大する。具体的には、本発明は、現在では広範に使用されているウェブ・ブラウザ認証の過度に単純化したパスワードによるＳＳＬシステムに対して可能なウェブサーバのスプーフィング攻撃のクラス全体を停止する。
【００９０】
本発明の様々な特徴および利点は、類似の参照番号が類似の構造上の要素を示す添付の図面と共に以下の詳細な説明を参照することによってより容易に理解することができる。
【００９１】
（詳細な説明）
図面を参照すると、図１は、本発明の原理による複数サーバ・システム１００の一例を示すブロック図である。この例示のシステム１００は、１つのクライアント１０１またはクライアント・コンピュータ１０１（Ａｌｉｃｅ）と、この例ではネットワーク１０２によって相互に結合されている２つのサーバＢ１  １０３とＢ２  １０４である複数の認証サーバ１０３、１０４とを含んでいるように示されている。
【００９２】
本発明のシステム１００および方法は、クライアント１０１が複数のサーバ１０３、１０４からマスター鍵のシェアを取り出すために変形ＳＰＥＫＥ方法を使用する。（数字ｎは、特定の実施態様で使用されるサーバ１０３、１０４の数を示すために使用される。）本発明を実施するために使用されるモデルは、保護されていないチャネルまたはネットワーク１０２を介して認証メッセージが送信されることを可能にし、安全なチャネル（例えばＳＳＬ）は一切必要としない。チャネルを制御する敵がＡｌｉｃｅを騙して不適切なマスター鍵を使用させる危険性を防止するために、Ａｌｉｃｅは敵に露出する可能性があるいかなるデータを作成するためにマスター鍵を使用する前にでもそのマスター鍵が正確であることを確認する。さらに認証ステップは、許容プロトコルに適応する目的で有効なログイン並びに以前の合法だが誤ったログインを認証するために署名済みメッセージを使用する。指数交換に対するパスワード導出ベースの要素を作成するために独特の関数が提供され、クライアント１０１とサーバ１０３、１０４のより柔軟な構成を可能にする態様を本発明者らは記載する。特別な状況には貴重な場合のある安全性の弱いモデルで代替方法が提供される。
【００９３】
好ましい実施態様では、Ａｌｉｃｅの潜在的に小さなパスワードとＡｌｉｃｅのすべてのパスワード保護データは、最大ｎ−１個までのサーバ１０３、１０４の完全に動的なリークがあった場合でさえ安全なままである。Ｋｍから導出された鍵によるＡｌｉｃｅの機密データの暗号化は、この認証プロセスで正確なパスワードを使用する関係者にのみＡｌｉｃｅのデータが入手可能になるよう保証する。
【００９４】
登録の時点で、Ａｌｉｃｅはパスワードと、マスター鍵Ｋｍを作成するために使用される一連のシェア｛ｙ１、ｙ２、…ｙｎ｝とを選択する。この実施例では、マスター鍵導出関数はＫｍ＝ハッシュ（Ｋ１‖Ｋ２‖．．．Ｋｎ）だが、ここで各シェアはＫｉ＝Ｐｙｉとして計算される。但し、他の代替鍵導出関数については後述する。ＡｌｉｃｅはＫｍを事前計算し、各Ｂｉと共に対応する鍵のシェアｙｉとＫｍに対する検証データを記憶する。検証データは、一般に公開鍵デジタル署名またはその代わりに対称鍵ＭＡＣ関数のどちらかを使用してデジタルに署名されたメッセージである。
【００９５】
各サーバＢｉは、ｙｉに関するサーバの知識に基づいて変形ＳＰＥＫＥプロトコルを使用してシェアＫｉをＡｌｉｃｅに提供する。プロトコルの各実行によって、Ａｌｉｃｅのブラインドされた鍵シェアのうちの１つ、この実施例では値ｍｉ＝Ｐｘｙｉが取り出される。Ａｌｉｃｅはこれらのシェアを結合しハッシュしてマスター鍵を導出する。この実施例では以下を使用する。
Ｋｍ＝ハッシュ（ｍ１１／ｘ‖ｍ２１／ｘ‖．．．ｍｎ１／ｘ）
ランダムなｙｉ値のため、これらの鍵のシェアは独立している。
【００９６】
図２を参照すると、Ａｌｉｃｅは後でサーバ１０３、１０４からマスター鍵を取り出す。クライアント１０１は、変形ＳＰＥＫＥ方法に従ってユーザにパスワード２０１を入力するよう促し、パスワード２０２から群要素を導出する。（（ｐ−１）／２素数と共にＺｐ＊の大きなプライム・オーダー部分集合を使用する場合に、そのような関数の一例はＰ＝ハッシュ（パスワード）２ｍｏｄ  ｐである。）変形ＳＰＥＫＥ方法を使用することによって、Ａｌｉｃｅは各サーバＢｉ２０３にブラインドされたパスワード値Ｐｘを送信する。各サーバＢｉはブラインドされたパスワード値をｍｉ＝（Ｐｘ）ｙｉのよう適切なベキ乗し、その結果をＡｌｉｃｅに戻す。Ａｌｉｃｅは、各鍵のシェアｍｉ２０４の対応するブラインドされた値を取り出し、各結果をアンブラインドし、それらを結合してＡｌｉｃｅのマスター鍵２０５、この実施例では関数Ｋｍ＝ハッシュ（ｍ１ｙｉ‖ｍ２ｙ２‖．．．ｍｎｙｎ）によって作成する。
【００９７】
Ａｌｉｃｅが任意のサーバから鍵のシェアＫｉを取り出すための一般的な方法、一般的にＢｉとラベリングされている方法は以下の通りである。
Ａ→Ｂｉ：      ｍ０＝Ｐｘ
Ｂｉ→Ａ：      ｍｉ＝ｍｏｙｉ
Ａ：           Ｋｉ＝ｍｉ１／ｘ＝Ｐｙｉ
【００９８】
Ｂｉが知っている秘密値ｙ１は、Ｂ２が知っている値ｙ２とは完全に独立しており、以下も同様である。したがって、サーバのどれ１つをとっても、ＫｍまたはＰのどちらかに対してディクショナリ攻撃を仕掛けるために十分な情報は有しない。このプロトコルを使用すると、各Ｂｉはｙｉを事前に記憶しており、またマスター鍵Ｋｍの単方向関数である検証データＶも記憶する。
【００９９】
ＡｌｉｃｅはＫｍを使用して、Ｋｍから導出された鍵を使用して暗号化されたコンテナに記憶されている個人の秘密データ２０８を解読することができる。このコンテナは、サーバ１０３、１０４のどれかに記憶されているか、または便利な他の場所に記憶されている場合があり、安全でないチャネルを介して取り出すことができる。しかし、ＡｌｉｃｅがＫｍに関するＡｌｉｃｅ自身の知識から導出した任意のデータを任意の他の関係者に露出する前に、ＡｌｉｃｅはまずＫｍが有効であるかどうかを判定する必要がある２０８。具体的な検証技術は後述する。
【０１００】
Ｋｍが有効でない場合、ローカル・パスワード再試行ポリシーに基づいて、ユーザにはパスワードの再入力を再度試行することが要求される場合がある２０１。再試行が実行されると、クライアント１０１は安全な短期メモリでの失敗した交換で使用されるＰｘ値を保存する。
【０１０１】
Ｋｍが有効である場合、ＡｌｉｃｅはＫｍの知識と、Ｐｘの知識と、短期メモリに記憶された同じユーザによって生成された任意の最近の以前のＰｘのリストとのプルーフを構築し、このプルーフをサーバ１０３、１０４のそれぞれに送信する２０７。この場合、Ａｌｉｃｅは、暗号化されたコンテナに記憶された秘密鍵によって公開文書に署名するように、Ｋｍから導出されたデータを自由に使用することができる２０９。
【０１０２】
Ａｌｉｃｅは、任意の適切なゼロ知識プロトコルを使用して任意のＢｉに対してＫｍに関する知識を証明することができるが、Ｋｍが大きなエントロピーを有しているのでこのゼロ知識・プロトコルはゼロ知識パスワード・プロトコルである必要はない。各サーバＢｉは、Ｋｍに対応し、サーバ自体にＡｌｉｃｅのＫｍのゼロ知識・プルーフを検証することを可能にする検証データ情報Ｖを有する。
【０１０３】
例えば一実施態様では、Ｋｍは公開鍵デジタル署名方式に対してユーザの秘密鍵Ｕを取り出すためにＡｌｉｃｅによって使用されるが、ここでＶはＵに対応するユーザの公開署名鍵である。Ａｌｉｃｅは、Ｂｉが署名を検証し、これがＡｌｉｃｅのＫｍに関する知識を証明する秘密鍵を使用してメッセージに署名するなどの多くの方法でＫｍに関する知識をＢｉに対して証明することができる。
【０１０４】
ＫｍからのＵの導出も多くの方法で実行することができる。一実施態様では、ＵおよびＶの値は他のデータを使用せずＫｍから直接的に導出することができる。
【０１０５】
本発明の好ましい一実施態様では、Ｕの値はＫｍから導出された対称鍵によって暗号化されたコンテナの中に封印して保存される。この実施例の場合、ＡｌｉｃｅはＫｍを使用して対称暗号鍵を導出し、次いでＡｌｉｃｅ自身の秘密鍵Ｕを開封する。
【０１０６】
Ａｌｉｃｅは次いでＢｉに知られているメッセージに署名するが、これはＫｍに関するＡｌｉｃｅ自身の知識を証明するものである。次いでＡｌｉｃｅは署名されたメッセージをＢｉに送信する。本発明の一実施態様では、メッセージはＢｏｂからＡｌｉｃｅに送信された値ＲＢｉである。
Ｂｉ→Ａ：      ＲＢｉ、ランダムな一時的な数
Ａ→Ｂｉ：      Ｕ（ＲＢｉ）、ＲＢｉの彼女の署名
【０１０７】
別法として、本発明の好ましい実施態様で、ＡｌｉｃｅはＵ（ＱＡ）を送信するが、これはＡｌｉｃｅがＱＡを使用して認証した一員であったことをさらに証明する。ＡｌｉｃｅがＱＡを認証すべき理由と、良いアクセス試行と悪いアクセス試行とを区別するためにそれを各サーバのニーズにどのように関係付けるかを後述する。
【０１０８】
第３の手法は、Ｖ＝ｇＫｍの場合、基本的にはＫｍに対するＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ公開鍵である。この場合、Ａｌｉｃｅは以下のように認証することができる。
Ｂｉ→Ａ：  ｇｘ
Ａ→Ｂｉ：  ｍ：＝ハッシュ（（ｇｘ）Ｋｍ）
Ｂｉ：    （ｍ＝Ｖｘ）の場合、ＡｌｉｃｅはＫｍを知らなければならない。
【０１０９】
Ａｌｉｃｅは次いで自分自身を証明するためにＥＫｍ（ＱＡ）を送信する。
【０１１０】
いかなる場合でも、ＡｌｉｃｅはＫｍに対する知識を証明する場合にパスワードＰに関する知識も証明する。
【０１１１】
Ｋｉとｙｉに関する結合された知識によってサーバはＰをクラックする能力を得るので、サーバＢｉに単一シェアＫｉを知ることを希望することは適切な判断である。単一サーバの場合、パスワードをクラックするために使用することができるある種のデータをそのサーバが記憶する必要があることは避けられないことであると考えられる。しかし理想的な複数サーバの場合、サーバがＰ、Ｋｍ、またはＫｉのどれか、またはＰをクラックすることに繋がる可能性のある他の何かをサーバが知ることは望ましくない。
【０１１２】
すなわち各ＢｉはＰまたはＫｉを知らない。Ｂｉはｙｉを使用して変形ＳＰＥＫＥを実行し、Ｋｍに関するＡｌｉｃｅの知識を認証する。各ＢｉはｙｉおよびＶ、すなわちＫｉに対する検証データとしても働くＫｍに対する検証データ、またはより広範にＰに関するＡｌｉｃｅの知識に対する検証データとして働くＫｍに対する検証データだけを知っている。
【０１１３】
登録
登録の時点で、Ａｌｉｃｅは自身のパスワード、および公開鍵デジタル署名を実行するために適した公開／秘密鍵対（Ｖ、Ｕ）を選択する。
【０１１４】
0004833489.tif 000003
【０１１５】
0004833489.tif 000004
【０１１６】
各サーバＢｉはＫｉを知らず、パスワードＰを知らずにこれを計算することはできないことを留意されたい。さらに良いことには、各ＢｉはＫｍまたはＰを知らず、他のシェアの知識なくしてＶからそれを計算することはできない。Ｂｉは、すべてのシェアｙｉを入手しない限り暴力によってさえｙｉからそれを計算することはできない。したがって、すべてのｎ個のサーバ１０３、１０４が損傷されない限り悪意のあるサーバはＰを計算することはできないという目的は達成された。ｙｉ値の１つにさえアクセスすることが不可能であるということによって、暴力は実行不可能になる。
【０１１７】
オンライン暴力的攻撃の防止
オンライン予測攻撃を防止するために、サーバ１０３、１０４は、ユーザ１人あたりベースのプロトコルの実行の回数および／または頻度を制限することを希望する。このような技術は周知である。しかし、このようなシステムを最適化するには、サーバ１０３、１０４がプロトコルの有効な実行と無効な実行との間を区別することが必要となる。さらにプロトコルの無効な実行の場合は、合法的なユーザの誤りと疑わしい攻撃との間を区別することも有用である。
【０１１８】
具体的には、誤って間違ったパスワードをタイプしたユーザと、本当に無許可の認証の試行との間を区別することが望ましい。マシン対マシン認証とは異なり、ユーザ認証での誤りは一般的である。具体的にはパスワード認証では、いくつかの一般的なタイプの誤りがある。おそらくＡｌｉｃｅは一時的に自分のパスワードを忘れて類似だが誤ったパスワードをタイプする場合がある。または、Ａｌｉｃｅはパスワードを知ってはいるがタイプする際に誤る場合もある。別の一般的な誤りは、Ａｌｉｃｅが曖昧に記憶している複数のパスワードから誤った選択肢をタイプするというものである。ユーザが、最後の試行が最終的に有効となった一連のログイン試行中にこのような誤りをなすことは非常に一般的である。仮にサーバがすべてのこのようなケースを疑わしいハッカーの攻撃とみなし、またユーザをロックアウトする前の試行回数に関して厳重な制限を有している場合、ユーザは一般的に自分のシステムから誤ってロックアウトされる場合がある。
【０１１９】
前述のシステム１００で、Ａｌｉｃｅは、すべての認証サーバ１０３、１０４がＡｌｉｃｅの合法ではあるがエラーのあるアクセス試行を攻撃者による予測試行と区別することができるようにすべての認証サーバ１０３、１０４に対してＡｌｉｃｅの｛Ｋｍ‖Ｐｘ｝に関する結合された知識を証明することができる。サーバが、おそらくは一定の時間間隔内で、そのようなプルーフを受信しない場合、サーバは、Ｐｘによってなされた予測は無効であり攻撃者による無許可のアクセスであると従来通りに推測し、許可された悪い予測の制限に対してそれを不利とみなす。
【０１２０】
無効アクセス回数にタイプミスが占める割合を最低限に抑えるための１つの手法は、クライアント１０１での二重の悪い入力を検出し、サーバ１０３、１０４に対して反復された二重の悪いパスワードを送信することを防止することである。クライアントのソフトウェアは、特定の入力がサーバによって拒絶されたことを検出すると、ユーザに対して拒絶メッセージを表示する。ユーザが同じ無効入力を反復する場合、クライアントのソフトウェアはそれを認識することができ、そのサーバに再度接触することを防止することができる。最適化は、クライアント１０１に記憶されているパスワードの露出を最小限に抑えるために短期間だけしか行うことはできない。
許容プロトコル
【０１２１】
この問題に対するもう１つの新しい手法は、「許容」プロトコルと称することを次に説明する。このシステム１００では、誤ったパスワードの多くの事故的な入力が発生すると即座に正確なパスワードの入力が続くことが前提となる。これが発生すると、サーバ１０３、１０４は誤った入力を許すことが望ましい。これは、これらの誤りが合法的なユーザによってなされたことが証明された場合に、記録されている無効アクセス試行回数からこの事象を事実上除去することによって行うことができる。許されることにより、自分のパスワードを頻繁にミスタイプするユーザは無許可アクセス試行に関する小さい長期制限を維持するシステム１００によって不要に罰則を受けることはない。
【０１２２】
稚拙な手法は、各成功裡の試行後にそれ以前のすべての無効な試行の記録を単純に消去することである。しかしこれは、パスワードに対する最適な予測回数を行うためにシステムの閾値を知っている攻撃者が実際のユーザによるプロトコルの有効な実行の間にインターリーブすることを可能にする。
【０１２３】
この問題に対する解決法は、エラーのあるどのアクセス試行が有効なユーザの単なる事故的な誤りであるかを（できるだけ多く）識別し、この情報をサーバに提供することである。これは、プロトコルの各成功裡の実行中にそのユーザによってなされた既知の以前の誤りの証拠をクライアントに送信させることによって行われる。基本的に、クライアントはそれぞれのそのような誤りに対して許しを求める。サーバは、有効なユーザが誤りをなしたことを検証すると、その記録から誤りをディスカウント（除去）する。
【０１２４】
利点は、無効アクセス回数に対するより厳しい制約は、反復された少数のタイプミスに関してユーザを罰せずにより厳しくすることができる。
【０１２５】
図３を参照すると、変形ＳＰＥＫＥ複数サーバ・システム１００の好ましい実施態様で使用されるような、許容プロトコル３００（ソフトウェア３００として実施される）の一例が示されている。
【０１２６】
サーバ１０３は、ユーザごとに以下のデータ変数を維持する。
Ｚ            悪い試行数
Ｎ            最近の増幅要求数
Ｒ［１．．Ｎ］  最近のＰｘパスワード増幅要求値リスト
Ｔ［１．．Ｎ］  Ｒ［１．．Ｎ］に関連付けられたタイムスタンプのリスト
【０１２７】
サーバ１０３はブラインドされたパスワード（ＰＸ）要求を受信する３０１。ローカル・ポリシーに従って、ユーザ・アカウントがロックされているかどうかを知るためにユーザ・アカウントがチェックされる３０２。ロックされている場合は、応答は送信されてはいけない３０３。アンロックされている場合、ブラインドされたパスワードは短期嫌疑リストに記録され３０４、ブラインドされた鍵のシェア（Ｐｘｙｉ）が作成され３０５、ブラインドされた鍵のシェア（Ｐｘｙｉ）がクライアント１０１に送信される３０６。
【０１２８】
ブラインドされたパスワード要求を記録することは、そのアカウントがロックされておらず、ブラインドされたシェアがクライアントに送信されるべき場合にのみ行われるべきである。しかし安全を期して、記録はブラインドされたシェアが送信される前に行われるべきである。
【０１２９】
したがって、パスワード増幅プロセス３０５が発生するログイン試行のたびにＮの値は増分され、サーバ１０３は、その実行で使用されたＱＡの値を短期メモリ３１５のリスト値Ｒ［Ｎ］に記録する。サーバ１０３はさらに、要求が受信された時刻を示す関連するタイムスタンプ値をＴ［Ｎ］に記録する。
【０１３０】
サーバ１０３は、陳腐な要求を発見３１３またはチェックする３１３ためのプロセスを定期的に実行する。Ｔ内の任意のタイムスタンプ値と現在時刻との間の差異が特定の時間間隔以上に大きくなる場合、サーバ１０３はいかなる対応するＲ値をも削除する３１４。この期間の長さは、誤りをなした有効なユーザが正確なパスワードでログインを試行し続けることが予想される典型的な最大時間である場合がある。各Ｒ値がリストから除去されると、対応するＴ値および最近の増幅数Ｎも同様に除去される。このような事象が発生するたびに、未検証のユーザに対してもう１回パスワード増幅が発生したことを示すために、長期メモリ３１６にある悪い試行回数Ｚが増分される。
【０１３１】
成功裡のログインが行われた場合、クライアント１０１は、ランダム乗したパスワードと等しいＱＡの値を、同じログイン・セッションの以前の実行のＱＡに対する任意の以前の値と共にデジタルに署名したメッセージ３０８形式で各サーバ１０３に送信する。このメッセージはマスター鍵Ｋｍに関するユーザの知識から導出された鍵を使用して署名される。この署名は、ユーザの公開鍵Ｖを有する任意のサーバ１０３によって検証可能なユーザの秘密鍵Ｕを使用して、メッセージ上の公開鍵デジタル署名を使用して実行されることが好ましい。
【０１３２】
別法として、署名は、ユーザとサーバによって共用される鍵による鍵の掛かった鍵を掛けられたＭＡＣを計算することによって実行することができる。この場合、鍵はＫｍから直接的に導出することも、Ｋｍによって対称的に暗号化された暗号化済みコンテナから得ることもできるが、一般的に共用鍵はそれぞれのユーザ／サーバ関係に対して一意である必要がある。
【０１３３】
この署名されたメッセージは、サーバによって受信され３０８、検証される３０９。検証ステップは、ユーザの公開署名鍵を使用した公開鍵デジタル署名検証であっても、あるいはサーバに既知のユーザ特有鍵を使用した鍵の掛かったＭＡＣの確認であってもよい。サーバ１０３は、すべての最近のＱＡ値のユーザのリストの署名を検証し、それらをリストＲの以前の最近の実行で発見された値のリストと比較する３０９。一致がない場合、リストＲは変更されない３１０。システムは、成功裡のログイン事象としてもまたは不成功のログイン事象としても無効プルーフの受信は一般に取り扱うべきでない。一致がある場合、対応するアクセス試行は短期メモリ３１５内のリストＲから除去され３１１、対応するタイムスタンプも除去され、Ｎの値が減分される。
【０１３４】
サーバ１０３は、悪い試行数Ｚまたはおそらくは悪い試行数と最近の未確認増幅（Ｚ＋Ｎ）の総数を制限することを選択することができる。この制限はユーザ、ユーザの集合、またはシステム規模の制限に対して特有であることができる。同様に、制限が超過された場合に取られるべき動作は、アカウントを永続的にロックアウトすること、一時的にロックアウトすること、かつ／またはシステム管理者に対して警報状態を提示することなど変動する場合がある。技術におけるこのような変動はパスワードベースのシステムでは一般的なことである。
【０１３５】
サーバ１０３は、アクセス・イベントを発生させたクライアント１０１またはネットワーク１０２に関連付けられた情報を記録することを希望することもできる。サーバ１０３は、そのようなイベントのアカウントをクライアント１人あたりベースで維持することさえできる。
【０１３６】
変形ＳＰＥＫＥシステム１００では、このようなデータは既に公開されているので、ＱＡ値の露出した記録であってもクライアント１０１またはサーバに対して安全性の脅威を提示しない。
【０１３７】
許容プロトコルを使用する際の１つの懸念は、共用ワークステーション設定にある。常に長期間にわたって実行されている永続的ログイン・プログラムがある場合、攻撃者は、標的となったユーザの予想到着時刻直前にワークステーションに到着することができ、またその攻撃者は間もなく許されるであろう数点の予測を挿入することができる場合がある。したがって、システム設計者はそのようなイベントの発生する可能性を考慮し、かつおそらくは許容時間ウィンドウを適切に調整する必要がある。この脅威を低減するもう１つの方法は、ログインに対してセッションベースの手法を提示するシステムを使用することである。クライアント１０１は、数回のアクセス試行に対して活動状態のままであり、次いで非活動状態の期間後に消失するログイン・ウィンドウを開始するために保護注意鍵を使用することができる。このシステムは、それ以前のセッションでなされた無効ログイン試行に対する許しを求めることは一切ないが、単一セッション中の悪い試行以外はすべて許容されることが可能である。ユーザは同様に、共用ワークステーションを使用している場合には常に新しいログイン・セッションを確実に使用するように訓練されるべきである。
【０１３８】
Ｕ（ＱＡ）メッセージを分配する明白なプロセスは、Ａｌｉｃｅに自身ですべてのＮ個のサーバ１０３、１０４に接触させることである。しかし、これらの活発なマシンに対する割込みを最小限に抑えるために、本発明者らはＡｌｉｃｅにサーバ１０３、１０４の１つだけに接触させることしかできない。次いでこのサーバ１０３、１０４は、証拠を他のすべてのサーバ１０３、１０４に伝播させ、また集められた一連の一括された要求でも同様に行うことができる。例えば、現在の間隔で、システムのすべてのユーザに対して「許容を求める」要求を分配するために数分ごとに更新を行うことができる。この技術は割込み数および各サーバに対する通信オーバーヘッド量を低減させることができる。
【０１３９】
許容プロトコルの概要
このシステム１００は、ユーザのアカウントの悪いアクセス試行の持分に対して有効なユーザによる誤りをカウントしないので、「寛大」である。これは、有効な遷移誤りはシステム１００に対する脅威としてではなくディスカウントするが、未知のユーザによる無効アクセス試行をカウントおよび制限する能力は依然として保持している。
【０１４０】
各成功裡の認証後の最近の以前の無効アクセス試行の証拠を送信することによってこれは達成される。この証拠を受信して検証する際、各サーバは記録からその誤りを消去するか、またはそのイベントを訂正された許容可能な誤りとして記録する。この方法でサーバのイベント・ログを微調整することによって、システム管理者は、有効なユーザが単に失敗している時点ではなくシステム１００が本当に危険な時点に関するより詳細な見解を得る。
【０１４１】
許容システム１００は、クライアント１０１での少なくとも１つの署名生成ステップと、サーバ１０３、１０４のそれぞれに対する少なくとも１つの署名検証ステップとを要求する。計算を最小限に抑えるために、署名ステップを、ユーザを認証する署名ステップと結合することができる。ユーザに対する有効認証メッセージを構築する際、クライアント１０１はそのユーザによって発行されたすべての最近のチャレンジ・メッセージの集合を含め、その結果をユーザの秘密鍵でデジタルに署名し、それをすべてのサーバ１０３、１０４に送信する。各サーバ１０３、１０４はユーザを認証するために署名を検証し、同時にユーザの最近の許容可能な誤りの証拠を検証する。許容システム１００のこの実施態様は、いかなる関係者に対しても著しい付加的な計算は一切要求しない。
【０１４２】
サービスの拒絶
アカウントのロックアウトに対する無効な試行に対して小さい制限を設定すると、サービス攻撃の拒絶の脅威も増加する。攻撃者は、反復した故意の無効アクセス試行を行うことによってシステム１００への特定ユーザによるアクセスを単純に拒絶することができる。
【０１４３】
この問題を緩和する１つの手法は、無効アクセス試行のソースに関する情報をサーバの記録に記録し、またサーバに、より具体的にはソース１つあたりベースでロックアウト・オペレーションを実行させることである。ソース情報は、そのような情報が入手可能な場合に発信側のクライアント・コンピュータ１０１の名前またはネットワーク・アドレスを含めることができる。
【０１４４】
拡張子
ユーザが自分のマスター鍵Ｋｍを得ると、上述の基本システム１００は多くの方法で拡張することができる。各認証サーバ、およびより一般的には任意の他のサーバは、ユーザのマスター鍵Ｋｍで対称的に暗号化されたクライアント１０１に対する秘密ファイルを記憶することができる。このファイルは、強力に暗号化されているので、認証なしにユーザに自由に送信することさえできる。このファイルはユーザの秘密鍵とユーザに関する任意の他の機密データを含めることができる。
【０１４５】
上述の基本的な複数サーバのプロトコルは、サーバ１０３、１０４のある種の部分集合が一時的に使用不可能になるケースを見込んで拡張することができる。
【０１４６】
シェアＫｉは多くの様々な方法で結合することができることに留意されたい。一例は、Ｋを構成するために十分なシェアを得るためには、ｎ個のサーバ１０３、１０４のうちのいくつかの部分集合ｍに対するアクセスで十分である場合にＮ個中Ｍ個の認証を可能にするためにこのシステム１００を拡張することである。この一例は以下の通りである。
【０１４７】
各ＣｉがＫｉシェアのすべての予想される有効な組み合わせの１つである｛Ｃ１、Ｃ２、．．．Ｃｘ｝の組み合わせのリストを計算する。例えば、ｍ＝ｎ−１の場合、ｎ−１のシェアのすべての有効な組み合わせは以下のように計算することができる。
0004833489.tif 000005
【０１４８】
次いでサーバは、Ｋ：Ｃ＝｛暗号（Ｃ１、Ｋ）、暗号（Ｃ２、Ｋ）、．．．暗号（Ｃｘ、Ｋ）｝のｘ個の異なる対称的な暗号を記憶する。
【０１４９】
認証の時点で、クライアント１０１はリストＣを取り出し、Ｋを解読し、Ｋに関する知識をサーバ１０３、１０４に対して証明する。この手法は、ｍおよびｎの小さい値の場合に実用的である場合がある。
【０１５０】
短い指数の問題
概略的にｑのサイズである累乗に対する指数が上述の方法の優勢な損失なので、指数のサイズを低減することが望ましい。能率的なゼロ知識方法に短い指数を提供する１組の方法が、参照により本明細書に組み込んだ１９９８年８月２０日のＵ．Ｓ．ＰＴＯによって出願された文書開示番号第４４３５１０号のＤ．Ｊａｂｌｏｎによる「Ｐａｓｓｗｏｒｄ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ  ｕｓｉｎｇ  ａ  Ｃｏｍｐｏｓｉｔｅ  Ｍｏｄｕｌｕｓ（複合モジュラスを使用したパスワード鍵交換）」に記載されている。
【０１５１】
もう１つの手法は、１９９６年５月のＥｕｒｏｃｒｙｐｔ  ９６，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇの議事録のＰ．Ｃ．ｖａｎ  ＯｏｒｓｃｈｏｔおよびＭ．Ｊ．Ｗｉｅｎｅｒによって「Ｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  Ｋｅｙ  Ａｇｒｅｅｍｅｎｔ  ｗｉｔｈ  Ｓｈｏｒｔ  Ｅｘｐｏｎｅｎｔｓ（短い指数によるＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵アグリーメント）」で議論されているような短い指数を使用するというものである。これらの著者は周知の計算の攻撃の相対的な損失を議論し、短い指数の適切なサイズを議論している。
【０１５２】
しかし、短いランダムな指数に異なるパスワード値をベキ乗した結果生じるドメインが高度に明確な場合、パスワード導出ベースに関する情報をリークするための技術が開発される場合のある可能性を残しているということが依然として懸念である場合がある。
【０１５３】
［１、ｏ（Ｇ）］で均一に分散された値の範囲から選択されたランダムな指数ｘを使用する際、ｘに関する知識なくしてＰｘだけに関する知識がＰに関する情報を一切露出しないことは明らかである。しかしｍ＜ｏ（Ｇ）として範囲［１、ｍ］で短い指数ｘを使用する際、セキュリティは、計算上の取り扱いにくさの何らかの付加的な仮定に依存している。この場合に対する特別な攻撃を誰かが発見したらどうすればよいのだろうか。
【０１５４】
Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎでの短い指数の使用はｖａｎ  ＯｏｒｓｃｈｏｔおよびＷｉｅｎｅｒによって議論されているが、ここで著者らは、いくつかの既知の固定した基数ｇに対してｇｘのランダムな指数ｘを計算する最も効率的な周知の方法としてＰｏｌｌａｒｄラムダ方法を特定している。ラムダ離散ログ計算は約ｘ１／２のオペレーションを必要とする。パスワード生成Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ交換を解読する単純化した手法は、Ｐ’を各候補パスワードに対して構築されたものとした場合に各潜在的な基数Ｐ’に対する指数を計算するというものである。しかし、より簡単な解決法があるかも知れないと考える人物もいる可能性がある。
【０１５５】
問題（１）が暴力的なラムダ攻撃よりも非常に簡単である場合があるという（おそらくは警告されていない）考慮により、本発明者らはモジュラスよりも非常に小さいプライム・オーダーの部分集合を使用することによってＡｌｉｃｅとＢｏｂの計算を低減させる手法を提案する。少なくとも敵がクライアントのＰｘ値だけから情報を決定する場合には計算上の取り扱いにくさのいかなる仮定をも除去することが望ましい。
【０１５６】
パスワード導出ジェネレータ用のＰ＝ｆ（ｇ・ｈ）方法
問題に対処する一方法は、モジュラスよりも非常に小さいオーダーで大きなプライム・オーダー部分集合を使用する。パスワードをこの部分集合のジェネレータに（比較的効率的に）変換する関数が使用され、計算上の取り扱いにくさの潜在的により少数の仮定をもってサーバの秘密指数に関する情報のリークを低減させることによってセキュリティを効率的に維持する手段が使用される。この実施態様では、値Ｐは２つ独立したランダムな群要素（ｇ、ｈ）から導出されるが、これら要素のうちの１つｈはパスワードの関数に基づいて累乗される。
固定したシステム・パラメータは以下の通りである。
２１０２３＜ｐ＜２１０２４であり、２１５９＜ｑ＜２１６０、ｐおよびｑが素数の場合にｐ＝ｋ・ｑ＋１とする
ｇ＝ハッシュ（“ｇ”）ｋｍｏｄ  ｐとする
ｈ＝ハッシュ（“ｈ”）ｋｍｏｄ  ｐ、オーダーｑの２つの関係しない要素とする
【０１５７】
ハッシュ関数はＳＨＡ１のような標準的な暗号ハッシュ関数である。この実施例の関数に対する入力ストリングは任意の定数であり、この実施例では単一のＡＳＣＩＩ文字ストリング「ｇ」と「ｈ」である。ｇとｈは任意の独立した数字であり、したがってｇはいかなる既知の指数累乗によってもｈに関係していることが知られないことが重要である。
【０１５８】
登録
Ａｌｉｃｅは登録時に以下のステップを実行する。
１からｑまでの範囲の乱数、ｙ∈Ｒ［１、ｑ］を選択する
ｔ＝ハッシュ（パスワード）ｍｏｄ  ｑを計算する
Ｐ＝ｇ・ｈｔｍｏｄ  ｐを計算する
Ｋ＝Ｐｙｍｏｄ  ｐを計算する
サーバＢでｙを記憶する
【０１５９】
指数のパスワード導出ｔは１９９７年６月のＪａｂｌｏｎの論文で示された「指数内パスワード」問題に関する懸念を増大させる。攻撃者は、ｇｅｉ＝Ｐｉのように、固定した基数ｇとＰに対する候補値のディクショナリ｛Ｐ１、Ｐ２、．．．｝との対応関係を確立するために「指数のディクショナリ」｛ｅ１、ｅ２、．．．｝を作成することが可能であってはならない。
【０１６０】
ｇとｈがいかなる既知の指数によっても関係付けられないように別個に選択された場合、この問題は回避される。上述のような固定したシステム・パラメータの構築がこれを保証する。
【０１６１】
何らかの理由で変数パラメータが望まれる場合、クライアント１０１は、ｇおよびｈの有効性を証明する公開された信用証明書を検証することによってｇおよびｈが適切であることを検証することができることに留意されたい。信用証明書は、この実施例ではストリング「ｇ」および「ｈ」であるハッシュ関数への単なる入力であってよい。ハッシュ関数が正常でなければならず、かつハッシュ空間が衝突を防止するために十分に大きくなければならない場合、結果として生じる値は基本的に乱数と区別不可能であるべきである。離散ログ問題は、２つのそのようなランダム要素間の指数の相関関係を決定することができないよう保証する。１つのそのような適切なハッシュ関数は、「Ｓｅｃｕｒｅ  Ｈａｓｈ  Ｓｔａｎｄａｒｄ（安全なハッシュ標準）」、ＦＩＰＳ  １８０−１、Ｕ．Ｓ．Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙに記載のＳＨＡ１である。
【０１６２】
認証
ＡｌｉｃｅがＢｏｂと共に実行するパスワード増幅プロトコルでは、
Ａｌｉｃｅは以下のように続行する。
ｔ＝ハッシュ（パスワード）ｍｏｄ  ｑを計算する
Ｐ＝ｇ・ｈｔｍｏｄ  ｐを計算する
ｘ∈Ｒ［１、ｑ］、１からｑの範囲の乱数を選択する
ｒ＝Ｐｘを計算する
ｒをＢｏｂに送信する
次いでＢｏｂは以下を実行する。
（ｒｑｍｏｄ  ｐ）≠１またはｒ＝１の場合にプロセスをアボートする。
ｓ＝ｒＶを計算する
ｓをＡｌｉｃｅに送信する
次いでＡｌｉｃｅは以下のステップを実行する。
（ｓｑｍｏｄ  ｐ）≠１またはｓ＝１の場合にアボートする。
Ｋｍ＝ｓ１／ｘｍｏｄ  ｐを計算する。
【０１６３】
この方法では、ＢｏｂとＡｌｉｃｅはそれぞれに１６０ビットの指数によって２つの累乗法を実行する。この方法は、類似のＦｏｒｄおよびＫａｌｉｓｋｉ方法と比較した場合、短い指数問題が解決可能であるという仮定の下で、非常に少ない計算によって略同等レベルのセキュリティを提供する。
【０１６４】
指数の最低サイズと対称鍵との間で任意の正確な等価の相関関係を決定することは困難なので、これは「略」同等とされる。上記の実施例ではランダム指数と部分群のサイズは１６０ビットであり、対称鍵は８０ビットの強度を有し、モジュラスのサイズは１０２４ビットと仮定する。このような相関関係は厳密に明確に定義付けるのは困難である。１つの参照点として、ＤＳＳ署名規格は５１２ビットのモジュラスの１６０ビットの部分群を使用したことに留意されたい。他の勧告は、通常、１６０ビットの部分群に対してより大きなモジュラスのサイズを仮定する。いかなる場合でも、全般的に増大する鍵のサイズに対して勧告が変化するにつれて、ここで説明する方法で使用する値のサイズを適切に調整することができる。
【０１６５】
Ｐ＝ｆ（ｇ・ｈ）によるモジュラスの構築
ｐ＝ｋｑ＋１でありオーダーｑの部分群が使用される上記の方法では、ｋの係数に関する懸念がある。小さい手段がある種の最低の安全なサイズよりも少ないｋのすべての小さな係数に関しては、敵はＴｙｍｏｄ  ｐを得るために特定の値Ｔでサーバをプローブすることができる。この結果によって敵はサーバの指数ｙに関する情報を学習することができる。Ｓをｋのすべての小さい係数の倍数として各小さい係数に関してそれを認める場合、対応する小さな部分群がある。Ｓ＝２となるようにｋを構築することによって、ｙの低いビットだけがリークされる最低レベルにまで攻撃を低減することができる。一実施態様では、ｋ＝Ｓ・ｒ、Ｓ＝２とし、ｒ、ｑおよびｐを素数とした場合にｐ＝ｋｑ＋１である。
【０１６６】
ｙの低いビットだけのリークは、指数ｙが本当にランダムである場合は重大な問題ではないはずである。その低いビットが別個にランダムであると仮定すると、最低の安全な指数サイズは補償するために１ビットだけ増やすことができる。この１ビットのリークは、ｙの低いビットをシステム１００全体を通して固定された定数とすることによって防止することができる。
【０１６７】
Ｐ＝ｆ（ｇ・ｈ）によるセキュリティと効率
プロービング攻撃から情報リークを低減する類似の手法は、ｙがＳの倍数になることを保証することである。ここでもまた、Ｓが１０ビットの数であるとｙはＳ＝２になるこの（上記の）場合よりも１０ビット大きくなるというように、ランダム性の損失を補償するためにｙのサイズが適切に増やされる必要がある。
【０１６８】
Ｐ＝ｆ（ｇ、ｈ）方法によって、本発明者らはクライアント１０１にほんの僅かな計算上の代償を追加する、より信頼性のある短い指数を使用することができる。この方法の性能は、同様に短い指数を使用するが、遥かに大きな群を生成する値Ｐを伴う方法と比較することができる。この方法は、サーバに対する重要な追加の計算は一切なく、クライアントの第１のメッセージのプローブ可能なセキュリティの保護を得る。クライアントの追加された損失は、ｔ乗されるｈの累乗法である。
【０１６９】
最後に、計算上の取り扱いにくさという仮定を除去することによってセキュリティを向上させる本発明で使用されている手法は、他日、不適切であると証明することができよう。短い指数を使用する計算上の安全性は、離散対数問題が扱いにくいという仮定などの、本発明者らが方法に対して全体として行った他の仮定と等価であることを証明することができる。
【０１７０】
代替鍵導出関数
鍵のシェア｛ｙ１、ｙ２、．．．ｙｎ｝からマスター鍵を導出するために代替鍵導出関数が可能である。ここでは３つのそのような関数を示すが、それらの関数の第１の関数は上記の実施例で使用される関数と同じである。
Ｋｍ＝ハッシュ（Ｐｙ１‖Ｐｙ２‖．．．Ｐｙ２）、連結を使用して
Ｋｍ＝ハッシュ（Ｐｙ１（○＋）Ｐｙ２（○＋）．．．Ｐｙｎ）、ＸＯＲ関数を使用して、
Ｋｍ＝ハッシュ（Ｐｙ１＊Ｐｙ２＊．．．Ｐｙ２）、群演算子を使用して、
特別な場合、ここで示し、かつさらに後述する結合された鍵導出関数によって群内で累乗法を使用する鍵のシェアを結合するのに有利な場合がある。
Ｋｍ＝ハッシュ（Ｐｙ１・ｙ２・．．．ｙｎ）、反復した群累乗法を使用して、
【０１７１】
次節では、これらの異なる代替関数が方法の異なる実施態様で有利であることを示す。
【０１７２】
代替フローおよび結合された鍵導出関数
複数のサーバ１０３、１０４を認証するための１つの簡単な手法は、クライアント１０１に以下のように複数のサーバのそれぞれと共に一連の連続したチャレンジ／応答プロトコルを実行させることである。
手法（１）
Ａ：      ｍ１＝Ｐｘ
Ａ→Ｂ１：  ｍ１
Ｂ１：      ｍ２＝ｍ１ｙ１
Ｂ１→Ａ：  ｍ２
Ａ→Ｂ２：  ｍ１
Ｂ２：      ｍ３＝ｍ１ｙ２
Ｂ２→Ａ：  ｍ３
Ａ：      Ｋｍ＝ハッシュ（ｍ２（１／ｘ）、ｍ３（１／ｘ））
【０１７３】
クライアント１０１に単一Ｐｘ値を複数のサーバ１０３、１０４に同時に送信させるもう１つの代替的な手法（２）は、クライアント１０１が非同期的に応答を収集することができる、サーバ１０３、１０４（Ｂ１およびＢ２）に同時に並行して応答を計算して送信する作業にあたらせる環境では有利である場合がある。
手法（２）
Ａ：      ｍ１＝Ｐｘ
Ａ→Ｂ１：  ｍ１
Ａ→Ｂ２：  ｍ１
Ｂ１：      ｍ２＝ｍ１ｙ１
Ｂ２：      ｍ３＝ｍ１ｙ２
Ｂ１→Ａ：  ｍ２
Ｂ２→Ａ：  ｍ３
Ａ：      Ｋｍ＝ハッシュ（ｍ２（１／ｘ）、ｍ３（１／ｘ））
【０１７４】
手法（２）は、手法（１）と比較して全体的な実行時間を低減することができる。
【０１７５】
手法（２）のさらなる最適化は、Ｋｍ＝ハッシュ（Ｋ１＊Ｋ２＊．．．Ｋｎ）のように、鍵のシェアのグループ積からマスター鍵を導出することである。この場合、Ａｌｉｃｅは、自分が実行しなければならない累乗法の量を低減させる計算Ｋｍ＝ハッシュ（（ｍ２＊ｍ３）（１／ｘ））を実行することができる。
【０１７６】
具体的には、図４は、最適化された計算によってグループ積鍵導出関数を使用して２つのサーバと共に１つのクライアントのオペレーションを示す本発明の原理による方法の一例４００を示す流れ図である。
【０１７７】
ステップ４０１では、登録時刻｛ユーザＩＤ、ｙｉ、Ｖ｝が各サーバ１０３、１０４に記憶され、Ｐ（Ｈｐ＝ハッシュ（Ｐ））のハッシュの暗号化されたコピーとユーザの秘密鍵Ｕはユーザの識別子｛ユーザＩＤ、暗号（Ｋｍ、｛Ｈｐ、Ｕ｝）｝に関連付けられるかまたは関係付けられたディレクトリに保存される。暗号化されたコンテナは、同様にＨｐを破損せずにＵを破損するようにコンテナが変更される危険性がないことを保証するためにメッセージ認証コードを含むことに留意されたい。
【０１７８】
ログインの時点で、ステップ４０２では、入力されたパスワード（上記のような）の適切な関数である群要素（Ｐ）が作成される。ステップ４０３では、ブラインドされた鍵のシェア（ｍ１＝Ｐｘ）が形成される。ステップ４０４では、ブラインドされた鍵のシェアは各サーバＢ１１０３およびＢ２１０４に送信される。
【０１７９】
ステップ４０５では、ブラインドされた鍵のシェア（ｍ２＝ｍ１ｙ１）は第１のサーバ（Ｂ１）１０３上で形成される。ステップ４０６では、サーバＢ１はブラインドされたパスワードを短期メモリに記録し、ステップ４０７ではブラインドされた鍵のシェア（ｍ２）をＡｌｉｃｅに送信する。ステップ４０８で、Ａｌｉｃｅは公開ディレクトリからＡｌｉｃｅの暗号化されたパスワード検証子Ｈｐと秘密鍵Ｕを獲得する。（ステップ４０８は任意の便宜的な時点で実行することができる。）ステップ４０９では、ブラインドされた鍵のシェア（ｍ３＝ｍ２ｙ２）は第２のサーバ（Ｂ２）１０４上で形成される。ステップ４１０では、第２のサーバ（Ｂ２）１０４はｍ１を短期メモリに記録し、ステップ４１１ではｍ３をＡｌｉｃｅに送信する。ステップ４１２では、Ａｌｉｃｅ１０１はそのシェアをアンブラインドし、Ａｌｉｃｅのマスター鍵Ｋｍ＝ハッシュ（（ｍ３＊ｍ３）（１／ｘ））を作成する。鍵導出用のシェアのグループ積を使用するＫｍ＝ハッシュ（Ｐｙ１＊Ｐｙ２）に留意されたい。
【０１８０】
ステップ４１３で、クライアント１０１はＨｐおよびＵを取り出すためにＫｍを使用してディレクトリ・データを解読する。ステップ４１４および４１５では、Ｈｐがハッシュ（Ｐ）に等しくない場合、クライアント１０１はアボートする。ステップ４１６では、クライアント１０１はクライアントの秘密鍵Ｕを使用してブラインドされたパスワードｍ１を含んでいる署名されたメッセージｍ４を作成し、それをクライアント１０１が合法的ユーザの代わりに動作していることのプルーフとしてＢ１およびＢ２に送信する。ステップ４１７で、各サーバ１０３、１０４はユーザの公開鍵Ｖを使用してメッセージｍ４のｍ１上の署名を検証する。ステップ４１８および４１９では、ｍ１上の署名が検証されてｍ１が疑わしいログイン要求の短期リスト内で発見される場合、ブラインドされた鍵のシェアｍ１はそのリストから消去される。
【０１８１】
しかし、サーバＢ１がクライアント１０１とサーバＢ２の間の媒介物として動作する連鎖的手法の一例のように、メッセージ・フローのシリアル化が必然である場合がある。この場合、本発明者らは、Ｋｍ＝ハッシュ（Ｐｙ１＊ｙ２＊．．．ｙｎ）でのようにブラインドされた鍵の連続的な累乗法を使用してマスター鍵を導出するために代替の結合された鍵導出関数を使用することができる。
手法（３）
Ａ：        ｍ１＝Ｐｘ
Ａ→Ｂ１：   ｍ１
Ｂ１：       ｍ２＝ｍ１ｙ１
Ｂ１→Ｂ２：  ｍ２
Ｂ２：       ｍ３＝ｍ２ｙ２
Ｂ２→Ｂ１：  ｍ３
Ｂ１→Ａ：   ｍ３
Ａ：        Ｋｍ＝ハッシュ（ｍ３（１／ｘ））
【０１８２】
Ｂ１とＢ２によって実行される計算の順番は交換可能であり、Ｂ２はｍ３を単純に直接的にＡに送信できることに留意されたい。この手法は以下で詳述し、図５に示す。代替的な等価のシーケンスは以下の通りである。
手法（４）
Ａ：        ｍ１＝Ｐｘ
Ａ→Ｂ１：   ｍ１
Ｂ１→Ｂ２：  ｍ１
Ｂ２：       ｍ２＝ｍ１ｙ２
Ｂ２→Ｂ１：  ｍ２
Ｂ１：       ｍ３＝ｍ２ｙ１
Ｂ１→Ａ：   ｍ３
Ａ：        Ｋｍ＝ハッシュ（ｍ３（１／ｘ））
【０１８３】
結合された鍵導出関数は、シリアル化された手法で媒介物としてのＡｌｉｃｅによっても使用することができる。
手法（５）
Ａ：       ｍ１＝Ｐｘ
Ａ→Ｂ１：  ｍ１
Ｂ１：      ｍ２＝ｍ１ｙ１
Ｂ１→Ａ：  ｍ２
Ａ→Ｂ２：  ｍ２
Ｂ２：      ｍ３＝ｍ２ｙ２
Ｂ２→Ａ：  ｍ３
Ａ：       Ｋｍ＝ハッシュ（ｍ３（１／ｘ））
【０１８４】
Ｋを導出する際にＡｌｉｃｅの累乗計算を低減するために結合された鍵導出関数を使用する手法（５）のこのプロセスは、任意の数のサーバ１０３、１０４に明らかな方法で拡張することができる。この手法では、Ａｌｉｃｅはｍ１に関するＡｌｉｃｅの知識のプルーフをサーバＢ１に、ｍ２のプルーフをサーバＢ２に、という具合に送信すべきである。
【０１８５】
しかし、サーバ１０３、１０４が計算で媒介物として動作し、Ａｌｉｃｅが媒介の結果に対するアクセス権を有しない場合、Ａｌｉｃｅの動的な参加を証明するためには別の手法が必要となる場合がある。ＡｌｉｃｅがサーバＢ１と直接的に通信するだけの結合された鍵導出関数を使用する２つのサーバ構成の特別な場合を図５に示す。より具体的には、図５は、クライアント１０１が２つのサーバ１０３と１０４のうちの１つだけと通信するオペレーションを示す本発明の原理による方法５００の一例を示す流れ図である。
【０１８６】
ステップ５０１では、登録時刻｛ユーザＩＤ、ｙｉ、Ｖ｝が各サーバ１０３、１０４に記憶され、パスワード（Ｈｐ＝ハッシュ（Ｐ））のハッシュの暗号化されたコピーとユーザの秘密鍵Ｕがユーザの識別子｛ユーザＩＤ、暗号（Ｋｍ、｛Ｈｐ、Ｕ｝）｝に関連付けられるかまたは関係付けられたディレクトリに保存される。暗号化されたコンテナは、同様にＨｐを破損せずにＵを破損するようにコンテナが変更される危険性がないことを保証するためにメッセージ認証コードを含むことに留意されたい。
【０１８７】
ログインの時点で、ステップ５０２では、入力されたパスワード（上記のような）の適切な関数である群要素（Ｐ）が作成される。ステップ５０３では、ブラインドされた鍵のシェア（ｍ１＝Ｐｘ）が形成される。ステップ５０４では、ブラインドされた鍵のシェアは各サーバＢ１１０３に送信される。
【０１８８】
ステップ５０５では、ブラインドされた鍵のシェア（ｍ２＝ｍ１ｙ１）は第１のサーバ（Ｂ１）１０３上で形成される。ステップ５０６では、サーバＢ１はブラインドされたパスワードを短期メモリに記録し、ステップ５０７でブラインドされた鍵のシェア（ｍ２）を第２のサーバＢ２１０４に送信する。ステップ５０８で、Ａｌｉｃｅは公開ディレクトリからＡｌｉｃｅの暗号化されたパスワード検証子Ｈｐと秘密鍵Ｕとを獲得する。（ステップ５０８は便宜的な時点で実行することができる。）ステップ５０９では、両方の鍵のシェア（ｍ３＝ｍ２ｙ２）のブラインドされ結合された形式が第２のサーバ（Ｂ２）１０４上で形成される。ステップ５１０では、第２のサーバ（Ｂ２）１０４はｍ３を短期メモリに記録する。（サーバは要求値ではなく応答値を記録するということに留意されたい。さらなる説明は以下を参照のこと。）ステップ５１１でＢ２はｍ３をＢ１に送信し、Ｂ１はそれをＡｌｉｃｅに転送する。ステップ５１２では、Ａｌｉｃｅ１０１はその結合されたシェアをアンブラインドし、Ａｌｉｃｅのマスター鍵Ｋｍ＝ハッシュ（ｍ３（１／ｘ））を作成する。鍵導出用の反復された累乗法を使用する、Ｋｍ＝ハッシュ（Ｐｙ１ｙ２）に留意されたい。
【０１８９】
ステップ５１３で、クライアント１０１はＨｐおよびＵを取り出すためにＫｍを使用してディレクトリ・データを解読する。ステップ５１４および５１５では、Ｈｐがハッシュ（Ｐ）に等しくない場合、クライアント１０１はアボートする。ステップ５１６では、クライアント１０１はクライアントの秘密鍵Ｕを使用してブラインドされたパスワードｍ１とブラインドされ結合された鍵のシェア値ｍ３を含んでいる署名されたメッセージｍ４を作成し、それをクライアント１０１が合法的ユーザの代わりに動作していることのプルーフとしてＢ１に送信する。Ｂ１はこのメッセージをＢ２にも送信する。ステップ５１７で、サーバＢ１１０３はユーザの公開鍵Ｖを使用してメッセージｍ４のｍ１上の署名を検証する。ステップ５１８および５１９では、ｍ１上の署名が検証されてｍ１が疑わしいログイン要求の短期リスト内で発見される場合、ブラインドされた鍵のシェアｍ１はそのリストから消去される。
【０１９０】
ステップ５２０では、サーバＢ１１０３は、ユーザの公開鍵Ｖを使用してメッセージｍ４のｍ３上の署名を検証する。ステップ５２１および５２２では、ｍ３上の署名が検証されてｍ３が疑わしいログイン要求の短期リスト内に発見される場合、ブラインドされた鍵のシェアｍ３はそのリストから消去される。
【０１９１】
この場合、Ｂ１はＡｌｉｃｅとＢ２の間の媒介物である。Ａｌｉｃｅは要求値Ｐｘの知識をＢ１に対して証明し、応答値（Ｐｘｙ１ｙ２）の知識をＢ２に対して証明する。サーバＢ２は必ずしもＢ１が正直であると信用してはおらず、Ｂ２とＡｌｉｃｅの両方に周知の特別な値がＫｍの計算に使用されたことのプルーフを有することを必要とするので、このような検証は必要である。この場合、この特別の値はサーバの入力値またはサーバの応答値のどちらかである。
【０１９２】
前の例示の実施態様のＢ１およびＢ２の検証オペレーションの対称性に留意されたい。Ｂ１とＢ２が類似のオペレーションを実行する場合に代替方法を使用することが望ましい場合がある。例えばどちらも入力要求値（Ｂ１に対するｍ１とＢ２に対するｍ２）並びに応答値（Ｂ１に対するｍ２とＢ２に対するｍ３）の両方を短期リストに記憶することができ、両方をチェックすることによって検証関数を実行することができる。要求または応答値のどちらかが短期リストに記憶されているものと一致する場合に署名が受信されると、次いでその鍵取り出しプロセスが有効であるとみなされる。これらすべての手法のハッシュ関数は、固定長ビットストリングとして扱われる引数の単方向ハッシュ関数として実施することができる。「Ｓｅｃｕｒｅ  Ｈａｓｈ  Ｓｔａｎｄａｒｄ（安全なハッシュ標準）」，ＦＩＰＳ  １８０−１  Ｕ．Ｓ．Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙで議論されるＳＨＡ１標準ハッシュ関数を使用するこの実施態様に示すように複数の関数が連結される。
ハッシュ（ｘ、ｙ）＝ＳＨＡ１（ｘ‖ｙ）
【０１９３】
他の類似の鍵導出関数は周知である。
【０１９４】
Ｋｍの検証および前のサーバ認証
通信チャネルのセキュリティは想定されていないので、ユーザのクライアント１０１は、敵に情報を露出する任意の方法で結合されたマスター鍵を使用する前にその結合されたマスター鍵の有効性チェックを実行する。有効性チェックが失敗すると、ユーザはこのプロセスをアボートする。
【０１９５】
ユーザがＫｍをチェックする１つの方法は、Ｋｍの正確な登録された値に基づいて鍵によって対称的に暗号化された追加メッセージを得ることである。ユーザは、認証サーバ１０３、１０４の任意の１つなどの任意の便利な場所からこの暗号化されたメッセージを得ることができる。Ｋｍに対する交渉済みの値を使用することで、ユーザはメッセージを解読し、解読されたデータに対して有効性チェックを実行することができる。無効である場合、クライアント１０１はプロセスをアボートし、Ｋｍに対する交渉済みの値に関して情報が一切露出されないことを保証する。
【０１９６】
メッセージを検証する１つの方法は、データに大きな固定したシステム定数値Ｊを埋め込むことである。クライアント１０１は、解読された値がＪと一致する場合、その鍵が正確であると確信する。しかし暗号システムに基づいて、敵は、複数の異なる鍵によるメッセージの解読がすべて値Ｊを含むクリア・テキスト・データを生じるように特別にメッセージを構築することができるという懸念がある場合がある。これは良好に設計された暗号システムでは不可能であるべきだが、これに対する１つの防衛方法はＪをパスワードの１つの関数にすることである。
【０１９７】
一実施態様では、本発明者らはＳＨＡ１（“Ｊ”‖パスワード）でのようにパスワードの単方向ハッシュを計算する。クライアント１０１はＫｍを使用してメッセージを解読し、Ｊの解読された値をＳＨＡ１（“Ｊ”‖パスワード）と比較し、それらが一致する場合、Ｋｍは有効であると想定される。それらが一致しない場合、クライアント１０１は認証のプロセスをアボートし、Ｋｍに対するその無効な値から導出された値は潜在的な敵に一切入手可能にならないよう保証する必要がある。
【０１９８】
Ｋｍの検証は、Ｋｍを作成するために使用された増幅された鍵のシェアのすべてを暗黙的に検証する。
【０１９９】
シェアの小さな部分群の制限
懸念を起こさせるもう１つの問題は、ネットワーク１０２を制御する敵が、Ｐｙを戻すのではなく、識別要素１のような小さな部分群要素を単純に戻すことができることである。すべてのサーバの応答が小さな群要素の場合、Ｋｍは値の小さな集合のうちの１つになるように強いられる。例えば、すべてのサーバの応答が１であるという特別な場合、Ｋｍは以下のように定数値を有するように計算される。
Ｋｍ＝ハッシュ（１１／ｘ、１１／ｘ、．．．）＝ハッシュ（１、１、．．．）
【０２００】
部分群の制限はＫｍに対する好ましい変形態様の方法では問題ではないが、Ｊに対する値が固定したシステム定数である場合には問題となりうることに留意されたい。この場合、パスワードに関わらず、Ｊに関する周知の固定した値を常に露出するように識別要素がメッセージを解読するように、攻撃者は検証データを構築することができる。同様に｛ｙ１、ｙ２、．．．｝がすべて非常に小さい部分群である場合、Ｊに関する固定した値を発見するようにクライアント１０１がメッセージを解読する大きなチャンスを得ることができるように敵はメッセージを構築することができる。
【０２０１】
Ｋの小さな部分群制限を防止する１つの代替方法は、米国特許出願第０８／８２３，９６１号および「Ｅｎｃｒｙｐｔｅｄ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ：  Ｐａｓｓｗｏｒｄ−ｂａｓｅｄ  ｐｒｏｔｏｃｏｌｓ  ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  ｄｉｃｔｉｏｎａｒｙ  ａｔｔａｃｋｓ（暗号化鍵交換：ディクショナリ攻撃に対して安全なパスワードベースのプロトコル）」と題するＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｒｅｓｅａｒｃｈ  ｉｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ１９９２年５月の議事録であるＳ．ＢｅｌｌｏｖｉｎおよびＭ．Ｍｅｒｒｉｔｔの論文と、「Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｋｅｙ  Ｅｘｃｈａｎｇｅｓ（認証および認証済み鍵交換）」Ｄｅｓｉｇｎｓ  Ｃｏｄｅｓ  ａｎｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ、２、１０７〜１２５（１９９２年）と題するＷ．Ｄｉｆｆｉｅ，Ｐ．Ｃ．ｖａｎ  ＯｏｒｓｃｈｏｔおよびＭ．Ｗｉｅｎｅｒの論文に記載のようにクライアント１０１にこれを直接的に検出させるというものである。クライアント１０１がチェックしなければならない特別な場合の数を最小限に抑えるため、クライアント１０１はまた、要素のより小さな集合、おそらくは集合｛１｝に解を入れるように受信した値を累乗し、次いで米国特許出願第０８／８２３，９６１号に記載のような場合に関して試験することもできる。これらの特別な場合を除外することによって、Ｋｍに対するより広範な種類の検証試験を安全に使用することができる。
【０２０２】
｛ｙ１、ｙ１、．．．ｙｎ｝に対する値を制御し、Ｐに対する値に関して特別の予測を行う人物によるプロービング攻撃は常に可能であることに留意されたい。ここでの目的は、プロトコルの各実行中に敵に対してＰに対して多くても１つしか予測をさせないことなので、これはプロトコルの懸念ではない。
【０２０３】
グループ・パラメータ内での検証
グループを使用されるべきであると定義するシステム・パラメータは、モジュラスｍと（ｍ−１）の任意の必須の係数を含めて、クライアントとサーバの実施態様に内蔵される固定したシステム・パラメータであることが一般的に想定される。これらの値はシステム１００のすべてのユーザに対して使用することができる。
【０２０４】
別法として、これらの方法は、Ｄｉｆｆｉｅ−ＨｅｌｌｍａｎおよびＩＥＥＥ  Ｓｔｄ  １３６３−２０００，ＩＥＥＥ  Ｓｔａｎｄａｒｄ  Ｓｐｅｃｉｆｉｃａｔｉｏｎｓ  ｆｏｒ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ，ＩＥＥＥ、２０００年８月２９日、Ａ．１１．１、１３１頁に記載の関連するプロトコルのための楕円曲線暗号方法では一般的な慣習であるように、楕円曲線の点のグループなどの任意の適切なグループを使用することができる。
【０２０５】
方法は、サーバによってクライアント１０１に送信された、またはその反対に送信された変数パラメータも使用することができる。この場合、関係者は、主要性試験を使用することによって、あるいは信頼ある関係者によるかまたはそれらの関係者に対して有効性の十分な保証を提供する任意の他の手段によって生成されたパラメータに対する信用証明書を検証することによってそのパラメータが有効であることを保証することに責任を負う必要がある。
【０２０６】
「ランダム」指数
秘密指数｛ｙ１、ｙ２、．．．｝はどのような潜在的な敵にも入手不可能であるように選択された独立した数であるべきである。これらの数が任意の潜在的な敵によって独立したランダム値であるようにみなされる限り、これらの数は擬似乱数ジェネレータから導出することで十分である場合がある。一般的な暗号の習慣は、ハッシュ関数を使用してランダム入力の１つまたは複数の共通した秘密ソースから、そのような暗号の目的に対する擬似乱数のシーケンスを導出することである。
【０２０７】
より脆弱なモデルでの認証
後述するような本発明の好ましい実施態様を開発する過程で、代替方法は、場合によってはゼロ知識パスワード技術を使用せずにより脆弱なモデルで動作するように開発された。理想的ではないが、これらの方法は特別の場合には有用な可能性のある代替態様を提供する。本明細書に記載の３つの実施態様は、クライアントの記憶（本明細書ではＡＭ１と称する）を伴う単一サーバ・システム１００と、２つのサーバ・ローミング・システム（ＡＭ２）１００と、複数サーバ・ローミング・システム（ＡＭＭ）１００である。
【０２０８】
ＣＣの代替態様
ＡＭ１システム１００は、単一サーバ環境の場合のＣＣシステム１００に対する１つの代替態様である。ＡＭ１システム１００は、ＣＣによって強制されたすべての特別な制約を除去し、ユーザの秘密鍵の関数を広げ、それでもなおＣＣとしてユーザのパスワードに対する少なくとも等価レベルのセキュリティを提供する。ＣＣシステム１００は基礎をなす公開鍵システムの使用と、ユーザの秘密／公開鍵対の使用とにある種の強力な制約を課すが、ＡＭ１の手法はこれらの制約を解消する。この手法は、ＣＣよりも理解し、構築し、分析しやすいＣＣに対するより良い代替態様を提供することができる。
【０２０９】
登録
ＡＭ１登録では、クライアント１０１はＰＩＮコードＰ、秘密鍵ＥＣ、非対称暗号システムに対する対応する公開鍵ＤＣを選択する。ここではＥＣおよびＤＣに対して課される特別な制約は一切ない。クライアント１０１は、ゼロ知識の登録プロセスに適切な関数ｆまたは任意の他の適切に強力なパスワード・システムを使用して、Ｓに対する検証データとしてＳ＝ｆ（ｓａｌｔ、Ｐ）とＶを構築する。これは１９９７年６月のＪａｂｌｏｎの論文で議論されるＢ−ＳＰＥＫＥなどの低いエントロピーＳに耐える強力な拡張パスワード・システムを使用することが好ましい。
クライアントは以下を記憶する：
ｓａｌｔ     クライアント１０１にのみ記憶される秘密ｓａｌｔ値
ＤＳ          認証サーバ（ＡＳ）の公開鍵
Ｄｓ（Ｖ）   ＡＳに対して封印されたクライアントのパスワード検証データ
ＤＳ（暗号（Ｋ、ＥＣ））  Ｋの下で暗号化され、次いでＡＳに対して封印されたクライアントの秘密鍵
ＤＣ        クライアントの秘密鍵ではなく公開鍵
【０２１０】
認証
ＡＭ１認証では、ユーザはＰを入力し、クライアント１０１はＳ＝ｆ（ｓａｌｔ、Ｐ）を計算し、ＤＳ（Ｖ）をサーバに送信し、ＳおよびＶに基づいて適切に強力なパスワード認証をサーバと共に実行する。これはＢ−ＳＰＥＫＥ方法を使用して好適に行うことができる。
【０２１１】
ユーザがＶによって検証されたようにＳによって認証されると、サーバは、Ｓの知識を証明したユーザのみがそれを読むことができるように暗号（Ｋ、ＥＣ）を送信して戻す。Ｋ２がクライアントのＳの知識を証明したＢ−ＳＬＥＫＥプロトコルによって生成されたセッション鍵である場合に、サーバはＥｎｃＫ２（暗号（Ｋ、ＥＣ））を送信することが好ましい。クライアント１０１はＫ２およびＫを知っており、したがってＥＣを解読することができる。
【０２１２】
クライアント１０１は次いで、一般的な公開鍵の目的で｛ＥＣ／ＤＣ｝鍵対を自由に使用する。ＥＣおよびＤＣの使用を認証サーバだけによるトランザクションに限定するＣＣシステムとは対照的に、ＥＣおよびＤＣの使用には一切の制約は課されない。同様に、信用証明書または信用証明書の連鎖はクライアントの公開鍵に関連付けることができる。
【０２１３】
２つのサーバに対するＣＣローミングの代替態様
ＡＭ２システム１００を次に説明する。このシステムは、２つのサーバのローミング解決法で使用するために変更された場合にＣＣに対する代替態様を提供する。ＡＭ２システム１００は上記のＣＣローミング解決法よりも簡単な解決法である。
【０２１４】
登録
ＡＭ２登録では、ユーザは２つのパスワードＰ１とＰ２とを、好適にはＰ１の知識はＰ２に関する情報を露出しないように、またその反対でもあるように独立した値として選ばれるように選択する。ユーザは、各パスワードに対する検証データＶ１とＶ２とをそれぞれに構築する。ユーザは２つのランダム鍵Ｙ１とＹ２も選択し、Ｋ＝ハッシュ（Ｙ１、Ｙ２）を構築する。ユーザは、マスター鍵Ｋを使用して、好適には秘密鍵ＤＡを含めて対称的に秘密データを暗号化する。
第１の認証サーバＡＳ１は以下を安全に記憶する。
｛Ｖ１、Ｙ１、および任意選択で暗号（Ｋ、ＤＡ）｝
第２の認証サーバＡＳ２は以下を安全に記憶する。
｛Ｖ２、Ｙ２、および任意選択で暗号（Ｋ、ＤＡ）｝
【０２１５】
暗号（Ｋ、ＤＡ）がどこにも記憶されていない場合、これらのサーバ１０３、１０４のうちの１つはそれを記憶して、クライアント１０１がＰ１またはＰ２によって認証するときにそのコピーをクライアント１０１に戻す必要がある。
ユーザはＹ１を得るためにＳ１を使用してＡＳ１に対して認証する。
ユーザはＹ２を得るためにＳ２を使用してＡＳ２に対して認証する。
ユーザのマスター鍵Ｋ＝ハッシュ（Ｙ１、Ｙ２、Ｓ１、Ｓ２）。
ユーザは鍵Ｋを使用して自分の暗号化された秘密鍵暗号（Ｋ、ＤＡ）をアンロックする。
【０２１６】
ＥＡには特別な制約が一切ないので、１つまたは複数のサーバはＥＡを公然と記憶し、それを暗号化されていない形式でクライアント１０１に送信することができる。
【０２１７】
認証
ＡＭ２認証では、クライアント１０１は、ＡＳ１の検証データＶ１を使用してサーバＡＳ１によって認証されたセッション鍵ＫＳ１を得るためにＰ１を使用する。ＡＳ１はＫＳ１の下で対称的に暗号化されたＹ１を戻す。
【０２１８】
類似のプロセスは、Ｙ２を取り出す目的でサーバＡＳ２に対して認証するためにＰ２を使用してクライアント１０１によって反復する。
２つのサーバ１０３、１０４のうちの１つが暗号（Ｋ、ＤＡ）を戻す。
クライアント１０１はＫ＝ハッシュ（Ｙ１、Ｙ２、Ｓ１、Ｓ２）を計算し、ＤＡを解読する。
これでＤＡとＥＡはユーザの完全に機能可能な秘密および公開鍵として使用することができる。
【０２１９】
代替態様
ＡＭ２の代替の一実施態様では、クライアント１０１および／またはユーザ、または認証サーバ１０３、１０４の１つまたは両方がサーバの公開鍵の信頼性を事前記憶または検証することができる場合、サーバの記憶されたデータはサーバの公開鍵によってそれを封印することによってカプセル化することができる。これによってデータはサーバにアクセス可能なだけになり、これは対応する秘密鍵を所有する唯一のエンティティであると想定される。このような封印されたデータ・セットは次いで、必要に応じてクライアント１０１または他の認証サーバに記憶することができる。
【０２２０】
この方法は、Ｎ＞２である場合にＮ個のサーバ１０３、１０４の任意の数まで明らかな方法で拡大縮小するということにも留意されたい。Ｎ番目のサーバから鍵のシェアを登録し獲得するプロセスは、第１または第２のサーバ１０３、１０４に対するプロセスと同一であってよい。結合鍵は必然的に以下のように計算することができる。
Ｋ＝ハッシュ（ｋ１‖ｋ２‖．．．ｋｎ）
【０２２１】
拡大縮小の問題は後述し、ｎ＞ｍ＞１の場合にｎ個のサーバ１０３、１０４のうちのｍ個だけによる成功裡の認証を可能にするために耐障害性の問題が扱われる。
【０２２２】
非ゼロ知識の複数サーバ方法
次にＡＭＭシステム１００を複数サーバ環境に関して説明する。ＡＭＭシステム１００が、上述の好ましい複数サーバ・ローミング・システム１００よりも安全性の脆弱なモデルで動作する。一例は、ゼロ知識のパスワード・プロトコルを一切使用しないが、それでもなお、各Ｂｉがパスワードまたはクラック可能なデータを自分のデータベースに記憶しないという特性は維持している。このシステム１００の設計および類似の制限を説明する。
【０２２３】
各ＡＭＭサーバＢｉは、上記の好ましいシステム１００でのように各ユーザに対して１つのｙｉ値を記憶する。各ＢｉはＡｌｉｃｅからＰを受信するがこれはアンブラインドされた形式である。ＢｉはＫ＝ハッシュ（Ｐ、ｙｉ）でＡｌｉｃｅに応答する。Ｂｉはいかなるパスワード導出データを記憶しないので、盗まれたデータベースに対するディクショナリ攻撃の脅威はまったくない。
各サーバＢｉに対して、
Ａ→Ｂｉ：Ｐ
Ｂｉ→Ａ：Ｋｉ＝ハッシュ（Ｐ、ｙｉ）
Ｋｍは上記のように計算され、証明される。
【０２２４】
この方法は通信チャネルに対するさらなる保護を必要とするが、そうしないと盗聴者がＰに対してディクショナリ攻撃を仕掛ける危険性がある。ここでの１つの解決法は、１つのＳＳＬ／ＴＬＳサーバ認証チャネルを使用することである。
【０２２５】
限界：Ｂｏｂに対する攻撃
ＡＭＭシステム１００で対処されない重大な限界は、パスワードがサーバ上で使用されている間に盗まれる危険性があるということである。Ｂｏｂに対して優先順位の高いアクセス権を得る攻撃者は、Ｂｏｂのソフトウェアに対して悪意のある変更を行う機会を得る可能性も同様にある。このような変更は悪意のある管理者、悪意または好奇心のあるハッカー、またはウィルスによって間接的にでさえインストールされたパッチまたは更新の形式で行うことができる。Ｂｏｂがシステム１００のユーザに関するＰの値を一時的に受信すると、パッチされたソフトウェアが制御権を有し、インターセプトしてこれらのパスワードを収集し、それらを攻撃者に対して入手可能にすることができる。事実上、攻撃者は、自分固有のパスワード・データベースを構築することができる。これはたとえこのようなデータベースが通常はシステム１００上には存在しないとしてもである。
【０２２６】
限界：通信チャネルに対する攻撃
ＡＭＭまたは任意の他の非ゼロ知識の複数サーバ方法のもう１つの限界は、Ｐに対する盗聴者のディクショナリ攻撃を防止するためにチャネルをセキュリティ保護する何らかの他の手段を必要とすることである。これはＳＳＬまたは何らかの他のプロトコルによって達成することができるが、システム１００を脆弱にし、ローミング解決法に対して受容不可能にする傾向のある鍵または信用証明書をクライアント１０１が維持するさらなる必要条件をさらに提示する。
【０２２７】
パスワード認証の多くの非ゼロ知識形式は可能だが、Ｂｏｂは一般的に自分のディクショナリ攻撃を可能にするためにこれらのプロトコルの各実行中に情報を受信する。したがって、この情報はＢｏｂを損なう攻撃者にもリークされる危険性がある。ゼロ知識のパスワード・プロトコルは、動的なサーバを損なうことによる攻撃を防止する際には不可欠である。
【０２２８】
本発明の単純化されたセキュリティ・モデル
本発明者らの方法の注目に値する一態様は、それらが非常に単純なセキュリティ・モデルで動作するというものである。クライアント・コンピュータ１０１は、いかなるユーザまたはサーバ特有状態をも記憶する必要はなく、本発明者らはいかなる構成要素間にも以前にセキュリティ保護または認証された通信チャネルを必要としない。このモデルは、安全な複数サーバ・パスワード認証に対するいかなる従来の方法で提示されるモデルよりも単純である。
【０２２９】
好ましい実施態様では、クライアント１０１はユーザまたはいかなるサーバに対しても長期の信用証明書を保存する必要はない。このより単純なモデルは、複数のルート信用証明書オーソリティの一般的なＳＳＬ／ブラウザのモデルで提示される場合があるように、追加の障害点を低減する。ＳＳＬ／ブラウザのモデルは、ユーザからのかなりの量の動作および／または注意を必要とする複雑な信用の連鎖に複数の潜在的な脆弱なリンクを作成する。本発明者らのより単純なモデルは、サーバ１０３、１０４の従来の認証に依存するモデルで従来は一般的に「人間のエラー」に属していた重大なリスクを解消する。
【０２３０】
本発明は広範な適用範囲を有している。本発明の方法の利点はローミングの用途だけに限定されるものではない。非ローミングの用途、ユーザのマスター鍵Ｋｍは上記の好ましいシステム１００を使用して取り出され、Ｋｍはユーザのパーソナル・ラップトップ・マシン上にローカルに記憶されている信用証明書にアクセスして解読するために使用される。これは特別なハードウェアを使用せずに小さなユーザ選択のパスワードと遠隔に記憶されている鍵のシェア係数｛ｙ１、ｙ２、．．．｝によって保護されるクラック不可能なローカル記憶を提供する。敵がすべての関係するネットワーク・サーバ１０３、１０４を攻撃したとしても、ローカルのラップトップ・データに対するアクセス権をも有しない限りＫｍおよび保護されたデータが敵に露出することはないという付加的な保証も同様にある。
【０２３１】
公的にアクセス可能な場所に記憶されている秘密データを解読するための対称鍵を作成するため、認証するために対称鍵を作成するため、封印されたメッセージを受信するための公開／秘密鍵対を直接的に導出するためにマスター鍵を使用することができる。
【０２３２】
上述のシステム１００はスマートカードに対する予測される最良のソフトウェアベースの代替態様を提供する。
【０２３３】
詳細なプロトコルの説明
以下では、以下の表１に要約された表記法を使用してプロトコルの実施態様を詳細に提示する。
表１．表記法
記号    意味［妥当な例］
Ｃｉ      Ｂｉによって記憶されている信用証明書のリスト
Ｐ      パスワード［ハッシュ（パスワード）２ｒｍｏｄ  ｐ］から導出された対応するＧｑの要素
Ｇｑ    プライム・オーダーｑのグループ
［Ｚｐ＊において、ｐ＝２ｒｑ＋１、２２ｊ＞ｑ＞２２ｊ−１、２ｋ＞ｐ＞２ｋ−１、ｐおよびｒは素数］
ハッシュ  暗号ハッシュ関数［ＳＨＡ１］
ｊ      暴力的な攻撃に抵抗するセキュリティ・パラメータ［８０］
ｋ      ＮＦＳ離散ログ攻撃に抵抗するセキュリティ・パラメータ［１０２４］Ｋｉ      ＡｌｉｃｅとＢｉ［ハッシュ（Ｋｍ‖ｉ）］の間で共用される鍵
Ｋｍ      Ａｌｉｃｅのマスター鍵［連結されたシェアのハッシュ  ハッシュ（Ｓ１‖．．．‖Ｓｎ）ｍｏｄ  ２ｊ］
Ｌｉ      Ｂｉによって記憶された疑わしい悪い試行のリスト
パスワード    ユーザのパスワード、０＜パスワード＜２２ｊ［ＳＨＡ１（ＡＳＣＩＩパスワード）］
Ｒｉ      ブラインドされた鍵のシェア＝Ｐｘｙｉ
Ｓｉ      鍵のシェア＝（Ｐ）ｙｉ
Ｕ      Ａｌｉｃｅの秘密署名鍵
Ｕｋ      Ａｌｉｃｅの暗号化された秘密鍵＝暗号（Ｋ、Ｕ）
Ｖ      Ｕに対応するＡｌｉｃｅの公開鍵
ｙｉ      Ｂｉによって記憶されたＡｌｉｃｅの秘密シェア指数
暗号（ｘ、ｙ）    対称鍵ｘによって暗号化されたメッセージｙ
解読（ｘ、ｙ）    対称鍵ｘによって解読されたメッセージｙ
署名（ｘ、ｙ）    秘密鍵ｘによって署名されたメッセージｙ（メッセージｙが読まれるように）
【０２３４】
パラメータ。このプロトコルでは、対称関数に対する所望のビット強度を表すｊと、非対称関数のモジュラスに対して要求されるビット数を表すｋの２つのセキュリティ・パラメータが定義されている。
【０２３５】
ｐ、ｑおよびｒを奇数の素数、ｐ＝２ｒｑ＋１、２ｋ＞ｐ＞２ｋ−１、ｒ≠ｑ、および２２ｊ＞ｑ＞２２ｊ−１として、ＧｑはＺｐ＊の位数ｑの部分群と定義されている。Ｐ＝ハッシュ（パスワード）∧２ｒｍｏｄ  ｐの、パスワードを群要素Ｐ∈Ｇｑにマッピングする関数が使用される。
【０２３６】
（別法として、ｐ、素数ｑ、および小さな余因数ｒ∈［１、１００］などに略等価の位数ｒ・ｑの点の群と共にＧＦ（ｐ）の楕円曲線群を使用することができる。この場合、すべての累乗法はスカラー点乗法に置き換えられ、Ｐ＝ｒ・点（ハッシュ（パスワード））と定義される。ここで点は、曲線上に任意の点を発見する目的で擬似乱数ジェネレータをシードするためにハッシュ（パスワード）を使用する。これは、Ｄ．ＪａｂｌｏｎによるＡＣＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｒｅｖｉｅｗ第２６巻、ｎｏ．５、１９９６年１０月の「Ｓｔｒｏｎｇ  ｐａｓｓｗｏｒｄ−ｏｎｌｙ  ａｕｔｈｅｎｔｉｃａｔｅｄ  ｋｅｙ  ｅｘｃｈａｎｇｅ（強力なパスワードのみによる認証済み鍵交換）」と題する論文で議論されている。
【０２３７】
登録。ＡｌｉｃｅはパスワードＰを選択し、Ｐ：＝ハッシュ（パスワード）２ｒを計算し、デジタル署名を実行するために適した秘密鍵Ｕと対応する公開鍵Ｖとを作成する。次いでＡｌｉｃｅは、ランダムに選択されたｙｉ∈Ｒ［１、ｑ−１］を使用してＳｉ：＝Ｐｙｉとして各ｉ番目のシェアＳｉ∈Ｇｑが形成されるｎ個の鍵のシェアを作成する。次いでＡｌｉｃｅは、Ｋｍ：＝ハッシュ（Ｓ１‖．．．‖Ｓｎ）ｍｏｄ  ２ｊによって自分のマスターｊビット対称鍵を作成し、ＵＫ：＝暗号（Ｋｍ、Ｕ）として自分の暗号化された秘密鍵を作成し、自分の鍵検証データであるプルーフＰＫｍ：＝ハッシュ（Ｋｍ‖ｇ）を作成する。
【０２３８】
これらの信用証明書を登録するために、クライアント１０１は各Ｂｉで維持されるリストＣｉに記憶されるべきＡｌｉｃｅの信用証明書を送信する。これらは、以下のように、Ａの正確な識別を保証する認証済みの通信方法を使用してこれらの動作を実行しなければならない。
クライアント：各ｉ∈［１、ｎ］に対して、｛登録、Ａ、ｙｉ、Ｖ、ＵＫ、プルーフＰＫｍ｝→Ｂｉ
サーバ：Ｃｉに｛Ａ、ｙｉ、Ｖ、ＵＫ、プルーフＰＫｍ｝を記憶する
【０２３９】
認証済みの取り出し。認証済みの信用証明書の取り出しの場合、クライアント１０１とサーバ１０３、１０４は以下に列挙する動作を実行する。このプロセスで、各サーバは疑わしい悪いアクセスの試行の記録を含んでいるリストＬｉを維持する。
0004833489.tif 000006
【０２４０】
定期的に、おそらくは１分に１回、各Ｂｉは、（現在時刻−ｔ）が許容不可能なほどに大きすぎる悪い入力｛Ａ、Ｑ、Ｖ、ｔ｝に関してそのリストＬｉをスキャンする。悪い入力が発見されると、そのエントリはリストから除去され、ユーザＡに対して悪いアクセス試行イベントがトリガされる。最適化として、Ａｌｉｃｅはすべてのサーバ１０３、１０４に対してすべての最近のＱ値のリストを認証するために単一の署名を計算して送信するだけでよいということに留意されたい。
【０２４１】
性能の向上
ＦＫ１プロトコルと本発明者らのプロトコルを比較する場合、基礎的なブラインディング関数に対する群算術のコストと、関係する検証関数のコストと、各サーバに対してサーバ認証チャネルを使用することのコスト、利点およびリスクとを含めて考慮すべき要因が数点ある。
【０２４２】
ブラインディング・オペレーションのコスト。セキュリティ係数ｊ＝８０およびｋ＝１０２４によって、新しいプロトコルはＦＫ１よりも非常に高い性能を提供する。ｑ＝（ｐ−１）／２を使用すると、各ＦＫ１サーバは１つの１０２３ビット累乗法を実行しなければならず、またクライアントはこれを２つ実行しなければならない。
【０２４３】
本発明者らの方法を示したようにｐ＝２ｒｑ＋１を使用する場合、本発明者らは位数２１６０＞ｑ＞２１５９の部分群を使用する。後者の場合、２つのクライアントと１つのサーバの計算は概略で以前の量の１／６にまで低減される。等価の対称および非対称セキュリティ・パラメータを評価するための異なる方法がある場合、マイレージは異なる場合がある。
【０２４４】
しかし、ＡｌｉｃｅがＰ：＝ハッシュ（パスワード）２ｒで８６４ビットの累乗法を実行しなければならない場合にはクライアントの利点は実現しない。それでも尚、後述する１つのケースようにＰの代替構築ではいくつかの利点を再生することができる。
【０２４５】
現段階ではこの比較は、サーバ認証チャネルのセットアップを解消することによって達成できるいかなる付加的な節約をも無視している。しかし、すべてのサーバ認証を解消することによって、節約は、偽サーバ１０３、１０４による少数のオンライン予測を可能にし、かつおそらくは識別Ａを盗聴者に露出するという犠牲に見合う場合がある。
【０２４６】
Ｐの代替構築。代替構築Ｐ：＝ｇ１・ｇ２hash(password)mod q  ｍａｎを使用することができる。これは、相互に周知の指数関係がない位数ｑの２つのランダム要素である固定したパラメータｇ１とｇ２を使用する。ｇ１とｇ２に対して普遍的に受容可能な値を作成する１つの可能性は、ｇ１：＝ハッシュ（“ｇ１”）２ｒｍｏｄ  ｐにあるように、ランダムなオラクルとしてハッシュ関数を使用することである。
【０２４７】
同じセキュリティ・パラメータを使用して、代替構築は、クライアント１０１に対して１６０ビットの累乗法を３つと、サーバに対して１つとを必要とするが、これはＦＫ１と比較してクライアントのコストを５３％、サーバのコストを８４％低減するものである。
【０２４８】
認証関数のコスト。上記の方法は、ユーザが自分のブラインドされたパスワードの集合の信頼性を証明するためにデジタル署名を必要とする。幸いながら、クライアントの署名生成は、すべてのサーバ１０３、１０４に対する１つまたは複数の最近送信されたパスワード要求を包含するメッセージを作成するために１回実行するだけでよく、またサーバの署名検証はＲＳＡを使用する場合は高速である。
【０２４９】
さらに、クライアント１０１での公開鍵署名オペレーションのコストを解消するために、Ａｌｉｃｅはその方法の代わりに、ＡｌｉｃｅがＢｉによって登録する共用秘密鍵Ｋｉ＝ハッシュ（Ｋｍ‖ｉ）を使用して、鍵を掛けたメッセージ認証コードによって自分のブラインドされたパスワードの集合に「署名」することができる。この場合Ａｌｉｃｅは別個の鍵を登録し、サーバごとに別個の署名を構築する。
【０２５０】
セキュリティに対する引数。本発明のセキュリティに関して数個の単純な引数を以下に示す。
【０２５１】
各鍵のシェアは強力な秘密である。各シェアに関する重要なデータは、望ましくは安全な信用証明書サーバの秘密ｙｉ値にだけ記憶され、変形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ交換の指数でのみ解放される。この計算は、ｐ＝２ｒｑ＋１の形式の素数を法とするものであるが、これは攻撃者がｙｉに関して得られる情報を極度に制限するものである。プロービング攻撃によって決定することができるのは、ｙｉが２ｒｑと共通する係数を有するかどうかということだけである。しかし、ｙｉはランダムであり２以外のすべての係数は莫大なので、確率は無視できるほど僅少である。したがって、２０００年６月のＦｏｒｄおよびＫａｌｉｓｋｉの論文で指摘されているように、決定することができる唯一の情報はｙｉの低いビットである。
【０２５２】
いかなる露出した値にも任意の所与のＰによって生成された同等の確率があるので、Ａｌｉｃｅは自分のブラインドされた要求メッセージではＰに関する情報をまったくリークしない。同様に、Ｐｘｙ値などの追加のデータが存在する場合でも、ｙ値は攻撃者に周知の任意のデータによってＰには関連しないので、攻撃者がＰを決定するためには役立たない。
【０２５３】
Ａｌｉｃｅがサーバから任意の無効応答を受信した場合、任意の有用な情報を解放する前にＡｌｉｃｅはアボートするので、Ａｌｉｃｅの確認メッセージでＡｌｉｃｅからチャネルを制御する敵への情報リークの機会は僅少である。結合するハッシュ関数のせいで、マスター鍵の１つのシェアが不正確であると、結合された鍵は圧倒的な確率で不正確となる。同様に、マスター鍵が不正確な場合、同じ理由によって検証子ハッシュ値も不正確となる。したがってそれらが一致する場合、Ａｌｉｃｅは自分の鍵が正確であることを確信することができる。
【０２５４】
通信チャネルは、サーバによって送信されたＵＫとプルーフＰＫｍ値の保存性を保証する必要はない。その理由を知るためには、これらの値を偽造してそれらをＡｌｉｃｅに送信する悪意ある関係者を想定されたい。最悪の場合、この敵は各実行中にパスワードに対する単一の予測を検証するか、またはサービス攻撃の拒絶を実行することができる。クライアント１０１がサーバよりも悪い予測により耐えるようには設計されていない場合、これらの攻撃は安全なチャネルのモデルで予想される攻撃と略等価である。幸いながら、人間は、ログインの失敗に対して低い耐性しか有しない傾向があり、何度も繰り返す問題に関してシステム管理者に不平を漏らす可能性がある。しかしクライアント１０１は、少なくとも当該ユーザが確実にすべての失敗に気づくように設計される必要がある。どちらのモデルでも、敵は少なくとも１つの方向では制限された少数のオンライン予測を行うことしかできず、またメッセージを変更または削除することによってサービスの拒絶の原因となる場合がある。
【０２５５】
上記のハッシュ（パスワード）２ｒ関数と代替構築のどちらも位数ｑの要素を保証し、１９９７年６月のＤ．Ｊａｂｌｏｎの論文と２０００年６月のＦｏｒｄとＫａｌｉｓｋｉの論文で指摘された指数内パスワードと短い指数問題から保護する。
【０２５６】
短い指数
計算を低減する代替的な手法はより短い指数を使用することである。例えばｐ＝ｑ＋１による群では、１０２３ビットのｑによって範囲［１、２１６０−１］で指数を使用することができる。Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎでの短い指数の使用については、１９９６年５月のｖａｎ  Ｏｏｒｓｃｈｏｔ他の論文で議論されている。短い指数を使用する場合、Ｐｏｌｌａｒｄラムダ方法は周知の固定した基数ｇに対してｇｘのランダム指数ｘを計算する最も効率的な周知の方法である。ラムダ離散ログ計算は、約ｘ１／２のオペレーションを必要とする。しかし、より単純な解決法が発見されないという保証はない。
【０２５７】
ユーザが単純に一連のブラインドされたパスワードを露出するが他の情報は攻撃者に対して一切入手可能でないアボートされるプロトコルを想定されたい。フルサイズの均等に分散したランダム指数ｘ∈Ｒ［１、ｏ（Ｇｑ）］を使用する場合、Ｐｘ値はＰに関する情報をまったく露出しない。
【０２５８】
短い指数ｘ∈Ｒ［１、ｍ］、ｍ＜＜ｑを使用する場合、セキュリティは計算上の扱いにくさというさらなる仮定を必要とする場合があるが、不要な仮定は除去することが望ましい。この仮定が重要かどうかは未解決の問題である。
【０２５９】
したがって、短い指数が不要な仮定をもたらすという（おそらくは保証されていない）懸念によって、計算を低減する好ましい手法は、モジュラスよりも非常に小さいプライム・オーダーの部分群を使用するというものである。
【０２６０】
本発明は、従来技術で使用されるモデルよりも単純なモデルを使用する。このように行う際、人がサーバ１０３、１０４を安全に識別すべきなのにそれをしないシステムに固有の問題を解消する。本発明は、クライアントに記憶された鍵または信用証明書を必要とせず、性能は向上させて、またパスワード入力の際に人間のエラーをよりよく管理するための強化された責任によって、より単純なモデルで従来からの目的のすべてを達成する。これらの方法は、非常に少ない計算によって離散ログ攻撃から少なくとも等価レベルのセキュリティでの保護を提供することもできる。
【０２６１】
以上、複数のサーバを使用した遠隔パスワード認証を行うシステム、方法およびソフトウェアを開示した。上記の実施態様は、本発明の原理の用途を表す多くの特定の実施態様の一部を示しているだけであるということを理解されたい。明らかに、当業者は、本発明の範囲を逸脱せずに多数の他の構成を容易に考案することができる。
【図面の簡単な説明】
【図１】  本発明の原理によるシステムの一例のクライアントとサーバの構成要素を示すブロック図である。
【図２】  本発明の原理によるクライアント・オペレーションの方法の一例を示す流れ図である。
【図３】  本発明の原理によるサーバ・オペレーションの方法の一例を示す流れ図である。
【図４】  ２つのサーバを伴う１つのクライアントのオペレーションを示す本発明の原理による方法の一例を示す流れ図である。
【図５】  ２つのサーバのうちの１つのサーバだけと通信する１つのクライアントのオペレーションを示す本発明の原理による方法の一例を示す流れ図である。
【図１】
0004833489.tif 000007
【図２】
0004833489.tif 000008
【図３】
0004833489.tif 000009
【図４】
0004833489.tif 000010
【図５】
0004833489.tif 000011