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