(57)【要約】【課題】方法は、ネットワークにおいてシリアルに伝送されるパケットを認証する。【解決手段】現時点のパスワードが、送信される現時点のパケット用に選択される。この現時点のパケットは、現時点のデータを含む。一方向／ワンタイムハッシュ関数が、現時点のパスワードに適用されて、現時点のタグが形成される。次のパスワードが、次のデータを含んだ次のパケット用に選択され、一方向／ワンタイムハッシュ関数が、この次のパスワードに適用されて、次のタグが形成される。次いで、一方向／ワンタイムハッシュ関数が、次のデータと、次のタグと、現時点のパスワードとに適用されて、ハッシュ値が得られる。次いで、このハッシュ値と、現時点のデータと、現時点のタグと、前の送信パケットの前のパスワードとを含む現時点のパケットが送信されて、現時点のデータが認証される。【選択図】図１
2005117626.tif 000002
【特許請求の範囲】
【請求項１】
現時点のデータＭｉを含んだ、送信される現時点のパケット用の現時点のパスワードＰｉを選択すること、
前記現時点のパスワードＰｉに一方向／ワンタイムハッシュ関数ｈを適用して、前記現時点のパケットの現時点のタグＹｉをＹｉ＋１＝ｈ（Ｐｉ＋１）として形成すること、
次のデータＭｉ＋１を含んだ、送信される次のパケット用の次のパスワードＰｉ＋１を選択すること、
前記次のパスワードＰｉ＋１に前記一方向／ワンタイムハッシュ関数ｈを適用して、前記次のパケットの次のタグＹｉ＋１をＹｉ＋１＝ｈ（Ｐｉ＋１）として形成すること、
前記次のデータＭｉ＋１、前記次のタグＹｉ＋１、および前記現時点のパケットの前記現時点のパスワードＰｉに前記一方向／ワンタイムハッシュ関数ｈを適用して、Ｚｉ＋１＝ｈ（Ｍｉ＋１，Ｙｉ＋１，Ｐｉ）を得る、前記一方向／ワンタイムハッシュ関数ｈを適用すること、
および
Ｚｉ＋１と、前記現時点のデータＭｉと、前記現時点のタグＹｉと、前に送信されたパケットの前のパスワードＰｉ−１とを含んだ前記現時点のパケットを送信して、前記現時点のデータＭｉを認証すること
を含むネットワークにおいてシリアルに伝送されるパケットを認証する方法。
【請求項２】
第１のパケットの第１のパスワードは、デジタル署名で認証される
請求項１記載のネットワークにおいてシリアルに伝送されるパケットを認証する方法。
【請求項３】
前記ネットワークはアドホックであり、
前記複数のパケットは制御パケットを含み、
前記データは、前記ネットワークにおける経路を発見するための経路要求である
請求項１記載のネットワークにおいてシリアルに伝送されるパケットを認証する方法。
【請求項４】
前記データは、前記経路の送信元アドレスおよび宛先アドレスを含む
請求項３記載のネットワークにおいてシリアルに伝送されるパケットを認証する方法。
【請求項５】
前記パスワードはランダムに選択される
請求項１記載のネットワークにおいてシリアルに伝送されるパケットを認証する方法。
【請求項６】
前記ネットワークはアドホックネットワークであり、
前記複数のパケットは制御パケットを含み、
前記データは、前記ネットワークにおいて発見された経路の経路応答である
請求項１記載のネットワークにおいてシリアルに伝送されるパケットを認証する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線ネットワークにおける安全なルーティングに関し、特に、アドホックネットワークにおけるパケットの認証に関する。
【背景技術】
【０００２】
アドホックネットワークは、従来のネットワークの集中管理を有しない通信ノードの集合体である。その上、アドホックネットワークのトポロジーは、頻繁に変化する。ノードは、ネットワークに自由に出入りし、ネットワークのノードは、動的なルーティングを提供する。例えば、アドホックオンデマンド距離ベクトル（ＡＯＤＶ（ad hoc, on demand, distance vector））プロトコルは、専らオンデマンドでのみ経路を決定する。これについては、Perkins等著「Ad hoc On-Demand Distance Vector Routing」Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, pp. 90-100, February 1999を参照されたい。多くの場合、ノードは、モバイル（無線）であり、資源が限られている。
【０００３】
アドホック環境は、従来の固定的なネットワークルーティングプロトコルでは一般に直面しなかった２つの主要な問題を招く。これらの問題は、固定的な基盤サポートが欠如しているということ、およびネットワークトポロジーが頻繁に変化するということである。無線アドホックネットワークは、動的な通信環境をサポートし、複雑な環境における大規模でリアルタイムなデータ処理を容易にする。アドホックネットワークは、基地局やアクセスポイントなどの固定的な基盤を必要としない。ネットワークは、必要に応じて安価に確立することができる。
【０００４】
アドホックネットワークの代表的なアプリケーションには、軍事機構および軍事コントロール、捜索救援、センサ、および災害救助、オフィス、大学キャンパス、家庭、移動無線データネットワーク、ならびにこれらのおよびそれ以外の生命またはセキュリティ／安全に依存する配備における他の多くの基幹資源オペレーションが含まれる。ネットワークをその目的となる使用に利用可能に維持することが不可欠である。このようなネットワークに対するサービス拒否（ＤｏＳ）攻撃は、人々の健康および安全を脅かす可能性がある。
【０００５】
物理レベルにおいて、無線チャネルは、信号干渉、ジャミング、不正変更、および盗聴の影響を受けやすい。防御には、スペクトル拡散変調方式、および影響を受ける区域周辺のルーティングが含まれる。また、攻撃者は、物理リンクレイヤにおいて、衝突攻撃（collision attack）および消耗攻撃（exhaustion attack）を開始する可能性もある。これについては、Wood等著「Denial of Service in Sensor Networks」IEEE Computer Magazine, Vol. 35, No. 10, pp.54-62, October 2002を参照されたい。
【０００６】
ＡＯＤＶプロトコルの望ましい特徴は、比較的静的なネットワークにおけるその低いオーバーヘッド、および、宛先連続番号を使用したループフリールーティングである。しかしながら、オンデマンドの経路要求（ＲＲＥＱ）は、通常、初期遅延を招く。また、このプロトコルは、多くの経路要求が存在する場合、および、ブロードキャストメッセージ認証コード（ＭＡＣ）が使用される場合に悪化する。
【０００７】
アドホックネットワーク用の多くのルーティングプロトコルに関連する問題は、それらのプロトコルがセキュリティ攻撃に対して脆弱であるということである。これらの攻撃は、受動的攻撃または能動的攻撃として分類することができる。受動的攻撃では、悪意のあるノードが、ネットワークの運用要求事項を無視する。例えば、経路に沿った中間ノードが、パケットの転送もせず、ルーティング情報も隠蔽する。経路を複数にし、メッセージングを冗長にすることにより、受動的攻撃を軽減することができる。
【０００８】
能動的攻撃では、悪意のあるノードが、例えば虚偽の距離ベクトル、虚偽の宛先シーケンス、または虚偽の経路要求といった虚偽の情報を持ち込む。この情報は、ルーティング手順を混乱させ、ネットワーク性能を劣化させる。虚偽の経路によって、悪意のあるノードは、パケットを傍受し、構成することができる。
【０００９】
別の能動的攻撃として、誤った宛先に向けることが挙げられる。この場合、中間ノードは、誤ったパスに沿ってパケットを転送する。この攻撃は、目的の宛先ノードを避けてパケットを誘導することにより、送信元ノードに影響を与える。
【００１０】
ＡＯＤＶプロトコルは、ルーティング情報がどのくらい最近生成されたかを示す宛先連続番号を使用する。複数の経路が利用可能な場合、送信元ノードは、常に、最大の宛先連続番号に関連付けられた経路を選択する。
【００１１】
悪意のあるノードは、虚偽の大きな宛先連続番号を偽造して、トラフィックを引き寄せることができる。さらに悪いことに、欺かれたノードは、虚偽の経路を誠実に他のノードに伝搬して、攻撃の影響を悪化させる可能性がある。この場合、攻撃者は、悪意を持ってデータトラフィックを引き寄せ、廃棄することができる。
【００１２】
また、悪意のあるノードは、どのノードも応答することができない虚偽の宛先アドレスをブロードキャストすることによって、大量のネットワーク帯域幅を消費することもできる。これは、他のトラフィックを遅延させ、パケットの破棄を引き起こす可能性があり、その結果、全体のネットワーク性能を低下させる。
【００１３】
悪意または機能不良を通じて、ルーティングメッセージの破損、偽造、遅延などの任意の挙動を示すノードによって引き起こされる「ビザンチン」障害を最小にする技法が知られている。少なくとも１つの正当な経路が存在する限り、送信元ノードから宛先へあらゆるパケットを配信するルーティングプロトコルは、ビザンチンローバスト（Byzantine robust）であると言われる。これについては、Perlman著「Network Layer Protocols with Byzantine Robustness」Ph.D. thesis, MIT LCS TR-429, October 1998を参照されたい。しかしながら、そのプロトコルの複雑性により、当該プロトコルは、アドホックネットワークには適していない。
【００１４】
Papadimitrators等は、「Secure Routing for Mobile Ad Hoc Networks」SCS Communication Networks and Distributed Systems Modeling and Simulation Conference, pp.27-31, January 2002において、オンデマンドルーティングに対する成りすまし攻撃および応答攻撃を防止する安全なルーティングプロトコル（ＳＲＰ（secure routing protocol））を記載している。このプロトコルは、経路キャッシュを無効にし、エンドツーエンド認証にＨＭＡＣプリミティブを提供する。これについては、「The Keyed-Hash Message Authentication Code (HMAC)」No. FIPS 198, National Institute for Standards and Technology (NIST), 2002を参照されたい。しかしながら、そのプロトコルは、送信元ノードおよび中間ノードを認証するメカニズムが存在しないので、悪意のある要求フラッディング（request flooding）を防止することができない。
【００１５】
別の技法は、ホップバイホップ認証（hop-by-hop authentication）を使用するものである。あらゆるノードが、あらゆるメッセージに署名し、あらゆるメッセージを認証するように要求される。それにより、処理所要量およびメッセージサイズが増加する。これについては、Dahill等著「A Secure Routing Protocol for Ad Hoc Networks」Technical Report UM-CS-2001-037, University of Massachusetts, Department of Computer Science, August, 2001を参照されたい。
【００１６】
別の技法は、各ノードが、すべてのルーティングパケットを確認するために、すべてのネットワークノードの証明された公開鍵にアクセスできることを必要とするものである。これについては、Zapata等著「Secure Ad hoc On-Demand Distance Vector Routing」ACM Mobile Computing and Communications Review (MC2R), Vol. 6. No. 3, pp. 106-107, July 2002を参照されたい。メッセージの発信元は、ＲＳＡ署名と、ハッシュチェーンの最後の要素、すなわち、或る乱数に対するｎ個の連続したハッシュ計算の結果とを追加する。これについては、Rivest等著「A method for obtaining Digital Signatures and Public Key Cryptosystems」Comm. of ACM, 21(2), pp. 120-126, February 1978、および、Lamport著「Password Authentication with Insecure Communication」Comm. of ACM, 24(11), pp. 770-772, November 1981を参照されたい。
【００１７】
メッセージがネットワークをトラバースする際に、中間ノードは、その署名およびハッシュ値を暗号的に確認でき、ｋをトラバースされたホップ数とすると、ハッシュチェーンのｋ番目の要素を生成でき、そして、ハッシュチェーンをメッセージに追加できる。これについては、Lamport著「Constructing Digital Signature Based on a Conventional Encryption Function」SRI TR CSL 98, 1979を参照されたい。
【００１８】
しかしながら、公開鍵暗号化技術は、ノードに高い処理オーバーヘッドを課し、センサなどの複雑度の低いデバイスからなる実際の低コストのアドホックネットワークには現実的でないことがある。ハッシュチェーン化は、ノードが同期したクロックを有することを必要とする。これについては、Cheung著「An Efficient Message Authentication Scheme for Link State Routing」13th Annual Computer Security Applications Conference, pages 90-98, 1997を参照されたい。一方、その技法は、攻撃が発生したずっと後になってその攻撃を発見できるにすぎない。
【００１９】
Hauser等は、リンクステートアルゴリズムにおいて、ハッシュチェーンを使用して特定のリンクのステータスを明らかにすることによって、その欠点を回避する。これについては、Hauser等著「Reducing the Cost of Security in Link State Routing」Symposium on Network and Distributed Systems Security, pp. 93-99, February 1997を参照されたい。彼らの方法も、ノードの同期を必要とする。
【００２０】
別の技法は、セグメントに分割されるノード固有のハッシュチェーンを使用するものである。セグメントは、ホップカウントを認証するのに使用される。これについては、Hu等著「SEAD: Secure efficient distance vector routing for mobile wireless ad hoc networks」Fourth IEEE Workshop on Mobile Computing Systems and Applications (WMCSA '02), page 3, June 2002、Broch等著「A performance comparison of multi-hop wireless ad hoc network routing protocols」Proceedings of the Fourth Annual International Conference on Mobile Computing and Networking, pp. 85-97, 1998を参照されたい。しかしながら、ＤＳＤＶは、ルーティング情報を定期的にしか分配しない。
【００２１】
多くのアプリケーションでは、反応型ルーティングプロトコルまたはオンデマンドルーティングプロトコルが好ましい。オンデマンドルーティングの場合、送信元ノードは、必要な場合にのみ経路を要求する。オンデマンドルーティングプロトコルは、多くの状況において、定期的なルーティングプロトコルよりもオーバーヘッドを大幅に低減することで、より良好に機能する。これについては、Hu等著「Ariadne: A secure On-Demand Routing Protocol for Ad hoc Networks」MobiCom 2002, September 2002を参照されたい。Ariadneの認証メカニズムは、ＴＥＳＬＡに基づいている。ＴＥＳＬＡについては、Perrig等著「Efficient and Secure Source Authentication for Multicast」Network and Distributed System Security Symposium, February 2001を参照されたい。彼らは、効率的な対称鍵暗号プリミティブのみを使用する。その手法の主要な欠点は、クロック同期を必要とすることであり、クロック同期は、無線アドホックネットワークでは非常に困難である。
【００２２】
ほとんど安全なルーティングプロトコルは、経路発見プロセスにおける認証に基づいている。技法の中には、パケット転送中の誤った挙動の観察に基づいて障害リンクを検出するものがある。Marti等は、ＤＳＲプロトコルを実行するアドホックネットワークにおいてパケットを破棄または変更するルータを検出して回避するプロトコルを記載している。これについては、Marti等著「Mitigating Routing Misbehavior in Mobile Ad Hoc Networks」6th ACM International Conference on Mobile Computing and Networking, August 2000を参照されたい。彼らは、近傍のノードを監視する信頼されたノードを有する。ノードは、さまざまな変調方式で転送されたパケットを傍受できることがあるので、その技法は、マルチレート無線ネットワークではあまり良く機能しない。さらに、その方法は、認証を行わないので、通謀および誤った挙動に対して脆弱である。
【００２３】
Awerbuch等は、適応型プローブ技法を使用する。これについては、「An On-Demand Secure Routing Protocol Resilient to Byzantine Failures」Proceedings of the 2002 ACM Workshop on Wireless Security, September 2002を参照されたい。しかしながら、悪意のあるノードは、プローブパケットを通常のデータパケットと区別することができ、したがって、検出を回避するためにプローブパケットを選択的に転送することができる。
【００２４】
Herzberg等は、肯定応答、タイムアウト、および障害公表を組み合わせて、パケット転送障害を検出することを記載している。これについては、「Early Detection of Message Forwarding Faults」SIAM J. Comput., Vol. 30, no. 4, pp. 1169-1196, 2000を参照されたい。実施態様は、Avramopoulos等著「A Routing Protocol with Byzantine Robustness」The 2003 IEEE Sarnoff Symposium, March 2003によって説明されている。しかしながら、そのプロトコルは、中間ルータのそれぞれに対して個別の認証パスワードを必要とし、したがって、マルチホップが使用される場合に、より多くの通信オーバーヘッドが追加される。
【００２５】
安全な動的ルーティング（ＳＤＲ（secure dynamic routing））プロトコルは、専らオンデマンドであり、経路発見および経路維持という２つの主要なメカニズムを使用する。これについては、Johnson著「Routing in Ad Hoc Networks of Mobile Hosts」Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, pp. 158-163, December 1994、Johnson等著「Dynamic Source Routing in Ad Hoc Wireless Networks」Mobile Computing, Imielinski et al. (ed.) Chapter 5, pp. 153-181, Kluwer Academic Publishers, 1996を参照されたい。
【００２６】
送信元ノードは、宛先ノードに送信するパケットを有するが、その宛先ノードへの経路を有しない場合に、経路要求（ＲＲＥＱ）パケットをブロードキャストする。このパケットは、宛先および一意のＲＲＥＱブロードキャスト識別子を指定する。
【００２７】
受信ノードは、自身のノードアドレスをＲＲＥＱ内のリストに添付して、そのＲＲＥＱを再ブロードキャストする。ＲＲＥＱが、宛先ノード、または、宛先への経路を知っている任意の中間ノードに到達すると、そのノードは、送信元ノードから宛先ノードへの累積アドレスリストを含んだ経路応答（ＲＲＥＰ）パケットを送信元ノードに返送する。ＲＲＥＰが送信元ノードに到達すると、送信元ノードは、自身の経路キャッシュに経路を記憶する。
【００２８】
経路維持は、記憶された経路を無効にし得るネットワークトポロジーの変化を検出するメカニズムである。これは、経路エラーパケットを用いて行われる。
【発明の開示】
【発明が解決しようとする課題】
【００２９】
方法は、ネットワークにおいてシリアルに伝送されるパケットを認証するものである。現時点のパスワードが、送信される現時点のパケット用に選択される。
【課題を解決するための手段】
【００３０】
この現時点のパケットは、現時点のデータを含む。一方向／ワンタイムハッシュ関数が、現時点のパスワードに適用されて、現時点のタグが形成される。次のパスワードが、次のデータを含んだ次のパケット用に選択され、一方向／ワンタイムハッシュ関数が、この次のパスワードに適用されて、次のタグが形成される。
【００３１】
次いで、一方向／ワンタイムハッシュ関数が、次のデータと、次のタグと、現時点のパスワードとに適用されて、ハッシュ値が得られる。
【００３２】
次いで、このハッシュ値と、現時点のデータと、現時点のタグと、前の送信パケットの前のパスワードとを含む現時点のパケットが送信されて、現時点のデータが認証される。
【発明を実施するための最良の形態】
【００３３】
システムオペレーション
図１に示すように、本発明者等の発明は、パケットがシリアルに伝送される無線アドホックネットワーク用の認証プロトコル１００を提供する。シリアルということは、前のパケットｐｉ−１が現時点のパケットｐｉの直前にあり、かつ、次のパケットｐｉ＋１が現時点のパケットｐｉの直後に続くことを意味する。
【００３４】
より具体的には、経路発見フェーズ１１０の期間中、安全な経路選択１２０、すなわち最短安全経路、つまり障害リンクを有しない経路が提供される。経路維持フェーズ１３０の期間中、パケットが転送されている間、タイムアウト条件１４２に基づいて、障害リンク１４１の検出１４０も行われる。肯定応答制御パケット１５１の受信によって、パケットの配信に成功したこと１５０が信号で通知される。
【００３５】
ガイフォークスプロトコル（Guy Fawkes Protocol）
パケット認証では、Ross等著「A New Family of Authentication Protocols」ACMOSR: ACM Operating Systems Review, ACM Press, Vol. 32, pp. 9-20, October 1998に記載されたプロトコルに基づく一方向／ワンタイム関数１１１が使用される。このプロトコルは、ガイフォークスプロトコルとして知られている。このハッシュ関数は、パスワードを符号化して、タグを形成する。
【００３６】
一方向ということは、タグからパスワードを復号できないことを意味し、ワンタイムということは、パスワードの値の一部がその使用後公開されるので、パスワードが一度しか使用されないことを意味する。そのプロトコルは、複数のパケットを順次送信する必要があるアドホックネットワークでの使用に適合されている。したがって、複数のパケットが順次送信されると、その都度、パスワードをリフレッシュする必要がある。このように、単一の認証は、従来技術のハッシュチェーンのように、将来のイベントのストリームではなく、将来のパケットのストリームに関連付けられる。さらに、将来のパケットではなく、現時点のパケットを認証するには、パスワードを知らなければならない。
【００３７】
従来技術を上回る利点として、非対称デジタル署名または秘密パスワードは、事前に判明している必要もないし、システムが動作可能となった後にノード間に分配される必要もない。各パスワードは、認証を行うために公開されるので、一度しか使用されないことにも留意すべきである。
【００３８】
本発明によって実施される一方向／ワンタイムハッシュ関数は、共有された秘密パスワードを事前に確立するようにノードに要求することなく、アドホックネットワークの経路に沿ってパケットをシリアル通信するのに理想的なものである。
【００３９】
図２に示すように、プロトコル２００は、以下のステップを含む。ランダムなパスワードＸｉ＋１２１１を選択する（２１０）。Ｙ＝ｈ（Ｘｉ＋１）となるタグＹ２２１を形成する（２２０）。例えば「我々は、自由な過激派であり、１１月５日に英国国会議事堂を爆破する。我々は、タグＹを形成するようにハッシュされたパスワードによって自身を認証する。」といったメッセージＭｉ＋１２３１を構成する（２３０）。ハッシュ値Ｚｉ＋１＝ｈ（Ｍｉ＋１，Ｙ，Ｘｉ）２４１を形成し（２４０）、これを公開する。行為を実行し（２５０）、Ｍｉ＋１、Ｙ、Ｘｉ２６１を公表して（２６０）、行為を認証する。
【００４０】
一方向／ワンタイムハッシュ関数を使用して、経路発見フェーズ１１０における送信元ノードによる経路要求（ＲＲＥＱ）およびブロードキャスト識別子、ならびにパケット転送フェーズ１３０におけるデータ制御パケットが認証される。このようにして、悪意のある要求および応答攻撃が阻止される。また、ホップ当たりのハッシュ（per-hop hashing）を使用して、経路を記述したノードリストにおいて中間ホップが省略されていないことが検証される。経路応答（ＲＲＥＰ）が宛先ノードによって認証され、したがって、攻撃者は、ルーティング情報を偽造することにより他のノードを欺くことはできない。
【００４１】
本発明者等の認証メカニズムは、効率的な対称鍵暗号化技術しか使用しないので、デジタル署名に基づく従来技術の安全なルーティングプロトコルとは異なる。また、ノードが１つのパスワードしか記憶しないのに対し、ハッシュチェーンに基づくプロトコルは複数のパスワードを記憶し、メモリ所要量が増加することから、本発明者等の方法は、従来技術のハッシュチェーンに基づくプロトコルよりも優れている。
【００４２】
障害リンクを検出する（１４０）ために、肯定応答１５１、タイムアウト１４２、および障害公表１４１が使用される。これらも、本発明者等の一方向／ワンタイムハッシュ関数１１１によって認証を受けることができる。したがって、各データおよび各制御パケットに対して単一の認証タグしか必要とされず、それによって、Avramopoulos等のプロトコルに比べて、ネットワーク帯域幅およびノードのメモリ所要量が削減される。
【００４３】
障害リンクの検出によって、データパケットの転送を不能にするすべての受動的攻撃者および能動的攻撃者、ならびに、悪意を持ってデータパケットを誤った宛先に向けるすべての受動的攻撃者および能動的攻撃者が認識され、その後のルーティングにおいて回避される。
【００４４】
プロトコル記述
安全な経路発見
例えばＤＳＲといったオンデマンドルーティングプロトコルでは、送信元ノードは、宛先ノードに送信するパケットを有し、かつ、自身の経路キャッシュに宛先ノードへの経路を記憶していない場合に、経路発見１１０を開始して経路を探し出す。送信元ノードは、ＲＲＥＱ制御パケットを近傍のノードにブロードキャストすることによりこれを行う。この要求が、経路上の中間ノードを発見できるように宛先ノードの方向への経路を最終的に探し出すまで、近傍のノードは、この要求を再ブロードキャストする。ＲＲＥＱ制御パケットは、一方向／ワンタイムハッシュ関数１１１により認証される。
【００４５】
ＲＲＥＱ認証
図４は、送信元ノードＳ４１０から中間ノードＡ４２０およびＢ４３０を介して宛先ノード４４０へのアドホックネットワーク４００の一例の経路を示している。この種の制御パケットでは、関連するパケットデータは、経路を定義することになる送信元アドレスおよび宛先アドレスである。
【００４６】
図４に示す経路４００の場合、図３および図５に示すように、送信元ノードは、２つのランダムなパスワードＰ１およびＰ２を選択して（３１０）、以下の第１のＲＲＥＱをブロードキャストする。
ＲＲＥＱ１＝｛ｓ１，ｈ（Ｐ１），Ｓｉｇ（ｓ１，ｈ（Ｐ１）），ｈ（ｓ２，ｈ（Ｐ２），Ｐ１），ｄｅｓｔ＿ａｄｄｒ，ｈＳＤ｝
ここで、ｓ１＝＜ｓｏｕｒｃｅ＿ａｄｄｒ（送信元アドレス），ｂｒｏａｄｃａｓｔ＿ｉｄ（ブロードキャストＩＤ）＝１＞であり、ｓ２＝＜ｓｏｕｒｃｅ＿ａｄｄｒ，ｂｒｏａｄｃａｓｔ＿ｉｄ＝２＞である。ｈは、本発明者等の一方向／ワンタイムハッシュ関数であり、Ｓｉｇ（ｓ１，ｈ（Ｐ１））は、他のノードへの（ｓ１，ｈ（Ｐ１））を検証するデジタル署名である。その結果、あらゆる中間ノードおよび宛先は、ＲＲＥＱ１パケットの（ｓｏｕｒｃｅ＿ａｄｄｒ，ｂｒｏａｄｃａｓｔ＿ｉｄ，ｈ（Ｐ１））が正当であり、要求した送信元ノードによって確かに生成されたものであることを検証することができる。
【００４７】
中間ノードは、送信元ノードＳのアドレス、ｂｒｏａｄｃａｓｔ＿ｉｄ＝１、ｘ１＝ｈ（Ｐ１）、およびｘ２＝ｈ（ｓ２，ｈ（Ｐ２），Ｐ１）を記憶することによって経路エントリを生成する。これらの値は、同じ送信元ノードからのその後の経路要求を検証することができる。成分＜ｓｏｕｒｃｅ＿ａｄｄｒ，ｂｒｏａｄｃａｓｔ＿ｉｄ＞は、ＲＲＥＱを一意に特定するものである。ｂｒｏａｄｃａｓｔ＿ｉｄの値は、送信元ノードが新たなＲＲＥＱを発行するごとにインクリメントされる。
【００４８】
値
【００４９】
【数１】
2005117626.tif 000003
【００５０】
は、宛先ノードへの情報を認証する鍵付きハッシュメッセージ認証コード（ＨＭＡＣ）である。秘密鍵ＫＳＤは、送信元ノードおよび宛先ノードによって共有される。これは、最初のパケットにのみ使用する必要がある。
【００５１】
ＲＲＥＱ制御パケットのブロードキャストの性質のため、アドホックネットワークのあらゆるノードは、最終的には、時間ｍΔの後、ＲＲＥＱ１を受信する。ここで、ｍはネットワークの直径であり、Δは最小ホップ遅延である。
【００５２】
時間間隔ｍΔの後、送信元ノードは、第２の経路要求ＲＲＥＱ２を送信する。したがって、送信元ノードは、第３のランダムなパスワードＰ３を選択して（３２０）、以下のＲＲＥＱ２をブロードキャストする。
ＲＲＥＱ２＝｛ｓ２，ｈ（Ｐ２），Ｐ１，ｈ（ｓ３，ｈ（Ｐ３），Ｐ２），ｄｅｓｔ＿ａｄｄｒ，ｈＳＤ｝
ここで、ｓ２＝＜ｓｏｕｒｃｅ＿ａｄｄｒ，ｂｒｏａｄｃａｓｔ＿ｉｄ＝２＞であり、ｓ３＝＜ｓｏｕｒｃｅ＿ａｄｄｒ，ｂｒｏａｄｃａｓｔ＿ｉｄ＝３＞である。各中間ノードは、現ＲＲＥＱパケットで運ばれたｓｏｕｒｃｅ＿ａｄｄｒおよびｂｒｏａｄｃａｓｔ＿ｉｄを検証する。これは、経路が発見されるまで繰り返すことができる。
【００５３】
中間ノードは、要求した送信元ノードに関連付けられた経路エントリを探し出し、ハッシュ関数ｈをＰ１に適用する。このＰ１は、ＲＲＥＱ２で受信されたものである。そして、中間ノードは、ハッシュ関数の適用結果が、ＲＲＥＱ１で先に受信されて経路エントリに記憶されているｘ１と等しいかどうかをチェックする。等しい場合には、Ｐ１は正当なものである。この場合、中間ノードは、ＲＲＥＱ２で運ばれた（ｓ２，ｈ（Ｐ２），Ｐ１）にハッシュ関数ｈを適用し、その結果が、経路エントリに記憶されているｘ２と同じであるかどうかをチェックする。このチェックも合格すると、（ｓ２，ｈ（Ｐ２））の真正性が検証される。このように、中間ノードは、ＲＲＥＱ２が、要求した送信元ノードからのものであり、現ｂｒｏａｄｃａｓｔ＿ｉｄ＝２が正当なものであることを確信する。次いで、中間ノードは、ｂｒｏａｄｃａｓｔ＿ｉｄ＝２、ｘ１＝ｈ（Ｐ２）、およびｘ２＝ｈ（ｓ３，ｈ（Ｐ３），Ｐ２）を記録することによって、その経路エントリを更新する。これら記録されたものは、ＲＲＥＱ３の認証に使用される。
【００５４】
一般に、ｋ番目の経路要求ＲＲＥＱｋを送信する前に、送信元ノードは、前回の要求ＲＲＥＱｋ−１の送信後、時間間隔ｍΔを待機する。その後、送信元ノードは、新しいランダムなパスワードＰｋ＋１を選択して（３３０）、以下のＲＲＥＱｋをブロードキャストする。
ＲＲＥＱｋ＝｛ｓｋ，ｈ（Ｐｋ），Ｐｋ−１，ｈ（ｓｋ＋１，ｈ（Ｐｋ＋１），Ｐｋ），ｄｅｓｔ＿ａｄｄｒ，ｈＳＤ｝
ここで、ｓｋ＝＜ｓｏｕｒｃｅ＿ａｄｄｒ，ｂｒｏａｄｃａｓｔ＿ｉｄ＝ｋ＞である。各中間ノードは、このＲＲＥＱｋを受信する。中間ノードは、送信元からのｋ個以上のｂｒｏａｄｃａｓｔ＿ｉｄを記憶している場合に、この要求を廃棄する。そうでない場合には、中間ノードは、ｘ１＝ｈ（Ｐｋ−１）であるかどうか、および、ｘ２＝ｈ（ｓｋ，ｈ（Ｐｋ），Ｐｋ−１）であるかどうかを検証する。双方の検査が真である場合、中間ノードは、ｂｒｏａｄｃａｓｔ＿ｉｄ＝ｋ、ｘ１＝ｈ（Ｐｋ）、およびｘ２＝ｈ（ｓｋ＋１，ｈ（Ｐｋ＋１），Ｐｋ）を記録することによって、要求した送信元ノードに関連付けられた経路エントリ、すなわちパケットデータを更新する。次いで、中間ノードは、自身のアドレスをＲＲＥＱの中間ノードリストの最後に追加し、ホップ当たりのハッシュを実行する。このホップ当たりのハッシュは、図５においてｈＳＤ、ｈＡＤ、ｈＢＤによって示すように、旧ハッシュタグに連結された中間ノード自身のアドレスをハッシュすることにより新たなハッシュタグを計算すること、および、旧ハッシュタグを取り替えることによって達成される。そして、中間ノードは、このＲＲＥＱを再ブロードキャストする。いずれのチェックも不合格であると、ＲＲＥＱは破棄される。
【００５５】
このように、ホップ当たりのハッシュの場合、攻撃者は、中間ノードと宛先ノードとの間の秘密パスワードを有しないので、ノードリストから中間ノードを消去することができない。
【００５６】
ＲＲＥＱが宛先ノードに到達すると、宛先ノードは、以下が成立するかどうかをチェックすることによってＲＲＥＱを検証する。
【００５７】
【数２】
2005117626.tif 000004
【００５８】
このチェックが合格すると、このＲＲＥＱの完全性が、その発信元およびノードＳからノードＤへのパスに沿ったあらゆる中間ノードの真正性と共に検証される。次いで、宛先ノードは、ＲＲＥＱからの蓄積アドレスリストの認証されたコピー、すなわちＲＲＥＱ制御パケットのパケットデータの認証されたコピーを含んだＲＲＥＰを送信元ノードに返送する。
【００５９】
図６に示すように、ＲＲＥＰ制御パケットは、次のフィールド、すなわち＜ｂｒｏａｄｃａｓｔ＿ｉｄ，（Ｓ，Ａ，Ｂ，Ｄ），ｈＤＢ，ｈＤＡ，ｈＤＳ＞５０１を含む。ここで、ｂｒｏａｄｃａｓｔ＿ｉｄは、送信元Ｓが、この応答の鮮度を検証するためのものであり、ハッシュ値５０３は、以下のようになる。
【００６０】
【数３】
2005117626.tif 000005
【００６１】
ＲＲＥＰパケットは、送信元ノードに戻りながら中間ノードを通過するので、各ノードは、対応する認証タグをチェックし、自身の経路キャッシュに経路情報を記憶する。次いで、送信元ノードは、障害リンクが事前に検出されていない宛先ノードへの最短経路を選択する（１２０）。
【００６２】
パケット転送および障害リンク検出
図７は、選択された経路に沿って送信元ノードから宛先ノードへ転送されたデータパケットを認証すると同時に障害リンクをチェックするステップを示している。ＤＳＲでは、送信元経路情報は、各パケットヘッダにおいて運ばれる。
【００６３】
送信元ノードＳは、送信元経路｛Ｓ，ｎ１，ｎ２，…ｎＬ，Ｄ｝を通って宛先ノードＤへ送信する一続きのデータパケット｛ｍ１，ｍ２，…ｍｎ｝を有する。ここで、ｎ１，ｎ２，…ｎＬは、この経路に沿ったノードである。送信元ノードは、最初のデータパケットｍ１を送信する際に、２つのランダムなパスワードＸ１およびＸ２を選択し、宛先の肯定応答（ＡＣＫ）１５１（図１参照）または障害リンク公表（ＦＡ）制御パケット１４１のいずれかを、経路に沿ったノードから受信するためのタイムアウトを設定する。送信元ノードは、経路に沿った最初の中間ノードに以下のメッセージを送信する。
ＭＳＧ１＝｛ｍ１，ｈ（Ｘ１），Ｓｉｇ（ｍ１，ｈ（Ｘ１）），ｈ（ｍ２，ｈ（Ｘ２），Ｘ１）｝
ここで、Ｓｉｇ（ｍ１，ｈ（Ｘ１））は、（ｍ１，ｈ（Ｘ１））に対する署名である。送信元ノードの公開鍵により、経路に沿ったあらゆるノードは、（ｍ１，ｈ（Ｘ１））が正当なものであり、送信元ノードによって確かに生成されたものであることを検証することができる。
【００６４】
（ｍ１，ｈ（Ｘ１））を認証する代替的な方法は、送信元ノードが、対をなす秘密鍵を経路に沿った各ノードと共有する場合に、認証タグを使用するものである。各ノードは、以下のものを記録することによって、送信元ノードＳの新たな経路テーブルエントリを生成する。
ａ．  ＜Ｓ，ｍｓｇ＿ｈａｓｈ１＝ｈ（Ｘ１），ｍｓｇ＿ｈａｓｈ２＝ｈ（ｍ２，ｈ（Ｘ２），Ｘ１）＞
これは、その後のメッセージＭＳＧ２を認証するのに使用される。
【００６５】
送信元ノードは、２番目のデータパケットｍ２を送信する際に、別のパスワードＸ３を選択し、２番目のメッセージＭＳＧ２、すなわちＭＳＧ２＝｛ｍ２，ｈ（Ｘ２），Ｘ１，ｈ（ｍ３，ｈ（Ｘ３），Ｘ２）｝を最初の下流側ルータに転送する。経路上の各ノードは、まず、ＭＳＧ２で受信したＸ１にハッシュ関数ｈを適用し、その結果が、自身の経路テーブルのｍｓｇ＿ｈａｓｈ１と同じ値であるかどうかをチェックすることによって、（ｍ２，ｈ（Ｘ２））を検証する。同じ値である場合、Ｘ１は正当なものである。次いで、ノードは、ＭＳＧ２で受信した（ｍ２，ｈ（Ｘ２），Ｘ１）に対してハッシュ関数を実行し、その結果が、ｍｓｇ＿ｈａｓｈ２と等しいかどうかをチェックする。このチェックが合格すると、（ｍ２，ｈ（Ｘ２））の真正性が検証される。次いで、ノードは、＜Ｓ，ｍｓｇ＿ｈａｓｈ１＝ｈ（Ｘ２），ｍｓｇ＿ｈａｓｈ２＝ｈ（ｍ３，ｈ（Ｘ３），Ｘ２）＞を記録することによって、自身のルーティングエントリを更新し、パケットヘッダのヘッダで指定された、経路に沿ったノードにデータパケットを転送する。
【００６６】
同様に、送信元ノードは、ｋ番目（ｋ≧２）のパケットｍｋを送信する際に、次のパスワードＸｋ＋１を選択し、ｋ番目のメッセージＭＳＧｋ、すなわちＭＳＧｋ＝｛ｍｋ，ｈ（Ｘｋ），Ｘｋ−１，ｈ（ｍｋ＋１，ｈ（Ｘｋ＋１），Ｘｋ）｝を転送する。
【００６７】
図８に示すように、中間ルータは、ｈ（Ｘｋ−１）＝ｍｓｇ＿ｈａｓｈ１かどうか、および、ｈ（ｍｋ，ｈ（Ｘｋ），Ｘｋ−１）＝ｍｓｇ＿ｈａｓｈ２かどうかをチェックすることによって、受信データパケットｍｋを認証する。これらのチェックのいずれかが不合格であると、そのパケットは破棄される。双方のチェックが合格すると、ノードは、＜Ｓ，ｍｓｇ＿ｈａｓｈ１＝ｈ（Ｘｋ），ｍｓｇ＿ｈａｓｈ２＝ｈ（ｍｋ＋１，ｈ（Ｘｋ＋１），Ｘｋ）＞によって、送信元Ｓに関連付けられた自身のルーティングエントリを更新する。次いで、データパケットは、経路に沿った次のノードに転送される。パケットの転送時に、各ノードは、このデータパケットに対するＡＣＫ１５１またはＦＡ１４１のいずれかを受信するためのタイムアウトを設定する。タイムアウトは、最悪の場合のラウンドトリップ時間に設定される。この時間は、アドホックネットワークのあらゆるノードに知られているものである。
【００６８】
ノードｎｉにおけるチェックが不合格である場合、ｎｉ−１またはＭＳＧ１のｈ（ｍ２，ｈ（Ｘ２），Ｘ１）のいずれかが変更されているか、または、ノードｎｉ−１が、ＭＳＧ２の（ｍ２，ｈ（Ｘ２），Ｘ１）を変更している。いずれの場合も、現時点のノードｎｉは、このパケットを破棄する。その結果、ノードｎｉ−１は、タイムアウト後も正当なＡＣＫを受信せず、このノードは、障害リンクエラー（ｎｉ−１，ｎｉ）を報告することができ、あるいは、ノードｎｉ−２が、リンク（ｎｉ−２，ｎｉ−１）の障害を送信元ノードに報告する。いずれの場合も、障害リンクは、悪意のあるノードｎｉ−１を含んでいる。
【００６９】
本発明による各パケットの認証タグは、２つのハッシュおよび１つのパスワードのみを有するのに対し、紹介した従来の技術の検出プロトコルでは、Ｌ個のホップを有する経路に対してＬ個の認証タグが必要とされる。したがって、本発明者等の方法は、通信／記憶オーバーヘッドが低い。
【００７０】
宛先ノードは、データパケットｍｋを受信すると、中間ノードと同じ方法でそのパケットの真正性を検証する。それらのチェックのいずれかが不合格であると、そのパケットは破棄される。双方のチェックが合格すると、そのパケットは、配信に成功し（１５０）、ＡＣＫ１５１を経路の逆方向パスに沿って送信するようにスケジューリングする。このＡＣＫは、パケット識別番号ｋを反映する。
【００７１】
宛先ノードも、逆方向パス上のノード用に、認証タグをＡＣＫメッセージの最後に追加する。この認証タグは、送信元ノードによって生成されたものと同じ構造を有する。具体的には、宛先ノードは、最初のパケットｍ１に対するＡＣＫ１を送信する際に、２つのパスワードＹ１およびＹ２をランダムに選択し、以下の情報、すなわちＡＣＫ１，ｈ（Ｙ１），Ｓｉｇ（ＡＣＫ１，ｈ（Ｙ１）），ｈ（ＡＣＫ２，ｈ（Ｙ２），Ｙ１）を送信する。同様に、Ｓｉｇ（ＡＣＫ１，ｈ（Ｙ１））は、経路の逆方向パスに沿った各ノードによって、（ＡＣＫ１，ｈ（Ｙ１））を検証するのに使用される。図８に示すように、宛先は、パケットｍｋ（ｋ≧２）に対する肯定応答を送信する際に、新たなパスワードＹｋ＋１を選択し、ＡＣＫｋ，ｈ（Ｙｋ），Ｙｋ−１，ｈ（ＡＣＫｋ＋１，ｈ（Ｙｋ＋１），Ｙｋ）を転送する。
【００７２】
中間ノードにおけるタイムアウトが満了すると、そのノードは、本発明者等のハッシュ関数による識別番号を有するＦＡ１４１を送信し、上流側ノードは、このＦＡの認証を行う。ノードは、ＡＣＫを受信すると、そのＡＣＫの真正性を検証し、この対応するデータパケット用のタイムアウトが保留状態であることを確認する。ＡＣＫが真正なものでない場合、または、タイムアウトが保留状態でない場合には、ノードは、そのＡＣＫを破棄する。それ以外の場合には、ノードは、タイムアウトを取り消して、そのＡＣＫを次のノードに転送する。
【００７３】
ノードは、ＦＡを受信すると、そのＦＡの真正性を検証し、その対応するデータパケット用のタイムアウトが保留状態であること、および、ＦＡで報告されたリンクが、そのＦＡを生成したノードに対して最初の下流側のものであることを確認する。ＦＡが真正なものでない場合、もしくは、タイムアウトが保留状態でない場合、または、リンクが、ＦＡを報告したノードに対して下流側のものでない場合には、ノードは、そのＦＡを破棄する。それ以外の場合には、ノードは、タイムアウトを取り消して、そのＦＡ制御パケットをさらに転送する。
【００７４】
タイムアウトが、送信元ノードにおいて満了すると、送信元ノードは、経路上の最初のリンクを自身の経路キャッシュから消去する。次いで、送信元ノードは、宛先ノードへの新たな経路を探し出し、「不成功の」パケットがあたかも新たなパケットであるかのように、その不成功のパケットを再処理する。送信元ノードは、ＡＣＫｋを受信すると、データパケットｍｋの配信が成功したことを知る。送信元が真正なＦＡを受信した場合において、その関連付けられたリンクが、ＦＡを生成したノードのリンクと同じであるときは、送信元ノードは、その関連付けられたリンクを自身の経路キャッシュから消去し、新たな経路を探し出す。
【００７５】
本発明者等のプロトコルの場合、メッセージＭＳＧｋ−１は、常に、メッセージＭＡＧｋの前に受信される。これは、すべてのパケットがＤＳＲの同じ経路に沿って転送されるからである。輻輳およびバッファリングの場合、メッセージは、メッセージの受信順序に従って、先入れ先出しバッファに記憶される。
【００７６】
送信元ノードは、宛先ノードへの別のパスを使用したい場合、上述したように、新たなパスワードを選択して、そのパスワードを新たな経路に沿ったあらゆるノードと共に認証し、プロセス全体を再び開始する。
【００７７】
個々のコンポーネントについての補足説明
通常のパケットが輻輳によっても決して確実に破棄されないようにするのに十分大きなメモリバッファを各ノードが有するものと仮定する。認証により、正当なパケットにバッファを確実に適切に割り当てるようにする。また、従来のＤｏＳでは、悪意のあるノードが、認証されていないパケットでネットワークをフラッディングさせるが、バッファは、この従来のＤｏＳからの保護にも役立つ。パケットを頻繁に送信する悪意のあるノードは、それ以外に、割り当てられたすべてのバッファ空間を素早く消費することもできる。
【００７８】
発明の効果
本発明によるパケット認証によれば、悪意のあるノードは、宛先ノードによって使用される秘密パスワードを有しないので、受動的攻撃者および能動的攻撃者を検出することができる。また、悪意のあるノードは、正当な認証タグを有するＡＣＫを偽造することもできない。
【００７９】
また、本発明による一方向／ワンタイムハッシュタグは、応答攻撃も防止する。応答攻撃では、中間ノードは、真正なパケットを記憶し、後になってそれらのパケットをネットワークに送り出し、新たなパケットを「排除する」。本発明者等のプロトコルによれば、新たな各パケットは、新たな異なるパスワードで送信される。その結果、中間ノードが、再生されたパスワードのハッシュを、当該中間ノードが前のメッセージで受信したハッシュ値と比較すると、この再生されたパスワードのチェックは不合格になる。ＡＣＫは、パケットの配信が成功したかどうかに関するフィードバックを提供する。
【００８０】
タイムアウトは、配信の失敗を検出する。送信元ルーティング、ＡＣＫ、認証、バッファ、ＦＩＦＯスケジューリング、およびタイムアウトを組み合わせて使用することは、経路が障害を有するかどうかを特定するのに十分なものとなる。あらゆる中間ノードにおけるタイムアウトをＦＡと組み合わせることにより、障害リンクに関するフィードバックも提供される。これは、ネットワーク管理目的に役立ち、また、経路選択プロセスも援助する。
【００８１】
好ましい実施の形態を例として本発明を説明してきたが、本発明の精神および範囲内において、他のさまざまな適合および変更を行い得ることが理解されるべきである。したがって、添付の特許請求項の目的は、本発明の真の精神および範囲に含まれるすべての変形および変更を網羅することである。
【図面の簡単な説明】
【００８２】
【図１】本発明による安全なルーティングプロトコルのフロー図である。
【図２】本発明により使用される一方向ハッシュ関数のステップのフロー図である。
【図３】本発明による経路発見フェーズのステップのブロック図である。
【図４】本発明による経路のブロック図である。
【図５】本発明による経路発見フェーズのステップのブロック図である。
【図６】本発明による経路応答メッセージのブロック図である。
【図７】本発明によるパケット転送フェーズのステップのブロック図である。
【図８】本発明による障害検出フェーズのステップのブロック図である。
【図１】
2005117626.tif 000006
【図２】
2005117626.tif 000007
【図３】
2005117626.tif 000008
【図４】
2005117626.tif 000009
【図５】
2005117626.tif 000010
【図６】
2005117626.tif 000011
【図７】
2005117626.tif 000012
【図８】
2005117626.tif 000013
【外国語明細書】
2005117626.tif 000014
2005117626.tif 000015
2005117626.tif 000016
2005117626.tif 000017
2005117626.tif 000018
2005117626.tif 000019
2005117626.tif 000020
2005117626.tif 000021
2005117626.tif 000022
2005117626.tif 000023
2005117626.tif 000024
2005117626.tif 000025
2005117626.tif 000026
2005117626.tif 000027
2005117626.tif 000028
2005117626.tif 000029
2005117626.tif 000030
2005117626.tif 000031
2005117626.tif 000032
2005117626.tif 000033
2005117626.tif 000034
2005117626.tif 000035
2005117626.tif 000036
2005117626.tif 000037
2005117626.tif 000038
2005117626.tif 000039
2005117626.tif 000040
2005117626.tif 000041
2005117626.tif 000042
2005117626.tif 000043
2005117626.tif 000044
2005117626.tif 000045
2005117626.tif 000046