論文封面格式

中 華 大 學 碩 士 論 文 有 效 率 的 RFID 認 證 協 定 基 於 二 次 剩 餘 密 碼 系 統 An Efficient RFID Authentication Protocol based on Quadratic Residue Cryptosystem 系 所 別 : 資 訊 工 程 學 系 碩 士 班 學 號 姓 名 :M09702043 邱 煥 訓 指 導 教 授 : 吳 林 全 博 士 中 華 民 國 100 年 8 月

摘 要 無 線 射 頻 辨 識 系 統 (RFID) 是 近 幾 年 發 展 的 一 項 相 當 具 有 潛 力 的 技 術 在 2003 年 美 國 百 貨 業 的 龍 頭 沃 爾 瑪 (Wal-Mart) 百 貨 公 司 針 對 前 一 百 大 供 應 商, 訂 定 在 2005 年 前 必 須 將 所 有 商 品 附 加 RFID 標 籤 的 目 標, 為 供 應 鏈 管 理 的 技 術 帶 來 革 命 性 的 轉 變 然 而, 我 國 的 行 政 院 經 濟 部 也 於 2005 年 率 先 推 動 一 個 在 公 有 領 域 應 用 RFID 的 計 畫, 並 且 引 導 私 人 企 業 投 入 研 發 這 兩 項 發 展 引 起 產 學 界 的 關 注, 而 在 日 後 RFID 也 廣 泛 地 應 用 在 各 種 領 域 之 中 近 年 來 RFID 應 用 的 普 及, 造 就 了 我 們 便 利 的 生 活, 但 也 引 發 了 各 種 安 全 性 的 質 疑, 因 此 有 許 多 學 者 針 對 這 些 問 題 提 出 了 改 善 的 方 法 在 本 論 文 中, 我 們 將 回 顧 近 年 來 的 一 些 RFID 認 證 協 定, 並 針 對 2008 年 Chen 等 學 者 所 提 出 的 基 於 二 次 剩 餘 密 碼 系 統 所 設 計 之 RFID 認 證 協 定 和 2010 年 Yeh 等 學 者 改 善 Chen 等 學 者 的 方 法 中 容 易 遭 受 偽 造 攻 擊 和 重 送 攻 擊 的 問 題 提 出 效 率 方 面 改 善 的 方 法 我 們 的 方 法 除 了 能 夠 改 善 Yeh 方 法 的 效 率, 同 時 也 能 夠 保 留 相 同 的 安 全 性 質, 在 標 籤 和 伺 服 器 各 別 只 需 要 1 次 二 次 剩 餘 運 算, 比 Chen 的 方 法 各 需 要 2 次 和 Yeh 的 方 法 各 需 要 3 次 還 少, 所 以 能 夠 大 量 的 減 少 標 籤 和 伺 服 器 的 負 擔, 而 其 他 運 算 的 次 數 也 明 顯 減 少, 因 此 非 常 適 合 用 於 利 用 二 次 剩 餘 密 碼 系 統 所 設 計 之 有 效 率 的 無 線 射 頻 辨 識 系 統 中 關 鍵 字 :RFID 認 證 二 次 剩 餘 密 碼 系 統 資 訊 安 全 i

ABSTRACT Radio Frequency Identification (RFID) is the popular technology in recent years. Wal-Mart is the leader of department store in the U.S., and it requests all goods for the top 100 suppliers must be attached RFID tag before 2006. It produces a serious change with the supply chain management of RFID technology. Moreover, Ministry of Economic Affairs takes the lead promote a plan in 2005 that uses the RFID in the public places. It also guides the development of private enterprises. They raise the concerns of industry and academia. The RFID technology will be applied in each kind of domain in the future. Recently, the popularity of RFID applications creates a convenient life. It also brings various security issues. There are many scholars presented solutions to improve these problems. In this paper, we will review some recent RFID authentication protocols. In 2008, Chen et al. presented the authentication protocol based on quadratic residue cryptosystem. Yeh et al. s pointed out that Chen et al. s scheme is vulnerable to impersonation attack and replay attack and submitted the improved scheme in 2010. Our proposed scheme is not only increase efficiency in RFID, but also retains the same safety properties. It needs only one quadratic residual operation in the tag and server respectively. The total numbers of operations in our scheme are less than Chen et al. s and Yeh et al. s schemes. Therefore, the proposed RFID authentication scheme is better in efficiency based on quadratic residue cryptosystem. Keywords:RFID Authentication Quadratic residue cryptosystem Security ii

誌 謝 寫 著 這 致 謝 的 同 時, 也 將 整 個 碩 士 班 生 涯 快 速 的 瀏 覽 一 遍, 果 然, 記 憶 裡 那 種 痛 苦 掙 扎 的 感 覺 是 淡 了 些, 而 那 些 曾 經 在 緊 要 關 頭 讓 我 突 破 困 境 向 前 拼 的 關 鍵 畫 面 卻 還 是 一 樣 鮮 明! 一 直 以 來 我 都 認 為 這 篇 論 文 是 個 不 可 能 的 任 務, 不 止 一 次 想 要 放 棄, 但 最 後 還 是 如 期 完 成 首 先 我 要 感 謝 指 導 教 授 吳 林 全 博 士 的 悉 心 教 導, 使 我 得 以 一 窺 資 訊 安 全 領 域 的 深 奧, 不 時 的 討 論 並 指 點 我 正 確 的 方 向, 使 我 在 這 些 年 中 獲 益 匪 淺 而 在 寫 作 論 文 的 期 間, 老 師 辛 勤 的 多 次 詳 細 閱 讀 並 提 出 寶 貴 的 建 議 幫 助 我 修 正, 而 在 於 課 業 上 或 是 課 堂 中 的 論 文 報 告 等 等, 老 師 也 不 吝 惜 的 給 予 意 見 與 指 導, 在 此 深 深 的 感 謝 再 來, 我 也 感 謝 在 我 研 究 所 這 段 期 間, 戴 瑞 成 蘇 俊 豪 劉 冠 廷 學 長 吳 嘉 恩 蔡 定 國 同 學 以 及 陳 健 儒 朱 元 佑 游 翔 晨 學 弟 的 陪 伴 及 支 持, 不 論 在 課 業 上 還 是 日 常 生 活 的 相 處, 有 了 你 們, 讓 我 在 研 究 所 的 生 活 過 得 既 充 實 又 快 樂, 在 此 也 感 謝 大 家 最 後, 我 要 感 謝 我 的 家 人 為 我 提 供 一 個 溫 暖 安 靜 的 窩, 讓 我 可 以 沈 澱 忙 碌 的 實 驗 和 慌 亂 的 情 緒, 謝 謝 爸 爸 媽 媽 對 我 的 寵 愛 和 信 任, 還 有 我 的 哥 哥 的 鼓 勵, 讓 我 可 以 全 心 專 注 在 自 己 的 課 業 上, 不 用 為 許 多 繁 瑣 的 事 情 分 心 在 完 成 這 份 論 文 的 過 程 中, 我 一 直 是 患 得 患 失 的, 而 今 能 走 到 最 後, 繳 出 一 份 令 人 滿 意 的 成 果, 最 要 感 謝 的 是 還 是 這 一 路 上 曾 幫 助 過 我 的 師 長 與 朋 友 們, 感 謝 你 們, 我 願 把 這 份 榮 耀 和 你 們 分 享, 謝 謝! iii

目 錄 摘 要... i ABSTRACT... ii 誌 謝... iii 目 錄... iv 表 目 錄... vi 圖 目 錄... vii 一 簡 介... 1 1.1 動 機... 2 1.2 目 的... 3 1.3 大 綱... 4 二 背 景 介 紹... 5 2.1 條 碼... 5 2.2 無 線 射 頻 辨 識 系 統... 6 2.3 無 線 射 頻 辨 識 系 統 和 條 碼 的 比 較... 9 2.4 電 子 產 品 編 碼 (Electronic Product Code)... 10 2.5 無 線 射 頻 辨 識 系 統 的 安 全 議 題... 11 2.6 二 次 剩 餘 原 理 及 密 碼 系 統... 12 三 相 關 研 究... 15 3.1 雜 湊 鎖 定 方 法 (Hash-Locking scheme)... 15 3.2 隨 機 雜 湊 鎖 定 方 法 (Randomized Hash-Locking scheme)... 16 3.3 Juels 的 方 法... 18 3.4 Wong 的 方 法... 19 3.5 Chen 的 方 法... 21 3.6 Yeh 的 方 法... 23 3.6.1 初 始 階 段... 23 iv

3.6.2 認 證 階 段... 23 3.7 主 要 相 關 研 究 關 係 圖... 25 四 我 們 提 出 的 方 法... 27 4.1 符 號 及 參 數 表... 27 4.2 環 境 變 數 設 定... 28 4.3 初 始 階 段... 28 4.4 認 證 階 段... 28 五 分 析... 31 5.1 計 算 量 的 分 析... 31 5.2 安 全 性 質 的 分 析... 32 結 論... 35 參 考 文 獻... 36 v

表 目 錄 表 2-1 各 種 無 線 射 頻 辨 識 系 統 之 比 較 表... 9 表 2-2 無 線 射 頻 辨 識 系 統 與 條 碼 比 較 表... 10 表 4-1 符 號 及 參 數 表... 27 表 5-1 計 算 量 的 分 析... 32 表 5-2 安 全 性 質 分 析... 34 vi

圖 目 錄 圖 2-1 條 碼 及 條 碼 掃 瞄 器... 5 圖 2-2 RFID 標 籤 和 讀 取 器... 7 圖 2-3 RFID 系 統 的 運 作 方 法... 8 圖 3-1 雜 湊 鎖 定 方 法 (Hash-Locking scheme)... 15 圖 3-2 隨 機 雜 湊 鎖 定 方 法 (Randomized Hash-Locking Scheme)... 17 圖 3-3 Juels 的 方 法... 18 圖 3-4 Wong 的 方 法... 20 圖 3-5 Chen 的 方 法... 21 圖 3-6 Yeh 的 方 法... 24 圖 3-7 RFID 主 要 相 關 研 究 關 係 圖... 26 圖 4-1 我 們 的 方 法... 30 vii

一 簡 介 隨 著 科 技 的 進 步, 人 們 不 斷 地 研 究 出 各 種 新 的 技 術, 讓 日 常 生 活 中 各 種 大 大 小 小 的 事 都 變 的 更 加 的 方 便, 目 的 就 是 為 了 改 善 生 活 的 品 質, 讓 我 們 的 生 活 更 加 的 便 利 其 中, 無 線 射 頻 辨 識 系 統 (Radio Frequency Identification; 簡 稱 RFID), 是 近 幾 年 來 相 當 受 到 各 界 關 注 的 一 個 身 分 辨 識 和 認 證 的 技 術 其 實 無 線 射 頻 辨 識 系 統 的 技 術 早 就 已 經 應 用 在 我 們 的 日 常 生 活 中 了, 不 論 是 撘 乘 捷 運 等 大 眾 運 輸 工 具 使 用 的 悠 遊 卡 出 入 大 門 所 使 用 的 Mifare 門 禁 感 應 卡 等, 都 是 我 們 目 前 常 見 的 應 用 無 線 射 頻 辨 識 系 統 的 運 作 是 使 用 無 線 電 波 訊 號, 識 別 一 定 的 範 圍 之 內 特 定 的 目 標 並 且 讀 取 所 需 之 相 關 的 資 料, 是 一 種 非 接 觸 式 的 自 動 辨 識 技 術, 取 代 傳 統 條 碼 (Bar code) 系 統 必 須 近 距 離 讀 取 的 缺 點, 因 此 可 以 節 省 相 當 多 的 人 力 和 時 間 無 線 射 頻 辨 識 系 統 一 般 是 由 標 籤 (Tag) 讀 取 器 (Reader) 和 伺 服 器 (Server) 組 成 標 籤 的 種 類 依 照 電 力 的 來 源 分 為 主 動 式 被 動 式 和 半 主 動 式 三 種 [2] 雖 然 主 動 式 標 籤 的 計 算 能 力 以 及 儲 存 空 間 都 是 最 佳 的, 但 是 價 格 成 本 也 是 最 高 相 較 之 下, 被 動 式 標 籤 的 成 本 低 廉, 因 此 在 目 前 的 無 線 射 頻 辨 識 系 統 中 大 部 分 都 是 使 用 被 動 式 的 標 籤 在 資 料 傳 輸 方 面, 由 於 無 線 射 頻 辨 識 系 統 是 透 過 無 線 的 方 式 傳 送 重 要 的 資 料 進 行 身 分 認 證, 這 些 資 料 等 於 是 暴 露 在 外 沒 有 受 到 保 護 的, 有 心 人 士 只 要 利 用 一 些 非 法 的 技 術 或 是 器 材, 便 可 從 中 攔 截 並 獲 取 重 要 的 資 料 所 以, 如 何 運 用 標 籤 中 有 限 的 記 憶 體 空 間 和 電 量 去 達 成 有 效 率 以 及 安 全 的 認 證, 是 相 當 值 得 我 們 去 探 討 1

