バッファを用いた軽量擬似乱数生成器のグリッチ削減方法とハードウェア実装評価

全文

(1)Computer Security Symposium 2014 22 - 24 October 2014. バッファを用いた軽量擬似乱数生成器のグリッチ削減方法とハードウェア実装評価三上修吾 †，渡辺大 † † 株式会社日立製作所横浜研究所 244-0817 神奈川県横浜市戸塚区吉田町 292 番地 [email protected]. 崎山一男 ‡ ‡ 電気通信大学 182-8585 東京都調布市調布ヶ丘 1-5-1. あらましパッシブ型 RFID タグなどの小型機器に実装する暗号回路は，低消費電力であることが求められる．筆者らはシフトレジスタを基本構成とする軽量擬似乱数生成器のハードウェア実装において，バッファを付加し，内部状態を逐次的に更新することで，消費電力の主要因である信号線のトグル数を削減可能であることを示してきた．しかし，この実装では，カウンタ値に応じてレジスタの動作を規定するため，カウンタのインクリメントに起因するグリッチが発生する．本稿では，グリッチの発生を抑えるために，ハミング距離が常に１となるカウンタを設計し，そのカウンタを用いて軽量擬似乱数生成器を実装することで，トグル数を約 60 ％削減できることを示す．. Hardware Implementation and Evaluation of Lightweight Pseudorandom Number Generators with Buffer Considering Glich Reduction Shugo Mikami†, Dai Watanabe†. Kazuo Sakiyama‡. †Hitachi, Ltd., Yokohama Research Laboratory. 292, Yoshida-cho, Totsuka-ku, Yokohama-shi, Kanagawa-ken, 244-0817 JAPAN [email protected] ‡University of Electro-Communications 1-5-1 Chofugaoka, Chofu-shi, Tokyo-to, 182-8585 JAPAN. Abstract Low power consumption is a requirement to a cryptographic circuit for a passive RFID tag. We have studied that the signal toggle, which is the primary factor of the power consumption of the cryptographic circuit, can be reduced by updating the internal state of the lightweight pseudorandom number generators sequentially using an additional buffer. However, since the registers used in this hardware architecture are controlled with the counter, electronics glitches occur. The glitch is an undesired transition that occurs before the signal settles to its intended value. In this paper, we design a counter whose Hamming Distance is always 1. Then we show hardware evaluation results of the lightweight pseudorandom number generators with the counter. The results reveal that the signal toggles can be reduced about 60 %.. － 72 －.

