(57)【要約】      （修正有）【課題】ユーザの階層のためのパスワードを生成する方法を提供する。【解決手段】アクセス制御デバイスの階層にアクセスするユーザのためのパスワードの階層を管理する。最初に、１つのコードワードが取得され、そのコードワードのシンドロームが求められる。次に、そのコードワードが確率ｐでランダムに変更され、変更済みコードワードが生成される。変更済みコードワードが復元可能である場合には、その変更済みコードワードがパスワードとして選択され、ユーザに割り当てられる。【選択図】図１
2010170521.tif 000002
【特許請求の範囲】
【請求項１】
パスワードの階層を管理する方法であって、前記方法の複数のステップを実行するプロセッサを含み、前記複数のステップは、
コードワードを取得すること、
前記コードワードをランダムに変更することにより、変更済みコードワードを生成すること、
前記変更済みコードワードが復元可能である場合には、該変更済みコードワードをパスワードとして選択すること、並びに、そうでない場合には、前記変更すること及び前記選択するステップを繰り返すこと、
前記パスワードをユーザに割り当てること
からなる、方法。
【請求項２】
前記コードワードのシンドロームを求めること、及び
前記コードワードの暗号ハッシュ及び前記シンドロームをアクセス制御デバイスに格納すること
をさらに含む、請求項１に記載の方法。
【請求項３】
前記パスワードをユーザデバイスに格納すること
をさらに含む、請求項１に記載の方法。
【請求項４】
前記変更済みコードワード及び前記シンドロームを入力として有する誤り訂正関数の実行の結果が前記コードワードに等しい場合には、前記変更済みコードワードは復元可能である、請求項２に記載の方法。
【請求項５】
前記パスワード及び前記シンドロームから候補コードワードを復元すること、並びに
前記候補コードワードの暗号ハッシュが前記コードワードの前記暗号ハッシュに等しい場合には、前記ユーザが前記アクセス制御デバイスにアクセスするのを許可すること
をさらに含む、請求項２に記載の方法。
【請求項６】
第２のユーザを前記ユーザに関連付けること、
前記パスワード及び前記シンドロームに基づいて前記コードワードを求めること、
前記コードワードを第１の確率でランダムに変更することにより、第２の変更済みコードワードを生成すること、
前記第２の変更済みコードワードの第２のシンドロームを求めること、
前記第２のシンドローム及び前記第２の変更済みコードワードの暗号ハッシュを第２のアクセス制御デバイスに格納すること、
前記第２の変更済みコードワードを第２の確率でランダムに変更することにより、第２のパスワードを生成すること、並びに
前記第２のパスワードを前記第２のユーザに割り当てること
をさらに含む、請求項２に記載の方法。
【請求項７】
前記第２のパスワードを第２のユーザデバイスに格納することをさらに含む、請求項６に記載の方法。
【請求項８】
前記ユーザにデジタル署名を割り当てることをさらに含む、請求項１に記載の方法。
【請求項９】
前記デジタル署名が前記パスワードと一致する場合には、前記ユーザが前記アクセス制御デバイスにアクセスするのを許可することをさらに含む、請求項８に記載の方法。
【請求項１０】
前記第２のパスワード及び前記第２のシンドロームから第２の候補コードワードを復元すること、並びに
前記第２の候補コードワードの暗号ハッシュが前記第２の変更済みコードワードの前記暗号ハッシュに等しい場合には、前記ユーザが前記第２のアクセス制御デバイスにアクセスするのを許可すること
をさらに含む、請求項６に記載の方法。
【請求項１１】
前記コードワードをランダムに変更することのために、乱数発生器のためのシードを割り当てること、及び
前記第２の変更済みコードワードをランダムに変更することのために、前記乱数発生器のための第２のシードを割り当てること
をさらに含む、請求項６に記載の方法。
【請求項１２】
乱数発生器のためのシードを用いて前記パスワードを変更することにより、変更済みパスワードを生成すること、
前記変更済みパスワード及び前記シンドロームから候補コードワードを復元すること、並びに
前記候補コードワードの暗号ハッシュが前記第２の変更済みコードワードの前記暗号ハッシュに等しい場合には、前記ユーザが前記第２のアクセス制御デバイスにアクセスするのを許可すること
をさらに含む、請求項６に記載の方法。
【請求項１３】
前記ユーザに１組のシードを割り当てること
をさらに含み、
前記１組のシードは、パスワードの階層を生成して、前記ユーザがアクセス制御デバイスの階層にアクセスすることができるようにするために、前記コードワードを変更するのに適している、請求項１に記載の方法。
【請求項１４】
前記１組のシードのうちの最初のｌ個のシードを用いて、前記パスワードをｌ回変更することにより、ｌレベルパスワードを生成すること、
前記ｌレベルパスワード及びｌレベルシンドロームからｌレベル候補コードワードを復元することであって、該ｌレベルシンドロームはｌレベルアクセス制御デバイスに関連付けられること、並びに
前記ｌレベル候補コードワードの暗号ハッシュが前記ｌレベルアクセス制御デバイスに関連付けられるｌレベルコードワードの暗号ハッシュに等しい場合には、前記ユーザが前記ｌレベルアクセス制御デバイスにアクセスするのを許可すること
をさらに含む、請求項１３に記載の方法。
【請求項１５】
パスワードのブラックリストを前記アクセス制御デバイスに関連付けることをさらに含み、
前記ブラックリスト内の各パスワードは前記アクセス制御デバイスへのアクセスを拒否される、請求項６に記載の方法。
【請求項１６】
アクセス制御デバイスの階層にアクセスするユーザのためのパスワードの階層を管理するシステムであって、
アクセス制御デバイスを備え、
前記デバイスは認証情報にアクセスすることができ、
前記認証情報は、
コードワードの暗号ハッシュと、
シンドロームと
を含み、ユーザのパスワード及び該シンドロームを入力として有する誤り訂正関数の実行の結果の暗号ハッシュが前記コードワードの前記暗号ハッシュに等しい場合には、前記ユーザに対して前記アクセス制御デバイスへのアクセスが許可されるように、前記シンドローム及び前記コードワードの前記暗号ハッシュは前記ユーザの前記パスワードを認証するのに適している、システム。
【請求項１７】
前記認証情報は、無効なパスワードのブラックリストを含む、請求項１６に記載のシステム。
【請求項１８】
前記認証情報は、前記ユーザのデジタル署名を認証するための公開鍵を含む、請求項１６に記載のシステム。
【請求項１９】
前記システムは、前記ユーザに関連付けられるユーザデバイスをさらに備え、
前記ユーザデバイスは該ユーザの前記パスワード及び該ユーザの前記デジタル署名を格納する、請求項１８に記載のシステム。
【請求項２０】
前記ユーザデバイスは、前記ユーザの前記パスワードを変更するための１組のシードにアクセスすることができ、前記ユーザが１組の低レベルのデバイスにアクセスするための１組のパスワードを生成する、請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはパスワードを生成する方法に関し、より詳細には、ユーザの階層のためのパスワードを生成する方法に関する。
【背景技術】
【０００２】
脆弱な電子情報に対する無許可のアクセスを拒否する必要がある。計算及び通信システムは経済活動のあらゆる領域において見受けられ、家庭及び他の場所においてもますます見受けられるようになっている。コンピュータを基にするシステムの利用可能性が広がり、その使用が進むにつれて、それらのシステムの相互接続も進む。その結果が、情報、計算及び通信の共用インフラストラクチャである。共有インフラストラクチャの性質は、ユーザにとっての脆弱性をもたらす。一般的に、ユーザにとってアクセスがより容易であることは、無許可のユーザによるアクセスがより容易であることを暗示する。特定のタイプの情報脆弱性に対処する際に、暗号法が重要な役割を果たす。
【０００３】
従来の暗号法は、暗号化過程及び秘密鍵を用いることによってデータを保護する。暗号化は、その鍵を用いて、平文を暗号文に変換する。異なる鍵を用いる結果として、異なる暗号文が作成される。復号化は、暗号文を変換して、平文に戻す。暗号化演算及び復号化演算が同じ鍵を用いるとき、その方法は、対称鍵暗号法として知られている。非対称鍵暗号法では、暗号化鍵と復号化鍵とが異なる。通常、これらの鍵のうちの一方は公に入手可能であるように作成され、他方の鍵は、許可を受けた関係者によって非公開で保持される。或るシステムのユーザに対して割り当てられるパスワードは、このユーザがそのシステムの特定の機能にアクセスすることができるようにする秘密鍵と見なすことができる。鍵及びパスワードを生成する方法、並びにその鍵及びパスワードを配布する方法は、「鍵管理」という広い名称の下に包括される。
【０００４】
多くの場合にアクセス制御方式を実施する必要があり、それによれば、データへのアクセスを承認するか、又は拒否するかの判断は、クラスの階層内のユーザの位置による。たとえば、ユーザは３つのクラス、Ａ、Ｂ及びＣに区分される。クラスＡは最も高い特権を有し、クラスＣは最も低い特権を有する。したがって、最もセキュリティの高いデバイスは、クラスＡのユーザに対してのみアクセスを許可する。中間のセキュリティのデバイスは、クラスＡ及びＢのユーザに対してアクセスを許可し、一方、セキュリティの低いデバイスは、全てのユーザに対してアクセスを許可する。このアーキテクチャは、４つ以上のクラスに拡張することができ、それらのクラスは数多くの実現可能な階層のうちの１つにおいて配置され、クラスの特権は階層内のそのクラスの位置による。特定の特権クラス内に多数のユーザが存在することができる。
【０００５】
そのような階層は、数多くの実用的なアクセス制御の用途において生じる。たとえば、工場において、或るエリアは、機械工場労働者の立ち入りを禁止することができ、資格のある監督者だけが出入りすることができる。別の例では、銀行の顧客サービス担当者は、顧客の公開情報にアクセスすることができ、一方、その上司は、さらに機密の詳細にアクセスすることができる。階層的パスワード方式は、階層内のユーザの位置に応じて、すなわち、ユーザの特権クラスに応じて、各ユーザに鍵又はパスワードを生成する方法と定義される。
【０００６】
セキュリティシステムにおいて鍵又はパスワード管理は重要である。鍵管理は、鍵の生成、配布及び破棄を含む。さらに、数多くの用途において、ユーザの複数のサブセットが異なるアクセス権を有するような、階層的なアクセス構造が必要とされる。
【０００７】
パスワードの階層を生成するための数多くの異なる構成が知られている。しかしながら、取り組まれていないままであるいくつかの重要な課題がある。第１の課題は、セキュリティシステムはネットワーク化され得ること、すなわちネットワーク接続を介して、新たなユーザを追加するか、又はユーザを取り消す動作を都合良く実行することができるように、全てのアクセス制御デバイスが中央管理デバイスに接続されることである。ネットワーク化が利用可能でないか、又はネットワーク化が可能でない場合には、アクセス制御デバイスのデータベース内に格納されているユーザ情報を手作業で変更することが大きな負担になる。第２の課題は、大部分の従来のパスワード方式では、各アクセス制御デバイスが、種々の認証情報、たとえば、そのデバイスに合法的にアクセスすることが許される全てのユーザのための暗号ハッシュ又は鍵を格納することである。これは、メモリ要件の点で効率的でない場合がある。
【０００８】
セキュリティシステム内のアクセス制御デバイスを更新する必要性を低減するか、又はその更新を完全に排除しながら、パスワードを生成することができる方法を提供することが望ましい。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、ユーザの階層のためのパスワードを生成する方法を提供することである。
【００１０】
本発明のさらに別の目的は、ユーザの階層が更新されるときに、アクセス制御デバイスを更新する必要性を排除する方法を提供することである。
【００１１】
本発明のさらに別の目的は、アクセス制御デバイスにおいて単一の暗号ハッシュ及び補助情報を用いて、多数のユーザの認証を可能にするのに適している方法を提供することである。
【課題を解決するための手段】
【００１２】
本発明は、復元可能でランダムに変更されるコードワードをパスワードとして用いることができるという認識に基づく。
【００１３】
本発明の複数の実施の形態が、ユーザの任意の階層のためのパスワードを生成する方法を提供する。その認証過程は、誤り訂正符号（ＥＣＣ）に基づいており、それによって、単一の暗号及びＥＣＣの単一のシンドロームを用いて、多数のパスワードを認証することができるようになる。
【００１４】
記憶要件を低減することに加えて、その方法は、アクセス制御デバイス上に格納されている情報を更新することなく、新たなユーザを登録することも可能にする。格納された情報しか与えられないものとすると、攻撃者にとって任意のユーザのパスワードを推測することは難しい。さらに、他のユーザに成りすますために正規のユーザが自身のパスワードを操作しないことを確実にするために、デジタル署名が用いられる。また、その方法は、システム管理者が、パスワードのうちの漏洩している可能性がある部分を取り消すことも可能にする。
【発明の効果】
【００１５】
本発明の実施の形態は、誤り訂正符号化及び暗号ハッシュの組み合わせを用いて、ユーザの任意の階層のためのパスワードを生成する。その方法は、暗号ハッシュだけに基づく従来の認証方式に対して複数の利点を有する。これらの利点は、アクセス制御デバイスを更新することなく、複数の新たなユーザを容易に登録すること、及びアクセス制御デバイス上の記憶要件が大幅に低減されることを含む。
【００１６】
その方法は、多数のアクセス制御の用途のために用いることができる。たとえば、例えば用途として次のものが挙げられる：異なる特権を有するユーザアカウントを介する、大企業又は銀行内のソフトウエアデータベースへのアクセス制御；スマートカードリーダを介する、工場の物理的な場所へのアクセス制御；セキュリティの目的から、建物の選択された部分への階層的アクセスを提供すること；ソフトウエアで、使用権を認められたユーザがツールボックスの許された部分だけにアクセスすることを可能にする鍵を提供すること；テレビゲーム又はコンピュータゲームで、使用権を認められたユーザがゲームレベルの許された部分だけにアクセスすることを可能にする鍵を提供すること。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施の形態に従って生成されるセキュリティ情報を用いるパスワード認証の方法及びシステムの流れ図である。
【図２Ａ】本発明の実施の形態による、認証情報を計算する方法のブロック図である。
【図２Ｂ】本発明の実施の形態による、認証情報を計算する方法のブロック図である。
【図３】本発明の実施の形態による、ユーザ及びアクセス制御デバイスの階層の一例の図である。
【図４】本発明の実施の形態による、パスワードを生成し、割り当てる方法のブロック図である。
【図５】本発明の実施の形態による、図３に示される階層例の場合の図４の方法の一例の流れ図である。
【図６】本発明の実施の形態による、ユーザで格納される認証情報及びアクセス制御デバイス上に格納される認証情報の概略図である。
【図７】本発明の実施の形態による、パスワード認証の方法のブロック図である。
【発明を実施するための形態】
【００１８】
図１は、本発明の実施の形態に従って生成されるセキュリティ情報を用いるパスワード認証の方法及びシステム１００を示す。ユーザｕのための認証情報、たとえば、パスワードＹ［ｕ］１１５が、ユーザデバイス１１０上に格納される。そのパスワードは、アクセス制御デバイスＤ１２０にアクセスするために用いられる。スマートカードが、ユーザデバイス１１０の一例である。他のデバイスは、移動端末、ハンドヘルドプロセッサ等を含む。
【００１９】
アクセス制御デバイス１２０は、無許可のアクセスからの保護を必要とする任意の資源であり、たとえば、安全化された部屋のドア、データベース又はドキュメントにアクセスする特権である。
【００２０】
アクセス制御デバイス１２０へのアクセスは、コードワード、たとえば、長さＮのバイナリコードワード
【００２１】
【数１】
2010170521.tif 000003
【００２２】
で保護される。しかしながら、そのコードワードは、デバイス１２０において格納される必要はない。代わりに、本発明の一実施の形態では、コードワードＣ［Ｄ］の暗号ハッシュｈ（Ｃ［Ｄ］）１２５、及び線形誤り訂正符号（ＥＣＣ）又はシンドロームＳ［Ｄ］１２６だけが、アクセス制御デバイス１２０に関連付けられるメモリ１３０内に格納される。ＥＣＣは、パリティチェック行列Ｈ６７０によって表すことができる。図６を参照されたい。パリティチェック行列は、Ｋ行及びＮ列の０及び１から成る行列である。パリティチェック行列のＮ列は、ＥＣＣのＮ個のシンボルに対応し、Ｋは、ＥＣＣが満たさなければならない制約の数を表す。
【００２３】
パリティチェック行列を用いて、Ｋ個の方程式及びＮ個の未知数の系を形成することができる。バイナリパリティチェック行列は
【００２４】
【数２】
2010170521.tif 000004
【００２５】
であり、関係Ｓ［Ｄ］＝Ｃ［Ｄ］ＨＴを用いてシンドロームを計算する。ただし、Ｋ＜Ｎであり、ＨＴは行列Ｈの転置を表す。たとえば、Ｋ＝３、Ｎ＝７の場合には、取り得るパリティチェック行列は以下の通りである。
【００２６】
【数３】
2010170521.tif 000005
【００２７】
Ｃ［Ｄ］＝［１０１１０００］であると仮定すると、以下の式が成り立つ。
【００２８】
【数４】
2010170521.tif 000006
【００２９】
Ｋ＜Ｎであるため、その方程式系は劣決定であり、すなわちシンドロームＳ［Ｄ］しか分からないとき、コードワードＣ［Ｄ］を求めることは不可能である。
【００３０】
パスワード認証方法１００は、シンドロームＳ［Ｄ］１２６を用いてパスワードＹ［ｕ］１１５のための誤り訂正関数ｇ（Ｙ［ｕ］，Ｓ［Ｄ］）１４０によって生成される候補コードワードのハッシュ１５５を求める（１５０）。これは、その方法が、格納されたシンドロームＳ［Ｄ］及びパスワードＹ［ｕ］の両方を用いて候補コードワードを求めることを意味する。候補コードワードのハッシュ１５５がデバイス１２０において格納されるハッシュ１２５と一致する（１６０）場合には、アクセス制御デバイス１２０へのアクセスが許可される。一実施の形態では、確率伝搬復号化法によって、候補コードワード］を求める。しかしながら、任意の他の誤り訂正復号化技法を用いることができる。
【００３１】
パスワード生成のための誤り訂正符号
Ｕ１、Ｕ２、．．．、ＵＴをデバイスＤへのアクセスを要求するユーザであるとする。従来の暗号技術に基づくパスワード方式では、システム管理者が各ユーザにパスワードを割り当て、そのパスワードの暗号ハッシュをアクセス制御デバイスに格納する。したがって、Ｔ人のユーザがＴ個のハッシュの格納を要求する。さらに、新たなユーザが追加されることになる場合には、そのデバイス上に新たなハッシュが格納されなければならない。
【００３２】
本発明の実施の形態は、Ｔ人のユーザが複数の異なるパスワード１１５を割り当てられ、そのパスワード全てを、適当なＥＣＣから計算される単一のシンドロームＳ［Ｄ］１２６、すなわち誤り指示子を用いて認証することができる方法を提供する。
【００３３】
図２Ａ及び図２Ｂは、本発明の実施の形態による、セキュリティ情報を計算する方法のブロック図である。図２Ａは、アクセス制御デバイス上に格納されることになるセキュリティ情報、すなわちシンドローム１２６及びハッシュ１２５を如何に求めるかを示す。図２Ｂは、ユーザデバイス１１０上に格納されることになるセキュリティ情報、すなわちパスワード１１０を如何に求めるかを示す。
【００３４】
アクセス制御デバイスＤ１２０の場合、長さＮのバイナリコードワードＣ［Ｄ］２１０を生成する。コードワードＣ［Ｄ］のビットは独立同分布（ｉ．ｉ．ｄ．）のベルヌーイ数であり、各ビットは０又は１であり、その確率ｂは等しく、すなわちｂ＝０．５である。したがって、任意の１つのビットの値がわかっても、任意の他のビットの値を推定する助けにはならない。パラメータｂを有するベルヌーイ数Ｘは、Ｘが０又は１のいずれかであり、その数は、ｂの確率で１であることを意味する。コードワードＣ［Ｄ］２１０の暗号ハッシュｈ（Ｃ［Ｄ］）１２５が求められ（２５０）、アクセス制御デバイス１２０に格納される。
【００３５】
このハッシュは、ＭＤ５、ＳＨＡ−１、ＳＨＡ−２のような任意の従来の暗号化技法を用いて求めることができ、ＭＤ５、すなわちメッセージダイジェストアルゴリズム５及びＳＨＡ、すなわちセキュアハッシュアルゴリズムは、既知の暗号ハッシュ関数の例である。さらに、本発明のＥＣＣは、バイナリパリティチェック行列Ｈを用いて、Ｓ［Ｄ］＝Ｃ［Ｄ］ＨＴのようなシンドロームＳ［Ｄ］１２６を求める（２６０）。また、シンドロームＳ［Ｄ］１２６はアクセス制御デバイス１２０に格納される。
【００３６】
本発明の実施の形態は、復元可能で、ランダムに変更されるコードワードをユーザのパスワードとして用いることができるという認識に基づく。任意のユーザＵｉ（ｉ＝１、２、．．．、Ｔ）のためのパスワードを見つけるために、図２Ｂに示されるように、交差確率ｐを有するバイナリ対称チャネル（ＢＳＣ）の中にコードワードＣ［Ｄ］２１０を通す（２２０）ことによって、コードワードをランダムに変更する。交差確率ｐを有するＢＳＣを、「ＢＳＣ−ｐ」によって示す。この過程は、確率ｐでコードワードＣ［Ｄ］２１０のビットをランダムに反転して、変更されたコードワードＸ［Ｕｉ，Ｄ］２３０を生成する。ビット反転の確率ｐは、シンドロームＳ［Ｄ］が与えられるときに、Ｘ［Ｕｉ，Ｄ］からコードワードＣ［Ｄ］を常に復元することができるように、すなわち、以下の式が成り立つように選択される。
【００３７】
【数５】
2010170521.tif 000007
【００３８】
ただし、関数ｇは、誤り訂正符号のための任意の復号化方法、たとえば、確率伝搬復号化とすることができる。
【００３９】
変更されたコードワードが復元可能である場合には、変更されたコードワードＸ［Ｕｉ，Ｄ］をユーザＵｉのためのパスワードＹ［Ｕｉ］１１５として選択し、そのパスワードをユーザデバイス１１０に割り当てる。上記のように、一実施の形態では、入力として、変更されたコードワード及びシンドロームを有する誤り訂正関数を実行した結果がコードワードに等しい場合には、変更されたコードワードを復元可能として選択する。変更されたコードワードが復元可能でない場合には、その方法の変更するステップ及び選択するステップを繰り返す。
【００４０】
ここで、ＢＳＣ−ｐの異なる実現形態に基づいて、異なるユーザＵｉに異なるパスワードを割り当てることができる。システム管理者は、ＢＳＣの実現値が異なることを検証することができ、式（１）が全てのＵｉの場合に成り立つことも検証することができる。或るＵｉの場合に、その関係が成り立たない場合には、その関係が成り立つＢＳＣ−ｐの別の実現形態を作り出すことは簡単なことである。
【００４１】
ＢＳＣ−ｐの異なる実現形態は、異なるユーザが異なるパスワードを割り当てられるのを確実にする。式（１）を検証することによって、正規のユーザがシステムにアクセスすることができることが保証される。Ｘ［Ｕｉ，Ｄ］は変更されたコードワードであるので、Ｘ［Ｕｉ，Ｄ］は必ずしもＣ［Ｄ］に復号化されるとは限らない。すなわち、変更されたコードワードは式（１）を満たさない。この場合、式（１）が満たされるまで、Ｘ［Ｕｉ，Ｄ］を生成し続け、その後、パスワードとして最新のＸ［Ｕｉ，Ｄ］を割り当てる。
【００４２】
コードワードＣ［Ｄ］はユーザデバイス上に格納される必要はなく、暗号ハッシュｈ（Ｃ［Ｄ］）だけが格納される必要があることに留意されたい。暗号ハッシュ関数は計算に関して安全であると仮定される。すなわち、格納されたハッシュの値からＣ［Ｄ］の値を推定することは極めて難しい。図１に示されるように、認証を実行するために、ユーザｕはパスワードＹ［ｕ］を入力し、以下の式が成り立つ場合に且つその場合に限り、アクセスが許可される。
【００４３】
【数６】
2010170521.tif 000008
【００４４】
本発明の実施の形態は、１つのシンドロームＳ［Ｄ］、及び１つの暗号ハッシュを用いて、Ｔ人のユーザのためのアクセス制御システムを構成する。加えて、コードワードＣ［Ｄ］のサイズＮが十分に大きい場合には、新たなユーザを追加することは、何の問題もない。管理者はすべきことは、ＢＳＣ−ｐの新たな実現形態を作り出し、上記のようなＸ［ＵＴ＋１，Ｄ］を得ることだけである。
【００４５】
パスワードの階層を生成する方法
単一のハッシュ及び１つのシンドロームで多数のユーザを認証する方法は、本発明の実施の形態による階層的パスワード割当て方法における基礎的要素として用いられる。この説明を容易にするために、４レベルのユーザの階層を用いる。コードワードのサイズＮが十分に大きいものとすると、本発明は、任意のレベル数及びレベル当たり任意のユーザ数に一般化される。また、本発明は、図３に示されるよりもはるかに複雑な、任意の分岐階層にも一般化される。
【００４６】
図３は、本発明の実施の形態による、ユーザ及びアクセス制御デバイスの階層３００を示す。その階層は、１つの根ノード及び複数の派生ノードを有する木の形をとる。階層３００は、デバイス３１、３２、３３、３４及び３５を含む。また、階層３００は、ユーザであるＡ、Ｂ１、Ｂ２、Ｃ１、Ｃ２、Ｃ３、Ｃ４、Ｃ５、Ｄ１及びＤ２を特定する。本実施の形態の目的は、これらのユーザのそれぞれにパスワードを割り当てることである。
【００４７】
表記及び定義
この説明のために、階層３００内の全てのユーザのパスワードが、以下の規則に従って割り当てられる。
【００４８】
その木の根ノードに近いユーザは、根ノードから離れているユーザよりも上位である。複数の下位のユーザが単一の上位のユーザに接続される場合には、その上位のユーザは祖先と呼ばれ、複数の下位のユーザは子孫と呼ばれる。たとえば、図３を参照すると、ユーザＢ１は、ユーザＣ１、Ｃ２、Ｄ１及びＤ２に対する祖先であり、ユーザＣ１、Ｃ２、Ｄ１及びＤ２は全てユーザＢ１の子孫である。
【００４９】
ユーザが所与のデバイスにアクセスすることができる場合には、全ての祖先も、それぞれのパスワードで、そのデバイスにアクセスすることが可能である。たとえば、さらに図３を参照すると、デバイス３５には、ユーザＤ１及びユーザＤ２がアクセスすることができるので、デバイスＤ１には、ユーザＣ２及びユーザＢ１もアクセスすることができるが、ユーザＣ１はアクセスすることができない。
【００５０】
ユーザｕがアクセスすることができる最もセキュリティの高いデバイスＤは、最も近いノードに関連付けられるデバイスである。したがって、ユーザｕがアクセスすることができる他のデバイスは、セキュリティのより低いデバイスである。たとえば、図３において、デバイス３２は、ユーザＢ２にとって最もセキュリティの高いデバイスであり、一方、デバイス３４は、ユーザＣ５にとって最もセキュリティの高いデバイスである。最もセキュリティの高いデバイスに割り当てられる、ユーザｕのためのパスワードは、全ての他のセキュリティのより低いデバイスへのアクセスを容易にする。
【００５１】
ユーザｕが最もセキュリティの高いデバイスＤにアクセスすることができる場合には、そのユーザの子孫は、割り当てられたパスワードだけを用いて、そのデバイスにアクセスすることはできない。たとえば、デバイス３３は、ユーザＣ２にとって最もセキュリティの高いデバイスであり、それゆえ、ユーザＤ１及びユーザＤ２は、デバイス３３にアクセスすることはできない。
【００５２】
ユーザｕに割り当てられるパスワードはＸ［ｕ，Ｄ］によって示される。ただし、Ｄはユーザのための最もセキュリティの高いデバイスである。たとえば、ユーザＢ２に割り当てられるパスワードはＸ［Ｂ２，３２］である。上記のように、このパスワードは、長さＮの２進数列である。さらに、本明細書において規定される規則によれば、このパスワードは、ユーザＢ２が祖先である全ての他のデバイスのパスワードとしても用いることができる。
【００５３】
特定のデバイスにアクセスすることができる全てのユーザは同僚と呼ばれる。たとえば、図３において、ユーザＣ１及びユーザＣ２は同僚である。同僚は、同じ祖先又は異なる祖先を有することができる。同僚は、同じ子孫又は異なる子孫を有することができる。
【００５４】
パスワード生成
図４は、本発明の実施の形態による、パスワードを生成し、割り当てる方法を示す。ユーザｕのためのパスワードＹ［ｕ］又はＸ［ｕ，Ｄ］は、システム管理者の管理下で典型的に実行される以下のステップを用いて生成される。
【００５５】
最初に、管理者は、ユーザｕの「親」すなわち最も近い祖先の位置を特定する（４１０）。たとえば、図３を参照すると、ユーザＤ１の親はユーザＣ２であり、ユーザＣ２の親はユーザＢ１であり、ユーザＢ１の親はユーザＡであり、ユーザＡの親は、長さがＮであり、ｉ．ｉ．ｄ．ベルヌーイ入力を有し、ｂ＝０．５であるバイナリコードワードＣ［Ｄ］∈Ｒ１×Ｎである。ユーザｕの親はｕ’によって示され、セキュリティデバイスはＤ’によって示される。したがって、親のパスワード４１５はＸ［ｕ’，Ｄ’］である。
【００５６】
親のデバイスＤ’のために、管理者は、式（１）に従って、シンドロームＳ［Ｄ’］を用いてコードワードＣ［Ｄ’］４２５、すなわちＣ［Ｄ’］＝ｇ（Ｘ［ｕ’，Ｄ’］，Ｓ［Ｄ’］）を求める（４２０）。
【００５７】
その後、管理者は、或る反転確率ｑ、たとえば、０．５を有するバイナリ対称チャネルの中に、コードワードＣ［Ｄ’］４２５のビットを通すことによって、親のコードワードを変更する（４３０）。Ｃ［Ｄ’］の変更されたバージョンは、Ｃ［Ｄ］４３５によって示される。典型的には、ＢＳＣ−ｑチャネルをシミュレートするために、すなわち、確率ｑでＣ［Ｄ’］のビットをランダムに反転するために、擬似乱数発生器が用いられる。任意のセキュリティのより低いデバイスにアクセスすることができるようにするために、擬似乱数発生器のシードが、親ユーザｕ’に予め割り当てられている。このシードはデバイス上に格納されないこと、又はこのシードはユーザｕには提供されないことに留意されたい。これは、親ｕ’の無許可の同僚によるデバイスＤへの攻撃するのを難しくする。
【００５８】
パリティチェック行列Ｈ４４２を用いる所定のＥＣＣの場合、シンドロームＳ［Ｄ］＝Ｃ［Ｄ］ＨＴ４４５を計算する（４４０）。シンドローム４４５は、アクセス制御デバイスＤ１２０に格納される。この単一のシンドロームを用いて、このデバイスにアクセスことを許される全てのユーザを認証する。
【００５９】
さらに、上記のように、ｈ（Ｃ［Ｄ］）、すなわちＣ［Ｄ］の暗号ハッシュ４５５を求め（４５０）、そのハッシュをデバイス１２０に格納する。典型的には、Ｃ［Ｄ］を直接デバイス１２０に格納しない。
【００６０】
図２Ｂを参照しながら上述したように、ＢＳＣ−ｑの１つの実現形態の中にコードワードＣ［Ｄ］４３５を通し（４６０）、Ｘ［ｕ，Ｄ］４６５を生成する。Ｘ［ｕ，Ｄ］４６５をユーザｕのためのパスワードＹ［ｕ］として割り当て、典型的には、そのパスワードをユーザデバイス１１０に格納する。
【００６１】
本発明のいくつかの実施の形態において、パスワードＸ［ｕ，Ｄ］４６５及びシステム管理者の秘密鍵４７５ＫＥを与えられると、デジタル署名４８０Ｚ［ｕ］＝Ｖ（Ｘ［ｕ，Ｄ］，ＫＥ）を求める（４７０）。また、署名Ｚ［ｕ］４８０はユーザｕに割り当てられ、ユーザデバイス１１０に格納される。アクセスを獲得するために、ユーザは、自分のパスワードＸ［ｕ，Ｄ］４６５及びデジタル署名Ｚ［ｕ］４８０の両方を提供し、インサイダ攻撃からシステムを保護しなければならない。
【００６２】
図５は、階層的な形において方法４００を示す。個々の演算ユニットは、図２を参照しながら説明された単一ステージのパスワード割当てのレプリカである。簡単にするために、パスワード割当て過程の最後のステップ、すなわちデジタル署名の計算は示されない。
【００６３】
ユーザ及びアクセス制御デバイスに格納される認証情報
図６は、ユーザが階層、たとえば階層３００の全ての許されるアクセス制御デバイスにアクセスすることができるようにするために、本発明の実施の形態に従ってユーザ及びアクセス制御デバイスに格納される認証情報例を示す。
【００６４】
本発明の実施の形態において、ユーザデバイス１１０は、パスワードＸ［ｕ，Ｄ］６１０にアクセスすることができる。ただし、Ｄは、ユーザｕがアクセスするのを許される最もセキュリティの高いデバイスを表す。このパスワードＸ［ｕ，Ｄ］６１０は、ユーザｕが、全ての子孫に割り当てられるデバイスにアクセスすることができるようにする。デジタル署名Ｚ［ｕ］６３０もデバイス１１０に格納され、それによって、アクセス制御デバイスは、パスワードの完全性を検査することができるようになる。これは、管理者に知られることなく新たなパスワードを生成することによってアクセスを獲得しようと試みる正規のユーザによるインサイダ攻撃に対する防御の最前線である。
【００６５】
シード６２０は、さらに詳細に後述するように、コードワード演算の変更を実行するために擬似乱数発生器によって用いられる。ユーザがデバイスＤ及びｌ個の他のセキュリティのより低いデバイスにアクセスする場合には、ｌ個のシードが格納され、より低いレベルのデバイス毎に１つのシードによって変更演算が実行される。その変更演算は、祖先のパスワードにアクセスする困難を増大させる。
【００６６】
アクセス制御デバイス１２０上に格納される認証情報は、そのデバイスが、ユーザデバイス１１０によって提供されるパスワードの信憑性を検証することを可能にする。デバイスＤにおいて、認証の過程は、シンドロームＳ［Ｄ］が与えられるときに、入力パスワードＹからコードワードＣ［ｄ］を復元することができるか否かを検証することを含む。しかしながら、セキュリティのために、デバイス１２０上にコードワードＣ［Ｄ］を直接格納することは望ましくない。なぜなら、悪意のある攻撃者がＣ［Ｄ］へのアクセスを獲得する場合には、その攻撃者が、入力パスワードＹ＝Ｃ［Ｄ］を用いることによって、当たり前のように自己認証することができるためである。
【００６７】
本発明のいくつかの実施の形態では、アクセス制御デバイス１２０は、誤り訂正符号のパリティチェック行列Ｈ６７０、シンドロームＳ［Ｄ］６４０及びｈ（Ｃ［Ｄ］）６５０によって表される、Ｃ［Ｄ］の暗号ハッシュにアクセスする。さらに、ユーザによって提供されるパスワードの完全性を検査するために用いられる公開鍵ＫＤ６６０も、デバイス１２０に格納される。ユーザがパスワードＸ［ｕ，Ｄ］及び署名Ｚ［ｕ］を入力しなければならないことを思い出されたい。インサイダ攻撃中に、パスワード内の数ビットを反転して新たなパスワードＹ［ｕ］を生成することによって、正規のユーザｕが、本人であることを隠すことができる。これを防ぐために、公開鍵ＫＤを用いて、Ｙ［ｕ］が署名Ｚ［ｕ］と一致するか否かを検査する。
【００６８】
パスワードを認証する方法
本発明の一実施の形態では、ユーザｕがパスワードＹ［ｕ］及び署名Ｚ［ｕ］を用いて、最もセキュリティの高いデバイスＤにアクセスするとき、以下のように、認証過程が行われる。そのデバイスは、システム管理者の公開鍵ＫＤ６６０を用いて、パスワードＹ［ｕ］、すなわちＸ［ｕ，Ｄ］６１０が、デジタル署名Ｚ［ｕ］６３０と一致するか否かを検証する。一致しない場合には、そのアクセスは拒否される。一致する場合には、そのデバイスは、式（２）の等式が満たされるか否かを検証する。満たされない場合には、アクセスが拒否される。満たされる場合には、アクセスが許可される。この最後のステップは、図１に示される方法１００と同様である。
【００６９】
図７は、ユーザｕが親である低レベルデバイスにおけるパスワード認証を示す。たとえば、ユーザＢ１が、デバイス３３にアクセスする必要がある。図３を参照されたい。セキュリティのより低いデバイスが、最もセキュリティの高いデバイスＤよりもｌレベルだけ低い一般的な状況を分析する。これは、パスワードを入力するために用いられるユーザデバイスが、ユーザのパスワードを変更するために少なくともｌ個のシードを格納することを意味する。一実施の形態では、各シードは、擬似乱数発生器によって生成される整数である。
【００７０】
正規のユーザ、たとえば親ユーザが、ｌ個の低レベルデバイス、すなわちｌレベルアクセス制御デバイスにアクセスすることができるようにするパスワードＹ’［ｕ］を求めるために、ｌ個のシード６２０の最初のシードを用いてパスワードＹ［ｕ］７１０を変更し、ｌレベル親パスワードを生成する。
【００７１】
たとえば、ユーザｕが、デバイス階層、たとえば、階層３００内の最もセキュリティの高いデバイスＤよりも１レベルだけ低いデバイスにアクセスする必要がある場合には、シード６２０のうちの最初のシードを用いて、パスワード７１０を１回だけ変更する（７００）。ユーザｕが、最もセキュリティの高いデバイスＤよりも３レベルだけ低いデバイスにアクセスする必要がある場合には、シード６２０のうちの最初の３つのシードを用いて、パスワード７１０を３回変更する（７００）。
【００７２】
変更されたパスワードは、ｌ回の変更演算の後に、Ｙ’［ｕ］７２０によって表される。変更されたパスワード７２０は、低レベルデバイスへのアクセスを認証するために、方法１００に供給される。したがって、ｌレベル親パスワード及びｌレベルシンドロームからｌレベル親候補コードワードを復元する。ただし、ｌレベルシンドロームはｌレベルアクセス制御デバイスに関連付けられる。次に、ｌレベル親候補コードワードの暗号ハッシュが、ｌレベルアクセス制御デバイスに関連付けられるｌレベルコードワードの暗号ハッシュに等しい場合には、親ユーザがｌレベルアクセス制御デバイスにアクセスするのを許可する。
【００７３】
パスワードの取消
ユーザに割り当てられたパスワードを取り消すことが必要になる場合がある。暗号ハッシュに基づく従来のパスワードシステムの場合、取消は、単にパスワードのハッシュを削除することによって実行される。本明細書において記述されるシステムの場合、この手順は、各アクセス制御デバイス上に無効なパスワードの「ブラックリスト」６８０を包含し、そのデバイス上の１つ又は複数のパスワードを取り消す必要があるときにはいつでも、そのブラックリストを更新することによって果たされる。新たなユーザは、アクセス制御デバイスを更新することなく登録されるが、任意のパスワードの取消は、ブラックリストの更新を必要とする。
【００７４】
ブラックリストにアクセスを獲得する攻撃者に対するセキュリティのために、システム管理者によってのみ保有されるシステムパスワードを用いて、デバイスへの書込みアクセスを要求する。このシステムパスワードは、従来の暗号ハッシュを用いて、又は本明細書において記述される階層的アクセス制御方式によって実現される。取消の過程は、任意のユーザを認証する前に実行され、すなわち、そのアクセス制御方法は最初に、入力パスワードがブラックリストに属するか否かを検査する。入力パスワードがブラックリストにおいて見つかる場合には、その方法の残りの部分は無効となり、アクセスが拒否される。
【００７５】
本発明は好ましい実施の形態の例として説明されてきたが、本発明の精神及び範囲内で、種々の他の適合及び変更が行われ得ることは理解されたい。それゆえ、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内に入るような全ての変形及び変更を包含することである。
【図１】
2010170521.tif 000009
【図２Ａ】
2010170521.tif 000010
【図２Ｂ】
2010170521.tif 000011
【図３】
2010170521.tif 000012
【図４】
2010170521.tif 000013
【図５】
2010170521.tif 000014
【図６】
2010170521.tif 000015
【図７】
2010170521.tif 000016
【外国語明細書】
2010170521.tif 000017
2010170521.tif 000018
2010170521.tif 000019
2010170521.tif 000020
2010170521.tif 000021
2010170521.tif 000022
2010170521.tif 000023
2010170521.tif 000024
2010170521.tif 000025
2010170521.tif 000026
2010170521.tif 000027
2010170521.tif 000028
2010170521.tif 000029
2010170521.tif 000030
2010170521.tif 000031
2010170521.tif 000032
2010170521.tif 000033
2010170521.tif 000034
2010170521.tif 000035
2010170521.tif 000036
2010170521.tif 000037
2010170521.tif 000038
2010170521.tif 000039
2010170521.tif 000040
2010170521.tif 000041
2010170521.tif 000042
2010170521.tif 000043
2010170521.tif 000044
2010170521.tif 000045
2010170521.tif 000046
2010170521.tif 000047
2010170521.tif 000048
2010170521.tif 000049
2010170521.tif 000050