JP3078841B2

JP3078841B2 - 通信システムの安全なキー配布を提供するための方法およびシステム

Info

Publication number: JP3078841B2
Application number: JP07505504A
Authority: JP
Inventors: ヤンソン、フィリッペ; ツディーク、ゲーネ
Original assignee: インターナシヨナル・ビジネス・マシーンズ・コーポレーシヨン
Priority date: 1993-07-27
Filing date: 1993-07-27
Publication date: 2000-08-21
Anticipated expiration: 2015-08-21
Also published as: JPH08511928A; EP0711480A1; US5729608A; DE69311581T2; EP0711480B1; WO1995004416A1; DE69311581D1

Description

【発明の詳細な説明】［技術分野］本発明は、全般的には安全な通信システムに関し、具
体的には、通信システムでの安全な暗号キー配布に関す
る。さらに具体的に言うと、本発明は、通信システムで
の安全な認証キー配布に関する。

［背景技術］認証プロトコルとキー配布プロトコルは、当技術分野
で既知である。

２者認証プロトコル（以下、2PAPと呼称する）は、バ
ード（R.Bird）、ゴパル（I.Gopal）、ヘルツバーグ
（A.Herzberg）、ジャンソン（P.Janson）、クッテン
（S.Kutten）、モルバ（R.Molva）、ヤング（M.Young）
共著、Systematic Design of Two−Party Authenticati
on Protocols,Proceeding of Crypto'91、1991年８月に
記載されている。これに記載の2PAPでは、２人のユーザ
が、質問（challenge）を送り、共有秘密キーを使用す
ることによってお互い認証する。このプロトコルは、イ
ンターリーブ・アタックとして既知の重要なクラスのア
タックに対して安全であることが示されている。このよ
うなアタックは、敵対者が下記のいずれかを使用する能
力に基づくものである。

・プロトコルの過去の実行から得られた合法的な処理
の流れ、または、・正当な当業者から敵対者によって引き出されたプロ
トコルの流れ。

キー配布プロトコル（以下、KDPと呼称する）のグル
ープは、モバル（R.Molva）、ツディク（G.Tsudik）、
バンヘレウェーケン（E.Van Herreweghen）、ザティ
（S.Zatti）共著、KriptoKnight Authentication and K
ey Distribution Service,Proceeding of ESORICS 92,1
992年10月,Toulouse,Franceに記載の実際のネットワー
ク・セキュリティ・サービス、KryptoKnightでその後実
現された。

２者キー配布プロトコル（以下、2PKDPと呼称する）
では、ユーザが、以前に既に秘密に共有されたキーを使
用して、別のユーザに新しい秘密キーを配布する。

３者キー配布プロトコル（以下、3PKDPと呼称する）
および多者キー配布プロトコル（以下、MPKDPと呼称す
る）では、米国特許第4649233号明細書に記載のよう
に、他のユーザのそれぞれと、対応するマスタ・キーを
共有するユーザ（しばしば「サーバ」と呼ばれる）が存
在し、各マスタ・ユーザ・キーは、サーバと、対応する
ユーザだけに知られている。ユーザ（２人以上）のグル
ープが機密を交換したい時には、彼らは共通のキーを共
有していないので、サーバとの共同作業に頼らなければ
ならない。要求時にはサーバが、２人（またはそれ以
上）の選択されたユーザのために新しいグループ・キー
を生成し、配布する。

変更が存在するときに、経路指定、同報通信およびマ
ルチキャスト（経路または経路のセットに沿ったユーザ
のサブセットへのメッセージ送出）を継続して可能とす
る動的経路指定機能を提供する通信システムでは、キー
配布は、時間制約のために特に困難である。このような
動的経路指定機能自体は、当技術分野で既知であり、た
とえば、バートセカス−ギャラガ（Bertsekas−Gallage
r）著、Data Networks,Prentice−Hall,1987年,section
5.3.を参照されたい。

［発明の開示］この従来技術には、いくつかの短所がある。当技術分
野で既知のキー配布プロトコルは、十分に（少なくと
も、バード他に記載の2PAPほどに）安全であることが示
されていない。すなわち、たとえばインターリーブ・ア
タックやカット・アンド・スプライス・アタックなどの
あらゆる種類のアタックに対して、抵抗力を有すると信
じられてはいるが、証明はされていない。

さらに従来技術の一部は、配布されるキーの完全性を
保証しない、すなわち、配布されるキーが敵対者によっ
て変更されえないことが保証されない。これらの制限
は、安全な認証キー配布のために最小長のメッセージを
用いるプロトコルの場合に特にあてはまる。

上記の従来技術の欠点は、請求項に示された本発明に
よって克服される。

本発明は、特にインターリーブ・アタックに対して、
プロトコル・メッセージの特徴的な構造のおかげで、2P
APと同程度に安全であることが数学的に実証されている
方法およびシステムを提供する。基本的な２者キー配布
（および認証）プロトコルは、より精巧な、たとえば、
３者、多者、またはドメイン間キー配布プロトコルを構
築するための基本構成要素として使用することができ
る。上記構造によって、さらに、配布されるキーの完全
性が保証される。さらに、この認証キー配布プロトコル
は、最小長のプロトコル・メッセージを必要とし、交換
されるメッセージの数およびサイズの両方で、可能な限
りコンパクトである。

これらのすべてが、最小の計算要件で達成でき、暗号
化／復合化機能を使用する必要はない。

前述およびその他の本発明の目的、特徴および長所
は、添付図面に示された本発明の好ましい実施例の下記
の詳細な説明から明らかになる。

［図面および表記の簡単な説明］下記の図面を参照して、本発明を詳細に説明する。

第１図は、本発明の方法およびシステムの実施に使用
することができる通信システムを表す図である。

第２図は、従来技術の2PAPを示す図である。

第３図は、本発明による２者認証キー配布プロトコル
の例を示す流れ図である。

第４図は、本発明による2PKDPの例のメッセージの流
れを示す図である。

第５図は、本発明による３者認証キー配布プロトコル
の例を示す流れ図である。

第６図は、本発明による3PKDPの例のメッセージの流
れを示す図である。

第７図は、本発明によるMPKDPの例のメッセージの流
れを示す図である。

第８図は、本発明による最適化された3PKDPの例のメ
ッセージの流れを示す図である。

本明細書全体を通じて、下記の用語を使用する。