1.1 動 機 由 於 無 線 射 頻 辨 識 系 統 技 術 的 迅 速 發 展, 在 不 知 不 覺 中, 已 經 漸 漸 成 為 我 們 的 日 常 生 活 的 ㄧ 部 份, 舉 例 來 說, 學 生 族 上 班 族 通 勤 時 使 用 的 悠 遊 卡 各 種 大 大 小 小 公 司 存 貨 倉 庫 的 物 流 管 理 醫 院 急 診 室 中 用 來 辨 識 病 人 身 分 的 手 環 借 書 還 書 利 用 無 線 射 頻 辨 識 系 統 技 術 取 代 人 力 的 無 人 圖 書 館 等 等 而 應 用 這 些 技 術 的 背 後, 隱 私 和 安 全 的 問 題 一 定 會 接 踵 而 至, 像 是 標 籤 記 憶 體 中 所 儲 存 的 個 人 資 料 外 洩 或 是 遭 受 到 非 法 的 複 製 因 此, 在 無 線 射 頻 辨 識 系 統 中 加 入 完 善 的 認 證 協 定 是 目 前 解 決 隱 私 安 全 的 ㄧ 種 方 法 然 而, 除 了 滿 足 隱 私 安 全 之 外, 整 個 系 統 的 運 作 效 率 也 必 須 納 入 考 量 因 此, 我 們 將 會 設 計 一 種 安 全 又 有 效 率 的 認 證 協 定, 結 合 二 次 剩 餘 密 碼 系 統, 利 用 離 散 場 域 中 將 一 個 整 數 進 行 平 方 的 運 算 較 為 容 易, 可 是 要 將 一 個 整 數 進 行 平 方 根 的 運 算 是 較 為 困 難 的 特 性, 加 強 了 認 證 協 定 的 強 度, 並 且 也 能 夠 降 低 無 線 射 頻 辨 識 系 統 中 標 籤 的 運 算 量, 讓 標 籤 能 夠 在 有 限 的 電 力 之 中 完 成 認 證 提 升 整 體 的 效 率 2

1.2 目 的 本 篇 論 文 中, 我 們 改 善 了 前 人 所 提 出 的 無 線 射 頻 辨 識 系 統 認 證 協 定 方 法, 此 方 法 將 二 次 剩 餘 的 概 念 結 合 到 認 證 協 定 中, 抵 擋 攻 擊 者 的 威 脅 和 攻 擊, 增 加 了 認 證 過 程 的 安 全 性 由 於 無 線 射 頻 辨 識 系 統 認 證 協 定 之 中 所 使 用 的 標 籤 大 多 數 是 被 動 式, 標 籤 的 計 算 能 力 和 資 料 的 儲 存 量 都 有 限, 無 法 儲 存 過 多 的 資 料 或 是 執 行 大 量 的 運 算 因 此, 如 何 利 用 最 少 量 的 計 算 花 費 達 成 最 大 的 安 全 防 護, 是 所 有 研 究 無 線 射 頻 辨 識 系 統 認 證 協 定 的 學 者 一 個 共 同 的 目 標 我 們 將 方 法 中 所 傳 送 內 容 以 及 步 驟 加 以 修 正, 不 僅 滿 足 了 現 今 的 無 線 射 頻 辨 識 系 統 常 見 的 隱 私 性 和 安 全 性 問 題, 還 降 低 了 標 籤 以 及 伺 服 器 的 運 算 量 以 及 資 料 傳 輸 量 目 的 就 是 為 了 朝 著 設 計 一 個 有 效 率 的 無 線 射 頻 辨 識 系 統 認 證 協 定 的 目 標 前 進 3

1.3 大 綱 本 篇 論 文 分 為 六 個 章 節, 第 一 章 介 紹 撰 寫 本 篇 論 文 的 動 機 和 目 的, 第 二 章 介 紹 無 線 射 頻 辨 識 系 統 的 組 成 運 作 方 法 以 及 和 前 一 代 條 碼 辨 識 技 術 的 比 較 第 三 章 介 紹 無 線 射 頻 辨 識 系 統 認 證 協 定 的 相 關 研 究 第 四 章 介 紹 本 篇 論 文 的 作 法 第 五 章 將 本 篇 提 出 的 方 法 和 相 關 研 究 的 論 文 進 行 安 全 性 以 及 計 算 量 的 比 較 第 六 章 總 結 本 篇 論 文 以 及 介 紹 未 來 的 展 望 4

二 背 景 介 紹 本 章 節 將 會 介 紹 目 前 常 見 的 物 品 辨 識 技 術 - 條 碼 和 無 線 射 頻 辨 識 系 統, 比 較 兩 者 之 間 的 特 性 操 作 環 境 和 應 用, 並 且 介 紹 目 前 無 線 射 頻 辨 識 系 統 使 用 的 電 子 產 品 碼 的 標 準, 以 及 無 線 射 頻 辨 識 系 統 中 常 見 的 隱 私 性 和 安 全 性 的 問 題 2.1 條 碼 條 碼 (Bar code)[3], 是 一 種 依 照 固 定 規 則 的 黑 白 線 條 所 組 成 的 一 種 編 碼 圖 形, 可 以 記 載 產 品 的 相 關 資 訊, 例 如 商 品 名 稱 生 產 地 製 造 商 名 稱 製 造 日 期 等 資 訊 條 碼 的 運 作 方 式, 是 利 用 具 有 紅 外 線 功 能 的 條 碼 掃 描 器 照 射 條 碼 產 生 反 射 光 線, 然 後 利 用 光 電 轉 換 器 將 明 暗 度 不 同 的 光 線 轉 換 成 電 腦 可 以 辨 識 的 數 位 資 料 過 去 大 部 分 的 商 品 都 是 利 用 條 碼 的 方 式 紀 錄 產 品 的 資 訊, 使 用 條 碼 的 自 由 度 大 設 備 簡 單 成 本 低, 但 是 條 碼 如 受 到 污 染 或 損 毀 則 無 法 讀 取 其 內 容, 這 是 使 用 條 碼 的 一 個 嚴 重 的 缺 點 如 圖 2-1 所 示, 條 碼 可 分 為 一 般 條 碼 以 及 二 維 條 碼 兩 種, 其 中 的 差 別 再 於 一 維 條 碼 是 依 照 寬 度 來 記 載 數 據, 長 度 沒 有 記 在 數 據 的 功 能, 而 二 維 條 碼 的 長 度 和 寬 度 皆 可 記 載 數 據, 另 外, 二 維 條 碼 較 一 般 條 碼 多 了 定 位 點 的 功 能 和 容 錯 的 機 制, 最 右 邊 則 為 條 碼 掃 瞄 器, 是 用 來 讀 取 條 碼 內 容 的 工 具 條 碼 ( 一 般 ) 二 維 條 碼 ( 手 機 可 讀 取 ) 條 碼 掃 瞄 器 * 圖 2-1 條 碼 及 條 碼 掃 瞄 器 * 資 料 來 源 : 條 碼 掃 描 器, 帝 商 科 技 股 份 有 限 公 司, 網 址 :http://www.regalscan.com.tw/tc/ 5

2.2 無 線 射 頻 辨 識 系 統 無 線 射 頻 辨 識 系 統 早 在 一 九 五 O 年 間 的 二 次 世 界 大 戰, 就 已 經 被 英 國 空 軍 所 採 用, 當 時 是 使 用 功 率 較 強 並 且 掛 載 電 池 的 主 動 式 標 籤, 主 要 的 功 能 是 用 來 偵 測 前 往 機 場 的 戰 機 是 否 屬 於 我 方 陣 營, 降 低 了 我 方 陣 營 的 戰 機 遭 受 誤 擊 的 可 能 性, 直 到 現 在 的 航 空 安 全 系 統, 都 還 是 沿 用 這 個 方 法 從 那 之 後, 無 線 射 頻 辨 識 系 統 就 很 少 被 應 用 到, 因 此 沉 寂 了 一 段 日 子 直 到 2005 年, 美 國 的 百 貨 零 售 業 的 龍 頭 沃 爾 瑪 (Wal-Mart), 宣 佈 要 求 旗 下 所 屬 的 前 100 大 貨 品 供 應 商, 將 無 線 射 頻 辨 識 系 統 導 入 出 貨 的 商 品 中, 因 此, 可 以 快 速 的 識 別 商 品 來 源, 大 幅 度 的 減 少 了 倉 庫 管 理 的 人 事 成 本, 才 讓 無 線 射 頻 辨 識 系 統 這 項 技 術 重 新 被 世 人 所 關 注 我 們 將 無 線 射 頻 辨 識 系 統 進 行 更 進 一 步 的 研 究 或 是 應 用 之 前, 必 須 先 了 解 其 構 造 以 及 運 作 的 方 法 一 個 完 整 的 無 線 射 頻 辨 識 系 統 一 般 是 由 標 籤 (Tag) 讀 取 器 (Reader) 和 伺 服 器 (Server) 組 成 標 籤 的 內 部 主 要 是 由 以 下 的 元 件 所 組 成 : 1. 天 線 (Antenna) 發 送 或 接 收 標 籤 跟 讀 取 器 之 間 的 射 頻 訊 號 2. 記 憶 體 (Memory) 用 來 存 放 標 籤 的 相 關 資 訊 3. 半 導 體 晶 片 (Semiconductor chip) 處 理 標 籤 運 算 的 部 分 4. 通 訊 控 制 單 元 (Communication control unit) 將 晶 片 運 算 後 產 生 的 資 料 轉 換 成 可 傳 輸 的 訊 號 5. 電 力 供 應 來 源 (Power supply) 產 生 供 應 標 籤 運 算 所 需 花 費 的 電 力 而 標 籤 的 種 類 依 照 電 力 來 源 的 不 同 可 分 為 以 下 三 種 [2]: 1. 主 動 式 (Active): 主 動 式 標 籤 本 身 具 有 電 力, 可 供 應 內 部 晶 片 處 理 資 料 所 需 之 電 量, 並 且 能 主 動 發 射 訊 號 與 讀 取 器 進 行 資 料 的 交 換, 讀 取 距 離 較 長, 資 料 儲 存 量 也 較 大, 但 所 需 的 6

成 本 也 會 較 高 2. 被 動 式 (Passive): 由 於 被 動 式 標 籤 體 積 較 小, 內 部 沒 有 電 池 供 給 電 力, 因 此 產 生 電 力 的 方 式 是 透 過 讀 取 器 發 射 無 線 電 訊 號 刺 激 內 部 的 感 應 線 圈 晶 片, 利 用 這 些 電 量 進 行 運 算 而 產 生 資 料, 所 以 當 附 近 沒 有 讀 取 器 感 應 時, 標 籤 是 不 會 運 作 的 由 於 被 動 式 標 籤 的 電 量 有 限, 所 以 讀 取 距 離 較 短, 資 料 儲 存 量 也 較 小, 但 是 相 對 的 成 本 也 較 為 低 廉, 可 應 用 的 範 圍 也 較 廣 3. 半 主 動 式 (Semi-active): 半 主 動 式 標 籤 與 被 動 式 標 籤 類 似, 不 同 的 地 方 在 於 半 主 動 式 標 籤 具 有 電 池 可 產 生 資 料, 解 決 了 因 天 線 忙 碌 而 造 成 訊 息 傳 輸 的 問 題 圖 2-2 由 左 到 右 分 別 為 讀 取 器 依 照 電 力 供 應 的 來 源 所 分 成 的 主 動 式 標 籤 以 及 被 動 式 標 籤 讀 取 器 主 動 式 標 籤 * 被 動 式 標 籤 圖 2-2 RFID 標 籤 和 讀 取 器 * 資 料 來 源 : 主 動 式 標 籤, 益 眾 科 技 股 份 有 限 公 司, 網 址 :http://www.icci.com.tw/ 如 圖 2-3 所 示, 無 線 射 頻 辨 識 系 統 的 運 作 方 法 為 讀 取 器 發 送 查 詢 (query) 的 訊 號 來 激 發 標 籤 裡 的 電 路, 產 生 所 需 的 電 力 提 供 標 籤 計 算 的 能 力 讀 取 器 主 要 的 功 能 是 發 射 及 接 收 無 線 電 訊 號, 將 所 接 受 到 的 標 籤 訊 息 回 傳 給 伺 服 器, 扮 演 一 個 中 繼 的 角 色 伺 服 器 則 是 存 放 所 有 標 籤 的 內 部 資 料 以 供 辨 識, 例 如 產 品 的 名 稱 型 號 製 造 日 期 和 價 格 等 相 關 的 資 訊, 而 這 個 固 定 形 式 的 代 碼 我 們 稱 為 電 子 產 品 編 碼 (Electronic Product 7