(2) はじめに. ハミング距離が常に 1 となるカウンタを用いることで，信号線のトグルを最大約 60 % 削減可能近年，パッシブ型 RFID (Radio Frequency であることを示す．なお，カウンタを置き換え IDentification) タグの利用が進んでいるが [1]，るだけであるから，回路規模はほぼ変わらない．プライバシ問題などのセキュリティ上の課題に以下，2 節で Grain-80, Trivium, Enocoro-80 対応するため，RFID タグのセキュリティ強化の仕様概要を記載する．3 節で，[7] で筆者らがが求められている．RFID タグのセキュリティ用いた実装アーキテクチャについて述べる．4 を強化する一方策として，RFID タグに暗号回節で，グリッチの発生を抑えるカウンタについ路を搭載し，認証や通信データの秘匿を行う方て述べる．5 節で，ASIC 実装性能を示し，6 節法がある．でまとめる．パッシブ型 RFID タグはハードウェアリソースが限られていることと，リーダから照射される電波によって電力を得ることから，RFID タ 2 軽量擬似乱数生成器の仕様グに搭載する回路は軽量，省電力であることが本節では，Grain-80，Trivium と Enocoro-80 望まれている．これらの背景から，RFID 認証の仕様概要を記載する．詳細な仕様については，プロトコルや RFID タグを対象プラットフォー Grain 仕様書 [4]，Trivium 仕様書 [5]，Enocoro ムとした軽量暗号アルゴリズムが多数発表され仕様書 [6] を参照のこと．てきた [2]．筆者らは，RFID タグにおいて，乱数生成用途などへの利用が見込まれる軽量擬似乱数生成器 2.1 Grain-80 の仕様に着目し，その省電力実装を検討している [7]． Grain-80 は Hell 等が発表した擬似乱数生成既に，軽量擬似乱数生成器の Grain-80 [4]，Triv器であって，eSTREAM (ECRYPT Stream Ciium [5]，Enocoro-801 [6] はシフトレジスタを基本構成とする暗号アルゴリズムであるため， pher Project) [3]Profile 2 の一つに選定されている．入力は秘密鍵 80 ビットと初期ベクトル付加したバッファを用いて内部状態を逐次的に更新する実装アーキテクチャを採用することで， (以下，IV と記す) 64 ビットである．内部状態の大きさは 160 ビットで，160 ラウンドの初期消費電力の主要因である，信号線のトグルを約化を行った後，1 ビットずつ擬似乱数列を出力 60 % 削減可能であることを述べた．一方で，トグルの挙動を詳細に解析すると，する．内部状態は 80 ビット長の線形フィードバックカウンタのインクリメントに起因してグリッチシフトレジスタ (LFSR) と 80 ビット長の非線が発生していることが新たに分かってきた．グ形フィードバックシフトレジスタ (NFSR) からリッチとはハードウェア基本素子の過渡的な出構成される．初期値の入力では，NFSR へ鍵を力信号であり，消費電力の増加原因となる．バッ入力し，LFSR へ鍵と定数を入力する．LFSR ファを活用する実装アーキテクチャでは，カウと NFSR の値を出力関数に入力し，その出力をンタの値によって，内部状態を格納するレジス擬似乱数列とする．Grain-80 は 1 ビットの擬似タの挙動を制御する．そのため，カウンタのインクリメントにおいてグリッチが発生すると，乱数列を出力するたびに，LFSR の 1 ビットと NFSR の 1 ビットを更新する．NFSR は 5 入力カウンタ値の変動に影響され，レジスタの入力 1 出力の非線形関数と LFSR の出力値で更新さ信号が変動し，グリッチが発生する．れる．LFSR は 6 入力 1 出力の線形関数で更新そこで，本稿では，グリッチの発生を抑えるされる．初期化フェースでは，出力関数の出力カウンタの設計と，そのカウンタを適用した Grain-80，Trivium と Enocoro-80 の ASIC (Ap- 値は NFSR と LFSR の入力値としてフィードバックされ，擬似乱数列を出力しない． plication Specific Integrated Circuit) 実装評価. 1. 結果について述べる．インクリメントにおいて，. － 73 －. 1. Enocoro は株式会社日立製作所の登録商標です．.

