(57)【特許請求の範囲】
【請求項１】
入力メッセージを出力メッセージにマッピングする鍵付き暗号化処理を実施するための暗号システムであって、
前記鍵を表す複数の基本ブロックのネットワークを備え、
少なくともいくつかの前記基本ブロックが、入力データを出力データにマッピングするように構成され、
前記複数の基本ブロックが、前記暗号化処理を集合的に実施するように構成され、
前記ネットワークが、
前記複数の基本ブロックの第1の基本ブロックからの出力データを、複数の符号化方式のうちの選択された符号化方式に従って符号器出力へと符号化するための符号器であり、前記入力メッセージに依存する選択データに従って、前記複数の符号化方式から、前記選択された符号化方式を選択するように構成され、前記選択された符号化方式に従って符号化されると共に前記符号器出力に依存する入力を前記ネットワークを介して受け取るように、前記複数の基本ブロックの第2の基本ブロックが構成される、符号器と、
前記符号化の影響を補償するために、複数の再符号化方式のうちの選択された再符号化方式に従って、中間データを再符号化するための補償器であり、前記中間データが前記第2の基本ブロックの出力データに依存するものであり、前記選択データに従って、前記複数の再符号化方式から、前記選択された再符号化方式を選択するように構成される補償器とを備える、暗号システム。
【請求項２】
前記複数の符号化方式が、前記第2の基本ブロックの自己等価性の符号化方式であり、前記選択された符号化方式に、出力符号化方式が対応しており、前記第2の基本ブロックの前記出力データが、前記出力符号化方式に従って符号化され、前記選択された再符号化方式が、前記出力データを前記出力符号化方式からさらなる符号化方式へと再符号化する、請求項1に記載の暗号システム。
【請求項３】
前記複数の符号化方式が、アフィン符号化方式である、請求項1または請求項2のいずれか一項に記載の暗号システム。
【請求項４】
前記第1の基本ブロックの前記出力データが、前記選択データに依存する符号化方式で符号化される、請求項2または請求項3のいずれか一項に記載の暗号システム。
【請求項５】
前記選択データが、前記複数の基本ブロックの前記第1の基本ブロックからの前記出力の少なくとも一部である、請求項1から請求項4のいずれか一項に記載の暗号システム。
【請求項６】
前記複数の基本ブロックの第3の基本ブロックからの出力に対する複数の符号化方式の1つによる符号化を除去するための復号器を備える、請求項1から請求項5のいずれか一項に記載の暗号システム。
【請求項７】
前記複数の基本ブロックが、さらなる選択された符号化方式に従って符号化された入力を、前記ネットワークを介して受け取るように構成された少なくともさらなる第2の基本ブロックを備え、
前記補償器が、前記さらなる符号化の影響を補償するために、複数の再符号化方式のうちのさらなる選択された再符号化方式に従って、前記さらなる第2の基本ブロックからのさらなる出力データに依存するさらなる中間データを再符号化するように構成され、
前記再符号化方式が、前記中間データを、共通の符号化方式に従って符号化された第1のデータへと再符号化するように構成され、
前記さらなる再符号化方式が、前記さらなる中間データを、前記共通の符号化方式とたかだか加算項が異なる符号化方式に従って符号化された第2のデータへと再符号化するように構成される、請求項1から請求項6のいずれか一項に記載の暗号システム。
【請求項８】
入力メッセージを出力メッセージにマッピングする暗号化処理を実施するためのコンピュータで実装される方法であって、
入力データを出力データにマッピングするようにそれぞれが構成され、前記暗号化処理を集合的に実施するように構成された複数の基本マッピング演算を含み、
前記コンピュータで実装される方法が、
前記入力メッセージに依存する選択データに従って、複数の符号化方式から、符号化方式を選択するステップと、
前記複数の基本マッピング演算の第1の基本マッピング演算からの出力データを、前記選択された符号化方式に従って符号器出力へと符号化するステップであり、少なくとも前記符号器出力を入力データとして演算するように、前記複数の基本マッピング演算の第2の基本マッピング演算が構成される、ステップと、
前記選択データに従って、複数の再符号化方式から、再符号化方式を選択するステップと、
前記符号化の影響を補償するために、前記選択された再符号化方式に従って、中間データを再符号化するステップであって、前記中間データが前記第2の基本マッピング演算の出力データに依存するものであるステップと
を含むコンピュータで実装される方法。
【請求項９】
耐改ざん性を高めるために、入力メッセージを出力メッセージにマッピングする暗号化処理を実施するシステムを確立する、コンピュータで実装される方法であって、
前記システムが、入力データを出力データにマッピングするようにそれぞれが構成された複数の基本ブロックを備え、
前記複数の基本ブロックが、前記暗号化処理を集合的に実施するように構成されており、
前記方法が、
前記複数の基本ブロックのうちの第1の基本ブロックおよび第2の基本ブロックを識別するステップであり、前記第2の基本ブロックが、入力として、前記第1の基本ブロックの出力を受け取るように構成されるステップと、
前記第1の基本ブロックと前記第2の基本ブロックの間に符号器を配置するステップであり、前記符号器が、前記第1の基本ブロックからの前記出力を、複数の符号化方式のうちの選択された符号化方式に従って符号器出力へと符号化するように構成され、前記入力メッセージに依存する選択データに従って前記選択された符号化方式が選択されたものであり、前記符号器出力を入力データとして受け取るように、前記第2の基本ブロックが適合されるステップと、
前記符号化の影響を補償するために、複数の再符号化方式のうちの選択された再符号化方式に従って、中間データを再符号化するように、前記第2の基本ブロックの後に補償器を配置するステップであり、前記中間データが前記第2の基本ブロックの出力データに依存するものであり、前記補償器が、前記選択データに従って、前記複数の再符号化方式から、前記選択された再符号化方式を選択するように構成されるステップと
を含むコンピュータで実装される方法。
【請求項１０】
コンピュータプログラムがコンピュータ上で実行されるとき、請求項8または請求項9のいずれか一項に記載のすべてのステップを実施するように適合されたコンピュータプログラムコード手段を備えるコンピュータプログラム。
【請求項１１】
請求項10に記載の前記コンピュータプログラムを記憶するコンピュータ可読媒体。
【請求項１２】
耐改ざん性を高めるために、入力メッセージを出力メッセージにマッピングする暗号化処理を実施するシステムを確立する、装置であって、
前記システムが、入力データを出力データにマッピングするようにそれぞれが構成された複数の基本ブロックを備え、
前記複数の基本ブロックが、前記暗号化処理を集合的に実施するように構成されており、
前記装置が、
前記複数の基本ブロックのうちの第1の基本ブロックおよび第2の基本ブロックを識別する手段であり、前記第2の基本ブロックが、入力として、前記第1の基本ブロックの出力を受け取るように構成される手段と、
前記第1の基本ブロックと前記第2の基本ブロックの間に符号器を配置する手段であり、前記符号器が、前記第1の基本ブロックからの前記出力を、複数の符号化方式のうちの選択された符号化方式に従って符号器出力へと符号化するように構成され、前記入力メッセージに依存する選択データに従って前記選択された符号化方式が選択されたものであり、前記符号器出力を入力データとして受け取るように、前記第2の基本ブロックが適合される手段と、
前記符号化の影響を補償するために、複数の再符号化方式のうちの選択された再符号化方式に従って、中間データを再符号化するように、前記第2の基本ブロックの後に補償器を配置する手段であり、前記中間データが前記第2の基本ブロックの出力データに依存するものであり、前記補償器が、前記選択データに従って、前記複数の再符号化方式から、前記選択された再符号化方式を選択するように構成される手段と
を含む装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力メッセージを出力メッセージへとマッピングする鍵付きの暗号化処理を実施するための暗号システムに関し、システムは、前記鍵を表す複数の基本ブロックのネットワークを備え、基本ブロックの少なくともいくつかが、入力データを出力データにマッピングするように構成され、その複数の基本ブロックが、暗号化処理を集合的に行うように構成される。
【背景技術】
【０００２】
インターネットは、デジタルコンテンツへの簡便でありユビキタスなアクセスをユーザに提供する。インターネットには強力な配信チャネルとしての潜在的能力があるため、多くの家庭用電子(CE)製品は、インターネットに直接アクセスするように、またはインターネットへの最も有力なポータルであるPCプラットフォームと相互運用するように、努める。CE製品は、これだけに限らないが、デジタルセットトップボックス、デジタルTV、ゲームコンソール、PC、および、ますます増加するPDA、移動電話などのハンドヘルド装置、ならびにApple社のiPodなどの移動記憶装置および表示装置を含む。著作権のあるコンテンツに対する配信媒体としてインターネットを使用することは、コンテンツプロバイダの利益を確保するために避けることのできない課題を生ずる。特に、コンテンツプロバイダの著作権およびビジネスモデルを保証することが必要とされる。適切なソフトウェアがロードされたプロセッサを用いて動作されるCEプラットフォームが増加している。このようなソフトウェアは、オーディオおよび/またはビデオなど、デジタルコンテンツをレンダリング(再生)するための機能の主要部分を含むことができる。再生ソフトウェアを制御することは、コンテンツが使用されうる期間および条件を含めて、コンテンツ所有者の利益を守るための1つの方法である。従来、(PCおよびPDAを除いて)多くのCEプラットフォームは、クローズドで使用されているが、今日では、より一層多くのプラットフォームが、少なくとも部分的にオープンである。PCプラットフォームに関しては特に、コンテンツへのアクセスを提供するハードウェアおよびソフトウェアに対する完全な制御を有し、またどんなコンテンツ保護機構も攻撃し、迂回するための大量の時間と資源を有するユーザがいるものと想定されうる。その結果、コンテンツプロバイダは、ユーザまたは装置のすべてが信用されるわけではないコミュニティに向けて、敵意のあるネットワークを介して、コンテンツを合法的なユーザに送達する必要がある。
【０００３】
通常、デジタル著作権管理システムは、ラウンドと呼ばれる一連の暗号化/復号化ステップを用いて、データストリームをブロックで処理するブロック暗号に基づく暗号化技法を用いる。各ラウンド中、ラウンド特有の関数が行われる。ラウンド特有の関数は、ラウンド特有の副鍵の制御の下で実行される同じラウンド関数に基づくことができる。多くの暗号化システムに対して、ラウンド関数は、マッピングテーブルまたはルックアップテーブルを用いて指定されうる。ラウンド関数の指定が明示的にテーブルの使用を含んでいない場合であっても、暗号化/復号化関数のソフトウェアで効率的に実行するために、関数の様々な部分に関する実装において、テーブルがしばしば使用される。コンピュータコードはテーブル値にアクセスし、またはテーブル値を関数のある範囲の値へと組み合わせる。ユーザ特有でありうる鍵を配布するのに代えて、暗号化または復号化アルゴリズムのための鍵ではなく、ユーザに特有のアルゴリズムを配布することは、より興味深いものとなる。これらのアルゴリズムは、ほとんどの場合は関数(マッピング)であるが、鍵と同様の要素を再設計することを阻止する、または再計算できないようにするために、難読化(隠す)される必要がある。コンピュータ上で、何らかのコンピュータコードを伴うテーブルは、これらの関数を表すことが多い。
【０００４】
コンテンツプロバイダは、すべてのユーザまたは装置が信用され得るわけではないコミュニティに向けて、敵意のあるネットワークを介して、コンテンツを合法的なユーザに送達する必要がある。PCプラットフォームに関しては特に、ユーザは、コンテンツへのアクセスを提供するハードウェアおよびソフトウェアに対する完全な制御を有し、またどんなコンテンツ保護機構も攻撃し、迂回するために、無制限の時間と資源を有するものと想定される必要がある。コンテンツが使用されうる期間および条件を強制するソフトウェアコードは、改ざんされてはならない。PCに配信される保護されたコンテンツに対するデジタル著作権管理における一般的な手法は、デジタルコンテンツを、例えば、DES(Data Encryption Standard:データ暗号化規格)、AES(Advanced Encryption Standard:次世代暗号標準)で、または国際公開9967918号で開示された方法を用いて暗号化し、復号鍵を用いることである。
【０００５】
暗号化を利用するデジタル著作権管理の脆弱性の2つの主な領域は、コンテンツが使用されうる期間および条件を強制するソフトウェアプラグイン、および鍵の配布、取扱いである。
【０００６】
通常、プラグインは、コンテンツが使用されるべき期間および条件を強制する。これらの期間および条件を除去することを狙う攻撃者は、ソフトウェアプラグインに含まれるプログラムコードを改ざんすることによりこの目的を達成しようと試みる可能性がある。
【０００７】
鍵の取扱いに関係して、メディアプレイヤは、再生するためにライセンスデータベースから復号鍵を取り出すことが必要である。次いで、この復号鍵を、暗号化されたコンテンツを復号するために、メモリのどこかに記憶する必要がある。これは、鍵に対する攻撃のために、2つの選択肢を攻撃者に与えることになる。まず、ライセンスデータベースアクセス関数のリバースエンジニアリングにより、ブラックボックスのソフトウェアが得られ(すなわち、攻撃者は、ソフトウェア関数の内部動作を理解する必要はない)、攻撃者は、すべてのライセンスデータベースからアセット鍵を取得できるようになる。第2に、コンテンツの復号中に、メモリへのアクセスを観察することにより、アセット鍵を取り出すことが可能になる。両方の場合で、鍵は、損なわれたと見なされる。以下では、一般に、ソフトウェアが、どのようにして耐改ざん性を有するようにされうるかの記述が提供される。
【０００８】
耐改ざん性を有するソフトウェアは、ソフトウェアを用いた目標指向の改ざんが複雑であるためにそのように呼ばれる。ソフトウェアアプリケーションの耐改ざん性を高めるための様々な技法が存在する。これらの技法の大部分は、ソフトウェアアプリケーションの制御とデータパスの両方を不規則性および複雑さのベールで覆うことにより、アプリケーションに関する埋め込まれた知識を隠すことに基づいている。この背後にある考えは、単にコード検査をするだけで情報を抽出しようとすることが、一層困難になるということである。したがって、例えば、アプリケーションのアクセスおよび許可の制御を処理し、最終的にそれを変更するコードを見出すことはさらに困難である。
【０００９】
以降で、「Chow1」と呼ばれる、Stanley Chow、Philip Eisen、Harold Johnson、およびPaul C. Van Oorschotによる「White-Box Cryptography and an AES Implementation」、Selected Areas in Cryptography: 9th Annual International Workshop、SAC 2002、セントジョンズ、ニューファウンドランド州、カナダ、2002年8月15〜16日、および以降で、「Chow2」と呼ばれる、Stanley Chow、Phil Eisen、Harold Johnson、およびPaul C. van Oorschotによる「A White-Box DES Implementation for DRM Applications」、Digital Rights Management: ACM CCS-9 Workshop、DRM 2002、ワシントン、DC、米国、2002年11月18日は、そのテーブルをランダムな全単射で符号化することと、暗号境界を、含んでいるアプリケーションへとさらに広げて拡張することを組み合わせることにより、鍵を隠すように意図する方法を開示する。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】国際公開第9967918号
【非特許文献】
【００１１】
【非特許文献１】Stanley Chow、Philip Eisen、Harold Johnson、およびPaul C. Van Oorschotによる「White-Box Cryptography and an AES Implementation」、Selected Areas in Cryptography: 9th Annual International Workshop、SAC 2002、セントジョンズ、ニューファウンドランド州、カナダ、2002年8月15〜16日
【非特許文献２】Stanley Chow、Philip Eisen、Harold Johnson、およびPaul C. Van Oorschotによる「A White-Box DES Implementation for DRM Applications」、Digital Rights Management:ACM CCS-9 Workshop、  DRM 2002、ワシントンDC、米国、2002年11月18日
【非特許文献３】W. Michiels, P. Gorissen、およびH.D.L. Hollmannによる「Cryptanalysis of a Generic Class of White-Box Implementations」、出典:Proceedings of the 15th Annual Workshop on Selected Areas in Cryptography (SAC 2008)、サックヴィル、ニューブランズウィック州、カナダ、2008年
【非特許文献４】A. Biryukov、C. De Canniere、A. Braeken、およびB. Preneelによる「A Toolbox for Cryptanalysis: Linear and Affine Equivalence Algorithms.」、Proceedings of Eurocrypt、2003、33〜50頁
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかし、以降で「Michiels1」と呼ばれる、W. Michiels, P. Gorissen、およびH.D.L. Hollmannによる「Cryptanalysis of a Generic Class of White-Box Implementations」、出典:Proceedings of the 15th Annual Workshop on Selected Areas in Cryptography (SAC 2008)、サックヴィル、ニューブランズウィック州、カナダ、2008年で、Chowの手法の弱点が指摘された。この弱点は攻撃者により利用され、また最悪の場合、ホワイトボックス実装に隠された秘密鍵が洩れる結果になりうる。
【００１３】
Michiels他による主要な観察は、Chowによるホワイトボックス実装における各ラウンドの個々の入力ワードは、普通の非ホワイトボックス実装における対応する入力ワードに対して特定の関係にあるということである。この関係は、個々の入力値以外の他の入力値を参照することなく表現されうる。この関係は、鍵に依存しており、攻撃者には未知のものであるが、上記で参照された論文でさらに説明されるように、この特徴は、ホワイトボックスを破ることを実質的に簡単化する十分な構造を提供する。
【課題を解決するための手段】
【００１４】
入力メッセージを出力メッセージにマッピングする暗号化処理を実施するための改善された暗号システムを有することは有利なはずである。この問題に良好に対処するために、本発明の第1の態様では、入力メッセージを出力メッセージにマッピングする鍵付きの暗号化処理を実施するための暗号システムが提示される。暗号システムは、前記鍵を表す複数の基本ブロックのネットワークを備え、基本ブロックの少なくともいくつかは、入力値を出力値にマッピングするように構成されており、その複数の基本ブロックが、暗号化処理を集合的に実施するように構成される。ネットワークは、複数の基本ブロックの第1の基本ブロックからの出力データを、複数の符号化方式のうちの選択された符号化方式に従って符号器出力へと符号化するための符号器であり、入力メッセージに依存する選択値に従って、複数の符号化方式から、選択された符号化方式を選択するように構成され、選択された符号化方式に従って符号化されると共に符号器出力に依存する入力をネットワークを介して受け取るように、複数の基本ブロックの第2の基本ブロックが構成される、符号器と、符号化の影響を補償するために、複数の再符号化方式のうちの選択された再符号化方式に従って、第2の基本ブロックの出力値に依存する中間値を再符号化するための補償器であり、選択値に従って、複数の再符号化方式から、選択された再符号化方式を選択するように構成される補償器とを備える。
【００１５】
より一般的には、第1のブロックの出力データは、入力に依存する符号化方式に従って符号化される。補償器は、その後で符号化を調整する。
【００１６】
主要な観察で述べたように、Chowの構成に脆弱性があることの1つの理由は、ホワイトボックス実装における各ラウンドの個々の入力値と、普通の非ホワイトボックス実装における個々の入力値との間に存在する固定関係である。本発明は、ある値を符号化する符号器が導入されるが、何らかの固定された符号化方式によるのではなく、複数の符号化から選ばれた符号化を用いる。この特徴は、固定された関係を壊すものである。符号器出力は、もはや、暗号化処理の非ホワイトボックス実装における何らかの個々の入力値との固定された関係はない。何らかの関係は存在することになるが、個々の入力値に依存するだけではなく、他の入力値にも依存することになる。この複雑さは、Michiels1で提示された攻撃を失敗させるのに十分である。
【００１７】
値の固定された符号化を壊すことにより、暗号システムのリバースエンジニアリングがより困難になるが、それは、リバースエンジニアにとって、本発明による暗号システムの動作を、暗号化処理の非ホワイトボックスバージョンの動作と比較することがより困難になるからである。
【００１８】
「第1の基本ブロック」における用語「第1」とは、第1の基本ブロックを他の基本ブロックと区別するために使用されることに留意されたい。第1の基本ブロックは、必ずしも入力メッセージを受け取る基本ブロックである必要はない。
【００１９】
前に述べたように、多くの暗号化処理に対して、ホワイトボックス実装を有することが望ましい。本発明は、例えば、対称および非対称暗号化処理に適用されうる。さらに、本発明は、ブロック暗号、ストリーム暗号、メッセージ認証方式、シグネチャ方式などに適用されうる。本発明はまた、ハッシュ関数にも適用されうることに留意されたい。後者は、ハッシュ関数が、例えば、秘密鍵、秘密データなどの秘密情報を処理するためのビルディングブロックとして使用される場合、特に有用である。例えば、本発明は、HMACまたはKHMAC(keyed-Hash Message Authentication Code:鍵付きハッシュメッセージ認証コード)で使用されるハッシュ関数に適用されうる。よく知られたブロック暗号は、AES(Advanced Encryption Standard:次世代暗号標準)、SAFER、その変形SAFER+およびSAFER++(Secure And Fast Encryption Routine)、Blowfish、DES(Data Encryption Standard:データ暗号化規格)などを含む。よく知られたストリーム暗号はRC4である。さらに、任意のブロック暗号は、例えば、CFB(Cipher feedback:暗号フィードバック)、CTR(Counter mode:カウンタモード)などの適切な動作モードを用いてストリーム暗号として使用されうる。
【００２０】
入力メッセージは、例えば、オーディオおよび/またはビデオデータを含むマルチメディアデータなどの暗号化されたコンテンツデータを表すことができる。暗号化されたコンテンツデータはまた、例えば、コンピュータゲーム、またはオフィスアプリケーションなどの何らかのコンピュータアプリケーションを表す暗号化されたコンピュータコードなど、暗号化されたソフトウェアを含むことができる。入力メッセージはまた、さらなる暗号化処理で使用するための鍵を表すことができる。後者は、例えば、鍵交換プロトコルで使用されうるが、本発明によるホワイトボックス実装は、新しい鍵を表すデータを暗号化し、かつ/または復号する。入力データはまた、例えば、平文ユーザデータなど、平文データとすることができる。後者は、メッセージ認証方式において特に有利である。本発明によるホワイトボックス実装は、その実装が、暗号化のためにだけ使用され、復号化のためにだけ使用され、両方で使用されえないという特性を有することができる。例えば、この特性は、その実装が、例えば、出力ビットよりも多くの入力ビットを有するルックアップテーブルなど、全単射ではないルックアップテーブルを使用する場合に達成されうる。したがって、ユーザが、ホワイトボックス復号器だけを有する場合、ユーザはMACコードを検証することができるが、新しいMACを作成することはできない。これは、このようなメッセージ認証方式の否認防止特性を強化する。
【００２１】
いくつかのブロックが、1つまたは複数の前のブロックの出力上に構築されるという意味で、複数の基本ブロックは相互接続される。基本ブロックは、例えば、コンピュータチップとして、ハードウェアで実施されうる。基本ブロックは、コンピュータハードウェアで関数を実施するために、スイッチボード、状態マシン、または任意の他の適切な構成を使用することができる。基本ブロックはまた、例えば、マイクロプロセッサなど、汎用のコンピュータチップ上で動作するソフトウェアで実施されうる。例えば、基本ブロックは、算術命令を含む複数のコンピュータ命令を使用することができ、それらは共に、基本ブロックの機能を実施する。ソフトウェアおよびハードウェアで共に使用されうる基本ブロックのための好ましい実施形態は、ルックアップテーブルである。ルックアップテーブル実装は、可能な入力値、出力値を一覧にするリストを備える。入力値は、ルックアップテーブル中で明示されうる。その状況において、ルックアップテーブル実装は、特定の入力に対する入力値のリストの中を検索することにより、特定の入力を特定の出力にマップすることができる。特定の入力が見出された場合、特定の出力も見出される。例えば、特定の出力は、特定の入力と並んで記憶されうる。入力値は、明示的にではなく、暗黙的にだけ記憶されることが好ましい。例えば、可能な入力が、連続する一連の、例えば、数またはビットストリングである場合、ルックアップテーブルは、出力値のリストを記憶することに限定されうる。特定の入力数が、例えば、数により示される位置に記憶される特定の出力へとマッピングされうる。
【００２２】
例えば、関数に対するルックアップテーブルは、その可能な入力に対する関数の出力値を計算することにより、またリストの中に出力を記憶することにより作成されうる。関数が、複数の入力に依存している場合、出力は、複数の入力のすべての可能な組合せに対して計算され、かつ記憶されうる。ルックアップテーブルは、変則的な方法で入力を出力にマッピングする非線形関数を実施するのに特に適している。ホワイトボックス実装はさらに、以下で説明されるように、固定され難読化された入力符号化、および固定された出力符号化を、その1つまたは複数のルックアップテーブルに適用することにより、さらに難読化されうる。固定され難読化された入力符号化、および出力符号化を適用した結果が、次いで、完全に事前評価される。この技法を用いれば、ルックアップテーブルは、同じ数の入力ビットを使用し、かつ同じ数の出力ビットを生成する同じディメンジョンを有する難読化されたルックアップテーブルにより置き換えられることになる。このような難読化で使用される入力符号化および出力符号化は、最終的なホワイトボックス実装において明示的ではない。本発明で、良好な難読化が達成されるが、そのことは固定されるのではなく、選択値に依存する符号化を導入する。本明細書で述べる可変の符号化は、有利には、従来の難読化技法と組み合わされうると共に、それらは合わさって、暗号化処理の内部動作をさらに曖昧にすることに留意されたい。
【００２３】
基本ブロックのネットワークは、入力メッセージと共に提示されたとき、出力メッセージを計算するように構成される。通常、入力メッセージは、いくつかの基本入力ブロックにより演算される。いくつかのさらなる基本ブロックは、1つまたは複数の基本入力ブロックから、かつ/または入力から、入力を得ることができる。さらに、他の基本ブロックは、入力メッセージ、基本入力ブロックの出力、およびさらなる基本ブロックの出力の任意の組合せで入力を得ることができる。最終的に、何組かの基本出口ブロック、すなわち、少なくとも1つは、出力として、出力メッセージのすべて、または一部を生成する。この方法では、入力メッセージから出力メッセージへのマッピングを集合的に計算する基本ブロックのネットワークが現れる。
【００２４】
使用される鍵は、暗号鍵であることが好ましく、また予想される総当たり攻撃に耐えるのに十分なエントロピーを含むことが好ましい。ホワイトボックス実装では、鍵は、その実施中に明示的に示されないことが好ましいことに留意されたい。これは、実施内容を調べることにより鍵が発見される危険にさらすことになる。鍵は、暗黙的に示されるだけであることが好ましい。暗号システムで、鍵を隠すための様々な方法が知られている。少なくとも部分評価法が使用されることが好ましく、その場合、鍵入力を必要とする基本ブロックは、入力メッセージに依存しない限り評価される。例えば、S-boxからの値などの入力メッセージに依存しない入力値、マスキング値、および鍵の値がXOR演算される必要のある基本演算は、事前に、鍵の値およびマスキング値を共にXOR演算することにより、部分的に評価されうる。この方法では、鍵の値は実装中に明示的に示されないが、演算はなお鍵の値に依存している。それに代えて、鍵の値とマスキング値の間のXOR演算だけが実装中に存在する。鍵を隠すさらに複雑な方法、および/またはさらなる方法は、本発明と互換性があることに留意されたい。
【００２５】
様々な符号化方式が本発明と共に使用されうる。符号化方式は、データ値を表現する新しい方法を与える。符号化方式は単射である。必須ではないが、符号化はまた、全単射であることが好ましい。
【００２６】
選択値は様々な方法で計算されうるが、例えば、選択値は、適切なハードアエアまたはソフトウェアを使用して、おそらく、実装中の他の値にも依存する入力メッセージ、例えば、ルックアップテーブル中の1つまたは複数の鍵に依存する値から計算されうる。
【００２７】
第2の基本ブロックは、データを受け取るように構成されるが、選択された符号化を用いて符号化される。符号化の後、データは、符号化された形でネットワークを進む。第2の基本ブロックは、選択値に基づいて適合される必要のないことが好ましい。すなわち、第2の基本ブロックは、選択値の値ごとに、出力値に対する入力値の同じマッピングを行うことができる。任意選択で、第2の基本ブロックは、符号化されたデータに対する中間演算を実質的に行うことなく、符号器出力に対して直接演算する。しかし、中間演算が存在することもありうる。特に、選択された符号化方式を遵守する演算が、第2の基本ブロックの前に行われる可能性がある。符号化方式を遵守する演算は、符号化された入力値だけを受け取る場合であっても、入力値に対応する正しい出力値を生成するが、出力値はまた、その符号化方式で符号化される。
【００２８】
例えば、符号化方式は、独立して働くことができるが、同様に、符号器入力の等しい部分における区分の異なる部分に対して働くことができる。区分の一部を並び替える次の転置処理は符号化方式を遵守している。例えば、何らかの特定のニブル符号化演算を共に用いて、互いに独立した第1および第2のニブルを符号化することにより、バイトが符号化されうる。第1および第2のニブルをその後に交換することは、この符号化方式を遵守する。
【００２９】
符号器は、その入力値に対して、例えば、同じ暗号化処理の非ホワイトボックス実装における値に対応する入力値に対して、直接演算することができる。他方で、何らかの難読化を、例えば、何らかのタイプの符号化を使用することができ、それは、符号器の入力値に、すなわち、第1の基本ブロックの出力値に対して使用されうる。第1の基本ブロックの出力値に対して使用される符号化はまた、例えば、選択値などの他の値に依存することができる。
【００３０】
例えば、前記第1のブロック、すなわち、複数の基本ブロックの前記第1の基本ブロックは、出力値x+νを生成することができる。符号器は、入力として選択値νおよび出力値x+νをとる。これらの2つの入力から、符号器は、複数の符号化方式のν’番目の符号化方式に従って符号化されたxを生成することができる。出力値「x」は、様々な方法で符号化され、かつ/または難読化されうることに留意されたい。例えば、第1の基本ブロックは、2つのルックアップテーブルを含んでもよく、値「x1」および「x2」を生成する。符号器は、例えば、「x1」および「x2」の連結として、「x」を再構成することができる。さらなる例として、+0を、普通の算術加算とすると、すなわちXOR加算ではないとすると、第1の基本ブロックにおける第1のエンティティは、第1の値x+0νを生成し、また第1の基本ブロックにおける第2のエンティティは、第2の値2x+0νを生成することができる。これらの2つの値から、符号器は、「x」(例えば、第2の値と第1の値の算術減算として)および「ν」(例えば、2回の第1の値と第2の値の算術減算として)を共に再構成することができる。
【００３１】
xが、同じ鍵に対する暗号化処理の非ホワイトボックス実装で使用される値に対応する場合、本発明の暗号システムにおける符号化ステップの後、xは、入力に依存する複数の符号化方式から選択された符号化方式に従って符号化が行われることが理解されうる。
【００３２】
入力値が、さらに可変の符号化方式で符号化されると、通常、第2の基本ブロックの出力、すなわち、複数の基本ブロックの前記第2の基本ブロックは、第2の基本演算を行った後、おそらく、大幅に撹拌されることになる。補償器は、符号化の影響を補償するために、第2の基本ブロックの出力を再符号化する。符号化方式は、選択値に依存するので、やはり選択値に依存する再符号化方式が選択される。補償器はまた、第2の基本ブロックの出力に依存する中間値を再符号化することができる。例えば、XORネットワークは、第2の基本ブロックと補償器の間に配置されうる。
【００３３】
好ましい実施形態では、複数の符号化方式は、第2の基本ブロックの自己等価性の(self-equivalent)符号化方式である。出力符号化方式は、選択された符号化方式に対応する。第2のブロックの出力値は、出力符号化方式に従って符号化される。選択された再符号化方式は、出力値を出力符号化方式からさらなる符号化方式へと再符号化する。
【００３４】
基本演算の自己等価性の符号化方式は、対応する出力符号化方式を有する。1対の自己等価性の符号化方式と出力符号化方式は、入力値がある符号化方式を用いて符号化される場合であっても、第2の基本ブロックは入力値に対応する正しい出力値を計算するが、正しい出力値は、次いで、出力符号化方式を用いて符号化されるという特性を有する。出力符号化方式は、入力符号化方式と異なることもありうる。
【００３５】
好ましい実施形態では、符号化方式はアフィン関数である。特に、符号器が選択値を用いて選択する符号化は、アフィン自己等価性符号化である場合が好ましい。アフィン自己等価性符号化を決定することは、任意の適切な方法を用いて行なわれうる。例えば、A. Biryukov、C. De Canniere、A. Braeken、およびB. Preneelによる「A Toolbox for Cryptanalysis: Linear and Affine Equivalence Algorithms.」、Proceedings of Eurocrypt、2003、33〜50頁の論文で述べられており、以降でBiryukov1と呼ぶ。
【００３６】
これは、第2の基本ブロックの出力が、アフィン関数を用いて符号化されることを暗に示しているので、アフィン自己符号化を用いることが好ましい。以下では、どのようにして、アフィン符号化が比較的容易に適用され、再符号化され、または除去されうるかが述べられる。従って、符号化がアフィンである場合、符号化は、大量のオーバヘッドなく補償されうる。例えば、アフィン符号化は、第2のブロックの出力がそれにより符号化された後続するアフィン符号化を除去することにより補償されうる。
【００３７】
好ましい実施形態では、選択値は、複数の基本ブロックの第1の基本ブロックからの出力の少なくとも一部である。これは、わずかな計算資源を必要とするに過ぎないが、内部で使用される符号化の多様化を達成する。
【００３８】
補償器が、符号化に対して補償した後、補償された出力は、基本ブロックにより、例えば、第3の基本ブロックによりさらに演算されうる。好ましい実施形態では、暗号システムは、複数の符号化方式の1つによる複数の基本ブロックの第3の基本ブロックからの出力に対する符号化を除去するための復号器を備える。
【００３９】
好ましい実施形態では、複数の基本ブロックは、さらなる選択された符号化方式に従って符号化された入力を、ネットワークを介して受け取るように構成された少なくともさらなる第2の基本ブロックを備え、補償器は、さらなる符号化の影響を補償するために、複数の再符号化方式のうちのさらなる選択された再符号化方式に従って、さらなる第2の基本ブロックからのさらなる出力値に依存するさらなる中間値を再符号化するように構成され、再符号化方式は、中間値を、共通の符号化方式に従って符号化された第1の値へと再符号化するように構成され、さらなる再符号化方式は、さらなる中間値を、共通の符号化方式とたかだか加算項(additive)が異なる符号化方式に従って符号化された第2の値へと再符号化するように構成される。
【００４０】
符号化された入力を受け取る複数の第2のブロックがありうる。第2の基本ブロック、およびさらなる第2の基本ブロックは、通常異なっているので、それらの入力符号化に対して異なって影響を与えることになり、それに応じて、これらの差に対して異なる方法で補償できる補償器を有することは有利である。さらに、入力は、同じ選択された符号化を用いて符号化されうるが、それらは、異なる選択された符号化に従って符号化されることが好ましい。特に、第2の基本ブロックおよびさらなる第2の基本ブロックへの入力は、自己等価性の符号化で符号化されることが好ましく、アフィン符号化であることが好ましい。通常、異なる基本ブロックに対する自己等価性の符号化の集合は異なる。中間値およびさらなる中間値が補償された後、それらが同じ共通の符号化にしたがって符号化される場合は有利である。これはさらに処理を簡単化する。他方で、符号化が最高で加算項まで等しい場合もさらに有利でありうる。加算項とは、符号化、再符号化、または復号化ステップを適用する間に加えられる項である。加算項の例は、アフィン符号化でXOR演算される値である。加算項は、事前に決められていることが好ましい。
【００４１】
例えば、共通の符号化方式がアフィン符号化方式であり、また補償の後の演算が、中間値とさらなる中間値のXOR演算である場合、加算項を除外することは計算を簡単化する。2つの値に対して同じ加算項がXOR演算され、これらの2つの値が、互いにその後XOR演算される場合、加算項は相殺される。しかし、加算項が値の一方とXOR演算されるだけであり、他方に対して行われない場合、加算項は、後続するXOR演算で相殺されることはない。ビットに対してXOR演算は、GF(2)（GF：Galois Field（ガロア体））に対する加算であることに留意されたい。
【００４２】
本発明のさらなる態様は、入力メッセージを出力メッセージにマッピングする暗号化処理を実施する暗号法である。方法は、複数の基本マッピング演算を含み、それぞれが、入力値を出力値にマッピングするように構成され、その複数の基本マッピング演算が、暗号化処理を集合的に実施するように構成される。暗号法は、入力メッセージに従って、複数の符号化方式から、選択された符号化方式を選択するステップと、複数の基本マッピング演算の第1の基本マッピング演算からの出力値を、選択された符号化方式に従って符号器出力へと符号化するステップであり、少なくとも符号器出力を入力データとして演算するように、複数の基本マッピング演算の第2の基本マッピング演算が構成される、ステップと、選択値に従って、複数の再符号化方式から、選択された再符号化方式を選択するステップと、符号化の影響を補償するために、複数の再符号化方式のうちの選択された再符号化方式に従って、第2の基本マッピング演算の出力値に依存する中間値を再符号化するステップとを含む。
【００４３】
本発明のさらなる態様は、耐改ざん性を高めるために暗号化処理を実施するシステムを確立する方法である。システムは、複数の基本ブロックを備え、それぞれが、入力値を出力値へとマッピングするように構成され、その複数の基本ブロックが、暗号化処理を集合的に実施するように構成される。本方法は、複数の基本ブロックのうちの第1の基本ブロックおよび第2の基本ブロックを識別するステップであり、第2の基本ブロックが、入力として、第1の基本ブロックの出力を受け取るように構成されるステップと、第1の基本ブロックと第2の基本ブロックの間に符号器を配置するステップであり、符号器が、第1の基本ブロックからの出力を、複数の符号化方式のうちの選択された符号化方式に従って符号器出力へと符号化するように構成され、符号器出力を入力データとして受け取るように、第2の基本ブロックが適合されるステップと、符号化の影響を補償するために、複数の再符号化方式のうちの選択された再符号化方式に従って、第2の基本ブロックの出力値に依存する中間値を再符号化するように、第2のブロックの後に補償器を配置するステップであり、補償器が、選択値に従って、複数の再符号化方式から、選択された再符号化方式を選択するように構成されるステップとを含む。
【００４４】
第1の基本ブロックと第2の基本ブロックの間に符号器を配置するステップは、例えば、符号器が、第1のブロックから直接または間接的に入力を受け取り、かつ第2のブロックが、符号器から直接または間接的に入力を受け取るように、基本ソフトウェアブロックおよび/または基本ハードウェアブロックを構成することにより実施されうる。同様に、第2のブロックの後に補償器を配置するステップは、第2のブロックから入力を受け取るように補償器を配置することにより実施されうる。
【００４５】
ホワイトボックス暗号は、しばしば、非常に複雑化され、かつ/または難読化されるので、記述することは人間にとって時間がかかる。したがって、自動化された方法で、本発明による暗号システムを作成する方法を有することは有利である。
【００４６】
本発明による方法は、コンピュータで実施される方法として、または専用のハードウェアで、またはその両方の組合せで、コンピュータ上で実施されうる。本発明による方法のための実行可能なコードは、コンピュータプログラム製品に記憶されうる。コンピュータプログラム製品の例は、メモリ装置、光学的記憶装置、集積回路、サーバ、オンラインのソフトウェアなどを含む。
【００４７】
好ましい実施形態では、コンピュータプログラムは、コンピュータプログラムがコンピュータ上で実行されるとき、本発明による方法のすべてのステップを実施するように適合されたコンピュータプログラムコード手段を含む。コンピュータプログラムは、コンピュータ可読媒体で実施されることが好ましい。
【００４８】
ホワイトボックス暗号システムは、したがって、その内部の値の少なくとも1つが、入力に依存する符号化を用いて表されるように提示される。システムは、暗号化処理を集合的に実施するように構成された複数の基本ブロックのネットワークを備える。符号器は、複数の符号化方式のうちの選択された符号化方式に従って、複数の基本ブロックの第1の基本ブロックからの出力データを符号器出力へと符号化するように構成され、前記選択は、システムへの入力メッセージに依存する。補償器は、符号化の影響を補償するために、複数の再符号化方式のうちの選択された再符号化方式に従って、中間データを再符号化するように構成される。固定された符号化に代えて、可変の符号化を用いることは、ホワイトボックス暗号システムのリバースエンジニアリングを複雑化する。
【００４９】
本発明のこれらの、かつ他の態様は、以下で図面を参照することにより明らかにされよう。
【図面の簡単な説明】
【００５０】
【図１】AESのラウンドにおける処理を示す図である。
【図２】難読化テーブルの例を示す図である。
【図３】ホワイトボックスAES実装における列に対するラウンドを示す図である。
【図４】タイプIaテーブルに組み込まれたマッピングを示す図である。
【図５】タイプIIテーブルに組み込まれたマッピングを示す図である。
【図６】タイプIIIテーブルに組み込まれたマッピングを示す図である。
【図７】タイプIVテーブルに組み込まれたマッピングを示す図である。
【図８】タイプIbテーブルに組み込まれたマッピングを示す図である。
【図９】符号化を用いたホワイトボックス実装を示す図である。
【図１０】符号化を示す図である。
【図１１】一実施形態を示す図である。
【発明を実施するための形態】
【００５１】
AESは、128ビット、すなわち16バイトのブロックサイズを用いるブロック暗号である。平文は、16バイトのブロックに分割されて、符号化アルゴリズムの最初の状態を形成し、また符号化アルゴリズムの最終状態は暗号文である。AESを概念的に説明するために、その状態のバイトは、4×4バイトの行列として編成される。AESは、いくつかのラウンドからなる。各ラウンドは、状態行列のバイト、行、または列に対して働く同様の処理ステップから構成され、各ラウンドは、これらの処理ステップにおいて、異なるラウンド鍵を用いる。
【００５２】
図1は、AESのラウンドのいくつかの主要な処理ステップを示している。処理ステップは、下記のものを含む。
・AddRoundKey2 -  状態の各バイトはラウンド鍵のバイトとXOR演算される。
・SubBytes4 -  ルックアップテーブルを用いたバイト対バイトの転置処理。
・ShiftRows6 -  状態の各行は、固定数のバイトで回転される。
・MixColumns8 -  各列は、GF(28)におけるモジュロ乗算を用いて処理される。
【００５３】
ステップSubBytes4、ShiftRows6、およびMixColumns8は、使用される特定の鍵とは独立している。鍵は、ステップAddRoundKey2で適用される。ステップShiftRows6を除いて、処理ステップは、他の列の知識を必要とせずに、4×4状態行列の各行に対して実施されうる。したがって、それらは、各列が4個の8ビット値からなるので、32ビットの演算と見なされうる。破線10は、処理が、必要なラウンド数が実施されるまで繰り返されることを示している。
【００５４】
これらのステップのそれぞれ、またはステップの組合せは、ルックアップテーブルにより、またはルックアップテーブルのネットワーク(S-box)により表されうる。AddRoundKeyステップが、ラウンド鍵でXOR演算されることにより実施された場合、鍵を、攻撃者はホワイトボックス攻撃コンテキストで見ることができる。AddRoundKeyステップはまた、鍵を見出すことをより曖昧にするルックアップテーブルの中に埋め込まれうる。実際に、ルックアップテーブルのネットワークによりAESのすべてのラウンドを置き換えることも可能である。例えば、SubBytes、ShiftRows、およびMixColumnsステップは、テーブル参照を用いて実施されうる。以下で、AESの可能なホワイトボックス実装をより十分に論ずるものとする。
【００５５】
図2は、鍵を抽出することをより一層困難にする方法を示している。AES暗号化などの暗号化処理が、基本演算ネットワークへと変換された後、さらなる難読化が可能である。XおよびYを2つの関数、すなわち、基本演算とする。図の12で示された合成演算
【００５６】
【数１】
0005688528.tif 000002
【００５７】
を考え、すなわち、合成演算を得るために、YはXの後で行われる。ここで、cは入力値であり、例えば、4バイトの状態列である。しかし、本手法は、任意のタイプの入力値cに対して適用される。XおよびYのマッピングは、ルックアップテーブルとして実施することができ、それらはメモリに記憶されうるが、それらがメモリに記憶された場合、その値は、攻撃者に読み取られるおそれがある。図の14は、ルックアップテーブルのコンテンツが、どのようにして入力符号化Fおよび出力符号化Hを用いることにより、難読化されうるかを示している。
【００５８】
【数２】
0005688528.tif 000003
【００５９】
および
【００６０】
【数３】
0005688528.tif 000004
【００６１】
に対応するルックアップテーブルが、図示される通りXおよびYの代わりに記憶され、XおよびYを抽出することをより困難にしている。図の16は、2つのテーブルの中間結果も符号化されるように、どのようにして、さらなる、例えば、ランダムな、全単射関数Gを追加するかを示している。この場合、2つのテーブルはメモリに記憶される。すなわち、
【００６２】
【数４】
0005688528.tif 000005
【００６３】
および
【００６４】
【数５】
0005688528.tif 000006
【００６５】
である。これは、図の18で再度示される。すなわち、
【００６６】
【数６】
0005688528.tif 000007
【００６７】
であり、式中
【００６８】
【数７】
0005688528.tif 000008
【００６９】
は、通常通り関数の合成を示し(すなわち、任意の2つの関数f(x)およびg(x)に対して定義すれば、
【００７０】
【数８】
0005688528.tif 000009
【００７１】
である。)、XおよびYは、ルックアップテーブルにより実施するのに適した関数である。同様に、2つを超える関数からなるネットワークも符号化されうる。XおよびYを符号化する実際のテーブルは、単一のルックアップテーブルで、
【００７２】
【数９】
0005688528.tif 000010
【００７３】
を組み合わせることにより、かつ単一のルックアップテーブルで、
【００７４】
【数１０】
0005688528.tif 000011
【００７５】
を組み合わせることにより難読化される。F、G、および/またはHが未知のままである限り、攻撃者は、ルックアップテーブルからXおよび/またはYに関する情報を抽出することができず、したがって、攻撃者は、Xおよび/またはYに関する基礎である鍵を抽出することができない。DESおよびRijndael(そのAESは特定のインスタンス化である)を含む他の暗号アルゴリズムはまた、前述のものと同様の方法で難読化されうるルックアップテーブル(のカスケードまたはネットワーク)として符号化されうる。本発明は、前述の例示的な暗号アルゴリズムに限定されない。
【００７６】
Chow1は、個々のステップではなく、構成を表すランダムな全単射を用いてそのテーブルを符号化することにより、鍵を隠すことを意図する方法を開示する。攻撃者が、他のマシン上でソフトウェア保護の目標を迂回できるようにする鍵材料を抽出することを阻止され、またはインストールされたソフトウェアの大規模なユーザベースにわたる安全対策を破る「グローバルクラック(global cracks)」を有効に生成する鍵材料を公開することを阻止される。それは、ソフトウェアだけの解決策、および敵意のあるホストが存在するという制約を仮定すると、高められた保護レベルを提供する。Chow1の手法では、(1)個々のステップではなく構成に対してテーブルを用いることにより、(2)ランダムな全単射を用いてこれらのテーブルを符号化することにより、(3)暗号境界を、暗号アルゴリズムそれ自体をさらに超えて含まれているアプリケーションへと拡張し、攻撃者(リバースエンジニア)に、その目標を達成するためには著しく大量のコードセグメントを理解させるように強制することにより、鍵が隠される。Chow1は、固定された鍵手法を論じており、鍵(複数可)は、鍵(複数可)に関して部分的に評価することにより実装中に埋め込まれ、したがって、鍵入力が不要となる。部分的な評価とは、鍵を含む表現が可能な限り合理的に評価され、その結果が、完全な表現ではなく、コードに含まれることを意味する。
【００７７】
可能な攻撃シナリオは、攻撃者が鍵特有の実装を抽出し、それを鍵の代わりに使用することである。この問題は、関数に適応された鍵特有の実装を、より大規模の収容するシステムのコンポーネントとして設計することにより緩和されうる。より大規模のシステムは、コンポーネントに、操作されたまたは符号化された形で入力を提供するように構成されうる。鍵特有の実装が攻撃者により除去され、異なる大規模のシステムに挿入された場合、鍵特有の実装は適正に機能しないが、それは、異なる大規模のシステムが、鍵特有の実装が期待する操作された形でその入力を提供することはないからである。
【００７８】
符号化テーブルのステップを参照すると、符号化は任意のものであるため、結果は、1つのステップの出力符号化が、次の入力符号化にマッチする場合に限って意味がある。例えば、ステップXの後にステップYが続く場合(
【００７９】
【数１１】
0005688528.tif 000012
【００８０】
の計算が得られる)、計算は、
【００８１】
【数１２】
0005688528.tif 000013
【００８２】
として符号化されうる。
【００８３】
このように、入力がFで符号化される必要があり、また出力がH-1で復号される必要があるが、
【００８４】
【数１３】
0005688528.tif 000014
【００８５】
は適正に計算される。ステップは、Y’およびX’に対応するテーブルとして別個に表され、したがって、F、G、およびHは、XおよびYと同様に隠される。
【００８６】
このような攪乱(confusion)ステップとは別に、Chow1は、その基礎となる演算をさらに偽装するために、線形変換による拡散ステップを使用する。混合(mixing)全単射という用語は、上記の意味で使用される線形の全単射を記述するために使用される。Chow1の実装は、入力を操作された形で取り込み、また出力を別の操作された形で生成し、それにより、ホワイトボックスAES実装を、それを含むアプリケーションから分離することを困難にする。
【００８７】
Chow2は、秘密鍵をプログラムから抽出することを狙うホワイトボックス攻撃に耐えるように設計されたDESの暗号実装を論ずる。ルックアップテーブルネットワークを難読化することに関するこの論文で論じられた技法は、AESおよび他のものを含む他の暗号アルゴリズムに対してもまた、多くの部分があてはまる。実行環境を制御する攻撃者は、鍵を明示的に抽出することなく、明確にソフトウェアそれ自体を(例えば、復号化のために)利用することができるが、手近にあるインストールされたインスタンスを使用するように攻撃者に強制することは、デジタル著作権管理(DRM)システムプロバイダにとって価値のあることが多い。一般に、Chow2における手法は、アフィン変換をいずれも実施しない置換処理ボックスから完全に構成される実装に向けて働くことである。Chow2で述べられるいくつかの技法は、全体的な手法をサポートする。これらの技法のいくつかは、I/Oブロック符号化、結合関数(combined function)符号化、バイパス符号化、スプリットパス符号化、および出力スプリッティングである。
【００８８】
部分評価は、実装の時点で(部分的に)知られた値に基づく表現が事前に評価されることを意味する。簡単化した例では、鍵が「5」であり、また元の実装が、表現「2*鍵」を含む場合、実装中に「2*5」を組み込むのではなく、事前に評価された表現「10」が、実装中に取り込まれる。このように、鍵「5」は、コード中に直接的に存在しない。固定鍵を備えるDESの場合では、これは、標準のS-boxを、例えば、コンパイル時にもしくはその前に鍵から計算されたものなど、鍵特有の事前に評価されたS-boxで置き換えることを含む。Chow2による混合全単射は、各出力ビットが多数の入力ビットに依存するように設計された全単射の線形変換である。I/Oブロック符号化は、多数の入力および出力ビットを処理するための符号化方法である。この場合、符号化/復号化は、符号化の連結として形成されうると共に、各符号化は、入力/出力ビットのサブセットを処理する。結合関数符号化は、2つ以上の演算が並列に処理されうる場合、単一の符号化関数が、並列演算の入力(それぞれ出力)の連結に適用されることを意味する。それは、多かれ少なかれ、I/Oブロック符号化とは反対のものである。バイパス符号化は、符号化変換が、難読化される変換の入力および/または出力に対して、いくつかの余分なビットのエントロピーを追加し、手順の最終的な出力に影響を与えないように、変換を再設計して余分なビットを「バイパスする」ように難読化されることを意味する。スプリットパス符号化は、関数が、基本的な情報ビットを難読化するために、さらなる出力ビットを提供するように変更されることを意味する。出力スプリッティングは、関数の出力が、いくつかの部分関数にわたって分配され、その場合、すべての部分関数の出力は、関数の元の出力を得るために、好ましくは非自明な方法で、結合される必要のあることを意味する。
【００８９】
Chow2は、おおよそ32ビット、またはさらに96ビットの広い入力を用いて、S-boxを構成するように符号化ネットワークを構築することを提案する。このような広い入力のS-boxは、それぞれが、より狭い入力および出力を有するS-boxのネットワークへと分割され、各S-boxは、S-box中に符号化関数を組み込むことにより符号化される。符号化関数の逆関数が、S-box中に組み込まれて、S-boxの出力を処理する。
【００９０】
説明を明確にするために、まずブロック暗号の可能なホワイトボックス実装を、この場合はAESであるが、述べるものとする。以下では、この実装に関する問題を示し、それがどのように修正されうるかを示すことになる。本発明が解決することを求める問題は、以下で示される特定の実装に単に限定されることはないが、概して、ホワイトボックス実装に特有のものであることに留意されたい。Chow1を、特に、セクション2.2からセクション3.6を参照するが、さらなる詳細は、既知のホワイトボックス実装による。
【００９１】
ホワイトボックスAES実装は、概略的に以下のように説明されうる。AES暗号化および復号化アルゴリズムへの入力は、単一の128ビットのブロックである。このブロックは、16バイトからなる4×4行列により表される。AESは、通常、AES-128に対して10ラウンドから成る。各ラウンドは、AESの状態を形成する1組の16バイトを更新し、したがって、各AESラウンドは128ビットを処理する。AES-128は128ビットの鍵を使用する。この鍵は、鍵を128ビットの別のラウンドの鍵へと変換するアルゴリズムのための入力として働く。基本的なラウンドは4つの部分からなり、すなわち、
・SubBytes
・ShiftRows
・MixColumns
・AddRoundKey
である。
【００９２】
この操作順がAES暗号化に適用される。AES復号化における標準の操作順は異なるが、AES暗号化に関するものと同じ操作順を有するようにAES復号化アルゴリズムを書き替えることも可能である。
【００９３】
第1のラウンドの前に、余分のAddRoundKey操作が生じ、またラウンド10から、MixColumns操作が除外される。鍵を使用する唯一の部分はAddRoundKeyであり、他の3部分は鍵を使用しない。実装において、ラウンドの境界は、AddRoundKeyステップおよび次のラウンドのSubBytesステップを1つのステップに統合するように変更される。ラウンドは、AddRoundKeyおよびSubBytesで開始し、その後にShiftRowsが続き、最後にMixColumnsが行われる。
【００９４】
まず、鍵は、SubBytesステップとAddRoundKeyを共に1つのステップに統合することにより隠される。これは、鍵をもはやそれ自体では見えなくする。鍵は、前に知られているため、鍵を含む演算は事前に評価されうる。これは、ステップSubBytesで使用される標準のS-boxが、鍵特有のS-boxで置き換え可能であることを意味する。AES-128の鍵特有のインスタンスを生成するために、16個の8×8(すなわち、8ビット入力、8ビット出力)ルックアップテーブル
【００９５】
【数１４】
0005688528.tif 000015
【００９６】
を作成することにより、鍵はSubBytes変換へと統合される、ただし、ルックアップテーブルは、
【００９７】
【数１５】
0005688528.tif 000016
【００９８】
で定義されるが、式中、SはAES S-box(可逆の8ビットマッピング)、および
【００９９】
【数１６】
0005688528.tif 000017
【０１００】
は、ラウンドrに対するラウンド鍵を表す4×4行列の位置i、jにおけるAES副鍵バイトである。これらのT-boxは、SubBytesステップを、前のラウンドのAddRoundKeyステップを用いて構成する。ラウンド10のT-boxは、以下のようにホワイト化後の鍵を吸収し、すなわち、
【０１０１】
【数１７】
0005688528.tif 000018
【０１０２】
であって、式中、sr(i, j)は、ShiftRowsステップの後のセルi、jの新しい位置を示している。T-boxの合計数は、10×16=160である。しかし、S-1が公に知られているため、鍵は、T-boxから容易に復元されうる。このことで、さらなる符号化が必要になる。
【０１０３】
線形変換は、T-boxへと入力を拡散させるために使用される。これらの線形変換は、混合全単射と呼ばれ、GF(2)にわたり、8×8行列で表わされ得る。混合全単射は、その効果を無効にするための早期の計算によって逆演算される。
【０１０４】
図3は、(ShiftRowsを適用した後の)状態の1つの32ビット列に対するホワイトボックスAESのラウンドに含まれるテーブルを示している。様々なタイプのテーブル名がここに示されている。それらは、以降でより詳細に論じられる。ラウンドの前に、128ビット状態の各バイトが、各タイプIaテーブルに適用される。この結果、タイプIVテーブルのネットワークを用いてXOR演算される各128ビット値が得られて、4つの32ビット値へと分割される128ビット出力を提供する。各32ビット値の処理ステップが、ここで概略的に示される。32ビット値の4バイトは、4つの各タイプIIテーブル20に入力される。4つのタイプIIテーブル20のそれぞれは、32ビットの出力をもたらす。これらの出力は、タイプIVテーブル22を用いてビット単位にXOR演算される。各タイプIVテーブル22は、4ビットのビット単位のXOR演算を行う。タイプIVテーブルの入力と出力を適正に結合することにより、当業者によって理解されるように、4つの32ビット出力のビット単位のXORが実現されうる。このステップの結果は32ビット値である。この値の4バイトのそれぞれは、各タイプIIIテーブル24に適用される。各タイプIIIテーブルは、32ビットの出力を提供する。これらの出力は、再度、タイプIVテーブル22のネットワークと同様のタイプIVテーブル26のネットワークを用いてビット単位でXOR演算される。出力は、状態の列を示す32ビット値である。これが、ラウンドごとに反復される。
【０１０５】
4つの32ビット値のそれぞれに対して、ラウンドが行われた後、出力は、128ビット値へと結合される。128ビット値の各バイトは、タイプIbテーブルに適用され、その結果が、タイプIVテーブルのネットワークを用いてXOR演算される。
【０１０６】
図4は、タイプIaテーブル100を示している。図5は、タイプIIテーブル200を示す。図6は、タイプIIIテーブル300を示す。図7は、タイプIVテーブル400を示す。図8は、タイプIbテーブル500を示す。
【０１０７】
混合全単射は以下のように使用される。AES状態は、バイトからなる4×4行列により表される。MixColumnsステップは、同時に1つの列(4つの8ビットセル)に対して演算する。32×32行列のMCを考える。これがテーブルにより表される場合、このテーブルは、232×32=137438953472ビット=16GBを使用することになる。このような大規模なテーブルを回避するために、行列は、4つのセクションへとブロック化される。
【０１０８】
MCは、4つの32×8セクション、MC0、MC1、MC2、MC3(ブロック208)へとブロック化される。32ビットベクトルx=(x0, . . . , x31)とMCの乗算は、xのビットを4バイトに分割し、かつMCの各セクションとバイトの1つとを乗算することにより行われ、4つの32ビットベクトル(z0, . . . , z3)を得る。この後に続いて、3つの32ビットのXOR演算が行われて、最終的な32ビットの結果zを与える。4つのテーブルは併せて、4×28×32=32768ビット=4KBを使用するだけである。
【０１０９】
3つのXORは、24個の4ビットXORへと分割され、それぞれが、適切な連結(例えば、((z[0, 0], z[0, 1], z[0, 2], z[0, 3])+(z[l, 0], z[l, 1], z[l, 2], z[l, 3]))‖((z[0, 4], z[0, 5], z[0, 6], z[0, 7])+(z[l, 4], z[l, 5], z[l, 6], z[l, 7]))‖ . . .)を備えた、おそらく符号化されたルックアップテーブルにより表され、ただし、‖は結合を示し、また+はXORを示す。これらのストリップ(strip)および副分割したXORを用いることにより、各ステップは、小さなルックアップテーブルにより表される。特に、i = 0, . . . , 3に対して、ziは8×32ビットテーブルを用いて計算される。8×32ビットテーブルは、8ビットの入力と32ビットの出力を有する。このようなテーブルは、それぞれ32ビットの28個の出力値を一覧にすることにより実施されうる。4ビットのXORは、24個の8×4ビットテーブルになる。図7は、入力復号化402および出力符号化406が、どのようにXOR404周りに挿入されうるかを示す。これらの符号化は、通常、ランダムに選択された非線形の4×4の全単射である。XORテーブルは、タイプIVテーブル400と呼ばれる。タイプIVテーブルは、2つの前の計算のそれぞれから、入力として4ビットを取る。これらの計算の出力符号化212は、互いに無効にするために、タイプIVテーブルに関して、入力復号化402と突き合わされる。4×4の非線形全単射に対する選択はテーブルのサイズに依存する。この状況で、タイプIVテーブルは、28×4ビット=128バイトだけである。併せると3KBを使用する24個のテーブルが必要になる。XORが分割されない場合、32ビットのXORを計算する3つのXORテーブルが必要になるはずである。T-box206および8×32ビットテーブル208は、別個のルックアップテーブルとして表されうる。それに代えて、それらは、SubBytesおよびAddRoundKey変換ならびにMixColumnsの一部を計算する新しい8×32ビットテーブル200を作成するように構成されうる。このことは、(T-boxを記憶するための)空間および
(テーブル参照をするための)時間を節約する。
【０１１０】
上記のようにMCをMCiへと分割する前に、MCは、図5において参照番号210で概略的に示され、フルランクの4×4の副行列を有する正則行列として選択された32×32の混合全単射MBにより左方乗算される。混合全単射を使用することは、特定のテーブルに対する可能な構成の数を増加させる。
【０１１１】
図5は、4×4の入力復号化202および4×4の出力符号化212を含む8×32タイプIIテーブル200を示している。これらの出力符号化および入力復号化は、非線形の4×4の全単射であり、それは、タイプIVテーブル400の入力復号化および出力符号化とマッチしなくてはならない。タイプIIテーブル200の後にタイプIVテーブル400が続いている。MBを逆演算するために、テーブルの余分の組が、MB-1を計算するために使用される。(x’0, . . . , x’31)をMixColumnsへの入力とし、かつ(z0, . . . , z31)をMixColumnsの後の出力とする。(z’0, . . . , z’31)TをMBで乗算した後の結果とする。(z’0, . . . , z’31)Tは、タイプIIIテーブル300への入力として働く。テーブルの出力符号化は、次のテーブルの入力復号化により無効にされるため、入力復号化および出力符号化はここでは考慮される必要がないことに留意されたい。タイプIIIテーブル300では、MB-1が適用され304、また次のラウンドの4つのタイプIIテーブル200の4つの入力混合全単射204を反転する308。
【０１１２】
図6は、4×4の非線形入力復号化および4×4の非線形出力符号化を含む8×32タイプIIIテーブル300を示す。これらのテーブルの後に、対応するタイプIVテーブル400が続く。
【０１１３】
データ演算の1つのラウンドは、128ビットの状態行列に対する演算を含む。128ビットの状態行列の32ビットの4つのストリップのそれぞれに対して行われるデータ演算は、以下のようになる。32ビットのストリップは、4つの8ビットバイトへと分割される。4バイトのそれぞれは、別個のタイプIIテーブル200に提供され、4つの32ビットの出力値をもたらす。これらの値は、難読化されるタイプIVテーブル400を用いてXOR演算される必要がある。その目的のために、各32ビット出力値は、8つの4ビットニブルへと分割され、ニブルの適切なペアが各タイプIVテーブルに入力されて、4つの32ビット出力値のXORが符号化された形で得られる。
【０１１４】
この32ビットの得られた、符号化されXOR演算された結果が、再度、バイトへと分割され、各バイトは、別個のタイプIIIテーブル300へと入力される。タイプIIIテーブルの各ニブルの入力復号化は、最後に適用されたタイプIVテーブルの出力符号化に対応する。タイプIIIテーブルは、難読化されたタイプIVテーブル400を用いて再度XOR演算される4つの32ビット出力値を再度もたらす。
【０１１５】
要約すると、ラウンドは、ルックアップテーブルにより実施される。単一のラウンドのルックアップテーブルは、以下のようにネットワーク化される。データはタイプIIテーブルに供給される。これらのテーブルの出力は、符号化されたXORを表すタイプIVテーブルのネットワークに供給される。このネットワークの出力は、タイプIIテーブルにより挿入された混合全単射符号化を無効にするタイプIIIテーブルに供給される。ラウンドの符号化された出力は、タイプIIIテーブルの出力を、符号化されたXORを表すタイプIVテーブルのネットワークへと再度供給することにより最終的に導かれる。
【０１１６】
さらに、ホワイトボックス実装は、タイプIテーブルを、外部の符号化を無効にし、かつ挿入するために、それぞれ、開始時(タイプIaテーブル100)、および最後に(タイプIbテーブル500)タイプIテーブルを含む。タイプIaテーブル100は、単一のテーブル参照を適用することにより、図4で示されるようなマッピングの連結を適用するために使用されうる。連結では、4ビットニブルの入力復号化102が最初に出現する。次いで8ビットから128ビットへのマッピング104が現れる。このマッピングは、ネットワークの入力および出力の符号化の一部である。このマッピングは、プログラム中の別の場所で無効にされうる。線形な8ビットから128ビットへのマッピングを別にしても、他のテーブルもまた外部の符号化の一部とすることができる。例えば、テーブル100が第1のラウンドに含まれる場合、102が含まれうる。同様に、テーブル100が最後のラウンド106にある場合、108が含まれうる。マッピング104の結果は、16個の8ビット部分へと分割され、それに対して、各8ビットの全単射106が適用される。最終的に、出力ニブル符号化108が適用される。前述のように、マッピング102、104、106、および108のカスケードは、事前に評価され、また最終的な結果は、ルックアップテーブルで表にされる。このことは、それぞれが128ビットのたかだか256個のエントリを備えるテーブルをもたらす。タイプIbテーブル500に組み込まれるマッピングの連結が、図8で概略的に表示される。最初のマッピングは、入力ニブル復号化502であり、その後に続いて、8ビットの全単射504、rが最後のラウンドに対応するT-boxのTri,j506、出力符号化を提供するための8ビットから128ビットへのマッピング、および出力ニブル符号化510が行われる。この種のテーブルの128ビット出力は、他のタイプIbテーブルの出力でXOR演算され、再度、ニブル入力および出力が符号化されたタイプIVテーブル400を利用する。出力符号化508は、プログラム中のいずれかで、すなわち、プログラムの暗号部分の外で無効にされる。これは、攻撃者が、プログラムの暗号部分の入力および出力だけを解析することにより、テーブルの符号化を破ることをさらに困難にする。
【０１１７】
以下では、AESの改善されたホワイトボックス実装が述べられる。
【０１１８】
例えば、Chow1およびChow2で述べられたものなど、ホワイトボックス技法は、ブロック暗号、ストリーム暗号、メッセージ認証コード(MAC)などを含む広範囲の暗号化処理のホワイトボックス実装を得るために、互いに様々な方法で組み合わせることができる。しかし、Michiels1で述べたように、このようなホワイトボックス実装は、基本的な弱点を共有している。様々な中間ラウンドの入力バイトが、Chow1および2で見出されたものなどの技法を用いて難読化される場合、入力バイトのそれぞれに対して、その入力バイトを、AESの単純な非ホワイトボックス実装の入力バイトにマッピングする関係が存在することになる。この関係が知られている場合、これは、ホワイトボックス実装のWBACの安全性を損なうことになる。暗号技術における専門家には、AESの中間ラウンドに対する入力バイトの知識が、暗号鍵を明らかにできることが知られている。特に、ブロック暗号における早期のラウンドおよび/または後のラウンドは、内部データの露出に対して特に脆弱である。しかし、結局のところ、単にこのような関係が存在することだけで、攻撃をしかけるためにはすでに十分である。さらに、Michiels1で示されるように、この特性は、Chowにより、またはこの文書で示されるAESまたはDES実装に特有のものではなく、実際に、置換処理-アフィン-変換暗号として表現されうる多くの暗号化処理で不可避のものである。
【０１１９】
概要では、改善は以下のようにして達成される。第1のラウンドから次のラウンドへと流れる間に、固定された符号化で中間データが難読化されることは回避される必要があるということは、本発明者の洞察するところであった。これは、ホワイトボックス実装に対する入力で変化する符号化方式により符号化することによって達成される。読みやすくするために、改善されたホワイトボックス技法を、任意の置換処理-アフィン変換暗号によるのではなく、AESに関して述べるものとする。
【０１２０】
図9では、AESのホワイトボックス実装の一部が概略的に述べられている。図示されているのは、タイプIVブロック422、タイプIIブロック423、タイプIVブロック425、およびタイプIIIブロック427であり、これらのブロックは、ブロック421で開始して、1つずつデータに演算を行う。図9では、基本ブロックのタイプが、ローマ数字で示されている。この演算のシーケンスは、例えば、第1のタイプIII演算の後に開始するなど、上記で複数回にわたり述べたホワイトボックス実装において見出されうる。ブロックの間に、符号化、再符号化、および復号化ステップが挿入される。実際には、並列して動作する複数の基本ブロックがありうることに留意されたい。例えば、AES実施形態では、16個のタイプIIルックアップテーブルが、図で示された単一のタイプIIブロック423で要約される。同様に、これらのタイプIIテーブルの出力は、24個のタイプIVルックアップテーブルを組み合わせたXORネットワーク425に結合される。
【０１２１】
タイプIVブロック422、すなわち、XORネットワークの前に、符号器421が配置され、符号器は、選択された符号化方式を用いてデータを符号化する。符号化方式は、ホワイトボックス実装への入力に依存する選択値を用いて複数の符号化の中から選択される。例えば、選択値は、例えば、最初のビット数、例えば、最初の4ビットなど、入力の暗号ハッシュに基づくことができる。しかし、選択値はまた、符号器それ自体への入力としても選択されうる。選択された符号化は、XORネットワークがその符号化を遵守するように選択されることが好ましい。すなわち、XORネットワーク422の出力が、なお、その符号化に従って符号化される。例えば、これは、アフィン符号化を用いることにより達成されうる。いくつかの暗号は、XOR演算を全く、少なくともこの場所では、使用しない可能性のあることにも留意されたい。このような状況において、他の符号化も選択されうるが、それは当業者により決定されうる。
【０１２２】
符号器421は、タイプII基本ブロック423のすぐ前に配置されうるが、符号器421とタイプII基本ブロック423の間に基本ブロック、例えば、ブロック422を有することは、攻撃者が、その実装で使用した符号化のタイプを突き止め、かつ解析することを困難にするので有利である。さらに、図9で示す配置では、符号化は、ブロック暗号のラウンド中に埋め込まれる。ラウンド間の遷移を解析するよりも、ラウンドを解析する方が困難であると考えられる。
【０１２３】
符号化されたデータは、次いで、T-box、タイプIIブロック423により演算される。T-boxは、AESのS-boxに依存して構成されているので、線形ではなく、通常、符号器421により適用される符号化を遵守しないはずである。したがって、タイプIIブロック423の出力は、異なる符号化で符号化される。通常、異なる符号化は、非常に非線形の符号化になるはずである。さらに、複数ブロック423の出力は、XORネットワークタイプIVブロック425で組み合わされる必要のあることを思い出すべきである。異なるT-boxは、異なる符号化を生ずることができる。この目的のために、補償器424が、タイプIIブロック423と、XORネットワーク、タイプIVブロック425との間に配置される。補償器424は、符号化に対するブロック423の影響、および出力バイト間の符号化の差を補償する。好ましくは、補償器424は、次のタイプIVブロック425で共にXOR演算されることになる出力バイトを収集し、また同じ符号化で、好ましくはアフィン符号化で符号化されることを保証する。本実施形態で行われるように、符号化がXORネットワークの後で除去されることになる場合、符号化は、アフィンであることが好ましいが、任意に選択されうる。例えば、補償器424は、異なる符号化の1つを使用し、他のデータのすべてをこの符号化に変換することができる。次のブロックがXORブロックであるので、補償器424はアフィン符号化へと変換することが好ましい。任意選択で、補償器424は、異なる符号化の1つを選ぶのではなく、その符号化に対して全く新しい符号化を選択することもできる。さらに、この新しい符号化は、さらなる複数の符号化の中から入力に依存して選択されうる。任意選択で、補償器424は、すべての符号化を除去することができる。
【０１２４】
XORネットワーク425の後、タイプIII演算が、ブロック423で使用されたタイプIIテーブルへと導入された混合全単射を無効にするために行われうる。ブロック427の前にデータを準備するために、復号器426は、補償器424、および/またはブロック423、および/またはブロック421で導入された符号化を除去する。概して、混合全単射は任意選択のものであり、暗号化処理の実施をさらに複雑化するための1つの方法に過ぎないことに留意されたい。混合全単射がブロック423のテーブルに導入されなかった場合、ブロック427は除外されうる。その場合、さらに復号器426も除外されうる。任意選択で、復号器426は、最後のラウンドに含まれうる。
【０１２５】
補償器424の動作を簡単にするために、自己等価性の符号化方式が、符号器421により使用されうる。特に、ブロック423への入力上に配置された符号化は、出力符号化方式に従って符号化されるにもかかわらず、通常の出力へと変換される。出力符号化方式は、入力と同じタイプの符号化に属する。特に、入力データ上に配置されたときアフィン出力符号化を生ずる、自己等価性のアフィン符号化がある。このような自己等価性の符号化は比較的まれであり、ブロック423は、非線形のS-boxを組み込む。しかし、論文Biryukov1から、このような自己等価性のアフィン符号化が存在することが知られている。特に、その論文のセクション4および5に留意されたい。特に、AES 2040のS-boxに対して、自己等価性のアフィン符号化が存在する。
【０１２６】
データの依存性が許容する限り、演算は、少なくとも部分的に並列で行われうることに留意されたい。
【０１２７】
改善されたホワイトボックス実装の詳細な説明
ホワイトボックス実装の実施形態のより詳細な説明を続ける。
【０１２８】
AESラウンドの開始は以下のようになる、ラウンドへの入力はバイトに分割される。各バイトiは、ラウンド鍵のバイトkiとXOR演算される。このXORの結果は、S-boxへの入力として使用される。ホワイトボックス実装の構成において、これらの2つの演算は、単一のいわゆるT-box演算へとマージされる。これは、ラウンドに対する各入力バイトiに対して、
【０１２９】
【数１８】
0005688528.tif 000019
【０１３０】
により、8対8ビット全単射マッピングTiを定義することを意味する。
【０１３１】
他の暗号は、情報の最も基本的な単位として、バイト、またはニブルも使用しない可能性があるが、AESに関して本明細書で示す手法は、ディメンジョンが、それに対応して変更される必要があるが、適用可能のままであることに留意されたい。前述のように、このT-box演算は、単独で使用せず、他の演算と統合されることが好ましい。さらに、図2について説明したように、非線形の難読化関数が挿入されてもよい。
【０１３２】
ホワイトボックス実装の構成において、このT-boxは、ルックアップテーブルにより実施される。ルックアップテーブルは、T-box演算を行うだけではなく、関数
【０１３３】
【数１９】
0005688528.tif 000020
【０１３４】
の演算も実施する、ただし、a1は全単射8対8ビットマッピングであり、またa2は必ずしも全単射である必要のない8対mビットマッピングである。前の説明では、Chow1の用語を用いると、Uiは、m=32のタイプIIテーブルと見なされうる。しかし、本発明は、自己等価性の符号化を有する基本演算に対して、より一般的に適用されうることに留意されたい。これは、ホワイトボックス実装の以下の特性を我々に提供する。Michiels1で提示された攻撃により利用されるのはこの特性である。
【０１３５】
特性:Iを、何らかの所与の鍵に対するAESの標準的な基準実装とし、WBを、実装Iのホワイトボックスバージョンとする。さらに、bを、Iにおけるラウンドの入力バイトとする。その場合、固定関数a1が存在し、WBは値a1(b)を導出する。固定関数a1は固定されており、その実装に対して与えられる入力に依存しない(それによりパラメータ化されない)。関数a1は、異なる入力バイトに対して異なっていてもよいことに留意すべきである。a1は、特定のホワイトボックス実装に依存していることにも留意されたい。
【０１３６】
本発明によるホワイトボックス実装では、標準実装とホワイトボックス実装の間のこの関係は崩れている。
【０１３７】
上記で述べたように、Chow他によるホワイトボックスAES実装は、a1およびa2に対する何らかの特定の選択に対して、関数
【０１３８】
【数２０】
0005688528.tif 000021
【０１３９】
を実施するルックアップテーブルを含む。Viを、
【０１４０】
【数２１】
0005688528.tif 000022
【０１４１】
であるような関数ペア(α,β)の集合とし、またWi={α|∃β(α,β)∈Vi}とする。次いで、任意の(α,β)∈Viに対して、αにより符号化された入力をUiに対するルックアップテーブルに提供した場合、この結果として、βにより符号化された出力を得る。Uiに対するルックアップテーブルの入力は、したがって、Wiからの符号化を用いて符号化されることが好ましいが、その場合、選択された符号化は、ホワイトボックス実装のすべての入力に対して同じである必要はない。
【０１４２】
Chow1により提案されたホワイトボックス実装は、2つのタイプの符号化を含む、すなわち、線形符号化と非線形符号化である。ホワイトボックス実装の構成は、2つのステップに分割されうる。第1のステップでは、線形符号化だけを含むホワイトボックス実装が構成され、第2のステップでは、非線形符号化が加えられる。この実施形態では、開始点として、第1ステップの後に導出されたホワイトボックス実装を使用する。したがって、この議論において、非線形符号化が適用されないものと仮定することができる。非線形符号化は、望ましい場合、後で適用されうる。
【０１４３】
ホワイトボックス実装では、T-boxは、8対32ビットテーブルに含まれており、このテーブルは、タイプIIテーブルと呼ばれる。このテーブルを4個の8対8ビットテーブルに分割した場合、j番目のテーブルにより実施される関数は、
【０１４４】
【数２２】
0005688528.tif 000023
【０１４５】
と書くことができ、式中、giおよびfi,jは線形関数である。関数giは全単射であり、また線形符号化を適正に選ぶことにより、fi,jが全単射であることを保証することもできる。この実施形態では、それらは共に全単射であると仮定することになる。
【０１４６】
Ui,jを実施するルックアップテーブルの後に、XORを実施するルックアップテーブルが行われる、すなわち、タイプIIテーブルの出力はさらに、タイプIVテーブルにより処理される。より正確には、XORテーブルは以下のように計算する。1組の16個のT-boxが区分されて、4組の4個のT-boxになる(T-boxは、AESのShiftRowステップの後、同じ列からのバイトに関連する場合、同じ組になる)。{i1,i2,i3,i4}をこのような組とし、yi,jを関数
【０１４７】
【数２３】
0005688528.tif 000024
【０１４８】
の結果とする。次いで、XORテーブルは、各j=1,2,3,4に対して、値
【０１４９】
【数２４】
0005688528.tif 000025
【０１５０】
のXORを計算する。
【０１５１】
Ui,jを実施するルックアップテーブルの前にさらに、XORを実施するルックアップテーブルが行われる。xiを関数Ui,jの入力とする。次いで、Ui,jに先行するXORテーブルは、4個のバイトxi,1、xi,2、xi,3、およびxi,4からバイトxiを計算する。
【０１５２】
本発明を、Uiに代えてUi,jに対して適用するので、上記で定義した集合ViおよびWiのインデックスにjへの依存性を追加する必要があることに留意されたい。示したように、関数Ui,jの入力は、一定ではない符号化により符号化される。上記で述べたホワイトボックス実装に対して行われうる変更は、3つの点に関する。それは、どの符号化を関数Ui,jの入力に対して使用するか、すなわち、どのようにして、Vi,jおよびWi,jの集合を定義するか、値に対してどのように符号化を使用するか、値に対して符号化をどこで使用すべきか、である。以下では、これらの質問のそれぞれに対する可能な答えが示される。
【０１５３】
このセクションは、どの符号化が、関数Ui,jの入力に対して使用されているかについて述べる。
【０１５４】
S-box Sに対して、集合ΦSを
【０１５５】
【数２５】
0005688528.tif 000026
【０１５６】
となるようなアフィン関数のすべてのペア
【０１５７】
【数２６】
0005688528.tif 000027
【０１５８】
の集合とする。Biryukov1は、任意のS-boxに対して、この集合を導くためのアルゴリズムを与える。AES S-boxに対して、この集合は、2040ペアの関数からなる。この集合から、任意の関数Ui,jに対して、
【０１５９】
【数２７】
0005688528.tif 000028
【０１６０】
となるようなアフィン関数のペア(α,β)の集合Vi,jを容易に導出することができる。
【０１６１】
【数２８】
0005688528.tif 000029
【０１６２】
であることを覚えておく必要があり、ただし、fi,jおよびgiは線形で、かつ全単射関数であり、
【０１６３】
【数２９】
0005688528.tif 000030
【０１６４】
は、関数
【０１６５】
【数３０】
0005688528.tif 000031
【０１６６】
を示す。より正確には、それは、
【０１６７】
【数３１】
0005688528.tif 000032
【０１６８】
により与えられる集合Vi,jが、すべてのα、β∈Vi,jに対して、
【０１６９】
【数３２】
0005688528.tif 000033
【０１７０】
を得る特性を有することを、示すことができる。この集合の基数は、ΦSに対するものと同じ、すなわち、2040である。この集合Vi,jは、Ui,jの入力に使用する符号化の集合Wi,jを定義する。すなわち、Ui,jへの入力は、アフィン関数α∈Wi,j、ただしWi,j={α|∃β(α,β)∈Vi,j}により符号化される。
【０１７１】
このセクションでは、概して、値が、どのようにしてアフィン変換を用いて符号化されうるかを論ずる。この技法は、最初の符号化に対して使用されうるが、再符号化および復号化に対しても使用されうる。符号器は、値を以下の方法で符号化することができる。まず、線形符号化に対して焦点を当てる。νを、ホワイトボックス実装の入力Mから導かれた4ビットの選択値とする。値νは、例えば、入力Mのニブルとすることができる。あるいは、νは、少なくとも部分的に、符号化することを望む値、すなわち、xから導くこともできる。さらに、Eを8ビットの24個の線形符号化からなる集合とし、すなわち、Eは24個の行列A1,A2,…,A16から構成され、各行列は、8×8ビットの可逆行列である。符号化の場合、これらの行列は、例えば、上記で定義された集合Vi,jにおけるアフィン符号化の線形部分として選択される可能性があることを思い出すべきである。多少、誤った表記法ではあるが、Nが行列である場合、Nとの行列乗算により定義される関数をまた、Nを用いて示すことになる、すなわち、N(x)=Nxである。値νが1と16の間の数であると解釈することにより、符号化Aνを参照することができる。次に、ホワイトボックス実装中で、8ビットの中間値xが、線形符号化Aνにより符号化されることをどのように実施すべきかを示す。符号化の数に対して異なる基数が可能であることに留意されたい。例えば、νを1ビット値に制限することにより、2つの符号化方式だけが必要になる。
【０１７２】
まず、xを2つのニブルx1およびx2へと分割する。さらに、任意のAiに対して、Aiの最初の4列により定義される行列としてAi,1を定義し、またAiの最後の4列により定義される行列としてAi,2を定義する。その場合、
【０１７３】
【数３３】
0005688528.tif 000034
【０１７４】
である。
【０１７５】
したがって、以下のようにxからAν(x)を計算することができる。4ビット値x1およびνをAν,1(x1)にマップする8対8ビットテーブルτ1を定義し、また4ビット値x2およびνをAν,2(x2)にマップする8対8ビットテーブルτ2を定義する。これらのテーブルの結果をXOR演算することにより(例えば、XORテーブルにより)、Aν(x)を得る。
【０１７６】
これでバイトxに対して線形符号化を適用するための方法を終了する。次に、バイトにアフィン符号化を適用するための同様な方法を論ずる。再度、4ビット値νが、16個の符号化からなる集合Eから、符号化を指示するために使用される。しかし、この場合、符号化の集合Eは、8ビットのアフィン符号化からなり、すなわち、関数
【０１７７】
【数３４】
0005688528.tif 000035
【０１７８】
であり、式中、Aは、8×8ビットの2進行列であり、またaは8ビットの定数である。νにより参照される符号化は、
【０１７９】
【数３５】
0005688528.tif 000036
【０１８０】
により示される。
【０１８１】
次に、線形符号化に関して同様な方法で進める。すなわち、まず、xを2つのニブルx1およびx2へと分割する。さらに、行列Ai,1およびAi,2が前と同様に定義されるが、それは、Ai,1が、Aiの最初の4列により定義される行列を示し、またAi,2が、Aiの最後の4列により定義される行列を示すことを意味する。その場合、
【０１８２】
【数３６】
0005688528.tif 000037
【０１８３】
である。
【０１８４】
したがって、以下のようにxからαν(x)を計算することができる。4ビット値x1およびνを
【０１８５】
【数３７】
0005688528.tif 000038
【０１８６】
にマッピングする8対8ビットテーブルτ1を定義し、また4ビット値x2およびνをAν,2(x2)にマッピングする8対8ビットテーブルτ2を定義する。これらのテーブルの結果をXOR演算することにより(例えば、XORテーブルにより)、αν(x)を得る。
【０１８７】
符号器ネットワークが図10に示されている。符号器ネットワークは、選択値νに依存する値xを符号化するように構成される。ルックアップテーブル431は、2つの4ビットサイズの入力、x1およびνを受け取るように構成される。それは1つの8ビット出力を生成するように構成される。同様に、ルックアップテーブル432は、2つの4ビットサイズの入力、x2およびνを受け取り、かつ8ビット出力を生成するように構成される。2つの8ビット値は、XORネットワーク433で互いにXOR演算される。XORネットワーク433は、2つのタイプIVテーブルを備え、XOR演算を行い、またニブルに対して別個に動作する。
【０１８８】
上記で、まだ符号化されていない値にどのようにして符号化を適用するかを論じた。次に、値xが符号化により符号化され、また、例えば、補償器424を用いて、その符号化を他のものに変更したい場合を考える。これをより正確にするために、Eおよび
【０１８９】
【数３８】
0005688528.tif 000039
【０１９０】
を、それぞれが16個のアフィン符号化からなる、2つの、おそらく異なる集合とする。Eにおける符号化を参照するためにαν(ただしν=1,2,…,16）を記述し、また、
【０１９１】
【数３９】
0005688528.tif 000040
【０１９２】
における符号化を参照するために、
【０１９３】
【数４０】
0005688528.tif 000041
【０１９４】
（ただしν=1,2,…,16）を記述する。次いで、バイトxの符号化を、ανから
【０１９５】
【数４１】
0005688528.tif 000042
【０１９６】
へと変更することを望む場合の問題を考える。この問題は、まだ符号化されていない値に符号化を適用する問題と同様であり、その場合、符号化は、28=256の符号化からなる集合
【０１９７】
【数４２】
0005688528.tif 000043
【０１９８】
から得られる。したがって、上記で述べた方法を再度使用することができる。唯一の差は、8対8ビットテーブルτ1およびτ2が、今度は、12ビット入力を有することであり、それは、
【０１９９】
【数４３】
0005688528.tif 000044
【０２００】
から要素を特定するために8ビットを必要とするからである。
【０２０１】
以下の続きでは、値に対する符号化をどこに使用すべきかという質問に答える。この質問に対する答えは、2つの部分に分割される。すなわち、符号化の導入および符号化の除去である。
【０２０２】
符号化の導入:
符号化は、XORネットワーク422の前に導入されうるが、何らかの注意が必要とされうる。例えば、アフィン符号化が、線形符号化に代えて使用される場合、XORネットワークに対するすべての入力は、同じ方法で符号化されることができない。任意のアフィン関数
【０２０３】
【数４４】
0005688528.tif 000045
【０２０４】
に対して、関数
【０２０５】
【数４５】
0005688528.tif 000046
【０２０６】
を、関数αの線形部分であるとする。さらに、
【０２０７】
【数４６】
0005688528.tif 000047
【０２０８】
を、アフィン関数の線形部分をWi,jに含む集合とする。すなわち、
【０２０９】
【数４７】
0005688528.tif 000048
【０２１０】
である。上記で示したように、関数Ui,jの入力値xiは、バイトxi,1、xi,2、xi,3、およびxi,4をXOR演算することにより構成される。関数Ui,jのxiの入力に対して符号化ανを使用するために、以下の手法を適用する。まず、ホワイトボックス実装の入力から4ビット値νを導出する。これは何らかの任意の方法で行われうる。値νを使用して、符号化ανにより値xi,1を符号化し、また符号化
【０２１１】
【数４８】
0005688528.tif 000049
【０２１２】
により値xi,2、xi,3、およびxi,4を符号化する。これらの値のXOR演算を行うことにより、値αν(x)をもたらす。これで符号化の導入を終了する。
【０２１３】
符号化の除去
前に示したように、基本的なホワイトボックス実装では、関数
【０２１４】
【数４９】
0005688528.tif 000050
【０２１５】
の出力
【０２１６】
【数５０】
0005688528.tif 000051
【０２１７】
は、3つの他のテーブル
【０２１８】
【数５１】
0005688528.tif 000052
【０２１９】
および
【０２２０】
【数５２】
0005688528.tif 000053
【０２２１】
の出力とXOR演算が行われる。この実施形態の場合は、XOR演算は、下記のように行われるものと仮定する。まず、
【０２２２】
【数５３】
0005688528.tif 000054
【０２２３】
が
【０２２４】
【数５４】
0005688528.tif 000055
【０２２５】
とXOR演算される。次に、r1と呼ぶこの結果を、
【０２２６】
【数５５】
0005688528.tif 000056
【０２２７】
とXOR演算する。この第2のXORの結果r2は、最終的に、値yjを得るために、
【０２２８】
【数５６】
0005688528.tif 000057
【０２２９】
とXOR演算される。
【０２３０】
βi,jを、値yi,jが符号化されるアフィン符号化を指すものとする。値をXOR演算する前に、すべての値
【０２３１】
【数５７】
0005688528.tif 000058
【０２３２】
および
【０２３３】
【数５８】
0005688528.tif 000059
【０２３４】
が、
【０２３５】
【数５９】
0005688528.tif 000060
【０２３６】
の符号化の線形部分により、すなわち、
【０２３７】
【数６０】
0005688528.tif 000061
【０２３８】
により符号化されるようにする。上記で、これがどのようにして行われうるかを説明した。次に、符号化された値
【０２３９】
【数６１】
0005688528.tif 000062
【０２４０】
および
【０２４１】
【数６２】
0005688528.tif 000063
【０２４２】
をXOR演算する。符号化された値
【０２４３】
【数６３】
0005688528.tif 000064
【０２４４】
および
【０２４５】
【数６４】
0005688528.tif 000065
【０２４６】
をXOR演算することは、符号化された値
【０２４７】
【数６５】
0005688528.tif 000066
【０２４８】
をもたらすことに留意されたい。この値を、
【０２４９】
【数６６】
0005688528.tif 000067
【０２５０】
とXOR演算することは、
【０２５１】
【数６７】
0005688528.tif 000068
【０２５２】
をもたらし、また
【０２５３】
【数６８】
0005688528.tif 000069
【０２５４】
を
【０２５５】
【数６９】
0005688528.tif 000070
【０２５６】
とXOR演算することは、
【０２５７】
【数７０】
0005688528.tif 000071
【０２５８】
をもたらす。値
【０２５９】
【数７１】
0005688528.tif 000072
【０２６０】
から、最終的に符号化を除去する。符号化を除去することは、符号化を追加することと同様の方法で行われうることに留意されたい(それは符号化の逆のものを加えることに相当する)。
【０２６１】
図11は、本発明の実施形態を示している。図は、デジタルコンテンツのプロバイダと接続するためのインターネットへの接続など、通信ポート95を示している。コンテンツはまた、DVDまたはCDなどの媒体96からも取得されうる。PC上のデジタルコンテンツは、通常、メモリ91を用いてプロセッサ92により実行されるメディアプレイヤを用いてレンダリングされる。このようなプレイヤは、特有のコンテンツフォーマットに対して、通信ポート95および/または媒体96を介して取得されたコンテンツに対応するフォーマット特有の復号化を実施するための各プラグインを実行することができる。これらのコンテンツフォーマットは、AVI、DV、モーションJPEG、MPEG-I、MPEG-2、MPEG-4、WMV、オーディオCD、MP3、WMA、WAV、AIFF/AIFC、AUなどを含むことができる。デジタル著作権のために、コンテンツを復号するだけではなく、コンテンツの解読もする安全なプラグインが使用されうる。このプラグインは、メモリ91に記憶されたプロセッサ命令およびパラメータを含む。プロセッサ命令は、プロセスに、本発明による方法を実施させることができる。パラメータは、本明細書で述べたルックアップテーブルを含む。ユーザ入力94が、レンダリングされるべきコンテンツを指示するためのコマンドをユーザから取得するために提供されてもよく、またディスプレイ93および/またはスピーカは、復号されたかつ/または解読されたコンテンツをレンダリングするために提供される。
【０２６２】
本発明はまた、コンピュータプログラムに、特に、本発明を実行に移すように適合された、担持体上もしくはその中のコンピュータプログラムにまで拡張することが理解されよう。プログラムは、ソースコード、オブジェクトコード、コードの中間ソース、および例えば部分的にコンパイルされた形のオブジェクトコードの形態で、または本発明による方法の実施で使用するのに適した任意の他の形態とすることができる。担持体は、プログラムを担持できる任意のエンティティまたは装置とすることができる。例えば、担持体は、例えば、CD ROMまたは半導体ROMなどのROM、または例えば、フロッピー（登録商標）ディスクもしくはハードディスクなどの磁気記録媒体など、記憶媒体を含むことができる。さらに、担持体は、電気的な信号または光学的な信号などの送信可能な搬送波とすることができ、それは、電気的なケーブルまたは光ケーブルにより、あるいは無線または他の手段により搬送されうる。プログラムが、このような信号で実施された場合、担持体は、このようなケーブルまたは他の装置もしくは手段により構成されうる。代替的には、担持体は、プログラムが組み込まれる集積回路とすることができ、集積回路は、関連する方法を実施するように、または関連する方法を実施するのに使用されるように適合される。
【０２６３】
上記で述べた実施形態は、本発明を限定するものではなく、例示するものであること、および当業者であれば、添付の特許請求の範囲から逸脱することなく、多くの代替の実施形態を設計できるであろうことに留意されたい。特許請求の範囲では、カッコの間に置かれたいずれの参照記号も、請求項を限定するものと解釈されるべきではない。動詞「含む/備える(comprise)」およびその活用形を使用することは、請求項で述べられたもの以外の要素またはステップの存在を排除するものではない。要素に先行する冠詞「1つの(a)」または「1つの(an)」は、このような要素の複数のものが存在することを排除するものではない。本発明は、いくつかの別個の要素を備えるハードウェアにより、かつ適切にプログラムされたコンピュータにより実施されうる。いくつかの手段を列挙する装置請求項では、これらの手段のいくつかは、ハードウェアの全く1つのアイテムにより実施されうる。単に、いくつかの対策が相互に異なる従属項に記載されているということだけで、これらの対策の組み合わせを有利に使用できないことを示すものではない。
【符号の説明】
【０２６４】
10(810)  破線
12(812)  合成演算
20(820)  タイプIIテーブル
22(822)  タイプIVテーブル
24(824)  タイプIIIテーブル
26(826)  タイプIVテーブル
91(891)  メモリ
92(892)  プロセッサ
93(893)  ディスプレイ
94(894)  ユーザ入力
95(895)  通信ポート
96(896)  媒体
100  タイプIaテーブル
102  4ビットニブルの入力復号化
104  8ビットから128ビットへのマッピング
106  8ビットの全単射
108  出力ニブル符号化
200  タイプIIテーブル
202  4×4の入力復号化
204  4つの入力混合全単射
206  T-box
208  8×32ビットテーブル
210  MC
212  4×4の出力符号化
300  タイプIIIテーブル
308  逆演算
400  タイプIVテーブル
402  入力復号化
404  XOR
406  出力符号化
421  符号器
422  タイプIVブロック、XORネットワーク
423  タイプIIブロック
424  補償器
425  タイプIVブロック、XORネットワーク
426  復号器
427  タイプIIIブロック
431  ルックアップテーブル
432  ルックアップテーブル
433  XORネットワーク
500  タイプIbテーブル
502  入力ニブル復号化
504  8ビットの全単射
506  T-box
508  出力符号化
510  出力ニブル符号化
【図１】
0005688528.tif 000073
【図２】
0005688528.tif 000074
【図３】
0005688528.tif 000075
【図４】
0005688528.tif 000076
【図５】
0005688528.tif 000077
【図６】
0005688528.tif 000078
【図７】
0005688528.tif 000079
【図８】
0005688528.tif 000080
【図９】
0005688528.tif 000081
【図１０】
0005688528.tif 000082
【図１１】
0005688528.tif 000083