Code;EPC) 在 資 料 傳 輸 方 面, 讀 取 器 和 伺 服 器 是 透 過 有 線 傳 輸, 所 以 比 較 沒 有 安 全 性 方 面 的 疑 慮 但 是 標 籤 和 讀 取 器 之 間 是 利 用 無 線 的 方 式 傳 輸 資 料, 因 此 在 傳 輸 資 料 的 過 程 中 容 易 遭 受 較 多 的 安 全 性 問 題 [4] 所 以 在 標 籤 到 讀 取 器 的 認 證 防 護 和 身 分 辨 識 機 制 是 很 重 要 的 圖 2-3 RFID 系 統 的 運 作 方 法 在 無 線 射 頻 辨 識 系 統 當 中 有 許 多 不 同 頻 率 的 系 統, 表 2-1 將 會 介 紹 這 些 系 統 在 發 射 頻 率 運 作 頻 率 傳 輸 距 離 傳 輸 速 度 傳 輸 方 式 應 用 等 六 種 的 區 別 標 籤 和 讀 取 器 之 間 的 發 射 頻 率 的 種 類 依 照 使 用 者 需 求 的 不 同 可 分 成 低 頻 高 頻 超 高 頻 和 微 波 四 種 ; 依 運 作 頻 率 來 分, 低 頻 為 134.2Khz, 高 頻 為 13.56Mhz, 超 高 頻 的 運 作 範 圍 在 868Mhz~956Mhz 間, 而 微 波 則 是 運 作 在 2.45Ghz 的 頻 率 之 中 ; 依 照 傳 輸 距 離 來 分, 低 頻 系 統 的 傳 輸 距 離 小 於 0.6 公 尺, 高 頻 系 統 傳 輸 距 離 約 0.6 公 尺, 超 高 頻 系 統 的 傳 輸 距 離 為 10 公 尺, 微 波 類 型 的 系 統 的 傳 輸 距 離 可 達 到 100 公 尺, 是 四 種 不 同 的 發 射 頻 率 當 中, 可 傳 送 最 遠 的 ; 依 照 傳 輸 的 速 度 來 分, 低 頻 系 統 的 傳 輸 速 度 最 慢, 高 頻 系 統 的 傳 輸 速 度 中 等, 超 高 頻 系 統 傳 送 的 傳 輸 速 度 較 快, 而 微 波 型 系 統 的 傳 輸 速 度 最 快 ; 傳 輸 的 方 式, 低 頻 系 統 和 高 頻 系 統 是 利 用 電 磁 感 應 的 方 式 傳 輸, 超 高 頻 系 統 和 微 波 型 系 統 則 是 利 用 電 波 的 方 式 傳 輸 ; 這 些 不 同 類 型 的 系 統 也 會 應 用 在 不 同 的 地 方, 低 頻 系 統 較 常 應 用 在 門 禁 管 制 上, 方 便 控 管 進 出 的 訪 客 ; 高 頻 系 統 應 用 於 電 子 收 費 系 統 - ( 悠 遊 卡 ) 中, 是 目 前 最 重 要 的 應 用 ; 超 高 頻 系 統 主 要 應 用 於 醫 院 的 醫 療 照 護 之 中, 讓 8

醫 生 能 更 迅 速 的 掌 握 病 人 的 醫 療 管 理 ; 微 波 類 型 的 系 統, 主 要 應 用 在 供 應 鏈 管 理, 能 夠 更 快 的 了 解 數 量 龐 大 的 貨 物 來 源 表 2-1 各 種 無 線 射 頻 辨 識 系 統 之 比 較 表 發 射 頻 率 低 頻 (LF) 高 頻 (HF) 超 高 頻 (UHF) 微 波 (Microwave) 運 作 頻 率 134.2KHz 13.56MHz 868~956Mhz 2.45GHz 通 訊 距 離 小 於 0.6 公 尺 0.6 公 尺 10 公 尺 1 公 尺 通 訊 速 度 慢 中 快 中 通 訊 方 式 電 磁 感 應 電 磁 感 應 電 波 電 波 應 用 門 禁 管 制 電 子 收 費 系 統 ( 悠 遊 卡 ) 醫 療 照 護 供 應 鏈 管 理 2.3 無 線 射 頻 辨 識 系 統 和 條 碼 的 比 較 無 線 射 頻 辨 識 系 統 和 條 碼 目 前 都 還 應 用 在 各 種 產 業 之 中, 本 節 將 會 介 紹 兩 者 之 間 的 不 同, 表 2-2 是 無 線 射 頻 辨 識 系 統 跟 條 碼 的 比 較 [5] 其 中 以 價 格 來 看, 條 碼 的 花 費 相 當 低 廉, 相 較 於 使 用 一 個 要 價 台 幣 10 元 的 無 線 射 頻 辨 識 系 統 標 籤, 這 是 使 用 條 碼 的 一 項 優 點, 因 此, 只 要 日 後 無 線 射 頻 辨 識 系 統 標 籤 的 成 本 降 低, 應 用 範 圍 將 會 變 得 更 廣 泛, 可 望 將 條 碼 完 全 取 代 條 碼 一 次 只 能 讀 取 一 個 目 標, 在 處 理 大 量 物 品 時, 會 花 費 較 多 的 時 間, 而 無 線 射 頻 辨 識 系 統 可 同 時 讀 取 多 個 標 籤, 這 可 以 讓 使 用 者 在 短 時 間 內 管 理 大 量 的 物 品, 大 幅 的 提 升 盤 點 的 速 度, 節 省 時 間 的 成 本 條 碼 的 資 料 儲 存 容 量 只 有 50 位 元 組 (bytes) 而 無 線 射 頻 辨 識 系 統 資 料 儲 存 容 量 可 達 到 1 百 萬 位 元 組 (Mega bytes), 所 以 可 以 儲 存 更 多 商 品 的 詳 細 資 訊, 不 會 受 到 容 量 上 的 限 制 條 碼 是 以 單 向 的 方 式 進 行 資 料 的 讀 取, 而 無 線 射 頻 辨 識 系 統 可 以 將 資 料 以 雙 向 的 方 式 傳 輸 來 進 行 簡 易 的 認 證, 增 加 系 統 的 安 全 條 碼 資 料 無 法 更 新, 而 無 線 射 頻 辨 識 系 統 標 籤 的 內 容 可 以 重 複 的 讀 寫 更 新 一 但 條 碼 受 到 污 染 和 損 毀 則 無 法 讀 取 相 關 的 內 容, 無 線 射 頻 辨 識 系 統 的 讀 取 器 利 用 無 線 的 方 式 讀 取 標 籤 資 料, 只 要 內 部 元 件 不 被 破 壞, 無 論 外 觀 遭 受 污 染 或 損 毀, 都 不 會 影 響 原 有 的 功 能, 所 以 條 碼 的 耐 久 度 比 無 線 射 9

頻 辨 識 系 統 還 來 的 低 傳 統 條 碼 常 常 因 為 消 磁 的 不 完 全 而 造 成 一 些 機 器 的 誤 判 而 引 起 警 報, 這 將 會 影 響 消 費 者 的 心 情 或 是 引 起 一 些 不 必 要 的 法 律 糾 紛, 安 全 性 較 低 所 以, 無 線 射 頻 辨 識 系 統 技 術 的 出 現 改 善 了 傳 統 條 碼 的 缺 點, 讓 我 們 的 生 活 更 加 的 便 利 表 2-2 無 線 射 頻 辨 識 系 統 與 條 碼 比 較 表 條 碼 (Bar code) 無 線 射 頻 辨 識 系 統 (RFID) 價 格 極 低 10 元 ( 台 幣 ) 讀 取 速 度 一 次 讀 取 一 個 條 碼 同 時 讀 取 多 個 標 籤 資 料 儲 存 容 量 小 (90-100byte) 大 (1Kbyte 以 上 ) 資 料 傳 輸 方 式 單 向 傳 輸 雙 向 傳 輸 資 料 更 新 無 法 更 新 可 重 覆 讀 寫 更 新 耐 久 度 低 高 安 全 性 低 高 2.4 電 子 產 品 編 碼 (Electronic Product Code) 無 線 射 頻 辨 識 系 統 能 夠 廣 泛 應 用 在 全 球 各 地, 必 須 先 有 一 套 大 家 公 認 的 標 準 (EPCglobal)[6] 所 以, 當 標 籤 在 全 世 界 的 各 個 地 方 流 通 時, 也 必 須 依 照 這 個 標 準, 才 能 夠 準 確 的 提 供 產 品 辨 識 和 分 類 的 功 能 如 同 傳 統 的 條 碼 一 般, 使 用 前 也 同 樣 必 須 制 定 一 套 共 通 的 標 準 目 前 在 無 線 射 頻 辨 識 系 統 上 使 用 的 號 碼, 我 們 稱 為 電 子 產 品 編 碼 (Electronic Product Code;EPC), 電 子 產 品 編 碼 是 一 段 獨 一 無 二 的 號 碼, 儲 存 在 無 線 射 頻 辨 識 系 統 的 標 籤 內, 可 提 供 讀 取 器 在 產 品 供 應 鏈 之 中 辨 識 特 定 的 物 品 標 籤 中 的 電 子 產 品 編 碼 被 讀 取 後, 可 與 後 端 伺 服 器 進 行 相 關 的 應 用 電 子 產 品 編 碼 是 一 個 具 有 彈 性 的 編 碼 系 統, 可 以 依 照 各 種 不 同 產 業 需 求 作 產 品 編 碼 上 的 調 整, 為 特 定 的 物 品 產 生 一 組 編 碼, 這 個 編 碼 將 為 此 物 品 所 獨 有 的 電 子 產 品 編 碼 標 籤 容 量 大 致 分 為 EPC-64 位 元 EPC-96 位 元 及 EPC-128 位 元 三 種 目 前 標 籤 大 多 數 是 使 用 EPC-96 位 元 的 長 度 儲 存 資 料, 儲 存 的 內 容 包 括 商 品 名 稱 代 碼 製 造 10

