説明

処理装置に対する特異な電力攻撃を最小限にする方法および装置

【課題】処理装置に対して電力分析攻撃を最小限にする方法を提供する。
【解決手段】暗号処理装置における条件付き分岐処理の遮断方法であって、プログラム実行は、基準値に対応する識別値Vの第1あるいは第2の命令に依存する2つの分岐のうちの一方へ分岐し、その基準は、上限Vmaxと下限Vminによって限度内に留められる。その方法は、条件付きの分岐の位置を決定するステップと、目標アドレスを計算するために上記識別値と基本アドレスとを使用することによって、プログラム実行を2つの分岐の一方のそれぞれに変更する命令を実行するために、そこにコードを挿入するステップであって、異なる数の命令が実行される上記命令の各評価のために特異な電力攻撃の効果を最小限にするステップとを備えている。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、暗号システム、特に、処理装置に対する有効な電力分析攻撃(succe
ssful poweranalysis attacks) を最小限にするための方法および装置に関する
ものである。
【背景技術】
【0002】
[発明の背景]
暗号システムは、一般的に、その仕組みを壊すことが不可能である場合を除い
て、その安全性が保たれるのは、情報の細かい部分が秘密に保たれているという
事実のおかげである。この秘密情報は、一般的に、安全な境界内で屈するに違い
ないが、秘密情報を得るために企てられた様々な組立や攻撃で、攻撃者が直接的
にそこへ達することを難しくしている。スマートカード(smart card)等を含む手
軽な暗号トークン(token)は、特別なリスクである。単純な電力分析、特異な電
力分析、より高いオーダーの特異な電力分析や、他の関連技術は、これらの特異
な弱点(vulnerable)を有するデバイスに対して行われたより最近の攻撃である。
これらの技術的に進歩した、非常に強大な分析ツールは、暗号デバイスから秘密
鍵を導くために、攻撃者によって使用される。これらの攻撃は、素早く開始でき
、有効なハードウェアをたやすく使用できることが知られている。これらの攻撃
に必要な時間の量は、デバイスによる攻撃や様々な何かのタイプに依存している
。例えば、特異な電力攻撃(DPA) は数時間かかるが、単純な電力攻撃(SPA) は、
典型的な場合でカード当たり数秒かかることが知られている。
暗号化処理は、基本的な処理を連続することで結果として起きる処理装置の処
理で行われ、その各々が別個のタイミングパターンを生成する。気をつかう以外
に面倒な端から端までの電力波形(end-to-end power waveforms)の分析は、秘密
鍵のそれぞれのビットで行われ、こうして秘密鍵全体(entire secret key) を探
すために分析され、そのシステムに含まれるこれらの基本的な処理の順番を分解
する(decompose)ことができる。
【0003】
スマートカードと他の安全なトークンに対する単純な電力分析(SPA) 攻撃では
、時間に変換されるトークンの消費電力を攻撃者が直接測定する。消費された電
力量は、実行されたマイクロプロセッサの命令に応じて変化する。マイクロプロ
セッサで行われた処理は、これらの処理の異なる部分の間に意味ありげに(signi
ficantly) 変化するので、ループやDESラウンド等における楕円カーブ(EC)加法
のような大きな計算は、おそらく立証されている。より高度な割合、すなわち、
より高度な分解で電流と電圧とをサンプリングすることで、個々の命令が差別化
される。
【0004】
差別化された電力分析攻撃(DPA) は、SPA よりも力強い攻撃であり、防ぐこと
がずっと難しい。第1に、DPA は、秘密鍵に対応するであろう情報を抽出するた
めに、統計的な分析とエラー訂正技術とを使用し、一方、SPA 攻撃は、関連する
電力の変動を立証するために、先ず視覚的な診断(visual inspection) を使用す
る。DPA 攻撃は、2段階で行われる。最初の段階では、暗号化ルーチンの実行の
間に、カードによって消費された電力への変換を示すデータを記憶する。第2段
階では、その選ばれたデータが、秘密鍵に関連する特別な情報を抽出するために
、統計的に分析される。これらの情報の詳しい分析は、ポール・コーチャーらに
よって、文献名「Introductionto Differential Power Analysis and Related
Attacks (特異な電力分析と関連する攻撃への導入)」に開示されている。
【0005】
これらの電力攻撃に対処するための様々な技術が、現在まで企てられている。
これらは、十分に濾過された電力供給や処理装置の部品の物理的な保護を提供す
るハードウェアの解決策を含んでいる。しかしながら、スマートカードや安全ト
ークンの場合には、これは実行できない。DPA の弱さ(vulnerabilities) は、ト
ランジスタや論理回路を露出することを伝える電気的な動作回路、マイクロプロ
セッサの動作、最終的にソフトウェアインプリメンテイション(software implem
entations)に起因している。
【0006】
暗号化ルーチンのソフトウェアインプリメンテイションでは、特に、スマート
カードに対して、プログラムフローにおける分岐は、電力分析測定に対して特に
弱い。一般的に、プログラムフローが分岐に至った場所では、その時、いくつか
の識別値Vに基づいて、プログラムの2つの分岐のうちの一方が実行される。二
つの起こりうるケースの間を区別するために、Vが閾値と比較され、比較の結果
として2ヵ所のうちの一方への分岐が実行される。これは、一般的に10で示さ
れた従来技術による、典型的な条件付き分岐の実行を示すフロー図である、図1
に示されている。一般的に、条件付き分岐は、「IF命令、それから命令1その以
外命令2」節を実行する。この場合には、フロー図は、識別値Vが範囲内で変化
し、コンディションが閾値THが識別値Vによって交差するか否かのどちらかで
あるシナリオを示している。閾値THは、上限下限をそれぞれ示すVMAXとV
MINの間のランダムな数である。こうして、図1に示すように、V<THであ
れば、プログラムは命令1を実行し、V≧THであれば、プログラムは命令2を
実行する。これは、VMAXからVMINの全てのVの値を繰り返していてもよ
い。
【0007】
単純な電力分析技術を利用することによってより早期に外形化されると、観察
者が「IF」分岐と「ELSE」分岐の何れが実行されたかを区別することができる。
これは、しかしながら、命令1と命令2とが、異なる目的の命令の2つの同じセ
ットからなる。スマートカードに関する電力あるいは電流消費測定は、どちらの
分岐が選ばれたかを明らかにすることができる。いくつかのケースでは、チップ
上のステイタスフラグ(status flags)がセットされたりリセットされたりしても
よい。これらのフラグは、SPA のために使用されてもよい。
【0008】
従って、システムにとって、成功する電力分析攻撃のリスクを減らすことが必
要であり、特に、電流ハードウェア環境設定(current hardware environments)
に適用できる。
【発明の概要】
【発明が解決しようとする課題】
【0009】
[発明の要約]
本発明の目的は、処理装置に対して電力分析攻撃(power analysis attacks)を
最小限にするための方法を提供することにある。
【課題を解決するための手段】
【0010】
この発明は、処理装置における条件付きの分岐処理を遮断する方法であって、
プログラム実行は、基準値に対応する識別値Vの第1あるいは第2の命令に依存
する2つの分岐(branch)の一方へ分岐し(jump)、その基準は、上限Vmaxと下限
minによって限度内に留められ(bounded) 、
条件付きの分岐の位置を決定するステップと、
目標アドレスを計算するために上記識別値と基本アドレスとを使用することに
よって、プログラム実行(program execution) を2つの分岐(branches)の一方の
それぞれに変更する命令を実行するために、そこにコードを挿入するステップで
あって、異なる数の(adifferent number of) 命令が実行される上記命令の各評
価のために特異な電力攻撃の効果を最小限にするステップとを備えている。
より具体的には、識別値がランダム値に組み合わせられ、その結果、各命令の
実行にランダムな数の命令を加えている。
例えば、本発明は以下の項目を提供する。
(項目1)
連続した命令を実行するためにプログラム化された、暗号化処理装置における
条件付き分岐処理を遮断する方法であって、上記条件付き分岐処理は、基準値に
対して識別値Vを評価することによって決定され、上記基準値は、上限値VMA
Xと下限値VMINとにより限度内におさめられ、
(a)プログラム内の条件付き分岐の位置を決定するステップと、
(b)目標アドレスによって特定された2つの分岐の一方に対して、プログラ
ム実行を変更するために上記位置で処理装置命令を挿入するステップであって、
上記目標アドレスは、上記識別値および基本アドレスから導かれ、上記基準値に
対する上記識別値の各評価のために、異なる数の命令がそれぞれの条件付き分岐
処理のために実行されるステップとを含んでいる方法。
(項目2)
上記識別値が、ランダムな値と組み合わせられており、その結果、条件付きの
評価毎にランダムな数の命令を加えることを特徴とする項目1に記載の方法。
(項目3)
上記挿入された命令は、それぞれのサブルーチンの呼出しを含んでおり、上記
サブルーチンは、上記2つの分岐の一方へサブルーチンのリターンアドレスを変
換する命令を含んでいる項目1に記載の方法。
(項目4)
上記目標アドレスは、識別値Vとランダムな数とを含んでいる項目1に記載
の方法。
(項目5)
上記目標アドレスは、上記処理装置の拡張されたアドレスモードを使用して計
算される項目4に記載の方法。
【図面の簡単な説明】
【0011】
【図1】条件付き処理の計画図である。
【図2】本発明の一実施形態に係るコンピュータプログラムの一部である。
【図3】本発明の他の実施形態に係るコンピュータプログラムの一部である。
【図4】本発明のさらに他の実施形態に係るコンピュータプログラムの一部である。
【図5】本発明のもう一つの実施形態を示すフロー図である。
【発明を実施するための形態】
【0012】
[好ましい実施の形態の詳細な説明]
図2に示すように、本発明の実施形態による、コンピュータプログラムにおけ
る条件付き分岐コンディション(conditional jump condition)を遮断する(maski
ng) 方法の概略図は、符号50により一般的に示される。本発明者らは、続くコ
ードフラグメント(codefragment) は、プロセッサにより実行され、識別値Vが
公知の範囲内で変化し、そして、このコンディションは、閾値THが識別値Vで
交差するか否かのどちらかである。この閾値は、上限値および下限値がそれぞれ
VMAXおよびVMINである公知の範囲におけるランダムな番号である。一般
的な実施形態において、本方法は、条件付きの分岐処理についてのロケーション
(location)を同定し、コール52のロケーションでサブルーチン54に挿入する
。サブルーチン54は、2つのプログラム分岐(branch)の一方へサブルーチンの
リターンアドレスを変更するための命令を含み、識別値Vの閾値について比較の
結果に対する応答において、分岐ステートメント(statement) 1または分岐ステ
ートメント2を実行する。
【0013】
図2に示すように、交換された条件付き分岐のロケーションは、コードブロッ
クaによって同定される。サブルーチンは、IRRITATE_1 (54)として同定さ
れ、a,b,c,dおよびeとして同定されるコードブロックを含む。コードブ
ロックcは、第1および第2セクション、それぞれ56および58を含む。第2
セクション58のスタートアドレスは、予め決定され、値KNOWN _DISPLACEMENT
によって同定される。その後、第1セクション56のスタートアドレスは、KNOW
N _DISPLACEMENTと識別値Vの上限値との間の差によって決定される。第1セク
ション56は、アドレスL1への一連の条件無し(unconditional) 分岐からなり
、そして第2セクション58は、アドレスL2への一連の条件無し分岐からなる
。ロケーションL1およびL2は、それぞれステートメント1およびステートメ
ント2を実行するために復帰プログラムフローに対するコードを含む。サブルー
チンIRRITATE_1に含まれるコードブロックbは、KNOWN _DISPLACEMENTアドレ
スとTHRESHOLDとの間の差を計算するためのコードを含む。次いで、得られたア
ドレスは、セクション56および58のうちの一方における目標アドレスロケー
ションを引き出すために識別値Vを加える。
【0014】
ブロックaに示すように、識別値Vは、サブルーチンを呼び出す間中保存され
、次には如何なる条件付き分岐も含まない。このサブルーチンにおいて、本発明
者らは、Vがサブルーチンから復帰後のこのようなTH以下か以上かに依存して
、サブルーチン(これはスタック(stack) に属する)のリターンアドレスを変換
し、プログラムが決定された分岐における実行を続ける。
【0015】
拡張してアドレスすることが知られるアドレスモードは、目標アドレスを決定
するために使用される。拡張してアドレスをアドレスすることは、続けなければ
ならないプログラムの実行が、2つの登録(register)の内容の合計として計算さ
れるアドレスである。例えば、Intel (登録商標)8051ファミリーの集合言語(a
ssemblylanguage) におけるJMP @A+DPTRは、続けられなければならないプログ
ラム実行が、アキュミュレータ(accumulator)AおよびデータポインタDPTRの内容
を加えることにより計算されるアドレスを意味する。他のプロセッサは、アドレ
スするための同様の機構を指示することができる。図2に示されるコードフラグ
メントは、方法を例示する。これらのコードフラグメントのラインを参照すると
、本発明者らは、レター(letter)および番号からなるラベルを使用する。従って
、この方法における要件は、本発明者が明確にすべきである:
a)コード56のブロックが属しているアドレス。これは、第1JMP L1のアドレ
スである;
b)識別値Vの範囲;
c)ランダムな閾値THの最大値。この最大値またはそれから誘導される値は、
JMP L1またはJMP L2を含むコードブロックの大きさを定義する。
【0016】
図2に示されるコードフラグメントの処理は、以下で議論する。コードフラグ
メントは、ループ内に位置され、これは、連続的にループの反復に対する与えら
れた範囲におけるVの値を変換する。例えば、Vは、ループカウンタの値である
。ゴールは、V<THRESHOLDである限り、ラベルDO_REAL、ラインd1で実行し続け
ることであり、V>=THRESHOLDに対してラベルDO_VOID、ラインe1で命令の実行を
続けることである。
【0017】
前で述べたように、THRESHOLDは、Vmin およびVmax の公知の範囲内のラン
ダムな値である。ラインa1では、識別値Vは、プロセッサのアキュミュレーター
に保存され、サブルーチンIRRITARE_1 は、ラインa2で呼び出される。このサブ
ルーチンからのリターンアドレスは、ラインa3であり、これは、プロセッサによ
って自動的にスタックに保存される。
【0018】
ラインb1におけるKNOWN_DISPLACEMENTは、第2セクション58の始めるロケ
ーションを特定する一定の値であり、ラインc9のアドレスを示す。従って、KNOW
N _DISPLACEMENT-Vmaxは、ラインc1のアドレスであり、第1セクション56の
始まる位置である。
【0019】
ブロックbにおけるKNOWN _DISPLACEMENTの値は、ラインb1での登録におい
て保存される。次のラインb2では、登録は、KNOWN-DISPLACEMENTおよびTHRESH
OLD の差を用いてアップデートされる。この差は、ラインb3でのDPTRにおいて
移動される。したがって、DPTRはブロックcにおけるc8を通ってラインc1の
一つのアドレスに含まれる。例えば、THRESHOLD=3 DPTRは、ラインc6に向けられ
る。次がVであると仮定し、アキュミュレーターの内容は、0(Vmin )から7
(Vmax)で変化することができる。ついで、DPTRは、c1からc8までのアドレス
を変化するので、ラインb4で計算されるアドレス@A+DPTRは、Vが0から7で変
化するにつれて、ラインc6のアドレスからc12 を変化することができる。従って
、V<3 に対して第1セクションにおけるJMPL1命令を実行し、V>=3 に対して第
2セクションにおけるJMP L2命令を実行する。
【0020】
ラベルL1およびL2は、それぞれラインc17およびc21に位置されるリターンア
ドレスに向けられる。ラインc17 からc19において、サブルーチンIRRITATE_1
のリターンアドレスはまた、回復または変換されるので、プログラムカウンター
が、サブルーチンが復帰した後にラインa4に向けられる。単純な分岐は、ライン
a3およびa4での命令である。
【0021】
行われる2 つの分岐間の実際の識別は、ブロックaにおける適切なラインに回
復されたサブルーチンリターンアドレスを変換したラインc18 とc22 で決定され
ることに注意すべきである。本実施形態において0 と1 の値は、再分配分岐(red
irection jump)がラインa3とa4のそれぞれでのサブルーチンIRRITATE_1への呼
び出し命令後、すぐに位置されるので、選択される。他の命令において、それら
のバイナリー表示(binarypesentation)における1's の等しい番号を有する異な
る値が使用されるので、ラインc18 およびc22Dでの加算処理における差は攻撃者
(attacker)に識別されることができる。この場合、NOPのおよその番号は、リタ
ーンアドレスを調整するためにコードブロックに加算される。
【0022】
さらに、リダイレクトプログラムが命令1および命令2にそれぞれ流れるライ
ンa3,a4での分岐命令は、バイナリー表現(binaryrepresentation )で同じ番
号の1をもつアドレスに置かれるべきである。これは、これらの二つの異なる場
所をアドレス指定する間に、アドレスバス(address bus )における均一な電力
消費という結果になる。同じ対策は、ラインd1とe1と、命令1および命令2の位
置とでそれぞれ応用される。さらに、ラインb2において、特別な注意は、SUB 命
令が実行される間に、処理装置のステータスワード(status word )内のフラグ
における変化を避けるために、THRESHOLD とKNOWN _DISPLACEMENTとの値の選択
に払われるべきである。
【0023】
本発明の第2の実施形態は、図3に示すように、符号100によって概して示
されている。本実施形態も、上述のように、拡張したアドレシングを利用してい
る。処理装置のIntel8051ファミリーの集合言語は、もう一度、その方法を証明
することに使用される。明確にするために(for clarity) 、op1 からop7 のしる
し(symbol)は、プログラムの命令を表すために使用される。この実施形態では
、識別値Vは、二つの明確な値Vmax とVmin の一方である。こうして、この場
合の条件は、識別値Vが明確な値であるVmax あるいはVmin のいずれか一方で
あることである。再度のサブルーチンの呼出し(call)は、条件付き分岐の位置
に挿入され、サブルーチンは、明確な値のVmax あるいはVmin の一方である識
別値Vに応じて、分岐命令1あるいは分岐命令2を実行するために、サブルーチ
ンのリターンアドレスを二つのプログラム分岐の一方に変換するための命令を含
んでいる。
【0024】
図3に示しているように、再配置された条件付きの分岐の位置は、コードブロ
ックf によって明らかにされる。サブルーチンは、IRRITATE_2(102)として認識
され、ブロックg とhとして認識されたコードブロックを含んでいる。コードブ
ロックh は、第1および第2のセクション106および108もそれぞれ含んで
いる。各セクションは、h1からh7のラインとh12 からh18 のラインとで表示され
たダミー処理op1の系列を含んでいる。各セクションは、サブルーチンIRRITATE
_2 のリターンアドレスを修復し、サブルーチンから戻った後で、プログラムカ
ウンターがラインf4あるいはf5を示すようにそれを変換するための連続した命令
によって終了される。ラインf4と二つの分岐のうちの一方への分岐を含んでいる
f4は、命令1および命令2をそれぞれ含むブロックiおよびブロックj として示
される。
【0025】
目標とする目的地アドレスは、二つの要素、すなわち、識別値VあるいはVか
ら導かれる値と、ラインg1で加算されるランダムな数(random number )MASKED
_RANDOMと比較される。最初と2番目のセクションの開始アドレスは、この目標
アドレスが、ラインh1からh8、あるいはラインh12からh19 の範囲のどちらかで
あるように選ばれる。目標アドレスの第2の要素は、ランダムな数であり、サブ
ルーチンIRRITATE_2のリターンアドレスがラインh8からh10 (あるいは、ライ
ンh19 からh21)において計算される前に、ランダムな数のダミー処理が実行さ
れる。
【0026】
上記実施例では、ラインh9からラインh20 におけるADD 値が、ブロックf に加
えられたNOP 命令の適正な番号とともに、同じハミングウェイト(hammingweig
ht)(1の番号)を持つように選ばれてもよい。
【0027】
加えて、ラインf4・f5におけるJMP命令は、その同じ番号とともにアドレスに
位置してもよい。追加されたJMP 命令は、同じメグメント内の目的地を持つライ
ンh1からh8の間に挿入されてもよい。
【0028】
この実施例では、従って、条件付き分岐の替わりに非条件付き分岐を使用し、
そのコードにランダムな数のダミー処理を加えている。前者の目的は、SPA に対
する対策であり、後者は、DPA 攻撃をもっと難しくさせる。特に、この実施例で
は、ランダムマスク(randaom mask)やノイズをプログラム実行進路に加え、セ
グメント内のランダムアドレスへの分岐は、その分岐のうちの一方が実行される
前に、ランダムな数のプログラム実行をもたらす。それゆえ、いつでも分岐の一
方が実行され、処理装置によって実行された数の処理は、ランダムにDPA 攻撃を
より困難なものに変化させる。
【0029】
上記実施形態では、サブルーチンがプログラムフローを転送することに慣れて
いるが、図4では、分岐の単純な系列が使用される。本発明は、こういった実施
例に示したことに制限を受けるものではない。
【0030】
図5によれば、暗号処理装置で使用される個人あるいは秘密鍵を遮断するため
の方法の実施形態が、符号200によって示されている。その方法は、その鍵を
複数の部品に分割するステップと、新しい部品が最初の個人鍵値と同値になるよ
うに組み合わせられるように新しい部品を抽出するため、nを法として(nは、
楕円カーブにおけるポイントの数)、ランダム値に各部品を組み合わせるステッ
プと、処理装置において分割された各部品を利用するステップとを含んでいる。
【0031】
図5に示すように、暗号化処理装置は、公開鍵あるいは秘密値d を用いて初期
化される。公開鍵Q=dPの計算では、秘密鍵dは、通常、dPを導くためにポイント
P と組み合わせられている。値dは、例えば、d=b10+b20 のように、多数の部品
に分割される。
【0032】
最初のステップでは、d=b10+b20 のように、b1=b10、b2=b20に初期化される。
これらのb1,b2の値は、dの替わりに蓄積される。一方、d 値は、蓄積すること
を望む場合には蓄積されるが、メモリが限られているスマートカードの場合には
、これは望ましくないかもしれない。
【0033】
次のステップでは、ランダムな数のπが生成され、値b1,b2が次のように更新
される。
【0034】
b1=b1+πmod n
b2=b2-πmod n
更新されたb1およびb2の値は、蓄積される。計算は、その時、以下のように、
構成要素b1およびb2を用いてポイントP上で実行される。
【0035】
dPmod n=b1P+b2Pmod n
そして、値πは各セッションのためにランダムに生成されると仮定すると、そ
の時、攻撃者は予想される電力署名(power signature )を確認できそうにない