Ａ、Ｂ、Ｃ完全なユーザ名。すべての名前が、別個
であると仮定する。これらの名前は、たとえば、名前を
直接コード化するか、その名前の元々のコーディングを
64ビット・フィールドに縮小するためにハッシュ関数を
適用するかのいずれかによって得られる64ビット値であ
る。

Ｓ認証サーバの完全な名前。Ｓは、構成ユーザのす
べてによって例外なく信用されると仮定されるユーザで
ある。

N_ab Ｎで始まる記号は、すべてがランダムな質問ま
たはナンス（nonce）すなわち、予測不能な１回だけ使
用される乱数である。これらを、新鮮度情報の単位と称
することもできる。添字の第１文字は、ナンスを生じた
ユーザを指し、添字の第２文字は、質問された目標ユー
ザを識別する（たとえば、N_abは、Ａによって生成さ
れ、Ｂに質問するために送られたナンスである）。

K_ab Ｋで始まる記号は、すべてがキーである。添字
は、そのキーを共有するユーザを識別する（たとえば、
K_abは、ＡとＢの間で共有されるキーである）。

排地的論理和またはXOR関数。

E_K（Ｘ）キーＫの下での平文ブロックＸの暗号化。
本明細書では、用語「暗号化」を、クリアな（暗号化さ
れていない）テキスト入力の単一ブロック交換を指すの
に使用する。これには、DES（National Bureau of Stan
dards,Federal Information Processing Standards,Nat
ional Bureau of Standards,Publication 46、1977年に
記載）などの従来の暗号関数ならびに、キーが接頭辞ま
たは接尾辞として使用される時のMD5（リベスト（R.Riv
est）著、The MD5 Message Digest Algorithm,Internet
DRAFT、1991年７月に記載）などの強力な一方向関数
（絶対に逆関数が計算できない）が含まれる。DESの場
合、ＫとＸの両方が、基礎となる暗号関数の基本ブロッ
ク・サイズすなわち64ビットを超えないものと仮定され
る（このような仮定は、定義によってどのようなパラメ
ータ・サイズでも受け容れるMD5などの多数の一方向ハ
ッシュ関数には無関係である）。

FUNC（x,y,z）引数ｘ、ｙ、ｚに依存する暗号関
数。関数は、その引数のすべてまたは一部だけに依存す
ることができる。すべての関数は、基礎となる暗号アル
ゴリズムの基本ブロック・サイズ、たとえばDESでは64
ビット、MD5では128ビットなどと等しいサイズの結果を
生成する。

Ａ⇒ＢＸこの表記は、単一のプロトコルの流れを
示す。これは、ＡがメッセージＸをＢに送ったことを表
す。

また、「_ba」は「ハットN_ba」と表記する。

同様に、「_ba」は「チルドN_ba」と表記する。

［発明の詳細な説明］ここで図面、具体的には第１図を参照すると、通信シ
ステム（100）が示されている。ユーザＡ（101）、Ｂ
（102）、Ｃ（103）は、１組のリンク（104、105、10
6、107、108）によって接続された、ローカル・エリア
・ネットワークのコンピュータ（端末）のいずれかの位
置に存在できる。これらのユーザのうちの１つ（または
複数）が、安全なキー配布のためのサーバＳ（109）と
して働くことができる。一般的な方法は、マスタ・ユー
ザ・キーのテーブルを、サーバの安全な記憶域に保存す
ることである（K_asは、サーバと、名前がＡのユーザと
によって共有されるマスタ・キーであり、K_bsは、同様
にＢと共有されるキーである）。各ユーザは、その安全
な記憶装置（暗号化されたファイル、特殊なハードウェ
ア、スマート・カードなど）に自分のマスタ・キーを記
憶させることもできる。

第２図は、従来技術の、バード他に記載の、共通のキ
ーK_abを共有する２ユーザ（ＡおよびＢ）の間での基本
的な安全な2PAPを示す図である。このプロトコルの実行
は、ブロック201から開始され、イニシエータ当事者Ａ
が、その名前ＡとナンスN_abを第２ユーザＢに送る。Ａ
からのメッセージを受け取る際に、共有キーK_ab、ナン
スN_ab、Ｂによって生成される新ナンスN_baおよびメッセ
ージ発信元の名前Ｂに基づく認証関数AUTH（K_ab,N_ab,N
_ba,B）が、第２ユーザＢによって計算される。ブロック
202を参照すると、この認証関数の値とナンスN_baが、Ｂ
からＡに送られる。Ｂからのメッセージを受け取る際
に、第１ユーザＡは、認証関数AUTH（K_ab,N_ab,N_ba,B）
の値を再計算し、Ｂが送ったメッセージ内の対応物と比
較する。これが一致すると、Ｂの認証がもたらされる。
その後、第１ユーザＡは、両方向認証を完了するため、
共有キーK_ab、ナンスN_abおよびナンスN_baに基づくもう
１つの認証関数ACK（K_ab,N_ab,N_ba）の値を計算する。ブ
ロック203を参照すると、認証関数ACK（K_ab,N_ab,N_ba）
の値がＡからＢへ送られる。Ａからのメッセージを受け
取る際に、ユーザＢは、認証関数ACK（K_ab,N_ab,N_ba）の
値を再計算し、Ａが送ったメッセージの対応物と比較す
る。これが一致すると、Ａの認証がもたらされる。

２者キー配布プロトコル（2PKDP）第３図は、本発明による、２ユーザＡおよびＢの間で
の安全な２者認証キー配布プロトコルの例を示す図であ
る。ＡとＢは、プロトコル実行の前に共通キーK_abを共
有すると仮定する。

このプロトコル実行は、ブロック301で開始され、イ
ニシエータ当事者Ａが、その名前ＡとナンスN_abを第２
ユーザＢに送る。この第２ユーザＢは、Ａに対してサー
バのように活動するものと見なすことができる。その
後、第２ユーザＢは、ブロック302で新キーK_baを生成
し、このキーは、安全な形で保持され、ＡとＢによる使
用だけを目的とする。少なくとも共有キーK_ab、ナンスN
_ab、新キーK_baおよびＢの名前に基づく認証関数AUTH（K
_ab,N_ab,K_ba,B）の値ハットN_baは、ブロック303で第２ユ
ーザＢによって計算される。この関数AUTH（K_ab,N_ab,K
_ba,B）は、共有キーK_abに基づく認証式とすることがで
きる。AUTHの１例を次に示す（ここでは、暗号化のすべ
てが、キーK_abを用いて実行される）。