地 生 產 日 期 等 相 關 的 資 訊 2.5 無 線 射 頻 辨 識 系 統 的 安 全 議 題 無 線 射 頻 辨 識 技 術 的 發 展 雖 然 為 我 們 的 生 活 帶 來 相 當 大 的 便 利 性, 但 是 目 前 在 安 全 性 方 面 還 未 能 夠 有 統 一 的 標 準 倘 若 傳 輸 的 資 料 沒 有 經 過 一 道 加 密 的 手 續 或 是 沒 有 完 整 存 取 控 制 的 權 限, 有 心 人 士 便 可 以 利 用 這 項 漏 洞 以 及 相 關 的 技 術, 讀 取 標 籤 中 的 資 料, 甚 至 竄 改 標 籤 中 的 資 料, 使 得 標 籤 中 的 資 料 遺 失 或 外 洩, 這 是 在 使 用 無 線 射 頻 辨 識 系 統 的 過 程 中 值 得 我 們 去 研 究 的 議 題 以 下 是 無 線 射 頻 辨 識 系 統 中 常 見 隱 私 性 和 安 全 性 的 威 脅 [7]: 資 料 機 密 性 (Data secrecy): 標 籤 中 的 重 要 資 料 不 會 輕 易 的 暴 露 在 傳 輸 過 程 中, 因 為 標 籤 跟 讀 取 器 的 資 料 交 換 是 透 過 無 線 的 方 式 進 行 傳 輸, 攻 擊 者 可 以 經 由 攔 截 訊 息 的 方 式 獲 取 標 籤 和 讀 取 器 之 間 的 資 料 並 加 以 修 改 一 但 讀 取 器 沒 有 經 由 合 法 的 認 證 程 序 就 無 法 獲 得 儲 存 於 標 籤 中 的 資 料, 這 就 滿 足 資 料 機 密 性 的 條 件 使 用 者 隱 私 (User privacy): 攻 擊 者 透 過 監 控 標 籤 傳 輸 到 讀 取 器 的 資 料 後 進 行 分 析, 利 用 獲 得 的 資 訊 得 知 標 籤 持 有 人 的 相 關 資 訊 位 置 隱 私 (Location privacy): 攻 擊 者 監 控 標 籤 傳 輸 到 讀 取 器 的 資 料, 利 用 兩 者 之 間 回 應 的 訊 息 去 追 蹤 到 標 籤 所 存 放 的 位 置 資 訊 前 向 安 全 性 (Forward secrecy): 保 存 在 標 籤 中 的 資 料 如 果 遭 受 到 破 解, 攻 擊 者 可 以 利 用 這 些 資 料 獲 得 過 去 這 個 標 籤 傳 輸 的 歷 史 紀 錄 竊 聽 攻 擊 (Eavesdropping attack): 由 於 標 籤 到 讀 取 器 之 間 是 利 用 無 線 的 方 式 傳 輸 所 需 要 的 資 訊, 等 於 將 資 料 以 公 開 的 方 式 暴 露 在 外, 攻 擊 者 只 需 要 藉 由 監 控 兩 者 之 間 的 傳 輸, 便 可 得 知 重 要 的 資 訊, 完 成 竊 聽 攻 擊 11

重 送 攻 擊 (Replay attack): 攻 擊 者 監 控 標 籤 並 攔 截 標 籤 和 讀 取 器 之 間 傳 輸 的 內 容, 進 行 修 改 後, 重 新 傳 送 標 籤 或 讀 取 器 所 曾 經 發 送 過 的 資 訊, 利 用 回 應 的 資 料 企 圖 欺 騙 讀 取 器 或 標 籤 以 通 過 認 證 阻 斷 式 服 務 攻 擊 (Denial of service attack): 阻 斷 式 服 務 攻 擊 就 是 針 對 一 個 特 定 的 目 標 傳 送 大 量 的 封 包, 造 成 後 端 主 機 的 癱 瘓 而 無 法 正 常 運 作 在 無 線 射 頻 辨 識 系 統 中, 攻 擊 者 發 佈 大 量 的 訊 息 給 讀 取 器, 企 圖 擾 亂 無 線 射 頻 辨 識 系 統 的 傳 輸, 雖 然 攻 擊 者 無 法 透 過 此 攻 擊 獲 得 標 籤 中 的 資 訊, 但 是 卻 能 讓 標 籤 和 伺 服 器 失 去 同 步, 無 法 成 功 地 完 成 認 證 偽 造 攻 擊 (Impersonation attack): 攻 擊 者 藉 由 攔 截 的 方 式 獲 取 標 籤 的 資 料, 並 且 利 用 這 些 資 料 偽 造 成 為 一 個 合 法 的 標 籤, 企 圖 欺 騙 讀 取 器 通 過 認 證 [8] 中 間 人 攻 擊 (Man-in-the-middle attack): 中 間 人 攻 擊 的 意 思 是 攻 擊 者 竊 聽 兩 者 之 間 的 傳 輸, 在 雙 方 都 不 知 情 的 情 況 下, 將 傳 輸 的 內 容 進 行 修 改, 並 且 將 修 改 過 後 的 內 容 傳 送 給 對 方, 由 於 傳 輸 並 未 因 此 中 斷, 使 用 者 如 果 沒 有 做 好 保 護 的 話, 這 項 攻 擊 將 很 難 會 被 發 現 在 無 線 射 頻 辨 識 系 統 中, 攻 擊 者 扮 演 中 間 人 的 角 色, 冒 充 假 的 伺 服 器 接 收 標 籤 回 傳 的 訊 息, 再 冒 充 成 假 的 標 籤 把 訊 息 傳 給 真 正 的 服 務 器, 那 麼 便 可 以 在 標 籤 和 伺 服 器 兩 端 都 不 知 情 的 情 況 下, 竊 取 或 修 改 傳 輸 的 訊 息 [9] 以 上 就 是 無 線 射 頻 辨 識 系 統 中, 較 常 出 現 的 九 種 安 全 性 的 威 脅 要 能 夠 完 全 避 免 這 些 威 脅 所 帶 來 問 題, 必 須 設 計 一 個 完 善 的 認 證 協 定, 才 能 夠 有 效 的 改 善 下 個 小 節 將 會 針 對 本 篇 論 文 提 出 結 合 二 次 剩 餘 原 理 的 認 證 協 定, 詳 細 的 說 明 其 原 理 以 及 二 次 剩 餘 密 碼 系 統 的 加 密 和 解 密 的 程 序 2.6 二 次 剩 餘 原 理 及 密 碼 系 統 由 於 在 無 線 射 頻 辨 識 系 統 的 環 境 下, 可 能 會 遭 受 到 各 種 不 同 的 攻 擊 者 惡 意 的 破 壞, 然 而 目 前 現 存 的 認 證 協 定 並 沒 有 辦 法 完 全 的 抵 抗, 因 此, 我 們 將 會 利 用 二 次 剩 餘 12

的 原 理 設 計 一 個 改 良 的 認 證 協 定, 使 得 無 線 射 頻 辨 識 系 統 能 夠 更 加 的 安 全 二 次 剩 餘 的 原 理, 簡 單 來 說, 就 是 當 y=x 2 mod n 的 時 候, 若 有 一 整 數 解 x, 那 麼 就 可 以 將 y 稱 為 mod n 的 二 次 剩 餘 (Quadratic Residue) [14] 記 為 QR n, 若 沒 有 存 在 整 數 解, 則 將 y 稱 為 mod n 的 非 二 次 剩 餘 (Quadratic non-residue) 記 為 QNR n 因 為 n 為 兩 個 大 的 奇 質 數 p q 的 乘 積, 如 果 只 知 道 y 和 n 是 無 法 利 用 離 散 對 數 的 方 法 解 出 x 因 為 將 兩 個 大 質 數 分 解 出 來 的 困 難 度 是 相 當 高 的, 即 所 謂 離 散 對 數 的 問 題 二 次 剩 餘 密 碼 系 統 是 將 二 次 剩 餘 的 原 理 代 入 密 碼 系 統 中, 屬 於 公 開 金 鑰 密 碼 系 統, 以 下 將 解 釋 金 鑰 產 生 的 步 驟 以 及 加 解 密 的 程 序 : 金 鑰 產 生 : 任 選 兩 個 大 的 質 數 p 和 q, 這 兩 個 值 必 須 為 奇 數, 並 且 計 算 n=pq 公 開 金 鑰 為 n, 私 密 金 鑰 為 p 和 q 加 密 程 序 : 如 果 x 為 明 文 資 料, 我 們 可 以 將 y=x 2 mod n 看 成 加 密 的 程 序,y 則 是 經 過 加 密 後 所 產 生 的 密 文 資 料 解 密 程 序 : 如 需 將 所 收 到 的 密 文 資 料 進 行 解 密, 假 設 y 為 mod p 和 mod q, 則 先 計 算 a 1 = y (p+1)/4 mod p a 2 = -y (p+1)/4 mod p b 1 =y (q+1)/4 mod q b 2 =y (q+1)/4 mod q, 因 此 能 夠 獲 得 以 下 四 個 解 : (1) x 1 = (a 1, b 1 ) (2) x 2 = (a 1,b 2 ) (3) x 3 = (a 2,b 1 ) (4) x 4 = (a 2,b 2 ) 由 中 國 餘 數 定 理 得 知 x 2 =y mod n 的 四 個 解 為 { x 1, x 2, x 3, x 4 }, 然 而 這 四 個 解 當 中 的 只 有 一 個 解 為 明 文 資 料 x 將 上 述 的 二 次 剩 餘 密 碼 系 統, 舉 個 實 際 的 例 子 來 說, 可 分 為 以 下 三 個 步 驟 : 金 鑰 產 生 : 選 定 兩 個 大 的 質 數 23 和 7, 並 計 算 161=23*7 公 開 金 鑰 為 161, 私 密 金 鑰 為 23 和 7 加 密 程 序 : 13

如 果 24 為 明 文 資 料, 我 們 可 以 將 y = 24 2 mod 161 = 93 看 成 加 密 的 程 序,93 則 是 經 過 加 密 後 所 產 生 的 密 文 資 料 解 密 程 序 : 假 設 93 為 mod 23 和 mod 7 的 二 次 剩 餘, 如 需 將 所 收 到 的 密 文 資 料 進 行 解 密, 則 先 計 算 : a 1 = 93 (23+1)/4 mod 23 1 mod 23 a 2 = -93 (23+1)/4 mod 23 22 mod 23 b 1 = 93 (7+1)/4 mod 7 4 mod 7 b 2 = -93 (7+1)/4 mod 7 3 mod 7 因 此 能 夠 獲 得 以 下 四 個 解 : (1) x 1 = (1 mod 23, 4 mod 7) (2) x 2 = (1 mod 23, 3 mod 7) (3) x 3 = (22 mod 23, 4 mod 7) (4) x 4 = (22 mod 23, 3 mod 7) 將 以 上 四 個 式 子 經 由 中 國 餘 數 定 理 運 算 後 可 得 知,x 2 =y mod n 的 四 個 解 為 { 116, 24, 137, 45}, 然 而 這 四 個 解 當 中, 只 有 一 個 解 為 原 本 的 明 文 資 料, 經 由 比 對 之 後, 可 求 出 明 文 資 料 為 24 14

三 相 關 研 究 在 這 個 章 節 中, 我 們 將 會 介 紹 幾 位 學 者 所 發 表 的 關 於 無 線 射 頻 辨 識 系 統 認 證 協 定 的 相 關 研 究,3.1 介 紹 雜 湊 鎖 定 的 方 法 3.2 介 紹 隨 機 雜 湊 鎖 定 的 方 法 3.3 介 紹 Juels 的 方 法 3.4 介 紹 Wong 的 方 法 3.5 介 紹 Chen 的 方 法 3.6 介 紹 Yeh 的 方 法 3.7 將 本 篇 出 現 的 方 法 以 關 係 圖 方 式 呈 現, 做 一 個 整 理 3.1 雜 湊 鎖 定 方 法 (Hash-Locking scheme) Weis[10] 等 人 於 2003 年 提 出 將 雜 湊 鎖 定 的 方 法 加 入 認 證 協 定 中, 對 於 有 效 率 的 無 線 射 頻 辨 識 系 統 的 認 證 技 術 是 一 大 突 破, 不 過 這 個 方 法 還 是 存 在 會 遭 受 攻 擊 者 竊 聽 和 追 蹤 的 問 題, 圖 3-1 介 紹 了 雜 湊 鎖 定 方 法 詳 細 的 步 驟 伺 服 器 (Server) 讀 取 器 (Reader) 標 籤 (Tag) (1)Query (3)metaID (2)metaID Hash(key)ß metaid 尋 找 相 對 應 的 key (4)(key, ID) (5)key (6)ID 比 對 h(key)?=metaid 如 果 符 合 標 籤 解 鎖 圖 3-1 雜 湊 鎖 定 方 法 (Hash-Locking scheme) 步 驟 一 : 讀 取 器 產 生 Query 訊 號 並 傳 送 給 標 籤 15

