早稲田大学大学院 基幹理工学研究科
博 士 論 文 概 要
論 文 題 目
暗号集積回路に対するスキャンベース サイドチャネル攻撃に関する研究 Scan-based side-channel attacks on
cryptographic integrated circuits using scan signatures
申 請 者
藤代 美佳 Mika FUJISHIRO
情報理工・情報通信専攻 情報システム設計研究
2015 年 12 月
No.1
近 年 で は I C T の 発 展 に よ り あ ら ゆ る 情 報 を デ ー タ と し て 扱 う よ う に な り ，扱 う 情 報 の 価 値 は 大 き く な っ て い る ． 情 報 の 改 ざ ん ， 漏 洩 が 多 発 す る 中 ， 想 定 さ れ る 攻 撃 対 象 は 金 銭 や 個 人 情 報 か ら 社 会 イ ン フ ラ ま で 及 び ， 人 身 や 国 家 の 安 全 性 を も 揺 る が す 事 態 に な っ て い る ． そ の た め 多 種 多 様 な 攻 撃 を 想 定 し た セ キ ュ ア な シ ス テ ム の 構 築 が 必 要 で あ る ．S u i c a や ク レ ジ ッ ト カ ー ド 等 の ス マ ー ト カ ー ド は ， 交 通 ，金 融 ，行 政 等 多 く の 分 野 に お い て 日 常 的 に よ く 使 わ れ て い る ．ま た 2 0 1 6 年 1 月 に は マ イ ナ ン バ ー カ ー ド の 導 入 が 決 定 し て い る ．こ れ ら ス マ ー ト カ ー ド に 対 し ， ハ ー ド ウ ェ ア の 特 性 を 利 用 し た サ イ ド チ ャ ネ ル 攻 撃 の 危 険 性 が 指 摘 さ れ て い る ． 今 日 で は 情 報 を 確 実 に 保 護 す る た め に は 暗 号 技 術 だ け で な く ハ ー ド ウ ェ ア の 特 性 も 考 慮 し な け れ ば な ら な い ． ス マ ー ト カ ー ド は 価 値 ・ 機 密 性 が 高 い 情 報 を 扱 う た め ， 機 密 情 報 を 確 実 に 保 護 す る 安 全 な 暗 号 集 積 回 路 の 設 計 が 求 め ら れ て お り ， 暗 号 技 術 と ハ ー ド ウ ェ ア の 特 性 の セ キ ュ リ テ ィ の 研 究 は 必 須 で あ る ．
安 全 な 暗 号 集 積 回 路 を 設 計 す る た め に は ，回 路 の 脆 弱 性 を 解 明 す る 必 要 が あ る ． こ れ ま で に 暗 号 集 積 回 路 に 対 す る 多 様 な 攻 撃 が 検 討 さ れ て お り ， テ ス ト 用 の ス キ ャ ン チ ェ イ ン を 利 用 し た ス キ ャ ン ベ ー ス 攻 撃 の 危 険 性 が 指 摘 さ れ て い る ． ス キ ャ ン チ ェ イ ン は L S I 中 の レ ジ ス タ を 直 列 に 接 続 し ， 外 部 か ら レ ジ ス タ を 直 接 制 御 ・ 観 測 可 能 に し た テ ス ト 技 術 で あ る ． ス キ ャ ン チ ェ イ ン か ら 取 得 し た レ ジ ス タ の 値 を ス キ ャ ン デ ー タ と い い ， ス キ ャ ン デ ー タ 上 の 値 と 実 際 の レ ジ ス タ と の 対 応 関 係 は 設 計 者 以 外 に は 分 か ら な い ． ス キ ャ ン ベ ー ス 攻 撃 で は ， ス キ ャ ン デ ー タ と レ ジ ス タ の 対 応 関 係 を 求 め る こ と が 最 大 の 鍵 と な る ． ス キ ャ ン ベ ー ス 攻 撃 に お け る 従 来 手 法 は ス キ ャ ン チ ェ イ ン に 接 続 さ れ た レ ジ ス タ が 特 定 の 構 成 に な っ て い る こ と を 前 提 と し て い る 場 合 が 多 い ． し か し ， 通 常 L S I 上 の ス キ ャ ン チ ェ イ ン は 様 々 な 回 路 の レ ジ ス タ を 接 続 し て い る ． こ の よ う に 攻 撃 手 法 が 特 定 の 条 件 下 で の み 有 効 で あ っ て も ， ス キ ャ ン ベ ー ス 攻 撃 の 危 険 性 を 完 全 に は 指 摘 し き れ て い な い ． 脆 弱 性 を 解 明 す る た め に は ， 攻 撃 手 法 が 有 効 に な る 条 件 を 限 定 せ ず ， 現 実 的 な 条 件 を 設 定 し た 上 で 攻 撃 手 法 を 検 討 す べ き で あ る ．
本 論 文 で は 暗 号 集 積 回 路 の セ キ ュ ア 設 計 を 目 的 と し て い る ． 安 全 な 暗 号 集 積 回 路 は ，「 強 固 な 暗 号 ア ル ゴ リ ズ ム 」 を 「 情 報 を 漏 え い し な い 適 切 な 仕 組 み で 実 装 」 し て い る こ と が 求 め ら れ る た め ，「 暗 号 ア ル ゴ リ ズ ム 」の 数 理 的 な 性 質・脆 弱 性 と
「 実 装 法 」 に お け る 脆 弱 性 を 評 価 す る ． ス ト リ ー ム 暗 号 ， ブ ロ ッ ク 暗 号 ア ル ゴ リ ズ ム を 実 装 し た 暗 号 集 積 回 路 に 対 し て ス キ ャ ン チ ェ イ ン の 構 造 に 依 存 し な い ス キ ャ ン ベ ー ス 攻 撃 手 法 を 提 案 す る こ と で ， 暗 号 集 積 回 路 の 「 暗 号 ア ル ゴ リ ズ ム 」 に お け る 脆 弱 性 ，「 実 装 法 」に お け る 脆 弱 性 を 指 摘 す る ．多 様 な 攻 撃 を 想 定 す る こ と で 暗 号 集 積 回 路 に お け る 脆 弱 性 を 解 明 し ， 防 御 設 計 に お け る 必 要 十 分 条 件 を 明 ら か に す る こ と が で き る ．
本 論 文 は 6 章 で 構 成 さ れ る ．
第 1 章 で は 本 論 文 の 背 景 ， 意 義 ， 概 要 を 示 す ．
第 2 章 で は サ イ ド チ ャ ネ ル 攻 撃 に 関 す る 研 究 を 紹 介 す る ． 暗 号 ア ル ゴ リ ズ ム の 特 性 だ け で な く ハ ー ド ウ ェ ア の 特 性 を 利 用 し た サ イ ド チ ャ ネ ル 攻 撃 が 注 目 さ れ て い る ． 既 存 研 究 と し て ， 暗 号 L S I の 消 費 電 力 を 計 測 ， 解 析 す る 差 分 電 力 解 析 を 扱 っ た K o c he r ら の 手 法 ，M c E v o y ら の 手 法 ，B e l a i d ら の 手 法 ， 桶 屋 ら の 手 法 が あ る ． 故 障 を 発 生 さ せ る こ と で 得 ら れ た 出 力 を 利 用 す る フ ォ ー ル ト 解 析 攻 撃 に 関 す る 研 究 と し て ，B o n e h ら の 手 法 ，B i h a m ら の 手 法 が あ る ． ス キ ャ ン ベ ー ス 攻 撃 に お い て は ス ト リ ー ム 暗 号 に 対 す る 手 法 と し て ，A g r a w al ら の 手 法 ，L i u ら の 手 法 ， M u k ho p ad h y a y ら の 手 法 が あ る ． ま た ブ ロ ッ ク 暗 号 に 対 す る 手 法 と し て Ya n g ら の 手 法 ， 奈 良 ら の 手 法 ， 小 寺 ら の 手 法 が あ る ．
第 3 章 で は ス ト リ ー ム 暗 号 に 対 す る ス キ ャ ン ベ ー ス 攻 撃 手 法 を 提 案 し ， 評 価 す る ．ス ト リ ー ム 暗 号 評 価 プ ロ ジ ェ ク ト で 推 奨 暗 号 に 認 定 さ れ た Tr i v i um を 対 象 に ス キ ャ ン ベ ー ス 攻 撃 手 法 を 提 案 す る ．Tr i v i u m は 3 本 の シ フ ト レ ジ ス タ か ら 構 成 さ れ ， 内 部 の 演 算 は ビ ッ ト 同 士 の A N D 演 算 と X O R 演 算 の み で あ る た め ， 構 造 が 単 純 で 高 速 に 動 作 す る ． 秘 密 鍵 K ( 8 0 b i t )と I V ( i n i t i al i z a t i o n v e c t o r : 初 期 化 ベ ク ト ル) ( 8 0b i t )に よ り 2 8 8 個 の 内 部 状 態 レ ジ ス タ が 初 期 化 さ れ ， 内 部 状 態 を 更 新 し な が ら キ ー ス ト リ ー ム の ビ ッ ト を 生 成 す る ．Tr i v i u m の 性 質 上 ， 攻 撃 者 が 解 読 対 象 の 暗 号 文 を 出 力 し た 直 後 の Tr i v i u m L S I の 内 部 状 態 値 を 取 得 し た 場 合 ，過 去 の い か な る 内 部 状 態 も 算 出 で き ， キ ー ス ト リ ー ム を 復 元 で き る ． 得 ら れ た キ ー ス ト リ ー ム と 暗 号 文 を 順 に 排 他 的 論 理 和 す る こ と で 元 の 平 文 を 取 得 で き る ． 暗 号 文 か ら 平 文 へ の 復 元 は ， い か に 暗 号 文 が 出 力 さ れ た 直 後 の 内 部 状 態 値 を 取 得 す る か に 還 元 さ れ る ． そ こ で ス ト リ ー ム 暗 号 L S I に 任 意 の 秘 密 鍵 と I V を 入 力 で き る こ と を 利 用 す る ． 秘 密 鍵 と I V の 値 を 入 力 ペ ア と し て 多 数 用 意 し ， 各 入 力 に 対 し Tr i v i um L S I を 数 サ イ ク ル 動 作 さ せ る と き ， あ る 1 ビ ッ ト レ ジ ス タ の 入 力 に 対 す る 値 の 変 化 ， 動 作 さ せ た サ イ ク ル 数 に 対 す る 値 の 変 化 は ， そ の レ ジ ス タ 固 有 の 値 に な る ． こ の 固 有 の 値 を ス キ ャ ン シ グ ネ チ ャ と 呼 ぶ ．Tr i v i u m の 内 部 状 態 レ ジ ス タ に 対 し そ れ ぞ れ ス キ ャ ン シ グ ネ チ ャ を シ ミ ュ レ ー タ で 計 算 し て お き ， 同 様 の 条 件 下 で 実 際 の L S I 回 路 か ら 取 得 し た ス キ ャ ン デ ー タ と 比 較 す る こ と で レ ジ ス タ と ス キ ャ ン デ ー タ 上 の ビ ッ ト の 対 応 を 解 析 で き る ． こ の 手 法 で は ， ス キ ャ ン デ ー タ に Tr i v i u m の レ ジ ス タ 以 外 の レ ジ ス タ の 値 が 含 ま れ て い て も ， 高 々1 ビ ッ ト の 値 の 変 化 に の み 着 目 し て い る た め ，内 部 状 態 レ ジ ス タ の ビ ッ ト の 位 置 を 特 定 で き る ． ス キ ャ ン デ ー タ の ビ ッ ト 対 応 が 一 度 求 ま れ ば ，Tr i v i um L S I が 暗 号 文 を 出 力 し た 直 後 の ス キ ャ ン デ ー タ か ら Tr i v i u m の 内 部 状 態 レ ジ ス タ の 各 値 を 求 め ら れ る ． Tr i v i um の 内 部 状 態 レ ジ ス タ 値 が 求 ま れ ば ， 過 去 の 内 部 状 態 ， キ ー ス ト リ ー ム を 復 元 で き ，Tr i v i um L S I が 出 力 し た 暗 号 文 と 排 他 的 論 理 和 す る こ と で ， 平 文 を 復 元 で き る ． 評 価 実 験 に よ り ， 提 案 手 法 は ス キ ャ ン デ ー タ に 他 の 回 路 の ビ ッ ト が 含 ま れ て い て も ， ビ ッ ト 対 応 解 析 可 能 と 確 認 し た ． ま た ，Tr i v i u m の 内 部 状 態 レ ジ
ス タ 2 8 8 個 の ビ ッ ト 対 応 解 析 に は ，特 定 の 入 力 を 設 定 し て キ ー ス ト リ ー ム 生 成 フ
No.3
ェ ー ズ か ら サ イ ク ル 毎 に ス キ ャ ン デ ー タ を 1 3 個 取 得 す れ ば 良 く ， 解 析 時 間 は 0. 1 3 9 秒 で 済 み ， 最 も 効 率 的 に 求 め ら れ る こ と を 確 認 し た ．
第 4 章 で は ブ ロ ッ ク 暗 号 に 対 す る ス キ ャ ン ベ ー ス 攻 撃 手 法 を 提 案 し ，評 価 す る ． 攻 撃 対 象 と す る ブ ロ ッ ク 暗 号 L E D は 6 4 ビ ッ ト か ら 1 2 8 ビ ッ ト の 秘 密 鍵 を 用 い て 副 鍵 を 生 成 し ， 分 割 ・ 転 置 を 実 行 す る ラ ウ ン ド 処 理 と 副 鍵 と の 排 他 的 論 理 和 を 繰 り 返 す ． 演 算 処 理 単 位 は 4 ビ ッ ト で あ り ， 各 4 ビ ッ ト を 1 要 素 と す る ． 秘 密 鍵 長 が 6 4 ビ ッ ト の 場 合 ， 秘 密 鍵 を 解 読 す る た め に は 0 番 目 の 副 鍵 S K0を 解 読 す れ ば よ い ．L E D の 性 質 よ り ，ラ ウ ン ド 処 理 実 行 前 の 値 の 任 意 の 1 要 素 は ラ ウ ン ド 処 理 実 行 後 の 値 の 4 つ の 要 素 に 影 響 を 及 ぼ し て お り ，他 の 要 素 と は 独 立 で あ る ．ま た ， ラ ウ ン ド 処 理 実 行 後 の 値 の 任 意 の 1 要 素 は ラ ウ ン ド 処 理 実 行 前 の 値 の 4 つ の 要 素 に 依 存 し て お り ， 他 の 要 素 と は 独 立 の 関 係 に あ る ． こ れ ら の 関 係 よ り 0 番 目 の 要 素 の み 異 な り ， 他 の 要 素 は 等 し い 2 つ の 平 文 を L E D 暗 号 L S I に 入 力 し ，1 ラ ウ ン ド 目 処 理 後 の 値 を ス キ ャ ン デ ー タ と し て 取 得 し ， 排 他 的 論 理 和 す る 時 ，4 つ の 要 素 ，つ ま り ，あ る 1 6 個 の ビ ッ ト は 副 鍵 S K0 の 中 の 0 番 目 の 要 素( 4 ビ ッ ト)の み に 依 存 し た 値 に な る ． よ っ て ， 副 鍵 S K0 の 0 番 目 の 要 素 の 全 パ タ ー ン に つ い て ， こ れ ら 1 6 個 の ビ ッ ト の ス キ ャ ン シ グ ネ チ ャ を 求 め ， ス キ ャ ン デ ー タ と 比 較 す る こ と で ， 副 鍵 S K0 の 0 番 目 の 要 素 を 解 読 で き る ． 同 様 に ， 副 鍵 S K0 の 他 の 要 素 に つ い て も こ れ ら の 手 法 で 解 読 可 能 で あ る ． 提 案 手 法 は ， ス キ ャ ン チ ェ イ ン に 他 の 回 路 が 含 ま れ て い て も 解 読 可 能 で ， ス キ ャ ン チ ェ イ ン 長 ， 秘 密 鍵 長 に 非 依 存 で あ る ．ス キ ャ ン チ ェ イ ン 長 が 3 万 ビ ッ ト 以 上 の 場 合 に は 副 鍵 S K0を 2 要 素 ず つ 順 番 に 求 め れ ば よ い ． ま た ， 秘 密 鍵 長 が 64 ビ ッ ト よ り 大 き い 場 合 ， 提 案 手 法 を 用 い て S K0，1 番 目 の 副 鍵 S K1 を 同 様 に 順 に 求 め る こ と で 判 明 す る ．計 算 機 実 験 で は ， 提 案 手 法 を 用 い て 平 均 7 3 個 の 平 文 で 6 4 ビ ッ ト の 秘 密 鍵 を 0 . 2 9 0 秒 で 復 元 可 能 と 確 認 し た ．ま た 平 均 1 4 5 個 の 平 文 で 1 2 8 ビ ッ ト の 秘 密 鍵 を 0 . 4 6 8 秒 で 復 元 可 能 と 確 認 し た ． ス キ ャ ン チ ェ イ ン に 他 の 回 路 が 含 ま れ て い る こ と を 想 定 し ， ス キ ャ ン デ ー タ に ラ ン ダ ム な ビ ッ ト 値 を 付 加 し て ス キ ャ ン チ ェ イ ン 長 を 1 3 万 ビ ッ ト 程 度 ま で 変 化 さ せ た 場 合 に も ，1 3 7 個 の 平 文 を 用 い て 副 鍵 S K0 を 2 要 素 ず つ 順 番 に 求 め る こ と で ，6 4 ビ ッ ト の 秘 密 鍵 を 2 時 間 半 程 度 で 解 読 で き る こ と を 確 認 し た ．
第 5 章 で は ， ハ ッ シ ュ 関 数 の 実 装 法 H M A C と ハ ッ シ ュ 関 数 P G V の 性 質 と ア ル ゴ リ ズ ム を 示 し ，H M A C - PG V へ の ス キ ャ ン ベ ー ス 攻 撃 手 法 を 提 案 す る ．H M A C は ハ ッ シ ュ 関 数 を 2 回 実 行 す る メ ッ セ ー ジ 認 証 コ ー ド で あ る ．A N S I, I E T F IS O , N I S T に よ り 標 準 化 さ れ ，S S L , T L S , S S H , I p s e c 等 に 使 わ れ て い る ． ハ ッ シ ュ 関 数 P G V は ブ ロ ッ ク 暗 号 を 利 用 し た ハ ッ シ ュ 関 数 で あ る ．H M A C - P G V- f1に 実 装 さ れ た ブ ロ ッ ク 暗 号 へ の ス キ ャ ン ベ ー ス 攻 撃 が 可 能 な 時 ，H M A C - PG V- f1 に 対 し て も ス キ ャ ン ベ ー ス 攻 撃 可 能 で あ る ． ソ フ ト ウ ェ ア に よ る 評 価 実 験 よ り ， ハ ッ シ ュ に 対 し て も ス キ ャ ン ベ ー ス 攻 撃 可 能 な こ と を 確 認 し た ．
第 6 章 で は 本 論 文 の 内 容 を ま と め ， 今 後 の 課 題 を 示 す ．
Ｎｏ.1
早稲田大学 博士（工学） 学位申請 研究業績書
氏 名 藤代 美佳 印
（2015 年 12 月現在）
種 類 別 題名、 発表・発行掲載誌名、 発表・発行年月、 連名者（申請者含む）
a. 論文：
学 術 誌 原 著論文
c. 講演：
国 際 会 議 ( 査 読 有 り)
[1]
○M. Fujishiro, M. Yanagisawa, and N. Togawa, “Scan-based side-channel attack on the LED block cipher using scan signatures,” IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, vol. E97-A, no. 12, pp.
2434-2442, 2014.
[2]
○M. Fujishiro, M. Yanagisawa, and N. Togawa, “Scan-based attack against trivium stream cipher using scan signatures,” IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, vol. E97-A, no. 7, pp. 1444-1451, 2014.
[3]
H. Jiang, M. Fujishiro, H. Kodera, M. Yanagisawa, and N. Togawa, “Scan-based side-channel attack on the camellia block cipher using scan signatures,” IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, vol.
E98-A, no. 12, pp. 2547-2555, 2015.
[4]
○M. Fujishiro, M. Yanagisawa, and N. Togawa, “Scan-based attack on the LED block cipher using scan signatures,” in Proc. IEEE International Symposium on Circuits and Systems (ISCAS 2014), pp. 1460-1463, 2014.
[5]
○M. Fujishiro, M. Yanagisawa, and N. Togawa, “Scan-based attack against trivium stream cipher independent of scan structure, ” in Proc. IEEE International Conference on ASIC (ASICON 2013), pp. 146-149, 2013.
[6] 【招待論文】
M. Fujishiro, Y. Shi, M. Yanagisawa, and N. Togawa, “Scan-based side-channel attack against symmetric key ciphers using scan signatures,” in Proc. IEEE Conference on Electron Devices and Solid-State Circuits (EDSSC 2015), pp. 309-312, 2015.
[7]
H. Jiang, M. Fujishiro, M. Yanagisawa, and N. Togawa, “Scan-based side-channel attack implementation evaluation on the LED cipher using SASEBO-GII,” in Proc.
Workshop on Synthesis And System Integration of Mixed Information Technologies (SASIMI 2015), pp. 433-434, 2015.
[8]
H. Jiang, M. Fujishiro, H. Kodera, M. Yanagisawa, and N. Togawa, “Scan-based side-channel attack on camellia cipher using scan signatures,” in Proc. IEEE Asia Pacifc Conference on Circuits and Systems (APCCAS 2014), pp. 252-255, 2014.
Ｎｏ.2
早稲田大学 博士（工学） 学位申請 研究業績書
種 類 別 題名、 発表・発行掲載誌名、 発表・発行年月、 連名者（申請者含む）
c. 講演：
国 内 学 会 ( 査 読 付 き)
c. 講演：
国 内 学 会 ( 査 読 無 し)
e. その他 (賞)
[9]
藤代美佳, 柳澤政生, 戸川望, “ストリーム暗号 Trivium に対するスキャンチェインの 構造に依存しないスキャンベース攻撃手法,” 第 26 回回路とシステムワークショップ論 文集, pp. 442-447, 2013.
[10]
藤代美佳, 柳澤政生, 戸川望, “鍵長に依存しない LED 暗号に対するスキャンベース攻 撃,” 情処研報, vol. 2015-SLDM-170, no. 47, pp. 149-154, 2015.
[11]
藤代美佳, 柳澤政生, 戸川望, “スキャンチェイン長に依存しない LED 暗号に対するス キャンベース攻撃, ” 信学技報, VLD2013-139, vol. 113, no. 454, pp. 31-36, 2014.
[12]
藤代美佳, 柳澤政生, 戸川望, “スキャンシグネチャを用いた LED 暗号へのスキャンベ ース攻撃, ” 信学技報, VLD2013-55, vol. 113, no. 235, pp. 47-52, 2013.
[13]
藤代美佳, 柳澤政生, 戸川望, “スキャンシグネチャを用いたストリーム暗号 Trivium へのスキャンベース攻撃手法,” 信学技報, VLD2013-8, vol. 113, no. 30, pp. 61-66, 2013.
2014 年 8 月 DA シンポジウム 2014 アルゴリズムデザインコンテスト特別賞．