Ｅ（Ｂ（Ｅ（K_baＥ（N_ab）））同一のユーザＢが、その後、ブロック304で、少なく
とも共有キーK_ab、認証関数AUTH（K_ab,N_ab,K_ba,B）の値
ハットN_baおよび新キーK_baに基づく関数BRAID（K_ab,ハ
ットN_ba,K_ba）の値を計算する。関数BRAIDは、暗号関数
とするか、共有キーK_abの下での値ハットN_baの暗号化に
よって計算されるマスク式 MASK＝E_Kab（_ba）と新キーK_baのXORすなわち、 E_Kab（_ba）K_ba とすることができる。ここでブロック305を参照する
と、認証関数AUTH（K_ab,N_ab,K_ba,B）の値および関数BRA
ID（K_ab,ハットN_ba,K_ba）の値が、ＢからＡに送られ
る。Ｂからのメッセージを受け取る際に、ブロック306
で、第１ユーザＡは、共有キーK_abおよび値ハットN_baを
使用して、関数BRAID（K_ab,ハットN_ba,K_ba）の値から新
キーK_baを抽出することができる。関数BRAIDが、 BRAID＝E_Kab（_ba）K_ba であると仮定すると、Ａは、マスク式 MASK＝E_Kab（_ba）の値を計算し、その後、関数 BRAID＝E_Kab（_ba）K_ba の値とこのマスク式の値をXORすることによって、新キ
ーK_baを抽出する。すなわち K_ab＝E_Kab（_ba）K_baMASK ＝E_Kab（_ba）K_baE_Kab（_ba）である。このユーザが、実際に、ブロック301でＢへ送
られた名前のユーザであるならば、このユーザは、キー
K_abを有し、新キーK_baを得ることができる。このユーザ
が、ユーザＡを装っている場合、このユーザはキーK_ab
を有しておらず、新キーK_baを得ることはできない。ブ
ロック307を参照すると、第１ユーザＡは、認証関数AUT
H（K_ab,N_ab,K_ba,B）の値を再計算し、Ｂが送ったメッセ
ージの対応物と比較する。一致が生じると、新キーK_ba
の正しく認証された（秘密の）配布がもたらされる。そ
の後、この処理はブロック308に進み、第１ユーザＡ
が、両方向認証を完了するため、少なくとも共有キーK
_ab、ナンスN_abおよび新キーK_baに基づくもう１つの認証
関数ACK（K_ab,N_ab,K_ba）の値を計算する。関数ACKは、
共有キーK_abに基づく認証式とすることができる。ACKの
１例を次に示す（ここでは、すべての暗号化が、キーK
_abを用いて実行される）。

Ｅ（K_baＥ（N_ab））ブロック309を参照すると、認証関数ACK（K_ab,N_ab,K
_ba）の値が、ＡからＢへ送られる。この処理は、ブロッ
ク310で終了するが、ここでは、ユーザＢが認証関数ACK
（K_ab,N_ab,K_ba）の値を再計算し、Ａが送ったメッセー
ジの対応物と比較する。一致が生じると、Ａの認証がも
たらされる。

BRAID関数の構造の独特な特徴は、認証と、それと同
時のキー配布の両方を達成するのに重要である。さら
に、この構造によって、最小の長さのプロトコル・メッ
セージを構築することが可能になる。これは、予測不能
なランダムな値を（秘密裡に）配布すると同時に、その
配布される値を２データ単位未満の長さのメッセージを
用いて認証することが不可能だからである。本明細書で
提案される２者キー配布プロトコルは、メッセージの個
数とサイズの両方において極端にコンパクトであり、こ
のため、プロトコル階層のどの層であってもこれを適用
することは簡単である。さらに、下で説明するように、
このプロトコルは、すべてのインターリーブ・アタック
に対して抵抗力を有する。このすべてが、最小の計算要
件で達成され、暗号化／復合化機能（より強力な暗号ツ
ールであるが、常に使用可能ではない）を使用する必要
はない。

本明細書で提案される2PKDPに従って交換されるメッ
セージのリストを、第４図に示す。

セキュリティの議論説明を単純明瞭にするために、第４図に示された2PKD
Pの例を参照する。

認証本明細書で提案される2PKDPのセキュリティの実証の
第１ステップは、これと2PAPが同等であることを示すこ
とである。言い換えると、本明細書で提案されるプロト
コルが、2PAPのセキュリティと等しいセキュリティを有
する２者認証のための手段を提供するものであるという
ことを明らかにする必要がある。この同等性を証明でき
るならば、本明細書で提案されるプロトコルが、2PAPの
基本特性すなわち、インターリーブ・アタックに対する
抵抗を継承することが立証される。もちろん、認証以外
のプロトコル目標を、2PAPから継承することはできな
い。具体的に言うと、本明細書で提案されるプロトコル
は、配布されるキーの非開示という追加要件に合致する
ことが示される。

キー配布プロトコル全般に関して、いくつかの初期の
仮定から始める。

・キーは、必ず１当事者によって生成される。

・配布されるキーは、ランダムで予測不能な値でなけ
ればならない。ＡとＢが2PKDPに関与し、Ｂがキーを生
成する場合、Ａもどの相手方も、このキーを予測できな
い。

・キーは、絶対に再利用されない。

これらの仮定から、新たに生成されるキーが、ナンス
に非常に似ているという重要な所見が導かれる。実際、
ナンスN_baと新キーK_baの間の唯一の相違は、N_baが平文
で通信されるが、K_baが秘密に保持されることである。

ここで、この２つのプロトコルの間の唯一の相違は、
第２メッセージのいわゆる「ナンス」フィールドである
ことがわかる。2PAP（202）では、ナンス・フィールド
が単にN_baであり、これに対して2PKDP（402）では、ナ
ンス・フィールドがより複雑な式 E_Kab（_ba）K_ba である。この式の目的は、ナンスとして使用されるキー
すなわちK_baを隠すことである（キー信頼性の問題は、
後で検討する）。それぞれのナンス・フィールドの同等
性を実証するためには、下記の３つの問題に対処しなけ
ればならない。

K_baはナンスであるか K_baが真のナンスではない場合、同等性は保持されな
い。しかし、前に述べたように、キーが秘密に保持され
るという事実以外に、キーとナンスの区別はない。具体
的に言うと、キー生成とナンス生成の規則および手順
は、全く同一である。