步 驟 二 : 標 籤 收 到 Query 訊 號 後, 隨 機 產 生 一 組 金 鑰 key, 計 算 h(key) 成 為 標 籤 的 metaid 後, 傳 送 給 讀 取 器 步 驟 三 : 讀 取 器 將 收 到 的 metaid 回 傳 給 伺 服 器 步 驟 四 : 伺 服 器 收 到 資 料 後, 搜 尋 資 料 庫 內 所 有 相 對 應 的 金 鑰 key, 找 出 對 應 的 key, 將 key 和 標 籤 的 ID 傳 送 給 讀 取 器 步 驟 五 : 讀 取 器 收 到 後, 將 key 回 傳 給 標 籤 步 驟 六 : 標 籤 收 到 後, 計 算 並 比 對 h(key) 是 否 等 於 metaid, 如 果 符 合, 標 籤 解 鎖 並 且 回 傳 ID 給 讀 取 器, 如 果 不 符 合, 則 取 消 認 證 優 點 : 標 籤 的 運 算 量 所 需 記 憶 體 空 間 和 傳 輸 的 資 料 量 極 低 缺 點 : 讀 取 器 和 標 籤 之 間 所 傳 送 的 都 是 未 經 保 護 的 固 定 資 料, 攻 擊 者 經 由 竊 聽 傳 輸 的 內 容 得 知 標 籤 的 內 部 資 料 3.2 隨 機 雜 湊 鎖 定 方 法 (Randomized Hash-Locking scheme) Weis 等 人 於 同 篇 論 文 提 出 另 一 個 隨 機 雜 湊 鎖 定 的 方 法 改 進 了 雜 湊 鎖 定 方 法 的 缺 點, 可 是, 隨 機 雜 湊 鎖 定 的 方 法 雖 然 每 次 傳 輸 的 值 都 會 變 更, 可 以 避 免 攻 擊 者 的 竊 聽 攻 擊, 但 是 此 方 法 在 步 驟 五 當 中, 讀 取 器 回 傳 的 是 未 經 保 護 的 ID k, 攻 擊 者 可 以 經 由 竊 聽 攻 擊 得 知 其 內 容, 圖 3-2 介 紹 了 隨 機 雜 湊 鎖 定 方 法 的 詳 細 步 驟 16

伺 服 器 (Server) 讀 取 器 (Reader) 標 籤 (Tag) (1)Query (3) 請 求 所 有 ID (2)R, h(id k R) 1. 產 生 隨 機 亂 數 R 2. 計 算 h(id k R) (4)ID 1, ID 2,, ID n 將 R 和 個 別 的 ID 連 接 後 進 行 雜 湊 運 算 和 暴 力 搜 尋 (5)ID k 圖 3-2 隨 機 雜 湊 鎖 定 方 法 (Randomized Hash-Locking Scheme) 步 驟 一 : 讀 取 器 產 生 Query 訊 號 並 傳 送 給 標 籤 步 驟 二 : 標 籤 收 到 後 產 生 隨 機 亂 數 R, 計 算 h(id k R) 後 將 R h(id k R) 傳 送 給 讀 取 器 步 驟 三 : 讀 取 器 收 到 資 料 後 向 伺 服 器 請 求 獲 得 所 有 的 ID 步 驟 四 : 伺 服 器 收 到 請 求 後, 將 所 有 標 籤 的 ID 資 料 傳 送 給 讀 取 器 步 驟 五 : 讀 取 器 收 到 後, 將 R 和 個 別 的 ID 連 接 後 進 行 雜 湊 運 算 和 暴 力 搜 尋, 將 ID k 傳 送 給 標 籤, 完 成 這 次 的 認 證 優 點 : 產 生 隨 機 亂 數 的 方 法 可 以 讓 每 次 傳 輸 的 值 都 會 變 更, 使 得 攻 擊 者 無 法 透 過 竊 聽 或 追 蹤 的 方 式 得 知 標 籤 的 資 訊 缺 點 : 由 於 在 步 驟 五 中, 透 過 讀 取 器 回 傳 給 標 籤 的 是 未 經 保 護 的 ID k, 等 於 是 將 明 文 資 料 散 播 在 無 線 的 環 境 下, 攻 擊 者 可 以 經 由 竊 聽 攻 擊 的 方 式 攔 截 讀 取 器 傳 送 給 標 籤 而 得 知 其 內 容 17

3.3 Juels 的 方 法 2004 年 Juels[11] 等 人 提 出 了 一 個 利 用 雜 湊 函 數 和 MAC(Message Authentication Code) 函 數 先 行 產 生 一 組 值 提 供 讀 取 器 在 離 線 的 環 境 下 驗 證 兩 個 標 籤 是 否 相 對 應 的 方 法 這 個 方 法 可 以 應 用 在 藥 品 稽 核 中, 將 兩 個 標 籤 分 別 貼 在 患 者 的 藥 品 罐 子 和 描 述 其 副 作 用 的 清 單 上, 降 低 患 者 誤 食 的 危 險, 提 高 安 全 性, 圖 3-3 介 紹 了 Juels 方 法 的 詳 細 步 驟 伺 服 器 (Server)T A 讀 取 器 (Reader) 標 籤 (Tag)T B (1) left proof r A = f xa [c A ] (2) a = (A,C A,r A ) (3) right proof mb = MAC xb [a, c B ] m AB = MAC xa [a, b] c A c A + 1 (5)b = (B, c B, m B ) (6)m AB (4) b=(b, c B, m B ) c B c B + 1 (7)P AB =( A, B, c A, c B, m AB ) 圖 3-3 Juels 的 方 法 步 驟 一 : 讀 取 器 傳 送 left proof 的 訊 號 給 標 籤 T A 步 驟 二 : 標 籤 T A 計 算 r A = f xa [c A ],f 是 一 個 安 全 的 雜 湊 函 數,x A 為 T A 的 秘 密 金 鑰, c A 為 計 數 器, 然 後 標 籤 T A 將 訊 息 a = (A, c A, r A ) 傳 送 給 讀 取 器 步 驟 三 : 讀 取 器 收 到 a 之 後, 傳 送 right proof 給 標 籤 T B 步 驟 四 : 標 籤 T B 計 算 m B = MAC xb [a, c B ],MAC 是 一 個 將 能 訊 息 加 密 的 驗 證 函 數, x B 為 T B 的 秘 密 金 鑰,c B 為 計 數 器, 然 後 標 籤 T B 將 訊 息 b = (B, c B, m B ) 傳 送 給 讀 取 器 18

步 驟 五 : 收 到 訊 息 b 之 後, 傳 送 給 標 籤 T A 步 驟 六 : 收 到 訊 息 b 之 後, 標 籤 T A 計 算 m AB = MAC xa [a, b] 並 將 m AB 傳 送 給 讀 取 器 步 驟 七 : 讀 取 器 收 到 m AB 後 會 利 用 以 上 步 驟 所 獲 得 的 值, 計 算 P AB = (A, B, c A, c B, m AB ) 完 成 上 述 步 驟 後, 合 法 的 讀 取 器 可 利 用 P AB 和 已 知 兩 個 標 籤 的 認 證 金 鑰 x A 和 x B 去 計 算 a' = (A, c A, f xa (c A )) b' = (B, c B, MAC xb (a, c B )), 然 後 檢 查 m AB 是 否 等 於 MAC xa (a', b') 優 點 : 利 用 雜 湊 函 數 和 MAC 函 數 能 將 要 傳 送 的 值 作 一 個 簡 單 的 保 護, 提 升 一 定 的 安 全 性 缺 點 : 由 於 在 步 驟 二 和 步 驟 三 傳 送 A B, 會 讓 攻 擊 者 輕 易 的 得 知 標 籤 的 來 源 而 無 法 保 護 個 人 隱 私 利 用 非 法 的 標 籤 透 過 重 送 步 驟 二 步 驟 六 和 步 驟 四 的 值 可 找 出 T A 和 T B 的 對 應 關 係, 因 此 無 法 抵 抗 重 送 攻 擊 攻 擊 者 也 可 以 透 過 竊 聽 標 籤 T A T B 和 讀 取 器 傳 輸 的 明 文 (r A, c A ) 和 (m B, (a, c B )), 經 過 比 對 後 可 得 知 x A 和 x B 的 值, 因 此 這 個 方 法 也 無 法 抵 抗 竊 聽 攻 擊 3.4 Wong 的 方 法 Wong[12] 的 方 法 將 標 籤 中 的 電 子 產 品 編 碼 EPC 利 用 了 雜 湊 運 算 中 位 移 的 函 數, 產 生 出 新 的 一 組 虛 擬 的 值 進 行 認 證, 在 首 次 認 證 前 會 將 K pub 和 K priv 分 別 儲 存 在 標 籤 和 伺 服 器 中, 圖 3-4 介 紹 了 Wong 方 法 詳 細 的 步 驟 19

伺 服 器 (Server) 讀 取 器 (Reader) 標 籤 (Tag) K pub =EPC K priv K pub =EPC K priv (3)pseudo-EPC key*= ShiftRight(pseudo-EPC, l) 如 果 (K pub K priv ) = key* 計 算 key=h(key*) (4)key (1)hello (2)pseudo-EPC (5)key 產 生 虛 擬 的 EPC pseudo-epc =ShiftLeft(K pub K priv, l) (7)ACK (6)ACK 比 對 key?=h(k pub K priv ) 如 果 符 合 回 傳 ACK 圖 3-4 Wong 的 方 法 步 驟 一 : 讀 取 器 產 生 Hello 訊 號 並 傳 送 給 標 籤 步 驟 二 : 標 籤 收 到 訊 號 後, 將 內 部 所 儲 存 K pub K priv 向 左 位 移 l 長 度 pseudo-epc = ShiftLeft(K pub K priv, l) 後 回 傳 給 讀 取 器 步 驟 三 : 讀 取 器 將 收 到 的 資 料 回 傳 給 伺 服 器 步 驟 四 : 伺 服 器 收 到 資 料 後, 將 收 到 的 pseudo-epc 向 右 位 移 l 長 度 求 出 key*, 計 算 K pub K priv 是 否 等 於 key*, 如 果 相 等, 則 計 算 key=h(key*) 後, 將 key 傳 送 至 讀 取 器 步 驟 五 : 讀 取 器 將 key 回 傳 給 標 籤 步 驟 六 : 標 籤 收 到 後 比 對 key 值 是 否 等 於 h(k pub K priv ), 若 相 等 則 回 傳 ACK 給 讀 取 器 步 驟 七 : 讀 取 器 將 ACK 傳 送 給 伺 服 器, 完 成 這 次 的 認 證 優 點 : 利 用 雜 湊 運 算 中 使 用 位 移 函 數 產 生 虛 擬 的 電 子 產 品 編 碼, 解 決 隨 機 雜 湊 鎖 定 的 方 法 易 竊 聽 攻 擊 的 威 脅 缺 點 : 20

由 於 認 證 過 程 中 所 需 要 的 虛 擬 電 子 產 品 編 碼 的 是 經 由 位 移 產 生 的, 攻 擊 者 只 要 利 用 暴 力 破 解 的 方 式 在 pseudo-epc / 2 的 次 數 以 內 得 到 正 確 的 EPC 值, 並 追 蹤 到 標 籤 的 位 置, 無 法 保 護 使 用 者 和 位 置 的 隱 私 攻 擊 者 亦 可 利 用 重 送 pseudo-epc 的 方 式 得 到 伺 服 器 回 傳 的 資 訊, 因 為 標 籤 產 生 的 pseudo-epc 是 固 定 的, 所 以 無 法 抵 擋 重 送 攻 擊 的 威 脅 3.5 Chen 的 方 法 2008 年 Chen[13] 等 人 利 用 二 次 剩 餘 的 方 法 結 合 無 線 射 頻 辨 識 系 統 認 證 協 定 提 升 了 隱 私 性 和 安 全 性, 作 者 利 用 二 次 剩 餘 特 性, 傳 送 一 個 不 需 透 過 雜 湊 函 數 所 產 生 大 的 奇 質 數, 攻 擊 者 無 法 透 過 因 式 分 解 得 知 其 內 容 一 開 始 由 伺 服 器 產 生 兩 個 大 的 奇 質 數 p q, 並 且 計 算 n = pq 伺 服 器 隨 機 產 生 一 個 亂 數 r 作 為 當 前 的 認 證 金 鑰, 並 且 將 h(tid) TID r 的 數 值 儲 存 在 標 籤 的 記 憶 體 裡, 伺 服 器 則 會 將 h(tid) TID r r old 儲 存 在 後 端 資 料 庫 中, 在 首 次 的 認 證 過 程 中 的 r old = r, 圖 3-5 介 紹 了 Chen 方 法 詳 細 的 步 驟 伺 服 器 (Server) 讀 取 器 (Reader) 標 籤 (Tag) p, q, n, h(.), PRNG(.) 隨 機 產 生 s n, h(.), PRNG(.) (3) X, R, h(x), h(r), s (1) hello, s (2) X, R, h(x), h(r) x = h(tid) r s X = x 2 mod n R = r 2 mod n 1. 解 開 X = x 2 mod n 和 R= r 2 mod n 得 到 (x 1, x 2, x 3, x 4 ) 和 (r 1, r 2, r 3, r 4 ) 2. 比 對 h(x i )?=h(x) 和 h(r i )?=h(r) 計 算 出 x 和 r 3. 計 算 h(tid) = x r s t 4. 利 用 h(tid) 搜 尋 TID 的 紀 錄 r?= r or r?= r old, 比 對 錯 誤 則 取 消 認 證 5. 產 生 ACK 訊 息 X ack = TID r 或 X ack = TID r old 6.r old = r, r = PRNG(r) (4) h(x ack ) (5) h(x ack ) 1.h(x ack )?=h(tid r) 2.r = PRNG(r) 圖 3-5 Chen 的 方 法 21

