(57)【特許請求の範囲】
【請求項１】
少なくとも１つの第２のデバイスとトランザクションを実施している間に、第１のデバイスを保護するためのコンピュータ実装の方法であって、前記第１のデバイスが、シーケンスに応じた複数の値として表すことが可能な内部秘密状態を有するコンピュータ可読メモリを含み、前記シーケンスは、複数のレベルによって特徴付けられ、前記内部秘密状態を表す各値は、前記複数のレベルのうちの１つのレベルを示し、前記少なくとも１つの第２のデバイスが、前記第１のデバイスにおける基準内部秘密状態に対応する値へのアクセス権を有する、前記第１のデバイスが実施する方法において、
（ａ）（ｉ）前記コンピュータ可読メモリから、前記内部秘密状態に関連付けられた索引パラメータを読み出し、
（ｉｉ）前記索引パラメータを使用して、入力状態を出力状態に変換する複数の状態変換操作のうちの少なくとも１つの状態変換操作を選択するステップであって、前記出力状態は、前記複数のレベルの中で、前記入力状態よりも相対的に上位のレベルまたは下位のレベルを示すステップと、
（ｂ）前記少なくとも１つの選択された状態変換操作を前記内部秘密状態に適用して、更新された内部秘密状態を生成し、
（ｉ）更新された秘密値を前記更新された内部秘密状態に関連付け、
（ｉｉ）前記少なくとも１つの選択された状態変換操作が、前記内部秘密状態の諸部分を混合させる、前記更新された内部秘密状態を生成するための非線形暗号関数を含むことによって、前記非線形暗号関数が既知の場合でも、前記ステップ（ａ）（ｉ）における前記内部秘密状態に関する漏洩した部分統計情報が、前記更新された内部秘密状態を有用に記述することを妨げるようにするステップと、
（ｃ）前記コンピュータ可読メモリ中で、
（ｉ）前記内部秘密状態を前記更新された内部秘密状態に、かつ、
（ｉｉ）前記索引パラメータを更新された索引パラメータに
置き代えるステップと、
（ｄ）（ｉ）前記更新された索引パラメータを使用して、前記複数の状態変換操作の中の上位レベルから下位レベルへの状態変換操作を実施することによって、前記少なくとも１つの第２のデバイスがアクセス権を有する、前記値に対応する前記第１のデバイスにおける前記基準内部秘密状態から前記更新された内部秘密状態を再生成し、
（ｉｉ）前記再生成された更新された内部秘密状態を使用して、少なくとも１つの保護されたデータを処理するように
構成された前記少なくとも１つの第２のデバイスに、前記更新された秘密値を使用して、前記更新された索引パラメータおよび前記少なくとも１つの保護されたデータを伝送することによって、前記少なくとも１つの第２のデバイスと暗号トランザクションを実施するステップと、
（ｅ）前記第１のデバイスが実施する複数のトランザクションを通じて、前記ステップ（ａ）から前記ステップ（ｄ）を複数回繰り返すステップと
を備え、
前記ステップ（ｅ）から前記ステップ（ａ）および前記ステップ（ｂ）への繰り返しが、前記内部秘密状態の前記シーケンスを定め、前記シーケンスにおける前記内部秘密状態を表す値の少なくとも一部は同一の値であり、
前記シーケンスは、前記基準内部秘密状態から前記更新された内部秘密状態までの、前記複数のレベルの内部秘密状態を取ることができ、
前記更新された内部秘密状態は、前記ステップ（ｂ）が前記ステップ（ｅ）に応じて繰り返されるときに生じる後続の前記ステップ（ｂ）に関する入力秘密状態として使用され、
前記再生成（ｄ）（ｉ）の回数が、前記第１のデバイスにおける前記ステップ（ｅ）に応じた前記ステップ（ａ）から前記ステップ（ｄ）に至る前記繰り返しの総回数よりも少ないことを特徴とする方法。
【請求項２】
前記ステップ（ｂ）が多数回繰り返されたときに、前記更新された内部秘密状態に対する値が決められた回数よりも多く繰り返されることが決してないことを特徴とする請求項１に記載の方法。
【請求項３】
前記決められた回数は、３回であることを特徴とする請求項２に記載の方法。
【請求項４】
前記少なくとも１つの選択された状態変換操作が正常に実施されたことを検証するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項５】
前記ステップ（ｂ）が少なくとも１回実施される前に、内部秘密状態の更新の失敗を記録する障害カウンタを増分するステップと、前記障害カウンタが最大値を超えた場合に停止するステップと、前記ステップ（ｂ）が完了した後に前記障害カウンタをリセットするステップとをさらに備えることを特徴とする請求項１に記載の方法。
【請求項６】
前記第１のデバイスは、ISO7816準拠スマートカードを含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記ISO7816準拠スマートカードは、該ISO7816準拠スマートカードを用いて実施されるトランザクションで使用できる値を格納することを特徴とする請求項６に記載の方法。
【請求項８】
前記トランザクションは、購買のための安全な支払いを含むことを特徴とする請求項１に記載の方法。
【請求項９】
前記トランザクションは、サービスへのアクセスを許可することを含むことを特徴とする請求項１に記載の方法。
【請求項１０】
前記サービスは、ウェブサーバへのアクセスを含むことを特徴とする請求項９に記載の方法。
【請求項１１】
前記第１のデバイスは、ISO7816準拠スマートカードを含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
（ａ）シーケンスに応じた複数の値として表すことが可能な秘密パラメータの値を含む少なくとも１つのメモリであって、前記シーケンスは、基準秘密パラメータを有し、前記秘密パラメータの各値は、複数のレベルのうちの１つのレベルを示す、少なくとも１つのメモリと、
（ｂ）受信する暗号処理デバイスと複数の暗号トランザクションを繰り返し実施するように構成された処理装置であって、各前記暗号トランザクションは、暗号によって処理されたデータを含み、
（ｉ）各前記暗号トランザクションは、前記秘密パラメータに関連付けられた鍵を使用して実施され、
（ｉｉ）前記繰り返される複数の暗号トランザクション間で、複数の変換操作のうちの少なくとも１つの変換操作が選択され、前記複数のレベルの中で、前記秘密パラメータよりも相対的に上位のレベルまたは下位のレベルを示す更新された秘密パラメータを生成するように、前記少なくとも１つの選択された変換操作が前記秘密パラメータに適用され、前記少なくとも１つの選択された変換操作が、前記秘密パラメータの諸部分を混合させる、前記更新された秘密パラメータを生成するための非線形暗号関数を含むことによって、前記非線形暗号関数が既知の場合でも、前記暗号デバイスの外部監視によって前もって集めることができる前記秘密パラメータに関する情報の有用性が低減され、
（ｉｉｉ）前記少なくとも１つの選択された変換操作後、前記更新された秘密パラメータの値が、少なくとも１つの後続のトランザクションで使用するために前記少なくとも１つのメモリに格納され、
（ｉｖ）前記（ｉ）から前記（ｉｉｉ）までが、前記暗号デバイスによって実施される複数のトランザクションを通じて複数回繰り返され、前記基準秘密パラメータから前記更新された秘密パラメータに至る秘密パラメータの値の前記シーケンスが、前記（ｉ）から前記（ｉｉｉ）までの繰り返しによって定められ、前記シーケンスにおける前記秘密パラメータの値の少なくとも一部は同一の値である、処理装置と、
（ｃ）前記処理装置が複数の変換操作を実施した後の前記秘密パラメータの更新された値が、前記複数の変換操作の前に前記秘密パラメータの値から導出することができる、前記受信する暗号処理デバイスに前記データを伝送するように構成されたインターフェースと
を備えたことを特徴とする暗号デバイス。
【請求項１３】
ISO7816準拠スマートカードを含むことを特徴とする請求項１２に記載の暗号デバイス。
【請求項１４】
（ｉ）前記複数の変換操作がｎ回実施され、（ｉｉ）前記処理装置が前記ｎ回の変換操作を実施した後の前記更新された秘密パラメータの値を、前記ｎ回の変換操作を実施するのに必要な計算労力よりも少ない計算労力で前記ｎ回の変換操作の前に、前記秘密パラメータの値から前記受信する暗号処理デバイスによって導出することができることを特徴とする請求項１２に記載の暗号デバイス。
【請求項１５】
前記ｎは、５０よりも大きいことを特徴とする請求項１４に記載の暗号デバイス。
【請求項１６】
前記変換操作がサイクル長ｘを有し、前記変換操作前の前記秘密パラメータから前記ｎ回の変換操作後の前記更新された秘密パラメータを導出するために前記受信する暗号処理デバイスによって必要な前記計算労力が、最大でもＯ（ｌｏｇｘ）の計算労力しか必要としないことを特徴とする請求項１４に記載の暗号デバイス。
【請求項１７】
前記暗号デバイスは、ISO7816準拠スマートカードであることを特徴とする請求項１４に記載の暗号デバイス。
【請求項１８】
前記少なくとも１つのメモリは、索引パラメータをさらに含み、前記処理装置は、前記秘密パラメータの値が更新されるたびに前記索引パラメータの値を増分するように構成されていることを特徴とする請求項１４に記載の暗号デバイス。
【請求項１９】
前記処理装置は、複数の事前定義された暗号変換から少なくとも１つの暗号変換を選択し、かつ前記少なくとも１つの暗号変換を前記秘密パラメータに適用することによって、前記秘密パラメータの値を更新するように構成されていることを特徴とする請求項１８に記載の暗号デバイス。
【請求項２０】
前記少なくとも１つのメモリは、深さパラメータＤをさらに含み、前記処理装置は、前記索引パラメータの現行値および前記深さパラメータＤに基づいて前記少なくとも１つの暗号変換を選択するように構成されていることを特徴とする請求項１９に記載の暗号デバイス。
【請求項２１】
前記秘密パラメータは、Ｄ個のサブエレメントを含み、前記少なくとも１つの暗号変換は、前記サブエレメントのうちの少なくとも１つのサブエレメントを変更し、前記変更する少なくとも１つのサブエレメントの選択は、前記索引パラメータによって決まることを特徴とする請求項２０に記載の暗号デバイス。
【請求項２２】
前記複数の事前定義された暗号変換は、少なくとも２つの変換および前記少なくとも２つの変換の逆変換を含むことを特徴とする請求項１９に記載の暗号デバイス。
【請求項２３】
前記複数の事前定義された暗号変換は、ブロック暗号を含むことを特徴とする請求項２２に記載の暗号デバイス。
【請求項２４】
前記少なくとも１つのメモリは、前記索引パラメータの初期値がゼロになるように初期設定され、前記処理装置は、前記索引パラメータの現行値がＤ−１よりも小さいときに第１の暗号変換を選択するように構成されていることを特徴とする請求項２１に記載の暗号デバイス。
【請求項２５】
前記処理装置は、前記索引パラメータの現行値がＤ−１に等しいときに前記第１の暗号変換の逆変換を選択するように構成され、前記処理装置は、前記索引パラメータの現行値がＤに等しいときに第２の暗号変換を選択するように構成され、前記処理装置は、前記索引パラメータの現行値がＤ＋１に等しいときに前記第２の暗号変換の逆変換を選択するように構成されていることを特徴とする請求項２４に記載の暗号デバイス。
【請求項２６】
前記処理装置は、前記索引パラメータの現行値が有効であることを検証するように構成されたオーバーフロー検出論理を含むことを特徴とする請求項１８に記載の暗号デバイス。
【請求項２７】
第１のデバイスと第２のデバイスとの間で複数のトランザクションを実施するための前記第１のデバイスと前記第２のデバイスとを備えた暗号システムであって、
（ａ）前記第１のデバイスは、
（ｉ）第１の秘密パラメータの値および索引パラメータの値を格納するためのメモリであって、前記第１の秘密パラメータの値は、決められた第１のシーケンスに応じた複数の値を取ることができ、前記第１の秘密パラメータの各値は、複数のレベルのうちの１つのレベルを示す、メモリと、
（ｉｉ）複数の暗号トランザクションを実施するように構成された処理装置であって、
（ａ１）前記第１のデバイスと前記第２のデバイスとの間の前記複数のトランザクションの各々は、前記第１の秘密パラメータに関連付けられたトランザクション鍵を使用して保護され、
（ａ２）トランザクション間で、前記第１のデバイスの外部監視によって前もって集めることができる前記第１の秘密パラメータに関する情報の有用性が、前記第１の秘密パラメータの諸部分を混合させる、更新された第１の秘密パラメータを生成するための非線形暗号関数を用いる変換操作を実施して、前記第１の秘密パラメータの値を更新することにより低減され、前記更新された第１の秘密パラメータは、前記複数のレベルの中で、前記第１の秘密パラメータよりも相対的に上位のレベルまたは下位のレベルを示し、
（ａ３）前記更新された第１のパラメータは、後続のトランザクションで使用するために前記メモリに格納される、処理装置と
を含み、
（ｂ）前記第２のデバイスは、
（ｉ）第２の秘密パラメータを含むメモリと、
（ｉｉ）前記索引パラメータの表現および暗号トランザクションデータを前記第１のデバイスから受信するためのインターフェースであって、前記トランザクションデータは、前記トランザクション鍵を使用して保護される、インターフェースと、
（ｉｉｉ）前記受信した索引パラメータを使用して、前記第１のシーケンスの中で上位レベルから下位レベルへの暗号変換のみを含む所定の暗号変換の第２のシーケンスを選択し、かつ、前記第２のシーケンスの前記暗号変換を実施することによって、前記第１のデバイスが前記第１の秘密パラメータをｎ回変換した場合に、前記トランザクション鍵を導出するために前記第２のデバイスに必要な変換の数がｎよりも小さい効率の良い形で、前記第２のシーケンスの前記暗号変換により、少なくとも前記第２の秘密パラメータから前記トランザクション鍵を導出するように構成された処理装置と、
（ｉｖ）前記トランザクション鍵を使用して前記トランザクションデータを処理するための論理とを含む
ことを特徴とする暗号システム。
【請求項２８】
前記第２のデバイスによって必要とされる変換の数は、前記ｎの全ての値に関して４０未満であることを特徴とする請求項２７に記載のシステム。
【請求項２９】
メモリに格納された秘密パラメータを使用して受信側デバイスと暗号トランザクションを実施する送信側デバイスによる方法であって、
（ａ）前記秘密パラメータに関連付けられた鍵を使用して暗号トランザクションを実施するステップと、
（ｂ）前記秘密パラメータの諸部分を混合させる、更新された秘密パラメータを生成するための非線形暗号関数を使用することにより、シーケンス中で、各後続の更新された秘密パラメータの値が、前の秘密パラメータの値に対して上位レベルまたは下位レベルを示すｎ回の変換操作の前記シーケンスが実施された後、外部監視攻撃によって前もって集めることができる前記秘密パラメータに関連付けられた値に関する情報の有用性を低減するために変換操作を適用するステップであって、前記ｎ回の変換操作の前に前記秘密パラメータの値を知っている前記受信側デバイスが、前記ｎ回の変換操作の前記シーケンスのうち、上位レベルから下位レベルへの変換操作のみを実施することによって、Ｏ（ｎ）回未満の変換操作で前記更新された秘密パラメータの値を導出することができるステップと、
（ｃ）前記秘密パラメータを、前記メモリ中で前記更新された秘密パラメータに置き代えるステップと
を備えることを特徴とする方法。
【請求項３０】
前記ステップ（ｂ）および前記ステップ（ｃ）は、一定の時間間隔で実施されることを特徴とする請求項２９に記載の方法。
【請求項３１】
ISO7816準拠スマートカードで実施されることを特徴とする請求項２９に記載の方法。
【請求項３２】
暗号化されたテレビジョン信号に対するアクセスを規制するデバイスで実施されることを特徴とする請求項２９に記載の方法。
【請求項３３】
支払課金デバイスで実施されることを特徴とする請求項２９に記載の方法。
【請求項３４】
決められたシーケンスに応じた複数の値を取ることができる秘密パラメータを使用して、第１のデバイスと第２のデバイスとの間での暗号トランザクションを保護する方法であって、前記秘密パラメータの各値は、複数のレベルのうちの１つのレベルを示す前記方法において、
（ａ）前記第１のデバイスが、該第１のデバイス内に含まれるメモリを前記秘密パラメータの初期値に初期設定するステップと、
（ｂ）前記第１のデバイスが、前記第２のデバイス内に含まれるメモリを、前記秘密パラメータの前記初期値を導出するために使用可能な値に初期設定するステップと、
（ｃ）前記第１のデバイスが、前記秘密パラメータに関連付けられたトランザクション鍵を用いてデータを保護するステップと、
（ｄ）前記第１のデバイスが、前記保護したデータおよび索引パラメータを含むトランザクションデータを前記第２のデバイスに伝送するステップと、
（ｅ）前記第１のデバイスが、
（ｉ）前記索引パラメータを使用して、入力状態を出力状態に変換する複数の状態変換操作のうちの少なくとも１つの状態変換操作を選択し、前記出力状態は、前記複数のレベルの中で、前記入力状態よりも相対的に上位のレベルまたは下位のレベルを示し、
（ｉｉ）前記秘密パラメータの諸部分を混合させる、後続のトランザクションで使用する更新された秘密パラメータを生成するための非線形暗号関数の形態の状態変換操作を適用することにより、外部監視攻撃によって前もって集めることができる前記秘密パラメータの値に関する情報の有用性を低減するステップと、
（ｆ）前記第１のデバイスが、前記メモリ中の前記秘密パラメータを前記更新された秘密パラメータに置き代えるステップと、
（ｇ）前記第２のデバイスが、前記トランザクションデータを受信するステップと、
（ｈ）前記第２のデバイスが、前記複数の状態変換操作のうち、上位レベルから下位レベルへの状態変換操作を実施するだけで、少なくとも前記索引パラメータを使用して、前記第２のデバイスの前記メモリに格納された前記値から前記トランザクション鍵を導出するステップであって、前記導出はｎ回未満の前記状態変換操作を必要とし、前記ｎは、前記秘密パラメータを更新するために前記第１のデバイスによって前記ステップ（ｅ）が適用された総回数を表すステップと、
（ｉ）前記第２のデバイスが、前記保護したデータを処理するために、前記ステップ（ｈ）で導出した前記トランザクション鍵を使用するステップと
を備えることを特徴とする方法。
【請求項３５】
前記ステップ（ｈ）で実施される前記状態変換操作の最大数はＯ（ｌｏｇｘ）であり、前記ｘは、前記第１のデバイスの攻撃者により観察することができるトランザクションの最大数であることを特徴とする請求項３４に記載の方法。
【請求項３６】
前記第１のデバイスは、ISO7816準拠スマートカードであることを特徴とする請求項３４に記載の方法。
【請求項３７】
前記第１のデバイスおよび前記第２のデバイスは、より大きなデバイスの構成要素であることを特徴とする請求項３４に記載の方法。
【請求項３８】
前記第２のデバイスは、索引パラメータを含み、
（ａ）前記第１のデバイスおよび前記第２のデバイスのうち、大きい方の索引パラメータを選択するステップと、
（ｂ）前記トランザクションを保護するために前記大きい方の索引パラメータの値を使用するステップと、
（ｃ）前記第１のデバイスおよび前記第２のデバイスの双方が、後続のトランザクションで使用するために前記大きい方の索引パラメータの値を増分し、格納するステップと
をさらに備えることを特徴とする請求項３４に記載の方法。
【請求項３９】
前記ステップ（ａ）から前記ステップ（ｉ）が異なる順序で実施されることを特徴とする請求項３４に記載の方法。
【請求項４０】
前記状態変換操作は、
（ａ）前記秘密パラメータの値を少なくとも２つの副次的な値に分割するステップと、
（ｂ）暗号化された副次的な値を生成するために前記副次的な値の第１の値を暗号化するステップと、
（ｃ）排他的ＯＲ演算を使用して、前記暗号化された副次的な第１の値を前記副次的な値の第２の値と組み合わせ、前記状態変換操作の結果の第１の部分を形成するステップと、
（ｄ）前記第１の部分の結果を暗号化するステップと、
（ｅ）前記暗号化した前記第１の部分の結果を、前記副次的な値の第１の値と排他的ＯＲ演算し、前記状態変換操作の結果の第２の部分を生成するステップと
を含むことを特徴とする請求項３４に記載の方法。
【請求項４１】
前記暗号化するステップは、ＤＥＳアルゴリズムを含むことを特徴とする請求項４０に記載の方法。
【発明の詳細な説明】
【０００１】
本出願は、１９９８年７月２日出願の米国仮特許出願第６０／０９１６４４号に基づいて優先権の利益を主張する。
【０００２】
本出願は、１９９８年１２月３１日出願の同時継続の米国特許出願第０９／２２４６８２号に関係する。
【０００３】
（発明の分野）
本発明は、暗号鍵を安全に管理し、使用するためのシステムに関し、より詳細には、外部監視攻撃（external monitoring attacks）に対して暗号デバイスを保護するための方法および装置に関する。
【０００４】
（発明の背景）
暗号鍵およびその他の秘密へアクセスした攻撃者は、場合によっては、許可されていない操作を実施したり、トランザクションを捏造する可能性がある。したがって、スマートカードベースの電子支払スキームなど多くのシステムにおいて、秘密は、不正に開封すればわかるようにできている（tamper-resistant：以下、タンパー・レジスタントという。）ハードウェアで保護される必要がある。しかし、Cryptography Researchによる最近の調査は、暗号秘密に関する情報が電力消費や電磁放射などデバイスの外部特性を監視する攻撃者に漏洩した場合に、スマートカードおよびその他のデバイスが損壊される恐れがあることを示している。
【０００５】
対称暗号システムと非対称暗号システムのどちらにおいても、鍵を損壊する攻撃者が、通信を復号する、シグニチャを捏造する、許可されていないトランザクションを実施する、ユーザになりすます、または、他の問題を引き起こす可能性があるため、秘密パラメータは、機密性を保持されなければならない。物理的に安全な、十分に遮蔽された部屋を使用して安全に鍵を管理する方法は、背景技術で知られており、今日広く使用されている。しかし、低コストの暗号デバイスで鍵を保護するための周知の方法は、しばしば、厳しい技術的制約（コスト、サイズ、性能など）を伴う適用例や、高度のタンパー・レジスタントを必要とする適用例など、多くの適用例に不適切である。顕微鏡を使用するＲＯＭのリバースエンジニアリング、タイミング攻撃暗号解読（timing attack cryptanalysis）（例えば、P.Kocher著「Timing Attacks on Implementations of Diffie-Hellman,RSA,DSS,and Other Systems」Advances in Cryptology-CRYPTO′96,Springer-Verlag,104〜113ページ参照）、および誤り分析（例えば、E.Biham,A.Shamir著「Differential Fault Analysis of Secret Key Cryptosystems」Advances in Cryptology-CRYPTO′97,Springer-Verlag,1997,513〜525ページ参照）など、暗号システムを分析するための攻撃が記述されてきた。
【０００６】
デバイスを損壊しようとする攻撃者が過去の鍵を導出することを防止するための鍵管理技法は、背景技術として知られている。例えば、ANSI X9.24「Financial services-retail management」は、攻撃者がデバイスの状態を完全に損壊した後に過去の鍵を導出することを防止するＤＵＫＰＴ（Derived Unique Key Per Transaction）と呼ばれるプロトコルを定義する。そのような技法は、攻撃者が古い鍵を導出することを防止することができるが、実用上の制限があり、攻撃者が現行の鍵に関する部分情報を使用して将来の鍵を損壊する外部監視攻撃に対する効果的な保護を提供しない。
【０００７】
Cryptography Researchは、また、クライアントおよびサーバが暗号操作を実施し、それと同時にクライアントが外部監視攻撃に対して自衛することを可能にする反復ハッシュ操作（iterated hashing operations）を使用する方法を開発した。そのような方法では、クライアントが、トランザクション間またはトランザクション中にその内部秘密に対して暗号関数を繰り返し適用し、それにより、一連のトランザクションそれぞれにおいて漏洩した情報を組み合せて秘密を損壊することをできないようにしている。しかしながら、上述されたシステムは、各トランザクションで使用される対称セッション鍵を再導出するために、サーバが同様の操作シーケンスを実施しなければならないという欠点を有する。したがって、例えば多数の非同期サーバデバイスが存在する場合（独立サーバとして多数の商用端末が動作する電子キャッシュ応用例など）、または、サーバが限られたメモリを有する場合、サーバは、クライアントが使いそうな全てのセッション鍵を信頼できるものとして再計算することができない。その結果、サーバが正確なセッション鍵を取得するのに比較的多数の操作が必要とされることがあるため、トランザクション性能が悪くなる。例えば、ｎ番目のクライアントセッション鍵は、導出するためにｎ回のサーバ動作を必要とすることがある。したがって、漏洩抵抗力（leak-resistant）および／または耐漏洩（leak-proof）のある対称鍵の合意を得るための高速で効率の良い方法が有利である。
【０００８】
（発明の概要）
本発明は、たとえ攻撃者が外部監視（またはその他の）攻撃を使用してクライアントデバイスの内部操作に関する情報を集めることができたとしても、スマートカード（およびその他の暗号クライアントデバイス）の安全を守る方法を記述する。一実施形態では、暗号クライアントデバイス（例えばスマートカード）が、その状態の一部として秘密鍵値を保持する。クライアントは、攻撃者に前もって漏洩している可能性がある秘密に関する部分情報が、新たに更新された秘密値をもはや（少なくともあまり）有用には開示されないようにする更新プロセスを使用して、いつでも、例えば各トランザクションの前に、その秘密値を更新することができる。（攻撃者が実際の攻撃を実施することを助けるまたは可能にする可能性がある場合に、情報が有用であると考える。）したがって、秘密鍵値は、十分頻繁に（おそらく１トランザクション当たり１回程）更新され、それにより入力状態に関する漏洩情報は、更新された状態を有用に開示しない。更新プロセスを繰り返し適用することによって、攻撃者によって収集される暗号操作中に漏洩された情報はすぐに、もう使えないものになる。したがって、そのようなシステムは、漏洩しやすい（すなわち秘密値に関する情報を漏洩する）ハードウェアおよびソフトウェアを使用してシステムが実施されたとしても、デバイスの電力消費または電磁特性を繰り返し測定することを含む攻撃に対して安全に保たれる。（逆に、従来のシステムは同じ秘密値を繰り返し使用し、攻撃者が多数のトランザクションから収集された情報を統計的に組み合わせることを可能にしている。）
【０００９】
本発明は、そのようなプロトコルを使用するクライアントおよびサーバと共に使用することができる。クライアントとのトランザクションを実施するために、サーバは、クライアントの現行トランザクションカウンタ（または別の鍵索引値）を取得する。次いでサーバは、一連の操作を実施して、クライアントの初期秘密値から正しいセッション鍵を再導出するのに必要な変換のシーケンスを決定する。次いで、これらの変換が実施され、その結果がトランザクションセッション鍵として使用される（または、セッション鍵を導出するために使用される）。
【００１０】
本発明は、対応するサーバ動作の性能の有意な改良を見込み、その一方でクライアントデバイスの漏洩抵抗力および／または耐漏洩セキュリティ特性を維持する一連のクライアント側更新プロセスを含むことができる。本発明の一実施形態では、シーケンス中の各プロセスが、２つの順暗号変換（forward cryptographic transformations）（ＦAおよびＦB）およびそれらの逆変換（ＦA-1およびＦB-1）の中から選択される。以下に詳細に説明する方法を使用して、そのような更新関数は、ある単一の秘密値が固定された回数（例えば３回）を超えて使用され、または導出されることが決してないことを保証するシーケンスによりクライアントによって適用される。さらに、更新関数およびシーケンスは、また、任意のトランザクションの状態（したがってトランザクションに使用される秘密セッション鍵値）が、ＦAおよびＦB（またはそれらの逆関数）の最小回数で適用され、開始状態（第１のトランザクションで使用される状態など）から効率良く導出可能であることを保証する。
【００１１】
クライアントによって安全に実施することができる操作の回数がｎ回である（すなわち、固定された回数を超えて同じ秘密値を使用することなく、ｎ回の異なるトランザクションを実施することができる）場合、クライアントの初期秘密値Ｋ（またはそれに対応する初期状態）を知っている、または取得することができるサーバが、一連のトランザクションで結果として生じる秘密値（または対応する状態）を、ｎ回の対応する更新を実施するよりもかなり速く導出することができる。事実、任意の所与のトランザクションに関する状態は、しばしばＦAおよびＦB（またはそれらの逆関数）のＯ（ｌｏｇｎ）計算を使用してサーバによって導出することができる。システム設計者がｎを十分に大きくした場合、それにより、ほとんど制限のないトランザクションのセットがクライアントによって実施され、それと同時に優れたサーバ性能を提供することが可能になる。
【００１２】
（発明の詳細な説明）
（索引付き鍵管理）
本発明は、外部監視攻撃に対するセキュリティを向上させた暗号操作を当事者が実施することを可能にする。例示的実施形態は、二者、「クライアント」および「サーバ」に関して記述するが、用語「クライアント」および「サーバ」は、便宜上選択したものであり、必ずしもシステム設計での特定の役割に直接対応するものではない場合がある。例えば、クライアントはスマートカードであってよく、サーバはメインフレームコンピュータであってよく、その逆であってもよい。さらに、ほとんどの暗号操作は二者（例えば、一方がクライアントにあり、他方がサーバにある）を含むが、当然本発明を、一者のみ（例えば、クライアントとサーバが共に単一当事者の制御下にあり、または単一デバイス内で組み合わされているセキュアメモリまたは格納システムにおけるもの）を含む環境で、または三者以上の当事者および／またはデバイスを含む環境で適用することもできる。
【００１３】
例示的実施形態では、クライアントが対称暗号システム用の秘密鍵Ｋ0を用いて初期設定され、このＫ0はサーバにも知られている（またはサーバによって導出可能である）。鍵Ｋ0は（必ずしもそうではないが）通常、個々のクライアントデバイスまたは当事者に特有のものである。クライアントは、また、ゼロに初期設定することができる（典型的には秘密でない）索引またはトランザクションカウンタＣを有する。さらなるパラメータは、索引の深さＤである。Ｄの値も秘密でなくてもよく、かつ（例えば）クライアントに特有であってよく、またはシステム全体にわたって汎用の定数であってよい。Ｄの値は、鍵更新プロセスのサイクル長を決定する。
【００１４】
図１は、（必ずしもそうではないが）典型的には１トランザクション当たり１状態を使用して、一連のトランザクションを実施するために使用可能なクライアントデバイス秘密状態値の例示的シーケンスを示す。（このシーケンスを生成するために使用されるクライアントプロセスは図２を参照して説明し、それに対応するサーバプロセスは図３を参照して説明する）。状態の秘密値は、必ずしもそうではないが典型的には、秘密セッション鍵を含む。したがって便宜上、秘密値をＫによって示し、用語「秘密値」を、幾分かは「鍵」と交換可能に使用することができるものとする。それでもやはり、一般的な場合には、それらが異なっている場合があることを当業者は理解されよう。また、説明を簡単にするために、５レベルの鍵値が存在することを意味するＤ＝５を有する例示的鍵更新プロセスを示す図が描かれている。しかし、Ｄに対する明確な制限はなく、例示的実施形態の根底にある一般的な原理をそのような他のサイクル長に関してどのように使用することができるかは、当業者には容易に理解されよう。実際、市販用に開発されるシステムは普通、Ｄに関してより大きな値を使用する。
【００１５】
図中の各ボックスは、秘密値（ＫC）の１つの値を表す。したがって、ボックス中の複数のドットが、同じ秘密値ＫCを共有する異なる状態を表す。図の一番上の行（行０）は、１つのボックスを含み、これは初期状態Ｋ0１１０、ならびに後続の状態Ｋ30１４０およびＫ60１７０に対応し、それらが全て同じ秘密値ＫCを共有する。次の行（行１）は２つのボックスを含み、左のボックスは、同じ秘密値を共有する三つの状態（Ｋ1１１１、Ｋ15、およびＫ29）の組に対応し、右のボックスは、別の秘密値を共有する第２の三つの状態（Ｋ31、Ｋ45、およびＫ59）の組に対応する。同様に、行２は４つのボックスを含み、計１２状態を表し、４つに分かれた組がそれぞれ、それら自体の間で同じ秘密値を共有する。より一般的には、この例示的実施形態では、行Ｎ（ここでＮ＜Ｄ−１）が、２N個のボックス（または一意の秘密値）および３（２N）の状態を含み、最後の行（Ｎ＝Ｄ−１）は、２N個のボックスおよび２Nの状態を含む。より太い（曲がっている）経路は、状態が更新されるプロセスを示し、初期状態１１０から始まって、最終状態１７０まで続く。状態が更新されると、カウンタＣも（各更新ごとに１だけ）更新される。
【００１６】
例示的状態更新プロセスは、計４つの関数に関して、２つの関数（ＦAおよびＦB）およびそれらの逆関数（ＦA-1およびＦB-1）を含む。ステップ１００で、クライアントが開始カウンタＣ＝０、および開始秘密値ＫC＝Ｋ0を有する開始状態に初期設定され、またはパーソナライズされる。ステップ１１０で、デバイスは、ＫC（またはＫCから導出される鍵）を使用して第１のトランザクションを実施する。鍵は、ほぼ任意の対称暗号トランザクションに使用することができる。（例えばそのようなトランザクションには、メッセージ上のＭＡＣ（メッセージ確認コード）を計算する、または検証すること、メッセージを暗号化すること、または復号化すること、疑似乱数チャレンジ値（pseudorandom challenge value）を生成すること、鍵を導出することなどを、それらに限定せずに含むことができる。メッセージの例としては、資金転送操作の量を指定するデータ、電子メールメッセージ、チャレンジ／レスポンス認証データ、パラメータ更新許可、コード更新、オーディオメッセージ、デジタル化イメージなどを、それらに限定せずに挙げられる。）
【００１７】
ステップ１１０の後、Ｃ←Ｃ＋１およびＫC←ＦA（ＫC）を実施することによって、クライアントデバイスの秘密値ＫCが、関数ＦAを適用することによって更新され、カウンタＣが増分される。（したがって、ステップ１１１で、Ｃ＝１であり、ＫC＝ＦA（Ｋ0）である）。ＫCの更新された値を使用して、ステップ１１１でトランザクションを実施する。ステップ１１１の後、Ｃ←Ｃ＋１およびＫC=2←ＦA（ＫC）を実施することによって、Ｃが再び増分され、ＦAが再びＫCに適用されて、ステップ１１２で使用される秘密鍵を生じる。同じ操作の対（Ｃ←Ｃ＋１とＫC←ＦA（ＫC））が、ステップ１１２と１１３の間、およびステップ１１３と１１４の間で同様に適用される。
【００１８】
ステップ１１３と１１５は、同じボックス内に示されているため、ステップ１１５でのトランザクションは、ステップ１１３でのトランザクションが使用したものと同じＫC値を使用するはずである。したがって、ステップ１１４でのトランザクション後、更新プロセスは、Ｃ←Ｃ＋１（Ｃ＝５を生じる）およびＫC=5←ＦA-1（ＫC）を計算することによって実施される。ＫC=5＝ＦA-1（ＫC=4）＝ＦA-1（ＦA（ＫC=3））＝ＫC=3であることに留意されたい。したがって、ステップ１１５で使用されるＫCの値は、ステップ１１３で使用される値と同じである。ステップ１１５でのトランザクション後、ＫCは、関数ＫBを使用して、Ｃを増分し、ＫC=6←ＦB（ＫC）を計算することによって更新される。ステップ１１６でのトランザクション後、トランザクション１１７に関する秘密値が、関数ＦB-1をＫCに適用することによって計算される。
【００１９】
更新プロセスは、各トランザクション後に鍵状態更新プロセスが実施されるように働く。鍵更新は、Ｃを増分すること、および関数ＦA、ＦB、ＦA-1、またはＦB-1の１つを状態ＫCに適用することを含む。逆変換可能な関数を使用することにより、第１の状態と第２の状態が同じ秘密値を共有することが可能になり、第１の状態は、親（上位レベル）ボックスから子（下位レベル）ボックスへのエントリを行い、第２の状態は、子ボックスから親ボックスへのリエントリによって作成される。さらに、多数の関数（例えば、例示実施形態でのＦAおよびＦB）により、シーケンスが（例えば終了状態１９０で）終わる前に、各親ボックスから多数の子ボックス、したがって多数の許容可能な状態を作成することを可能にする。ある特定の状態から別の特定の状態に進む際、関数の選択（例えば図１の例示的実施形態で、ＦA、ＦB、ＦA-1、またはＦB-1のどれを使用するか）は、２つの特定の状態の、現在の方向および位置によって決まる。特に、図１に示された例示的実施形態を再び参照すると、ステップ１１２と１１３の間など親ボックスから左側子ボックスへ下るとき、ＫC←ＦA（ＫC）を計算することによってＦAが適用される。さらに、ステップ１１５と１１６の間など親ボックスから右側子ボックスへ下るとき、ＦBが適用される。さらに、ステップ１１４と１１５の間など左側の子からその親に進むとき、ＫC←ＦA-1（ＫC）を計算することによってＦA-1が適用される。最後に、ステップ１１６と１１７の間など右側の子からその親に進むとき、ＦB-1が適用される。より一般的には、任意の特定の状態遷移に適用する関数の選択は、単にＣに応じて決定することができ、したがってクライアントが、その現行状態およびその現行カウンタ値以外の情報を何も保持する必要がない。これは、以下の項目「クライアント側索引付き鍵更新」において、図１の例示的実施形態に沿ってより詳細に説明する。
【００２０】
最終的に、クライアントは、テーブル全体が横切られた点に達することができる。例えば、図１のプロセスはステップ１７０で終了し、Ｃ＝６０である。このトランザクションの後（または、テーブルの長さがシステムによって許容されるトランザクションの最大数を超えている場合はそれよりも早い時点で）、クライアントデバイスは、例えばその内部秘密を削除することによってそれ自体を使用禁止にすることができ、典型的にはそうすることがある。しかし、ある場合には他のアクション（例えばステップ１１０に繰り返し戻り、再キー入力が必要とされる状態に入ること）が好ましいことがある。示された例示的実施形態では、プロセスの終了が行われる前に実施することができるトランザクションの数が、
【００２１】
【数１】
0004216475.tif 000002
【００２２】
に等しい。（Ｄ＝５の例では、これにより２6−３＝６１トランザクションになる。）Ｄに関して十分大きな値を選択することによって、システム設計者は、トランザクションの最大数を、「終了」に決して達しないほど大きくすることができる。例えば、Ｄ＝３９は、繰返しを伴わずに１兆（１０12）を超えるトランザクションを可能にする。
【００２３】
（クライアント側索引付き鍵更新）
図１の例示的実施形態に関して、Ｃを増分し、どの関数（ＦA、ＦB、ＦA-1、またはＦB-1）を適用するかを選択するプロセスは、クライアントによって図２に示されるように実施することができる。ステップ２１０で、クライアントデバイスは、例えばＣが非負であり、Ｃが２D+1−３未満であることを確認することによって、Ｃが有効であると検証する。（Ｃが無効である場合、トランザクションが失敗する、または他の適切なアクションが取られる。）クライアントが内部にＣを保持するため、Ｃが有効であるとクライアントが確信している場合は、ステップ２１０を省略することができる。ステップ２２０で、デバイスが一時的な深さおよびカウンタ変数ＮおよびＶを初期設定し、その値がそれぞれＤおよびＣに格納される。
【００２４】
ステップ２３０で、デバイスは、変数Ｖが数量２N−３に等しいかどうかテストする。等しい場合、関数ＦA-1が適用され、処理がステップ２３５に進み、デバイスがＣを増分し、ＫC←ＦA-1（ＫC）を計算することによってＫCを更新する。そうでない場合は、ステップ２４０で、デバイスは、変数Ｖが数量２（２N−２）に等しいかどうかテストする。等しい場合、関数ＦB-1が適用され、処理がステップ２４５に進み、デバイスがＣを増分し、ＫC←ＦB-1（ＫC）を計算することによってＫCを更新する。そうでない場合は、ステップ２５０で、変数Ｖがゼロに等しいかどうかテストする。等しい場合、関数ＦAが適用され、処理がステップ２５５に進み、デバイスがＣを増分し、ＫC←ＦA（ＫC）を計算することによってＫCを更新する。そうでない場合は、ステップ２６０で、変数Ｖが数量２N−２に等しいかどうかテストする。等しい場合、関数ＦBが適用され、処理はステップ２６５に進み、デバイスがＣを増分し、ＫC←ＦB（ＫC）を計算することによってＫCを更新する。
【００２５】
ステップ２７０で、デバイスは、Ｖの値が２N−２を超えているかどうかチェックする。超えていない場合、処理が直接ステップ２８０に進む。Ｖが２N−２よりも大きい場合、Ｖの値は２N−２だけ減少され、処理がステップ２８０に進む。ステップ２８０で、ＶおよびＮがそれぞれ減算され、その後処理がステップ２３０に進む。
【００２６】
ステップ２３５、ステップ２４５、ステップ２５５、またはステップ２６５で状態更新関数を実施した後、クライアントプロセスは、ステップ２９０で正常に終了する。図２のプロセスの正常な終了の後、秘密値ＫCを使用して、暗号トランザクションを実施する（または例えばＫCをハッシュする、または暗号化すること、ソルト（salt）またはノンス（nonce）を付加することなどによってトランザクションを実施するために使用される鍵を導出する）。
【００２７】
図２のプロセスの各反復が、正確な更新操作が決定されるまで、図１の図面で１レベル下に移動することに対応することに留意されたい。したがって、ループの反復の回数がＤを超えることはできない。鍵更新関数（例示的実施形態でのＦA、ＦB、ＦA-1、またはＦB-1）を除き、関数選択プロセスの実施は、漏洩抵抗力を全てにわたって有する必要がない。すなわち、図２の関数選択プロセス、その入力値（すなわちＣ）、および更新関数の選択が秘密である必要がない。最後に、例示的実施形態の場合において前述し、例示したように、特定の状態遷移に適用する関数の選択は、単にＣの関数に応じて特徴付けることができ、それによりクライアントは、その現行状態およびその現行カウンタ値以外の情報を何も保持する必要がない。
【００２８】
（サーバ側索引付き鍵導出）
図３は、図２の例示的クライアント側プロセスに適合する例示的サーバ側プロセスを示す。図３のプロセスを開始する前に、サーバは、クライアントのカウンタ値Ｃを（典型的にはデジタル入出力インターフェースを介して、クライアントデバイスからＣを受信することによって）取得し、その値が鍵索引として使用される。（この例示的実施形態では、トランザクションカウンタが鍵索引として使用されるが、代替実施形態は、鍵索引の異なる値または表現を使用することができる。）
【００２９】
サーバは、また、（例えば、サーバのメモリからＫ0を検索することによって、他の秘密鍵または秘密アルゴリズムを使用してＫ0を暗号の形で導出することによって、鍵サーバなどの第三者からＫ0を取得することによって、など）クライアントの基準鍵値Ｋ0を取得する。サーバは、また、Ｄを知るまたは取得する。ステップ３１０で、サーバは、Ｃを検証して、Ｃの任意の取り得る無効値を拒否する。ステップ３２０で、一時的変数Ｎ、Ｖ、およびＫが、それぞれＤ、Ｃ、およびＫ0の値に初期設定される。ステップ３３０で、サーバは、Ｖの値がゼロに等しいかどうかチェックする。等しい場合は、Ｋの値がクライアントの現行秘密（ＫC）と等しく、プロセスはステップ３９０で終了する。そうでない場合は、処理がステップ３４０に進み、サーバは、Ｖが値２N−２に等しいかどうかテストする。等しい場合は、Ｋの値がクライアントの現行秘密（ＫC）と等しく、プロセスはステップ３９０で終了する。そうでない場合は、処理がステップ３５０に進み、Ｖが値２（２N−２）に等しいかどうかテストする。等しい場合は、Ｋの値がクライアントの現行秘密（ＫC）と等しく、プロセスはステップ３９０で終了する。そうでない場合は、ステップ３６０で、Ｖが２N−２よりも大きいかどうかチェックする。そうでない場合は、処理がステップ３７０に進み、Ｖが減算され、ＦAを適用すること（すなわちＫ←ＦA（Ｋ））によってＫが更新され、Ｎが減算される。ステップ３６０でのテストが、Ｖが２N−２よりも大きいことを示した場合は、処理がステップ３８０に進み、Ｖから値２N−１が減算され、ＦBを適用すること（すなわちＫ←ＦB（Ｋ））によってＫが更新され、Ｎが減算される。ステップ３７０または３８０の後、処理はステップ３３０に進む。処理は、ステップ３３０、ステップ３４０、またはステップ３５０が完了を示すまで続く。図３のプロセスがステップ３９０で完了するとき、変数Ｋに含まれる値が、カウンタ値Ｃに関するクライアントでのＫCの値と等しい。したがって、クライアントおよびサーバは、Ｋ＝ＫCを使用して、暗号トランザクションを保護することができる。エラーまたはエラーを引き起こす攻撃が生じた場合、ＫおよびＫCが異なって、暗号トランザクションが失敗する。
【００３０】
（状態変換操作）
次に、例示的暗号操作ＦAおよびＦB、ならびにそれらの逆変換ＦA-1およびＦB-1に関わる上述の考察をより詳細に説明する。各種のそのような関数を使用することができ、これらの関数に関する最適な形式は、システムの要件および特徴によって異なる。
【００３１】
図４に示される例示的関数では、各関数の入力および出力は、サイズが１２８ビットである。関数ＦAでは、入力状態４００が、それぞれ６４ビットの左半分４０５と右半分４１０に分割される。右半分は、ＤＥＳ操作４１５に対する入力として提供され、操作４１５が、固定鍵ＫA1を使用してその入力（右半分４１０）を暗号化する。ＤＥＳ操作は、攻撃者が入力に関して有する可能性がある部分情報の有用性を減少するまたは除去する非線形変換としてのみ使用される。したがって、鍵ＫA1は、秘密である必要はなく、公開された定数であってよい。操作４２０で、ＤＥＳ暗号化の結果が、入力の左半分にＸＯＲ演算される。ＸＯＲ演算の結果は、左半分の結果４３５と、第２のＤＥＳ操作４２５に対する入力との両方になる。第２のＤＥＳ操作は、鍵ＫA2を使用して結果を生成し、それが操作４３０で入力の右半分４１０とＸＯＲ演算される。このＸＯＲ演算結果は、右半分の結果４４０になる。左半分の結果４３５と右半分の結果４４０が組み合わされて最終結果４４５を生成する。
【００３２】
関数ＦBの構造は、異なる鍵が使用されること以外は本質的に同じものにすることができる。特に、第１のＤＥＳ操作４５５が、鍵ＫB1を使用して入力の右半分４５０を暗号化し、ＤＥＳ操作４６０が、鍵ＫB2を使用して左半分と第１のＤＥＳ結果とのＸＯＲを暗号化する。ＦAと同様に、左半分の結果４６５と右半分の結果４６８とが組み合わされて、最終結果４７０を生成する。
【００３３】
関数ＦA-1（ＦAの逆関数）は、ＦAと同様の関数を使用して、しかし逆順で計算される。入力４７５は、左半分４７６と右半分４７７に分割される。ＤＥＳ操作４７８で、左半分４７６がＤＥＳ鍵ＫA2を使用して暗号化され、その結果が右半分４７７とＸＯＲ演算される。ＸＯＲ演算結果は、右半分の結果４８１になり、かつ鍵ＫA1を使用して暗号化を行うＤＥＳ操作４７９に対する入力として使用される。第２のＤＥＳ操作４７９の結果は、入力の左半分４７６とＸＯＲ演算されて、左半分の結果４８０を生成する。最後に、左半分の結果４８０と右半分の結果４８１とが組み合わされて、最終結果４８２を生成する。関数ＦB-1は、鍵ＫA2およびＫA1ではなくＫB2およびＫB1を使用して入力４８５が出力４９０に変換されること以外は、ＦA-1と同様である。
【００３４】
関数ＦA、ＦB、ＦA-1、およびＦB-1の主な目的は、攻撃者によって取得されている可能性がある入力に関する部分情報の有用性を破壊することである。例えば、図４に示される例示的関数ＦAで使用されるＤＥＳ操作が、関数を極端に非線形にする。１２８入力ビットそれぞれの値に関する統計情報を有する攻撃者は、（０．５よりもわずかに大きい確率で正しいビットの値の推測など）第１のＤＥＳ操作４１５に対する入力に関する統計情報を有する。しかし、たとえ攻撃者がＤＥＳ鍵ＫA1を知っていたとしても、ＤＥＳ出力は効果的にランダム化される。各更新プロセスでの２つのＤＥＳ操作が、全ての入力状態を「混合」させる。
【００３５】
したがって、個々のＤＥＳ入力ビットに関する部分統計情報は、ＤＥＳ出力ビットに関する有用な統計情報を提供せず、変換操作の全ての入力を推量することができる十分な情報を攻撃者が得ることは決してない。
【００３６】
（その他の実施形態）
図４は、ＦAおよびＦBに関する関数の１つの例示的セットのみを示す。多くの他の変形または代替設計を使用することができる。例えば、追加の丸めを使用して、生成される関数を使用することができる（例えば3-round Luby-Rackoffブロック暗号）。より一般的には、任意のブロック暗号を使用する暗号化および復号化を、関数およびそれらの逆関数に関して使用することができる。更新関数を構成するために使用される基本関数は、入力に関する漏洩した部分情報が出力に関する有用な情報を提供することを防止するためにのみ必要であり、したがってこの関数は、必ずしも暗号的に反転することが難しいものである必要はない。例えば、ＤＥＳの縮小丸め（reduced-round）変形を使用することができる。さらに、図４では、ＦAとＦBが同様の構造を有するが、必ずしもそうである必要はない。状態位置に応じて（例えば、各Ｄレベルごとに異なる関数または変更された関数を使用することによって）ＦAおよびＦBを選択または変更することもできる。
【００３７】
ＦAおよびＦBに関して他のタイプの関数を使用することもできる。例えば、入力状態が０と２Bの間の奇数値である場合、奇数定数と共にモジュロ２Bでの乗算を使用してＦAおよびＦBを実施することができ、それらの逆関数は、これもモジュロ２Bでの定数の逆数を用いた乗算を使用して実施することができる。（当然、素の母数（prime moduluses）を用いた乗算など他の操作を使用することもできる）。前述の説明は単に例として与えたものであり、関数ＦA、ＦB、ＦA-1、およびＦB-1を実施するために使用することができる多様な他の関数が存在することを当業者は理解されよう。
【００３８】
さらに漏洩抵抗力に対して、より大きな状態を使用することができ、例えば、４つの６４ビットブロックを使用し、かつ状態を更新するために４つ（またはそれより多い）ＤＥＳ操作を使用することによって、または１２８ビットハッシュ関数２つ（またはそれより多く）の適用を使用することによって、２５６ビットの状態を実施することができる。
【００３９】
本発明の代替実施形態では、他の鍵更新プロセスを使用することができる。例えば、３つ以上の更新関数（およびそれらの逆関数）を使用することによって、各親の状態が３つ以上の子状態を有することができる。実際、子の状態の数が増加するにつれて、親の状態に関わる暗号操作の数、および同じ秘密鍵を共有する状態の数も増加し、それにより攻撃者がシステムを攻撃する機会が場合により増大するが、親は任意の数の子状態を有することができる。
【００４０】
図１に関して例示的に説明した状態更新プロセスのタイプは、メモリおよび処理オーバヘッドをほとんど使用せず、それとともに同じ秘密値を使用するトランザクションの最大数が小さいため有利である。（そのような秘密値が使用される回数が増えるとそれだけ、外部監視攻撃が成功する可能性が高くなる。）したがって、代替実施形態では、（一度だけ生成される）図の最下位レベルにある状態のみを使用してトランザクションが実施され、そのため秘密値が再使用されない。これは、情報が漏洩する機会が減少するが、トランザクション当たりの処理オーバヘッドを平均約４回の更新に増大する。（また、更新プロセスの回数が２から２Ｄ−２の範囲にあるため、トランザクション当たりの時間が正確でない。しかし、ほとんどのアプリケーションが約４０よりも大きいＤの値を必要とせず、多くのデバイスが毎秒数千回の暗号操作を実施することができるため、これが問題とならないことが多い。）
【００４１】
他の代替実施形態では、クライアントが、各垂直または行レベルで値をキャッシュすることができる。より高い値をキャッシュすることによって、逆操作を実施することが必要なくなるが、わずかに多くのメモリが必要となる。そのような実施形態では、最下位レベル（単一使用）状態のみがトランザクションに関して使用される場合に、ＦAまたはＦB（そのような実施形態では、簡単な逆関数を有する必要はない）の２つの適用の平均が操作ごとに必要とされる。そのような実施に関する状態更新プロセスの図は、ハッシュツリーに類似している。一定時間のまたはより予測可能な性能を必要とする実施態様では、ＦAまたはＦBの単一の適用のみを必要とする操作の間に、利用可能な追加の処理時間を使用して、将来に必要とされる値を事前計算することができ、それにより実行時間をトランザクション当たり２つのＦAまたはＦB操作に制限する。
【００４２】
他の実施形態では、サーバが必要とするものが、ルート鍵から現行トランザクション鍵を導出するのに十分な情報のみであるため、サーバによって使用される鍵索引が、トランザクションカウンタ以外の値であってよい。
【００４３】
いくつかの適用例では、Ｃを定期的に（例えばＣがタイマによってドライブされる場合）、または実施されるトランザクション以外の何らかのイベントによって増分することができる。そのような実施形態では、クライアント（またはサーバ）が、Ｃを正常に更新し、それに対応する更新された鍵を導出することに失敗した場合、トランザクションが失敗する。クライアント（またはサーバ）によって試みられるＣの最初の値が失敗した場合、他の有望なセッション鍵値（Ｃに近い値を有するものなど）を試みることができる。（当然、Ｃのクライアントバージョンとサーババージョンがあまりに異なっている場合は、トランザクションが進まない。）鍵索引（例えばＣ）は通常、明示的に交換されるが、このような場合には、サーバが、間接的にＣを推測または取得することができることがある。
【００４４】
クライアントとサーバが共に外部監視攻撃に対して保護されることを必要とする場合、二者のトランザクションカウンタＣの大きい方を使用して、トランザクションを実施することができる。具体的には、クライアントとサーバが、カウンタ値を交換することができ、（カウンタが等しくない場合は）各デバイスがそのカウンタ値を、その値と受信した値の大きい方に等しくなるようにセットすることができる。より低い値を有するデバイスは、適切なトランザクション鍵を導出するためにその秘密を更新する。この更新は、通常の更新関数およびそれらの逆関数の組み合わせを適用することによって実施することができる。（例えば、図１に例示された技法を参照すると、状態１１７でのクライアントが、ＦA-1を２回適用し、次いでＦBを３回適用することによって、状態１３６にスキップすることができる。一般に、必要とされる更新関数の総数は、２Ｄ−１未満であるべきである。この「早送り」能力は、有限回数、ここでは３回、を超えて使用されまたは導出される状態が１つもないという特性を維持する。）この能力を実施するデバイスでは、大きくかつ不正確なＣの値が生じた場合に、システムが障害を起こさないことを保証するように注意が払われる。（例えば、デバイスは、Ｃの過度に大きいジャンプを拒否することができ、または追加の暗号認証、例えばＣの最も有意なビットを必要とすることができる）。そのようなプロトコルを使用して、暗号トランザクションにおいて、三者以上を含む実施形態に関するトランザクションカウンタに対応することができる。
【００４５】
最後に、トランザクション鍵に関して使用される実際の値は、変換関数から生成される値であってよく、または変換結果から導出される値を使用することができる。例えば、変換結果を暗号化し、またはハッシュして、セッション鍵を生成することができる。ハッシュステップは、任意の所与の鍵を用いて実施される操作の数を制限する働きをし、それにより攻撃者に漏洩する可能性がある鍵に関する情報の量を制限する働きをすることができる。別法として、または追加として、セッション鍵の使用中に追加のハッシュ操作を定期的に実施する場合があり、または新たなセッション鍵を定期的に必要とする場合がある。
【００４６】
所与の秘密鍵を用いるトランザクションの起こり得る最大数を観察するために、攻撃者は、デバイスのメモリが新たなＫCの値に更新されうる前に（例えば、ＦAまたはＦBの計算中、またはその直後に）、ターゲットデバイスをリセットすることを試みる可能性がある。しかし、多くのシステムの通常動作中にリセットが生じることがあるため、そのようなリセットは必ずしも攻撃が起こっていることを意味しない。（例えば、トランザクション中にスマートカードが除去された場合に電力が失われることがある。）したがって、１つの好ましい実施形態では、不揮発性メモリに格納された障害カウンタが、各更新プロセスの前に更新される。更新が始まる前に、カウンタをテストして、連続する障害の数が最大値を超えるかどうかを判定し、超えない場合はトランザクションが正常に進む。新たなＫCの値が計算されて、メモリに安全に書き込まれ、Ｃが増分されると、障害カウンタがリセットされる。デバイスの通常動作中に（すなわち攻撃が起こっていないときに）カウンタしきい値が超えられる可能性は、特に更新プロセスが速い場合には小さい。
【００４７】
図１、２、および３に関して説明した例示した鍵更新プロセスは、比較的小さい回数（ここでは３回）を超えるトランザクションで使用される秘密鍵値がないことを保証する。したがって、攻撃者は、３つのトランザクション自体、トランザクション鍵を生成する３つの鍵更新プロセス、およびトランザクション後のトランザクション鍵を変換する３つの更新プロセス自体の間に、秘密状態に関する情報を収集する機会を有する。作成者は、これらのプロセス中に攻撃者に漏洩する秘密に関する情報の総量が、秘密状態を損なわせるのに十分でないことを保証しなければならない。設計を特徴付けるとき、セキュリティを損なうことのない、各トランザクションから漏洩する可能性がある情報の最大量を求める、または評価することがしばしば有用である。
【００４８】
（その他の考慮事項）
不正確な計算が鍵を壊さないこと、または他の攻撃を可能にしないことを保証するために、通常は暗号操作をチェックすべきである。本発明の暗号実装は、暗号操作が正常に実施されることを保証するように誤り検出および／または誤り訂正論理と組み合わせることができ、本発明の好ましい実施形態ではそうなっている。例えば、簡単かつ効果的な技法は、理想的には２つの独立ハードウェア処理装置および実装を使用して、どちらも理想的な結果を生成することを検証するために比較器を用いて、暗号操作を２回実施するものである。２つのユニットによって生成された結果が一致しない場合、比較器は、両方の結果が使用されないようにする。信頼性よりも安全性の方が重要な状況では、比較器は、重大な誤りが生じた場合にデバイスの自己破壊をさせることができる。例えば、２回の不良ＤＥＳ操作が続けて行われた場合、またはデバイスの寿命中に５回の不良ＤＥＳ操作が行われた場合、比較器が自己破壊を生じることができる。いくつかの暗号システムでは、冗長性は必要でない。例えば、ＲＳＡでは、暗号システム実装自体に自己チェック機能を組み込むことができ、または操作後に検証を実施することができる。
【００４９】
また、ＰＯＳＴ（power-on-self-test）などの自己診断機能を組み込んで、暗号機能が損壊されていないことを検証すべきである。いくつかのスマートカードおよび他のデバイスでは、ＡＴＲ（answer-to-reset）を提供しなければ、包括的な自己テストを完了することができない。そのような場合には、自己テストを、第１のトランザクションまで、または十分なアイドル期間まで遅らせることができる。例えば、正常なＰＯＳＴ完了を示すフラグを初期設定時にセットすることができる。カードは、ホストシステムからのコマンドを待って待機しながら、ＰＯＳＴを試みることができる。ＰＯＳＴ中に受信される任意の入出力が割込みをもたらし、ＰＯＳＴを打ち消す（ＰＯＳＴ完了フラグをゼロのままである）。任意の暗号機能が呼び出された場合、デバイスは、ＰＯＳＴフラグをチェックし、（セットされていない場合は）まずＰＯＳＴを実施する。
【００５０】
（結論）
したがって、本発明は、本発明を使用していない同様のコストで複雑なデバイスよりも、攻撃に対する抵抗力がかなり強いデバイスの構成を可能にする、一連の関係する技法を包含する。さらに、システムを安全にするために複数のセキュリティ技法が必要である場合があり、他のセキュリティ方法または対抗手段と共に漏洩抵抗力を使用することができる。
【００５１】
当業者に理解されるように、上述の技法は、特定のホスト環境または形態要素に限定されない。以下のものをそれらに限定せずに含めた広い範囲の適用例に使用することができる。ISO7816-1、ISO7816-2、およびISO7816-3に実質的に準拠したスマートカード（「ISO7816準拠スマートカード」）をそれらに限定せずに含めた全ての種類の暗号スマートカード。コンタクトレスおよびプロキシミティベースのスマートカードおよび暗号トークン。値格納カードおよびシステム。暗号によって保護されたクレジットカードおよびデビットカード。顧客ロイヤリティカードおよびシステム。暗号によって認証されるクレジットカード。暗号アクセラレータ。ギャンブルおよび賭博システム。セキュア暗号チップ。タンパー・レジスタント・マイクロプロセッサ。ソフトウェアプログラム（パーソナルコンピュータやサーバなどで使用するプログラム、および暗号デバイスにロードされた、またはそこに組み込むことができるプログラムをそれらに限定せずに含む）。鍵管理デバイス。銀行用鍵管理システム。セキュアウェブサーバ。電子支払システム。マイクロペイメントシステムおよびメータ。プリペイドテレフォンカード。暗号識別カードおよびその他の一致検証システム。電子資金転送用システム。現金自動預払機。ＰＯＳ（販売時点情報管理）端末。証明書発行システム。電子バッジ。ドア開閉システム。暗号鍵を使用する全ての種類の物理的錠。テレビジョン信号復号用システム（ブロードキャストテレビジョン、衛星テレビジョン、ケーブルテレビジョンをそれらに限定せずに含む）。暗号化された音楽および他のオーディオコンテンツを復号するためのシステム（コンピュータネットワークを介して配信される音楽を含む）。あらゆる種類のビデオ信号を保護するためのシステム。知的財産保護およびコピープロテクトシステム（映画、オーディオコンテンツ、コンピュータプログラム、ビデオゲーム、画像、テキスト、データベースなどの許可されていないコピーまたは使用を防止するために使用されるシステムなど）。セルラ電話スクランブルおよび認証システム（電話認証スマートカードを含む）。セキュア電話（そのような電話用の鍵格納デバイスを含む）。暗号ＰＣＭＣＩＡカード。ポータブル暗号トークン。および暗号データ監査システム。
【００５２】
前述したことは全て、本発明の例示的実施形態および適用例を示すが、そこから関連する変形形態、改良、および変更形態が、本発明の精神および範囲を逸脱することなく明らかになろう。したがって本発明は前述の開示に制限すべきでなく、頭記の特許請求の範囲によって解釈すべきである。
【図面の簡単な説明】
【図１】  一連のトランザクションによる鍵更新プロセスの例示的実施形態を示す図である。
【図２】  例示的クライアント側索引付き鍵更新プロセスを示す図である。
【図３】  鍵索引および基準鍵からトランザクション鍵を導出するための例示的サーバプロセスを示す図である。
【図４】  ４つの状態変換操作の例示実施形態を示す図である。
【図１】
0004216475.tif 000003
【図２】
0004216475.tif 000004
【図３】
0004216475.tif 000005
【図４】
0004216475.tif 000006