説明

差分電力解析を妨害する命令マスクや他の手法を備えた暗号アーキテクチャ

【課題】タイムライン・アラインメントを利用するDPA攻撃を妨ぐ方法を実現する。
【解決手段】装置のDPA攻撃を防ぐ方法は、少なくとも1つのルックアップ・テーブル・アドレスを判定するのに必要な時間量をランダムに変更する工程と、少なくとも1つのルックアップ・テーブル107の1つのアクセスと別のルックアップ・テーブルの後のアクセスとの間で生じる時間量をランダムに変更する工程を挿入し、攻撃者が暗号化を解読するために実施しなくてはならない漏洩情報の時間的なアラインメントを実施不可能にする。

【発明の詳細な説明】
【技術分野】
【0001】
(関連出願との相互参照)
本願は、「Cryptographic Architecture with Random Instruction Masking to Thwart Differential Power Analysis」、「Cryptographic Bus Architecture for the Prevention of Differential Power Analysis」及び「Cryptographic CPU Architecture with Random Instruction Masking to Thwart Differential Power Analysis」とそれぞれ題する、西暦2004年6月8日付けで全て出願された米国特許出願第10/864,569号、米国特許出願第10/864,556号及び米国特許出願第10/864,568号の一部継続出願である。これらの関連出願のそれぞれの内容を本明細書及び特許請求の範囲に援用する。
【0002】
本発明は、マイクロエレクトロニクス組立体(スマート・カードや同様なものなど)において、差分電力解析(DPA)攻撃が利用された場合にそのセキュリティ漏洩を妨げるために用いる、暗号手法のセキュリティ、及び、プロセッサの暗号アーキテクチャに関する。
【背景技術】
【0003】
暗号手法は当該技術分野において周知である。実際に、暗号手法の起源は少なくとも、符号及び暗号によって情報を隠すやり方を人々が見出すほど、好奇の目に対して、特定の情報の秘密を保つ必要性が十分に重要になったシーザーの時代にさかのぼる。
【0004】
今日では、暗号手法の適用例は、政府及び民間の広い範囲に及んでいる。暗号手法の一適用例は、スマート・カードに記憶された情報の保護、及び/又は、認可されていない使用若しくは変更からの、スマート・カードの機能の保護である。スマート・カードなどの暗号装置は、秘密鍵を用いて、入力情報の処理、及び/又は、出力情報の生成を行う。強度が特に高い暗号手法が利用される場合には、暗号装置(スマート・カードなど)に記憶された情報は、攻撃に対して比較的安全であるとみなされている。
【0005】
現代の暗号法は、ディジタル・データの互換及び換字を利用する。暗号化対象のメッセージ(平文として知られている)は、鍵によってパラメータ化された関数によって変換される。暗号化処理の出力(暗号文として知られている)は次いで送信される。受信暗号文は次いで、鍵を用いてもう一度平文に復号される。
【0006】
現代の暗号法が用いられている一例は、ケーブル・テレビジョン及び衛星テレビジョンの有料チャネルなどの有料TV限定受信システムにみられる。(秘密鍵を含む)スマート・カード及び/又はセキュリティ・プロセッサを用いてテレビジョン信号を復号する。攻撃者は、秘密鍵を明らかにするために、ケーブル受信器又は衛星受信器を購入し、次いで、中にあるスマート・カード又はセキュリティ・プロセッサを攻撃する。暗号文は、ケーブル・プロバイダ又は衛星プロバイダから送出される情報であり、平文は、テレビ受像機に送出される復号テレビジョン信号である。よって、一般には、入力情報及び出力情報(すなわち、平文及び暗号文)が、攻撃者によって入手可能であり、秘密鍵についての情報が入手可能でないことがみなされている。図1は、暗号システムを表すものである。攻撃者は、EM放射、電力消費、時間観測等によって漏洩し得る、秘密鍵に関する情報を探すことによってスマート・カード又はセキュリティ・プロセッサを攻撃することができる。攻撃者は次いで、漏洩された情報(通常、設計者の予想しなかった情報(side channel information)と呼ばれている)を用いて、使用されている秘密鍵を明らかにすることが可能である。漏洩された情報、又は設計者が予想しなかった情報から秘密鍵を明らかにする通常の手法の1つは、差分電力解析(DPA)として知られている。残念ながら、電力消費、EM放射等によって、装置によって行われている特定の暗号処理情報の漏洩、及び、それによる、秘密についての情報の取得が行われる訳でないということを保証するやり方は何ら存在しない。
【0007】
よって、DPAなどの相関手法を用いるハッカーによって用いることが可能でない漏洩情報を生成する防御手法が必要である。
【0008】
本明細書記載の手法の一適用例の背景を表すために、以下に背景を説明する。これは、周知の暗号(解読するのにDPA解析が通常用いられるデータ暗号化規格(DES))に関するものである。この説明が例証の目的のために過ぎないこと、及び、設計者が予想しなかった情報を用いて秘密鍵を明らかにするいくつかのハッカー手法から、いくつかのデータ暗号化形式の秘密鍵を保護するのに本発明を用いることができることを当業者は認識するであろう。
【0009】
周知のDES暗号は、いくつか(通常は16個)の換字ボックス(Sボックス)関数を利用する。Sボックス関数は、非線形であり、テーブル・ルックアップ、ブール論理、又は適切にプログラムされたコンピュータを用いることによって実施することが可能である。
【0010】
攻撃者がDPAを利用して、DESを利用した暗号装置(スマート・カードなど)(特に、ディジタル暗号化規格(DES)が用いられている)において使用されている秘密鍵を明らかにすることが可能であることがここ数年の間に明らかになっている。例えば、Paul Cokerら(Cryptographic Research社(San Francisco、California))によって公表されているDifferential Power Analysisを参照のこと。DPAに関するチュートリアルは、Manfred Aignerら(The Institute for Applied Information Processing and Communication、University of Technology、Graz、Austria)によって公表されている論文Power Analysis Tutorialにも記載されている。前述の参考文献に開示されているように、DPA手法を利用するために、攻撃者は、暗号装置の電力消費を監視する。装置によって使用される電力における変動は、装置内で行われている動作を反映しており、今度は、これを用いて、装置内に記憶された、秘密鍵についての情報を少しずつ集めることが可能である。
【0011】
しかし、電力消費情報以外の、設計者が予想しなかった情報をDPAによって調べて暗号化鍵を抽出することができることを強調する。特定例として、電磁(EM)放射及び不良出力がある。残念ながら、電力消費、EM放射、及び同様なものによって、特定の情報が漏洩される訳でないということを保証するやり方は何ら存在せず、その電力消費、EM放射、又は同様なものによって情報を識別することができるという点で、暗号装置(スマート・カードなど)に全く漏れがないことを期待することは実際的でないと考えられている。しかし、高度な統計手法が(例えば、DPA処理において)用いられても、漏洩された如何なる情報の関係付けをも不能にする防御手法を用いることが可能である。そういうものとして、本発明は、暗号装置(スマート・カードなど)内に記憶された秘密鍵と、電力消費情報との互いの関係付けを不能にするという課題に対する解決策に関する。
【0012】
従来技術には、特定の無相関化手法が存在している。例えば、Messergesらによる米国特許第6,295,606号明細書及び米国特許第6,298,153号明細書、並びにBoeckelerによる欧州特許出願公報第1,098,469号明細書を参照のこと。
【0013】
Gregor Boeckelerによる欧州特許出願公報第1,098,469号明細書記載の無相関化手法は、マスター・クロックCLK1に基づいた、CPUの既存プロファイル上に挿入して、二次クロックCLK2に基づいた、ランダムな現行プロファイルを重ね合わせるものである。各クロックは、3MHz乃至7MHzの範囲でランダムに調節される。二つのクロックが互いに、その中心周波数に関して異なるために、合成された現行プロファイルは、無作為化され、それによって、DPA攻撃者の作業は、より困難になる。
【0014】
Thomas Messergesによる米国特許第6,208,135号明細書は、目標ビット組において無作為化開始点を用いるものである。上記文献では、対応する目標ビットを、異なる順序で処理する。よって、DPA攻撃者が、対象の平文全てからの関連目標ビットをグループ化して、特定の目標ビット位置に関連した統計解析を行うことが困難になる。しかし、この手法は、データ・バスによって漏洩される情報を隠すものでないのみならず、悪意のある攻撃者がこの情報を用いて目標ビットを、正しいビット位置に再配列することを妨げることも可能でない。
【0015】
ランダム・マスクを用いて、メモリに記憶されている間に、かつ、暗号アルゴリズム自体による処理中に、隠された状態にメッセージ及び鍵を保つ別の手法(米国特許番号6,295,606号明細書記載)もMessergesによって開発されている。しかし、マスクはランダムに変更されるので、新たなSボックスはそれに応じて更新しなければならず、これは時間を要する。この欠点は、この種のマスク処理が、3倍乃至5倍、DESアルゴリズムを遅くすることである。更に、この種のマスク処理は、正しい暗号出力をもたらすために結果を最終的にマスク解除しなければならないラウンド16(Round Sixteen)からの48ビット部分鍵を攻撃者が収集することを妨げることが可能でない。よって、Messergesの手法は、マスク解除後、DPAに対して脆弱になる。ラウンド16で48ビットはもう分かっており、次いで、攻撃者は、56個にするための残りの6つの鍵ビットを全数探索することが可能である。本願の手法は計算がより高速であり、DESアルゴリズムのラウンド16からの部分鍵を攻撃者が収集することを妨げることも可能である。
【発明の概要】
【発明が解決しようとする課題】
【0016】
前述の従来技術手法は特定の制約を有しており、よって改良を必要としている。本発明は、事実上、電力消費と暗号ビット値とを互いに関係付けることを不能にする、DPA処理に対する対抗手段としての、独自のランダム命令マスク(RIM)を提案するものである。本発明は、Messergesの手法、Boecklerの手法や他の手法に対して次の利点を有している。
【0017】
(1)計算がより効率的である:Messergesらの教示による手法は、Sボックスの定期的な更新によって300%乃至500%、DESアルゴリズムを減速させるものである。本発明では、DESアルゴリズムは、約15%、減速することになる。
【0018】
(2)よりロバストである:複数アドレス位置について情報の漏洩が存在している場合にもこれがあてはまる。
【0019】
(3)保護がより好適である;鍵の48ビットは、最終DESラウンドにおいて完全に隠すことが可能である(DESでは、出力がアルゴリズムの最後でマスク解除され、それによって鍵を露出させることになり、このことは従来技術では解決されない)。
【0020】
(4)電力消費が低い:電力消費を暗号処理中に約200%まで増加させる、Boecklerのランダムな現行プロファイリングに対して、電力消費の増加は1%未満である。
【0021】
本明細書記載の好ましい実施例の詳細を説明する前に、DESアルゴリズム及びDPA攻撃に関する更なる詳細を記載する。この分野に不案内の場合、更なる情報を次の論文で見つけることができる(P. Kocher、J. Jaffe及びB. Junによる「Introduction to Differential Power Analysis and Related Attacks、1998」、Thomas S. Messergers、Ezzy A. Dabbish及びRobert H. Sloanによる「Investigations of Power Analysis Attacks on Smartcards、Proceedings of USENIX Workshop on Smartcard Technology、Chicago、Illinois、May 1999、pp. 151−161」、並びに、Manfred Aigner及びElisabeth Oswaldによる「Power Analysis Tutorial、Institute for Applied Information Processing and Communications University of Technology Graz、Austria」)。本願記載の手法の詳細な説明の背景を示す記載を以下に設ける。
【0022】
DESアルゴリズムは、反復ブロック暗号の例である。DESは、内容を本明細書及び特許請求の範囲に援用する、ANSI X.392、「American Standard for Data Encryption Algorithm (DEA)、American Standard Institute、1981」に詳細に説明されている。DES暗号は周知であり、ラウンドと呼ばれるプログラム・シーケンスにおいて設けられたいくつかの(通常、16個の)換字・転置ボックス(SPボックス)関数を利用するものである。SPボックス関数は、非線形であり、通常、ルックアップ・テーブル若しくはブール論理ゲート、又は適切にプログラムされたコンピュータを用いて実施される。16ラウンドのそれぞれでは、DES暗号化アルゴリズムは、8つのSPボックス演算を、今度は、各ルックアップ・テーブルを順次アクセスすることによって、(又は、同等の論理ゲートを用いることによって)行う。8つのSPボックスそれぞれは入力として、スクランブルされた(ここで、スクランブルされたということは、鍵のXOR及びシフトが行われることを意味する)6ビット鍵を得て、OR演算を行うためにCPUによってアクセスされる対象の4ビット出力目標を生成する。前述のスクランブルされた6ビット鍵それぞれはSPボックスの・エントリ・アドレスである。表1は、DESの32ビット実施形態におけるSPボックス1及び2のC言語表現を示す。DESは16ビット、32ビット及び64ビットで実行することが可能であるが、基準例として32ビット表現を選んでいる。表1から、各SPルックアップが64個のエレメントを含んでいることが分かる。基準DES実施形態における各エレメントは32ビットであり、このエレメントには、特定の4ビット出力目標が埋め込まれている。この埋め込みは次に、更に詳細に説明する。
【0023】
データ・バスは通常、幅が32ビットであり、この4ビット出力目標を、表1において示唆される転置規則(SPボックス毎1つ)によって32ビット語内のどこかに分布させる。表1では、データは16進形式で示す。すなわち、各SPルックアップ・テーブルは、特定の4ビット出力目標について別々の埋め込み位置を有する。例えば、表1に示すルックアップ・テーブルSP1は、32ビット語におけるビット位置24、16、10及び2において4ビット出力目標を埋め込む。ルックアップ・テーブルSP2は、ビット位置20、5、31及び15において4ビット出力目標を埋め込む。ここで、特定の4ビット出力の場合、ビット20は最上位ビット(MSB)であり、ビット15は最下位ビット(LSB)である。更なる例証として、ルックアップ・テーブルSP1の最初の4つのエントリ(すなわち、SP1[0:3]={0x01010400L, 0x00000000L,
0x00010000L, 0x01010404L}は、14、0、4、15の4ビット出力目標値を有する。特に、SP[0]={0x01010400L}には、14の4ビット出力目標値(すなわち、1110)が埋め込まれる。例えば、SP1[0]の場合、32ビット2進語は0000 000 0000 000 0000 000 0000 000である。特定の32ビット2進語の場合、最も右の桁はLSBである一方、最も左の桁はMSBである。4ビット出力目標を導き出すために、24、16、10及び2におけるビット値が用いられる。例えば、SP1[0]の場合、4ビット目標は1110である。これは、32ビット2進語SP1[0]の位置24における4ビット出力目標のMSB値を探すことによって定められ、次のビットは32ビット2進語SP1[0]の位置16にあり、第3のビットは32ビット2進語SP1[0]の位置10にあり、最後に0のLSBは、32ビット2進語SP1[0]の位置2にある。上記2進表現では、ビット位置24、16、10及び0に下線を引いている。第4のエントリSP1[3]={0x01010404L}(LSBのみでSP1[0]の1110とは異なる)は、4ビット出力目標値15(すなわち、1111)を有する。
【0024】
一方、ルックアップ・テーブルSP2は、ルックアップ・テーブルSP2の最初の4つのエントリに示す、異なる埋め込みビット位置手法を示す(すなわち、SP2[0:3]={0x80108020L, 0x80008000L, 0x000080000L, 0x00108020L}である。対応する4ビット・ブロックの15、3、1及び13の値を反映するために、ビット位置20、5、31及び15における内容のみを変更する。特に、ルックアップ・テーブルSP2の第1のエントリ(SP2[0]={0x80108020L})は、4ビット出力目標値15(すなわち、1111)を有するが、それは、ビット20、ビット5、ビット31及びビット15が全て1の値を有するからである。第4のエントリ(SP2[3]={0x00108020L})(第2のLSBのみで、SP2[0]の1111とは異なる)は、4ビット目標値13(すなわち、1101)を有する。
【0025】
4ビット出力目標と、それに対応するSPボックスのエントリとの間の関係を明らかにすると、次に、特定のSPボックスのエントリ・アドレスの計算を記載する。一般に、DESアルゴリズムは、CPUにおいて実行しているシフト命令を用いてボックスのエントリ・アドレスを計算する。特定のSPボックスのエントリ・アドレスの計算において用いるシフト命令の数も、SPボックスの各連続アクセス間の時間間隔も、DESアルゴリズムに詳しい者には周知である。このことに鑑みれば、DPA攻撃は、そのボックスに特有の先行シフト命令署名を参照することによる、SPボックスの各4ビット出力目標の電力トレースのアラインメントに焦点を当てるものである。表2に示すように、通常の演算では、各SPボックスのアクセスには、異なる量のシフト(すなわち、>>8、>>16又は>>24(「>>」はCコンピュータ言語において右シフトを表し、よって、「>>n」は、nビットの右シフトを表す))が先行する。表2におけるルーチンがCコンピュータ言語で記述されていることを当業者は認識するであろう。図2aは、8つのSPボックス[SP1…SP8]の通常のアクセス順序に対応するタイムラインを示す。各シフト命令は通常、一度に1ビット、シフトするので、>>8は通常、8ビット右シフト命令を示唆し、>>16は通常、16ビット右シフト命令を示唆する等である。SP5のシフトは、数字131によって示す。
【0026】
電力トレースのアラインメントを行うために、DPA攻撃者は、電力トレースにおけるパターンを探す。SPボックス5(SP5)のSPアドレス計算を明らかにするため、DPA攻撃者は、表2においてわかるように8シフトを示すパターンを探す。更に、DPA攻撃者は、8シフト(数字131を参照のこと)の最初から次のシフト組の最初までの時間が、図2aに示す時間TIに等しいことが分かるものである。よって、電力トレースにおけるこのパターンが分かると、DPA攻撃者は、SP5のSPアドレス計算が(数字123で)明らかになったことが分かるものである。更に、攻撃者は、8シフトの最後に続く時間スロットの電力トレースにおける情報が、対応する4ビット出力目標情報を含むことも分かるものである。この情報によって、6ビット鍵に関する情報を供給する統計的平均化の電力トレースのアラインメントが可能になる。電力トレースには雑音があり、よって、命令署名や他のパターンを見つけることが、DPA攻撃の成功を保証しないことがあり得ることを当業者が認識するであろう。しかし、命令署名や他のパターンが従来技術において、攻撃者が用いるうえで入手可能である。こうした命令署名及び時間パターンを破壊することによって、DPA攻撃の成功の可能性はもっと低くなる。
【0027】
図2bは、8つのSPボックスのアクセス順序を無作為化させたタイムラインを示す。図2bに例証するように、SP1及びSP3の処理の順序が交換されており、SP4及びSP6も同様である。この場合には、SPボックス・アクセス順序を入れ替えることによって、こうしたシフト命令署名を識別して電力トレースのアラインメントを行わなければならないことになる。特定のSPボックスのアラインメントの後、こうした電力トレースの統計的平均化や他の解析を行うことが可能である。よって、DPA攻撃者は最終的に電力トレースのアラインメントを行って6ビット鍵を明らかにすることが可能である。
【課題を解決するための手段】
【0028】
一実施例では、本発明は、暗号装置のDPAの成功を抑制する方法を提供し、この方法は、少なくとも1つのルックアップ・テーブル・アドレスを判定するのに必要な時間量をランダムに変更する工程と、少なくとも1つのルックアップ・テーブルの1つのアクセスと別のルックアップ・テーブルの後のアクセスとの間で生じる時間量をランダムに変更する工程を備える。
【0029】
別の実施例では、本発明は、暗号アーキテクチャを提供する。暗号アーキテクチャは、プロセッサと、プロセッサに結合された、暗号アルゴリズムを含むメモリ・モジュールと、プロセッサに結合され、プロセッサの状態処理を制御する制御フラグ・レジスタと、制御フラグ・レジスタに結合された乱数生成器とを備え、プロセッサは制御フラグ・レジスタをセットし、乱数生成器は制御フラグ・レジスタをリセットする。
【0030】
更に別の実施例では、本発明は、DPAを妨害するシステムを提供し、このシステムは、暗号化アルゴリズムを実行する手段と、ランダムな数の疑似命令を暗号化アルゴリズムに挿入する手段とを備える。
【0031】
更に別の実施例では、本発明は、チャネル情報の無相関化を行うシステムを提供し、このシステムは、データ暗号化規格(DES)アルゴリズムを実行する手段を備え、DESアルゴリズムは、複数の換字/転置ボックス・エントリ・アドレス評価と、複数の換字/転置ボックス・エントリ・アドレス評価それぞれにおいて実行されるランダムな数のシフト命令を挿入する手段とを備える。
【0032】
更に別の実施例では、本発明は、暗号アーキテクチャの電力トレースを変える方法を提供し、この方法は、暗号化アルゴリズムを実行する工程と、制御フラグをセットする工程と、制御フラグがセットされている場合にランダムな数の命令を行う工程とを備える。
【0033】
なお更に別の実施例では、本発明は、暗号装置の差分電力解析の成功を抑制する方法を提供し、この方法は、少なくとも1つのルックアップ・テーブル・アドレスを判定するのに必要な時間量をランダムに増加させる工程と、少なくとも1つのルックアップ・テーブルの一アクセスと、別のルックアップ・テーブルの後のアクセスとの間に生じる時間量をランダムに増加させる工程とを備える。
【0034】
なお更にもう1つの別の実施例では、本発明は、暗号アーキテクチャを提供する。暗号アーキテクチャは、プロセッサと、プロセッサに結合された、暗号アルゴリズムを含むメモリ・モジュールと、プロセッサに結合され、プロセッサの状態処理を制御する制御フラグ・レジスタと、制御フラグ・レジスタに結合された乱数生成器とを備え、プロセッサは制御フラグ・レジスタをセットし、乱数生成器は制御フラグ・レジスタをリセットする。
【0035】
更に別の実施例では、本発明は、差分電力解析を妨害するシステムを提供し、このシステムは、暗号化アルゴリズムを実行する手段と、ランダムな数の疑似命令を暗号化アルゴリズムに挿入する手段とを備える。
【0036】
なお更に別の実施例では、本発明は、設計者が予想しなかった情報の無相関化を行うシステムを提供し、このシステムは、データ暗号化規格(DES)アルゴリズムを実行する手段を備え、DESアルゴリズムは、複数の換字/転置ボックス・エントリ・アドレス評価と、複数の換字/転置ボックス・エントリ・アドレス評価それぞれにおいて実行されるランダムな数のシフト命令を挿入する手段とを備える。
【0037】
更に別の実施例では、本発明は、暗号アーキテクチャの電力トレースを変える方法を提供し、この方法は、暗号化アルゴリズムを実行する工程と、制御フラグをセットする工程と、制御フラグがセットされている場合にランダムな数の命令を行う工程とを備える。
【0038】
更に別の実施例では、本発明は、暗号CPUアーキテクチャを提供する。暗号CPUアーキテクチャは、ALUと、制御フラグと、算術命令に応じてALUの出力を通常、受ける複数のレジスタと、制御フラグがセットされている場合に算術命令に応じて、複数のレジスタのうちの1つの代わりに、ALUの出力を受ける更なるレジスタとを備える。
【0039】
更に別の実施例では、本発明は、プログラムの実行中の電力解析から、CPUにおいて行われているデータ処理を隠す方法を提供する。この方法は、(i)プログラムの実行の一時点で、ランダムな数のプログラム・カウンタ・サイクル命令フェッチ・サイクルを挿入する工程と、(ii)ランダムな数の命令フェッチ・サイクルが行われている間に、メモリから命令をフェッチし、プログラム・シーケンスにおいてこうした命令を実行する一方、こうした命令の実行に基づいて通常のメモリ位置の更新を抑制する工程と、(iii)ランダムな数の命令の終わりに、ランダムな数の命令フェッチ・サイクルが行われている間に当初フェッチされた命令と同じ命令を再フェッチする一方、命令が再フェッチされた場合、CPUのメモリ位置を通常のやり方で更新することによって通常プログラム実行を再開する工程とを備える。
【0040】
なお更に別の実施例では、本発明は、プログラムの実行中の電力解析から、CPUにおいて行われているデータ処理を隠す方法を提供する。この方法は、(i)プログラムの実行中の時点に、ランダムな数のプログラム・カウンタ・サイクル命令フェッチ・サイクルを挿入する工程と、(ii)ランダムな数の命令フェッチ・サイクルが行われている間に、(a)命令をメモリからフェッチする工程、(b)プログラム・シーケンスにおいてこうした命令を実行する工程、及び(c)メモリ・レジスタに結果を書き込む工程に関連した電力消費をまねる工程とを備える。
【0041】
更に別の実施例では、本発明は、データ・プロセッサを提供する。データ・プロセッサは、算術論理演算装置と、制御フラグ・レジスタと、算術命令に応じ、かつ制御フラグ・レジスタの第1の状態に応じ算術論理演算装置の出力を通常、受ける複数のレジスタと、命令に応じ、かつ制御フラグ・レジスタの第2の状態に応じ複数のレジスタのうちの1つの代わりに、算術論理演算装置の出力を受けるダミー・レジスタとを備える。
【0042】
別の実施例では、本発明は、暗号バス・アーキテクチャを提供する。暗号バス・アーキテクチャは、複数ビットの乱数が出力される複数の乱数出力を有する乱数生成器と、複数の双方向バス・ドライバであって、それぞれが、乱数出力の少なくとも1つを受ける少なくとも1つの入力を有する双方向バス・ドライバと、複数の双方向バス・ドライバの少なくとも1つを、少なくとも別の双方向バス・ドライバに結合するバスとを備え、バスの共通線に結合された双方向バス・ドライバは、乱数出力のうちの、選択された共通の乱数出力によって制御される。
【0043】
別の実施例では、本発明は、セキュリティの漏洩を妨げる方法を提供し、この方法は、バスを介して暗号化ビットを送出する工程と、バス上の暗号化ビットの極性をランダムに切り換える工程とを備える。
【0044】
別の実施例は、本発明は、秘密鍵を保護する方法を提供する。この方法は、複数の双方向バス・ドライバを備える工程と、複数の双方向バス・ドライバのうちの少なくとも第1の双方向バス・ドライバと、複数の双方向バス・ドライバのうちの少なくとも第2の双方向バス・ドライバとの間にライン・データ・バスを結合する工程と、第1のビット組をバスに供給する旨を第1の双方向バス・ドライバに通知する工程であって、上記ビットが第1の極性を有する工程と、第1の極性を有する第1のビット組を受信する旨を第2の双方向バス・ドライバに通知する工程と、第2のビット組をバスに供給する旨を第1の双方向バス・ドライバにランダムに通知する工程であって、第2のビット組が、第1のビット組とは逆の極性を有する工程と、逆の極性を有する第2のビット組を受信する旨を第2の双方向バス・ドライバに通知する工程とを備える。
【図面の簡単な説明】
【0045】
【図1】攻撃者が入手可能な情報の、従来技術を表す図である。
【図2a】特定のラウンドの8つのSPルックアップ・テーブルの通常のアクセスに相当する、従来技術のタイムラインである。
【図2b】特定のラウンドの8つのSPルックアップ・テーブルの無作為化されたアクセス順序に相当する、従来技術のタイムラインを示す図である。
【図3】本明細書による、ランダム命令マスク(RIM)によって時間間隔及びSPボックス・アクセス順序が無作為化されたタイムラインを示す図である。
【図4】本明細書による、シフト命令が等化されたタイムラインを示す図である。
【図5】本明細書による、DESアルゴリズムを実施するハードウェア・アーキテクチャの第1の実施例の構成図である。
【図6】本明細書による、DESアルゴリズムを実施するハードウェア・アーキテクチャの第2の実施例の構成図である。
【図7】本明細書による、DESアルゴリズムを実施するハードウェア・アーキテクチャの第3の実施例の構成図である。
【図8】図7の実施例に関連したタイムラインである。
【図9】本明細書による、DESアルゴリズムを実施するハードウェア・アーキテクチャの第4の実施例の構成図である。
【図10】従来技術のRISC CPUの構成図である。
【図11】本発明の第6の実施例によるRISC CPUの構成図である。
【図12】暗号バス・アーキテクチャ実施例によるシステムの構成図である。
【図13】暗号バス・アーキテクチャ実施例によるバス・アーキテクチャの詳細の構成図である。
【図14】暗号バス・アーキテクチャ実施例による、デュアル・レールを備えたビット書き込みを表す構成図である。
【発明を実施するための形態】
【0046】
表1は、64個のエレメントのルックアップ・テーブルとして実施されたSPボックス1及び2の値(C言語で表している)を示す。
【0047】
表2は、特定のラウンドのDESの8つのSPルックアップ・テーブルの順次アクセスを行うC言語プログラムである。
【0048】
表3は、表2のCプログラム文番号5を実施するためのアセンブラ言語プログラムである。
【0049】
表4は、8個のS及びPのボックスの演算を、今度は、各ルックアップ・テーブルの順次アクセスによって行うDES暗号化アルゴリズムの一部分を実施するためのアセンブラ言語プログラムである。
【0050】
表5は、図7の実施例を用いて、表2のCプログラム文番号5を実施するためのアセンブラ言語プログラムである。
【0051】
序論
本明細書記載の手法を次に、添付図面を参照しながら、更に徹底的に説明する。この説明では、上記手法の好ましい実施例を図7及び図8を参照しながら説明する。しかし、図7及び図8を説明する前に、この詳細な説明は、前述の関連出願において提示された内容の一部の記載を繰り返す図3乃至図6をたどるものである。こうした説明は、図7及び図8によって示される改良をよりうまく理解するうえで有用である。
【0052】
図9は基本的に、図6及び図7の実施例の組み合わせである第4の実施例を表す。
【0053】
図11は、修正されたRISC CPU設計に基づいた第5の実施例を表す。しかし、上記修正は、望まれる場合、非RISC CPUに用いることもできる。
【0054】
図12乃至図14は、他の実施例とは無関係に用いても他の実施例と組み合わせて用いてもよい暗号バス・アーキテクチャに関する。
【0055】
本明細書記載の手法は、種々の多くの形態において実施することができ、本明細書記載の実施例に限定されるものとして解されるべきでない。
【0056】
以下の説明は、周知の暗号と、データ暗号化規格(DES)と、DESを解読するのに通常用いられる、DPA解析妨害とに関して本願開示を用いるうえでの1つの背景を設けるものである。この説明が例証の目的のために過ぎないこと、及び、設計者が予想しなかった情報を用いて秘密鍵を明らかにするいくつかのハッカー手法から、いくつかのデータ暗号化形式の秘密鍵を保護するのに本明細書記載の手法を利用することができることを当業者は認識するはずである。
【0057】
一般に、どの暗号化アルゴリズムも、プロセッサによって実行される一連の命令である。こうした命令の入力及び出力は種々のものである一方で、各命令を完了するのに必要な時間量は、プロセッサ、又はプロセッサとの間でデータが送信されるバスのクロック速度によって定められる。他の命令よりも多くのクロック・サイクルを要する命令がある。データの暗号化/復号に用いる暗号化アルゴリズムが分かっていることによって、アルゴリズムのタイミングについての知識(すなわち、使用される命令、及び、よって、各命令の所要時間長についての知識)がハッカーに与えられる。タイミングについてのこの知識を次いで用いて、設計者が予想しなかった情報のアラインメントを行うことが可能である。よって、設計者が予想しなかった情報を次いで、攻撃者が暗号化を破ることを可能にする高度な統計手法によって処理することが可能である。
【0058】
暗号化アルゴリズム内の命令数を無作為化するシステム及び方法を本明細書に記載する。命令数を無作為化することにより、かつ、そうした命令を実行し、それによって、ランダムな遅延時間を挿入することによって、暗号化アルゴリズム内の命令及びタイミングは、DPA攻撃者にはもう分からないものである。よって、アルゴリズムのタイミングは、攻撃者には分からないことになり、攻撃者は、設計者が予想しなかった情報のアラインメントを行うことができなくなる。設計者が予想しなかった情報のアラインメントなしでは、高度な統計手法は失敗することになり、暗号化情報は保護されることになる。
【0059】
以下の説明は、本明細書記載の手法の特定の実施例を、DESを用いたシステムに組み入れてDPA攻撃を妨げることができる。他の暗号化アルゴリズムを用いる他のシステムに本発明を組み入れて特定の命令間の時間の無作為化を行うことができることを当業者は認識するであろう。時間のこの無作為化を用いて、暗号化を破るためにアルゴリズムのタイミングの理解に依拠する何れかの攻撃を挫折させることができる。
【0060】
本明細書は、暗号処理を行うのに用いられる、マイクロプロセッサ上のオンチップ・ランダム命令マスク(RIM)アーキテクチャに特有の情報を記載するものである。更に、本明細書は、既存の暗号アルゴリズム(RSAアルゴリズム、DESアルゴリズム、AESアルゴリズム及び非線形アルゴリズムを含む)を、設計者が予想しなかった攻撃(すなわち、漏洩した電力情報に基づいた攻撃)から保護するアーキテクチャ手法を記載するものである。下にある回路が前述の情報を常に漏洩している可能性が非常に高いものであっても、セキュアな状態にシステムを維持するという動機付けがある。
【0061】
目標ビットの処理の順序を無作為化するというソフトウェア手法は、アルゴルズムを完全に保護するには十分でない。目標ビットをその元の順序にDPA攻撃者が再配列することを可能にし得る、命令署名又は電力パターン全てを破壊することも必要である。よって、一手法は、好ましくは、本明細書記載の、命令の無作為化と、時間遅延とを実施するアーキテクチャによるハードウェア保護によってソフトウェア手法を補完することである。
【0062】
DESや他の暗号アルゴリズムへの秘密鍵と互いに関係付けられる情報がDPA攻撃によって抽出されることを妨げるためのアーキテクチャ手法又はハードウェア手法のいくつかの実施例を以下に説明する。更に、DESに関する特定の背景情報を前述している。この分野に不案内の場合、まず、本明細書の導入部分に記載した文献を参照すべきである。更に、以下の例証は、DESアルゴリズムを徹底的に知っていることに依拠するものである。他のアルゴリズムのうちの1つに対する攻撃を試行するためには、適切なアルゴリズムを同等な詳細まで知っていることが必要になる。DPA攻撃や関連攻撃を妨げる防御的なRIM手法を説明することによってこの説明を始める。DPA選択機能は、低位命令が(通常、6つの鍵ビットを用いるため)4ビットを操作することが多いので、1ビットだけではなく、4つの目標ビットの値を同時に選択することが可能であるものとする。結果として生じるDPA特性は、より大きなピークを有する傾向にあるが、より良好な信号対雑音比を有するものでない。これは、比例してより少ないサンプルが、平均化において含められるからである。
【実施例】
【0063】
図3は、SPボックスのエントリ・アドレス計算131と、特定の4ビット出力目標123の生成との間のタイムライン関係を修正し得る方法を表す。上記修正は、(例えば、図5の実施例による)ランダムな数の疑似シフト命令133の挿入、又は(例えば、図6の実施例による)各SPボックスのエントリ・アドレス計算サブルーチンにおけるランダムな数の無作為化疑似命令の挿入を備える。
【0064】
挿入される疑似命令の数は必ずしもランダムでなくてよいが、それは、各SPボックスが、同数の実命令及び疑似命令を有することになった場合、どのボックスがどれであるかを確かめるうえで攻撃者になお残された情報がほとんどないか全くないからである。
【0065】
疑似シフト命令がシフトを含んでおり、実シフト命令の電力署名を厳密にまねることが望ましい。こうした疑似命令がシフトを含んでいない限り、その作用は、DPA攻撃者によって、おそらく観測され、よって無視され得る。(本明細書記載の手法が用いられない場合)シフト数とSPボックス指数との間には一定の関係が存在するものであり、攻撃者がどこかでそのシフト数を識別することが可能である限り、攻撃者は、アドレス指定される特定のSPボックスを識別することが可能である。攻撃者は、データの統計的な再配列を行って正しいシフト数を見出すことによってこのことを行うことが可能である。DESに加えて、大半の暗号化アルゴリズムは実際にシフト命令をどこかで利用しており、アルゴリズムをDPA攻撃者が分かっているものとみなした場合、本明細書記載の、ランダムな数のシフト命令を挿入する手法を利用しない限り、同様な相関を見出すことが可能である。
【0066】
図3に示すように、疑似シフト命令133や他の疑似命令133を挿入することによって、各SPボックスのエントリ・アドレス評価において実行される命令数のみならず、連続するSPボックス間の時間間隔Tnも変わる。図3に示す例では、ランダムな数の疑似シフト命令133がSP5に挿入されており、よって、図2bと比較して、SP5のアクセスとSP1のアクセスとの間の時間間隔Tが変えられている。更に、ランダムな数の疑似命令133がSP4に挿入されており、よって、図2bと比較して、SP4のアクセスとSP6のアクセスとの間の時間間隔Tが変えられている。当然、ランダムな数の疑似シフト命令133は、他のSPボックスのうちの1つ又は複数に挿入することも可能である。命令は、「疑似」と呼ばれているが、それは、好ましくは、対応する実命令の電力消費トレースをまねるからである(実際に、特定の実施例では、実命令であり得る)。一方、疑似命令の実行は、プロセッサによって更新されるデータを何らもたらさない。
【0067】
好ましくは実シフト命令を電力使用の視点からまねるランダムな数の疑似命令133を挿入することによって、シフト命令署名も時間間隔署名もカモフラージュされるものであるか、又は、除去されるものでもある。これによって、プログラムにおいてアクセスされているSPボックスSP1乃至SP8をDPA攻撃者が識別することができなくなってしまうことになる。これによって、SPボックスのアクセス順序の再シフト(無作為化)がDPA攻撃者から情報を隠すうえで効果的なやり方になることになる。よって、DPA攻撃者は、統計的な平均化及び解析のために同じ基準への別々の電力トレースのアラインメントを行うことがもうできなくなる。疑似命令が電力使用の視点から実シフト命令を厳密にまねた場合、攻撃者には、どのSPボックスがどれかを識別するのかが非常に難しくなり得る。疑似命令が無作為化命令組をまねた場合、SPボックスを少しでも認識するのが非常に難しいことが大いにあり得る。攻撃された装置が利用していると攻撃者がみなすプロトコルと、装置によって使用される暗号化プロトコルが同じであるか否かを攻撃者が知りたいと思うことは大いにあり得る。
【0068】
前述の通り、それぞれの(又は一部の)SPボックスのエントリ・アドレス評価において実行されるシフト命令の数の無作為化の代わりに、図4に示すように、各出力の前に(例えば)合計24個のシフトがあるようにみえるようにシフト命令数を等しくすることが考えられる。しかし、命令数を無作為化し、それによって、連続したSPボックス・アクセスそれぞれの間の時間間隔も無作為化することが好ましいことがあり得る。よって、無作為化は、SPボックスのアクセスを識別するための署名として、時間間隔の、攻撃者の作業の妨害の手助けとなる。こうして不確実性が更に増したことによって、攻撃者の作業は更に複雑になる。しかし、図4を参照することによって分かるように、挿入される疑似命令131の数を無作為化することは、本明細書記載内容に必須でない。
【0069】
第1の実施例の詳細な説明
図5は、(図3を参照して説明したような)ランダムな数の疑似シフト命令133又は(図4を参照して説明したような)等しくした数のシフト命令133を挿入するのに用い得るDESアルゴリズムを実施するハードウェア・アーキテクチャの第1の実施例を表す。図5に示すシステムは、単一チップ上にRAM103メモリ及びROM105メモリとともに32ビット・プロセッサ又は中央処理装置(CPU)101を含む。他のハードウェア・アーキテクチャ(2ビットや8ビットのアーキテクチャ)に本明細書記載の手法を実施することができることを当業者は認識するであろう。よって、CPUは16ビット・プロセッサ又は64ビット・プロセッサであり得る。
【0070】
システムは、前述のようにルックアップ・テーブルとして実施することが可能な換字/転置ボックス(SP1乃至SP8)107も含む。CPU101が、ROM105に記憶された暗号化/復号プログラムを実行する一方、RAM103は、暗号文データを中間的に記憶するためのものである。6ビット鍵(又は推測される鍵)121及びSPボックス107を用いて暗号関数fを計算する。乱数生成器115がランダム命令マスク(RIM)制御フラグ・レジスタ113に結合される。RIM制御フラグ・レジスタ113はCPU101に結合される。この実施例では、乱数生成器115及びRIM制御フラグ・レジスタ113を用いて、何れの特定の6ビット鍵121についても、統計的な情報をもたらすようこの電力トレースの時間アラインメントを行うことが可能でないように電力トレースをカムフラージュする。攻撃者は、シフト命令署名を追跡することによって、各4ビット出力目標123に関連した電力トレースのアラインメントを行うことに焦点を当てているので、本明細書記載のRIM手法は、この追跡機能をディセーブルすることに集中している。
【0071】
ランダムな数の疑似シフト命令133は、CPU101、RIM制御フラグ・レジスタ113及び乱数生成器115の反復によって生成される。CPU101は、ROM105に記憶された暗号化/復号プログラムを実行する。この暗号化/復号プログラム(後に説明することとする)に埋め込まれたものは、RIM制御フラグ・レジスタ113をセットするための命令である。この命令を処理すると、CPU101は、これをセットするRIM制御フラグ・レジスタ113に向けて、バス109上で信号を送出する。RIM制御フラグ・レジスタ113は次いで、制御線111上でRIM制御フラグ信号をCPU101に向けて送出し、それによって、CPU101状態マシンが停止することになる(計算に応じてレジスタの更新が停止することになる)。このことは、RIM制御フラグ・レジスタ113から信号を、CPU101内のプログラム・カウンタ・レジスタに送出することによって実現することができる。これによって、プログラム・カウンタはディセーブルされることになる。事実上、CPU101の状態マシンは停止される。
【0072】
CPU101の状態マシンは、RIM制御フラグ・レジスタ113がリセットされるまで、停止状態に留まる。これによって、RIM制御フラグ・レジスタ113によって信号がCPU101に向けて制御線111上で送出され、CPU101内のプログラム・カウンタがイネーブルされることになる。RIM制御フラグ・レジスタ113は好ましくは、乱数生成器115の使用によってリセットされる。設計を簡単にするために、乱数生成器115は好ましくは、1ビット乱数生成器である。乱数生成器115は、CPU101の命令サイクルのタイミングと同期化される。乱数生成器115は、クロック・サイクル毎に出力を供給することができるものであり、又は、ランダムな数の、X個のサイクル(Xは、何れかの数(5など)である)の後にRIM制御フラグ・レジスタに確実に供給されるようゲートすることができる。1ビット乱数生成器115の場合、使用される論理によってゼロ又は1が1ビット乱数生成器115から受信されるとリセットされるようRIM制御フラグ・レジスタ113がプログラムされる。例えば、1ビット乱数生成器115からのゼロによってRIM制御フラグ・レジスタ113がリセットされることになるものとする。1ビット乱数生成器115からゼロを受信した後にしかRIM制御フラグ・レジスタ113がリセットされず、ランダムな数のサイクル後に1ビット乱数生成器はゼロを生成することになるので、CPU101の状態マシンが停止される時間もランダムになる。よって、ランダムな数の疑似命令133が生成され、それによって、アルゴリズムのタイムラインに影響が及ぼされる。
【0073】
好ましくは、疑似命令133は、元の命令と同様な電力署名を電力トレース上に生成する命令であるが、CPU101内のデスティネーション・レジスタに実行結果をもう一度書き込むことは抑制される。CPU101の状態マシンが停止されるからである。CPU101の抑制によって、CPUの状態が維持される。よって、もう一度書き込むことを抑制することによって、アルゴリズムにおける次の工程にCPUが移ることが妨げられる。しかし、電力トレースによって、そうでないことが示唆される。よって、攻撃者は、電力トレースを用いて鍵を復号することができなくなる。
【0074】
図5中のCPU101は好ましくは、CPU101のデスティネーション・カウンタ、又はCPU101のプログラム・カウンタの更新を、アクティブ状態にされるとディセーブルする、バス111上で送出されるRIM制御フラグ信号(RIM制御フラグ・レジスタ113によって生成される)を備えた疑似命令に対処するよう修正される(修正CPUの実施例の詳細は、「Cryptographic CPU Architecture with Random Instruction Masking to Thwart Differential Power Analysis」と題する、西暦2004年6月8日付け出願の米国特許出願第10/864,568号明細書に開示されている)。
【0075】
バス111上のこのRIM制御フラグ信号の結果、CPU101の状態マシンが停止している間に実行される命令は全て、電力トレースの離散サンプルの数が、特定の4ビット出力目標123についてもう一定でないように電力トレースを変える以外には重大な影響は有しない。RIM制御フラグ・レジスタ113がセットされている間、ランダムな数の命令が実行される。RIM制御フラグ111がリセットされると、4ビット出力目標123がRAM103に供給される。RIMの導入によって、各SPボックスのエントリ・アドレス評価において実行されるシフト命令の数のランダムなばらつきのみならず、連続したSPボックス・アクセスTIそれぞれの間の時間間隔におけるランダムなばらつきも生じる。RIM制御フラグがアクティブ状態にされている間に実行されるランダムな命令に関する更なる詳細については、「Cryptographic Bus Architecture for the Prevention of Differential Power Analysis」と題する、西暦2004年6月8日付け出願の米国特許出願第10/864,556号明細書を参照のこと。
【0076】
疑似シフト命令の挿入が機能する方法を以下に説明する。表2に示すように、DESのC言語文第5番(すなわち、fval|=SP5[(work>>8)&0x3fL]は、SP5ルックアップ・テーブルをアクセスするためのエントリ・アドレス計算の一部として8ビット右シフト命令(すなわち、「work>>8」)を含む。表3は、対応するアセンブラ言語サブルーチンへの、この単一C言語文の拡張を示す。
【0077】
表3中のアセンブラ文第4番(すなわち、jal link rshft)は、「rshft」としてラベリングされたサブルーチン又は文第13番にジャンプし、かつリンクする(よって、ニーモニックはjalである)。この文における「link」の語は、戻りアドレスを含むレジスタを表す。プログラムが文第13番(すなわち、プログラム・カウンタpc←pc+1)を実行すると、プログラム・カウンタは引き上げるのを停止する。プログラム・カウンタは、文第14番を予めフェッチしようとするが、乱数生成器115によってRIM制御フラグがリセットされるまで停止される。「rshft」サブルーチンは、レジスタCにおいて規定されるように8つの位置、レジスタ1を右シフトする。シフト命令に関連した電力トレース部分をカムフラージュするために、(文第13番と文第14番との間に示す)可変ブロック・サイズのRIM文が、第15番(すなわち、sra 11)のような実際のシフト命令文の前(若しくは後、又は前と後との両方)に挿入される。RIM制御フラグ・レジスタ113がCPU101によってセットされると、RIM制御フラグ・レジスタ113が乱数生成器115によってリセットされるまで、表3中の命令第13番によってRIM命令の挿入が可能になる。文第15番の実行及びRIMブロックの完了の後に、プログラムの「有用な」実行が再開する。
【0078】
表3中の文第13番及び文第14番の位置は、例証の目的のためのものに過ぎない。これらの文は、第15番のような実際のシフト命令文の前、中間、又は後に存在し得る。好ましくは、設計を簡単にするために、文第13番及び文第14番は、シフト・ルーチンの範囲内に配置される。このランダムな挿入によって、シフト命令署名を追跡する、DPA攻撃者の試行が妨害されるが、それは、離散電力トレース・サンプルの数がもう一定でなく、ランダムであるからである。よって、攻撃者は、電力トレースの時間アラインメントを4ビット出力目標123毎に行うことが可能でない。更に、ランダムな命令をこのように挿入することによって、時間間隔(例えば、TI5)も変わり、それによって、DPA攻撃者の試行が更に妨害される。疑似シフト文のランダムな数の挿入は、その効果を強めるようにループの中央に挿入されることが好ましい。
【0079】
こうした文がループの外側に挿入された場合、1つ又は2つの疑似シフトしか付加しないことは実際には手助けにならないものである。a>>8をa>>10に変えることは、DESアルゴリズムの場合に、十分なカムフラージュにならないことがあり得る。a>>8をa>>16又はa>>24から隠そうとする場合、このことは、a>>8をa>>16又はa>>24と混同させるのに十分な疑似シフト命令を付加することを必要とする。付加されたランダムな数の疑似シフト文をループ内に配置することによって、付加された疑似シフト文数は確実に8の整数倍数になる。ランダムな数の疑似シフト文がループの外側に挿入された場合、他の手法を用いて、付加された疑似シフ命令数を確実に8、16、24(又はDPA攻撃者を混乱させるうえでこれらに十分に近い他の数)にすることが可能である。
【0080】
更なる情報を与えるという点で、表4は、8つのS及びPのボックス演算を、今度は、図5に示すように各ルックアップ・テーブル107を順次アクセスすることによって行う、DES暗号化アルゴリズムのDES部分の一部分を実施するための16ビットCPUのアセンブラ言語プログラムである。下線を引いた文は、コメント目的のための、対応するC言語文である。
【0081】
第2の実施例の詳細な説明
図6は、ランダムな数のランダムな疑似命令133(図3を参照のこと)を挿入するのに用いることができるDESアルゴリズムを実施するハードウェア・アーキテクチャの別の実施例を表す。
【0082】
DPA攻撃者は、シフト命令署名を追跡することによって、各4ビット出力目標に関連した電力トレースのアラインメントを行うことに焦点を当てているので、図5の第1の実施例は、各SPボックスのエントリ・アドレスの計算サブルーチンにランダムな数のRIM命令を挿入することによってこの追跡機能をディセーブルする。しかし、この実施例では、以下に詳細に説明するように、こうした命令の数のみならず内容も変更されることになる。
【0083】
図6に示すように、この第2の実施例は図5の第1の実施例に非常に類似しており、よって、共通の構成要素は、共通の参照符号によって表す。図5の実施例の場合にように、この実施例は好ましくは、単一チップ上に、RAMメモリ103及びROMメモリ105とともに配置された32ビットのCPU101である。このチップも好ましくは、ルックアップ・テーブルとして実施することが可能な換字/転置ボックス(SP1乃至SP8)107を含む。CPU101が、ROM105に記憶された当該プログラムを実行する一方、RAM103は、暗号文データを中間的に記憶するためのものである。この実施例では、CPU101は、ROM105から通常の暗号化プログラムのみならず、32ビットの疑似乱数生成器によって、カムフラージュされた、無作為化命令もフェッチする。図6に示すように、RIM制御フラグ・レジスタ113によって選択されるMUX119は、CPU101によってフェッチされる命令、ROM105からの実命令、又は32ビットの疑似乱数生成器117によって生成される無作為化命令のタイプを判定する。
【0084】
第1の実施例と同様に、アクティブ状態にされるとCPUのデスティネーション・レジスタの更新をディセーブルすることになるRIM制御フラグ・レジスタ113を含めるよう通常のCPUを修正する。このフラグがセットされていることによって、RIM文内で実行される命令は全て、特定の4ビット出力目標に対する離散電力トレース・サンプル数がもう一定でないように電力トレースをカムフラージュすることになる。こうした命令の数及びタイプは、乱数生成器によって実行中に判定される。RIM制御フラグが1ビット乱数生成器によってリセットされた後にCPUが通常の実行を再開するまでプログラム・カウンタは更新されないので、プログラム・アドレスも、別の32ビット疑似乱数によって置き換えられる。
【0085】
図5や図6のRIM制御線111は、半導体デバイスのレイヤ内に深く埋めることによって「プローブプルーフ」にすべきである。しかし、RIM制御線111を探ることが可能な場合、DPA攻撃を扱う前述の手法は、攻撃を通してグランド(又は、論理に応じてハイ)に接続することによって線111上のREM制御信号をDPA攻撃者がディセーブルする場合に打ち負かされることになる。
【0086】
第3の実施例の詳細な説明
図7は図5又は図6の実施例よりも探査に対する耐性が高い第3の実施例を表し、図8はこの実施例のタイムラインを示す。この実施例は、以下に説明するシフト制御カウンタ(SCC)140や他の変更を導入することによってシングル・ポイント障害攻撃(すなわち、前述の実施例の線111に対する攻撃)を克服するものである。この実施例は、シフト命令(実及び疑似)の合計数が24に固定される実施例を参照しながら説明する。しかし、固定される実命令の数は特定の他の数に固定することが可能であるか、図5及び図6を参照しながら前述した手法を利用して無作為化することが可能であることを当業者はこの場合、認識するはずである。図7の実施例は攻撃が線111に対して行われることを想定しており、攻撃が首尾良く行われた場合にも、保護されていない設計(図2a及び図2bを参照しながら説明した設計など)にシステムがもう一度戻らないように線111の前述の設計が修正される。
【0087】
データ暗号化規格(DES)アルゴリズムに規定された、特定のSPボックスのエントリ・アドレスの計算中に、SCC140は(例えば、適切なソフトウェア命令又はソフトウェア命令組(例えば、表5中の命令3及び命令4を参照のこと)によって)SPボックスのカウントに相当するカウントにセットされることになる。各復号化シフト命令によって、ゼロに達するまで、例えば、それ自身の復号器ハードウェアを用いてこのカウンタ140が1、減らされることになる。ゼロ・カウントによって、その出力で「RIM_shift」信号がアクティブ状態にされることになる。それによって、その後のシフト命令はどれもRIM命令(すなわち、カムフラージュされた電力署名を備えた疑似シフト命令)になる。図8では、各SPボックスは、それに関連した24個の右ビット・シフトを有する。しかし、右ビット・シフト命令の一部又は全部はRIM_shift(すなわち、疑似シフト)である。シフト(図8中の疑似シフト)は、ハッチング線によって表す。例えば、ボックスSP5の場合、8つのシフトが実右ビット・シフト命令である一方、16つのシフトは疑似シフト命令である。DPA攻撃者の攻撃によって「RIM_shift」信号がディセーブルされた場合、暗号化アルゴリズムの通常の実行が、追加のシフトが行われることによって中断されることになるが、それは、疑似シフト命令がその場合、線111との干渉によって実命令になるからである。線111との干渉によって、疑似シフト命令の生成が単に抑制される代わりに、実シフト命令によって、抑制された疑似シフト命令が置き換えられる。
【0088】
よって、攻撃者は、有用な統計的鍵情報を何ら収集することが可能でない。すなわち、RIMフラグを妨害することによって、暗号化アルゴリズムの通常の実行が中断されることになり、(追加の実シフトが行われることによって)正しい結果がもたらされるのでDPA攻撃は失敗する。一方、DPA攻撃者が「RIM_shift」信号をそのままにしておく場合、アクティブ状態にされた「RIM_shift」信号は、図5又は図6を参照して前述した、シフト命令の電力署名をカムフラージュすることになる。このことは、DPAが必要とする目標ビットのグループ化及び再配列がずっと難しくなるのでSPボックスをアクセスする順序の無作為化がDPA攻撃者の試行を妨害するうえで効果的なやり方になることを意味する。
【0089】
表5は表3と同様であるが、アセンブラ言語サブルーチンにおいて、SCC140増補RIM実施形態を示す。(イタリック・フォントの)同様なアセンブラ文第3番はまず、レジスタCの内容を語SCCに記憶する(よって、ニーモニックがswである)アセンブラ文第4番(すなわち、sw_SCC C)によって示すようにシフト制御カウンタ(SCC)を初期化するのに用いる対象のシフト数をレジスタCにロードする。アセンブラ文第3は、実行するシフト数をCPUに伝えることを意図しているものでない。その代わりに、アセンブラ文第5番をこの目的で用いてSPボックス・アクセス毎に同一のシフト命令電力署名を供給する。SCC制御回路は各シフト命令を復号化し、ゼロに達するまでそのカウンタを減らす。ゼロにされたSSCカウンタは次いで、電力署名をカムフラージュするよう「RIM_shft」信号をアサートすることによって、後の実シフト命令を疑似命令に変換する。非シフト命令によって、「RIM_shft」信号がアクティブ状態になることは決してないものである。SCC回路は、SPボックス・アクセス中に暗号化アルゴリズムを実行している際にのみ、アクティブ状態になっているので、通常のシフト命令の復号化は事実上、非SPボックス演算に対するものである。
【0090】
直接的な探査から、チップ上のRIM制御線111を物理的に保護することはもはや重要でない(しかし、攻撃によって有意義な結果を得ることになるとDPA攻撃者に思わせるために、保護することは意味をなすものである(そうした攻撃は徒労になる)。よって、精通している一部の攻撃者は、RIMをディセーブルするように、RIM制御線111を強制的に常に論理「0」にする(物理的に保護されているか否かにかかわらず)ことができる場合がある。この実施例では、チップのDPA攻撃は、新たな手法(すなわち、不必要な疑似シフトが実シフトに変換され、それによって、データが単に意味のないものになってしまう)もよって保護される。
【0091】
要約すれば、DPAの原理は、2つの電力トレース群の和の差を計算し、プロットするものである。DPAは、2つの電力トレース群の和の差と、特定の順序でシステムのデータ経路を進む目標ビット(b)の内容との間に統計的相関が存在していることによって効果的であり得る。この実施例におけるSCC増補RIMの導入が理由で、目標ビットがこの場合、特定の順序ではなくランダムな順序でシステムのデータ経路を介して進むものであり、暗号化アルゴリズムの通常の実行を中断することなくディセーブルすることは可能でないので、この統計的相関はもはや有効でない。RIM制御線を攻撃することによって暗号化アルゴリズムを中断することによって、攻撃者が収集する対象の有用な統計的鍵情報は何らもたらされない。
【0092】
DPAは、2つの電力トレース群の和の差と、特定の時点でシステムから出力される単一目標ビットの内容との間に統計的相関が存在している場合にのみ効果的であり得る。RIMを埋め込んだこの実施例では、この統計的相関は、目標ビットがこの場合、特定の時点ではなくランダムな時点でシステムのデータ経路を出ることが理由で、もう有効でない。埋め込んだRIMの導入によって、2つの特徴のランダムなばらつきが生じる。第1の特徴は、各SPボックスのエントリ・アドレス評価において実行される命令の数/タイプにおけるばらつきである。第2の特徴は、連続したSPボックス・アクセスそれぞれの間の時間間隔におけるばらつきである。これら2つの特徴によって、プログラムにおいてアクセスされているSPボックスをDPA攻撃者が識別することができなくなってしまうことになる。これによって、SPボックスのアクセス順序の再切り混ぜが、DPA攻撃者から情報を隠すうえで効果的なやり方になる。それは、DPA攻撃者は、統計的な平均化及び解析のために同じ基準への別々の電力トレースのアラインメントを行うことがもうできなくなるからである。
【0093】
図7の実施例では、各SPボックスに関連した実シフト及び疑似シフトの合計は24シフトになる。例えば、図8中のボックスSP5の場合、8個の実シフトが、16個の疑似シフトと関連付けられる。実シフトの8個は、DESアルゴリズムによる、ボックスSP5の正しいシフト数である。線111が攻撃された場合、代わりに、ボックスSP5において、(かつ他のSPボックスにおいても)24個の実シフトが行われ、DESアルゴリズムの、いわば「混乱」が生じることになる。
【0094】
図7では、実シフト後に行われるものとして疑似シフトを示しているが、望まれる場合、実シフトの前に、又は実シフトの中に混ぜられて疑似シフトが行われることになるように順序を変更することが可能である。
【0095】
第4の実施例の詳細な説明
各SPボックスにおける合計シフト数は、24個(又は、それについて更に言えば、特定の他の数)に固定しなくてよい一方、望まれる場合、変える、又は無作為化することができる。それは、例えば、図5又は図6の設計を組み入れることによって、図7に示すCPUの設計を幾分複雑にするが、合計シフト命令数を無作為化するのに必要な修正は、図6の実施例及び図7の実施例の組み合わせとして第4の実施例を示す図9を参照することによって分かり得るように、かなり簡単である。
【0096】
第5の実施例の詳細な説明
修正RISCプロセッサ(CPU)アーキテクチャを用いて、例えば、通常の命令、及び、ランダム命令マスク(RIM)フラグによって制御される、カムフレージュされた特別な「疑似」命令に対する同一の電力署名を生成することが可能である。この特定のプロセッサ・アーキテクチャは、ランダム命令マスク(RIM)を埋め込んだチップ上暗号システムにおいて実施されることが意図されており、ソフトウェア特有のRIM概念とこのアーキテクチャとの組み合わせは、電力解析及び差分電力解析を介した海賊行為から暗号システムを保護することが意図されている。カムフラージュされた命令とは、暗号化において通常用いられるものと同じ命令コード及び同じ電力署名を有するが、この特定のプロセッサ・アーキテクチャにおいて実行する場合、如何なるプロセサ・レジスタの内容も変えず、又はプロセッサ・ステータスを変えない命令のことである。ランダム命令マスクは、電力解析又は差分電力解析によるリバース・エンジニアリングから暗号装置を保護するための、カムフラージュされた暗号化プログラムを作成する手法である。
【0097】
図10は、概括的な(単純化された)RISCプロセッサ(CPU)アーキテクチャ200である。RISC命令は、ALU(算術論理演算装置)210がレジスタ・ファイル220の2つのレジスタから2つのオペランドを得て、演算の結果をレジスタ・ファイル220の第3のレジスタにもう一度書き込むことによって行われる算術演算関数又は論理演算関数である。レジスタ・ファイル220は、アドレス選択によってアクセスすることが可能な、同じ幅(ビット数、例えば、32ビット)を備えたいくつかのレジスタから成る。各命令サイクルでは、プロセッサはROM240から順次、その命令を取得し、これを命令レジスタ245にロードする。ROM240は、暗号化アルゴリズムを含むプログラム全体の命令コード全てを記憶する。制御論理250は、命令レジスタ245における命令コードを復号化し、正しい制御コマンドをプロセッサ200のALU210や他の部分に供給する。オペランド(ソースA及びB)のアドレス、並びにデスティネーション・アドレスも命令コードにおいて規定される。アドレス復号器260は、命令レジスタ245からのアドレス情報を復号化し、レジスタ・ファイル220における特定のレジスタのアクセス制御を備える。制御論理250によって制御されるALU210は、特定されたアドレスによってレジスタ・ファイル220から2つのオペランド(ソースA及びB)を取得し、命令が規定した算術演算又は論理演算を行う。ALU演算の結果は、データ・バス215上のデスティネーション・アドレスによってレジスタ・ファイル210内の別のレジスタにもう一度書き込まれる。命令のタイプによって、プログラム全体における命令の索引参照を記憶したプログラム・カウンタ230が、命令の実行中に制御論理によって増やされるか、又は更新されることになる。プロセッサの、一部の特定の命令は、プログラム・カウンタ230を増やすことも更新することもしない。プログラム・カウンタ230と同様な、プロセッサにおける一部の他のフラグ・レジスタ(図示せず)の更新も命令に依存する。
【0098】
現代のプロセッサの大半はCMOS技術で構築されている。CMOS回路はスタティック電流を引き込まないので、電力は負荷容量の充電及び放電(スイッチング)の際にのみ放出される。CMOS回路の電流消費は主に、容量性負荷、ドライバのドライブ能力、及びスイッチングの周波数によって変わってくる。プロセッサにおいて実行される完全な命令サイクルには、別々の時点で別々の回路を動作させることが関係する。プロセッサ回路の別々の部分は、デバイス寸法、寄生負荷及びスイッチング速度における差によって、アクティブ状態にされると電力バス上で時間に対して固有の電流パターン(電力署名)を生成する。電力解析又は差分電力解析(DPA)はこれらの電力署名パターンを用いて命令を互いに関係付ける。
【0099】
埋め込みランダム命令マスク(RIM)手法を用いて、前述のように各SPボックスのエントリ・アドレス計算サブルーチンにおけるRIM命令の数をランダムに変え、そうしたRIM命令の内容もランダムに変える。RIM手法がDPA攻撃を首尾良く妨げるうえで最も重要な条件の1つは、こうしたRIM命令の電力署名を全てなくすことである。このことを行ううえで最善のやり方は、電力解析又は差分電力解析(DPA)において識別可能でないようにRIM命令の電力署名を通常の命令と同一にすることである。図11は、図10に示すRISCプロセッサ200の改良されたバージョンを示す。例えば、乱数生成器223から生成されるRIM制御フラグ202は、RIM命令をアクティブ状態にすることを制御する。乱数生成器は、第1の実施例に関して図5に表す。図11のRISCプロセッサは、デスティネーション・アドレス及びプログラム・カウンタ・インクリメント・イネーブルを制御する、図5のプロセッサと比較して追加のANDゲートを有する。追加のレジスタ222はデータ・バスに接続される。このレジスタ222は、少なくとも電力消費の視点でレジスタ・ファイル220におけるレジスタと同一であるように設計される。電力消費の点でプロセッサにおいて元のプログラム・カウンタ230を複製するために疑似プログラム・カウンタ232が存在している。RIM制御フラグ202がセットされている間、疑似プログラム・カウンタ232はROM240から命令をフェッチし、命令は命令レジスタ245に入り、通常通り、アドレス復号器260によって復号化される。しかし、命令の結果は、レジスタ・ファイル220におけるレジスタの代わりに更なるレジスタ222に送られる。
【0100】
RIM制御フラグ202が論理「0」に等しい場合、プロセッサ200は通常の動作になる(すなわち、修正されないものとして図5に表すように動作する)。当該デスティネーション・アドレス及び当該プログラム・カウンタにおいて、追加のANDゲート221、231は、アドレス復号器260及び制御論理装置250からの元の信号を通すに過ぎない。同時に、追加されたレジスタ222及び疑似プログラム・カウンタ232がディセーブルされる。命令の実行中に関係する回路構成部分は全て、図10と同じであるので、図11の修正プロセッサにおいて実行する各命令の電力署名(すなわち、時間に対する消費電流パターン)は、図10のプロセッサと同じになる。
【0101】
RIM制御フラグ202がアクティブ(論理「1」に等しい)状態にされると、命令がROM240からフェッチされ、レジスタ・ファイル220からのAオペランド及びBオペランドを復号化し、参照し、ALU210におけるオペランドの演算は通常通り、続く。しかし、RIMフラグ202の状態に対する応答性を有するANDゲート221が存在していることによって、レジスタ・ファイル220におけるデスティネーション・レジスタの選択がディセーブルされ、ALU210からの結果を受けるためにレジスタ・ファイル220において選択されるデスティネーション・レジスタは何らない。むしろ、代わりに、ANDゲート223によって、ALU210からのデータがデータ・バス215上で、追加レジスタ222に向けられることになる。その結果、ALUは、レジスタ・ファイル220における通常のデスティネーション・レジスタのうちの1つの代わりに追加レジスタ222に、実行される命令に結果をロードするよう仕向けられる。追加レジスタ222の物理的な設計はレジスタ・ファイル220内のデスティネーション・レジスタと同一であるため、この追加レジスタ222のロードの消費電流パターンは、レジスタ・ファイル220における実デスティネーション・レジスタ220に結果をロードする場合と同じになる。追加レジスタの前に配置されたANDゲート223は、通常動作中にデスティネーション・レジスタのうちの1つを選択するのに用いられる1つのANDゲート221の電力をエミュレートする目的のためである。同時に、RIMフラグ202も実プログラム・カウンタ230をディセーブルし、疑似プログラム・カウンタ232を、増やすか、又は更新するようアクティブ状態にする。この場合も又、2つのプログラム・カウンタ230、232の間の同一の物理的な設計が理由で、実行される命令によるプログラム・カウンタの増加又は更新の電力パターンが維持されることになる。前述の命令サイクルの終了時に、レジスタ・ファイル220におけるデスティネーション・レジスタ又は実プログラム・カウンタ230の内容は何ら修正されるものでない。よって、プロセッサ200のステータスはRIMフラグ202がセットされている間、この命令が実行される前と同じ状態に留まる。RIMフラグ202がセットされると、プロセッサ200は、データ処理の観点からは、NOP(ノーオペレーション)命令を処理しているかのようにふるまう。しかし、電力消費の観点からは、プロセッサは、実命令を処理しているようにみえる。
【0102】
RIMフラグ202が論理「0」に戻ると、プロセッサはこの通常動作を再開して元のプログラムの実行を続けることになる。RIMフラグが論理「1」である間に実行される命令が何であっても(種類の制約は何らない)、電力トレースにおいて関連した通常の命令を実行するというカムフラージュ作用を単にもたらす以外には、プロセッサに対してもプログラミングに対しても何の影響もない。よって、RIMフラグが論理「1」の際にフェッチされた命令が基本的には、再フェッチされる。当然、分岐命令の結果が異なり得るので、順序は変わり得る。いずれにせよ、処理は基本的には、RIMフラグが論理「1」である際に中断された位置から続行する。SPボックス・アドレス計算サブルーチンにおけるRIMフラグ制御命令を備えたこのプロセッサを用いる場合、電力トレースは、いくつかの特定の命令のランダムな変形を含み、サブルーチンにおいて実行される各種命令も含むことになる。よって、DPA攻撃者は、SPボックス・サブルーチンの電力トレースの識別及びアラインメントを行うことがもう可能でない。
【0103】
データを受信し、記憶するという点で追加レジスタ222はダミー・レジスタであるが、それによって受信されるデータは、プロセッサ200による後のデータ処理に影響を及ぼすのに用いないことが好ましい。図11では、レジスタ・ファイル220から分離されて示しているが、望まれる場合、レジスタ・ファイル220の一部として実施することが可能である。
【0104】
チップ上のRIM制御フラグ202の出力でのRIM制御線を直接探査から保護することは重要である。RIM制御線が容易にアクセスされる場合、精通した一部の攻撃者は、この手法を用いて、RIMをディセーブルするように常に論理「0」にRIM制御線を強制的にすることができる。CMOS回路の物理的な設計をリバース・エンジニアリングから保護するためのカムフラージュ手法は、利用可能なものとしていくつか存在している。こうした手法を用いれば、シリコン・インプラント・レベルに深く埋め、アクティブ状態で接続された高位のポリシリコン・レイヤ及び金属レイヤによって遮蔽することによって、RIM制御線の探査を非常に困難にすることが可能である。このRIM制御線を見つけることは非常に困難になり、高位保護レイヤを何らかのやり方で除去しようとしても、チップの機能を損なうことになる。
【0105】
RIMフラグ202の状態は、疑似プログラム・カウンタ232を用いて命令をフェッチする場合、論理「1」にあるものとする。当業者に周知のように、図11に示すこの論理は、論理「0」によって疑似プログラム・カウンタ232が起動されるようになり、論理「1」が通常のCPU動作を表すように容易に修正することができる。
【0106】
図11に示す回路は、パイプライン型ALUを意図するものでない。しかし、図11の回路をパイプライン型ALUに適合させることは簡単である。一般に、パイプライン型ALUは4つの段(プリフェッチ、命令復号化、実行、再書き込み)を有する。RIMフラグからのRIM制御信号を、遅延回路によってパイプラインと同期化することができる。よって、RIM制御フラグ202は、パイプライン型ALUに用いる場合、追加レジスタ222、ANDゲート221及び疑似プログラム・カウンタ232と同期化するものとする。
【0107】
当然、プロセッサ200は、RIMモードで実行する場合に更新しないものとする更なるステータス・フラグ・レジスタを有し得る。前述のレジスタの制御は、レジスタと同様に((RIMモードにある場合に、結果を書き込むための)ダミー・フラグ・レジスタ(追加レジスタ222に相当する)を備えることによって)修正することができる。これによって、こうしたフラグ・レジスタを更新するための複製電力署名構成部分がもたらされる。こうしたフラグ・レジスタは、簡単にする目的のために、図11に表していない。
【0108】
プロセッサ内では、容量負荷が高く、速度が速いことは、データ・バスのスイッチングと、レジスタ・ファイル(メモリ)の読み書きが電力消費を支配することになることを意味する。フラグ・レジスタ(通常、単一ビット・レジスタ)の更新のスイッチング電力は、総電力と比較して大きいものでない。プログラム・カウンタのスイッチング電力でも、電力トレースにおいて観測可能な差をもたらすのに十分大きいものでない場合がある。こうしたフラグ・レジスタをそのままにしておくことは、所要の追加回路を削減するうえで好都合なやり方であり得る。
【0109】
バス・アーキテクチャ実施例の詳細な説明
この実施例は、「0」値を有する確率と「1」値を有する確率が等しくなるように維持する一方で、データ・バス・ドライバでの目標ビットの極性をランダムに切り換えることにより、DPA攻撃者による、設計者が予想しなかった情報の使用を妨げるものである。すなわち、電力トレースにはもう、秘密鍵との統計的な相関はない。よって、暗号システムによって用いられる鍵を明らかにするうえで、設計者が予想しなかった情報を用いることが可能でない。この実施例は、他の実施例とともに用いることができ、又は単独で用いることができる。
【0110】
特に、DPAに関して言えば、正しく推測された鍵Kによって選択関数から計算される同じ目標ビット値を有する各メッセージ群内で、対応する電力トレースが常に「0」で有るわけでも常に「1」である訳でもないという結果になる。目標ビットで「0」を有する可能性も「1」を有する可能性も、極性の無作為化によって約0.5になる。よって、選択関数Dは事実上、実際の電力トレース測定と互いに関係付けることが可能でない。選択関数Dは、実際の目標ビットの電力消費を予測する方法を奪われてしまっている。Kが誤って推測された場合、無作為化によって、Dと、対応する電力トレースとの無相関が維持されることになる。
【0111】
図12は、本発明による暗号バス・アーキテクチャ311(CBA)を表す。暗号バス・アーキテクチャは好ましくは、双方向ドライバ315、317を両端に有し、負荷が通常高いバス316をそれらの間に有する。非双方向ドライバを用いることによって、本発明を実施するのに必要なバス・ドライバ数が増える傾向にあるので、双方向ドライバが好ましい。バス311はCPU301をそのメモリ321、323に接続する。CPU301はROM321に記憶されたプログラムを実行し、RAM323は、暗号文データ及び鍵を中間的に記憶するためのものである。
【0112】
Nビットの乱数生成器313は、Nビット双方向ドライバ315、317を制御する。乱数生成器313はN個の出力314を有し、各出力は1ビットから成る。各ビット314乃至314は、1つのバス・ドライバ315、317を制御する。乱数生成器313は、「アクティブ状態にする信号」がCPU301からイネーブル線303を介して受信される都度、新たな、Nビット乱数314乃至314の組を生成する。アクティブ状態にする信号は、好ましくは、各DESラウンドの最初にCPU301によって送出され、好ましくは、ソフトウェアによって引き起こされる。各ランダム・ビット314乃至314の値は、ドライバ315、317を切り替える(すなわち、その極性を切り替える)やり方を明らかにし、高負荷内部データ・バス316を駆動させて相関を打ち負かすのに用いられる。極性制御線313は、「耐探査」にされることが好ましいが、それは、リバース・エンジニアに容易に分かる回路特徴の下に埋め込むのが好ましいからである。すなわち、この制御線は、(それぞれの内容を本明細書及び特許請求の範囲に援用する)米国特許第5,866,933号明細書、米国特許第6,294,816号明細書又は米国特許第6,613,661号明細書に記載の手法を用いて、基板内のインプラント・レイヤによって作製することが可能であり、よって、酸化物、ポリシリコン及び/又は金属の下に埋められており、それによって、制御線に接続する可能性がずっと難しい命題になる。所要の、極性の切り替えは、リバース・エンジニアによる統計解析を妨害するうえで十分、頻度が低い。例えば、極性は、各DESラウンドの最初に、又は、暗号化のための新たな平分それぞれのフェッチの最初に切り替えることが可能である。
【0113】
図13は、好ましい実施例のより詳細な構成図を表す。「CPU 読み取り」線401乃至401及び「CPU 書き込み」線403乃至403を用いてデータ・フロー方向を制御する。双方向バス・ドライバ315、317は、乱数生成器313によって生成される乱数の関連ランダム・ビット314乃至314の値によって定められる反転型又は非反転型のトライステート・バッファである。例えば、ランダム・ビット314が、「CPU書き込み」動作中の双方向バス・ドライバ315に対して「0」の場合、305上の信号がデータ・バス316上で反転されることになる。他方端では、双方向バス・ドライバ317は、ビット305に対する、データ・バス316からの反転信号を受信し、ビットをもう一度反転させて、元のデータ信号のインテグリティを保証することになる。このことは、データ信号105のビット毎に行われる(通常、一部のビットが反転され、他のビットは反転されない)。ビット314がランダムな「1」の場合、反転型バッファ320の代わりに非反転型バッファ319がデータ・バス316を駆動させることになる。信号314乃至314はランダムなため、「0」の値を有する可能性及び「1」の値を有する可能性は約0.5及び0.5である。その結果、データ・バスの内容に関連した決定性電力情報が全て失われることになる。よって、正しく推測された鍵を有するDPA攻撃の場合にも、データ・バス上の目標ビットの内容と、対応する電力トレースとの間の内報(tip−off)相関が失われる。
【0114】
データ・バス316(プロセッサの設計において高容量負荷を有する傾向にある)の論理内容が、電力トレース測定と互いに関係付けることが可能でないようにされた後、残っている相関は、ALUとレジスタ・ファイルとを接続する低負荷容量配線からのものであり得る。この相関の検出を最小にするために、好ましくは、デュアル・レール(d及びd_bar)の組を用いて、図14に示すように特定のレジスタ・ビットを書き込む。この設計の対称性が理由で、デュアル・レールは、新たなデータ「d」及びその補数「d_bar」を同時に含み、よって、「d」及び「d_bar」の平均化の結果、0.5に正規化する対象の外部電力消費をマスクする。相補型読み取り増幅器及び相補型書き込み増幅器が存在していることが分かる。特に、データ値Dが「0」の場合、デュアル・レール組は「0,1」を含む。データ値Dが「1」の場合、デュアル・レール組のデータ値は「1,0」である。よって、データ値Dとは無関係に、この回路(レールd及びd_bar、並びに、相補型読み取り増幅器及び相補型書き込み増幅器を含む)は、同じ平均電力消費を常に有することになり、よって、データ値Dと回路の電力消費とを互いに関係付けることを不可能にしてしまうことになる。図14の回路のデータ値Dは「0」の値又は「1」の値を有し得るが、何れの場合も、d及びd_barの一方は「0」に等しくなり、d及びd_barの他方は「1」に等しくなり、それらの平均は当然、0.5に等しくなる。その結果、回路の電力署名は、ALUレジスタ・ビットのデータ値の内容とは無関係になる。当然、特定のレジスタは複数ビットを有し、各記憶ビットは好ましくは、図14による設計によって構成される。
【0115】
本発明は好ましくは、暗号処理を行うのに用いられる、マイクロプロセッサのチップ上のバス及び/又はチップ・アーキテクチャにおいて実施される。このアーキテクチャ手法によって、既存の暗号アルゴリズム(RSA、DES、AES及び非線形アルゴリズムを含む)を安全にすることが可能になる。
【0116】
本明細書記載の手法をその別々の実施例に関して説明したが、当業者にはその修正が分かるものである。そういうものとして、特許請求の範囲記載の本発明は、特許請求の範囲によって特に必要とされる以外には、本明細書記載の実施例に限定されないものとする。
【0117】
【表1】

表1。 C言語で表しており、例えば、SPボックス1及び2が、64個のエレメントのルックアップ・テーブルとして実施されている。
【0118】
【表2】

表2。特定のラウンドのDESの8つのSPルックアップ・テーブルの順次アクセスを行うC言語プログラム。
【0119】
【表3】

表3。表2のCプログラム文番号5を実施するための対応アセンブラ言語プログラム。なお、「;」に始まる行はコメント行である。
【0120】
【表4】


表4。
【0121】
【表5】

表5。図7の実施例について、表2のCプログラム文番号5を実施するための対応アセンブラ言語プログラム。なお、「;」に始まる行はコメント行である。
【符号の説明】
【0122】
101 CPU
103 RAM
105 ROM
113 制御フラグ・レジスタ
115 乱数生成器

【特許請求の範囲】
【請求項1】
暗号アーキテクチャであって、
プロセッサと、
該プロセッサに結合された暗号化アルゴリズムを含むメモリと、
前記プロセッサに結合され、前記プロセッサの状態動作を制御する制御フラグ・レジスタ及びシフト制御カウンタであって、前記シフト制御カウンタが前記暗号化アルゴリズムを行うために所望の実シフト命令の数をカウントするよう適合された制御フラグ・レジスタ及びシフト制御カウンタと、
前記制御フラグ・レジスタに結合された乱数生成器とを備え、
前記制御フラグ・レジスタは、前記メモリに記憶され、前記プロセッサによって出される命令によってセットされ、前記制御フラグ・レジスタがセットされている場合に擬似シフト命令が前記プロセッサによって行われ、
ランダムな数の擬似シフト命令が行われた場合に前記制御フラグ・レジスタが前記乱数生成器によってリセットされ、
前記擬似シフト命令は、前記暗号化アルゴリズムに応じて行われる算出に影響を及ぼすことなくエネルギ消費において前記暗号化アルゴリズムの実シフト命令をまね、
前記暗号化アルゴリズムは複数の換字/転置シーケンスを有し、前記擬似シフト命令が前記換字/転置シーケンスの1つ又は複数に挿入され、
前記所望のシフト命令及び前記擬似シフト命令は複数の群において行われ、シフト命令の群はそれぞれ、固定数のシフト命令を含み、各群における擬似シフト命令の数は群毎に変動し、かつ/又は、
少なくとも1つの群は全て、擬似シフト命令を備え、別の少なくとも1つの群は全て、実シフト命令を備え、かつ/又は、
前記所望のシフト命令及び前記擬似シフト命令は複数の群において行われ、命令の群はそれぞれ、固定数のシフト命令を含み、各群における擬似シフト命令の数は群毎に変動し、かつ/又は、
少なくとも1つの群は全て、擬似シフト命令を備え、別の少なくとも1つの群は全て、実シフト命令を備えることを特徴とする暗号アーキテクチャ。
【請求項2】
請求項1記載の暗号ア―キテクチャであって、前記制御フラグ・レジスタ及びシフト制御レジスタは、ゲート対によって相互接続され、前記ゲート対の第1のゲートは、前記ゲート対の第2のゲートの第1の入力に結合された出力を有し、前記第1のゲートは、その一入力を前記制御フラグ・レジスタの出力に結合させており、その別の入力を前記第2のゲートの出力に結合させており、前記第2のゲートは、前記シフト制御カウンタに結合された別の入力を有し、前記第2のゲートの前記出力も、前記プロセッサに結合され、前記プロセッサの状態動作を停止することを特徴とする暗号アーキテクチャ。
【請求項3】
請求項1記載の暗号ア―キテクチャであって、
前記プロセッサは、16ビットのプロセッサ、32ビットのプロセッサ、又は64ビットのプロセッサであり、かつ/又は、
前記暗号化アルゴリズムがデータ暗号化規格(DES)アルゴリズムであることを特徴とする暗号アーキテクチャ。
【請求項4】
請求項1記載の暗号アーキテクチャであって、
前記擬似シフト命令は、電力消費の点で実シフト命令をビット単位でエミュレートすることを特徴とする暗号アーキテクチャ。
【請求項5】
請求項1記載の暗号アーキテクチャであって、
前記制御フラグ・レジスタに結合された乱数生成器を更に備え、
前記乱数生成器は1ビット乱数生成器であることを特徴とする暗号アーキテクチャ。
【請求項6】
サイド・チャネル電力トレースが秘密鍵と統計的に相関しないようにサイド・チャネル情報を無相関化するシステムであって、
データ暗号化規格(DES)アルゴリズムを実行する手段であって、前記DESアルゴリズムが、複数の換字/転置ボックスのエントリ・アドレスの評価を備える手段と、
固定数又はランダムな数の擬似命令を、前記複数の換字/転置ボックスのエントリ・アドレスの評価のうちの少なくとも1つに挿入する手段であって、前記擬似命令は、前記DESアルゴリズムの前記実行に影響を及ぼすことなく、実命令をエネルギ消費においてまねる手段とを備え、
前記挿入する手段は、前記プロセッサに結合され、少なくとも、前記プロセッサに関連したレジスタを更新する対応実命令ではなく、前記プロセッサに関連付けられたレジスタを更新しない擬似命令を前記プロセッサに出させる制御フラグ・レジスタを含み、かつ/又は、
前記挿入する手段は、前記制御フラグ・レジスタと前記プロセッサとの間の接続が攻撃者によって首尾良く探査された場合に更なる実命令を前記DESアルゴリズムに挿入するシフト制御カウンタを更に含み、前記挿入された更なる実命令は、前記DESアルゴリズムによって行われる算出をディセーブルするうえで効果的であることを特徴とするシステム。
【請求項7】
請求項6記載のシステムであって、
前記挿入する手段は前記制御フラグ・レジスタに結合された乱数生成器を更に含み、かつ/又は、
前記乱数生成器は1ビット乱数生成器であることを特徴とするシステム。
【請求項8】
請求項6記載のシステムであって、前記DESアルゴリズムを実行する手段は、
プロセッサと、
該プロセッサに結合された暗号化アルゴリズムを含むメモリと、
前記プロセッサに結合された複数のルックアップ・テーブルと
を含み、前記複数の換字/転置ボックスは前記複数のルックアップ・テーブルにおいて実施され、
前記プロセッサが、16ビットのプロセッサ、32ビットのプロセッサ、又は64ビットのプロセッサであることを特徴とするシステム。
【請求項9】
プロセッサを有する暗号アーキテクチャの電力トレースを変える方法であって、
前記方法は、
前記プロセッサ上で暗号化アルゴリズムを前記プロセッサによって実行する工程と、
前記暗号化アルゴリズムにおける制御フラグ命令により、制御フラグを前記プロセッサによってセットする工程と、
前記制御フラグがセットされている場合に、前記アルゴリズムの更なる命令の評価を前記プロセッサによって抑制し、その代わりに、ランダムな数の擬似命令を前記プロセッサによって行う工程と、
前記ランダムな数の疑似命令が行われた場合に前記制御フラグを前記プロセッサによってリセットする工程とを備え、
前記擬似シフト命令は、前記暗号化アルゴリズムに応じて行われる算出に影響を及ぼすことなくエネルギ消費において前記暗号化アルゴリズムの実命令をまね、
前記制御フラグをセットする工程は、前記暗号化アルゴリズムを実行するプロセッサの状態マシンを停止する工程を更に備え、前記状態マシンを停止する工程は、前記状態マシンにおけるデスティネーション・レジスタをディセーブルする工程を更に備え、かつ/又は、
複数のルックアップ・テーブルのアクセス順序を切り混ぜるよう前記暗号化アルゴリズムを修正する工程を更に備え、かつ/又は、
前記暗号化アルゴリズムがデータ暗号化規格(DES)アルゴリズムであり、かつ/又は、
前記制御フラグをリセットする工程を更に備え、前記リセットする工程は、乱数生成器から制御フラグ・レジスタに信号を送出する工程を更に備えることを特徴とする方法。

【図1】
image rotate

【図2a】
image rotate

【図2b】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate


【公開番号】特開2012−95345(P2012−95345A)
【公開日】平成24年5月17日(2012.5.17)
【国際特許分類】
【出願番号】特願2011−284585(P2011−284585)
【出願日】平成23年12月27日(2011.12.27)
【分割の表示】特願2007−527677(P2007−527677)の分割
【原出願日】平成17年6月7日(2005.6.7)
【出願人】(501411651)エイチアールエル ラボラトリーズ,エルエルシー (19)
【氏名又は名称原語表記】HRL LABORATORIES, LLC
【住所又は居所原語表記】3011 Malibu Canyon Road, Malibu, CA 90265−4799, United States of America
【Fターム(参考)】