步 驟 一 : 讀 取 器 產 生 一 個 隨 機 亂 數 s 並 且 將 hello 訊 號 跟 s 一 起 傳 送 給 標 籤 步 驟 二 : 標 籤 收 到 讀 取 器 所 傳 送 的 s 和 hello 訊 號 之 後, 標 籤 產 生 一 個 隨 機 亂 數 t 計 算 x = h(tid) r s X = x 2 mod n R = r 2 mod n; 並 且 將 (X, R, h(x), h(r)) 當 作 標 籤 的 回 應 傳 送 給 讀 取 器 步 驟 三 : 當 收 到 標 籤 的 回 應 之 後, 讀 取 器 將 收 到 的 值 跟 s 一 起 傳 送 到 伺 服 器 步 驟 四 : 收 到 (X, R, h(x), h(r), s) 之 後, 伺 服 器 將 p q 利 用 中 國 餘 數 定 理 解 開 X = x 2 mod n 和 R =r 2 mod n 分 別 得 到 四 個 根 (x 1,x 2,x 3,x 4 ) 和 (r 1,r 2,r 3,r 4 ) 然 後 比 對 h(x i ) 是 否 等 於 x i 和 h(r i ) 是 否 等 於 h(r),i = 1 到 4, 求 出 x 和 r 的 唯 一 解 然 後 伺 服 器 計 算 h(tid) = x r s, 並 且 將 h(tid) 當 成 一 個 索 引 去 搜 尋 伺 服 器 中 標 籤 的 紀 錄 如 果 找 不 到 相 符 合 的 紀 錄, 則 取 消 這 次 認 證 確 認 計 算 出 的 的 r 是 否 等 於 目 前 伺 服 器 所 儲 存 標 籤 的 r 或 是 r old, 如 果 不 相 等 亦 取 消 這 次 的 認 證 以 下 是 實 際 發 生 時 會 處 理 的 兩 種 情 況 (i) 如 果 計 算 出 的 的 r 跟 目 前 在 伺 服 器 儲 存 的 標 籤 r 互 相 對 應, 伺 服 器 將 計 算 h(x ack ) = h(tid r), 並 將 h(x ack ) 傳 送 到 讀 取 器, 再 將 r 更 新 為 r old, 利 用 虛 擬 亂 數 產 生 器 更 新 r (ii) 如 果 計 算 出 的 r 跟 目 前 在 伺 服 器 儲 存 的 標 籤 r old 互 相 對 應, 伺 服 器 計 算 h(x ack ) = h(tid r old ), 並 將 h(x ack ) 傳 送 到 讀 取 器, 再 利 用 虛 擬 亂 數 產 生 器 更 新 r 步 驟 五 : 將 標 籤 收 到 讀 取 器 回 傳 的 h(x ack ) 後, 驗 證 h(x ack ) 是 否 會 等 於 標 籤 計 算 的 h(tid r), 如 果 相 等, 則 將 標 籤 中 的 r 利 用 虛 擬 亂 數 產 生 器 更 新 優 點 : 改 善 了 無 線 射 頻 辨 識 系 統 的 隱 私 和 安 全 性, 結 合 隨 機 亂 數 和 二 次 剩 餘 的 方 法 讓 攻 擊 者 無 法 輕 易 的 進 行 破 解 缺 點 : 無 法 抵 抗 偽 造 攻 擊, 同 時 也 存 在 位 置 隱 私 可 能 會 洩 漏 和 無 法 抵 擋 重 送 攻 擊 的 問 題 由 於 標 籤 沒 有 產 生 隨 機 亂 數, 使 得 部 分 傳 輸 的 值 是 固 定 的, 因 此 在 認 證 的 過 程 中 很 容 易 遭 受 到 攻 擊 者 破 解 或 比 對 出 其 關 聯 性 22

3.6 Yeh 的 方 法 在 2010 年 Yeh[15] 等 人 提 出 了 利 用 在 標 籤 產 生 隨 機 亂 數, 並 且 將 部 分 內 容 和 隨 機 亂 數 運 算 後 再 傳 輸, 解 決 了 Chen 的 方 法 中 位 置 隱 私 易 遭 受 偽 造 和 重 送 攻 擊 的 威 脅, 提 升 了 認 證 的 安 全 性 Yeh 的 方 法 分 成 兩 個 階 段, 初 始 階 段 和 認 證 階 段, 圖 3-6 介 紹 了 Yeh 方 法 詳 細 的 步 驟 3.6.1 初 始 階 段 伺 服 器 產 生 兩 個 大 的 奇 質 數 p q, 並 且 計 算 n = pq 伺 服 器 隨 機 產 生 一 個 亂 數 r 作 為 當 前 的 認 證 金 鑰, 並 且 將 h(tid) TID r 的 數 值 儲 存 在 標 籤 的 記 憶 體 裡, 伺 服 器 則 會 將 h(tid) TID r r old 儲 存 在 後 端 資 料 庫 中, 在 首 次 的 認 證 過 程 中 的 r old = r 3.6.2 認 證 階 段 Yeh 的 方 法, 如 圖 3-6 所 示, 是 由 讀 取 器 經 由 伺 服 器 認 證 一 個 標 籤 的 是 否 合 法 的 步 驟 步 驟 一 : 讀 取 器 產 生 一 個 隨 機 亂 數 s 並 且 將 hello 訊 號 跟 s 一 起 傳 送 給 標 籤 步 驟 二 : 標 籤 收 到 讀 取 器 所 傳 送 的 s 和 hello 訊 號 之 後, 標 籤 產 生 一 個 隨 機 亂 數 t 計 算 x = h(tid) r t s y = r t X = x 2 mod n R = (r 2 mod n ) t, 和 T = t 2 mod n; 並 且 將 (X, R, T, h(x), h(y), h(t)) 當 作 標 籤 的 回 應 傳 送 給 讀 取 器 步 驟 三 : 當 收 到 標 籤 的 回 應 之 後, 讀 取 器 將 收 到 的 值 跟 s 一 起 傳 送 到 伺 服 器 步 驟 四 : 收 到 (X, R, T, h(x), h(y), h(t), s) 之 後, 伺 服 器 將 p q 利 用 中 國 餘 數 定 理 解 開 X = x 2 mod n 和 T = t 2 mod n 分 別 得 到 四 個 根 (x 1,x 2,x 3,x 4 ) 和 (t 1,t 2,t 3,t 4 ) 然 後 比 對 h(x i ) 是 否 等 於 x i 和 h(t i ) 是 否 等 於 h(t),i = 1 到 4, 求 出 x 和 t 的 唯 一 解 接 著 伺 服 器 計 算 R t = (r 2 mod n) 並 且 將 p q 利 用 中 國 餘 數 定 理 解 開 獲 得 四 個 根 (r 1, r 2, r 3, r 4 ) 並 且 分 別 比 對,i = 1 到 4 的 h(r i t) 和 h(y) 是 否 相 等, 求 出 r 的 唯 一 解 然 後 伺 服 器 計 算 h(tid) = x r t s, 並 且 將 h(tid) 當 成 一 個 索 引 去 搜 尋 伺 服 器 中 標 籤 的 紀 錄 如 果 找 不 到 相 符 合 的 紀 錄, 則 取 消 這 次 認 證 確 認 計 算 出 的 的 r 是 否 等 於 目 前 伺 服 器 所 儲 存 標 籤 的 r 或 是 23

r old, 如 果 不 相 等 亦 取 消 這 次 的 認 證 以 下 是 實 際 發 生 時 會 處 理 的 兩 種 情 況 (i) 如 果 計 算 出 的 的 r 跟 目 前 在 伺 服 器 儲 存 的 標 籤 r 互 相 對 應, 伺 服 器 將 計 算 h(x ack ) = h(tid t r), 並 將 h(x ack ) 傳 送 到 讀 取 器, 再 將 r 更 新 為 r old, 利 用 虛 擬 亂 數 產 生 器 更 新 r (ii) 如 果 計 算 出 的 r 跟 目 前 在 伺 服 器 儲 存 的 標 籤 r old 互 相 對 應, 伺 服 器 計 算 h(x ack ) = h(tid t r old ), 並 將 h(x ack ) 傳 送 到 讀 取 器, 再 利 用 虛 擬 亂 數 產 生 器 更 新 r 步 驟 五 : 將 標 籤 收 到 讀 取 器 回 傳 的 h(x ack ) 後, 驗 證 h(x ack ) 是 否 會 等 於 標 籤 計 算 的 h(tid t r), 如 果 相 等, 則 將 標 籤 中 的 r 利 用 虛 擬 亂 數 產 生 器 更 新 伺 服 器 (Server) 讀 取 器 (Reader) 標 籤 (Tag) p, q, n, h(.), PRNG(.) 隨 機 產 生 s n, h(.), PRNG(.) (3) X, R, T, h(x), h(y), h(t), s 1. 解 開 X = x 2 mod n 和 T = t 2 mod n 得 到 (x 1, x 2, x 3, x 4 ) 和 (t 1, t 2, t 3, t 4 ) 2. 比 對 h(x i )?=h(x) 和 h(t i )?=h(t) 計 算 出 x 和 t 3. 計 算 R = (r 2 mod n) t, 得 到 (r 1, r 2, r 3, r 4 ) 4. 比 對 h(r i t)?=h(y), 得 到 r 5. 計 算 h(tid) = x r s t 6. 利 用 h(tid) 搜 尋 TID 的 紀 錄 r?= r or r?= r old, 比 對 錯 誤 則 取 消 認 證 7. 產 生 ACK 訊 息 X ack = TID t r 或 X ack = TID t r old 8.r old = r, r = PRNG(r) (4) h(x ack ) (1) hello, s (2) X, R, T, h(x), h(y), h(t) (5) h(x ack ) 隨 機 產 生 亂 數 t x = h(tid) r t s y = r t X = x 2 mod n R = (r 2 mod n) t T = t 2 mod n 1.h(x ack )?=h(tid t r) 2.r = PRNG(r) 圖 3-6 Yeh 的 方 法 優 點 : 利 用 在 標 籤 產 生 的 隨 機 亂 數 t, 讓 步 驟 一 步 驟 二 和 步 驟 五 中 傳 輸 的 資 料 在 每 次 認 證 過 程 中 都 會 變 更, 改 善 了 Chen 的 方 法 無 法 抵 擋 位 置 隱 私 無 法 抵 擋 重 送 攻 擊 和 偽 造 攻 擊 的 問 題 缺 點 : 24