ハットN_baはナンスであるか K_abは真のナンスであり、ハットN_baは、K_baの強力な
１方向関数の結果であるから、ハットN_baもナンスであ
ると断定される。

E_Kab（_ba）K_baとK_baの間に１対１の関係があるか
または、 E_Kab（_ba）＝E_Kab（_ba）となる別個の値チルドN_baが存在するか、と言っても同
等である。

E_Kab が、DESなどの強力な暗号関数であるという仮定の下で
は、これは明らかに不可能である。というのは、そうで
なければ復合化が１対１にならないからである。その一
方で、Ｅが、その入力の固定サイズのダイジェストを作
る強力な１方向ハッシュ関数（たとえばMD5）である場
合には、異なる入力値が、同一のダイジェストにハッシ
ュ化される可能性がある。その場合、この問題は、チル
ドN_baの計算の困難さになる。たとえばMD5では、所与の
入力が既知のダイジェスト（本明細書の事例では、ダイ
ジェストされ未知である）にハッシュ化される確率は、
1/2¹²⁸（実際には不可能）である。

キー配布次に、本明細書で提案される2PKDPの追加の特徴であ
るキー配布を検討する。強力な認証は、安全なキー配布
の達成には不十分であり、したがって、前節の結果は、
これに関しては適用できない。

第１の問題は、安全なキー配布の定義である。キー配
布の目的に関して、プロトコルが安全と見なされるの
は、下記の３つが満たされる場合である。

非開示すなわち、配布されるキーを敵対者が（ＡまたはＢの
いずれかからの援助なしで）取得できないこと。

独立すなわち、あるキーの知識を他のキーの取得に使用で
きないこと。ここでは、配布されるキーが、後程別の2P
KDPでの暗号キーとして使用されないものと仮定する
（たとえば、ＡとＢの間で交換されるデータ・メッセー
ジに対する完全性検査の計算に、新しいキーを使用する
ことができる）。

完全性すなわち、配布されるキーを敵対者が変更できないこ
と。

非開示正当な当事者との共謀がないと仮定すると、キーの開
示は、敵対者がなんらかの方法でMASK値すなわち E_Kab（_ba）を得ることができる場合に限って可能である。しかし、
各MASKは、事実上、ハットN_baの１方向変換の結果であ
るから、これは不可能である。これは、敵対者が、１）
暗号キーK_abを所有するか、２）なんらかの方法で正当
な当事者のうちの１つから所望のMASK値を引き出すこと
ができるかのいずれかでなければならないことを暗示す
る。以下、後者の場合について、さらに詳しく検討す
る。

敵対者は、Ｂに問い合わせ、Ａを装うことによってMA
SK値を得ようと試みることができる。しかし、敵対者が
どのような値をＢに送っても、Ｂは必ずメッセージ（40
2）で新鮮なキーを生成する。敵対者が有用な情報を全
け得られないようにするのは、この新キーの新鮮さであ
る。実際に、敵対者がＢに何を送ろうと試みるかは全く
無関係である。というのは、ハットN_ba＝AUTH（K_ab,
N_ab,K_ba,B）が、新たに生成されるK_baに強く依存するか
らである。

その代わりに、敵対者はＡから情報を引きだそうと試
みることができる。これは、上の場合よりかなり困難で
ある。というのは、Ａは、メッセージ（402）が認証さ
れる場合に限ってメッセージ（403）で応答するからで
ある。したがって、敵対者は、メッセージ（402）内の
形式の式を生成できなければならないが、これは、メッ
セージ（402）の両方の暗号演算が、Ａのランダムな質
問N_abに対して計算されるので、不可能である。

独立ここで、敵対者が、なんらかの方法で2PKDPの行程の
１つからキーⁱ _baを発見することができたと仮定する。
さらに、この敵対者は、ＡまたはＢのいずれとも明瞭な
協力なしにこれを行ったものとする。これによって敵対
者が得ることのできる最も重要な追加の情報は、 E_Kab（ⁱ _ba）＝MASKⁱ である。

ここで、MASKⁱは、長期間使用されるキーK_abのもとに
おけるハットKⁱ _baの暗号であるから、この敵対者は、後
程K_abを破る試みに使用することができる［平文、暗号
文］ブロック対を発見できる。しかし、これは、敵対者
がKⁱ _baを発見することによる結果として推定されるセキ
ュリティの侵害と同程度の危険である。

残りの疑問は、敵対者が新たに獲得した情報を使用し
て、下記の１または２によってこのプロトコルを解明す
ること（アタック）ができるか否かである。

1.他のプロトコルの行程（過去または未来のいずれか）
からキーK^j _ba（ｉ≠ｊ）を発見する 2.Bを装いながら別のプロトコルの行程でＡにKⁱ _baを正
しく配布する前に述べたように、MASKは、ハットN_baの１方向関数
の結果である。また、ハットN_ba自体は、N_ab、K_baおよ
びＢの１方向関数である。これによって、本質的にタイ
プ１によるアタックの可能性が排除される。

タイプ２によって解明するには、敵対者が下記の形式
（ｉ≠ｊ）のメッセージを構築できることが必要であ
る。

^j _ba＝AUTH（K_ab,N^j _ab,K^j _ba,B）， E_Kab（^j _ba）K^j _ba ただし、K^j _ba≠Kⁱ _ba これは、敵対者が、新鮮なナンスN^j _abに対するAUTH式
の計算を含むハットN^j _baの新鮮な値を作ることができる
場合に限って可能である。敵対者は、オラクル（oracl
e）・アタックを介してハットN^j _baを得ることはできな
い。というのは、敵対者によって問い合わせのために選
択された当事者が、その当事者自身のナンスによって暗
黙のうちにリフレッシュされたメッセージで応答するか
らである。

完全性配布されるキーの完全性は、KDPの主要なセキュリテ
ィ上の特徴の１つではない。キーが敵対者によって選択
された特定の値に変更される可能性がない限り、純粋な
キー配布プロトコル自体は、キーの完全性に関係する必
要はない。たとえば、当技術分野で既知のKDPのいくつ
かは、バード他に記載の通り、キー自体が認証されず、
単に配布されるだけなので、キー変更アタックに弱い。
それにもかかわらず、これはプロトコルのバグとはみな
されない。というのは、敵対者がそのキーを既知の値に
変更できないからである。敵対者は、既知の値によりあ
るキーをオフセットすることしかできない。

