(57)【要約】【課題】アルゴリズムの実行状態を状態値により管理する装置への不正操作を高精度に検知し、セキュリティの強化が可能な不正操作検知回路、不正操作検知回路を備えた装置、及び不正操作検知方法を提供することを目的とする。【解決手段】不正操作検知回路１０であって、状態値の変化条件ルールを出力する変化条件ルール出力手段１３と、変化条件ルールに基づき、状態値を順次生成する状態値生成手段１１と、状態値を格納する状態値格納手段１２と、遷移前の状態値、遷移後の状態値を比較し、状態値の遷移が変化条件ルールに従っていなければ異常な処理であると判定する状態値比較判定手段１４とを有することにより上記課題を解決する。【選択図】  図１４
2010068135.tif 000002
【特許請求の範囲】
【請求項１】
アルゴリズムの実行状態を状態値により管理する装置への不正操作を検知する不正操作検知回路であって、
正常な処理における状態値の変化条件ルールを出力する変化条件ルール出力手段と、
前記変化条件ルール出力手段から出力される前記変化条件ルールに基づき、前記状態値を順次生成する状態値生成手段と、
前記状態値生成手段が生成した前記状態値を格納する状態値格納手段と、
前記状態値格納手段が格納している前記状態値を遷移前の状態値、前記状態値生成手段が生成した前記状態値を遷移後の状態値として比較し、前記状態値の遷移が前記変化条件ルール出力手段から出力される前記変化条件ルールに従っていなければ異常な処理であると判定する状態値比較判定手段と
を有する不正操作検知回路。
【請求項２】
前記変化条件ルール出力手段は正常な処理における状態値の複数種類の変化条件ルールから一つの前記変化条件ルールを出力する請求項１記載の不正操作検知回路。
【請求項３】
前記変化条件ルール出力手段は正常な処理における状態値の変化条件ルールとして前記遷移前の状態値と前記遷移後の状態値とで変化すべきビット数を出力する請求項１又は２記載の不正操作検知回路。
【請求項４】
前記変化条件ルール出力手段は正常な処理における状態値の複数種類の変化条件ルールとして、前記複数種類の変化条件ルールごとに前記遷移前の状態値と前記遷移後の状態値とで変化すべきビット数を異ならせて出力する請求項２記載の不正操作検知回路。
【請求項５】
アルゴリズムの実行状態を状態値により管理する装置への不正操作を検知する不正操作検知回路を備えた装置であって、
正常な処理における状態値の変化条件ルールを出力する変化条件ルール出力手段と、
前記変化条件ルール出力手段から出力される前記変化条件ルールに基づき、前記状態値を順次生成する状態値生成手段と、
前記状態値生成手段が生成した前記状態値を格納する状態値格納手段と、
前記状態値格納手段が格納している前記状態値を遷移前の状態値、前記状態値生成手段が生成した前記状態値を遷移後の状態値として比較し、前記状態値の遷移が前記変化条件ルール出力手段から出力される前記変化条件ルールに従っていなければ異常な処理であると判定する状態値比較判定手段と
を有する装置。
【請求項６】
アルゴリズムの実行状態を状態値により管理する装置への不正操作を検知する不正操作検知回路の不正操作検知方法であって、
変化条件ルール出力手段が、正常な処理における状態値の変化条件ルールを出力する変化条件ルール出力ステップと、
状態値生成手段が、前記変化条件ルール出力手段から出力される前記変化条件ルールに基づき、前記状態値を順次生成する状態値生成ステップと、
状態値格納手段が、前記状態値生成手段の生成した前記状態値を格納する状態値格納ステップと、
状態値比較判定手段が、前記状態値格納手段が格納している前記状態値を遷移前の状態値、前記状態値生成手段が生成した前記状態値を遷移後の状態値として比較し、前記状態値の遷移が前記変化条件ルール出力手段から出力される前記変化条件ルールに従っていなければ異常な処理であると判定する状態値比較判定ステップと
を有する不正操作検知方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、不正操作検知回路、不正操作検知回路を備えた装置、及び不正操作検知方法に係り、特にアルゴリズムの実行状態を状態（ステート）値により管理する装置への不正操作を検知する不正操作検知回路、不正操作検知回路を備えた装置、及び不正操作検知方法に関する。
【背景技術】
【０００２】
例えばアルゴリズムの実行状態を状態（ステート）値により管理する装置の一例としては任意の暗号機能を搭載したスマートカード（ＩＣカード）がある。従来の暗号機能を搭載したスマートカードには、暗号プロセッサ内部の秘密鍵に対するフォールト攻撃と呼ばれる攻撃を防ぐための耐タンパ技術が用いられているものがある。
【０００３】
暗号方式は共通鍵暗号方式と公開鍵暗号方式とに大別される。共通鍵暗号方式は暗号化と復号とで同一の鍵(秘密鍵)を用いる方式であり、この秘密鍵を送信者及び受信者以外の第三者にわからない情報とすることで安全性を保つものである。公開鍵暗号方式は暗号化と復号とで異なる鍵を用いる方式であり、暗号化を行うための鍵(公開鍵)を一般に公開する代わりに、暗号文を復号するための鍵(秘密鍵)を受信者のみの秘密情報とすることで安全性を保つものである。
【０００４】
暗号の分野における技術の一つには、攻撃技術とよばれるものがある。攻撃技術とは秘密鍵を暗号文等の入手可能な情報から推定する技術のことであり、様々な手法が存在している。これらの攻撃技術は２種類に大別される。
【０００５】
一つの攻撃技術は、理論攻撃と呼ばれるものであり、暗号アルゴリズムの入力データと出力データとの関係から秘密鍵を求める攻撃法である。この攻撃法は、攻撃対象となる暗号アルゴリズムの実装の形態に依存せず、成功することが特徴である。
【０００６】
もう一つの攻撃技術は、実装攻撃と呼ばれるものであり、暗号アルゴリズムを実装した装置に対して、入力データ、出力データの関係のみならず、装置に対して物理的なストレスを加えることで得られるエラー情報や、入出力データ以外に装置から観測される情報を利用することで秘密鍵を推定する技術のことである。この攻撃法の成功の可否は、暗号アルゴリズムの実装形態に依存する。
【０００７】
暗号アルゴリズムが理論攻撃に安全であっても、実装攻撃に対して脆弱である事例が多数知られており、実装攻撃に対して安全性を実現する対策技術は大きな課題である。実装攻撃への対策技術は、耐タンパ(Tamper-proof)技術と呼ばれる。
【０００８】
実装攻撃は、フォールト攻撃とサイドチャネル攻撃との２種類に大別される。フォールト攻撃とは、スマートカードなどに搭載された暗号プロセッサ（暗号装置）の回路の内部データ値に対して、意図的に異常を発生させた場合の暗号処理の出力結果と、正常な暗号処理の出力結果との差分情報を用いて回路の内部に格納されている秘密鍵を推定する方法である。
【０００９】
サイドチャネル攻撃とは、消費電力、電磁波、処理時間など、装置から漏洩する情報を用いて秘密鍵を推定する方法である。これらの中でも、サイドチャネル攻撃では消費電力を用いた方法が最もよく知られており、電力解析攻撃(Power Analysis Attack)と呼ばれている。電力解析攻撃は、消費電力波形から秘密鍵を推定することができる。
【００１０】
次に、ＲＳＡ暗号の演算方法について説明する。ＲＳＡ暗号の復号処理では、指数剰余演算処理と呼ばれる処理が行われる。指数剰余演算は、秘密鍵d，暗号文a，法nに対して、v=ad (mod n)により平文vを計算する処理である。一般的に、ＲＳＡ暗号における秘密鍵dのビット長は1024bit以上が用いられている。このため、d乗演算は単純な方法で実行すると、およそ21024回の乗算が必要となり、現実的な時間内に計算することが不可能となる。
【００１１】
このd乗演算を効率的に行うためのアルゴリズムとしてはバイナリ法が従来から知られている（例えば非特許文献１参照）。このバイナリ法を用いることで、d乗に必要な演算回数は、21024回から1024の定数倍(この定数は1.5以下の値)になり、効率的な演算を実現することができる。
【００１２】
秘密鍵dをu-bit値とし、その2進表現をd=(du-1,du-2,...,d0)2と表記する。ただし、diはdの個々のビット値を表す。図１はバイナリ法を用いた指数剰余演算のアルゴリズムを示す説明図である。図２は、バイナリ法の処理概要を示す説明図である。図１のアルゴリズムでは、dのビット値diを、i=u-1からi=0の順番にチェックする。このチェックの結果がdi=1ならば、２乗算と乗算の両方が実行される。チェックの結果がdi=0ならば、２乗算のみが実行される。この処理をi=u-1からi=0まで繰り返すことにより、バイナリ法はv=ad(mod n)を計算する。つまり、バイナリ法は、鍵ビットdiの値と、２乗算、乗算の実行パターンが、直接的に連動していることが特徴である。
【００１３】
フォールト攻撃とは、半導体に対して、過電圧、異常クロック、高温度、レーザーなどのストレスを与えることで、暗号装置内部のデータ値に異常(Fault)を発生させ、その結果出力される異常な出力値を利用することで、暗号装置内部に格納されている秘密鍵を解読する攻撃である。図３はフォールト攻撃の概要を示す説明図である。
【００１４】
特にレーザーを用いたストレス印加法は、1-bit単位で正確にフォールトを発生させることができ、攻撃者が意図した通りのフォールトを発生させることのできる精度の高い方法として知られている。
【００１５】
代表的なフォールト攻撃は、例えば非特許文献２に記載されている。ここでは、ＲＳＡ暗号に対するフォールト攻撃の概略について説明する。
【００１６】
ＲＳＡ暗号は、素数p,qに対しn=p×qを満たす合成数nを用いる暗号である。ＲＳＡ暗号の安全性は、素因数分解によりnから素数p,qを得ることが困難である、という仮定に基づいている。ただし、p,qは512-bit以上、nは1024-bit以上の大きな整数である。つまり、攻撃者が合成数nから素数p,qを得ることに成功すれば、ＲＳＡ暗号は解読することができる。
【００１７】
ＲＳＡ暗号に対するフォールト攻撃の目的は、素数pを得ることである。素数pを得ることができれば、割り算によりqも簡単に求めることができるので、p,qのいずれかを攻撃者が得ることができれば、ＲＳＡ暗号は解読できる。
【００１８】
ＲＳＡ暗号に対するフォールト攻撃は、正常な出力値と、フォールトを発生させた場合の異常な出力値との２つを用いることで、pを解読する。攻撃者は、正常な出力値を得た後、後述の(mod q)のべき乗剰余計算における計算処理を実行している最中にフォールトを発生させる。
【００１９】
この結果、正常な処理の場合 mq=cqdq (mod q)を得るのに対し、フォールト発生の場合は計算値が異常な値となり、m'q≠mqを満たすm'qを得る(m'qの値は、mqと等しくなければどのような値でも攻撃が成功する)。このm'qを用いて最終的に計算された結果、攻撃者は出力m'を得る。攻撃者は、正常な出力mとフォールト発生時の出力m'を用いて、GCD(m' - n, n)を計算することで、p=GCD(m' - m, n)を得る。ただし、GCD(a,b)は整数a,bの最大公約数を計算する関数である。
【００２０】
この攻撃が成立する理由は、異常なm'qを用いて後述するm'の計算を行うことで、正しいmの値とm'の値との差分がpの整数倍となる、つまり整数kに対してm' -m = kpとなるからであり、その結果、CD(m' - m, n)=GCD(kp, pq) = pを得ることができる。
【００２１】
入力：c (暗号文)
dp  (秘密鍵dに対し、dp=d mod (p-1)を満たす秘密鍵)
dq  (秘密鍵dに対し、dq=d mod (q-1)を満たす秘密鍵)
p  (n=p×qを満たす素数p)
q  (n=p×qを満たす素数q)
u  (u= q-1 (mod p)を満たす整数)
出力：m   (平文)
ただし、eは暗号化用の公開鍵, dは復号用秘密鍵であり、ed=1 mod (p-1)(q-1)を満たす。
【００２２】
＊正常な処理
1. cp= c mod p, cq = c mod q 
2. mp=cpdp (mod p)を計算。
【００２３】
3. mq=cqdq (mod q)を計算。
【００２４】
4. m = ( (mq - mp)×u (mod q) )×p + mp を計算
5. mを出力
＊Fault発生時の処理
1. cp= c mod p, cq = c mod q 
2. mp=cpdp (mod p)
3. mq=cqdq (mod q)計算中にfault発生、mqの代わりにm'q出力(mq'≠mq)
4. m = ( (m'q - mp)×u (mod q) )×p + mp を計算
5. m'を出力
前述したフォールト攻撃は、正常な出力値とフォールト発生時の出力値とを比較することにより、ＲＳＡ暗号を解読するための秘密鍵である素数pを得る攻撃である。ここではフォールト発生時の電力波形を観察することで秘密鍵dを得ることができるフォールト攻撃について説明する（例えば非特許文献３参照）。
【００２５】
図４はバイナリ法を用いるＲＳＡ暗号をベースとした電力解析への耐タンパ性を有するＲＳＡ暗号アルゴリズムを示す説明図である。図４の左側に記してある4ビット値１はＲＳＡ暗号アルゴリズムの実行状態を表す値であり、以下では「状態値」と呼ぶ。図４のＲＳＡ暗号アルゴリズムにおいては、(0000)2, (0001)2, ...., (1001)2が状態値である。図４のＲＳＡ暗号処理に限らず、全ての暗号処理を実行する装置において、状態値は演算の実行状態を管理するために用いられる値である。
【００２６】
図４のＲＳＡ暗号アルゴリズムは、入力された暗号文c, 秘密鍵d=(du-1,du-2,...,d0)2、法nから、平文m=cd (mod n)を計算するアルゴリズムであり、電力解析により秘密鍵dが漏洩することを防ぐ耐タンパ機能（耐タンパ性）を有する。ここでは、この耐タンパ機能について図５を用いて説明する。
【００２７】
図５は、図４のＲＳＡ暗号アルゴリズムを実装した装置におけるd=(10100...)2の場合の消費電力波形を表したイメージ図である。図５は、d=(du-1,du-2,...,d0)2に対して、以下の処理をi=u-1,...,1,0それぞれについて繰り替えし実行した場合の波形である。
【００２８】
di=1： R0=R0×R0で示される２乗算の後に、R0=R0×R1で示される乗算が実行される。
【００２９】
di=0： R0=R0×R0で示される２乗算が実行される。
【００３０】
つまり、図５はdiのビット値に応じて、R0=R0×R0とR0=R0×R1との２種類の乗算が実行されている。もし、これらの乗算の種類を消費電力波形により識別することが可能であるならば、diのビット値を判別でき、秘密鍵dは解読できる。しかし、図４のＲＳＡ暗号アルゴリズムに対しては、上記のような識別は困難である。なぜなら、R0,R1は図４の状態値(0001)2,(0010)2に記されている通り、初期値を乱数r1, r2により与えられ更新される常にランダムな値であるからである。
【００３１】
つまり、R0=R0×R0とR0=R0×R1との２種類の乗算は、いずれも(乱数)×(乱数)の乗算であり、このような乱数データ同士の乗算は、図５に示すように、消費電力波形で識別するのは困難である。すなわち、図４のＲＳＡ暗号アルゴリズムに対する電力解析は困難である。このように、図４のＲＳＡ暗号アルゴリズムを実行する装置は、電力解析に対して安全である。
【００３２】
図４のＲＳＡ暗号アルゴリズムに対して、フォールト攻撃を行うことで、電力解析に対する耐性を無効化できる攻撃法は、従来から存在している（例えば非特許文献３参照）。ＲＳＡ暗号アルゴリズムに対して、フォールト攻撃を行うことで、電力解析に対する耐性を無効化できる攻撃法の基本アイデアは、フォールト攻撃を行うことで、状態値の一部を強制的に変更し、電力解析への対策機能に必要となる処理をスキップし、対策機能を無効化させることである。
【００３３】
図６は、フォールト攻撃による電力解析の対策機能を無効化する方法を表した説明図である。図６に示すように、実行状態は基本的に状態値の遷移により管理される。正常な処理においては、この状態値は(0000)2→(0001)2→(0010)2→(0011)2...のように、１つずつ増加しながら遷移するので、図６に示した順番によるＲＳＡ暗号アルゴリズムの処理が行われる。
【００３４】
図６に示したＲＳＡ暗号アルゴリズムの処理に対し、フォールト攻撃は状態値の値を強制的に変更することで、(0000)2→ (0010)2→(0011)2...のように、一部の状態値（図６の例では(0001)2）を強制的にスキップさせることが可能である。なお、このような精度の高いフォールト発生は、レーザーを用いたストレス印加方法により実現できる。このように図６のＲＳＡ暗号アルゴリズムの処理に対し、フォールト攻撃により状態値(0001)2を強制的にスキップすることで、R0への乱数の書き込み処理がスキップされるため、R0の値は初期値0となる。
【００３５】
図４、図６のＲＳＡ暗号アルゴリズムにおいては、R0への乱数書き込みが耐タンパ機能を保障する重要な条件であり、この処理がスキップされることで耐タンパ機能が無効化される。このスキップの結果、R0の値が0となった場合の消費電力波形を図７に示す。図７は図６の状態値(0001)2をスキップしたＲＳＡ暗号アルゴリズムを実装した装置におけるd=(10100...)2の場合の消費電力波形を表したイメージ図である。
【００３６】
図７においては、R0=R0×R0とR0=R0×R1の２種類の乗算が発生している。図５の消費電力波形においては、これら２種類の乗算は共に(乱数)×(乱数)であった。しかし、図７の消費電力波形においては、フォールト発生によりR0の値がゼロであるので、それぞれ以下の乗算となる。
【００３７】
R0×R0：０×０
R0×R1：０×（乱数）
つまり、R0×R0は入力の両方がゼロである乗算である。R0×R1は入力の片方がゼロである乗算である。乗算の性質上、０を入力とする乗算の消費電力波形は、特殊な形状になることが知られている。このような特殊な波形は、０の入力が１個か、２個かに応じてさらに変化する場合がある。つまり、０の入力が１個である波形と、２個である波形はそれぞれに特徴がある。したがって、図７に示すようにR0×R0の乗算とR0×R1の乗算とは消費電力波形の形状によって識別できる。これらの消費電力波形を識別することで、そのままdのビット値を識別できるので、図７の消費電力波形からは秘密鍵dをd=(10100..)2と解読できる。
【００３８】
前述した、ＲＳＡ暗号アルゴリズムに対してフォールト攻撃を行うことで電力解析に対する耐性を無効化できる攻撃法を防ぐための対策技術は、従来から存在している（例えば特許文献１参照）この対策技術は、回路の内部状態をチェックし、フォールト発生の有無の検知を行う「フォールト検知」による対策法である。
【００３９】
フォールト検知を用いることで、フォールトが発生した場合でも、暗号装置の処理停止やデータ出力停止など、適切な防御方法を実施することができるので、フォールト検知技術はフォールト対策において重要な技術である。
【００４０】
従来のフォール検知の基本アイデアは、暗号装置の外側に状態値の外付けのカウンタを設置し、状態値の遷移が進むごとに、このカウンタを増加させ、このカウンタの値が期待通りの値であるかのチェックを定期的に行うことで、状態値の遷移が正しいかどうかのチェックを行う。つまり、従来のフォール検知の基本アイデアは状態値の遷移が正しく行われているかどうかを、外付けのカウンタを用いて間接的にチェックするものある。
【００４１】
図８はフォールト検知法を表した説明図である。図８は、装置内部の個々の処理を実現する単位を「被制御セクション」と記している。個々の被制御セクションには一つの状態値が対応する。この状態値の遷移をチェックするために、図８のフォールト検知法では外付けのカウンタZZが備えられている。
【００４２】
最初の「開始セクション」において、カウンタZZはZZ=0に初期化される。このZZの値は、被制御セクションを一つ完了するごとに1つ増加する(ZZ=ZZ+1)。N個の被制御セクションから構成されるので、条件分岐なしにN個全ての被制御セクションを実行する実行経路が、フォールト攻撃による状態スキップ無しに正常に実行された場合、カウンタZZの値はNとなっていることが期待される。
【００４３】
また、条件分岐により、全ての被制御セクションが実行されない場合でも、条件分岐によって実行されなかった被制御セクションの個数をZZに加算するので、フォールト攻撃による状態スキップ無しに正常に実行された場合、カウンタZZの値はNとなることが期待される。
【００４４】
例えば被制御セクション1の処理終了後に条件分岐を行う場合、残りのN−1個の被制御セクションが実行されないことになる。この場合は条件分岐時にZZに対してN−1が加算される。他の被制御セクション終了時の条件分岐についても同様に扱う。
【００４５】
これにより、全ての実行経路においてフォールト攻撃による状態スキップ無しに正常に実行された場合、カウンタZZの最終的な値はNとなることが期待される。つまり、図８のフォールト検知法では、このカウンタZZの値がNとなるかどうかを、最後にチェックすることで、フォールト発生の有無を検知することができる。この検知処理は、最後の状態sm+1に対応する「Fault検知：ZZ=N?」の処理において行われる。ZZの値がNであるならば、図８のフォールト検知法ではフォールト発生が無い正常処理と判定され、ZZの値がN以外であるならば、フォールトが発生したと判断する。
【００４６】
例えば図８のプログラムの「実行経路４」に示すように、「被制御セクション１」がフォールト攻撃によりスキップされた場合は、ZZ=ZZ+1の処理が一つスキップされることになるのでフォールト検知処理におけるZZの最終的な値がZZ=N−1となり、本来期待される値であるNではなくなるので、フォールトが発生したことを検知できる。
【特許文献１】特表２００５−５０９９３６号公報
【非特許文献１】Alfred J.Menezesほか著"HANDBOOK OF APPLIED CRYPTOGRAPHY"(CRC press)の615ページ, アルゴリズム14.79 (http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf)
【非特許文献２】D. Boneh, R. A. DeMillo, R. J. Lipton, "On the Importance of Checking Cryptographic Protocols for Faults", Eurocrypt'97, pp.37-51, 1997.
【非特許文献３】Benoit Feix and Louis Marcel, "Passive and Active Combined Attacks", 2007 Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2007）
【発明の開示】
【発明が解決しようとする課題】
【００４７】
図８の公知技術を用いることで、フォールト攻撃は検知できる。しかし、このフォールト検知法は、基本的なフォールト攻撃を検知できるものの、より高度なフォールト攻撃を行った場合、フォールト検知機能が無効化されるという問題点があった。以下では従来のフォールト検知法の問題点について説明を行う。
【００４８】
図９はフォールト検知法の基本的な問題点を表した説明図である。従来のフォールト検知法は前述したとおり、暗号装置の外側に状態値の外付けカウンタを追加し、このカウンタ値の整合性をチェックすることでフォールト発生の有無を検知する。この基本的なメカニズムにより、従来のフォールト検知法は、以下の（Ｐ１）〜（Ｐ３）に示す３つの性質を備える。
【００４９】
（Ｐ１）従来のフォールト検知法はフォールト検知のメカニズムとして、カウンタを増加させる仕組みとカウンタをチェックする仕組みとの２つが必要であり、カウンタのチェックを行うことで初めてフォールト検知に成功する。つまり、従来のフォールト検知法はフォールト検知可能なタイミングが限定される。
【００５０】
（Ｐ２）従来のフォールト検知法は、カウンタのチェックを行っている状態において、初めてフォールト検知が実行されるため、それ以外の状態でフォールト検知が実行できない。
【００５１】
（Ｐ３）従来のフォールト検知法は全ての状態遷移についてフォールト検知を実行することはできない。
【００５２】
（Ｐ３）に示す性質により、従来のフォールト検知法は高度なフォールト攻撃に対してフォールト検知を行うことができない。図９に示すとおり、フォールト検知可能な状態は最後の「Fault検知：ZZ=N?」、つまり状態sm+1のみである。そして、それ以外の状態ではフォールト検知できない。よって、従来のフォールト検知法はフォールト検知のリアルタイム性が失われるという問題を有している。この問題により、従来のフォールト検知法はフォールト検知のメカニズムが高度なフォールト攻撃に対しては無効化される。
【００５３】
また、前述した通り、従来のフォールト検知法は、フォールト検知にリアルタイム性がないため、フォールト検知可能な状態と不可能な状態とに２分される。フォールト検知可能な状態と不可能な状態とに２分されるという性質を考慮して、フォールト検知を無効化するメカニズムは図１０のようになる。
【００５４】
図１０はフォールト検知を無効化するフォールト攻撃を表した説明図である。攻撃者はフォールトを発生させて状態s1をスキップすることで、秘密鍵を得るためのスキップを実行する。しかし、このままではカウンタZZの整合性が失われ、フォールト発生が検知される。そこで、これを回避するために図１０のフォールト攻撃はフォールト検知状態である状態sm+1を再度スキップすることで、フォールト発生が検知されることを回避する。
【００５５】
よって、図１０のフォールト攻撃は秘密鍵を得るために発生させるスキップとフォールト検知を回避させるためのスキップとの２回のフォールトを発生させる高度なフォールト攻撃を行うことで、従来のフォールト検知法を無効化できる。つまり、従来のフォールト検知法は図８に示すフォールト発生を１回行うフォールトに有効であるが、図１０に示すフォールト発生を２回行うフォールト攻撃には無効である。
【００５６】
以上、従来のフォールト検知法はフォールト検知にリアルタイム性がない為、フォールトを１回発生させるフォールト攻撃に有効であるがフォールトを２回発生させるフォールト攻撃に無効である。
【００５７】
本発明の一実施形態は、上記の点に鑑みなされたもので、アルゴリズムの実行状態を状態値により管理する装置への不正操作を高精度に検知し、セキュリティの強化が可能な不正操作検知回路、不正操作検知回路を備えた装置、及び不正操作検知方法を提供することを目的とする。
【課題を解決するための手段】
【００５８】
上記課題を解決するため、本発明の一実施形態は、アルゴリズムの実行状態を状態値により管理する装置への不正操作を検知する不正操作検知回路であって、正常な処理における状態値の変化条件ルールを出力する変化条件ルール出力手段と、前記変化条件ルール出力手段から出力される前記変化条件ルールに基づき、前記状態値を順次生成する状態値生成手段と、前記状態値生成手段が生成した前記状態値を格納する状態値格納手段と、前記状態値格納手段が格納している前記状態値を遷移前の状態値、前記状態値生成手段が生成した前記状態値を遷移後の状態値として比較し、前記状態値の遷移が前記変化条件ルール出力手段から出力される前記変化条件ルールに従っていなければ異常な処理であると判定する状態値比較判定手段とを有する。
【００５９】
なお、本発明の一実施形態の構成要素、表現または構成要素の任意の組合せを、方法、装置、システム、コンピュータプログラム、記録媒体、データ構造などに適用したものも本発明の態様として有効である。
【発明の効果】
【００６０】
上述の如く、本発明の一実施形態によれば、アルゴリズムの実行状態を状態値により管理する装置への不正操作を高精度に検知し、セキュリティの強化が可能な不正操作検知回路、不正操作検知回路を備えた装置、及び不正操作検知方法を提供できる。
【発明を実施するための最良の形態】
【００６１】
次に、本発明を実施するための最良の形態を、以下の実施例に基づき図面を参照しつつ説明していく。なお、本実施例ではアルゴリズムの実行状態を状態（ステート）値により管理する装置の一例として任意の暗号機能を搭載したスマートカード（ＩＣカード）を例に説明するが、他の装置であってもよい。
【００６２】
まず、従来のフォールト検知法の問題点の原因はフォールト検知にリアルタイム性がないことにある。そのため、従来のフォールト検知法はフォールト検知の状態そのものをスキップすることでフォールト検知を無効化できることであった。また、従来のフォールト検知にリアルタイム性がない原因は、全ての状態遷移についてフォールト検知をできないことにあった。
【００６３】
本実施例では、従来のフォールト検知法における前述の問題を解消するために、全ての状態遷移についてフォールト検知を行う手段を提供する。従来のフォールト検知法の問題は状態値の遷移とフォールト検知のカウンタとが別々であったため、状態値のフォールト発生を直接的に検知することができず、フォールト検知のリアルタイム性が失われていたことにあると考えられる。
【００６４】
この問題を解決するために、本実施例においては、状態値の遷移とフォールト検知とを一体化する。状態値の遷移とフォールト検知とを一体化することで、本実施例は全ての状態遷移に関してフォールト検知を有効とし、フォールト検知のリアルタイム性を保障する手段を提供する。
【００６５】
ここでは、本実施例の基本的なアイデアを説明する。図１１はフォールト攻撃に脆弱な従来の状態値の遷移を表した説明図である。図１２は本実施例の状態値の遷移を表した説明図である。
【００６６】
図１１に示すフォールト検知法は、状態値の変化に制約を設けていないため、任意の値から任意の値に状態値が変化可能である。よって、(0000)2→(0010)2のような、本来ありえない状態値の遷移が発生した場合でも、従来のフォールト検知法はフォールト発生を検知することができない。
【００６７】
これに対し、図１２に示す本実施例のフォールト検知法は、正常な状態値の遷移に対して常に一定の制約条件を設ける。図１２は、正常な状態値遷移により状態値のビット値が常に1-bitのみ変化するという制約条件を設けた例である。よって、(0000)2→(0011)2のような、制約条件を満たさない2-bitの状態値の遷移が発生すれば、本実施例のフォールト検知法はフォールト発生を検知できる。
【００６８】
図１３は、フォールト発生が無い正常な場合の従来の状態値の遷移と本実施例の状態値の遷移とを表した説明図である。図１３の上段は従来の状態値の遷移を表している。図１３の下段は本実施例の状態値の遷移を表している。
【００６９】
図１３の上部に示すように、従来の状態値の遷移は分岐がない場合+1ずつ増加し、分岐がある場合、戻った状態数だけ減少する。つまり、フォールト無しの正常な場合における状態値の遷移の法則は一定していないため、状態値の遷移が正常であるか、異常であるかの判断を単純な方法で行うことは困難である。
【００７０】
これに対し、図１３下部に示すように、本実施例の状態値の遷移は分岐の有無に関係なく常に1-bit値だけ状態値が変化するという共通の法則を有する。よって、この法則に従う状態遷移であれば、フォールト無しの正常な遷移と判断でき、この法則に従わない状態遷移であれば、フォールト有りの異常な遷移と判断できる。よって、本実施例のフォールト検知法は、状態値の遷移が常に1-bit値の変化であるか、そうでないかという単純な検査回路（チェック機能回路）を用いることで、フォールト検知を行うことができる。
【００７１】
図１４は本実施例によるフォールト検知回路の一例の構成図である。図１４のフォールト検知回路１０は例えばステートマシンとして利用される。図１４のフォールト検知回路１０は、状態値生成回路１１，状態値レジスタ１２，変化条件ルール回路１３，状態値比較回路１４を有する構成である。
【００７２】
状態値生成回路１１は、遷移後の状態値を決定する。状態値レジスタ１２は現在の状態値を格納する。変化条件ルール回路１３は、フォールト攻撃無しの正常な処理における状態値の変化条件ルールを定める。状態値比較回路１４は状態値の遷移が正常であるかどうかを判断する。
【００７３】
状態値生成回路１１，状態値レジスタ１２は一般的に用いられる回路である。変化条件ルール回路１３，状態値比較回路１４はチェック機能回路である。状態値レジスタ１２の出力は、現在の状態値を表している。状態値レジスタ１２の入力は、次の状態値を表している。
【００７４】
つまり、状態値レジスタ１２の入力と出力とを比較することで、遷移前及び遷移後の状態値の比較を行うことができる。変化条件ルール回路１３，状態値比較回路１４は遷移前及び遷移後の状態値の比較によるフォールト検知のチェック機能回路として動作する。状態値比較回路１４は状態値レジスタ１２の入力と出力とを比較することで、フォールト発生の有無の検知を行う。
【００７５】
状態値比較回路１４が行うフォールト発生の有無の検知は状態値レジスタ１２の入力と出力との関係が、変化条件ルール回路１３の与える変化条件ルールに従っているか否かにより行われる。状態値比較回路１４は、状態値レジスタ１２の入力と出力との関係が変化条件ルール回路１３の与える変化条件ルールに従っている場合、フォールト発生の無い正常な処理であると判断し、変化条件ルールに従っていない場合、フォールトの発生した異常な処理であると判断する。
【００７６】
変化条件ルール回路１３の与える変化条件ルールが「1-bit値変化」である場合、図１２や図１３の下段に示したフォールト検知回路となる。もし、フォールトの発生した異常な処理であると判断される場合、状態値比較回路１４はフォールト検知出力によりフォールト発生を検知したことを外部の回路（例えばＣＰＵ）に通知する。
【００７７】
ここではフォールト検知機能を実現するために必要となる回路の比較のために、従来のフォールト検知回路の構成を図１５に示す。図１５は従来のフォールト検知回路の一例の構成図である。図１５のフォールト検知回路は、状態値生成回路２１，状態値レジスタ２２，フォールト検知用カウンタ制御回路２３，フォールト検知用カウンタ２４，フォールト検知用カウンタチェック回路２５を有する構成である。状態値生成回路２１は遷移後の状態値を決定する。状態値レジスタ２２は現在の状態値を格納する。
【００７８】
状態値生成回路２１，状態値レジスタ２２は一般的に用いられる回路である。フォールト検知用カウンタ制御回路２３，フォールト検知用カウンタ２４はカウンタ機能回路である。フォールト検知用カウンタチェック回路２５は、チェック機能回路である。
【００７９】
状態値生成回路２１により状態値の遷移が決定されるのを受けて、フォールト検知用カウンタ制御回路２３はフォールト検知用カウンタ２４の値の操作を行う。フォールト検知用カウンタ２４の値は、図８〜図１０におけるカウンタZZの値に相当する。
【００８０】
フォールト検知用カウンタ制御回路２３は図８〜図１０のカウンタZZと同様に、状態値の分岐の有無、および分岐のタイミングに応じて、フォールト検知用カウンタ２４に対する様々な操作を行う。フォールト検知用カウンタ制御回路２３は、状態値の遷移に応じてフォールト検知用カウンタ２４の操作を決定する。
【００８１】
フォールト検知用カウンタチェック回路２５はフォールト検知を行う。フォールト検知用カウンタチェック回路２５は、フォールト検知用カウンタ制御回路２３によるフォールト検知用カウンタ２４に対する操作が何回か繰り返されたあと、フォールト検知用カウンタ２４の値が期待値どおりの値であるかをチェックすることで、フォールト発生の有無を判断する。
【００８２】
なお、フォールト検知用カウンタ２４の値が期待値どおりの値であるかをチェックするフォールト検知用カウンタチェック回路２５の処理は、図８〜図１０において、カウンタZZについてZZ=Nであるかどうかの判定を行う処理に対応する。
【００８３】
フォールト検知用カウンタ２４の値が期待値どおりの正常な値であるならば、フォールト検知用カウンタチェック回路２５はフォールト発生の無い正常な処理と判断し、期待値通りの正常な値でなければフォールト発生の有る異常な処理と判断する。フォールトが発生していると判断された場合、フォールト検知用カウンタチェック回路２５はフォールト検知出力によりフォールト発生を検知したことを外部の回路に通知する。
【００８４】
従来のフォールト検知回路は状態値の遷移とフォールト検知とを一体化せず、間接的にフォールト検知を行うので、状態値の遷移をカウントするカウンタ機能回路と、その状態値の遷移のカウント値が期待値どおりの値であるかをチェックするチェック機能回路との両方が必要である。
【００８５】
これに対し、本発明のフォールト検知回路１０は、状態値の遷移とフォールト検知とを一体化しているため、図１４に示す通り、チェック機能回路のみの追加でよい為、従来のフォールト検知回路より小さな回路によるフォールト検知機能を実現できる。
【００８６】
図１４のフォールト検知回路１０は改良を加えることで、更にセキュリティを向上させることができる。ここでは、図１４のフォールト検知回路１０のセキュリティを向上させる改良について説明する。図１６は、図１４のフォールト検知回路により検知できない状態値のスキップを表した説明図である。
【００８７】
図１４のフォールト検知回路１０は変化条件ルールが「1-bit値変化」である場合における状態値の遷移例を表している。図６に示すＲＳＡ暗号アルゴリズムを実装した暗号装置は秘密鍵を得るための状態値のスキップとして、(0000)2→(0011)2...のフォールト攻撃を行われてもフォールト発生を検知できるので安全である。しかし、図１４のフォールト検知回路１０は一部の状態値のスキップを検知できない。なぜなら、図１４のフォールト検知回路１０は変化条件ルール（制約条件）の範囲内の状態値の遷移であれば、フォールト発生と判定しないからである。
【００８８】
図１６は変化条件ルールが「1-bit値変化」の例である為、状態値が1-bit値だけ変化する(0000)2→(0010)2及び(0000)2→(0100)2のフォールト攻撃を検知できないことを表している。このように、本実施例のフォールト検知回路１０は一部の状態値のスキップに関して検知できない、フォールト検知漏れを有する。このフォールト検知漏れを有していても図６に示すＲＳＡ暗号アルゴリズムを実装した暗号装置はフォールト攻撃による秘密鍵の解読を防ぐことができる。
【００８９】
図６に示すＲＳＡ暗号アルゴリズムを実装した暗号装置から秘密鍵を得る為にはR0への乱数書き込みに対してはスキップを行うがR1への乱数書き込みに対してはスキップを行わないことが必要である。なぜなら、R0,R1の両方の乱数書き込みをスキップすることでR0×R0, R0×R1の両方が0×0となるため、これらは完全に同一の演算となり、消費電力波形による識別が不可能となるからである。つまり、図６に示すＲＳＡ暗号アルゴリズムを実装した装置に対して秘密鍵を得るための状態値のスキップは、(0000)2→(0011)2に限定される。
【００９０】
よって、図１４に示す本実施例のフォールト検知回路１０はフォールト検知漏れを有するが、図６に示すＲＳＡ暗号アルゴリズムを実装した暗号装置に適用した場合、フォールト発生に成功しても秘密鍵を解読することができないため、安全である。
【００９１】
ゆえに、本実施例のフォールト検知回路１０は、暗号装置を開発する段階で既知の攻撃法(Known Attack)の調査を行い、秘密鍵を解読できる状態値のスキップのパターンを事前に網羅し、このようなフォールト検知漏れに関する秘密鍵の漏洩の可能性について検証を行うことで、秘密鍵の解読が不可能である状態値の遷移を構築することができる。
【００９２】
既知の攻撃法(Known Attack)に対しては図１４に示す本実施例のフォールト検知回路１０を用いることでフォールト攻撃による秘密鍵の解読を防止できる。ただし、図１４に示す本実施例のフォールト検知回路１０のフォールト検知漏れは既知の攻撃法に対する防御を実現できるが、未知の攻撃法(Unknown Attack)に対して秘密鍵が解読できる可能性を残す。
【００９３】
例えば図１６に示した例では、(0000)2→(0010)2及び(0000)2→(0100)2のスキップが可能であり、将来的に攻撃手法が進化した場合、これらのスキップを用いた秘密鍵の解読が成功する可能性が残されているからである。そこで、図１４のフォールト検知回路１０は改良を加えることで、既知の攻撃のみならず、将来的に発生しうる未知の攻撃に対する防御を実現できるようにする。
【００９４】
図１７は、図１４に示す本実施例のフォールト検知回路が有するフォールト検知漏れの解決方法を表した説明図である。図１７の上段は図１４に示す本実施例のフォールト検知回路１０において変化条件ルールを「1-bit値変化」とした場合における状態値の遷移例を表している。図１７の下段は図１４に示す本実施例のフォールト検知回路１０において変化条件ルールを「3-bit値変化」とした場合における状態値の遷移例を表している。
【００９５】
図１７の上段、下段いずれの場合についても、図６に示すアルゴリズムを実装した暗号装置から秘密鍵を得るための状態値のスキップとして、(0000)2→(0011)2（上段）もしくは(0000)2→(1010)2（下段）のフォールト攻撃を行おうとすると、フォールト発生を検知できるので安全である。
【００９６】
しかし、図１４のフォールト検知回路１０は、全ての状態値のスキップに関して検知できる完全な方法ではなく、一部の状態値のスキップに関しては検知できない。図１４に示すフォールト検知回路１０は、制約条件の範囲内の状態値の遷移であれば、フォールト発生と判断しないからである。
【００９７】
例えば図１７上段では、(0000)2→(0010)2および(0000)2→(0100)2のスキップが1-bit値変化であるためフォールト発生を検知できない。図１７下段では、(0000)2→(1110)2のスキップおよび(0000)2→(1011)2が3-bit値変化であるためフォールト発生を検知できない。
【００９８】
このように、図１４に示す本実施例の方式は一部の状態値の遷移についてスキップ可能であり、図１６に示すように状態値の変化条件ルールに応じて、固定のパターンによる状態値のスキップが可能である。
【００９９】
例えば図１７上段では(0000)2→(0010)2および(0000)2→(0100)2、つまり２パターンのスキップが可能である。同様に、図１７下段では(0000)2→(1110)2および(0000)2→(1011)2の２パターンのスキップが可能である。
【０１００】
つまり、ある状態値の変化条件ルールにおいて可能であった状態値のスキップは、もう片方の状態値の変化条件ルールにおいて不可能であることが分かる。よって、状態値の変化条件ルールを複数準備し、どの変化条件ルールを用いるかをフォールト検知回路１０の内部で発生させた乱数によって選択することで、フォールト検知回路１０はフォールト検知漏れとなる状態値のスキップのパターンを攻撃者が特定できなくなり、安全性を向上することができる。
【０１０１】
図１８は本実施例によるフォールト検知回路の他の例の構成図である。図１８に示したフォールト検知回路１０Ａは、状態値生成回路１１Ａ〜１１Ｃ，状態値レジスタ１２，変化条件ルール回路１３Ａ〜１３Ｃ，状態値比較回路１４，セレクタ１５及びセレクタ１６を有する構成である。
【０１０２】
状態値生成回路１１Ａ〜１１Ｃは、遷移後の状態値を決定する。状態値レジスタ１２は現在の状態値を格納する。変化条件ルール回路１３Ａ〜１３Ｃは、フォールト攻撃無しの正常な処理における状態値の変化条件ルールを定める。状態値比較回路１４は状態値の遷移が正常であるかどうかを判断する。セレクタ１５は乱数に基づいて、状態値生成回路１１Ａ〜１１Ｃの出力の何れか一つを、状態値レジスタ１２及び状態値比較回路１４に入力する。また、セレクタ１６は乱数に基づいて変化条件ルール回路１３Ａ〜１３Ｃの出力の何れか一つを、状態値比較回路１４に入力する。
【０１０３】
セレクタ１５及びセレクタ１６は乱数に基づいて連動し、状態値生成回路１１Ａの出力が選択されるとき変化条件ルール回路１３Ａの出力が選択され、状態値生成回路１１Ｂの出力が選択されるとき変化条件ルール回路１３Ｂの出力が選択され、状態値生成回路１１Ｃの出力が選択されるとき変化条件ルール回路１３Ｃの出力が選択される。
【０１０４】
状態値比較回路１４は状態値レジスタ１２の入力と出力とを比較することで、フォールト発生の有無の検知を行う。状態値比較回路１４が行うフォールト発生の有無の検知は状態値レジスタ１２の入力と出力との関係が、変化条件ルール回路１３Ａ〜１３Ｃの何れか一つにより与えられる変化条件ルールに従っているか否かにより行われる。
【０１０５】
状態値比較回路１４は、状態値レジスタ１２の入力と出力との関係が、セレクタ１６を介して変化条件ルール回路１３Ａ〜１３Ｃの何れか一つにより与えられる変化条件ルールに従っている場合、フォールト発生の無い正常な処理であると判断し、変化条件ルールに従っていない場合、フォールトの発生した異常な処理であると判断する。
【０１０６】
なお、セレクタ１５による状態値生成回路１１Ａ〜１１Ｃの出力の何れか一つを選択する処理と、セレクタ１６による変化条件ルール回路１３Ａ〜１３Ｃの出力の何れか一つを選択する処理とは、フォールト検知回路１０Ａが動作する最初のサイクルの初期化処理として実行される。
【０１０７】
図１８のフォールト検知回路１０Ａは、変化条件ルール回路１３Ａの与える変化条件ルールが「1-bit値変化」であり、変化条件ルール回路１３Ｂの与える変化条件ルールが「2-bit値変化」であり、変化条件ルール回路１３Ｃの与える変化条件ルールが「3-bit値変化」である例を表している。また、図１８のフォールト検知回路１０Ａは、状態値生成回路１１Ａが変化条件ルール「1-bit値変化」に基づいて遷移後の状態値を決定し、状態値生成回路１１Ｂが変化条件ルール「2-bit値変化」に基づいて遷移後の状態値を決定し、状態値生成回路１１Ｃが変化条件ルール「3-bit値変化」に基づいて遷移後の状態値を決定する。
【０１０８】
図１４のフォールト検知回路１０と比較すると、フォールト検知回路１０Ａは乱数の入力と、３つの状態値生成回路１１Ａ〜１１Ｃと、３つの変化条件ルール回路１３Ａ〜１３Ｃと、セレクタ１５と、セレクタ１６とを更に必要とするが、３つの中から乱数により一つの変化条件ルールを選択することで、図１４のフォールト回路１０におけるフォールト検知漏れの確率「１」を「１／３」に下げることができる。
【０１０９】
なお、フォールト検知漏れの確率が「１／３」ということは、フォールト検知できる確率が「１」から「１／３」であることを意味する。一般的に、フォールト検知回路を備えた暗号装置は、フォールト検知に１回でも成功したら、秘密鍵データ消去処理、暗号装置の利用停止処理などにより、攻撃者が２度とフォールト攻撃できないような適切な対処を実行する。
【０１１０】
したがって、攻撃者は何回もフォールト攻撃を繰り返し試すことにより秘密鍵を解読することが不可能である。図１８のフォールト検知回路１０Ａは、既知の攻撃を確率「１」で防御を行い、さらに未知の攻撃に対しても確率「１」−「１／３」で防御することができる。この確率は変化条件ルールの数を多くするほど「１」に近づけることができ、より安全となる。なお、図１８のフォールト検知回路１０Ａでは変化条件ルールが３つの例を示したが複数であれば他の数値でもよい。
【０１１１】
フォールト検知なしの回路、従来のフォールト検知回路，図１４のフォールト検知回路１０，図１８のフォールト検知回路の特徴は図１９のようになる。図１９はフォールト検知なしの回路、従来のフォールト検知回路，図１４のフォールト検知回路１０，図１８のフォールト検知回路１０Ａの特徴を比較した比較図である。
【０１１２】
本実施例の図１４に示したフォールト検知回路１０，図１８に示したフォールト検知回路１０Ａは、従来のフォールト検知回路が備えていなかった、フォールト検知のリアルタイム性を備えているというメリットを有する。
【０１１３】
また、本実施例の図１４に示したフォールト検知回路１０，図１８に示したフォールト検知回路１０Ａは、既知の攻撃に対してフォールト発生を１回実施する、２回実施する方法の両方に対して秘密鍵の漏洩を防止することができる。また、本実施例の図１８に示したフォールト検知回路１０Ａは、将来的に攻撃手法が進化し、未知の攻撃が発見された場合でも、秘密鍵の漏洩を防止することができる。
【０１１４】
また、従来のフォールト検知回路は、フォールト検知を実現するため、カウンタ機能とチェック機能の両方が必要であった。一方、本実施例の図１４に示したフォールト検知回路１０，図１８に示したフォールト検知回路１０Ａは、チェック機能のみによりフォールト検知を実現することができる。
【０１１５】
図２０はフォールト攻撃対策ハードウェアを搭載したスマートカードチップの一例の構成図である。スマートカードチップ１００は、ＣＰＵ１０１，ＲＯＭ１０２，通信回路１０３，外部インターフェース１０４，フォールト攻撃対策ハードウェア１０５，ＲＡＭ１０６，クロック生成回路１０７，電源回路１０８を有する構成である。
【０１１６】
図２０中、フォールト攻撃対策ハードウェア１０５は、本実施例のフォールト検知回路１０又は１０Ａに相当する。フォールト攻撃対策ハードウェア１０５は、上記したようにフォールト発生を検知すると、バス経由でＣＰＵ１０１にフォールト検知信号（割り込み信号）を出力する。ＣＰＵ１０１はフォールト検知信号を受信すると、秘密鍵データ消去処理、暗号装置の利用停止処理などにより、攻撃者が２度とフォールト攻撃できないような適切な対処を実行する。
【０１１７】
本実施例のフォールト検知回路１０又は１０Ａは、ＲＳＡ暗号アルゴリズム，ＡＥＳ暗号アルゴリズムなど、任意の暗号アルゴリズムに対するフォールト攻撃により秘密鍵の推定が行われることを防ぐための対策技術である。本実施例のフォールト検知回路１０又は１０Ａを適用することで、暗号装置は高い耐タンパ性を持つことができる。
【実施例１】
【０１１８】
図２１は共通鍵暗号方式への本実施例の適用を表した一例の説明図である。代表的な共通鍵暗号アルゴリズムは、Advanced Encryption Standard(AES)が、米国連邦標準Federal Information Standards (FIPS) FIPS 197として公開している（文献：http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf）。
【０１１９】
図２１は、この文献の１５ページ、Figure5に記されているAES暗号化処理に対して図１４に示したフォールト検知回路１０を用いた場合の状態値の遷移を表している。図２１では１３個の状態値を4-bitで表現している。状態値の変化条件ルールは、1-bit値変化である。正常な遷移である限り、状態値は常に1-bit変化を行う。
【０１２０】
本実施例のフォールト検知回路１０の状態値比較回路１４は、状態値の遷移前と遷移後の値を比較し、1-bit値の変化であればフォールト発生が無いと判定し、それ以外の変化であればフォールトが発生したと判定する。
【実施例２】
【０１２１】
図２２は共通鍵暗号方式への本実施例の適用を表した他の例の説明図である。図２２では状態値の変化条件ルールが２つ以上必要となる。図２２では第１の変化条件ルールとして「1-bit値変化」、第２の変化条件ルールとして「3-bit値変化」を利用している。図２２の共通鍵暗号アルゴリズムを実行する前の初期化処理として、本実施例のフォールト検知回路１０Ａは乱数により第１の変化条件ルール又は第２の変化条件ルールを選択する。
【０１２２】
本実施例のフォールト検知回路１０Ａの状態値比較回路１４は、選択された第１又は第２の変化条件ルールに応じて、状態値の遷移前と遷移後との比較を行う。フォールト検知回路１０Ａの状態値比較回路１４は、第１の変化条件ルールが選択された場合、1-bit値の変化であればフォールト発生が無いと判定し、それ以外の変化であればフォールトが発生したと判定する。
【０１２３】
フォールト検知回路１０Ａの状態値比較回路１４は、第２の変化条件ルールが選択された場合、3-bit値の変化であればフォールト発生が無いと判定し、それ以外の変化であればフォールトが発生したと判定する。
【実施例３】
【０１２４】
図２３は公開鍵暗号方式への本実施例の適用を表した一例の説明図である。代表的な公開鍵暗号アルゴリズムとしては、RSA暗号方式が知られている。RSA暗号は乗算剰余演算を繰り返すことで処理を行う公開鍵暗号である。
【０１２５】
RSA暗号は乗算剰余を効率的に実行するための方法として、整数A,B, 法Nに対してREDC(A,B,N)=A×B×R-1 (mod N)を計算するMontgomery乗算剰余という方法が一般的に知られている。ただし、RはNのビット長xに対して、R=2xで与えられる定数である。
【０１２６】
Montgomery乗算剰余の処理アルゴリズムは、様々な方法が知られているが、その一つに文献：Kouichi Itoh, Masahiko Takenaka, Naoya Torii, Syouji Temma, and Yasushi Kurihara, "Fast Implementation of Public-Key Cryptography on a DSP TMS320C6201", CHES '99, LNCS 1717, page 61-72の方法が知られている。
【０１２７】
図２３は、この文献のpage65, Algorithm4に記されたMontgomery乗算剰余に対して図１４に示したフォールト検知回路１０を用いた場合の状態値の遷移を表している。図２３では、w-bit単位の変数をg個並べることで、RSA暗号で用いられる1024-bit以上の数値を表現している。wは、一般的にw=16,32,64など、1024より小さな値である。w-bitの部分乗算を繰り返すことで、1024-bit以上の乗算剰余演算を行う。
【０１２８】
図２３では１７個の状態値を5-bitで表現している。状態値の変化条件ルールは、1-bit値変化である。いずれの状態遷移についても正常な遷移である限り、状態値は常に1-bit変化を行う。本実施例のフォールト検知回路１０の状態値比較回路１４は、状態値の遷移前と遷移後の値を比較し、1-bit値の変化であればフォールト発生が無いと判定し、それ以外の変化であればフォールトが発生したと判定する。
【０１２９】
実施例１，２は、共通鍵暗号方式の実施例であり、条件分岐のパターンは、for文による１重ループと非常に簡潔な構造であった。これに対し、図２３の示す公開鍵暗号方式の実施例においては条件分岐のパターンがもっと複雑となり、for文による２重ループと、if文による条件分岐とが組み合わさっている。条件分岐のパターンが複雑化することで、状態値の遷移パターンの構築は、より困難となる。
【０１３０】
この困難さを解決するためには、補助的な手段が必要となるが、その一つである"NOP"状態の挿入を図２３の条件分岐((11001)2-(10001)2の状態値)において用いている。"NOP"とは、何も処理を行わない状態を指す。"NOP"は何も処理を行わないため、冗長な処理であるが、状態値の遷移条件の制約下において、遷移パターンを構築するために用いることができる補助的な手段である。
【０１３１】
図２４は状態値の遷移条件が1-bit値変化である場合において、この"NOP"挿入が必要な例を示す説明図である。状態値の変化条件ルールが1-bit値変化の場合は、図２２に示すように、状態値A,B,Cを用いて以下の処理を行う場合、状態値BとCとの間にNOPを挿入する必要がある。
【０１３２】
A  if (cond) then {
B    処理1}
C  処理2
変化条件ルールを1-bit値変化とした場合には、状態値A→B→Cの遷移を行うことを考える。状態値Aに含まれる'1'の個数をｋと表記すると、状態変化ルールの制約により、状態値Bでは'1'の個数が1つ増えるか、もしくは減るかのいずれであるので、k-1もしくはk+1となる。同様に、状態値Bから状態値Cに遷移する場合は、'1'の個数はk-2、kもしくはk+2となる。
【０１３３】
以上により、変化条件ルールを1-bit値変化とした場合には、状態値A→B→Cの遷移を実現することができる。しかし、A→Cの遷移を行う場合は、'1'の個数がk個からk-2, k, k+2となる。つまり、A→Cの遷移を行う場合はkの値に関係なく、状態値が2-bit値変化するか、0-bit値変化するかのいずれかでしかなく、1-bit値変化を実現できない。この問題を解決するために、変化条件ルールを1-bit値変化とした場合には、状態値BとCとの間にNOPを挿入した以下の処理を行う。
【０１３４】
A  if (cond) then {
B    処理1
C    NOP }
D  処理2
状態値BとCとの間にNOPを挿入したことで、変化条件ルールを1-bit値変化とした場合には、状態値A→B→C→Dの遷移において、状態値CからDに遷移したときの'1'の個数を、k-1もしくはk+1とすることができる。このとき、状態値A→Dの遷移は1-bit値変化となる。つまり、状態値A→B→C→Dの遷移と、状態値A→Dの遷移とは、両方とも1-bit値変化という制約において実現することができる。ここでは、NOPの挿入を含めた、状態値の遷移パターンの構築に利用できる補助的な手段を以下に列挙する。
【０１３５】
・NOPの挿入
図２４では条件分岐に関する例を示したが、ループ分岐に対しても応用可能である。
【０１３６】
・状態値のビット長の拡大
状態値のビット長を拡大することで、状態値の選択の自由度が広がり、状態値の遷移パターンの構築が容易となる。例えば１５個の状態値が与えられている場合、それを表現するための最小のビット長は4-bitであるが、この4-bitより大きなビット長で１５個の状態値を表現することで、状態値の遷移パターンの構築が容易となる。
【０１３７】
・テンプレートの作成
１重ループ、２重ループ、条件分岐など、基本的なフロー制御の種類に応じて、状態値の構築のためのテンプレートを事前計算しておき、そのテンプレートを利用して、状態値の構築を行う。ループ中の状態数、条件分岐の状態数に応じて多様なテンプレートを作成することで、様々な処理に対応できる。
【実施例４】
【０１３８】
図２５は公開鍵暗号方式への本実施例の適用を表した他の例の説明図である。図２５では状態値の変化条件ルールが２つ以上必要となる。図２５では第１の変化条件ルールとして「1-bit値変化」、第２の変化条件ルールとして「3-bit値変化」を利用している。図２５の公開鍵暗号アルゴリズムを実行する前の初期化処理として、本実施例のフォールト検知回路１０Ａは乱数により第１の変化条件ルール又は第２の変化条件ルールを選択する。
【０１３９】
本実施例のフォールト検知回路１０Ａの状態値比較回路１４は、選択された第１又は第２の変化条件ルールに応じて、状態値の遷移前と遷移後との比較を行う。フォールト検知回路１０Ａの状態値比較回路１４は、第１の変化条件ルールが選択された場合、1-bit値の変化であればフォールト発生が無いと判定し、それ以外の変化であればフォールトが発生したと判定する。
【０１４０】
フォールト検知回路１０Ａの状態値比較回路１４は、第２の変化条件ルールが選択された場合、3-bit値の変化であればフォールト発生が無いと判定し、それ以外の変化であればフォールトが発生したと判定する。
【０１４１】
（効果）
本実施例の効果は図１９の比較図に示される通りである。本実施例は、従来のフォールト検知回路が備えていなかった、フォールト検知のリアルタイム性を備えている。既知の攻撃に対しては、フォールト発生を１回実施する、２回実施する方法の両方に対して秘密鍵の漏洩を防止することができる。将来的に攻撃手法が進化し、未知の攻撃が発見された場合でも、図１８のフォールト検知回路１０Ａは秘密鍵の漏洩を防止できる。
【０１４２】
また、従来のフォールト検知回路は、フォールト検知を実現するため、カウンタ機能とチェック機能の両方が必要であった。一方、本実施例の図１４に示したフォールト検知回路１０，図１８に示したフォールト検知回路１０Ａは、チェック機能のみによりフォールト検知を実現できる。
【０１４３】
本発明は、以下に記載する付記のような構成が考えられる。
（付記１）
アルゴリズムの実行状態を状態値により管理する装置への不正操作を検知する不正操作検知回路であって、
正常な処理における状態値の変化条件ルールを出力する変化条件ルール出力手段と、
前記変化条件ルール出力手段から出力される前記変化条件ルールに基づき、前記状態値を順次生成する状態値生成手段と、
前記状態値生成手段が生成した前記状態値を格納する状態値格納手段と、
前記状態値格納手段が格納している前記状態値を遷移前の状態値、前記状態値生成手段が生成した前記状態値を遷移後の状態値として比較し、前記状態値の遷移が前記変化条件ルール出力手段から出力される前記変化条件ルールに従っていなければ異常な処理であると判定する状態値比較判定手段と
を有する不正操作検知回路。
（付記２）
前記変化条件ルール出力手段は正常な処理における状態値の複数種類の変化条件ルールから一つの前記変化条件ルールを出力する付記１記載の不正操作検知回路。
（付記３）
前記変化条件ルール出力手段は正常な処理における状態値の変化条件ルールとして前記遷移前の状態値と前記遷移後の状態値とで変化すべきビット数を出力する付記１又は２記載の不正操作検知回路。
（付記４）
前記変化条件ルール出力手段は正常な処理における状態値の複数種類の変化条件ルールとして、前記複数種類の変化条件ルールごとに前記遷移前の状態値と前記遷移後の状態値とで変化すべきビット数を異ならせて出力する付記２記載の不正操作検知回路。
（付記５）
アルゴリズムの実行状態を状態値により管理する装置への不正操作を検知する不正操作検知回路を備えた装置であって、
正常な処理における状態値の変化条件ルールを出力する変化条件ルール出力手段と、
前記変化条件ルール出力手段から出力される前記変化条件ルールに基づき、前記状態値を順次生成する状態値生成手段と、
前記状態値生成手段が生成した前記状態値を格納する状態値格納手段と、
前記状態値格納手段が格納している前記状態値を遷移前の状態値、前記状態値生成手段が生成した前記状態値を遷移後の状態値として比較し、前記状態値の遷移が前記変化条件ルール出力手段から出力される前記変化条件ルールに従っていなければ異常な処理であると判定する状態値比較判定手段と
を有する装置。
（付記６）
アルゴリズムの実行状態を状態値により管理する装置への不正操作を検知する不正操作検知回路の不正操作検知方法であって、
変化条件ルール出力手段が、正常な処理における状態値の変化条件ルールを出力する変化条件ルール出力ステップと、
状態値生成手段が、前記変化条件ルール出力手段から出力される前記変化条件ルールに基づき、前記状態値を順次生成する状態値生成ステップと、
状態値格納手段が、前記状態値生成手段の生成した前記状態値を格納する状態値格納ステップと、
状態値比較判定手段が、前記状態値格納手段が格納している前記状態値を遷移前の状態値、前記状態値生成手段が生成した前記状態値を遷移後の状態値として比較し、前記状態値の遷移が前記変化条件ルール出力手段から出力される前記変化条件ルールに従っていなければ異常な処理であると判定する状態値比較判定ステップと
を有する不正操作検知方法。
【０１４４】
本発明は、具体的に開示された実施例に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【図面の簡単な説明】
【０１４５】
【図１】バイナリ法を用いた指数剰余演算のアルゴリズムを示す説明図である。
【図２】バイナリ法の処理概要を示す説明図である。
【図３】フォールト攻撃の概要を示す説明図である。
【図４】バイナリ法を用いるＲＳＡ暗号をベースとした電力解析への耐タンパ性を有するＲＳＡ暗号アルゴリズムを示す説明図である。
【図５】図４のＲＳＡ暗号アルゴリズムを実装した装置におけるd=(10100...)2の場合の消費電力波形を表したイメージ図である。
【図６】フォールト攻撃による電力解析の対策機能を無効化する方法を表した説明図である。
【図７】図６の状態値(0001)2をスキップしたＲＳＡ暗号アルゴリズムを実装した装置におけるd=(10100...)2の場合の消費電力波形を表したイメージ図である。
【図８】フォールト検知法を表した説明図である。
【図９】フォールト検知法の基本的な問題点を表した説明図である。
【図１０】フォールト検知を無効化するフォールト攻撃を表した説明図である。
【図１１】フォールト攻撃に脆弱な従来の状態値の遷移を表した説明図である。
【図１２】本実施例の状態値の遷移を表した説明図である。
【図１３】フォールト発生が無い正常な場合の従来の状態値の遷移と本実施例の状態値の遷移とを表した説明図である。
【図１４】本実施例によるフォールト検知回路の一例の構成図である。
【図１５】従来のフォールト検知回路の一例の構成図である。
【図１６】図１４のフォールト検知回路により検知できない状態値のスキップを表した説明図である。
【図１７】図１４に示す本実施例のフォールト検知回路が有するフォールト検知漏れの解決方法を表した説明図である。
【図１８】本実施例によるフォールト検知回路の他の例の構成図である。
【図１９】フォールト検知なしの回路、従来のフォールト検知回路，図１４のフォールト検知回路１０，図１８のフォールト検知回路１０Ａの特徴を比較した比較図である。
【図２０】フォールト攻撃対策ハードウェアを搭載したスマートカードチップの一例の構成図である。
【図２１】共通鍵暗号方式への本実施例の適用を表した一例の説明図である。
【図２２】共通鍵暗号方式への本実施例の適用を表した他の例の説明図である。
【図２３】公開鍵暗号方式への本実施例の適用を表した一例の説明図である。
【図２４】状態値の遷移条件が1-bit値変化である場合において、この"NOP"挿入が必要な例を示す説明図である。
【図２５】公開鍵暗号方式への本実施例の適用を表した他の例の説明図である。
【符号の説明】
【０１４６】
１    ４ビット値（状態値）
１０，１０Ａ    フォールト検知回路
１１，１１Ａ〜１１Ｃ，２１    状態値生成回路
１２，２２    状態値レジスタ
１３，１３Ａ〜１３Ｃ    変化条件ルール回路
１４    状態値比較回路
１５，１６    セレクタ
２３    フォールト検知用カウンタ制御回路
２４    フォールト検知用カウンタ
２５    フォールト検知用カウンタチェック回路
１００    スマートカードチップ
１０１    ＣＰＵ
１０２    ＲＯＭ
１０３    通信回路
１０４    外部インターフェース
１０５    フォールト攻撃対策ハードウェア
１０６    ＲＡＭ
１０７    クロック生成回路
１０８    電源回路
【図１】
2010068135.tif 000003
【図２】
2010068135.tif 000004
【図３】
2010068135.tif 000005
【図４】
2010068135.tif 000006
【図５】
2010068135.tif 000007
【図６】
2010068135.tif 000008
【図７】
2010068135.tif 000009
【図８】
2010068135.tif 000010
【図９】
2010068135.tif 000011
【図１０】
2010068135.tif 000012
【図１１】
2010068135.tif 000013
【図１２】
2010068135.tif 000014
【図１３】
2010068135.tif 000015
【図１４】
2010068135.tif 000016
【図１５】
2010068135.tif 000017
【図１６】
2010068135.tif 000018
【図１７】
2010068135.tif 000019
【図１８】
2010068135.tif 000020
【図１９】
2010068135.tif 000021
【図２０】
2010068135.tif 000022
【図２１】
2010068135.tif 000023
【図２２】
2010068135.tif 000024
【図２３】
2010068135.tif 000025
【図２４】
2010068135.tif 000026
【図２５】
2010068135.tif 000027