雖 然 可 抵 擋 的 攻 擊 種 類 增 加, 但 是 從 另 一 個 角 度 來 看, 整 個 認 證 過 程 中 傳 輸 的 資 料 量 和 標 籤 的 計 算 量 都 有 過 高 的 問 題, 違 背 了 有 效 率 的 無 線 射 頻 辨 識 系 統 認 證 協 定 的 設 計 理 念 3.7 主 要 相 關 研 究 關 係 圖 本 節 會 將 上 述 所 提 及 的 各 種 無 線 射 頻 辨 識 系 統 認 證 協 定 的 方 法 依 照 年 份 及 其 關 連 性 以 關 係 圖 的 方 式 呈 現, 可 以 快 速 的 回 顧 這 幾 個 方 法 之 間 的 差 異 性 如 圖 3-7 所 示, Wei 等 人 於 2003 年 提 出 雜 湊 鎖 定 和 隨 機 雜 湊 鎖 定 的 方 法, 雜 湊 鎖 定 方 法 是 最 早 將 雜 湊 函 數 的 概 念 加 入 到 無 線 射 頻 辨 識 系 統 的 認 證 協 定 中, 但 是 由 於 讀 取 器 和 標 籤 之 間 所 傳 送 的 都 是 未 經 保 護 的 固 定 資 料, 攻 擊 者 可 以 經 由 竊 聽 傳 輸 的 內 容 得 知 標 籤 的 內 部 資 料 隨 機 雜 湊 鎖 定 的 方 法 是 在 標 籤 加 入 隨 機 亂 數 產 生 器, 將 所 要 傳 送 的 資 料 和 一 個 隨 機 亂 數 做 雜 湊 運 算 讓 每 次 傳 輸 的 值 都 會 變 更, 可 以 避 免 攻 擊 者 的 竊 聽 攻 擊, 但 是 傳 送 的 資 料 太 固 定, 易 遭 受 攻 擊 者 竊 聽 的 風 險 Juels 等 人 在 2004 年 提 出 利 用 將 雜 湊 函 數 和 MAC 函 數 先 行 產 生 一 組 值 提 供 讀 取 器 在 離 線 的 環 境 下 驗 證 兩 個 標 籤 是 否 相 對 應 的 方 法 Wong 等 人 於 2006 年 應 用 雜 湊 運 算 中 位 移 函 數 產 生 虛 擬 的 電 子 產 品 編 碼, 解 決 隨 機 雜 湊 鎖 定 的 方 法 易 竊 聽 攻 擊 的 威 脅 Chen 等 人 於 2008 年 利 用 二 次 剩 餘 的 方 法 增 加 了 無 線 射 頻 辨 識 系 統 認 證 協 定 的 隱 私 安 全 2010 年 Yeh 等 人 提 出 了 利 用 在 標 籤 產 生 隨 機 亂 數, 並 且 將 部 分 內 容 和 隨 機 亂 數 運 算 後 再 傳 輸, 解 決 了 Chen 的 方 法 中 位 置 隱 私 易 遭 受 偽 造 和 重 送 攻 擊 的 威 脅, 提 升 了 認 證 的 安 全 性, 最 後 則 是 本 篇 所 提 出 利 用 標 籤 連 接 兩 個 相 同 長 度 的 值, 伺 服 器 可 以 快 速 的 拆 解 得 知 其 內 容 的 特 性, 降 低 Yeh 的 方 法 的 計 算 量, 而 且 同 樣 能 滿 足 相 同 的 安 全 性 質 25

2003-Wei:Hash- Locking[10] 2003-Wei:Randomized Hash-Locking[10] 2004-Juels:hash and MAC function[11] 2006-Wong:shift[12] 2008-Chen: Quadratic residues[13] 2010-Yeh:Tag generate a random number[15] 2010-Chiou:Contact two value of the same length 圖 3-7 RFID 主 要 相 關 研 究 關 係 圖 26

四 我 們 提 出 的 方 法 在 Yeh 的 方 法 中, 認 證 過 程 花 費 過 多 的 計 算 成 本, 在 本 篇 論 文 中, 為 了 減 少 伺 服 器 和 標 籤 的 計 算 花 費, 我 們 提 出 了 減 少 二 次 剩 餘 平 方 和 雜 湊 函 數 的 方 法 認 證 協 定 分 成 初 始 和 認 證 兩 個 階 段, 我 們 的 方 法 利 用 連 接 運 算 符 號 連 接 兩 個 固 定 長 度 的 值 當 資 料 傳 送 至 伺 服 器 時, 可 以 快 速 地 將 其 分 解 成 兩 個 需 要 的 資 料 4.1 符 號 及 參 數 表 表 4-1 介 紹 本 篇 論 文 的 認 證 協 定 中 所 會 出 現 的 符 號 以 及 該 符 號 的 相 關 說 明 表 4-1 符 號 及 參 數 表 符 號 說 明 p, q 奇 質 數 n s t h (.) PRNG(.) TID h(tid) r 由 p q 的 乘 積 所 組 成 讀 取 器 所 產 生 的 隨 機 亂 數 標 籤 所 產 生 的 隨 機 亂 數 單 向 雜 湊 函 數 虛 擬 亂 數 產 生 器 標 籤 的 編 號 將 標 籤 的 編 號 做 雜 湊, 用 來 作 為 伺 服 器 的 索 引 伺 服 器 和 標 籤 共 享 當 前 的 認 證 金 鑰 r old 儲 存 在 伺 服 器 的 舊 認 證 金 鑰 27

XOR 運 算 符 號 連 接 運 算 符 號 x, y, z 標 籤 經 過 認 證 運 算 過 後 的 參 數 x, y, z 伺 服 器 經 過 認 證 運 算 過 後 的 參 數 X ack 伺 服 器 傳 給 標 籤 的 回 應 X 二 次 剩 餘 運 算 後 產 生 的 值 4.2 環 境 變 數 設 定 無 線 射 頻 辨 識 系 統 必 須 運 作 於 線 上 (On-Line) 的 環 境 裡 伺 服 器 讀 取 器 和 標 籤 必 須 要 保 持 連 線 的 狀 態, 才 能 完 成 一 次 的 認 證 然 而 在 我 們 的 方 法 裡,TID t s r 的 值 皆 為 相 同 的 固 定 長 度, 例 如 :512 1024 或 更 長 位 元 4.3 初 始 階 段 首 先, 伺 服 器 產 生 兩 個 大 的 奇 質 數 p q, 並 且 計 算 n = pq 伺 服 器 隨 機 產 生 一 個 亂 數 r 作 為 第 一 次 的 認 證 金 鑰, 並 且 將 TID r 的 數 值 儲 存 在 標 籤 的 記 憶 體 裡, 伺 服 器 則 會 將 TID r r old 儲 存 在 後 端 資 料 庫 中 在 首 次 的 認 證 過 程 中 的 r old = r 4.4 認 證 階 段 認 證 階 段, 如 圖 4-1 表 示, 我 們 的 方 法 是 利 用 讀 取 器 與 伺 服 器 經 由 五 個 步 驟 認 證 一 個 標 籤 是 否 合 法 步 驟 一 : 讀 取 器 利 用 虛 擬 亂 數 產 生 器, 產 生 一 個 亂 數 s, 並 且 將 s 跟 hello 訊 號 傳 送 到 要 認 證 的 標 籤 中 28

步 驟 二 : 標 籤 收 到 讀 取 器 傳 送 的 s 和 hello 訊 號 之 後, 隨 機 產 生 一 個 亂 數 t, 計 算 y = r t s z = TID t x = y z X = x 2 mod n, 並 且 將 X h(x) 傳 送 至 讀 取 器 步 驟 三 : 收 到 標 籤 的 回 應 之 後, 讀 取 器 就 會 將 標 籤 傳 送 的 資 料 X h(x) 跟 亂 數 s 一 起 傳 送 至 伺 服 器 步 驟 四 : 收 到 讀 取 器 傳 送 的 資 料 X h(x) s 之 後, 伺 服 器 利 用 中 國 餘 數 定 理 解 開 X = x 2 mod n 後 獲 得 四 個 根 (x 1, x 2, x 3, x 4 ) 比 較 h(x i )?= h(x),i = 1 到 4, 找 出 對 應 的 x 的 值, 再 將 x 從 中 間 分 解 得 到 y z, 計 算 t = TID z 與 r = y t s 比 對 r =? r 或 r =? r old, 若 不 相 等 則 會 取 消 認 證, 而 相 等 則 代 表 伺 服 器 認 證 標 籤 成 功 認 證 成 功 後, 計 算 X ack = TID t r 或 X ack = TID t r old, 將 h(x ack ) 傳 送 至 讀 取 器 將 r old 更 新 成 r 並 且 利 用 虛 擬 亂 數 產 生 器 產 生 出 新 的 r 以 下 是 實 際 發 生 時 會 處 理 的 兩 種 情 況 (i) 如 果 計 算 出 的 r 跟 目 前 在 伺 服 器 儲 存 的 標 籤 r 互 相 對 應, 伺 服 器 計 算 h(x ack ) = h(tid t r), 並 將 h(x ack ) 傳 送 到 讀 取 器, 並 且 將 r 更 新 為 r old, 再 利 用 虛 擬 亂 數 產 生 器 更 新 r (ii) 如 果 計 算 出 的 r 跟 目 前 在 伺 服 器 儲 存 的 標 籤 r old 互 相 對 應, 伺 服 器 計 算 h(x ack ) = h(tid t r old ), 並 將 h(x ack ) 傳 送 到 讀 取 器, 再 利 用 虛 擬 亂 數 產 生 器 更 新 r 步 驟 五 : 讀 取 器 將 X ack 傳 送 至 標 籤 後 計 算 h(tid t r), 比 對 h(x ack ) 是 否 等 於 h(tid t r), 假 如 認 證 成 功, 則 標 籤 將 會 利 用 相 同 的 虛 擬 亂 數 產 生 器 將 r 更 新, 為 下 次 認 證 所 使 用 29

伺 服 器 (Server) 讀 取 器 (Reader) 標 籤 (Tag) p, q, n, h(.), PRNG(.) 隨 機 產 生 s n, h(.), PRNG(.) TID r rold 1. 解 開 X = x 2 mod n 得 到 (x 1,x 2,x 3,x 4 ) 2. 比 對 h(x i )?=h(x) 計 算 出 x 3. 解 開 x 得 到 y 和 z 4.t = TID z 5.r = y t s 6. r?= r or r?= r old 比 對 錯 誤 則 取 消 認 證 7. 產 生 ACK 訊 息, X ack = TID t r 或 X ack = TID t r old 8.r old = r, r = PRNG(r) (3) X, h(x), s (4) h(x ack ) (1) hello, s (2) X, h(x) (5) h(x ack ) 圖 4-1 我 們 的 方 法 TID 產 生 隨 機 亂 數 t y = r t s z =TID t x = y z X = x 2 mod n r 1.h(x ack )?=h(tid t r) 2. r = PRNG (r) 30

五 分 析 在 這 個 章 節 中 將 會 比 較 我 們 的 方 法 Chen 和 Yeh 方 法 計 算 量 和 安 全 性 質 的 差 異 性 在 計 算 量 方 面, 會 將 整 個 認 證 過 程 中 的 二 次 剩 餘 雜 湊 函 數 XOR 運 算 函 數 虛 擬 亂 數 產 生 器 和 連 接 運 算 函 數 的 計 算 次 數 和 Chen 以 及 Yeh 的 方 法 比 較 分 析 在 安 全 性 質 方 面, 會 將 2.5 節 所 提 到 的 隱 私 性 和 安 全 性 的 威 脅 進 行 詳 細 的 分 析 5.1 計 算 量 的 分 析 本 節 將 會 針 對 不 同 RFID 認 證 技 術 所 需 計 算 量 進 行 分 析 在 表 5-1 之 中, 分 別 比 較 了 Chen 方 法 Yeh 方 法 和 我 們 所 提 出 的 方 法 的 計 算 量 其 中 我 們 的 方 法 在 標 籤 和 伺 服 器 各 別 只 需 要 1 次 的 二 次 剩 餘 運 算, 優 於 Chen 方 法 各 需 要 2 次 和 Yeh 方 法 各 需 要 3 次 然 而, 雜 湊 函 數 的 運 算 次 數, 在 我 們 的 方 法 標 籤 和 伺 服 器 當 中 分 別 使 用 了 2 次 以 及 5 次 的 運 算, 優 於 Chen 的 方 法 標 籤 和 伺 服 器 分 別 使 用 3 次 和 9 次 的 運 算 和 Yeh 的 方 法 標 籤 和 伺 服 器 分 別 使 用 4 次 和 13 次 的 運 算, 而 其 他 種 類 運 算 的 次 數 也 明 顯 減 少 我 們 的 方 法 主 要 的 改 善 在 於 降 低 二 次 剩 餘 的 計 算 量, 因 為 二 次 剩 餘 計 算 量 的 花 費 遠 大 於 雜 湊 函 數 XOR 運 算 函 數 和 其 他 運 算 函 數 的 計 算 量 在 5.2 節 將 會 介 紹 我 們 的 方 法 安 全 性 質 的 分 析 31