その一方で、この種のアタックは、本発明の2PKDPに
対して簡単に実行可能ではない。というのは、キーを変
更するために、認証式AUTH（K_ab,N_ab,K_ba,B）を同時に
変更しなければならないからである。

３者キー配布プロトコル（3PKDP）第５図は、本発明による３者認証キー配布プロトコル
の流れ図である。3PKDPの目的は、新鮮なグループ・キ
ーをユーザのグループ（この例では２者）に配布するこ
とである。通常は認証サーバ（Ｓ）と呼称される相互に
信頼される第３者が存在すると仮定する。グループのユ
ーザのすべてが、プロトコル実行の前に、対応する秘密
のマスタ・ユーザ・キー（Ａ−Ｓ間ではK_as、Ｂ−Ｓ間
ではK_bs）を共有すると仮定する。前記ユーザ・キーの
それぞれは、サーバと対応ユーザのみが知っている。こ
の例のプロトコルでは、Ａと表記するイニンエータが存
在し、これが通信を開始する。グループは、誰がそれに
参加するかがＡに判る形で決定される。このプロトコル
は、最初にグループ内の他者（ユーザ）を識別するイニ
シエータＡによって開始される。

安全な3PKDPは、安全な2PKDPと同一の条件に、さらに
下記の要件が追加された条件を満たさなければならな
い。

・どの当事者も、配布されるグループ・キーを変更で
きてはならない。

より一般的に言うと、正当な当事者のうちの１つ（Ａ
またはＢ）は、任意の「ビザンチン（byzantine）」動
作を示すことができる（Ｓに登録された別の当事者を装
うことができる）と仮定する。もちろん、このような行
為のすべてのタイプにこのプロトコル内で対処すること
はできない。たとえば、セッション・キーの許可されて
いない開示を防止することはできない。しかし、安全な
3PKDPは、正当な当事者による攻撃に対して防御されな
ければならない。実際には、ビザンチン動作を示す正当
な当事者は、敵対者の特殊な事例（追加の知識を有する
敵対者）と見なすことができる。

2PKDPの２つの実体（行程）と2PAPの１つの実体を組
み合わせることによって、安全な3PKDPが得られる。２
ユーザＡおよびＢは、それぞれ認証サーバＳとの2PKDP
に関与する。ＡおよびＢは、それぞれがＳとユーザ秘密
キーすなわちK_asおよびK_bsを共有すると仮定する。新キ
ーK_abの配布の後に、ＡおよびＢは、お互いがK_abを知っ
ていることを確認するために2PAPに関与する。

ここでブロック501を参照すると、プロトコル実行
は、第１ユーザＡが、その名前Ａ、ナンスN_asおよびグ
ループのＡ以外のユーザ（この場合はＢだけ）の名前を
サーバＳに送ることから始まる。その後、サーバは、ブ
ロック502で新グループ・キーK_abを生成し、この新グル
ープ・キーは、安全な形で保持され、グループのユーザ
（この例ではＡおよびＢ）による使用だけを目的とす
る。少なくともユーザのキーK_as、ユーザーのナンス
N_as、グループ・キーK_abおよびグループのＡ以外のユー
ザ（この場合ではＢ）の名前に基づく認証関数AUTH（K
_as,N_as,K_ab,B）の値ハットN_saを、ブロック503でサーバ
が計算する。その後、サーバＳはブロック504で、少な
くともユーザのキーK_as、値ハットN_saおよびグループ・
キーK_abに基づく関数BRAID（K_as,ハットN_sa,K_ab）の値
を計算する。

次にブロック505を参照すると、認証関数AUTH（K_as,N
_as,K_ab,B）の値と関数BRAID（K_as,ハットN_sa,K_ab）の値
が、ＳからＡに送られる。Ｓからのメッセージを受け取
る際に、ブロック506で、第１ユーザＡは、ユーザのキ
ーK_asと値ハットN_saを使用して、ユーザの関数BRAID（K
_as,ハットN_sa,K_ab）の値からグループ・キーK_abを抽出
することができる。

次にブロック507を参照すると、第１ユーザＡは、ユ
ーザの認証関数AUTH（K_as,N_as,K_ab,B）の値を再計算
し、Ｓが送ったメッセージの対応物と比較する。一致が
生じると、グループ・キーK_abの正しく認証された（秘
密の）配布がもたらされる。その後、この処理はブロッ
ク508に進み、第１ユーザが、両方向認証を完了するた
め、少なくともユーザのキーK_as、ユーザのナンスN_asお
よびグループ・キーK_abに基づく、もう１つの認証関数A
CK（K_as,N_as,K_ab）の値を計算する。

次にブロック509を参照すると、認証関数ACK（K_as,N
_as,K_ab）の値が、ＡからＳに送られる。第１の2PKDP
は、ブロック510で終了するが、ここでは、サーバＳ
が、認証関数ACK（K_as,N_as,K_ab）の値を再計算し、Ａが
送ったメッセージの対応物と比較する。一致が生じる
と、Ａの認証がもたらされる。

同様のステップが、第２ユーザＢとサーバＳの間で実
行される。ブロック511を参照すると、第１ユーザＢ
は、その名前Ｂ、ナンスN_bsおよびグループのＢ以外の
ユーザ（この場合ではＡのみ）の名前をサーバＳに送
る。少なくともユーザのキーK_bs、ユーザのナンスN_bs、
グループ・キーK_abおよびグループのＢ以外のユーザ
（この場合ではＡ）の名前に基づく認証関数AUTH（K_bs,
N_bs,K_ab,A）の値ハットN_sbが、ブロック512でサーバに
よって計算される。その後、サーバＳは、ブロック513
で、少なくともユーザのキーK_bs、値ハットN_sbおよびグ
ループ・キーK_abに基づく関数BRAID（K_bs,ハットN_sb,K
_ab）の値を計算する。

次にブロック514を参照すると、認証関数AUTH（K_bs,N
_bs,K_ab,A）の値と、関数BRAID（K_bs,ハットN_sb,K_ab）の
値が、ＳからＢへ送られる。Ｓからのメッセージ受け取
る際に、ブロック515で、第２ユーザＢは、ユーザのキ
ーK_bsとハットN_sbを使用して、ユーザの関数BRAID
（K_bs,ハットN_sb,K_ab）の値からグループ・キーK_abを抽
出することができる。

