(57)【要約】【課題】  ネットワークにおいてノードを効率的に認証する。【解決手段】  あるサーバノードがあるクライアントノードを認証する方法は、前記クライアントノードがある秘密鍵ｓを取得し、ある証明書に含まれているユニークなハッシュコード値により前記クライアントノードのアイデンティティへバインドされる一方向ハッシュチェーンを、前記秘密鍵ｓを用いて生成するステップと、前記クライアントノードが、前記一方向ハッシュチェーンを用いて、公開鍵と秘密鍵とのｍ個のペアの数を求めるステップと、前記クライアントノードが、生成された公開鍵の一つを自己の証明書とともに前記サーバノードへ送信するステップと、前記サーバノードが、開示された公開鍵が前記クライアントノードの証明書に含まれているハッシュコード値へバインドされていることを検証して、前記クライアントノードを認証するステップとを含む。【選択図】  図１
2008113426.tif 000002
【特許請求の範囲】
【請求項１】
あるサーバノードがあるクライアントノードを認証する方法であって、
前記クライアントノードが秘密鍵ｓを取得し、証明書に含まれているユニークなハッシュコード値により前記クライアントノードのアイデンティティへバインドされる一方向ハッシュチェーンを、前記クライアントノードが前記秘密鍵ｓを用いて生成するステップと、
前記クライアントノードが、該クライアントノードの前記一方向ハッシュチェーンを用いて、公開鍵と秘密鍵とのｍ個のペアの数を求めるステップであって、ｍは整数であり、公開鍵と秘密鍵との前記ペアは、互いにバインドされるとともに、前記クライアントノードの前記証明書に含まれている前記ハッシュコード値にもバインドされるものである、ステップと、
前記クライアントノードが、生成された公開鍵の一つを自己の証明書とともに前記サーバノードへ送信するステップと、
前記サーバノードが、開示された公開鍵が前記クライアントノードの証明書に含まれているハッシュコード値へバインドされていることを検証することにより、前記クライアントノードを認証するステップと
を含む方法。
【請求項２】
公開鍵と秘密鍵の前記ペアの各々が、第１のハッシュ関数を用いて前記秘密鍵ｓに基づいて生成される第１の一方向ハッシュチェーンに基づいて生成されることにより、公開鍵と秘密鍵との前記ペアが互いにバインドされ、
前記公開鍵の基となる同じハッシュチェーンの１つ以上の要素を、前記クライアントノードが前記サーバノードへ送信するステップを含む請求項１に記載の方法。
【請求項３】
前記ハッシュチェーンに対して第２のハッシュ関数を適用することにより、公開鍵と秘密鍵との前記ペアがユニークな前記ハッシュコード値へバインドされる、請求項１または２に記載の方法。
【請求項４】
前記ハッシュコード値が、信頼できるサードパーティの秘密鍵を用いて生成されたシグネチャにより、前記クライアントノードの証明書に含まれている該クライアントノードのアイデンティティへバインドされる、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記クライアントノードが信頼できるサードパーティへ接続している初期化段階と、信頼できるサードパーティへの接続が必要ではない認証段階とを含み、
前記初期化段階が、
クライアントノードのクロックを、信頼できるサードパーティのクロックと同期を取るステップと、
チェック値として
【数１】
2008113426.tif 000037
を求めるステップであって、ｆは暗号化のための前記第１の一方向ハッシュ関数であり、ｈは前記第２の一方向ハッシュ関数である、ステップと、
前記信頼できるサードパーティが、前記クライアントノードのアイデンティティを前記チェック値へバインドする証明書を要求するステップであって、前記証明書が基準となる時間値を含む、ステップと、
時間を長さＬの均等なｍ個のインターバルに分割し、前記クライアントノードの一方向ハッシュチェーンの要素を用いて生成された異なる鍵を前記インターバルの各々へそれぞれ割り当てるステップであって、前記一方向ハッシュチェーンが、前記ハッシュ関数ｆをｓに繰返し適用することに基づいて生成されるものであり、前記クライアントノードがタイムインターバルＴi（０≦ｉ＜ｍ）において秘密鍵として
【数２】
2008113426.tif 000038
を使用し、対応する公開鍵として
【数３】
2008113426.tif 000039
を使用するものである、ステップと
を含み、
前記認証段階が、
前記クライアントノードが前記サーバノードへ前記チェック値を送信するステップと、
現在のタイムインターバルに割り当てられている公開鍵として
【数４】
2008113426.tif 000040
を前記クライアントノードが前記サーバノードへ送信するステップと、
ｆw+1（ｓ）＝ｆm-i（ｓ）と前記証明書とを前記クライアントノードが前記サーバノードへ送信するステップと、
前記サーバノードが、これらの値を使用して、
【数５】
2008113426.tif 000041
を計算し、ν＝ｈ（ν*）であることをチェックすることにより前記クライアントノードのアイデンティティを検証するステップと
を含む、
請求項１〜４のいずれか一項に記載の方法。
【請求項６】
Ｇ＝（Ｇ，＊）が位数ｑの有限巡回群であり、ｇ∈ＧがＧの生成元であり、ｆが集合｛０，１，…，ｑ−１｝をそれ自体にマッピングする暗号化のための（一方向）ハッシュ関数である、請求項５に記載の方法。
【請求項７】
前記初期化段階が、
Ｇとｇとｆとｍと信頼できるサードパーティの公開鍵ＫTTPと一方向ハッシュ関数であるｈとのうちの１つ以上を前記サーバノードへ配信するステップと、
自己のアイデンティティを証明しようとするクライアントノードに対して、前記チェック値と、
【数６】
2008113426.tif 000042
に基づく証明書とを計算するステップであって、ＩＤは前記ノードの識別子であり、ｔ0は基準時間または証明書の発行時間であり、Ｌは公開鍵と秘密鍵とのペアが有効であるタイムインターバルの長さであり、
【数７】
2008113426.tif 000043
は、証明書のフィールド内の秘密鍵
【数８】
2008113426.tif 000044
を用いて信頼できるサードパーティが生成したシグネチャである、ステップと
を含む、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
同期の取れたクロックの間の最大のクロックドリフトを定めることによりクロックのドリフトが考慮され、
認証中に２つ以上の鍵が開示されているか否かにより、起こり得るクロックのドリフトが考慮される、請求項２〜７のいずれか一項に記載の方法。
【請求項９】
前記サーバノードが前記クライアントノードを認証したやり方と同様のやり方で、前記クライアントノードが前記サーバノードを認証するステップを含む請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
【数９】
2008113426.tif 000045
を計算することにより、前記クライアントノードと前記サーバノードとの間にセッション鍵を確立するステップをさらに含み、ここで、
【数１０】
2008113426.tif 000046
は、前記クライアントノードが前記サーバノードへ送信する公開鍵であり、Ｋyは前記サーバノードの秘密鍵であり、
【数１１】
2008113426.tif 000047
は、前記サーバノードが前記クライアントノードへ送信する公開鍵であり、Ｋwは前記クライアントノードの秘密鍵である、請求項９に記載の方法。
【請求項１１】
あるアドホックネットワークにおいてサーバノードがクライアントノードを認証するための装置であって、
前記クライアントノードが秘密鍵ｓを取得して、証明書に含まれているユニークなハッシュコード値により前記クライアントノードのアイデンティティへバインドされる一方向ハッシュチェーンを、前記クライアントノードが前記秘密鍵ｓを用いて生成するためのモジュールと、
前記クライアントノードが、該クライアントノードの前記一方向ハッシュチェーンを用いて、公開鍵と秘密鍵とのｍ個のペアの数を求めるためのモジュールであって、ｍは整数であり、公開鍵と秘密鍵との前記ペアは、互いにバインドされるとともに、前記クライアントノードの前記証明書に含まれている前記ハッシュコード値にもバインドされるものである、モジュールと、
前記クライアントノードが、生成された公開鍵の一つを自己の証明書とともに前記サーバノードへ送信するためのモジュールと、
前記サーバノードが、開示された公開鍵が前記クライアントノードの証明書に含まれているハッシュコード値へバインドされていることを検証することにより、前記クライアントノードを認証するためのモジュールと
を備える装置。
【請求項１２】
公開鍵と秘密鍵の前記ペアの各々が、第１の一方向ハッシュ関数を用いて前記秘密鍵ｓに基づいて生成される第１の一方向ハッシュチェーンに基づいて生成されることにより、公開鍵と秘密鍵との前記ペアが互いにバインドされ、
前記公開鍵の基となる同じハッシュチェーンの１つ以上の要素を、前記クライアントノードが前記サーバノードへ送信するためのモジュールを備える請求項１１に記載の装置。
【請求項１３】
前記ハッシュチェーンに対して第２のハッシュ関数を適用することにより、公開鍵と秘密鍵との前記ペアがユニークな前記ハッシュコード値へバインドされる、請求項１１または１２に記載の装置。
【請求項１４】
前記ハッシュコード値が、信頼できるサードパーティの秘密鍵を用いて生成されたシグネチャにより、前記クライアントノードの証明書に含まれている該クライアントノードのアイデンティティへバインドされる、請求項１１〜１３のいずれか一項に記載の装置。
【請求項１５】
前記クライアントノードが信頼できるサードパーティへ接続している間に初期化を実行する初期化モジュールと、
信頼できるサードパーティへの接続を必要としない認証モジュールと
を備え、
前記初期化モジュールが、
クライアントノードのクロックを、信頼できるサードパーティのクロックと同期を取るステップと、
チェック値として
【数１２】
2008113426.tif 000048
を求めるステップであって、ｆは暗号化のための前記第１の一方向ハッシュ関数であり、ｈは前記第２の一方向ハッシュ関数である、ステップと、
前記信頼できるサードパーティが、前記クライアントノードのアイデンティティを前記チェック値へバインドする証明書を要求するステップであって、前記証明書が基準時間値を含む、ステップと、
時間を長さＬの均等なｍ個のインターバルに分割して、前記クライアントノードの一方向ハッシュチェーンの要素を用いて生成された異なる鍵を前記インターバルの各々へそれぞれ割り当てるステップであって、前記一方向ハッシュチェーンが前記ハッシュ関数ｆをｓに繰返し適用することに基づいて生成されるものであり、前記クライアントノードが、タイムインターバルＴi（０≦ｉ＜ｍ）において秘密鍵として
【数１３】
2008113426.tif 000049
を使用し、対応する公開鍵として
【数１４】
2008113426.tif 000050
を使用する、ステップと
を実行するものであり、
前記認証モジュールが、
前記クライアントノードが前記サーバノードへ前記チェック値を送信するためのモジュールと、
現在のタイムインターバルに割り当てられた公開鍵として
【数１５】
2008113426.tif 000051
を前記クライアントノードが前記サーバノードへ送信するためのモジュールと、
ｆw+1（ｓ）＝ｆm-i（ｓ）と前記証明書とを前記クライアントノードが前記サーバノードへ送信するためのモジュールと、
前記サーバノードが、これらの値を使用して、
【数１６】
2008113426.tif 000052
を計算し、ν＝ｈ（ν*）であることをチェックすることにより前記クライアントノードのアイデンティティを検証するためのモジュールと
を備える、請求項１１〜１４のいずれか一項に記載の装置。
【請求項１６】
Ｇ＝（Ｇ，＊）が位数ｑの有限巡回群であり、ｇ∈ＧがＧの生成元であり、ｆが集合｛０，１，…，ｑ−１｝をそれ自体にマッピングする暗号化のための（一方向）ハッシュ関数である、請求項１５に記載の装置。
【請求項１７】
前記初期化モジュールが、
Ｇとｇとｆとｍと信頼できるサードパーティの公開鍵ＫTTPと一方向ハッシュ関数であるｈとのうちの１つ以上を前記サーバノードへ配信するステップと、
自己のアイデンティティを証明しようとするクライアントノードに対して、前記チェック値と、
【数１７】
2008113426.tif 000053
に基づく証明書とを計算するステップであって、ＩＤは前記ノードの識別子であり、ｔ0は基準時間または証明書の発行時間であり、Ｌは公開鍵と秘密鍵とのペアが有効であるタイムインターバルの長さであり、
【数１８】
2008113426.tif 000054
は、証明書のフィールド内の秘密鍵
【数１９】
2008113426.tif 000055
を用いて信頼できるサードパーティが生成したシグネチャである、ステップと
を実行する、請求項１１〜１６のいずれか一項に記載の装置。
【請求項１８】
同期の取れたクロックの間の最大のクロックドリフトを定めることによりクロックのドリフトを考慮して、
認証中に２つ以上の鍵が開示されているか否かにより、起こり得るクロックのドリフトを考慮するためのモジュールをさらに備える請求項１１〜１７のいずれか一項に記載の装置。
【請求項１９】
前記サーバノードが前記クライアントノードを認証したやり方と同様のやり方で、前記クライアントノードが前記サーバノードを認証するためのモジュールをさらに備える請求項１１〜１８のいずれか一項に記載の装置。
【請求項２０】
【数２０】
2008113426.tif 000056
を計算することにより、前記クライアントノードと前記サーバノードとの間にセッション鍵を確立するためのモジュールをさらに備え、ここで、
【数２１】
2008113426.tif 000057
は、前記クライアントノードが前記サーバノードへ送信する公開鍵であり、Ｋyは前記サーバノードの秘密鍵であり、
【数２２】
2008113426.tif 000058
は、前記サーバノードが前記クライアントノードへ送信する公開鍵であり、Ｋwは前記クライアントノードの秘密鍵である、請求項１９に記載の装置。
【請求項２１】
あるアドホックネットワークにおいて認証を行うためのコンピュータプログラムであって、請求項１〜１０のいずれか一項に記載の方法をコンピュータに実行させるコンピュータプログラムコードを含むコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、認証方法および装置に関し、具体的にはアドホックネットワークまたはインフラストラクチャレスネットワークにおける認証方法および装置に関する。
【背景技術】
【０００２】
あるサーバがあるクライアントとのセキュア通信チャネルを確立しようとする場合、サーバは、対象のクライアントと確実に通信するために、そのクライアントを認証する必要があり、かつ対象のクライアントだけがその秘密鍵の値を認識できるようにセッション鍵を確立する必要がある。ここで、クライアントおよびサーバという用語はそれぞれ、認証されるエンティティおよび認証を行うエンティティを指すものとする。これらの用語は、クライアント−サーバ型の通信を定義するものと限定的に解釈することを目的とするものではない。以下に述べる本発明の解決策は、いずれのタイプの通信（クライアント−サーバ、ピアツーピア等）にも適用することができる。
【０００３】
セキュア通信チャネルの認証および確立を可能にする方法が２つある。すなわち、公開鍵証明書を使用するか、あるいは事前共有鍵（ｐｒｅｓｈａｒｅｄ  ｋｅｙ）を使用することができる。しかし、これらの解決策は、証明書の失効状態に関する最新の情報と秘密鍵とを配信することができるオンラインで常に到達可能な信頼できるサードパーティ（ｔｒｕｓｔｅｄ  ｔｈｉｒｄ  ｐａｒｔｙ：ＴＴＰ）か、または事前に秘密鍵を共有しているクライアントおよびサーバかのいずれかを必要とする。アドホックネットワークにおいては、ＴＴＰへ常に到達できることと、事前に秘密鍵を共有しているエンティティだけが存在することとを保証する固定的なインフラストラクチャがない。これは、サーバがクライアントとの秘密の通信を確立することを妨げる。しかし、用途の多くは、自然災害時（地震等）における救助隊同士の間の認証メッセージおよび機密メッセージの交換や、展示会でのビジネスパートナー間の機密メッセージの交換、モバイル装置間のマルチメディアリソースのリーガルな配信等のように、アドホックネットワークにおいてもデータの機密性を要件とする。
【０００４】
アドホックネットワークにおいてセキュア通信チャネルを確立するために解決すべき２つの根本的な問題は、次の通りである。１つ目は、サーバがそれまでに通信したことのないクライアントをいかにして認証できるかである。２つ目は、公開鍵証明書または事前に共有した秘密鍵を使用せずにいかにしてセッション鍵を確立できるかである。
【０００５】
認証のための既存の解決策は、ハッシュチェーンを使用する。既存の解決策では、クライアントが一方向ハッシュチェーン（ｏｎｅ−ｗａｙ  ｈａｓｈ  ｃｈａｉｎ）を使用してアイデンティティをサーバへ示すときに、そのクライアントはそのチェーンに含まれる値を公開しなければならない。このため、これらの値は、機密データを暗号化するために後で使用することができない。これが、秘密鍵を確立するために一方向ハッシュチェーンを使用できず、認証を実行するためにだけ使用される理由である。
【０００６】
一方向ハッシュチェーンの使用を、図１に模式的に示している。ここで、クライアントはＫmをサーバへ送信する。サーバによる第ｉ番目の認証のために、クライアントはＫm-iを送信する。次いでサーバは、ｆi（Ｋm-i）＝Ｋmであることをチェックする。一方向ハッシュチェーンは逆算（ｒｅｖｅｒｔ）が難しいので、一方向ハッシュチェーンを生成するために使用される秘密値ｓを知っているクライアントだけが、妥当な値をサーバへ送信することができる。
【０００７】
したがって、安全な通信を確立するために一方向ハッシュチェーンをどのように使用するかということに対する解決策を提供するために従来技術で提起された問題は以下の通りである。
１つ目は、その要素の公開を可能にする一方向ハッシュチェーンを、これらの公開された要素をコンプロマイズ（ｃｏｍｐｒｏｍｉｓｅ）することなく、いかに定義するかである。
２つ目は、公開鍵証明書を使用せずにこれらの要素を生成したクライアントのアイデンティティをいかにして検証するかである。
３つ目は、秘密鍵を得るためにこれらの公開された要素をいかに使用するかである。
【０００８】
【非特許文献１】Y.-R. Tsai and S.-J. Wang, "Routing security and authentication mechanism for mobile ad hoc networks," in "Proceedings of the IEEE 60th Vehicular Technology Conference, 2004"
【非特許文献２】「A. Perrig, R. Canneti, J. Tygar, and D. Song, "The TESLA broadcast authentication protocol," CryptoBytes, vol. 5, no. 2, pp. 2？13, 2002」
【非特許文献３】「L. Lamport, "Password authentication with insecure communication," Comm. ACM, vol. 24, no. 11, pp. 770？772, 1981」
【非特許文献４】「Perrig, D. Song, R. Canetti, J. D. Tygar, and B. Briscoe, "Timed Efficient Stream Loss-Tolerant Authentication (TESLA): Multicast Source Authentication Transform Introduction," RFC 4082 (Informational), June 2005」
【非特許文献５】「A. Weimerskirch and D. Westhoff, "Identity certified authentication for ad？hoc networks," in SASN '03: Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks. New York, NY, USA: ACM Press, 2003, pp. 33？40」
【発明の開示】
【発明が解決しようとする課題】
【０００９】
より一般的に言えば、モバイルアドホックネットワークなどのように、信頼できるサードパーティへの接続ができない環境で、いかにしてサーバがクライアントを認証するかということを本発明の課題とみなすことができる。
【００１０】
以下に、従来技術のアプローチを簡単に示す。
【００１１】
非特許文献１において、同一グループのエンティティは、グループ鍵および対となる秘密鍵（ｐａｉｒｗｉｓｅ  ｓｅｃｒｅｔ  ｋｅｙ）をグループ内の各メンバと共有する。これらの鍵はそれぞれ、グループのメンバであることを証明し、かつグループメンバのアイデンティティを証明するために使用される。しかし、インフラストラクチャレスネットワークまたはアドホックネットワークでは、秘密鍵を事前に共有するエンティティが常に存在することを保証するものは何もない。初めて通信するエンティティが共有鍵を確立することを可能にする解決策は提案されていないので、この解決策はインフラストラクチャレスネットワークまたはアドホックネットワークにおいて常に使用できるわけではない。
【００１２】
ＴＥＳＬＡブロードキャスト認証プロトコル（非特許文献２参照）は、一方向ハッシュチェーン（非特許文献３参照）を用いて、ブロードキャストされたいくつかのパケットの送信元を認証する。しかし、この解決策には、エンティティの認証をブートストラップする手段がない。そして、これをセッションのセットアップ時に通常のデータ認証システムによって提供しなければならない（非特許文献４参照）。さらに、これはセキュア通信チャネルの確立をサポートしていない。
【００１３】
非特許文献５には、あるエンティティＡが、固定的なネットワーク内の信頼できるサードパーティＴＴＰが発行したいくつかの証明書を有することが記載されている。この証明書の発行は、Ａが固定的なネットワークと接続している間に行なわれる。各証明書は、Ａのアイデンティティを一方向ハッシュチェーンへバインドする。さらに詳しく言えば、Ａはチェーンのアンカーである秘密鍵ｘ0を選択する。セキュア暗号化ハッシュ関数（secure cryptographic hash-function）をｈとし、システムパラメータをｍ（ｍ≧１）とし、ｘi＝ｈi（ｘ0）（ｉ≧０）とすると、Ａのチェーンに基づいて最後に生成されたハッシュ値ｘ2mが、Ａの証明書に含まれる。その証明書は、発行時刻およびあるランダムシードをも含んでいる。次いでＡは、公開された値Ｌを用いて時間を等しい長さＬのインターバルに分割し、チェーンを用いてその一方向ハッシュチェーンに基づく２つの鍵を各インターバルへ割り当てる。時間ｔ＝ｉＬと時間ｔ＝（ｉ＋１）Ｌとの間のインターバルＴi（０≦ｉ＜ｍ）において、Ａは、Ｂが認証するそのチェーンに基づく２つの値ｘ2m-2i-1およびｘ2m-2i-2を用いる。Ｂは、最初に証明書を検証してｘ2mについての信頼できるコピーを取得し、次いでハッシュ値に応じて適切な回数だけハッシュ関数をイタレートし、その結果を値ｘ2mと比較することにより、これらの２つの値が正しいことを検証することができる。しかし、ひとたびｘ2m-2i-1およびｘ2m-2i-2が開示されると、アタッカーがＡになりすまして、あるエンティティＣに対してそれらをリプレイできるようになる。このリスクを低減するために、ＢはＡに対して特定のシード値とともに証明書を使用するように要求しなければならない。その結果、アタッカーは、以前に使用した証明書を提示するように検証エンティティから要求され、それが別の検証ノードがＡに対して既に要求したシード値を含む場合にのみ、以前に開示された鍵をリプレイすることができる。しかし、エンティティの認証を行うためには鍵を開示しなければならないので、それらを使用してセキュア通信チャネルを確立することはできない。これは、ＡおよびＢが認証されたセッション鍵を確立できるようにするために、エンティティを認証するための追加的な解決策を使用しなければならないことを意味している。
【課題を解決するための手段】
【００１４】
一実施形態によれば、アドホックネットワークにおいてあるサーバノードがあるクライアントノードを認証する方法であって、
前記クライアントノードが秘密鍵ｓを取得し、証明書に含まれているユニークなハッシュコード値により前記クライアントノードのアイデンティティへバインドされる一方向ハッシュチェーンを、前記クライアントノードが前記秘密鍵ｓを用いて生成するステップと、
前記クライアントノードが、該クライアントノードの前記一方向ハッシュチェーンを用いて、公開鍵と秘密鍵とのｍ個のペアの数を求めるステップであって、ｍは整数であり、公開鍵と秘密鍵との前記ペアは、互いにバインドされるとともに、前記クライアントノードの前記証明書に含まれている前記ハッシュコード値にもバインドされるものである、ステップと、
前記クライアントノードが、生成された公開鍵の一つを自己の証明書とともに前記サーバノードへ送信するステップと、
前記サーバノードが、開示された公開鍵が前記クライアントノードの証明書に含まれているハッシュコード値へバインドされていることを検証することにより、前記クライアントノードを認証するステップと
を含む方法が提供される。
【００１５】
提供される解決策においては、各クライアント、例えばＡは、ある秘密鍵ｓを選択（または何らかの形で取得）し、それを使用して一方向ハッシュチェーンを生成する。そのチェーンは、ある証明書に含まれるユニークなハッシュコード値によりＡのアイデンティティへバインドされる。クライアントはそのチェーンを使用して、公開鍵と秘密鍵とのペアを複数求める。これらの公開鍵と秘密鍵とのペアは相互に、かつＡの証明書に含まれるハッシュコード値へバインドされる。次いで、サーバＢが認証するために、クライアントは、その公開鍵の１つをその証明書とともにＢへ送信しなければならない。Ｂは、開示された公開鍵がＡの証明書に含まれるハッシュコードへバインドされていることを検証することによって、Ａを認証することができる。
【００１６】
ここで、「互いにバインドされる」公開鍵と秘密鍵とのペアは、ハッシュチェーンの要素に基づいて公開鍵と秘密鍵とのペアを求めることにより得られることに言及しておきたい。これは、それらが互いに独立したものではなく、ある程度「互いに依存しており」、したがって「互いにバインドされている」とみなすことができることを保証する。したがって、クライアントの証明書に含まれるハッシュコードもハッシュチェーンに基づいている場合、このハッシュコードも「公開鍵と秘密鍵とのペアへバインドされている」とみなすことができる。
【００１７】
一実施形態によれば、公開鍵と秘密鍵の前記ペアの各々が、第１のハッシュ関数を用いて前記秘密鍵ｓに基づいて生成される第１の一方向ハッシュチェーンに基づいて生成されることにより、公開鍵と秘密鍵との前記ペアが互いにバインドされ、
前記方法は、前記公開鍵の基となる同じハッシュチェーンの１つ以上の要素を、前記クライアントノードが前記サーバノードへ送信するステップを含む。これにより、単一の秘密値ｓに基づいて複数の鍵を生成することができるようになる。さらに、クライアントがサーバへ送信する公開鍵の基になる同じハッシュチェーンの１つ以上の要素を用いてチェックできるようになる。
【００１８】
一実施形態によれば、前記一方向ハッシュチェーンに対して第２のハッシュ関数を適用することにより、公開鍵と秘密鍵との前記ペアが、証明書に含まれているユニークな前記ハッシュコード値へバインドされる。これにより、前記証明書に単一のハッシュ値だけを格納することが必要となる。
【００１９】
一実施形態によれば、前記ハッシュコード値は、信頼できるサードパーティの秘密鍵を用いて生成されたシグネチャにより、前記クライアントノードの証明書に含まれている該クライアントノードのアイデンティティへバインドされる。これにより最初に、提案されたスキームの初期化の段階で信頼関係が生まれる。
【００２０】
一実施形態によれば、前記方法は、前記クライアントノードが信頼できるサードパーティへ接続している初期化段階と、信頼できるサードパーティへの接続が必要ではない認証段階とを含むものであり、
前記初期化段階が、
クライアントのクロックを、信頼できるサードパーティのクロックと同期させるステップと、
チェック値として
【数１】
2008113426.tif 000003
を求めるステップであって、ｆは暗号化のための前記第１の一方向ハッシュ関数であり、ｈは前記第２の一方向ハッシュ関数である、ステップと、
前記信頼できるサードパーティが、前記クライアントのアイデンティティを前記チェック値へバインドする証明書を要求するステップであって、前記証明書が基準時間値（reference time value）を含む、ステップと、
時間を長さＬの均等なｍ個のインターバルに分割し、前記インターバルの各々にそれぞれ異なる鍵を割り当てるステップであって、前記鍵が前記ハッシュ関数ｆをｓに繰返し適用することに基づいて生成されるものであり、前記クライアントノードがタイムインターバルＴi（０≦ｉ＜ｍ）において秘密鍵として
【数２】
2008113426.tif 000004
を使用し、対応する公開鍵として
【数３】
2008113426.tif 000005
を使用するものである、ステップと
を含み、
前記認証段階が、
前記クライアントが前記サーバへ前記チェック値を送信するステップと、
現在のタイムインターバルに割り当てられた公開鍵として
【数４】
2008113426.tif 000006
を前記クライアントが前記サーバへ送信するステップと、
ｆw+1（ｓ）＝ｆm-i（ｓ）と前記証明書とを前記クライアントが前記サーバへ送信するステップと、
前記サーバノードが、これらの値を使用して、
【数５】
2008113426.tif 000007
を計算し、ν＝ｈ（ν*）であることをチェックすることにより前記クライアントノードのアイデンティティを検証するステップと
を含む。
【００２１】
このようにして、認証を行うためのサードパーティを必要とせずに、認証が可能となる。
【００２２】
一実施形態によれば、Ｇ＝（Ｇ，＊）は位数（order）ｑの有限巡回群（finite cyclic group）であり、ｇ∈ＧはＧの生成元（generator）であり、ｆは集合｛０，１，…，ｑ−１｝をそれ自体にマッピングする暗号化のための（一方向）ハッシュ関数である。
【００２３】
一実施形態によれば、前記初期化は、
Ｇとｇとｆとｍと信頼できるサードパーティの公開鍵ＫTTPと一方向ハッシュ関数であるｈとのうちの１つ以上を前記サーバノードへ配信するステップと、
自己のアイデンティティを証明しようとするクライアントノードに対して、前記チェック値と、
【数６】
2008113426.tif 000008
に基づく証明書とを計算するステップであって、ＩＤは前記ノードの識別子であり、ｔ0は基準時間（reference time）または証明書の発行時間であり、Ｌは公開鍵と秘密鍵とのペアが有効であるタイムインターバルの長さであり、
【数７】
2008113426.tif 000009
は、証明書のフィールド内の秘密鍵
【数８】
2008113426.tif 000010
を用いて信頼できるサードパーティが生成したシグネチャである、ステップと
を含む。
【００２４】
このようにして、異なる瞬間に異なる鍵が用いられる。これらは受信されるとすぐに認証される。ある時間における鍵のコンプロマイズは、将来使用される鍵に関する何らの情報を与えない。したがって、過去にある鍵をコンプロマイズさせたアタッカーが、その後利用者になりすますことはできない。
【００２５】
一実施形態によれば、同期の取れたクロックの間の最大のクロックドリフトを定めることによりクロックのドリフトが考慮され、認証中に２つ以上の鍵が開示されているか否かにより、起こり得るクロックのドリフトが考慮される。これにより、不完全な同期またはクロックのドリフトを考慮できる。
【００２６】
一実施形態によれば、前記方法は、前記サーバノードが前記クライアントノードを認証したやり方と同様のやり方で、前記クライアントノードが前記サーバノードを認証するステップを含む。これにより相互認証が可能となる。
【００２７】
一実施形態によれば、前記方法は、
【数９】
2008113426.tif 000011
を計算することにより、前記クライアントノードと前記サーバノードとの間にセッション鍵を確立するステップをさらに含み、ここで
【数１０】
2008113426.tif 000012
は、前記クライアントが前記サーバへ送信する公開鍵であり、Ｋyは前記サーバの秘密鍵である。
【００２８】
これにより、事前に秘密鍵を共有していないクライアントおよびサーバが、公開鍵証明書を使用せずに、一方向ハッシュチェーンを使用することにより、認証されたセッション鍵を確立することを可能にする解決策が提供される。
【００２９】
一実施形態によれば、あるアドホックネットワークにおいてサーバノードがクライアントノードを認証するための装置であって、
前記クライアントノードが秘密鍵ｓを取得して、証明書に含まれているユニークなハッシュコード値により前記クライアントノードのアイデンティティへバインドされる一方向ハッシュチェーンを、前記クライアントノードが前記秘密鍵ｓを用いて生成するためのモジュールと、
前記クライアントノードが、該クライアントノードの前記一方向ハッシュチェーンを用いて、公開鍵と秘密鍵とのｍ個のペアの数を求めるためのモジュールであって、ｍは整数であり、公開鍵と秘密鍵との前記ペアは、互いにバインドされるとともに、前記クライアントノードの前記証明書に含まれている前記ハッシュコード値にもバインドされるものである、モジュールと、
前記クライアントノードが、生成された公開鍵の一つを自己の証明書とともに前記サーバノードへ送信するためのモジュールと、
前記サーバノードが、開示された公開鍵が前記クライアントノードの証明書に含まれているハッシュコード値へバインドされていることを検証することにより、前記クライアントノードを認証するためのモジュールと
を備える装置が提供される。
【００３０】
一実施形態によれば、前記装置は、
前記クライアントノードが信頼できるサードパーティへ接続している間に初期化を実行する初期化モジュールと、
信頼できるサードパーティへの接続を必要としない認証モジュールと
を備えており、
前記初期化モジュールが、
クライアントのクロックを、信頼できるサードパーティのクロックと同期化するステップと、
チェック値として
【数１１】
2008113426.tif 000013
を求めるステップであって、ｆは暗号化のための前記第１の一方向ハッシュ関数であり、ｈは前記第２の一方向ハッシュ関数である、ステップと、
前記信頼できるサードパーティが、前記クライアントのアイデンティティを前記チェック値へバインドする証明書を要求するステップであって、前記証明書が基準時間値（reference time value）を含む、ステップと、
時間を長さＬの均等なｍ個のインターバルに分割し、前記インターバルの各々にそれぞれ異なる鍵を割り当てるステップであって、前記鍵が前記ハッシュ関数ｆをｓに繰返し適用することに基づいて生成されるものであり、前記クライアントノードが、タイムインターバルＴi（０≦ｉ＜ｍ）において秘密鍵として
【数１２】
2008113426.tif 000014
を使用し、対応する公開鍵として
【数１３】
2008113426.tif 000015
を使用する、ステップと
を実行するものであり、
前記認証モジュールが、
前記クライアントが前記サーバへ前記チェック値を送信するためのモジュールと、
現在のタイムインターバルに割り当てられた公開鍵として
【数１４】
2008113426.tif 000016
を前記クライアントが前記サーバへ送信するためのモジュールと、
ｆw+1（ｓ）＝ｆm-i（ｓ）と前記証明書とを前記クライアントが前記サーバへ送信するためのモジュールと、
前記サーバノードが、これらの値を使用して、
【数１５】
2008113426.tif 000017
を計算し、ν＝ｈ（ν*）であることをチェックすることにより前記クライアントノードのアイデンティティを検証するためのモジュールと
を備える。
【００３１】
一実施形態によれば、前記装置は、同期の取れたクロックの間の最大のクロックドリフトを定めることによりクロックのドリフトを考慮して、認証中に２つ以上の鍵が開示されているか否かにより、起こり得るクロックのドリフトを考慮するためのモジュールを備える。
【００３２】
一実施形態によれば、前記装置は、前記サーバノードが前記クライアントノードを認証したやり方と同様のやり方で、前記クライアントノードが前記サーバノードを認証するためのモジュールをさらに備える。
【００３３】
一実施形態によれば、前記装置は、
【数１６】
2008113426.tif 000018
を計算することにより、前記クライアントノードと前記サーバノードとの間にセッション鍵を確立するためのモジュールをさらに備え、ここで
【数１７】
2008113426.tif 000019
は、前記クライアントが前記サーバへ送信する公開鍵であり、Ｋyは前記サーバの秘密鍵である。
【００３４】
一実施形態によれば、アドホックネットワークにおいて認証を実行するためのコンピュータプログラムであって、本発明の一実施形態に基づく方法をコンピュータに実行させるコンピュータプログラムコードを含むコンピュータプログラムが提供される。
【００３５】
提案された認証スキームは、承認（authorization）やインテグリティ等のような他のセキュリティサービスを提供するために使用することができる。これにより、アドホックネットワークにおいてリソース（例えばマルチメディアファイル）の安全な交換などが確実にできるようになる。今日、携帯電話機はＭＰ３プレーヤでもある。したがって携帯電話機を使用して、インフラストラクチャにアクセスできない場合でも配信できるように、マルチメディアファイルを配信するための（リーガル）プラットフォームを拡張することができる。提案された認証スキームは、例えば展示会でのビジネスパートナー間の秘密の通信や、地震などの自然災害時において救助隊が認証に関する機密データの交換などをできるようにするためにも使用することができる。
【発明を実施するための最良の形態】
【００３６】
以下、本発明の詳細な実施形態について説明する。
【００３７】
本発明の実施形態に基づく認証スキームを使用する前に、全ての当事者がシステムパラメータについて以下の通りに合意する必要がある。
まず、Ｇ＝（Ｇ，＊）は、位数（order）ｑ（ｑは大きい）の有限巡回群（finite cyclic group）であり、ｇ∈ＧはＧの生成元（generator）であり、ｇについてＧにおける離散対数（discrete logarithm）を計算することはコンピュータ的に不可能であることを前提とする。例えば、Ｇは、大きい素数（large prime）ｐに対する
【数１８】
2008113426.tif 000020
の大きな乗法部分群（multiplicative subgroup）とすることができる。ここで、ｑは大きな素数であって、ｐ−１の約数（dividing）である。あるいは、Ｇを、（通常加法的に記述される）楕円曲線上の点群とすることができる。
次に、ｈは、任意の長さのバイナリ列を固定長（例えば？、？の典型的な値は２２４である）の列にマッピングする暗号化のための（一方向）ハッシュ関数である。
そして、ｆは、集合｛０，１，…，ｑ−１｝をそれ自体にマッピングする暗号化のための（一方向）ハッシュ関数である。実際には、ｆは、例えばｈから求められる。
また、ｍ≧１は、クライアントが利用できる鍵のペアの個数を定める正の整数である。
【００３８】
以下、本発明の実施形態に基づく認証スキームについて説明する。
【００３９】
スキームが初期化されると、クライアントは秘密値ｓ∈｛０，１，…，ｑ−１｝を選択する。次いでクライアントは、チェック値νを
【数１９】
2008113426.tif 000021
を用いて生成する。νは、何らかの信頼できるサードパーティ（ＴＴＰ）、例えばノードが加入しているネットワークのオペレータが署名した証明書に含まれている。この証明書は、クライアントのアイデンティティと、証明書の発行時間ｔ0などの基準時間（reference time）とを含んでいる。クライアントはＴＴＰと同期を取り、時間を等しい長さＬのインターバルに分割する。ここでＬは公開されている値である。各インターバルには、ｆをｓに繰返し適用することにより得られるクライアントの一方向ハッシュチェーンの要素により生成された鍵が割り当てられる。これを図２に模式的に示している。図２には、どのようにして時間を長さＬのインターバルに分割するか、そして時間ｉＬにおける各インターバルに異なる鍵が割り当てられることが示されている。時間によりある瞬間を正しく特定できる限り、証明書の発行時間ｔ0とは異なる時間も選択することができる。その結果、基準時間に基づいて、ある時間においてどのインターバルｉＬが有効であるかをその後いつでも決定でき、それにより、対応する鍵を特定できる。
【００４０】
続いて、タイムインターバルＴi（０≦ｉ＜ｍ）において、クライアントは秘密鍵として
【数２０】
2008113426.tif 000022
を使用し、対応する公開鍵として
【数２１】
2008113426.tif 000023
を使用する。サーバが公開鍵
【数２２】
2008113426.tif 000024
（ただし、ｗ＝ｍ−ｉ−１）についての検証されたコピーを得ることができるようにするために、クライアントはサーバに向けて
【数２３】
2008113426.tif 000025
と、ｆw+1（ｓ）と、νを含んだ証明書とを送信する。
【００４１】
サーバはｗを認識していると仮定することができる（それが時間に依存するものであり、現在の時間および証明書に含まれている基準時間ｔ0に基づいて求められるからである）。したがって、サーバは、
【数２４】
2008113426.tif 000026
を計算することができる。
【００４２】
これらの値を使用して、サーバは次に
【数２５】
2008113426.tif 000027
を計算する。
【００４３】
最後にサーバは、ν＝ｈ（ν*）であることをチェックする。
【００４４】
等しいことが検証できると、サーバは次に、受信した証明書にアイデンティティが含まれているクライアントが
【数２６】
2008113426.tif 000028
を生成したことを認識する。
【００４５】
図３は、認証が行われるある瞬間に、その瞬間に該当するインターバルに属するハッシュチェーンの値だけが公開されるということを示している。ハッシュチェーンにおける先行する値は公開されない。このことと、異なるインターバルにおいては異なる値が公開されるということとにより、提案されたメカニズムは高レベルのセキュリティを実現する。
【００４６】
サーバおよびクライアントが非対称の暗号化を使用することに同意した場合、サーバは、機密メッセージを
【数２７】
2008113426.tif 000029
で暗号化してクライアントへ送信することができる。次いで、クライアントはその秘密鍵Ｋwを用いてメッセージを復号化することができる。
【００４７】
一実施形態によれば、クライアントが以前に使用した方法と同じ方法をサーバが使用する場合、サーバは、鍵
ｇKy
【数２８】
2008113426.tif 000030
を開示することにより、自己のアイデンティティをクライアントに対して証明することができる。いったんクライアントが
【数２９】
2008113426.tif 000031
の有効性を検証すると、クライアントは、
【数３０】
2008113426.tif 000032
となるように、サーバとのデフィー・ヘルマン（Diffie-Hellman）セッション鍵ＳＫを生成することができる。サーバは、
【数３１】
2008113426.tif 000033
を計算することによって同じ鍵を取得する。
【００４８】
これまでに説明した解決策では、クライアント、サーバおよびＴＴＰは、同期の取れたクロックを有していなければならない。このような同期を達成するために、ネットワークタイムプロトコル（「D. Mills. Network Time Protocol (Version 3) Specification, Implementation and Analysis. RFC 1305, March 1992」参照）を使用して、クライアントおよびサーバがＴＴＰのクロックと同期を取ることなどを含めて、多くの解決策が利用できる。これは、初期化段階において、クライアントおよびサーバが固定的なネットワークへ接続している間に行なわれる。しかし、その後、それらはＴＴＰおよび固定的なネットワークとは独立して動作することができる。同期化は、認証プロセス中に公開された鍵の新しさおよび有効性を検証するために実行される。しかし、エンティティは完全に同期の取れたクロックを有している必要はない。例えば図４に示されているように、２つ以上の鍵がある時間において有効ならば、数秒のクロックドリフトは問題ではない。ＴＴＰと同期の取れた２つのエンティティの間で許容される最大のクロックドリフトをｄとすると、ｄは、同一のタイムインターバルにおいてこれらの２つの鍵の有効期間の開始を隔てる時間とすることができる。これにより、少なくとも１つの鍵が各タイムインターバルにおいて認証されたセッション鍵を確立できることが保証される。これを説明するために、図４を参照する。インターバルＴ0においてＫm-1および
【数３２】
2008113426.tif 000034
が有効であり、たとえクライアントのクロックとサーバのクロックとの間にｄ以下のクロックドリフトがあったとしても、鍵のうち少なくとも１つは、ν＝ｈ（ν*）という関係を検証できる。あるタイムインターバルにおいて２つ以上の鍵を開示しなければならない場合、ＴＴＰはそれを証明書において指定することができる。ｄは、ＴＴＰが指定でき、初期化段階においてＴＴＰがエンティティへ送信できる。
【００４９】
これまでに説明した実施形態では、エンティティは、失効状態に関する最新の情報を取得することにより証明書の有効性を検証する必要はない。実際、値ｓが充分に保護されている場合、これは例えばパスワードまたはパスフレーズに基づいて行うことができ、かつ、あるｉに対してＫiを生成するために必要な短い間しかマシンに保存することができない、ｓを認識しているクライアントだけが、インターバルＴiにおいて有効な鍵Ｋm-i―1と、対応する公開鍵
【数３３】
2008113426.tif 000035
とを生成することができる。Ｋm-i―1は、別の時間において公開されていないクライアントの一方向ハッシュチェーンの要素を用いて生成され、かつ一方向ハッシュチェーンはコンピュータ的に逆算が難しいので、クライアントが過去に使用した鍵に基づいてアタッカーがＫm-i―1を見つけることはできない。また、アタッカーが
【数３４】
2008113426.tif 000036
に基づいてＫm-i―1を見つけることもコンピュータ的に難しい（「W. Diffie and M. Hellman. New Directions in Cryptography. In IEEE Transactions on Information Theory, Vol. IT-22, No. 6, pp. 644--654, 1976」参照）。これらの理由により、証明書の正規なオーナーだけが、あるタイムインターバルにおいてあるサーバとの間で認証された有効なセッション鍵を生成することができる。
【００５０】
一実施形態によれば、クライアントが過去に使用した公開鍵についての信頼できるコピーをサーバがキャッシュする場合、公開鍵の検証プロセスの最適化が可能となる。
【００５１】
上述した実施形態では、サーバノードがクライアントノードを認証する場合について記載したが、「クライアントノード」という用語に代えて「第１のノード」という用語を使用することもできることと、「サーバノード」という用語に代えて「第２のノード」という用語を使用することもできることとを、当業者は理解されたい。したがって、「クライアント」として動作するクライアントノードは、認証されるノードを単に指しているだけであることを理解すべきである。認証されるノードである「クライアント」は、他の点では他のノードに対して「サーバ」として動作できるか、またはクライアントまたはサーバといった性質を持たずに単なる「通常のノード」としても動作できる。同様に、「サーバ」として動作するサーバノードは、認証を行うノードを単に指すだけであり、認証を行うノードであるサーバは、他の点では他のノードに対してクライアントとして動作できるか、またはクライアントまたは任意のサーバといった性質を持たずに単なる「通常のノード」としても動作できることをも理解すべきである。したがって、「クライアントノード」とは単に認証される任意のノードを意味するものであり、「サーバノード」とは単に認証を行う任意のノードを意味するものである。
【００５２】
これまでに述べた実施形態は、ハードウェア、ソフトウェア、またはソフトウェアおよびハードウェアの組合せによって実現することができることも、当業者は理解されたい。本発明の実施形態に関連して説明したモジュールおよび機能は、全体的または部分的に、本発明の実施形態に関連して説明した方法に基づいて動作するように適切にプログラムが組まれたマイクロプロセッサまたはコンピュータによって実現することができる。上述した説明に基づいて、当業者は、説明した実施形態に基づいて動作するように適切にプログラムを組むことによって、マイクロプロセッサまたはコンピュータを、上述した実施形態に係る方法または装置として実現することができる。前述したデータの交換および／または決定もしくは計算のためのインタフェースを実現するために、１つ以上のメモリを含む標準的なマイクロプロセッサ、および標準的なプログラミング言語といった標準的なプログラミングの手法を使用することができる。当業者は、上述した説明に基づいて、マイクロプロセッサが前述した実施形態に基づいて動作するように、どのようにプログラムするかを理解する。本発明の実施形態を実現する装置は例えば、本発明の実施形態で説明した認証を実行することができるように適切にプログラミングされるネットワーク内のノードまたは要素を含むことができる。
【００５３】
本発明の実施形態では、データキャリアに格納されるか、あるいは他の何らかのやり方で、記録媒体または送信リンクのような何らかの物理的手段によって具現化されるコンピュータプログラムであって、前述した本発明の実施形態に従ってコンピュータを動作させるコンピュータプログラムが提供される。
【００５４】
本発明の実施形態は、前述した認証メカニズムに基づいて動作するようにプログラムされた、例えばネットワーク内のノードまたはネットワーク内のいずれかのエンティティにより実施できる。
【図面の簡単な説明】
【００５５】
【図１】認証のための一方向ハッシュチェーンの使用を示す説明図である。
【図２】本発明の実施形態に基づいて、タイムインターバルと、クライアントの一方向ハッシュチェーンの要素を用いて生成された鍵とのマッピングを模式的に示す説明図である。
【図３】本発明の実施形態に基づいてハッシュチェーンのどの要素が公開されるかを模式的に示す説明図である。
【図４】本発明の実施形態に基づいてドリフトを考慮したメカニズムを模式的に示す説明図である。
【図１】
2008113426.tif 000059
【図２】
2008113426.tif 000060
【図３】
2008113426.tif 000061
【図４】
2008113426.tif 000062
【外国語明細書】
2008113426.tif 000063
2008113426.tif 000064
2008113426.tif 000065
2008113426.tif 000066
2008113426.tif 000067
2008113426.tif 000068
2008113426.tif 000069
2008113426.tif 000070
2008113426.tif 000071
2008113426.tif 000072
2008113426.tif 000073
2008113426.tif 000074
2008113426.tif 000075
2008113426.tif 000076
2008113426.tif 000077
2008113426.tif 000078
2008113426.tif 000079
2008113426.tif 000080
2008113426.tif 000081
2008113426.tif 000082
2008113426.tif 000083
2008113426.tif 000084
2008113426.tif 000085
2008113426.tif 000086
2008113426.tif 000087