表 5-1 計 算 量 的 分 析 標 籤 伺 服 器 計 算 量 分 析 Q H X P C Chen 的 方 法 2 3 3 1 0 Yeh 的 方 法 3 4 7 1 0 我 們 的 方 法 1 2 5 1 1 Chen 的 方 法 2 9 3 1 0 Yeh 的 方 法 3 13 7 1 0 我 們 的 方 法 1 5 5 1 1 Q: 二 次 剩 餘 X:XOR 運 算 函 數 C: 連 接 運 算 函 數 H: 雜 湊 函 數 P: 虛 擬 亂 數 產 生 器 5.2 安 全 性 質 的 分 析 本 章 節 討 論 我 們 的 方 法 是 否 能 避 免 無 線 射 頻 辨 識 系 統 較 易 遭 受 到 威 脅 或 攻 擊, 進 行 安 全 性 質 的 分 析 1. 達 到 資 料 機 密 性 (Data secrecy): 標 籤 中 的 資 料 (TID, r ) 不 會 暴 露 在 傳 輸 過 程 中, 只 有 合 法 有 效 的 伺 服 器 才 可 以 將 p q 利 用 中 國 餘 數 定 理 得 到 正 確 的 x r t 值 由 於 在 步 驟 二 所 傳 輸 的 h(x) 是 一 個 雜 湊 函 數 X 是 二 次 剩 餘 函 數, 兩 者 的 內 容 皆 無 法 輕 易 的 變 更, 滿 足 資 料 機 密 性 2. 保 護 使 用 者 隱 私 (User privacy): 利 用 標 籤 所 產 生 的 隨 機 亂 數 t, 讓 標 籤 在 認 證 的 過 程 中 傳 送 給 讀 取 器 的 內 容 都 是 會 改 變 的, 攻 擊 者 無 法 透 過 攔 截 或 修 改 步 驟 二 或 步 驟 五 的 資 料 追 蹤 到 標 籤 持 有 人 的 位 置, 保 護 使 用 者 的 隱 私 3. 保 護 位 置 隱 私 (Location privacy): 在 我 們 的 方 法 裡, 標 籤 所 產 生 的 隨 機 亂 數 t, 在 每 一 次 標 籤 的 認 證 過 程 中 都 是 會 改 變 的, 攻 擊 者 無 法 輕 易 地 預 測 內 容 如 果 攻 擊 者 攔 截 或 修 改 步 驟 二 和 步 驟 五 的 資 料, 也 無 法 追 蹤 到 標 籤 的 位 置 資 訊 4. 前 向 安 全 (Forward secrecy): 32

在 伺 服 器 或 是 標 籤 中 TID r 的 值 都 是 不 會 暴 露 在 傳 輸 過 程, 即 使 攻 擊 者 破 解 標 籤 後 得 到 其 內 部 資 訊, 會 因 為 讀 取 器 和 標 籤 分 別 所 產 生 的 隨 機 亂 數 s t 使 得 標 籤 所 傳 輸 的 資 料 在 每 次 的 傳 輸 過 程 都 沒 有 關 聯 性, 所 以 攻 擊 者 無 法 在 破 解 標 籤 的 狀 況 下, 進 而 得 知 先 前 所 傳 輸 的 內 容, 確 保 了 前 向 安 全 性 5. 竊 聽 攻 擊 (Eavesdropping attack): 攻 擊 者 無 法 透 過 竊 聽 讀 取 器 和 標 籤 之 間 利 用 無 線 的 方 式 所 傳 輸 的 資 料, 獲 得 重 要 的 資 訊 由 於 傳 輸 的 內 容 都 是 經 由 雜 湊 函 數 所 保 護, 因 此 能 夠 成 功 的 抵 禦 竊 聽 攻 擊 的 威 脅 6. 重 送 攻 擊 (Replay attack): 在 我 們 提 出 的 方 法 裡 亦 是 利 用 隨 機 亂 數 s t 讓 每 次 標 籤 或 伺 服 器 在 認 證 過 程 中 所 傳 輸 的 資 料 都 不 一 樣, 攻 擊 者 無 法 藉 由 重 複 傳 送 步 驟 二 的 h(x) X 或 步 驟 五 的 h(x ack ) 去 騙 取 通 過 認 證, 因 此 能 夠 抵 擋 重 送 攻 擊 7. 阻 斷 式 服 務 攻 擊 (Denial of service attack): 伺 服 器 會 儲 存 舊 的 值 r old, 目 的 就 是 為 了 恢 復 同 步 的 機 制 如 果 攻 擊 者 中 斷 了 步 驟 五 的 傳 輸, 使 得 伺 服 器 將 r 更 新, 而 標 籤 尚 未 更 新 r, 這 時 候 標 籤 和 伺 服 器 則 會 產 生 同 步 問 題 標 籤 在 下 次 的 認 證 過 程 中 利 用 r 作 為 認 證 金 鑰, 當 資 料 傳 給 後 端 資 料 庫 時, 伺 服 器 會 利 用 儲 存 的 r old 產 生 相 對 應 的 資 料 跟 標 籤 恢 復 同 步, 進 行 下 一 步 的 認 證, 因 此 可 以 抵 擋 阻 斷 式 服 務 攻 擊 8. 偽 造 攻 擊 (Impersonation attack): 只 有 合 法 的 伺 服 器 才 能 利 用 p q 藉 由 中 國 餘 數 定 理 產 生 x, 再 透 過 TID 計 算 出 正 確 的 X ack 由 於 標 籤 每 次 傳 輸 的 資 料 都 是 利 用 隨 機 亂 數 t 所 組 成 的, 資 料 在 每 次 認 證 過 程 中 都 會 變 更, 所 以 攻 擊 者 無 法 利 用 標 籤 的 回 應 取 得 內 部 資 訊, 也 無 法 成 功 地 偽 裝 成 一 個 合 法 的 標 籤 9. 中 間 人 攻 擊 (Man-in-the-middle attack ): 攻 擊 者 扮 演 中 間 人 的 角 色, 接 收 步 驟 二 經 由 標 籤 傳 送 給 讀 取 器 的 資 料, 然 而 我 們 所 傳 送 的 X 是 二 次 剩 餘 函 數 所 計 算 出 來 的 值, 攻 擊 者 無 法 竊 取 或 修 改 其 中 的 內 容, 因 此, 我 們 可 以 抵 擋 中 間 人 攻 擊 的 威 脅 由 以 上 的 安 全 性 分 析 結 果 得 知, 我 們 的 方 法 能 夠 抵 擋 無 線 射 頻 辨 識 系 統 中 常 見 的 33

隱 私 性 和 安 全 性 的 威 脅 表 5-2 將 Chen 的 方 法 Yeh 的 方 法 和 我 們 的 方 法 做 安 全 性 質 的 比 較 如 表 所 示,Chen 的 方 法 無 法 抵 抗 使 用 者 隱 私 和 位 置 隱 私 的 追 蹤 重 送 攻 擊 和 偽 造 攻 擊, 而 Yeh 的 方 法 和 我 們 的 方 法 針 對 攻 擊 者 在 無 線 射 頻 辨 識 系 統 中 的 九 種 安 全 性 方 面 的 威 脅, 都 能 夠 達 到 一 定 水 準 的 防 護 Yeh 的 方 法 和 我 們 的 方 法 都 能 夠 滿 足 相 同 的 安 全 性 質, 但 是 在 整 體 計 算 量 的 部 分,Yeh 方 法 的 計 算 量 明 顯 的 大 於 我 們 方 法 的 計 算 量 我 們 的 方 法 不 但 成 功 的 減 少 伺 服 器 和 標 籤 的 計 算 量, 還 能 夠 滿 足 相 同 的 安 全 性 質, 提 供 一 定 的 安 全 防 護, 故 我 們 的 方 法 是 個 有 效 率 的 認 證 協 定 表 5-2 安 全 性 質 分 析 安 全 分 析 Chen 的 方 法 Yeh 的 方 法 我 們 的 方 法 資 料 機 密 性 O O O 使 用 者 隱 私 X O O 位 置 隱 私 X O O 前 向 安 全 O O O 竊 聽 攻 擊 O O O 重 送 攻 擊 X O O 阻 斷 式 服 務 攻 擊 O O O 偽 造 攻 擊 X O O 中 間 人 攻 擊 O O O 34

結 論 本 篇 論 文 主 要 的 研 究 係 針 對 無 線 傳 輸 過 程 中 可 能 會 遭 受 到 的 安 全 威 脅 進 行 改 善, 並 且 透 過 安 全 性 和 計 算 量 分 析, 滿 足 相 同 的 安 全 防 護 並 且 能 夠 減 少 伺 服 器 和 標 籤 的 運 算 量 我 們 的 方 法 將 二 次 剩 餘 的 密 碼 系 統 應 用 在 其 中, 利 用 離 散 場 域 中 了 將 一 個 整 數 取 平 方 根 是 一 件 相 當 困 難 的 特 性, 設 計 了 一 個 更 安 全 的 認 證 協 定 而 我 們 的 方 法 相 較 於 Yeh 的 方 法 的 改 善 之 處 在 整 個 認 證 過 程 中 總 共 能 減 少 4 次 的 二 次 剩 餘 運 算 以 及 10 次 的 雜 湊 函 數 計 算 量, 不 僅 解 決 了 Yeh 的 方 法 中 標 籤 和 伺 服 器 計 算 量 過 高 的 問 題, 亦 能 滿 足 相 同 的 安 全 性 質, 抵 擋 隱 私 性 和 安 全 性 的 威 脅 期 望 在 未 來, 我 們 所 提 出 的 認 證 協 定 能 夠 應 用 在 需 要 較 高 的 安 全 性 並 講 求 效 率 的 無 線 射 頻 辨 識 系 統 環 境 之 中 ( 例 如 : 汽 車 的 智 慧 鑰 匙 ), 讓 整 體 的 隱 私 安 全 能 夠 得 到 更 多 的 保 障 35

參 考 文 獻 [1] C.M. Roberts, Radio frequency identification (RFID), Computers & Security, Vol.25, No. 1, pp. 18 26, 2006. [2] P. Rotter, A framework for assessing RFID system security and privacy risks, IEEE Pervasive Computing, Vol.7, No. 2, pp. 70 77, 2008. [3] C. L. Turner, A. C. Casbard, and M. F. Murphy, Barcode technology: its role in increasing the safety of blood transfusion, Transfusion, Vol.43, Issue 9, pp.1200-1209, 2003. [4] A. Juels, RFID security and privacy: a research survey, IEEE Journal on Selected Areas in Communications, Vol.24, No. 2, pp. 381 394, 2006. [5] 朱 耀 明, 林 財 世, 淺 談 RFID 無 線 射 頻 辨 識 系 統 技 術, 生 活 科 技 教 育 月 刊, 三 十 八 卷, 第 二 期, pp.73-87, 2005. [6] EPC global, http://www.gs1.org./epcglobal. [7] K. Finkenzeller, RFID Handbook: fundamentals and applications in contactless smart cards and identification, John Wiley & Sons, 2nd edition, 2003. [8] B. Song and C. J. Mitchell, RFID authentication protocol for low-cost tags, Wireless Network Security (WISEC), pp. 140-147, 2008. [9] D. Duc and K. Kim, Securing HB+ against GRS man-in-the-middle attack, Symposium on Cryptography and Information Security (SCIS), pp.123-127, 2007. [10] S.A. Weis, S.E. Sarma, R.L. Rivest, and D.W. Engels, Security and privacy aspects of low-cost radio frequency identification system, Prof. of First International Conference on Security in Pervasive Computing (SPC), LNCS 2802, pp. 454-469, 2003. [11] A. Juels, Yoking-Proofs for RFID tags, Pervasive Computing and Communications Workshops, pp. 138-143, 2004. 36

[12] H.M. Wong, C.L. Hui and C.K. Chan, Cryptography and authentication on RFID passive tags for apparel products, Computer in Industry, Vol.57 Issue 4, pp. 342-349, 2006. [13] Y. Chen, J.S. Chou and H.M. Sun, A novel mutual-authentication scheme based on quadratic residues for RFID systems, Computer Network, Vol.52, Issue 12, pp. 2373-2380, August 2008. [14] C.I Fan and C.L Lei, Efficient blind signature scheme based on quadratic residues, Electronics Letters, Vol.32, pp. 811-813, 1996. [15] T.C. Yeh, C.H. Wu and Y.M. Tseng, Improvement of the RFID authentication scheme based on quadratic residues, Computer Communications, Vol.34, Issue 3, pp. 337-341, 2010. 37