(3) 2.2. Trivium の仕様. 3. Trivium は C.D. Canni` ere 等が発表した擬似乱数生成器であって，ISO 標準暗号 (ISO/IEC 29192-3) の一つに採択されている．入力は秘密鍵 80 ビットと IV80 ビットである．内部状態の大きさは 288 ビットで，1152 ラウンドの初期化を行った後，1 ビットずつ擬似乱数列を出力する．内部状態は長さの異なる 3 本の LFSR から構成される．初期値の入力では，鍵と IV は 2 本の LFSR へ入力され，残りのビットには定数を入力する．各ラウンドにおいて，3 本の LFSR はそれぞれの LFSR 内で 1 ビットシフトする．さらに，LFSR の値を非線形関数に入力し，その出力値を隣接する LFSR への入力とする．3 本の LFSR から 1 ビットずつ値を選び，出力関数に入力し，その出力値を擬似乱数列とする．初期化フェースでは，擬似乱数列を出力しない．. 実装アーキテクチャ. 本節では，バッファを活用して内部状態を逐次的に更新する省電力実装アーキテクチャの概要について述べる [7]．通常，線形フィードバックシフトレジスタを基本構成とする暗号アルゴリズムの実装では，すべての内部状態を同時に更新する実装アーキテクチャとする．この実装アーキテクチャをベースとして，バッファを追加し，バッファに内部状態を一時的に退避し，内部状態を逐次的に更新した後，最後にバッファに退避した値を内部状態に入力するのが基本的な構成である．図 1 にバッファを活用した実装アー counter. counter update function. LFSR. data update function. 2.3. Enocoro-80 の仕様 buffer. Enocoro-80 は株式会社日立製作所が 2007 年に開発した擬似乱数生成器であって，ISO 標準暗号 (ISO/IEC 29192-3) の一つに採択されている．入力は秘密鍵 80 ビットと IV64 ビットである．内部状態の大きさは 176 ビットで，40 ラウンドの初期化を行った後，8 ビットずつ擬似乱数列を出力する．内部状態は 160 ビット長の LFSR と 16 ビット長のステートと呼ばれるレジスタから構成される．初期値の入力では，LFSR へ鍵，IV を入力し，残りは定数ビットを入力する．ステートの下位 8 ビットを擬似乱数列をして出力する． Enocoro-80 は 8 ビットの擬似乱数列を出力するたびに，LFSR とステートを更新する．LFSR は線形関数とステートの上位 8 ビットの値で更新される．ステートは LFSR の値を入力とする非線形関数の出力値で更新される．非線形関数は，8 ビット入力 8 ビット出力の非線形変換と線形関数で構成される．初期化フェーズでは擬似乱数列を出力しない．. output. 図 1: バッファを用いた実装アーキテクチャの基本構成図 . キテクチャの基本構成図を示す．図中，LFSR は線形フィードバックシフトレジスタ，buffer はバッファ，data update function は内部状態の更新関数である．また，counter はカウンタ値を格納するレジスタ，counter update function はカウンタの更新関数である．counter の出力値は，LFSR と buffer へ制御信号として入力される．暗号アルゴリズムによって，LFSR の長さや本数，更新関数の種類などは異なるが，LFSR と更新関数を主要な要素とする基本構造は同じである．また，図を簡略化するため，LFSR への初期値の入力線は記載を省略しているが，暗号モジュール外部から入力される鍵や IV を入. － 74 －.

(4) 力する．擬似乱数列を毎ラウンド 16 ビット生成し，バッファの大きさは 16 ビットである．以下に，初期化フェーズにおける内部状態の更新手順を示す．. 1. バッファに更新関数の出力値を格納． 2. LFSR をバッファ長/クロックずつ右へシフト． 3. LFSR の左端に手順 1. でバッファに格納した値を入力．この一連の処理により，ラウンド処理が終了する．擬似乱数出力フェーズでは，まず，生成した擬似乱数列をバッファに格納し，出力する．その後，初期化フェーズと同様の処理を行う．. 4 4.1. いて論理合成を行い，生成したネットリストを用いて動作シミュレーションを行った．図 2 は動作シミュレーションにおいて，カウンタ値が 11 から 12 へ遷移する際の詳細な挙動を記した図である．カウンタ値は 4 ビットで，信号線を上位から cnt[3], cnt[2], cnt[1], cnt[0] として記している．図 2 より，信号線は 1 本ずつ，時間差をつけて値が変化していることが分かる．従って，カウンタ値は 11 から直接 12 に遷移するのではなく，11 から 15，13，12 の順に過渡的な複数の値を経て，遷移していることがわかる．図 1 に示す実装アーキテクチャでは，カウンタの値によって，LFSR とバッファの動作を制御している．そのため，過渡的な値であってもカウンタ値が変わることによって，LFSR とバッファの入力信号線の値が変わるため，グリッチが発生する．. カウンタグリッチ. 4.2. カウンタの値はクロック毎にインクリメントする．通常のカウンタ設計では初期値を 0 とし，カウンタ値を 1 ずつインクリメントする．処理ステップが一巡すると，カウンタ値を再び 0 に戻す．カウンタのビット幅は処理ステップ数によって異なるが，通常は複数ビットである．従って，インクリメントにおいて，カウンタの複数本の信号線が動作するケースが多い．. cnt[3] cnt[2] cnt[1] cnt[0] 図 2: カウンタにおけるグリッチ . カウンタの設計. 動作シミュレーションによって，図 2 に示したように，カウンタの信号線は 1 本ずつ値が変わることが分かった．信号線の値が 1 本ずつ変わるということは，ハミング距離が 1 となる複数の段階を経て，カウンタ値が変化するということである．従って，ハミング距離が常に 1 となる巡回カウンタを設計すれば，過渡的なカウンタ値が発生しないため，グリッチの抑制が期待される．表 1 に Grain-80 と Enocoro-80 用に設計したカウンタを記す．ラウンド数とそれに対応するカウンタ値を記す．カウンタ値を 0,1,2 と変化されるのではなく，0000,0001,0011 の順に変化させることで，ハミング距離を常に 1 に保っている．表 2 に Trivium 用に設計したカウンタを記す．Trivium は Grain-80 と Enocoro-80 に比較して，内部状態が大きいため，処理ステップ数が多い．従って，カウンタのビット幅も 5 ビットへ増やしている．. Grain-80, Trivium, Enocoro-80 を図 1 のアーキテクチャで実装し，5 節で述べるツールを用. － 75 －.

(5) 表 1: Grain-80 と Enocoro-80 のカウンタ Round Counter value. # 0 1 2 3 4 5 6 7 8 9 10 11 12 13. 5. bit 0000 0001 0011 0111 0101 1101 1001 1011 1010 1000 1100 0100 0110 0010. 表 2: Trivium のカウンタ Round Counter value. # 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21. ASIC 実装評価. 本節では，Grain-80，Trivium と Enocoro-80 の ASIC 実装評価結果を示す．コンパイラとして Synopsys1 Design Compiler2 (Version C-2009.06SP5) で論理合成を行った．ライブラリには，TSMC 社の 90 nm high performance ライブラリを使用した．また，入力データの遅延時間を 0.4 ns，出力データの遅延時間を 0.4 ns に設定した．評価項目は回路規模，サイクル数，トグル数とした．サイクル数はデータの入出力に必要なサイクル数を含めて評価した．トグル数は回路素子のスイッチング回数を算出することで評価した．ランダムな入力パターンを 100 通り準備し， cadence3 の Simvision4 version 05.83-s015 を用いて回路動作をシミュレートし，VCD (Value Change Dump) ファイルを作成した．VCD ファイルから最大トグル数を標本値として算出し，標本値を用いて母平均と母分散を信頼係数 99 % で信頼区間で推定した後，3σ 範囲を用いてトグル数を推定した．実装結果を表 3 に示す．表中，FF はフリップフロップ (flip-flop) ，Combi は組合せ論理回路を示す．Arch.1 は通常設計のカウンタを用いた. － 76 －. 1. 2. 3. 4.. bit 00000 00001 00011 00111 00101 01101 01001 01011 01111 11111 10111 10011 11011 11001 11101 10101 10001 10000 10010 11010 01010 00010. Synopsys は Synopsys 社の登録商標です． Design Compiler は Sysnopsys 社の商品名称です． cadence は Cadence Design Systems 社の登録商標です． Simvision は Cadence Design Systems 社の登録商標です．.

(6) 表 3: Hardware performance of pseudorandom number generators Algorithm Architecture Area Clock cycle Signal toggle (GE) ( ♯ toggle) Total FF Combi Grain-80 Arch. 1 3900 1390 2510 299 99 Arch. 2 3850 1390 2460 299 43 Trivium Arch. 1 4050 2230 1820 1595 42 Arch. 2 4130 2260 1870 1595 32 Enocoro-80 Arch. 1 3640 1480 2150 418 46 Arch. 2 3660 1490 2170 418 37. 実装アーキテクチャを示し，Arch.2 はハミング距離が常に 1 となるカウンタを用いた実装アーキテクチャである．. 6. まとめ. 本稿では，軽量擬似乱数生成器の Grain-80, Trivium, Enocoro-80 の，バッファを活用して逐次的に内部状態を更新する実装アーキテクチャにおいて，グリッチの発生を抑えるためのカウンタの設計と ASIC 実装評価を行った．ハミング距離が常に 1 となるカウンタを用いることで，グリッチの発生が抑えられ，信号トグルを最大約 60 % 削減できることを示した．. 謝辞本研究成果は，独立行政法人情報通信研究機構 (NICT) の委託研究「軽量暗号プロトコルの省リソースデバイスに対する実装効率向上の研究開発」により得られたものです．同委託研究に関わるすべての関係者に感謝いたします．. 参考文献 Journal, [1] RFID rfidjournal.com/.. http://www.. [2] RFID Security & Privacy Lounge, http: //www.avoine.net/rfid/index.php.. － 77 －. [3] The eSTREAM Project, available at http://www.ecrypt.eu.org/stream/. [4] M. Hell, T.Johansson, and W.Meier, “Grain - A Stream Cipher for Constrained Environments”, available at http://www.ecrypt.eu.org/stream/ p3ciphers/grain/Grain p3.pdf. [5] C.D. Canni` ere, and B. Preneel, “TRIVIUM Specifications”, available at http://www.ecrypt.eu.org/stream/ p3ciphers/trivium/trivium p3.pdf. [6] 株式会社日立製作所，擬似乱数生成器 Enocoro, available at http://www.hitachi.co.jp/rd/yrl/ crypto/enocoro/index.html. [7] 三上修吾, 渡辺大, 崎山一男, “バッファを用いた軽量擬似乱数生成器の実装と評価,” In The 31th Symposium on Cryptography and Information Security –SCIS 2014, 2014..

(7)