(57)【要約】【課題】耐タンパ性能が確保されていない汎用MCU上で、安全なダウンロード、アップロード、及びセキュアブートを行うことを可能とする、拡散関数を利用したソフトウェアによる電力解析強度を向上させる暗号化アルゴリズムを提供する。【解決手段】耐タンパ性能が確保されていない汎用MCU上で、安全なダウンロード、アップロード、及びセキュアブートを行うことを可能とする、拡散関数を利用したソフトウェアによる電力解析強度を向上させる暗号化アルゴリズムを提供する。【選択図】図１
2017173702.tif 000002
【特許請求の範囲】
【請求項１】
暗号化対象メッセージに付されたハッシュ値を拡散関数を利用してメッセージとは独立したマスク値を生成し、本マスクの暗号化結果をメッセージと排他的論理和を取ることで暗号化し、更にブロック処理毎にマスク値に対して暗号化することで、電力差分解析強度を向上させる暗号化アルゴリズム。
【請求項２】
上記暗号化アルゴリズムにおいて、マスク暗号化時に利用する鍵もブロック処理毎に拡散関数を利用して変換させることを特徴とする前記第1項記載の暗号化アルゴリズム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、拡散関数を利用したソフトウェアによる電力解析強度を向上させる暗号化アルゴリズムに関する。
【背景技術】
【０００２】
電力解析に対する根本策としては、ハードウェアアプローチが一般的であり、DPAの発明者が創業したCryptography Research［CRI］社が『バスを2重化［一方はNOT］する』ことでoccurs(e, s)を消し込む基本特許を押さえており、Infineon等セキュアMCUベンダが契約を締結しているが、回路規模が大きく、通常の実装には適さない。
その他の方策として、一般的にdelay(e, s)をランダム化するためにクロック・デューティを内部変動させる方式、及びf(e, t)をマスクするために大きなノイズをランダムに重畳する方式が知られているが、やはり回路規模が問題となる。
一方、ソフトウェアアプローチとしても、一部、AES内部処理の排他的論理和演算順序を入れ替える等、delay(e, s)をランダム化する方法は検討されてきたが、根本的な対策は存在していない。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本発明の目的は、近年ITセキュリティの分野で注目を集めているSPA［Static Power Analysis：単純電力解析］、及び発展形であるDPA［Differential Power Analysis：電力差分解析］に対する強度を向上させるための暗号プロトコル、及びソフトウェア構造を提供することである。
これら攻撃方式は、デバイスに直接攻撃を仕掛ける方式ではなく、『サイドチャネル・アタック』と呼ばれる『アルゴリズム実装方式に起因した電圧、熱等の変化から内部情報を類推する方式』に属し、以降に示すようにデータ処理時の『消費電力の時間変化』が利用される。
【０００４】
『SPAの原理』
【０００５】
Kocher氏が提案した初期のSPAは、全入力値または出力値を必要とする非現実な方法だったが、その後の研究で入力値または出力値に関する情報を得る必要がない次の2ステップからなる攻撃法が提案され、脅威として市場認知されている。
【０００６】
ステップ1：鍵スケジュール部の特定化
【０００７】
攻撃者の第一目標は、得られた電力消費グラフの中で鍵スケジュール部に関係する部分を特定することで、そのために以下の2ステップの処理が実行される。
【０００８】
1］単一デバイスで入力項目を変化させた処理を多数回実行して電力消費特性を測定し、得られた複数の電力消費パターンにおける同一サイクルを比較し、電力消費値に大きなばらつきが存在するサイクルを鍵スケジュール部に関係しないサイクルとして除外する。
⇒ 単一デバイスでは鍵スケジュール処理内容は同一であり、鍵スケジュール部に関係するサイクルでの電力消費値は入力項目に依存しないため
【０００９】
2］発明の概要上記比較を鍵が異なる複数のデバイスに対して行い、絞り込んだサイクルにおいて、更に電力消費パターン間の同一サイクルを比較し、電力消費値のばらつきが小さいサイクルを鍵スケジュール部に関係しないサイクルとして除外する。
⇒  鍵が異なる各デバイスにおいて鍵スケジュール処理内容は異なる、つまり鍵スケジュール部に関係するサイクルにおける電力消費値はデバイス毎に異なるため
【００１０】
鍵スケジュール部に関係するサイクルの絞り込みだが、例えばDESでは16ラウンドがほぼ認識可能なので、攻撃者にとって大きな障害とはならないことが知られている。
【００１１】
ステップ2：秘密鍵の取出し
【００１２】
攻撃者の最終目標は、上述の攻撃により特定したサイクルから秘密鍵を取り出すことである。
【００１３】
一般的に、RAMリソースには制約があるため、暗号化に使用される全ての副次的な鍵［ラウンド鍵］をRAMに保持しておくことは困難で、実装時には各鍵を用いられる直前にRAMへ書込む方式が一般的である。
【００１４】
この際、書込み処理時における電力消費量は"1"を書き込んだ回数に関係するので、鍵の書込み処理時の電力消費量から鍵に含まれる"1"の個数が判明する。
【００１５】
つまり、鍵の書込み処理時の電力消費量を観測することで、鍵のハミング重みが計測可能で、情報理論的には8ビットのハミング重み計測1回当たりで平均2.54ビットの情報が取り出される点が根本的な問題となる。
【００１６】
もちろん、このハミング重み計測には多くの誤りが含まれている可能性があるが、単一デバイス［同一秘密鍵］での消費電力観測を多数行い、平均化することで誤りを減少させることが可能となる。
【００１７】
以下にDESの秘密鍵の取り出しについて具体例を示す。
【００１８】
アルゴリズム上、DESは56ビットの秘密鍵、16のラウンドを持ち、各ラウンドn［n = 1, 2, …16］で48ビットの秘密鍵Knは6ビットのサブ鍵に分割される。
【００１９】
一度にデバイス内のRAMへ書き込む単位を8ビットと仮定すると、RAMに保持される8ビットのハミング重み計測を各ラウンドにつき6回実行可能となる。
【００２０】
つまり、攻撃者は16ラウンドにわたるサブ鍵のハミング重み計測により、秘密鍵の各ビットを変数とする56変数の96個の線形方程式を得ることができ、得られた方程式を解くことにより56の変数の値、つまり秘密鍵が判明することになる。
【００２１】
もちろん、この攻撃法の問題点としては以下の2課題があげられる。
1］得られた方程式の解が不定になる可能性が存在する
2］ハミング重み計測誤りを効率良く検出すること
【００２２】
ただし、前者についてはDESアルゴリズム上、得られた方程式の解は唯一解であり、後者については例えば以下の2方法が適用可能となる。
1］求める変数が56個であるのに対し、得られる方程式は96個であることから、誤り訂正符号において用いられている手法を利用する
2] DESの構造上、得られた方程式を28変数48方程式に分離させることができるので、28ビットを全数探索する
【００２３】
『DPAの原理』
【００２４】
電力差分解析は、算術演算や論理演算等の処理においてデバイスの消費電力パターンと入力ビットに何らかの相関があることを利用した電力解析攻撃であり、AESでは0ラウンド鍵がアタック対象となることが知られている。
【００２５】
入力nビット［op1, op2, …, opn］の中でop1が処理Iにおける消費電力PIと相関を持つとすると、op1の値により処理Iにおける消費電力は次式で表せる。
PI (0) = Eop2,…,opn［P(I, 0, op2,…,opn)］
PI (1) = Eop2,…,opn［P(I, 1, op2,…,opn)］
ただし、Eop2,…,opn：op1以外の入力op2,…,opnを全通り入力したときの平均
【００２６】
ここで、処理Iにおける消費電力PIとop1が相関を持つとは、言い換えるとPI (0)≠PI (1)であって、D = PI (0)- PI (1)であるDが雑音に比べて十分大きい場合、電力差分解析は非常に強力な攻撃となる。
【００２７】
基本的に電力差分解析は以下の3ステップから構成される。
【００２８】
1］ステップ1：ターゲット指定
デバイス電力モデルに挙げた処理のうち、所定のサイクルの、所定の処理に注目する。
ここでは、先ずデバイス内の秘密鍵の予想値Kを設定し、次に入力値のaビット目のみ変えた場合の消費電力値の差Daを計算し、Daが大きい入力値を攻撃に使用する。
【００２９】
2］ステップ2：データ収集
様々な入力値を用いて消費電力パターンのサンプルを多数入手する。
【００３０】
3］ステップ3：データ解析
入力値のaビット目が"0"のグループと "1"のグループをそれぞれG0、G1とし，ステップ2で得られた消費電力パターンをG0、G1に分類する。
そして、Gi(i = 0, 1)に含まれる各サンプルでの消費電力値の和をPGiとすると、|PG0 - PG1|を最大にする秘密鍵の予想値Kが正しい値となる。
予想値が正しい場合|PG0 - PG1|≒D・n/2となり，逆に誤っている場合には|PG0 - PG1|は0に近づく。
【００３１】
『デバイス電力モデル』
【００３２】
近年のデバイスではCMOSプロセスが使用されているため、その特性としてデバイス上で何らかの変化が生じた場合だけ電力が消費され、状態維持するための消費電力は少ない傾向を示し、一般的には以下に示す処理が特徴的な電力消費パターンを示すことが知られている。
1］加算、減算、乗算
2］ビット毎の論理演算
3］RAM への書込み 
4］EEPROMへの書込み 
5］RAM、EEPROMからの読出し
【００３３】
一般的なデバイスは内部あるいは外部クロックにより駆動され、通常は全ての動作が次のクロックの立上がり前に終了する。
【００３４】
なお、DPA対策用のノイズ生成器等はクロックに関係なく連続的にランダムにかつ小さな電力消費を行うことが前提となる。
【００３５】
また、電力を消費する一連のイベントは、クロックに同期してチップ内部のマイクロ命令に従って駆動される。
【００３６】
1クロックサイクル間の一連のイベントを決定するのはチップ内部の状態であって、ここではこれを関連状態と呼ぶ。
【００３７】
クロック・エッジからのチップ全体の瞬間電力消費は、各々のイベントの瞬間電力消費の組み合わせで得られるが、実際の各イベントの消費電力はカップリング効果ばかりでなく、各マクロセルのレイアウト、気温、電圧等にも依存し、かつそのタイミングも複雑となる。
【００３８】
ただし、ここでは簡略化のために電力消費の総和が各イベントの電力消費の総和であると仮定します。
【００３９】
以下に、何らかの固定コードの実行パスの中のある命令のあるサイクルを考えてみることとする。
【００４０】
ここでは以下のパラメータ及び関数を考慮する。
S：このサイクルに到達する際の関連状態(relevant state)の集合
E：このサイクルの中で起こりうる全イベント空間
occurs(e, s)：各s∈S及びe∈E について、状態sにおいてイベントeが起きた時に1、そうでない時に0となる2値関数
delay(e, s)：状態sにおいてクロックのエッジからイベントeが起きるまでの遅延
f(e, t)：イベントeが起きたときの電力消費インパルスtの時間に関する関数
⇒この場合イベントが起きる時間がt = 0であり，またt < 0に対しf(e, t) = 0である
【００４１】
上記条件下では、このデバイスのサイクルの状態sにおけるクロックのエッジからの時間tにおける電力消費関数P(s, t)は以下のように表せる。
【００４２】
(図)４ 式１
【００４３】
ただし、N(e, t)：イベントeの電力消費に伴うガウス雑音
Nd(e, s)：遅延関数に影響するガウス雑音
Nc(t)：外部ガウス雑音
【００４４】
上式は、電力消費関数と状態sが強い関係にあることを示しており、電力差分解析はこの電力消費の非対称性を利用した方式と言える。
【００４５】
特に安価なデバイスでは状態空間が小さく、この非対称性が顕著となるため、攻撃に対して脆弱となることが知られている。
【課題を解決するための手段】
【００４６】
「汎用MCU上のソフトウェアで安全に実装可能である」という要件を満足させるためには、次の要件を満足させることが必要となる。
1] DPA対策として入力nビット［op1, op2, …, opn］を外部遮蔽し、入力と消費電力とのパターンを外部遮蔽する
2] ソフトウェアに対する攻撃［リバースエンジニアリング］を考慮し、鍵の寿命を極めて短く設定可能な暗号プロトコルとする。
【００４７】
先ずメッセージ生成者はデフォルトの共通鍵K0、RSA等の公開鍵暗号用の鍵ペア、及びデフォルトの拡散関数D0( )を生成し、メッセージ受信者にK0、公開鍵及びD0( )をメッセージ受信者に通知する。
【００４８】
なお、公開鍵は通常のPKIとは異なり、第三者に公開する必要は無く、必要に応じてTPM等の安価なセキュリティモジュールに格納しても良い。
【００４９】
次にメッセージ生成者は次の手順で暗号文を生成する。
【００５０】
手順_1：平文Pに対するハッシュ値H［メッセージダイジェスト］を生成する。なお、ハッシュ関数としてはSHA-1あるいはSHA-2等の関数が利用可能である。また、平文Pにはアプリケーション層で利用されるメッセージの他に、新規拡散関数D1( )［Object Code］及び暗号鍵Kを格納可能とし、アルゴリズムと鍵の更新を可能とする。
【００５１】
手順_2：ハッシュ値Hを拡散関数D0( )とし、D0( H )を生成する。なお、拡散関数としてはAES等の暗号関数が利用可能である。［鍵は関数埋め込み等］
【００５２】
手順_3：後述するDPA対策を実施した暗号関数Enc( )で平文Pを暗号化し、暗号文Cを生成する。
【００５３】
手順_4：ハッシュ値Hに対する署名Sを生成し、Cと共にメッセージ受信者に配送する
【００５４】
暗号関数Enc( )の構成であるが、鍵Kに対するDPA対策として、下図に示すように、入力と消費電力とのパターンを外部遮蔽するために、入力される平文 / 暗号文［Input_n］とは完全に独立した系での暗号化を実施する。
【００５５】
暗号方式としては、広範に知られている暗号利用モードの一つであるCTRモードと同様に、入力と暗号の出力結果であるマスク値［MASK_n］の排他的論理和を出力とする構造であるため、暗号と復号が同一アルゴリズムで実現可能となり、暗号と復号アルゴリズムが異なるAES等ではメモリリソース上の優位性が確保できる。
【００５６】
また、CTRモードとは異なり、暗号入力が無規則となるため、入力と消費電力とのパターンを外部遮蔽することが可能となる。
【００５７】
更に、マスク生成の初期値Hは公開鍵を知り得ない限り取得不可能であるため、攻撃者が入手可能な情報を最小化することも可能となる。
【００５８】
更に、リバースエンジニアリングを想定し、共通鍵Kと拡散関数Dを交換可能とすることで、定期的にこれら要素の更新を行うことで、攻撃者のアタック意欲を喪失させることが可能となる。
【発明の効果】
【００５９】
SPAあるいはDPA等に対する耐タンパ性能が確保されていない汎用MCUにおいても、安全なダウンロード、アップロード及びセキュアブートを行うことが可能となる。また、ダウンロードにより拡散関数、及び鍵を更新可能とすることで、リバースエンジニアリングを困難にすることできる。
【図面の簡単な説明】
【００６０】
【図１】暗号化プロセス
【図２】暗号アルゴリズムEnc( )［構成例1］
【図３】暗号アルゴリズムEnc( )［構成例2］
【図４】式１
【図１】
2017173702.tif 000003
【図２】
2017173702.tif 000004
【図３】
2017173702.tif 000005
【図４】
2017173702.tif 000006