(57)【要約】【課題】事前計算テーブルの要素サイズを変更することなく、キャッシュ・タイミング攻撃に対して安全に暗号演算を行う。【解決手段】暗号演算装置１は、複数のキャッシュラインからなるキャッシュセットを複数含むキャッシュメモリ２と、キャッシュセットそれぞれに対応する複数のメモリブロック群を含むメインメモリ３と、複数の相異なる参照値と当該参照値それぞれに対して任意の変換を実行した変換結果との組み合わせを要素とする事前計算テーブルを記憶するテーブル記憶部４と、N+1個以下のメモリブロック群に事前計算テーブルを格納するテーブル格納部５と、事前計算テーブルの所望の要素をメモリブロック群から読み込み当該メモリブロック群に対応するキャッシュセットに格納するキャッシュ制御部７と、任意の値から求めた参照値により事前計算テーブルの要素を参照して変換結果を求める演算部８とを有する。【選択図】図１
2014165813.tif 000002
【特許請求の範囲】
【請求項１】
複数のキャッシュラインからなるキャッシュセットを複数含むキャッシュメモリと、
前記キャッシュセットそれぞれに対応する複数のメモリブロック群を含むメインメモリと、
複数の相異なる参照値と当該参照値それぞれに対して任意の変換を実行した変換結果との組み合わせを要素とする事前計算テーブルを記憶するテーブル記憶部と、
Nを前記事前計算テーブルの容量を前記キャッシュセットの容量で除算した値以上の最小の整数として、N+1個以下のメモリブロック群に前記事前計算テーブルを格納するテーブル格納部と、
前記事前計算テーブルの所望の要素が前記キャッシュメモリに存在しなければ、当該要素を前記メモリブロック群から読み込み当該メモリブロック群に対応する前記キャッシュセットに格納するキャッシュ制御部と、
任意の値が入力されると当該値から求めた参照値により前記事前計算テーブルの要素を参照して前記変換結果を求める演算部と、
を有する暗号演算装置。
【請求項２】
請求項１に記載の暗号演算装置であって、
前記事前計算テーブルの要素のサイズが前記キャッシュセットの容量の約数である
ことを特徴とする暗号演算装置。
【請求項３】
請求項１または２に記載の暗号演算装置であって、
前記テーブル記憶部は、複数の前記事前計算テーブルを記憶し、
前記テーブル格納部は、複数の前記事前計算テーブルそれぞれを相異なる前記キャッシュセットに対応する前記メモリブロック群に格納する
ことを特徴とする暗号演算装置。
【請求項４】
請求項１から３のいずれかに記載の暗号演算装置であって、
前記テーブル格納部は、2個以下の前記キャッシュセットに対応する前記メモリブロック群に前記事前計算テーブルを格納する
ことを特徴とする暗号演算装置。
【請求項５】
請求項１から４のいずれかに記載の暗号演算装置であって、
前記変換は、任意の暗号方式を構成するいずれかのアルゴリズムで用いられる
ことを特徴とする暗号演算装置。
【請求項６】
請求項５に記載の暗号演算装置であって、
前記暗号方式は、AES暗号方式である
ことを特徴とする暗号演算装置。
【請求項７】
キャッシュメモリは、複数のキャッシュラインからなるキャッシュセットを複数含んでおり、
メインメモリは、前記キャッシュセットそれぞれに対応する複数のメモリブロック群を含んでおり、
テーブル記憶部に、複数の相異なる参照値と当該参照値それぞれに対して任意の変換を実行した変換結果との組み合わせを要素とする事前計算テーブルが記憶されており、
Nを前記事前計算テーブルの容量を前記キャッシュセットの容量で除算した値以上の最小の整数として、N+1個以下のメモリブロック群に前記事前計算テーブルを配置するテーブル格納ステップと、
キャッシュ制御部が、前記事前計算テーブルの所望の要素が前記キャッシュメモリに存在しなければ、当該要素を前記メモリブロック群から読み込み当該メモリブロック群に対応する前記キャッシュセットに格納するキャッシュ制御ステップと、
演算部が、任意の値が入力されると当該値から求めた参照値により前記事前計算テーブルの要素を参照して前記変換結果を求める演算ステップと、
を含む暗号演算方法。
【請求項８】
請求項１から６のいずれかに記載の暗号演算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関し、特に、キャッシュ・タイミング攻撃への耐性を有する暗号演算技術に関する。
【背景技術】
【０００２】
現在多くのコンピュータは中央演算処理装置（Central Processing Unit, CPU）に主記憶装置（Random Access Memory, RAM）（以下、メインメモリとも呼ぶ。）よりも高速なキャッシュメモリを搭載しており、頻繁にアクセスするデータをキャッシュメモリへ一時的に記憶することで各種演算の高速化を実現している。所定の演算を実行する際に、所望のデータがキャッシュメモリに存在し、キャッシュメモリから所望のデータを読み込む場合をキャッシュヒットと呼び、所望のデータがキャッシュメモリに存在せず、メインメモリから所望のデータを読み込む場合をキャッシュミスと呼ぶ。
【０００３】
キャッシュヒット時は高速なキャッシュメモリ上のデータを読み込むため演算時間は短いが、キャッシュミス時には低速なメインメモリからデータを読み込む必要があるため演算時間は長くなる。このキャッシュヒット時とキャッシュミス時の演算時間の差を利用して、暗号演算を実行するコンピュータから秘密鍵などの秘密情報を不正に取得するキャッシュ・タイミング攻撃が知られている（例えば、非特許文献１参照）。
【０００４】
暗号アルゴリズムの実装方法において、暗号演算速度の高速化を目的として秘密情報に関する値を参照値とした事前計算テーブルが頻繁に利用されている。キャッシュ・タイミング攻撃では、暗号演算に関するタイミング情報を測定することにより事前計算テーブルの参照位置を推測し、暗号演算に用いられた秘密鍵を導出する。上述の通り、暗号演算時にメインメモリ上の事前計算テーブルを参照するか、キャッシュメモリ上の事前計算テーブルを参照するかによりアクセス時間が異なるため、この時間差を解析することにより事前計算テーブルの参照位置を推測することができる。
【０００５】
このようなキャッシュ・タイミング攻撃への対策として、事前計算テーブルの参照値から、それに対応する秘密情報を一意に特定することを困難にするために、できるだけ小さい要素サイズの事前計算テーブルを使用することが知られている（例えば、非特許文献２参照）。このような対策を施せば、キャッシュラインと呼ばれるキャッシュメモリを構成する最小単位（通常、複数バイトからなる）に事前計算テーブルの多くの要素を格納することができるため、キャッシュ・タイミング攻撃で推測される事前計算テーブルの要素数が多くなり秘密情報を一意に特定することが困難となる。なお、事前計算テーブルのサイズを小さくすると演算速度の低下を招くことがあるため、暗号演算全体の中でキャッシュ・タイミング攻撃の標的となりやすい一部の個所のみに要素サイズの小さい事前計算テーブルを使用する実装方法などが知られている（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】E. Tromer, D. A. Osvik, and A. Shamir、“Efficient Cache Attacks on AES, and Countermeasures”、Journal of Cryptology、vol.23、no.1、pp.37-71
【非特許文献２】E. Brickell, G. Graunke, M. Neve, J.-P. Seifert、“Software mitigations to hedge AES against cache-based software side channel vulnerabilities”、Cryptology ePrint Archive、Report 2006/052、[online]、［平成25年2月13日検索］、インターネット<URL: http://eprint.iacr.org/2006/052.pdf>
【非特許文献３】OpenSSL Software Foundation、“OpenSSL: The Open Source toolkit for SSL/TLS”、 [online]、［平成25年2月13日検索］、インターネット<URL: http://www.openssl.org/>
【発明の概要】
【発明が解決しようとする課題】
【０００７】
従来のキャッシュ・タイミング攻撃への対策方法は、実装に必要なコストが高いという問題点があった。例えば、インターネット上で情報を暗号化して送受信するSSL/TLS（Secure Socket Layer/Transport Layer Security）プロトコルの具体的な実装の1つであるOpenSSL（例えば、非特許文献３参照）等で一般的に用いられている高速化手法は、事前計算テーブルの要素サイズを小さくすると使用することができなくなり、演算速度が遅くなるという問題があった。また、小さい要素サイズの事前計算テーブルを使用することによる速度低下を抑えるために、1回の暗号演算内で小さい要素サイズの事前計算テーブルと高速化手法で使用する事前計算テーブルの2種類を使用することが考えられるが、暗号演算内で2種類の事前計算テーブルの使用を切り替える必要があり実装が容易ではなかった。
【０００８】
この発明の目的は、事前計算テーブルの要素サイズを変更することなく、キャッシュ・タイミング攻撃に対して安全に暗号演算を行う技術を提供することである。
【課題を解決するための手段】
【０００９】
上記の課題を解決するために、この発明の暗号演算装置は、複数のキャッシュラインからなるキャッシュセットを複数含むキャッシュメモリと、キャッシュセットそれぞれに対応する複数のメモリブロック群を含むメインメモリと、複数の相異なる参照値と当該参照値それぞれに対して任意の変換を実行した変換結果との組み合わせを要素とする事前計算テーブルを記憶するテーブル記憶部と、Nを事前計算テーブルの容量をキャッシュセットの容量で除算した値以上の最小の整数として、N+1個以下のメモリブロック群に事前計算テーブルを格納するテーブル格納部と、事前計算テーブルの所望の要素がキャッシュメモリに存在しなければ、当該要素をメモリブロック群から読み込みメモリブロック群に対応するキャッシュセットに格納するキャッシュ制御部と、任意の値が入力されると当該値から求めた参照値により事前計算テーブルの要素を参照して変換結果を求める演算部とを有する。
【発明の効果】
【００１０】
この発明の暗号演算技術によれば、キャッシュ・タイミング攻撃を行うために暗号演算時間に関するタイミング情報が取得されたとしても解析を行うために必要とされる十分な情報を得られないため、キャッシュ・タイミング攻撃に対して安全に暗号演算を行うことができる。
【００１１】
また、事前計算テーブルの要素サイズを変更することなく利用可能であるため、一般的な高速化手法を引き続き使用することができる。これにより暗号演算速度の低下を招くことなく、かつ容易に実装することが可能である。
【図面の簡単な説明】
【００１２】
【図１】暗号演算装置の機能構成を例示する図。
【図２】キャッシュ方式を説明する図。
【図３】暗号演算装置の処理フローを例示する図。
【図４】事前計算テーブルの格納方法を例示する図。
【図５】事前計算テーブルの格納方法を例示する図。
【図６】事前計算テーブルの格納方法を例示する図。
【図７】事前計算テーブルの格納方法を例示する図。
【図８】AES暗号方式の具体的な実装方法を例示する図。
【図９】従来技術の実験結果を示す図。
【図１０】実施形態の実験結果を示す図。
【発明を実施するための形態】
【００１３】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１４】
［実施形態］
従来の事前計算テーブルを用いた暗号方式の実装では、事前計算テーブルを格納するためにメインメモリ上の連続する領域を確保していた。このような実装では、セットアソシアティブ方式のキャッシュ方式を採用する中央演算処理装置を備えるコンピュータにより暗号演算を行うと、多数のキャッシュセット位置に対応するメモリブロックに跨って領域が確保されることになる。その結果、事前計算テーブルの各要素は、キャッシュメモリ上では、その参照値に依存して多くのキャッシュセットに分散して格納されることになっていた。
【００１５】
実施形態の暗号演算装置は、セットアソシアティブ方式のキャッシュ方式を採用する中央演算処理装置を備えるコンピュータにおいて、秘密情報に関する値を参照値とした事前計算テーブルの各要素を、その参照値に依存せず、キャシュメモリ上でできるだけ同じキャッシュセット位置に格納されるように、そのキャッシュセット位置に対応するメインメモリ上に配置することを特徴とする。
【００１６】
＜構成＞
図１を参照して、実施形態の暗号演算装置１の機能構成の一例を説明する。暗号演算装置１は、キャッシュメモリ２、メインメモリ３、テーブル記憶部４、テーブル格納部５、入力部６、キャッシュ制御部７、演算部８、出力部９を有する。暗号演算装置１は、例えば、中央演算処理装置（Central Processing Unit、CPU）、主記憶装置（Random Access Memory、RAM）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。キャッシュメモリ２は、例えば、中央演算処理装置と主記憶装置を接続するバス上に設置された高速かつ小容量の記憶装置である。メインメモリ３は、例えば、半導体素子により構成される比較的低速かつ大容量の記憶装置である。テーブル記憶部４は、例えば、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）などの半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。入力部６および出力部９は、例えば、ネットワークを介して処理対象のデータを送受信するネットワーク・インターフェースや、入出力デバイスを介して処理対象のデータを入出力する各種ポートなどである。
【００１７】
暗号演算装置１の搭載する中央演算処理装置はキャッシュ方式としてセットアソシアティブ方式を採用する。図２を参照して、セットアソシアティブ方式におけるキャッシュメモリ２およびメインメモリ３の構成例を説明する。
【００１８】
キャッシュメモリ２はS（S≧1）個のキャシュセット２０0,…,２０S-1から構成される。キャシュセット２０k（0≦k<S）はy（y≧1）個のキャッシュライン２００k,0,…,２００k,y-1から構成される。キャッシュセットを構成するキャッシュラインの個数の単位をウェイと呼び、1個のキャシュセットがy個のキャッシュラインからなるセットアソシアティブ方式をyウェイセットアソシアティブ方式と呼ぶこともある。キャッシュメモリ２はキャッシュライン２００を一単位としてデータの入出力を管理する。以降ではキャッシュライン２００のサイズをB（B≧1）バイトとする。
【００１９】
メインメモリ３はS個のメモリブロック群３０0,…,３０S-1を含む。メモリブロック群３０kはw（w≧y）個のメモリブロック３００k,0,…,３００k,w-1を含む。メインメモリ３はメモリブロック３００を一単位として読み取りおよび書き込みが行われる。メモリブロック３００のサイズはキャッシュライン２００のサイズと等しいことが一般的である。
【００２０】
キャシュメモリ２上のキャシュセット２０0,…,２０S-1とメインメモリ３上のメモリブロック群３０0,…,３０S-1とはキャッシュセット番号により対応付けられている。同じキャッシュセット番号に対応付けられたメモリブロックのデータはそのキャッシュセット番号をもつキャッシュセットに記憶される。例えば、キャッシュセット番号0に対応付けられたw個のメモリブロック３００0,0,…,３００0,w-1のいずれかに記憶されているデータは、キャッシュセット２０0に含まれるキャッシュライン２００0,0,…,２００0,y-1のいずれかに記憶される。
【００２１】
＜処理＞
図３を参照して、暗号演算装置の実行する処理の一例を手続きの順に従って説明する。
【００２２】
テーブル記憶部４には事前計算テーブル４０が記憶されている。事前計算テーブル４０は、複数の相異なる参照値iとその参照値iに対して任意の変換fを実行した変換結果f(i)との組み合わせを要素とするテーブルである。テーブル記憶部４に記憶される事前計算テーブルの数は複数であってもよい。事前計算テーブルの数は適用する具体的な暗号アルゴリズムの実装により決定される。
【００２３】
変換fは、任意の暗号方式を構成するいずれかのアルゴリズムの一部として実行される、入力値を所定の規則に従って出力値に変換する演算である。入力値を出力値に変換する規則は、実行するアルゴリズムにより規定される。暗号方式としては、例えば、任意の共通鍵暗号方式や任意の公開鍵暗号方式を適用でき、これらと同等の機能を有する任意の暗号方式を適用することができる。共通鍵暗号方式は、送信者と受信者が同一の鍵を共有し、暗号化に使用する鍵と復号に使用する鍵が同一である暗号方式である。代表的な共通鍵暗号方式としては、例えば、DES（Data Encryption Standard）、AES（Advanced Encryption Standard）などがある。公開鍵暗号方式は、受信者が公開鍵と秘密鍵を生成し、送信者は公開鍵を用いて暗号文を生成し、受信者は秘密鍵を用いて暗号文を復号する暗号方式である。代表的な公開鍵暗号方式としては、例えば、RSA暗号などがある。
【００２４】
テーブル格納部５はテーブル記憶部４に記憶されている事前計算テーブル４０をメインメモリ３に格納する（ステップS5）。このとき、格納する要素の参照値に依存せず、できるだけ同じキャッシュセット２０に対応づけられたメモリブロック群３０に収まるように事前計算テーブル４０の各要素を格納する。すなわち、Nを事前計算テーブル４０の容量をキャッシュセット２０の容量で除算した値以上の最小の整数として、N+1個以下のメモリブロック群３０0,…,３０N-1に事前計算テーブル４０の各要素を格納すればよい。後述する通り、事前計算テーブル４０は複数の要素からなるが、事前計算テーブル４０の第1要素がメモリブロックの境界に一致して配置できる場合には、N個のメモリブロック群３０0,…,３０N-1へ格納する。事前計算テーブル４０の第1要素がメモリブロックの境界に一致して配置できない場合であり、N個のメモリブロック群３０0,…,３０N-1では格納できない場合には、N+1個のメモリブロック群３０0,…,３０Nへ格納する。
【００２５】
図４を参照して、事前計算テーブル４０をメインメモリ３へ格納する方法を説明する。事前計算テーブル４０はθ（θ≧1）個のテーブル要素t0,…,tθ-1を含んでいる。テーブル格納部５は事前計算テーブル４０を所定のサイズのブロックに等分割して、同じキャッシュセット番号に対応付けられたメモリブロック群２０へ格納する。事前計算テーブル４０の各要素t0,…,tθ-1をメインメモリ３へ効率的に格納するために、事前計算テーブル４０を等分割するための要素tの個数はキャッシュライン２００のサイズを事前計算テーブル４０の要素tのサイズで除算した値に合わせるとよい。キャッシュライン２００のサイズをBバイト、事前計算テーブルの要素tのサイズをLバイトとすれば、事前計算テーブル４０を等分割したブロックに含まれる要素tの個数δはB/Lである。図４は、δ=4とした例である。要素t0,…,t3はメモリブロック３００k,0、要素t4,…,t7はメモリブロック３００k,1、要素t8,…,t11はメモリブロック３００k,2のように、1つのメモリブロック３００へは4つの要素tを格納している。
【００２６】
また、事前計算テーブル４０の各要素t0,…,tθ-1をメインメモリ３へ効率的に格納するために、事前計算テーブル４０の第１要素t0はメモリブロックの境界に沿って配置するとよい。このとき、どのメモリブロックの境界の位置に配置するかは問わない。以降の説明では事前計算テーブル４０の第1要素t0をメモリブロックの境界に沿って配置する場合を前提とする。メインメモリ３上で分散する方法は、以下のようにすればよい。すなわち、あるメモリブロック３００k,i（0≦i<y）へBバイト分の事前計算テーブル４０の要素tを格納したら、{(S-1)×B}/Lバイト分を飛ばして次のメモリブロック３００k,i+1へ格納し、これをキャッシュメモリ２のウェイ数yだけ繰り返す。
【００２７】
暗号アルゴリズムの実装方式によっては複数の事前計算テーブル４０を使用する場合も考えられる。図５を参照して、複数の事前計算テーブル４０をメインメモリ３へ格納する方法を説明する。この例では、2つの事前計算テーブル４０0,４０1をメインメモリ３へ格納するものとする。1つ目の事前計算テーブル４０0は上述の手順に従ってあるキャッシュセット２０0に対応するメモリブロック群３０0に分散して格納すればよい。続いて、2つ目の事前計算テーブル４０1をキャッシュセット２０0のすぐ隣のキャッシュセット２０1に対応するメモリブロック群３０1に分散して格納する。
【００２８】
図４、５では、1つの事前計算テーブル４０は1つのキャッシュセット２０に対応するメモリブロック群３０に格納される例を説明したが、事前計算テーブル４０全体のサイズがキャッシュセット２０のサイズよりも大きい場合には、複数のキャッシュセット２０に跨って1つの事前計算テーブル４０を格納しても構わない。ただし、この場合には、できるだけ少ないメモリブロック群３０に格納されるようにする。具体的には、事前計算テーブル４０を格納するメモリブロック群の最大数をN+1とすると、Nは事前計算テーブル４０の容量をキャッシュセット２０の容量で除算した値以上の最小の整数である。上述の通り、事前計算テーブルの第1要素t0をメモリブロックの境界に沿って配置することができれば、N個のメモリブロック群３０に格納することができる。事前計算テーブルの第1要素t0をメモリブロックの境界に配置することができない場合であり、N個のメモリブロック群３０では格納できない場合には、N+1個のメモリブロック群３０に格納すればよい。
【００２９】
具体的な実装方法として、効率良く事前計算テーブル４０の各要素t0,…,tθ-1をメインメモリ３に格納するために、事前計算テーブル４０の第1要素t0はメインメモリ３上のメモリブロック３００の境界に沿って配置するとよい。事前計算テーブル４０の第1要素t0を格納するメモリブロック３００の位置は問わない。メモリブロック群３０に対して事前計算テーブル４０の要素t0,…,tθ-1を格納する方法は2通り考えられる。
【００３０】
図６を参照して1番目の格納方法を説明する。図６において、一点鎖線で囲った部分は、キャッシュメモリ２およびメインメモリ３である。破線で囲った部分は、k番目のキャッシュセット２０kと、そのキャッシュセット２０kに対応するメモリブロック群３０kである。太線で囲った部分は、キャッシュセット２０kに含まれるキャッシュライン２００それぞれの境界と、メモリブロック群３０kに含まれる各メモリブロック３００それぞれの境界を表している。まず、事前計算テーブル４０の要素t0,…,tθ-1をδ個ずつに分割する。ここで、δはキャッシュライン２００のサイズを要素tのサイズで除算した値（δ=B/L）である。最初のδ個の要素t0,…,tδ-1をメインメモリ３上の任意のメモリブロック３００k,iの先頭位置からメモリブロックの境界まで横方向（もしくは行方向）に充填する。メモリブロック群３０kに対応するキャッシュメモリ２の同一のキャッシュセット位置kにテーブル要素が格納されるようにメインメモリ３上で分散させるために、次のδ個の要素tδ,…,t2δ-1を次の列のメモリブロック３００k,i+1に格納する。すべての要素t0,…,tθ-1がメインメモリ３へ格納されるまでこれを繰り返す。図６に示す通り、この格納方法により、事前計算テーブル４０の第1要素t0から第δ要素tδ-1までのδ個の要素を1つのメモリブロック３００k,iに格納する。その後、第δ+1要素tδから第2δ要素t2δ-1までのテーブル要素を、キャッシュメモリ２の同一のキャッシュセット位置kに格納するように、メインメモリ３上でS-1個のメモリブロック３００を飛ばして次の列に格納する。これをキャッシュメモリ２上の1つのキャッシュセット位置がすべて埋まるまで、すなわちウェイの数yだけ繰り返すことによって、事前計算テーブル４０のすべての要素t0,…,tθ-1をメインメモリ３に格納する。事前計算テーブル４０のサイズ、キャッシュメモリ２のウェイ数yやキャッシュライン２００のサイズLによっては、1つのキャッシュセット番号ですべてのテーブル要素t0,…,tθ-1を格納できない場合がある。その場合は複数列を利用して事前計算テーブル４０の全ての要素t0,…,tθ-1を格納する。複数列を利用する場合は、最初に1列目すべてに要素tを格納し、次に2列目すべてに要素tを格納し、これを繰り返すことで、メインメモリ３上で1列ずつ要素tを格納してもよい。また、最初に複数列の1行目すべてに要素tを格納し、次に2行目すべてに要素tを格納し、これを繰り返すことで、メインメモリ３上で1行ずつ要素tを格納してもよい。
【００３１】
図７を参照して2番目の格納方法を説明する。図７において、一点鎖線、破線、太線は図６と同様の意味で用いている。まず、事前計算テーブル４０の要素t0,…,tθ-1をy個ずつに分割する。上述の通り、yはキャッシュセットのウェイ数である。最初のy個の要素t0,…,ty-1をメインメモリ３上の任意のメモリブロック３００k,iの先頭位置からメモリブロック３００k,i+y-1まで縦方向（もしくは列方向）に充填する。メモリブロック群３０kに対応するキャッシュメモリ２の同一のキャッシュセット位置kにテーブル要素が格納されるようにメインメモリ３上で分散させるために、次のy個の要素ty,…,t2y-1をメモリブロック３００k,iから３００k,i+y-1までの2番目の位置に格納する。すべての要素t0,…,tθ-1がメインメモリ３へ格納されるまでこれを繰り返す。図７に示す通り、この格納方法により、事前計算テーブル４０の第1要素t0から第y要素のテーブル要素ty-1を1つのメモリブロック群３０kに含まれるy個のメモリブロック３００k,i,…,３００k,i+y-1の先頭位置に格納する。その後、同じメモリブロック群３０kのメモリブロック３００k,i,…,３００k,i+y-1の2番目の位置に格納する。これをキャッシュメモリ２上の1つのキャッシュセット位置がすべて埋まるまで、すなわちキャッシュライン２００のサイズを要素tのサイズで除算した値δだけ繰り返すことによって、事前計算テーブル４０のすべての要素をメインメモリ３に格納する。1つのキャッシュセット番号ですべてのテーブル要素t0,…,tθ-1を格納できない場合の処理は、1番目の格納方法と同様である。
【００３２】
図８を参照して、事前計算テーブルを用いた暗号アルゴリズムの具体的な演算処理方法を説明する。この例では、共通鍵暗号方式の一種であるブロック暗号の代表的なアルゴリズムの一つであるAES（Advanced Encryption Standard）暗号方式に適用した場合を説明する。ブロック暗号では複数ラウンドから構成される演算処理を実行する。図８に示すキャッシュメモリ２は、キャッシュラインのサイズを64バイト（B=64）、ウェイ数を8（y=8）、キャッシュセット数を64（S=64）とする。事前計算テーブル４０は、要素サイズが4バイト（L=4）、要素数が256個（θ=256）の事前計算テーブルを4種類使用する。したがって、1つのキャッシュラインに格納される事前計算テーブルの要素の数δは16となる（δ=B÷L=64÷4=16）。ここでは、非特許文献３に示したOpenSSLの実装を基本とした高速化手法を適用した実装方法を利用するものとする。
【００３３】
4種類の事前計算テーブル４０0,４０1,４０2,４０3をメインメモリ３上に分散して格納するために、メインメモリ３上にキャッシュメモリ２と同サイズの領域を事前計算テーブル領域として確保する。この領域の容量は32,768バイト（64バイト×8ウェイ×64セット）である。この領域には、事前計算テーブルの要素tが8,192個（32,768バイト÷4バイト）格納できる。T[・]は事前計算テーブル領域の・番目の位置を表す。
【００３４】
4種類の事前計算テーブル４０0〜４０3の格納方法を以下に示す。事前計算テーブルの要素サイズが4バイトであり、合計256個の要素があるため、1つの事前計算テーブルについて1,024バイトのキャッシュメモリ領域が必要である。キャッシュメモリ２のウェイ数が8、キャッシュラインのサイズが64バイトであるため、1つのキャッシュセットに512バイトのデータを格納することが可能である。そのため、事前計算テーブル４０h（0≦h≦3）のすべての要素th,0,…,th,255を格納するためには、2つのキャッシュセット２０が必要である。1つのキャッシュライン２００には16個（64バイト÷4バイト）の要素が充填できるため、事前計算テーブル４０hの要素32個を連続してメインメモリ３上に配置する。より具体的には、事前計算テーブル４０0の先頭から32個の要素（t0,0,…,t0,31）を事前計算テーブル領域の0番目から31番目（T[0]〜T[31]）に配置する。同様に、事前計算テーブル４０1の先頭から32個の要素（t1,0,…,t1,31）を事前計算テーブル領域の32番目から63番目（T[32]〜T[63]）に、事前計算テーブル４０2の先頭から32個の要素（t2,0,…,t2,31）を事前計算テーブル領域の64番目から95番目（T[64]〜T[95]）に、事前計算テーブル４０3の先頭から32個の要素（t3,0,…,t3,31）を事前計算テーブル領域の96番目から127番目（T[96]〜T[127]）に配置する。次に、事前計算テーブル４０0の32番目から63番目の32個の要素（t0,32,…,t0,63）をT[127]から3,584バイト（要素896個分）空けた位置、すなわち事前計算テーブル領域の1,024番目から1,055番目（T[1024]〜T[1055]）に配置する。同様に、事前計算テーブル４０1〜４０3の32番目から63番目の32個の要素（t1,32,…,t1,63,t2,32,…,t2,63,t3,32,…,t3,63）を事前計算テーブル領域の1,056番目から1,087番目、1,088番目から1,119番目、1,120番目から1,151番目（T[1056]〜T[1087],T[1088]〜T[1119],T[1020]〜T[1151]）に配置する。このように、事前計算テーブル４０0の要素を32個ずつT[1024×i]（i=0,1,2,…,7）に配置し、事前計算テーブル４０0の32個の要素に続けて、事前計算テーブル４０1〜４０3それぞれの32個の要素（計96個）を配置する。これを4種類の事前計算テーブル４０0〜４０3の256個の要素（計1,024個）がすべて格納されるまで繰り返す。
【００３５】
このようにメインメモリ３上に格納することにより、事前計算テーブル４０0の256個の要素t0,0,…,t0,255はキャッシュセット番号が0,1のキャッシュメモリ領域に、事前計算テーブル４０1の256個の要素t1,0,…,t1,255はキャッシュセット番号が2,3のキャッシュメモリ領域に、事前計算テーブル４０2の256個の要素t2,0,…,t2,255はキャッシュセット番号が4,5のキャッシュメモリ領域に、事前計算テーブル４０3の256個の要素t3,0,…,t3,255はキャッシュセット番号が6,7のキャッシュメモリ領域に格納されることとなる。このように、キャッシュメモリ２上に事前計算テーブル４０0〜４０3を格納する際に少ないキャッシュセット数を利用するようにメインメモリ３上に事前計算テーブル４０0〜４０3を分散して格納することで、キャッシュ・タイミング攻撃が困難となる。
【００３６】
上記の事前計算テーブル領域T[8192]を利用してAES暗号方式の暗号演算を行う場合、事前計算テーブルの入力値yは以下の通りとなる。OpenSSLでの実装のオリジナルの入力値をx、xを事前計算テーブルの要素を連続して格納する数32で割った商をx_s、xを同様に32で割った時の余りをx_aとすると、事前計算テーブル４０0〜４０3に関する入力値z0,z1,z2,z3は以下の式(1)(2)(3)(4)により求めることができる。
z0=x_s×1024+x_a            …(1)
z1=x_s×1024+x_a+32         …(2)
z2=x_s×1024+x_a+64         …(3)
z3=x_s×1024+x_a+96         …(4)
【００３７】
ここで、式(1)〜(4)における1024はキャッシュラインのサイズ64バイト×キャッシュセットの数64を事前計算テーブルの要素サイズ4バイトで割った数である（64×64÷4=1024）。式(2)〜(4)では1つの事前計算テーブルにつき32個分（4バイト×32個）の要素をキャッシュセット方向に配置するため式(2)では32を足している。式(3)(4)も同様である。
【００３８】
AES暗号方式を利用して暗号化を行う時には、暗号アルゴリズムのオリジナルの入力値xを4種類の事前計算テーブル４０0〜４０3を参照して、式(1)〜(4)によりz0〜z3のいずれかに変換し、z0〜z3のいずれかの値をT[8192]の入力値として演算を行う。
【００３９】
テーブル格納部５により事前計算テーブル４０がメインメモリ３に格納された後、入力部６に演算対象の値mが入力される（ステップS6）。演算対象の値mは暗号アルゴリズムへ入力された平文値もしくは暗号アルゴリズムを実行する過程で生成される中間値である。入力値mは演算部８へ入力される。演算部８は入力値mから事前計算テーブル４０の参照値jを求める。入力値mから参照値jを求める方法は、適用する暗号アルゴリズムにより規定される。そして、演算部８は、値jを参照値とする事前計算テーブル４０の要素tjを求める。
【００４０】
キャッシュ制御部７は演算部８が参照しようとする事前計算テーブル４０の要素tjがキャッシュメモリ２上に存在するか否かを確認する（ステップS71）。事前計算テーブル４０の所望の要素tjがキャッシュメモリ２上に存在しない場合には、メインメモリ３のメモリブロック群３０に格納された事前計算テーブル４０から所望の要素tjを読み込み、その要素tjが存在したメモリブロック３００に対応するキャッシュライン２００へその要素tjを格納する（ステップS72）。
【００４１】
演算部８は、キャッシュメモリ２上に存在する事前計算テーブル４０の所望の要素tjを参照し、値jに対して上述の変換fを実行した変換結果f(j)を求める（ステップS8）。求められた変換結果f(j)は出力部９を介して出力される（ステップS9）。
【００４２】
＜効果＞
上記のように、実施形態の暗号演算装置では、秘密情報に関する値を参照値とする事前計算テーブルの各要素を、その参照値に関わらず、キャシュメモリ上でできるだけ同じキャッシュセット位置に格納されるようにメインメモリ上に配置する。このように構成することで、キャッシュ・タイミング攻撃を行うために暗号演算時間に関するタイミング情報が取得されたとしても解析を行うために必要とされる十分な情報を得られない。したがって、キャッシュ・タイミング攻撃に対して安全に暗号演算を行うことができる。
【００４３】
また、従来のキャッシュ・タイミング攻撃に対する対策のような事前計算テーブルの要素サイズに対する制約がないため、事前計算テーブルの要素サイズを変更することなく適用することが可能である。これにより、SSL/TLS等で従来から利用されている一般的な高速化手法を引き続き使用することができる。これにより暗号演算速度の低下を招くことなく、かつ容易に実装することが可能である。
【００４４】
なお、この発明の暗号演算技術に対して、既存の他のキャッシュ・タイミング攻撃への対策方法を適用することも可能である。
【００４５】
［実験結果］
この発明の効果を確認するために、実機を用いて暗号演算に対してキャッシュ・タイミング攻撃を実行する実験を行った。実験ではキャッシュ・タイミング攻撃に対する対策が未実装である従来の暗号演算装置と、実施形態の暗号演算装置とで、AES暗号方式の暗号演算をそれぞれ実行した。実験を行った装置は中央演算処理装置として“Intel（登録商標） Core Soloプロセッサ”を搭載している装置を使用した。“Intel（登録商標） Core Soloプロセッサ”は8ウェイセットアソシアティブ方式を採用したキャッシュメモリを搭載している中央演算処理装置である。この環境においてキャッシュ・タイミング攻撃の一形態であるAccess-Driven Cache Attackを実行した結果を比較した。
【００４６】
この実験ではAccess-Driven Cache Attackで用いられているPrime+Probe法という計測方法を用いて時間計測を行った。Prime+Probe法では、暗号演算の実行前に、キャッシュメモリのサイズと同程度のサイズであらかじめ確保したメインメモリ上の領域の値をメモリブロックごとに読み出し、キャッシュメモリの全領域をそれらの値ですべて埋める。その後、暗号演算を実行し、再び同じメインメモリ上の領域の値を読み出し、その読み出しにかかる時間を計測する。Access-Driven Cache Attackでは、図９、１０に示すように計測時間をパターン図で表現し、秘密鍵を1バイトずつ導出する。図９、１０では、縦軸を暗号演算に入力した平文の先頭1バイトである平文値（Plaintext(Pt[0])）、横軸をキャッシュセット位置（Cache set、最大64セット）として、計測時間を表している。実験では様々な平文を入力として102,400回の計測を行なった。図９，１０では平文値ごとに平均化した計測時間を更に正規化した値を表している。各マスの濃淡は読み込みの応答速度を表しており、図右端に示す凡例の通り、色が濃いほど応答速度が早いことを表している。従って、グラフの各マスはある平文値に対してあるキャッシュセット位置に対応するメインメモリ上の値を読み込んだ際の応答速度を表している。暗号演算の実行前に、あらかじめ確保したメインメモリ上の領域の値を読み込み、キャッシュメモリの全領域をそれらの値で埋めることを行なっているため、暗号演算により変更されなかったキャッシュセット位置に属するキャッシュライン上に格納されている値はキャッシュメモリから読み込まれるため応答速度は早くなる。Access-Driven Cache Attackではこの動作を利用して暗号演算に用いられたデータの位置を推測している。このデータ位置は事前計算テーブルの参照値に相当している。事前計算テーブルを用いたAES暗号方式の実装では、入力された平文または演算の中間値と秘密鍵から計算されるラウンド鍵との排他的論理和を取った値を参照値として事前計算テーブルを参照する。したがって、平文値と事前計算テーブルの参照値が既知であれば、それらの排他的論理和を計算することによりラウンド鍵が計算できる。これにより攻撃者は秘密鍵を推測することが可能となる。
【００４７】
図９は、キャッシュ・タイミング攻撃に対する対策が未実装の暗号演算装置によりAES暗号方式の暗号演算に対してAccess-Driven Cache Attackを実行した結果である。図９ではキャッシュセット番号が33から43までの位置に応答速度が長いことを表す白い部分が見られる。攻撃者はこのタイミング情報に基づいて暗号演算に用いられた秘密情報を推測することができる。
【００４８】
図１０は、実施形態の暗号演算装置によりAES暗号方式の暗号演算に対してAccess-Driven Cache Attackを実行した結果である。図１０では全体の応答速度がほぼ均等になっており、際立った偏りが認められない。攻撃者はキャッシュ・タイミング攻撃に必要となる十分なタイミング情報を得ることができないため、暗号演算に用いられた秘密情報を推測することはできない。
【００４９】
以上の実験結果より、実施形態の暗号演算装置にはキャッシュ・タイミング攻撃に対する耐性を高める効果があることが示された。
【００５０】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００５１】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００５２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００５６】
１  暗号演算装置
２  キャッシュメモリ
３  メインメモリ
４  テーブル記憶部
５  テーブル格納部
６  入力部
７  キャッシュ制御部
８  演算部
９  出力部
２０  キャッシュセット
３０  メモリブロック群
４０  事前計算テーブル
２００  キャッシュライン
３００  メモリブロック
【図１】
2014165813.tif 000003
【図２】
2014165813.tif 000004
【図３】
2014165813.tif 000005
【図４】
2014165813.tif 000006
【図５】
2014165813.tif 000007
【図６】
2014165813.tif 000008
【図７】
2014165813.tif 000009
【図８】
2014165813.tif 000010
【図９】
2014165813.tif 000011
【図１０】
2014165813.tif 000012