(57)【特許請求の範囲】
【請求項１】
１つまたは複数の１回限りのパスコードを提供することができる認証トークンを所有するユーザをベリファイアにおいて認証するための方法であって、
検証レコードを認証サーバから得るステップと、
前記検証レコードを前記ベリファイア上に記憶するステップであって、前記検証レコードがある期間及び／又はイベントに対応し、パスコードに対応する情報を含むステップと、
前記検証レコードを提供する認証サーバから切り離されているベリファイアにおいて前記ユーザを認証するために提示されるパスコードを前記認証トークンから得るステップと、
前記提示されたパスコードが、前記認証サーバで生成される参照パスコードの関数である前記検証レコードと整合性があるかどうかを判定するステップと、
前記認証が行われなかった場合に前記検証レコードとパスコードの整合性を判定するのに要求される作業の量を時とともに増加させるステップと、
を含む方法。
【請求項２】
参照パスコードの関数として生成された、ある期間及び／又はイベントに対応し、パスコードに対応する情報を含む複数の検証レコードを認証サーバから得て格納するためのメモリと、
前記メモリに結合され、前記検証レコードを提供する認証サーバからの連絡を絶たれている状態で、コンピュータに提示されたパスコードが、前記検証レコードの所与の１つと整合性があるかどうかを判定して、パスコードを提供することができる認証トークンを所有するユーザを認証するプロセッサとを含み、
前記認証が行われなかった場合に前記検証レコードとパスコードの整合性を判定するのに要求される作業の量を時とともに増加させることを特徴とする、
コンピュータ。
【請求項３】
マシンによって実行されると、１つまたは複数の１回限りのパスコードを提供することができる認証トークンを所有するユーザをベリファイアにおいて認証することを、
検証レコードを認証サーバから得るステップと、
前記検証レコードを前記ベリファイア上に記憶するステップであって、前記検証レコードがある期間及び／又はイベントに対応し、パスコードに対応する情報を含むステップと、
前記検証レコードを提供する認証サーバから切り離されているベリファイアにおいて前記ユーザを認証するために提示されるパスコードを前記認証トークンから得るステップと、
前記提示されたパスコードが、前記認証サーバで生成される参照パスコードの関数である前記検証レコードと整合性があるかどうかを判定するステップと、
前記認証が行われなかった場合に前記検証レコードとパスコードの整合性を判定するのに要求される作業の量を時とともに増加させるステップと、
によって行う命令を有するコンピュータプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、暗号化技術に関し、より詳細には、コンピュータセキュリティのためのシステムに関する。
【背景技術】
【０００２】
当技術分野で知られるとおり、コンピュータおよび／またはコンピュータネットワークに対してユーザを認証するための様々なシステムが存在する。例えば、コンピュータにログオンするのに、ユーザは、通常、パスワードをタイプ入力する。しかし、当技術分野で周知のとおり、パスワードだけのシステムは、限られたレベルのセキュリティを提供する。
【０００３】
他の知られている認証システムは、２つの識別材料（ｆａｃｔｏｒｓ  ｏｆ  ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）を要求する。１つのそのようなシステムが、マサチューセッツ州ベッドフォード所在のＲＳＡセキュリティ株式会社によるＲＡＳ  ＳＥＣＵＲＩＤシステムである。一般に、このシステムは、ユーザが、英数字のＰＩＮ（個人識別番号）と、ユーザが所有している認証トークンの形態の、デバイスからのデータを入力することを要する。サーバは、ユーザＰＩＮと、サーバによって知られている、トークンからのセキュリティデータとを認証する。ＲＳＡ  ＳＥＣＵＲＩＤシステムは、参照により本明細書に組み込まれている、Ｗｅｉｓｓに発行された米国特許第４７２０８６０号で全体的に説明されている。
【０００４】
ＲＳＡ  ＳＥＣＵＲＩＤトークンのような認証トークンは、保護されていないチャネルを介して、サーバに対してユーザを認証するために、ますます一般的になっている。標準のパスワードの使用に勝る認証トークンの利点は、非常に多く、偽装攻撃の危険が低くなることに主に関する。偽装攻撃とは、許可されていない個人が、保護されたサーバに対して認証を試みて、それにより、例えば、企業ネットワークにアクセスすることを指す。
【０００５】
通常、認証トークンは、一部の情報を、ＲＳＡ  Ｓｅｃｕｒｉｔｙ  ＡＣＥサーバのような認証サーバと共有し、ただし、その情報は、通常、その他の存在には知られておらず、その情報は、何らかの認証ストリングの少なくとも諸部分の生成および検証を可能にする。この認証ストリングは、一般に、トークンの所有者によって記憶されており、サーバ上にも格納されている何らかの情報も含むか、またはそのような情報の関数である。認証は、対話型である、例えば、チャレンジ−応答形式であることも、非対話型である、例えば、認証ストリングの生成を完了するために、サーバからユーザ／トークンに全く情報が送信されないことも可能である。
【０００６】
現在、認証の試みを構成する情報は、無線ネットワークまたは有線ネットワークなどの、何らかの保護されていないかもしれない通信リンクを介して送信される。一般的なシナリオでは、認証トークンを所有するユーザは、サーバによって制御される何らかのリソースにアクセスすることを所望する。サーバは、攻撃に対して保護されているものと想定でき、したがって、サーバによって格納された秘密情報も、危険にさらされ、問題のユーザに成り済ます目的で使用されることは出来ないものと想定することができる。前述したリソースは、例えば、データベース、電子メールアカウント、記憶装置、または処理能力であることが可能である。そのリソースは、そのリソースが、認証を実行するサーバと一致しない限り、認証ストリングを生成するのに役立つ情報は、全く格納している必要がないものと想定することができる。
【０００７】
そのようなシステムは、リモート認証サーバに関連するユーザの認証のために有効であるが、現行のシステムは、認証サーバが、利用できない場合、有効ではない可能性があり、アクセスが所望されるリソースが、トークン所有者が所有しているコンピュータである場合、実用的ではない。そのような状況下では、コンピュータが、リモート認証サーバと対話することなしに、認証コードを検証することができれば、有益である。しかし、コンピュータが、紛失した、または盗まれた場合、またはそれ以外で、侵入者によって制御される場合は、その侵入者が、検証情報を獲得し、その情報を使用して、リモート認証サーバに対してユーザ（すなわち、トークン）に成り済まそうと試みることができる可能性がある。このため、トークン出力の認証を可能にするため、いくらかの情報が、コンピュータ上に格納されることが可能であるが、それにより、許容できないセキュリティ上の脆弱性が生じさせられてはならない。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
したがって、前述した欠点、およびその他の欠点を克服することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、無連絡認証のためのシステムを提供する。サーバが、一連の検証レコードを、サーバに対して認証済みである、ラップトップコンピュータなどのコンピュータにダウンロードする。一実施形態では、レコードは、所定の期間に対応する。別の実施形態では、レコードは、イベントに対応する。レコードは、ラップトップ上に格納され、所定の期間のための認証トークンによるデータ出力、例えば、パスコードに対応する情報を含む。レコードは、攻撃者が、所与の将来の期間のためのトークン出力を知ることができる可能性を最小限に抑えるための方法およびフォーマットで格納されて、ラップトップに対する認証、および／またはサーバに再接続された際のユーザ成り済ましを阻止するようにする。
【００１０】
一般に、ベリファイアが、１つまたは複数の１回限りのパスコードを提供することができる認証トークンを所有するユーザを認証する。検証レコードが獲得され、パスコードが獲得される。次に、パスコードが、検証レコードと整合性があるかどうかが判定され、ただし、検証レコードは、参照パスコードの関数である。
【００１１】
一実施形態では、レコードは、一方向関数を使用して、暗号化された、不明瞭にされた、またはそれ以外で読めなくされた値を含む。ハッシュ関数が、そのような一方向関数の一例である。１つの特定の実施例では、ハッシュアルゴリズムが、入力として、所与の期間のためのトークン出力値、いわゆるソルト値と、いわゆるペッパ値とを受け取る。サーバからダウンロードされる結果のハッシュ値が、レコードの一部として、ラップトップ上に格納される。所定の期間のための各トークン出力時間間隔に対するレコードが、格納できる。ユーザは、トークン出力が、ユーザによって提供され、トークンデータ、ソルト値、およびペッパ値のハッシュが、その所与の時間間隔に対応するレコードと合致する場合、ラップトップに対して認証される。
【００１２】
本発明は、添付の図面と併せて解釈される以下の詳細な説明から、より完全に理解されよう。
【発明を実施するための最良の形態】
【００１３】
本発明は、認証サーバと通信することができないエージェント、例えば、ラップトップパーソナルコンピュータ（ＰＣ）における無連絡認証を円滑にするシステムを提供する。認証サーバに接続されると（無連絡の期間に先立って）、所定の期間に対応する一連の検証レコードが、エージェントにダウンロードされる。一実施形態では、エージェントが、認証サーバによって生成された１回限りのパスコードの処理済みの、例えば、ハッシュ化されたバージョンを格納する。
【００１４】
一般に、ベリファイアが、１つまたは複数の１回限りのパスコードを提供することができる認証トークンを所有するユーザを認証する。参照パスコードの関数である検証レコードが、獲得される。時間、イベント、チャレンジなどの関数として生成されることが可能な、提示されたパスコードが、以下に詳細に説明するとおり、検証レコードと整合性があるかどうかが判定される。一実施形態では、無連絡にされたユーザが、提示されたパスコードが、対応する検証レコードと整合性があるかどうかを判定することによるユーザの検証のために、認証トークンからベリファイアにパスコードを提示する。
【００１５】
１つの特定の実施形態では、ＲＳＡセキュリティ株式会社によるＲＳＡ  ＳＥＣＵＲＩＤトークンのような、ユーザの時間ベースの、またはシーケンスベースの認証トークンのシード値に基づき、時間ベースのパスコードが生成される。検証レコードは、例えば、ユーザが、旅行する前にダウンロードされることが可能である。代わりに、検証レコードは、１回のログインセッションの期間のため、例えば、数分間から数時間のためにダウンロードされることが可能である。このため、各検証レコードは、シード値から生成されることが可能な参照パスコードの関数である。
【００１６】
時間ベースのトークンの場合、１回限りのパスコードは、短い時間、例えば、１分間だけ有効である。各トークン時間間隔に対するレコードが、ダウンロードされなければならない。代わりに、（場合により、中間の）シード値などの、ダウンロードされる情報は、レコードが、ベリファイア自体によって生成されることを可能にするようにダウンロードされなければならず、ただし、シード値は、レコードが生成された後、削除されなければならない。これは、以下に図２で説明する、階層シード導出が関わるスキームに対してより適切である。というのは、中間シード値は、単一のマスタシードを有し、中間シード値を全く有さないスキームの場合と比べて、限られた存続期間を有するからである。トークン出力の期間は、エージェント上で知覚される時間に対する変化とは独立であり、トークンによって制御される。無連絡期間中、エージェントは、ユーザによって入力されたパスコード情報をハッシュ化して、格納されハッシュ化されたパスコードと比較して、合致の存在を確認し、これにより、ユーザを認証することができる。つまり、認証のための提示されたパスコードが、所与の検証レコードと整合性があるかどうかが判定され、ただし、検証レコードは、例えば、認証サーバによって生成されることが可能な参照パスコードの関数である。
【００１７】
図１は、本発明による無連絡認証を有する例示的なシステム１００を示す。ベリファイアとしてのパーソナルコンピュータ（ＰＣ）のようなエージェント１０２は、サーバによる認証のために、オプションのネットワーク１０６を介してサーバ１０４と通信することができる。ユーザは、ＰＩＮ（個人識別番号）、および認証トークン１０８からのデータをエージェント１０２に提供することができ、エージェント１０２は、その情報をサーバ１０４に通信する。一般に、トークン１０８は、エージェント１０２を制御するユーザが所有している。トークン１０８からの情報が、キーボードを介するなどして、ユーザによってエージェントに提供されること、あるいは、例えば、有線または無線の通信リンクによって自動的に提供されることが可能である。トークンに対する情報も同様に、必要な場合、様々な形で提供される。また、トークンは、ベリファイア内部で実施される「仮想」ソフトウェアトークンであってもよい。サーバは、トークン出力を、いくつかの時間間隔の（かつ／または複数のイベントに対応する）レコードに照らして検証して、クロックドリフト、または同期のその他の損失によって、サーバへのユーザのアクセスが無効にされないようにすることができるものと理解されたい。
【００１８】
ユーザの認証の後、サーバ１０４は、以下により完全に説明するとおり、限られた期間に対するユーザの認証を円滑にする情報をエージェント１０２に提供することができる。その構成では、許可されていない個人によるエージェント１０２へのアクセス、および／または再接続時にサーバ１０４に対して許可されたユーザに成り済ますのに成功することが、可能性が低いようにされることが可能である。
【００１９】
トークン出力またはトークンコードが、時間変数およびトークン秘密（例えば、シード値）の関数である、時間ベースのトークン、トークン出力またはトークン応答が、トークンに与えられたチャレンジ値およびトークン秘密の関数である、チャレンジ−応答トークン、トークン出力が、イベントカウンタおよびトークン秘密の関数である、またはトークン出力が、トークン秘密の関数であり、このトークン秘密が、何らかのイベント（例えば、トークン上のボタンを押すこと）に応答して更新される、イベントベースのトークン、および以上の何らかの組合せが関わるトークンを含め、様々なトークンタイプがサポートされることが可能である。また、トークン状態情報も、参照により本明細書に組み込まれている、２００３年１１月６日に出願したＭ．ＪａｋｏｂｓｓｏｎおよびＡ．Ｊｕｌｅｓ、「Ｉｄｅｎｔｉｔｙ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄｓ」、米国特許出願第１０／７２４０３４号でさらに説明するとおり、トークン出力を導出するプロセスに組み込まれることが可能である。さらに、１回限りのパスコードは、いずれの特定の関数によっても生成される必要がなく、トークンの中に格納され、認証サーバと共有されるランダムな値であることが可能である。また、トークンは、コンピューティングデバイス自体である必要はなく、代わりに、パスコードが印刷されたカード（「スクラッチオフ」の一種かもしれない）から成ることも可能である。パスコードという用語と、認証ストリングという用語は、互いに区別なく使用されるものと理解されたい。
【００２０】
さらに、ＰＩＮが、トークン出力に付加されること、またはそれ以外の形で、１回限りのパスコードを計算するプロセスの中に含められることが可能である。この結合は、トークン自体によって、または別の場所で行われることが可能である。代わりに、ＰＩＮは、トークンに与えられ、トークンによってローカルで検証されてから、トークンが、出力を生成してもよい。また、バイオメトリクスを使用して、トークンに対してローカルで認証を行ってもよい。しかし、ＰＩＮまたはバイオメトリックは、本明細書で説明する諸方法に必須ではない。
【００２１】
図２は、図１と併せて、本発明による無連絡認証のためにダウンロードされることが可能な情報を示す。１つの特定の実施形態では、認証トークン１０８は、年間シード１５２ａ〜ｍを生成するルートシード１５０を含み、年間シード１５２ａ〜ｍから、月ごとのシード１５４ａ−ｎが生成される。１日ごとのシード１５６ａ〜ｏが月ごとのシード１５４から、次いで１日ごとのシード１５８ａ〜ｐ、１時間ごとのシードａ〜ｐが生成され、以下同様であり、最終的に、６０秒（１分）ごとのような、所望の時間間隔で固有値１６０ａ〜ｑが生成される。シード値は、当技術分野で周知の形で一方向関数を使用して、生成されることが可能である。また、認証サーバ１０４も、それらの値を生成して、トークン値を検証することができるようにすることができる。さらに、それらの値は、エージェントにダウンロードされるレコードを生成するのに使用される。
【００２２】
ユーザが、サーバ１０４からの無連絡が生じることを知っている場合、３日間１６２のような、所定の期間を範囲に含む、レコードの形態の認証情報が、サーバによってエージェント１０２にダウンロードされることが可能である。レコードは、トークンに関する所与の時間間隔にそれぞれ対応することが可能である。ダウンロードされた情報は、サーバ１０４に対する再認証までの３日間１６２にわたって、ユーザが、コンピュータ（エージェント１０２）にアクセスすることができるようにしなければならない。ダウンロードされたレコードは、ラップトップコンピュータを盗んだ個人などの、許可されていない人が、コンピュータにアクセスし、かつ／または認証サーバに対してユーザに成り済ますのを極めて困難にするように格納されなければならない。多くのケースでは、攻撃者は、ユーザに成り済まして、例えば、企業ネットワークへのアクセスを得ることを所望することが理解されよう。
【００２３】
本発明は、パスワードまたは個人識別番号（ＰＩＮ）が、認証トークンからの情報とともに提供される諸実施形態、ならびにチャレンジ／応答の諸実施形態に適用可能であるものと理解されたい。
【００２４】
ダウンロードされる情報は、様々な自動機構および手動機構を使用してダウンロードされることが可能である。しかし、認証サーバは、ユーザが、情報をダウンロードするのを許可されていることを検証しなければならない。一般に、ダウンロードされた情報は、エージェント上にレコードとして格納されて、エージェントが、各レコードが関連する時間間隔を特定することができるようになる。
【００２５】
例示的な実施形態では、ダウンロードされたレコードは、所定の期間に対応する。例えば、許可されたユーザが、サーバからの３日の無連絡期間を有することが可能である。サーバは、その３日の期間中に認証を行うためのレコードをダウンロードすることができる。レコードは、チャレンジ／応答データに対応する情報を含むことが可能である。一実施形態では、レコードは、チャレンジｃに応答して、時刻ｔにおける認証トークンの応答Ａｔ（ｃ）に対応する暗号化されたデータを含み、このデータは、レコードの一部分を形成する。しかし、チャレンジは、要求されない。以下にさらに説明するとおり、時間ベースの値を単独で使用することもできる。より一般的には、本発明は、前述した様々な認証トークンタイプに適用可能である。
【００２６】
時間ベースの（いくつかの箇所では、チャレンジベースでも）認証トークンが想定されるが、本明細書で説明する技術は、イベントベース、またはその他の非時間ベースの諸実施形態にも容易に適合されるものと理解されたい。例えば、トークン出力を時間変数に関連付ける代わりに、出力は、カウンタに関連付けられることが可能であり、レコードは、相応して、期間（例えば、３日間）には直接に対応せず、代わりに、トークン出力の回数（例えば、３００回のトークン出力）に対応することが可能である。便宜のため、時間ベースの実施形態を以下に一般的に説明するが、イベントベース、またはシーケンスベースの実施形態への変換、およびチャレンジの組み込みは、当業者には直ちに明白であろう。Ａｔ（ｃ）という表記は、この様々な代替を表すものとする。
【００２７】
以下の説明は、ハッシュ関数の使用について主に述べるが、一方向アルゴリズムおよび一方向ではないアルゴリズムを含め、様々なアルゴリズムタイプが、本発明の範囲に完全に含まれるものと理解されたい。本明細書で使用する一方向関数とは、計算するより、逆算することが相当に困難である一方向関数を指す。ＳＨＡ２５６（連邦情報処理規格（ＦＩＰＳ）ＰＵＢ１８６−２、「Ｓｅｃｕｒｅ  Ｈａｓｈ  Ｓｔａｎｄａｒｄ（ＳＨＳ）」、Ａｕｇｕｓｔ  ２００２で定義される）のような標準のハッシュ関数を使用することができる。代わりに、よく理解されているとおり、反復ハッシュ構成、例えば、ＳＨＡ２５６の１０００回の連続的な反復を使用して、ユーザには、比較的小さいオーバーヘッドを維持しながら、攻撃者には、計算コストを大きくすることが有益である可能性がある。さらに、本発明は、時間ベースの変数、例えば、トークン出力を一方向関数に与えることに関連して、一般的に説明するが、変数は、イベントなどに対応することも可能であるものと理解されたい。
【００２８】
１つの特定の実施形態では、ダウンロードされたレコードは、所定の期間、例えば、３日間にわたるトークンの各時間間隔に対して、Ａｔ（ｃ）のハッシュとともに、ソルト値およびペッパ値を含む。ソルト値は、関連するレコードと一緒に格納され、ペッパ値は、格納されない。ソルト値は、異なる時刻に対して、たいてい異なる。代わりに、１つまたは複数のシード値などの情報が、レコードが生成されることを可能にするためにダウンロードされることも可能である。
【００２９】
本明細書で使用するソルト値とは、ハッシュ化された（または別の形で暗号化された）情報の一部として含められる値を指す。ソルト値は、例えば、所定のビット数を有する乱数として提供されることが可能である。ソルト値は、レコードと一緒に格納されてもよく、あるいは、格納要件を小さくするために、レコードセットに関連するマスタソルト値、ならびに所与のレコードに関連するその他の情報から生成されてもよい。当業者には理解されるとおり、ソルト値は、トークン出力などのセキュリティ値を獲得する辞書タイプの攻撃を失敗させる。ソルト値は、異なる時刻に対して異なるので、セキュリティ値を決定するために攻撃者によって要求される作業は、各時間間隔に対して実行されなければならない。というのは、ソルトは、ハッシュ化されたデータの一部だからである。
【００３０】
本明細書で使用するペッパとは、ハッシュ化されたデータの一部である、知られている、または予測可能な数のビットを有する値を指す。しかし、ソルト値とは異なり、ペッパ値は、格納されない。また、ペッパ値は、ダウンロードされない。このため、可能なペッパ値が、計算され、各ペッパ値に対して、ハッシュ関数が評価される。ペッパは、実際の値を明らかにするのに、可能なペッパ値に対してハッシュ関数が計算されなければならないので、辞書タイプの攻撃が遅くなるようにさせる。
【００３１】
図３に示した１つの特定の実施形態では、時刻ｔに対応する所与のレコード２００が、ハッシュ関数出力２０２に対応する情報を含む。ハッシュ関数に対する入力には、時刻ｔに対するトークン出力、Ａｔ（ｃ）２０４、時刻ｔに対するソルト値２０６、および時刻ｔに対するペッパ値２０８が含まれる。コンピュータへのアクセスを得ようと試みる場合、ユーザは、トークン出力Ａｔ（ｃ）２０４を提供するように求められることが可能である。ペッパ値２０８は、格納されていないので、ハッシュ関数は、可能なペッパ値において評価されるものと理解されたい。それらの値のそれぞれに対するビットの数は、様々である可能性があるが、例示的なビット数には、Ａｔ（ｃ）に対する２０ビット、ペッパに対する１０ビット、ならびにソルトに対する２１ビットが含まれる。結果のハッシュ関数２０２評価が、所与の時刻に対する格納されたレコード２００と比較されて、正しい値が明らかにされ、コンピュータへのアクセスを得る。
【００３２】
チャレンジが行われない場合、ｃは、格納されないものと理解されたい。更に、チャレンジが行われない場合、Ａｔは、ｃの関数ではなく、ユーザは、トークンの中にｃを入れることを要求されない（あるいは、トークンが、有線または無線の通信リンクを有する場合、トークンは、チャレンジｃを受け取ることを要求されない）。本発明は、チャレンジの実施形態および非チャレンジの実施形態に適用可能であるものと理解されたい。
【００３３】
所与の時刻に対するトークンセキュリティデータＡｔ（ｃ）２０４を知らず、ペッパ値２０８を知らずにハッシュ関数出力を計算することは、２０ビットのＡｔおよび１０ビットのペッパの場合、２２０×２１０＝２３０のオーダの計算を要求する。前述したとおり、ソルト値２０６は、知られているが、すべてのレコードに対する並行タイプの攻撃を防止する。
【００３４】
さらなる実施形態では、個人識別番号（ＰＩＮ）値２１０（図３にファントムで示す）が、ハッシュ化されるべきデータの一部分を形成することが可能である。ＰＩＮデータが、１３ビットである場合、攻撃者は、各時間間隔に対して、２３０×２１３＝２４３のオーダの作業を有する。以下にさらに完全に説明するとおり、演算は、レコードがダウンロードされた期間の有効期限切れより前に実行されなければならない。
【００３５】
図４に示した１つの特定の実施形態では、ＳＨＡ２５６として知られている公開の２５６ビットハッシュ関数が使用される。ＳＨＡ２５６からの２５６ビット出力は、認証トークンからのセキュリティ情報（すなわち、トークン出力またはパスコード）、ソルト、および可能なペッパの入力から計算される。ＳＨＡ２５６ハッシュ関数出力の一部分が、格納されたレコードと比較されることが可能である。例示的な実施形態では、ＳＨＡ２５６出力の上位１２８ビットが、格納されたレコードとの比較のために、ｈ’（ｘ）として定義されることが可能である。入力が正しい場合、ハッシュ結果（可能なペッパ値に対する諸結果からの）の１つに対するｈ’（ｘ）が合致する。
【００３６】
正しいペッパ値に対するＳＨＡ２５６ハッシュ関数出力の下位１２８ビット（ｈ″（ｘ））が、Ｗｉｎｄｏｗｓパスワードの暗号化された値を解読するキーとして使用される。この構成では、正しいＷｉｎｄｏｗｓパスワードは、認証トークンからの正しいセキュリティ情報が入力された場合にだけ、抽出されることが可能である。
【実施例１】
【００３７】
時間は、１つのトークン出力が表示される期間に等しい間隔に分けられる。１つのレコードが、それぞれのそのような期間に関連する。何らかの（任意の）ベースライン時間の後の第ｉ番の期間が、時間ｉと呼ばれ、その期間に関連するレコードが、ｒｅｃ＿ｉと呼ばれる。そのようなレコードは、トークンシードの知識を使用して、ＡＣＥサーバのようなマシンによって計算される。次に、レコードのバッチが、そのマシンから、ベリファイアと呼ぶことができる、トークン出力のオフライン検証を後に実行するマシンにダウンロードされる。ベリファイアは、通常、ラップトップである。
【００３８】
初期設定プロセス（レコードのバッチがダウンロードされるたびに、認証サーバによって実行される）は、以下のとおりである。例えば、４０ビットから８０ビットまで範囲の固定長を有するランダムなソルト値ｓａｌｔ＿ｉが、選択される。１０ビットから２５ビットまでの範囲の固定長を有するランダムな値ｐｅｐｐｅｒ＿ｉが、選択される。トークン、例えば、ＲＳＡ  ＳＥＣＵＲＩＤ、出力が、時間間隔ｉに対して計算され、正しいＰＩＮが付加されるか、または別の形で結合される。これを値ｖａｌ＿ｉとし、値ｖａｌ＿ｉは、６桁のトークンおよび４桁のＰＩＮの場合、３４ビット長である。ｖａｌ＿ｉを唯一のトークン出力とすることが可能であり、その場合、ＰＩＮは、ハッシュレコードを介して検証されない。値ｙ＝ＳＨＡ２５６（ｐｅｐｐｅｒ＿ｉ，ｓａｌｔ＿ｉ，ｖａｌ＿ｉ）が計算される。Ａ＿ｉをｙの第１の部分とし、ただし、Ａ＿ｉは、例えば、８０ビットから１２８ビットまでの範囲の固定サイズである。Ｂ＿ｉをｙの第２の部分とし、この部分は、１２８ビットであることが可能である（ただし、Ａ＿ｉのいずれの部分も含まない）。値Ａ＿ｉは、後に、認証の試みの正しさを検証するのに使用されるのに対して、Ｂ＿ｉは、Ｗｉｎｄｏｗｓパスワード、秘密キー、あるいはベリファイア上で使用するのが有益である他の任意の秘密情報を暗号化することができるキーを提供する。データ要素とも呼ばれるこの情報は、Ｍと呼ばれ、Ｂ＿ｉを使用したＭの暗号化は、Ｅ＿ｉと呼ばれる。Ｍの暗号化のために、周知のＡＥＳアルゴリズムを使用することができる。Ｍが、１２８ビットより長い場合、暗号は、暗号ブロック連鎖（ＣＢＣ）モードで使用される。ｒｅｃ＿ｉ＝（ｓａｌｔ＿ｉ，Ａ＿ｉ，Ｅ＿ｉ）とする。ｐｅｐｐｅｒ＿ｉ、ｖａｌ＿ｉ、およびＢ＿ｉという量は、レコードの中に含められず、ベリファイアに送られないことに留意されたい。
【００３９】
情報Ｍは、様々な形態をとることが可能であるものと理解されたい。既に述べた、Ｗｉｎｄｏｗｓパスワードを解読するためのキーに加え、情報は、以下のとおりであることが可能である。すなわち、
ベリファイア上のファイル、またはその他のデータを解読するための次世代暗号化標準（ＡＥＳ）などの、対称キー暗号システムのための秘密キー
メッセージ認証コード（ＭＡＣ）を使用してデータを認証するための秘密キー
ファイル、またはその他のデータを解読するための、ＲＳＡ公開キー暗号システムなどの非対称（公開キー）暗号システムにおけるプライベートキー
デジタル署名スキームを使用してデータを認証するためのプライベートキー
例えば、別のコンピュータ上の、アプリケーションを認証するための秘密キーまたはプライベートキー
他のキー（それら自体、前述した秘密キーまたはプライベートキーであることが可能な）をラップ解除するための秘密キーまたはプライベートキー
ユーザプロファイル情報（例えば、クレジットカード番号）などのセンシティブな情報、またはローカルパスワードテーブルを保護するためのキー
任意のセンシティブなデータ
Ｗｉｎｄｏｗｓパスワード自体である。
【００４０】
さらに、値Ｂ＿ｉを使用してＭを暗号化する代わりに、Ｂ＿ｉから直接にキーを導出することもできる。代わりに、値Ｂ＿ｉ自体も、キーとして使用することができる。
認証プロセスは、以下のとおりである。ユーザが、ユーザ名（オプション）、現在のトークンコード、およびＰＩＮ（オプション）を入力し、それらから、値ｖａｌ＿ｉが獲得される。ベリファイアが、ユーザ名（入力されている場合）および時間に基づき、入力をマッチさせるレコードｒｅｃ＿ｉを選択する。ｐｅｐｐｅｒ＿ｉの可能なすべての値にわたる全数探索を使用して（任意の所望の順序で）、値ｙ＝ＳＨＡ２５６（ｐｅｐｐｅｒ＿ｉ，ｓａｌｔ＿ｉ，ｖａｌ＿ｉ）が計算される。第１の部分（Ａ＿ｉと同一サイズの）が、ｒｅｃ＿ｉの中の値Ａ＿ｉと比較されて、合致が存在するかどうかが判定される。何らかのペッパに対して合致が存在する場合、認証は、成功する。その場合、Ｂ＿ｉをｙの第２の部分とする。値Ｂ＿ｉを使用してＥ＿ｉを解読して、Ｍを得ることができる。
【００４１】
１回限りのパスコードに対してよく理解されるとおり、トークンとベリファイアの間における同期のいくらかの損失が存在する可能性がある。例えば、参照により本明細書に組み込まれているＷｅｉｓｓの米国特許第４８８５７７８号を参照されたい。したがって、レコードｒｅｃ＿ｉで認証が成功しない場合、ベリファイアは、１つまたは複数の隣接するレコードで再び試みることができる。また、ベリファイアは、以前のトークンコードの再使用を防止するために、以前の成功した認証で使用済みであるレコードを常に把握しておくこともできる。
【００４２】
代わりに、Ａ＿ｉ値を計算する代わりに、ベリファイアは、Ｂ＿ｉ値だけを計算し、Ｅ＿ｉの解読の成功だけに基づいて、ユーザを認証することもできる。例えば、暗号化操作が、解読中に検査されるパディングまたはチェックサムなどの冗長性を含む場合、または暗号化された値Ｍ自体が、検証されることが可能な冗長性を有する場合、解読の成功により、正しいキーＢ＿ｉが使用されたという確信がもたらされる。これにより、次いで、提供されたセキュリティ情報が正しかったという確信がもたらされる。このアプローチは、Ａ＿ｉ値が、計算される、または格納されることがないので、格納要件および計算要件が小さくなるという利点を有する。
【００４３】
別の代替として、値Ｍの使用の成功が、セキュリティ情報が検証される手段であることも可能である。例えば、値Ｍが、Ｗｉｎｄｏｗｓパスワード（またはパスワードが解読されるキー）である場合、Ｗｉｎｄｏｗｓパスワードは、セキュリティ情報が正しいかどうかを判定する手段として、Ｗｉｎｄｏｗｓオペレーティングシステムによって検証されることが可能である。正しさの確信が大きくなることに加え、このアプローチは、値が、冗長性なしに暗号化されている場合、その値が、検証されるために、使用されなければならず、これにより、その値が使用される攻撃がシステムに知らされる可能性があるという利点も有する。つまり、レコードを獲得する攻撃者は、値Ｍを使用することなしに、セキュリティ情報に対する推測が正しいかどうかを確認することができないことが可能である。
【００４４】
また、前述した様々な代替法の諸要素を組み合わせて、正しさの確信が、Ａ＿ｉの合致、Ｅ＿ｉの解読の成功、および／またはＭの使用の成功からもたらされるようにすることもできる。
【００４５】
図５に示した本発明の別の態様では、ハッシュ関数に対するソルト値を「シェークする」こともできる。一実施形態では、第１の列２５０の中に示した各ハッシュレコードと、列２５２の中の対応するソルト値の間の関連が、並べ替えられた形で格納される。つまり、あるハッシュ出力と一緒に格納されたソルト値は、そのハッシュ出力に対するソルト値ではない。この構成では、ソルト値は、所与のハッシュ出力に対応するソルト値を明らかにするように試験される。当業者に知られている多種多様な機構を使用して、ソルト／ハッシュ関連を並べ替えることができる。
【００４６】
やはり図５に示す、さらなる実施形態では、ソルト値は、列２５４の中で示すとおり、別々に格納される第１のｓａｌｔ１、および第２の部分ｓａｌｔ２に分けられる。第１のソルト部分と第２のソルト部分が分けられ、並べ替えられ、格納される。ソルトは、様々な技術、および様々な仕方で、任意の数の部分に分けられ、並べ替えられることが可能であることが、当業者には直ちに明白であろう。使用することができるソルトとペッパの多数の混合が存在することが、さらに直ちに明白であろう。
【実施例２】
【００４７】
「ソルトシェーカ」初期設定プロセスの一環として、何らかの数ｎの、例えば、１０００のレコードが、同時に準備される。ペッパは、空のストリングに設定される（すなわち、ペッパは、全く使用されない）。各レコードに対して、これは、タプル（ｓａｌｔ＿ｉ，ｖａｌ＿ｉ，Ａ＿ｉ，Ｂ＿ｉ，Ｅ＿ｉ）をもたらす。それらの中で、ベリファイアは、Ｂ＿ｉ以外の全部を受け取る。しかし、いずれの値も送られる前に、ｎ個のｓａｌｔ＿ｉ値が、ランダムに並べ替えられる。ｓａｌｔ＿ｉ値のビットストリングは変更されず、それらの値が関連付けられたレコードだけが変更される。並べ替えの後、ｒｅｃ＿ｉ＝（ｓａｌｔ＿ｉ，Ａ＿ｉ，Ｅ＿ｉ）というフォーマットのｎ個のレコードが存在し、ただし、ｓａｌｔ＿ｉは、今や、第ｉ番の位置に並べ替えられたソルトを意味するように使用される。値Ａ＿ｉまたは値Ｅ＿ｉは、並べ替えられない。
【００４８】
検証プロセスでは、ベリファイアは、ｓａｌｔ＿ｉ値とＡ＿ｉ値のすべての組合せを網羅的に試みる。ベリファイアは、それぞれのそのようなソルト値に対して、第１の部分を、選択されたレコードのＡ＿ｉ値と比較して、値ｙ＝ＳＨＡ２５６（ｓａｌｔ＿ｉ，ｖａｌ＿ｉ）を計算する。このプロセスは、正しい値の計算を、平均でｎ／２倍に、最悪ケースとしてｎ倍に「遅延させる」。したがって、これは、長さ１０ビットのペッパ値に相当する。さらなるレコードを処理する必要なしに、より長い遅延を生じさせることは簡単である。
【００４９】
計算コストを平均ｎ＊ｎ／２倍に増加させるために、ソルト値を同一サイズの２つの部分に分け、それぞれのそのような部分が、次に、ランダムなレコードに関連付けられ、すなわち、半分が、独立に並べ替えられる。すると、レコードは、（ｓａｌｔ＿｛ｉ１｝，ｓａｌｔ＿｛ｉ２｝，Ａ＿ｉ，Ｅ＿ｉ）というフォーマットを有し、ただし、ｓａｌｔ＿｛ｉ１｝は、並べ替えられた第１の半分であり、ｓａｌｔ＿｛ｉ２｝は、並べ替えられた第２の半分である。トークン値を検証するのに、ベリファイアは、第１の半分のソルト値と第２の半分のソルト値のすべての組合せの中で全数探索を行う必要があり、これは、平均ｎ＊ｎ／２回の試行を要する。各ソルトをさらに小さい部分に分けることにより、さらに、第１の半分を先にする順序でそれらの部分を格納せず、各レコードに対してランダムな順序で格納することなどによっても、計算作業を容易に増大させることができる。作業を増大させる別の仕方は、やはり探索されなければならない「ダミー」レコードを挿入することである。
【００５０】
図６は、時間の経過により、攻撃者が、コンピュータにアクセスすることに成功するのに要求される作業が増大する、本発明の別の態様を示す。１つの特定の実施形態では、ユーザが、例えば、３日間にわたる認証レコードをダウンロードする。前述したとおり、攻撃の成功に要求される作業は、２４３回の計算を要する。ユーザが、１日などの、所定の期間にわたってログインしない場合、例えば、次の日、攻撃の成功のための作業の量は、２×２４３に増加する。ユーザが、２日間、ログインしない場合、すると、作業は、４×２４３に増加する。追加の作業は、正しいセキュリティ情報を提供したユーザを認証するのに要求される時間も徐々に増大させるが、攻撃者に要求される作業は、引き続く期間ごとに、例えば、１日ごとに２倍になる。ユーザがログインするのにかかる遅延は、顕著であってもよいが、許容できるものでなければならない。
【００５１】
一般に、コンピュータの作業は、本当のユーザが認証を行う際、本明細書で説明する本発明の技術がない場合と、同程度（かつ、比較的低く）なければならない。ユーザが、比較的長い期間にわたって認証を行っていなかった場合、計算コストが増大することは許容できる。しかし、システムは、可能なすべての組合せを試みることによってレコードを「分解する」ための多くの時間を、攻撃者に与えてはならない。したがって、将来の時間間隔に対応するレコードは、攻撃者が、それらのレコードを攻撃するためのより多くの時間を有するので、現在の時間間隔に対応するレコードよりも強力に保護されなければならない。
【００５２】
コンピュータへの許可されていないアクセスを得ようと試みる攻撃者は、要求される最低限の作業量で侵入することに達するように動機付けられていることが理解されよう。このため、攻撃者は、ダウンロードされたレコードに対応する所定の期間、例えば、３日間の終り近くまでトークン出力が回復されない時間間隔を選択する気にはならない可能性がある。攻撃者は、要求される作業の量に起因して、攻撃が可能である限られた期間を有する。
【００５３】
やはり図６を参照すると、一実施形態では、それぞれのログインの成功により、次のログイン、または次の期間に対する「ヒント」へのアクセスが提供される。例示的な実施形態では、ペッパ値に対するビットの数は、ユーザがログインしない日ごとに増加する。例えば、１日目に、ペッパ値は、１０ビットであり、これは、前述したとおり、２４３回の計算という量の作業に相当する。ユーザが、１日目の間にログインしない場合、ペッパ値は、２日目には、１１ビットに増加する。ユーザが、１日目にログインする場合、２日目の１１ビットペッパの１ビットが、２日目に使用するために獲得されて、２日目に対する１０ビットの有効ペッパ値がもたらされるようになる。
【００５４】
ユーザが、１日目または２日目の間にログインしない場合、３日目に対するペッパ値は、１２ビットに増加し、これは、２×２×２４３の作業に相当する。ユーザが、１日目または２日目の間にログインすることなしに、２日目にログインしようと試みた場合、アクセスを得る際の遅延は、より多くのペッパ値に対応する、より多くの計算に起因して、増大する可能性がある。しかし、増大した遅延は、法外であってはならない。
【００５５】
ヒントを提供することは、ペッパビットを獲得することとして説明されるが、ヒントを提供する仕方は、本明細書に含まれる説明に鑑みて、当業者には直ちに明白な形で、ビットの数、時間、前回のログインの日付、値のタイプなどに変更することが可能であるものと理解されたい。以下では、ヒントは、ペッパとは別個の変数として扱うが、ペッパの一部分、またはその他の特性として実施することもできる。
【００５６】
別の実施形態では、ヒントは、ペッパ値の空間の選択された諸部分、またはシェークされたソルト値の並べ替えから提供される。例えば、論理的「１」または論理的「０」である確率が等しくないランダムなビットを有する、ペッパ空間の等しくない部分が選択されることが可能である。
【実施例３】
【００５７】
時間間隔ｉに対して、レコードｒｅｃ＿ｉ＝（Ａ＿ｉ，Δ＿ｉ，ｓａｌｔ＿ｉ）である。また、時間も、ｔによって指し示される、２４時間間隔または暦日などの、より長い期間に分けられる。各期間ｔは、例えば、１〜１０ビット長の範囲内にあることが可能な、値ｈｉｎｔ＿ｉに関連付けられる。時間間隔ｉが属する、より長い期間は、ｔ＿ｉと表され、いくつかの連続的な時間間隔が、同一のより長い期間に属する（例えば、時間間隔が１分であり、より長い期間が１日である場合、１４４０の時間間隔）。
【００５８】
入力値ｖａｌ＿ｉを受け取った場合、その値が、ｒｅｃ＿ｉと合致するかどうかを検証することが望まれる。ここで、ｖａｌ＿ｉは、より長い期間ｔ＿ｉの一部であり、ｈｉｎｔ＿｛ｔ＿ｉ−１｝は、既知であるものと想定されたい。ヒントは、前のより長い期間中に、ユーザが、サーバに対して認証されることに成功した場合に分かる。ベリファイアは、ｐｅｐｐｅｒ＿ｉの可能なすべての値に対して、量（Ａ｜Ｂ）＝ｈ（ｖａｌ＿ｉ，ｈｉｎｔ＿｛ｔ＿ｉ−１｝，ｓａｌｔ＿ｉ，ｐｅｐｐｅｒ＿ｉ）を計算し、ただし、ｈ（）は、ハッシュ関数を示し、Ａは、Ａ＿ｉと同一サイズであり、ｓａｌｔ＿ｉは、間隔ｉに対するソルト値を指し、ｐｅｐｐｅｒ＿ｉは、間隔ｉにおける可能なペッパ値を指し、Ｂは、解読キーとして使用されることが可能なハッシュ出力の一部分を指す。量Ａが、値Ａ＿ｉと比較されて、合致する場合は、（ｖａｌ＿ｉ，ｐｅｐｐｅｒ＿ｉ）が、その時間間隔に対して、レコードｒｅｃ＿ｉに対応すると考えられる。
【００５９】
値Ｂを使用して、Ｗｉｎｄｏｗｓパスワードまたは他のデータと、次のヒントをともに暗号化することができるものと理解されたい。それぞれを解読するのに十分な情報が、レコードの中のフィールドＥ＿ｉとして格納されることが可能である。代わりに、デルタ値Δが、格納されて、Ｂの何らかの部分とＸＯＲ演算されると、結果が、何らかの将来の時間間隔のためのヒントを生成する。値Δは、認証サーバによって計算され、何らかの前の時点でコンピュータにダウンロードされることが可能である。
【００６０】
値ｈｉｎｔ＿｛ｔ＿｛ｉ−１｝｝が既知ではない場合、可能なすべての値が、網羅的に試みられなければならない。これは、システムの「正直な」使用にも、攻撃者が、壊れたマシンの状態を所与として、量ｖａｌ＿ｉを算出することを所望する攻撃にもともに当てはまる。
【００６１】
ヒントは、値Ｂから計算される。詳細には、ｈｉｎｔ＿｛ｔ＿ｉ｝＝Δ＿ｉ  ＸＯＲ  Ｂ’であり、ただし、Ｂ’は、Ｂのビット（またはそれ以外の形で、Ｂを介して獲得されたビット）である。このため、ｒｅｃ＿ｉを計算する当事者は、Δ＿ｉ＝Ｂ  ＸＯＲ  ｈｉｎｔ＿｛ｔ＿ｉ｝であるように設定し、ただし、ｈｉｎｔ＿ｉは、ｒｅｃ＿ｉの中の値とは独立に選択され、ＸＯＲは、排他論理和関数を指す。これにより、次のより長い期間中、ヒントを知らない当事者と比べて、ｈｉｎｔ＿｛ｔ＿ｉ−１｝を知っている当事者による、（Ａ｜Ｂ）の「割り引かれた」計算が可能になる。ヒントを知らない当事者は、可能なすべてのヒントを、可能なすべてのペッパと組み合わせて試みなければならず、ヒントを知っている当事者は、前の成功した認証からのヒントを保持しており、可能なすべてのペッパを試みるだけでよい。このため、ペッパは、皆が遅くなるようにし、ヒントは、ヒントを知らない人々だけが遅くなるようにする。
【００６２】
以上では、ヒントに関連する計算上の割り引きを得るために、直前のより長い期間内に明らかにされたヒントを知っている必要がある。（代わりに、ただし、割り引きなしに、現在の期間内にヒントについて解くこともできる。というのは、ヒントは、同一の期間内の他のレコードに対して同一だからである。）一実施形態では、さらに早期の期間内に受け取られたヒントの知識を有する当事者に、同様の便益を与えることが望ましい。
【００６３】
ヒントのサイズが１０ビットである場合、１０ビットの割り引きが、直前のより長い期間のヒント値を知っている当事者に与えられることが可能である。９ビットの割り引きが、２つ前のより長い期間のヒントを知っている当事者に与えられることが可能であり、８ビットの割り引きが、３つ前のより長い期間のヒントを知っている当事者に与えられることが可能である。これは、ｈｉｎｔ＿ｔ＝ｆ（ｈｉｎｔ＿｛ｔ−１｝，ｒ＿ｔ）とすることによって達することができ、ただし、ｒ＿ｔは、ランダムなビット（または、連続するヒント間の有用性の差が、２以上でなければならない場合、数ビット）である。この場合、ｆは、ＬＦＳＲ（リニアフィードバックシフトレジスタ）、一方向関数、または入力部分を適切に結合する他の機構として選択することもできる。
【００６４】
以上の説明は、計算作業が、前回の知られているヒント以来の期間の数とともに指数的に増大する設定に対応する。
代わりに、以下に説明するとおり、計算作業は、期間の数とともに直線的に増大するようにされることも可能である。セットアップ段階中、システムは、レコードがベリファイア上に格納されるべき、それぞれのより長い期間ｔに対するランダムな暗号化キーＫ＿ｔを生成する。システムは、Ｂ＿ｉ’ＸＯＲ  Δ＿ｉが、ランダムな暗号化キーを明らかにするようにΔ＿ｉを定義する。キーＫ＿ｔは、認証の成功の後に回復される。１日ごとの暗号化キーＫ＿ｔを使用して、ビットストリングＭ＿１、Ｍ＿２、．．．Ｍ＿Ｔの比較的小さいテーブルが暗号化され、ただし、Ｍ＿ｊは、第ｊ番の後続の期間に対する「マスク」であり、Ｔは、認証の成功が「割り引き」をもたらす、先の期間の数である。各値Ｍ＿ｊは、ペッパが、第ｊ番の後続の期間で出現する可能性がある、可能なペッパ値の空間の異なる部分に各ビットが対応する、Ｔビットストリングである。値Ｍ＿ｊはｊビットが設定される。これは、知られている（先行し、成功した認証の試みを所与として）Ｍ値が新しいほど、可能なペッパ値の探索空間が小さくなり、これにより、相応して、計算がスピードアップされる。
【００６５】
後に、認証の試みの成功のため、ストリングＭ＿１．．．Ｍ＿Ｔが導出され、ベリファイアによってプレーンテキストで格納される。これにより、将来の認証の試みの計算コストの低減が可能になる。Ｍ＿ｊのあるビットが設定されている場合、ペッパは、空間のその部分から探索されるべきであり、クリアである場合、そうではない。Ｍ＿ｊは、ｊビットが設定され、これは、ペッパ空間が、次の長い期間の完全なサイズの１／Ｔに縮小され、その後に続く長い期間に対して、２／Ｔに、その次の長い期間に対して３／Ｔに、といった具合に縮小されることを意味する。連続的な長い期間の間に明らかにされ、所与の将来の期間に対応するＭ＿ｊ値は、前の期間中に明らかにされたＭ＿ｊ値より、１ビット多くクリアされていて、異なる長い期間中に明らかにされるＭ＿ｊ値が、望ましくない量の情報を漏らさないようにしなければならない。
【００６６】
一実施形態では、レコードの新たな「長い期間」が、サーバに対する認証時に、定期的にベリファイアにダウンロードされる。マスクは、新たな長い期間に対して機能しなければならず、これは、サーバが、マスクを常に把握しておかなければならないことを意味する。ベリファイアによる最初のダウンロード（初期認証を要求する）は、初期セットのマスクから成ることが可能である。
【００６７】
また、前述した技術は、いわゆるソルトシェーカ実施形態に対しても機能し、ヒントが、並べ替えられたソルト値とともにハッシュ関数に入力され、次のヒントが、レコードの中で暗号化される。１つの代替の実施形態では、ソルトシェーカ実施形態の文脈におけるヒント値は、先行する成功した認証の試みに対応するソルト部分を消去するか、またはそれ以外で、それらの部分に探索済みであるというマークを付ける。すると、そのレコード、および関連するソルトは、将来の認証の試みに対して探索されず、これにより、それぞれの成功した認証の試みに対して、ある計算上の割り引きが提供される。ある限定された期間（並べ替えられたレコードセットに関連する）に対して存在する、成功した検証の試みの回数が多いほど、計算コストは、低くなる。
【実施例４】
【００６８】
時間は、日数に、例えば、２４時間に配分される。例えば、ユーザが、第１の２４時間中に、ベリファイアに対して認証を行うことに成功した場合、その後、２４時間を開始する期間に対して、トークン出力を検証するのは、より安価にならなければならず、次の２４時間に対して、はるかに安価であり、同一の２４時間に対して大幅に安価にならなければならない。
【００６９】
ペッパ値は、例えば、最大ペッパが、４０９５に等しい場合、範囲［０．．．最大ペッパ］から選択される。この範囲は、４つの部分、［０．．．１０２３］、［１０２４．．．２０４７］、［２０４８．．．３０７１］、［３０７２．．．４０９５］に分けられることが可能である。所与の日のすべてのペッパ値は、それらの４つの範囲の同一の範囲内から選択される。ユーザが、ベリファイアに対して認証を行うことに成功すると、ベリファイアには、それがどの部分であるかが分かり、したがって、同一日のうちの、あらゆるさらなる試みは、計算作業の点で、通常、かかるコストの１／４だけしかかからない。これは、同日後ほどのペッパが、同日のそれより前からと同一の範囲からであることが分かっており、ベリファイアが、その範囲を思い出すことに起因する。これは、次の日に対して、割り引きを与えない。しかし、値Ｍが、次の日に対するペッパのために使用されない２つの間隔（４つのうちの）についての情報を含む場合、これは、次の日のすべての認証の試みが、さもなければかかるコストの半分で実行されることを可能にする。
【００７０】
さらに、値Ｍが、次の次の日のために使用されない１つのペッパ間隔についての情報を含む場合、これにより、次の次の日に対して、１／４の計算上の割り引きが与えられる。２日間のヒントは、２つのヒントにより、コストを１／４に低減されることが、それが所望される振舞いでない限り、行われないようにするため、次の日のヒントのサブセットでなければならないことに留意されたい。
【００７１】
前述した様々なペッパおよびソルトシェーカのアプローチの利点は、攻撃者へのコストが、レコードを生成するコストに比較的小さい影響しか与えることなしに、大幅に増加されることである。これは、特に、新たなトークン出力が頻繁に（例えば、毎分）生成される時間ベースの認証トークンに対して、認証サーバにおいて多数のレコードが生成されることが要求される場合、魅力的であり、これは、多くのユーザが存在する場合、該当する可能性がある。しかし、ペッパアプローチおよびソルトシェーカアプローチは、必須ではない。代替のアプローチは、反復される、または別の形で遅くされたハッシュ関数を使用することである。これも、攻撃者へのコストを大幅に増加させるが、生成により大きい影響を与える可能性がある（というのは、レコードを生成する当事者も、単にペッパまたはソルト並べ替えを選択するのではなく、より遅いハッシュ関数を使用しなければならないからである）。
【００７２】
ペッパアプローチまたはソルトシェーカアプローチに対する別の代替は、Ｒ．Ｌ．Ｒｉｖｅｓｔ、Ａ．Ｓｈａｍｉｒ、およびＤ．Ａ．Ｗａｇｎｅｒ、「Ｔｉｍｅ−Ｌｏｃｋ  Ｐｕｚｚｌｅｓ  ａｎｄ  Ｔｉｍｅｄ−Ｒｅｌｅａｓｅ  Ｃｒｙｐｔｏ」、ｔｅｃｈｎｉｃａｌ  ｍｅｍｏ  ＭＩＴ／ＬＣＳ／ＴＲ−６８４、ＭＩＴ  Ｌａｂｏｒａｔｏｒｙ  ｆｏｒ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、Ｆｅｂｒｕｒａｙ  １９９６で説明されるような、時間ロックパズルを使用することである。時間ロックパズルは、効率的に構築することができるが、解決は、多数の演算を要するパズルである。例として、パズルは、値ｙ＝ｘ＾（２＾ｋ）ｍｏｄ  ｎの計算を要することが可能であり、ただし、ｎは、大きい合成モジュラスであり、ｘおよびｋは、所与の整数である。パズルを構築する当事者も、ｎの因数を知っており、そのため、ｐｈｉ（ｎ）を知っており、ただし、ｐｈｉ（ｎ）は、オイラーのファイ関数である。したがって、その当事者は、ｙ＝ｘ＾ｒ  ｍｏｄ  ｎとしてｙを効率的に計算することができ、ただし、ｒ＝２＾ｋ  ｍｏｄ  ｐｈｉ（ｎ）である。しかし、パズルを解く当事者は、モジュラスｎだけを知っており、ｐｈｉ（ｎ）は知らず、したがって、ｋ回の連続的なモジュラー・スクウェアリング（modular squarings）を実行しなければならない。ここでは、入力ｘが、ハッシュ関数への入力に取って代わり、値ｋは、コストを制御する可変の整数であり、出力ｙが、ハッシュ関数の出力に取って代わる。
【００７３】
時間ロックパズルは、ペッパまたはソルトシェーカと同一の特性を有し、すなわち、検証のコストが、生成のコストの大幅な増加なしに、増加される。しかし、ペッパアプローチおよびソルトシェーカアプローチでは、攻撃者が、偶然、予期されるよりも少ない演算で、ペッパまたはソルト並べ替えを正しく推測することができる可能性が残る。時間ロックパズルアプローチでは、反復ハッシュアプローチと同様に、攻撃者は、基本的に、要求されるすべてのステップを実行しなければならず、推測されるべき未知数は存在せず、行われるべき作業だけが存在する。（それでも、必要とされる場合、例えば、ハッシュまたはパズルへの入力のさらなる部分として、そのような「未知数」を容易に受け入れることができ、これにより、ヒントをこれらのアプローチに組み込む方法が提供される。）
さらなる実施形態では、レコードがダウンロードされた所定の間隔を過ぎた時刻におけるアクセスのために、「長期」ヒントが提供されることが可能である。例えば、３０日の期間のためのレコードがダウンロードされ、ユーザが、３０日の期間にわたってログインしなかった場合、ユーザは、電話を介して認証サーバまたはコールセンタと連絡をとり、さらなるパスコードを獲得する必要がある可能性がある。これは、比較的長い、緊急アクセスコードと考えることができる。
【００７４】
例示的な実施形態では、ダウンロードされたレコードには、第１の期間、例えば、最初の３０日に対する、前述したとおり、第１のフォーマットで格納されたレコードと、第２の期間、例えば、次の３０日に対する、第２のフォーマットで格納されたレコードとが含まれる。一実施形態では、第２の３０日に対するレコードは、前述した暗号化に加え、緊急アクセスコードで暗号化される。この構成では、緊急アクセスコードを獲得すると、ユーザは、第２の３０日期間中に認証を行うことができる。緊急アクセスコードは、第２の３０日期間内の時間間隔に対するハッシュの検証を円滑にするヒントと考えることができる。また、緊急コードを使用して、ヒントへのアクセスを可能にすることもできる。
【００７５】
代替の実施形態では、比較的長いペッパ値、例えば、８０ビットが、ハッシュ関数に入力されることが可能である。８０ビットのうち、ベリファイアには、最初、ペッパビットのうち６０ビットが与えられることが可能であり、これは、暦月などの、所定の期間にわたって同一である。次の月に対する６０ビットは、知られていない。次の月に対する６０ビットは、例えば、サーバに対する認証を介して、またはコールセンタによって提供されることが可能な口頭の電話通信を介して獲得されることが可能である。
【００７６】
１２８ビットのように、比較的長い緊急キーのユーザを含む、すべてのレコードは、一緒に暗号化されることが可能であり、あるいは個別のレコードが、「拡張されたペッパ値」を使用することができ、拡張は、緊急キーであり、３０日期間のすべてのレコードに対して同一であるものと理解されたい。緊急コードが明らかにされ、レコードと一緒に格納されると、ペッパ探索は、ペッパ値の拡張が全く行われなかった場合と同様に簡単である。
【００７７】
さらなる変種として、ユーザは、認証を行うため、一部のケースで、複数のトークン出力を使用するように要求されることも可能である。既に説明した技術は、２つ（またはそれより多く）のトークン出力（通常、連続的な）、およびオプションとして、ＰＩＮから、値ｖａｌ＿ｉを導出することにより、そのケースに対応するように容易に変更される。例として、ベリファイアに、第１の３０日期間のための通常のレコードセット（単一のトークン出力から導出された）、および次の３０日のための変更されたレコードセット（２つのトークン出力を要求する）が提供されることが可能である。このようにして、３０日間を超えて無連絡にされていたユーザは、依然、認証を行うことができるが、２つのトークン出力を使用して初めてそうすることができ、これは、次のそれらの３０日に対する正しいトークン出力を探索することの、攻撃者へのコストを大幅に増大させ、ベリファイア上に格納された将来のレコードに、適度により強力な保護を与える。実際、そのような強い保護で、１年分以上の将来のレコードを格納できる可能性があり、それにより、無期限の無連絡期間がサポートされる。しかし、多くのケースで、管理ポリシーは、ユーザが、サーバに対してときどき認証を行って、ユーザが、無連絡にされたマシンを使用することを許可されたままであることを検証するよう要求する可能性がある。それらの認証中にダウンロードされるさらなるヒントを将来のレコードに組み込んで、そのポリシーを強制することもできる。
【００７８】
前述したヒント機構を、この場合も、有益に適用することができる。変更されたレコードセットは、暗号化されたヒントも含むことが可能であり、したがって、ユーザが、２つのトークン出力を使用して第２の３０日期間中に認証を行った場合、それらの３０日中に単一のトークン出力を使用する後の認証を可能にするヒントが、獲得される。この特徴を実現する１つのやり方は、第２の３０日間のために２つのレコードセット、すなわち、暗号化されたヒントも含む、２つのトークン出力を要求する変更されたレコードセット、および単一のトークン出力に加えて、ヒントを要求する通常のレコードセットを有することである。第２の３０日期間に先立つ、攻撃者へのより高いコストは、依然、維持される。というのは、攻撃者は、２つの正しいトークン出力を推測する必要があるか、または１つの正しいトークン出力、およびヒント（比較的長いことが可能な）を推測する必要があるからである。しかし、ユーザが、２つのトークン出力を使用して、第２の３０日期間中に認証を行うことに成功すると、その期間に対するヒントが明らかにされ、ユーザは、その後、単一のトークン出力を使用して認証を行うことができる。
【００７９】
同様の構造が、複数の期間に対して適用されることが可能であり、したがって、ユーザが、新たな期間に入るたびに、２つのトークン出力が要求される。１つのケースとして、ユーザは、最初の期間に対して、２つのトークン出力を最初に入力するように要求されることが可能である。先行する期間からのヒントも、おそらく、様々な形で、この構成と組み合わせられることが可能であり、したがって、２つのトークン出力に対する要件は、ユーザが、１つのトークン出力を使用して、十分に近時に、または十分に頻繁に認証を行っている場合、たぶん破棄される。
【００８０】
２つのトークン出力と併せて使用される変更されたレコードは、ヒントを生成するだけでよく、２つのトークン出力の即時の認証を可能にする必要はなく、これは、トークン出力の正しさが、レコードから回復された値Ｍの使用によって判定されることが可能な、前述した原理の実施例である。この場合、値Ｍが、ヒントである。２つのトークン出力から候補ヒントを回復した後、ベリファイアは、次に、そのヒントを使用して、トークン出力の片方、または両方を通常のレコードに照らして検証する。このアプローチは、変更されたレコードが、Ａ＿ｉ値を含む必要がなく、Ｅ＿ｉ値（場合により、ソルトが、やはり前述したとおり、マスタソルトから導出されない場合は、ソルトも）を含むだけでよいという利点を有する。変更されたレコードに対するそれらのＥ＿ｉ値は、２つの別々のレコードセットを設けるのではなく、単に、通常のレコードの別のフィールドとして格納することができることは明らかである。
【００８１】
本発明の別の態様では、ユーザのＰＩＮの一部分だけが、レコードを生成する際に使用されて、偽装攻撃の失敗の可能性を高めるようにし、偽装攻撃を検出する機会を提供するようにする。前述したとおり、攻撃者が、所与の時間のための認証トークンに対するセキュリティ情報を獲得することができる可能性が存在する。ユーザＰＩＮの一部分だけを使用することにより、攻撃者は、レコードから正しいＰＩＮの完全な値を獲得することができない可能性がある。後に、攻撃者は、認証サーバに対してユーザに成り済まそうと試みる可能性がある。攻撃者は、正しいＰＩＮの完全な値をまだ有さないので、認証サーバは、攻撃を検出することができる可能性がある。ＰＩＮ情報の格納を変更して、認証サーバに対するセキュリティと、ラップトップコンピュータに対するセキュリティのバランスをとることができることが理解されよう。
【００８２】
例えば、ＰＩＮが、４桁である場合、２桁だけを使用してもよい。攻撃者は、レコードの中の２桁を獲得することができるが、他の２桁は、未知のままであり、攻撃者によって推測されなければならない。一実施形態では、攻撃者は、Ｗｉｎｄｏｗｓパスワードを獲得するのに、正しいＰＩＮを推測しなければならず、例えば、パスワード自体、ＰＩＮの少なくとも一部分と結合される。これにより、攻撃者が、Ｗｉｎｄｏｗｓパスワードを獲得することがより困難になる。
【００８３】
セキュリティ上の脅威は、攻撃者が、探索に成功した後、ＰＩＮを知ることができ、次に、そのＰＩＮを使用して、保護されたサーバに対して認証を行うことができることである。無連絡にされたマシン上でＰＩＮの一部分だけを使用することによって、攻撃者は、ＰＩＮ全体を獲得することができない。ユーザは、それでも、毎回、完全なＰＩＮを入力して、同一のユーザ体験を生じさせることができるが、ＰＩＮの諸部分は、計算で使用される前に無視されることが可能であるものと理解されたい。
【００８４】
本明細書で説明する一部の実施形態は、Ｗｉｎｄｏｗｓパスワードについて述べるが、本発明は、ユーザが、ログイン手続き中に身元確認情報を提供するように要求される、他のオペレーティングシステムにも適用可能であるものと理解されたい。
【００８５】
別の実施形態では、同一の時間間隔に対する複数のレコードが格納されることが可能である。各レコードが、正しいトークン出力に対応することが可能であるが、１つのレコードだけが、正しいＰＩＮを有する。例えば、いくつかの、例えば、３つのレコードが、所与の時間間隔に対して存在し、３つのレコードのうち２つは、誤ったＰＩＮを有することが可能である。攻撃者は、正しいＰＩＮを知らず、認証サーバに対してオンライン偽装を試みる際に、３つのレコードから正しいＰＩＮを推測しようと試みる可能性がある。攻撃者は、誤った推測をする可能性が高いので、偽装攻撃が成功する可能性が小さくなる。（この場合、すべてのレコードに対して、同一の誤ったＰＩＮセットが使用され、さもなければ、攻撃者は、正しいＰＩＮを誤ったＰＩＮと区別することができる。というのは、正しいＰＩＮが、多くのレコードの中で出現するのに対して、誤ったＰＩＮは、そうではない可能性があるからである。）
様々なパラメータは、特定の応用例のニーズを満たすように、容易に変更することができるものと理解されたい。例えば、ＰＩＮサイズ、誤ったレコードの数、およびハッシュに入力されるＰＩＮの部分のサイズなどが、所望に応じて調整されることが可能である。ＰＩＮの「部分」自体、単にサブストリングではなく、ＰＩＮの任意の関数であることも可能であり、したがって、類似のＰＩＮが、異なる部分を生じさせる可能性が高く、これにより、ユーザが、タイプ入力の誤りにより、正しいＰＩＮと同一の部分を有する誤ったＰＩＮを与える可能性が小さくなる。また、値ｖａｌ＿ｉを構築する際に、例えば、排他論理和により、ＰＩＮの一部分がトークン出力と結合された場合、ＰＩＮのその部分を回復することはできない（攻撃者が、他の何らかの手段によって、出力された本物のトークンへのアクセスを得ることができないのではない限り）。（Ｗｅｉｓｓに発行された米国特許第５１６８５２０号も参照されたい。）
さらに、認証サーバは、攻撃者が、正しいセキュリティ情報（トークン出力）と、誤ったレコードの１つからの「不良」ＰＩＮ、または正しい部分を有するが、別の形で誤っているＰＩＮとを提供した場合、偽装の試みを容易に検出することができる。これは、偽装攻撃が試みられたというサイレントアラームの役割をすることが可能である。許可されたユーザが、正しいトークン出力データを、誤ったレコードの１つからのＰＩＮ、または正しい部分を有するが、それ以外で誤っているＰＩＮを不注意で提供する可能性は、極めて低いか、または極めて低くすることができるものと理解されたい。
【００８６】
さらに、認証サーバが、何らかのタイプの反則を検出した場合、サーバは一時停止し、次のトークン出力を要求することができる。これにより、次のトークン出力に対しても解決していなければならないという、さらなる負担が、攻撃者に課せられる。サーバは一時停止し、かつ／または時刻、ＩＰアドレス、発信者ＩＤ情報、前回のログインの時刻、ダウンロードされたレコードを受け取った後の旅行からの最初のログインなどを含む、様々な要因に基づき、さらなるセキュリティ情報を要求することができるものと理解されたい。つまり、サーバは、何らかのタイプの反則に基づき、エージェントをさらなる精査の対象とすることができる。さらに、サーバは、時間の１０パーセントなど、ランダムに一時停止し、かつ／またはトークン出力を要求することができる。
【実施例５】
【００８７】
ベリファイアは、各期間ｉに対して、小さいレコードセットｒｅｃ＿｛ｉｊ｝を格納する。この場合、レコードｒ＿｛ｉｊ｝は、ｊの１つの値に対して、前述した値ｒｅｃ＿ｉと等しいが、その他の値に対しては、そうではない。ｊのその他の値に対して、誤ったＰＩＮがトークン出力と結合されて、問題のレコードに対してｖａｌ＿ｉが獲得される。これは、ベリファイアが、正しいトークン出力と、１つだけが、サーバに対して認証を行うための正しいＰＩＮである、小さいセットのＰＩＮとを使用する認証の試みを受け入れることを意味する。ベリファイアは、正しいＰＩＮが使用されたか否かを判定する方法を全く有さないが、合致したレコードｒｅｃ＿｛ｉｊ｝が存在する場合にだけ、アクセスを許す。ベリファイアが、攻撃者によって壊された場合、攻撃者は、十分な計算作業を所与として、ある期間に対して値ｖａｌ＿ｉを計算することができる可能性があるが、ＰＩＮの値は知らない。したがって、攻撃者が、認証サーバに対して認証を行おうと試みることにより、将来の期間にユーザに成り済まそうと試みた場合、サーバは、小さいセットの誤ったＰＩＮの１つと併せて使用される正しいトークン出力が、サーバが壊れていることを意味すると知っているので、セキュリティ違反が検出されることが可能である。これにより、サーバが、ユーザに警報すること、ユーザのアカウントへのアクセスを制限すること、そのトークンに関連するリソースへのアクセスを制限することなどを含むことが可能な、対策をとることが可能になる。
【００８８】
以上の実施形態は、非対話型のトークンの文脈で説明した。本発明は、チャレンジ−応答プロトコルを使用するトークンに容易に拡張可能であるものと理解されたい。そのようなトークンに対して、各レコードｒｅｃ＿ｉ（またはｒｅｃ＿｛ｉｊ｝）は、トークンに送られるべきランダムなチャレンジ、ならびにそのチャレンジへの正しい応答の関数であることが可能な値Ａ＿ｉを含む。
【００８９】
本発明は、ユーザが、保護されたサーバに接続されていない部分的に保護されたマシンに対して認証を行うことを可能にするシステムを提供する。部分的に保護されているとは、攻撃者の制御下に入る可能性があるマシンを指す。認証ストリングの検証が可能であるように、この部分的に保護されたマシン（ベリファイア）は、認証ストリングが、対話の形で生成されているか、非対話の形で生成されているかに関わらず、認証ストリングの検証を可能にする何らかの情報を格納する。ベリファイアが、例えば、不正プログラム、またはコンピュータ泥棒であることが可能な攻撃者によって壊された場合、システムは、損害を限定する。詳細には、ベリファイア上に格納された情報は、攻撃者が、保護されているか、または部分的に保護されているかに関わらず、別のマシンに対してユーザに成り済ますのに成功することを可能にしない。それらの偽装攻撃が可能な限りで、それらの攻撃が実行可能である時間の長さが制限される。さらに、そのような偽装を実行しようとする試みは、大量の計算作業を要求し、偽装の試みに意味がある時間内に実行することが、不経済にされることが可能である。
【００９０】
さらに、秘密情報を抽出し、偽装の試みを実行する試みは、それが行われたことの検出をもたらすことが出来る。より詳細には、攻撃者が通信する相手のサーバは、ベリファイアの以前のセキュリティ違反の結果として、認証の試みが行われたことを検出することができ、これにより、サーバが、ユーザによるリソースへのアクセスを制限すること、または別の形で、ユーザ、およびその他の人々に問題を知らせることが可能になる。
【００９１】
一般的なセキュリティ対策として、暗号プロトコル技術において標準的な慣行であるように、異なる目的を明らかにする追加の情報を、レコードの中、および／またはハッシュ関数への入力の中に含めることが役立つ可能性がある。例えば、ユーザの名前、トークン通し番号、ベリファイアに対する識別子、および／またはバッチを提供した認証サーバの識別子を含めることができる。これは、以下に説明するいくつかの実施形態において有益である。
【００９２】
異なるユーザに対するレコードの複数のバッチを、所与のベリファイアにおいて使用することができ、かつ／または異なるトークンに対する複数のバッチを同一のユーザに対して使用することができる。また、ユーザが、異なる認証サーバに対して同一のトークンを使用する場合、各サーバが、そのトークンに対して、レコードの独自のバッチを提供することができ、あるいは異なる認証サーバが、レコードの同一のバッチを共有することが可能である。
【００９３】
前述したとおり、ベリファイアは、通常、いくらかの期間にわたって認証サーバから無連絡にされるラップトップである。しかし、より一般的な状況では、ベリファイアは、認証サーバに必ずしも接続せずに、ユーザを認証することを所望する任意のコンピュータであることが可能である。「無連絡にされた」という用語は、（ａ）ベリファイアが、認証を実行するために、認証サーバに接続されていなくてもよいこと、および（ｂ）ベリファイアが、ユーザの認証トークンの中に秘密のコピーを格納していなくてもよいことを示すものと理解されなければならない。第１の態様は、認証システムの高い利用可能性およびスケーラビリティを可能にし、第２の態様は、ベリファイアに対する攻撃の影響を限定する。
【００９４】
１名または複数名のユーザをそれぞれが検証することができる複数のベリファイアが存在するシステムを考慮することができる。各ベリファイアは、１名または複数名のユーザおよび／または１つまたは複数のトークンに対するレコードのバッチを定期的に獲得する。これにより、ベリファイアが限定された期間にわたってユーザを認証することを可能にする。ベリファイアが、ユーザのコンピュータとは異なる場合、ユーザの認証ストリングは、ベリファイアに提供され、代表的な例として、ユーザは、ユーザのコンピュータに認証ストリングを与え、このコンピュータが、次に、おそらくネットワークを介して、そのストリングをベリファイアに転送する。その意味で、ユーザのコンピュータおよびベリファイアは、ネットワークから無連絡にされないが、認証動作中に認証サーバに接続されていなくてもよいという点で、認証の意味で無連絡にされている。
【００９５】
簡明にするため、以下では、「ベリファイア」は、何らかの目的で、本明細書で説明する方法に従ってユーザを認証するデバイスであり、「ユーザのコンピュータ」は、ユーザが、ベリファイアを含む、システム内の他のコンピュータ群と対話するのに媒介にするデバイスである。以上と同様に、「認証サーバ」は、ユーザの認証トークンと秘密を共有するサーバである。
【００９６】
他の諸実施形態では、無連絡にされた認証システムは、ベリファイアが、定期的に認証サーバから直接にレコードのバッチをダウンロードするか、別の形で受け取る、「サブスクリプション」モデルを利用する。例えば、レコードのバッチは、毎日、ベリファイアに提供されることが可能である。
【００９７】
例示的なサブスクリプションモデルは、ベリファイアが、限られた期間にわたってユーザを認証することを可能にするという点で、参照により本明細書に組み込まれている、２００３年７月３１日に出願された米国特許出願第１０／６３１９８９号、Ｂ．Ｍ．ＪａｋｏｂｓｓｏｎおよびＢ．Ｓ．Ｋａｌｉｓｋｉ  Ｊｒ．、「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｇｒａｐｈ−Ｂａｓｅｄ  Ｐａｒｔｉｔｉｏｎ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｆｕｎｃｔｉｏｎａｌｉｔｙ」で説明されている。Ｊａｋｏｂｓｓｏｎ−Ｋａｌｉｓｋｉでは、ベリファイアには、中間シードが与えられ、これらのシードから、他のシード、および／またはトークン出力などの認証値が導出され、検証されることが可能である。しかし、この場合、ベリファイアには、トークン出力のハッシュ値（または、それらの値を生成することができる情報）が与えられ、ベリファイアは、それらのハッシュ値を介してユーザを認証する。Ｊａｋｏｂｓｓｏｎ−Ｋａｌｉｓｋｉにおいて中間シードを有するベリファイアは、ローカル使用のためにハッシュ値のサブセットを生成すること、および／またはそれらの値を他のベリファイアに与えることができる。
【００９８】
別の実施形態では、システムは、ベリファイアが、認証サーバに対する所与のユーザによる検証が成功して初めて、そのユーザに対するレコードのバッチを獲得する、「セッション」モデルを含む。バッチによってカバーされる期間は、通常、単一のユーザセッションの長さ、例えば、セキュリティポリシーに依存して、数分間から数時間までに相当する。ベリファイアは、セッション中、認証サーバに対するさらなる接続を要することなしに、レコードのバッチを介して、ユーザの再認証を行うことができる。
【００９９】
レコードのバッチは、サブスクリプションモデルと同様に、ユーザの認証が成功した後、認証サーバによって、１つまたは複数のベリファイアに直接に与えられることが可能である。
【０１００】
代わりに、バッチは、ユーザのコンピュータを介して、１つまたは複数のベリファイアに間接的に与えられることも可能である。認証サーバに対するユーザの認証が成功すると、バッチは、ユーザのコンピュータに提供される。次に、ユーザのコンピュータが、そのバッチをベリファイアに即時に、または後に転送することが可能である。
【０１０１】
例えばレコードのバッチは、認証サーバによって発行されるＳＡＭＬアサーションの中に含めることもできる（「Ｓｅｃｕｒｉｔｙ  Ａｓｓｅｒｔｉｏｎ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ（ＳＡＭＬ）ｖ１．１」、Ｏｒｇａｎｉｚａｔｉｏｎ  ｆｏｒ  ｔｈｅ  Ａｄｖａｎｃｅｍｅｎｔ  ｏｆ  Ｓｔｒｕｃｔｕｒｅｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｔａｎｄａｒｄｓ（ＯＡＳＩＳ）、Ａｕｇｕｓｔ  ２００３参照）。レコードは、ユーザからの「所有証明」、すなわち、ユーザが、アサーションに結び付けられた認証資格証明（この場合は、トークン）を所有しつづけているという「所有証明」をユーザから獲得する手段をベリファイアに与える。
【０１０２】
また、ベリファイアは、「委託」の形態で、互いにバッチを配布することもできる。一実施例として、アプリケーションサーバが、別のアプリケーションサーバにレコードのバッチを配布して、その別のサーバも、より高い利用可能性のためか、または独自のローカルの目的で、ユーザを認証することができるようにすることが可能である。別の実施例として、ユーザのデスクトップが、バッチのレコードをユーザのラップトップに配布することも可能である。バッチを転送することは、ベリファイアのチェーンをさらに下に行くように続くことも可能である。
【０１０３】
バッチの配布は、バッチが正しいこと、すなわち、バッチが、トークンの実際の認証ストリングと合致することを検証する何らかの手段を前提とする。さもなければ、攻撃者が、認証ストリングを知っているユーザに関連していると主張する新たなレコードセットを構築して、そのバッチを代わりにベリファイアに提供することにより、ユーザに成り済ますことができる可能性がある。したがって、メッセージ認証コード（ＭＡＣ）またはデジタル署名などのデータ認証が、含められなければならず、ただし、ＭＡＣまたはデジタル署名キーは、認証サーバ、または別の信頼される機関に関連付けられる。ベリファイアは、ＭＡＣまたはデジタル署名の正しさを検査してから、レコードのバッチを受け入れ、使用する。代わりに、認証サーバからベリファイアまでの、保護されたサーバによって認証されたチャネルを使用することもできる。
【０１０４】
各レコードが、独自のＭＡＣまたはデジタル署名を証明として有することも可能であるが、これは、計算、格納、および伝送の点でオーバーヘッドを課す可能性がある。代わりに、レコードのバッチ全体が、単一のＭＡＣまたは署名を有することも可能であるが、これは、ベリファイア間でバッチ全体の伝送を要する可能性があり、委託においてあまり細分性を提供しない。（例えば、ベリファイアが、数時間分だけのレコードを別のベリファイアに委託することを所望するが、バッチ自体は、１日全体にわたることが可能である可能性がある。このより詳細なアプローチの１つの利点は、このアプローチが、レコードの開示を制限し、これにより、攻撃者が、トークン出力の探索を開始するレコードを獲得する機会が少なくなることである。）
個々のレコードに署名することと、バッチ全体に署名することの中間の妥協案として、様々なハッシュタイプの構成体を有益に適用することができる。例えば、各レコードが、ハッシュツリーのリーフとして扱われることが可能である。リーフは、標準の技術によってハッシュツリーに組み立てられ、署名またはＭＡＣが、そのツリーのルートに適用される。このようにすると、リーフ（すなわち、レコード）の任意のサブセットが、そのサブセットからルートまでのパス、および単一のＭＡＣまたは署名と一緒に、ベリファイアの間で交換されることが可能である。リーフのコンテンツ、各レベルにおける子の数、およびツリーの中のレベルの数は、標準の技術においてよく理解されているとおり、様々であることが可能である。実施例として、１時間分のレコードが、１つのリーフにまとめられて、２４のリーフが一緒にハッシュ化されて、１日のルートが形成され、このルートに署名が行われることも可能である。これは、１時間単位の細分性をもたらし、この細分性で、多くの応用例には十分である可能性がある。
【０１０５】
また、別々のベリファイアが関わるアプローチは、Ｂ．ＫａｌｉｓｋｉおよびＭ．Ｎｙｓｔｒｏｍ、「Ｐａｓｓｗｏｒｄ  Ｐｒｏｔｅｃｔｉｏｎ  Ｍｏｄｕｌｅ」（米国特許仮出願第６０／５９１６７２号を有する、２００４年７月２８日に出願された特許仮出願）、および、やはり「Ｐａｓｓｗｏｒｄ  Ｐｒｏｔｅｃｔｉｏｎ  Ｍｏｄｕｌｅ」という名称のＢ．ＫａｌｉｓｋｉおよびＭ．Ｎｙｓｔｒｏｍ（参照により本明細書に組み込まれている、米国特許仮出願第６０／５８４９９７号を有する、２００４年７月２日に出願された特許仮出願）におけるパスワード−ハッシュアプローチと両立することにも留意されたい。パスワード（または、より一般には、認証ストリング）は、アプリケーション識別子とハッシュ化されて、保護されたパスワードが生成され、このパスワードが、次に、アプリケーションに与えられる。（アプリケーション識別子は、アプリケーションセットの所与のアプリケーションに固有のストリング、例えば、そのアプリケーションのネットワークアドレス、ＵＲＬ、またはドメイン名である。）
ハッシュ化ステップは、壊れたアプリケーションが、パスワードを直接に受け取り、次いで、そのパスワードを、正当なアプリケーションに転送することができるのを防止する。以上に示唆したとおり、複数のベリファイアが関わる場合、保護されたパスワード（すなわち、保護された認証ストリング）をベリファイアに提供することが好ましい可能性がある。これにより、壊れたベリファイアが、獲得された情報を濫用して、他のベリファイアに対してユーザに成り済ますことも同様に防止される。したがって、提供されるレコードは、ベリファイアごとに異なる。というのは、レコードは、保護された認証ストリングに基づき、このストリングは、アプリケーション識別子およびトークン出力に依存するからである。
【０１０６】
Ｋａｌｉｓｋｉ−Ｎｙｓｔｒｏｍで示唆される確認コードは、レコードを介して、保護されたセンシティブなデータの一部として容易に受け入れることができる。これにより、レコードを獲得した攻撃者が、認証ストリングを知ることなしに、ベリファイアに成り済ますことができることが防止される。
【０１０７】
本明細書で説明する無連絡認証アプローチは、このアプローチがサポートする認証アーキテクチャの点で、特に柔軟性がある。無連絡にされたマシンに対する認証自体、トークン出力を使用するが、認証の成功が達せられた後、他のアプリケーションに対する認証の目的で使用することができるキー、または他のセンシティブなデータが回復されることが可能である。例えば、ＳＳＬ／ＴＬＳ（Ｔ．ＤｉｅｒｋｓおよびＣ．Ａｌｌｅｎ、「Ｔｈｅ  ＴＬＳ  Ｐｒｏｔｏｃｏｌ  Ｖｅｒｓｉｏｎ  １．０」、ＩＥＴＦ  ＲＦＣ２２４６、Ｊａｎｕａｒｙ  １９９９）として、またはＳＡＭＬアサーションに対する「所有証明」などの標準公開キーベースの認証プロトコルにおいて使用することができるプライベート署名キーが、回復されることが可能である。このため、ユーザは、１回限りのパスコード認証トークンだけを所有しながら、他のアプローチと比べて、無連絡にされたマシン上でプライベート署名キーが漏洩する危険が低く、標準の公開キーベースの技術を使用して、アプリケーションに対して認証を行うことができる。（これに対して、他のアプローチでは、ユーザは、認証トークンを介して、資格証明サーバに対して認証を行い、次いで、署名プライベートキーをダウンロードすることが可能であり、このキーが、次に、ユーザのコンピュータ上に暗号化されずに格納される。本明細書のアプローチは、プライベートキーが、トークン出力から導出された値を使用して暗号化され、したがって、ユーザのコンピュータ上のデータへのアクセスを得る攻撃者が、プライベートキーを容易に回復することができないという点で、有利である。）
プライベートキーが、他のアプリケーションに対する認証のために使用されるケースでは、レコード当たり単一のプライベートキーが存在すること、レコードのバッチ当たり単一のプライベートキーが存在すること、またはどこかその中間であることが可能である。対応する公開キーが、アプリケーションに利用可能にされる必要があるので、バッチ当たり１つのプライベートキーを使用する（そのため、バッチ当たり単一の公開キーを使用する）アプローチが、多くの署名スキームに対するキー管理の点で利点を有する可能性がある。しかし、一部の署名スキームは、レコード当たり単一のプライベートキーが存在するが、それでも、バッチ当たり１つの公開キーだけしか存在しないという特性を有する。
【０１０８】
一実施例として、Ｍ．Ｗｉｅｎｅｒ編、「Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−Ｃｒｙｐｔｏ’９９  Ｐｒｏｃｅｅｄｉｎｇｓ，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ｖｏｌ．１６６６，Ｓｐｒｉｎｇｅｒ，１９９９」に所収のＭ．ＢｅｌｌａｒｅおよびＳ．Ｍｉｎｅｒ、「Ａ  Ｆｏｒｗａｒｄ−Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ」におけるような、フォワードセキュア署名スキームは、１つの公開キーと、プライベートキーの連続とを有し、ただし、より後のプライベートキーは、より前のプライベートキーから計算されることが可能であるが、その逆は可能ではない。（ベリファイアは、可能なプライベートキーの連続の中で使用されるプライベートキーの位置を特定することができる。）これは、攻撃者が、後の時点で漏洩したプライベートキーを所与として、より古い署名であるように見えるものを偽造することが防止されるという点で、有益である。この場合、様々なプライベートキーが、バッチ全体に対して事前計算され、次いで、連続的なレコードで保護されることが可能である。ここで、通常のフォワードセキュアシーケンスと比べて、プライベートキーの順序を逆にして、所与の時間間隔に対してプライベートキーを漏洩させた攻撃者が、より前の時間間隔に対するプライベートキーだけしか計算できないようにすることが好ましい。後の時間間隔に対するセンシティブなデータが、前述したとおり、より前の時間間隔に対するデータよりも強力な保護を有するものと想定すると、このアプローチは、プライベートキーに対して上手な２レベルの防御を提供する。
【０１０９】
また、Ｍｅｒｋｌｅ署名スキームまたはハッシュツリー署名スキーム（Ｒ．Ｍｅｒｋｌｅ、「Ｓｅｃｕｒｉｔｙ，Ａｕｔｈｅｎｔｉｃａｔｉｏｎ，ａｎｄ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｓｙｓｔｅｍｓ」、Ｐｈ．Ｄ．ｄｉｓｓｅｒｔａｔｉｏｎ、Ｄｅｐｔ．ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｔａｎｆｏｒｄ  Ｕｎｉｖ．、１９７９参照、また、Ｍ．Ｊｏｙｅ編、「Ｔｏｐｉｃｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＴ−ＲＳＡ  ２００３  Ｐｒｏｃｅｅｄｉｎｇｓ，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ｖｏｌ．２６１２，Ｓｐｒｉｎｇｅｒ，２００３」に所収のＭ．Ｊａｋｏｂｓｓｏｎ、Ｆ．Ｔ．Ｌｅｉｇｈｔｏｎ、Ｓ．Ｍｉｃａｌｉ、およびＭ．Ｓｚｙｄｌｏ、「Ｆｒａｃｔａｌ  Ｍｅｒｋｌｅ  Ｔｒｅｅ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ａｎｄ  Ｔｒａｖｅｒｓａｌ」も参照）も、この場合、有益に使用することができる。というのは、このスキームも、例えば、各レコードに対して、相異なる署名操作のために、単一の公開キー（ルート）、ただし、異なるプライベートキー（リーフの集合）を有するからである。このスキームは、フォワードセキュアであるとともに、バックワードセキュアでもあり、つまり、単一のプライベートキーの漏洩により、いずれの方向でも、他のいずれのプライベートキーの計算も可能になることはない。
【０１１０】
他の多くの認証プロトコルをサポートすることができる。例えば、共有される対称キーが、アプリケーションに対して認証を行う目的で回復されることが可能である。共有されるキーは、例えば、Ｋｅｒｂｅｒｏｓ認証システムにおけるキーであることも可能である。別の実施例として、セッション状態が回復され、その状態から、ＳＳＬ／ＴＬＳセッションを再開することが可能である。代わりに、回復されるセンシティブなデータは、「仮想」認証トークンまたは「ソフト」認証トークンのためのシードであり、次に、そのトークンの出力を使用して、他のアプリケーションを認証することも可能である。別の実施例として、異なるトークンに対するトークン出力が回復可能である。さらに、センシティブなデータは、ハッシュ関数への入力から成ることが可能であり、ただし、ハッシュ関数の出力は、別のアプリケーションが入手することができ、入力は、そのアプリケーションに対する認証の証明として提供される。
【０１１１】
別の実施例として、Ｂ＿ｉ値自体が、レコードをやはり共有する別のベリファイア、例えば、Ｗｉｎｄｏｗｓドメインコントローラに対する「認証の証明」の役割をすることが可能である。ユーザのコンピュータは、所与のトークン出力から獲得されたＢ＿ｉ値を、別のベリファイアに提示し、その別のベリファイアは、Ｂ＿ｉ値により、Ｅ＿ｉ値のコピーが、正しく解読されるかどうかを判定する。
【０１１２】
認証プロトコルにおいて使用するためのセンシティブなデータのさらなる実施例は、ユーザの認証の証明として他のアプリケーションに提示されることが可能な、ＳＡＭＬアサーション、または他の署名された値である。１つまたは複数のＳＡＭＬアサーションが、認証サーバによって提供され、異なる時間間隔に対して暗号化されることが可能である。ベリファイアにおける認証の成功により、そのようなアサーションが回復され、このアサーションが、それらの他のアプリケーションに与えられる。これにより、一連の事前計算されたアサーションが、ベリファイアにおいて、認証サーバと対話することなしに、容易に獲得される、「自己発行」能力がベリファイアに与えられる。したがって、アサーションは、より短い存続期間を有することが出来、そのため、認証サーバによって通常に発行されるアサーションよりも「フレッシュ」である一方で、比較的長いセッションが維持される。（例えば、レコードセットが、ベリファイアによって認証サーバから毎日、ダウンロードされて、１時間だけの存続時間を有するアサーションが保護されることが可能である。ユーザは、１日に１回だけ、認証サーバと対話すればよく、フレッシュなアサーションを獲得するのに、１時間に１回、ベリファイアに対して認証を行う必要がある。）
Ｂ．Ｓ．Ｋａｌｉｓｋｉ  Ｊｒ．、「Ｃｌｉｎｅｔ／Ｓｅｒｖｅｒ  Ｐｒｏｔｏｃｏｌ  ｆｏｒ  Ｐｒｏｖｉｎｇ  Ａｕｔｈｅｎｔｉｃｉｔｙ」、米国特許第６０８５３２０号および米国特許第６１８９０９８号における技術に従うと、ＳＡＭＬアサーション全体を暗号化する必要はない。代わりに、アサーション上の署名、あるいは、ハッシュ関数の出力が、アサーションの一部である場合、ハッシュ関数への入力などの、アサーションを検証するのに必要な情報を暗号化するだけで十分とすることが出来る。
【０１１３】
本発明のさらなる特徴および利点は、以上に説明した諸実施形態に基づき、当業者には理解されよう。したがって、本発明は、添付の特許請求の範囲で示す場合を除き、特に示し、説明した事物によって限定されないものとする。本明細書で引用した、すべての刊行物および参照文献は、参照により全体が本明細書に明確に組み込まれている。
【図面の簡単な説明】
【０１１４】
【図１】本発明による無連絡認証を提供するシステムを示すブロック図である。
【図２】本発明による無連絡認証を提供するようにダウンロードされることが可能な、例示的な時間ベースの情報を示す図である。
【図３】本発明による無連絡認証の典型的なコンポーネントを示すブロック図である。
【図４】本発明による無連絡認証の一部分を形成することが可能な、例示的なレコード示すテキストである。
【図５】本発明による無連絡認証のさらなる特徴を示す図である。
【図６】本発明による無連絡認証のさらなる特徴を示すグラフである。
【図１】
0005451785.tif 000002
【図２】
0005451785.tif 000003
【図３】
0005451785.tif 000004
【図４】
0005451785.tif 000005
【図５】
0005451785.tif 000006
【図６】
0005451785.tif 000007