次にブロック516を参照すると、第２ユーザＢは、ユ
ーザの認証関数AUTH（K_bs,N_bs,K_ab,A）の値を再計算
し、Ｓが送ったメッセージの対応物と比較する。一致が
生じると、グループ・キーK_abの正しく認証された（秘
密の）配布がもたらされる。その後、この処理はブロッ
ク517に進み、第２ユーザが、両方向認証を完了するた
め、少なくともユーザのキーK_bs、ユーザのナンスN_bsお
よびグループ・キーK_abに基づく、もう１つの認証関数A
CK（K_bs,N_bs,K_ab）の値を計算する。

次に、ブロック518を参照すると、認証関数ACK（K_bs,
N_bs,K_ab）の値が、ＢからＳへ送られる。第２の2PKDP
は、ブロック519で終了し、ここで、サーバＳは、認証
関数ACK（K_bs,N_bs,K_ab）の値を再計算し、Ｂが送ったメ
ッセージの対応物と比較する。一致が生じると、Ｂの認
証がもたらされる。その後、２ユーザＡおよびＢは、2P
APによってお互いを認証することができる。ブロック52
0を参照すると、第１ユーザＡが、その名前とナンスN_ab
を第２ユーザＢに送る。Ａからのメッセージを受け取る
際に、少なくともグループ・キーK_ab、ナンスN_ab、新ナ
ンスN_baおよびメッセージ発信元の名前Ｂに基づく認証
関数AUTH（K_ab,N_ab,N_ba,B）の値が、ブロック521で第２
ユーザＢによって計算される。

次にブロック522を参照すると、認証関数AUTH（K_ab,N
_ab,N_ba,B）の値とナンスN_baが、ＢからＡへ送られる。
Ｂからのメッセージを受け取る際に、ブロック523で、
第１ユーザＡは、認証関数AUTH（K_ab,N_ab,N_ba,B）の値
を再計算し、Ｂが送ったメッセージの対応物と比較す
る。一致が生じると、Ｂの認証がもたらされる。その
後、この処理はブロック524に進み、第１ユーザが、両
方向認証を完了するため、少なくともグループ・キーK
_ab、ナンスN_abおよびナンスN_baに基づく認証関数ACK（K
_ab,N_ab,N_ba）の値を計算する。

次にブロック525を参照すると、認証関数ACK（K_ab,N
_ab,N_ba）の値が、ＡからＢへ送られる。この処理は、ブ
ロック526で終了するが、ここで、第２ユーザＢは、認
証関数ACK（K_ab,N_ab,N_ba）の値を再計算し、Ａが送った
メッセージの対応物と比較する。一致が生じると、Ａの
認証がもたらされる。

本明細書で提案される3PKDPに従って交換されるメッ
セージのリストを、第６図に示す。

サーバは、（サーバに加えて）ユーザの役割を演じる
こともできることに留意されたい。サーバは、サーバ自
体を含む（グループのメンバとして）グループとキーを
共有するためにこのプロトコルを使用することができ、
その場合、サーバは、それ自体へのグループ・キーの送
出と認証検証を省略し（これは不要である）、グループ
のサーバＳ以外のユーザから構成されるユーザのサブ・
グループのみにグループ・キーを送り、認証検証を行っ
て、プロトコル・サーバの役割とユーザの役割の両方を
演じることができる。特に、このことは、サーバと実際
のユーザだけが、それらが共有するキーを変更できるこ
とを保証する信頼性のある方法で、サーバとユーザによ
って共有されるキーのリフレッシュに使用されうる。グ
ループが、２ユーザのみからなる（たとえばＡとＳ）場
合、このプロトコルは、前に説明した2PKDPと同一にな
ることに留意されたい。

セキュリティの議論説明を単純明瞭にするために、第６図に示された3PKD
Pの例を参照する。

認証 2PKDPの場合と同様に、対処しなければならない最初
の問題は、認証プロトコルとしての3PKDPの強さであ
る。言い換えると、このプロトコルが、（A,S）、（B,
S）および、最後に（A,B）という対単位の認証を達成で
きるかどうかである。

プロトコルの末尾から始めて、K_abの安全な配布を仮
定すると、ＡとＢの間の認証プロトコルは、基礎となる
2PAPと同程度に安全である（実際に、これは2PKPであ
る）ことが簡単にわかる。

ＡとＳの間の2PKDPは、安全であり、したがって、Ｂ
とＳの間の2PKDPも安全である。しかし、3PKDPと２つの
関連しない2PKDPの行程との間の１つの重要な相違は、
Ｓによって生成されるナンスが、2PKDPの両方の行程で
同一である（すなわち、K_ab）ということである。各AUT
H式の計算に対等に接続された当事者の名前を明示的に
含める、すなわち、K_asを用いるAUTHにＢを含め、K_bsを
用いるAUTHにＡを含めることによって対処する。2PKDP
に完全に適合するための単純な方法の１つが、K_asを用
いるAUTHでK_abの代わりにK_abＡを使用し、同時にK_bs
を用いるAUTHでK_abの代わりにK_abＢを使用することで
あることに留意されたい。

キー配布 3PKDPでの非開示と独立の特性は、2PKDPから直接に継
承される。新キーの完全性は、別の問題である。両方の
当事者に同一のキーを配布することの問題点は、Ｓから
Ａへのメッセージ内のキーをマスクするのに使用される
式を、「内部」敵対者（たとえばＢ）が得ることができ
ることである。

MASK_a＝E_Kas（_sa）＝E_Kas（AUTH（K_as,N_as,K_ba,B））一見したところでは、この式を知ることによって、Ｂ
が無事にK_abを任意の選択された_abに変更できるよう
にみえる。それにもかかわらず、K_asを用いるAUTH式
（同一のメッセージに含まれる）によって、このアタッ
クが排除される。というのは、Ｂが、AUTH（K_as,N_as,K
_ab,B）をAUTH（K_as,N_as,_ab,B）に変更できないからで
ある。

関連する注意点として、3PKDPの結果としてＢが得る
１つの利益は、 _sa,E_Kas（_sa）という形式の平文−暗号文対の知識である。これは、Ｂ
がブルートフォース・アタックによってK_asを発見でき
る限り、脅威となる。しかし、そのために必要な平均的
な作業の量は、かなりな量になり、最初にAUTH式を破る
のに必要な量に確実に匹敵する。