【0036】
本発明の典型的なアプリケーションでは、署名要素s は、形式を持っている。
【0037】
s=ae+k(mod n)
P は、システムの予め定義したパラメータであるカーブ上の点であり、
k は、短い句の個人鍵あるいはセッション鍵として選ばれたランダムな整数
であり、
R=kPは、短い句の公開鍵に対応しており、
a は、送信者の長い句の個人鍵であり、
Q=aPは、公開鍵に対応する送信者であり、
e は、SHA-1ハッシュ関数のような、メッセージm と短い句の公開鍵R の安
全なハッシュであり、
n は、カーブの配列である。
【0038】
送信者は、R に対応するべき値R'=(sP-eQ)の計算によって、確認されたm,s,R
と署名とを含んでいるメッセージを受信者へ送信する。
【0039】
計算された値が一致する場合には、署名が確認される。上記例での両方の秘密
鍵は、本発明の方法を使用して、遮断されてもよい。
【0040】
発明は、ある特別な形態を参考にして述べられたものであるが、様々な修正は
、この発明における請求の範囲の中で本発明の精神、範囲から離れることなく、
その技術の範囲内であることは明らかである。

【特許請求の範囲】
【請求項1】
明細書に記載の発明。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate


【公開番号】特開2012−198565(P2012−198565A)
【公開日】平成24年10月18日(2012.10.18)
【国際特許分類】
【外国語出願】
【出願番号】特願2012−134710(P2012−134710)
【出願日】平成24年6月14日(2012.6.14)
【分割の表示】特願2000−594019(P2000−594019)の分割
【原出願日】平成12年1月11日(2000.1.11)
【出願人】(397071791)サーティコム コーポレーション (38)
【Fターム(参考)】