多者キー配布プロトコル第７図は、本発明による、サーバＳから選択されたユ
ーザのグループ（この例ではＡ、ＢおよびＣ）への安全
な多者認証キー配布プロトコルの例で交換されるメッセ
ージのリストを示す図である。この例のプロトコルに
は、Ａと称する、通信を開始するイニシエータが存在す
る。このグループは、誰がその一部であるかがＡに判る
形で決定されると仮定する。また、グループの全ユーザ
は、プロトコル実行の前に対応する秘密のユーザ・キー
（Ａ−Ｓ間ではK_as、Ｂ−Ｓ間ではK_bs、Ｃ−Ｓ間ではK
_cs）を共有すると仮定する。前記ユーザ・キーのそれぞ
れは、サーバとユーザのうちで対応するユーザのみが知
っている。このプロトコルは、最初にグループ内の他者
（ユーザ）を識別するイニシエータＡによって開始され
る。

上記のプロトコル・メッセージを実施する実際の処理
の流れは、前の例の実施の処理の流れの詳細な説明を考
慮に入れるならば、第７図から簡単に導出できる。

最適化第６図に示されたプロトコル（第７図のプロトコルに
関しても同様の考察を行うことができる）は、2PKDPと2
PAPの直裁な組み合わせによって得られた。これは、合
計９個のメッセージと３個の両方向通信（Ａ−Ｂ、Ａ−
Ｓ、Ｂ−Ｓ）を必要とする。メッセージの数を減らし、
プロトコルを最適化するために、メッセージのいくつか
を交互に配置することができる。さらに、ＡとＢの両方
がＳと直接通信する必要はない。より現実的なシナリオ
では、Ｓとの通信のすべてが、ＡまたはＢのいずれかを
介して行われるはずである。

次に第８図を参照すると、コンパクト化された版の3P
KDPが示されている。この例では、Ａが実行を開始し、
その後、その情報をＢに渡し、Ｂは、Ａの情報をＢの情
報と共にＳに渡す。反対方向の移動では、サーバＳが、
すべての情報をＢに送り、Ｂは、その情報の一部をＡに
配布する。このプロトコルが、互いに通信するユーザの
グループ内の通信の順序に敏感でなくなるようにするた
めに、タグを使用し、その結果、えデータのストリーム
内のどの情報を使用すべきかが特定のユーザに判るよう
にする。

フロントページの続き (56)参考文献特開平５−344117（ＪＰ，Ａ) 椿山英樹，大橋正良，古賀敬一朗“安全な相互認証／暗号鍵配送方式およびＩＣカード実験システムへの実装”電子情報通信学会論文誌，Ｖｏｌ．Ｊ76−Ｄ− ▲Ｉ▼，Ｎｏ．12，（1993年12月），ｐｐ．695−697 椿山英樹，大橋正良，古賀敬一朗“相互認証／暗号鍵配送方式”電子情報通信学会論文誌，Ｖｏｌ．Ｊ76−Ｄ−▲Ｉ ▼，Ｎｏ．12，（1993年12月），ｐｐ. 698−701 (58)調査した分野(Int.Cl.⁷，ＤＢ名) G09C 1/00 - 5/00 H04K 1/00 - 3/00 H04L 9/00 ＩＮＳＰＥＣ（ＤＩＡＬＯＧ) ＪＩＣＳＴファイル（ＪＯＩＳ) ＷＰＩ（ＤＩＡＬＯＧ)

Claims

(57)【特許請求の範囲】

【請求項１】選択されたユーザ・コンピュータのグルー
プによって使用されるキーの、コンピュータ通信システ
ム内での安全な認証配布を提供する方法であって、キー
が、サーバ・コンピュータから前記サーバ・コンピュー
タ以外の前記グループのユーザ・コンピュータからなる
サブグループへ配布され、前記サブグループの各ユーザ
・コンピュータが、前記サーバ・コンピュータと秘密の
ユーザ・コンピュータ・キーを共有し、・ユーザ・コンピュータの名前（Ａ）、ユーザ・コンピ
ュータの予測不能な１回だけ使用される乱数（以下「ナ
ンス（N_as）」という）および前記ユーザ・コンピュー
タ以外の前記サブグループのユーザ・コンピュータの名
前（Ｂ）を前記サブグループの各ユーザ・コンピュータ
から前記システムの使用可能な経路を介して前記サーバ
・コンピュータに送るステップ（501、511）と、・前記サーバ・コンピュータが、前記グループの全ユー
ザ・コンピュータ用の新しい共通グループ・キー
（K_ab）を生成するステップ（502）と、・少なくとも前記ユーザ・コンピュータのキー
（K_as）、前記ユーザ・コンピュータのナンス（N_as）、
前記グループ・キー（K_ab）および、前記ユーザ・コン
ピュータ以外の前記グループのユーザ・コンピュータの
名前（Ｂ）に依存する第１関数の値を、前記サーバ・コ
ンピュータが前記サブグループの各ユーザ・コンピュー
タについて計算するステップ（503、512）と、・少なくとも前記ユーザ・コンピュータのキー
（K_as）、前記ユーザ・コンピュータの第１関数の値お
よび前記グループ・キー（K_ab）に依存する第２関数の
値を、前記サーバ・コンピュータが前記サブグループの
各ユーザ・コンピュータについて計算するステップ（50
4、513）と、・前記サーバ・コンピュータから前記システムの使用可
能な経路を介して前記サブグループの各ユーザ・コンピ
ュータへ、前記ユーザ・コンピュータの第１関数および
第２関数の値を送るステップ（505、514）と、・前記サブグループの各ユーザ・コンピュータが、前記
ユーザ・コンピュータのキーおよび前記ユーザ・コンピ
ュータの第１関数の値を使用して、前記ユーザ・コンピ
ュータの第２関数の値から前記グループ・キーを抽出す
るステップ（506、515）と、・前記サブグループの各ユーザ・コンピュータが、前記
ユーザ・コンピュータの第１関数の値を再計算し（50
7、516）、前記再計算された値が前記サーバ・コンピュ
ータによって受け取られた前記ユーザ・コンピュータの
第１関数の値と等しい場合に、前記抽出されたグループ
・キー（K_ab）が認証されたとみなすステップとを含む方法。
【請求項２】さらに、・少なくとも前記ユーザ・コンピュータのキー
（K_as）、前記ユーザ・コンピュータのナンス（N_as）お
よび前記グループ・キー（N_ab）に依存する第３関数の
値を、前記サブグループの各ユーザ・コンピュータが計
算するステップ（508、517）と、・前記サブグループの各ユーザ・コンピュータから前記
システムの使用可能な経路を介して前記サーバ・コンピ
ュータへ、前記ユーザ・コンピュータの第３関数の値を
送るステップ（509、518）と、・前記サーバ・コンピュータが、前記サブグループの各
ユーザ・コンピュータについて前記ユーザ・コンピュー
タの第３関数の値を再計算し（510、519）、前記再計算
された値が、前記ユーザ・コンピュータによって受け取
られた前記ユーザ・コンピュータの第３関数の値と等し
い場合に、前記サブグループの各ユーザ・コンピュータ
を認証するステップと、を含む、請求項１に記載の方法。
【請求項３】さらに、・前記サブグループの各ユーザ・コンピュータが、前記
ユーザ・コンピュータ間で前記グループ・キー（K_ab）
を用いて情報を暗号化し、交換することによって、前記
サブグループの他のユーザ・コンピュータに対して各ユ
ーザ・コンピュータ自体を認証するステップ（520ない
し526）を含む、請求項１または２に記載の方法。
【請求項４】前記第１、第２および第３の関数が、前記
ユーザ・コンピュータのキー（K_as）の下での暗号関数
である請求項１ないし３のいずれか一項に記載の方法。
【請求項５】前記第２関数が、少なくとも前記グループ
・キー（K_ab）との排他的論理和をとられた前記ユーザ
・コンピュータの第１関数の、前記ユーザ・コンピュー
タのキー（K_as）の下での暗号関数である請求項１ない
し４のいずれか一項に記載の方法。
【請求項６】前記グループ・キー（K_ab）が、前記サブ
グループの各ユーザ・コンピュータによって、前記ユー
ザ・コンピュータの暗号関数の値を再計算し、前記結果
と前記ユーザ・コンピュータの第２関数の値の排他的論
理和をとることによって抽出される請求項５に記載の方
法。
【請求項７】さらに、・前記サブグループの各ユーザ・コンピュータからサー
バ・コンピュータに送られる情報が、システムのユーザ
・コンピュータのうちの１ユーザ・コンピュータによっ
て集められ、その後、前記１ユーザ・コンピュータから
前記サーバ・コンピュータへ送られる請求項１ないし６のいずれか一項に記載の方法。
【請求項８】さらに、・システムを介して送られる情報が、宛先のユーザ・コ
ンピュータまたはサーバ・コンピュータを識別するタグ
によって識別される請求項１ないし７のいずれか一項に記載の方法。
【請求項９】選択されたユーザ・コンピュータ（101、1
02、103、109）のグループによって使用されるキーの安
全な認証配布を提供するコンピュータ通信システム（10
0）であって、キーが、サーバ・コンピュータ（109）か
ら前記サーバ・コンピュータ以外の前記グループのユー
ザ・コンピュータからなるユーザ・コンピュータ（10
1、102、103）のサブグループへ配布され、前記サブグ
ループの各ユーザ・コンピュータが、前記サーバ・コン
ピュータと秘密の対応するユーザ・コンピュータ・キー
を共有し、・ユーザ・コンピュータの名前、ユーザ・コンピュータ
の予測不能な１回だけ使用される乱数（以下「ナンス
（N_as）」という）および前記ユーザ・コンピュータ以
外の前記サブグループのユーザ・コンピュータの名前を
前記サブグループの各ユーザ・コンピュータから前記シ
ステムの使用可能な経路を介して前記サーバ・コンピュ
ータに送る（501、511）手段と、・前記サーバ・コンピュータが、前記グループの全ユー
ザ・コンピュータ用の新しい共通グループ・キーを生成
する（502）手段と、・少なくとも前記ユーザ・コンピュータのキー、前記ユ
ーザ・コンピュータのナンス、前記グループ・キーおよ
び、前記ユーザ・コンピュータ以外の前記グループのユ
ーザ・コンピュータの名前に依存する第１関数の値を、
前記サーバ・コンピュータが前記サブグループの各ユー
ザ・コンピュータについて計算する（503、512）手段
と、・少なくとも前記ユーザ・コンピュータのキー、前記ユ
ーザ・コンピュータの第１関数の値および前記グループ
・キーに依存する第２関数の値を、前記サーバ・コンピ
ュータが前記サブグループの各ユーザ・コンピュータに
ついて計算する（504、513）手段と、・前記サーバ・コンピュータから前記システムの使用可
能な経路を介して前記サブグループの各ユーザ・コンピ
ュータへ、前記ユーザ・コンピュータの第１関数および
第２関数の値を送る（505、514）手段と、・前記サブグループの各ユーザ・コンピュータが、前記
ユーザ・コンピュータのキーおよび前記ユーザ・コンピ
ュータの第１関数の値を使用して、前記ユーザ・コンピ
ュータの第２関数の値から前記グループ・キーを抽出す
る（506、515）手段と、・前記サブグループの各ユーザ・コンピュータが、前記
ユーザ・コンピュータの第１関数の値を再計算し（50
7、516）、前記再計算された値が前記サーバ・コンピュ
ータによって受け取られた前記ユーザ・コンピュータの
第１関数の値と等しい場合に、前記抽出されたグループ
・キーが認証されたとみなす手段とを含むコンピュータ通信システム。
【請求項１０】さらに、・少なくとも前記ユーザ・コンピュータのキー、前記ユ
ーザ・コンピュータのナンスおよび前記グループ・キー
に依存する第３関数の値を、前記サブグループの各ユー
ザ・コンピュータが計算する（508、517）手段と、・前記サブグループの各ユーザ・コンピュータから前記
システムの使用可能な経路を介して前記サーバ・コンピ
ュータへ、前記ユーザ・コンピュータの第３関数の値を
送る（509、518）手段と、・前記サーバ・コンピュータが、前記サブグループの各
ユーザ・コンピュータについて前記ユーザ・コンピュー
タの第３関数の値を再計算し（510、519）、前記再計算
された値が、前記ユーザ・コンピュータによって受け取
られた前記ユーザ・コンピュータの第３関数の値と等し
い場合に、前記サブグループの各ユーザ・コンピュータ
を認証する手段と、を含む、請求項９に記載のコンピュータ通信システム。